1 ///===- SimpleLoopUnswitch.cpp - Hoist loop-invariant control flow ---------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #include "llvm/Transforms/Scalar/SimpleLoopUnswitch.h" 10 #include "llvm/ADT/DenseMap.h" 11 #include "llvm/ADT/STLExtras.h" 12 #include "llvm/ADT/Sequence.h" 13 #include "llvm/ADT/SetVector.h" 14 #include "llvm/ADT/SmallPtrSet.h" 15 #include "llvm/ADT/SmallVector.h" 16 #include "llvm/ADT/Statistic.h" 17 #include "llvm/ADT/Twine.h" 18 #include "llvm/Analysis/AssumptionCache.h" 19 #include "llvm/Analysis/BlockFrequencyInfo.h" 20 #include "llvm/Analysis/CFG.h" 21 #include "llvm/Analysis/CodeMetrics.h" 22 #include "llvm/Analysis/GuardUtils.h" 23 #include "llvm/Analysis/LoopAnalysisManager.h" 24 #include "llvm/Analysis/LoopInfo.h" 25 #include "llvm/Analysis/LoopIterator.h" 26 #include "llvm/Analysis/LoopPass.h" 27 #include "llvm/Analysis/MemorySSA.h" 28 #include "llvm/Analysis/MemorySSAUpdater.h" 29 #include "llvm/Analysis/MustExecute.h" 30 #include "llvm/Analysis/ProfileSummaryInfo.h" 31 #include "llvm/Analysis/ScalarEvolution.h" 32 #include "llvm/Analysis/TargetTransformInfo.h" 33 #include "llvm/Analysis/ValueTracking.h" 34 #include "llvm/IR/BasicBlock.h" 35 #include "llvm/IR/Constant.h" 36 #include "llvm/IR/Constants.h" 37 #include "llvm/IR/Dominators.h" 38 #include "llvm/IR/Function.h" 39 #include "llvm/IR/IRBuilder.h" 40 #include "llvm/IR/InstrTypes.h" 41 #include "llvm/IR/Instruction.h" 42 #include "llvm/IR/Instructions.h" 43 #include "llvm/IR/IntrinsicInst.h" 44 #include "llvm/IR/PatternMatch.h" 45 #include "llvm/IR/Use.h" 46 #include "llvm/IR/Value.h" 47 #include "llvm/InitializePasses.h" 48 #include "llvm/Pass.h" 49 #include "llvm/Support/Casting.h" 50 #include "llvm/Support/CommandLine.h" 51 #include "llvm/Support/Debug.h" 52 #include "llvm/Support/ErrorHandling.h" 53 #include "llvm/Support/GenericDomTree.h" 54 #include "llvm/Support/InstructionCost.h" 55 #include "llvm/Support/raw_ostream.h" 56 #include "llvm/Transforms/Scalar/LoopPassManager.h" 57 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 58 #include "llvm/Transforms/Utils/Cloning.h" 59 #include "llvm/Transforms/Utils/Local.h" 60 #include "llvm/Transforms/Utils/LoopUtils.h" 61 #include "llvm/Transforms/Utils/ValueMapper.h" 62 #include <algorithm> 63 #include <cassert> 64 #include <iterator> 65 #include <numeric> 66 #include <utility> 67 68 #define DEBUG_TYPE "simple-loop-unswitch" 69 70 using namespace llvm; 71 using namespace llvm::PatternMatch; 72 73 STATISTIC(NumBranches, "Number of branches unswitched"); 74 STATISTIC(NumSwitches, "Number of switches unswitched"); 75 STATISTIC(NumGuards, "Number of guards turned into branches for unswitching"); 76 STATISTIC(NumTrivial, "Number of unswitches that are trivial"); 77 STATISTIC( 78 NumCostMultiplierSkipped, 79 "Number of unswitch candidates that had their cost multiplier skipped"); 80 81 static cl::opt<bool> EnableNonTrivialUnswitch( 82 "enable-nontrivial-unswitch", cl::init(false), cl::Hidden, 83 cl::desc("Forcibly enables non-trivial loop unswitching rather than " 84 "following the configuration passed into the pass.")); 85 86 static cl::opt<int> 87 UnswitchThreshold("unswitch-threshold", cl::init(50), cl::Hidden, 88 cl::desc("The cost threshold for unswitching a loop.")); 89 90 static cl::opt<bool> EnableUnswitchCostMultiplier( 91 "enable-unswitch-cost-multiplier", cl::init(true), cl::Hidden, 92 cl::desc("Enable unswitch cost multiplier that prohibits exponential " 93 "explosion in nontrivial unswitch.")); 94 static cl::opt<int> UnswitchSiblingsToplevelDiv( 95 "unswitch-siblings-toplevel-div", cl::init(2), cl::Hidden, 96 cl::desc("Toplevel siblings divisor for cost multiplier.")); 97 static cl::opt<int> UnswitchNumInitialUnscaledCandidates( 98 "unswitch-num-initial-unscaled-candidates", cl::init(8), cl::Hidden, 99 cl::desc("Number of unswitch candidates that are ignored when calculating " 100 "cost multiplier.")); 101 static cl::opt<bool> UnswitchGuards( 102 "simple-loop-unswitch-guards", cl::init(true), cl::Hidden, 103 cl::desc("If enabled, simple loop unswitching will also consider " 104 "llvm.experimental.guard intrinsics as unswitch candidates.")); 105 static cl::opt<bool> DropNonTrivialImplicitNullChecks( 106 "simple-loop-unswitch-drop-non-trivial-implicit-null-checks", 107 cl::init(false), cl::Hidden, 108 cl::desc("If enabled, drop make.implicit metadata in unswitched implicit " 109 "null checks to save time analyzing if we can keep it.")); 110 static cl::opt<unsigned> 111 MSSAThreshold("simple-loop-unswitch-memoryssa-threshold", 112 cl::desc("Max number of memory uses to explore during " 113 "partial unswitching analysis"), 114 cl::init(100), cl::Hidden); 115 static cl::opt<bool> FreezeLoopUnswitchCond( 116 "freeze-loop-unswitch-cond", cl::init(true), cl::Hidden, 117 cl::desc("If enabled, the freeze instruction will be added to condition " 118 "of loop unswitch to prevent miscompilation.")); 119 120 // Helper to skip (select x, true, false), which matches both a logical AND and 121 // OR and can confuse code that tries to determine if \p Cond is either a 122 // logical AND or OR but not both. 123 static Value *skipTrivialSelect(Value *Cond) { 124 Value *CondNext; 125 while (match(Cond, m_Select(m_Value(CondNext), m_One(), m_Zero()))) 126 Cond = CondNext; 127 return Cond; 128 } 129 130 /// Collect all of the loop invariant input values transitively used by the 131 /// homogeneous instruction graph from a given root. 132 /// 133 /// This essentially walks from a root recursively through loop variant operands 134 /// which have perform the same logical operation (AND or OR) and finds all 135 /// inputs which are loop invariant. For some operations these can be 136 /// re-associated and unswitched out of the loop entirely. 137 static TinyPtrVector<Value *> 138 collectHomogenousInstGraphLoopInvariants(const Loop &L, Instruction &Root, 139 const LoopInfo &LI) { 140 assert(!L.isLoopInvariant(&Root) && 141 "Only need to walk the graph if root itself is not invariant."); 142 TinyPtrVector<Value *> Invariants; 143 144 bool IsRootAnd = match(&Root, m_LogicalAnd()); 145 bool IsRootOr = match(&Root, m_LogicalOr()); 146 147 // Build a worklist and recurse through operators collecting invariants. 148 SmallVector<Instruction *, 4> Worklist; 149 SmallPtrSet<Instruction *, 8> Visited; 150 Worklist.push_back(&Root); 151 Visited.insert(&Root); 152 do { 153 Instruction &I = *Worklist.pop_back_val(); 154 for (Value *OpV : I.operand_values()) { 155 // Skip constants as unswitching isn't interesting for them. 156 if (isa<Constant>(OpV)) 157 continue; 158 159 // Add it to our result if loop invariant. 160 if (L.isLoopInvariant(OpV)) { 161 Invariants.push_back(OpV); 162 continue; 163 } 164 165 // If not an instruction with the same opcode, nothing we can do. 166 Instruction *OpI = dyn_cast<Instruction>(skipTrivialSelect(OpV)); 167 168 if (OpI && ((IsRootAnd && match(OpI, m_LogicalAnd())) || 169 (IsRootOr && match(OpI, m_LogicalOr())))) { 170 // Visit this operand. 171 if (Visited.insert(OpI).second) 172 Worklist.push_back(OpI); 173 } 174 } 175 } while (!Worklist.empty()); 176 177 return Invariants; 178 } 179 180 static void replaceLoopInvariantUses(const Loop &L, Value *Invariant, 181 Constant &Replacement) { 182 assert(!isa<Constant>(Invariant) && "Why are we unswitching on a constant?"); 183 184 // Replace uses of LIC in the loop with the given constant. 185 // We use make_early_inc_range as set invalidates the iterator. 186 for (Use &U : llvm::make_early_inc_range(Invariant->uses())) { 187 Instruction *UserI = dyn_cast<Instruction>(U.getUser()); 188 189 // Replace this use within the loop body. 190 if (UserI && L.contains(UserI)) 191 U.set(&Replacement); 192 } 193 } 194 195 /// Check that all the LCSSA PHI nodes in the loop exit block have trivial 196 /// incoming values along this edge. 197 static bool areLoopExitPHIsLoopInvariant(const Loop &L, 198 const BasicBlock &ExitingBB, 199 const BasicBlock &ExitBB) { 200 for (const Instruction &I : ExitBB) { 201 auto *PN = dyn_cast<PHINode>(&I); 202 if (!PN) 203 // No more PHIs to check. 204 return true; 205 206 // If the incoming value for this edge isn't loop invariant the unswitch 207 // won't be trivial. 208 if (!L.isLoopInvariant(PN->getIncomingValueForBlock(&ExitingBB))) 209 return false; 210 } 211 llvm_unreachable("Basic blocks should never be empty!"); 212 } 213 214 /// Copy a set of loop invariant values \p ToDuplicate and insert them at the 215 /// end of \p BB and conditionally branch on the copied condition. We only 216 /// branch on a single value. 217 static void buildPartialUnswitchConditionalBranch( 218 BasicBlock &BB, ArrayRef<Value *> Invariants, bool Direction, 219 BasicBlock &UnswitchedSucc, BasicBlock &NormalSucc, bool InsertFreeze, 220 const Instruction *I, AssumptionCache *AC, const DominatorTree &DT) { 221 IRBuilder<> IRB(&BB); 222 223 SmallVector<Value *> FrozenInvariants; 224 for (Value *Inv : Invariants) { 225 if (InsertFreeze && !isGuaranteedNotToBeUndefOrPoison(Inv, AC, I, &DT)) 226 Inv = IRB.CreateFreeze(Inv, Inv->getName() + ".fr"); 227 FrozenInvariants.push_back(Inv); 228 } 229 230 Value *Cond = Direction ? IRB.CreateOr(FrozenInvariants) 231 : IRB.CreateAnd(FrozenInvariants); 232 IRB.CreateCondBr(Cond, Direction ? &UnswitchedSucc : &NormalSucc, 233 Direction ? &NormalSucc : &UnswitchedSucc); 234 } 235 236 /// Copy a set of loop invariant values, and conditionally branch on them. 237 static void buildPartialInvariantUnswitchConditionalBranch( 238 BasicBlock &BB, ArrayRef<Value *> ToDuplicate, bool Direction, 239 BasicBlock &UnswitchedSucc, BasicBlock &NormalSucc, Loop &L, 240 MemorySSAUpdater *MSSAU) { 241 ValueToValueMapTy VMap; 242 for (auto *Val : reverse(ToDuplicate)) { 243 Instruction *Inst = cast<Instruction>(Val); 244 Instruction *NewInst = Inst->clone(); 245 BB.getInstList().insert(BB.end(), NewInst); 246 RemapInstruction(NewInst, VMap, 247 RF_NoModuleLevelChanges | RF_IgnoreMissingLocals); 248 VMap[Val] = NewInst; 249 250 if (!MSSAU) 251 continue; 252 253 MemorySSA *MSSA = MSSAU->getMemorySSA(); 254 if (auto *MemUse = 255 dyn_cast_or_null<MemoryUse>(MSSA->getMemoryAccess(Inst))) { 256 auto *DefiningAccess = MemUse->getDefiningAccess(); 257 // Get the first defining access before the loop. 258 while (L.contains(DefiningAccess->getBlock())) { 259 // If the defining access is a MemoryPhi, get the incoming 260 // value for the pre-header as defining access. 261 if (auto *MemPhi = dyn_cast<MemoryPhi>(DefiningAccess)) 262 DefiningAccess = 263 MemPhi->getIncomingValueForBlock(L.getLoopPreheader()); 264 else 265 DefiningAccess = cast<MemoryDef>(DefiningAccess)->getDefiningAccess(); 266 } 267 MSSAU->createMemoryAccessInBB(NewInst, DefiningAccess, 268 NewInst->getParent(), 269 MemorySSA::BeforeTerminator); 270 } 271 } 272 273 IRBuilder<> IRB(&BB); 274 Value *Cond = VMap[ToDuplicate[0]]; 275 IRB.CreateCondBr(Cond, Direction ? &UnswitchedSucc : &NormalSucc, 276 Direction ? &NormalSucc : &UnswitchedSucc); 277 } 278 279 /// Rewrite the PHI nodes in an unswitched loop exit basic block. 280 /// 281 /// Requires that the loop exit and unswitched basic block are the same, and 282 /// that the exiting block was a unique predecessor of that block. Rewrites the 283 /// PHI nodes in that block such that what were LCSSA PHI nodes become trivial 284 /// PHI nodes from the old preheader that now contains the unswitched 285 /// terminator. 286 static void rewritePHINodesForUnswitchedExitBlock(BasicBlock &UnswitchedBB, 287 BasicBlock &OldExitingBB, 288 BasicBlock &OldPH) { 289 for (PHINode &PN : UnswitchedBB.phis()) { 290 // When the loop exit is directly unswitched we just need to update the 291 // incoming basic block. We loop to handle weird cases with repeated 292 // incoming blocks, but expect to typically only have one operand here. 293 for (auto i : seq<int>(0, PN.getNumOperands())) { 294 assert(PN.getIncomingBlock(i) == &OldExitingBB && 295 "Found incoming block different from unique predecessor!"); 296 PN.setIncomingBlock(i, &OldPH); 297 } 298 } 299 } 300 301 /// Rewrite the PHI nodes in the loop exit basic block and the split off 302 /// unswitched block. 303 /// 304 /// Because the exit block remains an exit from the loop, this rewrites the 305 /// LCSSA PHI nodes in it to remove the unswitched edge and introduces PHI 306 /// nodes into the unswitched basic block to select between the value in the 307 /// old preheader and the loop exit. 308 static void rewritePHINodesForExitAndUnswitchedBlocks(BasicBlock &ExitBB, 309 BasicBlock &UnswitchedBB, 310 BasicBlock &OldExitingBB, 311 BasicBlock &OldPH, 312 bool FullUnswitch) { 313 assert(&ExitBB != &UnswitchedBB && 314 "Must have different loop exit and unswitched blocks!"); 315 Instruction *InsertPt = &*UnswitchedBB.begin(); 316 for (PHINode &PN : ExitBB.phis()) { 317 auto *NewPN = PHINode::Create(PN.getType(), /*NumReservedValues*/ 2, 318 PN.getName() + ".split", InsertPt); 319 320 // Walk backwards over the old PHI node's inputs to minimize the cost of 321 // removing each one. We have to do this weird loop manually so that we 322 // create the same number of new incoming edges in the new PHI as we expect 323 // each case-based edge to be included in the unswitched switch in some 324 // cases. 325 // FIXME: This is really, really gross. It would be much cleaner if LLVM 326 // allowed us to create a single entry for a predecessor block without 327 // having separate entries for each "edge" even though these edges are 328 // required to produce identical results. 329 for (int i = PN.getNumIncomingValues() - 1; i >= 0; --i) { 330 if (PN.getIncomingBlock(i) != &OldExitingBB) 331 continue; 332 333 Value *Incoming = PN.getIncomingValue(i); 334 if (FullUnswitch) 335 // No more edge from the old exiting block to the exit block. 336 PN.removeIncomingValue(i); 337 338 NewPN->addIncoming(Incoming, &OldPH); 339 } 340 341 // Now replace the old PHI with the new one and wire the old one in as an 342 // input to the new one. 343 PN.replaceAllUsesWith(NewPN); 344 NewPN->addIncoming(&PN, &ExitBB); 345 } 346 } 347 348 /// Hoist the current loop up to the innermost loop containing a remaining exit. 349 /// 350 /// Because we've removed an exit from the loop, we may have changed the set of 351 /// loops reachable and need to move the current loop up the loop nest or even 352 /// to an entirely separate nest. 353 static void hoistLoopToNewParent(Loop &L, BasicBlock &Preheader, 354 DominatorTree &DT, LoopInfo &LI, 355 MemorySSAUpdater *MSSAU, ScalarEvolution *SE) { 356 // If the loop is already at the top level, we can't hoist it anywhere. 357 Loop *OldParentL = L.getParentLoop(); 358 if (!OldParentL) 359 return; 360 361 SmallVector<BasicBlock *, 4> Exits; 362 L.getExitBlocks(Exits); 363 Loop *NewParentL = nullptr; 364 for (auto *ExitBB : Exits) 365 if (Loop *ExitL = LI.getLoopFor(ExitBB)) 366 if (!NewParentL || NewParentL->contains(ExitL)) 367 NewParentL = ExitL; 368 369 if (NewParentL == OldParentL) 370 return; 371 372 // The new parent loop (if different) should always contain the old one. 373 if (NewParentL) 374 assert(NewParentL->contains(OldParentL) && 375 "Can only hoist this loop up the nest!"); 376 377 // The preheader will need to move with the body of this loop. However, 378 // because it isn't in this loop we also need to update the primary loop map. 379 assert(OldParentL == LI.getLoopFor(&Preheader) && 380 "Parent loop of this loop should contain this loop's preheader!"); 381 LI.changeLoopFor(&Preheader, NewParentL); 382 383 // Remove this loop from its old parent. 384 OldParentL->removeChildLoop(&L); 385 386 // Add the loop either to the new parent or as a top-level loop. 387 if (NewParentL) 388 NewParentL->addChildLoop(&L); 389 else 390 LI.addTopLevelLoop(&L); 391 392 // Remove this loops blocks from the old parent and every other loop up the 393 // nest until reaching the new parent. Also update all of these 394 // no-longer-containing loops to reflect the nesting change. 395 for (Loop *OldContainingL = OldParentL; OldContainingL != NewParentL; 396 OldContainingL = OldContainingL->getParentLoop()) { 397 llvm::erase_if(OldContainingL->getBlocksVector(), 398 [&](const BasicBlock *BB) { 399 return BB == &Preheader || L.contains(BB); 400 }); 401 402 OldContainingL->getBlocksSet().erase(&Preheader); 403 for (BasicBlock *BB : L.blocks()) 404 OldContainingL->getBlocksSet().erase(BB); 405 406 // Because we just hoisted a loop out of this one, we have essentially 407 // created new exit paths from it. That means we need to form LCSSA PHI 408 // nodes for values used in the no-longer-nested loop. 409 formLCSSA(*OldContainingL, DT, &LI, SE); 410 411 // We shouldn't need to form dedicated exits because the exit introduced 412 // here is the (just split by unswitching) preheader. However, after trivial 413 // unswitching it is possible to get new non-dedicated exits out of parent 414 // loop so let's conservatively form dedicated exit blocks and figure out 415 // if we can optimize later. 416 formDedicatedExitBlocks(OldContainingL, &DT, &LI, MSSAU, 417 /*PreserveLCSSA*/ true); 418 } 419 } 420 421 // Return the top-most loop containing ExitBB and having ExitBB as exiting block 422 // or the loop containing ExitBB, if there is no parent loop containing ExitBB 423 // as exiting block. 424 static const Loop *getTopMostExitingLoop(const BasicBlock *ExitBB, 425 const LoopInfo &LI) { 426 const Loop *TopMost = LI.getLoopFor(ExitBB); 427 const Loop *Current = TopMost; 428 while (Current) { 429 if (Current->isLoopExiting(ExitBB)) 430 TopMost = Current; 431 Current = Current->getParentLoop(); 432 } 433 return TopMost; 434 } 435 436 /// Unswitch a trivial branch if the condition is loop invariant. 437 /// 438 /// This routine should only be called when loop code leading to the branch has 439 /// been validated as trivial (no side effects). This routine checks if the 440 /// condition is invariant and one of the successors is a loop exit. This 441 /// allows us to unswitch without duplicating the loop, making it trivial. 442 /// 443 /// If this routine fails to unswitch the branch it returns false. 444 /// 445 /// If the branch can be unswitched, this routine splits the preheader and 446 /// hoists the branch above that split. Preserves loop simplified form 447 /// (splitting the exit block as necessary). It simplifies the branch within 448 /// the loop to an unconditional branch but doesn't remove it entirely. Further 449 /// cleanup can be done with some simplifycfg like pass. 450 /// 451 /// If `SE` is not null, it will be updated based on the potential loop SCEVs 452 /// invalidated by this. 453 static bool unswitchTrivialBranch(Loop &L, BranchInst &BI, DominatorTree &DT, 454 LoopInfo &LI, ScalarEvolution *SE, 455 MemorySSAUpdater *MSSAU) { 456 assert(BI.isConditional() && "Can only unswitch a conditional branch!"); 457 LLVM_DEBUG(dbgs() << " Trying to unswitch branch: " << BI << "\n"); 458 459 // The loop invariant values that we want to unswitch. 460 TinyPtrVector<Value *> Invariants; 461 462 // When true, we're fully unswitching the branch rather than just unswitching 463 // some input conditions to the branch. 464 bool FullUnswitch = false; 465 466 Value *Cond = skipTrivialSelect(BI.getCondition()); 467 if (L.isLoopInvariant(Cond)) { 468 Invariants.push_back(Cond); 469 FullUnswitch = true; 470 } else { 471 if (auto *CondInst = dyn_cast<Instruction>(Cond)) 472 Invariants = collectHomogenousInstGraphLoopInvariants(L, *CondInst, LI); 473 if (Invariants.empty()) { 474 LLVM_DEBUG(dbgs() << " Couldn't find invariant inputs!\n"); 475 return false; 476 } 477 } 478 479 // Check that one of the branch's successors exits, and which one. 480 bool ExitDirection = true; 481 int LoopExitSuccIdx = 0; 482 auto *LoopExitBB = BI.getSuccessor(0); 483 if (L.contains(LoopExitBB)) { 484 ExitDirection = false; 485 LoopExitSuccIdx = 1; 486 LoopExitBB = BI.getSuccessor(1); 487 if (L.contains(LoopExitBB)) { 488 LLVM_DEBUG(dbgs() << " Branch doesn't exit the loop!\n"); 489 return false; 490 } 491 } 492 auto *ContinueBB = BI.getSuccessor(1 - LoopExitSuccIdx); 493 auto *ParentBB = BI.getParent(); 494 if (!areLoopExitPHIsLoopInvariant(L, *ParentBB, *LoopExitBB)) { 495 LLVM_DEBUG(dbgs() << " Loop exit PHI's aren't loop-invariant!\n"); 496 return false; 497 } 498 499 // When unswitching only part of the branch's condition, we need the exit 500 // block to be reached directly from the partially unswitched input. This can 501 // be done when the exit block is along the true edge and the branch condition 502 // is a graph of `or` operations, or the exit block is along the false edge 503 // and the condition is a graph of `and` operations. 504 if (!FullUnswitch) { 505 if (ExitDirection ? !match(Cond, m_LogicalOr()) 506 : !match(Cond, m_LogicalAnd())) { 507 LLVM_DEBUG(dbgs() << " Branch condition is in improper form for " 508 "non-full unswitch!\n"); 509 return false; 510 } 511 } 512 513 LLVM_DEBUG({ 514 dbgs() << " unswitching trivial invariant conditions for: " << BI 515 << "\n"; 516 for (Value *Invariant : Invariants) { 517 dbgs() << " " << *Invariant << " == true"; 518 if (Invariant != Invariants.back()) 519 dbgs() << " ||"; 520 dbgs() << "\n"; 521 } 522 }); 523 524 // If we have scalar evolutions, we need to invalidate them including this 525 // loop, the loop containing the exit block and the topmost parent loop 526 // exiting via LoopExitBB. 527 if (SE) { 528 if (const Loop *ExitL = getTopMostExitingLoop(LoopExitBB, LI)) 529 SE->forgetLoop(ExitL); 530 else 531 // Forget the entire nest as this exits the entire nest. 532 SE->forgetTopmostLoop(&L); 533 } 534 535 if (MSSAU && VerifyMemorySSA) 536 MSSAU->getMemorySSA()->verifyMemorySSA(); 537 538 // Split the preheader, so that we know that there is a safe place to insert 539 // the conditional branch. We will change the preheader to have a conditional 540 // branch on LoopCond. 541 BasicBlock *OldPH = L.getLoopPreheader(); 542 BasicBlock *NewPH = SplitEdge(OldPH, L.getHeader(), &DT, &LI, MSSAU); 543 544 // Now that we have a place to insert the conditional branch, create a place 545 // to branch to: this is the exit block out of the loop that we are 546 // unswitching. We need to split this if there are other loop predecessors. 547 // Because the loop is in simplified form, *any* other predecessor is enough. 548 BasicBlock *UnswitchedBB; 549 if (FullUnswitch && LoopExitBB->getUniquePredecessor()) { 550 assert(LoopExitBB->getUniquePredecessor() == BI.getParent() && 551 "A branch's parent isn't a predecessor!"); 552 UnswitchedBB = LoopExitBB; 553 } else { 554 UnswitchedBB = 555 SplitBlock(LoopExitBB, &LoopExitBB->front(), &DT, &LI, MSSAU); 556 } 557 558 if (MSSAU && VerifyMemorySSA) 559 MSSAU->getMemorySSA()->verifyMemorySSA(); 560 561 // Actually move the invariant uses into the unswitched position. If possible, 562 // we do this by moving the instructions, but when doing partial unswitching 563 // we do it by building a new merge of the values in the unswitched position. 564 OldPH->getTerminator()->eraseFromParent(); 565 if (FullUnswitch) { 566 // If fully unswitching, we can use the existing branch instruction. 567 // Splice it into the old PH to gate reaching the new preheader and re-point 568 // its successors. 569 OldPH->getInstList().splice(OldPH->end(), BI.getParent()->getInstList(), 570 BI); 571 BI.setCondition(Cond); 572 if (MSSAU) { 573 // Temporarily clone the terminator, to make MSSA update cheaper by 574 // separating "insert edge" updates from "remove edge" ones. 575 ParentBB->getInstList().push_back(BI.clone()); 576 } else { 577 // Create a new unconditional branch that will continue the loop as a new 578 // terminator. 579 BranchInst::Create(ContinueBB, ParentBB); 580 } 581 BI.setSuccessor(LoopExitSuccIdx, UnswitchedBB); 582 BI.setSuccessor(1 - LoopExitSuccIdx, NewPH); 583 } else { 584 // Only unswitching a subset of inputs to the condition, so we will need to 585 // build a new branch that merges the invariant inputs. 586 if (ExitDirection) 587 assert(match(skipTrivialSelect(BI.getCondition()), m_LogicalOr()) && 588 "Must have an `or` of `i1`s or `select i1 X, true, Y`s for the " 589 "condition!"); 590 else 591 assert(match(skipTrivialSelect(BI.getCondition()), m_LogicalAnd()) && 592 "Must have an `and` of `i1`s or `select i1 X, Y, false`s for the" 593 " condition!"); 594 buildPartialUnswitchConditionalBranch( 595 *OldPH, Invariants, ExitDirection, *UnswitchedBB, *NewPH, 596 FreezeLoopUnswitchCond, OldPH->getTerminator(), nullptr, DT); 597 } 598 599 // Update the dominator tree with the added edge. 600 DT.insertEdge(OldPH, UnswitchedBB); 601 602 // After the dominator tree was updated with the added edge, update MemorySSA 603 // if available. 604 if (MSSAU) { 605 SmallVector<CFGUpdate, 1> Updates; 606 Updates.push_back({cfg::UpdateKind::Insert, OldPH, UnswitchedBB}); 607 MSSAU->applyInsertUpdates(Updates, DT); 608 } 609 610 // Finish updating dominator tree and memory ssa for full unswitch. 611 if (FullUnswitch) { 612 if (MSSAU) { 613 // Remove the cloned branch instruction. 614 ParentBB->getTerminator()->eraseFromParent(); 615 // Create unconditional branch now. 616 BranchInst::Create(ContinueBB, ParentBB); 617 MSSAU->removeEdge(ParentBB, LoopExitBB); 618 } 619 DT.deleteEdge(ParentBB, LoopExitBB); 620 } 621 622 if (MSSAU && VerifyMemorySSA) 623 MSSAU->getMemorySSA()->verifyMemorySSA(); 624 625 // Rewrite the relevant PHI nodes. 626 if (UnswitchedBB == LoopExitBB) 627 rewritePHINodesForUnswitchedExitBlock(*UnswitchedBB, *ParentBB, *OldPH); 628 else 629 rewritePHINodesForExitAndUnswitchedBlocks(*LoopExitBB, *UnswitchedBB, 630 *ParentBB, *OldPH, FullUnswitch); 631 632 // The constant we can replace all of our invariants with inside the loop 633 // body. If any of the invariants have a value other than this the loop won't 634 // be entered. 635 ConstantInt *Replacement = ExitDirection 636 ? ConstantInt::getFalse(BI.getContext()) 637 : ConstantInt::getTrue(BI.getContext()); 638 639 // Since this is an i1 condition we can also trivially replace uses of it 640 // within the loop with a constant. 641 for (Value *Invariant : Invariants) 642 replaceLoopInvariantUses(L, Invariant, *Replacement); 643 644 // If this was full unswitching, we may have changed the nesting relationship 645 // for this loop so hoist it to its correct parent if needed. 646 if (FullUnswitch) 647 hoistLoopToNewParent(L, *NewPH, DT, LI, MSSAU, SE); 648 649 if (MSSAU && VerifyMemorySSA) 650 MSSAU->getMemorySSA()->verifyMemorySSA(); 651 652 LLVM_DEBUG(dbgs() << " done: unswitching trivial branch...\n"); 653 ++NumTrivial; 654 ++NumBranches; 655 return true; 656 } 657 658 /// Unswitch a trivial switch if the condition is loop invariant. 659 /// 660 /// This routine should only be called when loop code leading to the switch has 661 /// been validated as trivial (no side effects). This routine checks if the 662 /// condition is invariant and that at least one of the successors is a loop 663 /// exit. This allows us to unswitch without duplicating the loop, making it 664 /// trivial. 665 /// 666 /// If this routine fails to unswitch the switch it returns false. 667 /// 668 /// If the switch can be unswitched, this routine splits the preheader and 669 /// copies the switch above that split. If the default case is one of the 670 /// exiting cases, it copies the non-exiting cases and points them at the new 671 /// preheader. If the default case is not exiting, it copies the exiting cases 672 /// and points the default at the preheader. It preserves loop simplified form 673 /// (splitting the exit blocks as necessary). It simplifies the switch within 674 /// the loop by removing now-dead cases. If the default case is one of those 675 /// unswitched, it replaces its destination with a new basic block containing 676 /// only unreachable. Such basic blocks, while technically loop exits, are not 677 /// considered for unswitching so this is a stable transform and the same 678 /// switch will not be revisited. If after unswitching there is only a single 679 /// in-loop successor, the switch is further simplified to an unconditional 680 /// branch. Still more cleanup can be done with some simplifycfg like pass. 681 /// 682 /// If `SE` is not null, it will be updated based on the potential loop SCEVs 683 /// invalidated by this. 684 static bool unswitchTrivialSwitch(Loop &L, SwitchInst &SI, DominatorTree &DT, 685 LoopInfo &LI, ScalarEvolution *SE, 686 MemorySSAUpdater *MSSAU) { 687 LLVM_DEBUG(dbgs() << " Trying to unswitch switch: " << SI << "\n"); 688 Value *LoopCond = SI.getCondition(); 689 690 // If this isn't switching on an invariant condition, we can't unswitch it. 691 if (!L.isLoopInvariant(LoopCond)) 692 return false; 693 694 auto *ParentBB = SI.getParent(); 695 696 // The same check must be used both for the default and the exit cases. We 697 // should never leave edges from the switch instruction to a basic block that 698 // we are unswitching, hence the condition used to determine the default case 699 // needs to also be used to populate ExitCaseIndices, which is then used to 700 // remove cases from the switch. 701 auto IsTriviallyUnswitchableExitBlock = [&](BasicBlock &BBToCheck) { 702 // BBToCheck is not an exit block if it is inside loop L. 703 if (L.contains(&BBToCheck)) 704 return false; 705 // BBToCheck is not trivial to unswitch if its phis aren't loop invariant. 706 if (!areLoopExitPHIsLoopInvariant(L, *ParentBB, BBToCheck)) 707 return false; 708 // We do not unswitch a block that only has an unreachable statement, as 709 // it's possible this is a previously unswitched block. Only unswitch if 710 // either the terminator is not unreachable, or, if it is, it's not the only 711 // instruction in the block. 712 auto *TI = BBToCheck.getTerminator(); 713 bool isUnreachable = isa<UnreachableInst>(TI); 714 return !isUnreachable || 715 (isUnreachable && (BBToCheck.getFirstNonPHIOrDbg() != TI)); 716 }; 717 718 SmallVector<int, 4> ExitCaseIndices; 719 for (auto Case : SI.cases()) 720 if (IsTriviallyUnswitchableExitBlock(*Case.getCaseSuccessor())) 721 ExitCaseIndices.push_back(Case.getCaseIndex()); 722 BasicBlock *DefaultExitBB = nullptr; 723 SwitchInstProfUpdateWrapper::CaseWeightOpt DefaultCaseWeight = 724 SwitchInstProfUpdateWrapper::getSuccessorWeight(SI, 0); 725 if (IsTriviallyUnswitchableExitBlock(*SI.getDefaultDest())) { 726 DefaultExitBB = SI.getDefaultDest(); 727 } else if (ExitCaseIndices.empty()) 728 return false; 729 730 LLVM_DEBUG(dbgs() << " unswitching trivial switch...\n"); 731 732 if (MSSAU && VerifyMemorySSA) 733 MSSAU->getMemorySSA()->verifyMemorySSA(); 734 735 // We may need to invalidate SCEVs for the outermost loop reached by any of 736 // the exits. 737 Loop *OuterL = &L; 738 739 if (DefaultExitBB) { 740 // Clear out the default destination temporarily to allow accurate 741 // predecessor lists to be examined below. 742 SI.setDefaultDest(nullptr); 743 // Check the loop containing this exit. 744 Loop *ExitL = LI.getLoopFor(DefaultExitBB); 745 if (!ExitL || ExitL->contains(OuterL)) 746 OuterL = ExitL; 747 } 748 749 // Store the exit cases into a separate data structure and remove them from 750 // the switch. 751 SmallVector<std::tuple<ConstantInt *, BasicBlock *, 752 SwitchInstProfUpdateWrapper::CaseWeightOpt>, 753 4> ExitCases; 754 ExitCases.reserve(ExitCaseIndices.size()); 755 SwitchInstProfUpdateWrapper SIW(SI); 756 // We walk the case indices backwards so that we remove the last case first 757 // and don't disrupt the earlier indices. 758 for (unsigned Index : reverse(ExitCaseIndices)) { 759 auto CaseI = SI.case_begin() + Index; 760 // Compute the outer loop from this exit. 761 Loop *ExitL = LI.getLoopFor(CaseI->getCaseSuccessor()); 762 if (!ExitL || ExitL->contains(OuterL)) 763 OuterL = ExitL; 764 // Save the value of this case. 765 auto W = SIW.getSuccessorWeight(CaseI->getSuccessorIndex()); 766 ExitCases.emplace_back(CaseI->getCaseValue(), CaseI->getCaseSuccessor(), W); 767 // Delete the unswitched cases. 768 SIW.removeCase(CaseI); 769 } 770 771 if (SE) { 772 if (OuterL) 773 SE->forgetLoop(OuterL); 774 else 775 SE->forgetTopmostLoop(&L); 776 } 777 778 // Check if after this all of the remaining cases point at the same 779 // successor. 780 BasicBlock *CommonSuccBB = nullptr; 781 if (SI.getNumCases() > 0 && 782 all_of(drop_begin(SI.cases()), [&SI](const SwitchInst::CaseHandle &Case) { 783 return Case.getCaseSuccessor() == SI.case_begin()->getCaseSuccessor(); 784 })) 785 CommonSuccBB = SI.case_begin()->getCaseSuccessor(); 786 if (!DefaultExitBB) { 787 // If we're not unswitching the default, we need it to match any cases to 788 // have a common successor or if we have no cases it is the common 789 // successor. 790 if (SI.getNumCases() == 0) 791 CommonSuccBB = SI.getDefaultDest(); 792 else if (SI.getDefaultDest() != CommonSuccBB) 793 CommonSuccBB = nullptr; 794 } 795 796 // Split the preheader, so that we know that there is a safe place to insert 797 // the switch. 798 BasicBlock *OldPH = L.getLoopPreheader(); 799 BasicBlock *NewPH = SplitEdge(OldPH, L.getHeader(), &DT, &LI, MSSAU); 800 OldPH->getTerminator()->eraseFromParent(); 801 802 // Now add the unswitched switch. 803 auto *NewSI = SwitchInst::Create(LoopCond, NewPH, ExitCases.size(), OldPH); 804 SwitchInstProfUpdateWrapper NewSIW(*NewSI); 805 806 // Rewrite the IR for the unswitched basic blocks. This requires two steps. 807 // First, we split any exit blocks with remaining in-loop predecessors. Then 808 // we update the PHIs in one of two ways depending on if there was a split. 809 // We walk in reverse so that we split in the same order as the cases 810 // appeared. This is purely for convenience of reading the resulting IR, but 811 // it doesn't cost anything really. 812 SmallPtrSet<BasicBlock *, 2> UnswitchedExitBBs; 813 SmallDenseMap<BasicBlock *, BasicBlock *, 2> SplitExitBBMap; 814 // Handle the default exit if necessary. 815 // FIXME: It'd be great if we could merge this with the loop below but LLVM's 816 // ranges aren't quite powerful enough yet. 817 if (DefaultExitBB) { 818 if (pred_empty(DefaultExitBB)) { 819 UnswitchedExitBBs.insert(DefaultExitBB); 820 rewritePHINodesForUnswitchedExitBlock(*DefaultExitBB, *ParentBB, *OldPH); 821 } else { 822 auto *SplitBB = 823 SplitBlock(DefaultExitBB, &DefaultExitBB->front(), &DT, &LI, MSSAU); 824 rewritePHINodesForExitAndUnswitchedBlocks(*DefaultExitBB, *SplitBB, 825 *ParentBB, *OldPH, 826 /*FullUnswitch*/ true); 827 DefaultExitBB = SplitExitBBMap[DefaultExitBB] = SplitBB; 828 } 829 } 830 // Note that we must use a reference in the for loop so that we update the 831 // container. 832 for (auto &ExitCase : reverse(ExitCases)) { 833 // Grab a reference to the exit block in the pair so that we can update it. 834 BasicBlock *ExitBB = std::get<1>(ExitCase); 835 836 // If this case is the last edge into the exit block, we can simply reuse it 837 // as it will no longer be a loop exit. No mapping necessary. 838 if (pred_empty(ExitBB)) { 839 // Only rewrite once. 840 if (UnswitchedExitBBs.insert(ExitBB).second) 841 rewritePHINodesForUnswitchedExitBlock(*ExitBB, *ParentBB, *OldPH); 842 continue; 843 } 844 845 // Otherwise we need to split the exit block so that we retain an exit 846 // block from the loop and a target for the unswitched condition. 847 BasicBlock *&SplitExitBB = SplitExitBBMap[ExitBB]; 848 if (!SplitExitBB) { 849 // If this is the first time we see this, do the split and remember it. 850 SplitExitBB = SplitBlock(ExitBB, &ExitBB->front(), &DT, &LI, MSSAU); 851 rewritePHINodesForExitAndUnswitchedBlocks(*ExitBB, *SplitExitBB, 852 *ParentBB, *OldPH, 853 /*FullUnswitch*/ true); 854 } 855 // Update the case pair to point to the split block. 856 std::get<1>(ExitCase) = SplitExitBB; 857 } 858 859 // Now add the unswitched cases. We do this in reverse order as we built them 860 // in reverse order. 861 for (auto &ExitCase : reverse(ExitCases)) { 862 ConstantInt *CaseVal = std::get<0>(ExitCase); 863 BasicBlock *UnswitchedBB = std::get<1>(ExitCase); 864 865 NewSIW.addCase(CaseVal, UnswitchedBB, std::get<2>(ExitCase)); 866 } 867 868 // If the default was unswitched, re-point it and add explicit cases for 869 // entering the loop. 870 if (DefaultExitBB) { 871 NewSIW->setDefaultDest(DefaultExitBB); 872 NewSIW.setSuccessorWeight(0, DefaultCaseWeight); 873 874 // We removed all the exit cases, so we just copy the cases to the 875 // unswitched switch. 876 for (const auto &Case : SI.cases()) 877 NewSIW.addCase(Case.getCaseValue(), NewPH, 878 SIW.getSuccessorWeight(Case.getSuccessorIndex())); 879 } else if (DefaultCaseWeight) { 880 // We have to set branch weight of the default case. 881 uint64_t SW = *DefaultCaseWeight; 882 for (const auto &Case : SI.cases()) { 883 auto W = SIW.getSuccessorWeight(Case.getSuccessorIndex()); 884 assert(W && 885 "case weight must be defined as default case weight is defined"); 886 SW += *W; 887 } 888 NewSIW.setSuccessorWeight(0, SW); 889 } 890 891 // If we ended up with a common successor for every path through the switch 892 // after unswitching, rewrite it to an unconditional branch to make it easy 893 // to recognize. Otherwise we potentially have to recognize the default case 894 // pointing at unreachable and other complexity. 895 if (CommonSuccBB) { 896 BasicBlock *BB = SI.getParent(); 897 // We may have had multiple edges to this common successor block, so remove 898 // them as predecessors. We skip the first one, either the default or the 899 // actual first case. 900 bool SkippedFirst = DefaultExitBB == nullptr; 901 for (auto Case : SI.cases()) { 902 assert(Case.getCaseSuccessor() == CommonSuccBB && 903 "Non-common successor!"); 904 (void)Case; 905 if (!SkippedFirst) { 906 SkippedFirst = true; 907 continue; 908 } 909 CommonSuccBB->removePredecessor(BB, 910 /*KeepOneInputPHIs*/ true); 911 } 912 // Now nuke the switch and replace it with a direct branch. 913 SIW.eraseFromParent(); 914 BranchInst::Create(CommonSuccBB, BB); 915 } else if (DefaultExitBB) { 916 assert(SI.getNumCases() > 0 && 917 "If we had no cases we'd have a common successor!"); 918 // Move the last case to the default successor. This is valid as if the 919 // default got unswitched it cannot be reached. This has the advantage of 920 // being simple and keeping the number of edges from this switch to 921 // successors the same, and avoiding any PHI update complexity. 922 auto LastCaseI = std::prev(SI.case_end()); 923 924 SI.setDefaultDest(LastCaseI->getCaseSuccessor()); 925 SIW.setSuccessorWeight( 926 0, SIW.getSuccessorWeight(LastCaseI->getSuccessorIndex())); 927 SIW.removeCase(LastCaseI); 928 } 929 930 // Walk the unswitched exit blocks and the unswitched split blocks and update 931 // the dominator tree based on the CFG edits. While we are walking unordered 932 // containers here, the API for applyUpdates takes an unordered list of 933 // updates and requires them to not contain duplicates. 934 SmallVector<DominatorTree::UpdateType, 4> DTUpdates; 935 for (auto *UnswitchedExitBB : UnswitchedExitBBs) { 936 DTUpdates.push_back({DT.Delete, ParentBB, UnswitchedExitBB}); 937 DTUpdates.push_back({DT.Insert, OldPH, UnswitchedExitBB}); 938 } 939 for (auto SplitUnswitchedPair : SplitExitBBMap) { 940 DTUpdates.push_back({DT.Delete, ParentBB, SplitUnswitchedPair.first}); 941 DTUpdates.push_back({DT.Insert, OldPH, SplitUnswitchedPair.second}); 942 } 943 944 if (MSSAU) { 945 MSSAU->applyUpdates(DTUpdates, DT, /*UpdateDT=*/true); 946 if (VerifyMemorySSA) 947 MSSAU->getMemorySSA()->verifyMemorySSA(); 948 } else { 949 DT.applyUpdates(DTUpdates); 950 } 951 952 assert(DT.verify(DominatorTree::VerificationLevel::Fast)); 953 954 // We may have changed the nesting relationship for this loop so hoist it to 955 // its correct parent if needed. 956 hoistLoopToNewParent(L, *NewPH, DT, LI, MSSAU, SE); 957 958 if (MSSAU && VerifyMemorySSA) 959 MSSAU->getMemorySSA()->verifyMemorySSA(); 960 961 ++NumTrivial; 962 ++NumSwitches; 963 LLVM_DEBUG(dbgs() << " done: unswitching trivial switch...\n"); 964 return true; 965 } 966 967 /// This routine scans the loop to find a branch or switch which occurs before 968 /// any side effects occur. These can potentially be unswitched without 969 /// duplicating the loop. If a branch or switch is successfully unswitched the 970 /// scanning continues to see if subsequent branches or switches have become 971 /// trivial. Once all trivial candidates have been unswitched, this routine 972 /// returns. 973 /// 974 /// The return value indicates whether anything was unswitched (and therefore 975 /// changed). 976 /// 977 /// If `SE` is not null, it will be updated based on the potential loop SCEVs 978 /// invalidated by this. 979 static bool unswitchAllTrivialConditions(Loop &L, DominatorTree &DT, 980 LoopInfo &LI, ScalarEvolution *SE, 981 MemorySSAUpdater *MSSAU) { 982 bool Changed = false; 983 984 // If loop header has only one reachable successor we should keep looking for 985 // trivial condition candidates in the successor as well. An alternative is 986 // to constant fold conditions and merge successors into loop header (then we 987 // only need to check header's terminator). The reason for not doing this in 988 // LoopUnswitch pass is that it could potentially break LoopPassManager's 989 // invariants. Folding dead branches could either eliminate the current loop 990 // or make other loops unreachable. LCSSA form might also not be preserved 991 // after deleting branches. The following code keeps traversing loop header's 992 // successors until it finds the trivial condition candidate (condition that 993 // is not a constant). Since unswitching generates branches with constant 994 // conditions, this scenario could be very common in practice. 995 BasicBlock *CurrentBB = L.getHeader(); 996 SmallPtrSet<BasicBlock *, 8> Visited; 997 Visited.insert(CurrentBB); 998 do { 999 // Check if there are any side-effecting instructions (e.g. stores, calls, 1000 // volatile loads) in the part of the loop that the code *would* execute 1001 // without unswitching. 1002 if (MSSAU) // Possible early exit with MSSA 1003 if (auto *Defs = MSSAU->getMemorySSA()->getBlockDefs(CurrentBB)) 1004 if (!isa<MemoryPhi>(*Defs->begin()) || (++Defs->begin() != Defs->end())) 1005 return Changed; 1006 if (llvm::any_of(*CurrentBB, 1007 [](Instruction &I) { return I.mayHaveSideEffects(); })) 1008 return Changed; 1009 1010 Instruction *CurrentTerm = CurrentBB->getTerminator(); 1011 1012 if (auto *SI = dyn_cast<SwitchInst>(CurrentTerm)) { 1013 // Don't bother trying to unswitch past a switch with a constant 1014 // condition. This should be removed prior to running this pass by 1015 // simplifycfg. 1016 if (isa<Constant>(SI->getCondition())) 1017 return Changed; 1018 1019 if (!unswitchTrivialSwitch(L, *SI, DT, LI, SE, MSSAU)) 1020 // Couldn't unswitch this one so we're done. 1021 return Changed; 1022 1023 // Mark that we managed to unswitch something. 1024 Changed = true; 1025 1026 // If unswitching turned the terminator into an unconditional branch then 1027 // we can continue. The unswitching logic specifically works to fold any 1028 // cases it can into an unconditional branch to make it easier to 1029 // recognize here. 1030 auto *BI = dyn_cast<BranchInst>(CurrentBB->getTerminator()); 1031 if (!BI || BI->isConditional()) 1032 return Changed; 1033 1034 CurrentBB = BI->getSuccessor(0); 1035 continue; 1036 } 1037 1038 auto *BI = dyn_cast<BranchInst>(CurrentTerm); 1039 if (!BI) 1040 // We do not understand other terminator instructions. 1041 return Changed; 1042 1043 // Don't bother trying to unswitch past an unconditional branch or a branch 1044 // with a constant value. These should be removed by simplifycfg prior to 1045 // running this pass. 1046 if (!BI->isConditional() || 1047 isa<Constant>(skipTrivialSelect(BI->getCondition()))) 1048 return Changed; 1049 1050 // Found a trivial condition candidate: non-foldable conditional branch. If 1051 // we fail to unswitch this, we can't do anything else that is trivial. 1052 if (!unswitchTrivialBranch(L, *BI, DT, LI, SE, MSSAU)) 1053 return Changed; 1054 1055 // Mark that we managed to unswitch something. 1056 Changed = true; 1057 1058 // If we only unswitched some of the conditions feeding the branch, we won't 1059 // have collapsed it to a single successor. 1060 BI = cast<BranchInst>(CurrentBB->getTerminator()); 1061 if (BI->isConditional()) 1062 return Changed; 1063 1064 // Follow the newly unconditional branch into its successor. 1065 CurrentBB = BI->getSuccessor(0); 1066 1067 // When continuing, if we exit the loop or reach a previous visited block, 1068 // then we can not reach any trivial condition candidates (unfoldable 1069 // branch instructions or switch instructions) and no unswitch can happen. 1070 } while (L.contains(CurrentBB) && Visited.insert(CurrentBB).second); 1071 1072 return Changed; 1073 } 1074 1075 /// Build the cloned blocks for an unswitched copy of the given loop. 1076 /// 1077 /// The cloned blocks are inserted before the loop preheader (`LoopPH`) and 1078 /// after the split block (`SplitBB`) that will be used to select between the 1079 /// cloned and original loop. 1080 /// 1081 /// This routine handles cloning all of the necessary loop blocks and exit 1082 /// blocks including rewriting their instructions and the relevant PHI nodes. 1083 /// Any loop blocks or exit blocks which are dominated by a different successor 1084 /// than the one for this clone of the loop blocks can be trivially skipped. We 1085 /// use the `DominatingSucc` map to determine whether a block satisfies that 1086 /// property with a simple map lookup. 1087 /// 1088 /// It also correctly creates the unconditional branch in the cloned 1089 /// unswitched parent block to only point at the unswitched successor. 1090 /// 1091 /// This does not handle most of the necessary updates to `LoopInfo`. Only exit 1092 /// block splitting is correctly reflected in `LoopInfo`, essentially all of 1093 /// the cloned blocks (and their loops) are left without full `LoopInfo` 1094 /// updates. This also doesn't fully update `DominatorTree`. It adds the cloned 1095 /// blocks to them but doesn't create the cloned `DominatorTree` structure and 1096 /// instead the caller must recompute an accurate DT. It *does* correctly 1097 /// update the `AssumptionCache` provided in `AC`. 1098 static BasicBlock *buildClonedLoopBlocks( 1099 Loop &L, BasicBlock *LoopPH, BasicBlock *SplitBB, 1100 ArrayRef<BasicBlock *> ExitBlocks, BasicBlock *ParentBB, 1101 BasicBlock *UnswitchedSuccBB, BasicBlock *ContinueSuccBB, 1102 const SmallDenseMap<BasicBlock *, BasicBlock *, 16> &DominatingSucc, 1103 ValueToValueMapTy &VMap, 1104 SmallVectorImpl<DominatorTree::UpdateType> &DTUpdates, AssumptionCache &AC, 1105 DominatorTree &DT, LoopInfo &LI, MemorySSAUpdater *MSSAU) { 1106 SmallVector<BasicBlock *, 4> NewBlocks; 1107 NewBlocks.reserve(L.getNumBlocks() + ExitBlocks.size()); 1108 1109 // We will need to clone a bunch of blocks, wrap up the clone operation in 1110 // a helper. 1111 auto CloneBlock = [&](BasicBlock *OldBB) { 1112 // Clone the basic block and insert it before the new preheader. 1113 BasicBlock *NewBB = CloneBasicBlock(OldBB, VMap, ".us", OldBB->getParent()); 1114 NewBB->moveBefore(LoopPH); 1115 1116 // Record this block and the mapping. 1117 NewBlocks.push_back(NewBB); 1118 VMap[OldBB] = NewBB; 1119 1120 return NewBB; 1121 }; 1122 1123 // We skip cloning blocks when they have a dominating succ that is not the 1124 // succ we are cloning for. 1125 auto SkipBlock = [&](BasicBlock *BB) { 1126 auto It = DominatingSucc.find(BB); 1127 return It != DominatingSucc.end() && It->second != UnswitchedSuccBB; 1128 }; 1129 1130 // First, clone the preheader. 1131 auto *ClonedPH = CloneBlock(LoopPH); 1132 1133 // Then clone all the loop blocks, skipping the ones that aren't necessary. 1134 for (auto *LoopBB : L.blocks()) 1135 if (!SkipBlock(LoopBB)) 1136 CloneBlock(LoopBB); 1137 1138 // Split all the loop exit edges so that when we clone the exit blocks, if 1139 // any of the exit blocks are *also* a preheader for some other loop, we 1140 // don't create multiple predecessors entering the loop header. 1141 for (auto *ExitBB : ExitBlocks) { 1142 if (SkipBlock(ExitBB)) 1143 continue; 1144 1145 // When we are going to clone an exit, we don't need to clone all the 1146 // instructions in the exit block and we want to ensure we have an easy 1147 // place to merge the CFG, so split the exit first. This is always safe to 1148 // do because there cannot be any non-loop predecessors of a loop exit in 1149 // loop simplified form. 1150 auto *MergeBB = SplitBlock(ExitBB, &ExitBB->front(), &DT, &LI, MSSAU); 1151 1152 // Rearrange the names to make it easier to write test cases by having the 1153 // exit block carry the suffix rather than the merge block carrying the 1154 // suffix. 1155 MergeBB->takeName(ExitBB); 1156 ExitBB->setName(Twine(MergeBB->getName()) + ".split"); 1157 1158 // Now clone the original exit block. 1159 auto *ClonedExitBB = CloneBlock(ExitBB); 1160 assert(ClonedExitBB->getTerminator()->getNumSuccessors() == 1 && 1161 "Exit block should have been split to have one successor!"); 1162 assert(ClonedExitBB->getTerminator()->getSuccessor(0) == MergeBB && 1163 "Cloned exit block has the wrong successor!"); 1164 1165 // Remap any cloned instructions and create a merge phi node for them. 1166 for (auto ZippedInsts : llvm::zip_first( 1167 llvm::make_range(ExitBB->begin(), std::prev(ExitBB->end())), 1168 llvm::make_range(ClonedExitBB->begin(), 1169 std::prev(ClonedExitBB->end())))) { 1170 Instruction &I = std::get<0>(ZippedInsts); 1171 Instruction &ClonedI = std::get<1>(ZippedInsts); 1172 1173 // The only instructions in the exit block should be PHI nodes and 1174 // potentially a landing pad. 1175 assert( 1176 (isa<PHINode>(I) || isa<LandingPadInst>(I) || isa<CatchPadInst>(I)) && 1177 "Bad instruction in exit block!"); 1178 // We should have a value map between the instruction and its clone. 1179 assert(VMap.lookup(&I) == &ClonedI && "Mismatch in the value map!"); 1180 1181 auto *MergePN = 1182 PHINode::Create(I.getType(), /*NumReservedValues*/ 2, ".us-phi", 1183 &*MergeBB->getFirstInsertionPt()); 1184 I.replaceAllUsesWith(MergePN); 1185 MergePN->addIncoming(&I, ExitBB); 1186 MergePN->addIncoming(&ClonedI, ClonedExitBB); 1187 } 1188 } 1189 1190 // Rewrite the instructions in the cloned blocks to refer to the instructions 1191 // in the cloned blocks. We have to do this as a second pass so that we have 1192 // everything available. Also, we have inserted new instructions which may 1193 // include assume intrinsics, so we update the assumption cache while 1194 // processing this. 1195 for (auto *ClonedBB : NewBlocks) 1196 for (Instruction &I : *ClonedBB) { 1197 RemapInstruction(&I, VMap, 1198 RF_NoModuleLevelChanges | RF_IgnoreMissingLocals); 1199 if (auto *II = dyn_cast<AssumeInst>(&I)) 1200 AC.registerAssumption(II); 1201 } 1202 1203 // Update any PHI nodes in the cloned successors of the skipped blocks to not 1204 // have spurious incoming values. 1205 for (auto *LoopBB : L.blocks()) 1206 if (SkipBlock(LoopBB)) 1207 for (auto *SuccBB : successors(LoopBB)) 1208 if (auto *ClonedSuccBB = cast_or_null<BasicBlock>(VMap.lookup(SuccBB))) 1209 for (PHINode &PN : ClonedSuccBB->phis()) 1210 PN.removeIncomingValue(LoopBB, /*DeletePHIIfEmpty*/ false); 1211 1212 // Remove the cloned parent as a predecessor of any successor we ended up 1213 // cloning other than the unswitched one. 1214 auto *ClonedParentBB = cast<BasicBlock>(VMap.lookup(ParentBB)); 1215 for (auto *SuccBB : successors(ParentBB)) { 1216 if (SuccBB == UnswitchedSuccBB) 1217 continue; 1218 1219 auto *ClonedSuccBB = cast_or_null<BasicBlock>(VMap.lookup(SuccBB)); 1220 if (!ClonedSuccBB) 1221 continue; 1222 1223 ClonedSuccBB->removePredecessor(ClonedParentBB, 1224 /*KeepOneInputPHIs*/ true); 1225 } 1226 1227 // Replace the cloned branch with an unconditional branch to the cloned 1228 // unswitched successor. 1229 auto *ClonedSuccBB = cast<BasicBlock>(VMap.lookup(UnswitchedSuccBB)); 1230 Instruction *ClonedTerminator = ClonedParentBB->getTerminator(); 1231 // Trivial Simplification. If Terminator is a conditional branch and 1232 // condition becomes dead - erase it. 1233 Value *ClonedConditionToErase = nullptr; 1234 if (auto *BI = dyn_cast<BranchInst>(ClonedTerminator)) 1235 ClonedConditionToErase = BI->getCondition(); 1236 else if (auto *SI = dyn_cast<SwitchInst>(ClonedTerminator)) 1237 ClonedConditionToErase = SI->getCondition(); 1238 1239 ClonedTerminator->eraseFromParent(); 1240 BranchInst::Create(ClonedSuccBB, ClonedParentBB); 1241 1242 if (ClonedConditionToErase) 1243 RecursivelyDeleteTriviallyDeadInstructions(ClonedConditionToErase, nullptr, 1244 MSSAU); 1245 1246 // If there are duplicate entries in the PHI nodes because of multiple edges 1247 // to the unswitched successor, we need to nuke all but one as we replaced it 1248 // with a direct branch. 1249 for (PHINode &PN : ClonedSuccBB->phis()) { 1250 bool Found = false; 1251 // Loop over the incoming operands backwards so we can easily delete as we 1252 // go without invalidating the index. 1253 for (int i = PN.getNumOperands() - 1; i >= 0; --i) { 1254 if (PN.getIncomingBlock(i) != ClonedParentBB) 1255 continue; 1256 if (!Found) { 1257 Found = true; 1258 continue; 1259 } 1260 PN.removeIncomingValue(i, /*DeletePHIIfEmpty*/ false); 1261 } 1262 } 1263 1264 // Record the domtree updates for the new blocks. 1265 SmallPtrSet<BasicBlock *, 4> SuccSet; 1266 for (auto *ClonedBB : NewBlocks) { 1267 for (auto *SuccBB : successors(ClonedBB)) 1268 if (SuccSet.insert(SuccBB).second) 1269 DTUpdates.push_back({DominatorTree::Insert, ClonedBB, SuccBB}); 1270 SuccSet.clear(); 1271 } 1272 1273 return ClonedPH; 1274 } 1275 1276 /// Recursively clone the specified loop and all of its children. 1277 /// 1278 /// The target parent loop for the clone should be provided, or can be null if 1279 /// the clone is a top-level loop. While cloning, all the blocks are mapped 1280 /// with the provided value map. The entire original loop must be present in 1281 /// the value map. The cloned loop is returned. 1282 static Loop *cloneLoopNest(Loop &OrigRootL, Loop *RootParentL, 1283 const ValueToValueMapTy &VMap, LoopInfo &LI) { 1284 auto AddClonedBlocksToLoop = [&](Loop &OrigL, Loop &ClonedL) { 1285 assert(ClonedL.getBlocks().empty() && "Must start with an empty loop!"); 1286 ClonedL.reserveBlocks(OrigL.getNumBlocks()); 1287 for (auto *BB : OrigL.blocks()) { 1288 auto *ClonedBB = cast<BasicBlock>(VMap.lookup(BB)); 1289 ClonedL.addBlockEntry(ClonedBB); 1290 if (LI.getLoopFor(BB) == &OrigL) 1291 LI.changeLoopFor(ClonedBB, &ClonedL); 1292 } 1293 }; 1294 1295 // We specially handle the first loop because it may get cloned into 1296 // a different parent and because we most commonly are cloning leaf loops. 1297 Loop *ClonedRootL = LI.AllocateLoop(); 1298 if (RootParentL) 1299 RootParentL->addChildLoop(ClonedRootL); 1300 else 1301 LI.addTopLevelLoop(ClonedRootL); 1302 AddClonedBlocksToLoop(OrigRootL, *ClonedRootL); 1303 1304 if (OrigRootL.isInnermost()) 1305 return ClonedRootL; 1306 1307 // If we have a nest, we can quickly clone the entire loop nest using an 1308 // iterative approach because it is a tree. We keep the cloned parent in the 1309 // data structure to avoid repeatedly querying through a map to find it. 1310 SmallVector<std::pair<Loop *, Loop *>, 16> LoopsToClone; 1311 // Build up the loops to clone in reverse order as we'll clone them from the 1312 // back. 1313 for (Loop *ChildL : llvm::reverse(OrigRootL)) 1314 LoopsToClone.push_back({ClonedRootL, ChildL}); 1315 do { 1316 Loop *ClonedParentL, *L; 1317 std::tie(ClonedParentL, L) = LoopsToClone.pop_back_val(); 1318 Loop *ClonedL = LI.AllocateLoop(); 1319 ClonedParentL->addChildLoop(ClonedL); 1320 AddClonedBlocksToLoop(*L, *ClonedL); 1321 for (Loop *ChildL : llvm::reverse(*L)) 1322 LoopsToClone.push_back({ClonedL, ChildL}); 1323 } while (!LoopsToClone.empty()); 1324 1325 return ClonedRootL; 1326 } 1327 1328 /// Build the cloned loops of an original loop from unswitching. 1329 /// 1330 /// Because unswitching simplifies the CFG of the loop, this isn't a trivial 1331 /// operation. We need to re-verify that there even is a loop (as the backedge 1332 /// may not have been cloned), and even if there are remaining backedges the 1333 /// backedge set may be different. However, we know that each child loop is 1334 /// undisturbed, we only need to find where to place each child loop within 1335 /// either any parent loop or within a cloned version of the original loop. 1336 /// 1337 /// Because child loops may end up cloned outside of any cloned version of the 1338 /// original loop, multiple cloned sibling loops may be created. All of them 1339 /// are returned so that the newly introduced loop nest roots can be 1340 /// identified. 1341 static void buildClonedLoops(Loop &OrigL, ArrayRef<BasicBlock *> ExitBlocks, 1342 const ValueToValueMapTy &VMap, LoopInfo &LI, 1343 SmallVectorImpl<Loop *> &NonChildClonedLoops) { 1344 Loop *ClonedL = nullptr; 1345 1346 auto *OrigPH = OrigL.getLoopPreheader(); 1347 auto *OrigHeader = OrigL.getHeader(); 1348 1349 auto *ClonedPH = cast<BasicBlock>(VMap.lookup(OrigPH)); 1350 auto *ClonedHeader = cast<BasicBlock>(VMap.lookup(OrigHeader)); 1351 1352 // We need to know the loops of the cloned exit blocks to even compute the 1353 // accurate parent loop. If we only clone exits to some parent of the 1354 // original parent, we want to clone into that outer loop. We also keep track 1355 // of the loops that our cloned exit blocks participate in. 1356 Loop *ParentL = nullptr; 1357 SmallVector<BasicBlock *, 4> ClonedExitsInLoops; 1358 SmallDenseMap<BasicBlock *, Loop *, 16> ExitLoopMap; 1359 ClonedExitsInLoops.reserve(ExitBlocks.size()); 1360 for (auto *ExitBB : ExitBlocks) 1361 if (auto *ClonedExitBB = cast_or_null<BasicBlock>(VMap.lookup(ExitBB))) 1362 if (Loop *ExitL = LI.getLoopFor(ExitBB)) { 1363 ExitLoopMap[ClonedExitBB] = ExitL; 1364 ClonedExitsInLoops.push_back(ClonedExitBB); 1365 if (!ParentL || (ParentL != ExitL && ParentL->contains(ExitL))) 1366 ParentL = ExitL; 1367 } 1368 assert((!ParentL || ParentL == OrigL.getParentLoop() || 1369 ParentL->contains(OrigL.getParentLoop())) && 1370 "The computed parent loop should always contain (or be) the parent of " 1371 "the original loop."); 1372 1373 // We build the set of blocks dominated by the cloned header from the set of 1374 // cloned blocks out of the original loop. While not all of these will 1375 // necessarily be in the cloned loop, it is enough to establish that they 1376 // aren't in unreachable cycles, etc. 1377 SmallSetVector<BasicBlock *, 16> ClonedLoopBlocks; 1378 for (auto *BB : OrigL.blocks()) 1379 if (auto *ClonedBB = cast_or_null<BasicBlock>(VMap.lookup(BB))) 1380 ClonedLoopBlocks.insert(ClonedBB); 1381 1382 // Rebuild the set of blocks that will end up in the cloned loop. We may have 1383 // skipped cloning some region of this loop which can in turn skip some of 1384 // the backedges so we have to rebuild the blocks in the loop based on the 1385 // backedges that remain after cloning. 1386 SmallVector<BasicBlock *, 16> Worklist; 1387 SmallPtrSet<BasicBlock *, 16> BlocksInClonedLoop; 1388 for (auto *Pred : predecessors(ClonedHeader)) { 1389 // The only possible non-loop header predecessor is the preheader because 1390 // we know we cloned the loop in simplified form. 1391 if (Pred == ClonedPH) 1392 continue; 1393 1394 // Because the loop was in simplified form, the only non-loop predecessor 1395 // should be the preheader. 1396 assert(ClonedLoopBlocks.count(Pred) && "Found a predecessor of the loop " 1397 "header other than the preheader " 1398 "that is not part of the loop!"); 1399 1400 // Insert this block into the loop set and on the first visit (and if it 1401 // isn't the header we're currently walking) put it into the worklist to 1402 // recurse through. 1403 if (BlocksInClonedLoop.insert(Pred).second && Pred != ClonedHeader) 1404 Worklist.push_back(Pred); 1405 } 1406 1407 // If we had any backedges then there *is* a cloned loop. Put the header into 1408 // the loop set and then walk the worklist backwards to find all the blocks 1409 // that remain within the loop after cloning. 1410 if (!BlocksInClonedLoop.empty()) { 1411 BlocksInClonedLoop.insert(ClonedHeader); 1412 1413 while (!Worklist.empty()) { 1414 BasicBlock *BB = Worklist.pop_back_val(); 1415 assert(BlocksInClonedLoop.count(BB) && 1416 "Didn't put block into the loop set!"); 1417 1418 // Insert any predecessors that are in the possible set into the cloned 1419 // set, and if the insert is successful, add them to the worklist. Note 1420 // that we filter on the blocks that are definitely reachable via the 1421 // backedge to the loop header so we may prune out dead code within the 1422 // cloned loop. 1423 for (auto *Pred : predecessors(BB)) 1424 if (ClonedLoopBlocks.count(Pred) && 1425 BlocksInClonedLoop.insert(Pred).second) 1426 Worklist.push_back(Pred); 1427 } 1428 1429 ClonedL = LI.AllocateLoop(); 1430 if (ParentL) { 1431 ParentL->addBasicBlockToLoop(ClonedPH, LI); 1432 ParentL->addChildLoop(ClonedL); 1433 } else { 1434 LI.addTopLevelLoop(ClonedL); 1435 } 1436 NonChildClonedLoops.push_back(ClonedL); 1437 1438 ClonedL->reserveBlocks(BlocksInClonedLoop.size()); 1439 // We don't want to just add the cloned loop blocks based on how we 1440 // discovered them. The original order of blocks was carefully built in 1441 // a way that doesn't rely on predecessor ordering. Rather than re-invent 1442 // that logic, we just re-walk the original blocks (and those of the child 1443 // loops) and filter them as we add them into the cloned loop. 1444 for (auto *BB : OrigL.blocks()) { 1445 auto *ClonedBB = cast_or_null<BasicBlock>(VMap.lookup(BB)); 1446 if (!ClonedBB || !BlocksInClonedLoop.count(ClonedBB)) 1447 continue; 1448 1449 // Directly add the blocks that are only in this loop. 1450 if (LI.getLoopFor(BB) == &OrigL) { 1451 ClonedL->addBasicBlockToLoop(ClonedBB, LI); 1452 continue; 1453 } 1454 1455 // We want to manually add it to this loop and parents. 1456 // Registering it with LoopInfo will happen when we clone the top 1457 // loop for this block. 1458 for (Loop *PL = ClonedL; PL; PL = PL->getParentLoop()) 1459 PL->addBlockEntry(ClonedBB); 1460 } 1461 1462 // Now add each child loop whose header remains within the cloned loop. All 1463 // of the blocks within the loop must satisfy the same constraints as the 1464 // header so once we pass the header checks we can just clone the entire 1465 // child loop nest. 1466 for (Loop *ChildL : OrigL) { 1467 auto *ClonedChildHeader = 1468 cast_or_null<BasicBlock>(VMap.lookup(ChildL->getHeader())); 1469 if (!ClonedChildHeader || !BlocksInClonedLoop.count(ClonedChildHeader)) 1470 continue; 1471 1472 #ifndef NDEBUG 1473 // We should never have a cloned child loop header but fail to have 1474 // all of the blocks for that child loop. 1475 for (auto *ChildLoopBB : ChildL->blocks()) 1476 assert(BlocksInClonedLoop.count( 1477 cast<BasicBlock>(VMap.lookup(ChildLoopBB))) && 1478 "Child cloned loop has a header within the cloned outer " 1479 "loop but not all of its blocks!"); 1480 #endif 1481 1482 cloneLoopNest(*ChildL, ClonedL, VMap, LI); 1483 } 1484 } 1485 1486 // Now that we've handled all the components of the original loop that were 1487 // cloned into a new loop, we still need to handle anything from the original 1488 // loop that wasn't in a cloned loop. 1489 1490 // Figure out what blocks are left to place within any loop nest containing 1491 // the unswitched loop. If we never formed a loop, the cloned PH is one of 1492 // them. 1493 SmallPtrSet<BasicBlock *, 16> UnloopedBlockSet; 1494 if (BlocksInClonedLoop.empty()) 1495 UnloopedBlockSet.insert(ClonedPH); 1496 for (auto *ClonedBB : ClonedLoopBlocks) 1497 if (!BlocksInClonedLoop.count(ClonedBB)) 1498 UnloopedBlockSet.insert(ClonedBB); 1499 1500 // Copy the cloned exits and sort them in ascending loop depth, we'll work 1501 // backwards across these to process them inside out. The order shouldn't 1502 // matter as we're just trying to build up the map from inside-out; we use 1503 // the map in a more stably ordered way below. 1504 auto OrderedClonedExitsInLoops = ClonedExitsInLoops; 1505 llvm::sort(OrderedClonedExitsInLoops, [&](BasicBlock *LHS, BasicBlock *RHS) { 1506 return ExitLoopMap.lookup(LHS)->getLoopDepth() < 1507 ExitLoopMap.lookup(RHS)->getLoopDepth(); 1508 }); 1509 1510 // Populate the existing ExitLoopMap with everything reachable from each 1511 // exit, starting from the inner most exit. 1512 while (!UnloopedBlockSet.empty() && !OrderedClonedExitsInLoops.empty()) { 1513 assert(Worklist.empty() && "Didn't clear worklist!"); 1514 1515 BasicBlock *ExitBB = OrderedClonedExitsInLoops.pop_back_val(); 1516 Loop *ExitL = ExitLoopMap.lookup(ExitBB); 1517 1518 // Walk the CFG back until we hit the cloned PH adding everything reachable 1519 // and in the unlooped set to this exit block's loop. 1520 Worklist.push_back(ExitBB); 1521 do { 1522 BasicBlock *BB = Worklist.pop_back_val(); 1523 // We can stop recursing at the cloned preheader (if we get there). 1524 if (BB == ClonedPH) 1525 continue; 1526 1527 for (BasicBlock *PredBB : predecessors(BB)) { 1528 // If this pred has already been moved to our set or is part of some 1529 // (inner) loop, no update needed. 1530 if (!UnloopedBlockSet.erase(PredBB)) { 1531 assert( 1532 (BlocksInClonedLoop.count(PredBB) || ExitLoopMap.count(PredBB)) && 1533 "Predecessor not mapped to a loop!"); 1534 continue; 1535 } 1536 1537 // We just insert into the loop set here. We'll add these blocks to the 1538 // exit loop after we build up the set in an order that doesn't rely on 1539 // predecessor order (which in turn relies on use list order). 1540 bool Inserted = ExitLoopMap.insert({PredBB, ExitL}).second; 1541 (void)Inserted; 1542 assert(Inserted && "Should only visit an unlooped block once!"); 1543 1544 // And recurse through to its predecessors. 1545 Worklist.push_back(PredBB); 1546 } 1547 } while (!Worklist.empty()); 1548 } 1549 1550 // Now that the ExitLoopMap gives as mapping for all the non-looping cloned 1551 // blocks to their outer loops, walk the cloned blocks and the cloned exits 1552 // in their original order adding them to the correct loop. 1553 1554 // We need a stable insertion order. We use the order of the original loop 1555 // order and map into the correct parent loop. 1556 for (auto *BB : llvm::concat<BasicBlock *const>( 1557 makeArrayRef(ClonedPH), ClonedLoopBlocks, ClonedExitsInLoops)) 1558 if (Loop *OuterL = ExitLoopMap.lookup(BB)) 1559 OuterL->addBasicBlockToLoop(BB, LI); 1560 1561 #ifndef NDEBUG 1562 for (auto &BBAndL : ExitLoopMap) { 1563 auto *BB = BBAndL.first; 1564 auto *OuterL = BBAndL.second; 1565 assert(LI.getLoopFor(BB) == OuterL && 1566 "Failed to put all blocks into outer loops!"); 1567 } 1568 #endif 1569 1570 // Now that all the blocks are placed into the correct containing loop in the 1571 // absence of child loops, find all the potentially cloned child loops and 1572 // clone them into whatever outer loop we placed their header into. 1573 for (Loop *ChildL : OrigL) { 1574 auto *ClonedChildHeader = 1575 cast_or_null<BasicBlock>(VMap.lookup(ChildL->getHeader())); 1576 if (!ClonedChildHeader || BlocksInClonedLoop.count(ClonedChildHeader)) 1577 continue; 1578 1579 #ifndef NDEBUG 1580 for (auto *ChildLoopBB : ChildL->blocks()) 1581 assert(VMap.count(ChildLoopBB) && 1582 "Cloned a child loop header but not all of that loops blocks!"); 1583 #endif 1584 1585 NonChildClonedLoops.push_back(cloneLoopNest( 1586 *ChildL, ExitLoopMap.lookup(ClonedChildHeader), VMap, LI)); 1587 } 1588 } 1589 1590 static void 1591 deleteDeadClonedBlocks(Loop &L, ArrayRef<BasicBlock *> ExitBlocks, 1592 ArrayRef<std::unique_ptr<ValueToValueMapTy>> VMaps, 1593 DominatorTree &DT, MemorySSAUpdater *MSSAU) { 1594 // Find all the dead clones, and remove them from their successors. 1595 SmallVector<BasicBlock *, 16> DeadBlocks; 1596 for (BasicBlock *BB : llvm::concat<BasicBlock *const>(L.blocks(), ExitBlocks)) 1597 for (const auto &VMap : VMaps) 1598 if (BasicBlock *ClonedBB = cast_or_null<BasicBlock>(VMap->lookup(BB))) 1599 if (!DT.isReachableFromEntry(ClonedBB)) { 1600 for (BasicBlock *SuccBB : successors(ClonedBB)) 1601 SuccBB->removePredecessor(ClonedBB); 1602 DeadBlocks.push_back(ClonedBB); 1603 } 1604 1605 // Remove all MemorySSA in the dead blocks 1606 if (MSSAU) { 1607 SmallSetVector<BasicBlock *, 8> DeadBlockSet(DeadBlocks.begin(), 1608 DeadBlocks.end()); 1609 MSSAU->removeBlocks(DeadBlockSet); 1610 } 1611 1612 // Drop any remaining references to break cycles. 1613 for (BasicBlock *BB : DeadBlocks) 1614 BB->dropAllReferences(); 1615 // Erase them from the IR. 1616 for (BasicBlock *BB : DeadBlocks) 1617 BB->eraseFromParent(); 1618 } 1619 1620 static void 1621 deleteDeadBlocksFromLoop(Loop &L, 1622 SmallVectorImpl<BasicBlock *> &ExitBlocks, 1623 DominatorTree &DT, LoopInfo &LI, 1624 MemorySSAUpdater *MSSAU, 1625 ScalarEvolution *SE, 1626 function_ref<void(Loop &, StringRef)> DestroyLoopCB) { 1627 // Find all the dead blocks tied to this loop, and remove them from their 1628 // successors. 1629 SmallSetVector<BasicBlock *, 8> DeadBlockSet; 1630 1631 // Start with loop/exit blocks and get a transitive closure of reachable dead 1632 // blocks. 1633 SmallVector<BasicBlock *, 16> DeathCandidates(ExitBlocks.begin(), 1634 ExitBlocks.end()); 1635 DeathCandidates.append(L.blocks().begin(), L.blocks().end()); 1636 while (!DeathCandidates.empty()) { 1637 auto *BB = DeathCandidates.pop_back_val(); 1638 if (!DeadBlockSet.count(BB) && !DT.isReachableFromEntry(BB)) { 1639 for (BasicBlock *SuccBB : successors(BB)) { 1640 SuccBB->removePredecessor(BB); 1641 DeathCandidates.push_back(SuccBB); 1642 } 1643 DeadBlockSet.insert(BB); 1644 } 1645 } 1646 1647 // Remove all MemorySSA in the dead blocks 1648 if (MSSAU) 1649 MSSAU->removeBlocks(DeadBlockSet); 1650 1651 // Filter out the dead blocks from the exit blocks list so that it can be 1652 // used in the caller. 1653 llvm::erase_if(ExitBlocks, 1654 [&](BasicBlock *BB) { return DeadBlockSet.count(BB); }); 1655 1656 // Walk from this loop up through its parents removing all of the dead blocks. 1657 for (Loop *ParentL = &L; ParentL; ParentL = ParentL->getParentLoop()) { 1658 for (auto *BB : DeadBlockSet) 1659 ParentL->getBlocksSet().erase(BB); 1660 llvm::erase_if(ParentL->getBlocksVector(), 1661 [&](BasicBlock *BB) { return DeadBlockSet.count(BB); }); 1662 } 1663 1664 // Now delete the dead child loops. This raw delete will clear them 1665 // recursively. 1666 llvm::erase_if(L.getSubLoopsVector(), [&](Loop *ChildL) { 1667 if (!DeadBlockSet.count(ChildL->getHeader())) 1668 return false; 1669 1670 assert(llvm::all_of(ChildL->blocks(), 1671 [&](BasicBlock *ChildBB) { 1672 return DeadBlockSet.count(ChildBB); 1673 }) && 1674 "If the child loop header is dead all blocks in the child loop must " 1675 "be dead as well!"); 1676 DestroyLoopCB(*ChildL, ChildL->getName()); 1677 if (SE) 1678 SE->forgetBlockAndLoopDispositions(); 1679 LI.destroy(ChildL); 1680 return true; 1681 }); 1682 1683 // Remove the loop mappings for the dead blocks and drop all the references 1684 // from these blocks to others to handle cyclic references as we start 1685 // deleting the blocks themselves. 1686 for (auto *BB : DeadBlockSet) { 1687 // Check that the dominator tree has already been updated. 1688 assert(!DT.getNode(BB) && "Should already have cleared domtree!"); 1689 LI.changeLoopFor(BB, nullptr); 1690 // Drop all uses of the instructions to make sure we won't have dangling 1691 // uses in other blocks. 1692 for (auto &I : *BB) 1693 if (!I.use_empty()) 1694 I.replaceAllUsesWith(PoisonValue::get(I.getType())); 1695 BB->dropAllReferences(); 1696 } 1697 1698 // Actually delete the blocks now that they've been fully unhooked from the 1699 // IR. 1700 for (auto *BB : DeadBlockSet) 1701 BB->eraseFromParent(); 1702 } 1703 1704 /// Recompute the set of blocks in a loop after unswitching. 1705 /// 1706 /// This walks from the original headers predecessors to rebuild the loop. We 1707 /// take advantage of the fact that new blocks can't have been added, and so we 1708 /// filter by the original loop's blocks. This also handles potentially 1709 /// unreachable code that we don't want to explore but might be found examining 1710 /// the predecessors of the header. 1711 /// 1712 /// If the original loop is no longer a loop, this will return an empty set. If 1713 /// it remains a loop, all the blocks within it will be added to the set 1714 /// (including those blocks in inner loops). 1715 static SmallPtrSet<const BasicBlock *, 16> recomputeLoopBlockSet(Loop &L, 1716 LoopInfo &LI) { 1717 SmallPtrSet<const BasicBlock *, 16> LoopBlockSet; 1718 1719 auto *PH = L.getLoopPreheader(); 1720 auto *Header = L.getHeader(); 1721 1722 // A worklist to use while walking backwards from the header. 1723 SmallVector<BasicBlock *, 16> Worklist; 1724 1725 // First walk the predecessors of the header to find the backedges. This will 1726 // form the basis of our walk. 1727 for (auto *Pred : predecessors(Header)) { 1728 // Skip the preheader. 1729 if (Pred == PH) 1730 continue; 1731 1732 // Because the loop was in simplified form, the only non-loop predecessor 1733 // is the preheader. 1734 assert(L.contains(Pred) && "Found a predecessor of the loop header other " 1735 "than the preheader that is not part of the " 1736 "loop!"); 1737 1738 // Insert this block into the loop set and on the first visit and, if it 1739 // isn't the header we're currently walking, put it into the worklist to 1740 // recurse through. 1741 if (LoopBlockSet.insert(Pred).second && Pred != Header) 1742 Worklist.push_back(Pred); 1743 } 1744 1745 // If no backedges were found, we're done. 1746 if (LoopBlockSet.empty()) 1747 return LoopBlockSet; 1748 1749 // We found backedges, recurse through them to identify the loop blocks. 1750 while (!Worklist.empty()) { 1751 BasicBlock *BB = Worklist.pop_back_val(); 1752 assert(LoopBlockSet.count(BB) && "Didn't put block into the loop set!"); 1753 1754 // No need to walk past the header. 1755 if (BB == Header) 1756 continue; 1757 1758 // Because we know the inner loop structure remains valid we can use the 1759 // loop structure to jump immediately across the entire nested loop. 1760 // Further, because it is in loop simplified form, we can directly jump 1761 // to its preheader afterward. 1762 if (Loop *InnerL = LI.getLoopFor(BB)) 1763 if (InnerL != &L) { 1764 assert(L.contains(InnerL) && 1765 "Should not reach a loop *outside* this loop!"); 1766 // The preheader is the only possible predecessor of the loop so 1767 // insert it into the set and check whether it was already handled. 1768 auto *InnerPH = InnerL->getLoopPreheader(); 1769 assert(L.contains(InnerPH) && "Cannot contain an inner loop block " 1770 "but not contain the inner loop " 1771 "preheader!"); 1772 if (!LoopBlockSet.insert(InnerPH).second) 1773 // The only way to reach the preheader is through the loop body 1774 // itself so if it has been visited the loop is already handled. 1775 continue; 1776 1777 // Insert all of the blocks (other than those already present) into 1778 // the loop set. We expect at least the block that led us to find the 1779 // inner loop to be in the block set, but we may also have other loop 1780 // blocks if they were already enqueued as predecessors of some other 1781 // outer loop block. 1782 for (auto *InnerBB : InnerL->blocks()) { 1783 if (InnerBB == BB) { 1784 assert(LoopBlockSet.count(InnerBB) && 1785 "Block should already be in the set!"); 1786 continue; 1787 } 1788 1789 LoopBlockSet.insert(InnerBB); 1790 } 1791 1792 // Add the preheader to the worklist so we will continue past the 1793 // loop body. 1794 Worklist.push_back(InnerPH); 1795 continue; 1796 } 1797 1798 // Insert any predecessors that were in the original loop into the new 1799 // set, and if the insert is successful, add them to the worklist. 1800 for (auto *Pred : predecessors(BB)) 1801 if (L.contains(Pred) && LoopBlockSet.insert(Pred).second) 1802 Worklist.push_back(Pred); 1803 } 1804 1805 assert(LoopBlockSet.count(Header) && "Cannot fail to add the header!"); 1806 1807 // We've found all the blocks participating in the loop, return our completed 1808 // set. 1809 return LoopBlockSet; 1810 } 1811 1812 /// Rebuild a loop after unswitching removes some subset of blocks and edges. 1813 /// 1814 /// The removal may have removed some child loops entirely but cannot have 1815 /// disturbed any remaining child loops. However, they may need to be hoisted 1816 /// to the parent loop (or to be top-level loops). The original loop may be 1817 /// completely removed. 1818 /// 1819 /// The sibling loops resulting from this update are returned. If the original 1820 /// loop remains a valid loop, it will be the first entry in this list with all 1821 /// of the newly sibling loops following it. 1822 /// 1823 /// Returns true if the loop remains a loop after unswitching, and false if it 1824 /// is no longer a loop after unswitching (and should not continue to be 1825 /// referenced). 1826 static bool rebuildLoopAfterUnswitch(Loop &L, ArrayRef<BasicBlock *> ExitBlocks, 1827 LoopInfo &LI, 1828 SmallVectorImpl<Loop *> &HoistedLoops, 1829 ScalarEvolution *SE) { 1830 auto *PH = L.getLoopPreheader(); 1831 1832 // Compute the actual parent loop from the exit blocks. Because we may have 1833 // pruned some exits the loop may be different from the original parent. 1834 Loop *ParentL = nullptr; 1835 SmallVector<Loop *, 4> ExitLoops; 1836 SmallVector<BasicBlock *, 4> ExitsInLoops; 1837 ExitsInLoops.reserve(ExitBlocks.size()); 1838 for (auto *ExitBB : ExitBlocks) 1839 if (Loop *ExitL = LI.getLoopFor(ExitBB)) { 1840 ExitLoops.push_back(ExitL); 1841 ExitsInLoops.push_back(ExitBB); 1842 if (!ParentL || (ParentL != ExitL && ParentL->contains(ExitL))) 1843 ParentL = ExitL; 1844 } 1845 1846 // Recompute the blocks participating in this loop. This may be empty if it 1847 // is no longer a loop. 1848 auto LoopBlockSet = recomputeLoopBlockSet(L, LI); 1849 1850 // If we still have a loop, we need to re-set the loop's parent as the exit 1851 // block set changing may have moved it within the loop nest. Note that this 1852 // can only happen when this loop has a parent as it can only hoist the loop 1853 // *up* the nest. 1854 if (!LoopBlockSet.empty() && L.getParentLoop() != ParentL) { 1855 // Remove this loop's (original) blocks from all of the intervening loops. 1856 for (Loop *IL = L.getParentLoop(); IL != ParentL; 1857 IL = IL->getParentLoop()) { 1858 IL->getBlocksSet().erase(PH); 1859 for (auto *BB : L.blocks()) 1860 IL->getBlocksSet().erase(BB); 1861 llvm::erase_if(IL->getBlocksVector(), [&](BasicBlock *BB) { 1862 return BB == PH || L.contains(BB); 1863 }); 1864 } 1865 1866 LI.changeLoopFor(PH, ParentL); 1867 L.getParentLoop()->removeChildLoop(&L); 1868 if (ParentL) 1869 ParentL->addChildLoop(&L); 1870 else 1871 LI.addTopLevelLoop(&L); 1872 } 1873 1874 // Now we update all the blocks which are no longer within the loop. 1875 auto &Blocks = L.getBlocksVector(); 1876 auto BlocksSplitI = 1877 LoopBlockSet.empty() 1878 ? Blocks.begin() 1879 : std::stable_partition( 1880 Blocks.begin(), Blocks.end(), 1881 [&](BasicBlock *BB) { return LoopBlockSet.count(BB); }); 1882 1883 // Before we erase the list of unlooped blocks, build a set of them. 1884 SmallPtrSet<BasicBlock *, 16> UnloopedBlocks(BlocksSplitI, Blocks.end()); 1885 if (LoopBlockSet.empty()) 1886 UnloopedBlocks.insert(PH); 1887 1888 // Now erase these blocks from the loop. 1889 for (auto *BB : make_range(BlocksSplitI, Blocks.end())) 1890 L.getBlocksSet().erase(BB); 1891 Blocks.erase(BlocksSplitI, Blocks.end()); 1892 1893 // Sort the exits in ascending loop depth, we'll work backwards across these 1894 // to process them inside out. 1895 llvm::stable_sort(ExitsInLoops, [&](BasicBlock *LHS, BasicBlock *RHS) { 1896 return LI.getLoopDepth(LHS) < LI.getLoopDepth(RHS); 1897 }); 1898 1899 // We'll build up a set for each exit loop. 1900 SmallPtrSet<BasicBlock *, 16> NewExitLoopBlocks; 1901 Loop *PrevExitL = L.getParentLoop(); // The deepest possible exit loop. 1902 1903 auto RemoveUnloopedBlocksFromLoop = 1904 [](Loop &L, SmallPtrSetImpl<BasicBlock *> &UnloopedBlocks) { 1905 for (auto *BB : UnloopedBlocks) 1906 L.getBlocksSet().erase(BB); 1907 llvm::erase_if(L.getBlocksVector(), [&](BasicBlock *BB) { 1908 return UnloopedBlocks.count(BB); 1909 }); 1910 }; 1911 1912 SmallVector<BasicBlock *, 16> Worklist; 1913 while (!UnloopedBlocks.empty() && !ExitsInLoops.empty()) { 1914 assert(Worklist.empty() && "Didn't clear worklist!"); 1915 assert(NewExitLoopBlocks.empty() && "Didn't clear loop set!"); 1916 1917 // Grab the next exit block, in decreasing loop depth order. 1918 BasicBlock *ExitBB = ExitsInLoops.pop_back_val(); 1919 Loop &ExitL = *LI.getLoopFor(ExitBB); 1920 assert(ExitL.contains(&L) && "Exit loop must contain the inner loop!"); 1921 1922 // Erase all of the unlooped blocks from the loops between the previous 1923 // exit loop and this exit loop. This works because the ExitInLoops list is 1924 // sorted in increasing order of loop depth and thus we visit loops in 1925 // decreasing order of loop depth. 1926 for (; PrevExitL != &ExitL; PrevExitL = PrevExitL->getParentLoop()) 1927 RemoveUnloopedBlocksFromLoop(*PrevExitL, UnloopedBlocks); 1928 1929 // Walk the CFG back until we hit the cloned PH adding everything reachable 1930 // and in the unlooped set to this exit block's loop. 1931 Worklist.push_back(ExitBB); 1932 do { 1933 BasicBlock *BB = Worklist.pop_back_val(); 1934 // We can stop recursing at the cloned preheader (if we get there). 1935 if (BB == PH) 1936 continue; 1937 1938 for (BasicBlock *PredBB : predecessors(BB)) { 1939 // If this pred has already been moved to our set or is part of some 1940 // (inner) loop, no update needed. 1941 if (!UnloopedBlocks.erase(PredBB)) { 1942 assert((NewExitLoopBlocks.count(PredBB) || 1943 ExitL.contains(LI.getLoopFor(PredBB))) && 1944 "Predecessor not in a nested loop (or already visited)!"); 1945 continue; 1946 } 1947 1948 // We just insert into the loop set here. We'll add these blocks to the 1949 // exit loop after we build up the set in a deterministic order rather 1950 // than the predecessor-influenced visit order. 1951 bool Inserted = NewExitLoopBlocks.insert(PredBB).second; 1952 (void)Inserted; 1953 assert(Inserted && "Should only visit an unlooped block once!"); 1954 1955 // And recurse through to its predecessors. 1956 Worklist.push_back(PredBB); 1957 } 1958 } while (!Worklist.empty()); 1959 1960 // If blocks in this exit loop were directly part of the original loop (as 1961 // opposed to a child loop) update the map to point to this exit loop. This 1962 // just updates a map and so the fact that the order is unstable is fine. 1963 for (auto *BB : NewExitLoopBlocks) 1964 if (Loop *BBL = LI.getLoopFor(BB)) 1965 if (BBL == &L || !L.contains(BBL)) 1966 LI.changeLoopFor(BB, &ExitL); 1967 1968 // We will remove the remaining unlooped blocks from this loop in the next 1969 // iteration or below. 1970 NewExitLoopBlocks.clear(); 1971 } 1972 1973 // Any remaining unlooped blocks are no longer part of any loop unless they 1974 // are part of some child loop. 1975 for (; PrevExitL; PrevExitL = PrevExitL->getParentLoop()) 1976 RemoveUnloopedBlocksFromLoop(*PrevExitL, UnloopedBlocks); 1977 for (auto *BB : UnloopedBlocks) 1978 if (Loop *BBL = LI.getLoopFor(BB)) 1979 if (BBL == &L || !L.contains(BBL)) 1980 LI.changeLoopFor(BB, nullptr); 1981 1982 // Sink all the child loops whose headers are no longer in the loop set to 1983 // the parent (or to be top level loops). We reach into the loop and directly 1984 // update its subloop vector to make this batch update efficient. 1985 auto &SubLoops = L.getSubLoopsVector(); 1986 auto SubLoopsSplitI = 1987 LoopBlockSet.empty() 1988 ? SubLoops.begin() 1989 : std::stable_partition( 1990 SubLoops.begin(), SubLoops.end(), [&](Loop *SubL) { 1991 return LoopBlockSet.count(SubL->getHeader()); 1992 }); 1993 for (auto *HoistedL : make_range(SubLoopsSplitI, SubLoops.end())) { 1994 HoistedLoops.push_back(HoistedL); 1995 HoistedL->setParentLoop(nullptr); 1996 1997 // To compute the new parent of this hoisted loop we look at where we 1998 // placed the preheader above. We can't lookup the header itself because we 1999 // retained the mapping from the header to the hoisted loop. But the 2000 // preheader and header should have the exact same new parent computed 2001 // based on the set of exit blocks from the original loop as the preheader 2002 // is a predecessor of the header and so reached in the reverse walk. And 2003 // because the loops were all in simplified form the preheader of the 2004 // hoisted loop can't be part of some *other* loop. 2005 if (auto *NewParentL = LI.getLoopFor(HoistedL->getLoopPreheader())) 2006 NewParentL->addChildLoop(HoistedL); 2007 else 2008 LI.addTopLevelLoop(HoistedL); 2009 } 2010 SubLoops.erase(SubLoopsSplitI, SubLoops.end()); 2011 2012 // Actually delete the loop if nothing remained within it. 2013 if (Blocks.empty()) { 2014 assert(SubLoops.empty() && 2015 "Failed to remove all subloops from the original loop!"); 2016 if (Loop *ParentL = L.getParentLoop()) 2017 ParentL->removeChildLoop(llvm::find(*ParentL, &L)); 2018 else 2019 LI.removeLoop(llvm::find(LI, &L)); 2020 // markLoopAsDeleted for L should be triggered by the caller (it is typically 2021 // done by using the UnswitchCB callback). 2022 if (SE) 2023 SE->forgetBlockAndLoopDispositions(); 2024 LI.destroy(&L); 2025 return false; 2026 } 2027 2028 return true; 2029 } 2030 2031 /// Helper to visit a dominator subtree, invoking a callable on each node. 2032 /// 2033 /// Returning false at any point will stop walking past that node of the tree. 2034 template <typename CallableT> 2035 void visitDomSubTree(DominatorTree &DT, BasicBlock *BB, CallableT Callable) { 2036 SmallVector<DomTreeNode *, 4> DomWorklist; 2037 DomWorklist.push_back(DT[BB]); 2038 #ifndef NDEBUG 2039 SmallPtrSet<DomTreeNode *, 4> Visited; 2040 Visited.insert(DT[BB]); 2041 #endif 2042 do { 2043 DomTreeNode *N = DomWorklist.pop_back_val(); 2044 2045 // Visit this node. 2046 if (!Callable(N->getBlock())) 2047 continue; 2048 2049 // Accumulate the child nodes. 2050 for (DomTreeNode *ChildN : *N) { 2051 assert(Visited.insert(ChildN).second && 2052 "Cannot visit a node twice when walking a tree!"); 2053 DomWorklist.push_back(ChildN); 2054 } 2055 } while (!DomWorklist.empty()); 2056 } 2057 2058 static void unswitchNontrivialInvariants( 2059 Loop &L, Instruction &TI, ArrayRef<Value *> Invariants, 2060 SmallVectorImpl<BasicBlock *> &ExitBlocks, IVConditionInfo &PartialIVInfo, 2061 DominatorTree &DT, LoopInfo &LI, AssumptionCache &AC, 2062 function_ref<void(bool, bool, ArrayRef<Loop *>)> UnswitchCB, 2063 ScalarEvolution *SE, MemorySSAUpdater *MSSAU, 2064 function_ref<void(Loop &, StringRef)> DestroyLoopCB) { 2065 auto *ParentBB = TI.getParent(); 2066 BranchInst *BI = dyn_cast<BranchInst>(&TI); 2067 SwitchInst *SI = BI ? nullptr : cast<SwitchInst>(&TI); 2068 2069 // We can only unswitch switches, conditional branches with an invariant 2070 // condition, or combining invariant conditions with an instruction or 2071 // partially invariant instructions. 2072 assert((SI || (BI && BI->isConditional())) && 2073 "Can only unswitch switches and conditional branch!"); 2074 bool PartiallyInvariant = !PartialIVInfo.InstToDuplicate.empty(); 2075 bool FullUnswitch = 2076 SI || (skipTrivialSelect(BI->getCondition()) == Invariants[0] && 2077 !PartiallyInvariant); 2078 if (FullUnswitch) 2079 assert(Invariants.size() == 1 && 2080 "Cannot have other invariants with full unswitching!"); 2081 else 2082 assert(isa<Instruction>(skipTrivialSelect(BI->getCondition())) && 2083 "Partial unswitching requires an instruction as the condition!"); 2084 2085 if (MSSAU && VerifyMemorySSA) 2086 MSSAU->getMemorySSA()->verifyMemorySSA(); 2087 2088 // Constant and BBs tracking the cloned and continuing successor. When we are 2089 // unswitching the entire condition, this can just be trivially chosen to 2090 // unswitch towards `true`. However, when we are unswitching a set of 2091 // invariants combined with `and` or `or` or partially invariant instructions, 2092 // the combining operation determines the best direction to unswitch: we want 2093 // to unswitch the direction that will collapse the branch. 2094 bool Direction = true; 2095 int ClonedSucc = 0; 2096 if (!FullUnswitch) { 2097 Value *Cond = skipTrivialSelect(BI->getCondition()); 2098 (void)Cond; 2099 assert(((match(Cond, m_LogicalAnd()) ^ match(Cond, m_LogicalOr())) || 2100 PartiallyInvariant) && 2101 "Only `or`, `and`, an `select`, partially invariant instructions " 2102 "can combine invariants being unswitched."); 2103 if (!match(Cond, m_LogicalOr())) { 2104 if (match(Cond, m_LogicalAnd()) || 2105 (PartiallyInvariant && !PartialIVInfo.KnownValue->isOneValue())) { 2106 Direction = false; 2107 ClonedSucc = 1; 2108 } 2109 } 2110 } 2111 2112 BasicBlock *RetainedSuccBB = 2113 BI ? BI->getSuccessor(1 - ClonedSucc) : SI->getDefaultDest(); 2114 SmallSetVector<BasicBlock *, 4> UnswitchedSuccBBs; 2115 if (BI) 2116 UnswitchedSuccBBs.insert(BI->getSuccessor(ClonedSucc)); 2117 else 2118 for (auto Case : SI->cases()) 2119 if (Case.getCaseSuccessor() != RetainedSuccBB) 2120 UnswitchedSuccBBs.insert(Case.getCaseSuccessor()); 2121 2122 assert(!UnswitchedSuccBBs.count(RetainedSuccBB) && 2123 "Should not unswitch the same successor we are retaining!"); 2124 2125 // The branch should be in this exact loop. Any inner loop's invariant branch 2126 // should be handled by unswitching that inner loop. The caller of this 2127 // routine should filter out any candidates that remain (but were skipped for 2128 // whatever reason). 2129 assert(LI.getLoopFor(ParentBB) == &L && "Branch in an inner loop!"); 2130 2131 // Compute the parent loop now before we start hacking on things. 2132 Loop *ParentL = L.getParentLoop(); 2133 // Get blocks in RPO order for MSSA update, before changing the CFG. 2134 LoopBlocksRPO LBRPO(&L); 2135 if (MSSAU) 2136 LBRPO.perform(&LI); 2137 2138 // Compute the outer-most loop containing one of our exit blocks. This is the 2139 // furthest up our loopnest which can be mutated, which we will use below to 2140 // update things. 2141 Loop *OuterExitL = &L; 2142 for (auto *ExitBB : ExitBlocks) { 2143 Loop *NewOuterExitL = LI.getLoopFor(ExitBB); 2144 if (!NewOuterExitL) { 2145 // We exited the entire nest with this block, so we're done. 2146 OuterExitL = nullptr; 2147 break; 2148 } 2149 if (NewOuterExitL != OuterExitL && NewOuterExitL->contains(OuterExitL)) 2150 OuterExitL = NewOuterExitL; 2151 } 2152 2153 // At this point, we're definitely going to unswitch something so invalidate 2154 // any cached information in ScalarEvolution for the outer most loop 2155 // containing an exit block and all nested loops. 2156 if (SE) { 2157 if (OuterExitL) 2158 SE->forgetLoop(OuterExitL); 2159 else 2160 SE->forgetTopmostLoop(&L); 2161 } 2162 2163 bool InsertFreeze = false; 2164 if (FreezeLoopUnswitchCond) { 2165 ICFLoopSafetyInfo SafetyInfo; 2166 SafetyInfo.computeLoopSafetyInfo(&L); 2167 InsertFreeze = !SafetyInfo.isGuaranteedToExecute(TI, &DT, &L); 2168 } 2169 2170 // If the edge from this terminator to a successor dominates that successor, 2171 // store a map from each block in its dominator subtree to it. This lets us 2172 // tell when cloning for a particular successor if a block is dominated by 2173 // some *other* successor with a single data structure. We use this to 2174 // significantly reduce cloning. 2175 SmallDenseMap<BasicBlock *, BasicBlock *, 16> DominatingSucc; 2176 for (auto *SuccBB : llvm::concat<BasicBlock *const>( 2177 makeArrayRef(RetainedSuccBB), UnswitchedSuccBBs)) 2178 if (SuccBB->getUniquePredecessor() || 2179 llvm::all_of(predecessors(SuccBB), [&](BasicBlock *PredBB) { 2180 return PredBB == ParentBB || DT.dominates(SuccBB, PredBB); 2181 })) 2182 visitDomSubTree(DT, SuccBB, [&](BasicBlock *BB) { 2183 DominatingSucc[BB] = SuccBB; 2184 return true; 2185 }); 2186 2187 // Split the preheader, so that we know that there is a safe place to insert 2188 // the conditional branch. We will change the preheader to have a conditional 2189 // branch on LoopCond. The original preheader will become the split point 2190 // between the unswitched versions, and we will have a new preheader for the 2191 // original loop. 2192 BasicBlock *SplitBB = L.getLoopPreheader(); 2193 BasicBlock *LoopPH = SplitEdge(SplitBB, L.getHeader(), &DT, &LI, MSSAU); 2194 2195 // Keep track of the dominator tree updates needed. 2196 SmallVector<DominatorTree::UpdateType, 4> DTUpdates; 2197 2198 // Clone the loop for each unswitched successor. 2199 SmallVector<std::unique_ptr<ValueToValueMapTy>, 4> VMaps; 2200 VMaps.reserve(UnswitchedSuccBBs.size()); 2201 SmallDenseMap<BasicBlock *, BasicBlock *, 4> ClonedPHs; 2202 for (auto *SuccBB : UnswitchedSuccBBs) { 2203 VMaps.emplace_back(new ValueToValueMapTy()); 2204 ClonedPHs[SuccBB] = buildClonedLoopBlocks( 2205 L, LoopPH, SplitBB, ExitBlocks, ParentBB, SuccBB, RetainedSuccBB, 2206 DominatingSucc, *VMaps.back(), DTUpdates, AC, DT, LI, MSSAU); 2207 } 2208 2209 // Drop metadata if we may break its semantics by moving this instr into the 2210 // split block. 2211 if (TI.getMetadata(LLVMContext::MD_make_implicit)) { 2212 if (DropNonTrivialImplicitNullChecks) 2213 // Do not spend time trying to understand if we can keep it, just drop it 2214 // to save compile time. 2215 TI.setMetadata(LLVMContext::MD_make_implicit, nullptr); 2216 else { 2217 // It is only legal to preserve make.implicit metadata if we are 2218 // guaranteed no reach implicit null check after following this branch. 2219 ICFLoopSafetyInfo SafetyInfo; 2220 SafetyInfo.computeLoopSafetyInfo(&L); 2221 if (!SafetyInfo.isGuaranteedToExecute(TI, &DT, &L)) 2222 TI.setMetadata(LLVMContext::MD_make_implicit, nullptr); 2223 } 2224 } 2225 2226 // The stitching of the branched code back together depends on whether we're 2227 // doing full unswitching or not with the exception that we always want to 2228 // nuke the initial terminator placed in the split block. 2229 SplitBB->getTerminator()->eraseFromParent(); 2230 if (FullUnswitch) { 2231 // Splice the terminator from the original loop and rewrite its 2232 // successors. 2233 SplitBB->getInstList().splice(SplitBB->end(), ParentBB->getInstList(), TI); 2234 2235 // Keep a clone of the terminator for MSSA updates. 2236 Instruction *NewTI = TI.clone(); 2237 ParentBB->getInstList().push_back(NewTI); 2238 2239 // First wire up the moved terminator to the preheaders. 2240 if (BI) { 2241 BasicBlock *ClonedPH = ClonedPHs.begin()->second; 2242 BI->setSuccessor(ClonedSucc, ClonedPH); 2243 BI->setSuccessor(1 - ClonedSucc, LoopPH); 2244 Value *Cond = skipTrivialSelect(BI->getCondition()); 2245 if (InsertFreeze) { 2246 if (!isGuaranteedNotToBeUndefOrPoison(Cond, &AC, BI, &DT)) 2247 Cond = new FreezeInst(Cond, Cond->getName() + ".fr", BI); 2248 } 2249 BI->setCondition(Cond); 2250 DTUpdates.push_back({DominatorTree::Insert, SplitBB, ClonedPH}); 2251 } else { 2252 assert(SI && "Must either be a branch or switch!"); 2253 2254 // Walk the cases and directly update their successors. 2255 assert(SI->getDefaultDest() == RetainedSuccBB && 2256 "Not retaining default successor!"); 2257 SI->setDefaultDest(LoopPH); 2258 for (const auto &Case : SI->cases()) 2259 if (Case.getCaseSuccessor() == RetainedSuccBB) 2260 Case.setSuccessor(LoopPH); 2261 else 2262 Case.setSuccessor(ClonedPHs.find(Case.getCaseSuccessor())->second); 2263 2264 if (InsertFreeze) { 2265 auto Cond = SI->getCondition(); 2266 if (!isGuaranteedNotToBeUndefOrPoison(Cond, &AC, SI, &DT)) 2267 SI->setCondition(new FreezeInst(Cond, Cond->getName() + ".fr", SI)); 2268 } 2269 // We need to use the set to populate domtree updates as even when there 2270 // are multiple cases pointing at the same successor we only want to 2271 // remove and insert one edge in the domtree. 2272 for (BasicBlock *SuccBB : UnswitchedSuccBBs) 2273 DTUpdates.push_back( 2274 {DominatorTree::Insert, SplitBB, ClonedPHs.find(SuccBB)->second}); 2275 } 2276 2277 if (MSSAU) { 2278 DT.applyUpdates(DTUpdates); 2279 DTUpdates.clear(); 2280 2281 // Remove all but one edge to the retained block and all unswitched 2282 // blocks. This is to avoid having duplicate entries in the cloned Phis, 2283 // when we know we only keep a single edge for each case. 2284 MSSAU->removeDuplicatePhiEdgesBetween(ParentBB, RetainedSuccBB); 2285 for (BasicBlock *SuccBB : UnswitchedSuccBBs) 2286 MSSAU->removeDuplicatePhiEdgesBetween(ParentBB, SuccBB); 2287 2288 for (auto &VMap : VMaps) 2289 MSSAU->updateForClonedLoop(LBRPO, ExitBlocks, *VMap, 2290 /*IgnoreIncomingWithNoClones=*/true); 2291 MSSAU->updateExitBlocksForClonedLoop(ExitBlocks, VMaps, DT); 2292 2293 // Remove all edges to unswitched blocks. 2294 for (BasicBlock *SuccBB : UnswitchedSuccBBs) 2295 MSSAU->removeEdge(ParentBB, SuccBB); 2296 } 2297 2298 // Now unhook the successor relationship as we'll be replacing 2299 // the terminator with a direct branch. This is much simpler for branches 2300 // than switches so we handle those first. 2301 if (BI) { 2302 // Remove the parent as a predecessor of the unswitched successor. 2303 assert(UnswitchedSuccBBs.size() == 1 && 2304 "Only one possible unswitched block for a branch!"); 2305 BasicBlock *UnswitchedSuccBB = *UnswitchedSuccBBs.begin(); 2306 UnswitchedSuccBB->removePredecessor(ParentBB, 2307 /*KeepOneInputPHIs*/ true); 2308 DTUpdates.push_back({DominatorTree::Delete, ParentBB, UnswitchedSuccBB}); 2309 } else { 2310 // Note that we actually want to remove the parent block as a predecessor 2311 // of *every* case successor. The case successor is either unswitched, 2312 // completely eliminating an edge from the parent to that successor, or it 2313 // is a duplicate edge to the retained successor as the retained successor 2314 // is always the default successor and as we'll replace this with a direct 2315 // branch we no longer need the duplicate entries in the PHI nodes. 2316 SwitchInst *NewSI = cast<SwitchInst>(NewTI); 2317 assert(NewSI->getDefaultDest() == RetainedSuccBB && 2318 "Not retaining default successor!"); 2319 for (const auto &Case : NewSI->cases()) 2320 Case.getCaseSuccessor()->removePredecessor( 2321 ParentBB, 2322 /*KeepOneInputPHIs*/ true); 2323 2324 // We need to use the set to populate domtree updates as even when there 2325 // are multiple cases pointing at the same successor we only want to 2326 // remove and insert one edge in the domtree. 2327 for (BasicBlock *SuccBB : UnswitchedSuccBBs) 2328 DTUpdates.push_back({DominatorTree::Delete, ParentBB, SuccBB}); 2329 } 2330 2331 // After MSSAU update, remove the cloned terminator instruction NewTI. 2332 ParentBB->getTerminator()->eraseFromParent(); 2333 2334 // Create a new unconditional branch to the continuing block (as opposed to 2335 // the one cloned). 2336 BranchInst::Create(RetainedSuccBB, ParentBB); 2337 } else { 2338 assert(BI && "Only branches have partial unswitching."); 2339 assert(UnswitchedSuccBBs.size() == 1 && 2340 "Only one possible unswitched block for a branch!"); 2341 BasicBlock *ClonedPH = ClonedPHs.begin()->second; 2342 // When doing a partial unswitch, we have to do a bit more work to build up 2343 // the branch in the split block. 2344 if (PartiallyInvariant) 2345 buildPartialInvariantUnswitchConditionalBranch( 2346 *SplitBB, Invariants, Direction, *ClonedPH, *LoopPH, L, MSSAU); 2347 else { 2348 buildPartialUnswitchConditionalBranch( 2349 *SplitBB, Invariants, Direction, *ClonedPH, *LoopPH, 2350 FreezeLoopUnswitchCond, BI, &AC, DT); 2351 } 2352 DTUpdates.push_back({DominatorTree::Insert, SplitBB, ClonedPH}); 2353 2354 if (MSSAU) { 2355 DT.applyUpdates(DTUpdates); 2356 DTUpdates.clear(); 2357 2358 // Perform MSSA cloning updates. 2359 for (auto &VMap : VMaps) 2360 MSSAU->updateForClonedLoop(LBRPO, ExitBlocks, *VMap, 2361 /*IgnoreIncomingWithNoClones=*/true); 2362 MSSAU->updateExitBlocksForClonedLoop(ExitBlocks, VMaps, DT); 2363 } 2364 } 2365 2366 // Apply the updates accumulated above to get an up-to-date dominator tree. 2367 DT.applyUpdates(DTUpdates); 2368 2369 // Now that we have an accurate dominator tree, first delete the dead cloned 2370 // blocks so that we can accurately build any cloned loops. It is important to 2371 // not delete the blocks from the original loop yet because we still want to 2372 // reference the original loop to understand the cloned loop's structure. 2373 deleteDeadClonedBlocks(L, ExitBlocks, VMaps, DT, MSSAU); 2374 2375 // Build the cloned loop structure itself. This may be substantially 2376 // different from the original structure due to the simplified CFG. This also 2377 // handles inserting all the cloned blocks into the correct loops. 2378 SmallVector<Loop *, 4> NonChildClonedLoops; 2379 for (std::unique_ptr<ValueToValueMapTy> &VMap : VMaps) 2380 buildClonedLoops(L, ExitBlocks, *VMap, LI, NonChildClonedLoops); 2381 2382 // Now that our cloned loops have been built, we can update the original loop. 2383 // First we delete the dead blocks from it and then we rebuild the loop 2384 // structure taking these deletions into account. 2385 deleteDeadBlocksFromLoop(L, ExitBlocks, DT, LI, MSSAU, SE,DestroyLoopCB); 2386 2387 if (MSSAU && VerifyMemorySSA) 2388 MSSAU->getMemorySSA()->verifyMemorySSA(); 2389 2390 SmallVector<Loop *, 4> HoistedLoops; 2391 bool IsStillLoop = 2392 rebuildLoopAfterUnswitch(L, ExitBlocks, LI, HoistedLoops, SE); 2393 2394 if (MSSAU && VerifyMemorySSA) 2395 MSSAU->getMemorySSA()->verifyMemorySSA(); 2396 2397 // This transformation has a high risk of corrupting the dominator tree, and 2398 // the below steps to rebuild loop structures will result in hard to debug 2399 // errors in that case so verify that the dominator tree is sane first. 2400 // FIXME: Remove this when the bugs stop showing up and rely on existing 2401 // verification steps. 2402 assert(DT.verify(DominatorTree::VerificationLevel::Fast)); 2403 2404 if (BI && !PartiallyInvariant) { 2405 // If we unswitched a branch which collapses the condition to a known 2406 // constant we want to replace all the uses of the invariants within both 2407 // the original and cloned blocks. We do this here so that we can use the 2408 // now updated dominator tree to identify which side the users are on. 2409 assert(UnswitchedSuccBBs.size() == 1 && 2410 "Only one possible unswitched block for a branch!"); 2411 BasicBlock *ClonedPH = ClonedPHs.begin()->second; 2412 2413 // When considering multiple partially-unswitched invariants 2414 // we cant just go replace them with constants in both branches. 2415 // 2416 // For 'AND' we infer that true branch ("continue") means true 2417 // for each invariant operand. 2418 // For 'OR' we can infer that false branch ("continue") means false 2419 // for each invariant operand. 2420 // So it happens that for multiple-partial case we dont replace 2421 // in the unswitched branch. 2422 bool ReplaceUnswitched = 2423 FullUnswitch || (Invariants.size() == 1) || PartiallyInvariant; 2424 2425 ConstantInt *UnswitchedReplacement = 2426 Direction ? ConstantInt::getTrue(BI->getContext()) 2427 : ConstantInt::getFalse(BI->getContext()); 2428 ConstantInt *ContinueReplacement = 2429 Direction ? ConstantInt::getFalse(BI->getContext()) 2430 : ConstantInt::getTrue(BI->getContext()); 2431 for (Value *Invariant : Invariants) { 2432 assert(!isa<Constant>(Invariant) && 2433 "Should not be replacing constant values!"); 2434 // Use make_early_inc_range here as set invalidates the iterator. 2435 for (Use &U : llvm::make_early_inc_range(Invariant->uses())) { 2436 Instruction *UserI = dyn_cast<Instruction>(U.getUser()); 2437 if (!UserI) 2438 continue; 2439 2440 // Replace it with the 'continue' side if in the main loop body, and the 2441 // unswitched if in the cloned blocks. 2442 if (DT.dominates(LoopPH, UserI->getParent())) 2443 U.set(ContinueReplacement); 2444 else if (ReplaceUnswitched && 2445 DT.dominates(ClonedPH, UserI->getParent())) 2446 U.set(UnswitchedReplacement); 2447 } 2448 } 2449 } 2450 2451 // We can change which blocks are exit blocks of all the cloned sibling 2452 // loops, the current loop, and any parent loops which shared exit blocks 2453 // with the current loop. As a consequence, we need to re-form LCSSA for 2454 // them. But we shouldn't need to re-form LCSSA for any child loops. 2455 // FIXME: This could be made more efficient by tracking which exit blocks are 2456 // new, and focusing on them, but that isn't likely to be necessary. 2457 // 2458 // In order to reasonably rebuild LCSSA we need to walk inside-out across the 2459 // loop nest and update every loop that could have had its exits changed. We 2460 // also need to cover any intervening loops. We add all of these loops to 2461 // a list and sort them by loop depth to achieve this without updating 2462 // unnecessary loops. 2463 auto UpdateLoop = [&](Loop &UpdateL) { 2464 #ifndef NDEBUG 2465 UpdateL.verifyLoop(); 2466 for (Loop *ChildL : UpdateL) { 2467 ChildL->verifyLoop(); 2468 assert(ChildL->isRecursivelyLCSSAForm(DT, LI) && 2469 "Perturbed a child loop's LCSSA form!"); 2470 } 2471 #endif 2472 // First build LCSSA for this loop so that we can preserve it when 2473 // forming dedicated exits. We don't want to perturb some other loop's 2474 // LCSSA while doing that CFG edit. 2475 formLCSSA(UpdateL, DT, &LI, SE); 2476 2477 // For loops reached by this loop's original exit blocks we may 2478 // introduced new, non-dedicated exits. At least try to re-form dedicated 2479 // exits for these loops. This may fail if they couldn't have dedicated 2480 // exits to start with. 2481 formDedicatedExitBlocks(&UpdateL, &DT, &LI, MSSAU, /*PreserveLCSSA*/ true); 2482 }; 2483 2484 // For non-child cloned loops and hoisted loops, we just need to update LCSSA 2485 // and we can do it in any order as they don't nest relative to each other. 2486 // 2487 // Also check if any of the loops we have updated have become top-level loops 2488 // as that will necessitate widening the outer loop scope. 2489 for (Loop *UpdatedL : 2490 llvm::concat<Loop *>(NonChildClonedLoops, HoistedLoops)) { 2491 UpdateLoop(*UpdatedL); 2492 if (UpdatedL->isOutermost()) 2493 OuterExitL = nullptr; 2494 } 2495 if (IsStillLoop) { 2496 UpdateLoop(L); 2497 if (L.isOutermost()) 2498 OuterExitL = nullptr; 2499 } 2500 2501 // If the original loop had exit blocks, walk up through the outer most loop 2502 // of those exit blocks to update LCSSA and form updated dedicated exits. 2503 if (OuterExitL != &L) 2504 for (Loop *OuterL = ParentL; OuterL != OuterExitL; 2505 OuterL = OuterL->getParentLoop()) 2506 UpdateLoop(*OuterL); 2507 2508 #ifndef NDEBUG 2509 // Verify the entire loop structure to catch any incorrect updates before we 2510 // progress in the pass pipeline. 2511 LI.verify(DT); 2512 #endif 2513 2514 // Now that we've unswitched something, make callbacks to report the changes. 2515 // For that we need to merge together the updated loops and the cloned loops 2516 // and check whether the original loop survived. 2517 SmallVector<Loop *, 4> SibLoops; 2518 for (Loop *UpdatedL : llvm::concat<Loop *>(NonChildClonedLoops, HoistedLoops)) 2519 if (UpdatedL->getParentLoop() == ParentL) 2520 SibLoops.push_back(UpdatedL); 2521 UnswitchCB(IsStillLoop, PartiallyInvariant, SibLoops); 2522 2523 if (MSSAU && VerifyMemorySSA) 2524 MSSAU->getMemorySSA()->verifyMemorySSA(); 2525 2526 if (BI) 2527 ++NumBranches; 2528 else 2529 ++NumSwitches; 2530 } 2531 2532 /// Recursively compute the cost of a dominator subtree based on the per-block 2533 /// cost map provided. 2534 /// 2535 /// The recursive computation is memozied into the provided DT-indexed cost map 2536 /// to allow querying it for most nodes in the domtree without it becoming 2537 /// quadratic. 2538 static InstructionCost computeDomSubtreeCost( 2539 DomTreeNode &N, 2540 const SmallDenseMap<BasicBlock *, InstructionCost, 4> &BBCostMap, 2541 SmallDenseMap<DomTreeNode *, InstructionCost, 4> &DTCostMap) { 2542 // Don't accumulate cost (or recurse through) blocks not in our block cost 2543 // map and thus not part of the duplication cost being considered. 2544 auto BBCostIt = BBCostMap.find(N.getBlock()); 2545 if (BBCostIt == BBCostMap.end()) 2546 return 0; 2547 2548 // Lookup this node to see if we already computed its cost. 2549 auto DTCostIt = DTCostMap.find(&N); 2550 if (DTCostIt != DTCostMap.end()) 2551 return DTCostIt->second; 2552 2553 // If not, we have to compute it. We can't use insert above and update 2554 // because computing the cost may insert more things into the map. 2555 InstructionCost Cost = std::accumulate( 2556 N.begin(), N.end(), BBCostIt->second, 2557 [&](InstructionCost Sum, DomTreeNode *ChildN) -> InstructionCost { 2558 return Sum + computeDomSubtreeCost(*ChildN, BBCostMap, DTCostMap); 2559 }); 2560 bool Inserted = DTCostMap.insert({&N, Cost}).second; 2561 (void)Inserted; 2562 assert(Inserted && "Should not insert a node while visiting children!"); 2563 return Cost; 2564 } 2565 2566 /// Turns a llvm.experimental.guard intrinsic into implicit control flow branch, 2567 /// making the following replacement: 2568 /// 2569 /// --code before guard-- 2570 /// call void (i1, ...) @llvm.experimental.guard(i1 %cond) [ "deopt"() ] 2571 /// --code after guard-- 2572 /// 2573 /// into 2574 /// 2575 /// --code before guard-- 2576 /// br i1 %cond, label %guarded, label %deopt 2577 /// 2578 /// guarded: 2579 /// --code after guard-- 2580 /// 2581 /// deopt: 2582 /// call void (i1, ...) @llvm.experimental.guard(i1 false) [ "deopt"() ] 2583 /// unreachable 2584 /// 2585 /// It also makes all relevant DT and LI updates, so that all structures are in 2586 /// valid state after this transform. 2587 static BranchInst * 2588 turnGuardIntoBranch(IntrinsicInst *GI, Loop &L, 2589 SmallVectorImpl<BasicBlock *> &ExitBlocks, 2590 DominatorTree &DT, LoopInfo &LI, MemorySSAUpdater *MSSAU) { 2591 SmallVector<DominatorTree::UpdateType, 4> DTUpdates; 2592 LLVM_DEBUG(dbgs() << "Turning " << *GI << " into a branch.\n"); 2593 BasicBlock *CheckBB = GI->getParent(); 2594 2595 if (MSSAU && VerifyMemorySSA) 2596 MSSAU->getMemorySSA()->verifyMemorySSA(); 2597 2598 // Remove all CheckBB's successors from DomTree. A block can be seen among 2599 // successors more than once, but for DomTree it should be added only once. 2600 SmallPtrSet<BasicBlock *, 4> Successors; 2601 for (auto *Succ : successors(CheckBB)) 2602 if (Successors.insert(Succ).second) 2603 DTUpdates.push_back({DominatorTree::Delete, CheckBB, Succ}); 2604 2605 Instruction *DeoptBlockTerm = 2606 SplitBlockAndInsertIfThen(GI->getArgOperand(0), GI, true); 2607 BranchInst *CheckBI = cast<BranchInst>(CheckBB->getTerminator()); 2608 // SplitBlockAndInsertIfThen inserts control flow that branches to 2609 // DeoptBlockTerm if the condition is true. We want the opposite. 2610 CheckBI->swapSuccessors(); 2611 2612 BasicBlock *GuardedBlock = CheckBI->getSuccessor(0); 2613 GuardedBlock->setName("guarded"); 2614 CheckBI->getSuccessor(1)->setName("deopt"); 2615 BasicBlock *DeoptBlock = CheckBI->getSuccessor(1); 2616 2617 // We now have a new exit block. 2618 ExitBlocks.push_back(CheckBI->getSuccessor(1)); 2619 2620 if (MSSAU) 2621 MSSAU->moveAllAfterSpliceBlocks(CheckBB, GuardedBlock, GI); 2622 2623 GI->moveBefore(DeoptBlockTerm); 2624 GI->setArgOperand(0, ConstantInt::getFalse(GI->getContext())); 2625 2626 // Add new successors of CheckBB into DomTree. 2627 for (auto *Succ : successors(CheckBB)) 2628 DTUpdates.push_back({DominatorTree::Insert, CheckBB, Succ}); 2629 2630 // Now the blocks that used to be CheckBB's successors are GuardedBlock's 2631 // successors. 2632 for (auto *Succ : Successors) 2633 DTUpdates.push_back({DominatorTree::Insert, GuardedBlock, Succ}); 2634 2635 // Make proper changes to DT. 2636 DT.applyUpdates(DTUpdates); 2637 // Inform LI of a new loop block. 2638 L.addBasicBlockToLoop(GuardedBlock, LI); 2639 2640 if (MSSAU) { 2641 MemoryDef *MD = cast<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess(GI)); 2642 MSSAU->moveToPlace(MD, DeoptBlock, MemorySSA::BeforeTerminator); 2643 if (VerifyMemorySSA) 2644 MSSAU->getMemorySSA()->verifyMemorySSA(); 2645 } 2646 2647 ++NumGuards; 2648 return CheckBI; 2649 } 2650 2651 /// Cost multiplier is a way to limit potentially exponential behavior 2652 /// of loop-unswitch. Cost is multipied in proportion of 2^number of unswitch 2653 /// candidates available. Also accounting for the number of "sibling" loops with 2654 /// the idea to account for previous unswitches that already happened on this 2655 /// cluster of loops. There was an attempt to keep this formula simple, 2656 /// just enough to limit the worst case behavior. Even if it is not that simple 2657 /// now it is still not an attempt to provide a detailed heuristic size 2658 /// prediction. 2659 /// 2660 /// TODO: Make a proper accounting of "explosion" effect for all kinds of 2661 /// unswitch candidates, making adequate predictions instead of wild guesses. 2662 /// That requires knowing not just the number of "remaining" candidates but 2663 /// also costs of unswitching for each of these candidates. 2664 static int CalculateUnswitchCostMultiplier( 2665 Instruction &TI, Loop &L, LoopInfo &LI, DominatorTree &DT, 2666 ArrayRef<std::pair<Instruction *, TinyPtrVector<Value *>>> 2667 UnswitchCandidates) { 2668 2669 // Guards and other exiting conditions do not contribute to exponential 2670 // explosion as soon as they dominate the latch (otherwise there might be 2671 // another path to the latch remaining that does not allow to eliminate the 2672 // loop copy on unswitch). 2673 BasicBlock *Latch = L.getLoopLatch(); 2674 BasicBlock *CondBlock = TI.getParent(); 2675 if (DT.dominates(CondBlock, Latch) && 2676 (isGuard(&TI) || 2677 llvm::count_if(successors(&TI), [&L](BasicBlock *SuccBB) { 2678 return L.contains(SuccBB); 2679 }) <= 1)) { 2680 NumCostMultiplierSkipped++; 2681 return 1; 2682 } 2683 2684 auto *ParentL = L.getParentLoop(); 2685 int SiblingsCount = (ParentL ? ParentL->getSubLoopsVector().size() 2686 : std::distance(LI.begin(), LI.end())); 2687 // Count amount of clones that all the candidates might cause during 2688 // unswitching. Branch/guard counts as 1, switch counts as log2 of its cases. 2689 int UnswitchedClones = 0; 2690 for (auto Candidate : UnswitchCandidates) { 2691 Instruction *CI = Candidate.first; 2692 BasicBlock *CondBlock = CI->getParent(); 2693 bool SkipExitingSuccessors = DT.dominates(CondBlock, Latch); 2694 if (isGuard(CI)) { 2695 if (!SkipExitingSuccessors) 2696 UnswitchedClones++; 2697 continue; 2698 } 2699 int NonExitingSuccessors = llvm::count_if( 2700 successors(CondBlock), [SkipExitingSuccessors, &L](BasicBlock *SuccBB) { 2701 return !SkipExitingSuccessors || L.contains(SuccBB); 2702 }); 2703 UnswitchedClones += Log2_32(NonExitingSuccessors); 2704 } 2705 2706 // Ignore up to the "unscaled candidates" number of unswitch candidates 2707 // when calculating the power-of-two scaling of the cost. The main idea 2708 // with this control is to allow a small number of unswitches to happen 2709 // and rely more on siblings multiplier (see below) when the number 2710 // of candidates is small. 2711 unsigned ClonesPower = 2712 std::max(UnswitchedClones - (int)UnswitchNumInitialUnscaledCandidates, 0); 2713 2714 // Allowing top-level loops to spread a bit more than nested ones. 2715 int SiblingsMultiplier = 2716 std::max((ParentL ? SiblingsCount 2717 : SiblingsCount / (int)UnswitchSiblingsToplevelDiv), 2718 1); 2719 // Compute the cost multiplier in a way that won't overflow by saturating 2720 // at an upper bound. 2721 int CostMultiplier; 2722 if (ClonesPower > Log2_32(UnswitchThreshold) || 2723 SiblingsMultiplier > UnswitchThreshold) 2724 CostMultiplier = UnswitchThreshold; 2725 else 2726 CostMultiplier = std::min(SiblingsMultiplier * (1 << ClonesPower), 2727 (int)UnswitchThreshold); 2728 2729 LLVM_DEBUG(dbgs() << " Computed multiplier " << CostMultiplier 2730 << " (siblings " << SiblingsMultiplier << " * clones " 2731 << (1 << ClonesPower) << ")" 2732 << " for unswitch candidate: " << TI << "\n"); 2733 return CostMultiplier; 2734 } 2735 2736 static bool unswitchBestCondition( 2737 Loop &L, DominatorTree &DT, LoopInfo &LI, AssumptionCache &AC, 2738 AAResults &AA, TargetTransformInfo &TTI, 2739 function_ref<void(bool, bool, ArrayRef<Loop *>)> UnswitchCB, 2740 ScalarEvolution *SE, MemorySSAUpdater *MSSAU, 2741 function_ref<void(Loop &, StringRef)> DestroyLoopCB) { 2742 // Collect all invariant conditions within this loop (as opposed to an inner 2743 // loop which would be handled when visiting that inner loop). 2744 SmallVector<std::pair<Instruction *, TinyPtrVector<Value *>>, 4> 2745 UnswitchCandidates; 2746 2747 // Whether or not we should also collect guards in the loop. 2748 bool CollectGuards = false; 2749 if (UnswitchGuards) { 2750 auto *GuardDecl = L.getHeader()->getParent()->getParent()->getFunction( 2751 Intrinsic::getName(Intrinsic::experimental_guard)); 2752 if (GuardDecl && !GuardDecl->use_empty()) 2753 CollectGuards = true; 2754 } 2755 2756 IVConditionInfo PartialIVInfo; 2757 for (auto *BB : L.blocks()) { 2758 if (LI.getLoopFor(BB) != &L) 2759 continue; 2760 2761 if (CollectGuards) 2762 for (auto &I : *BB) 2763 if (isGuard(&I)) { 2764 auto *Cond = cast<IntrinsicInst>(&I)->getArgOperand(0); 2765 // TODO: Support AND, OR conditions and partial unswitching. 2766 if (!isa<Constant>(Cond) && L.isLoopInvariant(Cond)) 2767 UnswitchCandidates.push_back({&I, {Cond}}); 2768 } 2769 2770 if (auto *SI = dyn_cast<SwitchInst>(BB->getTerminator())) { 2771 // We can only consider fully loop-invariant switch conditions as we need 2772 // to completely eliminate the switch after unswitching. 2773 if (!isa<Constant>(SI->getCondition()) && 2774 L.isLoopInvariant(SI->getCondition()) && !BB->getUniqueSuccessor()) 2775 UnswitchCandidates.push_back({SI, {SI->getCondition()}}); 2776 continue; 2777 } 2778 2779 auto *BI = dyn_cast<BranchInst>(BB->getTerminator()); 2780 if (!BI || !BI->isConditional() || isa<Constant>(BI->getCondition()) || 2781 BI->getSuccessor(0) == BI->getSuccessor(1)) 2782 continue; 2783 2784 Value *Cond = skipTrivialSelect(BI->getCondition()); 2785 if (isa<Constant>(Cond)) 2786 continue; 2787 2788 if (L.isLoopInvariant(Cond)) { 2789 UnswitchCandidates.push_back({BI, {Cond}}); 2790 continue; 2791 } 2792 2793 Instruction &CondI = *cast<Instruction>(Cond); 2794 if (match(&CondI, m_CombineOr(m_LogicalAnd(), m_LogicalOr()))) { 2795 TinyPtrVector<Value *> Invariants = 2796 collectHomogenousInstGraphLoopInvariants(L, CondI, LI); 2797 if (Invariants.empty()) 2798 continue; 2799 2800 UnswitchCandidates.push_back({BI, std::move(Invariants)}); 2801 continue; 2802 } 2803 } 2804 2805 Instruction *PartialIVCondBranch = nullptr; 2806 if (MSSAU && !findOptionMDForLoop(&L, "llvm.loop.unswitch.partial.disable") && 2807 !any_of(UnswitchCandidates, [&L](auto &TerminatorAndInvariants) { 2808 return TerminatorAndInvariants.first == L.getHeader()->getTerminator(); 2809 })) { 2810 MemorySSA *MSSA = MSSAU->getMemorySSA(); 2811 if (auto Info = hasPartialIVCondition(L, MSSAThreshold, *MSSA, AA)) { 2812 LLVM_DEBUG( 2813 dbgs() << "simple-loop-unswitch: Found partially invariant condition " 2814 << *Info->InstToDuplicate[0] << "\n"); 2815 PartialIVInfo = *Info; 2816 PartialIVCondBranch = L.getHeader()->getTerminator(); 2817 TinyPtrVector<Value *> ValsToDuplicate; 2818 llvm::append_range(ValsToDuplicate, Info->InstToDuplicate); 2819 UnswitchCandidates.push_back( 2820 {L.getHeader()->getTerminator(), std::move(ValsToDuplicate)}); 2821 } 2822 } 2823 2824 // If we didn't find any candidates, we're done. 2825 if (UnswitchCandidates.empty()) 2826 return false; 2827 2828 // Check if there are irreducible CFG cycles in this loop. If so, we cannot 2829 // easily unswitch non-trivial edges out of the loop. Doing so might turn the 2830 // irreducible control flow into reducible control flow and introduce new 2831 // loops "out of thin air". If we ever discover important use cases for doing 2832 // this, we can add support to loop unswitch, but it is a lot of complexity 2833 // for what seems little or no real world benefit. 2834 LoopBlocksRPO RPOT(&L); 2835 RPOT.perform(&LI); 2836 if (containsIrreducibleCFG<const BasicBlock *>(RPOT, LI)) 2837 return false; 2838 2839 SmallVector<BasicBlock *, 4> ExitBlocks; 2840 L.getUniqueExitBlocks(ExitBlocks); 2841 2842 // We cannot unswitch if exit blocks contain a cleanuppad/catchswitch 2843 // instruction as we don't know how to split those exit blocks. 2844 // FIXME: We should teach SplitBlock to handle this and remove this 2845 // restriction. 2846 for (auto *ExitBB : ExitBlocks) { 2847 auto *I = ExitBB->getFirstNonPHI(); 2848 if (isa<CleanupPadInst>(I) || isa<CatchSwitchInst>(I)) { 2849 LLVM_DEBUG(dbgs() << "Cannot unswitch because of cleanuppad/catchswitch " 2850 "in exit block\n"); 2851 return false; 2852 } 2853 } 2854 2855 LLVM_DEBUG( 2856 dbgs() << "Considering " << UnswitchCandidates.size() 2857 << " non-trivial loop invariant conditions for unswitching.\n"); 2858 2859 // Given that unswitching these terminators will require duplicating parts of 2860 // the loop, so we need to be able to model that cost. Compute the ephemeral 2861 // values and set up a data structure to hold per-BB costs. We cache each 2862 // block's cost so that we don't recompute this when considering different 2863 // subsets of the loop for duplication during unswitching. 2864 SmallPtrSet<const Value *, 4> EphValues; 2865 CodeMetrics::collectEphemeralValues(&L, &AC, EphValues); 2866 SmallDenseMap<BasicBlock *, InstructionCost, 4> BBCostMap; 2867 2868 // Compute the cost of each block, as well as the total loop cost. Also, bail 2869 // out if we see instructions which are incompatible with loop unswitching 2870 // (convergent, noduplicate, or cross-basic-block tokens). 2871 // FIXME: We might be able to safely handle some of these in non-duplicated 2872 // regions. 2873 TargetTransformInfo::TargetCostKind CostKind = 2874 L.getHeader()->getParent()->hasMinSize() 2875 ? TargetTransformInfo::TCK_CodeSize 2876 : TargetTransformInfo::TCK_SizeAndLatency; 2877 InstructionCost LoopCost = 0; 2878 for (auto *BB : L.blocks()) { 2879 InstructionCost Cost = 0; 2880 for (auto &I : *BB) { 2881 if (EphValues.count(&I)) 2882 continue; 2883 2884 if (I.getType()->isTokenTy() && I.isUsedOutsideOfBlock(BB)) 2885 return false; 2886 if (auto *CB = dyn_cast<CallBase>(&I)) 2887 if (CB->isConvergent() || CB->cannotDuplicate()) 2888 return false; 2889 2890 Cost += TTI.getInstructionCost(&I, CostKind); 2891 } 2892 assert(Cost >= 0 && "Must not have negative costs!"); 2893 LoopCost += Cost; 2894 assert(LoopCost >= 0 && "Must not have negative loop costs!"); 2895 BBCostMap[BB] = Cost; 2896 } 2897 LLVM_DEBUG(dbgs() << " Total loop cost: " << LoopCost << "\n"); 2898 2899 // Now we find the best candidate by searching for the one with the following 2900 // properties in order: 2901 // 2902 // 1) An unswitching cost below the threshold 2903 // 2) The smallest number of duplicated unswitch candidates (to avoid 2904 // creating redundant subsequent unswitching) 2905 // 3) The smallest cost after unswitching. 2906 // 2907 // We prioritize reducing fanout of unswitch candidates provided the cost 2908 // remains below the threshold because this has a multiplicative effect. 2909 // 2910 // This requires memoizing each dominator subtree to avoid redundant work. 2911 // 2912 // FIXME: Need to actually do the number of candidates part above. 2913 SmallDenseMap<DomTreeNode *, InstructionCost, 4> DTCostMap; 2914 // Given a terminator which might be unswitched, computes the non-duplicated 2915 // cost for that terminator. 2916 auto ComputeUnswitchedCost = [&](Instruction &TI, 2917 bool FullUnswitch) -> InstructionCost { 2918 BasicBlock &BB = *TI.getParent(); 2919 SmallPtrSet<BasicBlock *, 4> Visited; 2920 2921 InstructionCost Cost = 0; 2922 for (BasicBlock *SuccBB : successors(&BB)) { 2923 // Don't count successors more than once. 2924 if (!Visited.insert(SuccBB).second) 2925 continue; 2926 2927 // If this is a partial unswitch candidate, then it must be a conditional 2928 // branch with a condition of either `or`, `and`, their corresponding 2929 // select forms or partially invariant instructions. In that case, one of 2930 // the successors is necessarily duplicated, so don't even try to remove 2931 // its cost. 2932 if (!FullUnswitch) { 2933 auto &BI = cast<BranchInst>(TI); 2934 Value *Cond = skipTrivialSelect(BI.getCondition()); 2935 if (match(Cond, m_LogicalAnd())) { 2936 if (SuccBB == BI.getSuccessor(1)) 2937 continue; 2938 } else if (match(Cond, m_LogicalOr())) { 2939 if (SuccBB == BI.getSuccessor(0)) 2940 continue; 2941 } else if ((PartialIVInfo.KnownValue->isOneValue() && 2942 SuccBB == BI.getSuccessor(0)) || 2943 (!PartialIVInfo.KnownValue->isOneValue() && 2944 SuccBB == BI.getSuccessor(1))) 2945 continue; 2946 } 2947 2948 // This successor's domtree will not need to be duplicated after 2949 // unswitching if the edge to the successor dominates it (and thus the 2950 // entire tree). This essentially means there is no other path into this 2951 // subtree and so it will end up live in only one clone of the loop. 2952 if (SuccBB->getUniquePredecessor() || 2953 llvm::all_of(predecessors(SuccBB), [&](BasicBlock *PredBB) { 2954 return PredBB == &BB || DT.dominates(SuccBB, PredBB); 2955 })) { 2956 Cost += computeDomSubtreeCost(*DT[SuccBB], BBCostMap, DTCostMap); 2957 assert(Cost <= LoopCost && 2958 "Non-duplicated cost should never exceed total loop cost!"); 2959 } 2960 } 2961 2962 // Now scale the cost by the number of unique successors minus one. We 2963 // subtract one because there is already at least one copy of the entire 2964 // loop. This is computing the new cost of unswitching a condition. 2965 // Note that guards always have 2 unique successors that are implicit and 2966 // will be materialized if we decide to unswitch it. 2967 int SuccessorsCount = isGuard(&TI) ? 2 : Visited.size(); 2968 assert(SuccessorsCount > 1 && 2969 "Cannot unswitch a condition without multiple distinct successors!"); 2970 return (LoopCost - Cost) * (SuccessorsCount - 1); 2971 }; 2972 Instruction *BestUnswitchTI = nullptr; 2973 InstructionCost BestUnswitchCost = 0; 2974 ArrayRef<Value *> BestUnswitchInvariants; 2975 for (auto &TerminatorAndInvariants : UnswitchCandidates) { 2976 Instruction &TI = *TerminatorAndInvariants.first; 2977 ArrayRef<Value *> Invariants = TerminatorAndInvariants.second; 2978 BranchInst *BI = dyn_cast<BranchInst>(&TI); 2979 InstructionCost CandidateCost = ComputeUnswitchedCost( 2980 TI, /*FullUnswitch*/ !BI || 2981 (Invariants.size() == 1 && 2982 Invariants[0] == skipTrivialSelect(BI->getCondition()))); 2983 // Calculate cost multiplier which is a tool to limit potentially 2984 // exponential behavior of loop-unswitch. 2985 if (EnableUnswitchCostMultiplier) { 2986 int CostMultiplier = 2987 CalculateUnswitchCostMultiplier(TI, L, LI, DT, UnswitchCandidates); 2988 assert( 2989 (CostMultiplier > 0 && CostMultiplier <= UnswitchThreshold) && 2990 "cost multiplier needs to be in the range of 1..UnswitchThreshold"); 2991 CandidateCost *= CostMultiplier; 2992 LLVM_DEBUG(dbgs() << " Computed cost of " << CandidateCost 2993 << " (multiplier: " << CostMultiplier << ")" 2994 << " for unswitch candidate: " << TI << "\n"); 2995 } else { 2996 LLVM_DEBUG(dbgs() << " Computed cost of " << CandidateCost 2997 << " for unswitch candidate: " << TI << "\n"); 2998 } 2999 3000 if (!BestUnswitchTI || CandidateCost < BestUnswitchCost) { 3001 BestUnswitchTI = &TI; 3002 BestUnswitchCost = CandidateCost; 3003 BestUnswitchInvariants = Invariants; 3004 } 3005 } 3006 assert(BestUnswitchTI && "Failed to find loop unswitch candidate"); 3007 3008 if (BestUnswitchCost >= UnswitchThreshold) { 3009 LLVM_DEBUG(dbgs() << "Cannot unswitch, lowest cost found: " 3010 << BestUnswitchCost << "\n"); 3011 return false; 3012 } 3013 3014 if (BestUnswitchTI != PartialIVCondBranch) 3015 PartialIVInfo.InstToDuplicate.clear(); 3016 3017 // If the best candidate is a guard, turn it into a branch. 3018 if (isGuard(BestUnswitchTI)) 3019 BestUnswitchTI = turnGuardIntoBranch(cast<IntrinsicInst>(BestUnswitchTI), L, 3020 ExitBlocks, DT, LI, MSSAU); 3021 3022 LLVM_DEBUG(dbgs() << " Unswitching non-trivial (cost = " 3023 << BestUnswitchCost << ") terminator: " << *BestUnswitchTI 3024 << "\n"); 3025 unswitchNontrivialInvariants(L, *BestUnswitchTI, BestUnswitchInvariants, 3026 ExitBlocks, PartialIVInfo, DT, LI, AC, 3027 UnswitchCB, SE, MSSAU, DestroyLoopCB); 3028 return true; 3029 } 3030 3031 /// Unswitch control flow predicated on loop invariant conditions. 3032 /// 3033 /// This first hoists all branches or switches which are trivial (IE, do not 3034 /// require duplicating any part of the loop) out of the loop body. It then 3035 /// looks at other loop invariant control flows and tries to unswitch those as 3036 /// well by cloning the loop if the result is small enough. 3037 /// 3038 /// The `DT`, `LI`, `AC`, `AA`, `TTI` parameters are required analyses that are 3039 /// also updated based on the unswitch. The `MSSA` analysis is also updated if 3040 /// valid (i.e. its use is enabled). 3041 /// 3042 /// If either `NonTrivial` is true or the flag `EnableNonTrivialUnswitch` is 3043 /// true, we will attempt to do non-trivial unswitching as well as trivial 3044 /// unswitching. 3045 /// 3046 /// The `UnswitchCB` callback provided will be run after unswitching is 3047 /// complete, with the first parameter set to `true` if the provided loop 3048 /// remains a loop, and a list of new sibling loops created. 3049 /// 3050 /// If `SE` is non-null, we will update that analysis based on the unswitching 3051 /// done. 3052 static bool 3053 unswitchLoop(Loop &L, DominatorTree &DT, LoopInfo &LI, AssumptionCache &AC, 3054 AAResults &AA, TargetTransformInfo &TTI, bool Trivial, 3055 bool NonTrivial, 3056 function_ref<void(bool, bool, ArrayRef<Loop *>)> UnswitchCB, 3057 ScalarEvolution *SE, MemorySSAUpdater *MSSAU, 3058 ProfileSummaryInfo *PSI, BlockFrequencyInfo *BFI, 3059 function_ref<void(Loop &, StringRef)> DestroyLoopCB) { 3060 assert(L.isRecursivelyLCSSAForm(DT, LI) && 3061 "Loops must be in LCSSA form before unswitching."); 3062 3063 // Must be in loop simplified form: we need a preheader and dedicated exits. 3064 if (!L.isLoopSimplifyForm()) 3065 return false; 3066 3067 // Try trivial unswitch first before loop over other basic blocks in the loop. 3068 if (Trivial && unswitchAllTrivialConditions(L, DT, LI, SE, MSSAU)) { 3069 // If we unswitched successfully we will want to clean up the loop before 3070 // processing it further so just mark it as unswitched and return. 3071 UnswitchCB(/*CurrentLoopValid*/ true, false, {}); 3072 return true; 3073 } 3074 3075 // Check whether we should continue with non-trivial conditions. 3076 // EnableNonTrivialUnswitch: Global variable that forces non-trivial 3077 // unswitching for testing and debugging. 3078 // NonTrivial: Parameter that enables non-trivial unswitching for this 3079 // invocation of the transform. But this should be allowed only 3080 // for targets without branch divergence. 3081 // 3082 // FIXME: If divergence analysis becomes available to a loop 3083 // transform, we should allow unswitching for non-trivial uniform 3084 // branches even on targets that have divergence. 3085 // https://bugs.llvm.org/show_bug.cgi?id=48819 3086 bool ContinueWithNonTrivial = 3087 EnableNonTrivialUnswitch || (NonTrivial && !TTI.hasBranchDivergence()); 3088 if (!ContinueWithNonTrivial) 3089 return false; 3090 3091 // Skip non-trivial unswitching for optsize functions. 3092 if (L.getHeader()->getParent()->hasOptSize()) 3093 return false; 3094 3095 // Skip cold loops, as unswitching them brings little benefit 3096 // but increases the code size 3097 if (PSI && PSI->hasProfileSummary() && BFI && 3098 PSI->isFunctionColdInCallGraph(L.getHeader()->getParent(), *BFI)) { 3099 LLVM_DEBUG(dbgs() << " Skip cold loop: " << L << "\n"); 3100 return false; 3101 } 3102 3103 // Skip non-trivial unswitching for loops that cannot be cloned. 3104 if (!L.isSafeToClone()) 3105 return false; 3106 3107 // For non-trivial unswitching, because it often creates new loops, we rely on 3108 // the pass manager to iterate on the loops rather than trying to immediately 3109 // reach a fixed point. There is no substantial advantage to iterating 3110 // internally, and if any of the new loops are simplified enough to contain 3111 // trivial unswitching we want to prefer those. 3112 3113 // Try to unswitch the best invariant condition. We prefer this full unswitch to 3114 // a partial unswitch when possible below the threshold. 3115 if (unswitchBestCondition(L, DT, LI, AC, AA, TTI, UnswitchCB, SE, MSSAU, 3116 DestroyLoopCB)) 3117 return true; 3118 3119 // No other opportunities to unswitch. 3120 return false; 3121 } 3122 3123 PreservedAnalyses SimpleLoopUnswitchPass::run(Loop &L, LoopAnalysisManager &AM, 3124 LoopStandardAnalysisResults &AR, 3125 LPMUpdater &U) { 3126 Function &F = *L.getHeader()->getParent(); 3127 (void)F; 3128 ProfileSummaryInfo *PSI = nullptr; 3129 if (auto OuterProxy = 3130 AM.getResult<FunctionAnalysisManagerLoopProxy>(L, AR) 3131 .getCachedResult<ModuleAnalysisManagerFunctionProxy>(F)) 3132 PSI = OuterProxy->getCachedResult<ProfileSummaryAnalysis>(*F.getParent()); 3133 LLVM_DEBUG(dbgs() << "Unswitching loop in " << F.getName() << ": " << L 3134 << "\n"); 3135 3136 // Save the current loop name in a variable so that we can report it even 3137 // after it has been deleted. 3138 std::string LoopName = std::string(L.getName()); 3139 3140 auto UnswitchCB = [&L, &U, &LoopName](bool CurrentLoopValid, 3141 bool PartiallyInvariant, 3142 ArrayRef<Loop *> NewLoops) { 3143 // If we did a non-trivial unswitch, we have added new (cloned) loops. 3144 if (!NewLoops.empty()) 3145 U.addSiblingLoops(NewLoops); 3146 3147 // If the current loop remains valid, we should revisit it to catch any 3148 // other unswitch opportunities. Otherwise, we need to mark it as deleted. 3149 if (CurrentLoopValid) { 3150 if (PartiallyInvariant) { 3151 // Mark the new loop as partially unswitched, to avoid unswitching on 3152 // the same condition again. 3153 auto &Context = L.getHeader()->getContext(); 3154 MDNode *DisableUnswitchMD = MDNode::get( 3155 Context, 3156 MDString::get(Context, "llvm.loop.unswitch.partial.disable")); 3157 MDNode *NewLoopID = makePostTransformationMetadata( 3158 Context, L.getLoopID(), {"llvm.loop.unswitch.partial"}, 3159 {DisableUnswitchMD}); 3160 L.setLoopID(NewLoopID); 3161 } else 3162 U.revisitCurrentLoop(); 3163 } else 3164 U.markLoopAsDeleted(L, LoopName); 3165 }; 3166 3167 auto DestroyLoopCB = [&U](Loop &L, StringRef Name) { 3168 U.markLoopAsDeleted(L, Name); 3169 }; 3170 3171 Optional<MemorySSAUpdater> MSSAU; 3172 if (AR.MSSA) { 3173 MSSAU = MemorySSAUpdater(AR.MSSA); 3174 if (VerifyMemorySSA) 3175 AR.MSSA->verifyMemorySSA(); 3176 } 3177 if (!unswitchLoop(L, AR.DT, AR.LI, AR.AC, AR.AA, AR.TTI, Trivial, NonTrivial, 3178 UnswitchCB, &AR.SE, MSSAU ? MSSAU.getPointer() : nullptr, 3179 PSI, AR.BFI, DestroyLoopCB)) 3180 return PreservedAnalyses::all(); 3181 3182 if (AR.MSSA && VerifyMemorySSA) 3183 AR.MSSA->verifyMemorySSA(); 3184 3185 // Historically this pass has had issues with the dominator tree so verify it 3186 // in asserts builds. 3187 assert(AR.DT.verify(DominatorTree::VerificationLevel::Fast)); 3188 3189 auto PA = getLoopPassPreservedAnalyses(); 3190 if (AR.MSSA) 3191 PA.preserve<MemorySSAAnalysis>(); 3192 return PA; 3193 } 3194 3195 void SimpleLoopUnswitchPass::printPipeline( 3196 raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) { 3197 static_cast<PassInfoMixin<SimpleLoopUnswitchPass> *>(this)->printPipeline( 3198 OS, MapClassName2PassName); 3199 3200 OS << "<"; 3201 OS << (NonTrivial ? "" : "no-") << "nontrivial;"; 3202 OS << (Trivial ? "" : "no-") << "trivial"; 3203 OS << ">"; 3204 } 3205 3206 namespace { 3207 3208 class SimpleLoopUnswitchLegacyPass : public LoopPass { 3209 bool NonTrivial; 3210 3211 public: 3212 static char ID; // Pass ID, replacement for typeid 3213 3214 explicit SimpleLoopUnswitchLegacyPass(bool NonTrivial = false) 3215 : LoopPass(ID), NonTrivial(NonTrivial) { 3216 initializeSimpleLoopUnswitchLegacyPassPass( 3217 *PassRegistry::getPassRegistry()); 3218 } 3219 3220 bool runOnLoop(Loop *L, LPPassManager &LPM) override; 3221 3222 void getAnalysisUsage(AnalysisUsage &AU) const override { 3223 AU.addRequired<AssumptionCacheTracker>(); 3224 AU.addRequired<TargetTransformInfoWrapperPass>(); 3225 AU.addRequired<MemorySSAWrapperPass>(); 3226 AU.addPreserved<MemorySSAWrapperPass>(); 3227 getLoopAnalysisUsage(AU); 3228 } 3229 }; 3230 3231 } // end anonymous namespace 3232 3233 bool SimpleLoopUnswitchLegacyPass::runOnLoop(Loop *L, LPPassManager &LPM) { 3234 if (skipLoop(L)) 3235 return false; 3236 3237 Function &F = *L->getHeader()->getParent(); 3238 3239 LLVM_DEBUG(dbgs() << "Unswitching loop in " << F.getName() << ": " << *L 3240 << "\n"); 3241 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 3242 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); 3243 auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F); 3244 auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults(); 3245 auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F); 3246 MemorySSA *MSSA = &getAnalysis<MemorySSAWrapperPass>().getMSSA(); 3247 MemorySSAUpdater MSSAU(MSSA); 3248 3249 auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>(); 3250 auto *SE = SEWP ? &SEWP->getSE() : nullptr; 3251 3252 auto UnswitchCB = [&L, &LPM](bool CurrentLoopValid, bool PartiallyInvariant, 3253 ArrayRef<Loop *> NewLoops) { 3254 // If we did a non-trivial unswitch, we have added new (cloned) loops. 3255 for (auto *NewL : NewLoops) 3256 LPM.addLoop(*NewL); 3257 3258 // If the current loop remains valid, re-add it to the queue. This is 3259 // a little wasteful as we'll finish processing the current loop as well, 3260 // but it is the best we can do in the old PM. 3261 if (CurrentLoopValid) { 3262 // If the current loop has been unswitched using a partially invariant 3263 // condition, we should not re-add the current loop to avoid unswitching 3264 // on the same condition again. 3265 if (!PartiallyInvariant) 3266 LPM.addLoop(*L); 3267 } else 3268 LPM.markLoopAsDeleted(*L); 3269 }; 3270 3271 auto DestroyLoopCB = [&LPM](Loop &L, StringRef /* Name */) { 3272 LPM.markLoopAsDeleted(L); 3273 }; 3274 3275 if (VerifyMemorySSA) 3276 MSSA->verifyMemorySSA(); 3277 bool Changed = 3278 unswitchLoop(*L, DT, LI, AC, AA, TTI, true, NonTrivial, UnswitchCB, SE, 3279 &MSSAU, nullptr, nullptr, DestroyLoopCB); 3280 3281 if (VerifyMemorySSA) 3282 MSSA->verifyMemorySSA(); 3283 3284 // Historically this pass has had issues with the dominator tree so verify it 3285 // in asserts builds. 3286 assert(DT.verify(DominatorTree::VerificationLevel::Fast)); 3287 3288 return Changed; 3289 } 3290 3291 char SimpleLoopUnswitchLegacyPass::ID = 0; 3292 INITIALIZE_PASS_BEGIN(SimpleLoopUnswitchLegacyPass, "simple-loop-unswitch", 3293 "Simple unswitch loops", false, false) 3294 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) 3295 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 3296 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) 3297 INITIALIZE_PASS_DEPENDENCY(LoopPass) 3298 INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass) 3299 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) 3300 INITIALIZE_PASS_END(SimpleLoopUnswitchLegacyPass, "simple-loop-unswitch", 3301 "Simple unswitch loops", false, false) 3302 3303 Pass *llvm::createSimpleLoopUnswitchLegacyPass(bool NonTrivial) { 3304 return new SimpleLoopUnswitchLegacyPass(NonTrivial); 3305 } 3306