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