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