1134 lines · cpp
1//===-- UnrollLoopRuntime.cpp - Runtime 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 for loops with run-time10// trip counts. See LoopUnroll.cpp for unrolling loops with compile-time11// trip counts.12//13// The functions in this file are used to generate extra code when the14// run-time trip count modulo the unroll factor is not 0. When this is the15// case, we need to generate code to execute these 'left over' iterations.16//17// The current strategy generates an if-then-else sequence prior to the18// unrolled loop to execute the 'left over' iterations before or after the19// unrolled loop.20//21//===----------------------------------------------------------------------===//22 23#include "llvm/ADT/Statistic.h"24#include "llvm/Analysis/DomTreeUpdater.h"25#include "llvm/Analysis/InstructionSimplify.h"26#include "llvm/Analysis/LoopIterator.h"27#include "llvm/Analysis/ScalarEvolution.h"28#include "llvm/Analysis/ValueTracking.h"29#include "llvm/IR/BasicBlock.h"30#include "llvm/IR/Dominators.h"31#include "llvm/IR/MDBuilder.h"32#include "llvm/IR/Module.h"33#include "llvm/IR/ProfDataUtils.h"34#include "llvm/Support/CommandLine.h"35#include "llvm/Support/Debug.h"36#include "llvm/Support/raw_ostream.h"37#include "llvm/Transforms/Utils/BasicBlockUtils.h"38#include "llvm/Transforms/Utils/Cloning.h"39#include "llvm/Transforms/Utils/Local.h"40#include "llvm/Transforms/Utils/LoopUtils.h"41#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"42#include "llvm/Transforms/Utils/UnrollLoop.h"43#include <cmath>44 45using namespace llvm;46 47#define DEBUG_TYPE "loop-unroll"48 49STATISTIC(NumRuntimeUnrolled,50 "Number of loops unrolled with run-time trip counts");51static cl::opt<bool> UnrollRuntimeMultiExit(52 "unroll-runtime-multi-exit", cl::init(false), cl::Hidden,53 cl::desc("Allow runtime unrolling for loops with multiple exits, when "54 "epilog is generated"));55static cl::opt<bool> UnrollRuntimeOtherExitPredictable(56 "unroll-runtime-other-exit-predictable", cl::init(false), cl::Hidden,57 cl::desc("Assume the non latch exit block to be predictable"));58 59// Probability that the loop trip count is so small that after the prolog60// we do not enter the unrolled loop at all.61// It is unlikely that the loop trip count is smaller than the unroll factor;62// other than that, the choice of constant is not tuned yet.63static const uint32_t UnrolledLoopHeaderWeights[] = {1, 127};64// Probability that the loop trip count is so small that we skip the unrolled65// loop completely and immediately enter the epilogue loop.66// It is unlikely that the loop trip count is smaller than the unroll factor;67// other than that, the choice of constant is not tuned yet.68static const uint32_t EpilogHeaderWeights[] = {1, 127};69 70/// Connect the unrolling prolog code to the original loop.71/// The unrolling prolog code contains code to execute the72/// 'extra' iterations if the run-time trip count modulo the73/// unroll count is non-zero.74///75/// This function performs the following:76/// - Create PHI nodes at prolog end block to combine values77/// that exit the prolog code and jump around the prolog.78/// - Add a PHI operand to a PHI node at the loop exit block79/// for values that exit the prolog and go around the loop.80/// - Branch around the original loop if the trip count is less81/// than the unroll factor.82///83static void ConnectProlog(Loop *L, Value *BECount, unsigned Count,84 BasicBlock *PrologExit,85 BasicBlock *OriginalLoopLatchExit,86 BasicBlock *PreHeader, BasicBlock *NewPreHeader,87 ValueToValueMapTy &VMap, DominatorTree *DT,88 LoopInfo *LI, bool PreserveLCSSA,89 ScalarEvolution &SE) {90 // Loop structure should be the following:91 // Preheader92 // PrologHeader93 // ...94 // PrologLatch95 // PrologExit96 // NewPreheader97 // Header98 // ...99 // Latch100 // LatchExit101 BasicBlock *Latch = L->getLoopLatch();102 assert(Latch && "Loop must have a latch");103 BasicBlock *PrologLatch = cast<BasicBlock>(VMap[Latch]);104 105 // Create a PHI node for each outgoing value from the original loop106 // (which means it is an outgoing value from the prolog code too).107 // The new PHI node is inserted in the prolog end basic block.108 // The new PHI node value is added as an operand of a PHI node in either109 // the loop header or the loop exit block.110 for (BasicBlock *Succ : successors(Latch)) {111 for (PHINode &PN : Succ->phis()) {112 // Add a new PHI node to the prolog end block and add the113 // appropriate incoming values.114 // TODO: This code assumes that the PrologExit (or the LatchExit block for115 // prolog loop) contains only one predecessor from the loop, i.e. the116 // PrologLatch. When supporting multiple-exiting block loops, we can have117 // two or more blocks that have the LatchExit as the target in the118 // original loop.119 PHINode *NewPN = PHINode::Create(PN.getType(), 2, PN.getName() + ".unr");120 NewPN->insertBefore(PrologExit->getFirstNonPHIIt());121 // Adding a value to the new PHI node from the original loop preheader.122 // This is the value that skips all the prolog code.123 if (L->contains(&PN)) {124 // Succ is loop header.125 NewPN->addIncoming(PN.getIncomingValueForBlock(NewPreHeader),126 PreHeader);127 } else {128 // Succ is LatchExit.129 NewPN->addIncoming(PoisonValue::get(PN.getType()), PreHeader);130 }131 132 Value *V = PN.getIncomingValueForBlock(Latch);133 if (Instruction *I = dyn_cast<Instruction>(V)) {134 if (L->contains(I)) {135 V = VMap.lookup(I);136 }137 }138 // Adding a value to the new PHI node from the last prolog block139 // that was created.140 NewPN->addIncoming(V, PrologLatch);141 142 // Update the existing PHI node operand with the value from the143 // new PHI node. How this is done depends on if the existing144 // PHI node is in the original loop block, or the exit block.145 if (L->contains(&PN))146 PN.setIncomingValueForBlock(NewPreHeader, NewPN);147 else148 PN.addIncoming(NewPN, PrologExit);149 SE.forgetLcssaPhiWithNewPredecessor(L, &PN);150 }151 }152 153 // Make sure that created prolog loop is in simplified form154 SmallVector<BasicBlock *, 4> PrologExitPreds;155 Loop *PrologLoop = LI->getLoopFor(PrologLatch);156 if (PrologLoop) {157 for (BasicBlock *PredBB : predecessors(PrologExit))158 if (PrologLoop->contains(PredBB))159 PrologExitPreds.push_back(PredBB);160 161 SplitBlockPredecessors(PrologExit, PrologExitPreds, ".unr-lcssa", DT, LI,162 nullptr, PreserveLCSSA);163 }164 165 // Create a branch around the original loop, which is taken if there are no166 // iterations remaining to be executed after running the prologue.167 Instruction *InsertPt = PrologExit->getTerminator();168 IRBuilder<> B(InsertPt);169 170 assert(Count != 0 && "nonsensical Count!");171 172 // If BECount <u (Count - 1) then (BECount + 1) % Count == (BECount + 1)173 // This means %xtraiter is (BECount + 1) and all of the iterations of this174 // loop were executed by the prologue. Note that if BECount <u (Count - 1)175 // then (BECount + 1) cannot unsigned-overflow.176 Value *BrLoopExit =177 B.CreateICmpULT(BECount, ConstantInt::get(BECount->getType(), Count - 1));178 // Split the exit to maintain loop canonicalization guarantees179 SmallVector<BasicBlock *, 4> Preds(predecessors(OriginalLoopLatchExit));180 SplitBlockPredecessors(OriginalLoopLatchExit, Preds, ".unr-lcssa", DT, LI,181 nullptr, PreserveLCSSA);182 // Add the branch to the exit block (around the unrolled loop)183 MDNode *BranchWeights = nullptr;184 if (hasBranchWeightMD(*Latch->getTerminator())) {185 // Assume loop is nearly always entered.186 MDBuilder MDB(B.getContext());187 BranchWeights = MDB.createBranchWeights(UnrolledLoopHeaderWeights);188 }189 B.CreateCondBr(BrLoopExit, OriginalLoopLatchExit, NewPreHeader,190 BranchWeights);191 InsertPt->eraseFromParent();192 if (DT) {193 auto *NewDom = DT->findNearestCommonDominator(OriginalLoopLatchExit,194 PrologExit);195 DT->changeImmediateDominator(OriginalLoopLatchExit, NewDom);196 }197}198 199/// Assume, due to our position in the remainder loop or its guard, anywhere200/// from 0 to \p N more iterations can possibly execute. Among such cases in201/// the original loop (with loop probability \p OriginalLoopProb), what is the202/// probability of executing at least one more iteration?203static BranchProbability204probOfNextInRemainder(BranchProbability OriginalLoopProb, unsigned N) {205 // OriginalLoopProb == 1 would produce a division by zero in the calculation206 // below. The problem is that case indicates an always infinite loop, but a207 // remainder loop cannot be calculated at run time if the original loop is208 // infinite as infinity % UnrollCount is undefined. We then choose209 // probabilities indicating that all remainder loop iterations will always210 // execute.211 //212 // Currently, the remainder loop here is an epilogue, which cannot be reached213 // if the original loop is infinite, so the aforementioned choice is214 // arbitrary.215 //216 // FIXME: Branch weights still need to be fixed in the case of prologues217 // (issue #135812). In that case, the aforementioned choice seems reasonable218 // for the goal of maintaining the original loop's block frequencies. That219 // is, an infinite loop's initial iterations are not skipped, and the prologue220 // loop body might have unique blocks that execute a finite number of times221 // if, for example, the original loop body contains conditionals like i <222 // UnrollCount.223 if (OriginalLoopProb == BranchProbability::getOne())224 return BranchProbability::getOne();225 226 // Each of these variables holds the original loop's probability that the227 // number of iterations it will execute is some m in the specified range.228 BranchProbability ProbOne = OriginalLoopProb; // 1 <= m229 BranchProbability ProbTooMany = ProbOne.pow(N + 1); // N + 1 <= m230 BranchProbability ProbNotTooMany = ProbTooMany.getCompl(); // 0 <= m <= N231 BranchProbability ProbOneNotTooMany = ProbOne - ProbTooMany; // 1 <= m <= N232 return ProbOneNotTooMany / ProbNotTooMany;233}234 235/// Connect the unrolling epilog code to the original loop.236/// The unrolling epilog code contains code to execute the237/// 'extra' iterations if the run-time trip count modulo the238/// unroll count is non-zero.239///240/// This function performs the following:241/// - Update PHI nodes at the epilog loop exit242/// - Create PHI nodes at the unrolling loop exit and epilog preheader to243/// combine values that exit the unrolling loop code and jump around it.244/// - Update PHI operands in the epilog loop by the new PHI nodes245/// - At the unrolling loop exit, branch around the epilog loop if extra iters246// (ModVal) is zero.247/// - At the epilog preheader, add an llvm.assume call that extra iters is248/// non-zero. If the unrolling loop exit is the predecessor, the above new249/// branch guarantees that assumption. If the unrolling loop preheader is the250/// predecessor, then the required first iteration from the original loop has251/// yet to be executed, so it must be executed in the epilog loop. If we252/// later unroll the epilog loop, that llvm.assume call somehow enables253/// ScalarEvolution to compute a epilog loop maximum trip count, which enables254/// eliminating the branch at the end of the final unrolled epilog iteration.255///256static void ConnectEpilog(Loop *L, Value *ModVal, BasicBlock *NewExit,257 BasicBlock *Exit, BasicBlock *PreHeader,258 BasicBlock *EpilogPreHeader, BasicBlock *NewPreHeader,259 ValueToValueMapTy &VMap, DominatorTree *DT,260 LoopInfo *LI, bool PreserveLCSSA, ScalarEvolution &SE,261 unsigned Count, AssumptionCache &AC,262 BranchProbability OriginalLoopProb) {263 BasicBlock *Latch = L->getLoopLatch();264 assert(Latch && "Loop must have a latch");265 BasicBlock *EpilogLatch = cast<BasicBlock>(VMap[Latch]);266 267 // Loop structure should be the following:268 //269 // PreHeader270 // NewPreHeader271 // Header272 // ...273 // Latch274 // NewExit (PN)275 // EpilogPreHeader276 // EpilogHeader277 // ...278 // EpilogLatch279 // Exit (EpilogPN)280 281 // Update PHI nodes at Exit.282 for (PHINode &PN : NewExit->phis()) {283 // PN should be used in another PHI located in Exit block as284 // Exit was split by SplitBlockPredecessors into Exit and NewExit285 // Basically it should look like:286 // NewExit:287 // PN = PHI [I, Latch]288 // ...289 // Exit:290 // EpilogPN = PHI [PN, EpilogPreHeader], [X, Exit2], [Y, Exit2.epil]291 //292 // Exits from non-latch blocks point to the original exit block and the293 // epilogue edges have already been added.294 //295 // There is EpilogPreHeader incoming block instead of NewExit as296 // NewExit was split 1 more time to get EpilogPreHeader.297 assert(PN.hasOneUse() && "The phi should have 1 use");298 PHINode *EpilogPN = cast<PHINode>(PN.use_begin()->getUser());299 assert(EpilogPN->getParent() == Exit && "EpilogPN should be in Exit block");300 301 Value *V = PN.getIncomingValueForBlock(Latch);302 Instruction *I = dyn_cast<Instruction>(V);303 if (I && L->contains(I))304 // If value comes from an instruction in the loop add VMap value.305 V = VMap.lookup(I);306 // For the instruction out of the loop, constant or undefined value307 // insert value itself.308 EpilogPN->addIncoming(V, EpilogLatch);309 310 assert(EpilogPN->getBasicBlockIndex(EpilogPreHeader) >= 0 &&311 "EpilogPN should have EpilogPreHeader incoming block");312 // Change EpilogPreHeader incoming block to NewExit.313 EpilogPN->setIncomingBlock(EpilogPN->getBasicBlockIndex(EpilogPreHeader),314 NewExit);315 // Now PHIs should look like:316 // NewExit:317 // PN = PHI [I, Latch]318 // ...319 // Exit:320 // EpilogPN = PHI [PN, NewExit], [VMap[I], EpilogLatch]321 }322 323 // Create PHI nodes at NewExit (from the unrolling loop Latch) and at324 // EpilogPreHeader (from PreHeader and NewExit). Update corresponding PHI325 // nodes in epilog loop.326 for (BasicBlock *Succ : successors(Latch)) {327 // Skip this as we already updated phis in exit blocks.328 if (!L->contains(Succ))329 continue;330 331 // Succ here appears to always be just L->getHeader(). Otherwise, how do we332 // know its corresponding epilog block (from VMap) is EpilogHeader and thus333 // EpilogPreHeader is the right incoming block for VPN, as set below?334 // TODO: Can we thus avoid the enclosing loop over successors?335 assert(Succ == L->getHeader() &&336 "Expect the only in-loop successor of latch to be the loop header");337 338 for (PHINode &PN : Succ->phis()) {339 // Add new PHI nodes to the loop exit block.340 PHINode *NewPN0 = PHINode::Create(PN.getType(), /*NumReservedValues=*/1,341 PN.getName() + ".unr");342 NewPN0->insertBefore(NewExit->getFirstNonPHIIt());343 // Add value to the new PHI node from the unrolling loop latch.344 NewPN0->addIncoming(PN.getIncomingValueForBlock(Latch), Latch);345 346 // Add new PHI nodes to EpilogPreHeader.347 PHINode *NewPN1 = PHINode::Create(PN.getType(), /*NumReservedValues=*/2,348 PN.getName() + ".epil.init");349 NewPN1->insertBefore(EpilogPreHeader->getFirstNonPHIIt());350 // Add value to the new PHI node from the unrolling loop preheader.351 NewPN1->addIncoming(PN.getIncomingValueForBlock(NewPreHeader), PreHeader);352 // Add value to the new PHI node from the epilog loop guard.353 NewPN1->addIncoming(NewPN0, NewExit);354 355 // Update the existing PHI node operand with the value from the new PHI356 // node. Corresponding instruction in epilog loop should be PHI.357 PHINode *VPN = cast<PHINode>(VMap[&PN]);358 VPN->setIncomingValueForBlock(EpilogPreHeader, NewPN1);359 }360 }361 362 // In NewExit, branch around the epilog loop if no extra iters.363 Instruction *InsertPt = NewExit->getTerminator();364 IRBuilder<> B(InsertPt);365 Value *BrLoopExit = B.CreateIsNotNull(ModVal, "lcmp.mod");366 assert(Exit && "Loop must have a single exit block only");367 // Split the epilogue exit to maintain loop canonicalization guarantees368 SmallVector<BasicBlock*, 4> Preds(predecessors(Exit));369 SplitBlockPredecessors(Exit, Preds, ".epilog-lcssa", DT, LI, nullptr,370 PreserveLCSSA);371 // Add the branch to the exit block (around the epilog loop)372 MDNode *BranchWeights = nullptr;373 if (OriginalLoopProb.isUnknown() &&374 hasBranchWeightMD(*Latch->getTerminator())) {375 // Assume equal distribution in interval [0, Count).376 MDBuilder MDB(B.getContext());377 BranchWeights = MDB.createBranchWeights(1, Count - 1);378 }379 BranchInst *RemainderLoopGuard =380 B.CreateCondBr(BrLoopExit, EpilogPreHeader, Exit, BranchWeights);381 if (!OriginalLoopProb.isUnknown()) {382 setBranchProbability(RemainderLoopGuard,383 probOfNextInRemainder(OriginalLoopProb, Count - 1),384 /*ForFirstTarget=*/true);385 }386 InsertPt->eraseFromParent();387 if (DT) {388 auto *NewDom = DT->findNearestCommonDominator(Exit, NewExit);389 DT->changeImmediateDominator(Exit, NewDom);390 }391 392 // In EpilogPreHeader, assume extra iters is non-zero.393 IRBuilder<> B2(EpilogPreHeader, EpilogPreHeader->getFirstNonPHIIt());394 Value *ModIsNotNull = B2.CreateIsNotNull(ModVal, "lcmp.mod");395 AssumeInst *AI = cast<AssumeInst>(B2.CreateAssumption(ModIsNotNull));396 AC.registerAssumption(AI);397}398 399/// Create a clone of the blocks in a loop and connect them together. A new400/// loop will be created including all cloned blocks, and the iterator of the401/// new loop switched to count NewIter down to 0.402/// The cloned blocks should be inserted between InsertTop and InsertBot.403/// InsertTop should be new preheader, InsertBot new loop exit.404/// Returns the new cloned loop that is created.405static Loop *CloneLoopBlocks(Loop *L, Value *NewIter,406 const bool UseEpilogRemainder,407 const bool UnrollRemainder, BasicBlock *InsertTop,408 BasicBlock *InsertBot, BasicBlock *Preheader,409 std::vector<BasicBlock *> &NewBlocks,410 LoopBlocksDFS &LoopBlocks, ValueToValueMapTy &VMap,411 DominatorTree *DT, LoopInfo *LI, unsigned Count,412 std::optional<unsigned> OriginalTripCount,413 BranchProbability OriginalLoopProb) {414 StringRef suffix = UseEpilogRemainder ? "epil" : "prol";415 BasicBlock *Header = L->getHeader();416 BasicBlock *Latch = L->getLoopLatch();417 Function *F = Header->getParent();418 LoopBlocksDFS::RPOIterator BlockBegin = LoopBlocks.beginRPO();419 LoopBlocksDFS::RPOIterator BlockEnd = LoopBlocks.endRPO();420 Loop *ParentLoop = L->getParentLoop();421 NewLoopsMap NewLoops;422 NewLoops[ParentLoop] = ParentLoop;423 424 // For each block in the original loop, create a new copy,425 // and update the value map with the newly created values.426 for (LoopBlocksDFS::RPOIterator BB = BlockBegin; BB != BlockEnd; ++BB) {427 BasicBlock *NewBB = CloneBasicBlock(*BB, VMap, "." + suffix, F);428 NewBlocks.push_back(NewBB);429 430 addClonedBlockToLoopInfo(*BB, NewBB, LI, NewLoops);431 432 VMap[*BB] = NewBB;433 if (Header == *BB) {434 // For the first block, add a CFG connection to this newly435 // created block.436 InsertTop->getTerminator()->setSuccessor(0, NewBB);437 }438 439 if (DT) {440 if (Header == *BB) {441 // The header is dominated by the preheader.442 DT->addNewBlock(NewBB, InsertTop);443 } else {444 // Copy information from original loop to unrolled loop.445 BasicBlock *IDomBB = DT->getNode(*BB)->getIDom()->getBlock();446 DT->addNewBlock(NewBB, cast<BasicBlock>(VMap[IDomBB]));447 }448 }449 450 if (Latch == *BB) {451 // For the last block, create a loop back to cloned head.452 VMap.erase((*BB)->getTerminator());453 // Use an incrementing IV. Pre-incr/post-incr is backedge/trip count.454 // Subtle: NewIter can be 0 if we wrapped when computing the trip count,455 // thus we must compare the post-increment (wrapping) value.456 BasicBlock *FirstLoopBB = cast<BasicBlock>(VMap[Header]);457 BranchInst *LatchBR = cast<BranchInst>(NewBB->getTerminator());458 IRBuilder<> Builder(LatchBR);459 PHINode *NewIdx =460 PHINode::Create(NewIter->getType(), 2, suffix + ".iter");461 NewIdx->insertBefore(FirstLoopBB->getFirstNonPHIIt());462 auto *Zero = ConstantInt::get(NewIdx->getType(), 0);463 auto *One = ConstantInt::get(NewIdx->getType(), 1);464 Value *IdxNext =465 Builder.CreateAdd(NewIdx, One, NewIdx->getName() + ".next");466 Value *IdxCmp = Builder.CreateICmpNE(IdxNext, NewIter, NewIdx->getName() + ".cmp");467 MDNode *BranchWeights = nullptr;468 if ((OriginalLoopProb.isUnknown() || !UseEpilogRemainder) &&469 hasBranchWeightMD(*LatchBR)) {470 uint32_t ExitWeight;471 uint32_t BackEdgeWeight;472 if (Count >= 3) {473 // Note: We do not enter this loop for zero-remainders. The check474 // is at the end of the loop. We assume equal distribution between475 // possible remainders in [1, Count).476 ExitWeight = 1;477 BackEdgeWeight = (Count - 2) / 2;478 } else {479 // Unnecessary backedge, should never be taken. The conditional480 // jump should be optimized away later.481 ExitWeight = 1;482 BackEdgeWeight = 0;483 }484 MDBuilder MDB(Builder.getContext());485 BranchWeights = MDB.createBranchWeights(BackEdgeWeight, ExitWeight);486 }487 BranchInst *RemainderLoopLatch =488 Builder.CreateCondBr(IdxCmp, FirstLoopBB, InsertBot, BranchWeights);489 if (!OriginalLoopProb.isUnknown() && UseEpilogRemainder) {490 // Compute the total frequency of the original loop body from the491 // remainder iterations. Once we've reached them, the first of them492 // always executes, so its frequency and probability are 1.493 double FreqRemIters = 1;494 if (Count > 2) {495 BranchProbability ProbReaching = BranchProbability::getOne();496 for (unsigned N = Count - 2; N >= 1; --N) {497 ProbReaching *= probOfNextInRemainder(OriginalLoopProb, N);498 FreqRemIters += ProbReaching.toDouble();499 }500 }501 // Solve for the loop probability that would produce that frequency.502 // Sum(i=0..inf)(Prob^i) = 1/(1-Prob) = FreqRemIters.503 BranchProbability Prob =504 BranchProbability::getBranchProbability(1 - 1 / FreqRemIters);505 setBranchProbability(RemainderLoopLatch, Prob, /*ForFirstTarget=*/true);506 }507 NewIdx->addIncoming(Zero, InsertTop);508 NewIdx->addIncoming(IdxNext, NewBB);509 LatchBR->eraseFromParent();510 }511 }512 513 // Change the incoming values to the ones defined in the preheader or514 // cloned loop.515 for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {516 PHINode *NewPHI = cast<PHINode>(VMap[&*I]);517 unsigned idx = NewPHI->getBasicBlockIndex(Preheader);518 NewPHI->setIncomingBlock(idx, InsertTop);519 BasicBlock *NewLatch = cast<BasicBlock>(VMap[Latch]);520 idx = NewPHI->getBasicBlockIndex(Latch);521 Value *InVal = NewPHI->getIncomingValue(idx);522 NewPHI->setIncomingBlock(idx, NewLatch);523 if (Value *V = VMap.lookup(InVal))524 NewPHI->setIncomingValue(idx, V);525 }526 527 Loop *NewLoop = NewLoops[L];528 assert(NewLoop && "L should have been cloned");529 530 if (OriginalTripCount && UseEpilogRemainder)531 setLoopEstimatedTripCount(NewLoop, *OriginalTripCount % Count);532 533 // Add unroll disable metadata to disable future unrolling for this loop.534 if (!UnrollRemainder)535 NewLoop->setLoopAlreadyUnrolled();536 return NewLoop;537}538 539/// Returns true if we can profitably unroll the multi-exit loop L. Currently,540/// we return true only if UnrollRuntimeMultiExit is set to true.541static bool canProfitablyRuntimeUnrollMultiExitLoop(542 Loop *L, SmallVectorImpl<BasicBlock *> &OtherExits, BasicBlock *LatchExit,543 bool UseEpilogRemainder) {544 545 // The main pain point with multi-exit loop unrolling is that once unrolled,546 // we will not be able to merge all blocks into a straight line code.547 // There are branches within the unrolled loop that go to the OtherExits.548 // The second point is the increase in code size, but this is true549 // irrespective of multiple exits.550 551 // Note: Both the heuristics below are coarse grained. We are essentially552 // enabling unrolling of loops that have a single side exit other than the553 // normal LatchExit (i.e. exiting into a deoptimize block).554 // The heuristics considered are:555 // 1. low number of branches in the unrolled version.556 // 2. high predictability of these extra branches.557 // We avoid unrolling loops that have more than two exiting blocks. This558 // limits the total number of branches in the unrolled loop to be atmost559 // the unroll factor (since one of the exiting blocks is the latch block).560 SmallVector<BasicBlock*, 4> ExitingBlocks;561 L->getExitingBlocks(ExitingBlocks);562 if (ExitingBlocks.size() > 2)563 return false;564 565 // Allow unrolling of loops with no non latch exit blocks.566 if (OtherExits.size() == 0)567 return true;568 569 // The second heuristic is that L has one exit other than the latchexit and570 // that exit is a deoptimize block. We know that deoptimize blocks are rarely571 // taken, which also implies the branch leading to the deoptimize block is572 // highly predictable. When UnrollRuntimeOtherExitPredictable is specified, we573 // assume the other exit branch is predictable even if it has no deoptimize574 // call.575 return (OtherExits.size() == 1 &&576 (UnrollRuntimeOtherExitPredictable ||577 OtherExits[0]->getPostdominatingDeoptimizeCall()));578 // TODO: These can be fine-tuned further to consider code size or deopt states579 // that are captured by the deoptimize exit block.580 // Also, we can extend this to support more cases, if we actually581 // know of kinds of multiexit loops that would benefit from unrolling.582}583 584/// Calculate ModVal = (BECount + 1) % Count on the abstract integer domain585/// accounting for the possibility of unsigned overflow in the 2s complement586/// domain. Preconditions:587/// 1) TripCount = BECount + 1 (allowing overflow)588/// 2) Log2(Count) <= BitWidth(BECount)589static Value *CreateTripRemainder(IRBuilder<> &B, Value *BECount,590 Value *TripCount, unsigned Count) {591 // Note that TripCount is BECount + 1.592 if (isPowerOf2_32(Count))593 // If the expression is zero, then either:594 // 1. There are no iterations to be run in the prolog/epilog loop.595 // OR596 // 2. The addition computing TripCount overflowed.597 //598 // If (2) is true, we know that TripCount really is (1 << BEWidth) and so599 // the number of iterations that remain to be run in the original loop is a600 // multiple Count == (1 << Log2(Count)) because Log2(Count) <= BEWidth (a601 // precondition of this method).602 return B.CreateAnd(TripCount, Count - 1, "xtraiter");603 604 // As (BECount + 1) can potentially unsigned overflow we count605 // (BECount % Count) + 1 which is overflow safe as BECount % Count < Count.606 Constant *CountC = ConstantInt::get(BECount->getType(), Count);607 Value *ModValTmp = B.CreateURem(BECount, CountC);608 Value *ModValAdd = B.CreateAdd(ModValTmp,609 ConstantInt::get(ModValTmp->getType(), 1));610 // At that point (BECount % Count) + 1 could be equal to Count.611 // To handle this case we need to take mod by Count one more time.612 return B.CreateURem(ModValAdd, CountC, "xtraiter");613}614 615 616/// Insert code in the prolog/epilog code when unrolling a loop with a617/// run-time trip-count.618///619/// This method assumes that the loop unroll factor is total number620/// of loop bodies in the loop after unrolling. (Some folks refer621/// to the unroll factor as the number of *extra* copies added).622/// We assume also that the loop unroll factor is a power-of-two. So, after623/// unrolling the loop, the number of loop bodies executed is 2,624/// 4, 8, etc. Note - LLVM converts the if-then-sequence to a switch625/// instruction in SimplifyCFG.cpp. Then, the backend decides how code for626/// the switch instruction is generated.627///628/// ***Prolog case***629/// extraiters = tripcount % loopfactor630/// if (extraiters == 0) jump Loop:631/// else jump Prol:632/// Prol: LoopBody;633/// extraiters -= 1 // Omitted if unroll factor is 2.634/// if (extraiters != 0) jump Prol: // Omitted if unroll factor is 2.635/// if (tripcount < loopfactor) jump End:636/// Loop:637/// ...638/// End:639///640/// ***Epilog case***641/// extraiters = tripcount % loopfactor642/// if (tripcount < loopfactor) jump LoopExit:643/// unroll_iters = tripcount - extraiters644/// Loop: LoopBody; (executes unroll_iter times);645/// unroll_iter -= 1646/// if (unroll_iter != 0) jump Loop:647/// LoopExit:648/// if (extraiters == 0) jump EpilExit:649/// Epil: LoopBody; (executes extraiters times)650/// extraiters -= 1 // Omitted if unroll factor is 2.651/// if (extraiters != 0) jump Epil: // Omitted if unroll factor is 2.652/// EpilExit:653 654bool llvm::UnrollRuntimeLoopRemainder(655 Loop *L, unsigned Count, bool AllowExpensiveTripCount,656 bool UseEpilogRemainder, bool UnrollRemainder, bool ForgetAllSCEV,657 LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC,658 const TargetTransformInfo *TTI, bool PreserveLCSSA,659 unsigned SCEVExpansionBudget, bool RuntimeUnrollMultiExit,660 Loop **ResultLoop, std::optional<unsigned> OriginalTripCount,661 BranchProbability OriginalLoopProb) {662 LLVM_DEBUG(dbgs() << "Trying runtime unrolling on Loop: \n");663 LLVM_DEBUG(L->dump());664 LLVM_DEBUG(UseEpilogRemainder ? dbgs() << "Using epilog remainder.\n"665 : dbgs() << "Using prolog remainder.\n");666 667 // Make sure the loop is in canonical form.668 if (!L->isLoopSimplifyForm()) {669 LLVM_DEBUG(dbgs() << "Not in simplify form!\n");670 return false;671 }672 673 // Guaranteed by LoopSimplifyForm.674 BasicBlock *Latch = L->getLoopLatch();675 BasicBlock *Header = L->getHeader();676 677 BranchInst *LatchBR = cast<BranchInst>(Latch->getTerminator());678 679 if (!LatchBR || LatchBR->isUnconditional()) {680 // The loop-rotate pass can be helpful to avoid this in many cases.681 LLVM_DEBUG(682 dbgs()683 << "Loop latch not terminated by a conditional branch.\n");684 return false;685 }686 687 unsigned ExitIndex = LatchBR->getSuccessor(0) == Header ? 1 : 0;688 BasicBlock *LatchExit = LatchBR->getSuccessor(ExitIndex);689 690 if (L->contains(LatchExit)) {691 // Cloning the loop basic blocks (`CloneLoopBlocks`) requires that one of the692 // targets of the Latch be an exit block out of the loop.693 LLVM_DEBUG(694 dbgs()695 << "One of the loop latch successors must be the exit block.\n");696 return false;697 }698 699 // These are exit blocks other than the target of the latch exiting block.700 SmallVector<BasicBlock *, 4> OtherExits;701 L->getUniqueNonLatchExitBlocks(OtherExits);702 // Support only single exit and exiting block unless multi-exit loop703 // unrolling is enabled.704 if (!L->getExitingBlock() || OtherExits.size()) {705 // We rely on LCSSA form being preserved when the exit blocks are transformed.706 // (Note that only an off-by-default mode of the old PM disables PreserveLCCA.)707 if (!PreserveLCSSA)708 return false;709 710 // Priority goes to UnrollRuntimeMultiExit if it's supplied.711 if (UnrollRuntimeMultiExit.getNumOccurrences()) {712 if (!UnrollRuntimeMultiExit)713 return false;714 } else {715 // Otherwise perform multi-exit unrolling, if either the target indicates716 // it is profitable or the general profitability heuristics apply.717 if (!RuntimeUnrollMultiExit &&718 !canProfitablyRuntimeUnrollMultiExitLoop(L, OtherExits, LatchExit,719 UseEpilogRemainder)) {720 LLVM_DEBUG(dbgs() << "Multiple exit/exiting blocks in loop and "721 "multi-exit unrolling not enabled!\n");722 return false;723 }724 }725 }726 // Use Scalar Evolution to compute the trip count. This allows more loops to727 // be unrolled than relying on induction var simplification.728 if (!SE)729 return false;730 731 // Only unroll loops with a computable trip count.732 // We calculate the backedge count by using getExitCount on the Latch block,733 // which is proven to be the only exiting block in this loop. This is same as734 // calculating getBackedgeTakenCount on the loop (which computes SCEV for all735 // exiting blocks).736 const SCEV *BECountSC = SE->getExitCount(L, Latch);737 if (isa<SCEVCouldNotCompute>(BECountSC)) {738 LLVM_DEBUG(dbgs() << "Could not compute exit block SCEV\n");739 return false;740 }741 742 unsigned BEWidth = cast<IntegerType>(BECountSC->getType())->getBitWidth();743 744 // Add 1 since the backedge count doesn't include the first loop iteration.745 // (Note that overflow can occur, this is handled explicitly below)746 const SCEV *TripCountSC =747 SE->getAddExpr(BECountSC, SE->getConstant(BECountSC->getType(), 1));748 if (isa<SCEVCouldNotCompute>(TripCountSC)) {749 LLVM_DEBUG(dbgs() << "Could not compute trip count SCEV.\n");750 return false;751 }752 753 BasicBlock *PreHeader = L->getLoopPreheader();754 BranchInst *PreHeaderBR = cast<BranchInst>(PreHeader->getTerminator());755 const DataLayout &DL = Header->getDataLayout();756 SCEVExpander Expander(*SE, DL, "loop-unroll");757 if (!AllowExpensiveTripCount &&758 Expander.isHighCostExpansion(TripCountSC, L, SCEVExpansionBudget, TTI,759 PreHeaderBR)) {760 LLVM_DEBUG(dbgs() << "High cost for expanding trip count scev!\n");761 return false;762 }763 764 // This constraint lets us deal with an overflowing trip count easily; see the765 // comment on ModVal below.766 if (Log2_32(Count) > BEWidth) {767 LLVM_DEBUG(768 dbgs()769 << "Count failed constraint on overflow trip count calculation.\n");770 return false;771 }772 773 // Loop structure is the following:774 //775 // PreHeader776 // Header777 // ...778 // Latch779 // LatchExit780 781 BasicBlock *NewPreHeader;782 BasicBlock *NewExit = nullptr;783 BasicBlock *PrologExit = nullptr;784 BasicBlock *EpilogPreHeader = nullptr;785 BasicBlock *PrologPreHeader = nullptr;786 787 if (UseEpilogRemainder) {788 // If epilog remainder789 // Split PreHeader to insert a branch around loop for unrolling.790 NewPreHeader = SplitBlock(PreHeader, PreHeader->getTerminator(), DT, LI);791 NewPreHeader->setName(PreHeader->getName() + ".new");792 // Split LatchExit to create phi nodes from branch above.793 NewExit = SplitBlockPredecessors(LatchExit, {Latch}, ".unr-lcssa", DT, LI,794 nullptr, PreserveLCSSA);795 // NewExit gets its DebugLoc from LatchExit, which is not part of the796 // original Loop.797 // Fix this by setting Loop's DebugLoc to NewExit.798 auto *NewExitTerminator = NewExit->getTerminator();799 NewExitTerminator->setDebugLoc(Header->getTerminator()->getDebugLoc());800 // Split NewExit to insert epilog remainder loop.801 EpilogPreHeader = SplitBlock(NewExit, NewExitTerminator, DT, LI);802 EpilogPreHeader->setName(Header->getName() + ".epil.preheader");803 804 // If the latch exits from multiple level of nested loops, then805 // by assumption there must be another loop exit which branches to the806 // outer loop and we must adjust the loop for the newly inserted blocks807 // to account for the fact that our epilogue is still in the same outer808 // loop. Note that this leaves loopinfo temporarily out of sync with the809 // CFG until the actual epilogue loop is inserted.810 if (auto *ParentL = L->getParentLoop())811 if (LI->getLoopFor(LatchExit) != ParentL) {812 LI->removeBlock(NewExit);813 ParentL->addBasicBlockToLoop(NewExit, *LI);814 LI->removeBlock(EpilogPreHeader);815 ParentL->addBasicBlockToLoop(EpilogPreHeader, *LI);816 }817 818 } else {819 // If prolog remainder820 // Split the original preheader twice to insert prolog remainder loop821 PrologPreHeader = SplitEdge(PreHeader, Header, DT, LI);822 PrologPreHeader->setName(Header->getName() + ".prol.preheader");823 PrologExit = SplitBlock(PrologPreHeader, PrologPreHeader->getTerminator(),824 DT, LI);825 PrologExit->setName(Header->getName() + ".prol.loopexit");826 // Split PrologExit to get NewPreHeader.827 NewPreHeader = SplitBlock(PrologExit, PrologExit->getTerminator(), DT, LI);828 NewPreHeader->setName(PreHeader->getName() + ".new");829 }830 // Loop structure should be the following:831 // Epilog Prolog832 //833 // PreHeader PreHeader834 // *NewPreHeader *PrologPreHeader835 // Header *PrologExit836 // ... *NewPreHeader837 // Latch Header838 // *NewExit ...839 // *EpilogPreHeader Latch840 // LatchExit LatchExit841 842 // Calculate conditions for branch around loop for unrolling843 // in epilog case and around prolog remainder loop in prolog case.844 // Compute the number of extra iterations required, which is:845 // extra iterations = run-time trip count % loop unroll factor846 PreHeaderBR = cast<BranchInst>(PreHeader->getTerminator());847 IRBuilder<> B(PreHeaderBR);848 Value *TripCount = Expander.expandCodeFor(TripCountSC, TripCountSC->getType(),849 PreHeaderBR);850 Value *BECount;851 // If there are other exits before the latch, that may cause the latch exit852 // branch to never be executed, and the latch exit count may be poison.853 // In this case, freeze the TripCount and base BECount on the frozen854 // TripCount. We will introduce two branches using these values, and it's855 // important that they see a consistent value (which would not be guaranteed856 // if were frozen independently.)857 if ((!OtherExits.empty() || !SE->loopHasNoAbnormalExits(L)) &&858 !isGuaranteedNotToBeUndefOrPoison(TripCount, AC, PreHeaderBR, DT)) {859 TripCount = B.CreateFreeze(TripCount);860 BECount =861 B.CreateAdd(TripCount, Constant::getAllOnesValue(TripCount->getType()));862 } else {863 // If we don't need to freeze, use SCEVExpander for BECount as well, to864 // allow slightly better value reuse.865 BECount =866 Expander.expandCodeFor(BECountSC, BECountSC->getType(), PreHeaderBR);867 }868 869 Value * const ModVal = CreateTripRemainder(B, BECount, TripCount, Count);870 871 Value *BranchVal =872 UseEpilogRemainder ? B.CreateICmpULT(BECount,873 ConstantInt::get(BECount->getType(),874 Count - 1)) :875 B.CreateIsNotNull(ModVal, "lcmp.mod");876 BasicBlock *RemainderLoop =877 UseEpilogRemainder ? EpilogPreHeader : PrologPreHeader;878 BasicBlock *UnrollingLoop = UseEpilogRemainder ? NewPreHeader : PrologExit;879 // Branch to either remainder (extra iterations) loop or unrolling loop.880 MDNode *BranchWeights = nullptr;881 if ((OriginalLoopProb.isUnknown() || !UseEpilogRemainder) &&882 hasBranchWeightMD(*Latch->getTerminator())) {883 // Assume loop is nearly always entered.884 MDBuilder MDB(B.getContext());885 BranchWeights = MDB.createBranchWeights(EpilogHeaderWeights);886 }887 BranchInst *UnrollingLoopGuard =888 B.CreateCondBr(BranchVal, RemainderLoop, UnrollingLoop, BranchWeights);889 if (!OriginalLoopProb.isUnknown() && UseEpilogRemainder) {890 // The original loop's first iteration always happens. Compute the891 // probability of the original loop executing Count-1 iterations after that892 // to complete the first iteration of the unrolled loop.893 BranchProbability ProbOne = OriginalLoopProb;894 BranchProbability ProbRest = ProbOne.pow(Count - 1);895 setBranchProbability(UnrollingLoopGuard, ProbRest,896 /*ForFirstTarget=*/false);897 }898 PreHeaderBR->eraseFromParent();899 if (DT) {900 if (UseEpilogRemainder)901 DT->changeImmediateDominator(EpilogPreHeader, PreHeader);902 else903 DT->changeImmediateDominator(PrologExit, PreHeader);904 }905 Function *F = Header->getParent();906 // Get an ordered list of blocks in the loop to help with the ordering of the907 // cloned blocks in the prolog/epilog code908 LoopBlocksDFS LoopBlocks(L);909 LoopBlocks.perform(LI);910 911 //912 // For each extra loop iteration, create a copy of the loop's basic blocks913 // and generate a condition that branches to the copy depending on the914 // number of 'left over' iterations.915 //916 std::vector<BasicBlock *> NewBlocks;917 ValueToValueMapTy VMap;918 919 // Clone all the basic blocks in the loop. If Count is 2, we don't clone920 // the loop, otherwise we create a cloned loop to execute the extra921 // iterations. This function adds the appropriate CFG connections.922 BasicBlock *InsertBot = UseEpilogRemainder ? LatchExit : PrologExit;923 BasicBlock *InsertTop = UseEpilogRemainder ? EpilogPreHeader : PrologPreHeader;924 Loop *remainderLoop =925 CloneLoopBlocks(L, ModVal, UseEpilogRemainder, UnrollRemainder, InsertTop,926 InsertBot, NewPreHeader, NewBlocks, LoopBlocks, VMap, DT,927 LI, Count, OriginalTripCount, OriginalLoopProb);928 929 // Insert the cloned blocks into the function.930 F->splice(InsertBot->getIterator(), F, NewBlocks[0]->getIterator(), F->end());931 932 // Now the loop blocks are cloned and the other exiting blocks from the933 // remainder are connected to the original Loop's exit blocks. The remaining934 // work is to update the phi nodes in the original loop, and take in the935 // values from the cloned region.936 for (auto *BB : OtherExits) {937 // Given we preserve LCSSA form, we know that the values used outside the938 // loop will be used through these phi nodes at the exit blocks that are939 // transformed below.940 for (PHINode &PN : BB->phis()) {941 unsigned oldNumOperands = PN.getNumIncomingValues();942 // Add the incoming values from the remainder code to the end of the phi943 // node.944 for (unsigned i = 0; i < oldNumOperands; i++){945 auto *PredBB =PN.getIncomingBlock(i);946 if (PredBB == Latch)947 // The latch exit is handled separately, see connectX948 continue;949 if (!L->contains(PredBB))950 // Even if we had dedicated exits, the code above inserted an951 // extra branch which can reach the latch exit.952 continue;953 954 auto *V = PN.getIncomingValue(i);955 if (Instruction *I = dyn_cast<Instruction>(V))956 if (L->contains(I))957 V = VMap.lookup(I);958 PN.addIncoming(V, cast<BasicBlock>(VMap[PredBB]));959 }960 }961#if defined(EXPENSIVE_CHECKS) && !defined(NDEBUG)962 for (BasicBlock *SuccBB : successors(BB)) {963 assert(!(llvm::is_contained(OtherExits, SuccBB) || SuccBB == LatchExit) &&964 "Breaks the definition of dedicated exits!");965 }966#endif967 }968 969 // Update the immediate dominator of the exit blocks and blocks that are970 // reachable from the exit blocks. This is needed because we now have paths971 // from both the original loop and the remainder code reaching the exit972 // blocks. While the IDom of these exit blocks were from the original loop,973 // now the IDom is the preheader (which decides whether the original loop or974 // remainder code should run) unless the block still has just the original975 // predecessor (such as NewExit in the case of an epilog remainder).976 if (DT && !L->getExitingBlock()) {977 SmallVector<BasicBlock *, 16> ChildrenToUpdate;978 // NB! We have to examine the dom children of all loop blocks, not just979 // those which are the IDom of the exit blocks. This is because blocks980 // reachable from the exit blocks can have their IDom as the nearest common981 // dominator of the exit blocks.982 for (auto *BB : L->blocks()) {983 auto *DomNodeBB = DT->getNode(BB);984 for (auto *DomChild : DomNodeBB->children()) {985 auto *DomChildBB = DomChild->getBlock();986 if (!L->contains(LI->getLoopFor(DomChildBB)) &&987 DomChildBB->getUniquePredecessor() != BB)988 ChildrenToUpdate.push_back(DomChildBB);989 }990 }991 for (auto *BB : ChildrenToUpdate)992 DT->changeImmediateDominator(BB, PreHeader);993 }994 995 // Loop structure should be the following:996 // Epilog Prolog997 //998 // PreHeader PreHeader999 // NewPreHeader PrologPreHeader1000 // Header PrologHeader1001 // ... ...1002 // Latch PrologLatch1003 // NewExit PrologExit1004 // EpilogPreHeader NewPreHeader1005 // EpilogHeader Header1006 // ... ...1007 // EpilogLatch Latch1008 // LatchExit LatchExit1009 1010 // Rewrite the cloned instruction operands to use the values created when the1011 // clone is created.1012 for (BasicBlock *BB : NewBlocks) {1013 Module *M = BB->getModule();1014 for (Instruction &I : *BB) {1015 RemapInstruction(&I, VMap,1016 RF_NoModuleLevelChanges | RF_IgnoreMissingLocals);1017 RemapDbgRecordRange(M, I.getDbgRecordRange(), VMap,1018 RF_NoModuleLevelChanges | RF_IgnoreMissingLocals);1019 }1020 }1021 1022 if (UseEpilogRemainder) {1023 // Connect the epilog code to the original loop and update the1024 // PHI functions.1025 ConnectEpilog(L, ModVal, NewExit, LatchExit, PreHeader, EpilogPreHeader,1026 NewPreHeader, VMap, DT, LI, PreserveLCSSA, *SE, Count, *AC,1027 OriginalLoopProb);1028 1029 // Update counter in loop for unrolling.1030 // Use an incrementing IV. Pre-incr/post-incr is backedge/trip count.1031 // Subtle: TestVal can be 0 if we wrapped when computing the trip count,1032 // thus we must compare the post-increment (wrapping) value.1033 IRBuilder<> B2(NewPreHeader->getTerminator());1034 Value *TestVal = B2.CreateSub(TripCount, ModVal, "unroll_iter");1035 BranchInst *LatchBR = cast<BranchInst>(Latch->getTerminator());1036 PHINode *NewIdx = PHINode::Create(TestVal->getType(), 2, "niter");1037 NewIdx->insertBefore(Header->getFirstNonPHIIt());1038 B2.SetInsertPoint(LatchBR);1039 auto *Zero = ConstantInt::get(NewIdx->getType(), 0);1040 auto *One = ConstantInt::get(NewIdx->getType(), 1);1041 Value *IdxNext = B2.CreateAdd(NewIdx, One, NewIdx->getName() + ".next");1042 auto Pred = LatchBR->getSuccessor(0) == Header ? ICmpInst::ICMP_NE : ICmpInst::ICMP_EQ;1043 Value *IdxCmp = B2.CreateICmp(Pred, IdxNext, TestVal, NewIdx->getName() + ".ncmp");1044 NewIdx->addIncoming(Zero, NewPreHeader);1045 NewIdx->addIncoming(IdxNext, Latch);1046 LatchBR->setCondition(IdxCmp);1047 } else {1048 // Connect the prolog code to the original loop and update the1049 // PHI functions.1050 ConnectProlog(L, BECount, Count, PrologExit, LatchExit, PreHeader,1051 NewPreHeader, VMap, DT, LI, PreserveLCSSA, *SE);1052 }1053 1054 // If this loop is nested, then the loop unroller changes the code in the any1055 // of its parent loops, so the Scalar Evolution pass needs to be run again.1056 SE->forgetTopmostLoop(L);1057 1058 // Verify that the Dom Tree and Loop Info are correct.1059#if defined(EXPENSIVE_CHECKS) && !defined(NDEBUG)1060 if (DT) {1061 assert(DT->verify(DominatorTree::VerificationLevel::Full));1062 LI->verify(*DT);1063 }1064#endif1065 1066 // For unroll factor 2 remainder loop will have 1 iteration.1067 if (Count == 2 && DT && LI && SE) {1068 // TODO: This code could probably be pulled out into a helper function1069 // (e.g. breakLoopBackedgeAndSimplify) and reused in loop-deletion.1070 BasicBlock *RemainderLatch = remainderLoop->getLoopLatch();1071 assert(RemainderLatch);1072 SmallVector<BasicBlock *> RemainderBlocks(remainderLoop->getBlocks());1073 breakLoopBackedge(remainderLoop, *DT, *SE, *LI, nullptr);1074 remainderLoop = nullptr;1075 1076 // Simplify loop values after breaking the backedge1077 const DataLayout &DL = L->getHeader()->getDataLayout();1078 SmallVector<WeakTrackingVH, 16> DeadInsts;1079 for (BasicBlock *BB : RemainderBlocks) {1080 for (Instruction &Inst : llvm::make_early_inc_range(*BB)) {1081 if (Value *V = simplifyInstruction(&Inst, {DL, nullptr, DT, AC}))1082 if (LI->replacementPreservesLCSSAForm(&Inst, V))1083 Inst.replaceAllUsesWith(V);1084 if (isInstructionTriviallyDead(&Inst))1085 DeadInsts.emplace_back(&Inst);1086 }1087 // We can't do recursive deletion until we're done iterating, as we might1088 // have a phi which (potentially indirectly) uses instructions later in1089 // the block we're iterating through.1090 RecursivelyDeleteTriviallyDeadInstructions(DeadInsts);1091 }1092 1093 // Merge latch into exit block.1094 auto *ExitBB = RemainderLatch->getSingleSuccessor();1095 assert(ExitBB && "required after breaking cond br backedge");1096 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);1097 MergeBlockIntoPredecessor(ExitBB, &DTU, LI);1098 }1099 1100 // Canonicalize to LoopSimplifyForm both original and remainder loops. We1101 // cannot rely on the LoopUnrollPass to do this because it only does1102 // canonicalization for parent/subloops and not the sibling loops.1103 if (OtherExits.size() > 0) {1104 // Generate dedicated exit blocks for the original loop, to preserve1105 // LoopSimplifyForm.1106 formDedicatedExitBlocks(L, DT, LI, nullptr, PreserveLCSSA);1107 // Generate dedicated exit blocks for the remainder loop if one exists, to1108 // preserve LoopSimplifyForm.1109 if (remainderLoop)1110 formDedicatedExitBlocks(remainderLoop, DT, LI, nullptr, PreserveLCSSA);1111 }1112 1113 auto UnrollResult = LoopUnrollResult::Unmodified;1114 if (remainderLoop && UnrollRemainder) {1115 LLVM_DEBUG(dbgs() << "Unrolling remainder loop\n");1116 UnrollLoopOptions ULO;1117 ULO.Count = Count - 1;1118 ULO.Force = false;1119 ULO.Runtime = false;1120 ULO.AllowExpensiveTripCount = false;1121 ULO.UnrollRemainder = false;1122 ULO.ForgetAllSCEV = ForgetAllSCEV;1123 assert(!getLoopConvergenceHeart(L) &&1124 "A loop with a convergence heart does not allow runtime unrolling.");1125 UnrollResult = UnrollLoop(remainderLoop, ULO, LI, SE, DT, AC, TTI,1126 /*ORE*/ nullptr, PreserveLCSSA);1127 }1128 1129 if (ResultLoop && UnrollResult != LoopUnrollResult::FullyUnrolled)1130 *ResultLoop = remainderLoop;1131 NumRuntimeUnrolled++;1132 return true;1133}1134