1001 lines · cpp
1//===-- LoopUnrollAndJam.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 loop unroll and jam as a routine, much like10// LoopUnroll.cpp implements loop unroll.11//12//===----------------------------------------------------------------------===//13 14#include "llvm/ADT/ArrayRef.h"15#include "llvm/ADT/DenseMap.h"16#include "llvm/ADT/STLExtras.h"17#include "llvm/ADT/SmallPtrSet.h"18#include "llvm/ADT/SmallVector.h"19#include "llvm/ADT/Statistic.h"20#include "llvm/ADT/StringRef.h"21#include "llvm/ADT/Twine.h"22#include "llvm/Analysis/AssumptionCache.h"23#include "llvm/Analysis/DependenceAnalysis.h"24#include "llvm/Analysis/DomTreeUpdater.h"25#include "llvm/Analysis/LoopInfo.h"26#include "llvm/Analysis/LoopIterator.h"27#include "llvm/Analysis/MustExecute.h"28#include "llvm/Analysis/OptimizationRemarkEmitter.h"29#include "llvm/Analysis/ScalarEvolution.h"30#include "llvm/IR/BasicBlock.h"31#include "llvm/IR/DebugInfoMetadata.h"32#include "llvm/IR/DebugLoc.h"33#include "llvm/IR/DiagnosticInfo.h"34#include "llvm/IR/Dominators.h"35#include "llvm/IR/Function.h"36#include "llvm/IR/Instruction.h"37#include "llvm/IR/Instructions.h"38#include "llvm/IR/IntrinsicInst.h"39#include "llvm/IR/User.h"40#include "llvm/IR/Value.h"41#include "llvm/IR/ValueHandle.h"42#include "llvm/IR/ValueMap.h"43#include "llvm/Support/Casting.h"44#include "llvm/Support/Debug.h"45#include "llvm/Support/ErrorHandling.h"46#include "llvm/Support/GenericDomTree.h"47#include "llvm/Support/raw_ostream.h"48#include "llvm/Transforms/Utils/BasicBlockUtils.h"49#include "llvm/Transforms/Utils/Cloning.h"50#include "llvm/Transforms/Utils/LoopUtils.h"51#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"52#include "llvm/Transforms/Utils/UnrollLoop.h"53#include "llvm/Transforms/Utils/ValueMapper.h"54#include <assert.h>55#include <memory>56#include <vector>57 58using namespace llvm;59 60#define DEBUG_TYPE "loop-unroll-and-jam"61 62STATISTIC(NumUnrolledAndJammed, "Number of loops unroll and jammed");63STATISTIC(NumCompletelyUnrolledAndJammed, "Number of loops unroll and jammed");64 65typedef SmallPtrSet<BasicBlock *, 4> BasicBlockSet;66 67// Partition blocks in an outer/inner loop pair into blocks before and after68// the loop69static bool partitionLoopBlocks(Loop &L, BasicBlockSet &ForeBlocks,70 BasicBlockSet &AftBlocks, DominatorTree &DT) {71 Loop *SubLoop = L.getSubLoops()[0];72 BasicBlock *SubLoopLatch = SubLoop->getLoopLatch();73 74 for (BasicBlock *BB : L.blocks()) {75 if (!SubLoop->contains(BB)) {76 if (DT.dominates(SubLoopLatch, BB))77 AftBlocks.insert(BB);78 else79 ForeBlocks.insert(BB);80 }81 }82 83 // Check that all blocks in ForeBlocks together dominate the subloop84 // TODO: This might ideally be done better with a dominator/postdominators.85 BasicBlock *SubLoopPreHeader = SubLoop->getLoopPreheader();86 for (BasicBlock *BB : ForeBlocks) {87 if (BB == SubLoopPreHeader)88 continue;89 Instruction *TI = BB->getTerminator();90 for (BasicBlock *Succ : successors(TI))91 if (!ForeBlocks.count(Succ))92 return false;93 }94 95 return true;96}97 98/// Partition blocks in a loop nest into blocks before and after each inner99/// loop.100static bool partitionOuterLoopBlocks(101 Loop &Root, Loop &JamLoop, BasicBlockSet &JamLoopBlocks,102 DenseMap<Loop *, BasicBlockSet> &ForeBlocksMap,103 DenseMap<Loop *, BasicBlockSet> &AftBlocksMap, DominatorTree &DT) {104 JamLoopBlocks.insert_range(JamLoop.blocks());105 106 for (Loop *L : Root.getLoopsInPreorder()) {107 if (L == &JamLoop)108 break;109 110 if (!partitionLoopBlocks(*L, ForeBlocksMap[L], AftBlocksMap[L], DT))111 return false;112 }113 114 return true;115}116 117// TODO Remove when UnrollAndJamLoop changed to support unroll and jamming more118// than 2 levels loop.119static bool partitionOuterLoopBlocks(Loop *L, Loop *SubLoop,120 BasicBlockSet &ForeBlocks,121 BasicBlockSet &SubLoopBlocks,122 BasicBlockSet &AftBlocks,123 DominatorTree *DT) {124 SubLoopBlocks.insert_range(SubLoop->blocks());125 return partitionLoopBlocks(*L, ForeBlocks, AftBlocks, *DT);126}127 128// Looks at the phi nodes in Header for values coming from Latch. For these129// instructions and all their operands calls Visit on them, keeping going for130// all the operands in AftBlocks. Returns false if Visit returns false,131// otherwise returns true. This is used to process the instructions in the132// Aft blocks that need to be moved before the subloop. It is used in two133// places. One to check that the required set of instructions can be moved134// before the loop. Then to collect the instructions to actually move in135// moveHeaderPhiOperandsToForeBlocks.136template <typename T>137static bool processHeaderPhiOperands(BasicBlock *Header, BasicBlock *Latch,138 BasicBlockSet &AftBlocks, T Visit) {139 SmallPtrSet<Instruction *, 8> VisitedInstr;140 141 std::function<bool(Instruction * I)> ProcessInstr = [&](Instruction *I) {142 if (!VisitedInstr.insert(I).second)143 return true;144 145 if (AftBlocks.count(I->getParent()))146 for (auto &U : I->operands())147 if (Instruction *II = dyn_cast<Instruction>(U))148 if (!ProcessInstr(II))149 return false;150 151 return Visit(I);152 };153 154 for (auto &Phi : Header->phis()) {155 Value *V = Phi.getIncomingValueForBlock(Latch);156 if (Instruction *I = dyn_cast<Instruction>(V))157 if (!ProcessInstr(I))158 return false;159 }160 161 return true;162}163 164// Move the phi operands of Header from Latch out of AftBlocks to InsertLoc.165static void moveHeaderPhiOperandsToForeBlocks(BasicBlock *Header,166 BasicBlock *Latch,167 BasicBlock::iterator InsertLoc,168 BasicBlockSet &AftBlocks) {169 // We need to ensure we move the instructions in the correct order,170 // starting with the earliest required instruction and moving forward.171 processHeaderPhiOperands(Header, Latch, AftBlocks,172 [&AftBlocks, &InsertLoc](Instruction *I) {173 if (AftBlocks.count(I->getParent()))174 I->moveBefore(InsertLoc);175 return true;176 });177}178 179/*180 This method performs Unroll and Jam. For a simple loop like:181 for (i = ..)182 Fore(i)183 for (j = ..)184 SubLoop(i, j)185 Aft(i)186 187 Instead of doing normal inner or outer unrolling, we do:188 for (i = .., i+=2)189 Fore(i)190 Fore(i+1)191 for (j = ..)192 SubLoop(i, j)193 SubLoop(i+1, j)194 Aft(i)195 Aft(i+1)196 197 So the outer loop is essetially unrolled and then the inner loops are fused198 ("jammed") together into a single loop. This can increase speed when there199 are loads in SubLoop that are invariant to i, as they become shared between200 the now jammed inner loops.201 202 We do this by spliting the blocks in the loop into Fore, Subloop and Aft.203 Fore blocks are those before the inner loop, Aft are those after. Normal204 Unroll code is used to copy each of these sets of blocks and the results are205 combined together into the final form above.206 207 isSafeToUnrollAndJam should be used prior to calling this to make sure the208 unrolling will be valid. Checking profitablility is also advisable.209 210 If EpilogueLoop is non-null, it receives the epilogue loop (if it was211 necessary to create one and not fully unrolled).212*/213LoopUnrollResult214llvm::UnrollAndJamLoop(Loop *L, unsigned Count, unsigned TripCount,215 unsigned TripMultiple, bool UnrollRemainder,216 LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT,217 AssumptionCache *AC, const TargetTransformInfo *TTI,218 OptimizationRemarkEmitter *ORE, Loop **EpilogueLoop) {219 220 // When we enter here we should have already checked that it is safe221 BasicBlock *Header = L->getHeader();222 assert(Header && "No header.");223 assert(L->getSubLoops().size() == 1);224 Loop *SubLoop = *L->begin();225 226 // Don't enter the unroll code if there is nothing to do.227 if (TripCount == 0 && Count < 2) {228 LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; almost nothing to do\n");229 return LoopUnrollResult::Unmodified;230 }231 232 assert(Count > 0);233 assert(TripMultiple > 0);234 assert(TripCount == 0 || TripCount % TripMultiple == 0);235 236 // Are we eliminating the loop control altogether?237 bool CompletelyUnroll = (Count == TripCount);238 239 // We use the runtime remainder in cases where we don't know trip multiple240 if (TripMultiple % Count != 0) {241 if (!UnrollRuntimeLoopRemainder(L, Count, /*AllowExpensiveTripCount*/ false,242 /*UseEpilogRemainder*/ true,243 UnrollRemainder, /*ForgetAllSCEV*/ false,244 LI, SE, DT, AC, TTI, true,245 SCEVCheapExpansionBudget, EpilogueLoop)) {246 LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; remainder loop could not be "247 "generated when assuming runtime trip count\n");248 return LoopUnrollResult::Unmodified;249 }250 }251 252 // Notify ScalarEvolution that the loop will be substantially changed,253 // if not outright eliminated.254 if (SE) {255 SE->forgetLoop(L);256 SE->forgetBlockAndLoopDispositions();257 }258 259 using namespace ore;260 // Report the unrolling decision.261 if (CompletelyUnroll) {262 LLVM_DEBUG(dbgs() << "COMPLETELY UNROLL AND JAMMING loop %"263 << Header->getName() << " with trip count " << TripCount264 << "!\n");265 ORE->emit(OptimizationRemark(DEBUG_TYPE, "FullyUnrolled", L->getStartLoc(),266 L->getHeader())267 << "completely unroll and jammed loop with "268 << NV("UnrollCount", TripCount) << " iterations");269 } else {270 auto DiagBuilder = [&]() {271 OptimizationRemark Diag(DEBUG_TYPE, "PartialUnrolled", L->getStartLoc(),272 L->getHeader());273 return Diag << "unroll and jammed loop by a factor of "274 << NV("UnrollCount", Count);275 };276 277 LLVM_DEBUG(dbgs() << "UNROLL AND JAMMING loop %" << Header->getName()278 << " by " << Count);279 if (TripMultiple != 1) {280 LLVM_DEBUG(dbgs() << " with " << TripMultiple << " trips per branch");281 ORE->emit([&]() {282 return DiagBuilder() << " with " << NV("TripMultiple", TripMultiple)283 << " trips per branch";284 });285 } else {286 LLVM_DEBUG(dbgs() << " with run-time trip count");287 ORE->emit([&]() { return DiagBuilder() << " with run-time trip count"; });288 }289 LLVM_DEBUG(dbgs() << "!\n");290 }291 292 BasicBlock *Preheader = L->getLoopPreheader();293 BasicBlock *LatchBlock = L->getLoopLatch();294 assert(Preheader && "No preheader");295 assert(LatchBlock && "No latch block");296 BranchInst *BI = dyn_cast<BranchInst>(LatchBlock->getTerminator());297 assert(BI && !BI->isUnconditional());298 bool ContinueOnTrue = L->contains(BI->getSuccessor(0));299 BasicBlock *LoopExit = BI->getSuccessor(ContinueOnTrue);300 bool SubLoopContinueOnTrue = SubLoop->contains(301 SubLoop->getLoopLatch()->getTerminator()->getSuccessor(0));302 303 // Partition blocks in an outer/inner loop pair into blocks before and after304 // the loop305 BasicBlockSet SubLoopBlocks;306 BasicBlockSet ForeBlocks;307 BasicBlockSet AftBlocks;308 partitionOuterLoopBlocks(L, SubLoop, ForeBlocks, SubLoopBlocks, AftBlocks,309 DT);310 311 // We keep track of the entering/first and exiting/last block of each of312 // Fore/SubLoop/Aft in each iteration. This helps make the stapling up of313 // blocks easier.314 std::vector<BasicBlock *> ForeBlocksFirst;315 std::vector<BasicBlock *> ForeBlocksLast;316 std::vector<BasicBlock *> SubLoopBlocksFirst;317 std::vector<BasicBlock *> SubLoopBlocksLast;318 std::vector<BasicBlock *> AftBlocksFirst;319 std::vector<BasicBlock *> AftBlocksLast;320 ForeBlocksFirst.push_back(Header);321 ForeBlocksLast.push_back(SubLoop->getLoopPreheader());322 SubLoopBlocksFirst.push_back(SubLoop->getHeader());323 SubLoopBlocksLast.push_back(SubLoop->getExitingBlock());324 AftBlocksFirst.push_back(SubLoop->getExitBlock());325 AftBlocksLast.push_back(L->getExitingBlock());326 // Maps Blocks[0] -> Blocks[It]327 ValueToValueMapTy LastValueMap;328 329 // Move any instructions from fore phi operands from AftBlocks into Fore.330 moveHeaderPhiOperandsToForeBlocks(331 Header, LatchBlock, ForeBlocksLast[0]->getTerminator()->getIterator(),332 AftBlocks);333 334 // The current on-the-fly SSA update requires blocks to be processed in335 // reverse postorder so that LastValueMap contains the correct value at each336 // exit.337 LoopBlocksDFS DFS(L);338 DFS.perform(LI);339 // Stash the DFS iterators before adding blocks to the loop.340 LoopBlocksDFS::RPOIterator BlockBegin = DFS.beginRPO();341 LoopBlocksDFS::RPOIterator BlockEnd = DFS.endRPO();342 343 // When a FSDiscriminator is enabled, we don't need to add the multiply344 // factors to the discriminators.345 if (Header->getParent()->shouldEmitDebugInfoForProfiling() &&346 !EnableFSDiscriminator)347 for (BasicBlock *BB : L->getBlocks())348 for (Instruction &I : *BB)349 if (!I.isDebugOrPseudoInst())350 if (const DILocation *DIL = I.getDebugLoc()) {351 auto NewDIL = DIL->cloneByMultiplyingDuplicationFactor(Count);352 if (NewDIL)353 I.setDebugLoc(*NewDIL);354 else355 LLVM_DEBUG(dbgs()356 << "Failed to create new discriminator: "357 << DIL->getFilename() << " Line: " << DIL->getLine());358 }359 360 // Copy all blocks361 for (unsigned It = 1; It != Count; ++It) {362 SmallVector<BasicBlock *, 8> NewBlocks;363 // Maps Blocks[It] -> Blocks[It-1]364 DenseMap<Value *, Value *> PrevItValueMap;365 SmallDenseMap<const Loop *, Loop *, 4> NewLoops;366 NewLoops[L] = L;367 NewLoops[SubLoop] = SubLoop;368 369 for (LoopBlocksDFS::RPOIterator BB = BlockBegin; BB != BlockEnd; ++BB) {370 ValueToValueMapTy VMap;371 BasicBlock *New = CloneBasicBlock(*BB, VMap, "." + Twine(It));372 Header->getParent()->insert(Header->getParent()->end(), New);373 374 // Tell LI about New.375 addClonedBlockToLoopInfo(*BB, New, LI, NewLoops);376 377 if (ForeBlocks.count(*BB)) {378 if (*BB == ForeBlocksFirst[0])379 ForeBlocksFirst.push_back(New);380 if (*BB == ForeBlocksLast[0])381 ForeBlocksLast.push_back(New);382 } else if (SubLoopBlocks.count(*BB)) {383 if (*BB == SubLoopBlocksFirst[0])384 SubLoopBlocksFirst.push_back(New);385 if (*BB == SubLoopBlocksLast[0])386 SubLoopBlocksLast.push_back(New);387 } else if (AftBlocks.count(*BB)) {388 if (*BB == AftBlocksFirst[0])389 AftBlocksFirst.push_back(New);390 if (*BB == AftBlocksLast[0])391 AftBlocksLast.push_back(New);392 } else {393 llvm_unreachable("BB being cloned should be in Fore/Sub/Aft");394 }395 396 // Update our running maps of newest clones397 auto &Last = LastValueMap[*BB];398 PrevItValueMap[New] = (It == 1 ? *BB : Last);399 Last = New;400 for (ValueToValueMapTy::iterator VI = VMap.begin(), VE = VMap.end();401 VI != VE; ++VI) {402 auto &LVM = LastValueMap[VI->first];403 PrevItValueMap[VI->second] =404 const_cast<Value *>(It == 1 ? VI->first : LVM);405 LVM = VI->second;406 }407 408 NewBlocks.push_back(New);409 410 // Update DomTree:411 if (*BB == ForeBlocksFirst[0])412 DT->addNewBlock(New, ForeBlocksLast[It - 1]);413 else if (*BB == SubLoopBlocksFirst[0])414 DT->addNewBlock(New, SubLoopBlocksLast[It - 1]);415 else if (*BB == AftBlocksFirst[0])416 DT->addNewBlock(New, AftBlocksLast[It - 1]);417 else {418 // Each set of blocks (Fore/Sub/Aft) will have the same internal domtree419 // structure.420 auto BBDomNode = DT->getNode(*BB);421 auto BBIDom = BBDomNode->getIDom();422 BasicBlock *OriginalBBIDom = BBIDom->getBlock();423 assert(OriginalBBIDom);424 assert(LastValueMap[cast<Value>(OriginalBBIDom)]);425 DT->addNewBlock(426 New, cast<BasicBlock>(LastValueMap[cast<Value>(OriginalBBIDom)]));427 }428 }429 430 // Remap all instructions in the most recent iteration431 remapInstructionsInBlocks(NewBlocks, LastValueMap);432 for (BasicBlock *NewBlock : NewBlocks) {433 for (Instruction &I : *NewBlock) {434 if (auto *II = dyn_cast<AssumeInst>(&I))435 AC->registerAssumption(II);436 }437 }438 439 // Alter the ForeBlocks phi's, pointing them at the latest version of the440 // value from the previous iteration's phis441 for (PHINode &Phi : ForeBlocksFirst[It]->phis()) {442 Value *OldValue = Phi.getIncomingValueForBlock(AftBlocksLast[It]);443 assert(OldValue && "should have incoming edge from Aft[It]");444 Value *NewValue = OldValue;445 if (Value *PrevValue = PrevItValueMap[OldValue])446 NewValue = PrevValue;447 448 assert(Phi.getNumOperands() == 2);449 Phi.setIncomingBlock(0, ForeBlocksLast[It - 1]);450 Phi.setIncomingValue(0, NewValue);451 Phi.removeIncomingValue(1);452 }453 }454 455 // Now that all the basic blocks for the unrolled iterations are in place,456 // finish up connecting the blocks and phi nodes. At this point LastValueMap457 // is the last unrolled iterations values.458 459 // Update Phis in BB from OldBB to point to NewBB and use the latest value460 // from LastValueMap461 auto updatePHIBlocksAndValues = [](BasicBlock *BB, BasicBlock *OldBB,462 BasicBlock *NewBB,463 ValueToValueMapTy &LastValueMap) {464 for (PHINode &Phi : BB->phis()) {465 for (unsigned b = 0; b < Phi.getNumIncomingValues(); ++b) {466 if (Phi.getIncomingBlock(b) == OldBB) {467 Value *OldValue = Phi.getIncomingValue(b);468 if (Value *LastValue = LastValueMap[OldValue])469 Phi.setIncomingValue(b, LastValue);470 Phi.setIncomingBlock(b, NewBB);471 break;472 }473 }474 }475 };476 // Move all the phis from Src into Dest477 auto movePHIs = [](BasicBlock *Src, BasicBlock *Dest) {478 BasicBlock::iterator insertPoint = Dest->getFirstNonPHIIt();479 while (PHINode *Phi = dyn_cast<PHINode>(Src->begin()))480 Phi->moveBefore(*Dest, insertPoint);481 };482 483 // Update the PHI values outside the loop to point to the last block484 updatePHIBlocksAndValues(LoopExit, AftBlocksLast[0], AftBlocksLast.back(),485 LastValueMap);486 487 // Update ForeBlocks successors and phi nodes488 BranchInst *ForeTerm =489 cast<BranchInst>(ForeBlocksLast.back()->getTerminator());490 assert(ForeTerm->getNumSuccessors() == 1 && "Expecting one successor");491 ForeTerm->setSuccessor(0, SubLoopBlocksFirst[0]);492 493 if (CompletelyUnroll) {494 while (PHINode *Phi = dyn_cast<PHINode>(ForeBlocksFirst[0]->begin())) {495 Phi->replaceAllUsesWith(Phi->getIncomingValueForBlock(Preheader));496 Phi->eraseFromParent();497 }498 } else {499 // Update the PHI values to point to the last aft block500 updatePHIBlocksAndValues(ForeBlocksFirst[0], AftBlocksLast[0],501 AftBlocksLast.back(), LastValueMap);502 }503 504 for (unsigned It = 1; It != Count; It++) {505 // Remap ForeBlock successors from previous iteration to this506 BranchInst *ForeTerm =507 cast<BranchInst>(ForeBlocksLast[It - 1]->getTerminator());508 assert(ForeTerm->getNumSuccessors() == 1 && "Expecting one successor");509 ForeTerm->setSuccessor(0, ForeBlocksFirst[It]);510 }511 512 // Subloop successors and phis513 BranchInst *SubTerm =514 cast<BranchInst>(SubLoopBlocksLast.back()->getTerminator());515 SubTerm->setSuccessor(!SubLoopContinueOnTrue, SubLoopBlocksFirst[0]);516 SubTerm->setSuccessor(SubLoopContinueOnTrue, AftBlocksFirst[0]);517 SubLoopBlocksFirst[0]->replacePhiUsesWith(ForeBlocksLast[0],518 ForeBlocksLast.back());519 SubLoopBlocksFirst[0]->replacePhiUsesWith(SubLoopBlocksLast[0],520 SubLoopBlocksLast.back());521 522 for (unsigned It = 1; It != Count; It++) {523 // Replace the conditional branch of the previous iteration subloop with an524 // unconditional one to this one525 BranchInst *SubTerm =526 cast<BranchInst>(SubLoopBlocksLast[It - 1]->getTerminator());527 BranchInst::Create(SubLoopBlocksFirst[It], SubTerm->getIterator());528 SubTerm->eraseFromParent();529 530 SubLoopBlocksFirst[It]->replacePhiUsesWith(ForeBlocksLast[It],531 ForeBlocksLast.back());532 SubLoopBlocksFirst[It]->replacePhiUsesWith(SubLoopBlocksLast[It],533 SubLoopBlocksLast.back());534 movePHIs(SubLoopBlocksFirst[It], SubLoopBlocksFirst[0]);535 }536 537 // Aft blocks successors and phis538 BranchInst *AftTerm = cast<BranchInst>(AftBlocksLast.back()->getTerminator());539 if (CompletelyUnroll) {540 BranchInst::Create(LoopExit, AftTerm->getIterator());541 AftTerm->eraseFromParent();542 } else {543 AftTerm->setSuccessor(!ContinueOnTrue, ForeBlocksFirst[0]);544 assert(AftTerm->getSuccessor(ContinueOnTrue) == LoopExit &&545 "Expecting the ContinueOnTrue successor of AftTerm to be LoopExit");546 }547 AftBlocksFirst[0]->replacePhiUsesWith(SubLoopBlocksLast[0],548 SubLoopBlocksLast.back());549 550 for (unsigned It = 1; It != Count; It++) {551 // Replace the conditional branch of the previous iteration subloop with an552 // unconditional one to this one553 BranchInst *AftTerm =554 cast<BranchInst>(AftBlocksLast[It - 1]->getTerminator());555 BranchInst::Create(AftBlocksFirst[It], AftTerm->getIterator());556 AftTerm->eraseFromParent();557 558 AftBlocksFirst[It]->replacePhiUsesWith(SubLoopBlocksLast[It],559 SubLoopBlocksLast.back());560 movePHIs(AftBlocksFirst[It], AftBlocksFirst[0]);561 }562 563 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);564 // Dominator Tree. Remove the old links between Fore, Sub and Aft, adding the565 // new ones required.566 if (Count != 1) {567 SmallVector<DominatorTree::UpdateType, 4> DTUpdates;568 DTUpdates.emplace_back(DominatorTree::UpdateKind::Delete, ForeBlocksLast[0],569 SubLoopBlocksFirst[0]);570 DTUpdates.emplace_back(DominatorTree::UpdateKind::Delete,571 SubLoopBlocksLast[0], AftBlocksFirst[0]);572 573 DTUpdates.emplace_back(DominatorTree::UpdateKind::Insert,574 ForeBlocksLast.back(), SubLoopBlocksFirst[0]);575 DTUpdates.emplace_back(DominatorTree::UpdateKind::Insert,576 SubLoopBlocksLast.back(), AftBlocksFirst[0]);577 DTU.applyUpdatesPermissive(DTUpdates);578 }579 580 // Merge adjacent basic blocks, if possible.581 SmallPtrSet<BasicBlock *, 16> MergeBlocks;582 MergeBlocks.insert_range(ForeBlocksLast);583 MergeBlocks.insert_range(SubLoopBlocksLast);584 MergeBlocks.insert_range(AftBlocksLast);585 586 MergeBlockSuccessorsIntoGivenBlocks(MergeBlocks, L, &DTU, LI);587 588 // Apply updates to the DomTree.589 DT = &DTU.getDomTree();590 591 // At this point, the code is well formed. We now do a quick sweep over the592 // inserted code, doing constant propagation and dead code elimination as we593 // go.594 simplifyLoopAfterUnroll(SubLoop, true, LI, SE, DT, AC, TTI);595 simplifyLoopAfterUnroll(L, !CompletelyUnroll && Count > 1, LI, SE, DT, AC,596 TTI);597 598 NumCompletelyUnrolledAndJammed += CompletelyUnroll;599 ++NumUnrolledAndJammed;600 601 // Update LoopInfo if the loop is completely removed.602 if (CompletelyUnroll)603 LI->erase(L);604 605#ifndef NDEBUG606 // We shouldn't have done anything to break loop simplify form or LCSSA.607 Loop *OutestLoop = SubLoop->getParentLoop()608 ? SubLoop->getParentLoop()->getParentLoop()609 ? SubLoop->getParentLoop()->getParentLoop()610 : SubLoop->getParentLoop()611 : SubLoop;612 assert(DT->verify());613 LI->verify(*DT);614 assert(OutestLoop->isRecursivelyLCSSAForm(*DT, *LI));615 if (!CompletelyUnroll)616 assert(L->isLoopSimplifyForm());617 assert(SubLoop->isLoopSimplifyForm());618 SE->verify();619#endif620 621 return CompletelyUnroll ? LoopUnrollResult::FullyUnrolled622 : LoopUnrollResult::PartiallyUnrolled;623}624 625static bool getLoadsAndStores(BasicBlockSet &Blocks,626 SmallVector<Instruction *, 4> &MemInstr) {627 // Scan the BBs and collect legal loads and stores.628 // Returns false if non-simple loads/stores are found.629 for (BasicBlock *BB : Blocks) {630 for (Instruction &I : *BB) {631 if (auto *Ld = dyn_cast<LoadInst>(&I)) {632 if (!Ld->isSimple())633 return false;634 MemInstr.push_back(&I);635 } else if (auto *St = dyn_cast<StoreInst>(&I)) {636 if (!St->isSimple())637 return false;638 MemInstr.push_back(&I);639 } else if (I.mayReadOrWriteMemory()) {640 return false;641 }642 }643 }644 return true;645}646 647static bool preservesForwardDependence(Instruction *Src, Instruction *Dst,648 unsigned UnrollLevel, unsigned JamLevel,649 bool Sequentialized, Dependence *D) {650 // UnrollLevel might carry the dependency Src --> Dst651 // Does a different loop after unrolling?652 for (unsigned CurLoopDepth = UnrollLevel + 1; CurLoopDepth <= JamLevel;653 ++CurLoopDepth) {654 auto JammedDir = D->getDirection(CurLoopDepth);655 if (JammedDir == Dependence::DVEntry::LT)656 return true;657 658 if (JammedDir & Dependence::DVEntry::GT)659 return false;660 }661 662 return true;663}664 665static bool preservesBackwardDependence(Instruction *Src, Instruction *Dst,666 unsigned UnrollLevel, unsigned JamLevel,667 bool Sequentialized, Dependence *D) {668 // UnrollLevel might carry the dependency Dst --> Src669 for (unsigned CurLoopDepth = UnrollLevel + 1; CurLoopDepth <= JamLevel;670 ++CurLoopDepth) {671 auto JammedDir = D->getDirection(CurLoopDepth);672 if (JammedDir == Dependence::DVEntry::GT)673 return true;674 675 if (JammedDir & Dependence::DVEntry::LT)676 return false;677 }678 679 // Backward dependencies are only preserved if not interleaved.680 return Sequentialized;681}682 683// Check whether it is semantically safe Src and Dst considering any potential684// dependency between them.685//686// @param UnrollLevel The level of the loop being unrolled687// @param JamLevel The level of the loop being jammed; if Src and Dst are on688// different levels, the outermost common loop counts as jammed level689//690// @return true if is safe and false if there is a dependency violation.691static bool checkDependency(Instruction *Src, Instruction *Dst,692 unsigned UnrollLevel, unsigned JamLevel,693 bool Sequentialized, DependenceInfo &DI) {694 assert(UnrollLevel <= JamLevel &&695 "Expecting JamLevel to be at least UnrollLevel");696 697 if (Src == Dst)698 return true;699 // Ignore Input dependencies.700 if (isa<LoadInst>(Src) && isa<LoadInst>(Dst))701 return true;702 703 // Check whether unroll-and-jam may violate a dependency.704 // By construction, every dependency will be lexicographically non-negative705 // (if it was, it would violate the current execution order), such as706 // (0,0,>,*,*)707 // Unroll-and-jam changes the GT execution of two executions to the same708 // iteration of the chosen unroll level. That is, a GT dependence becomes a GE709 // dependence (or EQ, if we fully unrolled the loop) at the loop's position:710 // (0,0,>=,*,*)711 // Now, the dependency is not necessarily non-negative anymore, i.e.712 // unroll-and-jam may violate correctness.713 std::unique_ptr<Dependence> D = DI.depends(Src, Dst);714 if (!D)715 return true;716 assert(D->isOrdered() && "Expected an output, flow or anti dep.");717 718 if (D->isConfused()) {719 LLVM_DEBUG(dbgs() << " Confused dependency between:\n"720 << " " << *Src << "\n"721 << " " << *Dst << "\n");722 return false;723 }724 725 // If outer levels (levels enclosing the loop being unroll-and-jammed) have a726 // non-equal direction, then the locations accessed in the inner levels cannot727 // overlap in memory. We assumes the indexes never overlap into neighboring728 // dimensions.729 for (unsigned CurLoopDepth = 1; CurLoopDepth < UnrollLevel; ++CurLoopDepth)730 if (!(D->getDirection(CurLoopDepth) & Dependence::DVEntry::EQ))731 return true;732 733 auto UnrollDirection = D->getDirection(UnrollLevel);734 735 // If the distance carried by the unrolled loop is 0, then after unrolling736 // that distance will become non-zero resulting in non-overlapping accesses in737 // the inner loops.738 if (UnrollDirection == Dependence::DVEntry::EQ)739 return true;740 741 if (UnrollDirection & Dependence::DVEntry::LT &&742 !preservesForwardDependence(Src, Dst, UnrollLevel, JamLevel,743 Sequentialized, D.get()))744 return false;745 746 if (UnrollDirection & Dependence::DVEntry::GT &&747 !preservesBackwardDependence(Src, Dst, UnrollLevel, JamLevel,748 Sequentialized, D.get()))749 return false;750 751 return true;752}753 754static bool755checkDependencies(Loop &Root, const BasicBlockSet &SubLoopBlocks,756 const DenseMap<Loop *, BasicBlockSet> &ForeBlocksMap,757 const DenseMap<Loop *, BasicBlockSet> &AftBlocksMap,758 DependenceInfo &DI, LoopInfo &LI) {759 SmallVector<BasicBlockSet, 8> AllBlocks;760 for (Loop *L : Root.getLoopsInPreorder())761 if (ForeBlocksMap.contains(L))762 AllBlocks.push_back(ForeBlocksMap.lookup(L));763 AllBlocks.push_back(SubLoopBlocks);764 for (Loop *L : Root.getLoopsInPreorder())765 if (AftBlocksMap.contains(L))766 AllBlocks.push_back(AftBlocksMap.lookup(L));767 768 unsigned LoopDepth = Root.getLoopDepth();769 SmallVector<Instruction *, 4> EarlierLoadsAndStores;770 SmallVector<Instruction *, 4> CurrentLoadsAndStores;771 for (BasicBlockSet &Blocks : AllBlocks) {772 CurrentLoadsAndStores.clear();773 if (!getLoadsAndStores(Blocks, CurrentLoadsAndStores))774 return false;775 776 Loop *CurLoop = LI.getLoopFor((*Blocks.begin())->front().getParent());777 unsigned CurLoopDepth = CurLoop->getLoopDepth();778 779 for (auto *Earlier : EarlierLoadsAndStores) {780 Loop *EarlierLoop = LI.getLoopFor(Earlier->getParent());781 unsigned EarlierDepth = EarlierLoop->getLoopDepth();782 unsigned CommonLoopDepth = std::min(EarlierDepth, CurLoopDepth);783 for (auto *Later : CurrentLoadsAndStores) {784 if (!checkDependency(Earlier, Later, LoopDepth, CommonLoopDepth, false,785 DI))786 return false;787 }788 }789 790 size_t NumInsts = CurrentLoadsAndStores.size();791 for (size_t I = 0; I < NumInsts; ++I) {792 for (size_t J = I; J < NumInsts; ++J) {793 if (!checkDependency(CurrentLoadsAndStores[I], CurrentLoadsAndStores[J],794 LoopDepth, CurLoopDepth, true, DI))795 return false;796 }797 }798 799 EarlierLoadsAndStores.append(CurrentLoadsAndStores.begin(),800 CurrentLoadsAndStores.end());801 }802 return true;803}804 805static bool isEligibleLoopForm(const Loop &Root) {806 // Root must have a child.807 if (Root.getSubLoops().size() != 1)808 return false;809 810 const Loop *L = &Root;811 do {812 // All loops in Root need to be in simplify and rotated form.813 if (!L->isLoopSimplifyForm())814 return false;815 816 if (!L->isRotatedForm())817 return false;818 819 if (L->getHeader()->hasAddressTaken()) {820 LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; Address taken\n");821 return false;822 }823 824 unsigned SubLoopsSize = L->getSubLoops().size();825 if (SubLoopsSize == 0)826 return true;827 828 // Only one child is allowed.829 if (SubLoopsSize != 1)830 return false;831 832 // Only loops with a single exit block can be unrolled and jammed.833 // The function getExitBlock() is used for this check, rather than834 // getUniqueExitBlock() to ensure loops with mulitple exit edges are835 // disallowed.836 if (!L->getExitBlock()) {837 LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; only loops with single exit "838 "blocks can be unrolled and jammed.\n");839 return false;840 }841 842 // Only loops with a single exiting block can be unrolled and jammed.843 if (!L->getExitingBlock()) {844 LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; only loops with single "845 "exiting blocks can be unrolled and jammed.\n");846 return false;847 }848 849 L = L->getSubLoops()[0];850 } while (L);851 852 return true;853}854 855static Loop *getInnerMostLoop(Loop *L) {856 while (!L->getSubLoops().empty())857 L = L->getSubLoops()[0];858 return L;859}860 861bool llvm::isSafeToUnrollAndJam(Loop *L, ScalarEvolution &SE, DominatorTree &DT,862 DependenceInfo &DI, LoopInfo &LI) {863 if (!isEligibleLoopForm(*L)) {864 LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; Ineligible loop form\n");865 return false;866 }867 868 /* We currently handle outer loops like this:869 |870 ForeFirst <------\ }871 Blocks | } ForeBlocks of L872 ForeLast | }873 | |874 ... |875 | |876 ForeFirst <----\ | }877 Blocks | | } ForeBlocks of a inner loop of L878 ForeLast | | }879 | | |880 JamLoopFirst <\ | | }881 Blocks | | | } JamLoopBlocks of the innermost loop882 JamLoopLast -/ | | }883 | | |884 AftFirst | | }885 Blocks | | } AftBlocks of a inner loop of L886 AftLast ------/ | }887 | |888 ... |889 | |890 AftFirst | }891 Blocks | } AftBlocks of L892 AftLast --------/ }893 |894 895 There are (theoretically) any number of blocks in ForeBlocks, SubLoopBlocks896 and AftBlocks, providing that there is one edge from Fores to SubLoops,897 one edge from SubLoops to Afts and a single outer loop exit (from Afts).898 In practice we currently limit Aft blocks to a single block, and limit899 things further in the profitablility checks of the unroll and jam pass.900 901 Because of the way we rearrange basic blocks, we also require that902 the Fore blocks of L on all unrolled iterations are safe to move before the903 blocks of the direct child of L of all iterations. So we require that the904 phi node looping operands of ForeHeader can be moved to at least the end of905 ForeEnd, so that we can arrange cloned Fore Blocks before the subloop and906 match up Phi's correctly.907 908 i.e. The old order of blocks used to be909 (F1)1 (F2)1 J1_1 J1_2 (A2)1 (A1)1 (F1)2 (F2)2 J2_1 J2_2 (A2)2 (A1)2.910 It needs to be safe to transform this to911 (F1)1 (F1)2 (F2)1 (F2)2 J1_1 J1_2 J2_1 J2_2 (A2)1 (A2)2 (A1)1 (A1)2.912 913 There are then a number of checks along the lines of no calls, no914 exceptions, inner loop IV is consistent, etc. Note that for loops requiring915 runtime unrolling, UnrollRuntimeLoopRemainder can also fail in916 UnrollAndJamLoop if the trip count cannot be easily calculated.917 */918 919 // Split blocks into Fore/SubLoop/Aft based on dominators920 Loop *JamLoop = getInnerMostLoop(L);921 BasicBlockSet SubLoopBlocks;922 DenseMap<Loop *, BasicBlockSet> ForeBlocksMap;923 DenseMap<Loop *, BasicBlockSet> AftBlocksMap;924 if (!partitionOuterLoopBlocks(*L, *JamLoop, SubLoopBlocks, ForeBlocksMap,925 AftBlocksMap, DT)) {926 LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; Incompatible loop layout\n");927 return false;928 }929 930 // Aft blocks may need to move instructions to fore blocks, which becomes more931 // difficult if there are multiple (potentially conditionally executed)932 // blocks. For now we just exclude loops with multiple aft blocks.933 if (AftBlocksMap[L].size() != 1) {934 LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; Can't currently handle "935 "multiple blocks after the loop\n");936 return false;937 }938 939 // Check inner loop backedge count is consistent on all iterations of the940 // outer loop941 if (any_of(L->getLoopsInPreorder(), [&SE](Loop *SubLoop) {942 return !hasIterationCountInvariantInParent(SubLoop, SE);943 })) {944 LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; Inner loop iteration count is "945 "not consistent on each iteration\n");946 return false;947 }948 949 // Check the loop safety info for exceptions.950 SimpleLoopSafetyInfo LSI;951 LSI.computeLoopSafetyInfo(L);952 if (LSI.anyBlockMayThrow()) {953 LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; Something may throw\n");954 return false;955 }956 957 // We've ruled out the easy stuff and now need to check that there are no958 // interdependencies which may prevent us from moving the:959 // ForeBlocks before Subloop and AftBlocks.960 // Subloop before AftBlocks.961 // ForeBlock phi operands before the subloop962 963 // Make sure we can move all instructions we need to before the subloop964 BasicBlock *Header = L->getHeader();965 BasicBlock *Latch = L->getLoopLatch();966 BasicBlockSet AftBlocks = AftBlocksMap[L];967 Loop *SubLoop = L->getSubLoops()[0];968 if (!processHeaderPhiOperands(969 Header, Latch, AftBlocks, [&AftBlocks, &SubLoop](Instruction *I) {970 if (SubLoop->contains(I->getParent()))971 return false;972 if (AftBlocks.count(I->getParent())) {973 // If we hit a phi node in afts we know we are done (probably974 // LCSSA)975 if (isa<PHINode>(I))976 return false;977 // Can't move instructions with side effects or memory978 // reads/writes979 if (I->mayHaveSideEffects() || I->mayReadOrWriteMemory())980 return false;981 }982 // Keep going983 return true;984 })) {985 LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; can't move required "986 "instructions after subloop to before it\n");987 return false;988 }989 990 // Check for memory dependencies which prohibit the unrolling we are doing.991 // Because of the way we are unrolling Fore/Sub/Aft blocks, we need to check992 // there are no dependencies between Fore-Sub, Fore-Aft, Sub-Aft and Sub-Sub.993 if (!checkDependencies(*L, SubLoopBlocks, ForeBlocksMap, AftBlocksMap, DI,994 LI)) {995 LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; failed dependency check\n");996 return false;997 }998 999 return true;1000}1001