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-exception 6 // 7 //===----------------------------------------------------------------------===// 8 /// 9 /// \file 10 /// 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 a 14 /// Production Compiler 15 /// Christopher Mark Barton 16 /// MSc Thesis 17 /// https://webdocs.cs.ualberta.ca/~amaral/thesis/ChristopherBartonMSc.pdf 18 /// 19 /// The general approach taken is to collect sets of control flow equivalent 20 /// loops and test whether they can be fused. The necessary conditions for 21 /// fusion are: 22 /// 1. The loops must be adjacent (there cannot be any statements between 23 /// the two loops). 24 /// 2. The loops must be conforming (they must execute the same number of 25 /// iterations). 26 /// 3. The loops must be control flow equivalent (if one loop executes, the 27 /// 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 the 32 /// necessary information needed by fusion. It then operates on the fusion 33 /// candidates, first confirming that the candidate is eligible for fusion. The 34 /// candidates are then collected into control flow equivalent sets, sorted in 35 /// dominance order. Each set of control flow equivalent candidates is then 36 /// traversed, attempting to fuse pairs of candidates in the set. If all 37 /// requirements for fusion are met, the two candidates are fused, creating a 38 /// new (fused) candidate which is then added back into the set to consider for 39 /// additional fusion. 40 /// 41 /// This implementation currently does not make any modifications to remove 42 /// conditions for fusion. Code transformations to make loops conform to each of 43 /// the conditions for fusion are discussed in more detail in the document 44 /// 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/InitializePasses.h" 61 #include "llvm/Pass.h" 62 #include "llvm/Support/CommandLine.h" 63 #include "llvm/Support/Debug.h" 64 #include "llvm/Support/raw_ostream.h" 65 #include "llvm/Transforms/Scalar.h" 66 #include "llvm/Transforms/Utils.h" 67 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 68 #include "llvm/Transforms/Utils/CodeMoverUtils.h" 69 #include "llvm/Transforms/Utils/LoopPeel.h" 70 71 using namespace llvm; 72 73 #define DEBUG_TYPE "loop-fusion" 74 75 STATISTIC(FuseCounter, "Loops fused"); 76 STATISTIC(NumFusionCandidates, "Number of candidates for loop fusion"); 77 STATISTIC(InvalidPreheader, "Loop has invalid preheader"); 78 STATISTIC(InvalidHeader, "Loop has invalid header"); 79 STATISTIC(InvalidExitingBlock, "Loop has invalid exiting blocks"); 80 STATISTIC(InvalidExitBlock, "Loop has invalid exit block"); 81 STATISTIC(InvalidLatch, "Loop has invalid latch"); 82 STATISTIC(InvalidLoop, "Loop is invalid"); 83 STATISTIC(AddressTakenBB, "Basic block has address taken"); 84 STATISTIC(MayThrowException, "Loop may throw an exception"); 85 STATISTIC(ContainsVolatileAccess, "Loop contains a volatile access"); 86 STATISTIC(NotSimplifiedForm, "Loop is not in simplified form"); 87 STATISTIC(InvalidDependencies, "Dependencies prevent fusion"); 88 STATISTIC(UnknownTripCount, "Loop has unknown trip count"); 89 STATISTIC(UncomputableTripCount, "SCEV cannot compute trip count of loop"); 90 STATISTIC(NonEqualTripCount, "Loop trip counts are not the same"); 91 STATISTIC(NonAdjacent, "Loops are not adjacent"); 92 STATISTIC( 93 NonEmptyPreheader, 94 "Loop has a non-empty preheader with instructions that cannot be moved"); 95 STATISTIC(FusionNotBeneficial, "Fusion is not beneficial"); 96 STATISTIC(NonIdenticalGuards, "Candidates have different guards"); 97 STATISTIC(NonEmptyExitBlock, "Candidate has a non-empty exit block with " 98 "instructions that cannot be moved"); 99 STATISTIC(NonEmptyGuardBlock, "Candidate has a non-empty guard block with " 100 "instructions that cannot be moved"); 101 STATISTIC(NotRotated, "Candidate is not rotated"); 102 103 enum FusionDependenceAnalysisChoice { 104 FUSION_DEPENDENCE_ANALYSIS_SCEV, 105 FUSION_DEPENDENCE_ANALYSIS_DA, 106 FUSION_DEPENDENCE_ANALYSIS_ALL, 107 }; 108 109 static cl::opt<FusionDependenceAnalysisChoice> FusionDependenceAnalysis( 110 "loop-fusion-dependence-analysis", 111 cl::desc("Which dependence analysis should loop fusion use?"), 112 cl::values(clEnumValN(FUSION_DEPENDENCE_ANALYSIS_SCEV, "scev", 113 "Use the scalar evolution interface"), 114 clEnumValN(FUSION_DEPENDENCE_ANALYSIS_DA, "da", 115 "Use the dependence analysis interface"), 116 clEnumValN(FUSION_DEPENDENCE_ANALYSIS_ALL, "all", 117 "Use all available analyses")), 118 cl::Hidden, cl::init(FUSION_DEPENDENCE_ANALYSIS_ALL), cl::ZeroOrMore); 119 120 static cl::opt<unsigned> FusionPeelMaxCount( 121 "loop-fusion-peel-max-count", cl::init(0), cl::Hidden, 122 cl::desc("Max number of iterations to be peeled from a loop, such that " 123 "fusion can take place")); 124 125 #ifndef NDEBUG 126 static cl::opt<bool> 127 VerboseFusionDebugging("loop-fusion-verbose-debug", 128 cl::desc("Enable verbose debugging for Loop Fusion"), 129 cl::Hidden, cl::init(false), cl::ZeroOrMore); 130 #endif 131 132 namespace { 133 /// This class is used to represent a candidate for loop fusion. When it is 134 /// constructed, it checks the conditions for loop fusion to ensure that it 135 /// represents a valid candidate. It caches several parts of a loop that are 136 /// used throughout loop fusion (e.g., loop preheader, loop header, etc) instead 137 /// of continually querying the underlying Loop to retrieve these values. It is 138 /// assumed these will not change throughout loop fusion. 139 /// 140 /// The invalidate method should be used to indicate that the FusionCandidate is 141 /// no longer a valid candidate for fusion. Similarly, the isValid() method can 142 /// be used to ensure that the FusionCandidate is still valid for fusion. 143 struct FusionCandidate { 144 /// Cache of parts of the loop used throughout loop fusion. These should not 145 /// need to change throughout the analysis and transformation. 146 /// These parts are cached to avoid repeatedly looking up in the Loop class. 147 148 /// Preheader of the loop this candidate represents 149 BasicBlock *Preheader; 150 /// Header of the loop this candidate represents 151 BasicBlock *Header; 152 /// Blocks in the loop that exit the loop 153 BasicBlock *ExitingBlock; 154 /// The successor block of this loop (where the exiting blocks go to) 155 BasicBlock *ExitBlock; 156 /// Latch of the loop 157 BasicBlock *Latch; 158 /// The loop that this fusion candidate represents 159 Loop *L; 160 /// Vector of instructions in this loop that read from memory 161 SmallVector<Instruction *, 16> MemReads; 162 /// Vector of instructions in this loop that write to memory 163 SmallVector<Instruction *, 16> MemWrites; 164 /// Are all of the members of this fusion candidate still valid 165 bool Valid; 166 /// Guard branch of the loop, if it exists 167 BranchInst *GuardBranch; 168 /// Peeling Paramaters of the Loop. 169 TTI::PeelingPreferences PP; 170 /// Can you Peel this Loop? 171 bool AbleToPeel; 172 /// Has this loop been Peeled 173 bool Peeled; 174 175 /// Dominator and PostDominator trees are needed for the 176 /// FusionCandidateCompare function, required by FusionCandidateSet to 177 /// determine where the FusionCandidate should be inserted into the set. These 178 /// are used to establish ordering of the FusionCandidates based on dominance. 179 const DominatorTree *DT; 180 const PostDominatorTree *PDT; 181 182 OptimizationRemarkEmitter &ORE; 183 184 FusionCandidate(Loop *L, const DominatorTree *DT, 185 const PostDominatorTree *PDT, OptimizationRemarkEmitter &ORE, 186 TTI::PeelingPreferences PP) 187 : Preheader(L->getLoopPreheader()), Header(L->getHeader()), 188 ExitingBlock(L->getExitingBlock()), ExitBlock(L->getExitBlock()), 189 Latch(L->getLoopLatch()), L(L), Valid(true), 190 GuardBranch(L->getLoopGuardBranch()), PP(PP), AbleToPeel(canPeel(L)), 191 Peeled(false), DT(DT), PDT(PDT), ORE(ORE) { 192 193 // Walk over all blocks in the loop and check for conditions that may 194 // prevent fusion. For each block, walk over all instructions and collect 195 // the memory reads and writes If any instructions that prevent fusion are 196 // found, invalidate this object and return. 197 for (BasicBlock *BB : L->blocks()) { 198 if (BB->hasAddressTaken()) { 199 invalidate(); 200 reportInvalidCandidate(AddressTakenBB); 201 return; 202 } 203 204 for (Instruction &I : *BB) { 205 if (I.mayThrow()) { 206 invalidate(); 207 reportInvalidCandidate(MayThrowException); 208 return; 209 } 210 if (StoreInst *SI = dyn_cast<StoreInst>(&I)) { 211 if (SI->isVolatile()) { 212 invalidate(); 213 reportInvalidCandidate(ContainsVolatileAccess); 214 return; 215 } 216 } 217 if (LoadInst *LI = dyn_cast<LoadInst>(&I)) { 218 if (LI->isVolatile()) { 219 invalidate(); 220 reportInvalidCandidate(ContainsVolatileAccess); 221 return; 222 } 223 } 224 if (I.mayWriteToMemory()) 225 MemWrites.push_back(&I); 226 if (I.mayReadFromMemory()) 227 MemReads.push_back(&I); 228 } 229 } 230 } 231 232 /// Check if all members of the class are valid. 233 bool isValid() const { 234 return Preheader && Header && ExitingBlock && ExitBlock && Latch && L && 235 !L->isInvalid() && Valid; 236 } 237 238 /// Verify that all members are in sync with the Loop object. 239 void verify() const { 240 assert(isValid() && "Candidate is not valid!!"); 241 assert(!L->isInvalid() && "Loop is invalid!"); 242 assert(Preheader == L->getLoopPreheader() && "Preheader is out of sync"); 243 assert(Header == L->getHeader() && "Header is out of sync"); 244 assert(ExitingBlock == L->getExitingBlock() && 245 "Exiting Blocks is out of sync"); 246 assert(ExitBlock == L->getExitBlock() && "Exit block is out of sync"); 247 assert(Latch == L->getLoopLatch() && "Latch is out of sync"); 248 } 249 250 /// Get the entry block for this fusion candidate. 251 /// 252 /// If this fusion candidate represents a guarded loop, the entry block is the 253 /// loop guard block. If it represents an unguarded loop, the entry block is 254 /// the preheader of the loop. 255 BasicBlock *getEntryBlock() const { 256 if (GuardBranch) 257 return GuardBranch->getParent(); 258 else 259 return Preheader; 260 } 261 262 /// After Peeling the loop is modified quite a bit, hence all of the Blocks 263 /// need to be updated accordingly. 264 void updateAfterPeeling() { 265 Preheader = L->getLoopPreheader(); 266 Header = L->getHeader(); 267 ExitingBlock = L->getExitingBlock(); 268 ExitBlock = L->getExitBlock(); 269 Latch = L->getLoopLatch(); 270 verify(); 271 } 272 273 /// Given a guarded loop, get the successor of the guard that is not in the 274 /// loop. 275 /// 276 /// This method returns the successor of the loop guard that is not located 277 /// within the loop (i.e., the successor of the guard that is not the 278 /// preheader). 279 /// This method is only valid for guarded loops. 280 BasicBlock *getNonLoopBlock() const { 281 assert(GuardBranch && "Only valid on guarded loops."); 282 assert(GuardBranch->isConditional() && 283 "Expecting guard to be a conditional branch."); 284 if (Peeled) 285 return GuardBranch->getSuccessor(1); 286 return (GuardBranch->getSuccessor(0) == Preheader) 287 ? GuardBranch->getSuccessor(1) 288 : GuardBranch->getSuccessor(0); 289 } 290 291 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 292 LLVM_DUMP_METHOD void dump() const { 293 dbgs() << "\tGuardBranch: "; 294 if (GuardBranch) 295 dbgs() << *GuardBranch; 296 else 297 dbgs() << "nullptr"; 298 dbgs() << "\n" 299 << (GuardBranch ? GuardBranch->getName() : "nullptr") << "\n" 300 << "\tPreheader: " << (Preheader ? Preheader->getName() : "nullptr") 301 << "\n" 302 << "\tHeader: " << (Header ? Header->getName() : "nullptr") << "\n" 303 << "\tExitingBB: " 304 << (ExitingBlock ? ExitingBlock->getName() : "nullptr") << "\n" 305 << "\tExitBB: " << (ExitBlock ? ExitBlock->getName() : "nullptr") 306 << "\n" 307 << "\tLatch: " << (Latch ? Latch->getName() : "nullptr") << "\n" 308 << "\tEntryBlock: " 309 << (getEntryBlock() ? getEntryBlock()->getName() : "nullptr") 310 << "\n"; 311 } 312 #endif 313 314 /// Determine if a fusion candidate (representing a loop) is eligible for 315 /// fusion. Note that this only checks whether a single loop can be fused - it 316 /// does not check whether it is *legal* to fuse two loops together. 317 bool isEligibleForFusion(ScalarEvolution &SE) const { 318 if (!isValid()) { 319 LLVM_DEBUG(dbgs() << "FC has invalid CFG requirements!\n"); 320 if (!Preheader) 321 ++InvalidPreheader; 322 if (!Header) 323 ++InvalidHeader; 324 if (!ExitingBlock) 325 ++InvalidExitingBlock; 326 if (!ExitBlock) 327 ++InvalidExitBlock; 328 if (!Latch) 329 ++InvalidLatch; 330 if (L->isInvalid()) 331 ++InvalidLoop; 332 333 return false; 334 } 335 336 // Require ScalarEvolution to be able to determine a trip count. 337 if (!SE.hasLoopInvariantBackedgeTakenCount(L)) { 338 LLVM_DEBUG(dbgs() << "Loop " << L->getName() 339 << " trip count not computable!\n"); 340 return reportInvalidCandidate(UnknownTripCount); 341 } 342 343 if (!L->isLoopSimplifyForm()) { 344 LLVM_DEBUG(dbgs() << "Loop " << L->getName() 345 << " is not in simplified form!\n"); 346 return reportInvalidCandidate(NotSimplifiedForm); 347 } 348 349 if (!L->isRotatedForm()) { 350 LLVM_DEBUG(dbgs() << "Loop " << L->getName() << " is not rotated!\n"); 351 return reportInvalidCandidate(NotRotated); 352 } 353 354 return true; 355 } 356 357 private: 358 // This is only used internally for now, to clear the MemWrites and MemReads 359 // list and setting Valid to false. I can't envision other uses of this right 360 // now, since once FusionCandidates are put into the FusionCandidateSet they 361 // are immutable. Thus, any time we need to change/update a FusionCandidate, 362 // we must create a new one and insert it into the FusionCandidateSet to 363 // ensure the FusionCandidateSet remains ordered correctly. 364 void invalidate() { 365 MemWrites.clear(); 366 MemReads.clear(); 367 Valid = false; 368 } 369 370 bool reportInvalidCandidate(llvm::Statistic &Stat) const { 371 using namespace ore; 372 assert(L && Preheader && "Fusion candidate not initialized properly!"); 373 ++Stat; 374 ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE, Stat.getName(), 375 L->getStartLoc(), Preheader) 376 << "[" << Preheader->getParent()->getName() << "]: " 377 << "Loop is not a candidate for fusion: " << Stat.getDesc()); 378 return false; 379 } 380 }; 381 382 struct FusionCandidateCompare { 383 /// Comparison functor to sort two Control Flow Equivalent fusion candidates 384 /// into dominance order. 385 /// If LHS dominates RHS and RHS post-dominates LHS, return true; 386 /// IF RHS dominates LHS and LHS post-dominates RHS, return false; 387 bool operator()(const FusionCandidate &LHS, 388 const FusionCandidate &RHS) const { 389 const DominatorTree *DT = LHS.DT; 390 391 BasicBlock *LHSEntryBlock = LHS.getEntryBlock(); 392 BasicBlock *RHSEntryBlock = RHS.getEntryBlock(); 393 394 // Do not save PDT to local variable as it is only used in asserts and thus 395 // will trigger an unused variable warning if building without asserts. 396 assert(DT && LHS.PDT && "Expecting valid dominator tree"); 397 398 // Do this compare first so if LHS == RHS, function returns false. 399 if (DT->dominates(RHSEntryBlock, LHSEntryBlock)) { 400 // RHS dominates LHS 401 // Verify LHS post-dominates RHS 402 assert(LHS.PDT->dominates(LHSEntryBlock, RHSEntryBlock)); 403 return false; 404 } 405 406 if (DT->dominates(LHSEntryBlock, RHSEntryBlock)) { 407 // Verify RHS Postdominates LHS 408 assert(LHS.PDT->dominates(RHSEntryBlock, LHSEntryBlock)); 409 return true; 410 } 411 412 // If LHS does not dominate RHS and RHS does not dominate LHS then there is 413 // no dominance relationship between the two FusionCandidates. Thus, they 414 // should not be in the same set together. 415 llvm_unreachable( 416 "No dominance relationship between these fusion candidates!"); 417 } 418 }; 419 420 using LoopVector = SmallVector<Loop *, 4>; 421 422 // Set of Control Flow Equivalent (CFE) Fusion Candidates, sorted in dominance 423 // order. Thus, if FC0 comes *before* FC1 in a FusionCandidateSet, then FC0 424 // dominates FC1 and FC1 post-dominates FC0. 425 // std::set was chosen because we want a sorted data structure with stable 426 // iterators. A subsequent patch to loop fusion will enable fusing non-ajdacent 427 // loops by moving intervening code around. When this intervening code contains 428 // loops, those loops will be moved also. The corresponding FusionCandidates 429 // will also need to be moved accordingly. As this is done, having stable 430 // iterators will simplify the logic. Similarly, having an efficient insert that 431 // keeps the FusionCandidateSet sorted will also simplify the implementation. 432 using FusionCandidateSet = std::set<FusionCandidate, FusionCandidateCompare>; 433 using FusionCandidateCollection = SmallVector<FusionCandidateSet, 4>; 434 435 #if !defined(NDEBUG) 436 static llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, 437 const FusionCandidate &FC) { 438 if (FC.isValid()) 439 OS << FC.Preheader->getName(); 440 else 441 OS << "<Invalid>"; 442 443 return OS; 444 } 445 446 static llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, 447 const FusionCandidateSet &CandSet) { 448 for (const FusionCandidate &FC : CandSet) 449 OS << FC << '\n'; 450 451 return OS; 452 } 453 454 static void 455 printFusionCandidates(const FusionCandidateCollection &FusionCandidates) { 456 dbgs() << "Fusion Candidates: \n"; 457 for (const auto &CandidateSet : FusionCandidates) { 458 dbgs() << "*** Fusion Candidate Set ***\n"; 459 dbgs() << CandidateSet; 460 dbgs() << "****************************\n"; 461 } 462 } 463 #endif 464 465 /// Collect all loops in function at the same nest level, starting at the 466 /// outermost level. 467 /// 468 /// This data structure collects all loops at the same nest level for a 469 /// given function (specified by the LoopInfo object). It starts at the 470 /// outermost level. 471 struct LoopDepthTree { 472 using LoopsOnLevelTy = SmallVector<LoopVector, 4>; 473 using iterator = LoopsOnLevelTy::iterator; 474 using const_iterator = LoopsOnLevelTy::const_iterator; 475 476 LoopDepthTree(LoopInfo &LI) : Depth(1) { 477 if (!LI.empty()) 478 LoopsOnLevel.emplace_back(LoopVector(LI.rbegin(), LI.rend())); 479 } 480 481 /// Test whether a given loop has been removed from the function, and thus is 482 /// no longer valid. 483 bool isRemovedLoop(const Loop *L) const { return RemovedLoops.count(L); } 484 485 /// Record that a given loop has been removed from the function and is no 486 /// longer valid. 487 void removeLoop(const Loop *L) { RemovedLoops.insert(L); } 488 489 /// Descend the tree to the next (inner) nesting level 490 void descend() { 491 LoopsOnLevelTy LoopsOnNextLevel; 492 493 for (const LoopVector &LV : *this) 494 for (Loop *L : LV) 495 if (!isRemovedLoop(L) && L->begin() != L->end()) 496 LoopsOnNextLevel.emplace_back(LoopVector(L->begin(), L->end())); 497 498 LoopsOnLevel = LoopsOnNextLevel; 499 RemovedLoops.clear(); 500 Depth++; 501 } 502 503 bool empty() const { return size() == 0; } 504 size_t size() const { return LoopsOnLevel.size() - RemovedLoops.size(); } 505 unsigned getDepth() const { return Depth; } 506 507 iterator begin() { return LoopsOnLevel.begin(); } 508 iterator end() { return LoopsOnLevel.end(); } 509 const_iterator begin() const { return LoopsOnLevel.begin(); } 510 const_iterator end() const { return LoopsOnLevel.end(); } 511 512 private: 513 /// Set of loops that have been removed from the function and are no longer 514 /// valid. 515 SmallPtrSet<const Loop *, 8> RemovedLoops; 516 517 /// Depth of the current level, starting at 1 (outermost loops). 518 unsigned Depth; 519 520 /// Vector of loops at the current depth level that have the same parent loop 521 LoopsOnLevelTy LoopsOnLevel; 522 }; 523 524 #ifndef NDEBUG 525 static void printLoopVector(const LoopVector &LV) { 526 dbgs() << "****************************\n"; 527 for (auto L : LV) 528 printLoop(*L, dbgs()); 529 dbgs() << "****************************\n"; 530 } 531 #endif 532 533 struct LoopFuser { 534 private: 535 // Sets of control flow equivalent fusion candidates for a given nest level. 536 FusionCandidateCollection FusionCandidates; 537 538 LoopDepthTree LDT; 539 DomTreeUpdater DTU; 540 541 LoopInfo &LI; 542 DominatorTree &DT; 543 DependenceInfo &DI; 544 ScalarEvolution &SE; 545 PostDominatorTree &PDT; 546 OptimizationRemarkEmitter &ORE; 547 AssumptionCache &AC; 548 549 const TargetTransformInfo &TTI; 550 551 public: 552 LoopFuser(LoopInfo &LI, DominatorTree &DT, DependenceInfo &DI, 553 ScalarEvolution &SE, PostDominatorTree &PDT, 554 OptimizationRemarkEmitter &ORE, const DataLayout &DL, 555 AssumptionCache &AC, const TargetTransformInfo &TTI) 556 : LDT(LI), DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy), LI(LI), 557 DT(DT), DI(DI), SE(SE), PDT(PDT), ORE(ORE), AC(AC), TTI(TTI) {} 558 559 /// This is the main entry point for loop fusion. It will traverse the 560 /// specified function and collect candidate loops to fuse, starting at the 561 /// outermost nesting level and working inwards. 562 bool fuseLoops(Function &F) { 563 #ifndef NDEBUG 564 if (VerboseFusionDebugging) { 565 LI.print(dbgs()); 566 } 567 #endif 568 569 LLVM_DEBUG(dbgs() << "Performing Loop Fusion on function " << F.getName() 570 << "\n"); 571 bool Changed = false; 572 573 while (!LDT.empty()) { 574 LLVM_DEBUG(dbgs() << "Got " << LDT.size() << " loop sets for depth " 575 << LDT.getDepth() << "\n";); 576 577 for (const LoopVector &LV : LDT) { 578 assert(LV.size() > 0 && "Empty loop set was build!"); 579 580 // Skip singleton loop sets as they do not offer fusion opportunities on 581 // this level. 582 if (LV.size() == 1) 583 continue; 584 #ifndef NDEBUG 585 if (VerboseFusionDebugging) { 586 LLVM_DEBUG({ 587 dbgs() << " Visit loop set (#" << LV.size() << "):\n"; 588 printLoopVector(LV); 589 }); 590 } 591 #endif 592 593 collectFusionCandidates(LV); 594 Changed |= fuseCandidates(); 595 } 596 597 // Finished analyzing candidates at this level. 598 // Descend to the next level and clear all of the candidates currently 599 // collected. Note that it will not be possible to fuse any of the 600 // existing candidates with new candidates because the new candidates will 601 // be at a different nest level and thus not be control flow equivalent 602 // with all of the candidates collected so far. 603 LLVM_DEBUG(dbgs() << "Descend one level!\n"); 604 LDT.descend(); 605 FusionCandidates.clear(); 606 } 607 608 if (Changed) 609 LLVM_DEBUG(dbgs() << "Function after Loop Fusion: \n"; F.dump();); 610 611 #ifndef NDEBUG 612 assert(DT.verify()); 613 assert(PDT.verify()); 614 LI.verify(DT); 615 SE.verify(); 616 #endif 617 618 LLVM_DEBUG(dbgs() << "Loop Fusion complete\n"); 619 return Changed; 620 } 621 622 private: 623 /// Determine if two fusion candidates are control flow equivalent. 624 /// 625 /// Two fusion candidates are control flow equivalent if when one executes, 626 /// the other is guaranteed to execute. This is determined using dominators 627 /// and post-dominators: if A dominates B and B post-dominates A then A and B 628 /// are control-flow equivalent. 629 bool isControlFlowEquivalent(const FusionCandidate &FC0, 630 const FusionCandidate &FC1) const { 631 assert(FC0.Preheader && FC1.Preheader && "Expecting valid preheaders"); 632 633 return ::isControlFlowEquivalent(*FC0.getEntryBlock(), *FC1.getEntryBlock(), 634 DT, PDT); 635 } 636 637 /// Iterate over all loops in the given loop set and identify the loops that 638 /// are eligible for fusion. Place all eligible fusion candidates into Control 639 /// Flow Equivalent sets, sorted by dominance. 640 void collectFusionCandidates(const LoopVector &LV) { 641 for (Loop *L : LV) { 642 TTI::PeelingPreferences PP = 643 gatherPeelingPreferences(L, SE, TTI, None, None); 644 FusionCandidate CurrCand(L, &DT, &PDT, ORE, PP); 645 if (!CurrCand.isEligibleForFusion(SE)) 646 continue; 647 648 // Go through each list in FusionCandidates and determine if L is control 649 // flow equivalent with the first loop in that list. If it is, append LV. 650 // If not, go to the next list. 651 // If no suitable list is found, start another list and add it to 652 // FusionCandidates. 653 bool FoundSet = false; 654 655 for (auto &CurrCandSet : FusionCandidates) { 656 if (isControlFlowEquivalent(*CurrCandSet.begin(), CurrCand)) { 657 CurrCandSet.insert(CurrCand); 658 FoundSet = true; 659 #ifndef NDEBUG 660 if (VerboseFusionDebugging) 661 LLVM_DEBUG(dbgs() << "Adding " << CurrCand 662 << " to existing candidate set\n"); 663 #endif 664 break; 665 } 666 } 667 if (!FoundSet) { 668 // No set was found. Create a new set and add to FusionCandidates 669 #ifndef NDEBUG 670 if (VerboseFusionDebugging) 671 LLVM_DEBUG(dbgs() << "Adding " << CurrCand << " to new set\n"); 672 #endif 673 FusionCandidateSet NewCandSet; 674 NewCandSet.insert(CurrCand); 675 FusionCandidates.push_back(NewCandSet); 676 } 677 NumFusionCandidates++; 678 } 679 } 680 681 /// Determine if it is beneficial to fuse two loops. 682 /// 683 /// For now, this method simply returns true because we want to fuse as much 684 /// as possible (primarily to test the pass). This method will evolve, over 685 /// time, to add heuristics for profitability of fusion. 686 bool isBeneficialFusion(const FusionCandidate &FC0, 687 const FusionCandidate &FC1) { 688 return true; 689 } 690 691 /// Determine if two fusion candidates have the same trip count (i.e., they 692 /// execute the same number of iterations). 693 /// 694 /// This function will return a pair of values. The first is a boolean, 695 /// stating whether or not the two candidates are known at compile time to 696 /// have the same TripCount. The second is the difference in the two 697 /// TripCounts. This information can be used later to determine whether or not 698 /// peeling can be performed on either one of the candiates. 699 std::pair<bool, Optional<unsigned>> 700 haveIdenticalTripCounts(const FusionCandidate &FC0, 701 const FusionCandidate &FC1) const { 702 703 const SCEV *TripCount0 = SE.getBackedgeTakenCount(FC0.L); 704 if (isa<SCEVCouldNotCompute>(TripCount0)) { 705 UncomputableTripCount++; 706 LLVM_DEBUG(dbgs() << "Trip count of first loop could not be computed!"); 707 return {false, None}; 708 } 709 710 const SCEV *TripCount1 = SE.getBackedgeTakenCount(FC1.L); 711 if (isa<SCEVCouldNotCompute>(TripCount1)) { 712 UncomputableTripCount++; 713 LLVM_DEBUG(dbgs() << "Trip count of second loop could not be computed!"); 714 return {false, None}; 715 } 716 717 LLVM_DEBUG(dbgs() << "\tTrip counts: " << *TripCount0 << " & " 718 << *TripCount1 << " are " 719 << (TripCount0 == TripCount1 ? "identical" : "different") 720 << "\n"); 721 722 if (TripCount0 == TripCount1) 723 return {true, 0}; 724 725 LLVM_DEBUG(dbgs() << "The loops do not have the same tripcount, " 726 "determining the difference between trip counts\n"); 727 728 // Currently only considering loops with a single exit point 729 // and a non-constant trip count. 730 const unsigned TC0 = SE.getSmallConstantTripCount(FC0.L); 731 const unsigned TC1 = SE.getSmallConstantTripCount(FC1.L); 732 733 // If any of the tripcounts are zero that means that loop(s) do not have 734 // a single exit or a constant tripcount. 735 if (TC0 == 0 || TC1 == 0) { 736 LLVM_DEBUG(dbgs() << "Loop(s) do not have a single exit point or do not " 737 "have a constant number of iterations. Peeling " 738 "is not benefical\n"); 739 return {false, None}; 740 } 741 742 Optional<unsigned> Difference = None; 743 int Diff = TC0 - TC1; 744 745 if (Diff > 0) 746 Difference = Diff; 747 else { 748 LLVM_DEBUG( 749 dbgs() << "Difference is less than 0. FC1 (second loop) has more " 750 "iterations than the first one. Currently not supported\n"); 751 } 752 753 LLVM_DEBUG(dbgs() << "Difference in loop trip count is: " << Difference 754 << "\n"); 755 756 return {false, Difference}; 757 } 758 759 void peelFusionCandidate(FusionCandidate &FC0, const FusionCandidate &FC1, 760 unsigned PeelCount) { 761 assert(FC0.AbleToPeel && "Should be able to peel loop"); 762 763 LLVM_DEBUG(dbgs() << "Attempting to peel first " << PeelCount 764 << " iterations of the first loop. \n"); 765 766 FC0.Peeled = peelLoop(FC0.L, PeelCount, &LI, &SE, &DT, &AC, true); 767 if (FC0.Peeled) { 768 LLVM_DEBUG(dbgs() << "Done Peeling\n"); 769 770 #ifndef NDEBUG 771 auto IdenticalTripCount = haveIdenticalTripCounts(FC0, FC1); 772 773 assert(IdenticalTripCount.first && *IdenticalTripCount.second == 0 && 774 "Loops should have identical trip counts after peeling"); 775 #endif 776 777 FC0.PP.PeelCount += PeelCount; 778 779 // Peeling does not update the PDT 780 PDT.recalculate(*FC0.Preheader->getParent()); 781 782 FC0.updateAfterPeeling(); 783 784 // In this case the iterations of the loop are constant, so the first 785 // loop will execute completely (will not jump from one of 786 // the peeled blocks to the second loop). Here we are updating the 787 // branch conditions of each of the peeled blocks, such that it will 788 // branch to its successor which is not the preheader of the second loop 789 // in the case of unguarded loops, or the succesors of the exit block of 790 // the first loop otherwise. Doing this update will ensure that the entry 791 // block of the first loop dominates the entry block of the second loop. 792 BasicBlock *BB = 793 FC0.GuardBranch ? FC0.ExitBlock->getUniqueSuccessor() : FC1.Preheader; 794 if (BB) { 795 SmallVector<DominatorTree::UpdateType, 8> TreeUpdates; 796 SmallVector<Instruction *, 8> WorkList; 797 for (BasicBlock *Pred : predecessors(BB)) { 798 if (Pred != FC0.ExitBlock) { 799 WorkList.emplace_back(Pred->getTerminator()); 800 TreeUpdates.emplace_back( 801 DominatorTree::UpdateType(DominatorTree::Delete, Pred, BB)); 802 } 803 } 804 // Cannot modify the predecessors inside the above loop as it will cause 805 // the iterators to be nullptrs, causing memory errors. 806 for (Instruction *CurrentBranch: WorkList) { 807 BasicBlock *Succ = CurrentBranch->getSuccessor(0); 808 if (Succ == BB) 809 Succ = CurrentBranch->getSuccessor(1); 810 ReplaceInstWithInst(CurrentBranch, BranchInst::Create(Succ)); 811 } 812 813 DTU.applyUpdates(TreeUpdates); 814 DTU.flush(); 815 } 816 LLVM_DEBUG( 817 dbgs() << "Sucessfully peeled " << FC0.PP.PeelCount 818 << " iterations from the first loop.\n" 819 "Both Loops have the same number of iterations now.\n"); 820 } 821 } 822 823 /// Walk each set of control flow equivalent fusion candidates and attempt to 824 /// fuse them. This does a single linear traversal of all candidates in the 825 /// set. The conditions for legal fusion are checked at this point. If a pair 826 /// of fusion candidates passes all legality checks, they are fused together 827 /// and a new fusion candidate is created and added to the FusionCandidateSet. 828 /// The original fusion candidates are then removed, as they are no longer 829 /// valid. 830 bool fuseCandidates() { 831 bool Fused = false; 832 LLVM_DEBUG(printFusionCandidates(FusionCandidates)); 833 for (auto &CandidateSet : FusionCandidates) { 834 if (CandidateSet.size() < 2) 835 continue; 836 837 LLVM_DEBUG(dbgs() << "Attempting fusion on Candidate Set:\n" 838 << CandidateSet << "\n"); 839 840 for (auto FC0 = CandidateSet.begin(); FC0 != CandidateSet.end(); ++FC0) { 841 assert(!LDT.isRemovedLoop(FC0->L) && 842 "Should not have removed loops in CandidateSet!"); 843 auto FC1 = FC0; 844 for (++FC1; FC1 != CandidateSet.end(); ++FC1) { 845 assert(!LDT.isRemovedLoop(FC1->L) && 846 "Should not have removed loops in CandidateSet!"); 847 848 LLVM_DEBUG(dbgs() << "Attempting to fuse candidate \n"; FC0->dump(); 849 dbgs() << " with\n"; FC1->dump(); dbgs() << "\n"); 850 851 FC0->verify(); 852 FC1->verify(); 853 854 // Check if the candidates have identical tripcounts (first value of 855 // pair), and if not check the difference in the tripcounts between 856 // the loops (second value of pair). The difference is not equal to 857 // None iff the loops iterate a constant number of times, and have a 858 // single exit. 859 std::pair<bool, Optional<unsigned>> IdenticalTripCountRes = 860 haveIdenticalTripCounts(*FC0, *FC1); 861 bool SameTripCount = IdenticalTripCountRes.first; 862 Optional<unsigned> TCDifference = IdenticalTripCountRes.second; 863 864 // Here we are checking that FC0 (the first loop) can be peeled, and 865 // both loops have different tripcounts. 866 if (FC0->AbleToPeel && !SameTripCount && TCDifference) { 867 if (*TCDifference > FusionPeelMaxCount) { 868 LLVM_DEBUG(dbgs() 869 << "Difference in loop trip counts: " << *TCDifference 870 << " is greater than maximum peel count specificed: " 871 << FusionPeelMaxCount << "\n"); 872 } else { 873 // Dependent on peeling being performed on the first loop, and 874 // assuming all other conditions for fusion return true. 875 SameTripCount = true; 876 } 877 } 878 879 if (!SameTripCount) { 880 LLVM_DEBUG(dbgs() << "Fusion candidates do not have identical trip " 881 "counts. Not fusing.\n"); 882 reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1, 883 NonEqualTripCount); 884 continue; 885 } 886 887 if (!isAdjacent(*FC0, *FC1)) { 888 LLVM_DEBUG(dbgs() 889 << "Fusion candidates are not adjacent. Not fusing.\n"); 890 reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1, NonAdjacent); 891 continue; 892 } 893 894 // Ensure that FC0 and FC1 have identical guards. 895 // If one (or both) are not guarded, this check is not necessary. 896 if (FC0->GuardBranch && FC1->GuardBranch && 897 !haveIdenticalGuards(*FC0, *FC1) && !TCDifference) { 898 LLVM_DEBUG(dbgs() << "Fusion candidates do not have identical " 899 "guards. Not Fusing.\n"); 900 reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1, 901 NonIdenticalGuards); 902 continue; 903 } 904 905 if (!isSafeToMoveBefore(*FC1->Preheader, 906 *FC0->Preheader->getTerminator(), DT, &PDT, 907 &DI)) { 908 LLVM_DEBUG(dbgs() << "Fusion candidate contains unsafe " 909 "instructions in preheader. Not fusing.\n"); 910 reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1, 911 NonEmptyPreheader); 912 continue; 913 } 914 915 if (FC0->GuardBranch) { 916 assert(FC1->GuardBranch && "Expecting valid FC1 guard branch"); 917 918 if (!isSafeToMoveBefore(*FC0->ExitBlock, 919 *FC1->ExitBlock->getFirstNonPHIOrDbg(), DT, 920 &PDT, &DI)) { 921 LLVM_DEBUG(dbgs() << "Fusion candidate contains unsafe " 922 "instructions in exit block. Not fusing.\n"); 923 reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1, 924 NonEmptyExitBlock); 925 continue; 926 } 927 928 if (!isSafeToMoveBefore( 929 *FC1->GuardBranch->getParent(), 930 *FC0->GuardBranch->getParent()->getTerminator(), DT, &PDT, 931 &DI)) { 932 LLVM_DEBUG(dbgs() 933 << "Fusion candidate contains unsafe " 934 "instructions in guard block. Not fusing.\n"); 935 reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1, 936 NonEmptyGuardBlock); 937 continue; 938 } 939 } 940 941 // Check the dependencies across the loops and do not fuse if it would 942 // violate them. 943 if (!dependencesAllowFusion(*FC0, *FC1)) { 944 LLVM_DEBUG(dbgs() << "Memory dependencies do not allow fusion!\n"); 945 reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1, 946 InvalidDependencies); 947 continue; 948 } 949 950 bool BeneficialToFuse = isBeneficialFusion(*FC0, *FC1); 951 LLVM_DEBUG(dbgs() 952 << "\tFusion appears to be " 953 << (BeneficialToFuse ? "" : "un") << "profitable!\n"); 954 if (!BeneficialToFuse) { 955 reportLoopFusion<OptimizationRemarkMissed>(*FC0, *FC1, 956 FusionNotBeneficial); 957 continue; 958 } 959 // All analysis has completed and has determined that fusion is legal 960 // and profitable. At this point, start transforming the code and 961 // perform fusion. 962 963 LLVM_DEBUG(dbgs() << "\tFusion is performed: " << *FC0 << " and " 964 << *FC1 << "\n"); 965 966 FusionCandidate FC0Copy = *FC0; 967 // Peel the loop after determining that fusion is legal. The Loops 968 // will still be safe to fuse after the peeling is performed. 969 bool Peel = TCDifference && *TCDifference > 0; 970 if (Peel) 971 peelFusionCandidate(FC0Copy, *FC1, *TCDifference); 972 973 // Report fusion to the Optimization Remarks. 974 // Note this needs to be done *before* performFusion because 975 // performFusion will change the original loops, making it not 976 // possible to identify them after fusion is complete. 977 reportLoopFusion<OptimizationRemark>((Peel ? FC0Copy : *FC0), *FC1, 978 FuseCounter); 979 980 FusionCandidate FusedCand( 981 performFusion((Peel ? FC0Copy : *FC0), *FC1), &DT, &PDT, ORE, 982 FC0Copy.PP); 983 FusedCand.verify(); 984 assert(FusedCand.isEligibleForFusion(SE) && 985 "Fused candidate should be eligible for fusion!"); 986 987 // Notify the loop-depth-tree that these loops are not valid objects 988 LDT.removeLoop(FC1->L); 989 990 CandidateSet.erase(FC0); 991 CandidateSet.erase(FC1); 992 993 auto InsertPos = CandidateSet.insert(FusedCand); 994 995 assert(InsertPos.second && 996 "Unable to insert TargetCandidate in CandidateSet!"); 997 998 // Reset FC0 and FC1 the new (fused) candidate. Subsequent iterations 999 // of the FC1 loop will attempt to fuse the new (fused) loop with the 1000 // remaining candidates in the current candidate set. 1001 FC0 = FC1 = InsertPos.first; 1002 1003 LLVM_DEBUG(dbgs() << "Candidate Set (after fusion): " << CandidateSet 1004 << "\n"); 1005 1006 Fused = true; 1007 } 1008 } 1009 } 1010 return Fused; 1011 } 1012 1013 /// Rewrite all additive recurrences in a SCEV to use a new loop. 1014 class AddRecLoopReplacer : public SCEVRewriteVisitor<AddRecLoopReplacer> { 1015 public: 1016 AddRecLoopReplacer(ScalarEvolution &SE, const Loop &OldL, const Loop &NewL, 1017 bool UseMax = true) 1018 : SCEVRewriteVisitor(SE), Valid(true), UseMax(UseMax), OldL(OldL), 1019 NewL(NewL) {} 1020 1021 const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) { 1022 const Loop *ExprL = Expr->getLoop(); 1023 SmallVector<const SCEV *, 2> Operands; 1024 if (ExprL == &OldL) { 1025 Operands.append(Expr->op_begin(), Expr->op_end()); 1026 return SE.getAddRecExpr(Operands, &NewL, Expr->getNoWrapFlags()); 1027 } 1028 1029 if (OldL.contains(ExprL)) { 1030 bool Pos = SE.isKnownPositive(Expr->getStepRecurrence(SE)); 1031 if (!UseMax || !Pos || !Expr->isAffine()) { 1032 Valid = false; 1033 return Expr; 1034 } 1035 return visit(Expr->getStart()); 1036 } 1037 1038 for (const SCEV *Op : Expr->operands()) 1039 Operands.push_back(visit(Op)); 1040 return SE.getAddRecExpr(Operands, ExprL, Expr->getNoWrapFlags()); 1041 } 1042 1043 bool wasValidSCEV() const { return Valid; } 1044 1045 private: 1046 bool Valid, UseMax; 1047 const Loop &OldL, &NewL; 1048 }; 1049 1050 /// Return false if the access functions of \p I0 and \p I1 could cause 1051 /// a negative dependence. 1052 bool accessDiffIsPositive(const Loop &L0, const Loop &L1, Instruction &I0, 1053 Instruction &I1, bool EqualIsInvalid) { 1054 Value *Ptr0 = getLoadStorePointerOperand(&I0); 1055 Value *Ptr1 = getLoadStorePointerOperand(&I1); 1056 if (!Ptr0 || !Ptr1) 1057 return false; 1058 1059 const SCEV *SCEVPtr0 = SE.getSCEVAtScope(Ptr0, &L0); 1060 const SCEV *SCEVPtr1 = SE.getSCEVAtScope(Ptr1, &L1); 1061 #ifndef NDEBUG 1062 if (VerboseFusionDebugging) 1063 LLVM_DEBUG(dbgs() << " Access function check: " << *SCEVPtr0 << " vs " 1064 << *SCEVPtr1 << "\n"); 1065 #endif 1066 AddRecLoopReplacer Rewriter(SE, L0, L1); 1067 SCEVPtr0 = Rewriter.visit(SCEVPtr0); 1068 #ifndef NDEBUG 1069 if (VerboseFusionDebugging) 1070 LLVM_DEBUG(dbgs() << " Access function after rewrite: " << *SCEVPtr0 1071 << " [Valid: " << Rewriter.wasValidSCEV() << "]\n"); 1072 #endif 1073 if (!Rewriter.wasValidSCEV()) 1074 return false; 1075 1076 // TODO: isKnownPredicate doesnt work well when one SCEV is loop carried (by 1077 // L0) and the other is not. We could check if it is monotone and test 1078 // the beginning and end value instead. 1079 1080 BasicBlock *L0Header = L0.getHeader(); 1081 auto HasNonLinearDominanceRelation = [&](const SCEV *S) { 1082 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S); 1083 if (!AddRec) 1084 return false; 1085 return !DT.dominates(L0Header, AddRec->getLoop()->getHeader()) && 1086 !DT.dominates(AddRec->getLoop()->getHeader(), L0Header); 1087 }; 1088 if (SCEVExprContains(SCEVPtr1, HasNonLinearDominanceRelation)) 1089 return false; 1090 1091 ICmpInst::Predicate Pred = 1092 EqualIsInvalid ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_SGE; 1093 bool IsAlwaysGE = SE.isKnownPredicate(Pred, SCEVPtr0, SCEVPtr1); 1094 #ifndef NDEBUG 1095 if (VerboseFusionDebugging) 1096 LLVM_DEBUG(dbgs() << " Relation: " << *SCEVPtr0 1097 << (IsAlwaysGE ? " >= " : " may < ") << *SCEVPtr1 1098 << "\n"); 1099 #endif 1100 return IsAlwaysGE; 1101 } 1102 1103 /// Return true if the dependences between @p I0 (in @p L0) and @p I1 (in 1104 /// @p L1) allow loop fusion of @p L0 and @p L1. The dependence analyses 1105 /// specified by @p DepChoice are used to determine this. 1106 bool dependencesAllowFusion(const FusionCandidate &FC0, 1107 const FusionCandidate &FC1, Instruction &I0, 1108 Instruction &I1, bool AnyDep, 1109 FusionDependenceAnalysisChoice DepChoice) { 1110 #ifndef NDEBUG 1111 if (VerboseFusionDebugging) { 1112 LLVM_DEBUG(dbgs() << "Check dep: " << I0 << " vs " << I1 << " : " 1113 << DepChoice << "\n"); 1114 } 1115 #endif 1116 switch (DepChoice) { 1117 case FUSION_DEPENDENCE_ANALYSIS_SCEV: 1118 return accessDiffIsPositive(*FC0.L, *FC1.L, I0, I1, AnyDep); 1119 case FUSION_DEPENDENCE_ANALYSIS_DA: { 1120 auto DepResult = DI.depends(&I0, &I1, true); 1121 if (!DepResult) 1122 return true; 1123 #ifndef NDEBUG 1124 if (VerboseFusionDebugging) { 1125 LLVM_DEBUG(dbgs() << "DA res: "; DepResult->dump(dbgs()); 1126 dbgs() << " [#l: " << DepResult->getLevels() << "][Ordered: " 1127 << (DepResult->isOrdered() ? "true" : "false") 1128 << "]\n"); 1129 LLVM_DEBUG(dbgs() << "DepResult Levels: " << DepResult->getLevels() 1130 << "\n"); 1131 } 1132 #endif 1133 1134 if (DepResult->getNextPredecessor() || DepResult->getNextSuccessor()) 1135 LLVM_DEBUG( 1136 dbgs() << "TODO: Implement pred/succ dependence handling!\n"); 1137 1138 // TODO: Can we actually use the dependence info analysis here? 1139 return false; 1140 } 1141 1142 case FUSION_DEPENDENCE_ANALYSIS_ALL: 1143 return dependencesAllowFusion(FC0, FC1, I0, I1, AnyDep, 1144 FUSION_DEPENDENCE_ANALYSIS_SCEV) || 1145 dependencesAllowFusion(FC0, FC1, I0, I1, AnyDep, 1146 FUSION_DEPENDENCE_ANALYSIS_DA); 1147 } 1148 1149 llvm_unreachable("Unknown fusion dependence analysis choice!"); 1150 } 1151 1152 /// Perform a dependence check and return if @p FC0 and @p FC1 can be fused. 1153 bool dependencesAllowFusion(const FusionCandidate &FC0, 1154 const FusionCandidate &FC1) { 1155 LLVM_DEBUG(dbgs() << "Check if " << FC0 << " can be fused with " << FC1 1156 << "\n"); 1157 assert(FC0.L->getLoopDepth() == FC1.L->getLoopDepth()); 1158 assert(DT.dominates(FC0.getEntryBlock(), FC1.getEntryBlock())); 1159 1160 for (Instruction *WriteL0 : FC0.MemWrites) { 1161 for (Instruction *WriteL1 : FC1.MemWrites) 1162 if (!dependencesAllowFusion(FC0, FC1, *WriteL0, *WriteL1, 1163 /* AnyDep */ false, 1164 FusionDependenceAnalysis)) { 1165 InvalidDependencies++; 1166 return false; 1167 } 1168 for (Instruction *ReadL1 : FC1.MemReads) 1169 if (!dependencesAllowFusion(FC0, FC1, *WriteL0, *ReadL1, 1170 /* AnyDep */ false, 1171 FusionDependenceAnalysis)) { 1172 InvalidDependencies++; 1173 return false; 1174 } 1175 } 1176 1177 for (Instruction *WriteL1 : FC1.MemWrites) { 1178 for (Instruction *WriteL0 : FC0.MemWrites) 1179 if (!dependencesAllowFusion(FC0, FC1, *WriteL0, *WriteL1, 1180 /* AnyDep */ false, 1181 FusionDependenceAnalysis)) { 1182 InvalidDependencies++; 1183 return false; 1184 } 1185 for (Instruction *ReadL0 : FC0.MemReads) 1186 if (!dependencesAllowFusion(FC0, FC1, *ReadL0, *WriteL1, 1187 /* AnyDep */ false, 1188 FusionDependenceAnalysis)) { 1189 InvalidDependencies++; 1190 return false; 1191 } 1192 } 1193 1194 // Walk through all uses in FC1. For each use, find the reaching def. If the 1195 // def is located in FC0 then it is is not safe to fuse. 1196 for (BasicBlock *BB : FC1.L->blocks()) 1197 for (Instruction &I : *BB) 1198 for (auto &Op : I.operands()) 1199 if (Instruction *Def = dyn_cast<Instruction>(Op)) 1200 if (FC0.L->contains(Def->getParent())) { 1201 InvalidDependencies++; 1202 return false; 1203 } 1204 1205 return true; 1206 } 1207 1208 /// Determine if two fusion candidates are adjacent in the CFG. 1209 /// 1210 /// This method will determine if there are additional basic blocks in the CFG 1211 /// between the exit of \p FC0 and the entry of \p FC1. 1212 /// If the two candidates are guarded loops, then it checks whether the 1213 /// non-loop successor of the \p FC0 guard branch is the entry block of \p 1214 /// FC1. If not, then the loops are not adjacent. If the two candidates are 1215 /// not guarded loops, then it checks whether the exit block of \p FC0 is the 1216 /// preheader of \p FC1. 1217 bool isAdjacent(const FusionCandidate &FC0, 1218 const FusionCandidate &FC1) const { 1219 // If the successor of the guard branch is FC1, then the loops are adjacent 1220 if (FC0.GuardBranch) 1221 return FC0.getNonLoopBlock() == FC1.getEntryBlock(); 1222 else 1223 return FC0.ExitBlock == FC1.getEntryBlock(); 1224 } 1225 1226 /// Determine if two fusion candidates have identical guards 1227 /// 1228 /// This method will determine if two fusion candidates have the same guards. 1229 /// The guards are considered the same if: 1230 /// 1. The instructions to compute the condition used in the compare are 1231 /// identical. 1232 /// 2. The successors of the guard have the same flow into/around the loop. 1233 /// If the compare instructions are identical, then the first successor of the 1234 /// guard must go to the same place (either the preheader of the loop or the 1235 /// NonLoopBlock). In other words, the the first successor of both loops must 1236 /// both go into the loop (i.e., the preheader) or go around the loop (i.e., 1237 /// the NonLoopBlock). The same must be true for the second successor. 1238 bool haveIdenticalGuards(const FusionCandidate &FC0, 1239 const FusionCandidate &FC1) const { 1240 assert(FC0.GuardBranch && FC1.GuardBranch && 1241 "Expecting FC0 and FC1 to be guarded loops."); 1242 1243 if (auto FC0CmpInst = 1244 dyn_cast<Instruction>(FC0.GuardBranch->getCondition())) 1245 if (auto FC1CmpInst = 1246 dyn_cast<Instruction>(FC1.GuardBranch->getCondition())) 1247 if (!FC0CmpInst->isIdenticalTo(FC1CmpInst)) 1248 return false; 1249 1250 // The compare instructions are identical. 1251 // Now make sure the successor of the guards have the same flow into/around 1252 // the loop 1253 if (FC0.GuardBranch->getSuccessor(0) == FC0.Preheader) 1254 return (FC1.GuardBranch->getSuccessor(0) == FC1.Preheader); 1255 else 1256 return (FC1.GuardBranch->getSuccessor(1) == FC1.Preheader); 1257 } 1258 1259 /// Modify the latch branch of FC to be unconditional since successors of the 1260 /// branch are the same. 1261 void simplifyLatchBranch(const FusionCandidate &FC) const { 1262 BranchInst *FCLatchBranch = dyn_cast<BranchInst>(FC.Latch->getTerminator()); 1263 if (FCLatchBranch) { 1264 assert(FCLatchBranch->isConditional() && 1265 FCLatchBranch->getSuccessor(0) == FCLatchBranch->getSuccessor(1) && 1266 "Expecting the two successors of FCLatchBranch to be the same"); 1267 BranchInst *NewBranch = 1268 BranchInst::Create(FCLatchBranch->getSuccessor(0)); 1269 ReplaceInstWithInst(FCLatchBranch, NewBranch); 1270 } 1271 } 1272 1273 /// Move instructions from FC0.Latch to FC1.Latch. If FC0.Latch has an unique 1274 /// successor, then merge FC0.Latch with its unique successor. 1275 void mergeLatch(const FusionCandidate &FC0, const FusionCandidate &FC1) { 1276 moveInstructionsToTheBeginning(*FC0.Latch, *FC1.Latch, DT, PDT, DI); 1277 if (BasicBlock *Succ = FC0.Latch->getUniqueSuccessor()) { 1278 MergeBlockIntoPredecessor(Succ, &DTU, &LI); 1279 DTU.flush(); 1280 } 1281 } 1282 1283 /// Fuse two fusion candidates, creating a new fused loop. 1284 /// 1285 /// This method contains the mechanics of fusing two loops, represented by \p 1286 /// FC0 and \p FC1. It is assumed that \p FC0 dominates \p FC1 and \p FC1 1287 /// postdominates \p FC0 (making them control flow equivalent). It also 1288 /// assumes that the other conditions for fusion have been met: adjacent, 1289 /// identical trip counts, and no negative distance dependencies exist that 1290 /// would prevent fusion. Thus, there is no checking for these conditions in 1291 /// this method. 1292 /// 1293 /// Fusion is performed by rewiring the CFG to update successor blocks of the 1294 /// components of tho loop. Specifically, the following changes are done: 1295 /// 1296 /// 1. The preheader of \p FC1 is removed as it is no longer necessary 1297 /// (because it is currently only a single statement block). 1298 /// 2. The latch of \p FC0 is modified to jump to the header of \p FC1. 1299 /// 3. The latch of \p FC1 i modified to jump to the header of \p FC0. 1300 /// 4. All blocks from \p FC1 are removed from FC1 and added to FC0. 1301 /// 1302 /// All of these modifications are done with dominator tree updates, thus 1303 /// keeping the dominator (and post dominator) information up-to-date. 1304 /// 1305 /// This can be improved in the future by actually merging blocks during 1306 /// fusion. For example, the preheader of \p FC1 can be merged with the 1307 /// preheader of \p FC0. This would allow loops with more than a single 1308 /// statement in the preheader to be fused. Similarly, the latch blocks of the 1309 /// two loops could also be fused into a single block. This will require 1310 /// analysis to prove it is safe to move the contents of the block past 1311 /// existing code, which currently has not been implemented. 1312 Loop *performFusion(const FusionCandidate &FC0, const FusionCandidate &FC1) { 1313 assert(FC0.isValid() && FC1.isValid() && 1314 "Expecting valid fusion candidates"); 1315 1316 LLVM_DEBUG(dbgs() << "Fusion Candidate 0: \n"; FC0.dump(); 1317 dbgs() << "Fusion Candidate 1: \n"; FC1.dump();); 1318 1319 // Move instructions from the preheader of FC1 to the end of the preheader 1320 // of FC0. 1321 moveInstructionsToTheEnd(*FC1.Preheader, *FC0.Preheader, DT, PDT, DI); 1322 1323 // Fusing guarded loops is handled slightly differently than non-guarded 1324 // loops and has been broken out into a separate method instead of trying to 1325 // intersperse the logic within a single method. 1326 if (FC0.GuardBranch) 1327 return fuseGuardedLoops(FC0, FC1); 1328 1329 assert(FC1.Preheader == 1330 (FC0.Peeled ? FC0.ExitBlock->getUniqueSuccessor() : FC0.ExitBlock)); 1331 assert(FC1.Preheader->size() == 1 && 1332 FC1.Preheader->getSingleSuccessor() == FC1.Header); 1333 1334 // Remember the phi nodes originally in the header of FC0 in order to rewire 1335 // them later. However, this is only necessary if the new loop carried 1336 // values might not dominate the exiting branch. While we do not generally 1337 // test if this is the case but simply insert intermediate phi nodes, we 1338 // need to make sure these intermediate phi nodes have different 1339 // predecessors. To this end, we filter the special case where the exiting 1340 // block is the latch block of the first loop. Nothing needs to be done 1341 // anyway as all loop carried values dominate the latch and thereby also the 1342 // exiting branch. 1343 SmallVector<PHINode *, 8> OriginalFC0PHIs; 1344 if (FC0.ExitingBlock != FC0.Latch) 1345 for (PHINode &PHI : FC0.Header->phis()) 1346 OriginalFC0PHIs.push_back(&PHI); 1347 1348 // Replace incoming blocks for header PHIs first. 1349 FC1.Preheader->replaceSuccessorsPhiUsesWith(FC0.Preheader); 1350 FC0.Latch->replaceSuccessorsPhiUsesWith(FC1.Latch); 1351 1352 // Then modify the control flow and update DT and PDT. 1353 SmallVector<DominatorTree::UpdateType, 8> TreeUpdates; 1354 1355 // The old exiting block of the first loop (FC0) has to jump to the header 1356 // of the second as we need to execute the code in the second header block 1357 // regardless of the trip count. That is, if the trip count is 0, so the 1358 // back edge is never taken, we still have to execute both loop headers, 1359 // especially (but not only!) if the second is a do-while style loop. 1360 // However, doing so might invalidate the phi nodes of the first loop as 1361 // the new values do only need to dominate their latch and not the exiting 1362 // predicate. To remedy this potential problem we always introduce phi 1363 // nodes in the header of the second loop later that select the loop carried 1364 // value, if the second header was reached through an old latch of the 1365 // first, or undef otherwise. This is sound as exiting the first implies the 1366 // second will exit too, __without__ taking the back-edge. [Their 1367 // trip-counts are equal after all. 1368 // KB: Would this sequence be simpler to just just make FC0.ExitingBlock go 1369 // to FC1.Header? I think this is basically what the three sequences are 1370 // trying to accomplish; however, doing this directly in the CFG may mean 1371 // the DT/PDT becomes invalid 1372 if (!FC0.Peeled) { 1373 FC0.ExitingBlock->getTerminator()->replaceUsesOfWith(FC1.Preheader, 1374 FC1.Header); 1375 TreeUpdates.emplace_back(DominatorTree::UpdateType( 1376 DominatorTree::Delete, FC0.ExitingBlock, FC1.Preheader)); 1377 TreeUpdates.emplace_back(DominatorTree::UpdateType( 1378 DominatorTree::Insert, FC0.ExitingBlock, FC1.Header)); 1379 } else { 1380 TreeUpdates.emplace_back(DominatorTree::UpdateType( 1381 DominatorTree::Delete, FC0.ExitBlock, FC1.Preheader)); 1382 1383 // Remove the ExitBlock of the first Loop (also not needed) 1384 FC0.ExitingBlock->getTerminator()->replaceUsesOfWith(FC0.ExitBlock, 1385 FC1.Header); 1386 TreeUpdates.emplace_back(DominatorTree::UpdateType( 1387 DominatorTree::Delete, FC0.ExitingBlock, FC0.ExitBlock)); 1388 FC0.ExitBlock->getTerminator()->eraseFromParent(); 1389 TreeUpdates.emplace_back(DominatorTree::UpdateType( 1390 DominatorTree::Insert, FC0.ExitingBlock, FC1.Header)); 1391 new UnreachableInst(FC0.ExitBlock->getContext(), FC0.ExitBlock); 1392 } 1393 1394 // The pre-header of L1 is not necessary anymore. 1395 assert(pred_empty(FC1.Preheader)); 1396 FC1.Preheader->getTerminator()->eraseFromParent(); 1397 new UnreachableInst(FC1.Preheader->getContext(), FC1.Preheader); 1398 TreeUpdates.emplace_back(DominatorTree::UpdateType( 1399 DominatorTree::Delete, FC1.Preheader, FC1.Header)); 1400 1401 // Moves the phi nodes from the second to the first loops header block. 1402 while (PHINode *PHI = dyn_cast<PHINode>(&FC1.Header->front())) { 1403 if (SE.isSCEVable(PHI->getType())) 1404 SE.forgetValue(PHI); 1405 if (PHI->hasNUsesOrMore(1)) 1406 PHI->moveBefore(&*FC0.Header->getFirstInsertionPt()); 1407 else 1408 PHI->eraseFromParent(); 1409 } 1410 1411 // Introduce new phi nodes in the second loop header to ensure 1412 // exiting the first and jumping to the header of the second does not break 1413 // the SSA property of the phis originally in the first loop. See also the 1414 // comment above. 1415 Instruction *L1HeaderIP = &FC1.Header->front(); 1416 for (PHINode *LCPHI : OriginalFC0PHIs) { 1417 int L1LatchBBIdx = LCPHI->getBasicBlockIndex(FC1.Latch); 1418 assert(L1LatchBBIdx >= 0 && 1419 "Expected loop carried value to be rewired at this point!"); 1420 1421 Value *LCV = LCPHI->getIncomingValue(L1LatchBBIdx); 1422 1423 PHINode *L1HeaderPHI = PHINode::Create( 1424 LCV->getType(), 2, LCPHI->getName() + ".afterFC0", L1HeaderIP); 1425 L1HeaderPHI->addIncoming(LCV, FC0.Latch); 1426 L1HeaderPHI->addIncoming(UndefValue::get(LCV->getType()), 1427 FC0.ExitingBlock); 1428 1429 LCPHI->setIncomingValue(L1LatchBBIdx, L1HeaderPHI); 1430 } 1431 1432 // Replace latch terminator destinations. 1433 FC0.Latch->getTerminator()->replaceUsesOfWith(FC0.Header, FC1.Header); 1434 FC1.Latch->getTerminator()->replaceUsesOfWith(FC1.Header, FC0.Header); 1435 1436 // Modify the latch branch of FC0 to be unconditional as both successors of 1437 // the branch are the same. 1438 simplifyLatchBranch(FC0); 1439 1440 // If FC0.Latch and FC0.ExitingBlock are the same then we have already 1441 // performed the updates above. 1442 if (FC0.Latch != FC0.ExitingBlock) 1443 TreeUpdates.emplace_back(DominatorTree::UpdateType( 1444 DominatorTree::Insert, FC0.Latch, FC1.Header)); 1445 1446 TreeUpdates.emplace_back(DominatorTree::UpdateType(DominatorTree::Delete, 1447 FC0.Latch, FC0.Header)); 1448 TreeUpdates.emplace_back(DominatorTree::UpdateType(DominatorTree::Insert, 1449 FC1.Latch, FC0.Header)); 1450 TreeUpdates.emplace_back(DominatorTree::UpdateType(DominatorTree::Delete, 1451 FC1.Latch, FC1.Header)); 1452 1453 // Update DT/PDT 1454 DTU.applyUpdates(TreeUpdates); 1455 1456 LI.removeBlock(FC1.Preheader); 1457 DTU.deleteBB(FC1.Preheader); 1458 if (FC0.Peeled) { 1459 LI.removeBlock(FC0.ExitBlock); 1460 DTU.deleteBB(FC0.ExitBlock); 1461 } 1462 1463 DTU.flush(); 1464 1465 // Is there a way to keep SE up-to-date so we don't need to forget the loops 1466 // and rebuild the information in subsequent passes of fusion? 1467 // Note: Need to forget the loops before merging the loop latches, as 1468 // mergeLatch may remove the only block in FC1. 1469 SE.forgetLoop(FC1.L); 1470 SE.forgetLoop(FC0.L); 1471 1472 // Move instructions from FC0.Latch to FC1.Latch. 1473 // Note: mergeLatch requires an updated DT. 1474 mergeLatch(FC0, FC1); 1475 1476 // Merge the loops. 1477 SmallVector<BasicBlock *, 8> Blocks(FC1.L->blocks()); 1478 for (BasicBlock *BB : Blocks) { 1479 FC0.L->addBlockEntry(BB); 1480 FC1.L->removeBlockFromLoop(BB); 1481 if (LI.getLoopFor(BB) != FC1.L) 1482 continue; 1483 LI.changeLoopFor(BB, FC0.L); 1484 } 1485 while (!FC1.L->isInnermost()) { 1486 const auto &ChildLoopIt = FC1.L->begin(); 1487 Loop *ChildLoop = *ChildLoopIt; 1488 FC1.L->removeChildLoop(ChildLoopIt); 1489 FC0.L->addChildLoop(ChildLoop); 1490 } 1491 1492 // Delete the now empty loop L1. 1493 LI.erase(FC1.L); 1494 1495 #ifndef NDEBUG 1496 assert(!verifyFunction(*FC0.Header->getParent(), &errs())); 1497 assert(DT.verify(DominatorTree::VerificationLevel::Fast)); 1498 assert(PDT.verify()); 1499 LI.verify(DT); 1500 SE.verify(); 1501 #endif 1502 1503 LLVM_DEBUG(dbgs() << "Fusion done:\n"); 1504 1505 return FC0.L; 1506 } 1507 1508 /// Report details on loop fusion opportunities. 1509 /// 1510 /// This template function can be used to report both successful and missed 1511 /// loop fusion opportunities, based on the RemarkKind. The RemarkKind should 1512 /// be one of: 1513 /// - OptimizationRemarkMissed to report when loop fusion is unsuccessful 1514 /// given two valid fusion candidates. 1515 /// - OptimizationRemark to report successful fusion of two fusion 1516 /// candidates. 1517 /// The remarks will be printed using the form: 1518 /// <path/filename>:<line number>:<column number>: [<function name>]: 1519 /// <Cand1 Preheader> and <Cand2 Preheader>: <Stat Description> 1520 template <typename RemarkKind> 1521 void reportLoopFusion(const FusionCandidate &FC0, const FusionCandidate &FC1, 1522 llvm::Statistic &Stat) { 1523 assert(FC0.Preheader && FC1.Preheader && 1524 "Expecting valid fusion candidates"); 1525 using namespace ore; 1526 ++Stat; 1527 ORE.emit(RemarkKind(DEBUG_TYPE, Stat.getName(), FC0.L->getStartLoc(), 1528 FC0.Preheader) 1529 << "[" << FC0.Preheader->getParent()->getName() 1530 << "]: " << NV("Cand1", StringRef(FC0.Preheader->getName())) 1531 << " and " << NV("Cand2", StringRef(FC1.Preheader->getName())) 1532 << ": " << Stat.getDesc()); 1533 } 1534 1535 /// Fuse two guarded fusion candidates, creating a new fused loop. 1536 /// 1537 /// Fusing guarded loops is handled much the same way as fusing non-guarded 1538 /// loops. The rewiring of the CFG is slightly different though, because of 1539 /// the presence of the guards around the loops and the exit blocks after the 1540 /// loop body. As such, the new loop is rewired as follows: 1541 /// 1. Keep the guard branch from FC0 and use the non-loop block target 1542 /// from the FC1 guard branch. 1543 /// 2. Remove the exit block from FC0 (this exit block should be empty 1544 /// right now). 1545 /// 3. Remove the guard branch for FC1 1546 /// 4. Remove the preheader for FC1. 1547 /// The exit block successor for the latch of FC0 is updated to be the header 1548 /// of FC1 and the non-exit block successor of the latch of FC1 is updated to 1549 /// be the header of FC0, thus creating the fused loop. 1550 Loop *fuseGuardedLoops(const FusionCandidate &FC0, 1551 const FusionCandidate &FC1) { 1552 assert(FC0.GuardBranch && FC1.GuardBranch && "Expecting guarded loops"); 1553 1554 BasicBlock *FC0GuardBlock = FC0.GuardBranch->getParent(); 1555 BasicBlock *FC1GuardBlock = FC1.GuardBranch->getParent(); 1556 BasicBlock *FC0NonLoopBlock = FC0.getNonLoopBlock(); 1557 BasicBlock *FC1NonLoopBlock = FC1.getNonLoopBlock(); 1558 BasicBlock *FC0ExitBlockSuccessor = FC0.ExitBlock->getUniqueSuccessor(); 1559 1560 // Move instructions from the exit block of FC0 to the beginning of the exit 1561 // block of FC1, in the case that the FC0 loop has not been peeled. In the 1562 // case that FC0 loop is peeled, then move the instructions of the successor 1563 // of the FC0 Exit block to the beginning of the exit block of FC1. 1564 moveInstructionsToTheBeginning( 1565 (FC0.Peeled ? *FC0ExitBlockSuccessor : *FC0.ExitBlock), *FC1.ExitBlock, 1566 DT, PDT, DI); 1567 1568 // Move instructions from the guard block of FC1 to the end of the guard 1569 // block of FC0. 1570 moveInstructionsToTheEnd(*FC1GuardBlock, *FC0GuardBlock, DT, PDT, DI); 1571 1572 assert(FC0NonLoopBlock == FC1GuardBlock && "Loops are not adjacent"); 1573 1574 SmallVector<DominatorTree::UpdateType, 8> TreeUpdates; 1575 1576 //////////////////////////////////////////////////////////////////////////// 1577 // Update the Loop Guard 1578 //////////////////////////////////////////////////////////////////////////// 1579 // The guard for FC0 is updated to guard both FC0 and FC1. This is done by 1580 // changing the NonLoopGuardBlock for FC0 to the NonLoopGuardBlock for FC1. 1581 // Thus, one path from the guard goes to the preheader for FC0 (and thus 1582 // executes the new fused loop) and the other path goes to the NonLoopBlock 1583 // for FC1 (where FC1 guard would have gone if FC1 was not executed). 1584 FC1NonLoopBlock->replacePhiUsesWith(FC1GuardBlock, FC0GuardBlock); 1585 FC0.GuardBranch->replaceUsesOfWith(FC0NonLoopBlock, FC1NonLoopBlock); 1586 1587 BasicBlock *BBToUpdate = FC0.Peeled ? FC0ExitBlockSuccessor : FC0.ExitBlock; 1588 BBToUpdate->getTerminator()->replaceUsesOfWith(FC1GuardBlock, FC1.Header); 1589 1590 // The guard of FC1 is not necessary anymore. 1591 FC1.GuardBranch->eraseFromParent(); 1592 new UnreachableInst(FC1GuardBlock->getContext(), FC1GuardBlock); 1593 1594 TreeUpdates.emplace_back(DominatorTree::UpdateType( 1595 DominatorTree::Delete, FC1GuardBlock, FC1.Preheader)); 1596 TreeUpdates.emplace_back(DominatorTree::UpdateType( 1597 DominatorTree::Delete, FC1GuardBlock, FC1NonLoopBlock)); 1598 TreeUpdates.emplace_back(DominatorTree::UpdateType( 1599 DominatorTree::Delete, FC0GuardBlock, FC1GuardBlock)); 1600 TreeUpdates.emplace_back(DominatorTree::UpdateType( 1601 DominatorTree::Insert, FC0GuardBlock, FC1NonLoopBlock)); 1602 1603 if (FC0.Peeled) { 1604 // Remove the Block after the ExitBlock of FC0 1605 TreeUpdates.emplace_back(DominatorTree::UpdateType( 1606 DominatorTree::Delete, FC0ExitBlockSuccessor, FC1GuardBlock)); 1607 FC0ExitBlockSuccessor->getTerminator()->eraseFromParent(); 1608 new UnreachableInst(FC0ExitBlockSuccessor->getContext(), 1609 FC0ExitBlockSuccessor); 1610 } 1611 1612 assert(pred_empty(FC1GuardBlock) && 1613 "Expecting guard block to have no predecessors"); 1614 assert(succ_empty(FC1GuardBlock) && 1615 "Expecting guard block to have no successors"); 1616 1617 // Remember the phi nodes originally in the header of FC0 in order to rewire 1618 // them later. However, this is only necessary if the new loop carried 1619 // values might not dominate the exiting branch. While we do not generally 1620 // test if this is the case but simply insert intermediate phi nodes, we 1621 // need to make sure these intermediate phi nodes have different 1622 // predecessors. To this end, we filter the special case where the exiting 1623 // block is the latch block of the first loop. Nothing needs to be done 1624 // anyway as all loop carried values dominate the latch and thereby also the 1625 // exiting branch. 1626 // KB: This is no longer necessary because FC0.ExitingBlock == FC0.Latch 1627 // (because the loops are rotated. Thus, nothing will ever be added to 1628 // OriginalFC0PHIs. 1629 SmallVector<PHINode *, 8> OriginalFC0PHIs; 1630 if (FC0.ExitingBlock != FC0.Latch) 1631 for (PHINode &PHI : FC0.Header->phis()) 1632 OriginalFC0PHIs.push_back(&PHI); 1633 1634 assert(OriginalFC0PHIs.empty() && "Expecting OriginalFC0PHIs to be empty!"); 1635 1636 // Replace incoming blocks for header PHIs first. 1637 FC1.Preheader->replaceSuccessorsPhiUsesWith(FC0.Preheader); 1638 FC0.Latch->replaceSuccessorsPhiUsesWith(FC1.Latch); 1639 1640 // The old exiting block of the first loop (FC0) has to jump to the header 1641 // of the second as we need to execute the code in the second header block 1642 // regardless of the trip count. That is, if the trip count is 0, so the 1643 // back edge is never taken, we still have to execute both loop headers, 1644 // especially (but not only!) if the second is a do-while style loop. 1645 // However, doing so might invalidate the phi nodes of the first loop as 1646 // the new values do only need to dominate their latch and not the exiting 1647 // predicate. To remedy this potential problem we always introduce phi 1648 // nodes in the header of the second loop later that select the loop carried 1649 // value, if the second header was reached through an old latch of the 1650 // first, or undef otherwise. This is sound as exiting the first implies the 1651 // second will exit too, __without__ taking the back-edge (their 1652 // trip-counts are equal after all). 1653 FC0.ExitingBlock->getTerminator()->replaceUsesOfWith(FC0.ExitBlock, 1654 FC1.Header); 1655 1656 TreeUpdates.emplace_back(DominatorTree::UpdateType( 1657 DominatorTree::Delete, FC0.ExitingBlock, FC0.ExitBlock)); 1658 TreeUpdates.emplace_back(DominatorTree::UpdateType( 1659 DominatorTree::Insert, FC0.ExitingBlock, FC1.Header)); 1660 1661 // Remove FC0 Exit Block 1662 // The exit block for FC0 is no longer needed since control will flow 1663 // directly to the header of FC1. Since it is an empty block, it can be 1664 // removed at this point. 1665 // TODO: In the future, we can handle non-empty exit blocks my merging any 1666 // instructions from FC0 exit block into FC1 exit block prior to removing 1667 // the block. 1668 assert(pred_empty(FC0.ExitBlock) && "Expecting exit block to be empty"); 1669 FC0.ExitBlock->getTerminator()->eraseFromParent(); 1670 new UnreachableInst(FC0.ExitBlock->getContext(), FC0.ExitBlock); 1671 1672 // Remove FC1 Preheader 1673 // The pre-header of L1 is not necessary anymore. 1674 assert(pred_empty(FC1.Preheader)); 1675 FC1.Preheader->getTerminator()->eraseFromParent(); 1676 new UnreachableInst(FC1.Preheader->getContext(), FC1.Preheader); 1677 TreeUpdates.emplace_back(DominatorTree::UpdateType( 1678 DominatorTree::Delete, FC1.Preheader, FC1.Header)); 1679 1680 // Moves the phi nodes from the second to the first loops header block. 1681 while (PHINode *PHI = dyn_cast<PHINode>(&FC1.Header->front())) { 1682 if (SE.isSCEVable(PHI->getType())) 1683 SE.forgetValue(PHI); 1684 if (PHI->hasNUsesOrMore(1)) 1685 PHI->moveBefore(&*FC0.Header->getFirstInsertionPt()); 1686 else 1687 PHI->eraseFromParent(); 1688 } 1689 1690 // Introduce new phi nodes in the second loop header to ensure 1691 // exiting the first and jumping to the header of the second does not break 1692 // the SSA property of the phis originally in the first loop. See also the 1693 // comment above. 1694 Instruction *L1HeaderIP = &FC1.Header->front(); 1695 for (PHINode *LCPHI : OriginalFC0PHIs) { 1696 int L1LatchBBIdx = LCPHI->getBasicBlockIndex(FC1.Latch); 1697 assert(L1LatchBBIdx >= 0 && 1698 "Expected loop carried value to be rewired at this point!"); 1699 1700 Value *LCV = LCPHI->getIncomingValue(L1LatchBBIdx); 1701 1702 PHINode *L1HeaderPHI = PHINode::Create( 1703 LCV->getType(), 2, LCPHI->getName() + ".afterFC0", L1HeaderIP); 1704 L1HeaderPHI->addIncoming(LCV, FC0.Latch); 1705 L1HeaderPHI->addIncoming(UndefValue::get(LCV->getType()), 1706 FC0.ExitingBlock); 1707 1708 LCPHI->setIncomingValue(L1LatchBBIdx, L1HeaderPHI); 1709 } 1710 1711 // Update the latches 1712 1713 // Replace latch terminator destinations. 1714 FC0.Latch->getTerminator()->replaceUsesOfWith(FC0.Header, FC1.Header); 1715 FC1.Latch->getTerminator()->replaceUsesOfWith(FC1.Header, FC0.Header); 1716 1717 // Modify the latch branch of FC0 to be unconditional as both successors of 1718 // the branch are the same. 1719 simplifyLatchBranch(FC0); 1720 1721 // If FC0.Latch and FC0.ExitingBlock are the same then we have already 1722 // performed the updates above. 1723 if (FC0.Latch != FC0.ExitingBlock) 1724 TreeUpdates.emplace_back(DominatorTree::UpdateType( 1725 DominatorTree::Insert, FC0.Latch, FC1.Header)); 1726 1727 TreeUpdates.emplace_back(DominatorTree::UpdateType(DominatorTree::Delete, 1728 FC0.Latch, FC0.Header)); 1729 TreeUpdates.emplace_back(DominatorTree::UpdateType(DominatorTree::Insert, 1730 FC1.Latch, FC0.Header)); 1731 TreeUpdates.emplace_back(DominatorTree::UpdateType(DominatorTree::Delete, 1732 FC1.Latch, FC1.Header)); 1733 1734 // All done 1735 // Apply the updates to the Dominator Tree and cleanup. 1736 1737 assert(succ_empty(FC1GuardBlock) && "FC1GuardBlock has successors!!"); 1738 assert(pred_empty(FC1GuardBlock) && "FC1GuardBlock has predecessors!!"); 1739 1740 // Update DT/PDT 1741 DTU.applyUpdates(TreeUpdates); 1742 1743 LI.removeBlock(FC1GuardBlock); 1744 LI.removeBlock(FC1.Preheader); 1745 LI.removeBlock(FC0.ExitBlock); 1746 if (FC0.Peeled) { 1747 LI.removeBlock(FC0ExitBlockSuccessor); 1748 DTU.deleteBB(FC0ExitBlockSuccessor); 1749 } 1750 DTU.deleteBB(FC1GuardBlock); 1751 DTU.deleteBB(FC1.Preheader); 1752 DTU.deleteBB(FC0.ExitBlock); 1753 DTU.flush(); 1754 1755 // Is there a way to keep SE up-to-date so we don't need to forget the loops 1756 // and rebuild the information in subsequent passes of fusion? 1757 // Note: Need to forget the loops before merging the loop latches, as 1758 // mergeLatch may remove the only block in FC1. 1759 SE.forgetLoop(FC1.L); 1760 SE.forgetLoop(FC0.L); 1761 1762 // Move instructions from FC0.Latch to FC1.Latch. 1763 // Note: mergeLatch requires an updated DT. 1764 mergeLatch(FC0, FC1); 1765 1766 // Merge the loops. 1767 SmallVector<BasicBlock *, 8> Blocks(FC1.L->blocks()); 1768 for (BasicBlock *BB : Blocks) { 1769 FC0.L->addBlockEntry(BB); 1770 FC1.L->removeBlockFromLoop(BB); 1771 if (LI.getLoopFor(BB) != FC1.L) 1772 continue; 1773 LI.changeLoopFor(BB, FC0.L); 1774 } 1775 while (!FC1.L->isInnermost()) { 1776 const auto &ChildLoopIt = FC1.L->begin(); 1777 Loop *ChildLoop = *ChildLoopIt; 1778 FC1.L->removeChildLoop(ChildLoopIt); 1779 FC0.L->addChildLoop(ChildLoop); 1780 } 1781 1782 // Delete the now empty loop L1. 1783 LI.erase(FC1.L); 1784 1785 #ifndef NDEBUG 1786 assert(!verifyFunction(*FC0.Header->getParent(), &errs())); 1787 assert(DT.verify(DominatorTree::VerificationLevel::Fast)); 1788 assert(PDT.verify()); 1789 LI.verify(DT); 1790 SE.verify(); 1791 #endif 1792 1793 LLVM_DEBUG(dbgs() << "Fusion done:\n"); 1794 1795 return FC0.L; 1796 } 1797 }; 1798 1799 struct LoopFuseLegacy : public FunctionPass { 1800 1801 static char ID; 1802 1803 LoopFuseLegacy() : FunctionPass(ID) { 1804 initializeLoopFuseLegacyPass(*PassRegistry::getPassRegistry()); 1805 } 1806 1807 void getAnalysisUsage(AnalysisUsage &AU) const override { 1808 AU.addRequiredID(LoopSimplifyID); 1809 AU.addRequired<ScalarEvolutionWrapperPass>(); 1810 AU.addRequired<LoopInfoWrapperPass>(); 1811 AU.addRequired<DominatorTreeWrapperPass>(); 1812 AU.addRequired<PostDominatorTreeWrapperPass>(); 1813 AU.addRequired<OptimizationRemarkEmitterWrapperPass>(); 1814 AU.addRequired<DependenceAnalysisWrapperPass>(); 1815 AU.addRequired<AssumptionCacheTracker>(); 1816 AU.addRequired<TargetTransformInfoWrapperPass>(); 1817 1818 AU.addPreserved<ScalarEvolutionWrapperPass>(); 1819 AU.addPreserved<LoopInfoWrapperPass>(); 1820 AU.addPreserved<DominatorTreeWrapperPass>(); 1821 AU.addPreserved<PostDominatorTreeWrapperPass>(); 1822 } 1823 1824 bool runOnFunction(Function &F) override { 1825 if (skipFunction(F)) 1826 return false; 1827 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); 1828 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 1829 auto &DI = getAnalysis<DependenceAnalysisWrapperPass>().getDI(); 1830 auto &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE(); 1831 auto &PDT = getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree(); 1832 auto &ORE = getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE(); 1833 auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F); 1834 const TargetTransformInfo &TTI = 1835 getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F); 1836 const DataLayout &DL = F.getParent()->getDataLayout(); 1837 1838 LoopFuser LF(LI, DT, DI, SE, PDT, ORE, DL, AC, TTI); 1839 return LF.fuseLoops(F); 1840 } 1841 }; 1842 } // namespace 1843 1844 PreservedAnalyses LoopFusePass::run(Function &F, FunctionAnalysisManager &AM) { 1845 auto &LI = AM.getResult<LoopAnalysis>(F); 1846 auto &DT = AM.getResult<DominatorTreeAnalysis>(F); 1847 auto &DI = AM.getResult<DependenceAnalysis>(F); 1848 auto &SE = AM.getResult<ScalarEvolutionAnalysis>(F); 1849 auto &PDT = AM.getResult<PostDominatorTreeAnalysis>(F); 1850 auto &ORE = AM.getResult<OptimizationRemarkEmitterAnalysis>(F); 1851 auto &AC = AM.getResult<AssumptionAnalysis>(F); 1852 const TargetTransformInfo &TTI = AM.getResult<TargetIRAnalysis>(F); 1853 const DataLayout &DL = F.getParent()->getDataLayout(); 1854 1855 LoopFuser LF(LI, DT, DI, SE, PDT, ORE, DL, AC, TTI); 1856 bool Changed = LF.fuseLoops(F); 1857 if (!Changed) 1858 return PreservedAnalyses::all(); 1859 1860 PreservedAnalyses PA; 1861 PA.preserve<DominatorTreeAnalysis>(); 1862 PA.preserve<PostDominatorTreeAnalysis>(); 1863 PA.preserve<ScalarEvolutionAnalysis>(); 1864 PA.preserve<LoopAnalysis>(); 1865 return PA; 1866 } 1867 1868 char LoopFuseLegacy::ID = 0; 1869 1870 INITIALIZE_PASS_BEGIN(LoopFuseLegacy, "loop-fusion", "Loop Fusion", false, 1871 false) 1872 INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass) 1873 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass) 1874 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 1875 INITIALIZE_PASS_DEPENDENCY(DependenceAnalysisWrapperPass) 1876 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) 1877 INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass) 1878 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) 1879 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) 1880 INITIALIZE_PASS_END(LoopFuseLegacy, "loop-fusion", "Loop Fusion", false, false) 1881 1882 FunctionPass *llvm::createLoopFusePass() { return new LoopFuseLegacy(); } 1883