LLVM  7.0.0svn
LoopInstSimplify.cpp
Go to the documentation of this file.
1 //===- LoopInstSimplify.cpp - Loop Instruction Simplification Pass --------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This pass performs lightweight instruction simplification on loop bodies.
11 //
12 //===----------------------------------------------------------------------===//
13 
16 #include "llvm/ADT/STLExtras.h"
17 #include "llvm/ADT/SmallPtrSet.h"
18 #include "llvm/ADT/SmallVector.h"
19 #include "llvm/ADT/Statistic.h"
22 #include "llvm/Analysis/LoopInfo.h"
24 #include "llvm/Analysis/LoopPass.h"
27 #include "llvm/IR/BasicBlock.h"
28 #include "llvm/IR/CFG.h"
29 #include "llvm/IR/DataLayout.h"
30 #include "llvm/IR/Dominators.h"
31 #include "llvm/IR/Instruction.h"
32 #include "llvm/IR/Instructions.h"
33 #include "llvm/IR/Module.h"
34 #include "llvm/IR/PassManager.h"
35 #include "llvm/IR/User.h"
36 #include "llvm/Pass.h"
37 #include "llvm/Support/Casting.h"
38 #include "llvm/Transforms/Scalar.h"
40 #include <algorithm>
41 #include <utility>
42 
43 using namespace llvm;
44 
45 #define DEBUG_TYPE "loop-instsimplify"
46 
47 STATISTIC(NumSimplified, "Number of redundant instructions simplified");
48 
49 static bool simplifyLoopInst(Loop &L, DominatorTree &DT, LoopInfo &LI,
50  AssumptionCache &AC,
51  const TargetLibraryInfo &TLI) {
52  const DataLayout &DL = L.getHeader()->getModule()->getDataLayout();
53  SimplifyQuery SQ(DL, &TLI, &DT, &AC);
54 
55  // On the first pass over the loop body we try to simplify every instruction.
56  // On subsequent passes, we can restrict this to only simplifying instructions
57  // where the inputs have been updated. We end up needing two sets: one
58  // containing the instructions we are simplifying in *this* pass, and one for
59  // the instructions we will want to simplify in the *next* pass. We use
60  // pointers so we can swap between two stably allocated sets.
61  SmallPtrSet<const Instruction *, 8> S1, S2, *ToSimplify = &S1, *Next = &S2;
62 
63  // Track the PHI nodes that have already been visited during each iteration so
64  // that we can identify when it is necessary to iterate.
65  SmallPtrSet<PHINode *, 4> VisitedPHIs;
66 
67  // While simplifying we may discover dead code or cause code to become dead.
68  // Keep track of all such instructions and we will delete them at the end.
70 
71  // First we want to create an RPO traversal of the loop body. By processing in
72  // RPO we can ensure that definitions are processed prior to uses (for non PHI
73  // uses) in all cases. This ensures we maximize the simplifications in each
74  // iteration over the loop and minimizes the possible causes for continuing to
75  // iterate.
76  LoopBlocksRPO RPOT(&L);
77  RPOT.perform(&LI);
78 
79  bool Changed = false;
80  for (;;) {
81  for (BasicBlock *BB : RPOT) {
82  for (Instruction &I : *BB) {
83  if (auto *PI = dyn_cast<PHINode>(&I))
84  VisitedPHIs.insert(PI);
85 
86  if (I.use_empty()) {
87  if (isInstructionTriviallyDead(&I, &TLI))
88  DeadInsts.push_back(&I);
89  continue;
90  }
91 
92  // We special case the first iteration which we can detect due to the
93  // empty `ToSimplify` set.
94  bool IsFirstIteration = ToSimplify->empty();
95 
96  if (!IsFirstIteration && !ToSimplify->count(&I))
97  continue;
98 
100  if (!V || !LI.replacementPreservesLCSSAForm(&I, V))
101  continue;
102 
103  for (Value::use_iterator UI = I.use_begin(), UE = I.use_end();
104  UI != UE;) {
105  Use &U = *UI++;
106  auto *UserI = cast<Instruction>(U.getUser());
107  U.set(V);
108 
109  // If the instruction is used by a PHI node we have already processed
110  // we'll need to iterate on the loop body to converge, so add it to
111  // the next set.
112  if (auto *UserPI = dyn_cast<PHINode>(UserI))
113  if (VisitedPHIs.count(UserPI)) {
114  Next->insert(UserPI);
115  continue;
116  }
117 
118  // If we are only simplifying targeted instructions and the user is an
119  // instruction in the loop body, add it to our set of targeted
120  // instructions. Because we process defs before uses (outside of PHIs)
121  // we won't have visited it yet.
122  //
123  // We also skip any uses outside of the loop being simplified. Those
124  // should always be PHI nodes due to LCSSA form, and we don't want to
125  // try to simplify those away.
126  assert((L.contains(UserI) || isa<PHINode>(UserI)) &&
127  "Uses outside the loop should be PHI nodes due to LCSSA!");
128  if (!IsFirstIteration && L.contains(UserI))
129  ToSimplify->insert(UserI);
130  }
131 
132  assert(I.use_empty() && "Should always have replaced all uses!");
133  if (isInstructionTriviallyDead(&I, &TLI))
134  DeadInsts.push_back(&I);
135  ++NumSimplified;
136  Changed = true;
137  }
138  }
139 
140  // Delete any dead instructions found thus far now that we've finished an
141  // iteration over all instructions in all the loop blocks.
142  if (!DeadInsts.empty()) {
143  Changed = true;
145  }
146 
147  // If we never found a PHI that needs to be simplified in the next
148  // iteration, we're done.
149  if (Next->empty())
150  break;
151 
152  // Otherwise, put the next set in place for the next iteration and reset it
153  // and the visited PHIs for that iteration.
154  std::swap(Next, ToSimplify);
155  Next->clear();
156  VisitedPHIs.clear();
157  DeadInsts.clear();
158  }
159 
160  return Changed;
161 }
162 
163 namespace {
164 
165 class LoopInstSimplifyLegacyPass : public LoopPass {
166 public:
167  static char ID; // Pass ID, replacement for typeid
168 
169  LoopInstSimplifyLegacyPass() : LoopPass(ID) {
171  }
172 
173  bool runOnLoop(Loop *L, LPPassManager &LPM) override {
174  if (skipLoop(L))
175  return false;
176  DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
177  LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
178  AssumptionCache &AC =
179  getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
180  *L->getHeader()->getParent());
181  const TargetLibraryInfo &TLI =
182  getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
183 
184  return simplifyLoopInst(*L, DT, LI, AC, TLI);
185  }
186 
187  void getAnalysisUsage(AnalysisUsage &AU) const override {
191  AU.setPreservesCFG();
193  }
194 };
195 
196 } // end anonymous namespace
197 
200  LPMUpdater &) {
201  if (!simplifyLoopInst(L, AR.DT, AR.LI, AR.AC, AR.TLI))
202  return PreservedAnalyses::all();
203 
204  auto PA = getLoopPassPreservedAnalyses();
205  PA.preserveSet<CFGAnalyses>();
206  return PA;
207 }
208 
210 
211 INITIALIZE_PASS_BEGIN(LoopInstSimplifyLegacyPass, "loop-instsimplify",
212  "Simplify instructions in loops", false, false)
216 INITIALIZE_PASS_END(LoopInstSimplifyLegacyPass, "loop-instsimplify",
217  "Simplify instructions in loops", false, false)
218 
220  return new LoopInstSimplifyLegacyPass();
221 }
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:81
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:111
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
SimplifyQuery getWithInstruction(Instruction *I) const
An immutable pass that tracks lazily created AssumptionCache objects.
A cache of @llvm.assume calls within a function.
STATISTIC(NumFunctions, "Total number of functions")
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
AnalysisUsage & addRequired()
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
Definition: BasicBlock.cpp:134
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
static bool simplifyLoopInst(Loop &L, DominatorTree &DT, LoopInfo &LI, AssumptionCache &AC, const TargetLibraryInfo &TLI)
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:361
A Use represents the edge between a Value definition and its users.
Definition: Use.h:56
BlockT * getHeader() const
Definition: LoopInfo.h:100
User * getUser() const LLVM_READONLY
Returns the User that contains this Use.
Definition: Use.cpp:41
Pass * createLoopInstSimplifyPass()
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:142
loop instsimplify
use_iterator_impl< Use > use_iterator
Definition: Value.h:331
void initializeLoopInstSimplifyLegacyPassPass(PassRegistry &)
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
INITIALIZE_PASS_BEGIN(LoopInstSimplifyLegacyPass, "loop-instsimplify", "Simplify instructions in loops", false, false) INITIALIZE_PASS_END(LoopInstSimplifyLegacyPass
void set(Value *Val)
Definition: Value.h:670
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
LLVM_NODISCARD bool empty() const
Definition: SmallPtrSet.h:92
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:371
Represent the analysis usage information of a pass.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr)
If the specified value is a trivially dead instruction, delete it.
Definition: Local.cpp:429
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:110
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:418
loop Simplify instructions in loops
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:861
Module.h This file contains the declarations for the Module class.
Provides information about what library functions are available for the current target.
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:286
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:924
Represents analyses that only rely on functions&#39; control flow.
Definition: PassManager.h:114
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:62
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:445
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:108
#define I(x, y, z)
Definition: MD5.cpp:58
void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass&#39;s AnalysisUsage.
Definition: LoopUtils.cpp:1226
Wrapper class to LoopBlocksDFS that provides a standard begin()/end() interface for the DFS reverse p...
Definition: LoopIterator.h:173
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction has no side ef...
Definition: Local.cpp:346
LLVM Value Representation.
Definition: Value.h:73
inst_range instructions(Function *F)
Definition: InstIterator.h:134
A container for analyses that lazily runs them and caches their results.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:254
bool replacementPreservesLCSSAForm(Instruction *From, Value *To)
Returns true if replacing From with To everywhere is guaranteed to preserve LCSSA form...
Definition: LoopInfo.h:826
This header defines various interfaces for pass management in LLVM.
void perform(LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
Definition: LoopIterator.h:181
Value * SimplifyInstruction(Instruction *I, const SimplifyQuery &Q, OptimizationRemarkEmitter *ORE=nullptr)
See if we can compute a simplified version of this instruction.