Lines Matching refs:Loop
1 //===-- LoopUnswitch.cpp - Hoist loop-invariant conditionals in loop ------===//
10 // This pass transforms loops that contain branches on loop-invariant conditions
21 // a loop is unswitched) so we only unswitch if the resultant code will be
25 // of the loop, to make the unswitching opportunity obvious.
63 #define DEBUG_TYPE "loop-unswitch"
75 Threshold("loop-unswitch-threshold", cl::desc("Max loop size to unswitch"),
79 LoopUnswitchWithBlockFrequency("loop-unswitch-with-block-frequency",
85 ColdnessThreshold("loop-unswitch-coldness-threshold", cl::init(1), cl::Hidden,
86 cl::desc("Coldness threshold in percentage. The loop header frequency "
108 // LoopProperties pointer for current loop for better performance.
109 typedef std::map<const Loop*, LoopProperties> LoopPropsMap;
116 // A loop unswitching with an estimated cost above this threshold
118 // the current loop, and reduced correspondingly, though note that
119 // the quota is returned by releaseMemory() when the loop has been
122 // when a new loop is processed. An exception to that is that
124 // that were introduced due to loop unswitching of an outer loop.
137 // Analyze loop. Check its size, calculate is it possible to unswitch
138 // it. Returns true if we can unswitch this loop.
139 bool countLoop(const Loop *L, const TargetTransformInfo &TTI,
142 // Clean all data related to given loop.
143 void forgetLoop(const Loop *L);
157 // Clone all loop-unswitch related loop properties.
159 // Note, that new loop data is stored inside the VMap.
160 void cloneData(const Loop *NewLoop, const Loop *OldLoop,
165 LoopInfo *LI; // Loop information
169 // Used to check if second loop needs processing after
170 // RewriteLoopBodyWithConditionConstant rewrites first loop.
171 std::vector<Loop*> LoopProcessWorklist;
185 Loop *currentLoop;
190 // LoopBlocks contains all of the basic blocks of the loop, including the
191 // preheader of the loop, the body of the loop, and the exit blocks of the
192 // loop, in that order.
206 bool runOnLoop(Loop *L, LPPassManager &LPM) override;
209 /// This transformation requires natural loop information & requires that
210 /// loop preheaders be inserted into the CFG.
238 /// Split all of the edges from inside the loop to their exit blocks.
240 void SplitExitEdges(Loop *L,
247 void UnswitchTrivialCondition(Loop *L, Value *Cond, Constant *Val,
249 void UnswitchNontrivialCondition(Value *LIC, Constant *OnVal, Loop *L,
252 void RewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC,
261 void SimplifyCode(std::vector<Instruction*> &Worklist, Loop *L);
265 // Analyze loop. Check its size, calculate is it possible to unswitch
266 // it. Returns true if we can unswitch this loop.
267 bool LUAnalysisCache::countLoop(const Loop *L, const TargetTransformInfo &TTI,
278 // New loop.
282 // large numbers of branches which cause loop unswitching to go crazy.
292 for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); I != E;
302 DEBUG(dbgs() << "NOT unswitching loop %"
309 // Be careful. This links are good only before new loop addition.
316 // Clean all data related to given loop.
317 void LUAnalysisCache::forgetLoop(const Loop *L) {
348 // Clone all loop-unswitch related loop properties.
350 // Note, that new loop data is stored inside the VMap.
351 void LUAnalysisCache::cloneData(const Loop *NewLoop, const Loop *OldLoop,
370 // for new loop switches we clone info about values that was
383 INITIALIZE_PASS_BEGIN(LoopUnswitch, "loop-unswitch", "Unswitch loops",
390 INITIALIZE_PASS_END(LoopUnswitch, "loop-unswitch", "Unswitch loops",
397 /// Cond is a condition that occurs in L. If it is invariant in the loop, or has
399 static Value *FindLIVLoopCondition(Value *Cond, Loop *L, bool &Changed) {
421 // which will cause the branch to go away in one loop and the condition to
432 bool LoopUnswitch::runOnLoop(Loop *L, LPPassManager &LPM_Ref) {
470 /// Do actual work and unswitch loop if possible and profitable.
490 // Analyze loop cost, and stop unswitching if loop content can not be duplicated.
497 // Try trivial unswitch first before loop over other basic blocks in the loop.
524 // loop (loopHeader in this case since inner loops should be
525 // processed before outer loop). If it is less than ColdFrequency,
532 // Loop over all of the basic blocks in the loop. If we find an interior
533 // block that is branching on a loop-invariant condition, we can unswitch this
534 // loop.
535 for (Loop::block_iterator I = currentLoop->block_begin(),
542 // See if this, or some part of it, is loop invariant. If so, we can
600 /// Check to see if all paths from BB exit the loop with no side effects
606 static bool isTrivialLoopExitBlockHelper(Loop *L, BasicBlock *BB,
611 // loop.
615 // Otherwise, this is a loop exit, this is fine so long as this is the
622 // Otherwise, this is an unvisited intra-loop node. Check all successors.
624 // Check to see if the successor is a trivial loop exit.
639 /// the specified loop, and has no side-effects in the process. If so, return
641 static BasicBlock *isTrivialLoopExitBlock(Loop *L, BasicBlock *BB) {
651 /// simplify the loop. If we decide that this is profitable,
652 /// unswitch the loop, reprocess the pieces, then return true.
655 // Check to see if it would be profitable to unswitch current loop.
657 DEBUG(dbgs() << "NOT unswitching loop %"
669 /// Recursively clone the specified loop and all of its children,
671 static Loop *CloneLoop(Loop *L, Loop *PL, ValueToValueMapTy &VM,
673 Loop &New = LPM->addLoop(PL);
675 // Add all of the blocks in L to the new loop.
676 for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
681 // Add all of the subloops to the new loop.
682 for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
739 // We want to enter the new loop when the condition is true.
755 /// Given a loop that has a trivial unswitchable condition in it (a cond branch
756 /// from its header block to its latch block, where the path through the loop
759 /// outside of the loop and updating loop info.
760 void LoopUnswitch::UnswitchTrivialCondition(Loop *L, Value *Cond, Constant *Val,
763 DEBUG(dbgs() << "loop-unswitch: Trivial-Unswitch loop %"
775 // to branch to: this is the exit block out of the loop that we should
778 // Split this block now, so that the loop maintains its exit block, and so
781 // loop header, not the preheader).
782 assert(!L->contains(ExitBlock) && "Exit block is in the loop?");
792 // We need to reprocess this loop, it could be unswitched again.
795 // Now that we know that the loop is never entered when this condition is a
796 // particular value, rewrite the loop with this info. We know that this will
802 /// Check if the first non-constant condition starting from the loop header is
804 /// the loop does anything at all. If it is a trivial condition, unswitching
805 /// produces no code duplications (equivalently, it produces a simpler loop and
806 /// a new empty loop, which gets deleted). Therefore always unswitch trivial
813 // If loop header has only one reachable successor (currently via an
818 // and merge successors into loop header (then we only need to check header's
821 // branches could either eliminate the current loop or make other loops
823 // branches. The following code keeps traversing loop header's successors
830 // If we exit loop or reach a previous visited block, then
837 // Check if this loop will execute any side-effecting instructions (e.g.
838 // stores, calls, volatile loads) in the part of the loop that the code
864 // LoopExitBB is the BasicBlock that loop exits when meets trivial condition.
893 // If we didn't find a single unique LoopExit block, or if the loop exit
936 // If we didn't find a single unique LoopExit block, or if the loop exit
949 /// Split all of the edges from inside the loop to their exit blocks.
951 void LoopUnswitch::SplitExitEdges(Loop *L,
959 // Although SplitBlockPredecessors doesn't preserve loop-simplify in
966 /// We determined that the loop is profitable to unswitch when LIC equal Val.
967 /// Split it into loop versions and test the condition outside of either loop.
970 Loop *L, TerminatorInst *TI) {
972 DEBUG(dbgs() << "loop-unswitch: Unswitching loop %"
988 // We want the loop to come after the preheader, but before the exit blocks.
994 // Split all of the edges from inside the loop to their exit blocks. Update
1002 // Add exit blocks to the loop blocks.
1005 // Next step, clone all of the basic blocks that make up the loop (including
1006 // the loop preheader and exit blocks), keeping track of the mapping between
1028 // Now we create the new Loop object for the versioned loop.
1029 Loop *NewLoop = CloneLoop(L, L->getParentLoop(), VMap, LI, LPM);
1032 // Probably clone more loop-unswitch related loop properties.
1035 Loop *ParentLoop = L->getParentLoop();
1037 // Make sure to add the cloned preheader and exit blocks to the parent loop
1044 // The new exit block should be in the same loop as the old one.
1045 if (Loop *ExitBBLoop = LI->getLoopFor(ExitBlocks[i]))
1083 // Rewrite the original preheader to select between versions of the loop.
1088 // Emit the new branch that selects between the two versions of this loop.
1107 // It's possible that simplifying one loop could cause the other to be
1127 Loop *L, LPPassManager *LPM) {
1146 /// specified loop, or we know it does NOT have that value.
1148 void LoopUnswitch::RewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC,
1166 // in the loop with the appropriate one directly.
1192 // is certainly NOT "Val". As such, simplify any uses in the loop that we
1223 // If the DeadCase successor dominates the loop latch, then the
1230 // and hooked up so as to preserve the loop structure, because
1232 // loop structure and put the block on a dead code path.
1264 /// Now that we have simplified some instructions in the loop, walk over it and
1266 /// effectively a very simple loop-structure-aware optimizer. During processing
1267 /// of this loop, L could very well be deleted, so it must not be used.
1269 /// FIXME: When the loop optimizer is more mature, separate this out to a new
1272 void LoopUnswitch::SimplifyCode(std::vector<Instruction*> &Worklist, Loop *L) {
1331 // Remove Succ from the loop tree.
