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 "ScalarOptions.h"
49#include "llvm/ADT/Statistic.h"
50#include "llvm/Analysis/AssumptionCache.h"
51#include "llvm/Analysis/DependenceAnalysis.h"
52#include "llvm/Analysis/DomTreeUpdater.h"
53#include "llvm/Analysis/LoopInfo.h"
54#include "llvm/Analysis/LoopNestAnalysis.h"
55#include "llvm/Analysis/OptimizationRemarkEmitter.h"
56#include "llvm/Analysis/PostDominators.h"
57#include "llvm/Analysis/ScalarEvolution.h"
58#include "llvm/Analysis/TargetTransformInfo.h"
59#include "llvm/IR/Function.h"
60#include "llvm/IR/Verifier.h"
61#include "llvm/Support/CommandLine.h"
62#include "llvm/Support/Debug.h"
63#include "llvm/Support/raw_ostream.h"
64#include "llvm/Transforms/Utils/BasicBlockUtils.h"
65#include "llvm/Transforms/Utils/CodeMoverUtils.h"
66#include "llvm/Transforms/Utils/LoopPeel.h"
67#include "llvm/Transforms/Utils/LoopSimplify.h"
68#include "llvm/Transforms/Utils/LoopUtils.h"
69#include <list>
70
71using namespace llvm;
72
73#define DEBUG_TYPE "loop-fusion"
74
75STATISTIC(FuseCounter, "Loops fused");
76STATISTIC(NumFusionCandidates, "Number of candidates for loop fusion");
77STATISTIC(InvalidLoopStructure, "Loop has invalid structure");
78STATISTIC(AddressTakenBB, "Basic block has address taken");
79STATISTIC(MayThrowException, "Loop may throw an exception");
80STATISTIC(ContainsVolatileAccess, "Loop contains a volatile access");
81STATISTIC(ContainsAtomicAccess, "Loop contains an atomic access");
82STATISTIC(NotSimplifiedForm, "Loop is not in simplified form");
83STATISTIC(InvalidDependencies, "Dependencies prevent fusion");
84STATISTIC(UnknownTripCount, "Loop has unknown trip count");
85STATISTIC(UncomputableTripCount, "SCEV cannot compute trip count of loop");
86STATISTIC(NonEqualTripCount, "Loop trip counts are not the same");
87STATISTIC(
88 NonEmptyPreheader,
89 "Loop has a non-empty preheader with instructions that cannot be moved");
90STATISTIC(FusionNotBeneficial, "Fusion is not beneficial");
91STATISTIC(NonIdenticalGuards, "Candidates have different guards");
92STATISTIC(NonEmptyExitBlock, "Candidate has a non-empty exit block with "
93 "instructions that cannot be moved");
94STATISTIC(NonEmptyGuardBlock, "Candidate has a non-empty guard block with "
95 "instructions that cannot be moved");
96STATISTIC(NotRotated, "Candidate is not rotated");
97STATISTIC(OnlySecondCandidateIsGuarded,
98 "The second candidate is guarded while the first one is not");
99STATISTIC(NumHoistedInsts, "Number of hoisted preheader instructions.");
100STATISTIC(NumSunkInsts, "Number of sunk preheader instructions.");
101STATISTIC(NumDA, "DA checks passed");
102
103#ifndef NDEBUG
104static cl::opt<bool>
105 VerboseFusionDebugging("loop-fusion-verbose-debug",
106 cl::desc("Enable verbose debugging for Loop Fusion"),
107 cl::Hidden, cl::init(false));
108#endif
109
110namespace {
111/// This class is used to represent a candidate for loop fusion. When it is
112/// constructed, it checks the conditions for loop fusion to ensure that it
113/// represents a valid candidate. It caches several parts of a loop that are
114/// used throughout loop fusion (e.g., loop preheader, loop header, etc) instead
115/// of continually querying the underlying Loop to retrieve these values. It is
116/// assumed these will not change throughout loop fusion.
117///
118/// The invalidate method should be used to indicate that the FusionCandidate is
119/// no longer a valid candidate for fusion. Similarly, the isValid() method can
120/// be used to ensure that the FusionCandidate is still valid for fusion.
121struct FusionCandidate {
122 /// Cache of parts of the loop used throughout loop fusion. These should not
123 /// need to change throughout the analysis and transformation.
124 /// These parts are cached to avoid repeatedly looking up in the Loop class.
125
126 /// Preheader of the loop this candidate represents
127 BasicBlock *Preheader;
128 /// Header of the loop this candidate represents
129 BasicBlock *Header;
130 /// Blocks in the loop that exit the loop
131 BasicBlock *ExitingBlock;
132 /// The successor block of this loop (where the exiting blocks go to)
133 BasicBlock *ExitBlock;
134 /// Latch of the loop
135 BasicBlock *Latch;
136 /// The loop that this fusion candidate represents
137 Loop *L;
138 /// Vector of instructions in this loop that read from memory
139 SmallVector<Instruction *, 16> MemReads;
140 /// Vector of instructions in this loop that write to memory
141 SmallVector<Instruction *, 16> MemWrites;
142 /// Are all of the members of this fusion candidate still valid
143 bool Valid;
144 /// Guard branch of the loop, if it exists
145 CondBrInst *GuardBranch;
146 /// Peeling Paramaters of the Loop.
147 TTI::PeelingPreferences PP;
148 /// Can you Peel this Loop?
149 bool AbleToPeel;
150 /// Has this loop been Peeled
151 bool Peeled;
152
153 DominatorTree &DT;
154 const PostDominatorTree *PDT;
155
156 OptimizationRemarkEmitter &ORE;
157
158 FusionCandidate(Loop *L, DominatorTree &DT, const PostDominatorTree *PDT,
159 OptimizationRemarkEmitter &ORE, TTI::PeelingPreferences PP)
160 : Preheader(L->getLoopPreheader()), Header(L->getHeader()),
161 ExitingBlock(L->getExitingBlock()), ExitBlock(L->getExitBlock()),
162 Latch(L->getLoopLatch()), L(L), Valid(true),
163 GuardBranch(L->getLoopGuardBranch()), PP(PP), AbleToPeel(canPeel(L)),
164 Peeled(false), DT(DT), PDT(PDT), ORE(ORE) {
165
166 // Walk over all blocks in the loop and check for conditions that may
167 // prevent fusion. For each block, walk over all instructions and collect
168 // the memory reads and writes If any instructions that prevent fusion are
169 // found, invalidate this object and return.
170 for (BasicBlock *BB : L->blocks()) {
171 if (BB->hasAddressTaken()) {
172 invalidate();
173 ++AddressTakenBB;
174 reportInvalidCandidate(RemarkName: "AddressTakenBB",
175 RemarkMsg: "Basic block has address taken");
176 return;
177 }
178
179 for (Instruction &I : *BB) {
180 if (I.mayThrow()) {
181 invalidate();
182 ++MayThrowException;
183 reportInvalidCandidate(RemarkName: "MayThrowException",
184 RemarkMsg: "Loop may throw an exception");
185 return;
186 }
187 if (I.isVolatile()) {
188 invalidate();
189 ++ContainsVolatileAccess;
190 reportInvalidCandidate(RemarkName: "ContainsVolatileAccess",
191 RemarkMsg: "Loop contains a volatile access");
192 return;
193 }
194 // Atomic accesses impose ordering/synchronization constraints that the
195 // dependence analysis used for fusion does not model, so reordering
196 // them across the fused body could be unsafe.
197 if (I.isAtomic()) {
198 invalidate();
199 ++ContainsAtomicAccess;
200 reportInvalidCandidate(RemarkName: "ContainsAtomicAccess",
201 RemarkMsg: "Loop contains an atomic access");
202 return;
203 }
204 if (I.mayWriteToMemory())
205 MemWrites.push_back(Elt: &I);
206 if (I.mayReadFromMemory())
207 MemReads.push_back(Elt: &I);
208 }
209 }
210 }
211
212 /// Check if all members of the class are valid.
213 bool isValid() const {
214 return Preheader && ExitingBlock && ExitBlock && Latch && L &&
215 !L->isInvalid() && Valid;
216 }
217
218 /// Verify that all members are in sync with the Loop object.
219 void verify() const {
220 assert(isValid() && "Candidate is not valid!!");
221 assert(!L->isInvalid() && "Loop is invalid!");
222 assert(Preheader == L->getLoopPreheader() && "Preheader is out of sync");
223 assert(Header == L->getHeader() && "Header is out of sync");
224 assert(ExitingBlock == L->getExitingBlock() &&
225 "Exiting Blocks is out of sync");
226 assert(ExitBlock == L->getExitBlock() && "Exit block is out of sync");
227 assert(Latch == L->getLoopLatch() && "Latch is out of sync");
228 }
229
230 /// Get the entry block for this fusion candidate.
231 ///
232 /// If this fusion candidate represents a guarded loop, the entry block is the
233 /// loop guard block. If it represents an unguarded loop, the entry block is
234 /// the preheader of the loop.
235 BasicBlock *getEntryBlock() const {
236 if (GuardBranch)
237 return GuardBranch->getParent();
238 return Preheader;
239 }
240
241 /// After Peeling the loop is modified quite a bit, hence all of the Blocks
242 /// need to be updated accordingly.
243 void updateAfterPeeling() {
244 Preheader = L->getLoopPreheader();
245 Header = L->getHeader();
246 ExitingBlock = L->getExitingBlock();
247 ExitBlock = L->getExitBlock();
248 Latch = L->getLoopLatch();
249 verify();
250 }
251
252 /// Given a guarded loop, get the successor of the guard that is not in the
253 /// loop.
254 ///
255 /// This method returns the successor of the loop guard that is not located
256 /// within the loop (i.e., the successor of the guard that is not the
257 /// preheader).
258 /// This method is only valid for guarded loops.
259 BasicBlock *getNonLoopBlock() const {
260 assert(GuardBranch && "Only valid on guarded loops.");
261 if (Peeled)
262 return GuardBranch->getSuccessor(i: 1);
263 return (GuardBranch->getSuccessor(i: 0) == Preheader)
264 ? GuardBranch->getSuccessor(i: 1)
265 : GuardBranch->getSuccessor(i: 0);
266 }
267
268#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
269 LLVM_DUMP_METHOD void dump() const {
270 dbgs() << "\tGuardBranch: ";
271 if (GuardBranch)
272 dbgs() << *GuardBranch;
273 else
274 dbgs() << "nullptr";
275 dbgs() << "\n"
276 << (GuardBranch ? GuardBranch->getName() : "nullptr") << "\n"
277 << "\tPreheader: " << (Preheader ? Preheader->getName() : "nullptr")
278 << "\n"
279 << "\tHeader: " << (Header ? Header->getName() : "nullptr") << "\n"
280 << "\tExitingBB: "
281 << (ExitingBlock ? ExitingBlock->getName() : "nullptr") << "\n"
282 << "\tExitBB: " << (ExitBlock ? ExitBlock->getName() : "nullptr")
283 << "\n"
284 << "\tLatch: " << (Latch ? Latch->getName() : "nullptr") << "\n"
285 << "\tEntryBlock: "
286 << (getEntryBlock() ? getEntryBlock()->getName() : "nullptr")
287 << "\n";
288 }
289#endif
290
291 /// Determine if a fusion candidate (representing a loop) is eligible for
292 /// fusion. Note that this only checks whether a single loop can be fused - it
293 /// does not check whether it is *legal* to fuse two loops together.
294 bool isEligibleForFusion(ScalarEvolution &SE) const {
295 if (!isValid()) {
296 LLVM_DEBUG(dbgs() << "FC has invalid CFG requirements!\n");
297 assert(Header && "Header should be guaranteed to exist!");
298 ++InvalidLoopStructure;
299 return false;
300 }
301
302 // Require ScalarEvolution to be able to determine a trip count.
303 if (!SE.hasLoopInvariantBackedgeTakenCount(L)) {
304 LLVM_DEBUG(dbgs() << "Loop " << L->getName()
305 << " trip count not computable!\n");
306 ++UnknownTripCount;
307 return reportInvalidCandidate(RemarkName: "UnknownTripCount",
308 RemarkMsg: "Loop has unknown trip count");
309 }
310
311 if (!L->isLoopSimplifyForm()) {
312 LLVM_DEBUG(dbgs() << "Loop " << L->getName()
313 << " is not in simplified form!\n");
314 ++NotSimplifiedForm;
315 return reportInvalidCandidate(RemarkName: "NotSimplifiedForm",
316 RemarkMsg: "Loop is not in simplified form");
317 }
318
319 if (!L->isRotatedForm()) {
320 LLVM_DEBUG(dbgs() << "Loop " << L->getName() << " is not rotated!\n");
321 ++NotRotated;
322 return reportInvalidCandidate(RemarkName: "NotRotated", RemarkMsg: "Candidate is not rotated");
323 }
324
325 return true;
326 }
327
328private:
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 FusionCandidateList 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 FusionCandidateList to
334 // ensure the FusionCandidateList remains ordered correctly.
335 void invalidate() {
336 MemWrites.clear();
337 MemReads.clear();
338 Valid = false;
339 }
340
341 // Emit an analysis remark explaining why this loop cannot be fused. The
342 // remark is built from explicit strings so it does not depend on whether
343 // statistics are enabled. \p RemarkName is the -Rpass remark identifier and
344 // \p RemarkMsg the human-readable reason.
345 bool reportInvalidCandidate(StringRef RemarkName, StringRef RemarkMsg) const {
346 using namespace ore;
347 ORE.emit(OptDiag: OptimizationRemarkAnalysis(DEBUG_TYPE, "InvalidCandidate",
348 L->getStartLoc(), L->getHeader())
349 << "Loop is not a candidate for fusion");
350
351 ORE.emit(OptDiag: OptimizationRemarkAnalysis(DEBUG_TYPE, RemarkName,
352 L->getStartLoc(), L->getHeader())
353 << "[" << L->getHeader()->getParent()->getName() << "]: "
354 << "Loop is not a candidate for fusion: " << RemarkMsg);
355 return false;
356 }
357};
358} // namespace
359
360using LoopVector = SmallVector<Loop *, 4>;
361
362// List of adjacent fusion candidates in order. Thus, if FC0 comes *before* FC1
363// in a FusionCandidateList, then FC0 dominates FC1, FC1 post-dominates FC0,
364// and they are adjacent.
365using FusionCandidateList = std::list<FusionCandidate>;
366using FusionCandidateCollection = SmallVector<FusionCandidateList, 4>;
367
368#ifndef NDEBUG
369static void printLoopVector(const LoopVector &LV) {
370 dbgs() << "****************************\n";
371 for (const Loop *L : LV)
372 printLoop(*L, dbgs());
373 dbgs() << "****************************\n";
374}
375
376static raw_ostream &operator<<(raw_ostream &OS, const FusionCandidate &FC) {
377 if (FC.isValid())
378 OS << FC.Preheader->getName();
379 else
380 OS << "<Invalid>";
381
382 return OS;
383}
384
385static raw_ostream &operator<<(raw_ostream &OS,
386 const FusionCandidateList &CandList) {
387 for (const FusionCandidate &FC : CandList)
388 OS << FC << '\n';
389
390 return OS;
391}
392
393static void
394printFusionCandidates(const FusionCandidateCollection &FusionCandidates) {
395 dbgs() << "Fusion Candidates: \n";
396 for (const auto &CandidateList : FusionCandidates) {
397 dbgs() << "*** Fusion Candidate List ***\n";
398 dbgs() << CandidateList;
399 dbgs() << "****************************\n";
400 }
401}
402#endif // NDEBUG
403
404/// Fold away an empty block on the "skip" edge of \p L's loop guard, if any.
405///
406/// Loop::getLoopGuardBranch() recognizes a guard only when the non-loop
407/// successor of the guard branch is the block that the loop exit flows into
408/// (looking through empty blocks on the exit side only). Passes such as
409/// JumpThreading can leave an empty forwarding block on the guard side
410/// instead:
411///
412/// Guard: br %c, %Preheader, %Skip
413/// Skip: br %Merge ; empty, only reachable from Guard
414/// ...
415/// Exit: br %Merge
416/// Merge: ...
417///
418/// which makes getLoopGuardBranch() treat \p L as unguarded.
419/// This function folds %Skip: it redirects the guard branch to %Merge and
420/// deletes the empty %Skip block. Loop fusion calls this on every loop before
421/// collecting fusion candidates so that a guarded loop left in this shape by
422/// an earlier pass is still recognized as guarded and as adjacent to its
423/// neighbor. Returns true if the CFG was changed.
424static bool simplifyLoopGuard(Loop *L, DomTreeUpdater &DTU, LoopInfo &LI,
425 ScalarEvolution &SE) {
426 if (!L->isLoopSimplifyForm() || !L->isRotatedForm())
427 return false;
428
429 BasicBlock *Preheader = L->getLoopPreheader();
430 BasicBlock *ExitBlock = L->getUniqueExitBlock();
431 if (!ExitBlock)
432 return false;
433
434 BasicBlock *GuardBB = Preheader->getUniquePredecessor();
435 if (!GuardBB)
436 return false;
437
438 auto *GuardBI = dyn_cast<CondBrInst>(Val: GuardBB->getTerminator());
439 if (!GuardBI)
440 return false;
441
442 BasicBlock *SkipBB = GuardBI->getSuccessor(i: 0) == Preheader
443 ? GuardBI->getSuccessor(i: 1)
444 : GuardBI->getSuccessor(i: 0);
445 if (SkipBB == Preheader)
446 return false;
447
448 // The skip block must contain nothing but an unconditional branch and must
449 // be reachable only from the guard, so that removing it cannot change any
450 // other path.
451 if (SkipBB->size() != 1 || !isa<UncondBrInst>(Val: SkipBB->getTerminator()) ||
452 SkipBB->hasAddressTaken() || SkipBB->getUniquePredecessor() != GuardBB)
453 return false;
454
455 BasicBlock *MergeBB = SkipBB->getUniqueSuccessor();
456 if (!MergeBB || MergeBB == SkipBB || MergeBB == GuardBB ||
457 LI.isLoopHeader(BB: MergeBB))
458 return false;
459
460 // The loop exit must flow into the same block; otherwise the branch is
461 // not a loop guard.
462 if (&LoopNest::skipEmptyBlockUntil(From: ExitBlock, End: MergeBB,
463 /*CheckUniquePred=*/true) != MergeBB)
464 return false;
465
466 LLVM_DEBUG(dbgs() << "Removing empty guard skip block " << SkipBB->getName()
467 << " of loop " << L->getHeader()->getName() << "\n");
468
469 MergeBB->replacePhiUsesWith(Old: SkipBB, New: GuardBB);
470 GuardBI->replaceSuccessorWith(OldBB: SkipBB, NewBB: MergeBB);
471 SkipBB->getTerminator()->eraseFromParent();
472 new UnreachableInst(SkipBB->getContext(), SkipBB);
473
474 DTU.applyUpdates(Updates: {{DominatorTree::Delete, GuardBB, SkipBB},
475 {DominatorTree::Delete, SkipBB, MergeBB},
476 {DominatorTree::Insert, GuardBB, MergeBB}});
477 LI.removeBlock(BB: SkipBB);
478 DTU.deleteBB(DelBB: SkipBB);
479 DTU.flush();
480
481 return true;
482}
483
484namespace {
485
486/// Collect all loops in function at the same nest level, starting at the
487/// outermost level.
488///
489/// This data structure collects all loops at the same nest level for a
490/// given function (specified by the LoopInfo object). It starts at the
491/// outermost level.
492struct LoopDepthTree {
493 using LoopsOnLevelTy = SmallVector<LoopVector, 4>;
494 using iterator = LoopsOnLevelTy::iterator;
495 using const_iterator = LoopsOnLevelTy::const_iterator;
496
497 LoopDepthTree(LoopInfo &LI) : Depth(1) {
498 if (!LI.empty())
499 LoopsOnLevel.emplace_back(Args: LoopVector(LI.rbegin(), LI.rend()));
500 }
501
502 /// Test whether a given loop has been removed from the function, and thus is
503 /// no longer valid.
504 bool isRemovedLoop(const Loop *L) const { return RemovedLoops.count(Ptr: L); }
505
506 /// Record that a given loop has been removed from the function and is no
507 /// longer valid.
508 void removeLoop(const Loop *L) { RemovedLoops.insert(Ptr: L); }
509
510 /// Descend the tree to the next (inner) nesting level
511 void descend() {
512 LoopsOnLevelTy LoopsOnNextLevel;
513
514 for (const LoopVector &LV : *this)
515 for (Loop *L : LV)
516 if (!isRemovedLoop(L) && L->begin() != L->end())
517 LoopsOnNextLevel.emplace_back(Args: LoopVector(L->begin(), L->end()));
518
519 LoopsOnLevel = LoopsOnNextLevel;
520 RemovedLoops.clear();
521 Depth++;
522 }
523
524 bool empty() const { return size() == 0; }
525 size_t size() const { return LoopsOnLevel.size() - RemovedLoops.size(); }
526 unsigned getDepth() const { return Depth; }
527
528 iterator begin() { return LoopsOnLevel.begin(); }
529 iterator end() { return LoopsOnLevel.end(); }
530 const_iterator begin() const { return LoopsOnLevel.begin(); }
531 const_iterator end() const { return LoopsOnLevel.end(); }
532
533private:
534 /// Set of loops that have been removed from the function and are no longer
535 /// valid.
536 SmallPtrSet<const Loop *, 8> RemovedLoops;
537
538 /// Depth of the current level, starting at 1 (outermost loops).
539 unsigned Depth;
540
541 /// Vector of loops at the current depth level that have the same parent loop
542 LoopsOnLevelTy LoopsOnLevel;
543};
544
545struct LoopFuser {
546private:
547 // Sets of control flow equivalent fusion candidates for a given nest level.
548 FusionCandidateCollection FusionCandidates;
549
550 LoopDepthTree LDT;
551 DomTreeUpdater DTU;
552
553 LoopInfo &LI;
554 DominatorTree &DT;
555 DependenceInfo &DI;
556 ScalarEvolution &SE;
557 PostDominatorTree &PDT;
558 OptimizationRemarkEmitter &ORE;
559 AssumptionCache &AC;
560 const TargetTransformInfo &TTI;
561
562public:
563 LoopFuser(LoopInfo &LI, DominatorTree &DT, DependenceInfo &DI,
564 ScalarEvolution &SE, PostDominatorTree &PDT,
565 OptimizationRemarkEmitter &ORE, AssumptionCache &AC,
566 const TargetTransformInfo &TTI)
567 : LDT(LI), DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy), LI(LI),
568 DT(DT), DI(DI), SE(SE), PDT(PDT), ORE(ORE), AC(AC), TTI(TTI) {}
569
570 /// This is the main entry point for loop fusion. It will traverse the
571 /// specified function and collect candidate loops to fuse, starting at the
572 /// outermost nesting level and working inwards.
573 bool fuseLoops(Function &F) {
574#ifndef NDEBUG
575 if (VerboseFusionDebugging) {
576 LI.print(dbgs());
577 }
578#endif
579
580 LLVM_DEBUG(dbgs() << "Performing Loop Fusion on function " << F.getName()
581 << "\n");
582 bool Changed = false;
583
584 while (!LDT.empty()) {
585 LLVM_DEBUG(dbgs() << "Got " << LDT.size() << " loop sets for depth "
586 << LDT.getDepth() << "\n";);
587
588 for (const LoopVector &LV : LDT) {
589 assert(LV.size() > 0 && "Empty loop set was build!");
590
591 // Skip singleton loop sets as they do not offer fusion opportunities on
592 // this level.
593 if (LV.size() == 1)
594 continue;
595#ifndef NDEBUG
596 if (VerboseFusionDebugging) {
597 LLVM_DEBUG({
598 dbgs() << " Visit loop set (#" << LV.size() << "):\n";
599 printLoopVector(LV);
600 });
601 }
602#endif
603
604 collectFusionCandidates(LV);
605 Changed |= fuseCandidates();
606 // All loops in the candidate sets have a common parent (or no parent).
607 // Next loop vector will correspond to a different parent. It is safe
608 // to remove all the candidates currently in the set.
609 FusionCandidates.clear();
610 }
611
612 // Finished analyzing candidates at this level. Descend to the next level.
613 LLVM_DEBUG(dbgs() << "Descend one level!\n");
614 LDT.descend();
615 }
616
617 if (Changed)
618 LLVM_DEBUG(dbgs() << "Function after Loop Fusion: \n"; F.dump(););
619
620#ifndef NDEBUG
621 assert(DT.verify());
622 assert(PDT.verify());
623 LI.verify();
624 SE.verify();
625#endif
626
627 LLVM_DEBUG(dbgs() << "Loop Fusion complete\n");
628 return Changed;
629 }
630
631private:
632 /// Iterate over all loops in the given loop set and identify the loops that
633 /// are eligible for fusion. Place all eligible fusion candidates into Control
634 /// Flow Equivalent sets, sorted by dominance.
635 void collectFusionCandidates(const LoopVector &LV) {
636 for (Loop *L : LV) {
637 TTI::PeelingPreferences PP =
638 gatherPeelingPreferences(L, SE, TTI, UserAllowPeeling: std::nullopt, UserAllowProfileBasedPeeling: std::nullopt);
639 FusionCandidate CurrCand(L, DT, &PDT, ORE, PP);
640 if (!CurrCand.isEligibleForFusion(SE))
641 continue;
642
643 // Go through each list in FusionCandidates and determine if the first or
644 // last loop in the list is strictly adjacent to L. If it is, append L.
645 // If not, go to the next list.
646 // If no suitable list is found, start another list and add it to
647 // FusionCandidates.
648 bool FoundAdjacent = false;
649 for (auto &CurrCandList : FusionCandidates) {
650 if (isStrictlyAdjacent(FC0: CurrCandList.back(), FC1: CurrCand)) {
651 CurrCandList.push_back(x: CurrCand);
652 FoundAdjacent = true;
653 NumFusionCandidates++;
654#ifndef NDEBUG
655 if (VerboseFusionDebugging)
656 LLVM_DEBUG(dbgs() << "Adding " << CurrCand
657 << " to existing candidate list\n");
658#endif
659 break;
660 }
661 }
662 if (!FoundAdjacent) {
663 // No list was found. Create a new list and add to FusionCandidates
664#ifndef NDEBUG
665 if (VerboseFusionDebugging)
666 LLVM_DEBUG(dbgs() << "Adding " << CurrCand << " to new list\n");
667#endif
668 FusionCandidateList NewCandList;
669 NewCandList.push_back(x: CurrCand);
670 FusionCandidates.push_back(Elt: NewCandList);
671 }
672 }
673 }
674
675 /// Determine if it is beneficial to fuse two loops.
676 ///
677 /// For now, this method simply returns true because we want to fuse as much
678 /// as possible (primarily to test the pass). This method will evolve, over
679 /// time, to add heuristics for profitability of fusion.
680 bool isBeneficialFusion(const FusionCandidate &FC0,
681 const FusionCandidate &FC1) {
682 return true;
683 }
684
685 /// Computes the integer difference in trip counts:
686 /// TripCount(FC0) - TripCount(FC1).
687 ///
688 /// \returns The integer difference, or std::nullopt if it
689 /// cannot be determined.
690 std::optional<int64_t>
691 calculateTripCountDiff(const FusionCandidate &FC0,
692 const FusionCandidate &FC1) const {
693 const SCEV *TripCount0 = SE.getBackedgeTakenCount(L: FC0.L);
694 if (isa<SCEVCouldNotCompute>(Val: TripCount0)) {
695 UncomputableTripCount++;
696 LLVM_DEBUG(dbgs() << "Trip count of first loop could not be computed!");
697 return std::nullopt;
698 }
699
700 const SCEV *TripCount1 = SE.getBackedgeTakenCount(L: FC1.L);
701 if (isa<SCEVCouldNotCompute>(Val: TripCount1)) {
702 UncomputableTripCount++;
703 LLVM_DEBUG(dbgs() << "Trip count of second loop could not be computed!");
704 return std::nullopt;
705 }
706
707 LLVM_DEBUG(dbgs() << "\tTrip counts: " << *TripCount0 << " & "
708 << *TripCount1 << " are "
709 << (TripCount0 == TripCount1 ? "identical" : "different")
710 << "\n");
711
712 if (TripCount0 == TripCount1)
713 return 0;
714
715 LLVM_DEBUG(dbgs() << "The loops do not have the same tripcount, "
716 "determining the difference between trip counts\n");
717
718 // Currently only considering loops with a single exit point
719 // and a non-constant trip count. Note that the return value
720 // of getSmallConstantTripCount is a 32 bit number, based on
721 // the existing implementation.
722 const int64_t TC0 =
723 static_cast<int64_t>(SE.getSmallConstantTripCount(L: FC0.L));
724 const int64_t TC1 =
725 static_cast<int64_t>(SE.getSmallConstantTripCount(L: FC1.L));
726
727 // If any of the tripcounts are zero that means that loop(s) do not have
728 // a single exit or a constant tripcount.
729 if (TC0 == 0 || TC1 == 0) {
730 LLVM_DEBUG(dbgs() << "Loop(s) do not have a single exit point or do not "
731 "have a constant number of iterations. Peeling "
732 "is not benefical\n");
733 return std::nullopt;
734 }
735
736 return TC0 - TC1;
737 }
738
739 void peelFusionCandidate(FusionCandidate &FC0, const FusionCandidate &FC1,
740 unsigned PeelCount) {
741 assert(FC0.AbleToPeel && "Should be able to peel loop");
742
743 LLVM_DEBUG(dbgs() << "Attempting to peel first " << PeelCount
744 << " iterations of the first loop. \n");
745
746 ValueToValueMapTy VMap;
747 // LoopFusion is a function pass that neither requires nor preserves
748 // LCSSA, so peelLoop need not preserve it across its internal
749 // simplifyLoop call.
750 peelLoop(L: FC0.L, PeelCount, /*PeelLast=*/false, LI: &LI, SE: &SE, DT, AC: &AC,
751 /*PreserveLCSSA=*/false, VMap);
752 FC0.Peeled = true;
753 LLVM_DEBUG(dbgs() << "Done Peeling\n");
754
755#ifndef NDEBUG
756 auto TCDiff = calculateTripCountDiff(FC0, FC1);
757
758 assert(TCDiff && *TCDiff == 0 &&
759 "Loops should have identical trip counts after peeling");
760#endif
761
762 FC0.PP.PeelCount += PeelCount;
763
764 // Peeling does not update the PDT
765 PDT.recalculate(Func&: *FC0.Preheader->getParent());
766
767 FC0.updateAfterPeeling();
768
769 // In this case the iterations of the loop are constant, so the first
770 // loop will execute completely (will not jump from one of
771 // the peeled blocks to the second loop). Here we are updating the
772 // branch conditions of each of the peeled blocks, such that it will
773 // branch to its successor which is not the preheader of the second loop
774 // in the case of unguarded loops, or the succesors of the exit block of
775 // the first loop otherwise. Doing this update will ensure that the entry
776 // block of the first loop dominates the entry block of the second loop.
777 BasicBlock *BB =
778 FC0.GuardBranch ? FC0.ExitBlock->getUniqueSuccessor() : FC1.Preheader;
779 if (BB) {
780 SmallVector<DominatorTree::UpdateType, 8> TreeUpdates;
781 SmallVector<Instruction *, 8> WorkList;
782 for (BasicBlock *Pred : predecessors(BB)) {
783 if (Pred != FC0.ExitBlock) {
784 WorkList.emplace_back(Args: Pred->getTerminator());
785 TreeUpdates.emplace_back(
786 Args: DominatorTree::UpdateType(DominatorTree::Delete, Pred, BB));
787 }
788 }
789 // Cannot modify the predecessors inside the above loop as it will cause
790 // the iterators to be nullptrs, causing memory errors.
791 for (Instruction *CurrentBranch : WorkList) {
792 BasicBlock *Succ = CurrentBranch->getSuccessor(Idx: 0);
793 if (Succ == BB)
794 Succ = CurrentBranch->getSuccessor(Idx: 1);
795 ReplaceInstWithInst(From: CurrentBranch, To: UncondBrInst::Create(Target: Succ));
796 }
797
798 DTU.applyUpdates(Updates: TreeUpdates);
799 DTU.flush();
800 }
801 LLVM_DEBUG(
802 dbgs() << "Sucessfully peeled " << FC0.PP.PeelCount
803 << " iterations from the first loop.\n"
804 "Both Loops have the same number of iterations now.\n");
805 }
806
807 /// Walk each set of strictly adjacent fusion candidates and attempt to fuse
808 /// them. This does a single linear traversal of all candidates in the list.
809 /// The conditions for legal fusion are checked at this point. If a pair of
810 /// fusion candidates passes all legality checks, they are fused together and
811 /// a new fusion candidate is created and added to the FusionCandidateList.
812 /// The original fusion candidates are then removed, as they are no longer
813 /// valid.
814 bool fuseCandidates() {
815 bool Fused = false;
816 LLVM_DEBUG(printFusionCandidates(FusionCandidates));
817 for (auto &CandidateList : FusionCandidates) {
818 if (CandidateList.size() < 2)
819 continue;
820
821 LLVM_DEBUG(dbgs() << "Attempting fusion on Candidate List:\n"
822 << CandidateList << "\n");
823
824 for (auto It = CandidateList.begin(), NextIt = std::next(x: It);
825 NextIt != CandidateList.end(); It = NextIt, NextIt = std::next(x: It)) {
826
827 const FusionCandidate &FC0 = *It;
828 const FusionCandidate &FC1 = *NextIt;
829
830 assert(!LDT.isRemovedLoop(FC0.L) &&
831 "Should not have removed loops in CandidateList!");
832 assert(!LDT.isRemovedLoop(FC1.L) &&
833 "Should not have removed loops in CandidateList!");
834
835 LLVM_DEBUG(dbgs() << "Attempting to fuse candidate \n"; FC0.dump();
836 dbgs() << " with\n"; FC1.dump(); dbgs() << "\n");
837
838 FC0.verify();
839 FC1.verify();
840
841 std::optional<int64_t> TCDifference = calculateTripCountDiff(FC0, FC1);
842 // Here we are checking that FC0 (the first loop) can be peeled, and
843 // the first loop has a larger trip count. In this case it is possible
844 // that the first loop is peeled to expose the fusion opportunity.
845 // Peeling the second loop is not currently supported.
846 bool WillPeel =
847 FC0.AbleToPeel && TCDifference && *TCDifference > 0 &&
848 *TCDifference <=
849 static_cast<int64_t>(
850 ScalarOptions::Global.loop_fusion_peel_max_count);
851
852 if (!WillPeel && (!TCDifference || *TCDifference != 0)) {
853 LLVM_DEBUG(dbgs() << "Fusion candidates do not have identical trip "
854 "counts and peeling is not supported for this "
855 "case. Not fusing.\n");
856 ++NonEqualTripCount;
857 reportLoopFusion<OptimizationRemarkMissed>(
858 FC0, FC1, RemarkName: "NonEqualTripCount",
859 RemarkMsg: "Loop trip counts are not the same");
860 continue;
861 }
862
863 if ((!FC0.GuardBranch && FC1.GuardBranch) ||
864 (FC0.GuardBranch && !FC1.GuardBranch)) {
865 LLVM_DEBUG(dbgs() << "The one of candidate is guarded while the "
866 "another one is not. Not fusing.\n");
867 ++OnlySecondCandidateIsGuarded;
868 reportLoopFusion<OptimizationRemarkMissed>(
869 FC0, FC1, RemarkName: "OnlySecondCandidateIsGuarded",
870 RemarkMsg: "The second candidate is guarded while the first one is not");
871 continue;
872 }
873
874 // If Loops are guarded, we expect the guards to be identical.
875 // Currently peeling is supported only for loops with constant
876 // iteration counts. If two loops have different loop guards
877 // there is no mechanism in loop fusion to make their fusion legal.
878 // The trivial case where the guards compare two constant values can be
879 // ignored. Those guards will be optimized away by other passes.
880 if (FC0.GuardBranch && FC1.GuardBranch &&
881 !haveIdenticalGuards(FC0, FC1)) {
882 LLVM_DEBUG(dbgs() << "Fusion candidates do not have identical "
883 "guards. Not Fusing.\n");
884 ++NonIdenticalGuards;
885 reportLoopFusion<OptimizationRemarkMissed>(
886 FC0, FC1, RemarkName: "NonIdenticalGuards",
887 RemarkMsg: "Candidates have different guards");
888 continue;
889 }
890
891 if (FC0.GuardBranch) {
892 assert(FC1.GuardBranch && "Expecting valid FC1 guard branch");
893
894 if (!isSafeToMoveBefore(BB&: *FC0.ExitBlock,
895 InsertPoint&: *FC1.ExitBlock->getFirstNonPHIOrDbg(), DT,
896 PDT: &PDT, DI: &DI)) {
897 LLVM_DEBUG(dbgs() << "Fusion candidate contains unsafe "
898 "instructions in exit block. Not fusing.\n");
899 ++NonEmptyExitBlock;
900 reportLoopFusion<OptimizationRemarkMissed>(
901 FC0, FC1, RemarkName: "NonEmptyExitBlock",
902 RemarkMsg: "Candidate has a non-empty exit block with "
903 "instructions that cannot be moved");
904 continue;
905 }
906
907 if (!isSafeToMoveBefore(
908 BB&: *FC1.GuardBranch->getParent(),
909 InsertPoint&: *FC0.GuardBranch->getParent()->getTerminator(), DT, PDT: &PDT,
910 DI: &DI)) {
911 LLVM_DEBUG(dbgs() << "Fusion candidate contains unsafe "
912 "instructions in guard block. Not fusing.\n");
913 ++NonEmptyGuardBlock;
914 reportLoopFusion<OptimizationRemarkMissed>(
915 FC0, FC1, RemarkName: "NonEmptyGuardBlock",
916 RemarkMsg: "Candidate has a non-empty guard block with "
917 "instructions that cannot be moved");
918 continue;
919 }
920 }
921
922 // Check the dependencies across the loops and do not fuse if it would
923 // violate them.
924 if (!dependencesAllowFusion(FC0, FC1)) {
925 LLVM_DEBUG(dbgs() << "Memory dependencies do not allow fusion!\n");
926 ++InvalidDependencies;
927 reportLoopFusion<OptimizationRemarkMissed>(
928 FC0, FC1, RemarkName: "InvalidDependencies", RemarkMsg: "Dependencies prevent fusion");
929 continue;
930 }
931
932 // If the second loop has instructions in the pre-header, attempt to
933 // hoist them up to the first loop's pre-header or sink them into the
934 // body of the second loop.
935 SmallVector<Instruction *, 4> SafeToHoist;
936 SmallVector<Instruction *, 4> SafeToSink;
937 // At this point, this is the last remaining legality check.
938 // Which means if we can make this pre-header empty, we can fuse
939 // these loops
940 if (!isEmptyPreheader(FC: FC1)) {
941 LLVM_DEBUG(dbgs() << "Fusion candidate does not have empty "
942 "preheader.\n");
943
944 // If it is not safe to hoist/sink all instructions in the
945 // pre-header, we cannot fuse these loops.
946 if (!collectMovablePreheaderInsts(FC0, FC1, SafeToHoist,
947 SafeToSink)) {
948 LLVM_DEBUG(dbgs() << "Could not hoist/sink all instructions in "
949 "Fusion Candidate Pre-header.\n"
950 << "Not Fusing.\n");
951 ++NonEmptyPreheader;
952 reportLoopFusion<OptimizationRemarkMissed>(
953 FC0, FC1, RemarkName: "NonEmptyPreheader",
954 RemarkMsg: "Loop has a non-empty preheader with instructions that "
955 "cannot be moved");
956 continue;
957 }
958 }
959
960 bool BeneficialToFuse = isBeneficialFusion(FC0, FC1);
961 LLVM_DEBUG(dbgs() << "\tFusion appears to be "
962 << (BeneficialToFuse ? "" : "un") << "profitable!\n");
963 if (!BeneficialToFuse) {
964 ++FusionNotBeneficial;
965 reportLoopFusion<OptimizationRemarkMissed>(
966 FC0, FC1, RemarkName: "FusionNotBeneficial", RemarkMsg: "Fusion is not beneficial");
967 continue;
968 }
969 // All analysis has completed and has determined that fusion is legal
970 // and profitable. At this point, start transforming the code and
971 // perform fusion.
972
973 // Execute the hoist/sink operations on preheader instructions
974 movePreheaderInsts(FC0, FC1, HoistInsts&: SafeToHoist, SinkInsts&: SafeToSink);
975
976 LLVM_DEBUG(dbgs() << "\tFusion is performed: " << FC0 << " and " << FC1
977 << "\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(FC0&: FC0Copy, FC1, PeelCount: *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 ++FuseCounter;
991 reportLoopFusion<OptimizationRemark>(FC0: (Peel ? FC0Copy : FC0), FC1,
992 RemarkName: "FuseCounter", RemarkMsg: "Loops fused");
993
994 FusionCandidate FusedCand(performFusion(FC0: (Peel ? FC0Copy : FC0), FC1),
995 DT, &PDT, ORE, 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(L: FC1.L);
1002
1003 // Replace FC0 and FC1 with their fused loop
1004 It = CandidateList.erase(position: It);
1005 It = CandidateList.erase(position: It);
1006 It = CandidateList.insert(position: It, x: FusedCand);
1007
1008 // Start from FusedCand in the next iteration
1009 NextIt = It;
1010
1011 LLVM_DEBUG(dbgs() << "Candidate List (after fusion): " << CandidateList
1012 << "\n");
1013
1014 Fused = true;
1015 }
1016 }
1017 return Fused;
1018 }
1019
1020 // Returns true if the instruction \p I can be hoisted to the end of the
1021 // preheader of \p FC0. \p SafeToHoist contains the instructions that are
1022 // known to be safe to hoist. The instructions encountered that cannot be
1023 // hoisted are in \p NotHoisting.
1024 // TODO: Move functionality into CodeMoverUtils
1025 bool canHoistInst(Instruction &I,
1026 const SmallVector<Instruction *, 4> &SafeToHoist,
1027 const SmallVector<Instruction *, 4> &NotHoisting,
1028 const FusionCandidate &FC0) const {
1029 const BasicBlock *FC0PreheaderTarget = FC0.Preheader->getSingleSuccessor();
1030 assert(FC0PreheaderTarget &&
1031 "Expected single successor for loop preheader.");
1032
1033 for (Use &Op : I.operands()) {
1034 if (auto *OpInst = dyn_cast<Instruction>(Val&: Op)) {
1035 bool OpHoisted = is_contained(Range: SafeToHoist, Element: OpInst);
1036 // Check if we have already decided to hoist this operand. In this
1037 // case, it does not dominate FC0 *yet*, but will after we hoist it.
1038 if (!(OpHoisted || DT.dominates(Def: OpInst, BB: FC0PreheaderTarget))) {
1039 return false;
1040 }
1041 }
1042 }
1043
1044 // PHIs in FC1's header only have FC0 blocks as predecessors. PHIs
1045 // cannot be hoisted and should be sunk to the exit of the fused loop.
1046 if (isa<PHINode>(Val: I))
1047 return false;
1048
1049 // If this isn't a memory inst, hoisting is safe
1050 if (!I.mayReadOrWriteMemory())
1051 return true;
1052
1053 LLVM_DEBUG(dbgs() << "Checking if this mem inst can be hoisted.\n");
1054 for (Instruction *NotHoistedInst : NotHoisting) {
1055 if (auto D = DI.depends(Src: &I, Dst: NotHoistedInst)) {
1056 // Dependency is not read-before-write, write-before-read or
1057 // write-before-write
1058 if (D->isFlow() || D->isAnti() || D->isOutput()) {
1059 LLVM_DEBUG(dbgs() << "Inst depends on an instruction in FC1's "
1060 "preheader that is not being hoisted.\n");
1061 return false;
1062 }
1063 }
1064 }
1065
1066 for (Instruction *ReadInst : FC0.MemReads) {
1067 if (auto D = DI.depends(Src: ReadInst, Dst: &I)) {
1068 // Dependency is not read-before-write
1069 if (D->isAnti()) {
1070 LLVM_DEBUG(dbgs() << "Inst depends on a read instruction in FC0.\n");
1071 return false;
1072 }
1073 }
1074 }
1075
1076 for (Instruction *WriteInst : FC0.MemWrites) {
1077 if (auto D = DI.depends(Src: WriteInst, Dst: &I)) {
1078 // Dependency is not write-before-read or write-before-write
1079 if (D->isFlow() || D->isOutput()) {
1080 LLVM_DEBUG(dbgs() << "Inst depends on a write instruction in FC0.\n");
1081 return false;
1082 }
1083 }
1084 }
1085 return true;
1086 }
1087
1088 // Returns true if the instruction \p I can be sunk to the top of the exit
1089 // block of \p FC1.
1090 // TODO: Move functionality into CodeMoverUtils
1091 bool canSinkInst(Instruction &I, const FusionCandidate &FC1) const {
1092 for (User *U : I.users()) {
1093 if (auto *UI{dyn_cast<Instruction>(Val: U)}) {
1094 // Cannot sink if user in loop
1095 // If FC1 has phi users of this value, we cannot sink it into FC1.
1096 if (FC1.L->contains(Inst: UI)) {
1097 // Cannot hoist or sink this instruction. No hoisting/sinking
1098 // should take place, loops should not fuse
1099 return false;
1100 }
1101 }
1102 }
1103
1104 // If this isn't a memory inst, sinking is safe
1105 if (!I.mayReadOrWriteMemory())
1106 return true;
1107
1108 for (Instruction *ReadInst : FC1.MemReads) {
1109 if (auto D = DI.depends(Src: &I, Dst: ReadInst)) {
1110 // Dependency is not write-before-read
1111 if (D->isFlow()) {
1112 LLVM_DEBUG(dbgs() << "Inst depends on a read instruction in FC1.\n");
1113 return false;
1114 }
1115 }
1116 }
1117
1118 for (Instruction *WriteInst : FC1.MemWrites) {
1119 if (auto D = DI.depends(Src: &I, Dst: WriteInst)) {
1120 // Dependency is not write-before-write or read-before-write
1121 if (D->isOutput() || D->isAnti()) {
1122 LLVM_DEBUG(dbgs() << "Inst depends on a write instruction in FC1.\n");
1123 return false;
1124 }
1125 }
1126 }
1127
1128 return true;
1129 }
1130
1131 /// Collect instructions in the \p FC1 Preheader that can be hoisted
1132 /// to the \p FC0 Preheader or sunk into the \p FC1 Body
1133 bool collectMovablePreheaderInsts(
1134 const FusionCandidate &FC0, const FusionCandidate &FC1,
1135 SmallVector<Instruction *, 4> &SafeToHoist,
1136 SmallVector<Instruction *, 4> &SafeToSink) const {
1137 BasicBlock *FC1Preheader = FC1.Preheader;
1138 // Save the instructions that are not being hoisted, so we know not to hoist
1139 // mem insts that they dominate.
1140 SmallVector<Instruction *, 4> NotHoisting;
1141
1142 for (Instruction &I : *FC1Preheader) {
1143 // Can't move a branch
1144 if (&I == FC1Preheader->getTerminator())
1145 continue;
1146 // If the instruction has side-effects, give up.
1147 // TODO: The case of mayReadFromMemory we can handle but requires
1148 // additional work with a dependence analysis so for now we give
1149 // up on memory reads.
1150 if (I.mayThrow() || !I.willReturn()) {
1151 LLVM_DEBUG(dbgs() << "Inst: " << I << " may throw or won't return.\n");
1152 return false;
1153 }
1154
1155 LLVM_DEBUG(dbgs() << "Checking Inst: " << I << "\n");
1156
1157 if (I.isAtomic() || I.isVolatile()) {
1158 LLVM_DEBUG(
1159 dbgs() << "\tInstruction is volatile or atomic. Cannot move it.\n");
1160 return false;
1161 }
1162
1163 if (canHoistInst(I, SafeToHoist, NotHoisting, FC0)) {
1164 SafeToHoist.push_back(Elt: &I);
1165 LLVM_DEBUG(dbgs() << "\tSafe to hoist.\n");
1166 } else {
1167 LLVM_DEBUG(dbgs() << "\tCould not hoist. Trying to sink...\n");
1168 NotHoisting.push_back(Elt: &I);
1169
1170 if (canSinkInst(I, FC1)) {
1171 SafeToSink.push_back(Elt: &I);
1172 LLVM_DEBUG(dbgs() << "\tSafe to sink.\n");
1173 } else {
1174 LLVM_DEBUG(dbgs() << "\tCould not sink.\n");
1175 return false;
1176 }
1177 }
1178 }
1179 LLVM_DEBUG(
1180 dbgs() << "All preheader instructions could be sunk or hoisted!\n");
1181 return true;
1182 }
1183
1184 /// Return true if the dependences between @p I0 (in @p L0) and @p I1 (in
1185 /// @p L1) allow loop fusion of @p L0 and @p L1.
1186 bool dependencesAllowFusion(const FusionCandidate &FC0,
1187 const FusionCandidate &FC1, Instruction &I0,
1188 Instruction &I1) {
1189#ifndef NDEBUG
1190 if (VerboseFusionDebugging) {
1191 LLVM_DEBUG(dbgs() << "Check dep: " << I0 << " vs " << I1 << "\n");
1192 }
1193#endif
1194 auto DepResult = DI.depends(Src: &I0, Dst: &I1);
1195 if (!DepResult)
1196 return true;
1197 // If two stores write the same SSA value, fusion is safe regardless of
1198 // aliasing - writing the same value twice is idempotent.
1199 if (isa<StoreInst>(Val: I0) && isa<StoreInst>(Val: I1)) {
1200 auto *S0 = cast<StoreInst>(Val: &I0);
1201 auto *S1 = cast<StoreInst>(Val: &I1);
1202 if (S0->getValueOperand() == S1->getValueOperand())
1203 return true;
1204 }
1205#ifndef NDEBUG
1206 if (VerboseFusionDebugging) {
1207 LLVM_DEBUG(dbgs() << "DA res: "; DepResult->dump(dbgs());
1208 dbgs() << " [#l: " << DepResult->getLevels() << "][Ordered: "
1209 << (DepResult->isOrdered() ? "true" : "false")
1210 << "]\n");
1211 LLVM_DEBUG(dbgs() << "DepResult Levels: " << DepResult->getLevels()
1212 << "\n");
1213 }
1214#endif
1215 unsigned Levels = DepResult->getLevels();
1216 unsigned SameSDLevels = DepResult->getSameSDLevels();
1217 unsigned CurLoopLevel = FC0.L->getLoopDepth();
1218
1219 // Check if DA is missing info regarding the current loop level
1220 if (CurLoopLevel > Levels + SameSDLevels)
1221 return false;
1222
1223 // Iterating over the outer levels.
1224 for (unsigned Level = 1; Level <= std::min(a: CurLoopLevel - 1, b: Levels);
1225 ++Level) {
1226 unsigned Direction = DepResult->getDirection(Level, SameSD: false);
1227
1228 // Check if the direction vector does not include equality. If an outer
1229 // loop has a non-equal direction, outer indicies are different and it
1230 // is safe to fuse.
1231 if (!(Direction & Dependence::DVEntry::EQ)) {
1232 LLVM_DEBUG(dbgs() << "Safe to fuse due to non-equal acceses in the "
1233 "outer loops\n");
1234 NumDA++;
1235 return true;
1236 }
1237 }
1238
1239 assert(CurLoopLevel > Levels && "Fusion candidates are not separated");
1240
1241 if (DepResult->isScalar(Level: CurLoopLevel, SameSD: true)) {
1242 if (DepResult->isInput() || DepResult->isOutput()) {
1243 LLVM_DEBUG(dbgs() << "Safe to fuse due to a loop-invariant "
1244 << (DepResult->isInput() ? "input" : "output")
1245 << " dependency\n");
1246 NumDA++;
1247 return true;
1248 }
1249 // Same-iteration scalar flow/anti dependences between adjacent loops are
1250 // preserved by placing FC0's body before FC1's body in the fused loop.
1251 // This enables fusing accumulation chains such as:
1252 // for (i)
1253 // A[i] = ...;
1254 // for (i)
1255 // A[i] += ...;
1256 unsigned CurDir = DepResult->getDirection(Level: CurLoopLevel, SameSD: true);
1257 if (!(CurDir & Dependence::DVEntry::GT) &&
1258 !(CurDir & Dependence::DVEntry::LT)) {
1259 LLVM_DEBUG(dbgs() << "Safe to fuse same-iteration scalar dependence\n");
1260 NumDA++;
1261 return true;
1262 }
1263 LLVM_DEBUG(
1264 dbgs() << "Not safe to fuse due to a scalar flow dependency\n");
1265 return false;
1266 }
1267
1268 unsigned CurDir = DepResult->getDirection(Level: CurLoopLevel, SameSD: true);
1269
1270 // Check if the direction vector does not include greater direction. In
1271 // that case, the dependency is not a backward loop-carried and is legal
1272 // to fuse. For example here we have a forward dependency
1273 // for (int i = 0; i < n; i++)
1274 // A[i] = ...;
1275 // for (int i = 0; i < n; i++)
1276 // ... = A[i-1];
1277 if (!(CurDir & Dependence::DVEntry::GT)) {
1278 LLVM_DEBUG(dbgs() << "Safe to fuse with no backward loop-carried "
1279 "dependency\n");
1280 NumDA++;
1281 return true;
1282 }
1283
1284 if (DepResult->getNextPredecessor() || DepResult->getNextSuccessor())
1285 LLVM_DEBUG(dbgs() << "TODO: Implement pred/succ dependence handling!\n");
1286
1287 return false;
1288 }
1289
1290 /// Perform a dependence check and return if @p FC0 and @p FC1 can be fused.
1291 bool dependencesAllowFusion(const FusionCandidate &FC0,
1292 const FusionCandidate &FC1) {
1293 LLVM_DEBUG(dbgs() << "Check if " << FC0 << " can be fused with " << FC1
1294 << "\n");
1295 assert(FC0.L->getLoopDepth() == FC1.L->getLoopDepth());
1296 assert(DT.dominates(FC0.getEntryBlock(), FC1.getEntryBlock()));
1297
1298 // Walk through all uses in FC1. For each use, find the reaching def.
1299 // If the def is located in FC0 then it is not safe to fuse.
1300 for (BasicBlock *BB : FC1.L->blocks())
1301 for (Instruction &I : *BB)
1302 for (auto &Op : I.operands())
1303 if (Instruction *Def = dyn_cast<Instruction>(Val&: Op))
1304 if (FC0.L->contains(BB: Def->getParent())) {
1305 return false;
1306 }
1307
1308 for (Instruction *WriteL0 : FC0.MemWrites) {
1309 for (Instruction *WriteL1 : FC1.MemWrites)
1310 if (!dependencesAllowFusion(FC0, FC1, I0&: *WriteL0, I1&: *WriteL1)) {
1311 return false;
1312 }
1313 for (Instruction *ReadL1 : FC1.MemReads)
1314 if (!dependencesAllowFusion(FC0, FC1, I0&: *WriteL0, I1&: *ReadL1)) {
1315 return false;
1316 }
1317 }
1318
1319 // Write-write and write-read pairs are already covered above; only the
1320 // read-before-write pairs from FC0 reads to FC1 writes remain.
1321 for (Instruction *ReadL0 : FC0.MemReads)
1322 for (Instruction *WriteL1 : FC1.MemWrites)
1323 if (!dependencesAllowFusion(FC0, FC1, I0&: *ReadL0, I1&: *WriteL1)) {
1324 return false;
1325 }
1326
1327 return true;
1328 }
1329
1330 /// Determine if two fusion candidates are strictly adjacent in the CFG.
1331 ///
1332 /// This method will determine if there are additional basic blocks in the CFG
1333 /// between the exit of \p FC0 and the entry of \p FC1.
1334 /// If the two candidates are guarded loops, then it checks whether the
1335 /// exit block of the \p FC0 is the predecessor of the \p FC1 preheader. This
1336 /// implicitly ensures that the non-loop successor of the \p FC0 guard branch
1337 /// is the entry block of \p FC1. If not, then the loops are not adjacent. If
1338 /// the two candidates are not guarded loops, then it checks whether the exit
1339 /// block of \p FC0 is the preheader of \p FC1.
1340 /// Strictly means there is no predecessor for FC1 unless it is from FC0,
1341 /// i.e., FC0 dominates FC1.
1342 bool isStrictlyAdjacent(const FusionCandidate &FC0,
1343 const FusionCandidate &FC1) const {
1344 // If the successor of the guard branch is FC1, then the loops are adjacent
1345 if (FC0.GuardBranch)
1346 return DT.dominates(A: FC0.getEntryBlock(), B: FC1.getEntryBlock()) &&
1347 FC0.ExitBlock->getSingleSuccessor() == FC1.getEntryBlock();
1348 return FC0.ExitBlock == FC1.getEntryBlock();
1349 }
1350
1351 bool isEmptyPreheader(const FusionCandidate &FC) const {
1352 return FC.Preheader->size() == 1;
1353 }
1354
1355 /// Hoist \p FC1 Preheader instructions to \p FC0 Preheader
1356 /// and sink others into the body of \p FC1.
1357 void movePreheaderInsts(const FusionCandidate &FC0,
1358 const FusionCandidate &FC1,
1359 SmallVector<Instruction *, 4> &HoistInsts,
1360 SmallVector<Instruction *, 4> &SinkInsts) const {
1361 // All preheader instructions except the branch must be hoisted or sunk
1362 assert(HoistInsts.size() + SinkInsts.size() == FC1.Preheader->size() - 1 &&
1363 "Attempting to sink and hoist preheader instructions, but not all "
1364 "the preheader instructions are accounted for.");
1365
1366 NumHoistedInsts += HoistInsts.size();
1367 NumSunkInsts += SinkInsts.size();
1368
1369 LLVM_DEBUG(if (VerboseFusionDebugging) {
1370 if (!HoistInsts.empty())
1371 dbgs() << "Hoisting: \n";
1372 for (Instruction *I : HoistInsts)
1373 dbgs() << *I << "\n";
1374 if (!SinkInsts.empty())
1375 dbgs() << "Sinking: \n";
1376 for (Instruction *I : SinkInsts)
1377 dbgs() << *I << "\n";
1378 });
1379
1380 for (Instruction *I : HoistInsts) {
1381 assert(I->getParent() == FC1.Preheader);
1382 I->moveBefore(BB&: *FC0.Preheader,
1383 I: FC0.Preheader->getTerminator()->getIterator());
1384 }
1385 // insert instructions in reverse order to maintain dominance relationship
1386 for (Instruction *I : reverse(C&: SinkInsts)) {
1387 assert(I->getParent() == FC1.Preheader);
1388 if (isa<PHINode>(Val: I)) {
1389 // The Phis to be sunk should have only one incoming value, as is
1390 // assured by the condition that the second loop is dominated by the
1391 // first one which is enforced by isStrictlyAdjacent().
1392 // Replace the phi uses with the corresponding incoming value to clean
1393 // up the code.
1394 assert(cast<PHINode>(I)->getNumIncomingValues() == 1 &&
1395 "Expected the sunk PHI node to have 1 incoming value.");
1396 I->replaceAllUsesWith(V: I->getOperand(i: 0));
1397 I->eraseFromParent();
1398 } else
1399 I->moveBefore(BB&: *FC1.ExitBlock, I: FC1.ExitBlock->getFirstInsertionPt());
1400 }
1401 }
1402
1403 /// Determine if two fusion candidates have identical guards
1404 ///
1405 /// This method will determine if two fusion candidates have the same guards.
1406 /// The guards are considered the same if:
1407 /// 1. The instructions to compute the condition used in the compare are
1408 /// identical.
1409 /// 2. The successors of the guard have the same flow into/around the loop.
1410 /// If the compare instructions are identical, then the first successor of the
1411 /// guard must go to the same place (either the preheader of the loop or the
1412 /// NonLoopBlock). In other words, the first successor of both loops must
1413 /// both go into the loop (i.e., the preheader) or go around the loop (i.e.,
1414 /// the NonLoopBlock). The same must be true for the second successor.
1415 bool haveIdenticalGuards(const FusionCandidate &FC0,
1416 const FusionCandidate &FC1) const {
1417 assert(FC0.GuardBranch && FC1.GuardBranch &&
1418 "Expecting FC0 and FC1 to be guarded loops.");
1419
1420 auto *FC0CmpInst = dyn_cast<Instruction>(Val: FC0.GuardBranch->getCondition());
1421 auto *FC1CmpInst = dyn_cast<Instruction>(Val: FC1.GuardBranch->getCondition());
1422 if ((!FC0CmpInst || !FC1CmpInst) &&
1423 FC0.GuardBranch->getCondition() != FC1.GuardBranch->getCondition())
1424 return false;
1425
1426 if (FC0CmpInst && FC1CmpInst && !FC0CmpInst->isIdenticalTo(I: FC1CmpInst))
1427 return false;
1428
1429 // The compare instructions are identical.
1430 // Now make sure the successor of the guards have the same flow into/around
1431 // the loop
1432 if (FC0.GuardBranch->getSuccessor(i: 0) == FC0.Preheader)
1433 return (FC1.GuardBranch->getSuccessor(i: 0) == FC1.Preheader);
1434 return (FC1.GuardBranch->getSuccessor(i: 1) == FC1.Preheader);
1435 }
1436
1437 /// Modify the latch branch of FC to be unconditional since successors of the
1438 /// branch are the same.
1439 void simplifyLatchBranch(const FusionCandidate &FC) const {
1440 CondBrInst *FCLatchBranch = dyn_cast<CondBrInst>(Val: FC.Latch->getTerminator());
1441 if (FCLatchBranch) {
1442 assert(FCLatchBranch->getSuccessor(0) == FCLatchBranch->getSuccessor(1) &&
1443 "Expecting the two successors of FCLatchBranch to be the same");
1444 UncondBrInst *NewBranch =
1445 UncondBrInst::Create(Target: FCLatchBranch->getSuccessor(i: 0));
1446 ReplaceInstWithInst(From: FCLatchBranch, To: NewBranch);
1447 }
1448 }
1449
1450 /// Move instructions from FC0.Latch to FC1.Latch. If FC0.Latch has an unique
1451 /// successor, then merge FC0.Latch with its unique successor.
1452 void mergeLatch(const FusionCandidate &FC0, const FusionCandidate &FC1) {
1453 moveInstructionsToTheBeginning(FromBB&: *FC0.Latch, ToBB&: *FC1.Latch, DT, PDT, DI, SE);
1454 if (BasicBlock *Succ = FC0.Latch->getUniqueSuccessor()) {
1455 MergeBlockIntoPredecessor(BB: Succ, DTU: &DTU, LI: &LI);
1456 DTU.flush();
1457 }
1458 }
1459
1460 /// Move FC1's header PHIs into FC0's header, insert the loop-carried PHIs
1461 /// needed to keep SSA valid when FC0 exits without taking its back-edge, and
1462 /// rewire both latches to form the fused loop. Latch dominator-tree updates
1463 /// are appended to \p TreeUpdates for the caller to apply.
1464 void rewireFusedHeaderPHIsAndLatches(
1465 const FusionCandidate &FC0, const FusionCandidate &FC1,
1466 const SmallVectorImpl<PHINode *> &OriginalFC0PHIs,
1467 SmallVectorImpl<DominatorTree::UpdateType> &TreeUpdates) {
1468 // Moves the phi nodes from the second to the first loops header block.
1469 while (PHINode *PHI = dyn_cast<PHINode>(Val: &FC1.Header->front())) {
1470 if (SE.isSCEVable(Ty: PHI->getType()))
1471 SE.forgetValue(V: PHI);
1472 if (PHI->hasNUsesOrMore(N: 1))
1473 PHI->moveBefore(InsertPos: FC0.Header->getFirstInsertionPt());
1474 else
1475 PHI->eraseFromParent();
1476 }
1477
1478 // Introduce new phi nodes in the second loop header to ensure
1479 // exiting the first and jumping to the header of the second does not break
1480 // the SSA property of the phis originally in the first loop. See also the
1481 // comment above.
1482 BasicBlock::iterator L1HeaderIP = FC1.Header->begin();
1483 for (PHINode *LCPHI : OriginalFC0PHIs) {
1484 int L1LatchBBIdx = LCPHI->getBasicBlockIndex(BB: FC1.Latch);
1485 assert(L1LatchBBIdx >= 0 &&
1486 "Expected loop carried value to be rewired at this point!");
1487
1488 Value *LCV = LCPHI->getIncomingValue(i: L1LatchBBIdx);
1489
1490 PHINode *L1HeaderPHI =
1491 PHINode::Create(Ty: LCV->getType(), NumReservedValues: 2, NameStr: LCPHI->getName() + ".afterFC0");
1492 L1HeaderPHI->insertBefore(InsertPos: L1HeaderIP);
1493 L1HeaderPHI->addIncoming(V: LCV, BB: FC0.Latch);
1494 L1HeaderPHI->addIncoming(V: PoisonValue::get(T: LCV->getType()),
1495 BB: FC0.ExitingBlock);
1496
1497 LCPHI->setIncomingValue(i: L1LatchBBIdx, V: L1HeaderPHI);
1498 }
1499
1500 // Replace latch terminator destinations.
1501 FC0.Latch->getTerminator()->replaceUsesOfWith(From: FC0.Header, To: FC1.Header);
1502 FC1.Latch->getTerminator()->replaceUsesOfWith(From: FC1.Header, To: FC0.Header);
1503
1504 // Modify the latch branch of FC0 to be unconditional as both successors of
1505 // the branch are the same.
1506 simplifyLatchBranch(FC: FC0);
1507
1508 // If FC0.Latch and FC0.ExitingBlock are the same then we have already
1509 // performed the updates above.
1510 if (FC0.Latch != FC0.ExitingBlock)
1511 TreeUpdates.emplace_back(Args: DominatorTree::UpdateType(
1512 DominatorTree::Insert, FC0.Latch, FC1.Header));
1513
1514 TreeUpdates.emplace_back(Args: DominatorTree::UpdateType(DominatorTree::Delete,
1515 FC0.Latch, FC0.Header));
1516 TreeUpdates.emplace_back(Args: DominatorTree::UpdateType(DominatorTree::Insert,
1517 FC1.Latch, FC0.Header));
1518 TreeUpdates.emplace_back(Args: DominatorTree::UpdateType(DominatorTree::Delete,
1519 FC1.Latch, FC1.Header));
1520 }
1521
1522 /// Forget cached SCEV state for both loops, move all of FC1's blocks and
1523 /// child loops into FC0, erase the now-empty FC1, and merge the latches.
1524 /// Returns the fused loop (FC0.L).
1525 Loop *finalizeFusedLoop(const FusionCandidate &FC0,
1526 const FusionCandidate &FC1) {
1527 // Is there a way to keep SE up-to-date so we don't need to forget the loops
1528 // and rebuild the information in subsequent passes of fusion?
1529 // Note: Need to forget the loops before merging the loop latches, as
1530 // mergeLatch may remove the only block in FC1.
1531 SE.forgetLoop(L: FC1.L);
1532 SE.forgetLoop(L: FC0.L);
1533
1534 // Merge the loops.
1535 SmallVector<BasicBlock *, 8> Blocks(FC1.L->blocks());
1536 for (BasicBlock *BB : Blocks) {
1537 FC0.L->addBlockEntry(BB);
1538 FC1.L->removeBlockFromLoop(BB);
1539 if (LI.getLoopFor(BB) != FC1.L)
1540 continue;
1541 LI.changeLoopFor(BB, L: FC0.L);
1542 }
1543 while (!FC1.L->isInnermost()) {
1544 const auto &ChildLoopIt = FC1.L->begin();
1545 Loop *ChildLoop = *ChildLoopIt;
1546 FC1.L->removeChildLoop(I: ChildLoopIt);
1547 FC0.L->addChildLoop(NewChild: ChildLoop);
1548 }
1549
1550 // Delete the now empty loop L1.
1551 LI.erase(L: FC1.L);
1552
1553 // Forget block dispositions as well, so that there are no dangling
1554 // pointers to erased/free'ed blocks. It should be done after mergeLatch()
1555 // since merging the latches may affect the dispositions.
1556 SE.forgetBlockAndLoopDispositions();
1557
1558 // Move instructions from FC0.Latch to FC1.Latch.
1559 // Note: mergeLatch requires an updated DT.
1560 mergeLatch(FC0, FC1);
1561
1562#ifndef NDEBUG
1563 assert(!verifyFunction(*FC0.Header->getParent(), &errs()));
1564 assert(DT.verify(DominatorTree::VerificationLevel::Fast));
1565 assert(PDT.verify());
1566 LI.verify();
1567 SE.verify();
1568#endif
1569
1570 LLVM_DEBUG(dbgs() << "Fusion done:\n");
1571
1572 return FC0.L;
1573 }
1574
1575 /// Fuse two fusion candidates, creating a new fused loop.
1576 ///
1577 /// This method contains the mechanics of fusing two loops, represented by \p
1578 /// FC0 and \p FC1. It is assumed that \p FC0 dominates \p FC1 and \p FC1
1579 /// postdominates \p FC0 (making them control flow equivalent). It also
1580 /// assumes that the other conditions for fusion have been met: adjacent,
1581 /// identical trip counts, and no negative distance dependencies exist that
1582 /// would prevent fusion. Thus, there is no checking for these conditions in
1583 /// this method.
1584 ///
1585 /// Fusion is performed by rewiring the CFG to update successor blocks of the
1586 /// components of tho loop. Specifically, the following changes are done:
1587 ///
1588 /// 1. The preheader of \p FC1 is removed as it is no longer necessary
1589 /// (because it is currently only a single statement block).
1590 /// 2. The latch of \p FC0 is modified to jump to the header of \p FC1.
1591 /// 3. The latch of \p FC1 i modified to jump to the header of \p FC0.
1592 /// 4. All blocks from \p FC1 are removed from FC1 and added to FC0.
1593 ///
1594 /// All of these modifications are done with dominator tree updates, thus
1595 /// keeping the dominator (and post dominator) information up-to-date.
1596 ///
1597 /// This can be improved in the future by actually merging blocks during
1598 /// fusion. For example, the preheader of \p FC1 can be merged with the
1599 /// preheader of \p FC0. This would allow loops with more than a single
1600 /// statement in the preheader to be fused. Similarly, the latch blocks of the
1601 /// two loops could also be fused into a single block. This will require
1602 /// analysis to prove it is safe to move the contents of the block past
1603 /// existing code, which currently has not been implemented.
1604 Loop *performFusion(const FusionCandidate &FC0, const FusionCandidate &FC1) {
1605 assert(FC0.isValid() && FC1.isValid() &&
1606 "Expecting valid fusion candidates");
1607
1608 LLVM_DEBUG(dbgs() << "Fusion Candidate 0: \n"; FC0.dump();
1609 dbgs() << "Fusion Candidate 1: \n"; FC1.dump(););
1610
1611 // Move instructions from the preheader of FC1 to the end of the preheader
1612 // of FC0.
1613 moveInstructionsToTheEnd(FromBB&: *FC1.Preheader, ToBB&: *FC0.Preheader, DT, PDT, DI, SE);
1614
1615 // Fusing guarded loops is handled slightly differently than non-guarded
1616 // loops and has been broken out into a separate method instead of trying to
1617 // intersperse the logic within a single method.
1618 if (FC0.GuardBranch)
1619 return fuseGuardedLoops(FC0, FC1);
1620
1621 assert(FC1.Preheader ==
1622 (FC0.Peeled ? FC0.ExitBlock->getUniqueSuccessor() : FC0.ExitBlock));
1623 assert(FC1.Preheader->size() == 1 &&
1624 FC1.Preheader->getSingleSuccessor() == FC1.Header);
1625
1626 // Remember the phi nodes originally in the header of FC0 in order to rewire
1627 // them later. However, this is only necessary if the new loop carried
1628 // values might not dominate the exiting branch. While we do not generally
1629 // test if this is the case but simply insert intermediate phi nodes, we
1630 // need to make sure these intermediate phi nodes have different
1631 // predecessors. To this end, we filter the special case where the exiting
1632 // block is the latch block of the first loop. Nothing needs to be done
1633 // anyway as all loop carried values dominate the latch and thereby also the
1634 // exiting branch.
1635 SmallVector<PHINode *, 8> OriginalFC0PHIs;
1636 if (FC0.ExitingBlock != FC0.Latch)
1637 for (PHINode &PHI : FC0.Header->phis())
1638 OriginalFC0PHIs.push_back(Elt: &PHI);
1639
1640 // Replace incoming blocks for header PHIs first.
1641 FC1.Preheader->replaceSuccessorsPhiUsesWith(New: FC0.Preheader);
1642 FC0.Latch->replaceSuccessorsPhiUsesWith(New: FC1.Latch);
1643
1644 // Then modify the control flow and update DT and PDT.
1645 SmallVector<DominatorTree::UpdateType, 8> TreeUpdates;
1646
1647 // The old exiting block of the first loop (FC0) has to jump to the header
1648 // of the second as we need to execute the code in the second header block
1649 // regardless of the trip count. That is, if the trip count is 0, so the
1650 // back edge is never taken, we still have to execute both loop headers,
1651 // especially (but not only!) if the second is a do-while style loop.
1652 // However, doing so might invalidate the phi nodes of the first loop as
1653 // the new values do only need to dominate their latch and not the exiting
1654 // predicate. To remedy this potential problem we always introduce phi
1655 // nodes in the header of the second loop later that select the loop carried
1656 // value, if the second header was reached through an old latch of the
1657 // first, or undef otherwise. This is sound as exiting the first implies the
1658 // second will exit too, __without__ taking the back-edge. [Their
1659 // trip-counts are equal after all.
1660 // KB: Would this sequence be simpler to just make FC0.ExitingBlock go
1661 // to FC1.Header? I think this is basically what the three sequences are
1662 // trying to accomplish; however, doing this directly in the CFG may mean
1663 // the DT/PDT becomes invalid
1664 if (!FC0.Peeled) {
1665 FC0.ExitingBlock->getTerminator()->replaceUsesOfWith(From: FC1.Preheader,
1666 To: FC1.Header);
1667 TreeUpdates.emplace_back(Args: DominatorTree::UpdateType(
1668 DominatorTree::Delete, FC0.ExitingBlock, FC1.Preheader));
1669 TreeUpdates.emplace_back(Args: DominatorTree::UpdateType(
1670 DominatorTree::Insert, FC0.ExitingBlock, FC1.Header));
1671 } else {
1672 TreeUpdates.emplace_back(Args: DominatorTree::UpdateType(
1673 DominatorTree::Delete, FC0.ExitBlock, FC1.Preheader));
1674
1675 // Remove the ExitBlock of the first Loop (also not needed)
1676 FC0.ExitingBlock->getTerminator()->replaceUsesOfWith(From: FC0.ExitBlock,
1677 To: FC1.Header);
1678 TreeUpdates.emplace_back(Args: DominatorTree::UpdateType(
1679 DominatorTree::Delete, FC0.ExitingBlock, FC0.ExitBlock));
1680 FC0.ExitBlock->getTerminator()->eraseFromParent();
1681 TreeUpdates.emplace_back(Args: DominatorTree::UpdateType(
1682 DominatorTree::Insert, FC0.ExitingBlock, FC1.Header));
1683 new UnreachableInst(FC0.ExitBlock->getContext(), FC0.ExitBlock);
1684 }
1685
1686 // The pre-header of L1 is not necessary anymore.
1687 assert(pred_empty(FC1.Preheader));
1688 FC1.Preheader->getTerminator()->eraseFromParent();
1689 new UnreachableInst(FC1.Preheader->getContext(), FC1.Preheader);
1690 TreeUpdates.emplace_back(Args: DominatorTree::UpdateType(
1691 DominatorTree::Delete, FC1.Preheader, FC1.Header));
1692
1693 rewireFusedHeaderPHIsAndLatches(FC0, FC1, OriginalFC0PHIs, TreeUpdates);
1694
1695 // Update DT/PDT
1696 DTU.applyUpdates(Updates: TreeUpdates);
1697
1698 LI.removeBlock(BB: FC1.Preheader);
1699 DTU.deleteBB(DelBB: FC1.Preheader);
1700 if (FC0.Peeled) {
1701 LI.removeBlock(BB: FC0.ExitBlock);
1702 DTU.deleteBB(DelBB: FC0.ExitBlock);
1703 }
1704
1705 DTU.flush();
1706
1707 return finalizeFusedLoop(FC0, FC1);
1708 }
1709
1710 /// Report details on loop fusion opportunities.
1711 ///
1712 /// This template function can be used to report both successful and missed
1713 /// loop fusion opportunities, based on the RemarkKind. The RemarkKind should
1714 /// be one of:
1715 /// - OptimizationRemarkMissed to report when loop fusion is unsuccessful
1716 /// given two valid fusion candidates.
1717 /// - OptimizationRemark to report successful fusion of two fusion
1718 /// candidates.
1719 /// The remarks will be printed using the form:
1720 /// <path/filename>:<line number>:<column number>: [<function name>]:
1721 /// <Cand1 Preheader> and <Cand2 Preheader>: <Stat Description>
1722 template <typename RemarkKind>
1723 void reportLoopFusion(const FusionCandidate &FC0, const FusionCandidate &FC1,
1724 StringRef RemarkName, StringRef RemarkMsg) {
1725 assert(FC0.Preheader && FC1.Preheader &&
1726 "Expecting valid fusion candidates");
1727 using namespace ore;
1728 ORE.emit(
1729 RemarkKind(DEBUG_TYPE, RemarkName, FC0.L->getStartLoc(), FC0.Preheader)
1730 << "[" << FC0.Preheader->getParent()->getName()
1731 << "]: " << NV("Cand1", StringRef(FC0.Preheader->getName())) << " and "
1732 << NV("Cand2", StringRef(FC1.Preheader->getName())) << ": "
1733 << RemarkMsg);
1734 }
1735
1736 /// Fuse two guarded fusion candidates, creating a new fused loop.
1737 ///
1738 /// Fusing guarded loops is handled much the same way as fusing non-guarded
1739 /// loops. The rewiring of the CFG is slightly different though, because of
1740 /// the presence of the guards around the loops and the exit blocks after the
1741 /// loop body. As such, the new loop is rewired as follows:
1742 /// 1. Keep the guard branch from FC0 and use the non-loop block target
1743 /// from the FC1 guard branch.
1744 /// 2. Remove the exit block from FC0 (this exit block should be empty
1745 /// right now).
1746 /// 3. Remove the guard branch for FC1
1747 /// 4. Remove the preheader for FC1.
1748 /// The exit block successor for the latch of FC0 is updated to be the header
1749 /// of FC1 and the non-exit block successor of the latch of FC1 is updated to
1750 /// be the header of FC0, thus creating the fused loop.
1751 Loop *fuseGuardedLoops(const FusionCandidate &FC0,
1752 const FusionCandidate &FC1) {
1753 assert(FC0.GuardBranch && FC1.GuardBranch && "Expecting guarded loops");
1754
1755 BasicBlock *FC0GuardBlock = FC0.GuardBranch->getParent();
1756 BasicBlock *FC1GuardBlock = FC1.GuardBranch->getParent();
1757 BasicBlock *FC0NonLoopBlock = FC0.getNonLoopBlock();
1758 BasicBlock *FC1NonLoopBlock = FC1.getNonLoopBlock();
1759 BasicBlock *FC0ExitBlockSuccessor = FC0.ExitBlock->getUniqueSuccessor();
1760
1761 // Move instructions from the exit block of FC0 to the beginning of the exit
1762 // block of FC1, in the case that the FC0 loop has not been peeled. In the
1763 // case that FC0 loop is peeled, then move the instructions of the successor
1764 // of the FC0 Exit block to the beginning of the exit block of FC1.
1765 moveInstructionsToTheBeginning(
1766 FromBB&: (FC0.Peeled ? *FC0ExitBlockSuccessor : *FC0.ExitBlock), ToBB&: *FC1.ExitBlock,
1767 DT, PDT, DI, SE);
1768
1769 // Move instructions from the guard block of FC1 to the end of the guard
1770 // block of FC0.
1771 moveInstructionsToTheEnd(FromBB&: *FC1GuardBlock, ToBB&: *FC0GuardBlock, DT, PDT, DI, SE);
1772
1773 assert(FC0NonLoopBlock == FC1GuardBlock && "Loops are not adjacent");
1774
1775 SmallVector<DominatorTree::UpdateType, 8> TreeUpdates;
1776
1777 ////////////////////////////////////////////////////////////////////////////
1778 // Update the Loop Guard
1779 ////////////////////////////////////////////////////////////////////////////
1780 // The guard for FC0 is updated to guard both FC0 and FC1. This is done by
1781 // changing the NonLoopGuardBlock for FC0 to the NonLoopGuardBlock for FC1.
1782 // Thus, one path from the guard goes to the preheader for FC0 (and thus
1783 // executes the new fused loop) and the other path goes to the NonLoopBlock
1784 // for FC1 (where FC1 guard would have gone if FC1 was not executed).
1785 FC1NonLoopBlock->replacePhiUsesWith(Old: FC1GuardBlock, New: FC0GuardBlock);
1786 FC0.GuardBranch->replaceUsesOfWith(From: FC0NonLoopBlock, To: FC1NonLoopBlock);
1787
1788 BasicBlock *BBToUpdate = FC0.Peeled ? FC0ExitBlockSuccessor : FC0.ExitBlock;
1789 BBToUpdate->getTerminator()->replaceUsesOfWith(From: FC1GuardBlock, To: FC1.Header);
1790
1791 // The guard of FC1 is not necessary anymore.
1792 FC1.GuardBranch->eraseFromParent();
1793 new UnreachableInst(FC1GuardBlock->getContext(), FC1GuardBlock);
1794
1795 TreeUpdates.emplace_back(Args: DominatorTree::UpdateType(
1796 DominatorTree::Delete, FC1GuardBlock, FC1.Preheader));
1797 TreeUpdates.emplace_back(Args: DominatorTree::UpdateType(
1798 DominatorTree::Delete, FC1GuardBlock, FC1NonLoopBlock));
1799 TreeUpdates.emplace_back(Args: DominatorTree::UpdateType(
1800 DominatorTree::Delete, FC0GuardBlock, FC1GuardBlock));
1801 TreeUpdates.emplace_back(Args: DominatorTree::UpdateType(
1802 DominatorTree::Insert, FC0GuardBlock, FC1NonLoopBlock));
1803
1804 if (FC0.Peeled) {
1805 TreeUpdates.emplace_back(Args: DominatorTree::UpdateType(
1806 DominatorTree::Delete, FC0.ExitBlock, FC0ExitBlockSuccessor));
1807 // Remove the Block after the ExitBlock of FC0
1808 TreeUpdates.emplace_back(Args: DominatorTree::UpdateType(
1809 DominatorTree::Delete, FC0ExitBlockSuccessor, FC1GuardBlock));
1810 FC0ExitBlockSuccessor->getTerminator()->eraseFromParent();
1811 new UnreachableInst(FC0ExitBlockSuccessor->getContext(),
1812 FC0ExitBlockSuccessor);
1813 }
1814
1815 assert(pred_empty(FC1GuardBlock) &&
1816 "Expecting guard block to have no predecessors");
1817 assert(succ_empty(FC1GuardBlock) &&
1818 "Expecting guard block to have no successors");
1819
1820 // Remember the phi nodes originally in the header of FC0 in order to rewire
1821 // them later. However, this is only necessary if the new loop carried
1822 // values might not dominate the exiting branch. While we do not generally
1823 // test if this is the case but simply insert intermediate phi nodes, we
1824 // need to make sure these intermediate phi nodes have different
1825 // predecessors. To this end, we filter the special case where the exiting
1826 // block is the latch block of the first loop. Nothing needs to be done
1827 // anyway as all loop carried values dominate the latch and thereby also the
1828 // exiting branch.
1829 // KB: This is no longer necessary because FC0.ExitingBlock == FC0.Latch
1830 // (because the loops are rotated. Thus, nothing will ever be added to
1831 // OriginalFC0PHIs.
1832 SmallVector<PHINode *, 8> OriginalFC0PHIs;
1833 if (FC0.ExitingBlock != FC0.Latch)
1834 for (PHINode &PHI : FC0.Header->phis())
1835 OriginalFC0PHIs.push_back(Elt: &PHI);
1836
1837 assert(OriginalFC0PHIs.empty() && "Expecting OriginalFC0PHIs to be empty!");
1838
1839 // Replace incoming blocks for header PHIs first.
1840 FC1.Preheader->replaceSuccessorsPhiUsesWith(New: FC0.Preheader);
1841 FC0.Latch->replaceSuccessorsPhiUsesWith(New: FC1.Latch);
1842
1843 // The old exiting block of the first loop (FC0) has to jump to the header
1844 // of the second as we need to execute the code in the second header block
1845 // regardless of the trip count. That is, if the trip count is 0, so the
1846 // back edge is never taken, we still have to execute both loop headers,
1847 // especially (but not only!) if the second is a do-while style loop.
1848 // However, doing so might invalidate the phi nodes of the first loop as
1849 // the new values do only need to dominate their latch and not the exiting
1850 // predicate. To remedy this potential problem we always introduce phi
1851 // nodes in the header of the second loop later that select the loop carried
1852 // value, if the second header was reached through an old latch of the
1853 // first, or undef otherwise. This is sound as exiting the first implies the
1854 // second will exit too, __without__ taking the back-edge (their
1855 // trip-counts are equal after all).
1856 FC0.ExitingBlock->getTerminator()->replaceUsesOfWith(From: FC0.ExitBlock,
1857 To: FC1.Header);
1858
1859 TreeUpdates.emplace_back(Args: DominatorTree::UpdateType(
1860 DominatorTree::Delete, FC0.ExitingBlock, FC0.ExitBlock));
1861 TreeUpdates.emplace_back(Args: DominatorTree::UpdateType(
1862 DominatorTree::Insert, FC0.ExitingBlock, FC1.Header));
1863
1864 // Remove FC0 Exit Block
1865 // The exit block for FC0 is no longer needed since control will flow
1866 // directly to the header of FC1. Since it is an empty block, it can be
1867 // removed at this point.
1868 // TODO: In the future, we can handle non-empty exit blocks my merging any
1869 // instructions from FC0 exit block into FC1 exit block prior to removing
1870 // the block.
1871 assert(pred_empty(FC0.ExitBlock) && "Expecting exit block to be empty");
1872 FC0.ExitBlock->getTerminator()->eraseFromParent();
1873 new UnreachableInst(FC0.ExitBlock->getContext(), FC0.ExitBlock);
1874
1875 // Remove FC1 Preheader
1876 // The pre-header of L1 is not necessary anymore.
1877 assert(pred_empty(FC1.Preheader));
1878 FC1.Preheader->getTerminator()->eraseFromParent();
1879 new UnreachableInst(FC1.Preheader->getContext(), FC1.Preheader);
1880 TreeUpdates.emplace_back(Args: DominatorTree::UpdateType(
1881 DominatorTree::Delete, FC1.Preheader, FC1.Header));
1882
1883 rewireFusedHeaderPHIsAndLatches(FC0, FC1, OriginalFC0PHIs, TreeUpdates);
1884
1885 // All done
1886 // Apply the updates to the Dominator Tree and cleanup.
1887
1888 assert(succ_empty(FC1GuardBlock) && "FC1GuardBlock has successors!!");
1889 assert(pred_empty(FC1GuardBlock) && "FC1GuardBlock has predecessors!!");
1890
1891 // Update DT/PDT
1892 DTU.applyUpdates(Updates: TreeUpdates);
1893
1894 LI.removeBlock(BB: FC1GuardBlock);
1895 LI.removeBlock(BB: FC1.Preheader);
1896 LI.removeBlock(BB: FC0.ExitBlock);
1897 if (FC0.Peeled) {
1898 LI.removeBlock(BB: FC0ExitBlockSuccessor);
1899 DTU.deleteBB(DelBB: FC0ExitBlockSuccessor);
1900 }
1901 DTU.deleteBB(DelBB: FC1GuardBlock);
1902 DTU.deleteBB(DelBB: FC1.Preheader);
1903 DTU.deleteBB(DelBB: FC0.ExitBlock);
1904 DTU.flush();
1905
1906 return finalizeFusedLoop(FC0, FC1);
1907 }
1908};
1909} // namespace
1910
1911PreservedAnalyses LoopFusePass::run(Function &F, FunctionAnalysisManager &AM) {
1912 auto &LI = AM.getResult<LoopAnalysis>(IR&: F);
1913 auto &DT = AM.getResult<DominatorTreeAnalysis>(IR&: F);
1914 auto &DI = AM.getResult<DependenceAnalysis>(IR&: F);
1915 auto &SE = AM.getResult<ScalarEvolutionAnalysis>(IR&: F);
1916 auto &PDT = AM.getResult<PostDominatorTreeAnalysis>(IR&: F);
1917 auto &ORE = AM.getResult<OptimizationRemarkEmitterAnalysis>(IR&: F);
1918 auto &AC = AM.getResult<AssumptionAnalysis>(IR&: F);
1919 const TargetTransformInfo &TTI = AM.getResult<TargetIRAnalysis>(IR&: F);
1920
1921 // Ensure loops are in simplifed form which is a pre-requisite for loop fusion
1922 // pass. Added only for new PM since the legacy PM has already added
1923 // LoopSimplify pass as a dependency.
1924 bool Changed = false;
1925 DomTreeUpdater DTU(&DT, DomTreeUpdater::UpdateStrategy::Lazy);
1926 for (auto &L : LI) {
1927 Changed |=
1928 simplifyLoop(L, DT: &DT, LI: &LI, SE: &SE, AC: &AC, MSSAU: nullptr, PreserveLCSSA: false /* PreserveLCSSA */);
1929 }
1930 for (Loop *L : LI.getLoopsInPreorder()) {
1931 Changed |= simplifyLoopGuard(L, DTU, LI, SE);
1932 }
1933
1934 if (Changed)
1935 PDT.recalculate(Func&: F);
1936
1937 LoopFuser LF(LI, DT, DI, SE, PDT, ORE, AC, TTI);
1938 Changed |= LF.fuseLoops(F);
1939 if (!Changed)
1940 return PreservedAnalyses::all();
1941
1942 PreservedAnalyses PA;
1943 PA.preserve<DominatorTreeAnalysis>();
1944 PA.preserve<PostDominatorTreeAnalysis>();
1945 PA.preserve<ScalarEvolutionAnalysis>();
1946 PA.preserve<LoopAnalysis>();
1947 return PA;
1948}
1949