1289 lines · cpp
1//===-- UnrollLoop.cpp - Loop unrolling utilities -------------------------===//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 implements some loop unrolling utilities. It does not define any10// actual pass or policy, but provides a single function to perform loop11// unrolling.12//13// The process of unrolling can produce extraneous basic blocks linked with14// unconditional branches. This will be corrected in the future.15//16//===----------------------------------------------------------------------===//17 18#include "llvm/ADT/ArrayRef.h"19#include "llvm/ADT/DenseMap.h"20#include "llvm/ADT/STLExtras.h"21#include "llvm/ADT/ScopedHashTable.h"22#include "llvm/ADT/SetVector.h"23#include "llvm/ADT/SmallVector.h"24#include "llvm/ADT/Statistic.h"25#include "llvm/ADT/StringRef.h"26#include "llvm/ADT/Twine.h"27#include "llvm/Analysis/AliasAnalysis.h"28#include "llvm/Analysis/AssumptionCache.h"29#include "llvm/Analysis/DomTreeUpdater.h"30#include "llvm/Analysis/InstructionSimplify.h"31#include "llvm/Analysis/LoopInfo.h"32#include "llvm/Analysis/LoopIterator.h"33#include "llvm/Analysis/MemorySSA.h"34#include "llvm/Analysis/OptimizationRemarkEmitter.h"35#include "llvm/Analysis/ScalarEvolution.h"36#include "llvm/IR/BasicBlock.h"37#include "llvm/IR/CFG.h"38#include "llvm/IR/Constants.h"39#include "llvm/IR/DebugInfoMetadata.h"40#include "llvm/IR/DebugLoc.h"41#include "llvm/IR/DiagnosticInfo.h"42#include "llvm/IR/Dominators.h"43#include "llvm/IR/Function.h"44#include "llvm/IR/IRBuilder.h"45#include "llvm/IR/Instruction.h"46#include "llvm/IR/Instructions.h"47#include "llvm/IR/IntrinsicInst.h"48#include "llvm/IR/Metadata.h"49#include "llvm/IR/PatternMatch.h"50#include "llvm/IR/Use.h"51#include "llvm/IR/User.h"52#include "llvm/IR/ValueHandle.h"53#include "llvm/IR/ValueMap.h"54#include "llvm/Support/Casting.h"55#include "llvm/Support/CommandLine.h"56#include "llvm/Support/Debug.h"57#include "llvm/Support/GenericDomTree.h"58#include "llvm/Support/raw_ostream.h"59#include "llvm/Transforms/Utils/BasicBlockUtils.h"60#include "llvm/Transforms/Utils/Cloning.h"61#include "llvm/Transforms/Utils/Local.h"62#include "llvm/Transforms/Utils/LoopSimplify.h"63#include "llvm/Transforms/Utils/LoopUtils.h"64#include "llvm/Transforms/Utils/SimplifyIndVar.h"65#include "llvm/Transforms/Utils/UnrollLoop.h"66#include "llvm/Transforms/Utils/ValueMapper.h"67#include <assert.h>68#include <numeric>69#include <vector>70 71namespace llvm {72class DataLayout;73class Value;74} // namespace llvm75 76using namespace llvm;77 78#define DEBUG_TYPE "loop-unroll"79 80// TODO: Should these be here or in LoopUnroll?81STATISTIC(NumCompletelyUnrolled, "Number of loops completely unrolled");82STATISTIC(NumUnrolled, "Number of loops unrolled (completely or otherwise)");83STATISTIC(NumUnrolledNotLatch, "Number of loops unrolled without a conditional "84 "latch (completely or otherwise)");85 86static cl::opt<bool>87UnrollRuntimeEpilog("unroll-runtime-epilog", cl::init(false), cl::Hidden,88 cl::desc("Allow runtime unrolled loops to be unrolled "89 "with epilog instead of prolog."));90 91static cl::opt<bool>92UnrollVerifyDomtree("unroll-verify-domtree", cl::Hidden,93 cl::desc("Verify domtree after unrolling"),94#ifdef EXPENSIVE_CHECKS95 cl::init(true)96#else97 cl::init(false)98#endif99 );100 101static cl::opt<bool>102UnrollVerifyLoopInfo("unroll-verify-loopinfo", cl::Hidden,103 cl::desc("Verify loopinfo after unrolling"),104#ifdef EXPENSIVE_CHECKS105 cl::init(true)106#else107 cl::init(false)108#endif109 );110 111static cl::opt<bool> UnrollAddParallelReductions(112 "unroll-add-parallel-reductions", cl::init(false), cl::Hidden,113 cl::desc("Allow unrolling to add parallel reduction phis."));114 115/// Check if unrolling created a situation where we need to insert phi nodes to116/// preserve LCSSA form.117/// \param Blocks is a vector of basic blocks representing unrolled loop.118/// \param L is the outer loop.119/// It's possible that some of the blocks are in L, and some are not. In this120/// case, if there is a use is outside L, and definition is inside L, we need to121/// insert a phi-node, otherwise LCSSA will be broken.122/// The function is just a helper function for llvm::UnrollLoop that returns123/// true if this situation occurs, indicating that LCSSA needs to be fixed.124static bool needToInsertPhisForLCSSA(Loop *L,125 const std::vector<BasicBlock *> &Blocks,126 LoopInfo *LI) {127 for (BasicBlock *BB : Blocks) {128 if (LI->getLoopFor(BB) == L)129 continue;130 for (Instruction &I : *BB) {131 for (Use &U : I.operands()) {132 if (const auto *Def = dyn_cast<Instruction>(U)) {133 Loop *DefLoop = LI->getLoopFor(Def->getParent());134 if (!DefLoop)135 continue;136 if (DefLoop->contains(L))137 return true;138 }139 }140 }141 }142 return false;143}144 145/// Adds ClonedBB to LoopInfo, creates a new loop for ClonedBB if necessary146/// and adds a mapping from the original loop to the new loop to NewLoops.147/// Returns nullptr if no new loop was created and a pointer to the148/// original loop OriginalBB was part of otherwise.149const Loop* llvm::addClonedBlockToLoopInfo(BasicBlock *OriginalBB,150 BasicBlock *ClonedBB, LoopInfo *LI,151 NewLoopsMap &NewLoops) {152 // Figure out which loop New is in.153 const Loop *OldLoop = LI->getLoopFor(OriginalBB);154 assert(OldLoop && "Should (at least) be in the loop being unrolled!");155 156 Loop *&NewLoop = NewLoops[OldLoop];157 if (!NewLoop) {158 // Found a new sub-loop.159 assert(OriginalBB == OldLoop->getHeader() &&160 "Header should be first in RPO");161 162 NewLoop = LI->AllocateLoop();163 Loop *NewLoopParent = NewLoops.lookup(OldLoop->getParentLoop());164 165 if (NewLoopParent)166 NewLoopParent->addChildLoop(NewLoop);167 else168 LI->addTopLevelLoop(NewLoop);169 170 NewLoop->addBasicBlockToLoop(ClonedBB, *LI);171 return OldLoop;172 } else {173 NewLoop->addBasicBlockToLoop(ClonedBB, *LI);174 return nullptr;175 }176}177 178/// The function chooses which type of unroll (epilog or prolog) is more179/// profitabale.180/// Epilog unroll is more profitable when there is PHI that starts from181/// constant. In this case epilog will leave PHI start from constant,182/// but prolog will convert it to non-constant.183///184/// loop:185/// PN = PHI [I, Latch], [CI, PreHeader]186/// I = foo(PN)187/// ...188///189/// Epilog unroll case.190/// loop:191/// PN = PHI [I2, Latch], [CI, PreHeader]192/// I1 = foo(PN)193/// I2 = foo(I1)194/// ...195/// Prolog unroll case.196/// NewPN = PHI [PrologI, Prolog], [CI, PreHeader]197/// loop:198/// PN = PHI [I2, Latch], [NewPN, PreHeader]199/// I1 = foo(PN)200/// I2 = foo(I1)201/// ...202///203static bool isEpilogProfitable(Loop *L) {204 BasicBlock *PreHeader = L->getLoopPreheader();205 BasicBlock *Header = L->getHeader();206 assert(PreHeader && Header);207 for (const PHINode &PN : Header->phis()) {208 if (isa<ConstantInt>(PN.getIncomingValueForBlock(PreHeader)))209 return true;210 }211 return false;212}213 214struct LoadValue {215 Instruction *DefI = nullptr;216 unsigned Generation = 0;217 LoadValue() = default;218 LoadValue(Instruction *Inst, unsigned Generation)219 : DefI(Inst), Generation(Generation) {}220};221 222class StackNode {223 ScopedHashTable<const SCEV *, LoadValue>::ScopeTy LoadScope;224 unsigned CurrentGeneration;225 unsigned ChildGeneration;226 DomTreeNode *Node;227 DomTreeNode::const_iterator ChildIter;228 DomTreeNode::const_iterator EndIter;229 bool Processed = false;230 231public:232 StackNode(ScopedHashTable<const SCEV *, LoadValue> &AvailableLoads,233 unsigned cg, DomTreeNode *N, DomTreeNode::const_iterator Child,234 DomTreeNode::const_iterator End)235 : LoadScope(AvailableLoads), CurrentGeneration(cg), ChildGeneration(cg),236 Node(N), ChildIter(Child), EndIter(End) {}237 // Accessors.238 unsigned currentGeneration() const { return CurrentGeneration; }239 unsigned childGeneration() const { return ChildGeneration; }240 void childGeneration(unsigned generation) { ChildGeneration = generation; }241 DomTreeNode *node() { return Node; }242 DomTreeNode::const_iterator childIter() const { return ChildIter; }243 244 DomTreeNode *nextChild() {245 DomTreeNode *Child = *ChildIter;246 ++ChildIter;247 return Child;248 }249 250 DomTreeNode::const_iterator end() const { return EndIter; }251 bool isProcessed() const { return Processed; }252 void process() { Processed = true; }253};254 255Value *getMatchingValue(LoadValue LV, LoadInst *LI, unsigned CurrentGeneration,256 BatchAAResults &BAA,257 function_ref<MemorySSA *()> GetMSSA) {258 if (!LV.DefI)259 return nullptr;260 if (LV.DefI->getType() != LI->getType())261 return nullptr;262 if (LV.Generation != CurrentGeneration) {263 MemorySSA *MSSA = GetMSSA();264 if (!MSSA)265 return nullptr;266 auto *EarlierMA = MSSA->getMemoryAccess(LV.DefI);267 MemoryAccess *LaterDef =268 MSSA->getWalker()->getClobberingMemoryAccess(LI, BAA);269 if (!MSSA->dominates(LaterDef, EarlierMA))270 return nullptr;271 }272 return LV.DefI;273}274 275void loadCSE(Loop *L, DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI,276 BatchAAResults &BAA, function_ref<MemorySSA *()> GetMSSA) {277 ScopedHashTable<const SCEV *, LoadValue> AvailableLoads;278 SmallVector<std::unique_ptr<StackNode>> NodesToProcess;279 DomTreeNode *HeaderD = DT.getNode(L->getHeader());280 NodesToProcess.emplace_back(new StackNode(AvailableLoads, 0, HeaderD,281 HeaderD->begin(), HeaderD->end()));282 283 unsigned CurrentGeneration = 0;284 while (!NodesToProcess.empty()) {285 StackNode *NodeToProcess = &*NodesToProcess.back();286 287 CurrentGeneration = NodeToProcess->currentGeneration();288 289 if (!NodeToProcess->isProcessed()) {290 // Process the node.291 292 // If this block has a single predecessor, then the predecessor is the293 // parent294 // of the domtree node and all of the live out memory values are still295 // current in this block. If this block has multiple predecessors, then296 // they could have invalidated the live-out memory values of our parent297 // value. For now, just be conservative and invalidate memory if this298 // block has multiple predecessors.299 if (!NodeToProcess->node()->getBlock()->getSinglePredecessor())300 ++CurrentGeneration;301 for (auto &I : make_early_inc_range(*NodeToProcess->node()->getBlock())) {302 303 auto *Load = dyn_cast<LoadInst>(&I);304 if (!Load || !Load->isSimple()) {305 if (I.mayWriteToMemory())306 CurrentGeneration++;307 continue;308 }309 310 const SCEV *PtrSCEV = SE.getSCEV(Load->getPointerOperand());311 LoadValue LV = AvailableLoads.lookup(PtrSCEV);312 if (Value *M =313 getMatchingValue(LV, Load, CurrentGeneration, BAA, GetMSSA)) {314 if (LI.replacementPreservesLCSSAForm(Load, M)) {315 Load->replaceAllUsesWith(M);316 Load->eraseFromParent();317 }318 } else {319 AvailableLoads.insert(PtrSCEV, LoadValue(Load, CurrentGeneration));320 }321 }322 NodeToProcess->childGeneration(CurrentGeneration);323 NodeToProcess->process();324 } else if (NodeToProcess->childIter() != NodeToProcess->end()) {325 // Push the next child onto the stack.326 DomTreeNode *Child = NodeToProcess->nextChild();327 if (!L->contains(Child->getBlock()))328 continue;329 NodesToProcess.emplace_back(330 new StackNode(AvailableLoads, NodeToProcess->childGeneration(), Child,331 Child->begin(), Child->end()));332 } else {333 // It has been processed, and there are no more children to process,334 // so delete it and pop it off the stack.335 NodesToProcess.pop_back();336 }337 }338}339 340/// Perform some cleanup and simplifications on loops after unrolling. It is341/// useful to simplify the IV's in the new loop, as well as do a quick342/// simplify/dce pass of the instructions.343void llvm::simplifyLoopAfterUnroll(Loop *L, bool SimplifyIVs, LoopInfo *LI,344 ScalarEvolution *SE, DominatorTree *DT,345 AssumptionCache *AC,346 const TargetTransformInfo *TTI,347 AAResults *AA) {348 using namespace llvm::PatternMatch;349 350 // Simplify any new induction variables in the partially unrolled loop.351 if (SE && SimplifyIVs) {352 SmallVector<WeakTrackingVH, 16> DeadInsts;353 simplifyLoopIVs(L, SE, DT, LI, TTI, DeadInsts);354 355 // Aggressively clean up dead instructions that simplifyLoopIVs already356 // identified. Any remaining should be cleaned up below.357 while (!DeadInsts.empty()) {358 Value *V = DeadInsts.pop_back_val();359 if (Instruction *Inst = dyn_cast_or_null<Instruction>(V))360 RecursivelyDeleteTriviallyDeadInstructions(Inst);361 }362 363 if (AA) {364 std::unique_ptr<MemorySSA> MSSA = nullptr;365 BatchAAResults BAA(*AA);366 loadCSE(L, *DT, *SE, *LI, BAA, [L, AA, DT, &MSSA]() -> MemorySSA * {367 if (!MSSA)368 MSSA.reset(new MemorySSA(*L, AA, DT));369 return &*MSSA;370 });371 }372 }373 374 // At this point, the code is well formed. Perform constprop, instsimplify,375 // and dce.376 const DataLayout &DL = L->getHeader()->getDataLayout();377 SmallVector<WeakTrackingVH, 16> DeadInsts;378 for (BasicBlock *BB : L->getBlocks()) {379 // Remove repeated debug instructions after loop unrolling.380 if (BB->getParent()->getSubprogram())381 RemoveRedundantDbgInstrs(BB);382 383 for (Instruction &Inst : llvm::make_early_inc_range(*BB)) {384 if (Value *V = simplifyInstruction(&Inst, {DL, nullptr, DT, AC}))385 if (LI->replacementPreservesLCSSAForm(&Inst, V))386 Inst.replaceAllUsesWith(V);387 if (isInstructionTriviallyDead(&Inst))388 DeadInsts.emplace_back(&Inst);389 390 // Fold ((add X, C1), C2) to (add X, C1+C2). This is very common in391 // unrolled loops, and handling this early allows following code to392 // identify the IV as a "simple recurrence" without first folding away393 // a long chain of adds.394 {395 Value *X;396 const APInt *C1, *C2;397 if (match(&Inst, m_Add(m_Add(m_Value(X), m_APInt(C1)), m_APInt(C2)))) {398 auto *InnerI = dyn_cast<Instruction>(Inst.getOperand(0));399 auto *InnerOBO = cast<OverflowingBinaryOperator>(Inst.getOperand(0));400 bool SignedOverflow;401 APInt NewC = C1->sadd_ov(*C2, SignedOverflow);402 Inst.setOperand(0, X);403 Inst.setOperand(1, ConstantInt::get(Inst.getType(), NewC));404 Inst.setHasNoUnsignedWrap(Inst.hasNoUnsignedWrap() &&405 InnerOBO->hasNoUnsignedWrap());406 Inst.setHasNoSignedWrap(Inst.hasNoSignedWrap() &&407 InnerOBO->hasNoSignedWrap() &&408 !SignedOverflow);409 if (InnerI && isInstructionTriviallyDead(InnerI))410 DeadInsts.emplace_back(InnerI);411 }412 }413 }414 // We can't do recursive deletion until we're done iterating, as we might415 // have a phi which (potentially indirectly) uses instructions later in416 // the block we're iterating through.417 RecursivelyDeleteTriviallyDeadInstructions(DeadInsts);418 }419}420 421// Loops containing convergent instructions that are uncontrolled or controlled422// from outside the loop must have a count that divides their TripMultiple.423LLVM_ATTRIBUTE_USED424static bool canHaveUnrollRemainder(const Loop *L) {425 if (getLoopConvergenceHeart(L))426 return false;427 428 // Check for uncontrolled convergent operations.429 for (auto &BB : L->blocks()) {430 for (auto &I : *BB) {431 if (isa<ConvergenceControlInst>(I))432 return true;433 if (auto *CB = dyn_cast<CallBase>(&I))434 if (CB->isConvergent())435 return CB->getConvergenceControlToken();436 }437 }438 return true;439}440 441/// Unroll the given loop by Count. The loop must be in LCSSA form. Unrolling442/// can only fail when the loop's latch block is not terminated by a conditional443/// branch instruction. However, if the trip count (and multiple) are not known,444/// loop unrolling will mostly produce more code that is no faster.445///446/// If Runtime is true then UnrollLoop will try to insert a prologue or447/// epilogue that ensures the latch has a trip multiple of Count. UnrollLoop448/// will not runtime-unroll the loop if computing the run-time trip count will449/// be expensive and AllowExpensiveTripCount is false.450///451/// The LoopInfo Analysis that is passed will be kept consistent.452///453/// This utility preserves LoopInfo. It will also preserve ScalarEvolution and454/// DominatorTree if they are non-null.455///456/// If RemainderLoop is non-null, it will receive the remainder loop (if457/// required and not fully unrolled).458LoopUnrollResult459llvm::UnrollLoop(Loop *L, UnrollLoopOptions ULO, LoopInfo *LI,460 ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC,461 const TargetTransformInfo *TTI, OptimizationRemarkEmitter *ORE,462 bool PreserveLCSSA, Loop **RemainderLoop, AAResults *AA) {463 assert(DT && "DomTree is required");464 465 if (!L->getLoopPreheader()) {466 LLVM_DEBUG(dbgs() << " Can't unroll; loop preheader-insertion failed.\n");467 return LoopUnrollResult::Unmodified;468 }469 470 if (!L->getLoopLatch()) {471 LLVM_DEBUG(dbgs() << " Can't unroll; loop exit-block-insertion failed.\n");472 return LoopUnrollResult::Unmodified;473 }474 475 // Loops with indirectbr cannot be cloned.476 if (!L->isSafeToClone()) {477 LLVM_DEBUG(dbgs() << " Can't unroll; Loop body cannot be cloned.\n");478 return LoopUnrollResult::Unmodified;479 }480 481 if (L->getHeader()->hasAddressTaken()) {482 // The loop-rotate pass can be helpful to avoid this in many cases.483 LLVM_DEBUG(484 dbgs() << " Won't unroll loop: address of header block is taken.\n");485 return LoopUnrollResult::Unmodified;486 }487 488 assert(ULO.Count > 0);489 490 // All these values should be taken only after peeling because they might have491 // changed.492 BasicBlock *Preheader = L->getLoopPreheader();493 BasicBlock *Header = L->getHeader();494 BasicBlock *LatchBlock = L->getLoopLatch();495 SmallVector<BasicBlock *, 4> ExitBlocks;496 L->getExitBlocks(ExitBlocks);497 std::vector<BasicBlock *> OriginalLoopBlocks = L->getBlocks();498 499 const unsigned MaxTripCount = SE->getSmallConstantMaxTripCount(L);500 const bool MaxOrZero = SE->isBackedgeTakenCountMaxOrZero(L);501 std::optional<unsigned> OriginalTripCount =502 llvm::getLoopEstimatedTripCount(L);503 BranchProbability OriginalLoopProb = llvm::getLoopProbability(L);504 505 // Effectively "DCE" unrolled iterations that are beyond the max tripcount506 // and will never be executed.507 if (MaxTripCount && ULO.Count > MaxTripCount)508 ULO.Count = MaxTripCount;509 510 struct ExitInfo {511 unsigned TripCount;512 unsigned TripMultiple;513 unsigned BreakoutTrip;514 bool ExitOnTrue;515 BasicBlock *FirstExitingBlock = nullptr;516 SmallVector<BasicBlock *> ExitingBlocks;517 };518 DenseMap<BasicBlock *, ExitInfo> ExitInfos;519 SmallVector<BasicBlock *, 4> ExitingBlocks;520 L->getExitingBlocks(ExitingBlocks);521 for (auto *ExitingBlock : ExitingBlocks) {522 // The folding code is not prepared to deal with non-branch instructions523 // right now.524 auto *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator());525 if (!BI)526 continue;527 528 ExitInfo &Info = ExitInfos[ExitingBlock];529 Info.TripCount = SE->getSmallConstantTripCount(L, ExitingBlock);530 Info.TripMultiple = SE->getSmallConstantTripMultiple(L, ExitingBlock);531 if (Info.TripCount != 0) {532 Info.BreakoutTrip = Info.TripCount % ULO.Count;533 Info.TripMultiple = 0;534 } else {535 Info.BreakoutTrip = Info.TripMultiple =536 (unsigned)std::gcd(ULO.Count, Info.TripMultiple);537 }538 Info.ExitOnTrue = !L->contains(BI->getSuccessor(0));539 Info.ExitingBlocks.push_back(ExitingBlock);540 LLVM_DEBUG(dbgs() << " Exiting block %" << ExitingBlock->getName()541 << ": TripCount=" << Info.TripCount542 << ", TripMultiple=" << Info.TripMultiple543 << ", BreakoutTrip=" << Info.BreakoutTrip << "\n");544 }545 546 // Are we eliminating the loop control altogether? Note that we can know547 // we're eliminating the backedge without knowing exactly which iteration548 // of the unrolled body exits.549 const bool CompletelyUnroll = ULO.Count == MaxTripCount;550 551 const bool PreserveOnlyFirst = CompletelyUnroll && MaxOrZero;552 553 // There's no point in performing runtime unrolling if this unroll count554 // results in a full unroll.555 if (CompletelyUnroll)556 ULO.Runtime = false;557 558 // Go through all exits of L and see if there are any phi-nodes there. We just559 // conservatively assume that they're inserted to preserve LCSSA form, which560 // means that complete unrolling might break this form. We need to either fix561 // it in-place after the transformation, or entirely rebuild LCSSA. TODO: For562 // now we just recompute LCSSA for the outer loop, but it should be possible563 // to fix it in-place.564 bool NeedToFixLCSSA =565 PreserveLCSSA && CompletelyUnroll &&566 any_of(ExitBlocks,567 [](const BasicBlock *BB) { return isa<PHINode>(BB->begin()); });568 569 // The current loop unroll pass can unroll loops that have570 // (1) single latch; and571 // (2a) latch is unconditional; or572 // (2b) latch is conditional and is an exiting block573 // FIXME: The implementation can be extended to work with more complicated574 // cases, e.g. loops with multiple latches.575 BranchInst *LatchBI = dyn_cast<BranchInst>(LatchBlock->getTerminator());576 577 // A conditional branch which exits the loop, which can be optimized to an578 // unconditional branch in the unrolled loop in some cases.579 bool LatchIsExiting = L->isLoopExiting(LatchBlock);580 if (!LatchBI || (LatchBI->isConditional() && !LatchIsExiting)) {581 LLVM_DEBUG(582 dbgs() << "Can't unroll; a conditional latch must exit the loop");583 return LoopUnrollResult::Unmodified;584 }585 586 assert((!ULO.Runtime || canHaveUnrollRemainder(L)) &&587 "Can't runtime unroll if loop contains a convergent operation.");588 589 bool EpilogProfitability =590 UnrollRuntimeEpilog.getNumOccurrences() ? UnrollRuntimeEpilog591 : isEpilogProfitable(L);592 593 if (ULO.Runtime &&594 !UnrollRuntimeLoopRemainder(595 L, ULO.Count, ULO.AllowExpensiveTripCount, EpilogProfitability,596 ULO.UnrollRemainder, ULO.ForgetAllSCEV, LI, SE, DT, AC, TTI,597 PreserveLCSSA, ULO.SCEVExpansionBudget, ULO.RuntimeUnrollMultiExit,598 RemainderLoop, OriginalTripCount, OriginalLoopProb)) {599 if (ULO.Force)600 ULO.Runtime = false;601 else {602 LLVM_DEBUG(dbgs() << "Won't unroll; remainder loop could not be "603 "generated when assuming runtime trip count\n");604 return LoopUnrollResult::Unmodified;605 }606 }607 608 using namespace ore;609 // Report the unrolling decision.610 if (CompletelyUnroll) {611 LLVM_DEBUG(dbgs() << "COMPLETELY UNROLLING loop %" << Header->getName()612 << " with trip count " << ULO.Count << "!\n");613 if (ORE)614 ORE->emit([&]() {615 return OptimizationRemark(DEBUG_TYPE, "FullyUnrolled", L->getStartLoc(),616 L->getHeader())617 << "completely unrolled loop with "618 << NV("UnrollCount", ULO.Count) << " iterations";619 });620 } else {621 LLVM_DEBUG(dbgs() << "UNROLLING loop %" << Header->getName() << " by "622 << ULO.Count);623 if (ULO.Runtime)624 LLVM_DEBUG(dbgs() << " with run-time trip count");625 LLVM_DEBUG(dbgs() << "!\n");626 627 if (ORE)628 ORE->emit([&]() {629 OptimizationRemark Diag(DEBUG_TYPE, "PartialUnrolled", L->getStartLoc(),630 L->getHeader());631 Diag << "unrolled loop by a factor of " << NV("UnrollCount", ULO.Count);632 if (ULO.Runtime)633 Diag << " with run-time trip count";634 return Diag;635 });636 }637 638 // We are going to make changes to this loop. SCEV may be keeping cached info639 // about it, in particular about backedge taken count. The changes we make640 // are guaranteed to invalidate this information for our loop. It is tempting641 // to only invalidate the loop being unrolled, but it is incorrect as long as642 // all exiting branches from all inner loops have impact on the outer loops,643 // and if something changes inside them then any of outer loops may also644 // change. When we forget outermost loop, we also forget all contained loops645 // and this is what we need here.646 if (SE) {647 if (ULO.ForgetAllSCEV)648 SE->forgetAllLoops();649 else {650 SE->forgetTopmostLoop(L);651 SE->forgetBlockAndLoopDispositions();652 }653 }654 655 if (!LatchIsExiting)656 ++NumUnrolledNotLatch;657 658 // For the first iteration of the loop, we should use the precloned values for659 // PHI nodes. Insert associations now.660 ValueToValueMapTy LastValueMap;661 std::vector<PHINode*> OrigPHINode;662 for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {663 OrigPHINode.push_back(cast<PHINode>(I));664 }665 666 // Collect phi nodes for reductions for which we can introduce multiple667 // parallel reduction phis and compute the final reduction result after the668 // loop. This requires a single exit block after unrolling. This is ensured by669 // restricting to single-block loops where the unrolled iterations are known670 // to not exit.671 DenseMap<PHINode *, RecurrenceDescriptor> Reductions;672 bool CanAddAdditionalAccumulators =673 (UnrollAddParallelReductions.getNumOccurrences() > 0674 ? UnrollAddParallelReductions675 : ULO.AddAdditionalAccumulators) &&676 !CompletelyUnroll && L->getNumBlocks() == 1 &&677 (ULO.Runtime ||678 (ExitInfos.contains(Header) && ((ExitInfos[Header].TripCount != 0 &&679 ExitInfos[Header].BreakoutTrip == 0))));680 681 // Limit parallelizing reductions to unroll counts of 4 or less for now.682 // TODO: The number of parallel reductions should depend on the number of683 // execution units. We also don't have to add a parallel reduction phi per684 // unrolled iteration, but could for example add a parallel phi for every 2685 // unrolled iterations.686 if (CanAddAdditionalAccumulators && ULO.Count <= 4) {687 for (PHINode &Phi : Header->phis()) {688 auto RdxDesc = canParallelizeReductionWhenUnrolling(Phi, L, SE);689 if (!RdxDesc)690 continue;691 692 // Only handle duplicate phis for a single reduction for now.693 // TODO: Handle any number of reductions694 if (!Reductions.empty())695 continue;696 697 Reductions[&Phi] = *RdxDesc;698 }699 }700 701 std::vector<BasicBlock *> Headers;702 std::vector<BasicBlock *> Latches;703 Headers.push_back(Header);704 Latches.push_back(LatchBlock);705 706 // The current on-the-fly SSA update requires blocks to be processed in707 // reverse postorder so that LastValueMap contains the correct value at each708 // exit.709 LoopBlocksDFS DFS(L);710 DFS.perform(LI);711 712 // Stash the DFS iterators before adding blocks to the loop.713 LoopBlocksDFS::RPOIterator BlockBegin = DFS.beginRPO();714 LoopBlocksDFS::RPOIterator BlockEnd = DFS.endRPO();715 716 std::vector<BasicBlock*> UnrolledLoopBlocks = L->getBlocks();717 718 // Loop Unrolling might create new loops. While we do preserve LoopInfo, we719 // might break loop-simplified form for these loops (as they, e.g., would720 // share the same exit blocks). We'll keep track of loops for which we can721 // break this so that later we can re-simplify them.722 SmallSetVector<Loop *, 4> LoopsToSimplify;723 LoopsToSimplify.insert_range(*L);724 725 // When a FSDiscriminator is enabled, we don't need to add the multiply726 // factors to the discriminators.727 if (Header->getParent()->shouldEmitDebugInfoForProfiling() &&728 !EnableFSDiscriminator)729 for (BasicBlock *BB : L->getBlocks())730 for (Instruction &I : *BB)731 if (!I.isDebugOrPseudoInst())732 if (const DILocation *DIL = I.getDebugLoc()) {733 auto NewDIL = DIL->cloneByMultiplyingDuplicationFactor(ULO.Count);734 if (NewDIL)735 I.setDebugLoc(*NewDIL);736 else737 LLVM_DEBUG(dbgs()738 << "Failed to create new discriminator: "739 << DIL->getFilename() << " Line: " << DIL->getLine());740 }741 742 // Identify what noalias metadata is inside the loop: if it is inside the743 // loop, the associated metadata must be cloned for each iteration.744 SmallVector<MDNode *, 6> LoopLocalNoAliasDeclScopes;745 identifyNoAliasScopesToClone(L->getBlocks(), LoopLocalNoAliasDeclScopes);746 747 // We place the unrolled iterations immediately after the original loop748 // latch. This is a reasonable default placement if we don't have block749 // frequencies, and if we do, well the layout will be adjusted later.750 auto BlockInsertPt = std::next(LatchBlock->getIterator());751 SmallVector<Instruction *> PartialReductions;752 for (unsigned It = 1; It != ULO.Count; ++It) {753 SmallVector<BasicBlock *, 8> NewBlocks;754 SmallDenseMap<const Loop *, Loop *, 4> NewLoops;755 NewLoops[L] = L;756 757 for (LoopBlocksDFS::RPOIterator BB = BlockBegin; BB != BlockEnd; ++BB) {758 ValueToValueMapTy VMap;759 BasicBlock *New = CloneBasicBlock(*BB, VMap, "." + Twine(It));760 Header->getParent()->insert(BlockInsertPt, New);761 762 assert((*BB != Header || LI->getLoopFor(*BB) == L) &&763 "Header should not be in a sub-loop");764 // Tell LI about New.765 const Loop *OldLoop = addClonedBlockToLoopInfo(*BB, New, LI, NewLoops);766 if (OldLoop)767 LoopsToSimplify.insert(NewLoops[OldLoop]);768 769 if (*BB == Header) {770 // Loop over all of the PHI nodes in the block, changing them to use771 // the incoming values from the previous block.772 for (PHINode *OrigPHI : OrigPHINode) {773 PHINode *NewPHI = cast<PHINode>(VMap[OrigPHI]);774 Value *InVal = NewPHI->getIncomingValueForBlock(LatchBlock);775 776 // Use cloned phis as parallel phis for partial reductions, which will777 // get combined to the final reduction result after the loop.778 if (Reductions.contains(OrigPHI)) {779 // Collect partial reduction results.780 if (PartialReductions.empty())781 PartialReductions.push_back(cast<Instruction>(InVal));782 PartialReductions.push_back(cast<Instruction>(VMap[InVal]));783 784 // Update the start value for the cloned phis to use the identity785 // value for the reduction.786 const RecurrenceDescriptor &RdxDesc = Reductions[OrigPHI];787 NewPHI->setIncomingValueForBlock(788 L->getLoopPreheader(),789 getRecurrenceIdentity(RdxDesc.getRecurrenceKind(),790 OrigPHI->getType(),791 RdxDesc.getFastMathFlags()));792 793 // Update NewPHI to use the cloned value for the iteration and move794 // to header.795 NewPHI->replaceUsesOfWith(InVal, VMap[InVal]);796 NewPHI->moveBefore(OrigPHI->getIterator());797 continue;798 }799 800 if (Instruction *InValI = dyn_cast<Instruction>(InVal))801 if (It > 1 && L->contains(InValI))802 InVal = LastValueMap[InValI];803 VMap[OrigPHI] = InVal;804 NewPHI->eraseFromParent();805 }806 807 // Eliminate copies of the loop heart intrinsic, if any.808 if (ULO.Heart) {809 auto it = VMap.find(ULO.Heart);810 assert(it != VMap.end());811 Instruction *heartCopy = cast<Instruction>(it->second);812 heartCopy->eraseFromParent();813 VMap.erase(it);814 }815 }816 817 // Remap source location atom instance. Do this now, rather than818 // when we remap instructions, because remap is called once we've819 // cloned all blocks (all the clones would get the same atom820 // number).821 if (!VMap.AtomMap.empty())822 for (Instruction &I : *New)823 RemapSourceAtom(&I, VMap);824 825 // Update our running map of newest clones826 LastValueMap[*BB] = New;827 for (ValueToValueMapTy::iterator VI = VMap.begin(), VE = VMap.end();828 VI != VE; ++VI)829 LastValueMap[VI->first] = VI->second;830 831 // Add phi entries for newly created values to all exit blocks.832 for (BasicBlock *Succ : successors(*BB)) {833 if (L->contains(Succ))834 continue;835 for (PHINode &PHI : Succ->phis()) {836 Value *Incoming = PHI.getIncomingValueForBlock(*BB);837 ValueToValueMapTy::iterator It = LastValueMap.find(Incoming);838 if (It != LastValueMap.end())839 Incoming = It->second;840 PHI.addIncoming(Incoming, New);841 SE->forgetLcssaPhiWithNewPredecessor(L, &PHI);842 }843 }844 // Keep track of new headers and latches as we create them, so that845 // we can insert the proper branches later.846 if (*BB == Header)847 Headers.push_back(New);848 if (*BB == LatchBlock)849 Latches.push_back(New);850 851 // Keep track of the exiting block and its successor block contained in852 // the loop for the current iteration.853 auto ExitInfoIt = ExitInfos.find(*BB);854 if (ExitInfoIt != ExitInfos.end())855 ExitInfoIt->second.ExitingBlocks.push_back(New);856 857 NewBlocks.push_back(New);858 UnrolledLoopBlocks.push_back(New);859 860 // Update DomTree: since we just copy the loop body, and each copy has a861 // dedicated entry block (copy of the header block), this header's copy862 // dominates all copied blocks. That means, dominance relations in the863 // copied body are the same as in the original body.864 if (*BB == Header)865 DT->addNewBlock(New, Latches[It - 1]);866 else {867 auto BBDomNode = DT->getNode(*BB);868 auto BBIDom = BBDomNode->getIDom();869 BasicBlock *OriginalBBIDom = BBIDom->getBlock();870 DT->addNewBlock(871 New, cast<BasicBlock>(LastValueMap[cast<Value>(OriginalBBIDom)]));872 }873 }874 875 // Remap all instructions in the most recent iteration.876 // Key Instructions: Nothing to do - we've already remapped the atoms.877 remapInstructionsInBlocks(NewBlocks, LastValueMap);878 for (BasicBlock *NewBlock : NewBlocks)879 for (Instruction &I : *NewBlock)880 if (auto *II = dyn_cast<AssumeInst>(&I))881 AC->registerAssumption(II);882 883 {884 // Identify what other metadata depends on the cloned version. After885 // cloning, replace the metadata with the corrected version for both886 // memory instructions and noalias intrinsics.887 std::string ext = (Twine("It") + Twine(It)).str();888 cloneAndAdaptNoAliasScopes(LoopLocalNoAliasDeclScopes, NewBlocks,889 Header->getContext(), ext);890 }891 }892 893 // Loop over the PHI nodes in the original block, setting incoming values.894 for (PHINode *PN : OrigPHINode) {895 if (CompletelyUnroll) {896 PN->replaceAllUsesWith(PN->getIncomingValueForBlock(Preheader));897 PN->eraseFromParent();898 } else if (ULO.Count > 1) {899 if (Reductions.contains(PN))900 continue;901 902 Value *InVal = PN->removeIncomingValue(LatchBlock, false);903 // If this value was defined in the loop, take the value defined by the904 // last iteration of the loop.905 if (Instruction *InValI = dyn_cast<Instruction>(InVal)) {906 if (L->contains(InValI))907 InVal = LastValueMap[InVal];908 }909 assert(Latches.back() == LastValueMap[LatchBlock] && "bad last latch");910 PN->addIncoming(InVal, Latches.back());911 }912 }913 914 // Connect latches of the unrolled iterations to the headers of the next915 // iteration. Currently they point to the header of the same iteration.916 for (unsigned i = 0, e = Latches.size(); i != e; ++i) {917 unsigned j = (i + 1) % e;918 Latches[i]->getTerminator()->replaceSuccessorWith(Headers[i], Headers[j]);919 }920 921 // Update dominators of blocks we might reach through exits.922 // Immediate dominator of such block might change, because we add more923 // routes which can lead to the exit: we can now reach it from the copied924 // iterations too.925 if (ULO.Count > 1) {926 for (auto *BB : OriginalLoopBlocks) {927 auto *BBDomNode = DT->getNode(BB);928 SmallVector<BasicBlock *, 16> ChildrenToUpdate;929 for (auto *ChildDomNode : BBDomNode->children()) {930 auto *ChildBB = ChildDomNode->getBlock();931 if (!L->contains(ChildBB))932 ChildrenToUpdate.push_back(ChildBB);933 }934 // The new idom of the block will be the nearest common dominator935 // of all copies of the previous idom. This is equivalent to the936 // nearest common dominator of the previous idom and the first latch,937 // which dominates all copies of the previous idom.938 BasicBlock *NewIDom = DT->findNearestCommonDominator(BB, LatchBlock);939 for (auto *ChildBB : ChildrenToUpdate)940 DT->changeImmediateDominator(ChildBB, NewIDom);941 }942 }943 944 assert(!UnrollVerifyDomtree ||945 DT->verify(DominatorTree::VerificationLevel::Fast));946 947 SmallVector<DominatorTree::UpdateType> DTUpdates;948 auto SetDest = [&](BasicBlock *Src, bool WillExit, bool ExitOnTrue) {949 auto *Term = cast<BranchInst>(Src->getTerminator());950 const unsigned Idx = ExitOnTrue ^ WillExit;951 BasicBlock *Dest = Term->getSuccessor(Idx);952 BasicBlock *DeadSucc = Term->getSuccessor(1-Idx);953 954 // Remove predecessors from all non-Dest successors.955 DeadSucc->removePredecessor(Src, /* KeepOneInputPHIs */ true);956 957 // Replace the conditional branch with an unconditional one.958 auto *BI = BranchInst::Create(Dest, Term->getIterator());959 BI->setDebugLoc(Term->getDebugLoc());960 Term->eraseFromParent();961 962 DTUpdates.emplace_back(DominatorTree::Delete, Src, DeadSucc);963 };964 965 auto WillExit = [&](const ExitInfo &Info, unsigned i, unsigned j,966 bool IsLatch) -> std::optional<bool> {967 if (CompletelyUnroll) {968 if (PreserveOnlyFirst) {969 if (i == 0)970 return std::nullopt;971 return j == 0;972 }973 // Complete (but possibly inexact) unrolling974 if (j == 0)975 return true;976 if (Info.TripCount && j != Info.TripCount)977 return false;978 return std::nullopt;979 }980 981 if (ULO.Runtime) {982 // If runtime unrolling inserts a prologue, information about non-latch983 // exits may be stale.984 if (IsLatch && j != 0)985 return false;986 return std::nullopt;987 }988 989 if (j != Info.BreakoutTrip &&990 (Info.TripMultiple == 0 || j % Info.TripMultiple != 0)) {991 // If we know the trip count or a multiple of it, we can safely use an992 // unconditional branch for some iterations.993 return false;994 }995 return std::nullopt;996 };997 998 // Fold branches for iterations where we know that they will exit or not999 // exit.1000 for (auto &Pair : ExitInfos) {1001 ExitInfo &Info = Pair.second;1002 for (unsigned i = 0, e = Info.ExitingBlocks.size(); i != e; ++i) {1003 // The branch destination.1004 unsigned j = (i + 1) % e;1005 bool IsLatch = Pair.first == LatchBlock;1006 std::optional<bool> KnownWillExit = WillExit(Info, i, j, IsLatch);1007 if (!KnownWillExit) {1008 if (!Info.FirstExitingBlock)1009 Info.FirstExitingBlock = Info.ExitingBlocks[i];1010 continue;1011 }1012 1013 // We don't fold known-exiting branches for non-latch exits here,1014 // because this ensures that both all loop blocks and all exit blocks1015 // remain reachable in the CFG.1016 // TODO: We could fold these branches, but it would require much more1017 // sophisticated updates to LoopInfo.1018 if (*KnownWillExit && !IsLatch) {1019 if (!Info.FirstExitingBlock)1020 Info.FirstExitingBlock = Info.ExitingBlocks[i];1021 continue;1022 }1023 1024 SetDest(Info.ExitingBlocks[i], *KnownWillExit, Info.ExitOnTrue);1025 }1026 }1027 1028 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);1029 DomTreeUpdater *DTUToUse = &DTU;1030 if (ExitingBlocks.size() == 1 && ExitInfos.size() == 1) {1031 // Manually update the DT if there's a single exiting node. In that case1032 // there's a single exit node and it is sufficient to update the nodes1033 // immediately dominated by the original exiting block. They will become1034 // dominated by the first exiting block that leaves the loop after1035 // unrolling. Note that the CFG inside the loop does not change, so there's1036 // no need to update the DT inside the unrolled loop.1037 DTUToUse = nullptr;1038 auto &[OriginalExit, Info] = *ExitInfos.begin();1039 if (!Info.FirstExitingBlock)1040 Info.FirstExitingBlock = Info.ExitingBlocks.back();1041 for (auto *C : to_vector(DT->getNode(OriginalExit)->children())) {1042 if (L->contains(C->getBlock()))1043 continue;1044 C->setIDom(DT->getNode(Info.FirstExitingBlock));1045 }1046 } else {1047 DTU.applyUpdates(DTUpdates);1048 }1049 1050 // When completely unrolling, the last latch becomes unreachable.1051 if (!LatchIsExiting && CompletelyUnroll) {1052 // There is no need to update the DT here, because there must be a unique1053 // latch. Hence if the latch is not exiting it must directly branch back to1054 // the original loop header and does not dominate any nodes.1055 assert(LatchBlock->getSingleSuccessor() && "Loop with multiple latches?");1056 changeToUnreachable(Latches.back()->getTerminator(), PreserveLCSSA);1057 }1058 1059 // Merge adjacent basic blocks, if possible.1060 for (BasicBlock *Latch : Latches) {1061 BranchInst *Term = dyn_cast<BranchInst>(Latch->getTerminator());1062 assert((Term ||1063 (CompletelyUnroll && !LatchIsExiting && Latch == Latches.back())) &&1064 "Need a branch as terminator, except when fully unrolling with "1065 "unconditional latch");1066 if (Term && Term->isUnconditional()) {1067 BasicBlock *Dest = Term->getSuccessor(0);1068 BasicBlock *Fold = Dest->getUniquePredecessor();1069 if (MergeBlockIntoPredecessor(Dest, /*DTU=*/DTUToUse, LI,1070 /*MSSAU=*/nullptr, /*MemDep=*/nullptr,1071 /*PredecessorWithTwoSuccessors=*/false,1072 DTUToUse ? nullptr : DT)) {1073 // Dest has been folded into Fold. Update our worklists accordingly.1074 llvm::replace(Latches, Dest, Fold);1075 llvm::erase(UnrolledLoopBlocks, Dest);1076 }1077 }1078 }1079 1080 // If there are partial reductions, create code in the exit block to compute1081 // the final result and update users of the final result.1082 if (!PartialReductions.empty()) {1083 BasicBlock *ExitBlock = L->getExitBlock();1084 assert(ExitBlock &&1085 "Can only introduce parallel reduction phis with single exit block");1086 assert(Reductions.size() == 1 &&1087 "currently only a single reduction is supported");1088 Value *FinalRdxValue = PartialReductions.back();1089 Value *RdxResult = nullptr;1090 for (PHINode &Phi : ExitBlock->phis()) {1091 if (Phi.getIncomingValueForBlock(L->getLoopLatch()) != FinalRdxValue)1092 continue;1093 if (!RdxResult) {1094 RdxResult = PartialReductions.front();1095 IRBuilder Builder(ExitBlock, ExitBlock->getFirstNonPHIIt());1096 Builder.setFastMathFlags(Reductions.begin()->second.getFastMathFlags());1097 RecurKind RK = Reductions.begin()->second.getRecurrenceKind();1098 for (Instruction *RdxPart : drop_begin(PartialReductions)) {1099 RdxResult = Builder.CreateBinOp(1100 (Instruction::BinaryOps)RecurrenceDescriptor::getOpcode(RK),1101 RdxPart, RdxResult, "bin.rdx");1102 }1103 NeedToFixLCSSA = true;1104 for (Instruction *RdxPart : PartialReductions)1105 RdxPart->dropPoisonGeneratingFlags();1106 }1107 1108 Phi.replaceAllUsesWith(RdxResult);1109 }1110 }1111 1112 if (DTUToUse) {1113 // Apply updates to the DomTree.1114 DT = &DTU.getDomTree();1115 }1116 assert(!UnrollVerifyDomtree ||1117 DT->verify(DominatorTree::VerificationLevel::Fast));1118 1119 // At this point, the code is well formed. We now simplify the unrolled loop,1120 // doing constant propagation and dead code elimination as we go.1121 simplifyLoopAfterUnroll(L, !CompletelyUnroll && ULO.Count > 1, LI, SE, DT, AC,1122 TTI, AA);1123 1124 NumCompletelyUnrolled += CompletelyUnroll;1125 ++NumUnrolled;1126 1127 Loop *OuterL = L->getParentLoop();1128 // Update LoopInfo if the loop is completely removed.1129 if (CompletelyUnroll) {1130 LI->erase(L);1131 // We shouldn't try to use `L` anymore.1132 L = nullptr;1133 } else {1134 // Update metadata for the loop's branch weights and estimated trip count:1135 // - If ULO.Runtime, UnrollRuntimeLoopRemainder sets the guard branch1136 // weights, latch branch weights, and estimated trip count of the1137 // remainder loop it creates. It also sets the branch weights for the1138 // unrolled loop guard it creates. The branch weights for the unrolled1139 // loop latch are adjusted below. FIXME: Handle prologue loops.1140 // - Otherwise, if unrolled loop iteration latches become unconditional,1141 // branch weights are adjusted above. FIXME: Actually handle such1142 // unconditional latches.1143 // - Otherwise, the original loop's branch weights are correct for the1144 // unrolled loop, so do not adjust them.1145 // - In all cases, the unrolled loop's estimated trip count is set below.1146 //1147 // As an example of the last case, consider what happens if the unroll count1148 // is 4 for a loop with an estimated trip count of 10 when we do not create1149 // a remainder loop and all iterations' latches remain conditional. Each1150 // unrolled iteration's latch still has the same probability of exiting the1151 // loop as it did when in the original loop, and thus it should still have1152 // the same branch weights. Each unrolled iteration's non-zero probability1153 // of exiting already appropriately reduces the probability of reaching the1154 // remaining iterations just as it did in the original loop. Trying to also1155 // adjust the branch weights of the final unrolled iteration's latch (i.e.,1156 // the backedge for the unrolled loop as a whole) to reflect its new trip1157 // count of 3 will erroneously further reduce its block frequencies.1158 // However, in case an analysis later needs to estimate the trip count of1159 // the unrolled loop as a whole without considering the branch weights for1160 // each unrolled iteration's latch within it, we store the new trip count as1161 // separate metadata.1162 if (!OriginalLoopProb.isUnknown() && ULO.Runtime && EpilogProfitability) {1163 // Where p is always the probability of executing at least 1 more1164 // iteration, the probability for at least n more iterations is p^n.1165 setLoopProbability(L, OriginalLoopProb.pow(ULO.Count));1166 }1167 if (OriginalTripCount) {1168 unsigned NewTripCount = *OriginalTripCount / ULO.Count;1169 if (!ULO.Runtime && *OriginalTripCount % ULO.Count)1170 ++NewTripCount;1171 setLoopEstimatedTripCount(L, NewTripCount);1172 }1173 }1174 1175 // LoopInfo should not be valid, confirm that.1176 if (UnrollVerifyLoopInfo)1177 LI->verify(*DT);1178 1179 // After complete unrolling most of the blocks should be contained in OuterL.1180 // However, some of them might happen to be out of OuterL (e.g. if they1181 // precede a loop exit). In this case we might need to insert PHI nodes in1182 // order to preserve LCSSA form.1183 // We don't need to check this if we already know that we need to fix LCSSA1184 // form.1185 // TODO: For now we just recompute LCSSA for the outer loop in this case, but1186 // it should be possible to fix it in-place.1187 if (PreserveLCSSA && OuterL && CompletelyUnroll && !NeedToFixLCSSA)1188 NeedToFixLCSSA |= ::needToInsertPhisForLCSSA(OuterL, UnrolledLoopBlocks, LI);1189 1190 // Make sure that loop-simplify form is preserved. We want to simplify1191 // at least one layer outside of the loop that was unrolled so that any1192 // changes to the parent loop exposed by the unrolling are considered.1193 if (OuterL) {1194 // OuterL includes all loops for which we can break loop-simplify, so1195 // it's sufficient to simplify only it (it'll recursively simplify inner1196 // loops too).1197 if (NeedToFixLCSSA) {1198 // LCSSA must be performed on the outermost affected loop. The unrolled1199 // loop's last loop latch is guaranteed to be in the outermost loop1200 // after LoopInfo's been updated by LoopInfo::erase.1201 Loop *LatchLoop = LI->getLoopFor(Latches.back());1202 Loop *FixLCSSALoop = OuterL;1203 if (!FixLCSSALoop->contains(LatchLoop))1204 while (FixLCSSALoop->getParentLoop() != LatchLoop)1205 FixLCSSALoop = FixLCSSALoop->getParentLoop();1206 1207 formLCSSARecursively(*FixLCSSALoop, *DT, LI, SE);1208 } else if (PreserveLCSSA) {1209 assert(OuterL->isLCSSAForm(*DT) &&1210 "Loops should be in LCSSA form after loop-unroll.");1211 }1212 1213 // TODO: That potentially might be compile-time expensive. We should try1214 // to fix the loop-simplified form incrementally.1215 simplifyLoop(OuterL, DT, LI, SE, AC, nullptr, PreserveLCSSA);1216 } else {1217 // Simplify loops for which we might've broken loop-simplify form.1218 for (Loop *SubLoop : LoopsToSimplify)1219 simplifyLoop(SubLoop, DT, LI, SE, AC, nullptr, PreserveLCSSA);1220 }1221 1222 return CompletelyUnroll ? LoopUnrollResult::FullyUnrolled1223 : LoopUnrollResult::PartiallyUnrolled;1224}1225 1226/// Given an llvm.loop loop id metadata node, returns the loop hint metadata1227/// node with the given name (for example, "llvm.loop.unroll.count"). If no1228/// such metadata node exists, then nullptr is returned.1229MDNode *llvm::GetUnrollMetadata(MDNode *LoopID, StringRef Name) {1230 // First operand should refer to the loop id itself.1231 assert(LoopID->getNumOperands() > 0 && "requires at least one operand");1232 assert(LoopID->getOperand(0) == LoopID && "invalid loop id");1233 1234 for (const MDOperand &MDO : llvm::drop_begin(LoopID->operands())) {1235 MDNode *MD = dyn_cast<MDNode>(MDO);1236 if (!MD)1237 continue;1238 1239 MDString *S = dyn_cast<MDString>(MD->getOperand(0));1240 if (!S)1241 continue;1242 1243 if (Name == S->getString())1244 return MD;1245 }1246 return nullptr;1247}1248 1249std::optional<RecurrenceDescriptor>1250llvm::canParallelizeReductionWhenUnrolling(PHINode &Phi, Loop *L,1251 ScalarEvolution *SE) {1252 RecurrenceDescriptor RdxDesc;1253 if (!RecurrenceDescriptor::isReductionPHI(&Phi, L, RdxDesc,1254 /*DemandedBits=*/nullptr,1255 /*AC=*/nullptr, /*DT=*/nullptr, SE))1256 return std::nullopt;1257 if (RdxDesc.hasUsesOutsideReductionChain())1258 return std::nullopt;1259 RecurKind RK = RdxDesc.getRecurrenceKind();1260 // Skip unsupported reductions.1261 // TODO: Handle additional reductions, including min-max reductions.1262 if (RecurrenceDescriptor::isAnyOfRecurrenceKind(RK) ||1263 RecurrenceDescriptor::isFindIVRecurrenceKind(RK) ||1264 RecurrenceDescriptor::isMinMaxRecurrenceKind(RK))1265 return std::nullopt;1266 1267 if (RdxDesc.hasExactFPMath())1268 return std::nullopt;1269 1270 if (RdxDesc.IntermediateStore)1271 return std::nullopt;1272 1273 // Don't unroll reductions with constant ops; those can be folded to a1274 // single induction update.1275 if (any_of(cast<Instruction>(Phi.getIncomingValueForBlock(L->getLoopLatch()))1276 ->operands(),1277 IsaPred<Constant>))1278 return std::nullopt;1279 1280 BasicBlock *Latch = L->getLoopLatch();1281 if (!Latch ||1282 !is_contained(1283 cast<Instruction>(Phi.getIncomingValueForBlock(Latch))->operands(),1284 &Phi))1285 return std::nullopt;1286 1287 return RdxDesc;1288}1289