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.
29 #define DEBUG_TYPE "loop-unswitch"
66 Threshold("loop-unswitch-threshold", cl::desc("Max loop size to unswitch"),
85 // LoopProperties pointer for current loop for better performance.
86 typedef std::map<const Loop*, LoopProperties> LoopPropsMap;
103 // Analyze loop. Check its size, calculate is it possible to unswitch
104 // it. Returns true if we can unswitch this loop.
105 bool countLoop(const Loop* L, const TargetTransformInfo &TTI);
107 // Clean all data related to given loop.
108 void forgetLoop(const Loop* L);
118 // Clone all loop-unswitch related loop properties.
120 // Note, that new loop data is stored inside the VMap.
121 void cloneData(const Loop* NewLoop, const Loop* OldLoop,
126 LoopInfo *LI; // Loop information
129 // LoopProcessWorklist - Used to check if second loop needs processing
130 // after RewriteLoopBodyWithConditionConstant rewrites first loop.
131 std::vector<Loop*> LoopProcessWorklist;
138 Loop *currentLoop;
143 // LoopBlocks contains all of the basic blocks of the loop, including the
144 // preheader of the loop, the body of the loop, and the exit blocks of the
145 // loop, in that order.
159 bool runOnLoop(Loop *L, LPPassManager &LPM);
162 /// This transformation requires natural loop information & requires that
163 /// loop preheaders be inserted into the CFG.
183 /// RemoveLoopFromWorklist - If the specified loop is on the loop worklist,
185 void RemoveLoopFromWorklist(Loop *L) {
186 std::vector<Loop*>::iterator I = std::find(LoopProcessWorklist.begin(),
197 /// Split all of the edges from inside the loop to their exit blocks.
199 void SplitExitEdges(Loop *L, const SmallVector<BasicBlock *, 8> &ExitBlocks);
202 void UnswitchTrivialCondition(Loop *L, Value *Cond, Constant *Val,
204 void UnswitchNontrivialCondition(Value *LIC, Constant *OnVal, Loop *L);
206 void RewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC,
214 void SimplifyCode(std::vector<Instruction*> &Worklist, Loop *L);
216 std::vector<Instruction*> &Worklist, Loop *l);
217 void RemoveLoopFromHierarchy(Loop *L);
224 // Analyze loop. Check its size, calculate is it possible to unswitch
225 // it. Returns true if we can unswitch this loop.
226 bool LUAnalysisCache::countLoop(const Loop *L, const TargetTransformInfo &TTI) {
234 // New loop.
238 // large numbers of branches which cause loop unswitching to go crazy.
245 for (Loop::block_iterator I = L->block_begin(),
255 DEBUG(dbgs() << "NOT unswitching loop %"
263 DEBUG(dbgs() << "NOT unswitching loop %"
270 // Be careful. This links are good only before new loop addition.
277 // Clean all data related to given loop.
278 void LUAnalysisCache::forgetLoop(const Loop* L) {
304 // Clone all loop-unswitch related loop properties.
306 // Note, that new loop data is stored inside the VMap.
307 void LUAnalysisCache::cloneData(const Loop* NewLoop, const Loop* OldLoop,
324 // for new loop switches we clone info about values that was
337 INITIALIZE_PASS_BEGIN(LoopUnswitch, "loop-unswitch", "Unswitch loops",
343 INITIALIZE_PASS_END(LoopUnswitch, "loop-unswitch", "Unswitch loops",
351 /// invariant in the loop, or has an invariant piece, return the invariant.
353 static Value *FindLIVLoopCondition(Value *Cond, Loop *L, bool &Changed) {
375 // which will cause the branch to go away in one loop and the condition to
386 bool LoopUnswitch::runOnLoop(Loop *L, LPPassManager &LPM_Ref) {
407 /// processCurrentLoop - Do actual work and unswitch loop if possible
428 // Probably we reach the quota of branches for this loop. If so
433 // Loop over all of the basic blocks in the loop. If we find an interior
434 // block that is branching on a loop-invariant condition, we can unswitch this
435 // loop.
436 for (Loop::block_iterator I = currentLoop->block_begin(),
443 // See if this, or some part of it, is loop invariant. If so, we can
502 /// loop with no side effects (including infinite loops).
507 static bool isTrivialLoopExitBlockHelper(Loop *L, BasicBlock *BB,
512 // loop.
515 // Otherwise, this is a loop exit, this is fine so long as this is the
522 // Otherwise, this is an unvisited intra-loop node. Check all successors.
524 // Check to see if the successor is a trivial loop exit.
539 /// leads to an exit from the specified loop, and has no side-effects in the
541 static BasicBlock *isTrivialLoopExitBlock(Loop *L, BasicBlock *BB) {
551 /// trivial: that is, that the condition controls whether or not the loop does
553 /// code duplications (equivalently, it produces a simpler loop and a new empty
554 /// loop, which gets deleted).
558 /// trivial condition: when Cond dynamically equals Val, the loop is known to
559 /// exit. Finally, this sets LoopExit to the BB that the loop exits to when
615 // If we didn't find a single unique LoopExit block, or if the loop exit block
623 // loop. As such, we just have to check to see if this loop will execute any
625 // part of the loop that the code *would* execute. We already checked the
634 /// LoopCond == Val to simplify the loop. If we decide that this is profitable,
635 /// unswitch the loop, reprocess the pieces, then return true.
648 // Check to see if it would be profitable to unswitch current loop.
660 /// CloneLoop - Recursively clone the specified loop and all of its children,
662 static Loop *CloneLoop(Loop *L, Loop *PL, ValueToValueMapTy &VM,
664 Loop *New = new Loop();
667 // Add all of the blocks in L to the new loop.
668 for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
673 // Add all of the subloops to the new loop.
674 for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
694 // We want to enter the new loop when the condition is true.
706 /// UnswitchTrivialCondition - Given a loop that has a trivial unswitchable
708 /// where the path through the loop that doesn't execute its body has no
710 /// moving the conditional branch outside of the loop and updating loop info.
711 void LoopUnswitch::UnswitchTrivialCondition(Loop *L, Value *Cond,
714 DEBUG(dbgs() << "loop-unswitch: Trivial-Unswitch loop %"
725 // to branch to: this is the exit block out of the loop that we should
728 // Split this block now, so that the loop maintains its exit block, and so
731 // loop header, not the preheader).
732 assert(!L->contains(ExitBlock) && "Exit block is in the loop?");
742 // We need to reprocess this loop, it could be unswitched again.
745 // Now that we know that the loop is never entered when this condition is a
746 // particular value, rewrite the loop with this info. We know that this will
752 /// SplitExitEdges - Split all of the edges from inside the loop to their exit
754 void LoopUnswitch::SplitExitEdges(Loop *L,
762 // Although SplitBlockPredecessors doesn't preserve loop-simplify in
774 /// UnswitchNontrivialCondition - We determined that the loop is profitable
775 /// to unswitch when LIC equal Val. Split it into loop versions and test the
776 /// condition outside of either loop. Return the loops created as Out1/Out2.
778 Loop *L) {
780 DEBUG(dbgs() << "loop-unswitch: Unswitching loop %"
796 // We want the loop to come after the preheader, but before the exit blocks.
802 // Split all of the edges from inside the loop to their exit blocks. Update
810 // Add exit blocks to the loop blocks.
813 // Next step, clone all of the basic blocks that make up the loop (including
814 // the loop preheader and exit blocks), keeping track of the mapping between
831 // Now we create the new Loop object for the versioned loop.
832 Loop *NewLoop = CloneLoop(L, L->getParentLoop(), VMap, LI, LPM);
835 loop-unswitch related loop properties.
838 Loop *ParentLoop = L->getParentLoop();
840 // Make sure to add the cloned preheader and exit blocks to the parent loop
847 // The new exit block should be in the same loop as the old one.
848 if (Loop *ExitBBLoop = LI->getLoopFor(ExitBlocks[i]))
886 // Rewrite the original preheader to select between versions of the loop.
891 // Emit the new branch that selects between the two versions of this loop.
909 // It's possible that simplifying one loop could cause the other to be
930 Loop *L, LPPassManager *LPM) {
949 /// RemoveBlockIfDead - If the specified block is dead, remove it, update loop
954 Loop *L) {
965 // If this is the header of a loop and the only pred is the latch, we now
966 // have an unreachable loop.
967 if (Loop *L = LI->getLoopFor(BB))
976 // The loop is now broken, remove it from LI.
1007 // If this is the edge to the header block for a loop, remove the loop and
1009 if (Loop *BBLoop = LI->getLoopFor(BB)) {
1019 // Remove the block from the loop info, which removes it from any loops it
1045 // One exception is loop headers. If this block was the preheader for a
1046 // loop, then we DO want to visit the loop so the loop gets deleted.
1047 // We know that if the successor is a loop header, that this loop had to
1060 /// RemoveLoopFromHierarchy - We have discovered that the specified loop has
1063 /// latch block was removed, the loop is unwrapped but subloops are still alive,
1066 void LoopUnswitch::RemoveLoopFromHierarchy(Loop *L) {
1072 // the value specified by Val in the specified loop, or we know it does NOT have
1074 void LoopUnswitch::RewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC,
1093 // in the loop with the appropriate one directly.
1120 // is certainly NOT "Val". As such, simplify any uses in the loop that we
1152 // If the DeadCase successor dominates the loop latch, then the
1159 // and hooked up so as to preserve the loop structure, because
1161 // loop structure and put the block on a dead code path.
1195 /// loop, walk over it and constant prop, dce, and fold control flow where
1196 /// possible. Note that this is effectively a very simple loop-structure-aware
1197 /// optimizer. During processing of this loop, L could very well be deleted, so
1200 /// FIXME: When the loop optimizer is more mature, separate this out to a new
1203 void LoopUnswitch::SimplifyCode(std::vector<Instruction*> &Worklist, Loop *L) {
1261 // Remove Succ from the loop tree.
