1 //===- LoopIndexSplit.cpp - Loop Index Splitting 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 file implements Loop Index Splitting Pass. This pass handles three
13 // [1] Loop is eliminated when loop body is executed only once. For example,
14 // for (i = 0; i < N; ++i) {
20 // [2] Loop's iteration space is shrunk if loop body is executed for certain
21 // range only. For example,
23 // for (i = 0; i < N; ++i) {
24 // if ( i > A && i < B) {
28 // is trnasformed to iterators from A to B, if A > 0 and B < N.
30 // [3] Loop is split if the loop body is dominated by an branch. For example,
32 // for (i = LB; i < UB; ++i) { if (i < SV) A; else B; }
34 // is transformed into
36 // for (i = LB; i < min(UB, AEV); ++i)
38 // for (i = max(LB, BSV); i < UB; ++i);
40 //===----------------------------------------------------------------------===//
42 #define DEBUG_TYPE "loop-index-split"
44 #include "llvm/Transforms/Scalar.h"
45 #include "llvm/IntrinsicInst.h"
46 #include "llvm/Analysis/LoopPass.h"
47 #include "llvm/Analysis/ScalarEvolution.h"
48 #include "llvm/Analysis/Dominators.h"
49 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
50 #include "llvm/Transforms/Utils/Cloning.h"
51 #include "llvm/Transforms/Utils/Local.h"
52 #include "llvm/Support/Compiler.h"
53 #include "llvm/ADT/DepthFirstIterator.h"
54 #include "llvm/ADT/Statistic.h"
58 STATISTIC(NumIndexSplit, "Number of loop index split");
59 STATISTIC(NumIndexSplitRemoved, "Number of loops eliminated by loop index split");
60 STATISTIC(NumRestrictBounds, "Number of loop iteration space restricted");
64 class VISIBILITY_HIDDEN LoopIndexSplit : public LoopPass {
67 static char ID; // Pass ID, replacement for typeid
68 LoopIndexSplit() : LoopPass(&ID) {}
70 // Index split Loop L. Return true if loop is split.
71 bool runOnLoop(Loop *L, LPPassManager &LPM);
73 void getAnalysisUsage(AnalysisUsage &AU) const {
74 AU.addPreserved<ScalarEvolution>();
75 AU.addRequiredID(LCSSAID);
76 AU.addPreservedID(LCSSAID);
77 AU.addRequired<LoopInfo>();
78 AU.addPreserved<LoopInfo>();
79 AU.addRequiredID(LoopSimplifyID);
80 AU.addPreservedID(LoopSimplifyID);
81 AU.addRequired<DominatorTree>();
82 AU.addRequired<DominanceFrontier>();
83 AU.addPreserved<DominatorTree>();
84 AU.addPreserved<DominanceFrontier>();
88 /// processOneIterationLoop -- Eliminate loop if loop body is executed
89 /// only once. For example,
90 /// for (i = 0; i < N; ++i) {
96 bool processOneIterationLoop();
98 // -- Routines used by updateLoopIterationSpace();
100 /// updateLoopIterationSpace -- Update loop's iteration space if loop
101 /// body is executed for certain IV range only. For example,
103 /// for (i = 0; i < N; ++i) {
104 /// if ( i > A && i < B) {
108 /// is transformed to iterators from A to B, if A > 0 and B < N.
110 bool updateLoopIterationSpace();
112 /// restrictLoopBound - Op dominates loop body. Op compares an IV based value
113 /// with a loop invariant value. Update loop's lower and upper bound based on
114 /// the loop invariant value.
115 bool restrictLoopBound(ICmpInst &Op);
117 // --- Routines used by splitLoop(). --- /
121 /// removeBlocks - Remove basic block DeadBB and all blocks dominated by
122 /// DeadBB. This routine is used to remove split condition's dead branch,
123 /// dominated by DeadBB. LiveBB dominates split conidition's other branch.
124 void removeBlocks(BasicBlock *DeadBB, Loop *LP, BasicBlock *LiveBB);
126 /// moveExitCondition - Move exit condition EC into split condition block.
127 void moveExitCondition(BasicBlock *CondBB, BasicBlock *ActiveBB,
128 BasicBlock *ExitBB, ICmpInst *EC, ICmpInst *SC,
129 PHINode *IV, Instruction *IVAdd, Loop *LP,
132 /// updatePHINodes - CFG has been changed.
134 /// - ExitBB's single predecessor was Latch
135 /// - Latch's second successor was Header
137 /// - ExitBB's single predecessor was Header
138 /// - Latch's one and only successor was Header
140 /// Update ExitBB PHINodes' to reflect this change.
141 void updatePHINodes(BasicBlock *ExitBB, BasicBlock *Latch,
143 PHINode *IV, Instruction *IVIncrement, Loop *LP);
145 // --- Utility routines --- /
147 /// cleanBlock - A block is considered clean if all non terminal
148 /// instructions are either PHINodes or IV based values.
149 bool cleanBlock(BasicBlock *BB);
151 /// IVisLT - If Op is comparing IV based value with an loop invariant and
152 /// IV based value is less than the loop invariant then return the loop
153 /// invariant. Otherwise return NULL.
154 Value * IVisLT(ICmpInst &Op);
156 /// IVisLE - If Op is comparing IV based value with an loop invariant and
157 /// IV based value is less than or equal to the loop invariant then
158 /// return the loop invariant. Otherwise return NULL.
159 Value * IVisLE(ICmpInst &Op);
161 /// IVisGT - If Op is comparing IV based value with an loop invariant and
162 /// IV based value is greater than the loop invariant then return the loop
163 /// invariant. Otherwise return NULL.
164 Value * IVisGT(ICmpInst &Op);
166 /// IVisGE - If Op is comparing IV based value with an loop invariant and
167 /// IV based value is greater than or equal to the loop invariant then
168 /// return the loop invariant. Otherwise return NULL.
169 Value * IVisGE(ICmpInst &Op);
173 // Current Loop information.
178 DominanceFrontier *DF;
181 ICmpInst *ExitCondition;
182 ICmpInst *SplitCondition;
185 Instruction *IVIncrement;
186 SmallPtrSet<Value *, 4> IVBasedValues;
190 char LoopIndexSplit::ID = 0;
191 static RegisterPass<LoopIndexSplit>
192 X("loop-index-split", "Index Split Loops");
194 Pass *llvm::createLoopIndexSplitPass() {
195 return new LoopIndexSplit();
198 // Index split Loop L. Return true if loop is split.
199 bool LoopIndexSplit::runOnLoop(Loop *IncomingLoop, LPPassManager &LPM_Ref) {
203 // FIXME - Nested loops make dominator info updates tricky.
204 if (!L->getSubLoops().empty())
207 DT = &getAnalysis<DominatorTree>();
208 LI = &getAnalysis<LoopInfo>();
209 DF = &getAnalysis<DominanceFrontier>();
211 // Initialize loop data.
212 IndVar = L->getCanonicalInductionVariable();
213 if (!IndVar) return false;
215 bool P1InLoop = L->contains(IndVar->getIncomingBlock(1));
216 IVStartValue = IndVar->getIncomingValue(!P1InLoop);
217 IVIncrement = dyn_cast<Instruction>(IndVar->getIncomingValue(P1InLoop));
218 if (!IVIncrement) return false;
220 IVBasedValues.clear();
221 IVBasedValues.insert(IndVar);
222 IVBasedValues.insert(IVIncrement);
223 for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
225 for(BasicBlock::iterator BI = (*I)->begin(), BE = (*I)->end();
227 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(BI))
228 if (BO != IVIncrement
229 && (BO->getOpcode() == Instruction::Add
230 || BO->getOpcode() == Instruction::Sub))
231 if (IVBasedValues.count(BO->getOperand(0))
232 && L->isLoopInvariant(BO->getOperand(1)))
233 IVBasedValues.insert(BO);
236 // Reject loop if loop exit condition is not suitable.
237 BasicBlock *ExitingBlock = L->getExitingBlock();
240 BranchInst *EBR = dyn_cast<BranchInst>(ExitingBlock->getTerminator());
241 if (!EBR) return false;
242 ExitCondition = dyn_cast<ICmpInst>(EBR->getCondition());
243 if (!ExitCondition) return false;
244 if (ExitingBlock != L->getLoopLatch()) return false;
245 IVExitValue = ExitCondition->getOperand(1);
246 if (!L->isLoopInvariant(IVExitValue))
247 IVExitValue = ExitCondition->getOperand(0);
248 if (!L->isLoopInvariant(IVExitValue))
251 // If start value is more then exit value where induction variable
252 // increments by 1 then we are potentially dealing with an infinite loop.
253 // Do not index split this loop.
254 if (ConstantInt *SV = dyn_cast<ConstantInt>(IVStartValue))
255 if (ConstantInt *EV = dyn_cast<ConstantInt>(IVExitValue))
256 if (SV->getSExtValue() > EV->getSExtValue())
259 if (processOneIterationLoop())
262 if (updateLoopIterationSpace())
271 // --- Helper routines ---
272 // isUsedOutsideLoop - Returns true iff V is used outside the loop L.
273 static bool isUsedOutsideLoop(Value *V, Loop *L) {
274 for(Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ++UI)
275 if (!L->contains(cast<Instruction>(*UI)->getParent()))
281 static Value *getPlusOne(Value *V, bool Sign, Instruction *InsertPt) {
282 ConstantInt *One = ConstantInt::get(V->getType(), 1, Sign);
283 return BinaryOperator::CreateAdd(V, One, "lsp", InsertPt);
287 static Value *getMinusOne(Value *V, bool Sign, Instruction *InsertPt) {
288 ConstantInt *One = ConstantInt::get(V->getType(), 1, Sign);
289 return BinaryOperator::CreateSub(V, One, "lsp", InsertPt);
292 // Return min(V1, V1)
293 static Value *getMin(Value *V1, Value *V2, bool Sign, Instruction *InsertPt) {
295 Value *C = new ICmpInst(Sign ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
296 V1, V2, "lsp", InsertPt);
297 return SelectInst::Create(C, V1, V2, "lsp", InsertPt);
300 // Return max(V1, V2)
301 static Value *getMax(Value *V1, Value *V2, bool Sign, Instruction *InsertPt) {
303 Value *C = new ICmpInst(Sign ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
304 V1, V2, "lsp", InsertPt);
305 return SelectInst::Create(C, V2, V1, "lsp", InsertPt);
308 /// processOneIterationLoop -- Eliminate loop if loop body is executed
309 /// only once. For example,
310 /// for (i = 0; i < N; ++i) {
316 bool LoopIndexSplit::processOneIterationLoop() {
317 SplitCondition = NULL;
318 BasicBlock *Latch = L->getLoopLatch();
319 BasicBlock *Header = L->getHeader();
320 BranchInst *BR = dyn_cast<BranchInst>(Header->getTerminator());
321 if (!BR) return false;
322 if (!isa<BranchInst>(Latch->getTerminator())) return false;
323 if (BR->isUnconditional()) return false;
324 SplitCondition = dyn_cast<ICmpInst>(BR->getCondition());
325 if (!SplitCondition) return false;
326 if (SplitCondition == ExitCondition) return false;
327 if (SplitCondition->getPredicate() != ICmpInst::ICMP_EQ) return false;
328 if (BR->getOperand(1) != Latch) return false;
329 if (!IVBasedValues.count(SplitCondition->getOperand(0))
330 && !IVBasedValues.count(SplitCondition->getOperand(1)))
333 // If IV is used outside the loop then this loop traversal is required.
334 // FIXME: Calculate and use last IV value.
335 if (isUsedOutsideLoop(IVIncrement, L))
338 // If BR operands are not IV or not loop invariants then skip this loop.
339 Value *OPV = SplitCondition->getOperand(0);
340 Value *SplitValue = SplitCondition->getOperand(1);
341 if (!L->isLoopInvariant(SplitValue)) {
342 Value *T = SplitValue;
346 if (!L->isLoopInvariant(SplitValue))
348 Instruction *OPI = dyn_cast<Instruction>(OPV);
351 if (OPI->getParent() != Header || isUsedOutsideLoop(OPI, L))
353 Value *StartValue = IVStartValue;
354 Value *ExitValue = IVExitValue;;
357 // If BR operand is IV based then use this operand to calculate
358 // effective conditions for loop body.
359 BinaryOperator *BOPV = dyn_cast<BinaryOperator>(OPV);
362 if (BOPV->getOpcode() != Instruction::Add)
364 StartValue = BinaryOperator::CreateAdd(OPV, StartValue, "" , BR);
365 ExitValue = BinaryOperator::CreateAdd(OPV, ExitValue, "" , BR);
368 if (!cleanBlock(Header))
371 if (!cleanBlock(Latch))
374 // If the merge point for BR is not loop latch then skip this loop.
375 if (BR->getSuccessor(0) != Latch) {
376 DominanceFrontier::iterator DF0 = DF->find(BR->getSuccessor(0));
377 assert (DF0 != DF->end() && "Unable to find dominance frontier");
378 if (!DF0->second.count(Latch))
382 if (BR->getSuccessor(1) != Latch) {
383 DominanceFrontier::iterator DF1 = DF->find(BR->getSuccessor(1));
384 assert (DF1 != DF->end() && "Unable to find dominance frontier");
385 if (!DF1->second.count(Latch))
389 // Now, Current loop L contains compare instruction
390 // that compares induction variable, IndVar, against loop invariant. And
391 // entire (i.e. meaningful) loop body is dominated by this compare
392 // instruction. In such case eliminate
393 // loop structure surrounding this loop body. For example,
394 // for (int i = start; i < end; ++i) {
395 // if ( i == somevalue) {
399 // can be transformed into
400 // if (somevalue >= start && somevalue < end) {
405 // Replace index variable with split value in loop body. Loop body is executed
406 // only when index variable is equal to split value.
407 IndVar->replaceAllUsesWith(SplitValue);
409 // Replace split condition in header.
411 // SplitCondition : icmp eq i32 IndVar, SplitValue
413 // c1 = icmp uge i32 SplitValue, StartValue
414 // c2 = icmp ult i32 SplitValue, ExitValue
416 Instruction *C1 = new ICmpInst(ExitCondition->isSignedPredicate() ?
417 ICmpInst::ICMP_SGE : ICmpInst::ICMP_UGE,
418 SplitValue, StartValue, "lisplit", BR);
420 CmpInst::Predicate C2P = ExitCondition->getPredicate();
421 BranchInst *LatchBR = cast<BranchInst>(Latch->getTerminator());
422 if (LatchBR->getOperand(0) != Header)
423 C2P = CmpInst::getInversePredicate(C2P);
424 Instruction *C2 = new ICmpInst(C2P, SplitValue, ExitValue, "lisplit", BR);
425 Instruction *NSplitCond = BinaryOperator::CreateAnd(C1, C2, "lisplit", BR);
427 SplitCondition->replaceAllUsesWith(NSplitCond);
428 SplitCondition->eraseFromParent();
430 // Remove Latch to Header edge.
431 BasicBlock *LatchSucc = NULL;
432 Header->removePredecessor(Latch);
433 for (succ_iterator SI = succ_begin(Latch), E = succ_end(Latch);
439 // Clean up latch block.
440 Value *LatchBRCond = LatchBR->getCondition();
441 LatchBR->setUnconditionalDest(LatchSucc);
442 RecursivelyDeleteTriviallyDeadInstructions(LatchBRCond);
444 LPM->deleteLoopFromQueue(L);
446 // Update Dominator Info.
447 // Only CFG change done is to remove Latch to Header edge. This
448 // does not change dominator tree because Latch did not dominate
451 DominanceFrontier::iterator HeaderDF = DF->find(Header);
452 if (HeaderDF != DF->end())
453 DF->removeFromFrontier(HeaderDF, Header);
455 DominanceFrontier::iterator LatchDF = DF->find(Latch);
456 if (LatchDF != DF->end())
457 DF->removeFromFrontier(LatchDF, Header);
460 ++NumIndexSplitRemoved;
464 /// restrictLoopBound - Op dominates loop body. Op compares an IV based value
465 /// with a loop invariant value. Update loop's lower and upper bound based on
466 /// the loop invariant value.
467 bool LoopIndexSplit::restrictLoopBound(ICmpInst &Op) {
468 bool Sign = Op.isSignedPredicate();
469 Instruction *PHTerm = L->getLoopPreheader()->getTerminator();
471 if (IVisGT(*ExitCondition) || IVisGE(*ExitCondition)) {
473 cast<BranchInst>(ExitCondition->getParent()->getTerminator());
474 ExitCondition->setPredicate(ExitCondition->getInversePredicate());
475 BasicBlock *T = EBR->getSuccessor(0);
476 EBR->setSuccessor(0, EBR->getSuccessor(1));
477 EBR->setSuccessor(1, T);
480 // New upper and lower bounds.
483 if (Value *V = IVisLT(Op)) {
484 // Restrict upper bound.
485 if (IVisLE(*ExitCondition))
486 V = getMinusOne(V, Sign, PHTerm);
487 NUB = getMin(V, IVExitValue, Sign, PHTerm);
488 } else if (Value *V = IVisLE(Op)) {
489 // Restrict upper bound.
490 if (IVisLT(*ExitCondition))
491 V = getPlusOne(V, Sign, PHTerm);
492 NUB = getMin(V, IVExitValue, Sign, PHTerm);
493 } else if (Value *V = IVisGT(Op)) {
494 // Restrict lower bound.
495 V = getPlusOne(V, Sign, PHTerm);
496 NLB = getMax(V, IVStartValue, Sign, PHTerm);
497 } else if (Value *V = IVisGE(Op))
498 // Restrict lower bound.
499 NLB = getMax(V, IVStartValue, Sign, PHTerm);
505 unsigned i = IndVar->getBasicBlockIndex(L->getLoopPreheader());
506 IndVar->setIncomingValue(i, NLB);
510 unsigned i = (ExitCondition->getOperand(0) != IVExitValue);
511 ExitCondition->setOperand(i, NUB);
516 /// updateLoopIterationSpace -- Update loop's iteration space if loop
517 /// body is executed for certain IV range only. For example,
519 /// for (i = 0; i < N; ++i) {
520 /// if ( i > A && i < B) {
524 /// is transformed to iterators from A to B, if A > 0 and B < N.
526 bool LoopIndexSplit::updateLoopIterationSpace() {
527 SplitCondition = NULL;
528 if (ExitCondition->getPredicate() == ICmpInst::ICMP_NE
529 || ExitCondition->getPredicate() == ICmpInst::ICMP_EQ)
531 BasicBlock *Latch = L->getLoopLatch();
532 BasicBlock *Header = L->getHeader();
533 BranchInst *BR = dyn_cast<BranchInst>(Header->getTerminator());
534 if (!BR) return false;
535 if (!isa<BranchInst>(Latch->getTerminator())) return false;
536 if (BR->isUnconditional()) return false;
537 BinaryOperator *AND = dyn_cast<BinaryOperator>(BR->getCondition());
538 if (!AND) return false;
539 if (AND->getOpcode() != Instruction::And) return false;
540 ICmpInst *Op0 = dyn_cast<ICmpInst>(AND->getOperand(0));
541 ICmpInst *Op1 = dyn_cast<ICmpInst>(AND->getOperand(1));
544 IVBasedValues.insert(AND);
545 IVBasedValues.insert(Op0);
546 IVBasedValues.insert(Op1);
547 if (!cleanBlock(Header)) return false;
548 BasicBlock *ExitingBlock = ExitCondition->getParent();
549 if (!cleanBlock(ExitingBlock)) return false;
551 // If the merge point for BR is not loop latch then skip this loop.
552 if (BR->getSuccessor(0) != Latch) {
553 DominanceFrontier::iterator DF0 = DF->find(BR->getSuccessor(0));
554 assert (DF0 != DF->end() && "Unable to find dominance frontier");
555 if (!DF0->second.count(Latch))
559 if (BR->getSuccessor(1) != Latch) {
560 DominanceFrontier::iterator DF1 = DF->find(BR->getSuccessor(1));
561 assert (DF1 != DF->end() && "Unable to find dominance frontier");
562 if (!DF1->second.count(Latch))
566 // Verify that loop exiting block has only two predecessor, where one pred
567 // is split condition block. The other predecessor will become exiting block's
568 // dominator after CFG is updated. TODO : Handle CFG's where exiting block has
569 // more then two predecessors. This requires extra work in updating dominator
571 BasicBlock *ExitingBBPred = NULL;
572 for (pred_iterator PI = pred_begin(ExitingBlock), PE = pred_end(ExitingBlock);
574 BasicBlock *BB = *PI;
583 if (!restrictLoopBound(*Op0))
586 if (!restrictLoopBound(*Op1))
590 if (BR->getSuccessor(0) == ExitingBlock)
591 BR->setUnconditionalDest(BR->getSuccessor(1));
593 BR->setUnconditionalDest(BR->getSuccessor(0));
595 AND->eraseFromParent();
596 if (Op0->use_empty())
597 Op0->eraseFromParent();
598 if (Op1->use_empty())
599 Op1->eraseFromParent();
601 // Update domiantor info. Now, ExitingBlock has only one predecessor,
602 // ExitingBBPred, and it is ExitingBlock's immediate domiantor.
603 DT->changeImmediateDominator(ExitingBlock, ExitingBBPred);
605 BasicBlock *ExitBlock = ExitingBlock->getTerminator()->getSuccessor(1);
606 if (L->contains(ExitBlock))
607 ExitBlock = ExitingBlock->getTerminator()->getSuccessor(0);
609 // If ExitingBlock is a member of the loop basic blocks' DF list then
610 // replace ExitingBlock with header and exit block in the DF list
611 DominanceFrontier::iterator ExitingBlockDF = DF->find(ExitingBlock);
612 for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
615 if (BB == Header || BB == ExitingBlock)
617 DominanceFrontier::iterator BBDF = DF->find(BB);
618 DominanceFrontier::DomSetType::iterator DomSetI = BBDF->second.begin();
619 DominanceFrontier::DomSetType::iterator DomSetE = BBDF->second.end();
620 while (DomSetI != DomSetE) {
621 DominanceFrontier::DomSetType::iterator CurrentItr = DomSetI;
623 BasicBlock *DFBB = *CurrentItr;
624 if (DFBB == ExitingBlock) {
625 BBDF->second.erase(DFBB);
626 for (DominanceFrontier::DomSetType::iterator
627 EBI = ExitingBlockDF->second.begin(),
628 EBE = ExitingBlockDF->second.end(); EBI != EBE; ++EBI)
629 BBDF->second.insert(*EBI);
637 /// removeBlocks - Remove basic block DeadBB and all blocks dominated by DeadBB.
638 /// This routine is used to remove split condition's dead branch, dominated by
639 /// DeadBB. LiveBB dominates split conidition's other branch.
640 void LoopIndexSplit::removeBlocks(BasicBlock *DeadBB, Loop *LP,
641 BasicBlock *LiveBB) {
643 // First update DeadBB's dominance frontier.
644 SmallVector<BasicBlock *, 8> FrontierBBs;
645 DominanceFrontier::iterator DeadBBDF = DF->find(DeadBB);
646 if (DeadBBDF != DF->end()) {
647 SmallVector<BasicBlock *, 8> PredBlocks;
649 DominanceFrontier::DomSetType DeadBBSet = DeadBBDF->second;
650 for (DominanceFrontier::DomSetType::iterator DeadBBSetI = DeadBBSet.begin(),
651 DeadBBSetE = DeadBBSet.end(); DeadBBSetI != DeadBBSetE; ++DeadBBSetI)
653 BasicBlock *FrontierBB = *DeadBBSetI;
654 FrontierBBs.push_back(FrontierBB);
656 // Rremove any PHI incoming edge from blocks dominated by DeadBB.
658 for(pred_iterator PI = pred_begin(FrontierBB), PE = pred_end(FrontierBB);
661 if (P == DeadBB || DT->dominates(DeadBB, P))
662 PredBlocks.push_back(P);
665 for(BasicBlock::iterator FBI = FrontierBB->begin(), FBE = FrontierBB->end();
667 if (PHINode *PN = dyn_cast<PHINode>(FBI)) {
668 for(SmallVector<BasicBlock *, 8>::iterator PI = PredBlocks.begin(),
669 PE = PredBlocks.end(); PI != PE; ++PI) {
671 PN->removeIncomingValue(P);
680 // Now remove DeadBB and all nodes dominated by DeadBB in df order.
681 SmallVector<BasicBlock *, 32> WorkList;
682 DomTreeNode *DN = DT->getNode(DeadBB);
683 for (df_iterator<DomTreeNode*> DI = df_begin(DN),
684 E = df_end(DN); DI != E; ++DI) {
685 BasicBlock *BB = DI->getBlock();
686 WorkList.push_back(BB);
687 BB->replaceAllUsesWith(UndefValue::get(Type::LabelTy));
690 while (!WorkList.empty()) {
691 BasicBlock *BB = WorkList.back(); WorkList.pop_back();
692 LPM->deleteSimpleAnalysisValue(BB, LP);
693 for(BasicBlock::iterator BBI = BB->begin(), BBE = BB->end();
695 Instruction *I = BBI;
697 I->replaceAllUsesWith(UndefValue::get(I->getType()));
698 LPM->deleteSimpleAnalysisValue(I, LP);
699 I->eraseFromParent();
704 BB->eraseFromParent();
707 // Update Frontier BBs' dominator info.
708 while (!FrontierBBs.empty()) {
709 BasicBlock *FBB = FrontierBBs.back(); FrontierBBs.pop_back();
710 BasicBlock *NewDominator = FBB->getSinglePredecessor();
712 pred_iterator PI = pred_begin(FBB), PE = pred_end(FBB);
715 if (NewDominator != LiveBB) {
716 for(; PI != PE; ++PI) {
719 NewDominator = LiveBB;
722 NewDominator = DT->findNearestCommonDominator(NewDominator, P);
726 assert (NewDominator && "Unable to fix dominator info.");
727 DT->changeImmediateDominator(FBB, NewDominator);
728 DF->changeImmediateDominator(FBB, NewDominator, DT);
733 // moveExitCondition - Move exit condition EC into split condition block CondBB.
734 void LoopIndexSplit::moveExitCondition(BasicBlock *CondBB, BasicBlock *ActiveBB,
735 BasicBlock *ExitBB, ICmpInst *EC,
736 ICmpInst *SC, PHINode *IV,
737 Instruction *IVAdd, Loop *LP,
738 unsigned ExitValueNum) {
740 BasicBlock *ExitingBB = EC->getParent();
741 Instruction *CurrentBR = CondBB->getTerminator();
743 // Move exit condition into split condition block.
744 EC->moveBefore(CurrentBR);
745 EC->setOperand(ExitValueNum == 0 ? 1 : 0, IV);
747 // Move exiting block's branch into split condition block. Update its branch
749 BranchInst *ExitingBR = cast<BranchInst>(ExitingBB->getTerminator());
750 ExitingBR->moveBefore(CurrentBR);
751 BasicBlock *OrigDestBB = NULL;
752 if (ExitingBR->getSuccessor(0) == ExitBB) {
753 OrigDestBB = ExitingBR->getSuccessor(1);
754 ExitingBR->setSuccessor(1, ActiveBB);
757 OrigDestBB = ExitingBR->getSuccessor(0);
758 ExitingBR->setSuccessor(0, ActiveBB);
761 // Remove split condition and current split condition branch.
762 SC->eraseFromParent();
763 CurrentBR->eraseFromParent();
765 // Connect exiting block to original destination.
766 BranchInst::Create(OrigDestBB, ExitingBB);
769 updatePHINodes(ExitBB, ExitingBB, CondBB, IV, IVAdd, LP);
771 // Fix dominator info.
772 // ExitBB is now dominated by CondBB
773 DT->changeImmediateDominator(ExitBB, CondBB);
774 DF->changeImmediateDominator(ExitBB, CondBB, DT);
776 // Basicblocks dominated by ActiveBB may have ExitingBB or
777 // a basic block outside the loop in their DF list. If so,
778 // replace it with CondBB.
779 DomTreeNode *Node = DT->getNode(ActiveBB);
780 for (df_iterator<DomTreeNode *> DI = df_begin(Node), DE = df_end(Node);
782 BasicBlock *BB = DI->getBlock();
783 DominanceFrontier::iterator BBDF = DF->find(BB);
784 DominanceFrontier::DomSetType::iterator DomSetI = BBDF->second.begin();
785 DominanceFrontier::DomSetType::iterator DomSetE = BBDF->second.end();
786 while (DomSetI != DomSetE) {
787 DominanceFrontier::DomSetType::iterator CurrentItr = DomSetI;
789 BasicBlock *DFBB = *CurrentItr;
790 if (DFBB == ExitingBB || !L->contains(DFBB)) {
791 BBDF->second.erase(DFBB);
792 BBDF->second.insert(CondBB);
798 /// updatePHINodes - CFG has been changed.
800 /// - ExitBB's single predecessor was Latch
801 /// - Latch's second successor was Header
803 /// - ExitBB's single predecessor is Header
804 /// - Latch's one and only successor is Header
806 /// Update ExitBB PHINodes' to reflect this change.
807 void LoopIndexSplit::updatePHINodes(BasicBlock *ExitBB, BasicBlock *Latch,
809 PHINode *IV, Instruction *IVIncrement,
812 for (BasicBlock::iterator BI = ExitBB->begin(), BE = ExitBB->end();
814 PHINode *PN = dyn_cast<PHINode>(BI);
819 Value *V = PN->getIncomingValueForBlock(Latch);
820 if (PHINode *PHV = dyn_cast<PHINode>(V)) {
821 // PHV is in Latch. PHV has one use is in ExitBB PHINode. And one use
822 // in Header which is new incoming value for PN.
824 for (Value::use_iterator UI = PHV->use_begin(), E = PHV->use_end();
826 if (PHINode *U = dyn_cast<PHINode>(*UI))
827 if (LP->contains(U->getParent())) {
832 // Add incoming value from header only if PN has any use inside the loop.
834 PN->addIncoming(NewV, Header);
836 } else if (Instruction *PHI = dyn_cast<Instruction>(V)) {
837 // If this instruction is IVIncrement then IV is new incoming value
838 // from header otherwise this instruction must be incoming value from
839 // header because loop is in LCSSA form.
840 if (PHI == IVIncrement)
841 PN->addIncoming(IV, Header);
843 PN->addIncoming(V, Header);
845 // Otherwise this is an incoming value from header because loop is in
847 PN->addIncoming(V, Header);
849 // Remove incoming value from Latch.
850 PN->removeIncomingValue(Latch);
854 bool LoopIndexSplit::splitLoop() {
855 SplitCondition = NULL;
856 if (ExitCondition->getPredicate() == ICmpInst::ICMP_NE
857 || ExitCondition->getPredicate() == ICmpInst::ICMP_EQ)
859 BasicBlock *Header = L->getHeader();
860 BasicBlock *Latch = L->getLoopLatch();
861 BranchInst *SBR = NULL; // Split Condition Branch
862 BranchInst *EBR = cast<BranchInst>(ExitCondition->getParent()->getTerminator());
863 // If Exiting block includes loop variant instructions then this
864 // loop may not be split safely.
865 BasicBlock *ExitingBlock = ExitCondition->getParent();
866 if (!cleanBlock(ExitingBlock)) return false;
868 for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
870 BranchInst *BR = dyn_cast<BranchInst>((*I)->getTerminator());
871 if (!BR || BR->isUnconditional()) continue;
872 ICmpInst *CI = dyn_cast<ICmpInst>(BR->getCondition());
873 if (!CI || CI == ExitCondition
874 || CI->getPredicate() == ICmpInst::ICMP_NE
875 || CI->getPredicate() == ICmpInst::ICMP_EQ)
878 // Unable to handle triangle loops at the moment.
879 // In triangle loop, split condition is in header and one of the
880 // the split destination is loop latch. If split condition is EQ
881 // then such loops are already handle in processOneIterationLoop().
883 && (Latch == BR->getSuccessor(0) || Latch == BR->getSuccessor(1)))
886 // If the block does not dominate the latch then this is not a diamond.
887 // Such loop may not benefit from index split.
888 if (!DT->dominates((*I), Latch))
891 // If split condition branches heads do not have single predecessor,
892 // SplitCondBlock, then is not possible to remove inactive branch.
893 if (!BR->getSuccessor(0)->getSinglePredecessor()
894 || !BR->getSuccessor(1)->getSinglePredecessor())
897 // If the merge point for BR is not loop latch then skip this condition.
898 if (BR->getSuccessor(0) != Latch) {
899 DominanceFrontier::iterator DF0 = DF->find(BR->getSuccessor(0));
900 assert (DF0 != DF->end() && "Unable to find dominance frontier");
901 if (!DF0->second.count(Latch))
905 if (BR->getSuccessor(1) != Latch) {
906 DominanceFrontier::iterator DF1 = DF->find(BR->getSuccessor(1));
907 assert (DF1 != DF->end() && "Unable to find dominance frontier");
908 if (!DF1->second.count(Latch))
919 // If the predicate sign does not match then skip.
920 if (ExitCondition->isSignedPredicate() != SplitCondition->isSignedPredicate())
923 unsigned EVOpNum = (ExitCondition->getOperand(1) == IVExitValue);
924 unsigned SVOpNum = IVBasedValues.count(SplitCondition->getOperand(0));
925 Value *SplitValue = SplitCondition->getOperand(SVOpNum);
926 if (!L->isLoopInvariant(SplitValue))
928 if (!IVBasedValues.count(SplitCondition->getOperand(!SVOpNum)))
931 // Normalize loop conditions so that it is easier to calculate new loop
933 if (IVisGT(*ExitCondition) || IVisGE(*ExitCondition)) {
934 ExitCondition->setPredicate(ExitCondition->getInversePredicate());
935 BasicBlock *T = EBR->getSuccessor(0);
936 EBR->setSuccessor(0, EBR->getSuccessor(1));
937 EBR->setSuccessor(1, T);
940 if (IVisGT(*SplitCondition) || IVisGE(*SplitCondition)) {
941 SplitCondition->setPredicate(SplitCondition->getInversePredicate());
942 BasicBlock *T = SBR->getSuccessor(0);
943 SBR->setSuccessor(0, SBR->getSuccessor(1));
944 SBR->setSuccessor(1, T);
947 //[*] Calculate new loop bounds.
948 Value *AEV = SplitValue;
949 Value *BSV = SplitValue;
950 bool Sign = SplitCondition->isSignedPredicate();
951 Instruction *PHTerm = L->getLoopPreheader()->getTerminator();
953 if (IVisLT(*ExitCondition)) {
954 if (IVisLT(*SplitCondition)) {
957 else if (IVisLE(*SplitCondition)) {
958 AEV = getPlusOne(SplitValue, Sign, PHTerm);
959 BSV = getPlusOne(SplitValue, Sign, PHTerm);
961 assert (0 && "Unexpected split condition!");
964 else if (IVisLE(*ExitCondition)) {
965 if (IVisLT(*SplitCondition)) {
966 AEV = getMinusOne(SplitValue, Sign, PHTerm);
968 else if (IVisLE(*SplitCondition)) {
969 BSV = getPlusOne(SplitValue, Sign, PHTerm);
971 assert (0 && "Unexpected split condition!");
974 assert (0 && "Unexpected exit condition!");
976 AEV = getMin(AEV, IVExitValue, Sign, PHTerm);
977 BSV = getMax(BSV, IVStartValue, Sign, PHTerm);
980 DenseMap<const Value *, Value *> ValueMap;
981 Loop *BLoop = CloneLoop(L, LPM, LI, ValueMap, this);
984 // [*] ALoop's exiting edge enters BLoop's header.
985 // ALoop's original exit block becomes BLoop's exit block.
986 PHINode *B_IndVar = cast<PHINode>(ValueMap[IndVar]);
987 BasicBlock *A_ExitingBlock = ExitCondition->getParent();
988 BranchInst *A_ExitInsn =
989 dyn_cast<BranchInst>(A_ExitingBlock->getTerminator());
990 assert (A_ExitInsn && "Unable to find suitable loop exit branch");
991 BasicBlock *B_ExitBlock = A_ExitInsn->getSuccessor(1);
992 BasicBlock *B_Header = BLoop->getHeader();
993 if (ALoop->contains(B_ExitBlock)) {
994 B_ExitBlock = A_ExitInsn->getSuccessor(0);
995 A_ExitInsn->setSuccessor(0, B_Header);
997 A_ExitInsn->setSuccessor(1, B_Header);
999 // [*] Update ALoop's exit value using new exit value.
1000 ExitCondition->setOperand(EVOpNum, AEV);
1002 // [*] Update BLoop's header phi nodes. Remove incoming PHINode's from
1003 // original loop's preheader. Add incoming PHINode values from
1004 // ALoop's exiting block. Update BLoop header's domiantor info.
1006 // Collect inverse map of Header PHINodes.
1007 DenseMap<Value *, Value *> InverseMap;
1008 for (BasicBlock::iterator BI = ALoop->getHeader()->begin(),
1009 BE = ALoop->getHeader()->end(); BI != BE; ++BI) {
1010 if (PHINode *PN = dyn_cast<PHINode>(BI)) {
1011 PHINode *PNClone = cast<PHINode>(ValueMap[PN]);
1012 InverseMap[PNClone] = PN;
1017 BasicBlock *A_Preheader = ALoop->getLoopPreheader();
1018 for (BasicBlock::iterator BI = B_Header->begin(), BE = B_Header->end();
1020 if (PHINode *PN = dyn_cast<PHINode>(BI)) {
1021 // Remove incoming value from original preheader.
1022 PN->removeIncomingValue(A_Preheader);
1024 // Add incoming value from A_ExitingBlock.
1026 PN->addIncoming(BSV, A_ExitingBlock);
1028 PHINode *OrigPN = cast<PHINode>(InverseMap[PN]);
1030 // If loop header is also loop exiting block then
1031 // OrigPN is incoming value for B loop header.
1032 if (A_ExitingBlock == ALoop->getHeader())
1035 V2 = OrigPN->getIncomingValueForBlock(A_ExitingBlock);
1036 PN->addIncoming(V2, A_ExitingBlock);
1042 DT->changeImmediateDominator(B_Header, A_ExitingBlock);
1043 DF->changeImmediateDominator(B_Header, A_ExitingBlock, DT);
1045 // [*] Update BLoop's exit block. Its new predecessor is BLoop's exit
1046 // block. Remove incoming PHINode values from ALoop's exiting block.
1047 // Add new incoming values from BLoop's incoming exiting value.
1048 // Update BLoop exit block's dominator info..
1049 BasicBlock *B_ExitingBlock = cast<BasicBlock>(ValueMap[A_ExitingBlock]);
1050 for (BasicBlock::iterator BI = B_ExitBlock->begin(), BE = B_ExitBlock->end();
1052 if (PHINode *PN = dyn_cast<PHINode>(BI)) {
1053 PN->addIncoming(ValueMap[PN->getIncomingValueForBlock(A_ExitingBlock)],
1055 PN->removeIncomingValue(A_ExitingBlock);
1060 DT->changeImmediateDominator(B_ExitBlock, B_ExitingBlock);
1061 DF->changeImmediateDominator(B_ExitBlock, B_ExitingBlock, DT);
1063 //[*] Split ALoop's exit edge. This creates a new block which
1064 // serves two purposes. First one is to hold PHINode defnitions
1065 // to ensure that ALoop's LCSSA form. Second use it to act
1066 // as a preheader for BLoop.
1067 BasicBlock *A_ExitBlock = SplitEdge(A_ExitingBlock, B_Header, this);
1069 //[*] Preserve ALoop's LCSSA form. Create new forwarding PHINodes
1070 // in A_ExitBlock to redefine outgoing PHI definitions from ALoop.
1071 for(BasicBlock::iterator BI = B_Header->begin(), BE = B_Header->end();
1073 if (PHINode *PN = dyn_cast<PHINode>(BI)) {
1074 Value *V1 = PN->getIncomingValueForBlock(A_ExitBlock);
1075 PHINode *newPHI = PHINode::Create(PN->getType(), PN->getName());
1076 newPHI->addIncoming(V1, A_ExitingBlock);
1077 A_ExitBlock->getInstList().push_front(newPHI);
1078 PN->removeIncomingValue(A_ExitBlock);
1079 PN->addIncoming(newPHI, A_ExitBlock);
1084 //[*] Eliminate split condition's inactive branch from ALoop.
1085 BasicBlock *A_SplitCondBlock = SplitCondition->getParent();
1086 BranchInst *A_BR = cast<BranchInst>(A_SplitCondBlock->getTerminator());
1087 BasicBlock *A_InactiveBranch = NULL;
1088 BasicBlock *A_ActiveBranch = NULL;
1089 A_ActiveBranch = A_BR->getSuccessor(0);
1090 A_InactiveBranch = A_BR->getSuccessor(1);
1091 A_BR->setUnconditionalDest(A_ActiveBranch);
1092 removeBlocks(A_InactiveBranch, L, A_ActiveBranch);
1094 //[*] Eliminate split condition's inactive branch in from BLoop.
1095 BasicBlock *B_SplitCondBlock = cast<BasicBlock>(ValueMap[A_SplitCondBlock]);
1096 BranchInst *B_BR = cast<BranchInst>(B_SplitCondBlock->getTerminator());
1097 BasicBlock *B_InactiveBranch = NULL;
1098 BasicBlock *B_ActiveBranch = NULL;
1099 B_ActiveBranch = B_BR->getSuccessor(1);
1100 B_InactiveBranch = B_BR->getSuccessor(0);
1101 B_BR->setUnconditionalDest(B_ActiveBranch);
1102 removeBlocks(B_InactiveBranch, BLoop, B_ActiveBranch);
1104 BasicBlock *A_Header = ALoop->getHeader();
1105 if (A_ExitingBlock == A_Header)
1108 //[*] Move exit condition into split condition block to avoid
1109 // executing dead loop iteration.
1110 ICmpInst *B_ExitCondition = cast<ICmpInst>(ValueMap[ExitCondition]);
1111 Instruction *B_IndVarIncrement = cast<Instruction>(ValueMap[IVIncrement]);
1112 ICmpInst *B_SplitCondition = cast<ICmpInst>(ValueMap[SplitCondition]);
1114 moveExitCondition(A_SplitCondBlock, A_ActiveBranch, A_ExitBlock, ExitCondition,
1115 cast<ICmpInst>(SplitCondition), IndVar, IVIncrement,
1118 moveExitCondition(B_SplitCondBlock, B_ActiveBranch,
1119 B_ExitBlock, B_ExitCondition,
1120 B_SplitCondition, B_IndVar, B_IndVarIncrement,
1127 /// cleanBlock - A block is considered clean if all non terminal instructions
1128 /// are either, PHINodes, IV based.
1129 bool LoopIndexSplit::cleanBlock(BasicBlock *BB) {
1130 Instruction *Terminator = BB->getTerminator();
1131 for(BasicBlock::iterator BI = BB->begin(), BE = BB->end();
1133 Instruction *I = BI;
1135 if (isa<PHINode>(I) || I == Terminator || I == ExitCondition
1136 || I == SplitCondition || IVBasedValues.count(I)
1137 || isa<DbgInfoIntrinsic>(I))
1140 if (I->mayWriteToMemory())
1143 // I is used only inside this block then it is OK.
1144 bool usedOutsideBB = false;
1145 for (Value::use_iterator UI = I->use_begin(), UE = I->use_end();
1147 Instruction *U = cast<Instruction>(UI);
1148 if (U->getParent() != BB)
1149 usedOutsideBB = true;
1154 // Otherwise we have a instruction that may not allow loop spliting.
1160 /// IVisLT - If Op is comparing IV based value with an loop invariant and
1161 /// IV based value is less than the loop invariant then return the loop
1162 /// invariant. Otherwise return NULL.
1163 Value * LoopIndexSplit::IVisLT(ICmpInst &Op) {
1164 ICmpInst::Predicate P = Op.getPredicate();
1165 if ((P == ICmpInst::ICMP_SLT || P == ICmpInst::ICMP_ULT)
1166 && IVBasedValues.count(Op.getOperand(0))
1167 && L->isLoopInvariant(Op.getOperand(1)))
1168 return Op.getOperand(1);
1170 if ((P == ICmpInst::ICMP_SGT || P == ICmpInst::ICMP_UGT)
1171 && IVBasedValues.count(Op.getOperand(1))
1172 && L->isLoopInvariant(Op.getOperand(0)))
1173 return Op.getOperand(0);
1178 /// IVisLE - If Op is comparing IV based value with an loop invariant and
1179 /// IV based value is less than or equal to the loop invariant then
1180 /// return the loop invariant. Otherwise return NULL.
1181 Value * LoopIndexSplit::IVisLE(ICmpInst &Op) {
1182 ICmpInst::Predicate P = Op.getPredicate();
1183 if ((P == ICmpInst::ICMP_SLE || P == ICmpInst::ICMP_ULE)
1184 && IVBasedValues.count(Op.getOperand(0))
1185 && L->isLoopInvariant(Op.getOperand(1)))
1186 return Op.getOperand(1);
1188 if ((P == ICmpInst::ICMP_SGE || P == ICmpInst::ICMP_UGE)
1189 && IVBasedValues.count(Op.getOperand(1))
1190 && L->isLoopInvariant(Op.getOperand(0)))
1191 return Op.getOperand(0);
1196 /// IVisGT - If Op is comparing IV based value with an loop invariant and
1197 /// IV based value is greater than the loop invariant then return the loop
1198 /// invariant. Otherwise return NULL.
1199 Value * LoopIndexSplit::IVisGT(ICmpInst &Op) {
1200 ICmpInst::Predicate P = Op.getPredicate();
1201 if ((P == ICmpInst::ICMP_SGT || P == ICmpInst::ICMP_UGT)
1202 && IVBasedValues.count(Op.getOperand(0))
1203 && L->isLoopInvariant(Op.getOperand(1)))
1204 return Op.getOperand(1);
1206 if ((P == ICmpInst::ICMP_SLT || P == ICmpInst::ICMP_ULT)
1207 && IVBasedValues.count(Op.getOperand(1))
1208 && L->isLoopInvariant(Op.getOperand(0)))
1209 return Op.getOperand(0);
1214 /// IVisGE - If Op is comparing IV based value with an loop invariant and
1215 /// IV based value is greater than or equal to the loop invariant then
1216 /// return the loop invariant. Otherwise return NULL.
1217 Value * LoopIndexSplit::IVisGE(ICmpInst &Op) {
1218 ICmpInst::Predicate P = Op.getPredicate();
1219 if ((P == ICmpInst::ICMP_SGE || P == ICmpInst::ICMP_UGE)
1220 && IVBasedValues.count(Op.getOperand(0))
1221 && L->isLoopInvariant(Op.getOperand(1)))
1222 return Op.getOperand(1);
1224 if ((P == ICmpInst::ICMP_SLE || P == ICmpInst::ICMP_ULE)
1225 && IVBasedValues.count(Op.getOperand(1))
1226 && L->isLoopInvariant(Op.getOperand(0)))
1227 return Op.getOperand(0);