1 //===- LoopSimplify.cpp - Loop Canonicalization Pass ----------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This pass performs several transformations to transform natural loops into a
11 // simpler form, which makes subsequent analyses and transformations simpler and
14 // Loop pre-header insertion guarantees that there is a single, non-critical
15 // entry edge from outside of the loop to the loop header. This simplifies a
16 // number of analyses and transformations, such as LICM.
18 // Loop exit-block insertion guarantees that all exit blocks from the loop
19 // (blocks which are outside of the loop that have predecessors inside of the
20 // loop) only have predecessors from inside of the loop (and are thus dominated
21 // by the loop header). This simplifies transformations such as store-sinking
22 // that are built into LICM.
24 // This pass also guarantees that loops will have exactly one backedge.
26 // Indirectbr instructions introduce several complications. If the loop
27 // contains or is entered by an indirectbr instruction, it may not be possible
28 // to transform the loop and make these guarantees. Client code should check
29 // that these conditions are true before relying on them.
31 // Note that the simplifycfg pass will clean up blocks which are split out but
32 // end up being unnecessary, so usage of this pass should not pessimize
35 // This pass obviously modifies the CFG, but updates loop information and
36 // dominator information.
38 //===----------------------------------------------------------------------===//
40 #define DEBUG_TYPE "loopsimplify"
41 #include "llvm/Transforms/Scalar.h"
42 #include "llvm/Constants.h"
43 #include "llvm/Instructions.h"
44 #include "llvm/IntrinsicInst.h"
45 #include "llvm/Function.h"
46 #include "llvm/LLVMContext.h"
47 #include "llvm/Type.h"
48 #include "llvm/Analysis/AliasAnalysis.h"
49 #include "llvm/Analysis/Dominators.h"
50 #include "llvm/Analysis/InstructionSimplify.h"
51 #include "llvm/Analysis/LoopPass.h"
52 #include "llvm/Analysis/ScalarEvolution.h"
53 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
54 #include "llvm/Transforms/Utils/Local.h"
55 #include "llvm/Support/CFG.h"
56 #include "llvm/Support/Debug.h"
57 #include "llvm/ADT/SetOperations.h"
58 #include "llvm/ADT/SetVector.h"
59 #include "llvm/ADT/Statistic.h"
60 #include "llvm/ADT/DepthFirstIterator.h"
63 STATISTIC(NumInserted
, "Number of pre-header or exit blocks inserted");
64 STATISTIC(NumNested
, "Number of nested loops split out");
67 struct LoopSimplify
: public LoopPass
{
68 static char ID
; // Pass identification, replacement for typeid
69 LoopSimplify() : LoopPass(ID
) {
70 initializeLoopSimplifyPass(*PassRegistry::getPassRegistry());
73 // AA - If we have an alias analysis object to update, this is it, otherwise
80 virtual bool runOnLoop(Loop
*L
, LPPassManager
&LPM
);
82 virtual void getAnalysisUsage(AnalysisUsage
&AU
) const {
83 // We need loop information to identify the loops...
84 AU
.addRequired
<DominatorTree
>();
85 AU
.addPreserved
<DominatorTree
>();
87 AU
.addRequired
<LoopInfo
>();
88 AU
.addPreserved
<LoopInfo
>();
90 AU
.addPreserved
<AliasAnalysis
>();
91 AU
.addPreserved
<ScalarEvolution
>();
92 AU
.addPreservedID(BreakCriticalEdgesID
); // No critical edges added.
93 AU
.addPreserved
<DominanceFrontier
>();
94 AU
.addPreservedID(LCSSAID
);
97 /// verifyAnalysis() - Verify LoopSimplifyForm's guarantees.
98 void verifyAnalysis() const;
101 bool ProcessLoop(Loop
*L
, LPPassManager
&LPM
);
102 BasicBlock
*RewriteLoopExitBlock(Loop
*L
, BasicBlock
*Exit
);
103 BasicBlock
*InsertPreheaderForLoop(Loop
*L
);
104 Loop
*SeparateNestedLoop(Loop
*L
, LPPassManager
&LPM
);
105 BasicBlock
*InsertUniqueBackedgeBlock(Loop
*L
, BasicBlock
*Preheader
);
106 void PlaceSplitBlockCarefully(BasicBlock
*NewBB
,
107 SmallVectorImpl
<BasicBlock
*> &SplitPreds
,
112 char LoopSimplify::ID
= 0;
113 INITIALIZE_PASS_BEGIN(LoopSimplify
, "loopsimplify",
114 "Canonicalize natural loops", true, false)
115 INITIALIZE_PASS_DEPENDENCY(DominatorTree
)
116 INITIALIZE_PASS_DEPENDENCY(LoopInfo
)
117 INITIALIZE_PASS_END(LoopSimplify
, "loopsimplify",
118 "Canonicalize natural loops", true, false)
120 // Publically exposed interface to pass...
121 char &llvm::LoopSimplifyID
= LoopSimplify::ID
;
122 Pass
*llvm::createLoopSimplifyPass() { return new LoopSimplify(); }
124 /// runOnLoop - Run down all loops in the CFG (recursively, but we could do
125 /// it in any convenient order) inserting preheaders...
127 bool LoopSimplify::runOnLoop(Loop
*l
, LPPassManager
&LPM
) {
129 bool Changed
= false;
130 LI
= &getAnalysis
<LoopInfo
>();
131 AA
= getAnalysisIfAvailable
<AliasAnalysis
>();
132 DT
= &getAnalysis
<DominatorTree
>();
133 SE
= getAnalysisIfAvailable
<ScalarEvolution
>();
135 Changed
|= ProcessLoop(L
, LPM
);
140 /// ProcessLoop - Walk the loop structure in depth first order, ensuring that
141 /// all loops have preheaders.
143 bool LoopSimplify::ProcessLoop(Loop
*L
, LPPassManager
&LPM
) {
144 bool Changed
= false;
147 // Check to see that no blocks (other than the header) in this loop have
148 // predecessors that are not in the loop. This is not valid for natural
149 // loops, but can occur if the blocks are unreachable. Since they are
150 // unreachable we can just shamelessly delete those CFG edges!
151 for (Loop::block_iterator BB
= L
->block_begin(), E
= L
->block_end();
153 if (*BB
== L
->getHeader()) continue;
155 SmallPtrSet
<BasicBlock
*, 4> BadPreds
;
156 for (pred_iterator PI
= pred_begin(*BB
),
157 PE
= pred_end(*BB
); PI
!= PE
; ++PI
) {
163 // Delete each unique out-of-loop (and thus dead) predecessor.
164 for (SmallPtrSet
<BasicBlock
*, 4>::iterator I
= BadPreds
.begin(),
165 E
= BadPreds
.end(); I
!= E
; ++I
) {
167 DEBUG(dbgs() << "LoopSimplify: Deleting edge from dead predecessor ";
168 WriteAsOperand(dbgs(), *I
, false);
171 // Inform each successor of each dead pred.
172 for (succ_iterator SI
= succ_begin(*I
), SE
= succ_end(*I
); SI
!= SE
; ++SI
)
173 (*SI
)->removePredecessor(*I
);
174 // Zap the dead pred's terminator and replace it with unreachable.
175 TerminatorInst
*TI
= (*I
)->getTerminator();
176 TI
->replaceAllUsesWith(UndefValue::get(TI
->getType()));
177 (*I
)->getTerminator()->eraseFromParent();
178 new UnreachableInst((*I
)->getContext(), *I
);
183 // If there are exiting blocks with branches on undef, resolve the undef in
184 // the direction which will exit the loop. This will help simplify loop
185 // trip count computations.
186 SmallVector
<BasicBlock
*, 8> ExitingBlocks
;
187 L
->getExitingBlocks(ExitingBlocks
);
188 for (SmallVectorImpl
<BasicBlock
*>::iterator I
= ExitingBlocks
.begin(),
189 E
= ExitingBlocks
.end(); I
!= E
; ++I
)
190 if (BranchInst
*BI
= dyn_cast
<BranchInst
>((*I
)->getTerminator()))
191 if (BI
->isConditional()) {
192 if (UndefValue
*Cond
= dyn_cast
<UndefValue
>(BI
->getCondition())) {
194 DEBUG(dbgs() << "LoopSimplify: Resolving \"br i1 undef\" to exit in ";
195 WriteAsOperand(dbgs(), *I
, false);
198 BI
->setCondition(ConstantInt::get(Cond
->getType(),
199 !L
->contains(BI
->getSuccessor(0))));
204 // Does the loop already have a preheader? If so, don't insert one.
205 BasicBlock
*Preheader
= L
->getLoopPreheader();
207 Preheader
= InsertPreheaderForLoop(L
);
214 // Next, check to make sure that all exit nodes of the loop only have
215 // predecessors that are inside of the loop. This check guarantees that the
216 // loop preheader/header will dominate the exit blocks. If the exit block has
217 // predecessors from outside of the loop, split the edge now.
218 SmallVector
<BasicBlock
*, 8> ExitBlocks
;
219 L
->getExitBlocks(ExitBlocks
);
221 SmallSetVector
<BasicBlock
*, 8> ExitBlockSet(ExitBlocks
.begin(),
223 for (SmallSetVector
<BasicBlock
*, 8>::iterator I
= ExitBlockSet
.begin(),
224 E
= ExitBlockSet
.end(); I
!= E
; ++I
) {
225 BasicBlock
*ExitBlock
= *I
;
226 for (pred_iterator PI
= pred_begin(ExitBlock
), PE
= pred_end(ExitBlock
);
228 // Must be exactly this loop: no subloops, parent loops, or non-loop preds
230 if (!L
->contains(*PI
)) {
231 if (RewriteLoopExitBlock(L
, ExitBlock
)) {
239 // If the header has more than two predecessors at this point (from the
240 // preheader and from multiple backedges), we must adjust the loop.
241 BasicBlock
*LoopLatch
= L
->getLoopLatch();
243 // If this is really a nested loop, rip it out into a child loop. Don't do
244 // this for loops with a giant number of backedges, just factor them into a
245 // common backedge instead.
246 if (L
->getNumBackEdges() < 8) {
247 if (SeparateNestedLoop(L
, LPM
)) {
249 // This is a big restructuring change, reprocess the whole loop.
251 // GCC doesn't tail recursion eliminate this.
256 // If we either couldn't, or didn't want to, identify nesting of the loops,
257 // insert a new block that all backedges target, then make it jump to the
259 LoopLatch
= InsertUniqueBackedgeBlock(L
, Preheader
);
266 // Scan over the PHI nodes in the loop header. Since they now have only two
267 // incoming values (the loop is canonicalized), we may have simplified the PHI
268 // down to 'X = phi [X, Y]', which should be replaced with 'Y'.
270 for (BasicBlock::iterator I
= L
->getHeader()->begin();
271 (PN
= dyn_cast
<PHINode
>(I
++)); )
272 if (Value
*V
= SimplifyInstruction(PN
, 0, DT
))
273 if (LI
->replacementPreservesLCSSAForm(PN
, V
)) {
274 if (AA
) AA
->deleteValue(PN
);
275 PN
->replaceAllUsesWith(V
);
276 PN
->eraseFromParent();
279 // If this loop has multiple exits and the exits all go to the same
280 // block, attempt to merge the exits. This helps several passes, such
281 // as LoopRotation, which do not support loops with multiple exits.
282 // SimplifyCFG also does this (and this code uses the same utility
283 // function), however this code is loop-aware, where SimplifyCFG is
284 // not. That gives it the advantage of being able to hoist
285 // loop-invariant instructions out of the way to open up more
286 // opportunities, and the disadvantage of having the responsibility
287 // to preserve dominator information.
288 bool UniqueExit
= true;
289 if (!ExitBlocks
.empty())
290 for (unsigned i
= 1, e
= ExitBlocks
.size(); i
!= e
; ++i
)
291 if (ExitBlocks
[i
] != ExitBlocks
[0]) {
296 for (unsigned i
= 0, e
= ExitingBlocks
.size(); i
!= e
; ++i
) {
297 BasicBlock
*ExitingBlock
= ExitingBlocks
[i
];
298 if (!ExitingBlock
->getSinglePredecessor()) continue;
299 BranchInst
*BI
= dyn_cast
<BranchInst
>(ExitingBlock
->getTerminator());
300 if (!BI
|| !BI
->isConditional()) continue;
301 CmpInst
*CI
= dyn_cast
<CmpInst
>(BI
->getCondition());
302 if (!CI
|| CI
->getParent() != ExitingBlock
) continue;
304 // Attempt to hoist out all instructions except for the
305 // comparison and the branch.
306 bool AllInvariant
= true;
307 for (BasicBlock::iterator I
= ExitingBlock
->begin(); &*I
!= BI
; ) {
308 Instruction
*Inst
= I
++;
309 // Skip debug info intrinsics.
310 if (isa
<DbgInfoIntrinsic
>(Inst
))
314 if (!L
->makeLoopInvariant(Inst
, Changed
,
315 Preheader
? Preheader
->getTerminator() : 0)) {
316 AllInvariant
= false;
320 if (!AllInvariant
) continue;
322 // The block has now been cleared of all instructions except for
323 // a comparison and a conditional branch. SimplifyCFG may be able
325 if (!FoldBranchToCommonDest(BI
)) continue;
327 // Success. The block is now dead, so remove it from the loop,
328 // update the dominator tree and dominance frontier, and delete it.
330 DEBUG(dbgs() << "LoopSimplify: Eliminating exiting block ";
331 WriteAsOperand(dbgs(), ExitingBlock
, false);
334 assert(pred_begin(ExitingBlock
) == pred_end(ExitingBlock
));
336 LI
->removeBlock(ExitingBlock
);
338 DominanceFrontier
*DF
= getAnalysisIfAvailable
<DominanceFrontier
>();
339 DomTreeNode
*Node
= DT
->getNode(ExitingBlock
);
340 const std::vector
<DomTreeNodeBase
<BasicBlock
> *> &Children
=
342 while (!Children
.empty()) {
343 DomTreeNode
*Child
= Children
.front();
344 DT
->changeImmediateDominator(Child
, Node
->getIDom());
345 if (DF
) DF
->changeImmediateDominator(Child
->getBlock(),
346 Node
->getIDom()->getBlock(),
349 DT
->eraseNode(ExitingBlock
);
350 if (DF
) DF
->removeBlock(ExitingBlock
);
352 BI
->getSuccessor(0)->removePredecessor(ExitingBlock
);
353 BI
->getSuccessor(1)->removePredecessor(ExitingBlock
);
354 ExitingBlock
->eraseFromParent();
361 /// InsertPreheaderForLoop - Once we discover that a loop doesn't have a
362 /// preheader, this method is called to insert one. This method has two phases:
363 /// preheader insertion and analysis updating.
365 BasicBlock
*LoopSimplify::InsertPreheaderForLoop(Loop
*L
) {
366 BasicBlock
*Header
= L
->getHeader();
368 // Compute the set of predecessors of the loop that are not in the loop.
369 SmallVector
<BasicBlock
*, 8> OutsideBlocks
;
370 for (pred_iterator PI
= pred_begin(Header
), PE
= pred_end(Header
);
373 if (!L
->contains(P
)) { // Coming in from outside the loop?
374 // If the loop is branched to from an indirect branch, we won't
375 // be able to fully transform the loop, because it prohibits
377 if (isa
<IndirectBrInst
>(P
->getTerminator())) return 0;
380 OutsideBlocks
.push_back(P
);
384 // Split out the loop pre-header.
386 SplitBlockPredecessors(Header
, &OutsideBlocks
[0], OutsideBlocks
.size(),
389 DEBUG(dbgs() << "LoopSimplify: Creating pre-header ";
390 WriteAsOperand(dbgs(), NewBB
, false);
393 // Make sure that NewBB is put someplace intelligent, which doesn't mess up
394 // code layout too horribly.
395 PlaceSplitBlockCarefully(NewBB
, OutsideBlocks
, L
);
400 /// RewriteLoopExitBlock - Ensure that the loop preheader dominates all exit
401 /// blocks. This method is used to split exit blocks that have predecessors
402 /// outside of the loop.
403 BasicBlock
*LoopSimplify::RewriteLoopExitBlock(Loop
*L
, BasicBlock
*Exit
) {
404 SmallVector
<BasicBlock
*, 8> LoopBlocks
;
405 for (pred_iterator I
= pred_begin(Exit
), E
= pred_end(Exit
); I
!= E
; ++I
) {
407 if (L
->contains(P
)) {
408 // Don't do this if the loop is exited via an indirect branch.
409 if (isa
<IndirectBrInst
>(P
->getTerminator())) return 0;
411 LoopBlocks
.push_back(P
);
415 assert(!LoopBlocks
.empty() && "No edges coming in from outside the loop?");
416 BasicBlock
*NewBB
= SplitBlockPredecessors(Exit
, &LoopBlocks
[0],
417 LoopBlocks
.size(), ".loopexit",
420 DEBUG(dbgs() << "LoopSimplify: Creating dedicated exit block ";
421 WriteAsOperand(dbgs(), NewBB
, false);
427 /// AddBlockAndPredsToSet - Add the specified block, and all of its
428 /// predecessors, to the specified set, if it's not already in there. Stop
429 /// predecessor traversal when we reach StopBlock.
430 static void AddBlockAndPredsToSet(BasicBlock
*InputBB
, BasicBlock
*StopBlock
,
431 std::set
<BasicBlock
*> &Blocks
) {
432 std::vector
<BasicBlock
*> WorkList
;
433 WorkList
.push_back(InputBB
);
435 BasicBlock
*BB
= WorkList
.back(); WorkList
.pop_back();
436 if (Blocks
.insert(BB
).second
&& BB
!= StopBlock
)
437 // If BB is not already processed and it is not a stop block then
438 // insert its predecessor in the work list
439 for (pred_iterator I
= pred_begin(BB
), E
= pred_end(BB
); I
!= E
; ++I
) {
440 BasicBlock
*WBB
= *I
;
441 WorkList
.push_back(WBB
);
443 } while(!WorkList
.empty());
446 /// FindPHIToPartitionLoops - The first part of loop-nestification is to find a
447 /// PHI node that tells us how to partition the loops.
448 static PHINode
*FindPHIToPartitionLoops(Loop
*L
, DominatorTree
*DT
,
449 AliasAnalysis
*AA
, LoopInfo
*LI
) {
450 for (BasicBlock::iterator I
= L
->getHeader()->begin(); isa
<PHINode
>(I
); ) {
451 PHINode
*PN
= cast
<PHINode
>(I
);
453 if (Value
*V
= SimplifyInstruction(PN
, 0, DT
))
454 if (LI
->replacementPreservesLCSSAForm(PN
, V
)) {
455 // This is a degenerate PHI already, don't modify it!
456 PN
->replaceAllUsesWith(V
);
457 if (AA
) AA
->deleteValue(PN
);
458 PN
->eraseFromParent();
462 // Scan this PHI node looking for a use of the PHI node by itself.
463 for (unsigned i
= 0, e
= PN
->getNumIncomingValues(); i
!= e
; ++i
)
464 if (PN
->getIncomingValue(i
) == PN
&&
465 L
->contains(PN
->getIncomingBlock(i
)))
466 // We found something tasty to remove.
472 // PlaceSplitBlockCarefully - If the block isn't already, move the new block to
473 // right after some 'outside block' block. This prevents the preheader from
474 // being placed inside the loop body, e.g. when the loop hasn't been rotated.
475 void LoopSimplify::PlaceSplitBlockCarefully(BasicBlock
*NewBB
,
476 SmallVectorImpl
<BasicBlock
*> &SplitPreds
,
478 // Check to see if NewBB is already well placed.
479 Function::iterator BBI
= NewBB
; --BBI
;
480 for (unsigned i
= 0, e
= SplitPreds
.size(); i
!= e
; ++i
) {
481 if (&*BBI
== SplitPreds
[i
])
485 // If it isn't already after an outside block, move it after one. This is
486 // always good as it makes the uncond branch from the outside block into a
489 // Figure out *which* outside block to put this after. Prefer an outside
490 // block that neighbors a BB actually in the loop.
491 BasicBlock
*FoundBB
= 0;
492 for (unsigned i
= 0, e
= SplitPreds
.size(); i
!= e
; ++i
) {
493 Function::iterator BBI
= SplitPreds
[i
];
494 if (++BBI
!= NewBB
->getParent()->end() &&
496 FoundBB
= SplitPreds
[i
];
501 // If our heuristic for a *good* bb to place this after doesn't find
502 // anything, just pick something. It's likely better than leaving it within
505 FoundBB
= SplitPreds
[0];
506 NewBB
->moveAfter(FoundBB
);
510 /// SeparateNestedLoop - If this loop has multiple backedges, try to pull one of
511 /// them out into a nested loop. This is important for code that looks like
516 /// br cond, Loop, Next
518 /// br cond2, Loop, Out
520 /// To identify this common case, we look at the PHI nodes in the header of the
521 /// loop. PHI nodes with unchanging values on one backedge correspond to values
522 /// that change in the "outer" loop, but not in the "inner" loop.
524 /// If we are able to separate out a loop, return the new outer loop that was
527 Loop
*LoopSimplify::SeparateNestedLoop(Loop
*L
, LPPassManager
&LPM
) {
528 PHINode
*PN
= FindPHIToPartitionLoops(L
, DT
, AA
, LI
);
529 if (PN
== 0) return 0; // No known way to partition.
531 // Pull out all predecessors that have varying values in the loop. This
532 // handles the case when a PHI node has multiple instances of itself as
534 SmallVector
<BasicBlock
*, 8> OuterLoopPreds
;
535 for (unsigned i
= 0, e
= PN
->getNumIncomingValues(); i
!= e
; ++i
)
536 if (PN
->getIncomingValue(i
) != PN
||
537 !L
->contains(PN
->getIncomingBlock(i
))) {
538 // We can't split indirectbr edges.
539 if (isa
<IndirectBrInst
>(PN
->getIncomingBlock(i
)->getTerminator()))
542 OuterLoopPreds
.push_back(PN
->getIncomingBlock(i
));
545 DEBUG(dbgs() << "LoopSimplify: Splitting out a new outer loop\n");
547 // If ScalarEvolution is around and knows anything about values in
548 // this loop, tell it to forget them, because we're about to
549 // substantially change it.
553 BasicBlock
*Header
= L
->getHeader();
554 BasicBlock
*NewBB
= SplitBlockPredecessors(Header
, &OuterLoopPreds
[0],
555 OuterLoopPreds
.size(),
558 // Make sure that NewBB is put someplace intelligent, which doesn't mess up
559 // code layout too horribly.
560 PlaceSplitBlockCarefully(NewBB
, OuterLoopPreds
, L
);
562 // Create the new outer loop.
563 Loop
*NewOuter
= new Loop();
565 // Change the parent loop to use the outer loop as its child now.
566 if (Loop
*Parent
= L
->getParentLoop())
567 Parent
->replaceChildLoopWith(L
, NewOuter
);
569 LI
->changeTopLevelLoop(L
, NewOuter
);
571 // L is now a subloop of our outer loop.
572 NewOuter
->addChildLoop(L
);
574 // Add the new loop to the pass manager queue.
575 LPM
.insertLoopIntoQueue(NewOuter
);
577 for (Loop::block_iterator I
= L
->block_begin(), E
= L
->block_end();
579 NewOuter
->addBlockEntry(*I
);
581 // Now reset the header in L, which had been moved by
582 // SplitBlockPredecessors for the outer loop.
583 L
->moveToHeader(Header
);
585 // Determine which blocks should stay in L and which should be moved out to
586 // the Outer loop now.
587 std::set
<BasicBlock
*> BlocksInL
;
588 for (pred_iterator PI
=pred_begin(Header
), E
= pred_end(Header
); PI
!=E
; ++PI
) {
590 if (DT
->dominates(Header
, P
))
591 AddBlockAndPredsToSet(P
, Header
, BlocksInL
);
594 // Scan all of the loop children of L, moving them to OuterLoop if they are
595 // not part of the inner loop.
596 const std::vector
<Loop
*> &SubLoops
= L
->getSubLoops();
597 for (size_t I
= 0; I
!= SubLoops
.size(); )
598 if (BlocksInL
.count(SubLoops
[I
]->getHeader()))
599 ++I
; // Loop remains in L
601 NewOuter
->addChildLoop(L
->removeChildLoop(SubLoops
.begin() + I
));
603 // Now that we know which blocks are in L and which need to be moved to
604 // OuterLoop, move any blocks that need it.
605 for (unsigned i
= 0; i
!= L
->getBlocks().size(); ++i
) {
606 BasicBlock
*BB
= L
->getBlocks()[i
];
607 if (!BlocksInL
.count(BB
)) {
608 // Move this block to the parent, updating the exit blocks sets
609 L
->removeBlockFromLoop(BB
);
611 LI
->changeLoopFor(BB
, NewOuter
);
621 /// InsertUniqueBackedgeBlock - This method is called when the specified loop
622 /// has more than one backedge in it. If this occurs, revector all of these
623 /// backedges to target a new basic block and have that block branch to the loop
624 /// header. This ensures that loops have exactly one backedge.
627 LoopSimplify::InsertUniqueBackedgeBlock(Loop
*L
, BasicBlock
*Preheader
) {
628 assert(L
->getNumBackEdges() > 1 && "Must have > 1 backedge!");
630 // Get information about the loop
631 BasicBlock
*Header
= L
->getHeader();
632 Function
*F
= Header
->getParent();
634 // Unique backedge insertion currently depends on having a preheader.
638 // Figure out which basic blocks contain back-edges to the loop header.
639 std::vector
<BasicBlock
*> BackedgeBlocks
;
640 for (pred_iterator I
= pred_begin(Header
), E
= pred_end(Header
); I
!= E
; ++I
){
643 // Indirectbr edges cannot be split, so we must fail if we find one.
644 if (isa
<IndirectBrInst
>(P
->getTerminator()))
647 if (P
!= Preheader
) BackedgeBlocks
.push_back(P
);
650 // Create and insert the new backedge block...
651 BasicBlock
*BEBlock
= BasicBlock::Create(Header
->getContext(),
652 Header
->getName()+".backedge", F
);
653 BranchInst
*BETerminator
= BranchInst::Create(Header
, BEBlock
);
655 DEBUG(dbgs() << "LoopSimplify: Inserting unique backedge block ";
656 WriteAsOperand(dbgs(), BEBlock
, false);
659 // Move the new backedge block to right after the last backedge block.
660 Function::iterator InsertPos
= BackedgeBlocks
.back(); ++InsertPos
;
661 F
->getBasicBlockList().splice(InsertPos
, F
->getBasicBlockList(), BEBlock
);
663 // Now that the block has been inserted into the function, create PHI nodes in
664 // the backedge block which correspond to any PHI nodes in the header block.
665 for (BasicBlock::iterator I
= Header
->begin(); isa
<PHINode
>(I
); ++I
) {
666 PHINode
*PN
= cast
<PHINode
>(I
);
667 PHINode
*NewPN
= PHINode::Create(PN
->getType(), PN
->getName()+".be",
669 NewPN
->reserveOperandSpace(BackedgeBlocks
.size());
670 if (AA
) AA
->copyValue(PN
, NewPN
);
672 // Loop over the PHI node, moving all entries except the one for the
673 // preheader over to the new PHI node.
674 unsigned PreheaderIdx
= ~0U;
675 bool HasUniqueIncomingValue
= true;
676 Value
*UniqueValue
= 0;
677 for (unsigned i
= 0, e
= PN
->getNumIncomingValues(); i
!= e
; ++i
) {
678 BasicBlock
*IBB
= PN
->getIncomingBlock(i
);
679 Value
*IV
= PN
->getIncomingValue(i
);
680 if (IBB
== Preheader
) {
683 NewPN
->addIncoming(IV
, IBB
);
684 if (HasUniqueIncomingValue
) {
685 if (UniqueValue
== 0)
687 else if (UniqueValue
!= IV
)
688 HasUniqueIncomingValue
= false;
693 // Delete all of the incoming values from the old PN except the preheader's
694 assert(PreheaderIdx
!= ~0U && "PHI has no preheader entry??");
695 if (PreheaderIdx
!= 0) {
696 PN
->setIncomingValue(0, PN
->getIncomingValue(PreheaderIdx
));
697 PN
->setIncomingBlock(0, PN
->getIncomingBlock(PreheaderIdx
));
699 // Nuke all entries except the zero'th.
700 for (unsigned i
= 0, e
= PN
->getNumIncomingValues()-1; i
!= e
; ++i
)
701 PN
->removeIncomingValue(e
-i
, false);
703 // Finally, add the newly constructed PHI node as the entry for the BEBlock.
704 PN
->addIncoming(NewPN
, BEBlock
);
706 // As an optimization, if all incoming values in the new PhiNode (which is a
707 // subset of the incoming values of the old PHI node) have the same value,
708 // eliminate the PHI Node.
709 if (HasUniqueIncomingValue
) {
710 NewPN
->replaceAllUsesWith(UniqueValue
);
711 if (AA
) AA
->deleteValue(NewPN
);
712 BEBlock
->getInstList().erase(NewPN
);
716 // Now that all of the PHI nodes have been inserted and adjusted, modify the
717 // backedge blocks to just to the BEBlock instead of the header.
718 for (unsigned i
= 0, e
= BackedgeBlocks
.size(); i
!= e
; ++i
) {
719 TerminatorInst
*TI
= BackedgeBlocks
[i
]->getTerminator();
720 for (unsigned Op
= 0, e
= TI
->getNumSuccessors(); Op
!= e
; ++Op
)
721 if (TI
->getSuccessor(Op
) == Header
)
722 TI
->setSuccessor(Op
, BEBlock
);
725 //===--- Update all analyses which we must preserve now -----------------===//
727 // Update Loop Information - we know that this block is now in the current
728 // loop and all parent loops.
729 L
->addBasicBlockToLoop(BEBlock
, LI
->getBase());
731 // Update dominator information
732 DT
->splitBlock(BEBlock
);
733 if (DominanceFrontier
*DF
= getAnalysisIfAvailable
<DominanceFrontier
>())
734 DF
->splitBlock(BEBlock
);
739 void LoopSimplify::verifyAnalysis() const {
740 // It used to be possible to just assert L->isLoopSimplifyForm(), however
741 // with the introduction of indirectbr, there are now cases where it's
742 // not possible to transform a loop as necessary. We can at least check
743 // that there is an indirectbr near any time there's trouble.
745 // Indirectbr can interfere with preheader and unique backedge insertion.
746 if (!L
->getLoopPreheader() || !L
->getLoopLatch()) {
747 bool HasIndBrPred
= false;
748 for (pred_iterator PI
= pred_begin(L
->getHeader()),
749 PE
= pred_end(L
->getHeader()); PI
!= PE
; ++PI
)
750 if (isa
<IndirectBrInst
>((*PI
)->getTerminator())) {
754 assert(HasIndBrPred
&&
755 "LoopSimplify has no excuse for missing loop header info!");
758 // Indirectbr can interfere with exit block canonicalization.
759 if (!L
->hasDedicatedExits()) {
760 bool HasIndBrExiting
= false;
761 SmallVector
<BasicBlock
*, 8> ExitingBlocks
;
762 L
->getExitingBlocks(ExitingBlocks
);
763 for (unsigned i
= 0, e
= ExitingBlocks
.size(); i
!= e
; ++i
)
764 if (isa
<IndirectBrInst
>((ExitingBlocks
[i
])->getTerminator())) {
765 HasIndBrExiting
= true;
768 assert(HasIndBrExiting
&&
769 "LoopSimplify has no excuse for missing exit block info!");