LLVM API Documentation
00001 //===-- LoopUnswitch.cpp - Hoist loop-invariant conditionals in loop ------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This pass transforms loops that contain branches on loop-invariant conditions 00011 // to have multiple loops. For example, it turns the left into the right code: 00012 // 00013 // for (...) if (lic) 00014 // A for (...) 00015 // if (lic) A; B; C 00016 // B else 00017 // C for (...) 00018 // A; C 00019 // 00020 // This can increase the size of the code exponentially (doubling it every time 00021 // a loop is unswitched) so we only unswitch if the resultant code will be 00022 // smaller than a threshold. 00023 // 00024 // This pass expects LICM to be run before it to hoist invariant conditions out 00025 // of the loop, to make the unswitching opportunity obvious. 00026 // 00027 //===----------------------------------------------------------------------===// 00028 00029 #define DEBUG_TYPE "loop-unswitch" 00030 #include "llvm/Transforms/Scalar.h" 00031 #include "llvm/Constants.h" 00032 #include "llvm/Function.h" 00033 #include "llvm/Instructions.h" 00034 #include "llvm/Analysis/LoopInfo.h" 00035 #include "llvm/Transforms/Utils/Cloning.h" 00036 #include "llvm/Transforms/Utils/Local.h" 00037 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 00038 #include "llvm/ADT/Statistic.h" 00039 #include "llvm/ADT/PostOrderIterator.h" 00040 #include "llvm/Support/Debug.h" 00041 #include "llvm/Support/CommandLine.h" 00042 #include <algorithm> 00043 #include <iostream> 00044 #include <set> 00045 using namespace llvm; 00046 00047 namespace { 00048 Statistic<> NumBranches("loop-unswitch", "Number of branches unswitched"); 00049 Statistic<> NumSwitches("loop-unswitch", "Number of switches unswitched"); 00050 Statistic<> NumSelects ("loop-unswitch", "Number of selects unswitched"); 00051 Statistic<> NumTrivial ("loop-unswitch", 00052 "Number of unswitches that are trivial"); 00053 Statistic<> NumSimplify("loop-unswitch", 00054 "Number of simplifications of unswitched code"); 00055 cl::opt<unsigned> 00056 Threshold("loop-unswitch-threshold", cl::desc("Max loop size to unswitch"), 00057 cl::init(10), cl::Hidden); 00058 00059 class LoopUnswitch : public FunctionPass { 00060 LoopInfo *LI; // Loop information 00061 00062 // LoopProcessWorklist - List of loops we need to process. 00063 std::vector<Loop*> LoopProcessWorklist; 00064 public: 00065 virtual bool runOnFunction(Function &F); 00066 bool visitLoop(Loop *L); 00067 00068 /// This transformation requires natural loop information & requires that 00069 /// loop preheaders be inserted into the CFG... 00070 /// 00071 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00072 AU.addRequiredID(LoopSimplifyID); 00073 AU.addPreservedID(LoopSimplifyID); 00074 AU.addRequired<LoopInfo>(); 00075 AU.addPreserved<LoopInfo>(); 00076 } 00077 00078 private: 00079 /// RemoveLoopFromWorklist - If the specified loop is on the loop worklist, 00080 /// remove it. 00081 void RemoveLoopFromWorklist(Loop *L) { 00082 std::vector<Loop*>::iterator I = std::find(LoopProcessWorklist.begin(), 00083 LoopProcessWorklist.end(), L); 00084 if (I != LoopProcessWorklist.end()) 00085 LoopProcessWorklist.erase(I); 00086 } 00087 00088 bool UnswitchIfProfitable(Value *LoopCond, Constant *Val,Loop *L); 00089 unsigned getLoopUnswitchCost(Loop *L, Value *LIC); 00090 void UnswitchTrivialCondition(Loop *L, Value *Cond, Constant *Val, 00091 BasicBlock *ExitBlock); 00092 void UnswitchNontrivialCondition(Value *LIC, Constant *OnVal, Loop *L); 00093 BasicBlock *SplitEdge(BasicBlock *From, BasicBlock *To); 00094 BasicBlock *SplitBlock(BasicBlock *Old, Instruction *SplitPt); 00095 00096 void RewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC, 00097 Constant *Val, bool isEqual); 00098 00099 void SimplifyCode(std::vector<Instruction*> &Worklist); 00100 void RemoveBlockIfDead(BasicBlock *BB, 00101 std::vector<Instruction*> &Worklist); 00102 void RemoveLoopFromHierarchy(Loop *L); 00103 }; 00104 RegisterOpt<LoopUnswitch> X("loop-unswitch", "Unswitch loops"); 00105 } 00106 00107 FunctionPass *llvm::createLoopUnswitchPass() { return new LoopUnswitch(); } 00108 00109 bool LoopUnswitch::runOnFunction(Function &F) { 00110 bool Changed = false; 00111 LI = &getAnalysis<LoopInfo>(); 00112 00113 // Populate the worklist of loops to process in post-order. 00114 for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) 00115 for (po_iterator<Loop*> LI = po_begin(*I), E = po_end(*I); LI != E; ++LI) 00116 LoopProcessWorklist.push_back(*LI); 00117 00118 // Process the loops in worklist order, this is a post-order visitation of 00119 // the loops. We use a worklist of loops so that loops can be removed at any 00120 // time if they are deleted (e.g. the backedge of a loop is removed). 00121 while (!LoopProcessWorklist.empty()) { 00122 Loop *L = LoopProcessWorklist.back(); 00123 LoopProcessWorklist.pop_back(); 00124 Changed |= visitLoop(L); 00125 } 00126 00127 return Changed; 00128 } 00129 00130 /// FindLIVLoopCondition - Cond is a condition that occurs in L. If it is 00131 /// invariant in the loop, or has an invariant piece, return the invariant. 00132 /// Otherwise, return null. 00133 static Value *FindLIVLoopCondition(Value *Cond, Loop *L, bool &Changed) { 00134 // Constants should be folded, not unswitched on! 00135 if (isa<Constant>(Cond)) return false; 00136 00137 // TODO: Handle: br (VARIANT|INVARIANT). 00138 // TODO: Hoist simple expressions out of loops. 00139 if (L->isLoopInvariant(Cond)) return Cond; 00140 00141 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Cond)) 00142 if (BO->getOpcode() == Instruction::And || 00143 BO->getOpcode() == Instruction::Or) { 00144 // If either the left or right side is invariant, we can unswitch on this, 00145 // which will cause the branch to go away in one loop and the condition to 00146 // simplify in the other one. 00147 if (Value *LHS = FindLIVLoopCondition(BO->getOperand(0), L, Changed)) 00148 return LHS; 00149 if (Value *RHS = FindLIVLoopCondition(BO->getOperand(1), L, Changed)) 00150 return RHS; 00151 } 00152 00153 return 0; 00154 } 00155 00156 bool LoopUnswitch::visitLoop(Loop *L) { 00157 bool Changed = false; 00158 00159 // Loop over all of the basic blocks in the loop. If we find an interior 00160 // block that is branching on a loop-invariant condition, we can unswitch this 00161 // loop. 00162 for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); 00163 I != E; ++I) { 00164 TerminatorInst *TI = (*I)->getTerminator(); 00165 if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { 00166 // If this isn't branching on an invariant condition, we can't unswitch 00167 // it. 00168 if (BI->isConditional()) { 00169 // See if this, or some part of it, is loop invariant. If so, we can 00170 // unswitch on it if we desire. 00171 Value *LoopCond = FindLIVLoopCondition(BI->getCondition(), L, Changed); 00172 if (LoopCond && UnswitchIfProfitable(LoopCond, ConstantBool::True, L)) { 00173 ++NumBranches; 00174 return true; 00175 } 00176 } 00177 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 00178 Value *LoopCond = FindLIVLoopCondition(SI->getCondition(), L, Changed); 00179 if (LoopCond && SI->getNumCases() > 1) { 00180 // Find a value to unswitch on: 00181 // FIXME: this should chose the most expensive case! 00182 Constant *UnswitchVal = SI->getCaseValue(1); 00183 if (UnswitchIfProfitable(LoopCond, UnswitchVal, L)) { 00184 ++NumSwitches; 00185 return true; 00186 } 00187 } 00188 } 00189 00190 // Scan the instructions to check for unswitchable values. 00191 for (BasicBlock::iterator BBI = (*I)->begin(), E = (*I)->end(); 00192 BBI != E; ++BBI) 00193 if (SelectInst *SI = dyn_cast<SelectInst>(BBI)) { 00194 Value *LoopCond = FindLIVLoopCondition(SI->getCondition(), L, Changed); 00195 if (LoopCond && UnswitchIfProfitable(LoopCond, ConstantBool::True, L)) { 00196 ++NumSelects; 00197 return true; 00198 } 00199 } 00200 } 00201 00202 return Changed; 00203 } 00204 00205 00206 /// LoopValuesUsedOutsideLoop - Return true if there are any values defined in 00207 /// the loop that are used by instructions outside of it. 00208 static bool LoopValuesUsedOutsideLoop(Loop *L) { 00209 // We will be doing lots of "loop contains block" queries. Loop::contains is 00210 // linear time, use a set to speed this up. 00211 std::set<BasicBlock*> LoopBlocks; 00212 00213 for (Loop::block_iterator BB = L->block_begin(), E = L->block_end(); 00214 BB != E; ++BB) 00215 LoopBlocks.insert(*BB); 00216 00217 for (Loop::block_iterator BB = L->block_begin(), E = L->block_end(); 00218 BB != E; ++BB) { 00219 for (BasicBlock::iterator I = (*BB)->begin(), E = (*BB)->end(); I != E; ++I) 00220 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; 00221 ++UI) { 00222 BasicBlock *UserBB = cast<Instruction>(*UI)->getParent(); 00223 if (!LoopBlocks.count(UserBB)) 00224 return true; 00225 } 00226 } 00227 return false; 00228 } 00229 00230 /// isTrivialLoopExitBlock - Check to see if all paths from BB either: 00231 /// 1. Exit the loop with no side effects. 00232 /// 2. Branch to the latch block with no side-effects. 00233 /// 00234 /// If these conditions are true, we return true and set ExitBB to the block we 00235 /// exit through. 00236 /// 00237 static bool isTrivialLoopExitBlockHelper(Loop *L, BasicBlock *BB, 00238 BasicBlock *&ExitBB, 00239 std::set<BasicBlock*> &Visited) { 00240 if (!Visited.insert(BB).second) { 00241 // Already visited and Ok, end of recursion. 00242 return true; 00243 } else if (!L->contains(BB)) { 00244 // Otherwise, this is a loop exit, this is fine so long as this is the 00245 // first exit. 00246 if (ExitBB != 0) return false; 00247 ExitBB = BB; 00248 return true; 00249 } 00250 00251 // Otherwise, this is an unvisited intra-loop node. Check all successors. 00252 for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI) { 00253 // Check to see if the successor is a trivial loop exit. 00254 if (!isTrivialLoopExitBlockHelper(L, *SI, ExitBB, Visited)) 00255 return false; 00256 } 00257 00258 // Okay, everything after this looks good, check to make sure that this block 00259 // doesn't include any side effects. 00260 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) 00261 if (I->mayWriteToMemory()) 00262 return false; 00263 00264 return true; 00265 } 00266 00267 /// isTrivialLoopExitBlock - Return true if the specified block unconditionally 00268 /// leads to an exit from the specified loop, and has no side-effects in the 00269 /// process. If so, return the block that is exited to, otherwise return null. 00270 static BasicBlock *isTrivialLoopExitBlock(Loop *L, BasicBlock *BB) { 00271 std::set<BasicBlock*> Visited; 00272 Visited.insert(L->getHeader()); // Branches to header are ok. 00273 BasicBlock *ExitBB = 0; 00274 if (isTrivialLoopExitBlockHelper(L, BB, ExitBB, Visited)) 00275 return ExitBB; 00276 return 0; 00277 } 00278 00279 /// IsTrivialUnswitchCondition - Check to see if this unswitch condition is 00280 /// trivial: that is, that the condition controls whether or not the loop does 00281 /// anything at all. If this is a trivial condition, unswitching produces no 00282 /// code duplications (equivalently, it produces a simpler loop and a new empty 00283 /// loop, which gets deleted). 00284 /// 00285 /// If this is a trivial condition, return true, otherwise return false. When 00286 /// returning true, this sets Cond and Val to the condition that controls the 00287 /// trivial condition: when Cond dynamically equals Val, the loop is known to 00288 /// exit. Finally, this sets LoopExit to the BB that the loop exits to when 00289 /// Cond == Val. 00290 /// 00291 static bool IsTrivialUnswitchCondition(Loop *L, Value *Cond, Constant **Val = 0, 00292 BasicBlock **LoopExit = 0) { 00293 BasicBlock *Header = L->getHeader(); 00294 TerminatorInst *HeaderTerm = Header->getTerminator(); 00295 00296 BasicBlock *LoopExitBB = 0; 00297 if (BranchInst *BI = dyn_cast<BranchInst>(HeaderTerm)) { 00298 // If the header block doesn't end with a conditional branch on Cond, we 00299 // can't handle it. 00300 if (!BI->isConditional() || BI->getCondition() != Cond) 00301 return false; 00302 00303 // Check to see if a successor of the branch is guaranteed to go to the 00304 // latch block or exit through a one exit block without having any 00305 // side-effects. If so, determine the value of Cond that causes it to do 00306 // this. 00307 if ((LoopExitBB = isTrivialLoopExitBlock(L, BI->getSuccessor(0)))) { 00308 if (Val) *Val = ConstantBool::True; 00309 } else if ((LoopExitBB = isTrivialLoopExitBlock(L, BI->getSuccessor(1)))) { 00310 if (Val) *Val = ConstantBool::False; 00311 } 00312 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(HeaderTerm)) { 00313 // If this isn't a switch on Cond, we can't handle it. 00314 if (SI->getCondition() != Cond) return false; 00315 00316 // Check to see if a successor of the switch is guaranteed to go to the 00317 // latch block or exit through a one exit block without having any 00318 // side-effects. If so, determine the value of Cond that causes it to do 00319 // this. Note that we can't trivially unswitch on the default case. 00320 for (unsigned i = 1, e = SI->getNumSuccessors(); i != e; ++i) 00321 if ((LoopExitBB = isTrivialLoopExitBlock(L, SI->getSuccessor(i)))) { 00322 // Okay, we found a trivial case, remember the value that is trivial. 00323 if (Val) *Val = SI->getCaseValue(i); 00324 break; 00325 } 00326 } 00327 00328 // If we didn't find a single unique LoopExit block, or if the loop exit block 00329 // contains phi nodes, this isn't trivial. 00330 if (!LoopExitBB || isa<PHINode>(LoopExitBB->begin())) 00331 return false; // Can't handle this. 00332 00333 if (LoopExit) *LoopExit = LoopExitBB; 00334 00335 // We already know that nothing uses any scalar values defined inside of this 00336 // loop. As such, we just have to check to see if this loop will execute any 00337 // side-effecting instructions (e.g. stores, calls, volatile loads) in the 00338 // part of the loop that the code *would* execute. We already checked the 00339 // tail, check the header now. 00340 for (BasicBlock::iterator I = Header->begin(), E = Header->end(); I != E; ++I) 00341 if (I->mayWriteToMemory()) 00342 return false; 00343 return true; 00344 } 00345 00346 /// getLoopUnswitchCost - Return the cost (code size growth) that will happen if 00347 /// we choose to unswitch the specified loop on the specified value. 00348 /// 00349 unsigned LoopUnswitch::getLoopUnswitchCost(Loop *L, Value *LIC) { 00350 // If the condition is trivial, always unswitch. There is no code growth for 00351 // this case. 00352 if (IsTrivialUnswitchCondition(L, LIC)) 00353 return 0; 00354 00355 unsigned Cost = 0; 00356 // FIXME: this is brain dead. It should take into consideration code 00357 // shrinkage. 00358 for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); 00359 I != E; ++I) { 00360 BasicBlock *BB = *I; 00361 // Do not include empty blocks in the cost calculation. This happen due to 00362 // loop canonicalization and will be removed. 00363 if (BB->begin() == BasicBlock::iterator(BB->getTerminator())) 00364 continue; 00365 00366 // Count basic blocks. 00367 ++Cost; 00368 } 00369 00370 return Cost; 00371 } 00372 00373 /// UnswitchIfProfitable - We have found that we can unswitch L when 00374 /// LoopCond == Val to simplify the loop. If we decide that this is profitable, 00375 /// unswitch the loop, reprocess the pieces, then return true. 00376 bool LoopUnswitch::UnswitchIfProfitable(Value *LoopCond, Constant *Val,Loop *L){ 00377 // Check to see if it would be profitable to unswitch this loop. 00378 unsigned Cost = getLoopUnswitchCost(L, LoopCond); 00379 if (Cost > Threshold) { 00380 // FIXME: this should estimate growth by the amount of code shared by the 00381 // resultant unswitched loops. 00382 // 00383 DEBUG(std::cerr << "NOT unswitching loop %" 00384 << L->getHeader()->getName() << ", cost too high: " 00385 << L->getBlocks().size() << "\n"); 00386 return false; 00387 } 00388 00389 // If this loop has live-out values, we can't unswitch it. We need something 00390 // like loop-closed SSA form in order to know how to insert PHI nodes for 00391 // these values. 00392 if (LoopValuesUsedOutsideLoop(L)) { 00393 DEBUG(std::cerr << "NOT unswitching loop %" << L->getHeader()->getName() 00394 << ", a loop value is used outside loop! Cost: " 00395 << Cost << "\n"); 00396 return false; 00397 } 00398 00399 // If this is a trivial condition to unswitch (which results in no code 00400 // duplication), do it now. 00401 Constant *CondVal; 00402 BasicBlock *ExitBlock; 00403 if (IsTrivialUnswitchCondition(L, LoopCond, &CondVal, &ExitBlock)) { 00404 UnswitchTrivialCondition(L, LoopCond, CondVal, ExitBlock); 00405 } else { 00406 UnswitchNontrivialCondition(LoopCond, Val, L); 00407 } 00408 00409 return true; 00410 } 00411 00412 /// SplitBlock - Split the specified block at the specified instruction - every 00413 /// thing before SplitPt stays in Old and everything starting with SplitPt moves 00414 /// to a new block. The two blocks are joined by an unconditional branch and 00415 /// the loop info is updated. 00416 /// 00417 BasicBlock *LoopUnswitch::SplitBlock(BasicBlock *Old, Instruction *SplitPt) { 00418 BasicBlock::iterator SplitIt = SplitPt; 00419 while (isa<PHINode>(SplitIt)) 00420 ++SplitIt; 00421 BasicBlock *New = Old->splitBasicBlock(SplitIt, Old->getName()+".split"); 00422 00423 // The new block lives in whichever loop the old one did. 00424 if (Loop *L = LI->getLoopFor(Old)) 00425 L->addBasicBlockToLoop(New, *LI); 00426 00427 return New; 00428 } 00429 00430 00431 BasicBlock *LoopUnswitch::SplitEdge(BasicBlock *BB, BasicBlock *Succ) { 00432 TerminatorInst *LatchTerm = BB->getTerminator(); 00433 unsigned SuccNum = 0; 00434 for (unsigned i = 0, e = LatchTerm->getNumSuccessors(); ; ++i) { 00435 assert(i != e && "Didn't find edge?"); 00436 if (LatchTerm->getSuccessor(i) == Succ) { 00437 SuccNum = i; 00438 break; 00439 } 00440 } 00441 00442 // If this is a critical edge, let SplitCriticalEdge do it. 00443 if (SplitCriticalEdge(BB->getTerminator(), SuccNum, this)) 00444 return LatchTerm->getSuccessor(SuccNum); 00445 00446 // If the edge isn't critical, then BB has a single successor or Succ has a 00447 // single pred. Split the block. 00448 BasicBlock::iterator SplitPoint; 00449 if (BasicBlock *SP = Succ->getSinglePredecessor()) { 00450 // If the successor only has a single pred, split the top of the successor 00451 // block. 00452 assert(SP == BB && "CFG broken"); 00453 return SplitBlock(Succ, Succ->begin()); 00454 } else { 00455 // Otherwise, if BB has a single successor, split it at the bottom of the 00456 // block. 00457 assert(BB->getTerminator()->getNumSuccessors() == 1 && 00458 "Should have a single succ!"); 00459 return SplitBlock(BB, BB->getTerminator()); 00460 } 00461 } 00462 00463 00464 00465 // RemapInstruction - Convert the instruction operands from referencing the 00466 // current values into those specified by ValueMap. 00467 // 00468 static inline void RemapInstruction(Instruction *I, 00469 std::map<const Value *, Value*> &ValueMap) { 00470 for (unsigned op = 0, E = I->getNumOperands(); op != E; ++op) { 00471 Value *Op = I->getOperand(op); 00472 std::map<const Value *, Value*>::iterator It = ValueMap.find(Op); 00473 if (It != ValueMap.end()) Op = It->second; 00474 I->setOperand(op, Op); 00475 } 00476 } 00477 00478 /// CloneLoop - Recursively clone the specified loop and all of its children, 00479 /// mapping the blocks with the specified map. 00480 static Loop *CloneLoop(Loop *L, Loop *PL, std::map<const Value*, Value*> &VM, 00481 LoopInfo *LI) { 00482 Loop *New = new Loop(); 00483 00484 if (PL) 00485 PL->addChildLoop(New); 00486 else 00487 LI->addTopLevelLoop(New); 00488 00489 // Add all of the blocks in L to the new loop. 00490 for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); 00491 I != E; ++I) 00492 if (LI->getLoopFor(*I) == L) 00493 New->addBasicBlockToLoop(cast<BasicBlock>(VM[*I]), *LI); 00494 00495 // Add all of the subloops to the new loop. 00496 for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I) 00497 CloneLoop(*I, New, VM, LI); 00498 00499 return New; 00500 } 00501 00502 /// EmitPreheaderBranchOnCondition - Emit a conditional branch on two values 00503 /// if LIC == Val, branch to TrueDst, otherwise branch to FalseDest. Insert the 00504 /// code immediately before InsertPt. 00505 static void EmitPreheaderBranchOnCondition(Value *LIC, Constant *Val, 00506 BasicBlock *TrueDest, 00507 BasicBlock *FalseDest, 00508 Instruction *InsertPt) { 00509 // Insert a conditional branch on LIC to the two preheaders. The original 00510 // code is the true version and the new code is the false version. 00511 Value *BranchVal = LIC; 00512 if (!isa<ConstantBool>(Val)) { 00513 BranchVal = BinaryOperator::createSetEQ(LIC, Val, "tmp", InsertPt); 00514 } else if (Val != ConstantBool::True) { 00515 // We want to enter the new loop when the condition is true. 00516 std::swap(TrueDest, FalseDest); 00517 } 00518 00519 // Insert the new branch. 00520 new BranchInst(TrueDest, FalseDest, BranchVal, InsertPt); 00521 } 00522 00523 00524 /// UnswitchTrivialCondition - Given a loop that has a trivial unswitchable 00525 /// condition in it (a cond branch from its header block to its latch block, 00526 /// where the path through the loop that doesn't execute its body has no 00527 /// side-effects), unswitch it. This doesn't involve any code duplication, just 00528 /// moving the conditional branch outside of the loop and updating loop info. 00529 void LoopUnswitch::UnswitchTrivialCondition(Loop *L, Value *Cond, 00530 Constant *Val, 00531 BasicBlock *ExitBlock) { 00532 DEBUG(std::cerr << "loop-unswitch: Trivial-Unswitch loop %" 00533 << L->getHeader()->getName() << " [" << L->getBlocks().size() 00534 << " blocks] in Function " << L->getHeader()->getParent()->getName() 00535 << " on cond: " << *Val << " == " << *Cond << "\n"); 00536 00537 // First step, split the preheader, so that we know that there is a safe place 00538 // to insert the conditional branch. We will change 'OrigPH' to have a 00539 // conditional branch on Cond. 00540 BasicBlock *OrigPH = L->getLoopPreheader(); 00541 BasicBlock *NewPH = SplitEdge(OrigPH, L->getHeader()); 00542 00543 // Now that we have a place to insert the conditional branch, create a place 00544 // to branch to: this is the exit block out of the loop that we should 00545 // short-circuit to. 00546 00547 // Split this block now, so that the loop maintains its exit block, and so 00548 // that the jump from the preheader can execute the contents of the exit block 00549 // without actually branching to it (the exit block should be dominated by the 00550 // loop header, not the preheader). 00551 assert(!L->contains(ExitBlock) && "Exit block is in the loop?"); 00552 BasicBlock *NewExit = SplitBlock(ExitBlock, ExitBlock->begin()); 00553 00554 // Okay, now we have a position to branch from and a position to branch to, 00555 // insert the new conditional branch. 00556 EmitPreheaderBranchOnCondition(Cond, Val, NewExit, NewPH, 00557 OrigPH->getTerminator()); 00558 OrigPH->getTerminator()->eraseFromParent(); 00559 00560 // We need to reprocess this loop, it could be unswitched again. 00561 LoopProcessWorklist.push_back(L); 00562 00563 // Now that we know that the loop is never entered when this condition is a 00564 // particular value, rewrite the loop with this info. We know that this will 00565 // at least eliminate the old branch. 00566 RewriteLoopBodyWithConditionConstant(L, Cond, Val, false); 00567 ++NumTrivial; 00568 } 00569 00570 00571 /// VersionLoop - We determined that the loop is profitable to unswitch when LIC 00572 /// equal Val. Split it into loop versions and test the condition outside of 00573 /// either loop. Return the loops created as Out1/Out2. 00574 void LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val, 00575 Loop *L) { 00576 Function *F = L->getHeader()->getParent(); 00577 DEBUG(std::cerr << "loop-unswitch: Unswitching loop %" 00578 << L->getHeader()->getName() << " [" << L->getBlocks().size() 00579 << " blocks] in Function " << F->getName() 00580 << " when '" << *Val << "' == " << *LIC << "\n"); 00581 00582 // LoopBlocks contains all of the basic blocks of the loop, including the 00583 // preheader of the loop, the body of the loop, and the exit blocks of the 00584 // loop, in that order. 00585 std::vector<BasicBlock*> LoopBlocks; 00586 00587 // First step, split the preheader and exit blocks, and add these blocks to 00588 // the LoopBlocks list. 00589 BasicBlock *OrigPreheader = L->getLoopPreheader(); 00590 LoopBlocks.push_back(SplitEdge(OrigPreheader, L->getHeader())); 00591 00592 // We want the loop to come after the preheader, but before the exit blocks. 00593 LoopBlocks.insert(LoopBlocks.end(), L->block_begin(), L->block_end()); 00594 00595 std::vector<BasicBlock*> ExitBlocks; 00596 L->getExitBlocks(ExitBlocks); 00597 std::sort(ExitBlocks.begin(), ExitBlocks.end()); 00598 ExitBlocks.erase(std::unique(ExitBlocks.begin(), ExitBlocks.end()), 00599 ExitBlocks.end()); 00600 00601 // Split all of the edges from inside the loop to their exit blocks. This 00602 // unswitching trivial: no phi nodes to update. 00603 unsigned NumBlocks = L->getBlocks().size(); 00604 00605 for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) { 00606 BasicBlock *ExitBlock = ExitBlocks[i]; 00607 std::vector<BasicBlock*> Preds(pred_begin(ExitBlock), pred_end(ExitBlock)); 00608 00609 for (unsigned j = 0, e = Preds.size(); j != e; ++j) { 00610 assert(L->contains(Preds[j]) && 00611 "All preds of loop exit blocks must be the same loop!"); 00612 SplitEdge(Preds[j], ExitBlock); 00613 } 00614 } 00615 00616 // The exit blocks may have been changed due to edge splitting, recompute. 00617 ExitBlocks.clear(); 00618 L->getExitBlocks(ExitBlocks); 00619 std::sort(ExitBlocks.begin(), ExitBlocks.end()); 00620 ExitBlocks.erase(std::unique(ExitBlocks.begin(), ExitBlocks.end()), 00621 ExitBlocks.end()); 00622 00623 // Add exit blocks to the loop blocks. 00624 LoopBlocks.insert(LoopBlocks.end(), ExitBlocks.begin(), ExitBlocks.end()); 00625 00626 // Next step, clone all of the basic blocks that make up the loop (including 00627 // the loop preheader and exit blocks), keeping track of the mapping between 00628 // the instructions and blocks. 00629 std::vector<BasicBlock*> NewBlocks; 00630 NewBlocks.reserve(LoopBlocks.size()); 00631 std::map<const Value*, Value*> ValueMap; 00632 for (unsigned i = 0, e = LoopBlocks.size(); i != e; ++i) { 00633 BasicBlock *New = CloneBasicBlock(LoopBlocks[i], ValueMap, ".us", F); 00634 NewBlocks.push_back(New); 00635 ValueMap[LoopBlocks[i]] = New; // Keep the BB mapping. 00636 } 00637 00638 // Splice the newly inserted blocks into the function right before the 00639 // original preheader. 00640 F->getBasicBlockList().splice(LoopBlocks[0], F->getBasicBlockList(), 00641 NewBlocks[0], F->end()); 00642 00643 // Now we create the new Loop object for the versioned loop. 00644 Loop *NewLoop = CloneLoop(L, L->getParentLoop(), ValueMap, LI); 00645 Loop *ParentLoop = L->getParentLoop(); 00646 if (ParentLoop) { 00647 // Make sure to add the cloned preheader and exit blocks to the parent loop 00648 // as well. 00649 ParentLoop->addBasicBlockToLoop(NewBlocks[0], *LI); 00650 } 00651 00652 for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) { 00653 BasicBlock *NewExit = cast<BasicBlock>(ValueMap[ExitBlocks[i]]); 00654 // The new exit block should be in the same loop as the old one. 00655 if (Loop *ExitBBLoop = LI->getLoopFor(ExitBlocks[i])) 00656 ExitBBLoop->addBasicBlockToLoop(NewExit, *LI); 00657 00658 assert(NewExit->getTerminator()->getNumSuccessors() == 1 && 00659 "Exit block should have been split to have one successor!"); 00660 BasicBlock *ExitSucc = NewExit->getTerminator()->getSuccessor(0); 00661 00662 // If the successor of the exit block had PHI nodes, add an entry for 00663 // NewExit. 00664 PHINode *PN; 00665 for (BasicBlock::iterator I = ExitSucc->begin(); 00666 (PN = dyn_cast<PHINode>(I)); ++I) { 00667 Value *V = PN->getIncomingValueForBlock(ExitBlocks[i]); 00668 std::map<const Value *, Value*>::iterator It = ValueMap.find(V); 00669 if (It != ValueMap.end()) V = It->second; 00670 PN->addIncoming(V, NewExit); 00671 } 00672 } 00673 00674 // Rewrite the code to refer to itself. 00675 for (unsigned i = 0, e = NewBlocks.size(); i != e; ++i) 00676 for (BasicBlock::iterator I = NewBlocks[i]->begin(), 00677 E = NewBlocks[i]->end(); I != E; ++I) 00678 RemapInstruction(I, ValueMap); 00679 00680 // Rewrite the original preheader to select between versions of the loop. 00681 BranchInst *OldBR = cast<BranchInst>(OrigPreheader->getTerminator()); 00682 assert(OldBR->isUnconditional() && OldBR->getSuccessor(0) == LoopBlocks[0] && 00683 "Preheader splitting did not work correctly!"); 00684 00685 // Emit the new branch that selects between the two versions of this loop. 00686 EmitPreheaderBranchOnCondition(LIC, Val, NewBlocks[0], LoopBlocks[0], OldBR); 00687 OldBR->eraseFromParent(); 00688 00689 LoopProcessWorklist.push_back(L); 00690 LoopProcessWorklist.push_back(NewLoop); 00691 00692 // Now we rewrite the original code to know that the condition is true and the 00693 // new code to know that the condition is false. 00694 RewriteLoopBodyWithConditionConstant(L , LIC, Val, false); 00695 00696 // It's possible that simplifying one loop could cause the other to be 00697 // deleted. If so, don't simplify it. 00698 if (!LoopProcessWorklist.empty() && LoopProcessWorklist.back() == NewLoop) 00699 RewriteLoopBodyWithConditionConstant(NewLoop, LIC, Val, true); 00700 } 00701 00702 /// RemoveFromWorklist - Remove all instances of I from the worklist vector 00703 /// specified. 00704 static void RemoveFromWorklist(Instruction *I, 00705 std::vector<Instruction*> &Worklist) { 00706 std::vector<Instruction*>::iterator WI = std::find(Worklist.begin(), 00707 Worklist.end(), I); 00708 while (WI != Worklist.end()) { 00709 unsigned Offset = WI-Worklist.begin(); 00710 Worklist.erase(WI); 00711 WI = std::find(Worklist.begin()+Offset, Worklist.end(), I); 00712 } 00713 } 00714 00715 /// ReplaceUsesOfWith - When we find that I really equals V, remove I from the 00716 /// program, replacing all uses with V and update the worklist. 00717 static void ReplaceUsesOfWith(Instruction *I, Value *V, 00718 std::vector<Instruction*> &Worklist) { 00719 DEBUG(std::cerr << "Replace with '" << *V << "': " << *I); 00720 00721 // Add uses to the worklist, which may be dead now. 00722 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 00723 if (Instruction *Use = dyn_cast<Instruction>(I->getOperand(i))) 00724 Worklist.push_back(Use); 00725 00726 // Add users to the worklist which may be simplified now. 00727 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 00728 UI != E; ++UI) 00729 Worklist.push_back(cast<Instruction>(*UI)); 00730 I->replaceAllUsesWith(V); 00731 I->eraseFromParent(); 00732 RemoveFromWorklist(I, Worklist); 00733 ++NumSimplify; 00734 } 00735 00736 /// RemoveBlockIfDead - If the specified block is dead, remove it, update loop 00737 /// information, and remove any dead successors it has. 00738 /// 00739 void LoopUnswitch::RemoveBlockIfDead(BasicBlock *BB, 00740 std::vector<Instruction*> &Worklist) { 00741 if (pred_begin(BB) != pred_end(BB)) { 00742 // This block isn't dead, since an edge to BB was just removed, see if there 00743 // are any easy simplifications we can do now. 00744 if (BasicBlock *Pred = BB->getSinglePredecessor()) { 00745 // If it has one pred, fold phi nodes in BB. 00746 while (isa<PHINode>(BB->begin())) 00747 ReplaceUsesOfWith(BB->begin(), 00748 cast<PHINode>(BB->begin())->getIncomingValue(0), 00749 Worklist); 00750 00751 // If this is the header of a loop and the only pred is the latch, we now 00752 // have an unreachable loop. 00753 if (Loop *L = LI->getLoopFor(BB)) 00754 if (L->getHeader() == BB && L->contains(Pred)) { 00755 // Remove the branch from the latch to the header block, this makes 00756 // the header dead, which will make the latch dead (because the header 00757 // dominates the latch). 00758 Pred->getTerminator()->eraseFromParent(); 00759 new UnreachableInst(Pred); 00760 00761 // The loop is now broken, remove it from LI. 00762 RemoveLoopFromHierarchy(L); 00763 00764 // Reprocess the header, which now IS dead. 00765 RemoveBlockIfDead(BB, Worklist); 00766 return; 00767 } 00768 00769 // If pred ends in a uncond branch, add uncond branch to worklist so that 00770 // the two blocks will get merged. 00771 if (BranchInst *BI = dyn_cast<BranchInst>(Pred->getTerminator())) 00772 if (BI->isUnconditional()) 00773 Worklist.push_back(BI); 00774 } 00775 return; 00776 } 00777 00778 DEBUG(std::cerr << "Nuking dead block: " << *BB); 00779 00780 // Remove the instructions in the basic block from the worklist. 00781 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) { 00782 RemoveFromWorklist(I, Worklist); 00783 00784 // Anything that uses the instructions in this basic block should have their 00785 // uses replaced with undefs. 00786 if (!I->use_empty()) 00787 I->replaceAllUsesWith(UndefValue::get(I->getType())); 00788 } 00789 00790 // If this is the edge to the header block for a loop, remove the loop and 00791 // promote all subloops. 00792 if (Loop *BBLoop = LI->getLoopFor(BB)) { 00793 if (BBLoop->getLoopLatch() == BB) 00794 RemoveLoopFromHierarchy(BBLoop); 00795 } 00796 00797 // Remove the block from the loop info, which removes it from any loops it 00798 // was in. 00799 LI->removeBlock(BB); 00800 00801 00802 // Remove phi node entries in successors for this block. 00803 TerminatorInst *TI = BB->getTerminator(); 00804 std::vector<BasicBlock*> Succs; 00805 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) { 00806 Succs.push_back(TI->getSuccessor(i)); 00807 TI->getSuccessor(i)->removePredecessor(BB); 00808 } 00809 00810 // Unique the successors, remove anything with multiple uses. 00811 std::sort(Succs.begin(), Succs.end()); 00812 Succs.erase(std::unique(Succs.begin(), Succs.end()), Succs.end()); 00813 00814 // Remove the basic block, including all of the instructions contained in it. 00815 BB->eraseFromParent(); 00816 00817 // Remove successor blocks here that are not dead, so that we know we only 00818 // have dead blocks in this list. Nondead blocks have a way of becoming dead, 00819 // then getting removed before we revisit them, which is badness. 00820 // 00821 for (unsigned i = 0; i != Succs.size(); ++i) 00822 if (pred_begin(Succs[i]) != pred_end(Succs[i])) { 00823 // One exception is loop headers. If this block was the preheader for a 00824 // loop, then we DO want to visit the loop so the loop gets deleted. 00825 // We know that if the successor is a loop header, that this loop had to 00826 // be the preheader: the case where this was the latch block was handled 00827 // above and headers can only have two predecessors. 00828 if (!LI->isLoopHeader(Succs[i])) { 00829 Succs.erase(Succs.begin()+i); 00830 --i; 00831 } 00832 } 00833 00834 for (unsigned i = 0, e = Succs.size(); i != e; ++i) 00835 RemoveBlockIfDead(Succs[i], Worklist); 00836 } 00837 00838 /// RemoveLoopFromHierarchy - We have discovered that the specified loop has 00839 /// become unwrapped, either because the backedge was deleted, or because the 00840 /// edge into the header was removed. If the edge into the header from the 00841 /// latch block was removed, the loop is unwrapped but subloops are still alive, 00842 /// so they just reparent loops. If the loops are actually dead, they will be 00843 /// removed later. 00844 void LoopUnswitch::RemoveLoopFromHierarchy(Loop *L) { 00845 if (Loop *ParentLoop = L->getParentLoop()) { // Not a top-level loop. 00846 // Reparent all of the blocks in this loop. Since BBLoop had a parent, 00847 // they are now all in it. 00848 for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); 00849 I != E; ++I) 00850 if (LI->getLoopFor(*I) == L) // Don't change blocks in subloops. 00851 LI->changeLoopFor(*I, ParentLoop); 00852 00853 // Remove the loop from its parent loop. 00854 for (Loop::iterator I = ParentLoop->begin(), E = ParentLoop->end();; 00855 ++I) { 00856 assert(I != E && "Couldn't find loop"); 00857 if (*I == L) { 00858 ParentLoop->removeChildLoop(I); 00859 break; 00860 } 00861 } 00862 00863 // Move all subloops into the parent loop. 00864 while (L->begin() != L->end()) 00865 ParentLoop->addChildLoop(L->removeChildLoop(L->end()-1)); 00866 } else { 00867 // Reparent all of the blocks in this loop. Since BBLoop had no parent, 00868 // they no longer in a loop at all. 00869 00870 for (unsigned i = 0; i != L->getBlocks().size(); ++i) { 00871 // Don't change blocks in subloops. 00872 if (LI->getLoopFor(L->getBlocks()[i]) == L) { 00873 LI->removeBlock(L->getBlocks()[i]); 00874 --i; 00875 } 00876 } 00877 00878 // Remove the loop from the top-level LoopInfo object. 00879 for (LoopInfo::iterator I = LI->begin(), E = LI->end();; ++I) { 00880 assert(I != E && "Couldn't find loop"); 00881 if (*I == L) { 00882 LI->removeLoop(I); 00883 break; 00884 } 00885 } 00886 00887 // Move all of the subloops to the top-level. 00888 while (L->begin() != L->end()) 00889 LI->addTopLevelLoop(L->removeChildLoop(L->end()-1)); 00890 } 00891 00892 delete L; 00893 RemoveLoopFromWorklist(L); 00894 } 00895 00896 00897 00898 // RewriteLoopBodyWithConditionConstant - We know either that the value LIC has 00899 // the value specified by Val in the specified loop, or we know it does NOT have 00900 // that value. Rewrite any uses of LIC or of properties correlated to it. 00901 void LoopUnswitch::RewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC, 00902 Constant *Val, 00903 bool IsEqual) { 00904 assert(!isa<Constant>(LIC) && "Why are we unswitching on a constant?"); 00905 00906 // FIXME: Support correlated properties, like: 00907 // for (...) 00908 // if (li1 < li2) 00909 // ... 00910 // if (li1 > li2) 00911 // ... 00912 00913 // FOLD boolean conditions (X|LIC), (X&LIC). Fold conditional branches, 00914 // selects, switches. 00915 std::vector<User*> Users(LIC->use_begin(), LIC->use_end()); 00916 std::vector<Instruction*> Worklist; 00917 00918 // If we know that LIC == Val, or that LIC == NotVal, just replace uses of LIC 00919 // in the loop with the appropriate one directly. 00920 if (IsEqual || isa<ConstantBool>(Val)) { 00921 Value *Replacement; 00922 if (IsEqual) 00923 Replacement = Val; 00924 else 00925 Replacement = ConstantBool::get(!cast<ConstantBool>(Val)->getValue()); 00926 00927 for (unsigned i = 0, e = Users.size(); i != e; ++i) 00928 if (Instruction *U = cast<Instruction>(Users[i])) { 00929 if (!L->contains(U->getParent())) 00930 continue; 00931 U->replaceUsesOfWith(LIC, Replacement); 00932 Worklist.push_back(U); 00933 } 00934 } else { 00935 // Otherwise, we don't know the precise value of LIC, but we do know that it 00936 // is certainly NOT "Val". As such, simplify any uses in the loop that we 00937 // can. This case occurs when we unswitch switch statements. 00938 for (unsigned i = 0, e = Users.size(); i != e; ++i) 00939 if (Instruction *U = cast<Instruction>(Users[i])) { 00940 if (!L->contains(U->getParent())) 00941 continue; 00942 00943 Worklist.push_back(U); 00944 00945 // If we know that LIC is not Val, use this info to simplify code. 00946 if (SwitchInst *SI = dyn_cast<SwitchInst>(U)) { 00947 for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) { 00948 if (SI->getCaseValue(i) == Val) { 00949 // Found a dead case value. Don't remove PHI nodes in the 00950 // successor if they become single-entry, those PHI nodes may 00951 // be in the Users list. 00952 SI->getSuccessor(i)->removePredecessor(SI->getParent(), true); 00953 SI->removeCase(i); 00954 break; 00955 } 00956 } 00957 } 00958 00959 // TODO: We could do other simplifications, for example, turning 00960 // LIC == Val -> false. 00961 } 00962 } 00963 00964 SimplifyCode(Worklist); 00965 } 00966 00967 /// SimplifyCode - Okay, now that we have simplified some instructions in the 00968 /// loop, walk over it and constant prop, dce, and fold control flow where 00969 /// possible. Note that this is effectively a very simple loop-structure-aware 00970 /// optimizer. During processing of this loop, L could very well be deleted, so 00971 /// it must not be used. 00972 /// 00973 /// FIXME: When the loop optimizer is more mature, separate this out to a new 00974 /// pass. 00975 /// 00976 void LoopUnswitch::SimplifyCode(std::vector<Instruction*> &Worklist) { 00977 while (!Worklist.empty()) { 00978 Instruction *I = Worklist.back(); 00979 Worklist.pop_back(); 00980 00981 // Simple constant folding. 00982 if (Constant *C = ConstantFoldInstruction(I)) { 00983 ReplaceUsesOfWith(I, C, Worklist); 00984 continue; 00985 } 00986 00987 // Simple DCE. 00988 if (isInstructionTriviallyDead(I)) { 00989 DEBUG(std::cerr << "Remove dead instruction '" << *I); 00990 00991 // Add uses to the worklist, which may be dead now. 00992 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 00993 if (Instruction *Use = dyn_cast<Instruction>(I->getOperand(i))) 00994 Worklist.push_back(Use); 00995 I->eraseFromParent(); 00996 RemoveFromWorklist(I, Worklist); 00997 ++NumSimplify; 00998 continue; 00999 } 01000 01001 // Special case hacks that appear commonly in unswitched code. 01002 switch (I->getOpcode()) { 01003 case Instruction::Select: 01004 if (ConstantBool *CB = dyn_cast<ConstantBool>(I->getOperand(0))) { 01005 ReplaceUsesOfWith(I, I->getOperand(!CB->getValue()+1), Worklist); 01006 continue; 01007 } 01008 break; 01009 case Instruction::And: 01010 if (isa<ConstantBool>(I->getOperand(0))) // constant -> RHS 01011 cast<BinaryOperator>(I)->swapOperands(); 01012 if (ConstantBool *CB = dyn_cast<ConstantBool>(I->getOperand(1))) { 01013 if (CB->getValue()) // X & 1 -> X 01014 ReplaceUsesOfWith(I, I->getOperand(0), Worklist); 01015 else // X & 0 -> 0 01016 ReplaceUsesOfWith(I, I->getOperand(1), Worklist); 01017 continue; 01018 } 01019 break; 01020 case Instruction::Or: 01021 if (isa<ConstantBool>(I->getOperand(0))) // constant -> RHS 01022 cast<BinaryOperator>(I)->swapOperands(); 01023 if (ConstantBool *CB = dyn_cast<ConstantBool>(I->getOperand(1))) { 01024 if (CB->getValue()) // X | 1 -> 1 01025 ReplaceUsesOfWith(I, I->getOperand(1), Worklist); 01026 else // X | 0 -> X 01027 ReplaceUsesOfWith(I, I->getOperand(0), Worklist); 01028 continue; 01029 } 01030 break; 01031 case Instruction::Br: { 01032 BranchInst *BI = cast<BranchInst>(I); 01033 if (BI->isUnconditional()) { 01034 // If BI's parent is the only pred of the successor, fold the two blocks 01035 // together. 01036 BasicBlock *Pred = BI->getParent(); 01037 BasicBlock *Succ = BI->getSuccessor(0); 01038 BasicBlock *SinglePred = Succ->getSinglePredecessor(); 01039 if (!SinglePred) continue; // Nothing to do. 01040 assert(SinglePred == Pred && "CFG broken"); 01041 01042 DEBUG(std::cerr << "Merging blocks: " << Pred->getName() << " <- " 01043 << Succ->getName() << "\n"); 01044 01045 // Resolve any single entry PHI nodes in Succ. 01046 while (PHINode *PN = dyn_cast<PHINode>(Succ->begin())) 01047 ReplaceUsesOfWith(PN, PN->getIncomingValue(0), Worklist); 01048 01049 // Move all of the successor contents from Succ to Pred. 01050 Pred->getInstList().splice(BI, Succ->getInstList(), Succ->begin(), 01051 Succ->end()); 01052 BI->eraseFromParent(); 01053 RemoveFromWorklist(BI, Worklist); 01054 01055 // If Succ has any successors with PHI nodes, update them to have 01056 // entries coming from Pred instead of Succ. 01057 Succ->replaceAllUsesWith(Pred); 01058 01059 // Remove Succ from the loop tree. 01060 LI->removeBlock(Succ); 01061 Succ->eraseFromParent(); 01062 ++NumSimplify; 01063 } else if (ConstantBool *CB = dyn_cast<ConstantBool>(BI->getCondition())){ 01064 // Conditional branch. Turn it into an unconditional branch, then 01065 // remove dead blocks. 01066 break; // FIXME: Enable. 01067 01068 DEBUG(std::cerr << "Folded branch: " << *BI); 01069 BasicBlock *DeadSucc = BI->getSuccessor(CB->getValue()); 01070 BasicBlock *LiveSucc = BI->getSuccessor(!CB->getValue()); 01071 DeadSucc->removePredecessor(BI->getParent(), true); 01072 Worklist.push_back(new BranchInst(LiveSucc, BI)); 01073 BI->eraseFromParent(); 01074 RemoveFromWorklist(BI, Worklist); 01075 ++NumSimplify; 01076 01077 RemoveBlockIfDead(DeadSucc, Worklist); 01078 } 01079 break; 01080 } 01081 } 01082 } 01083 }