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