1 //===----------------- LoopRotationUtils.cpp -----------------------------===// 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 // This file provides utilities to convert a loop into a loop with bottom test. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #include "llvm/Transforms/Utils/LoopRotationUtils.h" 14 #include "llvm/ADT/Statistic.h" 15 #include "llvm/Analysis/AssumptionCache.h" 16 #include "llvm/Analysis/CodeMetrics.h" 17 #include "llvm/Analysis/DomTreeUpdater.h" 18 #include "llvm/Analysis/InstructionSimplify.h" 19 #include "llvm/Analysis/LoopInfo.h" 20 #include "llvm/Analysis/MemorySSA.h" 21 #include "llvm/Analysis/MemorySSAUpdater.h" 22 #include "llvm/Analysis/ScalarEvolution.h" 23 #include "llvm/Analysis/ValueTracking.h" 24 #include "llvm/IR/CFG.h" 25 #include "llvm/IR/DebugInfo.h" 26 #include "llvm/IR/Dominators.h" 27 #include "llvm/IR/IntrinsicInst.h" 28 #include "llvm/IR/MDBuilder.h" 29 #include "llvm/IR/ProfDataUtils.h" 30 #include "llvm/Support/CommandLine.h" 31 #include "llvm/Support/Debug.h" 32 #include "llvm/Support/raw_ostream.h" 33 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 34 #include "llvm/Transforms/Utils/Cloning.h" 35 #include "llvm/Transforms/Utils/Local.h" 36 #include "llvm/Transforms/Utils/SSAUpdater.h" 37 #include "llvm/Transforms/Utils/ValueMapper.h" 38 using namespace llvm; 39 40 #define DEBUG_TYPE "loop-rotate" 41 42 STATISTIC(NumNotRotatedDueToHeaderSize, 43 "Number of loops not rotated due to the header size"); 44 STATISTIC(NumInstrsHoisted, 45 "Number of instructions hoisted into loop preheader"); 46 STATISTIC(NumInstrsDuplicated, 47 "Number of instructions cloned into loop preheader"); 48 STATISTIC(NumRotated, "Number of loops rotated"); 49 50 static cl::opt<bool> 51 MultiRotate("loop-rotate-multi", cl::init(false), cl::Hidden, 52 cl::desc("Allow loop rotation multiple times in order to reach " 53 "a better latch exit")); 54 55 // Probability that a rotated loop has zero trip count / is never entered. 56 static constexpr uint32_t ZeroTripCountWeights[] = {1, 127}; 57 58 namespace { 59 /// A simple loop rotation transformation. 60 class LoopRotate { 61 const unsigned MaxHeaderSize; 62 LoopInfo *LI; 63 const TargetTransformInfo *TTI; 64 AssumptionCache *AC; 65 DominatorTree *DT; 66 ScalarEvolution *SE; 67 MemorySSAUpdater *MSSAU; 68 const SimplifyQuery &SQ; 69 bool RotationOnly; 70 bool IsUtilMode; 71 bool PrepareForLTO; 72 73 public: 74 LoopRotate(unsigned MaxHeaderSize, LoopInfo *LI, 75 const TargetTransformInfo *TTI, AssumptionCache *AC, 76 DominatorTree *DT, ScalarEvolution *SE, MemorySSAUpdater *MSSAU, 77 const SimplifyQuery &SQ, bool RotationOnly, bool IsUtilMode, 78 bool PrepareForLTO) 79 : MaxHeaderSize(MaxHeaderSize), LI(LI), TTI(TTI), AC(AC), DT(DT), SE(SE), 80 MSSAU(MSSAU), SQ(SQ), RotationOnly(RotationOnly), 81 IsUtilMode(IsUtilMode), PrepareForLTO(PrepareForLTO) {} 82 bool processLoop(Loop *L); 83 84 private: 85 bool rotateLoop(Loop *L, bool SimplifiedLatch); 86 bool simplifyLoopLatch(Loop *L); 87 }; 88 } // end anonymous namespace 89 90 /// Insert (K, V) pair into the ValueToValueMap, and verify the key did not 91 /// previously exist in the map, and the value was inserted. 92 static void InsertNewValueIntoMap(ValueToValueMapTy &VM, Value *K, Value *V) { 93 bool Inserted = VM.insert({K, V}).second; 94 assert(Inserted); 95 (void)Inserted; 96 } 97 /// RewriteUsesOfClonedInstructions - We just cloned the instructions from the 98 /// old header into the preheader. If there were uses of the values produced by 99 /// these instruction that were outside of the loop, we have to insert PHI nodes 100 /// to merge the two values. Do this now. 101 static void RewriteUsesOfClonedInstructions(BasicBlock *OrigHeader, 102 BasicBlock *OrigPreheader, 103 ValueToValueMapTy &ValueMap, 104 ScalarEvolution *SE, 105 SmallVectorImpl<PHINode*> *InsertedPHIs) { 106 // Remove PHI node entries that are no longer live. 107 BasicBlock::iterator I, E = OrigHeader->end(); 108 for (I = OrigHeader->begin(); PHINode *PN = dyn_cast<PHINode>(I); ++I) 109 PN->removeIncomingValue(PN->getBasicBlockIndex(OrigPreheader)); 110 111 // Now fix up users of the instructions in OrigHeader, inserting PHI nodes 112 // as necessary. 113 SSAUpdater SSA(InsertedPHIs); 114 for (I = OrigHeader->begin(); I != E; ++I) { 115 Value *OrigHeaderVal = &*I; 116 117 // If there are no uses of the value (e.g. because it returns void), there 118 // is nothing to rewrite. 119 if (OrigHeaderVal->use_empty()) 120 continue; 121 122 Value *OrigPreHeaderVal = ValueMap.lookup(OrigHeaderVal); 123 124 // The value now exits in two versions: the initial value in the preheader 125 // and the loop "next" value in the original header. 126 SSA.Initialize(OrigHeaderVal->getType(), OrigHeaderVal->getName()); 127 // Force re-computation of OrigHeaderVal, as some users now need to use the 128 // new PHI node. 129 if (SE) 130 SE->forgetValue(OrigHeaderVal); 131 SSA.AddAvailableValue(OrigHeader, OrigHeaderVal); 132 SSA.AddAvailableValue(OrigPreheader, OrigPreHeaderVal); 133 134 // Visit each use of the OrigHeader instruction. 135 for (Use &U : llvm::make_early_inc_range(OrigHeaderVal->uses())) { 136 // SSAUpdater can't handle a non-PHI use in the same block as an 137 // earlier def. We can easily handle those cases manually. 138 Instruction *UserInst = cast<Instruction>(U.getUser()); 139 if (!isa<PHINode>(UserInst)) { 140 BasicBlock *UserBB = UserInst->getParent(); 141 142 // The original users in the OrigHeader are already using the 143 // original definitions. 144 if (UserBB == OrigHeader) 145 continue; 146 147 // Users in the OrigPreHeader need to use the value to which the 148 // original definitions are mapped. 149 if (UserBB == OrigPreheader) { 150 U = OrigPreHeaderVal; 151 continue; 152 } 153 } 154 155 // Anything else can be handled by SSAUpdater. 156 SSA.RewriteUse(U); 157 } 158 159 // Replace MetadataAsValue(ValueAsMetadata(OrigHeaderVal)) uses in debug 160 // intrinsics. 161 SmallVector<DbgValueInst *, 1> DbgValues; 162 llvm::findDbgValues(DbgValues, OrigHeaderVal); 163 for (auto &DbgValue : DbgValues) { 164 // The original users in the OrigHeader are already using the original 165 // definitions. 166 BasicBlock *UserBB = DbgValue->getParent(); 167 if (UserBB == OrigHeader) 168 continue; 169 170 // Users in the OrigPreHeader need to use the value to which the 171 // original definitions are mapped and anything else can be handled by 172 // the SSAUpdater. To avoid adding PHINodes, check if the value is 173 // available in UserBB, if not substitute undef. 174 Value *NewVal; 175 if (UserBB == OrigPreheader) 176 NewVal = OrigPreHeaderVal; 177 else if (SSA.HasValueForBlock(UserBB)) 178 NewVal = SSA.GetValueInMiddleOfBlock(UserBB); 179 else 180 NewVal = UndefValue::get(OrigHeaderVal->getType()); 181 DbgValue->replaceVariableLocationOp(OrigHeaderVal, NewVal); 182 } 183 } 184 } 185 186 // Assuming both header and latch are exiting, look for a phi which is only 187 // used outside the loop (via a LCSSA phi) in the exit from the header. 188 // This means that rotating the loop can remove the phi. 189 static bool profitableToRotateLoopExitingLatch(Loop *L) { 190 BasicBlock *Header = L->getHeader(); 191 BranchInst *BI = dyn_cast<BranchInst>(Header->getTerminator()); 192 assert(BI && BI->isConditional() && "need header with conditional exit"); 193 BasicBlock *HeaderExit = BI->getSuccessor(0); 194 if (L->contains(HeaderExit)) 195 HeaderExit = BI->getSuccessor(1); 196 197 for (auto &Phi : Header->phis()) { 198 // Look for uses of this phi in the loop/via exits other than the header. 199 if (llvm::any_of(Phi.users(), [HeaderExit](const User *U) { 200 return cast<Instruction>(U)->getParent() != HeaderExit; 201 })) 202 continue; 203 return true; 204 } 205 return false; 206 } 207 208 // Check that latch exit is deoptimizing (which means - very unlikely to happen) 209 // and there is another exit from the loop which is non-deoptimizing. 210 // If we rotate latch to that exit our loop has a better chance of being fully 211 // canonical. 212 // 213 // It can give false positives in some rare cases. 214 static bool canRotateDeoptimizingLatchExit(Loop *L) { 215 BasicBlock *Latch = L->getLoopLatch(); 216 assert(Latch && "need latch"); 217 BranchInst *BI = dyn_cast<BranchInst>(Latch->getTerminator()); 218 // Need normal exiting latch. 219 if (!BI || !BI->isConditional()) 220 return false; 221 222 BasicBlock *Exit = BI->getSuccessor(1); 223 if (L->contains(Exit)) 224 Exit = BI->getSuccessor(0); 225 226 // Latch exit is non-deoptimizing, no need to rotate. 227 if (!Exit->getPostdominatingDeoptimizeCall()) 228 return false; 229 230 SmallVector<BasicBlock *, 4> Exits; 231 L->getUniqueExitBlocks(Exits); 232 if (!Exits.empty()) { 233 // There is at least one non-deoptimizing exit. 234 // 235 // Note, that BasicBlock::getPostdominatingDeoptimizeCall is not exact, 236 // as it can conservatively return false for deoptimizing exits with 237 // complex enough control flow down to deoptimize call. 238 // 239 // That means here we can report success for a case where 240 // all exits are deoptimizing but one of them has complex enough 241 // control flow (e.g. with loops). 242 // 243 // That should be a very rare case and false positives for this function 244 // have compile-time effect only. 245 return any_of(Exits, [](const BasicBlock *BB) { 246 return !BB->getPostdominatingDeoptimizeCall(); 247 }); 248 } 249 return false; 250 } 251 252 static void updateBranchWeights(BranchInst &PreHeaderBI, BranchInst &LoopBI, 253 bool HasConditionalPreHeader, 254 bool SuccsSwapped) { 255 MDNode *WeightMD = getBranchWeightMDNode(PreHeaderBI); 256 if (WeightMD == nullptr) 257 return; 258 259 // LoopBI should currently be a clone of PreHeaderBI with the same 260 // metadata. But we double check to make sure we don't have a degenerate case 261 // where instsimplify changed the instructions. 262 if (WeightMD != getBranchWeightMDNode(LoopBI)) 263 return; 264 265 SmallVector<uint32_t, 2> Weights; 266 extractFromBranchWeightMD(WeightMD, Weights); 267 if (Weights.size() != 2) 268 return; 269 uint32_t OrigLoopExitWeight = Weights[0]; 270 uint32_t OrigLoopBackedgeWeight = Weights[1]; 271 272 if (SuccsSwapped) 273 std::swap(OrigLoopExitWeight, OrigLoopBackedgeWeight); 274 275 // Update branch weights. Consider the following edge-counts: 276 // 277 // | |-------- | 278 // V V | V 279 // Br i1 ... | Br i1 ... 280 // | | | | | 281 // x| y| | becomes: | y0| |----- 282 // V V | | V V | 283 // Exit Loop | | Loop | 284 // | | | Br i1 ... | 285 // ----- | | | | 286 // x0| x1| y1 | | 287 // V V ---- 288 // Exit 289 // 290 // The following must hold: 291 // - x == x0 + x1 # counts to "exit" must stay the same. 292 // - y0 == x - x0 == x1 # how often loop was entered at all. 293 // - y1 == y - y0 # How often loop was repeated (after first iter.). 294 // 295 // We cannot generally deduce how often we had a zero-trip count loop so we 296 // have to make a guess for how to distribute x among the new x0 and x1. 297 298 uint32_t ExitWeight0; // aka x0 299 uint32_t ExitWeight1; // aka x1 300 uint32_t EnterWeight; // aka y0 301 uint32_t LoopBackWeight; // aka y1 302 if (OrigLoopExitWeight > 0 && OrigLoopBackedgeWeight > 0) { 303 ExitWeight0 = 0; 304 if (HasConditionalPreHeader) { 305 // Here we cannot know how many 0-trip count loops we have, so we guess: 306 if (OrigLoopBackedgeWeight >= OrigLoopExitWeight) { 307 // If the loop count is bigger than the exit count then we set 308 // probabilities as if 0-trip count nearly never happens. 309 ExitWeight0 = ZeroTripCountWeights[0]; 310 // Scale up counts if necessary so we can match `ZeroTripCountWeights` 311 // for the `ExitWeight0`:`ExitWeight1` (aka `x0`:`x1` ratio`) ratio. 312 while (OrigLoopExitWeight < ZeroTripCountWeights[1] + ExitWeight0) { 313 // ... but don't overflow. 314 uint32_t const HighBit = uint32_t{1} << (sizeof(uint32_t) * 8 - 1); 315 if ((OrigLoopBackedgeWeight & HighBit) != 0 || 316 (OrigLoopExitWeight & HighBit) != 0) 317 break; 318 OrigLoopBackedgeWeight <<= 1; 319 OrigLoopExitWeight <<= 1; 320 } 321 } else { 322 // If there's a higher exit-count than backedge-count then we set 323 // probabilities as if there are only 0-trip and 1-trip cases. 324 ExitWeight0 = OrigLoopExitWeight - OrigLoopBackedgeWeight; 325 } 326 } 327 ExitWeight1 = OrigLoopExitWeight - ExitWeight0; 328 EnterWeight = ExitWeight1; 329 LoopBackWeight = OrigLoopBackedgeWeight - EnterWeight; 330 } else if (OrigLoopExitWeight == 0) { 331 if (OrigLoopBackedgeWeight == 0) { 332 // degenerate case... keep everything zero... 333 ExitWeight0 = 0; 334 ExitWeight1 = 0; 335 EnterWeight = 0; 336 LoopBackWeight = 0; 337 } else { 338 // Special case "LoopExitWeight == 0" weights which behaves like an 339 // endless where we don't want loop-enttry (y0) to be the same as 340 // loop-exit (x1). 341 ExitWeight0 = 0; 342 ExitWeight1 = 0; 343 EnterWeight = 1; 344 LoopBackWeight = OrigLoopBackedgeWeight; 345 } 346 } else { 347 // loop is never entered. 348 assert(OrigLoopBackedgeWeight == 0 && "remaining case is backedge zero"); 349 ExitWeight0 = 1; 350 ExitWeight1 = 1; 351 EnterWeight = 0; 352 LoopBackWeight = 0; 353 } 354 355 const uint32_t LoopBIWeights[] = { 356 SuccsSwapped ? LoopBackWeight : ExitWeight1, 357 SuccsSwapped ? ExitWeight1 : LoopBackWeight, 358 }; 359 setBranchWeights(LoopBI, LoopBIWeights); 360 if (HasConditionalPreHeader) { 361 const uint32_t PreHeaderBIWeights[] = { 362 SuccsSwapped ? EnterWeight : ExitWeight0, 363 SuccsSwapped ? ExitWeight0 : EnterWeight, 364 }; 365 setBranchWeights(PreHeaderBI, PreHeaderBIWeights); 366 } 367 } 368 369 /// Rotate loop LP. Return true if the loop is rotated. 370 /// 371 /// \param SimplifiedLatch is true if the latch was just folded into the final 372 /// loop exit. In this case we may want to rotate even though the new latch is 373 /// now an exiting branch. This rotation would have happened had the latch not 374 /// been simplified. However, if SimplifiedLatch is false, then we avoid 375 /// rotating loops in which the latch exits to avoid excessive or endless 376 /// rotation. LoopRotate should be repeatable and converge to a canonical 377 /// form. This property is satisfied because simplifying the loop latch can only 378 /// happen once across multiple invocations of the LoopRotate pass. 379 /// 380 /// If -loop-rotate-multi is enabled we can do multiple rotations in one go 381 /// so to reach a suitable (non-deoptimizing) exit. 382 bool LoopRotate::rotateLoop(Loop *L, bool SimplifiedLatch) { 383 // If the loop has only one block then there is not much to rotate. 384 if (L->getBlocks().size() == 1) 385 return false; 386 387 bool Rotated = false; 388 do { 389 BasicBlock *OrigHeader = L->getHeader(); 390 BasicBlock *OrigLatch = L->getLoopLatch(); 391 392 BranchInst *BI = dyn_cast<BranchInst>(OrigHeader->getTerminator()); 393 if (!BI || BI->isUnconditional()) 394 return Rotated; 395 396 // If the loop header is not one of the loop exiting blocks then 397 // either this loop is already rotated or it is not 398 // suitable for loop rotation transformations. 399 if (!L->isLoopExiting(OrigHeader)) 400 return Rotated; 401 402 // If the loop latch already contains a branch that leaves the loop then the 403 // loop is already rotated. 404 if (!OrigLatch) 405 return Rotated; 406 407 // Rotate if either the loop latch does *not* exit the loop, or if the loop 408 // latch was just simplified. Or if we think it will be profitable. 409 if (L->isLoopExiting(OrigLatch) && !SimplifiedLatch && IsUtilMode == false && 410 !profitableToRotateLoopExitingLatch(L) && 411 !canRotateDeoptimizingLatchExit(L)) 412 return Rotated; 413 414 // Check size of original header and reject loop if it is very big or we can't 415 // duplicate blocks inside it. 416 { 417 SmallPtrSet<const Value *, 32> EphValues; 418 CodeMetrics::collectEphemeralValues(L, AC, EphValues); 419 420 CodeMetrics Metrics; 421 Metrics.analyzeBasicBlock(OrigHeader, *TTI, EphValues, PrepareForLTO); 422 if (Metrics.notDuplicatable) { 423 LLVM_DEBUG( 424 dbgs() << "LoopRotation: NOT rotating - contains non-duplicatable" 425 << " instructions: "; 426 L->dump()); 427 return Rotated; 428 } 429 if (Metrics.convergent) { 430 LLVM_DEBUG(dbgs() << "LoopRotation: NOT rotating - contains convergent " 431 "instructions: "; 432 L->dump()); 433 return Rotated; 434 } 435 if (!Metrics.NumInsts.isValid()) { 436 LLVM_DEBUG(dbgs() << "LoopRotation: NOT rotating - contains instructions" 437 " with invalid cost: "; 438 L->dump()); 439 return Rotated; 440 } 441 if (Metrics.NumInsts > MaxHeaderSize) { 442 LLVM_DEBUG(dbgs() << "LoopRotation: NOT rotating - contains " 443 << Metrics.NumInsts 444 << " instructions, which is more than the threshold (" 445 << MaxHeaderSize << " instructions): "; 446 L->dump()); 447 ++NumNotRotatedDueToHeaderSize; 448 return Rotated; 449 } 450 451 // When preparing for LTO, avoid rotating loops with calls that could be 452 // inlined during the LTO stage. 453 if (PrepareForLTO && Metrics.NumInlineCandidates > 0) 454 return Rotated; 455 } 456 457 // Now, this loop is suitable for rotation. 458 BasicBlock *OrigPreheader = L->getLoopPreheader(); 459 460 // If the loop could not be converted to canonical form, it must have an 461 // indirectbr in it, just give up. 462 if (!OrigPreheader || !L->hasDedicatedExits()) 463 return Rotated; 464 465 // Anything ScalarEvolution may know about this loop or the PHI nodes 466 // in its header will soon be invalidated. We should also invalidate 467 // all outer loops because insertion and deletion of blocks that happens 468 // during the rotation may violate invariants related to backedge taken 469 // infos in them. 470 if (SE) { 471 SE->forgetTopmostLoop(L); 472 // We may hoist some instructions out of loop. In case if they were cached 473 // as "loop variant" or "loop computable", these caches must be dropped. 474 // We also may fold basic blocks, so cached block dispositions also need 475 // to be dropped. 476 SE->forgetBlockAndLoopDispositions(); 477 } 478 479 LLVM_DEBUG(dbgs() << "LoopRotation: rotating "; L->dump()); 480 if (MSSAU && VerifyMemorySSA) 481 MSSAU->getMemorySSA()->verifyMemorySSA(); 482 483 // Find new Loop header. NewHeader is a Header's one and only successor 484 // that is inside loop. Header's other successor is outside the 485 // loop. Otherwise loop is not suitable for rotation. 486 BasicBlock *Exit = BI->getSuccessor(0); 487 BasicBlock *NewHeader = BI->getSuccessor(1); 488 bool BISuccsSwapped = L->contains(Exit); 489 if (BISuccsSwapped) 490 std::swap(Exit, NewHeader); 491 assert(NewHeader && "Unable to determine new loop header"); 492 assert(L->contains(NewHeader) && !L->contains(Exit) && 493 "Unable to determine loop header and exit blocks"); 494 495 // This code assumes that the new header has exactly one predecessor. 496 // Remove any single-entry PHI nodes in it. 497 assert(NewHeader->getSinglePredecessor() && 498 "New header doesn't have one pred!"); 499 FoldSingleEntryPHINodes(NewHeader); 500 501 // Begin by walking OrigHeader and populating ValueMap with an entry for 502 // each Instruction. 503 BasicBlock::iterator I = OrigHeader->begin(), E = OrigHeader->end(); 504 ValueToValueMapTy ValueMap, ValueMapMSSA; 505 506 // For PHI nodes, the value available in OldPreHeader is just the 507 // incoming value from OldPreHeader. 508 for (; PHINode *PN = dyn_cast<PHINode>(I); ++I) 509 InsertNewValueIntoMap(ValueMap, PN, 510 PN->getIncomingValueForBlock(OrigPreheader)); 511 512 // For the rest of the instructions, either hoist to the OrigPreheader if 513 // possible or create a clone in the OldPreHeader if not. 514 Instruction *LoopEntryBranch = OrigPreheader->getTerminator(); 515 516 // Record all debug intrinsics preceding LoopEntryBranch to avoid 517 // duplication. 518 using DbgIntrinsicHash = 519 std::pair<std::pair<hash_code, DILocalVariable *>, DIExpression *>; 520 auto makeHash = [](DbgVariableIntrinsic *D) -> DbgIntrinsicHash { 521 auto VarLocOps = D->location_ops(); 522 return {{hash_combine_range(VarLocOps.begin(), VarLocOps.end()), 523 D->getVariable()}, 524 D->getExpression()}; 525 }; 526 SmallDenseSet<DbgIntrinsicHash, 8> DbgIntrinsics; 527 for (Instruction &I : llvm::drop_begin(llvm::reverse(*OrigPreheader))) { 528 if (auto *DII = dyn_cast<DbgVariableIntrinsic>(&I)) 529 DbgIntrinsics.insert(makeHash(DII)); 530 else 531 break; 532 } 533 534 // Remember the local noalias scope declarations in the header. After the 535 // rotation, they must be duplicated and the scope must be cloned. This 536 // avoids unwanted interaction across iterations. 537 SmallVector<NoAliasScopeDeclInst *, 6> NoAliasDeclInstructions; 538 for (Instruction &I : *OrigHeader) 539 if (auto *Decl = dyn_cast<NoAliasScopeDeclInst>(&I)) 540 NoAliasDeclInstructions.push_back(Decl); 541 542 while (I != E) { 543 Instruction *Inst = &*I++; 544 545 // If the instruction's operands are invariant and it doesn't read or write 546 // memory, then it is safe to hoist. Doing this doesn't change the order of 547 // execution in the preheader, but does prevent the instruction from 548 // executing in each iteration of the loop. This means it is safe to hoist 549 // something that might trap, but isn't safe to hoist something that reads 550 // memory (without proving that the loop doesn't write). 551 if (L->hasLoopInvariantOperands(Inst) && !Inst->mayReadFromMemory() && 552 !Inst->mayWriteToMemory() && !Inst->isTerminator() && 553 !isa<DbgInfoIntrinsic>(Inst) && !isa<AllocaInst>(Inst)) { 554 Inst->moveBefore(LoopEntryBranch); 555 ++NumInstrsHoisted; 556 continue; 557 } 558 559 // Otherwise, create a duplicate of the instruction. 560 Instruction *C = Inst->clone(); 561 C->insertBefore(LoopEntryBranch); 562 563 ++NumInstrsDuplicated; 564 565 // Eagerly remap the operands of the instruction. 566 RemapInstruction(C, ValueMap, 567 RF_NoModuleLevelChanges | RF_IgnoreMissingLocals); 568 569 // Avoid inserting the same intrinsic twice. 570 if (auto *DII = dyn_cast<DbgVariableIntrinsic>(C)) 571 if (DbgIntrinsics.count(makeHash(DII))) { 572 C->eraseFromParent(); 573 continue; 574 } 575 576 // With the operands remapped, see if the instruction constant folds or is 577 // otherwise simplifyable. This commonly occurs because the entry from PHI 578 // nodes allows icmps and other instructions to fold. 579 Value *V = simplifyInstruction(C, SQ); 580 if (V && LI->replacementPreservesLCSSAForm(C, V)) { 581 // If so, then delete the temporary instruction and stick the folded value 582 // in the map. 583 InsertNewValueIntoMap(ValueMap, Inst, V); 584 if (!C->mayHaveSideEffects()) { 585 C->eraseFromParent(); 586 C = nullptr; 587 } 588 } else { 589 InsertNewValueIntoMap(ValueMap, Inst, C); 590 } 591 if (C) { 592 // Otherwise, stick the new instruction into the new block! 593 C->setName(Inst->getName()); 594 595 if (auto *II = dyn_cast<AssumeInst>(C)) 596 AC->registerAssumption(II); 597 // MemorySSA cares whether the cloned instruction was inserted or not, and 598 // not whether it can be remapped to a simplified value. 599 if (MSSAU) 600 InsertNewValueIntoMap(ValueMapMSSA, Inst, C); 601 } 602 } 603 604 if (!NoAliasDeclInstructions.empty()) { 605 // There are noalias scope declarations: 606 // (general): 607 // Original: OrigPre { OrigHeader NewHeader ... Latch } 608 // after: (OrigPre+OrigHeader') { NewHeader ... Latch OrigHeader } 609 // 610 // with D: llvm.experimental.noalias.scope.decl, 611 // U: !noalias or !alias.scope depending on D 612 // ... { D U1 U2 } can transform into: 613 // (0) : ... { D U1 U2 } // no relevant rotation for this part 614 // (1) : ... D' { U1 U2 D } // D is part of OrigHeader 615 // (2) : ... D' U1' { U2 D U1 } // D, U1 are part of OrigHeader 616 // 617 // We now want to transform: 618 // (1) -> : ... D' { D U1 U2 D'' } 619 // (2) -> : ... D' U1' { D U2 D'' U1'' } 620 // D: original llvm.experimental.noalias.scope.decl 621 // D', U1': duplicate with replaced scopes 622 // D'', U1'': different duplicate with replaced scopes 623 // This ensures a safe fallback to 'may_alias' introduced by the rotate, 624 // as U1'' and U1' scopes will not be compatible wrt to the local restrict 625 626 // Clone the llvm.experimental.noalias.decl again for the NewHeader. 627 Instruction *NewHeaderInsertionPoint = &(*NewHeader->getFirstNonPHI()); 628 for (NoAliasScopeDeclInst *NAD : NoAliasDeclInstructions) { 629 LLVM_DEBUG(dbgs() << " Cloning llvm.experimental.noalias.scope.decl:" 630 << *NAD << "\n"); 631 Instruction *NewNAD = NAD->clone(); 632 NewNAD->insertBefore(NewHeaderInsertionPoint); 633 } 634 635 // Scopes must now be duplicated, once for OrigHeader and once for 636 // OrigPreHeader'. 637 { 638 auto &Context = NewHeader->getContext(); 639 640 SmallVector<MDNode *, 8> NoAliasDeclScopes; 641 for (NoAliasScopeDeclInst *NAD : NoAliasDeclInstructions) 642 NoAliasDeclScopes.push_back(NAD->getScopeList()); 643 644 LLVM_DEBUG(dbgs() << " Updating OrigHeader scopes\n"); 645 cloneAndAdaptNoAliasScopes(NoAliasDeclScopes, {OrigHeader}, Context, 646 "h.rot"); 647 LLVM_DEBUG(OrigHeader->dump()); 648 649 // Keep the compile time impact low by only adapting the inserted block 650 // of instructions in the OrigPreHeader. This might result in slightly 651 // more aliasing between these instructions and those that were already 652 // present, but it will be much faster when the original PreHeader is 653 // large. 654 LLVM_DEBUG(dbgs() << " Updating part of OrigPreheader scopes\n"); 655 auto *FirstDecl = 656 cast<Instruction>(ValueMap[*NoAliasDeclInstructions.begin()]); 657 auto *LastInst = &OrigPreheader->back(); 658 cloneAndAdaptNoAliasScopes(NoAliasDeclScopes, FirstDecl, LastInst, 659 Context, "pre.rot"); 660 LLVM_DEBUG(OrigPreheader->dump()); 661 662 LLVM_DEBUG(dbgs() << " Updated NewHeader:\n"); 663 LLVM_DEBUG(NewHeader->dump()); 664 } 665 } 666 667 // Along with all the other instructions, we just cloned OrigHeader's 668 // terminator into OrigPreHeader. Fix up the PHI nodes in each of OrigHeader's 669 // successors by duplicating their incoming values for OrigHeader. 670 for (BasicBlock *SuccBB : successors(OrigHeader)) 671 for (BasicBlock::iterator BI = SuccBB->begin(); 672 PHINode *PN = dyn_cast<PHINode>(BI); ++BI) 673 PN->addIncoming(PN->getIncomingValueForBlock(OrigHeader), OrigPreheader); 674 675 // Now that OrigPreHeader has a clone of OrigHeader's terminator, remove 676 // OrigPreHeader's old terminator (the original branch into the loop), and 677 // remove the corresponding incoming values from the PHI nodes in OrigHeader. 678 LoopEntryBranch->eraseFromParent(); 679 680 // Update MemorySSA before the rewrite call below changes the 1:1 681 // instruction:cloned_instruction_or_value mapping. 682 if (MSSAU) { 683 InsertNewValueIntoMap(ValueMapMSSA, OrigHeader, OrigPreheader); 684 MSSAU->updateForClonedBlockIntoPred(OrigHeader, OrigPreheader, 685 ValueMapMSSA); 686 } 687 688 SmallVector<PHINode*, 2> InsertedPHIs; 689 // If there were any uses of instructions in the duplicated block outside the 690 // loop, update them, inserting PHI nodes as required 691 RewriteUsesOfClonedInstructions(OrigHeader, OrigPreheader, ValueMap, SE, 692 &InsertedPHIs); 693 694 // Attach dbg.value intrinsics to the new phis if that phi uses a value that 695 // previously had debug metadata attached. This keeps the debug info 696 // up-to-date in the loop body. 697 if (!InsertedPHIs.empty()) 698 insertDebugValuesForPHIs(OrigHeader, InsertedPHIs); 699 700 // NewHeader is now the header of the loop. 701 L->moveToHeader(NewHeader); 702 assert(L->getHeader() == NewHeader && "Latch block is our new header"); 703 704 // Inform DT about changes to the CFG. 705 if (DT) { 706 // The OrigPreheader branches to the NewHeader and Exit now. Then, inform 707 // the DT about the removed edge to the OrigHeader (that got removed). 708 SmallVector<DominatorTree::UpdateType, 3> Updates; 709 Updates.push_back({DominatorTree::Insert, OrigPreheader, Exit}); 710 Updates.push_back({DominatorTree::Insert, OrigPreheader, NewHeader}); 711 Updates.push_back({DominatorTree::Delete, OrigPreheader, OrigHeader}); 712 713 if (MSSAU) { 714 MSSAU->applyUpdates(Updates, *DT, /*UpdateDT=*/true); 715 if (VerifyMemorySSA) 716 MSSAU->getMemorySSA()->verifyMemorySSA(); 717 } else { 718 DT->applyUpdates(Updates); 719 } 720 } 721 722 // At this point, we've finished our major CFG changes. As part of cloning 723 // the loop into the preheader we've simplified instructions and the 724 // duplicated conditional branch may now be branching on a constant. If it is 725 // branching on a constant and if that constant means that we enter the loop, 726 // then we fold away the cond branch to an uncond branch. This simplifies the 727 // loop in cases important for nested loops, and it also means we don't have 728 // to split as many edges. 729 BranchInst *PHBI = cast<BranchInst>(OrigPreheader->getTerminator()); 730 assert(PHBI->isConditional() && "Should be clone of BI condbr!"); 731 const Value *Cond = PHBI->getCondition(); 732 const bool HasConditionalPreHeader = 733 !isa<ConstantInt>(Cond) || 734 PHBI->getSuccessor(cast<ConstantInt>(Cond)->isZero()) != NewHeader; 735 736 updateBranchWeights(*PHBI, *BI, HasConditionalPreHeader, BISuccsSwapped); 737 738 if (HasConditionalPreHeader) { 739 // The conditional branch can't be folded, handle the general case. 740 // Split edges as necessary to preserve LoopSimplify form. 741 742 // Right now OrigPreHeader has two successors, NewHeader and ExitBlock, and 743 // thus is not a preheader anymore. 744 // Split the edge to form a real preheader. 745 BasicBlock *NewPH = SplitCriticalEdge( 746 OrigPreheader, NewHeader, 747 CriticalEdgeSplittingOptions(DT, LI, MSSAU).setPreserveLCSSA()); 748 NewPH->setName(NewHeader->getName() + ".lr.ph"); 749 750 // Preserve canonical loop form, which means that 'Exit' should have only 751 // one predecessor. Note that Exit could be an exit block for multiple 752 // nested loops, causing both of the edges to now be critical and need to 753 // be split. 754 SmallVector<BasicBlock *, 4> ExitPreds(predecessors(Exit)); 755 bool SplitLatchEdge = false; 756 for (BasicBlock *ExitPred : ExitPreds) { 757 // We only need to split loop exit edges. 758 Loop *PredLoop = LI->getLoopFor(ExitPred); 759 if (!PredLoop || PredLoop->contains(Exit) || 760 isa<IndirectBrInst>(ExitPred->getTerminator())) 761 continue; 762 SplitLatchEdge |= L->getLoopLatch() == ExitPred; 763 BasicBlock *ExitSplit = SplitCriticalEdge( 764 ExitPred, Exit, 765 CriticalEdgeSplittingOptions(DT, LI, MSSAU).setPreserveLCSSA()); 766 ExitSplit->moveBefore(Exit); 767 } 768 assert(SplitLatchEdge && 769 "Despite splitting all preds, failed to split latch exit?"); 770 (void)SplitLatchEdge; 771 } else { 772 // We can fold the conditional branch in the preheader, this makes things 773 // simpler. The first step is to remove the extra edge to the Exit block. 774 Exit->removePredecessor(OrigPreheader, true /*preserve LCSSA*/); 775 BranchInst *NewBI = BranchInst::Create(NewHeader, PHBI); 776 NewBI->setDebugLoc(PHBI->getDebugLoc()); 777 PHBI->eraseFromParent(); 778 779 // With our CFG finalized, update DomTree if it is available. 780 if (DT) DT->deleteEdge(OrigPreheader, Exit); 781 782 // Update MSSA too, if available. 783 if (MSSAU) 784 MSSAU->removeEdge(OrigPreheader, Exit); 785 } 786 787 assert(L->getLoopPreheader() && "Invalid loop preheader after loop rotation"); 788 assert(L->getLoopLatch() && "Invalid loop latch after loop rotation"); 789 790 if (MSSAU && VerifyMemorySSA) 791 MSSAU->getMemorySSA()->verifyMemorySSA(); 792 793 // Now that the CFG and DomTree are in a consistent state again, try to merge 794 // the OrigHeader block into OrigLatch. This will succeed if they are 795 // connected by an unconditional branch. This is just a cleanup so the 796 // emitted code isn't too gross in this common case. 797 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager); 798 BasicBlock *PredBB = OrigHeader->getUniquePredecessor(); 799 bool DidMerge = MergeBlockIntoPredecessor(OrigHeader, &DTU, LI, MSSAU); 800 if (DidMerge) 801 RemoveRedundantDbgInstrs(PredBB); 802 803 if (MSSAU && VerifyMemorySSA) 804 MSSAU->getMemorySSA()->verifyMemorySSA(); 805 806 LLVM_DEBUG(dbgs() << "LoopRotation: into "; L->dump()); 807 808 ++NumRotated; 809 810 Rotated = true; 811 SimplifiedLatch = false; 812 813 // Check that new latch is a deoptimizing exit and then repeat rotation if possible. 814 // Deoptimizing latch exit is not a generally typical case, so we just loop over. 815 // TODO: if it becomes a performance bottleneck extend rotation algorithm 816 // to handle multiple rotations in one go. 817 } while (MultiRotate && canRotateDeoptimizingLatchExit(L)); 818 819 820 return true; 821 } 822 823 /// Determine whether the instructions in this range may be safely and cheaply 824 /// speculated. This is not an important enough situation to develop complex 825 /// heuristics. We handle a single arithmetic instruction along with any type 826 /// conversions. 827 static bool shouldSpeculateInstrs(BasicBlock::iterator Begin, 828 BasicBlock::iterator End, Loop *L) { 829 bool seenIncrement = false; 830 bool MultiExitLoop = false; 831 832 if (!L->getExitingBlock()) 833 MultiExitLoop = true; 834 835 for (BasicBlock::iterator I = Begin; I != End; ++I) { 836 837 if (!isSafeToSpeculativelyExecute(&*I)) 838 return false; 839 840 if (isa<DbgInfoIntrinsic>(I)) 841 continue; 842 843 switch (I->getOpcode()) { 844 default: 845 return false; 846 case Instruction::GetElementPtr: 847 // GEPs are cheap if all indices are constant. 848 if (!cast<GEPOperator>(I)->hasAllConstantIndices()) 849 return false; 850 // fall-thru to increment case 851 [[fallthrough]]; 852 case Instruction::Add: 853 case Instruction::Sub: 854 case Instruction::And: 855 case Instruction::Or: 856 case Instruction::Xor: 857 case Instruction::Shl: 858 case Instruction::LShr: 859 case Instruction::AShr: { 860 Value *IVOpnd = 861 !isa<Constant>(I->getOperand(0)) 862 ? I->getOperand(0) 863 : !isa<Constant>(I->getOperand(1)) ? I->getOperand(1) : nullptr; 864 if (!IVOpnd) 865 return false; 866 867 // If increment operand is used outside of the loop, this speculation 868 // could cause extra live range interference. 869 if (MultiExitLoop) { 870 for (User *UseI : IVOpnd->users()) { 871 auto *UserInst = cast<Instruction>(UseI); 872 if (!L->contains(UserInst)) 873 return false; 874 } 875 } 876 877 if (seenIncrement) 878 return false; 879 seenIncrement = true; 880 break; 881 } 882 case Instruction::Trunc: 883 case Instruction::ZExt: 884 case Instruction::SExt: 885 // ignore type conversions 886 break; 887 } 888 } 889 return true; 890 } 891 892 /// Fold the loop tail into the loop exit by speculating the loop tail 893 /// instructions. Typically, this is a single post-increment. In the case of a 894 /// simple 2-block loop, hoisting the increment can be much better than 895 /// duplicating the entire loop header. In the case of loops with early exits, 896 /// rotation will not work anyway, but simplifyLoopLatch will put the loop in 897 /// canonical form so downstream passes can handle it. 898 /// 899 /// I don't believe this invalidates SCEV. 900 bool LoopRotate::simplifyLoopLatch(Loop *L) { 901 BasicBlock *Latch = L->getLoopLatch(); 902 if (!Latch || Latch->hasAddressTaken()) 903 return false; 904 905 BranchInst *Jmp = dyn_cast<BranchInst>(Latch->getTerminator()); 906 if (!Jmp || !Jmp->isUnconditional()) 907 return false; 908 909 BasicBlock *LastExit = Latch->getSinglePredecessor(); 910 if (!LastExit || !L->isLoopExiting(LastExit)) 911 return false; 912 913 BranchInst *BI = dyn_cast<BranchInst>(LastExit->getTerminator()); 914 if (!BI) 915 return false; 916 917 if (!shouldSpeculateInstrs(Latch->begin(), Jmp->getIterator(), L)) 918 return false; 919 920 LLVM_DEBUG(dbgs() << "Folding loop latch " << Latch->getName() << " into " 921 << LastExit->getName() << "\n"); 922 923 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager); 924 MergeBlockIntoPredecessor(Latch, &DTU, LI, MSSAU, nullptr, 925 /*PredecessorWithTwoSuccessors=*/true); 926 927 if (SE) { 928 // Merging blocks may remove blocks reference in the block disposition cache. Clear the cache. 929 SE->forgetBlockAndLoopDispositions(); 930 } 931 932 if (MSSAU && VerifyMemorySSA) 933 MSSAU->getMemorySSA()->verifyMemorySSA(); 934 935 return true; 936 } 937 938 /// Rotate \c L, and return true if any modification was made. 939 bool LoopRotate::processLoop(Loop *L) { 940 // Save the loop metadata. 941 MDNode *LoopMD = L->getLoopID(); 942 943 bool SimplifiedLatch = false; 944 945 // Simplify the loop latch before attempting to rotate the header 946 // upward. Rotation may not be needed if the loop tail can be folded into the 947 // loop exit. 948 if (!RotationOnly) 949 SimplifiedLatch = simplifyLoopLatch(L); 950 951 bool MadeChange = rotateLoop(L, SimplifiedLatch); 952 assert((!MadeChange || L->isLoopExiting(L->getLoopLatch())) && 953 "Loop latch should be exiting after loop-rotate."); 954 955 // Restore the loop metadata. 956 // NB! We presume LoopRotation DOESN'T ADD its own metadata. 957 if ((MadeChange || SimplifiedLatch) && LoopMD) 958 L->setLoopID(LoopMD); 959 960 return MadeChange || SimplifiedLatch; 961 } 962 963 964 /// The utility to convert a loop into a loop with bottom test. 965 bool llvm::LoopRotation(Loop *L, LoopInfo *LI, const TargetTransformInfo *TTI, 966 AssumptionCache *AC, DominatorTree *DT, 967 ScalarEvolution *SE, MemorySSAUpdater *MSSAU, 968 const SimplifyQuery &SQ, bool RotationOnly = true, 969 unsigned Threshold = unsigned(-1), 970 bool IsUtilMode = true, bool PrepareForLTO) { 971 LoopRotate LR(Threshold, LI, TTI, AC, DT, SE, MSSAU, SQ, RotationOnly, 972 IsUtilMode, PrepareForLTO); 973 return LR.processLoop(L); 974 } 975