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