2175 lines · cpp
1//===- LoopFuse.cpp - Loop Fusion Pass ------------------------------------===//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/// \file10/// This file implements the loop fusion pass.11/// The implementation is largely based on the following document:12///13/// Code Transformations to Augment the Scope of Loop Fusion in a14/// Production Compiler15/// Christopher Mark Barton16/// MSc Thesis17/// https://webdocs.cs.ualberta.ca/~amaral/thesis/ChristopherBartonMSc.pdf18///19/// The general approach taken is to collect sets of control flow equivalent20/// loops and test whether they can be fused. The necessary conditions for21/// fusion are:22/// 1. The loops must be adjacent (there cannot be any statements between23/// the two loops).24/// 2. The loops must be conforming (they must execute the same number of25/// iterations).26/// 3. The loops must be control flow equivalent (if one loop executes, the27/// other is guaranteed to execute).28/// 4. There cannot be any negative distance dependencies between the loops.29/// If all of these conditions are satisfied, it is safe to fuse the loops.30///31/// This implementation creates FusionCandidates that represent the loop and the32/// necessary information needed by fusion. It then operates on the fusion33/// candidates, first confirming that the candidate is eligible for fusion. The34/// candidates are then collected into control flow equivalent sets, sorted in35/// dominance order. Each set of control flow equivalent candidates is then36/// traversed, attempting to fuse pairs of candidates in the set. If all37/// requirements for fusion are met, the two candidates are fused, creating a38/// new (fused) candidate which is then added back into the set to consider for39/// additional fusion.40///41/// This implementation currently does not make any modifications to remove42/// conditions for fusion. Code transformations to make loops conform to each of43/// the conditions for fusion are discussed in more detail in the document44/// above. These can be added to the current implementation in the future.45//===----------------------------------------------------------------------===//46 47#include "llvm/Transforms/Scalar/LoopFuse.h"48#include "llvm/ADT/Statistic.h"49#include "llvm/Analysis/AssumptionCache.h"50#include "llvm/Analysis/DependenceAnalysis.h"51#include "llvm/Analysis/DomTreeUpdater.h"52#include "llvm/Analysis/LoopInfo.h"53#include "llvm/Analysis/OptimizationRemarkEmitter.h"54#include "llvm/Analysis/PostDominators.h"55#include "llvm/Analysis/ScalarEvolution.h"56#include "llvm/Analysis/ScalarEvolutionExpressions.h"57#include "llvm/Analysis/TargetTransformInfo.h"58#include "llvm/IR/Function.h"59#include "llvm/IR/Verifier.h"60#include "llvm/Support/CommandLine.h"61#include "llvm/Support/Debug.h"62#include "llvm/Support/raw_ostream.h"63#include "llvm/Transforms/Utils/BasicBlockUtils.h"64#include "llvm/Transforms/Utils/CodeMoverUtils.h"65#include "llvm/Transforms/Utils/LoopPeel.h"66#include "llvm/Transforms/Utils/LoopSimplify.h"67 68using namespace llvm;69 70#define DEBUG_TYPE "loop-fusion"71 72STATISTIC(FuseCounter, "Loops fused");73STATISTIC(NumFusionCandidates, "Number of candidates for loop fusion");74STATISTIC(InvalidPreheader, "Loop has invalid preheader");75STATISTIC(InvalidHeader, "Loop has invalid header");76STATISTIC(InvalidExitingBlock, "Loop has invalid exiting blocks");77STATISTIC(InvalidExitBlock, "Loop has invalid exit block");78STATISTIC(InvalidLatch, "Loop has invalid latch");79STATISTIC(InvalidLoop, "Loop is invalid");80STATISTIC(AddressTakenBB, "Basic block has address taken");81STATISTIC(MayThrowException, "Loop may throw an exception");82STATISTIC(ContainsVolatileAccess, "Loop contains a volatile access");83STATISTIC(NotSimplifiedForm, "Loop is not in simplified form");84STATISTIC(InvalidDependencies, "Dependencies prevent fusion");85STATISTIC(UnknownTripCount, "Loop has unknown trip count");86STATISTIC(UncomputableTripCount, "SCEV cannot compute trip count of loop");87STATISTIC(NonEqualTripCount, "Loop trip counts are not the same");88STATISTIC(NonAdjacent, "Loops are not adjacent");89STATISTIC(90 NonEmptyPreheader,91 "Loop has a non-empty preheader with instructions that cannot be moved");92STATISTIC(FusionNotBeneficial, "Fusion is not beneficial");93STATISTIC(NonIdenticalGuards, "Candidates have different guards");94STATISTIC(NonEmptyExitBlock, "Candidate has a non-empty exit block with "95 "instructions that cannot be moved");96STATISTIC(NonEmptyGuardBlock, "Candidate has a non-empty guard block with "97 "instructions that cannot be moved");98STATISTIC(NotRotated, "Candidate is not rotated");99STATISTIC(OnlySecondCandidateIsGuarded,100 "The second candidate is guarded while the first one is not");101STATISTIC(NumHoistedInsts, "Number of hoisted preheader instructions.");102STATISTIC(NumSunkInsts, "Number of hoisted preheader instructions.");103STATISTIC(NumDA, "DA checks passed");104 105enum FusionDependenceAnalysisChoice {106 FUSION_DEPENDENCE_ANALYSIS_SCEV,107 FUSION_DEPENDENCE_ANALYSIS_DA,108 FUSION_DEPENDENCE_ANALYSIS_ALL,109};110 111static cl::opt<FusionDependenceAnalysisChoice> FusionDependenceAnalysis(112 "loop-fusion-dependence-analysis",113 cl::desc("Which dependence analysis should loop fusion use?"),114 cl::values(clEnumValN(FUSION_DEPENDENCE_ANALYSIS_SCEV, "scev",115 "Use the scalar evolution interface"),116 clEnumValN(FUSION_DEPENDENCE_ANALYSIS_DA, "da",117 "Use the dependence analysis interface"),118 clEnumValN(FUSION_DEPENDENCE_ANALYSIS_ALL, "all",119 "Use all available analyses")),120 cl::Hidden, cl::init(FUSION_DEPENDENCE_ANALYSIS_ALL));121 122static cl::opt<unsigned> FusionPeelMaxCount(123 "loop-fusion-peel-max-count", cl::init(0), cl::Hidden,124 cl::desc("Max number of iterations to be peeled from a loop, such that "125 "fusion can take place"));126 127#ifndef NDEBUG128static cl::opt<bool>129 VerboseFusionDebugging("loop-fusion-verbose-debug",130 cl::desc("Enable verbose debugging for Loop Fusion"),131 cl::Hidden, cl::init(false));132#endif133 134namespace {135/// This class is used to represent a candidate for loop fusion. When it is136/// constructed, it checks the conditions for loop fusion to ensure that it137/// represents a valid candidate. It caches several parts of a loop that are138/// used throughout loop fusion (e.g., loop preheader, loop header, etc) instead139/// of continually querying the underlying Loop to retrieve these values. It is140/// assumed these will not change throughout loop fusion.141///142/// The invalidate method should be used to indicate that the FusionCandidate is143/// no longer a valid candidate for fusion. Similarly, the isValid() method can144/// be used to ensure that the FusionCandidate is still valid for fusion.145struct FusionCandidate {146 /// Cache of parts of the loop used throughout loop fusion. These should not147 /// need to change throughout the analysis and transformation.148 /// These parts are cached to avoid repeatedly looking up in the Loop class.149 150 /// Preheader of the loop this candidate represents151 BasicBlock *Preheader;152 /// Header of the loop this candidate represents153 BasicBlock *Header;154 /// Blocks in the loop that exit the loop155 BasicBlock *ExitingBlock;156 /// The successor block of this loop (where the exiting blocks go to)157 BasicBlock *ExitBlock;158 /// Latch of the loop159 BasicBlock *Latch;160 /// The loop that this fusion candidate represents161 Loop *L;162 /// Vector of instructions in this loop that read from memory163 SmallVector<Instruction *, 16> MemReads;164 /// Vector of instructions in this loop that write to memory165 SmallVector<Instruction *, 16> MemWrites;166 /// Are all of the members of this fusion candidate still valid167 bool Valid;168 /// Guard branch of the loop, if it exists169 BranchInst *GuardBranch;170 /// Peeling Paramaters of the Loop.171 TTI::PeelingPreferences PP;172 /// Can you Peel this Loop?173 bool AbleToPeel;174 /// Has this loop been Peeled175 bool Peeled;176 177 /// Dominator and PostDominator trees are needed for the178 /// FusionCandidateCompare function, required by FusionCandidateSet to179 /// determine where the FusionCandidate should be inserted into the set. These180 /// are used to establish ordering of the FusionCandidates based on dominance.181 DominatorTree &DT;182 const PostDominatorTree *PDT;183 184 OptimizationRemarkEmitter &ORE;185 186 FusionCandidate(Loop *L, DominatorTree &DT, const PostDominatorTree *PDT,187 OptimizationRemarkEmitter &ORE, TTI::PeelingPreferences PP)188 : Preheader(L->getLoopPreheader()), Header(L->getHeader()),189 ExitingBlock(L->getExitingBlock()), ExitBlock(L->getExitBlock()),190 Latch(L->getLoopLatch()), L(L), Valid(true),191 GuardBranch(L->getLoopGuardBranch()), PP(PP), AbleToPeel(canPeel(L)),192 Peeled(false), DT(DT), PDT(PDT), ORE(ORE) {193 194 // Walk over all blocks in the loop and check for conditions that may195 // prevent fusion. For each block, walk over all instructions and collect196 // the memory reads and writes If any instructions that prevent fusion are197 // found, invalidate this object and return.198 for (BasicBlock *BB : L->blocks()) {199 if (BB->hasAddressTaken()) {200 invalidate();201 reportInvalidCandidate(AddressTakenBB);202 return;203 }204 205 for (Instruction &I : *BB) {206 if (I.mayThrow()) {207 invalidate();208 reportInvalidCandidate(MayThrowException);209 return;210 }211 if (StoreInst *SI = dyn_cast<StoreInst>(&I)) {212 if (SI->isVolatile()) {213 invalidate();214 reportInvalidCandidate(ContainsVolatileAccess);215 return;216 }217 }218 if (LoadInst *LI = dyn_cast<LoadInst>(&I)) {219 if (LI->isVolatile()) {220 invalidate();221 reportInvalidCandidate(ContainsVolatileAccess);222 return;223 }224 }225 if (I.mayWriteToMemory())226 MemWrites.push_back(&I);227 if (I.mayReadFromMemory())228 MemReads.push_back(&I);229 }230 }231 }232 233 /// Check if all members of the class are valid.234 bool isValid() const {235 return Preheader && Header && ExitingBlock && ExitBlock && Latch && L &&236 !L->isInvalid() && Valid;237 }238 239 /// Verify that all members are in sync with the Loop object.240 void verify() const {241 assert(isValid() && "Candidate is not valid!!");242 assert(!L->isInvalid() && "Loop is invalid!");243 assert(Preheader == L->getLoopPreheader() && "Preheader is out of sync");244 assert(Header == L->getHeader() && "Header is out of sync");245 assert(ExitingBlock == L->getExitingBlock() &&246 "Exiting Blocks is out of sync");247 assert(ExitBlock == L->getExitBlock() && "Exit block is out of sync");248 assert(Latch == L->getLoopLatch() && "Latch is out of sync");249 }250 251 /// Get the entry block for this fusion candidate.252 ///253 /// If this fusion candidate represents a guarded loop, the entry block is the254 /// loop guard block. If it represents an unguarded loop, the entry block is255 /// the preheader of the loop.256 BasicBlock *getEntryBlock() const {257 if (GuardBranch)258 return GuardBranch->getParent();259 else260 return Preheader;261 }262 263 /// After Peeling the loop is modified quite a bit, hence all of the Blocks264 /// need to be updated accordingly.265 void updateAfterPeeling() {266 Preheader = L->getLoopPreheader();267 Header = L->getHeader();268 ExitingBlock = L->getExitingBlock();269 ExitBlock = L->getExitBlock();270 Latch = L->getLoopLatch();271 verify();272 }273 274 /// Given a guarded loop, get the successor of the guard that is not in the275 /// loop.276 ///277 /// This method returns the successor of the loop guard that is not located278 /// within the loop (i.e., the successor of the guard that is not the279 /// preheader).280 /// This method is only valid for guarded loops.281 BasicBlock *getNonLoopBlock() const {282 assert(GuardBranch && "Only valid on guarded loops.");283 assert(GuardBranch->isConditional() &&284 "Expecting guard to be a conditional branch.");285 if (Peeled)286 return GuardBranch->getSuccessor(1);287 return (GuardBranch->getSuccessor(0) == Preheader)288 ? GuardBranch->getSuccessor(1)289 : GuardBranch->getSuccessor(0);290 }291 292#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)293 LLVM_DUMP_METHOD void dump() const {294 dbgs() << "\tGuardBranch: ";295 if (GuardBranch)296 dbgs() << *GuardBranch;297 else298 dbgs() << "nullptr";299 dbgs() << "\n"300 << (GuardBranch ? GuardBranch->getName() : "nullptr") << "\n"301 << "\tPreheader: " << (Preheader ? Preheader->getName() : "nullptr")302 << "\n"303 << "\tHeader: " << (Header ? Header->getName() : "nullptr") << "\n"304 << "\tExitingBB: "305 << (ExitingBlock ? ExitingBlock->getName() : "nullptr") << "\n"306 << "\tExitBB: " << (ExitBlock ? ExitBlock->getName() : "nullptr")307 << "\n"308 << "\tLatch: " << (Latch ? Latch->getName() : "nullptr") << "\n"309 << "\tEntryBlock: "310 << (getEntryBlock() ? getEntryBlock()->getName() : "nullptr")311 << "\n";312 }313#endif314 315 /// Determine if a fusion candidate (representing a loop) is eligible for316 /// fusion. Note that this only checks whether a single loop can be fused - it317 /// does not check whether it is *legal* to fuse two loops together.318 bool isEligibleForFusion(ScalarEvolution &SE) const {319 if (!isValid()) {320 LLVM_DEBUG(dbgs() << "FC has invalid CFG requirements!\n");321 if (!Preheader)322 ++InvalidPreheader;323 if (!Header)324 ++InvalidHeader;325 if (!ExitingBlock)326 ++InvalidExitingBlock;327 if (!ExitBlock)328 ++InvalidExitBlock;329 if (!Latch)330 ++InvalidLatch;331 if (L->isInvalid())332 ++InvalidLoop;333 334 return false;335 }336 337 // Require ScalarEvolution to be able to determine a trip count.338 if (!SE.hasLoopInvariantBackedgeTakenCount(L)) {339 LLVM_DEBUG(dbgs() << "Loop " << L->getName()340 << " trip count not computable!\n");341 return reportInvalidCandidate(UnknownTripCount);342 }343 344 if (!L->isLoopSimplifyForm()) {345 LLVM_DEBUG(dbgs() << "Loop " << L->getName()346 << " is not in simplified form!\n");347 return reportInvalidCandidate(NotSimplifiedForm);348 }349 350 if (!L->isRotatedForm()) {351 LLVM_DEBUG(dbgs() << "Loop " << L->getName() << " is not rotated!\n");352 return reportInvalidCandidate(NotRotated);353 }354 355 return true;356 }357 358private:359 // This is only used internally for now, to clear the MemWrites and MemReads360 // list and setting Valid to false. I can't envision other uses of this right361 // now, since once FusionCandidates are put into the FusionCandidateSet they362 // are immutable. Thus, any time we need to change/update a FusionCandidate,363 // we must create a new one and insert it into the FusionCandidateSet to364 // ensure the FusionCandidateSet remains ordered correctly.365 void invalidate() {366 MemWrites.clear();367 MemReads.clear();368 Valid = false;369 }370 371 bool reportInvalidCandidate(Statistic &Stat) const {372 using namespace ore;373 assert(L && Preheader && "Fusion candidate not initialized properly!");374#if LLVM_ENABLE_STATS375 ++Stat;376 ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE, Stat.getName(),377 L->getStartLoc(), Preheader)378 << "[" << Preheader->getParent()->getName() << "]: "379 << "Loop is not a candidate for fusion: " << Stat.getDesc());380#endif381 return false;382 }383};384 385struct FusionCandidateCompare {386 /// Comparison functor to sort two Control Flow Equivalent fusion candidates387 /// into dominance order.388 /// If LHS dominates RHS and RHS post-dominates LHS, return true;389 /// If RHS dominates LHS and LHS post-dominates RHS, return false;390 /// If both LHS and RHS are not dominating each other then, non-strictly391 /// post dominate check will decide the order of candidates. If RHS392 /// non-strictly post dominates LHS then, return true. If LHS non-strictly393 /// post dominates RHS then, return false. If both are non-strictly post394 /// dominate each other then, level in the post dominator tree will decide395 /// the order of candidates.396 bool operator()(const FusionCandidate &LHS,397 const FusionCandidate &RHS) const {398 const DominatorTree *DT = &(LHS.DT);399 400 BasicBlock *LHSEntryBlock = LHS.getEntryBlock();401 BasicBlock *RHSEntryBlock = RHS.getEntryBlock();402 403 // Do not save PDT to local variable as it is only used in asserts and thus404 // will trigger an unused variable warning if building without asserts.405 assert(DT && LHS.PDT && "Expecting valid dominator tree");406 407 // Do this compare first so if LHS == RHS, function returns false.408 if (DT->dominates(RHSEntryBlock, LHSEntryBlock)) {409 // RHS dominates LHS410 // Verify LHS post-dominates RHS411 assert(LHS.PDT->dominates(LHSEntryBlock, RHSEntryBlock));412 return false;413 }414 415 if (DT->dominates(LHSEntryBlock, RHSEntryBlock)) {416 // Verify RHS Postdominates LHS417 assert(LHS.PDT->dominates(RHSEntryBlock, LHSEntryBlock));418 return true;419 }420 421 // If two FusionCandidates are in the same level of dominator tree,422 // they will not dominate each other, but may still be control flow423 // equivalent. To sort those FusionCandidates, nonStrictlyPostDominate()424 // function is needed.425 bool WrongOrder =426 nonStrictlyPostDominate(LHSEntryBlock, RHSEntryBlock, DT, LHS.PDT);427 bool RightOrder =428 nonStrictlyPostDominate(RHSEntryBlock, LHSEntryBlock, DT, LHS.PDT);429 if (WrongOrder && RightOrder) {430 // If common predecessor of LHS and RHS post dominates both431 // FusionCandidates then, Order of FusionCandidate can be432 // identified by its level in post dominator tree.433 DomTreeNode *LNode = LHS.PDT->getNode(LHSEntryBlock);434 DomTreeNode *RNode = LHS.PDT->getNode(RHSEntryBlock);435 return LNode->getLevel() > RNode->getLevel();436 } else if (WrongOrder)437 return false;438 else if (RightOrder)439 return true;440 441 // If LHS does not non-strict Postdominate RHS and RHS does not non-strict442 // Postdominate LHS then, there is no dominance relationship between the443 // two FusionCandidates. Thus, they should not be in the same set together.444 llvm_unreachable(445 "No dominance relationship between these fusion candidates!");446 }447};448} // namespace449 450using LoopVector = SmallVector<Loop *, 4>;451 452// Set of Control Flow Equivalent (CFE) Fusion Candidates, sorted in dominance453// order. Thus, if FC0 comes *before* FC1 in a FusionCandidateSet, then FC0454// dominates FC1 and FC1 post-dominates FC0.455// std::set was chosen because we want a sorted data structure with stable456// iterators. A subsequent patch to loop fusion will enable fusing non-adjacent457// loops by moving intervening code around. When this intervening code contains458// loops, those loops will be moved also. The corresponding FusionCandidates459// will also need to be moved accordingly. As this is done, having stable460// iterators will simplify the logic. Similarly, having an efficient insert that461// keeps the FusionCandidateSet sorted will also simplify the implementation.462using FusionCandidateSet = std::set<FusionCandidate, FusionCandidateCompare>;463using FusionCandidateCollection = SmallVector<FusionCandidateSet, 4>;464 465#ifndef NDEBUG466static void printLoopVector(const LoopVector &LV) {467 dbgs() << "****************************\n";468 for (const Loop *L : LV)469 printLoop(*L, dbgs());470 dbgs() << "****************************\n";471}472 473static raw_ostream &operator<<(raw_ostream &OS, const FusionCandidate &FC) {474 if (FC.isValid())475 OS << FC.Preheader->getName();476 else477 OS << "<Invalid>";478 479 return OS;480}481 482static raw_ostream &operator<<(raw_ostream &OS,483 const FusionCandidateSet &CandSet) {484 for (const FusionCandidate &FC : CandSet)485 OS << FC << '\n';486 487 return OS;488}489 490static void491printFusionCandidates(const FusionCandidateCollection &FusionCandidates) {492 dbgs() << "Fusion Candidates: \n";493 for (const auto &CandidateSet : FusionCandidates) {494 dbgs() << "*** Fusion Candidate Set ***\n";495 dbgs() << CandidateSet;496 dbgs() << "****************************\n";497 }498}499#endif // NDEBUG500 501namespace {502 503/// Collect all loops in function at the same nest level, starting at the504/// outermost level.505///506/// This data structure collects all loops at the same nest level for a507/// given function (specified by the LoopInfo object). It starts at the508/// outermost level.509struct LoopDepthTree {510 using LoopsOnLevelTy = SmallVector<LoopVector, 4>;511 using iterator = LoopsOnLevelTy::iterator;512 using const_iterator = LoopsOnLevelTy::const_iterator;513 514 LoopDepthTree(LoopInfo &LI) : Depth(1) {515 if (!LI.empty())516 LoopsOnLevel.emplace_back(LoopVector(LI.rbegin(), LI.rend()));517 }518 519 /// Test whether a given loop has been removed from the function, and thus is520 /// no longer valid.521 bool isRemovedLoop(const Loop *L) const { return RemovedLoops.count(L); }522 523 /// Record that a given loop has been removed from the function and is no524 /// longer valid.525 void removeLoop(const Loop *L) { RemovedLoops.insert(L); }526 527 /// Descend the tree to the next (inner) nesting level528 void descend() {529 LoopsOnLevelTy LoopsOnNextLevel;530 531 for (const LoopVector &LV : *this)532 for (Loop *L : LV)533 if (!isRemovedLoop(L) && L->begin() != L->end())534 LoopsOnNextLevel.emplace_back(LoopVector(L->begin(), L->end()));535 536 LoopsOnLevel = LoopsOnNextLevel;537 RemovedLoops.clear();538 Depth++;539 }540 541 bool empty() const { return size() == 0; }542 size_t size() const { return LoopsOnLevel.size() - RemovedLoops.size(); }543 unsigned getDepth() const { return Depth; }544 545 iterator begin() { return LoopsOnLevel.begin(); }546 iterator end() { return LoopsOnLevel.end(); }547 const_iterator begin() const { return LoopsOnLevel.begin(); }548 const_iterator end() const { return LoopsOnLevel.end(); }549 550private:551 /// Set of loops that have been removed from the function and are no longer552 /// valid.553 SmallPtrSet<const Loop *, 8> RemovedLoops;554 555 /// Depth of the current level, starting at 1 (outermost loops).556 unsigned Depth;557 558 /// Vector of loops at the current depth level that have the same parent loop559 LoopsOnLevelTy LoopsOnLevel;560};561 562struct LoopFuser {563private:564 // Sets of control flow equivalent fusion candidates for a given nest level.565 FusionCandidateCollection FusionCandidates;566 567 LoopDepthTree LDT;568 DomTreeUpdater DTU;569 570 LoopInfo &LI;571 DominatorTree &DT;572 DependenceInfo &DI;573 ScalarEvolution &SE;574 PostDominatorTree &PDT;575 OptimizationRemarkEmitter &ORE;576 AssumptionCache &AC;577 const TargetTransformInfo &TTI;578 579public:580 LoopFuser(LoopInfo &LI, DominatorTree &DT, DependenceInfo &DI,581 ScalarEvolution &SE, PostDominatorTree &PDT,582 OptimizationRemarkEmitter &ORE, const DataLayout &DL,583 AssumptionCache &AC, const TargetTransformInfo &TTI)584 : LDT(LI), DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy), LI(LI),585 DT(DT), DI(DI), SE(SE), PDT(PDT), ORE(ORE), AC(AC), TTI(TTI) {}586 587 /// This is the main entry point for loop fusion. It will traverse the588 /// specified function and collect candidate loops to fuse, starting at the589 /// outermost nesting level and working inwards.590 bool fuseLoops(Function &F) {591#ifndef NDEBUG592 if (VerboseFusionDebugging) {593 LI.print(dbgs());594 }595#endif596 597 LLVM_DEBUG(dbgs() << "Performing Loop Fusion on function " << F.getName()598 << "\n");599 bool Changed = false;600 601 while (!LDT.empty()) {602 LLVM_DEBUG(dbgs() << "Got " << LDT.size() << " loop sets for depth "603 << LDT.getDepth() << "\n";);604 605 for (const LoopVector &LV : LDT) {606 assert(LV.size() > 0 && "Empty loop set was build!");607 608 // Skip singleton loop sets as they do not offer fusion opportunities on609 // this level.610 if (LV.size() == 1)611 continue;612#ifndef NDEBUG613 if (VerboseFusionDebugging) {614 LLVM_DEBUG({615 dbgs() << " Visit loop set (#" << LV.size() << "):\n";616 printLoopVector(LV);617 });618 }619#endif620 621 collectFusionCandidates(LV);622 Changed |= fuseCandidates();623 }624 625 // Finished analyzing candidates at this level.626 // Descend to the next level and clear all of the candidates currently627 // collected. Note that it will not be possible to fuse any of the628 // existing candidates with new candidates because the new candidates will629 // be at a different nest level and thus not be control flow equivalent630 // with all of the candidates collected so far.631 LLVM_DEBUG(dbgs() << "Descend one level!\n");632 LDT.descend();633 FusionCandidates.clear();634 }635 636 if (Changed)637 LLVM_DEBUG(dbgs() << "Function after Loop Fusion: \n"; F.dump(););638 639#ifndef NDEBUG640 assert(DT.verify());641 assert(PDT.verify());642 LI.verify(DT);643 SE.verify();644#endif645 646 LLVM_DEBUG(dbgs() << "Loop Fusion complete\n");647 return Changed;648 }649 650private:651 /// Determine if two fusion candidates are control flow equivalent.652 ///653 /// Two fusion candidates are control flow equivalent if when one executes,654 /// the other is guaranteed to execute. This is determined using dominators655 /// and post-dominators: if A dominates B and B post-dominates A then A and B656 /// are control-flow equivalent.657 bool isControlFlowEquivalent(const FusionCandidate &FC0,658 const FusionCandidate &FC1) const {659 assert(FC0.Preheader && FC1.Preheader && "Expecting valid preheaders");660 661 return ::isControlFlowEquivalent(*FC0.getEntryBlock(), *FC1.getEntryBlock(),662 DT, PDT);663 }664 665 /// Iterate over all loops in the given loop set and identify the loops that666 /// are eligible for fusion. Place all eligible fusion candidates into Control667 /// Flow Equivalent sets, sorted by dominance.668 void collectFusionCandidates(const LoopVector &LV) {669 for (Loop *L : LV) {670 TTI::PeelingPreferences PP =671 gatherPeelingPreferences(L, SE, TTI, std::nullopt, std::nullopt);672 FusionCandidate CurrCand(L, DT, &PDT, ORE, PP);673 if (!CurrCand.isEligibleForFusion(SE))674 continue;675 676 // Go through each list in FusionCandidates and determine if L is control677 // flow equivalent with the first loop in that list. If it is, append LV.678 // If not, go to the next list.679 // If no suitable list is found, start another list and add it to680 // FusionCandidates.681 bool FoundSet = false;682 683 for (auto &CurrCandSet : FusionCandidates) {684 if (isControlFlowEquivalent(*CurrCandSet.begin(), CurrCand)) {685 CurrCandSet.insert(CurrCand);686 FoundSet = true;687#ifndef NDEBUG688 if (VerboseFusionDebugging)689 LLVM_DEBUG(dbgs() << "Adding " << CurrCand690 << " to existing candidate set\n");691#endif692 break;693 }694 }695 if (!FoundSet) {696 // No set was found. Create a new set and add to FusionCandidates697#ifndef NDEBUG698 if (VerboseFusionDebugging)699 LLVM_DEBUG(dbgs() << "Adding " << CurrCand << " to new set\n");700#endif701 FusionCandidateSet NewCandSet;702 NewCandSet.insert(CurrCand);703 FusionCandidates.push_back(NewCandSet);704 }705 NumFusionCandidates++;706 }707 }708 709 /// Determine if it is beneficial to fuse two loops.710 ///711 /// For now, this method simply returns true because we want to fuse as much712 /// as possible (primarily to test the pass). This method will evolve, over713 /// time, to add heuristics for profitability of fusion.714 bool isBeneficialFusion(const FusionCandidate &FC0,715 const FusionCandidate &FC1) {716 return true;717 }718 719 /// Determine if two fusion candidates have the same trip count (i.e., they720 /// execute the same number of iterations).721 ///722 /// This function will return a pair of values. The first is a boolean,723 /// stating whether or not the two candidates are known at compile time to724 /// have the same TripCount. The second is the difference in the two725 /// TripCounts. This information can be used later to determine whether or not726 /// peeling can be performed on either one of the candidates.727 std::pair<bool, std::optional<unsigned>>728 haveIdenticalTripCounts(const FusionCandidate &FC0,729 const FusionCandidate &FC1) const {730 const SCEV *TripCount0 = SE.getBackedgeTakenCount(FC0.L);731 if (isa<SCEVCouldNotCompute>(TripCount0)) {732 UncomputableTripCount++;733 LLVM_DEBUG(dbgs() << "Trip count of first loop could not be computed!");734 return {false, std::nullopt};735 }736 737 const SCEV *TripCount1 = SE.getBackedgeTakenCount(FC1.L);738 if (isa<SCEVCouldNotCompute>(TripCount1)) {739 UncomputableTripCount++;740 LLVM_DEBUG(dbgs() << "Trip count of second loop could not be computed!");741 return {false, std::nullopt};742 }743 744 LLVM_DEBUG(dbgs() << "\tTrip counts: " << *TripCount0 << " & "745 << *TripCount1 << " are "746 << (TripCount0 == TripCount1 ? "identical" : "different")747 << "\n");748 749 if (TripCount0 == TripCount1)750 return {true, 0};751 752 LLVM_DEBUG(dbgs() << "The loops do not have the same tripcount, "753 "determining the difference between trip counts\n");754 755 // Currently only considering loops with a single exit point756 // and a non-constant trip count.757 const unsigned TC0 = SE.getSmallConstantTripCount(FC0.L);758 const unsigned TC1 = SE.getSmallConstantTripCount(FC1.L);759 760 // If any of the tripcounts are zero that means that loop(s) do not have761 // a single exit or a constant tripcount.762 if (TC0 == 0 || TC1 == 0) {763 LLVM_DEBUG(dbgs() << "Loop(s) do not have a single exit point or do not "764 "have a constant number of iterations. Peeling "765 "is not benefical\n");766 return {false, std::nullopt};767 }768 769 std::optional<unsigned> Difference;770 int Diff = TC0 - TC1;771 772 if (Diff > 0)773 Difference = Diff;774 else {775 LLVM_DEBUG(776 dbgs() << "Difference is less than 0. FC1 (second loop) has more "777 "iterations than the first one. Currently not supported\n");778 }779 780 LLVM_DEBUG(dbgs() << "Difference in loop trip count is: " << Difference781 << "\n");782 783 return {false, Difference};784 }785 786 void peelFusionCandidate(FusionCandidate &FC0, const FusionCandidate &FC1,787 unsigned PeelCount) {788 assert(FC0.AbleToPeel && "Should be able to peel loop");789 790 LLVM_DEBUG(dbgs() << "Attempting to peel first " << PeelCount791 << " iterations of the first loop. \n");792 793 ValueToValueMapTy VMap;794 FC0.Peeled =795 peelLoop(FC0.L, PeelCount, false, &LI, &SE, DT, &AC, true, VMap);796 if (FC0.Peeled) {797 LLVM_DEBUG(dbgs() << "Done Peeling\n");798 799#ifndef NDEBUG800 auto IdenticalTripCount = haveIdenticalTripCounts(FC0, FC1);801 802 assert(IdenticalTripCount.first && *IdenticalTripCount.second == 0 &&803 "Loops should have identical trip counts after peeling");804#endif805 806 FC0.PP.PeelCount += PeelCount;807 808 // Peeling does not update the PDT809 PDT.recalculate(*FC0.Preheader->getParent());810 811 FC0.updateAfterPeeling();812 813 // In this case the iterations of the loop are constant, so the first814 // loop will execute completely (will not jump from one of815 // the peeled blocks to the second loop). Here we are updating the816 // branch conditions of each of the peeled blocks, such that it will817 // branch to its successor which is not the preheader of the second loop818 // in the case of unguarded loops, or the succesors of the exit block of819 // the first loop otherwise. Doing this update will ensure that the entry820 // block of the first loop dominates the entry block of the second loop.821 BasicBlock *BB =822 FC0.GuardBranch ? FC0.ExitBlock->getUniqueSuccessor() : FC1.Preheader;823 if (BB) {824 SmallVector<DominatorTree::UpdateType, 8> TreeUpdates;825 SmallVector<Instruction *, 8> WorkList;826 for (BasicBlock *Pred : predecessors(BB)) {827 if (Pred != FC0.ExitBlock) {828 WorkList.emplace_back(Pred->getTerminator());829 TreeUpdates.emplace_back(830 DominatorTree::UpdateType(DominatorTree::Delete, Pred, BB));831 }832 }833 // Cannot modify the predecessors inside the above loop as it will cause834 // the iterators to be nullptrs, causing memory errors.835 for (Instruction *CurrentBranch : WorkList) {836 BasicBlock *Succ = CurrentBranch->getSuccessor(0);837 if (Succ == BB)838 Succ = CurrentBranch->getSuccessor(1);839 ReplaceInstWithInst(CurrentBranch, BranchInst::Create(Succ));840 }841 842 DTU.applyUpdates(TreeUpdates);843 DTU.flush();844 }845 LLVM_DEBUG(846 dbgs() << "Sucessfully peeled " << FC0.PP.PeelCount847 << " iterations from the first loop.\n"848 "Both Loops have the same number of iterations now.\n");849 }850 }851 852 /// Walk each set of control flow equivalent fusion candidates and attempt to853 /// fuse them. This does a single linear traversal of all candidates in the854 /// set. The conditions for legal fusion are checked at this point. If a pair855 /// of fusion candidates passes all legality checks, they are fused together856 /// and a new fusion candidate is created and added to the FusionCandidateSet.857 /// The original fusion candidates are then removed, as they are no longer858 /// valid.859 bool fuseCandidates() {860 bool Fused = false;861 LLVM_DEBUG(printFusionCandidates(FusionCandidates));862 for (auto &CandidateSet : FusionCandidates) {863 if (CandidateSet.size() < 2)864 continue;865 866 LLVM_DEBUG(dbgs() << "Attempting fusion on Candidate Set:\n"867 << CandidateSet << "\n");868 869 for (auto FC0 = CandidateSet.begin(); FC0 != CandidateSet.end(); ++FC0) {870 assert(!LDT.isRemovedLoop(FC0->L) &&871 "Should not have removed loops in CandidateSet!");872 auto FC1 = FC0;873 for (++FC1; FC1 != CandidateSet.end(); ++FC1) {874 assert(!LDT.isRemovedLoop(FC1->L) &&875 "Should not have removed loops in CandidateSet!");876 877 LLVM_DEBUG(dbgs() << "Attempting to fuse candidate \n"; FC0->dump();878 dbgs() << " with\n"; FC1->dump(); dbgs() << "\n");879 880 FC0->verify();881 FC1->verify();882 883 // Check if the candidates have identical tripcounts (first value of884 // pair), and if not check the difference in the tripcounts between885 // the loops (second value of pair). The difference is not equal to886 // std::nullopt iff the loops iterate a constant number of times, and887 // have a single exit.888 std::pair<bool, std::optional<unsigned>> IdenticalTripCountRes =889 haveIdenticalTripCounts(*FC0, *FC1);890 bool SameTripCount = IdenticalTripCountRes.first;891 std::optional<unsigned> TCDifference = IdenticalTripCountRes.second;892 893 // Here we are checking that FC0 (the first loop) can be peeled, and894 // both loops have different tripcounts.895 if (FC0->AbleToPeel && !SameTripCount && TCDifference) {896 if (*TCDifference > FusionPeelMaxCount) {897 LLVM_DEBUG(dbgs()898 << "Difference in loop trip counts: " << *TCDifference899 << " is greater than maximum peel count specificed: "900 << FusionPeelMaxCount << "\n");901 } else {902 // Dependent on peeling being performed on the first loop, and903 // assuming all other conditions for fusion return true.904 SameTripCount = true;905 }906 }907 908 if (!SameTripCount) {909 LLVM_DEBUG(dbgs() << "Fusion candidates do not have identical trip "910 "counts. Not fusing.\n");911 reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1,912 NonEqualTripCount);913 continue;914 }915 916 if (!isAdjacent(*FC0, *FC1)) {917 LLVM_DEBUG(dbgs()918 << "Fusion candidates are not adjacent. Not fusing.\n");919 reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1, NonAdjacent);920 continue;921 }922 923 if ((!FC0->GuardBranch && FC1->GuardBranch) ||924 (FC0->GuardBranch && !FC1->GuardBranch)) {925 LLVM_DEBUG(dbgs() << "The one of candidate is guarded while the "926 "another one is not. Not fusing.\n");927 reportLoopFusion<OptimizationRemarkMissed>(928 *FC0, *FC1, OnlySecondCandidateIsGuarded);929 continue;930 }931 932 // Ensure that FC0 and FC1 have identical guards.933 // If one (or both) are not guarded, this check is not necessary.934 if (FC0->GuardBranch && FC1->GuardBranch &&935 !haveIdenticalGuards(*FC0, *FC1) && !TCDifference) {936 LLVM_DEBUG(dbgs() << "Fusion candidates do not have identical "937 "guards. Not Fusing.\n");938 reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1,939 NonIdenticalGuards);940 continue;941 }942 943 if (FC0->GuardBranch) {944 assert(FC1->GuardBranch && "Expecting valid FC1 guard branch");945 946 if (!isSafeToMoveBefore(*FC0->ExitBlock,947 *FC1->ExitBlock->getFirstNonPHIOrDbg(), DT,948 &PDT, &DI)) {949 LLVM_DEBUG(dbgs() << "Fusion candidate contains unsafe "950 "instructions in exit block. Not fusing.\n");951 reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1,952 NonEmptyExitBlock);953 continue;954 }955 956 if (!isSafeToMoveBefore(957 *FC1->GuardBranch->getParent(),958 *FC0->GuardBranch->getParent()->getTerminator(), DT, &PDT,959 &DI)) {960 LLVM_DEBUG(dbgs()961 << "Fusion candidate contains unsafe "962 "instructions in guard block. Not fusing.\n");963 reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1,964 NonEmptyGuardBlock);965 continue;966 }967 }968 969 // Check the dependencies across the loops and do not fuse if it would970 // violate them.971 if (!dependencesAllowFusion(*FC0, *FC1)) {972 LLVM_DEBUG(dbgs() << "Memory dependencies do not allow fusion!\n");973 reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1,974 InvalidDependencies);975 continue;976 }977 978 // If the second loop has instructions in the pre-header, attempt to979 // hoist them up to the first loop's pre-header or sink them into the980 // body of the second loop.981 SmallVector<Instruction *, 4> SafeToHoist;982 SmallVector<Instruction *, 4> SafeToSink;983 // At this point, this is the last remaining legality check.984 // Which means if we can make this pre-header empty, we can fuse985 // these loops986 if (!isEmptyPreheader(*FC1)) {987 LLVM_DEBUG(dbgs() << "Fusion candidate does not have empty "988 "preheader.\n");989 990 // If it is not safe to hoist/sink all instructions in the991 // pre-header, we cannot fuse these loops.992 if (!collectMovablePreheaderInsts(*FC0, *FC1, SafeToHoist,993 SafeToSink)) {994 LLVM_DEBUG(dbgs() << "Could not hoist/sink all instructions in "995 "Fusion Candidate Pre-header.\n"996 << "Not Fusing.\n");997 reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1,998 NonEmptyPreheader);999 continue;1000 }1001 }1002 1003 bool BeneficialToFuse = isBeneficialFusion(*FC0, *FC1);1004 LLVM_DEBUG(dbgs()1005 << "\tFusion appears to be "1006 << (BeneficialToFuse ? "" : "un") << "profitable!\n");1007 if (!BeneficialToFuse) {1008 reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1,1009 FusionNotBeneficial);1010 continue;1011 }1012 // All analysis has completed and has determined that fusion is legal1013 // and profitable. At this point, start transforming the code and1014 // perform fusion.1015 1016 // Execute the hoist/sink operations on preheader instructions1017 movePreheaderInsts(*FC0, *FC1, SafeToHoist, SafeToSink);1018 1019 LLVM_DEBUG(dbgs() << "\tFusion is performed: " << *FC0 << " and "1020 << *FC1 << "\n");1021 1022 FusionCandidate FC0Copy = *FC0;1023 // Peel the loop after determining that fusion is legal. The Loops1024 // will still be safe to fuse after the peeling is performed.1025 bool Peel = TCDifference && *TCDifference > 0;1026 if (Peel)1027 peelFusionCandidate(FC0Copy, *FC1, *TCDifference);1028 1029 // Report fusion to the Optimization Remarks.1030 // Note this needs to be done *before* performFusion because1031 // performFusion will change the original loops, making it not1032 // possible to identify them after fusion is complete.1033 reportLoopFusion<OptimizationRemark>((Peel ? FC0Copy : *FC0), *FC1,1034 FuseCounter);1035 1036 FusionCandidate FusedCand(1037 performFusion((Peel ? FC0Copy : *FC0), *FC1), DT, &PDT, ORE,1038 FC0Copy.PP);1039 FusedCand.verify();1040 assert(FusedCand.isEligibleForFusion(SE) &&1041 "Fused candidate should be eligible for fusion!");1042 1043 // Notify the loop-depth-tree that these loops are not valid objects1044 LDT.removeLoop(FC1->L);1045 1046 CandidateSet.erase(FC0);1047 CandidateSet.erase(FC1);1048 1049 auto InsertPos = CandidateSet.insert(FusedCand);1050 1051 assert(InsertPos.second &&1052 "Unable to insert TargetCandidate in CandidateSet!");1053 1054 // Reset FC0 and FC1 the new (fused) candidate. Subsequent iterations1055 // of the FC1 loop will attempt to fuse the new (fused) loop with the1056 // remaining candidates in the current candidate set.1057 FC0 = FC1 = InsertPos.first;1058 1059 LLVM_DEBUG(dbgs() << "Candidate Set (after fusion): " << CandidateSet1060 << "\n");1061 1062 Fused = true;1063 }1064 }1065 }1066 return Fused;1067 }1068 1069 // Returns true if the instruction \p I can be hoisted to the end of the1070 // preheader of \p FC0. \p SafeToHoist contains the instructions that are1071 // known to be safe to hoist. The instructions encountered that cannot be1072 // hoisted are in \p NotHoisting.1073 // TODO: Move functionality into CodeMoverUtils1074 bool canHoistInst(Instruction &I,1075 const SmallVector<Instruction *, 4> &SafeToHoist,1076 const SmallVector<Instruction *, 4> &NotHoisting,1077 const FusionCandidate &FC0) const {1078 const BasicBlock *FC0PreheaderTarget = FC0.Preheader->getSingleSuccessor();1079 assert(FC0PreheaderTarget &&1080 "Expected single successor for loop preheader.");1081 1082 for (Use &Op : I.operands()) {1083 if (auto *OpInst = dyn_cast<Instruction>(Op)) {1084 bool OpHoisted = is_contained(SafeToHoist, OpInst);1085 // Check if we have already decided to hoist this operand. In this1086 // case, it does not dominate FC0 *yet*, but will after we hoist it.1087 if (!(OpHoisted || DT.dominates(OpInst, FC0PreheaderTarget))) {1088 return false;1089 }1090 }1091 }1092 1093 // PHIs in FC1's header only have FC0 blocks as predecessors. PHIs1094 // cannot be hoisted and should be sunk to the exit of the fused loop.1095 if (isa<PHINode>(I))1096 return false;1097 1098 // If this isn't a memory inst, hoisting is safe1099 if (!I.mayReadOrWriteMemory())1100 return true;1101 1102 LLVM_DEBUG(dbgs() << "Checking if this mem inst can be hoisted.\n");1103 for (Instruction *NotHoistedInst : NotHoisting) {1104 if (auto D = DI.depends(&I, NotHoistedInst)) {1105 // Dependency is not read-before-write, write-before-read or1106 // write-before-write1107 if (D->isFlow() || D->isAnti() || D->isOutput()) {1108 LLVM_DEBUG(dbgs() << "Inst depends on an instruction in FC1's "1109 "preheader that is not being hoisted.\n");1110 return false;1111 }1112 }1113 }1114 1115 for (Instruction *ReadInst : FC0.MemReads) {1116 if (auto D = DI.depends(ReadInst, &I)) {1117 // Dependency is not read-before-write1118 if (D->isAnti()) {1119 LLVM_DEBUG(dbgs() << "Inst depends on a read instruction in FC0.\n");1120 return false;1121 }1122 }1123 }1124 1125 for (Instruction *WriteInst : FC0.MemWrites) {1126 if (auto D = DI.depends(WriteInst, &I)) {1127 // Dependency is not write-before-read or write-before-write1128 if (D->isFlow() || D->isOutput()) {1129 LLVM_DEBUG(dbgs() << "Inst depends on a write instruction in FC0.\n");1130 return false;1131 }1132 }1133 }1134 return true;1135 }1136 1137 // Returns true if the instruction \p I can be sunk to the top of the exit1138 // block of \p FC1.1139 // TODO: Move functionality into CodeMoverUtils1140 bool canSinkInst(Instruction &I, const FusionCandidate &FC1) const {1141 for (User *U : I.users()) {1142 if (auto *UI{dyn_cast<Instruction>(U)}) {1143 // Cannot sink if user in loop1144 // If FC1 has phi users of this value, we cannot sink it into FC1.1145 if (FC1.L->contains(UI)) {1146 // Cannot hoist or sink this instruction. No hoisting/sinking1147 // should take place, loops should not fuse1148 return false;1149 }1150 }1151 }1152 1153 // If this isn't a memory inst, sinking is safe1154 if (!I.mayReadOrWriteMemory())1155 return true;1156 1157 for (Instruction *ReadInst : FC1.MemReads) {1158 if (auto D = DI.depends(&I, ReadInst)) {1159 // Dependency is not write-before-read1160 if (D->isFlow()) {1161 LLVM_DEBUG(dbgs() << "Inst depends on a read instruction in FC1.\n");1162 return false;1163 }1164 }1165 }1166 1167 for (Instruction *WriteInst : FC1.MemWrites) {1168 if (auto D = DI.depends(&I, WriteInst)) {1169 // Dependency is not write-before-write or read-before-write1170 if (D->isOutput() || D->isAnti()) {1171 LLVM_DEBUG(dbgs() << "Inst depends on a write instruction in FC1.\n");1172 return false;1173 }1174 }1175 }1176 1177 return true;1178 }1179 1180 /// This function fixes PHI nodes after fusion in \p SafeToSink.1181 /// \p SafeToSink instructions are the instructions that are to be moved past1182 /// the fused loop. Thus, the PHI nodes in \p SafeToSink should be updated to1183 /// receive values from the fused loop if they are currently taking values1184 /// from the first loop (i.e. FC0)'s latch.1185 void fixPHINodes(ArrayRef<Instruction *> SafeToSink,1186 const FusionCandidate &FC0,1187 const FusionCandidate &FC1) const {1188 for (Instruction *Inst : SafeToSink) {1189 // No update needed for non-PHI nodes.1190 PHINode *Phi = dyn_cast<PHINode>(Inst);1191 if (!Phi)1192 continue;1193 for (unsigned I = 0; I < Phi->getNumIncomingValues(); I++) {1194 if (Phi->getIncomingBlock(I) != FC0.Latch)1195 continue;1196 assert(FC1.Latch && "FC1 latch is not set");1197 Phi->setIncomingBlock(I, FC1.Latch);1198 }1199 }1200 }1201 1202 /// Collect instructions in the \p FC1 Preheader that can be hoisted1203 /// to the \p FC0 Preheader or sunk into the \p FC1 Body1204 bool collectMovablePreheaderInsts(1205 const FusionCandidate &FC0, const FusionCandidate &FC1,1206 SmallVector<Instruction *, 4> &SafeToHoist,1207 SmallVector<Instruction *, 4> &SafeToSink) const {1208 BasicBlock *FC1Preheader = FC1.Preheader;1209 // Save the instructions that are not being hoisted, so we know not to hoist1210 // mem insts that they dominate.1211 SmallVector<Instruction *, 4> NotHoisting;1212 1213 for (Instruction &I : *FC1Preheader) {1214 // Can't move a branch1215 if (&I == FC1Preheader->getTerminator())1216 continue;1217 // If the instruction has side-effects, give up.1218 // TODO: The case of mayReadFromMemory we can handle but requires1219 // additional work with a dependence analysis so for now we give1220 // up on memory reads.1221 if (I.mayThrow() || !I.willReturn()) {1222 LLVM_DEBUG(dbgs() << "Inst: " << I << " may throw or won't return.\n");1223 return false;1224 }1225 1226 LLVM_DEBUG(dbgs() << "Checking Inst: " << I << "\n");1227 1228 if (I.isAtomic() || I.isVolatile()) {1229 LLVM_DEBUG(1230 dbgs() << "\tInstruction is volatile or atomic. Cannot move it.\n");1231 return false;1232 }1233 1234 if (canHoistInst(I, SafeToHoist, NotHoisting, FC0)) {1235 SafeToHoist.push_back(&I);1236 LLVM_DEBUG(dbgs() << "\tSafe to hoist.\n");1237 } else {1238 LLVM_DEBUG(dbgs() << "\tCould not hoist. Trying to sink...\n");1239 NotHoisting.push_back(&I);1240 1241 if (canSinkInst(I, FC1)) {1242 SafeToSink.push_back(&I);1243 LLVM_DEBUG(dbgs() << "\tSafe to sink.\n");1244 } else {1245 LLVM_DEBUG(dbgs() << "\tCould not sink.\n");1246 return false;1247 }1248 }1249 }1250 LLVM_DEBUG(1251 dbgs() << "All preheader instructions could be sunk or hoisted!\n");1252 return true;1253 }1254 1255 /// Rewrite all additive recurrences in a SCEV to use a new loop.1256 class AddRecLoopReplacer : public SCEVRewriteVisitor<AddRecLoopReplacer> {1257 public:1258 AddRecLoopReplacer(ScalarEvolution &SE, const Loop &OldL, const Loop &NewL,1259 bool UseMax = true)1260 : SCEVRewriteVisitor(SE), Valid(true), UseMax(UseMax), OldL(OldL),1261 NewL(NewL) {}1262 1263 const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) {1264 const Loop *ExprL = Expr->getLoop();1265 SmallVector<const SCEV *, 2> Operands;1266 if (ExprL == &OldL) {1267 append_range(Operands, Expr->operands());1268 return SE.getAddRecExpr(Operands, &NewL, Expr->getNoWrapFlags());1269 }1270 1271 if (OldL.contains(ExprL)) {1272 bool Pos = SE.isKnownPositive(Expr->getStepRecurrence(SE));1273 if (!UseMax || !Pos || !Expr->isAffine()) {1274 Valid = false;1275 return Expr;1276 }1277 return visit(Expr->getStart());1278 }1279 1280 for (const SCEV *Op : Expr->operands())1281 Operands.push_back(visit(Op));1282 return SE.getAddRecExpr(Operands, ExprL, Expr->getNoWrapFlags());1283 }1284 1285 bool wasValidSCEV() const { return Valid; }1286 1287 private:1288 bool Valid, UseMax;1289 const Loop &OldL, &NewL;1290 };1291 1292 /// Return false if the access functions of \p I0 and \p I1 could cause1293 /// a negative dependence.1294 bool accessDiffIsPositive(const Loop &L0, const Loop &L1, Instruction &I0,1295 Instruction &I1, bool EqualIsInvalid) {1296 Value *Ptr0 = getLoadStorePointerOperand(&I0);1297 Value *Ptr1 = getLoadStorePointerOperand(&I1);1298 if (!Ptr0 || !Ptr1)1299 return false;1300 1301 const SCEV *SCEVPtr0 = SE.getSCEVAtScope(Ptr0, &L0);1302 const SCEV *SCEVPtr1 = SE.getSCEVAtScope(Ptr1, &L1);1303#ifndef NDEBUG1304 if (VerboseFusionDebugging)1305 LLVM_DEBUG(dbgs() << " Access function check: " << *SCEVPtr0 << " vs "1306 << *SCEVPtr1 << "\n");1307#endif1308 AddRecLoopReplacer Rewriter(SE, L0, L1);1309 SCEVPtr0 = Rewriter.visit(SCEVPtr0);1310#ifndef NDEBUG1311 if (VerboseFusionDebugging)1312 LLVM_DEBUG(dbgs() << " Access function after rewrite: " << *SCEVPtr01313 << " [Valid: " << Rewriter.wasValidSCEV() << "]\n");1314#endif1315 if (!Rewriter.wasValidSCEV())1316 return false;1317 1318 // TODO: isKnownPredicate doesnt work well when one SCEV is loop carried (by1319 // L0) and the other is not. We could check if it is monotone and test1320 // the beginning and end value instead.1321 1322 BasicBlock *L0Header = L0.getHeader();1323 auto HasNonLinearDominanceRelation = [&](const SCEV *S) {1324 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S);1325 if (!AddRec)1326 return false;1327 return !DT.dominates(L0Header, AddRec->getLoop()->getHeader()) &&1328 !DT.dominates(AddRec->getLoop()->getHeader(), L0Header);1329 };1330 if (SCEVExprContains(SCEVPtr1, HasNonLinearDominanceRelation))1331 return false;1332 1333 ICmpInst::Predicate Pred =1334 EqualIsInvalid ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_SGE;1335 bool IsAlwaysGE = SE.isKnownPredicate(Pred, SCEVPtr0, SCEVPtr1);1336#ifndef NDEBUG1337 if (VerboseFusionDebugging)1338 LLVM_DEBUG(dbgs() << " Relation: " << *SCEVPtr01339 << (IsAlwaysGE ? " >= " : " may < ") << *SCEVPtr11340 << "\n");1341#endif1342 return IsAlwaysGE;1343 }1344 1345 /// Return true if the dependences between @p I0 (in @p L0) and @p I1 (in1346 /// @p L1) allow loop fusion of @p L0 and @p L1. The dependence analyses1347 /// specified by @p DepChoice are used to determine this.1348 bool dependencesAllowFusion(const FusionCandidate &FC0,1349 const FusionCandidate &FC1, Instruction &I0,1350 Instruction &I1, bool AnyDep,1351 FusionDependenceAnalysisChoice DepChoice) {1352#ifndef NDEBUG1353 if (VerboseFusionDebugging) {1354 LLVM_DEBUG(dbgs() << "Check dep: " << I0 << " vs " << I1 << " : "1355 << DepChoice << "\n");1356 }1357#endif1358 switch (DepChoice) {1359 case FUSION_DEPENDENCE_ANALYSIS_SCEV:1360 return accessDiffIsPositive(*FC0.L, *FC1.L, I0, I1, AnyDep);1361 case FUSION_DEPENDENCE_ANALYSIS_DA: {1362 auto DepResult = DI.depends(&I0, &I1);1363 if (!DepResult)1364 return true;1365#ifndef NDEBUG1366 if (VerboseFusionDebugging) {1367 LLVM_DEBUG(dbgs() << "DA res: "; DepResult->dump(dbgs());1368 dbgs() << " [#l: " << DepResult->getLevels() << "][Ordered: "1369 << (DepResult->isOrdered() ? "true" : "false")1370 << "]\n");1371 LLVM_DEBUG(dbgs() << "DepResult Levels: " << DepResult->getLevels()1372 << "\n");1373 }1374#endif1375 unsigned Levels = DepResult->getLevels();1376 unsigned SameSDLevels = DepResult->getSameSDLevels();1377 unsigned CurLoopLevel = FC0.L->getLoopDepth();1378 1379 // Check if DA is missing info regarding the current loop level1380 if (CurLoopLevel > Levels + SameSDLevels)1381 return false;1382 1383 // Iterating over the outer levels.1384 for (unsigned Level = 1; Level <= std::min(CurLoopLevel - 1, Levels);1385 ++Level) {1386 unsigned Direction = DepResult->getDirection(Level, false);1387 1388 // Check if the direction vector does not include equality. If an outer1389 // loop has a non-equal direction, outer indicies are different and it1390 // is safe to fuse.1391 if (!(Direction & Dependence::DVEntry::EQ)) {1392 LLVM_DEBUG(dbgs() << "Safe to fuse due to non-equal acceses in the "1393 "outer loops\n");1394 NumDA++;1395 return true;1396 }1397 }1398 1399 assert(CurLoopLevel > Levels && "Fusion candidates are not separated");1400 1401 unsigned CurDir = DepResult->getDirection(CurLoopLevel, true);1402 1403 // Check if the direction vector does not include greater direction. In1404 // that case, the dependency is not a backward loop-carried and is legal1405 // to fuse. For example here we have a forward dependency1406 // for (int i = 0; i < n; i++)1407 // A[i] = ...;1408 // for (int i = 0; i < n; i++)1409 // ... = A[i-1];1410 if (!(CurDir & Dependence::DVEntry::GT)) {1411 LLVM_DEBUG(dbgs() << "Safe to fuse with no backward loop-carried "1412 "dependency\n");1413 NumDA++;1414 return true;1415 }1416 1417 if (DepResult->getNextPredecessor() || DepResult->getNextSuccessor())1418 LLVM_DEBUG(1419 dbgs() << "TODO: Implement pred/succ dependence handling!\n");1420 1421 // TODO: Can we actually use the dependence info analysis here?1422 return false;1423 }1424 1425 case FUSION_DEPENDENCE_ANALYSIS_ALL:1426 return dependencesAllowFusion(FC0, FC1, I0, I1, AnyDep,1427 FUSION_DEPENDENCE_ANALYSIS_SCEV) ||1428 dependencesAllowFusion(FC0, FC1, I0, I1, AnyDep,1429 FUSION_DEPENDENCE_ANALYSIS_DA);1430 }1431 1432 llvm_unreachable("Unknown fusion dependence analysis choice!");1433 }1434 1435 /// Perform a dependence check and return if @p FC0 and @p FC1 can be fused.1436 bool dependencesAllowFusion(const FusionCandidate &FC0,1437 const FusionCandidate &FC1) {1438 LLVM_DEBUG(dbgs() << "Check if " << FC0 << " can be fused with " << FC11439 << "\n");1440 assert(FC0.L->getLoopDepth() == FC1.L->getLoopDepth());1441 assert(DT.dominates(FC0.getEntryBlock(), FC1.getEntryBlock()));1442 1443 for (Instruction *WriteL0 : FC0.MemWrites) {1444 for (Instruction *WriteL1 : FC1.MemWrites)1445 if (!dependencesAllowFusion(FC0, FC1, *WriteL0, *WriteL1,1446 /* AnyDep */ false,1447 FusionDependenceAnalysis)) {1448 InvalidDependencies++;1449 return false;1450 }1451 for (Instruction *ReadL1 : FC1.MemReads)1452 if (!dependencesAllowFusion(FC0, FC1, *WriteL0, *ReadL1,1453 /* AnyDep */ false,1454 FusionDependenceAnalysis)) {1455 InvalidDependencies++;1456 return false;1457 }1458 }1459 1460 for (Instruction *WriteL1 : FC1.MemWrites) {1461 for (Instruction *WriteL0 : FC0.MemWrites)1462 if (!dependencesAllowFusion(FC0, FC1, *WriteL0, *WriteL1,1463 /* AnyDep */ false,1464 FusionDependenceAnalysis)) {1465 InvalidDependencies++;1466 return false;1467 }1468 for (Instruction *ReadL0 : FC0.MemReads)1469 if (!dependencesAllowFusion(FC0, FC1, *ReadL0, *WriteL1,1470 /* AnyDep */ false,1471 FusionDependenceAnalysis)) {1472 InvalidDependencies++;1473 return false;1474 }1475 }1476 1477 // Walk through all uses in FC1. For each use, find the reaching def. If the1478 // def is located in FC0 then it is not safe to fuse.1479 for (BasicBlock *BB : FC1.L->blocks())1480 for (Instruction &I : *BB)1481 for (auto &Op : I.operands())1482 if (Instruction *Def = dyn_cast<Instruction>(Op))1483 if (FC0.L->contains(Def->getParent())) {1484 InvalidDependencies++;1485 return false;1486 }1487 1488 return true;1489 }1490 1491 /// Determine if two fusion candidates are adjacent in the CFG.1492 ///1493 /// This method will determine if there are additional basic blocks in the CFG1494 /// between the exit of \p FC0 and the entry of \p FC1.1495 /// If the two candidates are guarded loops, then it checks whether the1496 /// non-loop successor of the \p FC0 guard branch is the entry block of \p1497 /// FC1. If not, then the loops are not adjacent. If the two candidates are1498 /// not guarded loops, then it checks whether the exit block of \p FC0 is the1499 /// preheader of \p FC1.1500 bool isAdjacent(const FusionCandidate &FC0,1501 const FusionCandidate &FC1) const {1502 // If the successor of the guard branch is FC1, then the loops are adjacent1503 if (FC0.GuardBranch)1504 return FC0.getNonLoopBlock() == FC1.getEntryBlock();1505 else1506 return FC0.ExitBlock == FC1.getEntryBlock();1507 }1508 1509 bool isEmptyPreheader(const FusionCandidate &FC) const {1510 return FC.Preheader->size() == 1;1511 }1512 1513 /// Hoist \p FC1 Preheader instructions to \p FC0 Preheader1514 /// and sink others into the body of \p FC1.1515 void movePreheaderInsts(const FusionCandidate &FC0,1516 const FusionCandidate &FC1,1517 SmallVector<Instruction *, 4> &HoistInsts,1518 SmallVector<Instruction *, 4> &SinkInsts) const {1519 // All preheader instructions except the branch must be hoisted or sunk1520 assert(HoistInsts.size() + SinkInsts.size() == FC1.Preheader->size() - 1 &&1521 "Attempting to sink and hoist preheader instructions, but not all "1522 "the preheader instructions are accounted for.");1523 1524 NumHoistedInsts += HoistInsts.size();1525 NumSunkInsts += SinkInsts.size();1526 1527 LLVM_DEBUG(if (VerboseFusionDebugging) {1528 if (!HoistInsts.empty())1529 dbgs() << "Hoisting: \n";1530 for (Instruction *I : HoistInsts)1531 dbgs() << *I << "\n";1532 if (!SinkInsts.empty())1533 dbgs() << "Sinking: \n";1534 for (Instruction *I : SinkInsts)1535 dbgs() << *I << "\n";1536 });1537 1538 for (Instruction *I : HoistInsts) {1539 assert(I->getParent() == FC1.Preheader);1540 I->moveBefore(*FC0.Preheader,1541 FC0.Preheader->getTerminator()->getIterator());1542 }1543 // insert instructions in reverse order to maintain dominance relationship1544 for (Instruction *I : reverse(SinkInsts)) {1545 assert(I->getParent() == FC1.Preheader);1546 I->moveBefore(*FC1.ExitBlock, FC1.ExitBlock->getFirstInsertionPt());1547 }1548 // PHI nodes in SinkInsts need to be updated to receive values from the1549 // fused loop.1550 fixPHINodes(SinkInsts, FC0, FC1);1551 }1552 1553 /// Determine if two fusion candidates have identical guards1554 ///1555 /// This method will determine if two fusion candidates have the same guards.1556 /// The guards are considered the same if:1557 /// 1. The instructions to compute the condition used in the compare are1558 /// identical.1559 /// 2. The successors of the guard have the same flow into/around the loop.1560 /// If the compare instructions are identical, then the first successor of the1561 /// guard must go to the same place (either the preheader of the loop or the1562 /// NonLoopBlock). In other words, the first successor of both loops must1563 /// both go into the loop (i.e., the preheader) or go around the loop (i.e.,1564 /// the NonLoopBlock). The same must be true for the second successor.1565 bool haveIdenticalGuards(const FusionCandidate &FC0,1566 const FusionCandidate &FC1) const {1567 assert(FC0.GuardBranch && FC1.GuardBranch &&1568 "Expecting FC0 and FC1 to be guarded loops.");1569 1570 if (auto FC0CmpInst =1571 dyn_cast<Instruction>(FC0.GuardBranch->getCondition()))1572 if (auto FC1CmpInst =1573 dyn_cast<Instruction>(FC1.GuardBranch->getCondition()))1574 if (!FC0CmpInst->isIdenticalTo(FC1CmpInst))1575 return false;1576 1577 // The compare instructions are identical.1578 // Now make sure the successor of the guards have the same flow into/around1579 // the loop1580 if (FC0.GuardBranch->getSuccessor(0) == FC0.Preheader)1581 return (FC1.GuardBranch->getSuccessor(0) == FC1.Preheader);1582 else1583 return (FC1.GuardBranch->getSuccessor(1) == FC1.Preheader);1584 }1585 1586 /// Modify the latch branch of FC to be unconditional since successors of the1587 /// branch are the same.1588 void simplifyLatchBranch(const FusionCandidate &FC) const {1589 BranchInst *FCLatchBranch = dyn_cast<BranchInst>(FC.Latch->getTerminator());1590 if (FCLatchBranch) {1591 assert(FCLatchBranch->isConditional() &&1592 FCLatchBranch->getSuccessor(0) == FCLatchBranch->getSuccessor(1) &&1593 "Expecting the two successors of FCLatchBranch to be the same");1594 BranchInst *NewBranch =1595 BranchInst::Create(FCLatchBranch->getSuccessor(0));1596 ReplaceInstWithInst(FCLatchBranch, NewBranch);1597 }1598 }1599 1600 /// Move instructions from FC0.Latch to FC1.Latch. If FC0.Latch has an unique1601 /// successor, then merge FC0.Latch with its unique successor.1602 void mergeLatch(const FusionCandidate &FC0, const FusionCandidate &FC1) {1603 moveInstructionsToTheBeginning(*FC0.Latch, *FC1.Latch, DT, PDT, DI);1604 if (BasicBlock *Succ = FC0.Latch->getUniqueSuccessor()) {1605 MergeBlockIntoPredecessor(Succ, &DTU, &LI);1606 DTU.flush();1607 }1608 }1609 1610 /// Fuse two fusion candidates, creating a new fused loop.1611 ///1612 /// This method contains the mechanics of fusing two loops, represented by \p1613 /// FC0 and \p FC1. It is assumed that \p FC0 dominates \p FC1 and \p FC11614 /// postdominates \p FC0 (making them control flow equivalent). It also1615 /// assumes that the other conditions for fusion have been met: adjacent,1616 /// identical trip counts, and no negative distance dependencies exist that1617 /// would prevent fusion. Thus, there is no checking for these conditions in1618 /// this method.1619 ///1620 /// Fusion is performed by rewiring the CFG to update successor blocks of the1621 /// components of tho loop. Specifically, the following changes are done:1622 ///1623 /// 1. The preheader of \p FC1 is removed as it is no longer necessary1624 /// (because it is currently only a single statement block).1625 /// 2. The latch of \p FC0 is modified to jump to the header of \p FC1.1626 /// 3. The latch of \p FC1 i modified to jump to the header of \p FC0.1627 /// 4. All blocks from \p FC1 are removed from FC1 and added to FC0.1628 ///1629 /// All of these modifications are done with dominator tree updates, thus1630 /// keeping the dominator (and post dominator) information up-to-date.1631 ///1632 /// This can be improved in the future by actually merging blocks during1633 /// fusion. For example, the preheader of \p FC1 can be merged with the1634 /// preheader of \p FC0. This would allow loops with more than a single1635 /// statement in the preheader to be fused. Similarly, the latch blocks of the1636 /// two loops could also be fused into a single block. This will require1637 /// analysis to prove it is safe to move the contents of the block past1638 /// existing code, which currently has not been implemented.1639 Loop *performFusion(const FusionCandidate &FC0, const FusionCandidate &FC1) {1640 assert(FC0.isValid() && FC1.isValid() &&1641 "Expecting valid fusion candidates");1642 1643 LLVM_DEBUG(dbgs() << "Fusion Candidate 0: \n"; FC0.dump();1644 dbgs() << "Fusion Candidate 1: \n"; FC1.dump(););1645 1646 // Move instructions from the preheader of FC1 to the end of the preheader1647 // of FC0.1648 moveInstructionsToTheEnd(*FC1.Preheader, *FC0.Preheader, DT, PDT, DI);1649 1650 // Fusing guarded loops is handled slightly differently than non-guarded1651 // loops and has been broken out into a separate method instead of trying to1652 // intersperse the logic within a single method.1653 if (FC0.GuardBranch)1654 return fuseGuardedLoops(FC0, FC1);1655 1656 assert(FC1.Preheader ==1657 (FC0.Peeled ? FC0.ExitBlock->getUniqueSuccessor() : FC0.ExitBlock));1658 assert(FC1.Preheader->size() == 1 &&1659 FC1.Preheader->getSingleSuccessor() == FC1.Header);1660 1661 // Remember the phi nodes originally in the header of FC0 in order to rewire1662 // them later. However, this is only necessary if the new loop carried1663 // values might not dominate the exiting branch. While we do not generally1664 // test if this is the case but simply insert intermediate phi nodes, we1665 // need to make sure these intermediate phi nodes have different1666 // predecessors. To this end, we filter the special case where the exiting1667 // block is the latch block of the first loop. Nothing needs to be done1668 // anyway as all loop carried values dominate the latch and thereby also the1669 // exiting branch.1670 SmallVector<PHINode *, 8> OriginalFC0PHIs;1671 if (FC0.ExitingBlock != FC0.Latch)1672 for (PHINode &PHI : FC0.Header->phis())1673 OriginalFC0PHIs.push_back(&PHI);1674 1675 // Replace incoming blocks for header PHIs first.1676 FC1.Preheader->replaceSuccessorsPhiUsesWith(FC0.Preheader);1677 FC0.Latch->replaceSuccessorsPhiUsesWith(FC1.Latch);1678 1679 // Then modify the control flow and update DT and PDT.1680 SmallVector<DominatorTree::UpdateType, 8> TreeUpdates;1681 1682 // The old exiting block of the first loop (FC0) has to jump to the header1683 // of the second as we need to execute the code in the second header block1684 // regardless of the trip count. That is, if the trip count is 0, so the1685 // back edge is never taken, we still have to execute both loop headers,1686 // especially (but not only!) if the second is a do-while style loop.1687 // However, doing so might invalidate the phi nodes of the first loop as1688 // the new values do only need to dominate their latch and not the exiting1689 // predicate. To remedy this potential problem we always introduce phi1690 // nodes in the header of the second loop later that select the loop carried1691 // value, if the second header was reached through an old latch of the1692 // first, or undef otherwise. This is sound as exiting the first implies the1693 // second will exit too, __without__ taking the back-edge. [Their1694 // trip-counts are equal after all.1695 // KB: Would this sequence be simpler to just make FC0.ExitingBlock go1696 // to FC1.Header? I think this is basically what the three sequences are1697 // trying to accomplish; however, doing this directly in the CFG may mean1698 // the DT/PDT becomes invalid1699 if (!FC0.Peeled) {1700 FC0.ExitingBlock->getTerminator()->replaceUsesOfWith(FC1.Preheader,1701 FC1.Header);1702 TreeUpdates.emplace_back(DominatorTree::UpdateType(1703 DominatorTree::Delete, FC0.ExitingBlock, FC1.Preheader));1704 TreeUpdates.emplace_back(DominatorTree::UpdateType(1705 DominatorTree::Insert, FC0.ExitingBlock, FC1.Header));1706 } else {1707 TreeUpdates.emplace_back(DominatorTree::UpdateType(1708 DominatorTree::Delete, FC0.ExitBlock, FC1.Preheader));1709 1710 // Remove the ExitBlock of the first Loop (also not needed)1711 FC0.ExitingBlock->getTerminator()->replaceUsesOfWith(FC0.ExitBlock,1712 FC1.Header);1713 TreeUpdates.emplace_back(DominatorTree::UpdateType(1714 DominatorTree::Delete, FC0.ExitingBlock, FC0.ExitBlock));1715 FC0.ExitBlock->getTerminator()->eraseFromParent();1716 TreeUpdates.emplace_back(DominatorTree::UpdateType(1717 DominatorTree::Insert, FC0.ExitingBlock, FC1.Header));1718 new UnreachableInst(FC0.ExitBlock->getContext(), FC0.ExitBlock);1719 }1720 1721 // The pre-header of L1 is not necessary anymore.1722 assert(pred_empty(FC1.Preheader));1723 FC1.Preheader->getTerminator()->eraseFromParent();1724 new UnreachableInst(FC1.Preheader->getContext(), FC1.Preheader);1725 TreeUpdates.emplace_back(DominatorTree::UpdateType(1726 DominatorTree::Delete, FC1.Preheader, FC1.Header));1727 1728 // Moves the phi nodes from the second to the first loops header block.1729 while (PHINode *PHI = dyn_cast<PHINode>(&FC1.Header->front())) {1730 if (SE.isSCEVable(PHI->getType()))1731 SE.forgetValue(PHI);1732 if (PHI->hasNUsesOrMore(1))1733 PHI->moveBefore(FC0.Header->getFirstInsertionPt());1734 else1735 PHI->eraseFromParent();1736 }1737 1738 // Introduce new phi nodes in the second loop header to ensure1739 // exiting the first and jumping to the header of the second does not break1740 // the SSA property of the phis originally in the first loop. See also the1741 // comment above.1742 BasicBlock::iterator L1HeaderIP = FC1.Header->begin();1743 for (PHINode *LCPHI : OriginalFC0PHIs) {1744 int L1LatchBBIdx = LCPHI->getBasicBlockIndex(FC1.Latch);1745 assert(L1LatchBBIdx >= 0 &&1746 "Expected loop carried value to be rewired at this point!");1747 1748 Value *LCV = LCPHI->getIncomingValue(L1LatchBBIdx);1749 1750 PHINode *L1HeaderPHI =1751 PHINode::Create(LCV->getType(), 2, LCPHI->getName() + ".afterFC0");1752 L1HeaderPHI->insertBefore(L1HeaderIP);1753 L1HeaderPHI->addIncoming(LCV, FC0.Latch);1754 L1HeaderPHI->addIncoming(PoisonValue::get(LCV->getType()),1755 FC0.ExitingBlock);1756 1757 LCPHI->setIncomingValue(L1LatchBBIdx, L1HeaderPHI);1758 }1759 1760 // Replace latch terminator destinations.1761 FC0.Latch->getTerminator()->replaceUsesOfWith(FC0.Header, FC1.Header);1762 FC1.Latch->getTerminator()->replaceUsesOfWith(FC1.Header, FC0.Header);1763 1764 // Modify the latch branch of FC0 to be unconditional as both successors of1765 // the branch are the same.1766 simplifyLatchBranch(FC0);1767 1768 // If FC0.Latch and FC0.ExitingBlock are the same then we have already1769 // performed the updates above.1770 if (FC0.Latch != FC0.ExitingBlock)1771 TreeUpdates.emplace_back(DominatorTree::UpdateType(1772 DominatorTree::Insert, FC0.Latch, FC1.Header));1773 1774 TreeUpdates.emplace_back(DominatorTree::UpdateType(DominatorTree::Delete,1775 FC0.Latch, FC0.Header));1776 TreeUpdates.emplace_back(DominatorTree::UpdateType(DominatorTree::Insert,1777 FC1.Latch, FC0.Header));1778 TreeUpdates.emplace_back(DominatorTree::UpdateType(DominatorTree::Delete,1779 FC1.Latch, FC1.Header));1780 1781 // Update DT/PDT1782 DTU.applyUpdates(TreeUpdates);1783 1784 LI.removeBlock(FC1.Preheader);1785 DTU.deleteBB(FC1.Preheader);1786 if (FC0.Peeled) {1787 LI.removeBlock(FC0.ExitBlock);1788 DTU.deleteBB(FC0.ExitBlock);1789 }1790 1791 DTU.flush();1792 1793 // Is there a way to keep SE up-to-date so we don't need to forget the loops1794 // and rebuild the information in subsequent passes of fusion?1795 // Note: Need to forget the loops before merging the loop latches, as1796 // mergeLatch may remove the only block in FC1.1797 SE.forgetLoop(FC1.L);1798 SE.forgetLoop(FC0.L);1799 1800 // Move instructions from FC0.Latch to FC1.Latch.1801 // Note: mergeLatch requires an updated DT.1802 mergeLatch(FC0, FC1);1803 1804 // Forget block dispositions as well, so that there are no dangling1805 // pointers to erased/free'ed blocks. It should be done after mergeLatch()1806 // since merging the latches may affect the dispositions.1807 SE.forgetBlockAndLoopDispositions();1808 1809 // Merge the loops.1810 SmallVector<BasicBlock *, 8> Blocks(FC1.L->blocks());1811 for (BasicBlock *BB : Blocks) {1812 FC0.L->addBlockEntry(BB);1813 FC1.L->removeBlockFromLoop(BB);1814 if (LI.getLoopFor(BB) != FC1.L)1815 continue;1816 LI.changeLoopFor(BB, FC0.L);1817 }1818 while (!FC1.L->isInnermost()) {1819 const auto &ChildLoopIt = FC1.L->begin();1820 Loop *ChildLoop = *ChildLoopIt;1821 FC1.L->removeChildLoop(ChildLoopIt);1822 FC0.L->addChildLoop(ChildLoop);1823 }1824 1825 // Delete the now empty loop L1.1826 LI.erase(FC1.L);1827 1828#ifndef NDEBUG1829 assert(!verifyFunction(*FC0.Header->getParent(), &errs()));1830 assert(DT.verify(DominatorTree::VerificationLevel::Fast));1831 assert(PDT.verify());1832 LI.verify(DT);1833 SE.verify();1834#endif1835 1836 LLVM_DEBUG(dbgs() << "Fusion done:\n");1837 1838 return FC0.L;1839 }1840 1841 /// Report details on loop fusion opportunities.1842 ///1843 /// This template function can be used to report both successful and missed1844 /// loop fusion opportunities, based on the RemarkKind. The RemarkKind should1845 /// be one of:1846 /// - OptimizationRemarkMissed to report when loop fusion is unsuccessful1847 /// given two valid fusion candidates.1848 /// - OptimizationRemark to report successful fusion of two fusion1849 /// candidates.1850 /// The remarks will be printed using the form:1851 /// <path/filename>:<line number>:<column number>: [<function name>]:1852 /// <Cand1 Preheader> and <Cand2 Preheader>: <Stat Description>1853 template <typename RemarkKind>1854 void reportLoopFusion(const FusionCandidate &FC0, const FusionCandidate &FC1,1855 Statistic &Stat) {1856 assert(FC0.Preheader && FC1.Preheader &&1857 "Expecting valid fusion candidates");1858 using namespace ore;1859#if LLVM_ENABLE_STATS1860 ++Stat;1861 ORE.emit(RemarkKind(DEBUG_TYPE, Stat.getName(), FC0.L->getStartLoc(),1862 FC0.Preheader)1863 << "[" << FC0.Preheader->getParent()->getName()1864 << "]: " << NV("Cand1", StringRef(FC0.Preheader->getName()))1865 << " and " << NV("Cand2", StringRef(FC1.Preheader->getName()))1866 << ": " << Stat.getDesc());1867#endif1868 }1869 1870 /// Fuse two guarded fusion candidates, creating a new fused loop.1871 ///1872 /// Fusing guarded loops is handled much the same way as fusing non-guarded1873 /// loops. The rewiring of the CFG is slightly different though, because of1874 /// the presence of the guards around the loops and the exit blocks after the1875 /// loop body. As such, the new loop is rewired as follows:1876 /// 1. Keep the guard branch from FC0 and use the non-loop block target1877 /// from the FC1 guard branch.1878 /// 2. Remove the exit block from FC0 (this exit block should be empty1879 /// right now).1880 /// 3. Remove the guard branch for FC11881 /// 4. Remove the preheader for FC1.1882 /// The exit block successor for the latch of FC0 is updated to be the header1883 /// of FC1 and the non-exit block successor of the latch of FC1 is updated to1884 /// be the header of FC0, thus creating the fused loop.1885 Loop *fuseGuardedLoops(const FusionCandidate &FC0,1886 const FusionCandidate &FC1) {1887 assert(FC0.GuardBranch && FC1.GuardBranch && "Expecting guarded loops");1888 1889 BasicBlock *FC0GuardBlock = FC0.GuardBranch->getParent();1890 BasicBlock *FC1GuardBlock = FC1.GuardBranch->getParent();1891 BasicBlock *FC0NonLoopBlock = FC0.getNonLoopBlock();1892 BasicBlock *FC1NonLoopBlock = FC1.getNonLoopBlock();1893 BasicBlock *FC0ExitBlockSuccessor = FC0.ExitBlock->getUniqueSuccessor();1894 1895 // Move instructions from the exit block of FC0 to the beginning of the exit1896 // block of FC1, in the case that the FC0 loop has not been peeled. In the1897 // case that FC0 loop is peeled, then move the instructions of the successor1898 // of the FC0 Exit block to the beginning of the exit block of FC1.1899 moveInstructionsToTheBeginning(1900 (FC0.Peeled ? *FC0ExitBlockSuccessor : *FC0.ExitBlock), *FC1.ExitBlock,1901 DT, PDT, DI);1902 1903 // Move instructions from the guard block of FC1 to the end of the guard1904 // block of FC0.1905 moveInstructionsToTheEnd(*FC1GuardBlock, *FC0GuardBlock, DT, PDT, DI);1906 1907 assert(FC0NonLoopBlock == FC1GuardBlock && "Loops are not adjacent");1908 1909 SmallVector<DominatorTree::UpdateType, 8> TreeUpdates;1910 1911 ////////////////////////////////////////////////////////////////////////////1912 // Update the Loop Guard1913 ////////////////////////////////////////////////////////////////////////////1914 // The guard for FC0 is updated to guard both FC0 and FC1. This is done by1915 // changing the NonLoopGuardBlock for FC0 to the NonLoopGuardBlock for FC1.1916 // Thus, one path from the guard goes to the preheader for FC0 (and thus1917 // executes the new fused loop) and the other path goes to the NonLoopBlock1918 // for FC1 (where FC1 guard would have gone if FC1 was not executed).1919 FC1NonLoopBlock->replacePhiUsesWith(FC1GuardBlock, FC0GuardBlock);1920 FC0.GuardBranch->replaceUsesOfWith(FC0NonLoopBlock, FC1NonLoopBlock);1921 1922 BasicBlock *BBToUpdate = FC0.Peeled ? FC0ExitBlockSuccessor : FC0.ExitBlock;1923 BBToUpdate->getTerminator()->replaceUsesOfWith(FC1GuardBlock, FC1.Header);1924 1925 // The guard of FC1 is not necessary anymore.1926 FC1.GuardBranch->eraseFromParent();1927 new UnreachableInst(FC1GuardBlock->getContext(), FC1GuardBlock);1928 1929 TreeUpdates.emplace_back(DominatorTree::UpdateType(1930 DominatorTree::Delete, FC1GuardBlock, FC1.Preheader));1931 TreeUpdates.emplace_back(DominatorTree::UpdateType(1932 DominatorTree::Delete, FC1GuardBlock, FC1NonLoopBlock));1933 TreeUpdates.emplace_back(DominatorTree::UpdateType(1934 DominatorTree::Delete, FC0GuardBlock, FC1GuardBlock));1935 TreeUpdates.emplace_back(DominatorTree::UpdateType(1936 DominatorTree::Insert, FC0GuardBlock, FC1NonLoopBlock));1937 1938 if (FC0.Peeled) {1939 // Remove the Block after the ExitBlock of FC01940 TreeUpdates.emplace_back(DominatorTree::UpdateType(1941 DominatorTree::Delete, FC0ExitBlockSuccessor, FC1GuardBlock));1942 FC0ExitBlockSuccessor->getTerminator()->eraseFromParent();1943 new UnreachableInst(FC0ExitBlockSuccessor->getContext(),1944 FC0ExitBlockSuccessor);1945 }1946 1947 assert(pred_empty(FC1GuardBlock) &&1948 "Expecting guard block to have no predecessors");1949 assert(succ_empty(FC1GuardBlock) &&1950 "Expecting guard block to have no successors");1951 1952 // Remember the phi nodes originally in the header of FC0 in order to rewire1953 // them later. However, this is only necessary if the new loop carried1954 // values might not dominate the exiting branch. While we do not generally1955 // test if this is the case but simply insert intermediate phi nodes, we1956 // need to make sure these intermediate phi nodes have different1957 // predecessors. To this end, we filter the special case where the exiting1958 // block is the latch block of the first loop. Nothing needs to be done1959 // anyway as all loop carried values dominate the latch and thereby also the1960 // exiting branch.1961 // KB: This is no longer necessary because FC0.ExitingBlock == FC0.Latch1962 // (because the loops are rotated. Thus, nothing will ever be added to1963 // OriginalFC0PHIs.1964 SmallVector<PHINode *, 8> OriginalFC0PHIs;1965 if (FC0.ExitingBlock != FC0.Latch)1966 for (PHINode &PHI : FC0.Header->phis())1967 OriginalFC0PHIs.push_back(&PHI);1968 1969 assert(OriginalFC0PHIs.empty() && "Expecting OriginalFC0PHIs to be empty!");1970 1971 // Replace incoming blocks for header PHIs first.1972 FC1.Preheader->replaceSuccessorsPhiUsesWith(FC0.Preheader);1973 FC0.Latch->replaceSuccessorsPhiUsesWith(FC1.Latch);1974 1975 // The old exiting block of the first loop (FC0) has to jump to the header1976 // of the second as we need to execute the code in the second header block1977 // regardless of the trip count. That is, if the trip count is 0, so the1978 // back edge is never taken, we still have to execute both loop headers,1979 // especially (but not only!) if the second is a do-while style loop.1980 // However, doing so might invalidate the phi nodes of the first loop as1981 // the new values do only need to dominate their latch and not the exiting1982 // predicate. To remedy this potential problem we always introduce phi1983 // nodes in the header of the second loop later that select the loop carried1984 // value, if the second header was reached through an old latch of the1985 // first, or undef otherwise. This is sound as exiting the first implies the1986 // second will exit too, __without__ taking the back-edge (their1987 // trip-counts are equal after all).1988 FC0.ExitingBlock->getTerminator()->replaceUsesOfWith(FC0.ExitBlock,1989 FC1.Header);1990 1991 TreeUpdates.emplace_back(DominatorTree::UpdateType(1992 DominatorTree::Delete, FC0.ExitingBlock, FC0.ExitBlock));1993 TreeUpdates.emplace_back(DominatorTree::UpdateType(1994 DominatorTree::Insert, FC0.ExitingBlock, FC1.Header));1995 1996 // Remove FC0 Exit Block1997 // The exit block for FC0 is no longer needed since control will flow1998 // directly to the header of FC1. Since it is an empty block, it can be1999 // removed at this point.2000 // TODO: In the future, we can handle non-empty exit blocks my merging any2001 // instructions from FC0 exit block into FC1 exit block prior to removing2002 // the block.2003 assert(pred_empty(FC0.ExitBlock) && "Expecting exit block to be empty");2004 FC0.ExitBlock->getTerminator()->eraseFromParent();2005 new UnreachableInst(FC0.ExitBlock->getContext(), FC0.ExitBlock);2006 2007 // Remove FC1 Preheader2008 // The pre-header of L1 is not necessary anymore.2009 assert(pred_empty(FC1.Preheader));2010 FC1.Preheader->getTerminator()->eraseFromParent();2011 new UnreachableInst(FC1.Preheader->getContext(), FC1.Preheader);2012 TreeUpdates.emplace_back(DominatorTree::UpdateType(2013 DominatorTree::Delete, FC1.Preheader, FC1.Header));2014 2015 // Moves the phi nodes from the second to the first loops header block.2016 while (PHINode *PHI = dyn_cast<PHINode>(&FC1.Header->front())) {2017 if (SE.isSCEVable(PHI->getType()))2018 SE.forgetValue(PHI);2019 if (PHI->hasNUsesOrMore(1))2020 PHI->moveBefore(FC0.Header->getFirstInsertionPt());2021 else2022 PHI->eraseFromParent();2023 }2024 2025 // Introduce new phi nodes in the second loop header to ensure2026 // exiting the first and jumping to the header of the second does not break2027 // the SSA property of the phis originally in the first loop. See also the2028 // comment above.2029 BasicBlock::iterator L1HeaderIP = FC1.Header->begin();2030 for (PHINode *LCPHI : OriginalFC0PHIs) {2031 int L1LatchBBIdx = LCPHI->getBasicBlockIndex(FC1.Latch);2032 assert(L1LatchBBIdx >= 0 &&2033 "Expected loop carried value to be rewired at this point!");2034 2035 Value *LCV = LCPHI->getIncomingValue(L1LatchBBIdx);2036 2037 PHINode *L1HeaderPHI =2038 PHINode::Create(LCV->getType(), 2, LCPHI->getName() + ".afterFC0");2039 L1HeaderPHI->insertBefore(L1HeaderIP);2040 L1HeaderPHI->addIncoming(LCV, FC0.Latch);2041 L1HeaderPHI->addIncoming(PoisonValue::get(LCV->getType()),2042 FC0.ExitingBlock);2043 2044 LCPHI->setIncomingValue(L1LatchBBIdx, L1HeaderPHI);2045 }2046 2047 // Update the latches2048 2049 // Replace latch terminator destinations.2050 FC0.Latch->getTerminator()->replaceUsesOfWith(FC0.Header, FC1.Header);2051 FC1.Latch->getTerminator()->replaceUsesOfWith(FC1.Header, FC0.Header);2052 2053 // Modify the latch branch of FC0 to be unconditional as both successors of2054 // the branch are the same.2055 simplifyLatchBranch(FC0);2056 2057 // If FC0.Latch and FC0.ExitingBlock are the same then we have already2058 // performed the updates above.2059 if (FC0.Latch != FC0.ExitingBlock)2060 TreeUpdates.emplace_back(DominatorTree::UpdateType(2061 DominatorTree::Insert, FC0.Latch, FC1.Header));2062 2063 TreeUpdates.emplace_back(DominatorTree::UpdateType(DominatorTree::Delete,2064 FC0.Latch, FC0.Header));2065 TreeUpdates.emplace_back(DominatorTree::UpdateType(DominatorTree::Insert,2066 FC1.Latch, FC0.Header));2067 TreeUpdates.emplace_back(DominatorTree::UpdateType(DominatorTree::Delete,2068 FC1.Latch, FC1.Header));2069 2070 // All done2071 // Apply the updates to the Dominator Tree and cleanup.2072 2073 assert(succ_empty(FC1GuardBlock) && "FC1GuardBlock has successors!!");2074 assert(pred_empty(FC1GuardBlock) && "FC1GuardBlock has predecessors!!");2075 2076 // Update DT/PDT2077 DTU.applyUpdates(TreeUpdates);2078 2079 LI.removeBlock(FC1GuardBlock);2080 LI.removeBlock(FC1.Preheader);2081 LI.removeBlock(FC0.ExitBlock);2082 if (FC0.Peeled) {2083 LI.removeBlock(FC0ExitBlockSuccessor);2084 DTU.deleteBB(FC0ExitBlockSuccessor);2085 }2086 DTU.deleteBB(FC1GuardBlock);2087 DTU.deleteBB(FC1.Preheader);2088 DTU.deleteBB(FC0.ExitBlock);2089 DTU.flush();2090 2091 // Is there a way to keep SE up-to-date so we don't need to forget the loops2092 // and rebuild the information in subsequent passes of fusion?2093 // Note: Need to forget the loops before merging the loop latches, as2094 // mergeLatch may remove the only block in FC1.2095 SE.forgetLoop(FC1.L);2096 SE.forgetLoop(FC0.L);2097 2098 // Move instructions from FC0.Latch to FC1.Latch.2099 // Note: mergeLatch requires an updated DT.2100 mergeLatch(FC0, FC1);2101 2102 // Forget block dispositions as well, so that there are no dangling2103 // pointers to erased/free'ed blocks. It should be done after mergeLatch()2104 // since merging the latches may affect the dispositions.2105 SE.forgetBlockAndLoopDispositions();2106 2107 // Merge the loops.2108 SmallVector<BasicBlock *, 8> Blocks(FC1.L->blocks());2109 for (BasicBlock *BB : Blocks) {2110 FC0.L->addBlockEntry(BB);2111 FC1.L->removeBlockFromLoop(BB);2112 if (LI.getLoopFor(BB) != FC1.L)2113 continue;2114 LI.changeLoopFor(BB, FC0.L);2115 }2116 while (!FC1.L->isInnermost()) {2117 const auto &ChildLoopIt = FC1.L->begin();2118 Loop *ChildLoop = *ChildLoopIt;2119 FC1.L->removeChildLoop(ChildLoopIt);2120 FC0.L->addChildLoop(ChildLoop);2121 }2122 2123 // Delete the now empty loop L1.2124 LI.erase(FC1.L);2125 2126#ifndef NDEBUG2127 assert(!verifyFunction(*FC0.Header->getParent(), &errs()));2128 assert(DT.verify(DominatorTree::VerificationLevel::Fast));2129 assert(PDT.verify());2130 LI.verify(DT);2131 SE.verify();2132#endif2133 2134 LLVM_DEBUG(dbgs() << "Fusion done:\n");2135 2136 return FC0.L;2137 }2138};2139} // namespace2140 2141PreservedAnalyses LoopFusePass::run(Function &F, FunctionAnalysisManager &AM) {2142 auto &LI = AM.getResult<LoopAnalysis>(F);2143 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);2144 auto &DI = AM.getResult<DependenceAnalysis>(F);2145 auto &SE = AM.getResult<ScalarEvolutionAnalysis>(F);2146 auto &PDT = AM.getResult<PostDominatorTreeAnalysis>(F);2147 auto &ORE = AM.getResult<OptimizationRemarkEmitterAnalysis>(F);2148 auto &AC = AM.getResult<AssumptionAnalysis>(F);2149 const TargetTransformInfo &TTI = AM.getResult<TargetIRAnalysis>(F);2150 const DataLayout &DL = F.getDataLayout();2151 2152 // Ensure loops are in simplifed form which is a pre-requisite for loop fusion2153 // pass. Added only for new PM since the legacy PM has already added2154 // LoopSimplify pass as a dependency.2155 bool Changed = false;2156 for (auto &L : LI) {2157 Changed |=2158 simplifyLoop(L, &DT, &LI, &SE, &AC, nullptr, false /* PreserveLCSSA */);2159 }2160 if (Changed)2161 PDT.recalculate(F);2162 2163 LoopFuser LF(LI, DT, DI, SE, PDT, ORE, DL, AC, TTI);2164 Changed |= LF.fuseLoops(F);2165 if (!Changed)2166 return PreservedAnalyses::all();2167 2168 PreservedAnalyses PA;2169 PA.preserve<DominatorTreeAnalysis>();2170 PA.preserve<PostDominatorTreeAnalysis>();2171 PA.preserve<ScalarEvolutionAnalysis>();2172 PA.preserve<LoopAnalysis>();2173 return PA;2174}2175