1 //===-- LoopUnswitch.cpp - Hoist loop-invariant conditionals in loop ------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This pass transforms loops that contain branches on loop-invariant conditions 11 // to have multiple loops. For example, it turns the left into the right code: 12 // 13 // for (...) if (lic) 14 // A for (...) 15 // if (lic) A; B; C 16 // B else 17 // C for (...) 18 // A; C 19 // 20 // This can increase the size of the code exponentially (doubling it every time 21 // a loop is unswitched) so we only unswitch if the resultant code will be 22 // smaller than a threshold. 23 // 24 // This pass expects LICM to be run before it to hoist invariant conditions out 25 // of the loop, to make the unswitching opportunity obvious. 26 // 27 //===----------------------------------------------------------------------===// 28 29 #include "llvm/Transforms/Scalar.h" 30 #include "llvm/ADT/STLExtras.h" 31 #include "llvm/ADT/SmallPtrSet.h" 32 #include "llvm/ADT/Statistic.h" 33 #include "llvm/Analysis/AssumptionCache.h" 34 #include "llvm/Analysis/CodeMetrics.h" 35 #include "llvm/Analysis/InstructionSimplify.h" 36 #include "llvm/Analysis/LoopInfo.h" 37 #include "llvm/Analysis/LoopPass.h" 38 #include "llvm/Analysis/ScalarEvolution.h" 39 #include "llvm/Analysis/TargetTransformInfo.h" 40 #include "llvm/IR/Constants.h" 41 #include "llvm/IR/DerivedTypes.h" 42 #include "llvm/IR/Dominators.h" 43 #include "llvm/IR/Function.h" 44 #include "llvm/IR/Instructions.h" 45 #include "llvm/IR/Module.h" 46 #include "llvm/Support/CommandLine.h" 47 #include "llvm/Support/Debug.h" 48 #include "llvm/Support/raw_ostream.h" 49 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 50 #include "llvm/Transforms/Utils/Cloning.h" 51 #include "llvm/Transforms/Utils/Local.h" 52 #include <algorithm> 53 #include <map> 54 #include <set> 55 using namespace llvm; 56 57 #define DEBUG_TYPE "loop-unswitch" 58 59 STATISTIC(NumBranches, "Number of branches unswitched"); 60 STATISTIC(NumSwitches, "Number of switches unswitched"); 61 STATISTIC(NumSelects , "Number of selects unswitched"); 62 STATISTIC(NumTrivial , "Number of unswitches that are trivial"); 63 STATISTIC(NumSimplify, "Number of simplifications of unswitched code"); 64 STATISTIC(TotalInsts, "Total number of instructions analyzed"); 65 66 // The specific value of 100 here was chosen based only on intuition and a 67 // few specific examples. 68 static cl::opt<unsigned> 69 Threshold("loop-unswitch-threshold", cl::desc("Max loop size to unswitch"), 70 cl::init(100), cl::Hidden); 71 72 namespace { 73 74 class LUAnalysisCache { 75 76 typedef DenseMap<const SwitchInst*, SmallPtrSet<const Value *, 8> > 77 UnswitchedValsMap; 78 79 typedef UnswitchedValsMap::iterator UnswitchedValsIt; 80 81 struct LoopProperties { 82 unsigned CanBeUnswitchedCount; 83 unsigned SizeEstimation; 84 UnswitchedValsMap UnswitchedVals; 85 }; 86 87 // Here we use std::map instead of DenseMap, since we need to keep valid 88 // LoopProperties pointer for current loop for better performance. 89 typedef std::map<const Loop*, LoopProperties> LoopPropsMap; 90 typedef LoopPropsMap::iterator LoopPropsMapIt; 91 92 LoopPropsMap LoopsProperties; 93 UnswitchedValsMap *CurLoopInstructions; 94 LoopProperties *CurrentLoopProperties; 95 96 // Max size of code we can produce on remained iterations. 97 unsigned MaxSize; 98 99 public: 100 101 LUAnalysisCache() : 102 CurLoopInstructions(nullptr), CurrentLoopProperties(nullptr), 103 MaxSize(Threshold) 104 {} 105 106 // Analyze loop. Check its size, calculate is it possible to unswitch 107 // it. Returns true if we can unswitch this loop. 108 bool countLoop(const Loop *L, const TargetTransformInfo &TTI, 109 AssumptionCache *AC); 110 111 // Clean all data related to given loop. 112 void forgetLoop(const Loop *L); 113 114 // Mark case value as unswitched. 115 // Since SI instruction can be partly unswitched, in order to avoid 116 // extra unswitching in cloned loops keep track all unswitched values. 117 void setUnswitched(const SwitchInst *SI, const Value *V); 118 119 // Check was this case value unswitched before or not. 120 bool isUnswitched(const SwitchInst *SI, const Value *V); 121 122 // Clone all loop-unswitch related loop properties. 123 // Redistribute unswitching quotas. 124 // Note, that new loop data is stored inside the VMap. 125 void cloneData(const Loop *NewLoop, const Loop *OldLoop, 126 const ValueToValueMapTy &VMap); 127 }; 128 129 class LoopUnswitch : public LoopPass { 130 LoopInfo *LI; // Loop information 131 LPPassManager *LPM; 132 AssumptionCache *AC; 133 134 // LoopProcessWorklist - Used to check if second loop needs processing 135 // after RewriteLoopBodyWithConditionConstant rewrites first loop. 136 std::vector<Loop*> LoopProcessWorklist; 137 138 LUAnalysisCache BranchesInfo; 139 140 bool OptimizeForSize; 141 bool redoLoop; 142 143 Loop *currentLoop; 144 DominatorTree *DT; 145 BasicBlock *loopHeader; 146 BasicBlock *loopPreheader; 147 148 // LoopBlocks contains all of the basic blocks of the loop, including the 149 // preheader of the loop, the body of the loop, and the exit blocks of the 150 // loop, in that order. 151 std::vector<BasicBlock*> LoopBlocks; 152 // NewBlocks contained cloned copy of basic blocks from LoopBlocks. 153 std::vector<BasicBlock*> NewBlocks; 154 155 public: 156 static char ID; // Pass ID, replacement for typeid 157 explicit LoopUnswitch(bool Os = false) : 158 LoopPass(ID), OptimizeForSize(Os), redoLoop(false), 159 currentLoop(nullptr), DT(nullptr), loopHeader(nullptr), 160 loopPreheader(nullptr) { 161 initializeLoopUnswitchPass(*PassRegistry::getPassRegistry()); 162 } 163 164 bool runOnLoop(Loop *L, LPPassManager &LPM) override; 165 bool processCurrentLoop(); 166 167 /// This transformation requires natural loop information & requires that 168 /// loop preheaders be inserted into the CFG. 169 /// 170 void getAnalysisUsage(AnalysisUsage &AU) const override { 171 AU.addRequired<AssumptionCacheTracker>(); 172 AU.addRequiredID(LoopSimplifyID); 173 AU.addPreservedID(LoopSimplifyID); 174 AU.addRequired<LoopInfoWrapperPass>(); 175 AU.addPreserved<LoopInfoWrapperPass>(); 176 AU.addRequiredID(LCSSAID); 177 AU.addPreservedID(LCSSAID); 178 AU.addPreserved<DominatorTreeWrapperPass>(); 179 AU.addPreserved<ScalarEvolution>(); 180 AU.addRequired<TargetTransformInfoWrapperPass>(); 181 } 182 183 private: 184 185 void releaseMemory() override { 186 BranchesInfo.forgetLoop(currentLoop); 187 } 188 189 void initLoopData() { 190 loopHeader = currentLoop->getHeader(); 191 loopPreheader = currentLoop->getLoopPreheader(); 192 } 193 194 /// Split all of the edges from inside the loop to their exit blocks. 195 /// Update the appropriate Phi nodes as we do so. 196 void SplitExitEdges(Loop *L, const SmallVectorImpl<BasicBlock *> &ExitBlocks); 197 198 bool UnswitchIfProfitable(Value *LoopCond, Constant *Val); 199 void UnswitchTrivialCondition(Loop *L, Value *Cond, Constant *Val, 200 BasicBlock *ExitBlock); 201 void UnswitchNontrivialCondition(Value *LIC, Constant *OnVal, Loop *L); 202 203 void RewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC, 204 Constant *Val, bool isEqual); 205 206 void EmitPreheaderBranchOnCondition(Value *LIC, Constant *Val, 207 BasicBlock *TrueDest, 208 BasicBlock *FalseDest, 209 Instruction *InsertPt); 210 211 void SimplifyCode(std::vector<Instruction*> &Worklist, Loop *L); 212 bool IsTrivialUnswitchCondition(Value *Cond, Constant **Val = nullptr, 213 BasicBlock **LoopExit = nullptr); 214 215 }; 216 } 217 218 // Analyze loop. Check its size, calculate is it possible to unswitch 219 // it. Returns true if we can unswitch this loop. 220 bool LUAnalysisCache::countLoop(const Loop *L, const TargetTransformInfo &TTI, 221 AssumptionCache *AC) { 222 223 LoopPropsMapIt PropsIt; 224 bool Inserted; 225 std::tie(PropsIt, Inserted) = 226 LoopsProperties.insert(std::make_pair(L, LoopProperties())); 227 228 LoopProperties &Props = PropsIt->second; 229 230 if (Inserted) { 231 // New loop. 232 233 // Limit the number of instructions to avoid causing significant code 234 // expansion, and the number of basic blocks, to avoid loops with 235 // large numbers of branches which cause loop unswitching to go crazy. 236 // This is a very ad-hoc heuristic. 237 238 SmallPtrSet<const Value *, 32> EphValues; 239 CodeMetrics::collectEphemeralValues(L, AC, EphValues); 240 241 // FIXME: This is overly conservative because it does not take into 242 // consideration code simplification opportunities and code that can 243 // be shared by the resultant unswitched loops. 244 CodeMetrics Metrics; 245 for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); 246 I != E; ++I) 247 Metrics.analyzeBasicBlock(*I, TTI, EphValues); 248 249 Props.SizeEstimation = std::min(Metrics.NumInsts, Metrics.NumBlocks * 5); 250 Props.CanBeUnswitchedCount = MaxSize / (Props.SizeEstimation); 251 MaxSize -= Props.SizeEstimation * Props.CanBeUnswitchedCount; 252 253 if (Metrics.notDuplicatable) { 254 DEBUG(dbgs() << "NOT unswitching loop %" 255 << L->getHeader()->getName() << ", contents cannot be " 256 << "duplicated!\n"); 257 return false; 258 } 259 } 260 261 if (!Props.CanBeUnswitchedCount) { 262 DEBUG(dbgs() << "NOT unswitching loop %" 263 << L->getHeader()->getName() << ", cost too high: " 264 << L->getBlocks().size() << "\n"); 265 return false; 266 } 267 268 // Be careful. This links are good only before new loop addition. 269 CurrentLoopProperties = &Props; 270 CurLoopInstructions = &Props.UnswitchedVals; 271 272 return true; 273 } 274 275 // Clean all data related to given loop. 276 void LUAnalysisCache::forgetLoop(const Loop *L) { 277 278 LoopPropsMapIt LIt = LoopsProperties.find(L); 279 280 if (LIt != LoopsProperties.end()) { 281 LoopProperties &Props = LIt->second; 282 MaxSize += Props.CanBeUnswitchedCount * Props.SizeEstimation; 283 LoopsProperties.erase(LIt); 284 } 285 286 CurrentLoopProperties = nullptr; 287 CurLoopInstructions = nullptr; 288 } 289 290 // Mark case value as unswitched. 291 // Since SI instruction can be partly unswitched, in order to avoid 292 // extra unswitching in cloned loops keep track all unswitched values. 293 void LUAnalysisCache::setUnswitched(const SwitchInst *SI, const Value *V) { 294 (*CurLoopInstructions)[SI].insert(V); 295 } 296 297 // Check was this case value unswitched before or not. 298 bool LUAnalysisCache::isUnswitched(const SwitchInst *SI, const Value *V) { 299 return (*CurLoopInstructions)[SI].count(V); 300 } 301 302 // Clone all loop-unswitch related loop properties. 303 // Redistribute unswitching quotas. 304 // Note, that new loop data is stored inside the VMap. 305 void LUAnalysisCache::cloneData(const Loop *NewLoop, const Loop *OldLoop, 306 const ValueToValueMapTy &VMap) { 307 308 LoopProperties &NewLoopProps = LoopsProperties[NewLoop]; 309 LoopProperties &OldLoopProps = *CurrentLoopProperties; 310 UnswitchedValsMap &Insts = OldLoopProps.UnswitchedVals; 311 312 // Reallocate "can-be-unswitched quota" 313 314 --OldLoopProps.CanBeUnswitchedCount; 315 unsigned Quota = OldLoopProps.CanBeUnswitchedCount; 316 NewLoopProps.CanBeUnswitchedCount = Quota / 2; 317 OldLoopProps.CanBeUnswitchedCount = Quota - Quota / 2; 318 319 NewLoopProps.SizeEstimation = OldLoopProps.SizeEstimation; 320 321 // Clone unswitched values info: 322 // for new loop switches we clone info about values that was 323 // already unswitched and has redundant successors. 324 for (UnswitchedValsIt I = Insts.begin(); I != Insts.end(); ++I) { 325 const SwitchInst *OldInst = I->first; 326 Value *NewI = VMap.lookup(OldInst); 327 const SwitchInst *NewInst = cast_or_null<SwitchInst>(NewI); 328 assert(NewInst && "All instructions that are in SrcBB must be in VMap."); 329 330 NewLoopProps.UnswitchedVals[NewInst] = OldLoopProps.UnswitchedVals[OldInst]; 331 } 332 } 333 334 char LoopUnswitch::ID = 0; 335 INITIALIZE_PASS_BEGIN(LoopUnswitch, "loop-unswitch", "Unswitch loops", 336 false, false) 337 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) 338 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) 339 INITIALIZE_PASS_DEPENDENCY(LoopSimplify) 340 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) 341 INITIALIZE_PASS_DEPENDENCY(LCSSA) 342 INITIALIZE_PASS_END(LoopUnswitch, "loop-unswitch", "Unswitch loops", 343 false, false) 344 345 Pass *llvm::createLoopUnswitchPass(bool Os) { 346 return new LoopUnswitch(Os); 347 } 348 349 /// FindLIVLoopCondition - Cond is a condition that occurs in L. If it is 350 /// invariant in the loop, or has an invariant piece, return the invariant. 351 /// Otherwise, return null. 352 static Value *FindLIVLoopCondition(Value *Cond, Loop *L, bool &Changed) { 353 354 // We started analyze new instruction, increment scanned instructions counter. 355 ++TotalInsts; 356 357 // We can never unswitch on vector conditions. 358 if (Cond->getType()->isVectorTy()) 359 return nullptr; 360 361 // Constants should be folded, not unswitched on! 362 if (isa<Constant>(Cond)) return nullptr; 363 364 // TODO: Handle: br (VARIANT|INVARIANT). 365 366 // Hoist simple values out. 367 if (L->makeLoopInvariant(Cond, Changed)) 368 return Cond; 369 370 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Cond)) 371 if (BO->getOpcode() == Instruction::And || 372 BO->getOpcode() == Instruction::Or) { 373 // If either the left or right side is invariant, we can unswitch on this, 374 // which will cause the branch to go away in one loop and the condition to 375 // simplify in the other one. 376 if (Value *LHS = FindLIVLoopCondition(BO->getOperand(0), L, Changed)) 377 return LHS; 378 if (Value *RHS = FindLIVLoopCondition(BO->getOperand(1), L, Changed)) 379 return RHS; 380 } 381 382 return nullptr; 383 } 384 385 bool LoopUnswitch::runOnLoop(Loop *L, LPPassManager &LPM_Ref) { 386 if (skipOptnoneFunction(L)) 387 return false; 388 389 AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache( 390 *L->getHeader()->getParent()); 391 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); 392 LPM = &LPM_Ref; 393 DominatorTreeWrapperPass *DTWP = 394 getAnalysisIfAvailable<DominatorTreeWrapperPass>(); 395 DT = DTWP ? &DTWP->getDomTree() : nullptr; 396 currentLoop = L; 397 Function *F = currentLoop->getHeader()->getParent(); 398 bool Changed = false; 399 do { 400 assert(currentLoop->isLCSSAForm(*DT)); 401 redoLoop = false; 402 Changed |= processCurrentLoop(); 403 } while(redoLoop); 404 405 if (Changed) { 406 // FIXME: Reconstruct dom info, because it is not preserved properly. 407 if (DT) 408 DT->recalculate(*F); 409 } 410 return Changed; 411 } 412 413 /// processCurrentLoop - Do actual work and unswitch loop if possible 414 /// and profitable. 415 bool LoopUnswitch::processCurrentLoop() { 416 bool Changed = false; 417 418 initLoopData(); 419 420 // If LoopSimplify was unable to form a preheader, don't do any unswitching. 421 if (!loopPreheader) 422 return false; 423 424 // Loops with indirectbr cannot be cloned. 425 if (!currentLoop->isSafeToClone()) 426 return false; 427 428 // Without dedicated exits, splitting the exit edge may fail. 429 if (!currentLoop->hasDedicatedExits()) 430 return false; 431 432 LLVMContext &Context = loopHeader->getContext(); 433 434 // Probably we reach the quota of branches for this loop. If so 435 // stop unswitching. 436 if (!BranchesInfo.countLoop( 437 currentLoop, getAnalysis<TargetTransformInfoWrapperPass>().getTTI( 438 *currentLoop->getHeader()->getParent()), 439 AC)) 440 return false; 441 442 // Loop over all of the basic blocks in the loop. If we find an interior 443 // block that is branching on a loop-invariant condition, we can unswitch this 444 // loop. 445 for (Loop::block_iterator I = currentLoop->block_begin(), 446 E = currentLoop->block_end(); I != E; ++I) { 447 TerminatorInst *TI = (*I)->getTerminator(); 448 if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { 449 // If this isn't branching on an invariant condition, we can't unswitch 450 // it. 451 if (BI->isConditional()) { 452 // See if this, or some part of it, is loop invariant. If so, we can 453 // unswitch on it if we desire. 454 Value *LoopCond = FindLIVLoopCondition(BI->getCondition(), 455 currentLoop, Changed); 456 if (LoopCond && UnswitchIfProfitable(LoopCond, 457 ConstantInt::getTrue(Context))) { 458 ++NumBranches; 459 return true; 460 } 461 } 462 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 463 Value *LoopCond = FindLIVLoopCondition(SI->getCondition(), 464 currentLoop, Changed); 465 unsigned NumCases = SI->getNumCases(); 466 if (LoopCond && NumCases) { 467 // Find a value to unswitch on: 468 // FIXME: this should chose the most expensive case! 469 // FIXME: scan for a case with a non-critical edge? 470 Constant *UnswitchVal = nullptr; 471 472 // Do not process same value again and again. 473 // At this point we have some cases already unswitched and 474 // some not yet unswitched. Let's find the first not yet unswitched one. 475 for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end(); 476 i != e; ++i) { 477 Constant *UnswitchValCandidate = i.getCaseValue(); 478 if (!BranchesInfo.isUnswitched(SI, UnswitchValCandidate)) { 479 UnswitchVal = UnswitchValCandidate; 480 break; 481 } 482 } 483 484 if (!UnswitchVal) 485 continue; 486 487 if (UnswitchIfProfitable(LoopCond, UnswitchVal)) { 488 ++NumSwitches; 489 return true; 490 } 491 } 492 } 493 494 // Scan the instructions to check for unswitchable values. 495 for (BasicBlock::iterator BBI = (*I)->begin(), E = (*I)->end(); 496 BBI != E; ++BBI) 497 if (SelectInst *SI = dyn_cast<SelectInst>(BBI)) { 498 Value *LoopCond = FindLIVLoopCondition(SI->getCondition(), 499 currentLoop, Changed); 500 if (LoopCond && UnswitchIfProfitable(LoopCond, 501 ConstantInt::getTrue(Context))) { 502 ++NumSelects; 503 return true; 504 } 505 } 506 } 507 return Changed; 508 } 509 510 /// isTrivialLoopExitBlock - Check to see if all paths from BB exit the 511 /// loop with no side effects (including infinite loops). 512 /// 513 /// If true, we return true and set ExitBB to the block we 514 /// exit through. 515 /// 516 static bool isTrivialLoopExitBlockHelper(Loop *L, BasicBlock *BB, 517 BasicBlock *&ExitBB, 518 std::set<BasicBlock*> &Visited) { 519 if (!Visited.insert(BB).second) { 520 // Already visited. Without more analysis, this could indicate an infinite 521 // loop. 522 return false; 523 } 524 if (!L->contains(BB)) { 525 // Otherwise, this is a loop exit, this is fine so long as this is the 526 // first exit. 527 if (ExitBB) return false; 528 ExitBB = BB; 529 return true; 530 } 531 532 // Otherwise, this is an unvisited intra-loop node. Check all successors. 533 for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI) { 534 // Check to see if the successor is a trivial loop exit. 535 if (!isTrivialLoopExitBlockHelper(L, *SI, ExitBB, Visited)) 536 return false; 537 } 538 539 // Okay, everything after this looks good, check to make sure that this block 540 // doesn't include any side effects. 541 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) 542 if (I->mayHaveSideEffects()) 543 return false; 544 545 return true; 546 } 547 548 /// isTrivialLoopExitBlock - Return true if the specified block unconditionally 549 /// leads to an exit from the specified loop, and has no side-effects in the 550 /// process. If so, return the block that is exited to, otherwise return null. 551 static BasicBlock *isTrivialLoopExitBlock(Loop *L, BasicBlock *BB) { 552 std::set<BasicBlock*> Visited; 553 Visited.insert(L->getHeader()); // Branches to header make infinite loops. 554 BasicBlock *ExitBB = nullptr; 555 if (isTrivialLoopExitBlockHelper(L, BB, ExitBB, Visited)) 556 return ExitBB; 557 return nullptr; 558 } 559 560 /// IsTrivialUnswitchCondition - Check to see if this unswitch condition is 561 /// trivial: that is, that the condition controls whether or not the loop does 562 /// anything at all. If this is a trivial condition, unswitching produces no 563 /// code duplications (equivalently, it produces a simpler loop and a new empty 564 /// loop, which gets deleted). 565 /// 566 /// If this is a trivial condition, return true, otherwise return false. When 567 /// returning true, this sets Cond and Val to the condition that controls the 568 /// trivial condition: when Cond dynamically equals Val, the loop is known to 569 /// exit. Finally, this sets LoopExit to the BB that the loop exits to when 570 /// Cond == Val. 571 /// 572 bool LoopUnswitch::IsTrivialUnswitchCondition(Value *Cond, Constant **Val, 573 BasicBlock **LoopExit) { 574 BasicBlock *Header = currentLoop->getHeader(); 575 TerminatorInst *HeaderTerm = Header->getTerminator(); 576 LLVMContext &Context = Header->getContext(); 577 578 BasicBlock *LoopExitBB = nullptr; 579 if (BranchInst *BI = dyn_cast<BranchInst>(HeaderTerm)) { 580 // If the header block doesn't end with a conditional branch on Cond, we 581 // can't handle it. 582 if (!BI->isConditional() || BI->getCondition() != Cond) 583 return false; 584 585 // Check to see if a successor of the branch is guaranteed to 586 // exit through a unique exit block without having any 587 // side-effects. If so, determine the value of Cond that causes it to do 588 // this. 589 if ((LoopExitBB = isTrivialLoopExitBlock(currentLoop, 590 BI->getSuccessor(0)))) { 591 if (Val) *Val = ConstantInt::getTrue(Context); 592 } else if ((LoopExitBB = isTrivialLoopExitBlock(currentLoop, 593 BI->getSuccessor(1)))) { 594 if (Val) *Val = ConstantInt::getFalse(Context); 595 } 596 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(HeaderTerm)) { 597 // If this isn't a switch on Cond, we can't handle it. 598 if (SI->getCondition() != Cond) return false; 599 600 // Check to see if a successor of the switch is guaranteed to go to the 601 // latch block or exit through a one exit block without having any 602 // side-effects. If so, determine the value of Cond that causes it to do 603 // this. 604 // Note that we can't trivially unswitch on the default case or 605 // on already unswitched cases. 606 for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end(); 607 i != e; ++i) { 608 BasicBlock *LoopExitCandidate; 609 if ((LoopExitCandidate = isTrivialLoopExitBlock(currentLoop, 610 i.getCaseSuccessor()))) { 611 // Okay, we found a trivial case, remember the value that is trivial. 612 ConstantInt *CaseVal = i.getCaseValue(); 613 614 // Check that it was not unswitched before, since already unswitched 615 // trivial vals are looks trivial too. 616 if (BranchesInfo.isUnswitched(SI, CaseVal)) 617 continue; 618 LoopExitBB = LoopExitCandidate; 619 if (Val) *Val = CaseVal; 620 break; 621 } 622 } 623 } 624 625 // If we didn't find a single unique LoopExit block, or if the loop exit block 626 // contains phi nodes, this isn't trivial. 627 if (!LoopExitBB || isa<PHINode>(LoopExitBB->begin())) 628 return false; // Can't handle this. 629 630 if (LoopExit) *LoopExit = LoopExitBB; 631 632 // We already know that nothing uses any scalar values defined inside of this 633 // loop. As such, we just have to check to see if this loop will execute any 634 // side-effecting instructions (e.g. stores, calls, volatile loads) in the 635 // part of the loop that the code *would* execute. We already checked the 636 // tail, check the header now. 637 for (BasicBlock::iterator I = Header->begin(), E = Header->end(); I != E; ++I) 638 if (I->mayHaveSideEffects()) 639 return false; 640 return true; 641 } 642 643 /// UnswitchIfProfitable - We have found that we can unswitch currentLoop when 644 /// LoopCond == Val to simplify the loop. If we decide that this is profitable, 645 /// unswitch the loop, reprocess the pieces, then return true. 646 bool LoopUnswitch::UnswitchIfProfitable(Value *LoopCond, Constant *Val) { 647 Function *F = loopHeader->getParent(); 648 Constant *CondVal = nullptr; 649 BasicBlock *ExitBlock = nullptr; 650 651 if (IsTrivialUnswitchCondition(LoopCond, &CondVal, &ExitBlock)) { 652 // If the condition is trivial, always unswitch. There is no code growth 653 // for this case. 654 UnswitchTrivialCondition(currentLoop, LoopCond, CondVal, ExitBlock); 655 return true; 656 } 657 658 // Check to see if it would be profitable to unswitch current loop. 659 660 // Do not do non-trivial unswitch while optimizing for size. 661 if (OptimizeForSize || F->hasFnAttribute(Attribute::OptimizeForSize)) 662 return false; 663 664 UnswitchNontrivialCondition(LoopCond, Val, currentLoop); 665 return true; 666 } 667 668 /// CloneLoop - Recursively clone the specified loop and all of its children, 669 /// mapping the blocks with the specified map. 670 static Loop *CloneLoop(Loop *L, Loop *PL, ValueToValueMapTy &VM, 671 LoopInfo *LI, LPPassManager *LPM) { 672 Loop *New = new Loop(); 673 LPM->insertLoop(New, PL); 674 675 // Add all of the blocks in L to the new loop. 676 for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); 677 I != E; ++I) 678 if (LI->getLoopFor(*I) == L) 679 New->addBasicBlockToLoop(cast<BasicBlock>(VM[*I]), *LI); 680 681 // Add all of the subloops to the new loop. 682 for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I) 683 CloneLoop(*I, New, VM, LI, LPM); 684 685 return New; 686 } 687 688 /// EmitPreheaderBranchOnCondition - Emit a conditional branch on two values 689 /// if LIC == Val, branch to TrueDst, otherwise branch to FalseDest. Insert the 690 /// code immediately before InsertPt. 691 void LoopUnswitch::EmitPreheaderBranchOnCondition(Value *LIC, Constant *Val, 692 BasicBlock *TrueDest, 693 BasicBlock *FalseDest, 694 Instruction *InsertPt) { 695 // Insert a conditional branch on LIC to the two preheaders. The original 696 // code is the true version and the new code is the false version. 697 Value *BranchVal = LIC; 698 if (!isa<ConstantInt>(Val) || 699 Val->getType() != Type::getInt1Ty(LIC->getContext())) 700 BranchVal = new ICmpInst(InsertPt, ICmpInst::ICMP_EQ, LIC, Val); 701 else if (Val != ConstantInt::getTrue(Val->getContext())) 702 // We want to enter the new loop when the condition is true. 703 std::swap(TrueDest, FalseDest); 704 705 // Insert the new branch. 706 BranchInst *BI = BranchInst::Create(TrueDest, FalseDest, BranchVal, InsertPt); 707 708 // If either edge is critical, split it. This helps preserve LoopSimplify 709 // form for enclosing loops. 710 auto Options = CriticalEdgeSplittingOptions(DT, LI).setPreserveLCSSA(); 711 SplitCriticalEdge(BI, 0, Options); 712 SplitCriticalEdge(BI, 1, Options); 713 } 714 715 /// UnswitchTrivialCondition - Given a loop that has a trivial unswitchable 716 /// condition in it (a cond branch from its header block to its latch block, 717 /// where the path through the loop that doesn't execute its body has no 718 /// side-effects), unswitch it. This doesn't involve any code duplication, just 719 /// moving the conditional branch outside of the loop and updating loop info. 720 void LoopUnswitch::UnswitchTrivialCondition(Loop *L, Value *Cond, 721 Constant *Val, 722 BasicBlock *ExitBlock) { 723 DEBUG(dbgs() << "loop-unswitch: Trivial-Unswitch loop %" 724 << loopHeader->getName() << " [" << L->getBlocks().size() 725 << " blocks] in Function " << L->getHeader()->getParent()->getName() 726 << " on cond: " << *Val << " == " << *Cond << "\n"); 727 728 // First step, split the preheader, so that we know that there is a safe place 729 // to insert the conditional branch. We will change loopPreheader to have a 730 // conditional branch on Cond. 731 BasicBlock *NewPH = SplitEdge(loopPreheader, loopHeader, DT, LI); 732 733 // Now that we have a place to insert the conditional branch, create a place 734 // to branch to: this is the exit block out of the loop that we should 735 // short-circuit to. 736 737 // Split this block now, so that the loop maintains its exit block, and so 738 // that the jump from the preheader can execute the contents of the exit block 739 // without actually branching to it (the exit block should be dominated by the 740 // loop header, not the preheader). 741 assert(!L->contains(ExitBlock) && "Exit block is in the loop?"); 742 BasicBlock *NewExit = SplitBlock(ExitBlock, ExitBlock->begin(), DT, LI); 743 744 // Okay, now we have a position to branch from and a position to branch to, 745 // insert the new conditional branch. 746 EmitPreheaderBranchOnCondition(Cond, Val, NewExit, NewPH, 747 loopPreheader->getTerminator()); 748 LPM->deleteSimpleAnalysisValue(loopPreheader->getTerminator(), L); 749 loopPreheader->getTerminator()->eraseFromParent(); 750 751 // We need to reprocess this loop, it could be unswitched again. 752 redoLoop = true; 753 754 // Now that we know that the loop is never entered when this condition is a 755 // particular value, rewrite the loop with this info. We know that this will 756 // at least eliminate the old branch. 757 RewriteLoopBodyWithConditionConstant(L, Cond, Val, false); 758 ++NumTrivial; 759 } 760 761 /// SplitExitEdges - Split all of the edges from inside the loop to their exit 762 /// blocks. Update the appropriate Phi nodes as we do so. 763 void LoopUnswitch::SplitExitEdges(Loop *L, 764 const SmallVectorImpl<BasicBlock *> &ExitBlocks){ 765 766 for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) { 767 BasicBlock *ExitBlock = ExitBlocks[i]; 768 SmallVector<BasicBlock *, 4> Preds(pred_begin(ExitBlock), 769 pred_end(ExitBlock)); 770 771 // Although SplitBlockPredecessors doesn't preserve loop-simplify in 772 // general, if we call it on all predecessors of all exits then it does. 773 SplitBlockPredecessors(ExitBlock, Preds, ".us-lcssa", 774 /*AliasAnalysis*/ nullptr, DT, LI, 775 /*PreserveLCSSA*/ true); 776 } 777 } 778 779 /// UnswitchNontrivialCondition - We determined that the loop is profitable 780 /// to unswitch when LIC equal Val. Split it into loop versions and test the 781 /// condition outside of either loop. Return the loops created as Out1/Out2. 782 void LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val, 783 Loop *L) { 784 Function *F = loopHeader->getParent(); 785 DEBUG(dbgs() << "loop-unswitch: Unswitching loop %" 786 << loopHeader->getName() << " [" << L->getBlocks().size() 787 << " blocks] in Function " << F->getName() 788 << " when '" << *Val << "' == " << *LIC << "\n"); 789 790 if (ScalarEvolution *SE = getAnalysisIfAvailable<ScalarEvolution>()) 791 SE->forgetLoop(L); 792 793 LoopBlocks.clear(); 794 NewBlocks.clear(); 795 796 // First step, split the preheader and exit blocks, and add these blocks to 797 // the LoopBlocks list. 798 BasicBlock *NewPreheader = SplitEdge(loopPreheader, loopHeader, DT, LI); 799 LoopBlocks.push_back(NewPreheader); 800 801 // We want the loop to come after the preheader, but before the exit blocks. 802 LoopBlocks.insert(LoopBlocks.end(), L->block_begin(), L->block_end()); 803 804 SmallVector<BasicBlock*, 8> ExitBlocks; 805 L->getUniqueExitBlocks(ExitBlocks); 806 807 // Split all of the edges from inside the loop to their exit blocks. Update 808 // the appropriate Phi nodes as we do so. 809 SplitExitEdges(L, ExitBlocks); 810 811 // The exit blocks may have been changed due to edge splitting, recompute. 812 ExitBlocks.clear(); 813 L->getUniqueExitBlocks(ExitBlocks); 814 815 // Add exit blocks to the loop blocks. 816 LoopBlocks.insert(LoopBlocks.end(), ExitBlocks.begin(), ExitBlocks.end()); 817 818 // Next step, clone all of the basic blocks that make up the loop (including 819 // the loop preheader and exit blocks), keeping track of the mapping between 820 // the instructions and blocks. 821 NewBlocks.reserve(LoopBlocks.size()); 822 ValueToValueMapTy VMap; 823 for (unsigned i = 0, e = LoopBlocks.size(); i != e; ++i) { 824 BasicBlock *NewBB = CloneBasicBlock(LoopBlocks[i], VMap, ".us", F); 825 826 NewBlocks.push_back(NewBB); 827 VMap[LoopBlocks[i]] = NewBB; // Keep the BB mapping. 828 LPM->cloneBasicBlockSimpleAnalysis(LoopBlocks[i], NewBB, L); 829 } 830 831 // Splice the newly inserted blocks into the function right before the 832 // original preheader. 833 F->getBasicBlockList().splice(NewPreheader, F->getBasicBlockList(), 834 NewBlocks[0], F->end()); 835 836 // FIXME: We could register any cloned assumptions instead of clearing the 837 // whole function's cache. 838 AC->clear(); 839 840 // Now we create the new Loop object for the versioned loop. 841 Loop *NewLoop = CloneLoop(L, L->getParentLoop(), VMap, LI, LPM); 842 843 // Recalculate unswitching quota, inherit simplified switches info for NewBB, 844 // Probably clone more loop-unswitch related loop properties. 845 BranchesInfo.cloneData(NewLoop, L, VMap); 846 847 Loop *ParentLoop = L->getParentLoop(); 848 if (ParentLoop) { 849 // Make sure to add the cloned preheader and exit blocks to the parent loop 850 // as well. 851 ParentLoop->addBasicBlockToLoop(NewBlocks[0], *LI); 852 } 853 854 for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) { 855 BasicBlock *NewExit = cast<BasicBlock>(VMap[ExitBlocks[i]]); 856 // The new exit block should be in the same loop as the old one. 857 if (Loop *ExitBBLoop = LI->getLoopFor(ExitBlocks[i])) 858 ExitBBLoop->addBasicBlockToLoop(NewExit, *LI); 859 860 assert(NewExit->getTerminator()->getNumSuccessors() == 1 && 861 "Exit block should have been split to have one successor!"); 862 BasicBlock *ExitSucc = NewExit->getTerminator()->getSuccessor(0); 863 864 // If the successor of the exit block had PHI nodes, add an entry for 865 // NewExit. 866 for (BasicBlock::iterator I = ExitSucc->begin(); 867 PHINode *PN = dyn_cast<PHINode>(I); ++I) { 868 Value *V = PN->getIncomingValueForBlock(ExitBlocks[i]); 869 ValueToValueMapTy::iterator It = VMap.find(V); 870 if (It != VMap.end()) V = It->second; 871 PN->addIncoming(V, NewExit); 872 } 873 874 if (LandingPadInst *LPad = NewExit->getLandingPadInst()) { 875 PHINode *PN = PHINode::Create(LPad->getType(), 0, "", 876 ExitSucc->getFirstInsertionPt()); 877 878 for (pred_iterator I = pred_begin(ExitSucc), E = pred_end(ExitSucc); 879 I != E; ++I) { 880 BasicBlock *BB = *I; 881 LandingPadInst *LPI = BB->getLandingPadInst(); 882 LPI->replaceAllUsesWith(PN); 883 PN->addIncoming(LPI, BB); 884 } 885 } 886 } 887 888 // Rewrite the code to refer to itself. 889 for (unsigned i = 0, e = NewBlocks.size(); i != e; ++i) 890 for (BasicBlock::iterator I = NewBlocks[i]->begin(), 891 E = NewBlocks[i]->end(); I != E; ++I) 892 RemapInstruction(I, VMap,RF_NoModuleLevelChanges|RF_IgnoreMissingEntries); 893 894 // Rewrite the original preheader to select between versions of the loop. 895 BranchInst *OldBR = cast<BranchInst>(loopPreheader->getTerminator()); 896 assert(OldBR->isUnconditional() && OldBR->getSuccessor(0) == LoopBlocks[0] && 897 "Preheader splitting did not work correctly!"); 898 899 // Emit the new branch that selects between the two versions of this loop. 900 EmitPreheaderBranchOnCondition(LIC, Val, NewBlocks[0], LoopBlocks[0], OldBR); 901 LPM->deleteSimpleAnalysisValue(OldBR, L); 902 OldBR->eraseFromParent(); 903 904 LoopProcessWorklist.push_back(NewLoop); 905 redoLoop = true; 906 907 // Keep a WeakVH holding onto LIC. If the first call to RewriteLoopBody 908 // deletes the instruction (for example by simplifying a PHI that feeds into 909 // the condition that we're unswitching on), we don't rewrite the second 910 // iteration. 911 WeakVH LICHandle(LIC); 912 913 // Now we rewrite the original code to know that the condition is true and the 914 // new code to know that the condition is false. 915 RewriteLoopBodyWithConditionConstant(L, LIC, Val, false); 916 917 // It's possible that simplifying one loop could cause the other to be 918 // changed to another value or a constant. If its a constant, don't simplify 919 // it. 920 if (!LoopProcessWorklist.empty() && LoopProcessWorklist.back() == NewLoop && 921 LICHandle && !isa<Constant>(LICHandle)) 922 RewriteLoopBodyWithConditionConstant(NewLoop, LICHandle, Val, true); 923 } 924 925 /// RemoveFromWorklist - Remove all instances of I from the worklist vector 926 /// specified. 927 static void RemoveFromWorklist(Instruction *I, 928 std::vector<Instruction*> &Worklist) { 929 930 Worklist.erase(std::remove(Worklist.begin(), Worklist.end(), I), 931 Worklist.end()); 932 } 933 934 /// ReplaceUsesOfWith - When we find that I really equals V, remove I from the 935 /// program, replacing all uses with V and update the worklist. 936 static void ReplaceUsesOfWith(Instruction *I, Value *V, 937 std::vector<Instruction*> &Worklist, 938 Loop *L, LPPassManager *LPM) { 939 DEBUG(dbgs() << "Replace with '" << *V << "': " << *I); 940 941 // Add uses to the worklist, which may be dead now. 942 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 943 if (Instruction *Use = dyn_cast<Instruction>(I->getOperand(i))) 944 Worklist.push_back(Use); 945 946 // Add users to the worklist which may be simplified now. 947 for (User *U : I->users()) 948 Worklist.push_back(cast<Instruction>(U)); 949 LPM->deleteSimpleAnalysisValue(I, L); 950 RemoveFromWorklist(I, Worklist); 951 I->replaceAllUsesWith(V); 952 I->eraseFromParent(); 953 ++NumSimplify; 954 } 955 956 // RewriteLoopBodyWithConditionConstant - We know either that the value LIC has 957 // the value specified by Val in the specified loop, or we know it does NOT have 958 // that value. Rewrite any uses of LIC or of properties correlated to it. 959 void LoopUnswitch::RewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC, 960 Constant *Val, 961 bool IsEqual) { 962 assert(!isa<Constant>(LIC) && "Why are we unswitching on a constant?"); 963 964 // FIXME: Support correlated properties, like: 965 // for (...) 966 // if (li1 < li2) 967 // ... 968 // if (li1 > li2) 969 // ... 970 971 // FOLD boolean conditions (X|LIC), (X&LIC). Fold conditional branches, 972 // selects, switches. 973 std::vector<Instruction*> Worklist; 974 LLVMContext &Context = Val->getContext(); 975 976 // If we know that LIC == Val, or that LIC == NotVal, just replace uses of LIC 977 // in the loop with the appropriate one directly. 978 if (IsEqual || (isa<ConstantInt>(Val) && 979 Val->getType()->isIntegerTy(1))) { 980 Value *Replacement; 981 if (IsEqual) 982 Replacement = Val; 983 else 984 Replacement = ConstantInt::get(Type::getInt1Ty(Val->getContext()), 985 !cast<ConstantInt>(Val)->getZExtValue()); 986 987 for (User *U : LIC->users()) { 988 Instruction *UI = dyn_cast<Instruction>(U); 989 if (!UI || !L->contains(UI)) 990 continue; 991 Worklist.push_back(UI); 992 } 993 994 for (std::vector<Instruction*>::iterator UI = Worklist.begin(), 995 UE = Worklist.end(); UI != UE; ++UI) 996 (*UI)->replaceUsesOfWith(LIC, Replacement); 997 998 SimplifyCode(Worklist, L); 999 return; 1000 } 1001 1002 // Otherwise, we don't know the precise value of LIC, but we do know that it 1003 // is certainly NOT "Val". As such, simplify any uses in the loop that we 1004 // can. This case occurs when we unswitch switch statements. 1005 for (User *U : LIC->users()) { 1006 Instruction *UI = dyn_cast<Instruction>(U); 1007 if (!UI || !L->contains(UI)) 1008 continue; 1009 1010 Worklist.push_back(UI); 1011 1012 // TODO: We could do other simplifications, for example, turning 1013 // 'icmp eq LIC, Val' -> false. 1014 1015 // If we know that LIC is not Val, use this info to simplify code. 1016 SwitchInst *SI = dyn_cast<SwitchInst>(UI); 1017 if (!SI || !isa<ConstantInt>(Val)) continue; 1018 1019 SwitchInst::CaseIt DeadCase = SI->findCaseValue(cast<ConstantInt>(Val)); 1020 // Default case is live for multiple values. 1021 if (DeadCase == SI->case_default()) continue; 1022 1023 // Found a dead case value. Don't remove PHI nodes in the 1024 // successor if they become single-entry, those PHI nodes may 1025 // be in the Users list. 1026 1027 BasicBlock *Switch = SI->getParent(); 1028 BasicBlock *SISucc = DeadCase.getCaseSuccessor(); 1029 BasicBlock *Latch = L->getLoopLatch(); 1030 1031 BranchesInfo.setUnswitched(SI, Val); 1032 1033 if (!SI->findCaseDest(SISucc)) continue; // Edge is critical. 1034 // If the DeadCase successor dominates the loop latch, then the 1035 // transformation isn't safe since it will delete the sole predecessor edge 1036 // to the latch. 1037 if (Latch && DT->dominates(SISucc, Latch)) 1038 continue; 1039 1040 // FIXME: This is a hack. We need to keep the successor around 1041 // and hooked up so as to preserve the loop structure, because 1042 // trying to update it is complicated. So instead we preserve the 1043 // loop structure and put the block on a dead code path. 1044 SplitEdge(Switch, SISucc, DT, LI); 1045 // Compute the successors instead of relying on the return value 1046 // of SplitEdge, since it may have split the switch successor 1047 // after PHI nodes. 1048 BasicBlock *NewSISucc = DeadCase.getCaseSuccessor(); 1049 BasicBlock *OldSISucc = *succ_begin(NewSISucc); 1050 // Create an "unreachable" destination. 1051 BasicBlock *Abort = BasicBlock::Create(Context, "us-unreachable", 1052 Switch->getParent(), 1053 OldSISucc); 1054 new UnreachableInst(Context, Abort); 1055 // Force the new case destination to branch to the "unreachable" 1056 // block while maintaining a (dead) CFG edge to the old block. 1057 NewSISucc->getTerminator()->eraseFromParent(); 1058 BranchInst::Create(Abort, OldSISucc, 1059 ConstantInt::getTrue(Context), NewSISucc); 1060 // Release the PHI operands for this edge. 1061 for (BasicBlock::iterator II = NewSISucc->begin(); 1062 PHINode *PN = dyn_cast<PHINode>(II); ++II) 1063 PN->setIncomingValue(PN->getBasicBlockIndex(Switch), 1064 UndefValue::get(PN->getType())); 1065 // Tell the domtree about the new block. We don't fully update the 1066 // domtree here -- instead we force it to do a full recomputation 1067 // after the pass is complete -- but we do need to inform it of 1068 // new blocks. 1069 if (DT) 1070 DT->addNewBlock(Abort, NewSISucc); 1071 } 1072 1073 SimplifyCode(Worklist, L); 1074 } 1075 1076 /// SimplifyCode - Okay, now that we have simplified some instructions in the 1077 /// loop, walk over it and constant prop, dce, and fold control flow where 1078 /// possible. Note that this is effectively a very simple loop-structure-aware 1079 /// optimizer. During processing of this loop, L could very well be deleted, so 1080 /// it must not be used. 1081 /// 1082 /// FIXME: When the loop optimizer is more mature, separate this out to a new 1083 /// pass. 1084 /// 1085 void LoopUnswitch::SimplifyCode(std::vector<Instruction*> &Worklist, Loop *L) { 1086 const DataLayout &DL = L->getHeader()->getModule()->getDataLayout(); 1087 while (!Worklist.empty()) { 1088 Instruction *I = Worklist.back(); 1089 Worklist.pop_back(); 1090 1091 // Simple DCE. 1092 if (isInstructionTriviallyDead(I)) { 1093 DEBUG(dbgs() << "Remove dead instruction '" << *I); 1094 1095 // Add uses to the worklist, which may be dead now. 1096 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 1097 if (Instruction *Use = dyn_cast<Instruction>(I->getOperand(i))) 1098 Worklist.push_back(Use); 1099 LPM->deleteSimpleAnalysisValue(I, L); 1100 RemoveFromWorklist(I, Worklist); 1101 I->eraseFromParent(); 1102 ++NumSimplify; 1103 continue; 1104 } 1105 1106 // See if instruction simplification can hack this up. This is common for 1107 // things like "select false, X, Y" after unswitching made the condition be 1108 // 'false'. TODO: update the domtree properly so we can pass it here. 1109 if (Value *V = SimplifyInstruction(I, DL)) 1110 if (LI->replacementPreservesLCSSAForm(I, V)) { 1111 ReplaceUsesOfWith(I, V, Worklist, L, LPM); 1112 continue; 1113 } 1114 1115 // Special case hacks that appear commonly in unswitched code. 1116 if (BranchInst *BI = dyn_cast<BranchInst>(I)) { 1117 if (BI->isUnconditional()) { 1118 // If BI's parent is the only pred of the successor, fold the two blocks 1119 // together. 1120 BasicBlock *Pred = BI->getParent(); 1121 BasicBlock *Succ = BI->getSuccessor(0); 1122 BasicBlock *SinglePred = Succ->getSinglePredecessor(); 1123 if (!SinglePred) continue; // Nothing to do. 1124 assert(SinglePred == Pred && "CFG broken"); 1125 1126 DEBUG(dbgs() << "Merging blocks: " << Pred->getName() << " <- " 1127 << Succ->getName() << "\n"); 1128 1129 // Resolve any single entry PHI nodes in Succ. 1130 while (PHINode *PN = dyn_cast<PHINode>(Succ->begin())) 1131 ReplaceUsesOfWith(PN, PN->getIncomingValue(0), Worklist, L, LPM); 1132 1133 // If Succ has any successors with PHI nodes, update them to have 1134 // entries coming from Pred instead of Succ. 1135 Succ->replaceAllUsesWith(Pred); 1136 1137 // Move all of the successor contents from Succ to Pred. 1138 Pred->getInstList().splice(BI, Succ->getInstList(), Succ->begin(), 1139 Succ->end()); 1140 LPM->deleteSimpleAnalysisValue(BI, L); 1141 BI->eraseFromParent(); 1142 RemoveFromWorklist(BI, Worklist); 1143 1144 // Remove Succ from the loop tree. 1145 LI->removeBlock(Succ); 1146 LPM->deleteSimpleAnalysisValue(Succ, L); 1147 Succ->eraseFromParent(); 1148 ++NumSimplify; 1149 continue; 1150 } 1151 1152 continue; 1153 } 1154 } 1155 } 1156