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

source code of llvm/lib/Transforms/Scalar/LoopFuse.cpp