976 lines · cpp
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-exception6//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"38using namespace llvm;39 40#define DEBUG_TYPE "loop-rotate"41 42STATISTIC(NumNotRotatedDueToHeaderSize,43 "Number of loops not rotated due to the header size");44STATISTIC(NumInstrsHoisted,45 "Number of instructions hoisted into loop preheader");46STATISTIC(NumInstrsDuplicated,47 "Number of instructions cloned into loop preheader");48 49// Probability that a rotated loop has zero trip count / is never entered.50static constexpr uint32_t ZeroTripCountWeights[] = {1, 127};51 52namespace {53/// A simple loop rotation transformation.54class LoopRotate {55 const unsigned MaxHeaderSize;56 LoopInfo *LI;57 const TargetTransformInfo *TTI;58 AssumptionCache *AC;59 DominatorTree *DT;60 ScalarEvolution *SE;61 MemorySSAUpdater *MSSAU;62 const SimplifyQuery &SQ;63 bool RotationOnly;64 bool IsUtilMode;65 bool PrepareForLTO;66 67public:68 LoopRotate(unsigned MaxHeaderSize, LoopInfo *LI,69 const TargetTransformInfo *TTI, AssumptionCache *AC,70 DominatorTree *DT, ScalarEvolution *SE, MemorySSAUpdater *MSSAU,71 const SimplifyQuery &SQ, bool RotationOnly, bool IsUtilMode,72 bool PrepareForLTO)73 : MaxHeaderSize(MaxHeaderSize), LI(LI), TTI(TTI), AC(AC), DT(DT), SE(SE),74 MSSAU(MSSAU), SQ(SQ), RotationOnly(RotationOnly),75 IsUtilMode(IsUtilMode), PrepareForLTO(PrepareForLTO) {}76 bool processLoop(Loop *L);77 78private:79 bool rotateLoop(Loop *L, bool SimplifiedLatch);80 bool simplifyLoopLatch(Loop *L);81};82} // end anonymous namespace83 84/// Insert (K, V) pair into the ValueToValueMap, and verify the key did not85/// previously exist in the map, and the value was inserted.86static void InsertNewValueIntoMap(ValueToValueMapTy &VM, Value *K, Value *V) {87 bool Inserted = VM.insert({K, V}).second;88 assert(Inserted);89 (void)Inserted;90}91/// RewriteUsesOfClonedInstructions - We just cloned the instructions from the92/// old header into the preheader. If there were uses of the values produced by93/// these instruction that were outside of the loop, we have to insert PHI nodes94/// to merge the two values. Do this now.95static void RewriteUsesOfClonedInstructions(BasicBlock *OrigHeader,96 BasicBlock *OrigPreheader,97 ValueToValueMapTy &ValueMap,98 ScalarEvolution *SE,99 SmallVectorImpl<PHINode*> *InsertedPHIs) {100 // Remove PHI node entries that are no longer live.101 BasicBlock::iterator I, E = OrigHeader->end();102 for (I = OrigHeader->begin(); PHINode *PN = dyn_cast<PHINode>(I); ++I)103 PN->removeIncomingValue(PN->getBasicBlockIndex(OrigPreheader));104 105 // Now fix up users of the instructions in OrigHeader, inserting PHI nodes106 // as necessary.107 SSAUpdater SSA(InsertedPHIs);108 for (I = OrigHeader->begin(); I != E; ++I) {109 Value *OrigHeaderVal = &*I;110 111 // If there are no uses of the value (e.g. because it returns void), there112 // is nothing to rewrite.113 if (OrigHeaderVal->use_empty())114 continue;115 116 Value *OrigPreHeaderVal = ValueMap.lookup(OrigHeaderVal);117 118 // The value now exits in two versions: the initial value in the preheader119 // and the loop "next" value in the original header.120 SSA.Initialize(OrigHeaderVal->getType(), OrigHeaderVal->getName());121 // Force re-computation of OrigHeaderVal, as some users now need to use the122 // new PHI node.123 if (SE)124 SE->forgetValue(OrigHeaderVal);125 SSA.AddAvailableValue(OrigHeader, OrigHeaderVal);126 SSA.AddAvailableValue(OrigPreheader, OrigPreHeaderVal);127 128 // Visit each use of the OrigHeader instruction.129 for (Use &U : llvm::make_early_inc_range(OrigHeaderVal->uses())) {130 // SSAUpdater can't handle a non-PHI use in the same block as an131 // earlier def. We can easily handle those cases manually.132 Instruction *UserInst = cast<Instruction>(U.getUser());133 if (!isa<PHINode>(UserInst)) {134 BasicBlock *UserBB = UserInst->getParent();135 136 // The original users in the OrigHeader are already using the137 // original definitions.138 if (UserBB == OrigHeader)139 continue;140 141 // Users in the OrigPreHeader need to use the value to which the142 // original definitions are mapped.143 if (UserBB == OrigPreheader) {144 U = OrigPreHeaderVal;145 continue;146 }147 }148 149 // Anything else can be handled by SSAUpdater.150 SSA.RewriteUse(U);151 }152 153 // Replace MetadataAsValue(ValueAsMetadata(OrigHeaderVal)) uses in debug154 // intrinsics.155 SmallVector<DbgVariableRecord *, 1> DbgVariableRecords;156 llvm::findDbgValues(OrigHeaderVal, DbgVariableRecords);157 158 for (DbgVariableRecord *DVR : DbgVariableRecords) {159 // The original users in the OrigHeader are already using the original160 // definitions.161 BasicBlock *UserBB = DVR->getMarker()->getParent();162 if (UserBB == OrigHeader)163 continue;164 165 // Users in the OrigPreHeader need to use the value to which the166 // original definitions are mapped and anything else can be handled by167 // the SSAUpdater. To avoid adding PHINodes, check if the value is168 // available in UserBB, if not substitute poison.169 Value *NewVal;170 if (UserBB == OrigPreheader)171 NewVal = OrigPreHeaderVal;172 else if (SSA.HasValueForBlock(UserBB))173 NewVal = SSA.GetValueInMiddleOfBlock(UserBB);174 else175 NewVal = PoisonValue::get(OrigHeaderVal->getType());176 DVR->replaceVariableLocationOp(OrigHeaderVal, NewVal);177 }178 }179}180 181// Assuming both header and latch are exiting, look for a phi which is only182// used outside the loop (via a LCSSA phi) in the exit from the header.183// This means that rotating the loop can remove the phi.184static bool profitableToRotateLoopExitingLatch(Loop *L) {185 BasicBlock *Header = L->getHeader();186 BranchInst *BI = dyn_cast<BranchInst>(Header->getTerminator());187 assert(BI && BI->isConditional() && "need header with conditional exit");188 BasicBlock *HeaderExit = BI->getSuccessor(0);189 if (L->contains(HeaderExit))190 HeaderExit = BI->getSuccessor(1);191 192 for (auto &Phi : Header->phis()) {193 // Look for uses of this phi in the loop/via exits other than the header.194 if (llvm::any_of(Phi.users(), [HeaderExit](const User *U) {195 return cast<Instruction>(U)->getParent() != HeaderExit;196 }))197 continue;198 return true;199 }200 return false;201}202 203static void updateBranchWeights(BranchInst &PreHeaderBI, BranchInst &LoopBI,204 bool HasConditionalPreHeader,205 bool SuccsSwapped) {206 MDNode *WeightMD = getBranchWeightMDNode(PreHeaderBI);207 if (WeightMD == nullptr)208 return;209 210 // LoopBI should currently be a clone of PreHeaderBI with the same211 // metadata. But we double check to make sure we don't have a degenerate case212 // where instsimplify changed the instructions.213 if (WeightMD != getBranchWeightMDNode(LoopBI))214 return;215 216 SmallVector<uint32_t, 2> Weights;217 extractFromBranchWeightMD32(WeightMD, Weights);218 if (Weights.size() != 2)219 return;220 uint32_t OrigLoopExitWeight = Weights[0];221 uint32_t OrigLoopBackedgeWeight = Weights[1];222 223 if (SuccsSwapped)224 std::swap(OrigLoopExitWeight, OrigLoopBackedgeWeight);225 226 // Update branch weights. Consider the following edge-counts:227 //228 // | |-------- |229 // V V | V230 // Br i1 ... | Br i1 ...231 // | | | | |232 // x| y| | becomes: | y0| |-----233 // V V | | V V |234 // Exit Loop | | Loop |235 // | | | Br i1 ... |236 // ----- | | | |237 // x0| x1| y1 | |238 // V V ----239 // Exit240 //241 // The following must hold:242 // - x == x0 + x1 # counts to "exit" must stay the same.243 // - y0 == x - x0 == x1 # how often loop was entered at all.244 // - y1 == y - y0 # How often loop was repeated (after first iter.).245 //246 // We cannot generally deduce how often we had a zero-trip count loop so we247 // have to make a guess for how to distribute x among the new x0 and x1.248 249 uint32_t ExitWeight0; // aka x0250 uint32_t ExitWeight1; // aka x1251 uint32_t EnterWeight; // aka y0252 uint32_t LoopBackWeight; // aka y1253 if (OrigLoopExitWeight > 0 && OrigLoopBackedgeWeight > 0) {254 ExitWeight0 = 0;255 if (HasConditionalPreHeader) {256 // Here we cannot know how many 0-trip count loops we have, so we guess:257 if (OrigLoopBackedgeWeight >= OrigLoopExitWeight) {258 // If the loop count is bigger than the exit count then we set259 // probabilities as if 0-trip count nearly never happens.260 ExitWeight0 = ZeroTripCountWeights[0];261 // Scale up counts if necessary so we can match `ZeroTripCountWeights`262 // for the `ExitWeight0`:`ExitWeight1` (aka `x0`:`x1` ratio`) ratio.263 while (OrigLoopExitWeight < ZeroTripCountWeights[1] + ExitWeight0) {264 // ... but don't overflow.265 uint32_t const HighBit = uint32_t{1} << (sizeof(uint32_t) * 8 - 1);266 if ((OrigLoopBackedgeWeight & HighBit) != 0 ||267 (OrigLoopExitWeight & HighBit) != 0)268 break;269 OrigLoopBackedgeWeight <<= 1;270 OrigLoopExitWeight <<= 1;271 }272 } else {273 // If there's a higher exit-count than backedge-count then we set274 // probabilities as if there are only 0-trip and 1-trip cases.275 ExitWeight0 = OrigLoopExitWeight - OrigLoopBackedgeWeight;276 }277 } else {278 // Theoretically, if the loop body must be executed at least once, the279 // backedge count must be not less than exit count. However the branch280 // weight collected by sampling-based PGO may be not very accurate due to281 // sampling. Therefore this workaround is required here to avoid underflow282 // of unsigned in following update of branch weight.283 if (OrigLoopExitWeight > OrigLoopBackedgeWeight)284 OrigLoopBackedgeWeight = OrigLoopExitWeight;285 }286 assert(OrigLoopExitWeight >= ExitWeight0 && "Bad branch weight");287 ExitWeight1 = OrigLoopExitWeight - ExitWeight0;288 EnterWeight = ExitWeight1;289 assert(OrigLoopBackedgeWeight >= EnterWeight && "Bad branch weight");290 LoopBackWeight = OrigLoopBackedgeWeight - EnterWeight;291 } else if (OrigLoopExitWeight == 0) {292 if (OrigLoopBackedgeWeight == 0) {293 // degenerate case... keep everything zero...294 ExitWeight0 = 0;295 ExitWeight1 = 0;296 EnterWeight = 0;297 LoopBackWeight = 0;298 } else {299 // Special case "LoopExitWeight == 0" weights which behaves like an300 // endless where we don't want loop-enttry (y0) to be the same as301 // loop-exit (x1).302 ExitWeight0 = 0;303 ExitWeight1 = 0;304 EnterWeight = 1;305 LoopBackWeight = OrigLoopBackedgeWeight;306 }307 } else {308 // loop is never entered.309 assert(OrigLoopBackedgeWeight == 0 && "remaining case is backedge zero");310 ExitWeight0 = 1;311 ExitWeight1 = 1;312 EnterWeight = 0;313 LoopBackWeight = 0;314 }315 316 const uint32_t LoopBIWeights[] = {317 SuccsSwapped ? LoopBackWeight : ExitWeight1,318 SuccsSwapped ? ExitWeight1 : LoopBackWeight,319 };320 setBranchWeights(LoopBI, LoopBIWeights, /*IsExpected=*/false);321 if (HasConditionalPreHeader) {322 const uint32_t PreHeaderBIWeights[] = {323 SuccsSwapped ? EnterWeight : ExitWeight0,324 SuccsSwapped ? ExitWeight0 : EnterWeight,325 };326 setBranchWeights(PreHeaderBI, PreHeaderBIWeights, /*IsExpected=*/false);327 }328}329 330/// Rotate loop LP. Return true if the loop is rotated.331///332/// \param SimplifiedLatch is true if the latch was just folded into the final333/// loop exit. In this case we may want to rotate even though the new latch is334/// now an exiting branch. This rotation would have happened had the latch not335/// been simplified. However, if SimplifiedLatch is false, then we avoid336/// rotating loops in which the latch exits to avoid excessive or endless337/// rotation. LoopRotate should be repeatable and converge to a canonical338/// form. This property is satisfied because simplifying the loop latch can only339/// happen once across multiple invocations of the LoopRotate pass.340bool LoopRotate::rotateLoop(Loop *L, bool SimplifiedLatch) {341 // If the loop has only one block then there is not much to rotate.342 if (L->getBlocks().size() == 1)343 return false;344 345 bool Rotated = false;346 BasicBlock *OrigHeader = L->getHeader();347 BasicBlock *OrigLatch = L->getLoopLatch();348 349 BranchInst *BI = dyn_cast<BranchInst>(OrigHeader->getTerminator());350 if (!BI || BI->isUnconditional())351 return Rotated;352 353 // If the loop header is not one of the loop exiting blocks then354 // either this loop is already rotated or it is not355 // suitable for loop rotation transformations.356 if (!L->isLoopExiting(OrigHeader))357 return Rotated;358 359 // If the loop latch already contains a branch that leaves the loop then the360 // loop is already rotated.361 if (!OrigLatch)362 return Rotated;363 364 // Rotate if the loop latch was just simplified. Or if it makes the loop exit365 // count computable. Or if we think it will be profitable.366 if (L->isLoopExiting(OrigLatch) && !SimplifiedLatch && IsUtilMode == false &&367 !profitableToRotateLoopExitingLatch(L))368 return Rotated;369 370 // Check size of original header and reject loop if it is very big or we can't371 // duplicate blocks inside it.372 {373 SmallPtrSet<const Value *, 32> EphValues;374 CodeMetrics::collectEphemeralValues(L, AC, EphValues);375 376 CodeMetrics Metrics;377 Metrics.analyzeBasicBlock(OrigHeader, *TTI, EphValues, PrepareForLTO);378 if (Metrics.notDuplicatable) {379 LLVM_DEBUG(380 dbgs() << "LoopRotation: NOT rotating - contains non-duplicatable"381 << " instructions: ";382 L->dump());383 return Rotated;384 }385 if (Metrics.Convergence != ConvergenceKind::None) {386 LLVM_DEBUG(dbgs() << "LoopRotation: NOT rotating - contains convergent "387 "instructions: ";388 L->dump());389 return Rotated;390 }391 if (!Metrics.NumInsts.isValid()) {392 LLVM_DEBUG(dbgs() << "LoopRotation: NOT rotating - contains instructions"393 " with invalid cost: ";394 L->dump());395 return Rotated;396 }397 if (Metrics.NumInsts > MaxHeaderSize) {398 LLVM_DEBUG(dbgs() << "LoopRotation: NOT rotating - contains "399 << Metrics.NumInsts400 << " instructions, which is more than the threshold ("401 << MaxHeaderSize << " instructions): ";402 L->dump());403 ++NumNotRotatedDueToHeaderSize;404 return Rotated;405 }406 407 // When preparing for LTO, avoid rotating loops with calls that could be408 // inlined during the LTO stage.409 if (PrepareForLTO && Metrics.NumInlineCandidates > 0)410 return Rotated;411 }412 413 // Now, this loop is suitable for rotation.414 BasicBlock *OrigPreheader = L->getLoopPreheader();415 416 // If the loop could not be converted to canonical form, it must have an417 // indirectbr in it, just give up.418 if (!OrigPreheader || !L->hasDedicatedExits())419 return Rotated;420 421 // Anything ScalarEvolution may know about this loop or the PHI nodes422 // in its header will soon be invalidated. We should also invalidate423 // all outer loops because insertion and deletion of blocks that happens424 // during the rotation may violate invariants related to backedge taken425 // infos in them.426 if (SE) {427 SE->forgetTopmostLoop(L);428 // We may hoist some instructions out of loop. In case if they were cached429 // as "loop variant" or "loop computable", these caches must be dropped.430 // We also may fold basic blocks, so cached block dispositions also need431 // to be dropped.432 SE->forgetBlockAndLoopDispositions();433 }434 435 LLVM_DEBUG(dbgs() << "LoopRotation: rotating "; L->dump());436 if (MSSAU && VerifyMemorySSA)437 MSSAU->getMemorySSA()->verifyMemorySSA();438 439 // Find new Loop header. NewHeader is a Header's one and only successor440 // that is inside loop. Header's other successor is outside the441 // loop. Otherwise loop is not suitable for rotation.442 BasicBlock *Exit = BI->getSuccessor(0);443 BasicBlock *NewHeader = BI->getSuccessor(1);444 bool BISuccsSwapped = L->contains(Exit);445 if (BISuccsSwapped)446 std::swap(Exit, NewHeader);447 assert(NewHeader && "Unable to determine new loop header");448 assert(L->contains(NewHeader) && !L->contains(Exit) &&449 "Unable to determine loop header and exit blocks");450 451 // This code assumes that the new header has exactly one predecessor.452 // Remove any single-entry PHI nodes in it.453 assert(NewHeader->getSinglePredecessor() &&454 "New header doesn't have one pred!");455 FoldSingleEntryPHINodes(NewHeader);456 457 // Begin by walking OrigHeader and populating ValueMap with an entry for458 // each Instruction.459 BasicBlock::iterator I = OrigHeader->begin(), E = OrigHeader->end();460 ValueToValueMapTy ValueMap, ValueMapMSSA;461 462 // For PHI nodes, the value available in OldPreHeader is just the463 // incoming value from OldPreHeader.464 for (; PHINode *PN = dyn_cast<PHINode>(I); ++I)465 InsertNewValueIntoMap(ValueMap, PN,466 PN->getIncomingValueForBlock(OrigPreheader));467 468 // For the rest of the instructions, either hoist to the OrigPreheader if469 // possible or create a clone in the OldPreHeader if not.470 Instruction *LoopEntryBranch = OrigPreheader->getTerminator();471 472 // Record all debug records preceding LoopEntryBranch to avoid473 // duplication.474 using DbgHash =475 std::pair<std::pair<hash_code, DILocalVariable *>, DIExpression *>;476 auto makeHash = [](const DbgVariableRecord *D) -> DbgHash {477 auto VarLocOps = D->location_ops();478 return {{hash_combine_range(VarLocOps), D->getVariable()},479 D->getExpression()};480 };481 482 SmallDenseSet<DbgHash, 8> DbgRecords;483 // Build DbgVariableRecord hashes for DbgVariableRecords attached to the484 // terminator.485 for (const DbgVariableRecord &DVR :486 filterDbgVars(OrigPreheader->getTerminator()->getDbgRecordRange()))487 DbgRecords.insert(makeHash(&DVR));488 489 // Remember the local noalias scope declarations in the header. After the490 // rotation, they must be duplicated and the scope must be cloned. This491 // avoids unwanted interaction across iterations.492 SmallVector<NoAliasScopeDeclInst *, 6> NoAliasDeclInstructions;493 for (Instruction &I : *OrigHeader)494 if (auto *Decl = dyn_cast<NoAliasScopeDeclInst>(&I))495 NoAliasDeclInstructions.push_back(Decl);496 497 Module *M = OrigHeader->getModule();498 499 // Track the next DbgRecord to clone. If we have a sequence where an500 // instruction is hoisted instead of being cloned:501 // DbgRecord blah502 // %foo = add i32 0, 0503 // DbgRecord xyzzy504 // %bar = call i32 @foobar()505 // where %foo is hoisted, then the DbgRecord "blah" will be seen twice, once506 // attached to %foo, then when %foo his hoisted it will "fall down" onto the507 // function call:508 // DbgRecord blah509 // DbgRecord xyzzy510 // %bar = call i32 @foobar()511 // causing it to appear attached to the call too.512 //513 // To avoid this, cloneDebugInfoFrom takes an optional "start cloning from514 // here" position to account for this behaviour. We point it at any515 // DbgRecords on the next instruction, here labelled xyzzy, before we hoist516 // %foo. Later, we only only clone DbgRecords from that position (xyzzy)517 // onwards, which avoids cloning DbgRecord "blah" multiple times. (Stored as518 // a range because it gives us a natural way of testing whether519 // there were DbgRecords on the next instruction before we hoisted things).520 iterator_range<DbgRecord::self_iterator> NextDbgInsts =521 (I != E) ? I->getDbgRecordRange() : DbgMarker::getEmptyDbgRecordRange();522 523 while (I != E) {524 Instruction *Inst = &*I++;525 526 // If the instruction's operands are invariant and it doesn't read or write527 // memory, then it is safe to hoist. Doing this doesn't change the order of528 // execution in the preheader, but does prevent the instruction from529 // executing in each iteration of the loop. This means it is safe to hoist530 // something that might trap, but isn't safe to hoist something that reads531 // memory (without proving that the loop doesn't write).532 if (L->hasLoopInvariantOperands(Inst) && !Inst->mayReadFromMemory() &&533 !Inst->mayWriteToMemory() && !Inst->isTerminator() &&534 !isa<AllocaInst>(Inst) &&535 // It is not safe to hoist the value of these instructions in536 // coroutines, as the addresses of otherwise eligible variables (e.g.537 // thread-local variables and errno) may change if the coroutine is538 // resumed in a different thread.Therefore, we disable this539 // optimization for correctness. However, this may block other correct540 // optimizations.541 // FIXME: This should be reverted once we have a better model for542 // memory access in coroutines.543 !Inst->getFunction()->isPresplitCoroutine()) {544 545 if (!NextDbgInsts.empty()) {546 auto DbgValueRange =547 LoopEntryBranch->cloneDebugInfoFrom(Inst, NextDbgInsts.begin());548 RemapDbgRecordRange(M, DbgValueRange, ValueMap,549 RF_NoModuleLevelChanges | RF_IgnoreMissingLocals);550 // Erase anything we've seen before.551 for (DbgVariableRecord &DVR :552 make_early_inc_range(filterDbgVars(DbgValueRange)))553 if (DbgRecords.count(makeHash(&DVR)))554 DVR.eraseFromParent();555 }556 557 NextDbgInsts = I->getDbgRecordRange();558 559 Inst->moveBefore(LoopEntryBranch->getIterator());560 561 ++NumInstrsHoisted;562 continue;563 }564 565 // Otherwise, create a duplicate of the instruction.566 Instruction *C = Inst->clone();567 if (const DebugLoc &DL = C->getDebugLoc())568 mapAtomInstance(DL, ValueMap);569 570 C->insertBefore(LoopEntryBranch->getIterator());571 572 ++NumInstrsDuplicated;573 574 if (!NextDbgInsts.empty()) {575 auto Range = C->cloneDebugInfoFrom(Inst, NextDbgInsts.begin());576 RemapDbgRecordRange(M, Range, ValueMap,577 RF_NoModuleLevelChanges | RF_IgnoreMissingLocals);578 NextDbgInsts = DbgMarker::getEmptyDbgRecordRange();579 // Erase anything we've seen before.580 for (DbgVariableRecord &DVR : make_early_inc_range(filterDbgVars(Range)))581 if (DbgRecords.count(makeHash(&DVR)))582 DVR.eraseFromParent();583 }584 585 // Eagerly remap the operands of the instruction.586 RemapInstruction(C, ValueMap,587 RF_NoModuleLevelChanges | RF_IgnoreMissingLocals);588 589 // With the operands remapped, see if the instruction constant folds or is590 // otherwise simplifyable. This commonly occurs because the entry from PHI591 // nodes allows icmps and other instructions to fold.592 Value *V = simplifyInstruction(C, SQ);593 if (V && LI->replacementPreservesLCSSAForm(C, V)) {594 // If so, then delete the temporary instruction and stick the folded value595 // in the map.596 InsertNewValueIntoMap(ValueMap, Inst, V);597 if (!C->mayHaveSideEffects()) {598 C->eraseFromParent();599 C = nullptr;600 }601 } else {602 InsertNewValueIntoMap(ValueMap, Inst, C);603 }604 if (C) {605 // Otherwise, stick the new instruction into the new block!606 C->setName(Inst->getName());607 608 if (auto *II = dyn_cast<AssumeInst>(C))609 AC->registerAssumption(II);610 // MemorySSA cares whether the cloned instruction was inserted or not, and611 // not whether it can be remapped to a simplified value.612 if (MSSAU)613 InsertNewValueIntoMap(ValueMapMSSA, Inst, C);614 }615 }616 617 if (!NoAliasDeclInstructions.empty()) {618 // There are noalias scope declarations:619 // (general):620 // Original: OrigPre { OrigHeader NewHeader ... Latch }621 // after: (OrigPre+OrigHeader') { NewHeader ... Latch OrigHeader }622 //623 // with D: llvm.experimental.noalias.scope.decl,624 // U: !noalias or !alias.scope depending on D625 // ... { D U1 U2 } can transform into:626 // (0) : ... { D U1 U2 } // no relevant rotation for this part627 // (1) : ... D' { U1 U2 D } // D is part of OrigHeader628 // (2) : ... D' U1' { U2 D U1 } // D, U1 are part of OrigHeader629 //630 // We now want to transform:631 // (1) -> : ... D' { D U1 U2 D'' }632 // (2) -> : ... D' U1' { D U2 D'' U1'' }633 // D: original llvm.experimental.noalias.scope.decl634 // D', U1': duplicate with replaced scopes635 // D'', U1'': different duplicate with replaced scopes636 // This ensures a safe fallback to 'may_alias' introduced by the rotate,637 // as U1'' and U1' scopes will not be compatible wrt to the local restrict638 639 // Clone the llvm.experimental.noalias.decl again for the NewHeader.640 BasicBlock::iterator NewHeaderInsertionPoint =641 NewHeader->getFirstNonPHIIt();642 for (NoAliasScopeDeclInst *NAD : NoAliasDeclInstructions) {643 LLVM_DEBUG(dbgs() << " Cloning llvm.experimental.noalias.scope.decl:"644 << *NAD << "\n");645 Instruction *NewNAD = NAD->clone();646 NewNAD->insertBefore(*NewHeader, NewHeaderInsertionPoint);647 }648 649 // Scopes must now be duplicated, once for OrigHeader and once for650 // OrigPreHeader'.651 {652 auto &Context = NewHeader->getContext();653 654 SmallVector<MDNode *, 8> NoAliasDeclScopes;655 for (NoAliasScopeDeclInst *NAD : NoAliasDeclInstructions)656 NoAliasDeclScopes.push_back(NAD->getScopeList());657 658 LLVM_DEBUG(dbgs() << " Updating OrigHeader scopes\n");659 cloneAndAdaptNoAliasScopes(NoAliasDeclScopes, {OrigHeader}, Context,660 "h.rot");661 LLVM_DEBUG(OrigHeader->dump());662 663 // Keep the compile time impact low by only adapting the inserted block664 // of instructions in the OrigPreHeader. This might result in slightly665 // more aliasing between these instructions and those that were already666 // present, but it will be much faster when the original PreHeader is667 // large.668 LLVM_DEBUG(dbgs() << " Updating part of OrigPreheader scopes\n");669 auto *FirstDecl =670 cast<Instruction>(ValueMap[*NoAliasDeclInstructions.begin()]);671 auto *LastInst = &OrigPreheader->back();672 cloneAndAdaptNoAliasScopes(NoAliasDeclScopes, FirstDecl, LastInst,673 Context, "pre.rot");674 LLVM_DEBUG(OrigPreheader->dump());675 676 LLVM_DEBUG(dbgs() << " Updated NewHeader:\n");677 LLVM_DEBUG(NewHeader->dump());678 }679 }680 681 // Along with all the other instructions, we just cloned OrigHeader's682 // terminator into OrigPreHeader. Fix up the PHI nodes in each of OrigHeader's683 // successors by duplicating their incoming values for OrigHeader.684 for (BasicBlock *SuccBB : successors(OrigHeader))685 for (BasicBlock::iterator BI = SuccBB->begin();686 PHINode *PN = dyn_cast<PHINode>(BI); ++BI)687 PN->addIncoming(PN->getIncomingValueForBlock(OrigHeader), OrigPreheader);688 689 // Now that OrigPreHeader has a clone of OrigHeader's terminator, remove690 // OrigPreHeader's old terminator (the original branch into the loop), and691 // remove the corresponding incoming values from the PHI nodes in OrigHeader.692 LoopEntryBranch->eraseFromParent();693 OrigPreheader->flushTerminatorDbgRecords();694 695 // Update MemorySSA before the rewrite call below changes the 1:1696 // instruction:cloned_instruction_or_value mapping.697 if (MSSAU) {698 InsertNewValueIntoMap(ValueMapMSSA, OrigHeader, OrigPreheader);699 MSSAU->updateForClonedBlockIntoPred(OrigHeader, OrigPreheader,700 ValueMapMSSA);701 }702 703 SmallVector<PHINode *, 2> InsertedPHIs;704 // If there were any uses of instructions in the duplicated block outside the705 // loop, update them, inserting PHI nodes as required706 RewriteUsesOfClonedInstructions(OrigHeader, OrigPreheader, ValueMap, SE,707 &InsertedPHIs);708 709 // Attach debug records to the new phis if that phi uses a value that710 // previously had debug metadata attached. This keeps the debug info711 // up-to-date in the loop body.712 if (!InsertedPHIs.empty())713 insertDebugValuesForPHIs(OrigHeader, InsertedPHIs);714 715 // NewHeader is now the header of the loop.716 L->moveToHeader(NewHeader);717 assert(L->getHeader() == NewHeader && "Latch block is our new header");718 719 // Inform DT about changes to the CFG.720 if (DT) {721 // The OrigPreheader branches to the NewHeader and Exit now. Then, inform722 // the DT about the removed edge to the OrigHeader (that got removed).723 SmallVector<DominatorTree::UpdateType, 3> Updates = {724 {DominatorTree::Insert, OrigPreheader, Exit},725 {DominatorTree::Insert, OrigPreheader, NewHeader},726 {DominatorTree::Delete, OrigPreheader, OrigHeader}};727 728 if (MSSAU) {729 MSSAU->applyUpdates(Updates, *DT, /*UpdateDT=*/true);730 if (VerifyMemorySSA)731 MSSAU->getMemorySSA()->verifyMemorySSA();732 } else {733 DT->applyUpdates(Updates);734 }735 }736 737 // At this point, we've finished our major CFG changes. As part of cloning738 // the loop into the preheader we've simplified instructions and the739 // duplicated conditional branch may now be branching on a constant. If it is740 // branching on a constant and if that constant means that we enter the loop,741 // then we fold away the cond branch to an uncond branch. This simplifies the742 // loop in cases important for nested loops, and it also means we don't have743 // to split as many edges.744 BranchInst *PHBI = cast<BranchInst>(OrigPreheader->getTerminator());745 assert(PHBI->isConditional() && "Should be clone of BI condbr!");746 const Value *Cond = PHBI->getCondition();747 const bool HasConditionalPreHeader =748 !isa<ConstantInt>(Cond) ||749 PHBI->getSuccessor(cast<ConstantInt>(Cond)->isZero()) != NewHeader;750 751 updateBranchWeights(*PHBI, *BI, HasConditionalPreHeader, BISuccsSwapped);752 753 if (HasConditionalPreHeader) {754 // The conditional branch can't be folded, handle the general case.755 // Split edges as necessary to preserve LoopSimplify form.756 757 // Right now OrigPreHeader has two successors, NewHeader and ExitBlock, and758 // thus is not a preheader anymore.759 // Split the edge to form a real preheader.760 BasicBlock *NewPH = SplitCriticalEdge(761 OrigPreheader, NewHeader,762 CriticalEdgeSplittingOptions(DT, LI, MSSAU).setPreserveLCSSA());763 NewPH->setName(NewHeader->getName() + ".lr.ph");764 765 // Preserve canonical loop form, which means that 'Exit' should have only766 // one predecessor. Note that Exit could be an exit block for multiple767 // nested loops, causing both of the edges to now be critical and need to768 // be split.769 SmallVector<BasicBlock *, 4> ExitPreds(predecessors(Exit));770 bool SplitLatchEdge = false;771 for (BasicBlock *ExitPred : ExitPreds) {772 // We only need to split loop exit edges.773 Loop *PredLoop = LI->getLoopFor(ExitPred);774 if (!PredLoop || PredLoop->contains(Exit) ||775 isa<IndirectBrInst>(ExitPred->getTerminator()))776 continue;777 SplitLatchEdge |= L->getLoopLatch() == ExitPred;778 BasicBlock *ExitSplit = SplitCriticalEdge(779 ExitPred, Exit,780 CriticalEdgeSplittingOptions(DT, LI, MSSAU).setPreserveLCSSA());781 ExitSplit->moveBefore(Exit);782 }783 assert(SplitLatchEdge &&784 "Despite splitting all preds, failed to split latch exit?");785 (void)SplitLatchEdge;786 } else {787 // We can fold the conditional branch in the preheader, this makes things788 // simpler. The first step is to remove the extra edge to the Exit block.789 Exit->removePredecessor(OrigPreheader, true /*preserve LCSSA*/);790 BranchInst *NewBI = BranchInst::Create(NewHeader, PHBI->getIterator());791 NewBI->setDebugLoc(PHBI->getDebugLoc());792 PHBI->eraseFromParent();793 794 // With our CFG finalized, update DomTree if it is available.795 if (DT)796 DT->deleteEdge(OrigPreheader, Exit);797 798 // Update MSSA too, if available.799 if (MSSAU)800 MSSAU->removeEdge(OrigPreheader, Exit);801 }802 803 assert(L->getLoopPreheader() && "Invalid loop preheader after loop rotation");804 assert(L->getLoopLatch() && "Invalid loop latch after loop rotation");805 806 if (MSSAU && VerifyMemorySSA)807 MSSAU->getMemorySSA()->verifyMemorySSA();808 809 // Now that the CFG and DomTree are in a consistent state again, try to merge810 // the OrigHeader block into OrigLatch. This will succeed if they are811 // connected by an unconditional branch. This is just a cleanup so the812 // emitted code isn't too gross in this common case.813 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);814 BasicBlock *PredBB = OrigHeader->getUniquePredecessor();815 bool DidMerge = MergeBlockIntoPredecessor(OrigHeader, &DTU, LI, MSSAU);816 if (DidMerge)817 RemoveRedundantDbgInstrs(PredBB);818 819 if (MSSAU && VerifyMemorySSA)820 MSSAU->getMemorySSA()->verifyMemorySSA();821 822 LLVM_DEBUG(dbgs() << "LoopRotation: into "; L->dump());823 824 return true;825}826 827/// Determine whether the instructions in this range may be safely and cheaply828/// speculated. This is not an important enough situation to develop complex829/// heuristics. We handle a single arithmetic instruction along with any type830/// conversions.831static bool shouldSpeculateInstrs(BasicBlock::iterator Begin,832 BasicBlock::iterator End, Loop *L) {833 bool seenIncrement = false;834 bool MultiExitLoop = false;835 836 if (!L->getExitingBlock())837 MultiExitLoop = true;838 839 for (BasicBlock::iterator I = Begin; I != End; ++I) {840 841 if (!isSafeToSpeculativelyExecute(&*I))842 return false;843 844 switch (I->getOpcode()) {845 default:846 return false;847 case Instruction::GetElementPtr:848 // GEPs are cheap if all indices are constant.849 if (!cast<GEPOperator>(I)->hasAllConstantIndices())850 return false;851 // fall-thru to increment case852 [[fallthrough]];853 case Instruction::Add:854 case Instruction::Sub:855 case Instruction::And:856 case Instruction::Or:857 case Instruction::Xor:858 case Instruction::Shl:859 case Instruction::LShr:860 case Instruction::AShr: {861 Value *IVOpnd =862 !isa<Constant>(I->getOperand(0))863 ? I->getOperand(0)864 : !isa<Constant>(I->getOperand(1)) ? I->getOperand(1) : nullptr;865 if (!IVOpnd)866 return false;867 868 // If increment operand is used outside of the loop, this speculation869 // could cause extra live range interference.870 if (MultiExitLoop) {871 for (User *UseI : IVOpnd->users()) {872 auto *UserInst = cast<Instruction>(UseI);873 if (!L->contains(UserInst))874 return false;875 }876 }877 878 if (seenIncrement)879 return false;880 seenIncrement = true;881 break;882 }883 case Instruction::Trunc:884 case Instruction::ZExt:885 case Instruction::SExt:886 // ignore type conversions887 break;888 }889 }890 return true;891}892 893/// Fold the loop tail into the loop exit by speculating the loop tail894/// instructions. Typically, this is a single post-increment. In the case of a895/// simple 2-block loop, hoisting the increment can be much better than896/// duplicating the entire loop header. In the case of loops with early exits,897/// rotation will not work anyway, but simplifyLoopLatch will put the loop in898/// canonical form so downstream passes can handle it.899///900/// I don't believe this invalidates SCEV.901bool LoopRotate::simplifyLoopLatch(Loop *L) {902 BasicBlock *Latch = L->getLoopLatch();903 if (!Latch || Latch->hasAddressTaken())904 return false;905 906 BranchInst *Jmp = dyn_cast<BranchInst>(Latch->getTerminator());907 if (!Jmp || !Jmp->isUnconditional())908 return false;909 910 BasicBlock *LastExit = Latch->getSinglePredecessor();911 if (!LastExit || !L->isLoopExiting(LastExit))912 return false;913 914 BranchInst *BI = dyn_cast<BranchInst>(LastExit->getTerminator());915 if (!BI)916 return false;917 918 if (!shouldSpeculateInstrs(Latch->begin(), Jmp->getIterator(), L))919 return false;920 921 LLVM_DEBUG(dbgs() << "Folding loop latch " << Latch->getName() << " into "922 << LastExit->getName() << "\n");923 924 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);925 MergeBlockIntoPredecessor(Latch, &DTU, LI, MSSAU, nullptr,926 /*PredecessorWithTwoSuccessors=*/true);927 928 if (SE) {929 // Merging blocks may remove blocks reference in the block disposition cache. Clear the cache.930 SE->forgetBlockAndLoopDispositions();931 }932 933 if (MSSAU && VerifyMemorySSA)934 MSSAU->getMemorySSA()->verifyMemorySSA();935 936 return true;937}938 939/// Rotate \c L, and return true if any modification was made.940bool LoopRotate::processLoop(Loop *L) {941 // Save the loop metadata.942 MDNode *LoopMD = L->getLoopID();943 944 bool SimplifiedLatch = false;945 946 // Simplify the loop latch before attempting to rotate the header947 // upward. Rotation may not be needed if the loop tail can be folded into the948 // loop exit.949 if (!RotationOnly)950 SimplifiedLatch = simplifyLoopLatch(L);951 952 bool MadeChange = rotateLoop(L, SimplifiedLatch);953 assert((!MadeChange || L->isLoopExiting(L->getLoopLatch())) &&954 "Loop latch should be exiting after loop-rotate.");955 956 // Restore the loop metadata.957 // NB! We presume LoopRotation DOESN'T ADD its own metadata.958 if ((MadeChange || SimplifiedLatch) && LoopMD)959 L->setLoopID(LoopMD);960 961 return MadeChange || SimplifiedLatch;962}963 964 965/// The utility to convert a loop into a loop with bottom test.966bool llvm::LoopRotation(Loop *L, LoopInfo *LI, const TargetTransformInfo *TTI,967 AssumptionCache *AC, DominatorTree *DT,968 ScalarEvolution *SE, MemorySSAUpdater *MSSAU,969 const SimplifyQuery &SQ, bool RotationOnly = true,970 unsigned Threshold = unsigned(-1),971 bool IsUtilMode = true, bool PrepareForLTO) {972 LoopRotate LR(Threshold, LI, TTI, AC, DT, SE, MSSAU, SQ, RotationOnly,973 IsUtilMode, PrepareForLTO);974 return LR.processLoop(L);975}976