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