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