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.
55 #define DEBUG_TYPE "loop-unswitch"
67 Threshold("loop-unswitch-threshold", cl::desc("Max loop size to unswitch"),
86 // LoopProperties pointer for current loop for better performance.
87 typedef std::map<const Loop*, LoopProperties> LoopPropsMap;
104 // Analyze loop. Check its size, calculate is it possible to unswitch
105 // it. Returns true if we can unswitch this loop.
106 bool countLoop(const Loop *L, const TargetTransformInfo &TTI);
108 // Clean all data related to given loop.
109 void forgetLoop(const Loop *L);
119 // Clone all loop-unswitch related loop properties.
121 // Note, that new loop data is stored inside the VMap.
122 void cloneData(const Loop *NewLoop, const Loop *OldLoop,
127 LoopInfo *LI; // Loop information
130 // LoopProcessWorklist - Used to check if second loop needs processing
131 // after RewriteLoopBodyWithConditionConstant rewrites first loop.
132 std::vector<Loop*> LoopProcessWorklist;
139 Loop *currentLoop;
144 // LoopBlocks contains all of the basic blocks of the loop, including the
145 // preheader of the loop, the body of the loop, and the exit blocks of the
146 // loop, in that order.
160 bool runOnLoop(Loop *L, LPPassManager &LPM) override;
163 /// This transformation requires natural loop information & requires that
164 /// loop preheaders be inserted into the CFG.
189 /// Split all of the edges from inside the loop to their exit blocks.
191 void SplitExitEdges(Loop *L, const SmallVectorImpl<BasicBlock *> &ExitBlocks);
194 void UnswitchTrivialCondition(Loop *L, Value *Cond, Constant *Val,
196 void UnswitchNontrivialCondition(Value *LIC, Constant *OnVal, Loop *L);
198 void RewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC,
206 void SimplifyCode(std::vector<Instruction*> &Worklist, Loop *L);
213 // Analyze loop. Check its size, calculate is it possible to unswitch
214 // it. Returns true if we can unswitch this loop.
215 bool LUAnalysisCache::countLoop(const Loop *L, const TargetTransformInfo &TTI) {
225 // New loop.
229 // large numbers of branches which cause loop unswitching to go crazy.
236 for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
245 DEBUG(dbgs() << "NOT unswitching loop %"
253 DEBUG(dbgs() << "NOT unswitching loop %"
259 // Be careful. This links are good only before new loop addition.
266 // Clean all data related to given loop.
267 void LUAnalysisCache::forgetLoop(const Loop *L) {
293 // Clone all loop-unswitch related loop properties.
295 // Note, that new loop data is stored inside the VMap.
296 void LUAnalysisCache::cloneData(const Loop *NewLoop, const Loop *OldLoop,
313 // for new loop switches we clone info about values that was
326 INITIALIZE_PASS_BEGIN(LoopUnswitch, "loop-unswitch", "Unswitch loops",
332 INITIALIZE_PASS_END(LoopUnswitch, "loop-unswitch", "Unswitch loops",
340 /// invariant in the loop, or has an invariant piece, return the invariant.
342 static Value *FindLIVLoopCondition(Value *Cond, Loop *L, bool &Changed) {
364 // which will cause the branch to go away in one loop and the condition to
375 bool LoopUnswitch::runOnLoop(Loop *L, LPPassManager &LPM_Ref) {
401 /// processCurrentLoop - Do actual work and unswitch loop if possible
422 // Probably we reach the quota of branches for this loop. If so
427 // Loop over all of the basic blocks in the loop. If we find an interior
428 // block that is branching on a loop-invariant condition, we can unswitch this
429 // loop.
430 for (Loop::block_iterator I = currentLoop->block_begin(),
437 // See if this, or some part of it, is loop invariant. If so, we can
496 /// loop with no side effects (including infinite loops).
501 static bool isTrivialLoopExitBlockHelper(Loop *L, BasicBlock *BB,
506 // loop.
510 // Otherwise, this is a loop exit, this is fine so long as this is the
517 // Otherwise, this is an unvisited intra-loop node. Check all successors.
519 // Check to see if the successor is a trivial loop exit.
534 /// leads to an exit from the specified loop, and has no side-effects in the
536 static BasicBlock *isTrivialLoopExitBlock(Loop *L, BasicBlock *BB) {
546 /// trivial: that is, that the condition controls whether or not the loop does
548 /// code duplications (equivalently, it produces a simpler loop and a new empty
549 /// loop, which gets deleted).
553 /// trivial condition: when Cond dynamically equals Val, the loop is known to
554 /// exit. Finally, this sets LoopExit to the BB that the loop exits to when
610 // If we didn't find a single unique LoopExit block, or if the loop exit block
618 // loop. As such, we just have to check to see if this loop will execute any
620 // part of the loop that the code *would* execute. We already checked the
629 /// LoopCond == Val to simplify the loop. If we decide that this is profitable,
630 /// unswitch the loop, reprocess the pieces, then return true.
643 // Check to see if it would be profitable to unswitch current loop.
655 /// CloneLoop - Recursively clone the specified loop and all of its children,
657 static Loop *CloneLoop(Loop *L, Loop *PL, ValueToValueMapTy &VM,
659 Loop *New = new Loop();
662 // Add all of the blocks in L to the new loop.
663 for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
668 // Add all of the subloops to the new loop.
669 for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
689 // We want to enter the new loop when the condition is true.
701 /// UnswitchTrivialCondition - Given a loop that has a trivial unswitchable
703 /// where the path through the loop that doesn't execute its body has no
705 /// moving the conditional branch outside of the loop and updating loop info.
706 void LoopUnswitch::UnswitchTrivialCondition(Loop *L, Value *Cond,
709 DEBUG(dbgs() << "loop-unswitch: Trivial-Unswitch loop %"
720 // to branch to: this is the exit block out of the loop that we should
723 // Split this block now, so that the loop maintains its exit block, and so
726 // loop header, not the preheader).
727 assert(!L->contains(ExitBlock) && "Exit block is in the loop?");
737 // We need to reprocess this loop, it could be unswitched again.
740 // Now that we know that the loop is never entered when this condition is a
741 // particular value, rewrite the loop with this info. We know that this will
747 /// SplitExitEdges - Split all of the edges from inside the loop to their exit
749 void LoopUnswitch::SplitExitEdges(Loop *L,
757 // Although SplitBlockPredecessors doesn't preserve loop-simplify in
769 /// UnswitchNontrivialCondition - We determined that the loop is profitable
770 /// to unswitch when LIC equal Val. Split it into loop versions and test the
771 /// condition outside of either loop. Return the loops created as Out1/Out2.
773 Loop *L) {
775 DEBUG(dbgs() << "loop-unswitch: Unswitching loop %"
791 // We want the loop to come after the preheader, but before the exit blocks.
797 // Split all of the edges from inside the loop to their exit blocks. Update
805 // Add exit blocks to the loop blocks.
808 // Next step, clone all of the basic blocks that make up the loop (including
809 // the loop preheader and exit blocks), keeping track of the mapping between
826 // Now we create the new Loop object for the versioned loop.
827 Loop *NewLoop = CloneLoop(L, L->getParentLoop(), VMap, LI, LPM);
830 // Probably clone more loop-unswitch related loop properties.
833 Loop *ParentLoop = L->getParentLoop();
835 // Make sure to add the cloned preheader and exit blocks to the parent loop
842 // The new exit block should be in the same loop as the old one.
843 if (Loop *ExitBBLoop = LI->getLoopFor(ExitBlocks[i]))
880 // Rewrite the original preheader to select between versions of the loop.
885 // Emit the new branch that selects between the two versions of this loop.
903 // It's possible that simplifying one loop could cause the other to be
924 Loop *L, LPPassManager *LPM) {
943 // the value specified by Val in the specified loop, or we know it does NOT have
945 void LoopUnswitch::RewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC,
963 // in the loop with the appropriate one directly.
989 // is certainly NOT "Val". As such, simplify any uses in the loop that we
1020 // If the DeadCase successor dominates the loop latch, then the
1027 // and hooked up so as to preserve the loop structure, because
1029 // loop structure and put the block on a dead code path.
1063 /// loop, walk over it and constant prop, dce, and fold control flow where
1064 /// possible. Note that this is effectively a very simple loop-structure-aware
1065 /// optimizer. During processing of this loop, L could very well be deleted, so
1068 /// FIXME: When the loop optimizer is more mature, separate this out to a new
1071 void LoopUnswitch::SimplifyCode(std::vector<Instruction*> &Worklist, Loop *L) {
1129 // Remove Succ from the loop tree.
