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