1 //===- LoopSimplify.cpp - Loop Canonicalization Pass ----------------------===// 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 performs several transformations to transform natural loops into a 11 // simpler form, which makes subsequent analyses and transformations simpler and 12 // more effective. 13 // 14 // Loop pre-header insertion guarantees that there is a single, non-critical 15 // entry edge from outside of the loop to the loop header. This simplifies a 16 // number of analyses and transformations, such as LICM. 17 // 18 // Loop exit-block insertion guarantees that all exit blocks from the loop 19 // (blocks which are outside of the loop that have predecessors inside of the 20 // loop) only have predecessors from inside of the loop (and are thus dominated 21 // by the loop header). This simplifies transformations such as store-sinking 22 // that are built into LICM. 23 // 24 // This pass also guarantees that loops will have exactly one backedge. 25 // 26 // Indirectbr instructions introduce several complications. If the loop 27 // contains or is entered by an indirectbr instruction, it may not be possible 28 // to transform the loop and make these guarantees. Client code should check 29 // that these conditions are true before relying on them. 30 // 31 // Note that the simplifycfg pass will clean up blocks which are split out but 32 // end up being unnecessary, so usage of this pass should not pessimize 33 // generated code. 34 // 35 // This pass obviously modifies the CFG, but updates loop information and 36 // dominator information. 37 // 38 //===----------------------------------------------------------------------===// 39 40 #include "llvm/Transforms/Utils/LoopSimplify.h" 41 #include "llvm/Transforms/Scalar.h" 42 #include "llvm/ADT/DepthFirstIterator.h" 43 #include "llvm/ADT/SetOperations.h" 44 #include "llvm/ADT/SetVector.h" 45 #include "llvm/ADT/SmallVector.h" 46 #include "llvm/ADT/Statistic.h" 47 #include "llvm/Analysis/AliasAnalysis.h" 48 #include "llvm/Analysis/BasicAliasAnalysis.h" 49 #include "llvm/Analysis/AssumptionCache.h" 50 #include "llvm/Analysis/DependenceAnalysis.h" 51 #include "llvm/Analysis/GlobalsModRef.h" 52 #include "llvm/Analysis/InstructionSimplify.h" 53 #include "llvm/Analysis/LoopInfo.h" 54 #include "llvm/Analysis/ScalarEvolution.h" 55 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h" 56 #include "llvm/IR/CFG.h" 57 #include "llvm/IR/Constants.h" 58 #include "llvm/IR/DataLayout.h" 59 #include "llvm/IR/Dominators.h" 60 #include "llvm/IR/Function.h" 61 #include "llvm/IR/Instructions.h" 62 #include "llvm/IR/IntrinsicInst.h" 63 #include "llvm/IR/LLVMContext.h" 64 #include "llvm/IR/Module.h" 65 #include "llvm/IR/Type.h" 66 #include "llvm/Support/Debug.h" 67 #include "llvm/Support/raw_ostream.h" 68 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 69 #include "llvm/Transforms/Utils/Local.h" 70 #include "llvm/Transforms/Utils/LoopUtils.h" 71 using namespace llvm; 72 73 #define DEBUG_TYPE "loop-simplify" 74 75 STATISTIC(NumInserted, "Number of pre-header or exit blocks inserted"); 76 STATISTIC(NumNested , "Number of nested loops split out"); 77 78 // If the block isn't already, move the new block to right after some 'outside 79 // block' block. This prevents the preheader from being placed inside the loop 80 // body, e.g. when the loop hasn't been rotated. 81 static void placeSplitBlockCarefully(BasicBlock *NewBB, 82 SmallVectorImpl<BasicBlock *> &SplitPreds, 83 Loop *L) { 84 // Check to see if NewBB is already well placed. 85 Function::iterator BBI = --NewBB->getIterator(); 86 for (unsigned i = 0, e = SplitPreds.size(); i != e; ++i) { 87 if (&*BBI == SplitPreds[i]) 88 return; 89 } 90 91 // If it isn't already after an outside block, move it after one. This is 92 // always good as it makes the uncond branch from the outside block into a 93 // fall-through. 94 95 // Figure out *which* outside block to put this after. Prefer an outside 96 // block that neighbors a BB actually in the loop. 97 BasicBlock *FoundBB = nullptr; 98 for (unsigned i = 0, e = SplitPreds.size(); i != e; ++i) { 99 Function::iterator BBI = SplitPreds[i]->getIterator(); 100 if (++BBI != NewBB->getParent()->end() && L->contains(&*BBI)) { 101 FoundBB = SplitPreds[i]; 102 break; 103 } 104 } 105 106 // If our heuristic for a *good* bb to place this after doesn't find 107 // anything, just pick something. It's likely better than leaving it within 108 // the loop. 109 if (!FoundBB) 110 FoundBB = SplitPreds[0]; 111 NewBB->moveAfter(FoundBB); 112 } 113 114 /// InsertPreheaderForLoop - Once we discover that a loop doesn't have a 115 /// preheader, this method is called to insert one. This method has two phases: 116 /// preheader insertion and analysis updating. 117 /// 118 BasicBlock *llvm::InsertPreheaderForLoop(Loop *L, DominatorTree *DT, 119 LoopInfo *LI, bool PreserveLCSSA) { 120 BasicBlock *Header = L->getHeader(); 121 122 // Compute the set of predecessors of the loop that are not in the loop. 123 SmallVector<BasicBlock*, 8> OutsideBlocks; 124 for (pred_iterator PI = pred_begin(Header), PE = pred_end(Header); 125 PI != PE; ++PI) { 126 BasicBlock *P = *PI; 127 if (!L->contains(P)) { // Coming in from outside the loop? 128 // If the loop is branched to from an indirect branch, we won't 129 // be able to fully transform the loop, because it prohibits 130 // edge splitting. 131 if (isa<IndirectBrInst>(P->getTerminator())) return nullptr; 132 133 // Keep track of it. 134 OutsideBlocks.push_back(P); 135 } 136 } 137 138 // Split out the loop pre-header. 139 BasicBlock *PreheaderBB; 140 PreheaderBB = SplitBlockPredecessors(Header, OutsideBlocks, ".preheader", DT, 141 LI, PreserveLCSSA); 142 if (!PreheaderBB) 143 return nullptr; 144 145 DEBUG(dbgs() << "LoopSimplify: Creating pre-header " 146 << PreheaderBB->getName() << "\n"); 147 148 // Make sure that NewBB is put someplace intelligent, which doesn't mess up 149 // code layout too horribly. 150 placeSplitBlockCarefully(PreheaderBB, OutsideBlocks, L); 151 152 return PreheaderBB; 153 } 154 155 /// \brief Ensure that the loop preheader dominates all exit blocks. 156 /// 157 /// This method is used to split exit blocks that have predecessors outside of 158 /// the loop. 159 static BasicBlock *rewriteLoopExitBlock(Loop *L, BasicBlock *Exit, 160 DominatorTree *DT, LoopInfo *LI, 161 bool PreserveLCSSA) { 162 SmallVector<BasicBlock*, 8> LoopBlocks; 163 for (pred_iterator I = pred_begin(Exit), E = pred_end(Exit); I != E; ++I) { 164 BasicBlock *P = *I; 165 if (L->contains(P)) { 166 // Don't do this if the loop is exited via an indirect branch. 167 if (isa<IndirectBrInst>(P->getTerminator())) return nullptr; 168 169 LoopBlocks.push_back(P); 170 } 171 } 172 173 assert(!LoopBlocks.empty() && "No edges coming in from outside the loop?"); 174 BasicBlock *NewExitBB = nullptr; 175 176 NewExitBB = SplitBlockPredecessors(Exit, LoopBlocks, ".loopexit", DT, LI, 177 PreserveLCSSA); 178 if (!NewExitBB) 179 return nullptr; 180 181 DEBUG(dbgs() << "LoopSimplify: Creating dedicated exit block " 182 << NewExitBB->getName() << "\n"); 183 return NewExitBB; 184 } 185 186 /// Add the specified block, and all of its predecessors, to the specified set, 187 /// if it's not already in there. Stop predecessor traversal when we reach 188 /// StopBlock. 189 static void addBlockAndPredsToSet(BasicBlock *InputBB, BasicBlock *StopBlock, 190 std::set<BasicBlock*> &Blocks) { 191 SmallVector<BasicBlock *, 8> Worklist; 192 Worklist.push_back(InputBB); 193 do { 194 BasicBlock *BB = Worklist.pop_back_val(); 195 if (Blocks.insert(BB).second && BB != StopBlock) 196 // If BB is not already processed and it is not a stop block then 197 // insert its predecessor in the work list 198 for (pred_iterator I = pred_begin(BB), E = pred_end(BB); I != E; ++I) { 199 BasicBlock *WBB = *I; 200 Worklist.push_back(WBB); 201 } 202 } while (!Worklist.empty()); 203 } 204 205 /// \brief The first part of loop-nestification is to find a PHI node that tells 206 /// us how to partition the loops. 207 static PHINode *findPHIToPartitionLoops(Loop *L, DominatorTree *DT, 208 AssumptionCache *AC) { 209 const DataLayout &DL = L->getHeader()->getModule()->getDataLayout(); 210 for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ) { 211 PHINode *PN = cast<PHINode>(I); 212 ++I; 213 if (Value *V = SimplifyInstruction(PN, DL, nullptr, DT, AC)) { 214 // This is a degenerate PHI already, don't modify it! 215 PN->replaceAllUsesWith(V); 216 PN->eraseFromParent(); 217 continue; 218 } 219 220 // Scan this PHI node looking for a use of the PHI node by itself. 221 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 222 if (PN->getIncomingValue(i) == PN && 223 L->contains(PN->getIncomingBlock(i))) 224 // We found something tasty to remove. 225 return PN; 226 } 227 return nullptr; 228 } 229 230 /// \brief If this loop has multiple backedges, try to pull one of them out into 231 /// a nested loop. 232 /// 233 /// This is important for code that looks like 234 /// this: 235 /// 236 /// Loop: 237 /// ... 238 /// br cond, Loop, Next 239 /// ... 240 /// br cond2, Loop, Out 241 /// 242 /// To identify this common case, we look at the PHI nodes in the header of the 243 /// loop. PHI nodes with unchanging values on one backedge correspond to values 244 /// that change in the "outer" loop, but not in the "inner" loop. 245 /// 246 /// If we are able to separate out a loop, return the new outer loop that was 247 /// created. 248 /// 249 static Loop *separateNestedLoop(Loop *L, BasicBlock *Preheader, 250 DominatorTree *DT, LoopInfo *LI, 251 ScalarEvolution *SE, bool PreserveLCSSA, 252 AssumptionCache *AC) { 253 // Don't try to separate loops without a preheader. 254 if (!Preheader) 255 return nullptr; 256 257 // The header is not a landing pad; preheader insertion should ensure this. 258 BasicBlock *Header = L->getHeader(); 259 assert(!Header->isEHPad() && "Can't insert backedge to EH pad"); 260 261 PHINode *PN = findPHIToPartitionLoops(L, DT, AC); 262 if (!PN) return nullptr; // No known way to partition. 263 264 // Pull out all predecessors that have varying values in the loop. This 265 // handles the case when a PHI node has multiple instances of itself as 266 // arguments. 267 SmallVector<BasicBlock*, 8> OuterLoopPreds; 268 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 269 if (PN->getIncomingValue(i) != PN || 270 !L->contains(PN->getIncomingBlock(i))) { 271 // We can't split indirectbr edges. 272 if (isa<IndirectBrInst>(PN->getIncomingBlock(i)->getTerminator())) 273 return nullptr; 274 OuterLoopPreds.push_back(PN->getIncomingBlock(i)); 275 } 276 } 277 DEBUG(dbgs() << "LoopSimplify: Splitting out a new outer loop\n"); 278 279 // If ScalarEvolution is around and knows anything about values in 280 // this loop, tell it to forget them, because we're about to 281 // substantially change it. 282 if (SE) 283 SE->forgetLoop(L); 284 285 BasicBlock *NewBB = SplitBlockPredecessors(Header, OuterLoopPreds, ".outer", 286 DT, LI, PreserveLCSSA); 287 288 // Make sure that NewBB is put someplace intelligent, which doesn't mess up 289 // code layout too horribly. 290 placeSplitBlockCarefully(NewBB, OuterLoopPreds, L); 291 292 // Create the new outer loop. 293 Loop *NewOuter = new Loop(); 294 295 // Change the parent loop to use the outer loop as its child now. 296 if (Loop *Parent = L->getParentLoop()) 297 Parent->replaceChildLoopWith(L, NewOuter); 298 else 299 LI->changeTopLevelLoop(L, NewOuter); 300 301 // L is now a subloop of our outer loop. 302 NewOuter->addChildLoop(L); 303 304 for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); 305 I != E; ++I) 306 NewOuter->addBlockEntry(*I); 307 308 // Now reset the header in L, which had been moved by 309 // SplitBlockPredecessors for the outer loop. 310 L->moveToHeader(Header); 311 312 // Determine which blocks should stay in L and which should be moved out to 313 // the Outer loop now. 314 std::set<BasicBlock*> BlocksInL; 315 for (pred_iterator PI=pred_begin(Header), E = pred_end(Header); PI!=E; ++PI) { 316 BasicBlock *P = *PI; 317 if (DT->dominates(Header, P)) 318 addBlockAndPredsToSet(P, Header, BlocksInL); 319 } 320 321 // Scan all of the loop children of L, moving them to OuterLoop if they are 322 // not part of the inner loop. 323 const std::vector<Loop*> &SubLoops = L->getSubLoops(); 324 for (size_t I = 0; I != SubLoops.size(); ) 325 if (BlocksInL.count(SubLoops[I]->getHeader())) 326 ++I; // Loop remains in L 327 else 328 NewOuter->addChildLoop(L->removeChildLoop(SubLoops.begin() + I)); 329 330 // Now that we know which blocks are in L and which need to be moved to 331 // OuterLoop, move any blocks that need it. 332 for (unsigned i = 0; i != L->getBlocks().size(); ++i) { 333 BasicBlock *BB = L->getBlocks()[i]; 334 if (!BlocksInL.count(BB)) { 335 // Move this block to the parent, updating the exit blocks sets 336 L->removeBlockFromLoop(BB); 337 if ((*LI)[BB] == L) 338 LI->changeLoopFor(BB, NewOuter); 339 --i; 340 } 341 } 342 343 return NewOuter; 344 } 345 346 /// \brief This method is called when the specified loop has more than one 347 /// backedge in it. 348 /// 349 /// If this occurs, revector all of these backedges to target a new basic block 350 /// and have that block branch to the loop header. This ensures that loops 351 /// have exactly one backedge. 352 static BasicBlock *insertUniqueBackedgeBlock(Loop *L, BasicBlock *Preheader, 353 DominatorTree *DT, LoopInfo *LI) { 354 assert(L->getNumBackEdges() > 1 && "Must have > 1 backedge!"); 355 356 // Get information about the loop 357 BasicBlock *Header = L->getHeader(); 358 Function *F = Header->getParent(); 359 360 // Unique backedge insertion currently depends on having a preheader. 361 if (!Preheader) 362 return nullptr; 363 364 // The header is not an EH pad; preheader insertion should ensure this. 365 assert(!Header->isEHPad() && "Can't insert backedge to EH pad"); 366 367 // Figure out which basic blocks contain back-edges to the loop header. 368 std::vector<BasicBlock*> BackedgeBlocks; 369 for (pred_iterator I = pred_begin(Header), E = pred_end(Header); I != E; ++I){ 370 BasicBlock *P = *I; 371 372 // Indirectbr edges cannot be split, so we must fail if we find one. 373 if (isa<IndirectBrInst>(P->getTerminator())) 374 return nullptr; 375 376 if (P != Preheader) BackedgeBlocks.push_back(P); 377 } 378 379 // Create and insert the new backedge block... 380 BasicBlock *BEBlock = BasicBlock::Create(Header->getContext(), 381 Header->getName() + ".backedge", F); 382 BranchInst *BETerminator = BranchInst::Create(Header, BEBlock); 383 BETerminator->setDebugLoc(Header->getFirstNonPHI()->getDebugLoc()); 384 385 DEBUG(dbgs() << "LoopSimplify: Inserting unique backedge block " 386 << BEBlock->getName() << "\n"); 387 388 // Move the new backedge block to right after the last backedge block. 389 Function::iterator InsertPos = ++BackedgeBlocks.back()->getIterator(); 390 F->getBasicBlockList().splice(InsertPos, F->getBasicBlockList(), BEBlock); 391 392 // Now that the block has been inserted into the function, create PHI nodes in 393 // the backedge block which correspond to any PHI nodes in the header block. 394 for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) { 395 PHINode *PN = cast<PHINode>(I); 396 PHINode *NewPN = PHINode::Create(PN->getType(), BackedgeBlocks.size(), 397 PN->getName()+".be", BETerminator); 398 399 // Loop over the PHI node, moving all entries except the one for the 400 // preheader over to the new PHI node. 401 unsigned PreheaderIdx = ~0U; 402 bool HasUniqueIncomingValue = true; 403 Value *UniqueValue = nullptr; 404 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 405 BasicBlock *IBB = PN->getIncomingBlock(i); 406 Value *IV = PN->getIncomingValue(i); 407 if (IBB == Preheader) { 408 PreheaderIdx = i; 409 } else { 410 NewPN->addIncoming(IV, IBB); 411 if (HasUniqueIncomingValue) { 412 if (!UniqueValue) 413 UniqueValue = IV; 414 else if (UniqueValue != IV) 415 HasUniqueIncomingValue = false; 416 } 417 } 418 } 419 420 // Delete all of the incoming values from the old PN except the preheader's 421 assert(PreheaderIdx != ~0U && "PHI has no preheader entry??"); 422 if (PreheaderIdx != 0) { 423 PN->setIncomingValue(0, PN->getIncomingValue(PreheaderIdx)); 424 PN->setIncomingBlock(0, PN->getIncomingBlock(PreheaderIdx)); 425 } 426 // Nuke all entries except the zero'th. 427 for (unsigned i = 0, e = PN->getNumIncomingValues()-1; i != e; ++i) 428 PN->removeIncomingValue(e-i, false); 429 430 // Finally, add the newly constructed PHI node as the entry for the BEBlock. 431 PN->addIncoming(NewPN, BEBlock); 432 433 // As an optimization, if all incoming values in the new PhiNode (which is a 434 // subset of the incoming values of the old PHI node) have the same value, 435 // eliminate the PHI Node. 436 if (HasUniqueIncomingValue) { 437 NewPN->replaceAllUsesWith(UniqueValue); 438 BEBlock->getInstList().erase(NewPN); 439 } 440 } 441 442 // Now that all of the PHI nodes have been inserted and adjusted, modify the 443 // backedge blocks to just to the BEBlock instead of the header. 444 for (unsigned i = 0, e = BackedgeBlocks.size(); i != e; ++i) { 445 TerminatorInst *TI = BackedgeBlocks[i]->getTerminator(); 446 for (unsigned Op = 0, e = TI->getNumSuccessors(); Op != e; ++Op) 447 if (TI->getSuccessor(Op) == Header) 448 TI->setSuccessor(Op, BEBlock); 449 } 450 451 //===--- Update all analyses which we must preserve now -----------------===// 452 453 // Update Loop Information - we know that this block is now in the current 454 // loop and all parent loops. 455 L->addBasicBlockToLoop(BEBlock, *LI); 456 457 // Update dominator information 458 DT->splitBlock(BEBlock); 459 460 return BEBlock; 461 } 462 463 /// \brief Simplify one loop and queue further loops for simplification. 464 static bool simplifyOneLoop(Loop *L, SmallVectorImpl<Loop *> &Worklist, 465 DominatorTree *DT, LoopInfo *LI, 466 ScalarEvolution *SE, AssumptionCache *AC, 467 bool PreserveLCSSA) { 468 bool Changed = false; 469 ReprocessLoop: 470 471 // Check to see that no blocks (other than the header) in this loop have 472 // predecessors that are not in the loop. This is not valid for natural 473 // loops, but can occur if the blocks are unreachable. Since they are 474 // unreachable we can just shamelessly delete those CFG edges! 475 for (Loop::block_iterator BB = L->block_begin(), E = L->block_end(); 476 BB != E; ++BB) { 477 if (*BB == L->getHeader()) continue; 478 479 SmallPtrSet<BasicBlock*, 4> BadPreds; 480 for (pred_iterator PI = pred_begin(*BB), 481 PE = pred_end(*BB); PI != PE; ++PI) { 482 BasicBlock *P = *PI; 483 if (!L->contains(P)) 484 BadPreds.insert(P); 485 } 486 487 // Delete each unique out-of-loop (and thus dead) predecessor. 488 for (BasicBlock *P : BadPreds) { 489 490 DEBUG(dbgs() << "LoopSimplify: Deleting edge from dead predecessor " 491 << P->getName() << "\n"); 492 493 // Zap the dead pred's terminator and replace it with unreachable. 494 TerminatorInst *TI = P->getTerminator(); 495 changeToUnreachable(TI, /*UseLLVMTrap=*/false); 496 Changed = true; 497 } 498 } 499 500 // If there are exiting blocks with branches on undef, resolve the undef in 501 // the direction which will exit the loop. This will help simplify loop 502 // trip count computations. 503 SmallVector<BasicBlock*, 8> ExitingBlocks; 504 L->getExitingBlocks(ExitingBlocks); 505 for (BasicBlock *ExitingBlock : ExitingBlocks) 506 if (BranchInst *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator())) 507 if (BI->isConditional()) { 508 if (UndefValue *Cond = dyn_cast<UndefValue>(BI->getCondition())) { 509 510 DEBUG(dbgs() << "LoopSimplify: Resolving \"br i1 undef\" to exit in " 511 << ExitingBlock->getName() << "\n"); 512 513 BI->setCondition(ConstantInt::get(Cond->getType(), 514 !L->contains(BI->getSuccessor(0)))); 515 516 // This may make the loop analyzable, force SCEV recomputation. 517 if (SE) 518 SE->forgetLoop(L); 519 520 Changed = true; 521 } 522 } 523 524 // Does the loop already have a preheader? If so, don't insert one. 525 BasicBlock *Preheader = L->getLoopPreheader(); 526 if (!Preheader) { 527 Preheader = InsertPreheaderForLoop(L, DT, LI, PreserveLCSSA); 528 if (Preheader) { 529 ++NumInserted; 530 Changed = true; 531 } 532 } 533 534 // Next, check to make sure that all exit nodes of the loop only have 535 // predecessors that are inside of the loop. This check guarantees that the 536 // loop preheader/header will dominate the exit blocks. If the exit block has 537 // predecessors from outside of the loop, split the edge now. 538 SmallVector<BasicBlock*, 8> ExitBlocks; 539 L->getExitBlocks(ExitBlocks); 540 541 SmallSetVector<BasicBlock *, 8> ExitBlockSet(ExitBlocks.begin(), 542 ExitBlocks.end()); 543 for (BasicBlock *ExitBlock : ExitBlockSet) { 544 for (pred_iterator PI = pred_begin(ExitBlock), PE = pred_end(ExitBlock); 545 PI != PE; ++PI) 546 // Must be exactly this loop: no subloops, parent loops, or non-loop preds 547 // allowed. 548 if (!L->contains(*PI)) { 549 if (rewriteLoopExitBlock(L, ExitBlock, DT, LI, PreserveLCSSA)) { 550 ++NumInserted; 551 Changed = true; 552 } 553 break; 554 } 555 } 556 557 // If the header has more than two predecessors at this point (from the 558 // preheader and from multiple backedges), we must adjust the loop. 559 BasicBlock *LoopLatch = L->getLoopLatch(); 560 if (!LoopLatch) { 561 // If this is really a nested loop, rip it out into a child loop. Don't do 562 // this for loops with a giant number of backedges, just factor them into a 563 // common backedge instead. 564 if (L->getNumBackEdges() < 8) { 565 if (Loop *OuterL = 566 separateNestedLoop(L, Preheader, DT, LI, SE, PreserveLCSSA, AC)) { 567 ++NumNested; 568 // Enqueue the outer loop as it should be processed next in our 569 // depth-first nest walk. 570 Worklist.push_back(OuterL); 571 572 // This is a big restructuring change, reprocess the whole loop. 573 Changed = true; 574 // GCC doesn't tail recursion eliminate this. 575 // FIXME: It isn't clear we can't rely on LLVM to TRE this. 576 goto ReprocessLoop; 577 } 578 } 579 580 // If we either couldn't, or didn't want to, identify nesting of the loops, 581 // insert a new block that all backedges target, then make it jump to the 582 // loop header. 583 LoopLatch = insertUniqueBackedgeBlock(L, Preheader, DT, LI); 584 if (LoopLatch) { 585 ++NumInserted; 586 Changed = true; 587 } 588 } 589 590 const DataLayout &DL = L->getHeader()->getModule()->getDataLayout(); 591 592 // Scan over the PHI nodes in the loop header. Since they now have only two 593 // incoming values (the loop is canonicalized), we may have simplified the PHI 594 // down to 'X = phi [X, Y]', which should be replaced with 'Y'. 595 PHINode *PN; 596 for (BasicBlock::iterator I = L->getHeader()->begin(); 597 (PN = dyn_cast<PHINode>(I++)); ) 598 if (Value *V = SimplifyInstruction(PN, DL, nullptr, DT, AC)) { 599 if (SE) SE->forgetValue(PN); 600 PN->replaceAllUsesWith(V); 601 PN->eraseFromParent(); 602 } 603 604 // If this loop has multiple exits and the exits all go to the same 605 // block, attempt to merge the exits. This helps several passes, such 606 // as LoopRotation, which do not support loops with multiple exits. 607 // SimplifyCFG also does this (and this code uses the same utility 608 // function), however this code is loop-aware, where SimplifyCFG is 609 // not. That gives it the advantage of being able to hoist 610 // loop-invariant instructions out of the way to open up more 611 // opportunities, and the disadvantage of having the responsibility 612 // to preserve dominator information. 613 bool UniqueExit = true; 614 if (!ExitBlocks.empty()) 615 for (unsigned i = 1, e = ExitBlocks.size(); i != e; ++i) 616 if (ExitBlocks[i] != ExitBlocks[0]) { 617 UniqueExit = false; 618 break; 619 } 620 if (UniqueExit) { 621 for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) { 622 BasicBlock *ExitingBlock = ExitingBlocks[i]; 623 if (!ExitingBlock->getSinglePredecessor()) continue; 624 BranchInst *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator()); 625 if (!BI || !BI->isConditional()) continue; 626 CmpInst *CI = dyn_cast<CmpInst>(BI->getCondition()); 627 if (!CI || CI->getParent() != ExitingBlock) continue; 628 629 // Attempt to hoist out all instructions except for the 630 // comparison and the branch. 631 bool AllInvariant = true; 632 bool AnyInvariant = false; 633 for (BasicBlock::iterator I = ExitingBlock->begin(); &*I != BI; ) { 634 Instruction *Inst = &*I++; 635 // Skip debug info intrinsics. 636 if (isa<DbgInfoIntrinsic>(Inst)) 637 continue; 638 if (Inst == CI) 639 continue; 640 if (!L->makeLoopInvariant(Inst, AnyInvariant, 641 Preheader ? Preheader->getTerminator() 642 : nullptr)) { 643 AllInvariant = false; 644 break; 645 } 646 } 647 if (AnyInvariant) { 648 Changed = true; 649 // The loop disposition of all SCEV expressions that depend on any 650 // hoisted values have also changed. 651 if (SE) 652 SE->forgetLoopDispositions(L); 653 } 654 if (!AllInvariant) continue; 655 656 // The block has now been cleared of all instructions except for 657 // a comparison and a conditional branch. SimplifyCFG may be able 658 // to fold it now. 659 if (!FoldBranchToCommonDest(BI)) 660 continue; 661 662 // Success. The block is now dead, so remove it from the loop, 663 // update the dominator tree and delete it. 664 DEBUG(dbgs() << "LoopSimplify: Eliminating exiting block " 665 << ExitingBlock->getName() << "\n"); 666 667 // Notify ScalarEvolution before deleting this block. Currently assume the 668 // parent loop doesn't change (spliting edges doesn't count). If blocks, 669 // CFG edges, or other values in the parent loop change, then we need call 670 // to forgetLoop() for the parent instead. 671 if (SE) 672 SE->forgetLoop(L); 673 674 assert(pred_begin(ExitingBlock) == pred_end(ExitingBlock)); 675 Changed = true; 676 LI->removeBlock(ExitingBlock); 677 678 DomTreeNode *Node = DT->getNode(ExitingBlock); 679 const std::vector<DomTreeNodeBase<BasicBlock> *> &Children = 680 Node->getChildren(); 681 while (!Children.empty()) { 682 DomTreeNode *Child = Children.front(); 683 DT->changeImmediateDominator(Child, Node->getIDom()); 684 } 685 DT->eraseNode(ExitingBlock); 686 687 BI->getSuccessor(0)->removePredecessor( 688 ExitingBlock, /* DontDeleteUselessPHIs */ PreserveLCSSA); 689 BI->getSuccessor(1)->removePredecessor( 690 ExitingBlock, /* DontDeleteUselessPHIs */ PreserveLCSSA); 691 ExitingBlock->eraseFromParent(); 692 } 693 } 694 695 return Changed; 696 } 697 698 bool llvm::simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, 699 ScalarEvolution *SE, AssumptionCache *AC, 700 bool PreserveLCSSA) { 701 bool Changed = false; 702 703 // Worklist maintains our depth-first queue of loops in this nest to process. 704 SmallVector<Loop *, 4> Worklist; 705 Worklist.push_back(L); 706 707 // Walk the worklist from front to back, pushing newly found sub loops onto 708 // the back. This will let us process loops from back to front in depth-first 709 // order. We can use this simple process because loops form a tree. 710 for (unsigned Idx = 0; Idx != Worklist.size(); ++Idx) { 711 Loop *L2 = Worklist[Idx]; 712 Worklist.append(L2->begin(), L2->end()); 713 } 714 715 while (!Worklist.empty()) 716 Changed |= simplifyOneLoop(Worklist.pop_back_val(), Worklist, DT, LI, SE, 717 AC, PreserveLCSSA); 718 719 return Changed; 720 } 721 722 namespace { 723 struct LoopSimplify : public FunctionPass { 724 static char ID; // Pass identification, replacement for typeid 725 LoopSimplify() : FunctionPass(ID) { 726 initializeLoopSimplifyPass(*PassRegistry::getPassRegistry()); 727 } 728 729 bool runOnFunction(Function &F) override; 730 731 void getAnalysisUsage(AnalysisUsage &AU) const override { 732 AU.addRequired<AssumptionCacheTracker>(); 733 734 // We need loop information to identify the loops... 735 AU.addRequired<DominatorTreeWrapperPass>(); 736 AU.addPreserved<DominatorTreeWrapperPass>(); 737 738 AU.addRequired<LoopInfoWrapperPass>(); 739 AU.addPreserved<LoopInfoWrapperPass>(); 740 741 AU.addPreserved<BasicAAWrapperPass>(); 742 AU.addPreserved<AAResultsWrapperPass>(); 743 AU.addPreserved<GlobalsAAWrapperPass>(); 744 AU.addPreserved<ScalarEvolutionWrapperPass>(); 745 AU.addPreserved<SCEVAAWrapperPass>(); 746 AU.addPreservedID(LCSSAID); 747 AU.addPreserved<DependenceAnalysisWrapperPass>(); 748 AU.addPreservedID(BreakCriticalEdgesID); // No critical edges added. 749 } 750 751 /// verifyAnalysis() - Verify LoopSimplifyForm's guarantees. 752 void verifyAnalysis() const override; 753 }; 754 } 755 756 char LoopSimplify::ID = 0; 757 INITIALIZE_PASS_BEGIN(LoopSimplify, "loop-simplify", 758 "Canonicalize natural loops", false, false) 759 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) 760 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 761 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) 762 INITIALIZE_PASS_END(LoopSimplify, "loop-simplify", 763 "Canonicalize natural loops", false, false) 764 765 // Publicly exposed interface to pass... 766 char &llvm::LoopSimplifyID = LoopSimplify::ID; 767 Pass *llvm::createLoopSimplifyPass() { return new LoopSimplify(); } 768 769 /// runOnFunction - Run down all loops in the CFG (recursively, but we could do 770 /// it in any convenient order) inserting preheaders... 771 /// 772 bool LoopSimplify::runOnFunction(Function &F) { 773 bool Changed = false; 774 LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); 775 DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 776 auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>(); 777 ScalarEvolution *SE = SEWP ? &SEWP->getSE() : nullptr; 778 AssumptionCache *AC = 779 &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F); 780 781 bool PreserveLCSSA = mustPreserveAnalysisID(LCSSAID); 782 #ifndef NDEBUG 783 if (PreserveLCSSA) { 784 assert(DT && "DT not available."); 785 assert(LI && "LI not available."); 786 bool InLCSSA = 787 all_of(*LI, [&](Loop *L) { return L->isRecursivelyLCSSAForm(*DT); }); 788 assert(InLCSSA && "Requested to preserve LCSSA, but it's already broken."); 789 } 790 #endif 791 792 // Simplify each loop nest in the function. 793 for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) 794 Changed |= simplifyLoop(*I, DT, LI, SE, AC, PreserveLCSSA); 795 796 #ifndef NDEBUG 797 if (PreserveLCSSA) { 798 bool InLCSSA = 799 all_of(*LI, [&](Loop *L) { return L->isRecursivelyLCSSAForm(*DT); }); 800 assert(InLCSSA && "LCSSA is broken after loop-simplify."); 801 } 802 #endif 803 return Changed; 804 } 805 806 PreservedAnalyses LoopSimplifyPass::run(Function &F, 807 AnalysisManager<Function> &AM) { 808 bool Changed = false; 809 LoopInfo *LI = &AM.getResult<LoopAnalysis>(F); 810 DominatorTree *DT = &AM.getResult<DominatorTreeAnalysis>(F); 811 ScalarEvolution *SE = AM.getCachedResult<ScalarEvolutionAnalysis>(F); 812 AssumptionCache *AC = &AM.getResult<AssumptionAnalysis>(F); 813 814 // FIXME: This pass should verify that the loops on which it's operating 815 // are in canonical SSA form, and that the pass itself preserves this form. 816 for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) 817 Changed |= simplifyLoop(*I, DT, LI, SE, AC, true /* PreserveLCSSA */); 818 819 if (!Changed) 820 return PreservedAnalyses::all(); 821 PreservedAnalyses PA; 822 PA.preserve<DominatorTreeAnalysis>(); 823 PA.preserve<LoopAnalysis>(); 824 PA.preserve<BasicAA>(); 825 PA.preserve<GlobalsAA>(); 826 PA.preserve<SCEVAA>(); 827 PA.preserve<ScalarEvolutionAnalysis>(); 828 PA.preserve<DependenceAnalysis>(); 829 return PA; 830 } 831 832 // FIXME: Restore this code when we re-enable verification in verifyAnalysis 833 // below. 834 #if 0 835 static void verifyLoop(Loop *L) { 836 // Verify subloops. 837 for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I) 838 verifyLoop(*I); 839 840 // It used to be possible to just assert L->isLoopSimplifyForm(), however 841 // with the introduction of indirectbr, there are now cases where it's 842 // not possible to transform a loop as necessary. We can at least check 843 // that there is an indirectbr near any time there's trouble. 844 845 // Indirectbr can interfere with preheader and unique backedge insertion. 846 if (!L->getLoopPreheader() || !L->getLoopLatch()) { 847 bool HasIndBrPred = false; 848 for (pred_iterator PI = pred_begin(L->getHeader()), 849 PE = pred_end(L->getHeader()); PI != PE; ++PI) 850 if (isa<IndirectBrInst>((*PI)->getTerminator())) { 851 HasIndBrPred = true; 852 break; 853 } 854 assert(HasIndBrPred && 855 "LoopSimplify has no excuse for missing loop header info!"); 856 (void)HasIndBrPred; 857 } 858 859 // Indirectbr can interfere with exit block canonicalization. 860 if (!L->hasDedicatedExits()) { 861 bool HasIndBrExiting = false; 862 SmallVector<BasicBlock*, 8> ExitingBlocks; 863 L->getExitingBlocks(ExitingBlocks); 864 for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) { 865 if (isa<IndirectBrInst>((ExitingBlocks[i])->getTerminator())) { 866 HasIndBrExiting = true; 867 break; 868 } 869 } 870 871 assert(HasIndBrExiting && 872 "LoopSimplify has no excuse for missing exit block info!"); 873 (void)HasIndBrExiting; 874 } 875 } 876 #endif 877 878 void LoopSimplify::verifyAnalysis() const { 879 // FIXME: This routine is being called mid-way through the loop pass manager 880 // as loop passes destroy this analysis. That's actually fine, but we have no 881 // way of expressing that here. Once all of the passes that destroy this are 882 // hoisted out of the loop pass manager we can add back verification here. 883 #if 0 884 for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) 885 verifyLoop(*I); 886 #endif 887 } 888