LLVM API Documentation
00001 //===- LoopIndexSplit.cpp - Loop Index Splitting Pass ---------------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file implements Loop Index Splitting Pass. This pass handles three 00011 // kinds of loops. 00012 // 00013 // [1] A loop may be eliminated if the body is executed exactly once. 00014 // For example, 00015 // 00016 // for (i = 0; i < N; ++i) { 00017 // if (i == X) { 00018 // body; 00019 // } 00020 // } 00021 // 00022 // is transformed to 00023 // 00024 // i = X; 00025 // body; 00026 // 00027 // [2] A loop's iteration space may be shrunk if the loop body is executed 00028 // for a proper sub-range of the loop's iteration space. For example, 00029 // 00030 // for (i = 0; i < N; ++i) { 00031 // if (i > A && i < B) { 00032 // ... 00033 // } 00034 // } 00035 // 00036 // is transformed to iterators from A to B, if A > 0 and B < N. 00037 // 00038 // [3] A loop may be split if the loop body is dominated by a branch. 00039 // For example, 00040 // 00041 // for (i = LB; i < UB; ++i) { if (i < SV) A; else B; } 00042 // 00043 // is transformed into 00044 // 00045 // AEV = BSV = SV 00046 // for (i = LB; i < min(UB, AEV); ++i) 00047 // A; 00048 // for (i = max(LB, BSV); i < UB; ++i); 00049 // B; 00050 // 00051 //===----------------------------------------------------------------------===// 00052 00053 #define DEBUG_TYPE "loop-index-split" 00054 00055 #include "llvm/Transforms/Scalar.h" 00056 #include "llvm/IntrinsicInst.h" 00057 #include "llvm/LLVMContext.h" 00058 #include "llvm/Analysis/LoopPass.h" 00059 #include "llvm/Analysis/ScalarEvolution.h" 00060 #include "llvm/Analysis/Dominators.h" 00061 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 00062 #include "llvm/Transforms/Utils/Cloning.h" 00063 #include "llvm/Transforms/Utils/Local.h" 00064 #include "llvm/Support/Compiler.h" 00065 #include "llvm/ADT/DepthFirstIterator.h" 00066 #include "llvm/ADT/Statistic.h" 00067 00068 using namespace llvm; 00069 00070 STATISTIC(NumIndexSplit, "Number of loop index split"); 00071 STATISTIC(NumIndexSplitRemoved, "Number of loops eliminated by loop index split"); 00072 STATISTIC(NumRestrictBounds, "Number of loop iteration space restricted"); 00073 00074 namespace { 00075 00076 class VISIBILITY_HIDDEN LoopIndexSplit : public LoopPass { 00077 00078 public: 00079 static char ID; // Pass ID, replacement for typeid 00080 LoopIndexSplit() : LoopPass(&ID) {} 00081 00082 // Index split Loop L. Return true if loop is split. 00083 bool runOnLoop(Loop *L, LPPassManager &LPM); 00084 00085 void getAnalysisUsage(AnalysisUsage &AU) const { 00086 AU.addPreserved<ScalarEvolution>(); 00087 AU.addRequiredID(LCSSAID); 00088 AU.addPreservedID(LCSSAID); 00089 AU.addRequired<LoopInfo>(); 00090 AU.addPreserved<LoopInfo>(); 00091 AU.addRequiredID(LoopSimplifyID); 00092 AU.addPreservedID(LoopSimplifyID); 00093 AU.addRequired<DominatorTree>(); 00094 AU.addRequired<DominanceFrontier>(); 00095 AU.addPreserved<DominatorTree>(); 00096 AU.addPreserved<DominanceFrontier>(); 00097 } 00098 00099 private: 00100 /// processOneIterationLoop -- Eliminate loop if loop body is executed 00101 /// only once. For example, 00102 /// for (i = 0; i < N; ++i) { 00103 /// if ( i == X) { 00104 /// ... 00105 /// } 00106 /// } 00107 /// 00108 bool processOneIterationLoop(); 00109 00110 // -- Routines used by updateLoopIterationSpace(); 00111 00112 /// updateLoopIterationSpace -- Update loop's iteration space if loop 00113 /// body is executed for certain IV range only. For example, 00114 /// 00115 /// for (i = 0; i < N; ++i) { 00116 /// if ( i > A && i < B) { 00117 /// ... 00118 /// } 00119 /// } 00120 /// is transformed to iterators from A to B, if A > 0 and B < N. 00121 /// 00122 bool updateLoopIterationSpace(); 00123 00124 /// restrictLoopBound - Op dominates loop body. Op compares an IV based value 00125 /// with a loop invariant value. Update loop's lower and upper bound based on 00126 /// the loop invariant value. 00127 bool restrictLoopBound(ICmpInst &Op); 00128 00129 // --- Routines used by splitLoop(). --- / 00130 00131 bool splitLoop(); 00132 00133 /// removeBlocks - Remove basic block DeadBB and all blocks dominated by 00134 /// DeadBB. This routine is used to remove split condition's dead branch, 00135 /// dominated by DeadBB. LiveBB dominates split conidition's other branch. 00136 void removeBlocks(BasicBlock *DeadBB, Loop *LP, BasicBlock *LiveBB); 00137 00138 /// moveExitCondition - Move exit condition EC into split condition block. 00139 void moveExitCondition(BasicBlock *CondBB, BasicBlock *ActiveBB, 00140 BasicBlock *ExitBB, ICmpInst *EC, ICmpInst *SC, 00141 PHINode *IV, Instruction *IVAdd, Loop *LP, 00142 unsigned); 00143 00144 /// updatePHINodes - CFG has been changed. 00145 /// Before 00146 /// - ExitBB's single predecessor was Latch 00147 /// - Latch's second successor was Header 00148 /// Now 00149 /// - ExitBB's single predecessor was Header 00150 /// - Latch's one and only successor was Header 00151 /// 00152 /// Update ExitBB PHINodes' to reflect this change. 00153 void updatePHINodes(BasicBlock *ExitBB, BasicBlock *Latch, 00154 BasicBlock *Header, 00155 PHINode *IV, Instruction *IVIncrement, Loop *LP); 00156 00157 // --- Utility routines --- / 00158 00159 /// cleanBlock - A block is considered clean if all non terminal 00160 /// instructions are either PHINodes or IV based values. 00161 bool cleanBlock(BasicBlock *BB); 00162 00163 /// IVisLT - If Op is comparing IV based value with an loop invariant and 00164 /// IV based value is less than the loop invariant then return the loop 00165 /// invariant. Otherwise return NULL. 00166 Value * IVisLT(ICmpInst &Op); 00167 00168 /// IVisLE - If Op is comparing IV based value with an loop invariant and 00169 /// IV based value is less than or equal to the loop invariant then 00170 /// return the loop invariant. Otherwise return NULL. 00171 Value * IVisLE(ICmpInst &Op); 00172 00173 /// IVisGT - If Op is comparing IV based value with an loop invariant and 00174 /// IV based value is greater than the loop invariant then return the loop 00175 /// invariant. Otherwise return NULL. 00176 Value * IVisGT(ICmpInst &Op); 00177 00178 /// IVisGE - If Op is comparing IV based value with an loop invariant and 00179 /// IV based value is greater than or equal to the loop invariant then 00180 /// return the loop invariant. Otherwise return NULL. 00181 Value * IVisGE(ICmpInst &Op); 00182 00183 private: 00184 00185 // Current Loop information. 00186 Loop *L; 00187 LPPassManager *LPM; 00188 LoopInfo *LI; 00189 DominatorTree *DT; 00190 DominanceFrontier *DF; 00191 00192 PHINode *IndVar; 00193 ICmpInst *ExitCondition; 00194 ICmpInst *SplitCondition; 00195 Value *IVStartValue; 00196 Value *IVExitValue; 00197 Instruction *IVIncrement; 00198 SmallPtrSet<Value *, 4> IVBasedValues; 00199 }; 00200 } 00201 00202 char LoopIndexSplit::ID = 0; 00203 static RegisterPass<LoopIndexSplit> 00204 X("loop-index-split", "Index Split Loops"); 00205 00206 Pass *llvm::createLoopIndexSplitPass() { 00207 return new LoopIndexSplit(); 00208 } 00209 00210 // Index split Loop L. Return true if loop is split. 00211 bool LoopIndexSplit::runOnLoop(Loop *IncomingLoop, LPPassManager &LPM_Ref) { 00212 L = IncomingLoop; 00213 LPM = &LPM_Ref; 00214 00215 // FIXME - Nested loops make dominator info updates tricky. 00216 if (!L->getSubLoops().empty()) 00217 return false; 00218 00219 DT = &getAnalysis<DominatorTree>(); 00220 LI = &getAnalysis<LoopInfo>(); 00221 DF = &getAnalysis<DominanceFrontier>(); 00222 00223 // Initialize loop data. 00224 IndVar = L->getCanonicalInductionVariable(); 00225 if (!IndVar) return false; 00226 00227 bool P1InLoop = L->contains(IndVar->getIncomingBlock(1)); 00228 IVStartValue = IndVar->getIncomingValue(!P1InLoop); 00229 IVIncrement = dyn_cast<Instruction>(IndVar->getIncomingValue(P1InLoop)); 00230 if (!IVIncrement) return false; 00231 00232 IVBasedValues.clear(); 00233 IVBasedValues.insert(IndVar); 00234 IVBasedValues.insert(IVIncrement); 00235 for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); 00236 I != E; ++I) 00237 for(BasicBlock::iterator BI = (*I)->begin(), BE = (*I)->end(); 00238 BI != BE; ++BI) { 00239 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(BI)) 00240 if (BO != IVIncrement 00241 && (BO->getOpcode() == Instruction::Add 00242 || BO->getOpcode() == Instruction::Sub)) 00243 if (IVBasedValues.count(BO->getOperand(0)) 00244 && L->isLoopInvariant(BO->getOperand(1))) 00245 IVBasedValues.insert(BO); 00246 } 00247 00248 // Reject loop if loop exit condition is not suitable. 00249 BasicBlock *ExitingBlock = L->getExitingBlock(); 00250 if (!ExitingBlock) 00251 return false; 00252 BranchInst *EBR = dyn_cast<BranchInst>(ExitingBlock->getTerminator()); 00253 if (!EBR) return false; 00254 ExitCondition = dyn_cast<ICmpInst>(EBR->getCondition()); 00255 if (!ExitCondition) return false; 00256 if (ExitingBlock != L->getLoopLatch()) return false; 00257 IVExitValue = ExitCondition->getOperand(1); 00258 if (!L->isLoopInvariant(IVExitValue)) 00259 IVExitValue = ExitCondition->getOperand(0); 00260 if (!L->isLoopInvariant(IVExitValue)) 00261 return false; 00262 if (!IVBasedValues.count( 00263 ExitCondition->getOperand(IVExitValue == ExitCondition->getOperand(0)))) 00264 return false; 00265 00266 // If start value is more then exit value where induction variable 00267 // increments by 1 then we are potentially dealing with an infinite loop. 00268 // Do not index split this loop. 00269 if (ConstantInt *SV = dyn_cast<ConstantInt>(IVStartValue)) 00270 if (ConstantInt *EV = dyn_cast<ConstantInt>(IVExitValue)) 00271 if (SV->getSExtValue() > EV->getSExtValue()) 00272 return false; 00273 00274 if (processOneIterationLoop()) 00275 return true; 00276 00277 if (updateLoopIterationSpace()) 00278 return true; 00279 00280 if (splitLoop()) 00281 return true; 00282 00283 return false; 00284 } 00285 00286 // --- Helper routines --- 00287 // isUsedOutsideLoop - Returns true iff V is used outside the loop L. 00288 static bool isUsedOutsideLoop(Value *V, Loop *L) { 00289 for(Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ++UI) 00290 if (!L->contains(cast<Instruction>(*UI)->getParent())) 00291 return true; 00292 return false; 00293 } 00294 00295 // Return V+1 00296 static Value *getPlusOne(Value *V, bool Sign, Instruction *InsertPt, 00297 LLVMContext &Context) { 00298 Constant *One = ConstantInt::get(V->getType(), 1, Sign); 00299 return BinaryOperator::CreateAdd(V, One, "lsp", InsertPt); 00300 } 00301 00302 // Return V-1 00303 static Value *getMinusOne(Value *V, bool Sign, Instruction *InsertPt, 00304 LLVMContext &Context) { 00305 Constant *One = ConstantInt::get(V->getType(), 1, Sign); 00306 return BinaryOperator::CreateSub(V, One, "lsp", InsertPt); 00307 } 00308 00309 // Return min(V1, V1) 00310 static Value *getMin(Value *V1, Value *V2, bool Sign, Instruction *InsertPt) { 00311 00312 Value *C = new ICmpInst(InsertPt, 00313 Sign ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT, 00314 V1, V2, "lsp"); 00315 return SelectInst::Create(C, V1, V2, "lsp", InsertPt); 00316 } 00317 00318 // Return max(V1, V2) 00319 static Value *getMax(Value *V1, Value *V2, bool Sign, Instruction *InsertPt) { 00320 00321 Value *C = new ICmpInst(InsertPt, 00322 Sign ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT, 00323 V1, V2, "lsp"); 00324 return SelectInst::Create(C, V2, V1, "lsp", InsertPt); 00325 } 00326 00327 /// processOneIterationLoop -- Eliminate loop if loop body is executed 00328 /// only once. For example, 00329 /// for (i = 0; i < N; ++i) { 00330 /// if ( i == X) { 00331 /// ... 00332 /// } 00333 /// } 00334 /// 00335 bool LoopIndexSplit::processOneIterationLoop() { 00336 SplitCondition = NULL; 00337 BasicBlock *Latch = L->getLoopLatch(); 00338 BasicBlock *Header = L->getHeader(); 00339 BranchInst *BR = dyn_cast<BranchInst>(Header->getTerminator()); 00340 if (!BR) return false; 00341 if (!isa<BranchInst>(Latch->getTerminator())) return false; 00342 if (BR->isUnconditional()) return false; 00343 SplitCondition = dyn_cast<ICmpInst>(BR->getCondition()); 00344 if (!SplitCondition) return false; 00345 if (SplitCondition == ExitCondition) return false; 00346 if (SplitCondition->getPredicate() != ICmpInst::ICMP_EQ) return false; 00347 if (BR->getOperand(1) != Latch) return false; 00348 if (!IVBasedValues.count(SplitCondition->getOperand(0)) 00349 && !IVBasedValues.count(SplitCondition->getOperand(1))) 00350 return false; 00351 00352 // If IV is used outside the loop then this loop traversal is required. 00353 // FIXME: Calculate and use last IV value. 00354 if (isUsedOutsideLoop(IVIncrement, L)) 00355 return false; 00356 00357 // If BR operands are not IV or not loop invariants then skip this loop. 00358 Value *OPV = SplitCondition->getOperand(0); 00359 Value *SplitValue = SplitCondition->getOperand(1); 00360 if (!L->isLoopInvariant(SplitValue)) 00361 std::swap(OPV, SplitValue); 00362 if (!L->isLoopInvariant(SplitValue)) 00363 return false; 00364 Instruction *OPI = dyn_cast<Instruction>(OPV); 00365 if (!OPI) 00366 return false; 00367 if (OPI->getParent() != Header || isUsedOutsideLoop(OPI, L)) 00368 return false; 00369 Value *StartValue = IVStartValue; 00370 Value *ExitValue = IVExitValue;; 00371 00372 if (OPV != IndVar) { 00373 // If BR operand is IV based then use this operand to calculate 00374 // effective conditions for loop body. 00375 BinaryOperator *BOPV = dyn_cast<BinaryOperator>(OPV); 00376 if (!BOPV) 00377 return false; 00378 if (BOPV->getOpcode() != Instruction::Add) 00379 return false; 00380 StartValue = BinaryOperator::CreateAdd(OPV, StartValue, "" , BR); 00381 ExitValue = BinaryOperator::CreateAdd(OPV, ExitValue, "" , BR); 00382 } 00383 00384 if (!cleanBlock(Header)) 00385 return false; 00386 00387 if (!cleanBlock(Latch)) 00388 return false; 00389 00390 // If the merge point for BR is not loop latch then skip this loop. 00391 if (BR->getSuccessor(0) != Latch) { 00392 DominanceFrontier::iterator DF0 = DF->find(BR->getSuccessor(0)); 00393 assert (DF0 != DF->end() && "Unable to find dominance frontier"); 00394 if (!DF0->second.count(Latch)) 00395 return false; 00396 } 00397 00398 if (BR->getSuccessor(1) != Latch) { 00399 DominanceFrontier::iterator DF1 = DF->find(BR->getSuccessor(1)); 00400 assert (DF1 != DF->end() && "Unable to find dominance frontier"); 00401 if (!DF1->second.count(Latch)) 00402 return false; 00403 } 00404 00405 // Now, Current loop L contains compare instruction 00406 // that compares induction variable, IndVar, against loop invariant. And 00407 // entire (i.e. meaningful) loop body is dominated by this compare 00408 // instruction. In such case eliminate 00409 // loop structure surrounding this loop body. For example, 00410 // for (int i = start; i < end; ++i) { 00411 // if ( i == somevalue) { 00412 // loop_body 00413 // } 00414 // } 00415 // can be transformed into 00416 // if (somevalue >= start && somevalue < end) { 00417 // i = somevalue; 00418 // loop_body 00419 // } 00420 00421 // Replace index variable with split value in loop body. Loop body is executed 00422 // only when index variable is equal to split value. 00423 IndVar->replaceAllUsesWith(SplitValue); 00424 00425 // Replace split condition in header. 00426 // Transform 00427 // SplitCondition : icmp eq i32 IndVar, SplitValue 00428 // into 00429 // c1 = icmp uge i32 SplitValue, StartValue 00430 // c2 = icmp ult i32 SplitValue, ExitValue 00431 // and i32 c1, c2 00432 Instruction *C1 = new ICmpInst(BR, ExitCondition->isSignedPredicate() ? 00433 ICmpInst::ICMP_SGE : ICmpInst::ICMP_UGE, 00434 SplitValue, StartValue, "lisplit"); 00435 00436 CmpInst::Predicate C2P = ExitCondition->getPredicate(); 00437 BranchInst *LatchBR = cast<BranchInst>(Latch->getTerminator()); 00438 if (LatchBR->getOperand(0) != Header) 00439 C2P = CmpInst::getInversePredicate(C2P); 00440 Instruction *C2 = new ICmpInst(BR, C2P, SplitValue, ExitValue, "lisplit"); 00441 Instruction *NSplitCond = BinaryOperator::CreateAnd(C1, C2, "lisplit", BR); 00442 00443 SplitCondition->replaceAllUsesWith(NSplitCond); 00444 SplitCondition->eraseFromParent(); 00445 00446 // Remove Latch to Header edge. 00447 BasicBlock *LatchSucc = NULL; 00448 Header->removePredecessor(Latch); 00449 for (succ_iterator SI = succ_begin(Latch), E = succ_end(Latch); 00450 SI != E; ++SI) { 00451 if (Header != *SI) 00452 LatchSucc = *SI; 00453 } 00454 00455 // Clean up latch block. 00456 Value *LatchBRCond = LatchBR->getCondition(); 00457 LatchBR->setUnconditionalDest(LatchSucc); 00458 RecursivelyDeleteTriviallyDeadInstructions(LatchBRCond); 00459 00460 LPM->deleteLoopFromQueue(L); 00461 00462 // Update Dominator Info. 00463 // Only CFG change done is to remove Latch to Header edge. This 00464 // does not change dominator tree because Latch did not dominate 00465 // Header. 00466 if (DF) { 00467 DominanceFrontier::iterator HeaderDF = DF->find(Header); 00468 if (HeaderDF != DF->end()) 00469 DF->removeFromFrontier(HeaderDF, Header); 00470 00471 DominanceFrontier::iterator LatchDF = DF->find(Latch); 00472 if (LatchDF != DF->end()) 00473 DF->removeFromFrontier(LatchDF, Header); 00474 } 00475 00476 ++NumIndexSplitRemoved; 00477 return true; 00478 } 00479 00480 /// restrictLoopBound - Op dominates loop body. Op compares an IV based value 00481 /// with a loop invariant value. Update loop's lower and upper bound based on 00482 /// the loop invariant value. 00483 bool LoopIndexSplit::restrictLoopBound(ICmpInst &Op) { 00484 bool Sign = Op.isSignedPredicate(); 00485 Instruction *PHTerm = L->getLoopPreheader()->getTerminator(); 00486 00487 if (IVisGT(*ExitCondition) || IVisGE(*ExitCondition)) { 00488 BranchInst *EBR = 00489 cast<BranchInst>(ExitCondition->getParent()->getTerminator()); 00490 ExitCondition->setPredicate(ExitCondition->getInversePredicate()); 00491 BasicBlock *T = EBR->getSuccessor(0); 00492 EBR->setSuccessor(0, EBR->getSuccessor(1)); 00493 EBR->setSuccessor(1, T); 00494 } 00495 00496 LLVMContext &Context = Op.getContext(); 00497 00498 // New upper and lower bounds. 00499 Value *NLB = NULL; 00500 Value *NUB = NULL; 00501 if (Value *V = IVisLT(Op)) { 00502 // Restrict upper bound. 00503 if (IVisLE(*ExitCondition)) 00504 V = getMinusOne(V, Sign, PHTerm, Context); 00505 NUB = getMin(V, IVExitValue, Sign, PHTerm); 00506 } else if (Value *V = IVisLE(Op)) { 00507 // Restrict upper bound. 00508 if (IVisLT(*ExitCondition)) 00509 V = getPlusOne(V, Sign, PHTerm, Context); 00510 NUB = getMin(V, IVExitValue, Sign, PHTerm); 00511 } else if (Value *V = IVisGT(Op)) { 00512 // Restrict lower bound. 00513 V = getPlusOne(V, Sign, PHTerm, Context); 00514 NLB = getMax(V, IVStartValue, Sign, PHTerm); 00515 } else if (Value *V = IVisGE(Op)) 00516 // Restrict lower bound. 00517 NLB = getMax(V, IVStartValue, Sign, PHTerm); 00518 00519 if (!NLB && !NUB) 00520 return false; 00521 00522 if (NLB) { 00523 unsigned i = IndVar->getBasicBlockIndex(L->getLoopPreheader()); 00524 IndVar->setIncomingValue(i, NLB); 00525 } 00526 00527 if (NUB) { 00528 unsigned i = (ExitCondition->getOperand(0) != IVExitValue); 00529 ExitCondition->setOperand(i, NUB); 00530 } 00531 return true; 00532 } 00533 00534 /// updateLoopIterationSpace -- Update loop's iteration space if loop 00535 /// body is executed for certain IV range only. For example, 00536 /// 00537 /// for (i = 0; i < N; ++i) { 00538 /// if ( i > A && i < B) { 00539 /// ... 00540 /// } 00541 /// } 00542 /// is transformed to iterators from A to B, if A > 0 and B < N. 00543 /// 00544 bool LoopIndexSplit::updateLoopIterationSpace() { 00545 SplitCondition = NULL; 00546 if (ExitCondition->getPredicate() == ICmpInst::ICMP_NE 00547 || ExitCondition->getPredicate() == ICmpInst::ICMP_EQ) 00548 return false; 00549 BasicBlock *Latch = L->getLoopLatch(); 00550 BasicBlock *Header = L->getHeader(); 00551 BranchInst *BR = dyn_cast<BranchInst>(Header->getTerminator()); 00552 if (!BR) return false; 00553 if (!isa<BranchInst>(Latch->getTerminator())) return false; 00554 if (BR->isUnconditional()) return false; 00555 BinaryOperator *AND = dyn_cast<BinaryOperator>(BR->getCondition()); 00556 if (!AND) return false; 00557 if (AND->getOpcode() != Instruction::And) return false; 00558 ICmpInst *Op0 = dyn_cast<ICmpInst>(AND->getOperand(0)); 00559 ICmpInst *Op1 = dyn_cast<ICmpInst>(AND->getOperand(1)); 00560 if (!Op0 || !Op1) 00561 return false; 00562 IVBasedValues.insert(AND); 00563 IVBasedValues.insert(Op0); 00564 IVBasedValues.insert(Op1); 00565 if (!cleanBlock(Header)) return false; 00566 BasicBlock *ExitingBlock = ExitCondition->getParent(); 00567 if (!cleanBlock(ExitingBlock)) return false; 00568 00569 // If the merge point for BR is not loop latch then skip this loop. 00570 if (BR->getSuccessor(0) != Latch) { 00571 DominanceFrontier::iterator DF0 = DF->find(BR->getSuccessor(0)); 00572 assert (DF0 != DF->end() && "Unable to find dominance frontier"); 00573 if (!DF0->second.count(Latch)) 00574 return false; 00575 } 00576 00577 if (BR->getSuccessor(1) != Latch) { 00578 DominanceFrontier::iterator DF1 = DF->find(BR->getSuccessor(1)); 00579 assert (DF1 != DF->end() && "Unable to find dominance frontier"); 00580 if (!DF1->second.count(Latch)) 00581 return false; 00582 } 00583 00584 // Verify that loop exiting block has only two predecessor, where one pred 00585 // is split condition block. The other predecessor will become exiting block's 00586 // dominator after CFG is updated. TODO : Handle CFG's where exiting block has 00587 // more then two predecessors. This requires extra work in updating dominator 00588 // information. 00589 BasicBlock *ExitingBBPred = NULL; 00590 for (pred_iterator PI = pred_begin(ExitingBlock), PE = pred_end(ExitingBlock); 00591 PI != PE; ++PI) { 00592 BasicBlock *BB = *PI; 00593 if (Header == BB) 00594 continue; 00595 if (ExitingBBPred) 00596 return false; 00597 else 00598 ExitingBBPred = BB; 00599 } 00600 00601 if (!restrictLoopBound(*Op0)) 00602 return false; 00603 00604 if (!restrictLoopBound(*Op1)) 00605 return false; 00606 00607 // Update CFG. 00608 if (BR->getSuccessor(0) == ExitingBlock) 00609 BR->setUnconditionalDest(BR->getSuccessor(1)); 00610 else 00611 BR->setUnconditionalDest(BR->getSuccessor(0)); 00612 00613 AND->eraseFromParent(); 00614 if (Op0->use_empty()) 00615 Op0->eraseFromParent(); 00616 if (Op1->use_empty()) 00617 Op1->eraseFromParent(); 00618 00619 // Update domiantor info. Now, ExitingBlock has only one predecessor, 00620 // ExitingBBPred, and it is ExitingBlock's immediate domiantor. 00621 DT->changeImmediateDominator(ExitingBlock, ExitingBBPred); 00622 00623 BasicBlock *ExitBlock = ExitingBlock->getTerminator()->getSuccessor(1); 00624 if (L->contains(ExitBlock)) 00625 ExitBlock = ExitingBlock->getTerminator()->getSuccessor(0); 00626 00627 // If ExitingBlock is a member of the loop basic blocks' DF list then 00628 // replace ExitingBlock with header and exit block in the DF list 00629 DominanceFrontier::iterator ExitingBlockDF = DF->find(ExitingBlock); 00630 for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); 00631 I != E; ++I) { 00632 BasicBlock *BB = *I; 00633 if (BB == Header || BB == ExitingBlock) 00634 continue; 00635 DominanceFrontier::iterator BBDF = DF->find(BB); 00636 DominanceFrontier::DomSetType::iterator DomSetI = BBDF->second.begin(); 00637 DominanceFrontier::DomSetType::iterator DomSetE = BBDF->second.end(); 00638 while (DomSetI != DomSetE) { 00639 DominanceFrontier::DomSetType::iterator CurrentItr = DomSetI; 00640 ++DomSetI; 00641 BasicBlock *DFBB = *CurrentItr; 00642 if (DFBB == ExitingBlock) { 00643 BBDF->second.erase(DFBB); 00644 for (DominanceFrontier::DomSetType::iterator 00645 EBI = ExitingBlockDF->second.begin(), 00646 EBE = ExitingBlockDF->second.end(); EBI != EBE; ++EBI) 00647 BBDF->second.insert(*EBI); 00648 } 00649 } 00650 } 00651 NumRestrictBounds++; 00652 return true; 00653 } 00654 00655 /// removeBlocks - Remove basic block DeadBB and all blocks dominated by DeadBB. 00656 /// This routine is used to remove split condition's dead branch, dominated by 00657 /// DeadBB. LiveBB dominates split conidition's other branch. 00658 void LoopIndexSplit::removeBlocks(BasicBlock *DeadBB, Loop *LP, 00659 BasicBlock *LiveBB) { 00660 00661 // First update DeadBB's dominance frontier. 00662 SmallVector<BasicBlock *, 8> FrontierBBs; 00663 DominanceFrontier::iterator DeadBBDF = DF->find(DeadBB); 00664 if (DeadBBDF != DF->end()) { 00665 SmallVector<BasicBlock *, 8> PredBlocks; 00666 00667 DominanceFrontier::DomSetType DeadBBSet = DeadBBDF->second; 00668 for (DominanceFrontier::DomSetType::iterator DeadBBSetI = DeadBBSet.begin(), 00669 DeadBBSetE = DeadBBSet.end(); DeadBBSetI != DeadBBSetE; ++DeadBBSetI) 00670 { 00671 BasicBlock *FrontierBB = *DeadBBSetI; 00672 FrontierBBs.push_back(FrontierBB); 00673 00674 // Rremove any PHI incoming edge from blocks dominated by DeadBB. 00675 PredBlocks.clear(); 00676 for(pred_iterator PI = pred_begin(FrontierBB), PE = pred_end(FrontierBB); 00677 PI != PE; ++PI) { 00678 BasicBlock *P = *PI; 00679 if (P == DeadBB || DT->dominates(DeadBB, P)) 00680 PredBlocks.push_back(P); 00681 } 00682 00683 for(BasicBlock::iterator FBI = FrontierBB->begin(), FBE = FrontierBB->end(); 00684 FBI != FBE; ++FBI) { 00685 if (PHINode *PN = dyn_cast<PHINode>(FBI)) { 00686 for(SmallVector<BasicBlock *, 8>::iterator PI = PredBlocks.begin(), 00687 PE = PredBlocks.end(); PI != PE; ++PI) { 00688 BasicBlock *P = *PI; 00689 PN->removeIncomingValue(P); 00690 } 00691 } 00692 else 00693 break; 00694 } 00695 } 00696 } 00697 00698 // Now remove DeadBB and all nodes dominated by DeadBB in df order. 00699 SmallVector<BasicBlock *, 32> WorkList; 00700 DomTreeNode *DN = DT->getNode(DeadBB); 00701 for (df_iterator<DomTreeNode*> DI = df_begin(DN), 00702 E = df_end(DN); DI != E; ++DI) { 00703 BasicBlock *BB = DI->getBlock(); 00704 WorkList.push_back(BB); 00705 BB->replaceAllUsesWith(UndefValue::get( 00706 Type::getLabelTy(DeadBB->getContext()))); 00707 } 00708 00709 while (!WorkList.empty()) { 00710 BasicBlock *BB = WorkList.back(); WorkList.pop_back(); 00711 LPM->deleteSimpleAnalysisValue(BB, LP); 00712 for(BasicBlock::iterator BBI = BB->begin(), BBE = BB->end(); 00713 BBI != BBE; ) { 00714 Instruction *I = BBI; 00715 ++BBI; 00716 I->replaceAllUsesWith(UndefValue::get(I->getType())); 00717 LPM->deleteSimpleAnalysisValue(I, LP); 00718 I->eraseFromParent(); 00719 } 00720 DT->eraseNode(BB); 00721 DF->removeBlock(BB); 00722 LI->removeBlock(BB); 00723 BB->eraseFromParent(); 00724 } 00725 00726 // Update Frontier BBs' dominator info. 00727 while (!FrontierBBs.empty()) { 00728 BasicBlock *FBB = FrontierBBs.back(); FrontierBBs.pop_back(); 00729 BasicBlock *NewDominator = FBB->getSinglePredecessor(); 00730 if (!NewDominator) { 00731 pred_iterator PI = pred_begin(FBB), PE = pred_end(FBB); 00732 NewDominator = *PI; 00733 ++PI; 00734 if (NewDominator != LiveBB) { 00735 for(; PI != PE; ++PI) { 00736 BasicBlock *P = *PI; 00737 if (P == LiveBB) { 00738 NewDominator = LiveBB; 00739 break; 00740 } 00741 NewDominator = DT->findNearestCommonDominator(NewDominator, P); 00742 } 00743 } 00744 } 00745 assert (NewDominator && "Unable to fix dominator info."); 00746 DT->changeImmediateDominator(FBB, NewDominator); 00747 DF->changeImmediateDominator(FBB, NewDominator, DT); 00748 } 00749 00750 } 00751 00752 // moveExitCondition - Move exit condition EC into split condition block CondBB. 00753 void LoopIndexSplit::moveExitCondition(BasicBlock *CondBB, BasicBlock *ActiveBB, 00754 BasicBlock *ExitBB, ICmpInst *EC, 00755 ICmpInst *SC, PHINode *IV, 00756 Instruction *IVAdd, Loop *LP, 00757 unsigned ExitValueNum) { 00758 00759 BasicBlock *ExitingBB = EC->getParent(); 00760 Instruction *CurrentBR = CondBB->getTerminator(); 00761 00762 // Move exit condition into split condition block. 00763 EC->moveBefore(CurrentBR); 00764 EC->setOperand(ExitValueNum == 0 ? 1 : 0, IV); 00765 00766 // Move exiting block's branch into split condition block. Update its branch 00767 // destination. 00768 BranchInst *ExitingBR = cast<BranchInst>(ExitingBB->getTerminator()); 00769 ExitingBR->moveBefore(CurrentBR); 00770 BasicBlock *OrigDestBB = NULL; 00771 if (ExitingBR->getSuccessor(0) == ExitBB) { 00772 OrigDestBB = ExitingBR->getSuccessor(1); 00773 ExitingBR->setSuccessor(1, ActiveBB); 00774 } 00775 else { 00776 OrigDestBB = ExitingBR->getSuccessor(0); 00777 ExitingBR->setSuccessor(0, ActiveBB); 00778 } 00779 00780 // Remove split condition and current split condition branch. 00781 SC->eraseFromParent(); 00782 CurrentBR->eraseFromParent(); 00783 00784 // Connect exiting block to original destination. 00785 BranchInst::Create(OrigDestBB, ExitingBB); 00786 00787 // Update PHINodes 00788 updatePHINodes(ExitBB, ExitingBB, CondBB, IV, IVAdd, LP); 00789 00790 // Fix dominator info. 00791 // ExitBB is now dominated by CondBB 00792 DT->changeImmediateDominator(ExitBB, CondBB); 00793 DF->changeImmediateDominator(ExitBB, CondBB, DT); 00794 00795 // Blocks outside the loop may have been in the dominance frontier of blocks 00796 // inside the condition; this is now impossible because the blocks inside the 00797 // condition no loger dominate the exit. Remove the relevant blocks from 00798 // the dominance frontiers. 00799 for (Loop::block_iterator I = LP->block_begin(), E = LP->block_end(); 00800 I != E; ++I) { 00801 if (*I == CondBB || !DT->dominates(CondBB, *I)) continue; 00802 DominanceFrontier::iterator BBDF = DF->find(*I); 00803 DominanceFrontier::DomSetType::iterator DomSetI = BBDF->second.begin(); 00804 DominanceFrontier::DomSetType::iterator DomSetE = BBDF->second.end(); 00805 while (DomSetI != DomSetE) { 00806 DominanceFrontier::DomSetType::iterator CurrentItr = DomSetI; 00807 ++DomSetI; 00808 BasicBlock *DFBB = *CurrentItr; 00809 if (!LP->contains(DFBB)) 00810 BBDF->second.erase(DFBB); 00811 } 00812 } 00813 } 00814 00815 /// updatePHINodes - CFG has been changed. 00816 /// Before 00817 /// - ExitBB's single predecessor was Latch 00818 /// - Latch's second successor was Header 00819 /// Now 00820 /// - ExitBB's single predecessor is Header 00821 /// - Latch's one and only successor is Header 00822 /// 00823 /// Update ExitBB PHINodes' to reflect this change. 00824 void LoopIndexSplit::updatePHINodes(BasicBlock *ExitBB, BasicBlock *Latch, 00825 BasicBlock *Header, 00826 PHINode *IV, Instruction *IVIncrement, 00827 Loop *LP) { 00828 00829 for (BasicBlock::iterator BI = ExitBB->begin(), BE = ExitBB->end(); 00830 BI != BE; ) { 00831 PHINode *PN = dyn_cast<PHINode>(BI); 00832 ++BI; 00833 if (!PN) 00834 break; 00835 00836 Value *V = PN->getIncomingValueForBlock(Latch); 00837 if (PHINode *PHV = dyn_cast<PHINode>(V)) { 00838 // PHV is in Latch. PHV has one use is in ExitBB PHINode. And one use 00839 // in Header which is new incoming value for PN. 00840 Value *NewV = NULL; 00841 for (Value::use_iterator UI = PHV->use_begin(), E = PHV->use_end(); 00842 UI != E; ++UI) 00843 if (PHINode *U = dyn_cast<PHINode>(*UI)) 00844 if (LP->contains(U->getParent())) { 00845 NewV = U; 00846 break; 00847 } 00848 00849 // Add incoming value from header only if PN has any use inside the loop. 00850 if (NewV) 00851 PN->addIncoming(NewV, Header); 00852 00853 } else if (Instruction *PHI = dyn_cast<Instruction>(V)) { 00854 // If this instruction is IVIncrement then IV is new incoming value 00855 // from header otherwise this instruction must be incoming value from 00856 // header because loop is in LCSSA form. 00857 if (PHI == IVIncrement) 00858 PN->addIncoming(IV, Header); 00859 else 00860 PN->addIncoming(V, Header); 00861 } else 00862 // Otherwise this is an incoming value from header because loop is in 00863 // LCSSA form. 00864 PN->addIncoming(V, Header); 00865 00866 // Remove incoming value from Latch. 00867 PN->removeIncomingValue(Latch); 00868 } 00869 } 00870 00871 bool LoopIndexSplit::splitLoop() { 00872 SplitCondition = NULL; 00873 if (ExitCondition->getPredicate() == ICmpInst::ICMP_NE 00874 || ExitCondition->getPredicate() == ICmpInst::ICMP_EQ) 00875 return false; 00876 BasicBlock *Header = L->getHeader(); 00877 BasicBlock *Latch = L->getLoopLatch(); 00878 BranchInst *SBR = NULL; // Split Condition Branch 00879 BranchInst *EBR = cast<BranchInst>(ExitCondition->getParent()->getTerminator()); 00880 // If Exiting block includes loop variant instructions then this 00881 // loop may not be split safely. 00882 BasicBlock *ExitingBlock = ExitCondition->getParent(); 00883 if (!cleanBlock(ExitingBlock)) return false; 00884 00885 LLVMContext &Context = Header->getContext(); 00886 00887 for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); 00888 I != E; ++I) { 00889 BranchInst *BR = dyn_cast<BranchInst>((*I)->getTerminator()); 00890 if (!BR || BR->isUnconditional()) continue; 00891 ICmpInst *CI = dyn_cast<ICmpInst>(BR->getCondition()); 00892 if (!CI || CI == ExitCondition 00893 || CI->getPredicate() == ICmpInst::ICMP_NE 00894 || CI->getPredicate() == ICmpInst::ICMP_EQ) 00895 continue; 00896 00897 // Unable to handle triangle loops at the moment. 00898 // In triangle loop, split condition is in header and one of the 00899 // the split destination is loop latch. If split condition is EQ 00900 // then such loops are already handle in processOneIterationLoop(). 00901 if (Header == (*I) 00902 && (Latch == BR->getSuccessor(0) || Latch == BR->getSuccessor(1))) 00903 continue; 00904 00905 // If the block does not dominate the latch then this is not a diamond. 00906 // Such loop may not benefit from index split. 00907 if (!DT->dominates((*I), Latch)) 00908 continue; 00909 00910 // If split condition branches heads do not have single predecessor, 00911 // SplitCondBlock, then is not possible to remove inactive branch. 00912 if (!BR->getSuccessor(0)->getSinglePredecessor() 00913 || !BR->getSuccessor(1)->getSinglePredecessor()) 00914 return false; 00915 00916 // If the merge point for BR is not loop latch then skip this condition. 00917 if (BR->getSuccessor(0) != Latch) { 00918 DominanceFrontier::iterator DF0 = DF->find(BR->getSuccessor(0)); 00919 assert (DF0 != DF->end() && "Unable to find dominance frontier"); 00920 if (!DF0->second.count(Latch)) 00921 continue; 00922 } 00923 00924 if (BR->getSuccessor(1) != Latch) { 00925 DominanceFrontier::iterator DF1 = DF->find(BR->getSuccessor(1)); 00926 assert (DF1 != DF->end() && "Unable to find dominance frontier"); 00927 if (!DF1->second.count(Latch)) 00928 continue; 00929 } 00930 SplitCondition = CI; 00931 SBR = BR; 00932 break; 00933 } 00934 00935 if (!SplitCondition) 00936 return false; 00937 00938 // If the predicate sign does not match then skip. 00939 if (ExitCondition->isSignedPredicate() != SplitCondition->isSignedPredicate()) 00940 return false; 00941 00942 unsigned EVOpNum = (ExitCondition->getOperand(1) == IVExitValue); 00943 unsigned SVOpNum = IVBasedValues.count(SplitCondition->getOperand(0)); 00944 Value *SplitValue = SplitCondition->getOperand(SVOpNum); 00945 if (!L->isLoopInvariant(SplitValue)) 00946 return false; 00947 if (!IVBasedValues.count(SplitCondition->getOperand(!SVOpNum))) 00948 return false; 00949 00950 // Normalize loop conditions so that it is easier to calculate new loop 00951 // bounds. 00952 if (IVisGT(*ExitCondition) || IVisGE(*ExitCondition)) { 00953 ExitCondition->setPredicate(ExitCondition->getInversePredicate()); 00954 BasicBlock *T = EBR->getSuccessor(0); 00955 EBR->setSuccessor(0, EBR->getSuccessor(1)); 00956 EBR->setSuccessor(1, T); 00957 } 00958 00959 if (IVisGT(*SplitCondition) || IVisGE(*SplitCondition)) { 00960 SplitCondition->setPredicate(SplitCondition->getInversePredicate()); 00961 BasicBlock *T = SBR->getSuccessor(0); 00962 SBR->setSuccessor(0, SBR->getSuccessor(1)); 00963 SBR->setSuccessor(1, T); 00964 } 00965 00966 //[*] Calculate new loop bounds. 00967 Value *AEV = SplitValue; 00968 Value *BSV = SplitValue; 00969 bool Sign = SplitCondition->isSignedPredicate(); 00970 Instruction *PHTerm = L->getLoopPreheader()->getTerminator(); 00971 00972 if (IVisLT(*ExitCondition)) { 00973 if (IVisLT(*SplitCondition)) { 00974 /* Do nothing */ 00975 } 00976 else if (IVisLE(*SplitCondition)) { 00977 AEV = getPlusOne(SplitValue, Sign, PHTerm, Context); 00978 BSV = getPlusOne(SplitValue, Sign, PHTerm, Context); 00979 } else { 00980 assert (0 && "Unexpected split condition!"); 00981 } 00982 } 00983 else if (IVisLE(*ExitCondition)) { 00984 if (IVisLT(*SplitCondition)) { 00985 AEV = getMinusOne(SplitValue, Sign, PHTerm, Context); 00986 } 00987 else if (IVisLE(*SplitCondition)) { 00988 BSV = getPlusOne(SplitValue, Sign, PHTerm, Context); 00989 } else { 00990 assert (0 && "Unexpected split condition!"); 00991 } 00992 } else { 00993 assert (0 && "Unexpected exit condition!"); 00994 } 00995 AEV = getMin(AEV, IVExitValue, Sign, PHTerm); 00996 BSV = getMax(BSV, IVStartValue, Sign, PHTerm); 00997 00998 // [*] Clone Loop 00999 DenseMap<const Value *, Value *> ValueMap; 01000 Loop *BLoop = CloneLoop(L, LPM, LI, ValueMap, this); 01001 Loop *ALoop = L; 01002 01003 // [*] ALoop's exiting edge enters BLoop's header. 01004 // ALoop's original exit block becomes BLoop's exit block. 01005 PHINode *B_IndVar = cast<PHINode>(ValueMap[IndVar]); 01006 BasicBlock *A_ExitingBlock = ExitCondition->getParent(); 01007 BranchInst *A_ExitInsn = 01008 dyn_cast<BranchInst>(A_ExitingBlock->getTerminator()); 01009 assert (A_ExitInsn && "Unable to find suitable loop exit branch"); 01010 BasicBlock *B_ExitBlock = A_ExitInsn->getSuccessor(1); 01011 BasicBlock *B_Header = BLoop->getHeader(); 01012 if (ALoop->contains(B_ExitBlock)) { 01013 B_ExitBlock = A_ExitInsn->getSuccessor(0); 01014 A_ExitInsn->setSuccessor(0, B_Header); 01015 } else 01016 A_ExitInsn->setSuccessor(1, B_Header); 01017 01018 // [*] Update ALoop's exit value using new exit value. 01019 ExitCondition->setOperand(EVOpNum, AEV); 01020 01021 // [*] Update BLoop's header phi nodes. Remove incoming PHINode's from 01022 // original loop's preheader. Add incoming PHINode values from 01023 // ALoop's exiting block. Update BLoop header's domiantor info. 01024 01025 // Collect inverse map of Header PHINodes. 01026 DenseMap<Value *, Value *> InverseMap; 01027 for (BasicBlock::iterator BI = ALoop->getHeader()->begin(), 01028 BE = ALoop->getHeader()->end(); BI != BE; ++BI) { 01029 if (PHINode *PN = dyn_cast<PHINode>(BI)) { 01030 PHINode *PNClone = cast<PHINode>(ValueMap[PN]); 01031 InverseMap[PNClone] = PN; 01032 } else 01033 break; 01034 } 01035 01036 BasicBlock *A_Preheader = ALoop->getLoopPreheader(); 01037 for (BasicBlock::iterator BI = B_Header->begin(), BE = B_Header->end(); 01038 BI != BE; ++BI) { 01039 if (PHINode *PN = dyn_cast<PHINode>(BI)) { 01040 // Remove incoming value from original preheader. 01041 PN->removeIncomingValue(A_Preheader); 01042 01043 // Add incoming value from A_ExitingBlock. 01044 if (PN == B_IndVar) 01045 PN->addIncoming(BSV, A_ExitingBlock); 01046 else { 01047 PHINode *OrigPN = cast<PHINode>(InverseMap[PN]); 01048 Value *V2 = NULL; 01049 // If loop header is also loop exiting block then 01050 // OrigPN is incoming value for B loop header. 01051 if (A_ExitingBlock == ALoop->getHeader()) 01052 V2 = OrigPN; 01053 else 01054 V2 = OrigPN->getIncomingValueForBlock(A_ExitingBlock); 01055 PN->addIncoming(V2, A_ExitingBlock); 01056 } 01057 } else 01058 break; 01059 } 01060 01061 DT->changeImmediateDominator(B_Header, A_ExitingBlock); 01062 DF->changeImmediateDominator(B_Header, A_ExitingBlock, DT); 01063 01064 // [*] Update BLoop's exit block. Its new predecessor is BLoop's exit 01065 // block. Remove incoming PHINode values from ALoop's exiting block. 01066 // Add new incoming values from BLoop's incoming exiting value. 01067 // Update BLoop exit block's dominator info.. 01068 BasicBlock *B_ExitingBlock = cast<BasicBlock>(ValueMap[A_ExitingBlock]); 01069 for (BasicBlock::iterator BI = B_ExitBlock->begin(), BE = B_ExitBlock->end(); 01070 BI != BE; ++BI) { 01071 if (PHINode *PN = dyn_cast<PHINode>(BI)) { 01072 PN->addIncoming(ValueMap[PN->getIncomingValueForBlock(A_ExitingBlock)], 01073 B_ExitingBlock); 01074 PN->removeIncomingValue(A_ExitingBlock); 01075 } else 01076 break; 01077 } 01078 01079 DT->changeImmediateDominator(B_ExitBlock, B_ExitingBlock); 01080 DF->changeImmediateDominator(B_ExitBlock, B_ExitingBlock, DT); 01081 01082 //[*] Split ALoop's exit edge. This creates a new block which 01083 // serves two purposes. First one is to hold PHINode defnitions 01084 // to ensure that ALoop's LCSSA form. Second use it to act 01085 // as a preheader for BLoop. 01086 BasicBlock *A_ExitBlock = SplitEdge(A_ExitingBlock, B_Header, this); 01087 01088 //[*] Preserve ALoop's LCSSA form. Create new forwarding PHINodes 01089 // in A_ExitBlock to redefine outgoing PHI definitions from ALoop. 01090 for(BasicBlock::iterator BI = B_Header->begin(), BE = B_Header->end(); 01091 BI != BE; ++BI) { 01092 if (PHINode *PN = dyn_cast<PHINode>(BI)) { 01093 Value *V1 = PN->getIncomingValueForBlock(A_ExitBlock); 01094 PHINode *newPHI = PHINode::Create(PN->getType(), PN->getName()); 01095 newPHI->addIncoming(V1, A_ExitingBlock); 01096 A_ExitBlock->getInstList().push_front(newPHI); 01097 PN->removeIncomingValue(A_ExitBlock); 01098 PN->addIncoming(newPHI, A_ExitBlock); 01099 } else 01100 break; 01101 } 01102 01103 //[*] Eliminate split condition's inactive branch from ALoop. 01104 BasicBlock *A_SplitCondBlock = SplitCondition->getParent(); 01105 BranchInst *A_BR = cast<BranchInst>(A_SplitCondBlock->getTerminator()); 01106 BasicBlock *A_InactiveBranch = NULL; 01107 BasicBlock *A_ActiveBranch = NULL; 01108 A_ActiveBranch = A_BR->getSuccessor(0); 01109 A_InactiveBranch = A_BR->getSuccessor(1); 01110 A_BR->setUnconditionalDest(A_ActiveBranch); 01111 removeBlocks(A_InactiveBranch, L, A_ActiveBranch); 01112 01113 //[*] Eliminate split condition's inactive branch in from BLoop. 01114 BasicBlock *B_SplitCondBlock = cast<BasicBlock>(ValueMap[A_SplitCondBlock]); 01115 BranchInst *B_BR = cast<BranchInst>(B_SplitCondBlock->getTerminator()); 01116 BasicBlock *B_InactiveBranch = NULL; 01117 BasicBlock *B_ActiveBranch = NULL; 01118 B_ActiveBranch = B_BR->getSuccessor(1); 01119 B_InactiveBranch = B_BR->getSuccessor(0); 01120 B_BR->setUnconditionalDest(B_ActiveBranch); 01121 removeBlocks(B_InactiveBranch, BLoop, B_ActiveBranch); 01122 01123 BasicBlock *A_Header = ALoop->getHeader(); 01124 if (A_ExitingBlock == A_Header) 01125 return true; 01126 01127 //[*] Move exit condition into split condition block to avoid 01128 // executing dead loop iteration. 01129 ICmpInst *B_ExitCondition = cast<ICmpInst>(ValueMap[ExitCondition]); 01130 Instruction *B_IndVarIncrement = cast<Instruction>(ValueMap[IVIncrement]); 01131 ICmpInst *B_SplitCondition = cast<ICmpInst>(ValueMap[SplitCondition]); 01132 01133 moveExitCondition(A_SplitCondBlock, A_ActiveBranch, A_ExitBlock, ExitCondition, 01134 cast<ICmpInst>(SplitCondition), IndVar, IVIncrement, 01135 ALoop, EVOpNum); 01136 01137 moveExitCondition(B_SplitCondBlock, B_ActiveBranch, 01138 B_ExitBlock, B_ExitCondition, 01139 B_SplitCondition, B_IndVar, B_IndVarIncrement, 01140 BLoop, EVOpNum); 01141 01142 NumIndexSplit++; 01143 return true; 01144 } 01145 01146 /// cleanBlock - A block is considered clean if all non terminal instructions 01147 /// are either, PHINodes, IV based. 01148 bool LoopIndexSplit::cleanBlock(BasicBlock *BB) { 01149 Instruction *Terminator = BB->getTerminator(); 01150 for(BasicBlock::iterator BI = BB->begin(), BE = BB->end(); 01151 BI != BE; ++BI) { 01152 Instruction *I = BI; 01153 01154 if (isa<PHINode>(I) || I == Terminator || I == ExitCondition 01155 || I == SplitCondition || IVBasedValues.count(I) 01156 || isa<DbgInfoIntrinsic>(I)) 01157 continue; 01158 01159 if (I->mayHaveSideEffects()) 01160 return false; 01161 01162 // I is used only inside this block then it is OK. 01163 bool usedOutsideBB = false; 01164 for (Value::use_iterator UI = I->use_begin(), UE = I->use_end(); 01165 UI != UE; ++UI) { 01166 Instruction *U = cast<Instruction>(UI); 01167 if (U->getParent() != BB) 01168 usedOutsideBB = true; 01169 } 01170 if (!usedOutsideBB) 01171 continue; 01172 01173 // Otherwise we have a instruction that may not allow loop spliting. 01174 return false; 01175 } 01176 return true; 01177 } 01178 01179 /// IVisLT - If Op is comparing IV based value with an loop invariant and 01180 /// IV based value is less than the loop invariant then return the loop 01181 /// invariant. Otherwise return NULL. 01182 Value * LoopIndexSplit::IVisLT(ICmpInst &Op) { 01183 ICmpInst::Predicate P = Op.getPredicate(); 01184 if ((P == ICmpInst::ICMP_SLT || P == ICmpInst::ICMP_ULT) 01185 && IVBasedValues.count(Op.getOperand(0)) 01186 && L->isLoopInvariant(Op.getOperand(1))) 01187 return Op.getOperand(1); 01188 01189 if ((P == ICmpInst::ICMP_SGT || P == ICmpInst::ICMP_UGT) 01190 && IVBasedValues.count(Op.getOperand(1)) 01191 && L->isLoopInvariant(Op.getOperand(0))) 01192 return Op.getOperand(0); 01193 01194 return NULL; 01195 } 01196 01197 /// IVisLE - If Op is comparing IV based value with an loop invariant and 01198 /// IV based value is less than or equal to the loop invariant then 01199 /// return the loop invariant. Otherwise return NULL. 01200 Value * LoopIndexSplit::IVisLE(ICmpInst &Op) { 01201 ICmpInst::Predicate P = Op.getPredicate(); 01202 if ((P == ICmpInst::ICMP_SLE || P == ICmpInst::ICMP_ULE) 01203 && IVBasedValues.count(Op.getOperand(0)) 01204 && L->isLoopInvariant(Op.getOperand(1))) 01205 return Op.getOperand(1); 01206 01207 if ((P == ICmpInst::ICMP_SGE || P == ICmpInst::ICMP_UGE) 01208 && IVBasedValues.count(Op.getOperand(1)) 01209 && L->isLoopInvariant(Op.getOperand(0))) 01210 return Op.getOperand(0); 01211 01212 return NULL; 01213 } 01214 01215 /// IVisGT - If Op is comparing IV based value with an loop invariant and 01216 /// IV based value is greater than the loop invariant then return the loop 01217 /// invariant. Otherwise return NULL. 01218 Value * LoopIndexSplit::IVisGT(ICmpInst &Op) { 01219 ICmpInst::Predicate P = Op.getPredicate(); 01220 if ((P == ICmpInst::ICMP_SGT || P == ICmpInst::ICMP_UGT) 01221 && IVBasedValues.count(Op.getOperand(0)) 01222 && L->isLoopInvariant(Op.getOperand(1))) 01223 return Op.getOperand(1); 01224 01225 if ((P == ICmpInst::ICMP_SLT || P == ICmpInst::ICMP_ULT) 01226 && IVBasedValues.count(Op.getOperand(1)) 01227 && L->isLoopInvariant(Op.getOperand(0))) 01228 return Op.getOperand(0); 01229 01230 return NULL; 01231 } 01232 01233 /// IVisGE - If Op is comparing IV based value with an loop invariant and 01234 /// IV based value is greater than or equal to the loop invariant then 01235 /// return the loop invariant. Otherwise return NULL. 01236 Value * LoopIndexSplit::IVisGE(ICmpInst &Op) { 01237 ICmpInst::Predicate P = Op.getPredicate(); 01238 if ((P == ICmpInst::ICMP_SGE || P == ICmpInst::ICMP_UGE) 01239 && IVBasedValues.count(Op.getOperand(0)) 01240 && L->isLoopInvariant(Op.getOperand(1))) 01241 return Op.getOperand(1); 01242 01243 if ((P == ICmpInst::ICMP_SLE || P == ICmpInst::ICMP_ULE) 01244 && IVBasedValues.count(Op.getOperand(1)) 01245 && L->isLoopInvariant(Op.getOperand(0))) 01246 return Op.getOperand(0); 01247 01248 return NULL; 01249 } 01250