Lines Matching refs:Loop
1 //===-- LICM.cpp - Loop Invariant Code Motion Pass ------------------------===//
10 // This pass performs loop invariant code motion, attempting to remove as much
11 // code from the body of a loop as possible. It does this by either hoisting
13 // safe. This pass also promotes must-aliased memory locations in the loop to
18 // 1. Moving loop invariant loads and calls out of loops. If we can determine
19 // that a load or call inside of a loop never aliases anything stored to,
22 // the loop, we try to move the store to happen AFTER the loop instead of
23 // inside of the loop. This can only happen if a few conditions are true:
24 // A. The pointer stored through is loop invariant
25 // B. There are no stores or loads in the loop which _may_ alias the
26 // pointer. There are no calls in the loop which mod/ref the pointer.
28 // loop of the pointer to use a temporary alloca'd variable. We then use
67 STATISTIC(NumSunk , "Number of instructions sunk out of loop");
68 STATISTIC(NumHoisted , "Number of instructions hoisted out of loop");
77 static bool inSubLoop(BasicBlock *BB, Loop *CurLoop, LoopInfo *LI);
78 static bool isNotUsedInLoop(const Instruction &I, const Loop *CurLoop);
81 const Loop *CurLoop, AliasSetTracker *CurAST );
84 const Loop *CurLoop,
89 const Loop *CurLoop,
101 Loop *CurLoop, AliasSetTracker *CurAST,
111 bool runOnLoop(Loop *L, LPPassManager &LPM) override;
113 /// This transformation requires natural loop information & requires that
114 /// loop preheaders be inserted into the CFG...
136 assert(LoopToAliasSetMap.empty() && "Didn't free loop alias sets");
143 DominatorTree *DT; // Dominator Tree for the current Loop.
149 BasicBlock *Preheader; // The preheader block of the current loop...
150 Loop *CurLoop; // The current loop we are working on...
151 AliasSetTracker *CurAST; // AliasSet information for the current loop...
152 DenseMap<Loop*, AliasSetTracker*> LoopToAliasSetMap;
156 Loop *L) override;
160 void deleteAnalysisValue(Value *V, Loop *L) override;
162 /// Simple Analysis hook. Delete loop L from alias set map.
163 void deleteAnalysisLoop(Loop *L) override;
168 INITIALIZE_PASS_BEGIN(LICM, "licm", "Loop Invariant Code Motion", false, false)
179 INITIALIZE_PASS_END(LICM, "licm", "Loop Invariant Code Motion", false, false)
183 /// Hoist expressions out of the specified loop. Note, alias info for inner
184 /// loop is not preserved so it is not a good idea to run LICM multiple
185 /// times on one loop.
187 bool LICM::runOnLoop(Loop *L, LPPassManager &LPM) {
193 // Get our Loop and Alias Analysis information...
200 assert(L->isLCSSAForm(*DT) && "Loop is not in LCSSA form.");
204 for (Loop::iterator LoopItr = L->begin(), LoopItrE = L->end();
206 Loop *InnerL = *LoopItr;
213 // Once we've incorporated the inner loop's AST into ours, we don't need the
224 // Loop over the body of this loop, looking for calls, invokes, and stores.
228 for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
235 // Compute loop safety information.
239 // We want to visit all of the instructions in this loop... that are not parts
241 // their loop, into this loop, so there is no need to process the BODIES of
244 // Traverse the body of the loop in depth first order on the dominator tree so
247 // instructions, we perform another pass to hoist them out of the loop.
256 // Now that all loop invariants have been removed from the loop, promote any
263 // Loop over all of the alias sets in the tracker object.
270 // Once we have promoted values across the loop body we have to recursively
271 // reform LCSSA as any nested loop may now have values defined within the
272 // loop used in the outer loop.
282 // Check that neither this loop nor its parent have had LCSSA broken. LICM is
283 // specifically moving instructions across the loop boundary and so it is
285 assert(L->isLCSSAForm(*DT) && "Loop not left in LCSSA form after LICM!");
287 "Parent loop not left in LCSSA form after LICM!");
293 // If this loop is nested inside of another one, save the alias information
294 // for when we process the outer loop.
303 /// the specified block, and that are in the current loop) in reverse depth
305 /// definitions, allowing us to sink a loop body in one pass without iteration.
308 DominatorTree *DT, TargetLibraryInfo *TLI, Loop *CurLoop,
320 // If this subregion is not in the top level loop at all, exit.
336 // in the loop, instead, just delete it.
347 // of the loop. We can do this if the all users of the instruction are
348 // outside of the loop. In this case, it doesn't even matter if the
349 // operands of the instruction are loop invariant.
361 /// the specified block, and that are in the current loop) in depth first
363 /// uses, allowing us to hoist a loop body in one pass without iteration.
366 DominatorTree *DT, TargetLibraryInfo *TLI, Loop *CurLoop,
376 // If this subregion is not in the top level loop
397 // if all of the operands of the instruction are loop invariant and if it
414 /// Computes loop safety information, checks loop body & header
417 void llvm::computeLICMSafetyInfo(LICMSafetyInfo * SafetyInfo, Loop * CurLoop) {
429 // Iterate over loop instructions and compute safety info.
430 for (Loop::block_iterator BB = CurLoop->block_begin(),
441 TargetLibraryInfo *TLI, Loop *CurLoop,
455 // Don't hoist loads which have may-aliased stores in loop.
476 // writes to this memory in the loop, we can hoist or sink.
486 // in the loop, we can hoist or sink the call as appropriate.
534 /// the loop. If this is true, we can sink the instruction to the exit
535 /// blocks of the loop.
537 static bool isNotUsedInLoop(const Instruction &I, const Loop *CurLoop) {
553 // values. Check for such a use being inside the loop.
576 // Build LCSSA PHI nodes for any in-loop operands. Note that this is
586 if (Loop *OLoop = LI->getLoopFor(OInst->getParent()))
598 /// When an instruction is found to only be used outside of the loop, this
601 /// position, and may either delete it or move it to outside of the loop.
604 const Loop *CurLoop, AliasSetTracker *CurAST ) {
622 // If this instruction is only used outside of the loop, then all users are
666 /// When an instruction is found to only use loop invariant operands that
691 const Loop *CurLoop,
702 const Loop *CurLoop,
706 // of the exit blocks. If it doesn't, then there is a path out of the loop
709 // If the instruction is in the header block for the loop (which is very
717 // Somewhere in this loop there is an instruction which may throw and make us
718 // exit the loop.
722 // Get the exit blocks for the current loop.
726 // Verify that the block dominates each of the exit blocks of the loop.
731 // As a degenerate case, if the loop is statically infinite then we haven't
754 if (Loop *L = LI.getLoopFor(I->getParent()))
791 // Insert stores after in the loop exit blocks. Each exit block gets a
793 // the SSA updater about the defs in the loop and the preheader
819 /// loop and moving loads to before the loop. We do this by looping over
820 /// the stores in the loop, looking for stores to Must pointers which are
821 /// loop invariant.
827 DominatorTree *DT, Loop *CurLoop,
838 // set, if the pointer is loop invariant, and if we are not eliminating any
850 // It isn't safe to promote a load/store from the loop if the load/store is
888 // Ignore instructions that are outside the loop.
893 // If there is an non-load/store instruction in the loop, we can't promote
908 // containing indirect branches are not transformed by loop simplify,
954 DEBUG(dbgs() << "LICM: Promoting value stored to in loop: " <<*SomePtr<<'\n');
964 // Figure out the loop exits and their insertion points, if this is the
981 // value from the preheader that uses in the loop will use.
990 // Rewrite all the loads in the loop and remember all the definitions from
991 // stores in the loop.
1003 void LICM::cloneBasicBlockAnalysis(BasicBlock *From, BasicBlock *To, Loop *L) {
1013 void LICM::deleteAnalysisValue(Value *V, Loop *L) {
1023 void LICM::deleteAnalysisLoop(Loop *L) {
1033 /// Return true if the body of this loop may store into the memory
1046 static bool inSubLoop(BasicBlock *BB, Loop *CurLoop, LoopInfo *LI) {
1047 assert(CurLoop->contains(BB) && "Only valid if BB is IN the loop");
