1//===- LoopInterchange.cpp - Loop interchange 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// This Pass handles loop interchange transform.
10// This pass interchanges loops to provide a more cache-friendly memory access
11// patterns.
12//
13//===----------------------------------------------------------------------===//
14
15#include "llvm/Transforms/Scalar/LoopInterchange.h"
16#include "llvm/ADT/STLExtras.h"
17#include "llvm/ADT/SmallSet.h"
18#include "llvm/ADT/SmallVector.h"
19#include "llvm/ADT/Statistic.h"
20#include "llvm/ADT/StringMap.h"
21#include "llvm/ADT/StringRef.h"
22#include "llvm/Analysis/DependenceAnalysis.h"
23#include "llvm/Analysis/LoopCacheAnalysis.h"
24#include "llvm/Analysis/LoopInfo.h"
25#include "llvm/Analysis/LoopNestAnalysis.h"
26#include "llvm/Analysis/LoopPass.h"
27#include "llvm/Analysis/OptimizationRemarkEmitter.h"
28#include "llvm/Analysis/ScalarEvolution.h"
29#include "llvm/Analysis/ScalarEvolutionExpressions.h"
30#include "llvm/IR/BasicBlock.h"
31#include "llvm/IR/DiagnosticInfo.h"
32#include "llvm/IR/Dominators.h"
33#include "llvm/IR/Function.h"
34#include "llvm/IR/IRBuilder.h"
35#include "llvm/IR/InstrTypes.h"
36#include "llvm/IR/Instruction.h"
37#include "llvm/IR/Instructions.h"
38#include "llvm/IR/User.h"
39#include "llvm/IR/Value.h"
40#include "llvm/Support/Casting.h"
41#include "llvm/Support/CommandLine.h"
42#include "llvm/Support/Debug.h"
43#include "llvm/Support/ErrorHandling.h"
44#include "llvm/Support/raw_ostream.h"
45#include "llvm/Transforms/Scalar/LoopPassManager.h"
46#include "llvm/Transforms/Utils/BasicBlockUtils.h"
47#include "llvm/Transforms/Utils/Local.h"
48#include "llvm/Transforms/Utils/LoopUtils.h"
49#include <cassert>
50#include <utility>
51#include <vector>
52
53using namespace llvm;
54
55#define DEBUG_TYPE "loop-interchange"
56
57STATISTIC(LoopsInterchanged, "Number of loops interchanged");
58
59static cl::opt<int> LoopInterchangeCostThreshold(
60 "loop-interchange-threshold", cl::init(Val: 0), cl::Hidden,
61 cl::desc("Interchange if you gain more than this number"));
62
63static cl::opt<unsigned int> MaxMemInstrRatio(
64 "loop-interchange-max-mem-instr-ratio", cl::init(Val: 4), cl::Hidden,
65 cl::desc("Maximum number of load/store instructions squared in relation to "
66 "the total number of instructions. Higher value may lead to more "
67 "interchanges at the cost of compile-time"));
68
69namespace {
70
71using LoopVector = SmallVector<Loop *, 8>;
72
73/// A list of direction vectors. Each entry represents a direction vector
74/// corresponding to one or more dependencies existing in the loop nest. The
75/// length of all direction vectors is equal and is N + 1, where N is the depth
76/// of the loop nest. The first N elements correspond to the dependency
77/// direction of each N loops. The last one indicates whether this entry is
78/// forward dependency ('<') or not ('*'). The term "forward" aligns with what
79/// is defined in LoopAccessAnalysis.
80// TODO: Check if we can use a sparse matrix here.
81using CharMatrix = std::vector<std::vector<char>>;
82
83/// Types of rules used in profitability check.
84enum class RuleTy {
85 PerLoopCacheAnalysis,
86 PerInstrOrderCost,
87 ForVectorization,
88 Ignore
89};
90
91} // end anonymous namespace
92
93// Minimum loop depth supported.
94static cl::opt<unsigned int> MinLoopNestDepth(
95 "loop-interchange-min-loop-nest-depth", cl::init(Val: 2), cl::Hidden,
96 cl::desc("Minimum depth of loop nest considered for the transform"));
97
98// Maximum loop depth supported.
99static cl::opt<unsigned int> MaxLoopNestDepth(
100 "loop-interchange-max-loop-nest-depth", cl::init(Val: 10), cl::Hidden,
101 cl::desc("Maximum depth of loop nest considered for the transform"));
102
103// We prefer cache cost to vectorization by default.
104static cl::list<RuleTy> Profitabilities(
105 "loop-interchange-profitabilities", cl::MiscFlags::CommaSeparated,
106 cl::Hidden,
107 cl::desc("List of profitability heuristics to be used. They are applied in "
108 "the given order"),
109 cl::list_init<RuleTy>(Vals: {RuleTy::PerInstrOrderCost,
110 RuleTy::ForVectorization}),
111 cl::values(clEnumValN(RuleTy::PerLoopCacheAnalysis, "cache",
112 "Prioritize loop cache cost"),
113 clEnumValN(RuleTy::PerInstrOrderCost, "instorder",
114 "Prioritize the IVs order of each instruction"),
115 clEnumValN(RuleTy::ForVectorization, "vectorize",
116 "Prioritize vectorization"),
117 clEnumValN(RuleTy::Ignore, "ignore",
118 "Ignore profitability, force interchange (does not "
119 "work with other options)")));
120
121// Support for the inner-loop reduction pattern.
122static cl::opt<bool> EnableReduction2Memory(
123 "loop-interchange-reduction-to-mem", cl::init(Val: false), cl::Hidden,
124 cl::desc("Support for the inner-loop reduction pattern."));
125
126#ifndef NDEBUG
127static bool noDuplicateRulesAndIgnore(ArrayRef<RuleTy> Rules) {
128 SmallSet<RuleTy, 4> Set;
129 for (RuleTy Rule : Rules) {
130 if (!Set.insert(Rule).second)
131 return false;
132 if (Rule == RuleTy::Ignore)
133 return false;
134 }
135 return true;
136}
137
138static void printDepMatrix(CharMatrix &DepMatrix) {
139 for (auto &Row : DepMatrix) {
140 // Drop the last element because it is a flag indicating whether this is
141 // forward dependency or not, which doesn't affect the legality check.
142 for (char D : drop_end(Row))
143 LLVM_DEBUG(dbgs() << D << " ");
144 LLVM_DEBUG(dbgs() << "\n");
145 }
146}
147
148/// Return true if \p Src appears before \p Dst in the same basic block.
149/// Precondition: \p Src and \Dst are distinct instructions within the same
150/// basic block.
151static bool inThisOrder(const Instruction *Src, const Instruction *Dst) {
152 assert(Src->getParent() == Dst->getParent() && Src != Dst &&
153 "Expected Src and Dst to be different instructions in the same BB");
154
155 bool FoundSrc = false;
156 for (const Instruction &I : *(Src->getParent())) {
157 if (&I == Src) {
158 FoundSrc = true;
159 continue;
160 }
161 if (&I == Dst)
162 return FoundSrc;
163 }
164
165 llvm_unreachable("Dst not found");
166}
167#endif
168
169static bool populateDependencyMatrix(CharMatrix &DepMatrix, unsigned Level,
170 Loop *L, DependenceInfo *DI,
171 ScalarEvolution *SE,
172 OptimizationRemarkEmitter *ORE) {
173 using ValueVector = SmallVector<Value *, 16>;
174
175 ValueVector MemInstr;
176 unsigned NumInsts = 0;
177
178 // For each block.
179 for (BasicBlock *BB : L->blocks()) {
180 // Scan the BB and collect legal loads and stores.
181 for (Instruction &I : *BB) {
182 NumInsts++;
183 if (auto *Ld = dyn_cast<LoadInst>(Val: &I)) {
184 if (!Ld->isSimple())
185 return false;
186 MemInstr.push_back(Elt: &I);
187 } else if (auto *St = dyn_cast<StoreInst>(Val: &I)) {
188 if (!St->isSimple())
189 return false;
190 MemInstr.push_back(Elt: &I);
191 }
192 }
193 }
194
195 // To populate the dependence matrix, we perform dependence test for each pair
196 // of memory instructions, which has O(NumMemInstr^2) complexity. This implies
197 // that even if the number of memory instructions is small, the analysis can
198 // still be expensive if the most of the instructions in the loop are memory
199 // instructions. On the other hand, if the number of memory instructions is
200 // not small, but the loop is large (i.e., it contains many non-memory
201 // instructions), the analysis can still be affordable.
202 unsigned NumMemInstr = MemInstr.size();
203 LLVM_DEBUG(dbgs() << "Found " << NumMemInstr
204 << " Loads and Stores to analyze\n");
205 if (MaxMemInstrRatio * NumInsts < NumMemInstr * NumMemInstr) {
206 ORE->emit(RemarkBuilder: [&]() {
207 return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedLoop",
208 L->getStartLoc(), L->getHeader())
209 << "Number of loads/stores exceeded, the supported maximum can be "
210 "increased with option -loop-interchange-max-mem-instr-ratio.";
211 });
212 return false;
213 }
214 ValueVector::iterator I, IE, J, JE;
215
216 // Manage direction vectors that are already seen. Map each direction vector
217 // to an index of DepMatrix at which it is stored.
218 StringMap<unsigned> Seen;
219
220 for (I = MemInstr.begin(), IE = MemInstr.end(); I != IE; ++I) {
221 for (J = I, JE = MemInstr.end(); J != JE; ++J) {
222 std::vector<char> Dep;
223 Instruction *Src = cast<Instruction>(Val: *I);
224 Instruction *Dst = cast<Instruction>(Val: *J);
225 // Ignore Input dependencies.
226 if (isa<LoadInst>(Val: Src) && isa<LoadInst>(Val: Dst))
227 continue;
228 // Track Output, Flow, and Anti dependencies.
229 if (auto D = DI->depends(Src, Dst)) {
230 assert(D->isOrdered() && "Expected an output, flow or anti dep.");
231 // If the direction vector is negative, normalize it to
232 // make it non-negative.
233 if (D->normalize(SE))
234 LLVM_DEBUG(dbgs() << "Negative dependence vector normalized.\n");
235 LLVM_DEBUG(StringRef DepType =
236 D->isFlow() ? "flow" : D->isAnti() ? "anti" : "output";
237 dbgs() << "Found " << DepType
238 << " dependency between Src and Dst\n"
239 << " Src:" << *Src << "\n Dst:" << *Dst << '\n');
240 unsigned Levels = D->getLevels();
241 char Direction;
242 for (unsigned II = 1; II <= Levels; ++II) {
243 // `DVEntry::LE` is converted to `*`. This is because `LE` means `<`
244 // or `=`, for which we don't have an equivalent representation, so
245 // that the conservative approximation is necessary. The same goes for
246 // `DVEntry::GE`.
247 // TODO: Use of fine-grained expressions allows for more accurate
248 // analysis.
249 unsigned Dir = D->getDirection(Level: II);
250 if (Dir == Dependence::DVEntry::LT)
251 Direction = '<';
252 else if (Dir == Dependence::DVEntry::GT)
253 Direction = '>';
254 else if (Dir == Dependence::DVEntry::EQ)
255 Direction = '=';
256 else
257 Direction = '*';
258 Dep.push_back(x: Direction);
259 }
260
261 // If the Dependence object doesn't have any information, fill the
262 // dependency vector with '*'.
263 if (D->isConfused()) {
264 assert(Dep.empty() && "Expected empty dependency vector");
265 Dep.assign(n: Level, val: '*');
266 }
267
268 while (Dep.size() != Level) {
269 Dep.push_back(x: 'I');
270 }
271
272 // If all the elements of any direction vector have only '*', legality
273 // can't be proven. Exit early to save compile time.
274 if (all_of(Range&: Dep, P: equal_to(Arg: '*'))) {
275 ORE->emit(RemarkBuilder: [&]() {
276 return OptimizationRemarkMissed(DEBUG_TYPE, "Dependence",
277 L->getStartLoc(), L->getHeader())
278 << "All loops have dependencies in all directions.";
279 });
280 return false;
281 }
282
283 // Test whether the dependency is forward or not.
284 bool IsKnownForward = true;
285 if (Src->getParent() != Dst->getParent()) {
286 // In general, when Src and Dst are in different BBs, the execution
287 // order of them within a single iteration is not guaranteed. Treat
288 // conservatively as not-forward dependency in this case.
289 IsKnownForward = false;
290 } else {
291 // Src and Dst are in the same BB. If they are the different
292 // instructions, Src should appear before Dst in the BB as they are
293 // stored to MemInstr in that order.
294 assert((Src == Dst || inThisOrder(Src, Dst)) &&
295 "Unexpected instructions");
296
297 // If the Dependence object is reversed (due to normalization), it
298 // represents the dependency from Dst to Src, meaning it is a backward
299 // dependency. Otherwise it should be a forward dependency.
300 bool IsReversed = D->getSrc() != Src;
301 if (IsReversed)
302 IsKnownForward = false;
303 }
304
305 // Initialize the last element. Assume forward dependencies only; it
306 // will be updated later if there is any non-forward dependency.
307 Dep.push_back(x: '<');
308
309 // The last element should express the "summary" among one or more
310 // direction vectors whose first N elements are the same (where N is
311 // the depth of the loop nest). Hence we exclude the last element from
312 // the Seen map.
313 auto [Ite, Inserted] = Seen.try_emplace(
314 Key: StringRef(Dep.data(), Dep.size() - 1), Args: DepMatrix.size());
315
316 // Make sure we only add unique entries to the dependency matrix.
317 if (Inserted)
318 DepMatrix.push_back(x: Dep);
319
320 // If we cannot prove that this dependency is forward, change the last
321 // element of the corresponding entry. Since a `[... *]` dependency
322 // includes a `[... <]` dependency, we do not need to keep both and
323 // change the existing entry instead.
324 if (!IsKnownForward)
325 DepMatrix[Ite->second].back() = '*';
326 }
327 }
328 }
329
330 return true;
331}
332
333// A loop is moved from index 'from' to an index 'to'. Update the Dependence
334// matrix by exchanging the two columns.
335static void interChangeDependencies(CharMatrix &DepMatrix, unsigned FromIndx,
336 unsigned ToIndx) {
337 for (auto &Row : DepMatrix)
338 std::swap(a&: Row[ToIndx], b&: Row[FromIndx]);
339}
340
341// Check if a direction vector is lexicographically positive. Return true if it
342// is positive, nullopt if it is "zero", otherwise false.
343// [Theorem] A permutation of the loops in a perfect nest is legal if and only
344// if the direction matrix, after the same permutation is applied to its
345// columns, has no ">" direction as the leftmost non-"=" direction in any row.
346static std::optional<bool>
347isLexicographicallyPositive(ArrayRef<char> DV, unsigned Begin, unsigned End) {
348 for (unsigned char Direction : DV.slice(N: Begin, M: End - Begin)) {
349 if (Direction == '<')
350 return true;
351 if (Direction == '>' || Direction == '*')
352 return false;
353 }
354 return std::nullopt;
355}
356
357// Checks if it is legal to interchange 2 loops.
358static bool isLegalToInterChangeLoops(CharMatrix &DepMatrix,
359 unsigned InnerLoopId,
360 unsigned OuterLoopId) {
361 unsigned NumRows = DepMatrix.size();
362 std::vector<char> Cur;
363 // For each row check if it is valid to interchange.
364 for (unsigned Row = 0; Row < NumRows; ++Row) {
365 // Create temporary DepVector check its lexicographical order
366 // before and after swapping OuterLoop vs InnerLoop
367 Cur = DepMatrix[Row];
368
369 // If the surrounding loops already ensure that the direction vector is
370 // lexicographically positive, nothing within the loop will be able to break
371 // the dependence. In such a case we can skip the subsequent check.
372 if (isLexicographicallyPositive(DV: Cur, Begin: 0, End: OuterLoopId) == true)
373 continue;
374
375 // Check if the direction vector is lexicographically positive (or zero)
376 // for both before/after exchanged. Ignore the last element because it
377 // doesn't affect the legality.
378 if (isLexicographicallyPositive(DV: Cur, Begin: OuterLoopId, End: Cur.size() - 1) == false)
379 return false;
380 std::swap(a&: Cur[InnerLoopId], b&: Cur[OuterLoopId]);
381 if (isLexicographicallyPositive(DV: Cur, Begin: OuterLoopId, End: Cur.size() - 1) == false)
382 return false;
383 }
384 return true;
385}
386
387static void populateWorklist(Loop &L, LoopVector &LoopList) {
388 LLVM_DEBUG(dbgs() << "Calling populateWorklist on Func: "
389 << L.getHeader()->getParent()->getName() << " Loop: %"
390 << L.getHeader()->getName() << '\n');
391 assert(LoopList.empty() && "LoopList should initially be empty!");
392 Loop *CurrentLoop = &L;
393 const std::vector<Loop *> *Vec = &CurrentLoop->getSubLoops();
394 while (!Vec->empty()) {
395 // The current loop has multiple subloops in it hence it is not tightly
396 // nested.
397 // Discard all loops above it added into Worklist.
398 if (Vec->size() != 1) {
399 LoopList = {};
400 return;
401 }
402
403 LoopList.push_back(Elt: CurrentLoop);
404 CurrentLoop = Vec->front();
405 Vec = &CurrentLoop->getSubLoops();
406 }
407 LoopList.push_back(Elt: CurrentLoop);
408}
409
410static bool hasSupportedLoopDepth(ArrayRef<Loop *> LoopList,
411 OptimizationRemarkEmitter &ORE) {
412 unsigned LoopNestDepth = LoopList.size();
413 if (LoopNestDepth < MinLoopNestDepth || LoopNestDepth > MaxLoopNestDepth) {
414 LLVM_DEBUG(dbgs() << "Unsupported depth of loop nest " << LoopNestDepth
415 << ", the supported range is [" << MinLoopNestDepth
416 << ", " << MaxLoopNestDepth << "].\n");
417 Loop *OuterLoop = LoopList.front();
418 ORE.emit(RemarkBuilder: [&]() {
419 return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedLoopNestDepth",
420 OuterLoop->getStartLoc(),
421 OuterLoop->getHeader())
422 << "Unsupported depth of loop nest, the supported range is ["
423 << std::to_string(val: MinLoopNestDepth) << ", "
424 << std::to_string(val: MaxLoopNestDepth) << "].\n";
425 });
426 return false;
427 }
428 return true;
429}
430
431static bool isComputableLoopNest(ScalarEvolution *SE,
432 ArrayRef<Loop *> LoopList) {
433 for (Loop *L : LoopList) {
434 const SCEV *ExitCountOuter = SE->getBackedgeTakenCount(L);
435 if (isa<SCEVCouldNotCompute>(Val: ExitCountOuter)) {
436 LLVM_DEBUG(dbgs() << "Couldn't compute backedge count\n");
437 return false;
438 }
439 if (L->getNumBackEdges() != 1) {
440 LLVM_DEBUG(dbgs() << "NumBackEdges is not equal to 1\n");
441 return false;
442 }
443 if (!L->getExitingBlock()) {
444 LLVM_DEBUG(dbgs() << "Loop doesn't have unique exit block\n");
445 return false;
446 }
447 }
448 return true;
449}
450
451namespace {
452
453/// LoopInterchangeLegality checks if it is legal to interchange the loop.
454class LoopInterchangeLegality {
455public:
456 LoopInterchangeLegality(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
457 OptimizationRemarkEmitter *ORE, DominatorTree *DT)
458 : OuterLoop(Outer), InnerLoop(Inner), SE(SE), DT(DT), ORE(ORE) {}
459
460 /// Check if the loops can be interchanged.
461 bool canInterchangeLoops(unsigned InnerLoopId, unsigned OuterLoopId,
462 CharMatrix &DepMatrix);
463
464 /// Check if the loop structure is understood. We do not handle triangular
465 /// loops for now.
466 bool isLoopStructureUnderstood();
467
468 bool currentLimitations();
469
470 const SmallPtrSetImpl<PHINode *> &getOuterInnerReductions() const {
471 return OuterInnerReductions;
472 }
473
474 const ArrayRef<PHINode *> getInnerLoopInductions() const {
475 return InnerLoopInductions;
476 }
477
478 ArrayRef<Instruction *> getHasNoWrapReductions() const {
479 return HasNoWrapReductions;
480 }
481
482 ArrayRef<Instruction *> getHasNoInfInsts() const { return HasNoInfInsts; }
483
484 /// Record reductions in the inner loop. Currently supported reductions:
485 /// - initialized from a constant.
486 /// - reduction PHI node has only one user.
487 /// - located in the innermost loop.
488 struct InnerReduction {
489 /// The reduction itself.
490 PHINode *Reduction;
491 Value *Init;
492 Value *Next;
493 /// The Lcssa PHI.
494 PHINode *LcssaPhi;
495 /// Store reduction result into memory object.
496 StoreInst *LcssaStore;
497 /// The memory Location.
498 Value *MemRef;
499 Type *ElemTy;
500 };
501
502 ArrayRef<InnerReduction> getInnerReductions() const {
503 return InnerReductions;
504 }
505
506private:
507 bool tightlyNested(Loop *Outer, Loop *Inner);
508 bool containsUnsafeInstructions(BasicBlock *BB, Instruction *Skip);
509
510 /// Traverse all PHI nodes in the header of each loop in the loop nest
511 /// starting from \p OuterLoop, and perform the following checks:
512 ///
513 /// - Identify induction variables in the child loop of \p OuterLoop.
514 /// - Check for reductions across the inner loop and \p OuterLoop.
515 /// - Detect unsupported PHI nodes.
516 ///
517 /// Return false if any unsupported PHI node is found or if no induction
518 /// variable is found in the child loop of \p OuterLoop. Otherwise return
519 /// true.
520 bool checkInductionsAndReductions(Loop *OuterLoop);
521
522 /// Detect and record the reduction of the inner loop. Add them to
523 /// InnerReductions.
524 ///
525 /// innerloop:
526 /// Re = phi<0.0, Next>
527 /// Next = Re op ...
528 /// OuterLoopLatch:
529 /// Lcssa = phi<Next> ; lcssa phi
530 /// store Lcssa, MemRef ; LcssaStore
531 ///
532 bool isInnerReduction(Loop *L, PHINode *Phi,
533 SmallVectorImpl<Instruction *> &HasNoWrapInsts);
534
535 Loop *OuterLoop;
536 Loop *InnerLoop;
537
538 ScalarEvolution *SE;
539 DominatorTree *DT;
540
541 /// Interface to emit optimization remarks.
542 OptimizationRemarkEmitter *ORE;
543
544 /// Set of reduction PHIs taking part of a reduction across the inner and
545 /// outer loop.
546 SmallPtrSet<PHINode *, 4> OuterInnerReductions;
547
548 /// Set of inner loop induction PHIs
549 SmallVector<PHINode *, 8> InnerLoopInductions;
550
551 /// Hold instructions that have nuw/nsw flags and involved in reductions,
552 /// like integer addition/multiplication. Those flags must be dropped when
553 /// interchanging the loops.
554 SmallVector<Instruction *, 4> HasNoWrapReductions;
555
556 /// Hold instructions that have ninf flags and involved in reductions. Those
557 /// flags must be dropped when interchanging the loops.
558 SmallVector<Instruction *, 4> HasNoInfInsts;
559
560 /// Vector of reductions in the inner loop.
561 SmallVector<InnerReduction, 8> InnerReductions;
562};
563
564/// Manages information utilized by the profitability check for cache. The main
565/// purpose of this class is to delay the computation of CacheCost until it is
566/// actually needed.
567class CacheCostManager {
568 Loop *OutermostLoop;
569 LoopStandardAnalysisResults *AR;
570 DependenceInfo *DI;
571
572 /// CacheCost for \ref OutermostLoop. Once it is computed, it is cached. Note
573 /// that the result can be nullptr.
574 std::optional<std::unique_ptr<CacheCost>> CC;
575
576 /// Maps each loop to an index representing the optimal position within the
577 /// loop-nest, as determined by the cache cost analysis.
578 DenseMap<const Loop *, unsigned> CostMap;
579
580 void computeIfUnitinialized();
581
582public:
583 CacheCostManager(Loop *OutermostLoop, LoopStandardAnalysisResults *AR,
584 DependenceInfo *DI)
585 : OutermostLoop(OutermostLoop), AR(AR), DI(DI) {}
586 CacheCost *getCacheCost();
587 const DenseMap<const Loop *, unsigned> &getCostMap();
588};
589
590/// LoopInterchangeProfitability checks if it is profitable to interchange the
591/// loop.
592class LoopInterchangeProfitability {
593public:
594 LoopInterchangeProfitability(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
595 OptimizationRemarkEmitter *ORE)
596 : OuterLoop(Outer), InnerLoop(Inner), SE(SE), ORE(ORE) {}
597
598 /// Check if the loop interchange is profitable.
599 bool isProfitable(const Loop *InnerLoop, const Loop *OuterLoop,
600 unsigned InnerLoopId, unsigned OuterLoopId,
601 CharMatrix &DepMatrix, CacheCostManager &CCM);
602
603private:
604 int getInstrOrderCost();
605 std::optional<bool> isProfitablePerLoopCacheAnalysis(
606 const DenseMap<const Loop *, unsigned> &CostMap, CacheCost *CC);
607 std::optional<bool> isProfitablePerInstrOrderCost();
608 std::optional<bool> isProfitableForVectorization(unsigned InnerLoopId,
609 unsigned OuterLoopId,
610 CharMatrix &DepMatrix);
611 Loop *OuterLoop;
612 Loop *InnerLoop;
613
614 /// Scev analysis.
615 ScalarEvolution *SE;
616
617 /// Interface to emit optimization remarks.
618 OptimizationRemarkEmitter *ORE;
619};
620
621/// LoopInterchangeTransform interchanges the loop.
622class LoopInterchangeTransform {
623public:
624 LoopInterchangeTransform(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
625 LoopInfo *LI, DominatorTree *DT,
626 const LoopInterchangeLegality &LIL)
627 : OuterLoop(Outer), InnerLoop(Inner), SE(SE), LI(LI), DT(DT), LIL(LIL) {}
628
629 /// Interchange OuterLoop and InnerLoop.
630 void transform(ArrayRef<Instruction *> DropNoWrapInsts,
631 ArrayRef<Instruction *> DropNoInfInsts);
632 void reduction2Memory();
633 void restructureLoops(Loop *NewInner, Loop *NewOuter,
634 BasicBlock *OrigInnerPreHeader,
635 BasicBlock *OrigOuterPreHeader);
636 void removeChildLoop(Loop *OuterLoop, Loop *InnerLoop);
637
638private:
639 void adjustLoopLinks();
640 void adjustLoopBranches();
641
642 Loop *OuterLoop;
643 Loop *InnerLoop;
644
645 /// Scev analysis.
646 ScalarEvolution *SE;
647
648 LoopInfo *LI;
649 DominatorTree *DT;
650
651 const LoopInterchangeLegality &LIL;
652};
653
654struct LoopInterchange {
655 ScalarEvolution *SE = nullptr;
656 LoopInfo *LI = nullptr;
657 DependenceInfo *DI = nullptr;
658 DominatorTree *DT = nullptr;
659 LoopStandardAnalysisResults *AR = nullptr;
660
661 /// Interface to emit optimization remarks.
662 OptimizationRemarkEmitter *ORE;
663
664 LoopInterchange(ScalarEvolution *SE, LoopInfo *LI, DependenceInfo *DI,
665 DominatorTree *DT, LoopStandardAnalysisResults *AR,
666 OptimizationRemarkEmitter *ORE)
667 : SE(SE), LI(LI), DI(DI), DT(DT), AR(AR), ORE(ORE) {}
668
669 bool run(Loop *L) {
670 if (L->getParentLoop())
671 return false;
672 SmallVector<Loop *, 8> LoopList;
673 populateWorklist(L&: *L, LoopList);
674 return processLoopList(LoopList);
675 }
676
677 bool run(LoopNest &LN) {
678 SmallVector<Loop *, 8> LoopList(LN.getLoops());
679 for (unsigned I = 1; I < LoopList.size(); ++I)
680 if (LoopList[I]->getParentLoop() != LoopList[I - 1])
681 return false;
682 return processLoopList(LoopList);
683 }
684
685 unsigned selectLoopForInterchange(ArrayRef<Loop *> LoopList) {
686 // TODO: Add a better heuristic to select the loop to be interchanged based
687 // on the dependence matrix. Currently we select the innermost loop.
688 return LoopList.size() - 1;
689 }
690
691 bool processLoopList(SmallVectorImpl<Loop *> &LoopList) {
692 bool Changed = false;
693
694 // Ensure proper loop nest depth.
695 assert(hasSupportedLoopDepth(LoopList, *ORE) &&
696 "Unsupported depth of loop nest.");
697
698 unsigned LoopNestDepth = LoopList.size();
699
700 LLVM_DEBUG({
701 dbgs() << "Processing LoopList of size = " << LoopNestDepth
702 << " containing the following loops:\n";
703 for (auto *L : LoopList) {
704 dbgs() << " - ";
705 L->print(dbgs());
706 }
707 });
708
709 CharMatrix DependencyMatrix;
710 Loop *OuterMostLoop = *(LoopList.begin());
711 if (!populateDependencyMatrix(DepMatrix&: DependencyMatrix, Level: LoopNestDepth,
712 L: OuterMostLoop, DI, SE, ORE)) {
713 LLVM_DEBUG(dbgs() << "Populating dependency matrix failed\n");
714 return false;
715 }
716
717 LLVM_DEBUG(dbgs() << "Dependency matrix before interchange:\n";
718 printDepMatrix(DependencyMatrix));
719
720 // Get the Outermost loop exit.
721 BasicBlock *LoopNestExit = OuterMostLoop->getExitBlock();
722 if (!LoopNestExit) {
723 LLVM_DEBUG(dbgs() << "OuterMostLoop '" << OuterMostLoop->getName()
724 << "' needs an unique exit block");
725 return false;
726 }
727
728 unsigned SelecLoopId = selectLoopForInterchange(LoopList);
729 CacheCostManager CCM(LoopList[0], AR, DI);
730 // We try to achieve the globally optimal memory access for the loopnest,
731 // and do interchange based on a bubble-sort fasion. We start from
732 // the innermost loop, move it outwards to the best possible position
733 // and repeat this process.
734 for (unsigned j = SelecLoopId; j > 0; j--) {
735 bool ChangedPerIter = false;
736 for (unsigned i = SelecLoopId; i > SelecLoopId - j; i--) {
737 bool Interchanged =
738 processLoop(LoopList, InnerLoopId: i, OuterLoopId: i - 1, DependencyMatrix, CCM);
739 ChangedPerIter |= Interchanged;
740 Changed |= Interchanged;
741 }
742 // Early abort if there was no interchange during an entire round of
743 // moving loops outwards.
744 if (!ChangedPerIter)
745 break;
746 }
747 return Changed;
748 }
749
750 bool processLoop(SmallVectorImpl<Loop *> &LoopList, unsigned InnerLoopId,
751 unsigned OuterLoopId,
752 std::vector<std::vector<char>> &DependencyMatrix,
753 CacheCostManager &CCM) {
754 Loop *OuterLoop = LoopList[OuterLoopId];
755 Loop *InnerLoop = LoopList[InnerLoopId];
756 LLVM_DEBUG(dbgs() << "Processing InnerLoopId = " << InnerLoopId
757 << " and OuterLoopId = " << OuterLoopId << "\n");
758 LoopInterchangeLegality LIL(OuterLoop, InnerLoop, SE, ORE, DT);
759 if (!LIL.canInterchangeLoops(InnerLoopId, OuterLoopId, DepMatrix&: DependencyMatrix)) {
760 LLVM_DEBUG(dbgs() << "Cannot prove legality, not interchanging loops '"
761 << OuterLoop->getName() << "' and '"
762 << InnerLoop->getName() << "'\n");
763 return false;
764 }
765 LLVM_DEBUG(dbgs() << "Loops '" << OuterLoop->getName() << "' and '"
766 << InnerLoop->getName()
767 << "' are legal to interchange\n");
768 LoopInterchangeProfitability LIP(OuterLoop, InnerLoop, SE, ORE);
769 if (!LIP.isProfitable(InnerLoop, OuterLoop, InnerLoopId, OuterLoopId,
770 DepMatrix&: DependencyMatrix, CCM)) {
771 LLVM_DEBUG(dbgs() << "Interchanging loops '" << OuterLoop->getName()
772 << "' and '" << InnerLoop->getName()
773 << "' not profitable.\n");
774 return false;
775 }
776
777 ORE->emit(RemarkBuilder: [&]() {
778 return OptimizationRemark(DEBUG_TYPE, "Interchanged",
779 InnerLoop->getStartLoc(),
780 InnerLoop->getHeader())
781 << "Loop interchanged with enclosing loop.";
782 });
783
784 LoopInterchangeTransform LIT(OuterLoop, InnerLoop, SE, LI, DT, LIL);
785 LIT.transform(DropNoWrapInsts: LIL.getHasNoWrapReductions(), DropNoInfInsts: LIL.getHasNoInfInsts());
786 LLVM_DEBUG(dbgs() << "Loops interchanged: outer loop '"
787 << OuterLoop->getName() << "' and inner loop '"
788 << InnerLoop->getName() << "'\n");
789 LoopsInterchanged++;
790
791 llvm::formLCSSARecursively(L&: *OuterLoop, DT: *DT, LI, SE);
792
793 // Loops interchanged, update LoopList accordingly.
794 std::swap(a&: LoopList[OuterLoopId], b&: LoopList[InnerLoopId]);
795 // Update the DependencyMatrix
796 interChangeDependencies(DepMatrix&: DependencyMatrix, FromIndx: InnerLoopId, ToIndx: OuterLoopId);
797
798 LLVM_DEBUG(dbgs() << "Dependency matrix after interchange:\n";
799 printDepMatrix(DependencyMatrix));
800
801 return true;
802 }
803};
804
805} // end anonymous namespace
806
807bool LoopInterchangeLegality::containsUnsafeInstructions(BasicBlock *BB,
808 Instruction *Skip) {
809 return any_of(Range&: *BB, P: [Skip](const Instruction &I) {
810 if (&I == Skip)
811 return false;
812 return I.mayHaveSideEffects() || I.mayReadFromMemory();
813 });
814}
815
816static FreezeInst *findFreezeInReNestedBlocks(Loop *OuterLoop,
817 Loop *InnerLoop) {
818 // adjustLoopLinks swaps the preheader bodies after changing their loop
819 // roles, so the original outer-preheader body remains outside the new outer
820 // loop and retains its execution count.
821 BasicBlock *Blocks[] = {
822 OuterLoop->getHeader(),
823 OuterLoop->getLoopLatch(),
824 InnerLoop->getLoopPreheader(),
825 InnerLoop->getExitBlock(),
826 };
827 for (BasicBlock *BB : Blocks)
828 if (BB)
829 for (Instruction &I : *BB)
830 if (auto *Freeze = dyn_cast<FreezeInst>(Val: &I))
831 return Freeze;
832 return nullptr;
833}
834
835static FreezeInst *
836findFreezeInInnerLatchCloneSet(Loop *InnerLoop,
837 ArrayRef<PHINode *> InnerLoopInductions) {
838 // Mirror the latch-condition and induction-update operand closure cloned by
839 // MoveInstructions in LoopInterchangeTransform::transform.
840 SmallSetVector<Instruction *, 8> Worklist;
841 auto IsDirectInnerLoopBlock = [InnerLoop](BasicBlock *BB) {
842 return InnerLoop->contains(BB) &&
843 none_of(Range: InnerLoop->getSubLoops(),
844 P: [BB](Loop *SubLoop) { return SubLoop->contains(BB); });
845 };
846 auto *LatchBranch =
847 dyn_cast<CondBrInst>(Val: InnerLoop->getLoopLatch()->getTerminator());
848 if (LatchBranch)
849 if (auto *Condition = dyn_cast<Instruction>(Val: LatchBranch->getCondition()))
850 Worklist.insert(X: Condition);
851
852 for (PHINode *Induction : InnerLoopInductions) {
853 auto *Incoming = dyn_cast<Instruction>(
854 Val: Induction->getIncomingValueForBlock(BB: InnerLoop->getLoopLatch()));
855 if (Incoming && !is_contained(Range&: InnerLoopInductions, Element: Incoming))
856 Worklist.insert(X: Incoming);
857 }
858
859 for (unsigned I = 0; I < Worklist.size(); ++I) {
860 Instruction *Current = Worklist[I];
861 if (auto *Freeze = dyn_cast<FreezeInst>(Val: Current))
862 return Freeze;
863 for (Value *Operand : Current->operands()) {
864 auto *OperandI = dyn_cast<Instruction>(Val: Operand);
865 if (!OperandI || !IsDirectInnerLoopBlock(OperandI->getParent()) ||
866 is_contained(Range&: InnerLoopInductions, Element: OperandI))
867 continue;
868 Worklist.insert(X: OperandI);
869 }
870 }
871 return nullptr;
872}
873
874bool LoopInterchangeLegality::tightlyNested(Loop *OuterLoop, Loop *InnerLoop) {
875 BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
876 BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
877 BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
878
879 LLVM_DEBUG(dbgs() << "Checking if loops '" << OuterLoop->getName()
880 << "' and '" << InnerLoop->getName()
881 << "' are tightly nested\n");
882
883 // In a perfectly nested loop the outer header branches only into the inner
884 // loop. If it can also reach the outer latch, it conditionally guards the
885 // inner loop (an imperfect nest), so the inner loop runs on only a subset of
886 // the outer iterations. Interchanging such a nest would run the inner loop on
887 // every outer iteration, including the guarded-off ones, which is illegal
888 // when the inner loop relies on the guard to terminate (e.g. an eq/ne exit
889 // whose trip count is degenerate once the guard is false). Reject by allowing
890 // the outer header to branch only into the inner loop.
891 //
892 // TODO: This is conservative. A guarded nest is still safe to interchange
893 // when the inner loop has a computable trip count that is empty exactly when
894 // the guard is false, e.g.:
895 // for (i = 0; i < N; i++)
896 // if (M > 0) // loop-invariant guard
897 // for (j = 0; j < M; j++) // empty when M <= 0
898 // A[j][i] = ...;
899 // Interchanging is legal here because the inner loop runs zero times on the
900 // guarded-off iterations.
901 for (BasicBlock *Succ : successors(BB: OuterLoopHeader))
902 if (Succ != InnerLoopPreHeader && Succ != InnerLoop->getHeader())
903 return false;
904
905 LLVM_DEBUG(dbgs() << "Checking instructions in Loop header and Loop latch\n");
906
907 // The inner loop reduction pattern requires storing the LCSSA PHI in
908 // the OuterLoop Latch. Therefore, when reduction2Memory is enabled, skip
909 // that store during checks.
910 Instruction *Skip = nullptr;
911 assert(InnerReductions.size() <= 1 &&
912 "So far we only support at most one reduction.");
913 if (InnerReductions.size() == 1)
914 Skip = InnerReductions[0].LcssaStore;
915
916 // We do not have any basic block in between now make sure the outer header
917 // and outer loop latch doesn't contain any unsafe instructions.
918 if (containsUnsafeInstructions(BB: OuterLoopHeader, Skip) ||
919 containsUnsafeInstructions(BB: OuterLoopLatch, Skip))
920 return false;
921
922 // Also make sure the inner loop preheader does not contain any unsafe
923 // instructions. Note that all instructions in the preheader will be moved to
924 // the outer loop header when interchanging.
925 if (InnerLoopPreHeader != OuterLoopHeader &&
926 containsUnsafeInstructions(BB: InnerLoopPreHeader, Skip))
927 return false;
928
929 BasicBlock *InnerLoopExit = InnerLoop->getExitBlock();
930 // Ensure the inner loop exit block flows to the outer loop latch possibly
931 // through empty blocks.
932 const BasicBlock &SuccInner =
933 LoopNest::skipEmptyBlockUntil(From: InnerLoopExit, End: OuterLoopLatch);
934 if (&SuccInner != OuterLoopLatch) {
935 LLVM_DEBUG(dbgs() << "Inner loop exit block " << *InnerLoopExit
936 << " does not lead to the outer loop latch.\n";);
937 return false;
938 }
939 // The inner loop exit block does flow to the outer loop latch and not some
940 // other BBs, now make sure it contains safe instructions, since it will be
941 // moved into the (new) inner loop after interchange.
942 if (containsUnsafeInstructions(BB: InnerLoopExit, Skip))
943 return false;
944
945 LLVM_DEBUG(dbgs() << "Loops are perfectly nested\n");
946 // We have a perfect loop nest.
947 return true;
948}
949
950bool LoopInterchangeLegality::isLoopStructureUnderstood() {
951 BasicBlock *InnerLoopPreheader = InnerLoop->getLoopPreheader();
952 for (PHINode *InnerInduction : InnerLoopInductions) {
953 unsigned Num = InnerInduction->getNumOperands();
954 for (unsigned i = 0; i < Num; ++i) {
955 Value *Val = InnerInduction->getOperand(i_nocapture: i);
956 if (isa<Constant>(Val))
957 continue;
958 Instruction *I = dyn_cast<Instruction>(Val);
959 if (!I)
960 return false;
961 // TODO: Handle triangular loops.
962 // e.g. for(int i=0;i<N;i++)
963 // for(int j=i;j<N;j++)
964 unsigned IncomBlockIndx = PHINode::getIncomingValueNumForOperand(i);
965 if (InnerInduction->getIncomingBlock(i: IncomBlockIndx) ==
966 InnerLoopPreheader &&
967 !OuterLoop->isLoopInvariant(V: I)) {
968 return false;
969 }
970 }
971 }
972
973 // TODO: Handle triangular loops of another form.
974 // e.g. for(int i=0;i<N;i++)
975 // for(int j=0;j<i;j++)
976 // or,
977 // for(int i=0;i<N;i++)
978 // for(int j=0;j*i<N;j++)
979 BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
980 CondBrInst *InnerLoopLatchBI =
981 dyn_cast<CondBrInst>(Val: InnerLoopLatch->getTerminator());
982 if (!InnerLoopLatchBI)
983 return false;
984
985 CmpInst *InnerLoopCmp = dyn_cast<CmpInst>(Val: InnerLoopLatchBI->getCondition());
986 if (!InnerLoopCmp)
987 return false;
988
989 Value *Op0 = InnerLoopCmp->getOperand(i_nocapture: 0);
990 Value *Op1 = InnerLoopCmp->getOperand(i_nocapture: 1);
991
992 // LHS and RHS of the inner loop exit condition, e.g.,
993 // in "for(int j=0;j<i;j++)", LHS is j and RHS is i.
994 Value *Left = nullptr;
995 Value *Right = nullptr;
996
997 // Check if V only involves inner loop induction variable.
998 // Return true if V is InnerInduction, or a cast from
999 // InnerInduction, or a binary operator that involves
1000 // InnerInduction and a constant.
1001 std::function<bool(Value *)> IsPathToInnerIndVar;
1002 IsPathToInnerIndVar = [this, &IsPathToInnerIndVar](const Value *V) -> bool {
1003 if (llvm::is_contained(Range&: InnerLoopInductions, Element: V))
1004 return true;
1005 if (isa<Constant>(Val: V))
1006 return true;
1007 const Instruction *I = dyn_cast<Instruction>(Val: V);
1008 if (!I)
1009 return false;
1010 if (isa<CastInst>(Val: I))
1011 return IsPathToInnerIndVar(I->getOperand(i: 0));
1012 if (isa<BinaryOperator>(Val: I))
1013 return IsPathToInnerIndVar(I->getOperand(i: 0)) &&
1014 IsPathToInnerIndVar(I->getOperand(i: 1));
1015 return false;
1016 };
1017
1018 // In case of multiple inner loop indvars, it is okay if LHS and RHS
1019 // are both inner indvar related variables.
1020 if (IsPathToInnerIndVar(Op0) && IsPathToInnerIndVar(Op1))
1021 return true;
1022
1023 // Otherwise we check if the cmp instruction compares an inner indvar
1024 // related variable (Left) with a outer loop invariant (Right).
1025 if (IsPathToInnerIndVar(Op0) && !isa<Constant>(Val: Op0)) {
1026 Left = Op0;
1027 Right = Op1;
1028 } else if (IsPathToInnerIndVar(Op1) && !isa<Constant>(Val: Op1)) {
1029 Left = Op1;
1030 Right = Op0;
1031 }
1032
1033 if (Left == nullptr)
1034 return false;
1035
1036 const SCEV *S = SE->getSCEV(V: Right);
1037 if (!SE->isLoopInvariant(S, L: OuterLoop))
1038 return false;
1039
1040 return true;
1041}
1042
1043// If SV is a LCSSA PHI node with a single incoming value, return the incoming
1044// value.
1045static Value *followLCSSA(Value *SV) {
1046 PHINode *PHI = dyn_cast<PHINode>(Val: SV);
1047 if (!PHI)
1048 return SV;
1049
1050 if (PHI->getNumIncomingValues() != 1)
1051 return SV;
1052 return followLCSSA(SV: PHI->getIncomingValue(i: 0));
1053}
1054
1055static bool checkReductionKind(Loop *L, PHINode *PHI,
1056 SmallVectorImpl<Instruction *> &HasNoWrapInsts,
1057 SmallVectorImpl<Instruction *> &HasNoInfInsts) {
1058 RecurrenceDescriptor RD;
1059 if (RecurrenceDescriptor::isReductionPHI(Phi: PHI, TheLoop: L, RedDes&: RD)) {
1060 // Detect floating point reduction only when it can be reordered.
1061 if (RD.getExactFPMathInst() != nullptr)
1062 return false;
1063
1064 RecurKind RK = RD.getRecurrenceKind();
1065 switch (RK) {
1066 case RecurKind::Or:
1067 case RecurKind::And:
1068 case RecurKind::Xor:
1069 case RecurKind::SMin:
1070 case RecurKind::SMax:
1071 case RecurKind::UMin:
1072 case RecurKind::UMax:
1073 return true;
1074
1075 // Interchanging the loops that contain AnyOf reduction is not always legal.
1076 // Especially, when the result value of the AnyOf is not loop-invariant with
1077 // respect to the outer loop, interchanging may change the semantics. The
1078 // following is an example of such case:
1079 // int A = {{ 1, 0 }, { 0, 1 }};
1080 // int red = 0;
1081 // for (int i = 0; i < 2; i++)
1082 // for (int j = 0; j < 2; j++)
1083 // red = (A[j][i] == 0) ? i + 1 : red;
1084 //
1085 // TODO: We may be able to support interchanging loops with AnyOf reduction
1086 // by checking the operand of the reduction is loop-invariant with respect
1087 // to the outer loop as well.
1088 case RecurKind::AnyOf:
1089 return false;
1090
1091 // Changing the order of floating-point operations may alter the results. If
1092 // a certain instruction has the ninf flag, it means that reordering can
1093 // produce a poison value, which may lead to undefined behavior. To prevent
1094 // this, we must drop the ninf flags if we decide to apply the
1095 // transformation.
1096 case RecurKind::FAdd:
1097 case RecurKind::FMul:
1098 case RecurKind::FMin:
1099 case RecurKind::FMax:
1100 case RecurKind::FMinimum:
1101 case RecurKind::FMaximum:
1102 case RecurKind::FMinimumNum:
1103 case RecurKind::FMaximumNum:
1104 case RecurKind::FMulAdd:
1105 for (Instruction *I : RD.getReductionOpChain(Phi: PHI, L))
1106 if (isa<FPMathOperator>(Val: I) && I->hasNoInfs())
1107 HasNoInfInsts.push_back(Elt: I);
1108 return true;
1109
1110 // Change the order of integer addition/multiplication may change the
1111 // semantics. Consider the following case:
1112 //
1113 // int A[2][2] = {{ INT_MAX, INT_MAX }, { INT_MIN, INT_MIN }};
1114 // int sum = 0;
1115 // for (int i = 0; i < 2; i++)
1116 // for (int j = 0; j < 2; j++)
1117 // sum += A[j][i];
1118 //
1119 // If the above loops are exchanged, the addition will cause an
1120 // overflow. To prevent this, we must drop the nuw/nsw flags from the
1121 // addition/multiplication instructions when we actually exchanges the
1122 // loops.
1123 case RecurKind::Add:
1124 case RecurKind::Mul: {
1125 unsigned OpCode = RecurrenceDescriptor::getOpcode(Kind: RK);
1126 SmallVector<Instruction *, 4> Ops = RD.getReductionOpChain(Phi: PHI, L);
1127
1128 // Bail out when we fail to collect reduction instructions chain.
1129 if (Ops.empty())
1130 return false;
1131
1132 for (Instruction *I : Ops) {
1133 assert(I->getOpcode() == OpCode &&
1134 "Expected the instruction to be the reduction operation");
1135 (void)OpCode;
1136
1137 // If the instruction has nuw/nsw flags, we must drop them when the
1138 // transformation is actually performed.
1139 if (I->hasNoSignedWrap() || I->hasNoUnsignedWrap())
1140 HasNoWrapInsts.push_back(Elt: I);
1141 }
1142 return true;
1143 }
1144
1145 default:
1146 return false;
1147 }
1148 } else
1149 return false;
1150}
1151
1152// Check V's users to see if it is involved in a reduction in L.
1153static PHINode *
1154findInnerReductionPhi(Loop *L, Value *V,
1155 SmallVectorImpl<Instruction *> &HasNoWrapInsts,
1156 SmallVectorImpl<Instruction *> &HasNoInfInsts) {
1157 // Reduction variables cannot be constants.
1158 if (isa<Constant>(Val: V))
1159 return nullptr;
1160
1161 for (Value *User : V->users()) {
1162 if (PHINode *PHI = dyn_cast<PHINode>(Val: User)) {
1163 if (PHI->getNumIncomingValues() == 1)
1164 continue;
1165
1166 if (checkReductionKind(L, PHI, HasNoWrapInsts, HasNoInfInsts))
1167 return PHI;
1168 else
1169 return nullptr;
1170 }
1171 }
1172
1173 return nullptr;
1174}
1175
1176bool LoopInterchangeLegality::isInnerReduction(
1177 Loop *L, PHINode *Phi, SmallVectorImpl<Instruction *> &HasNoWrapInsts) {
1178
1179 // Only support reduction2Mem when the loop nest to be interchanged is
1180 // the innermost two loops.
1181 if (!L->isInnermost()) {
1182 LLVM_DEBUG(dbgs() << "Only supported when the loop is the innermost.\n");
1183 ORE->emit(RemarkBuilder: [&]() {
1184 return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedInnerReduction",
1185 L->getStartLoc(), L->getHeader())
1186 << "Only supported when the loop is the innermost.";
1187 });
1188 return false;
1189 }
1190
1191 if (Phi->getNumIncomingValues() != 2)
1192 return false;
1193
1194 Value *Init = Phi->getIncomingValueForBlock(BB: L->getLoopPreheader());
1195 Value *Next = Phi->getIncomingValueForBlock(BB: L->getLoopLatch());
1196
1197 // So far only supports constant initial value.
1198 if (!isa<Constant>(Val: Init)) {
1199 LLVM_DEBUG(
1200 dbgs()
1201 << "Only supported for the reduction with a constant initial value.\n");
1202 ORE->emit(RemarkBuilder: [&]() {
1203 return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedInnerReduction",
1204 L->getStartLoc(), L->getHeader())
1205 << "Only supported for the reduction with a constant initial "
1206 "value.";
1207 });
1208 return false;
1209 }
1210
1211 // The reduction result must live in the inner loop.
1212 if (Instruction *I = dyn_cast<Instruction>(Val: Next)) {
1213 BasicBlock *BB = I->getParent();
1214 if (!L->contains(BB))
1215 return false;
1216 }
1217
1218 // The reduction should have only one user.
1219 if (!Phi->hasOneUser())
1220 return false;
1221
1222 // Check the reduction kind.
1223 if (!checkReductionKind(L, PHI: Phi, HasNoWrapInsts, HasNoInfInsts))
1224 return false;
1225
1226 // Find lcssa_phi in OuterLoop's Latch
1227 BasicBlock *ExitBlock = L->getExitBlock();
1228 if (!ExitBlock)
1229 return false;
1230
1231 PHINode *Lcssa = NULL;
1232 for (auto *U : Next->users()) {
1233 if (auto *P = dyn_cast<PHINode>(Val: U)) {
1234 if (P == Phi)
1235 continue;
1236
1237 if (Lcssa == NULL && P->getParent() == ExitBlock &&
1238 P->getIncomingValueForBlock(BB: L->getLoopLatch()) == Next)
1239 Lcssa = P;
1240 else
1241 return false;
1242 } else
1243 return false;
1244 }
1245 if (!Lcssa)
1246 return false;
1247
1248 if (!Lcssa->hasOneUser()) {
1249 LLVM_DEBUG(dbgs() << "Only supported when the reduction is used once in "
1250 "the outer loop.\n");
1251 ORE->emit(RemarkBuilder: [&]() {
1252 return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedInnerReduction",
1253 L->getStartLoc(), L->getHeader())
1254 << "Only supported when the reduction is used once in the outer "
1255 "loop.";
1256 });
1257 return false;
1258 }
1259
1260 StoreInst *LcssaStore =
1261 dyn_cast<StoreInst>(Val: Lcssa->getUniqueUndroppableUser());
1262 if (!LcssaStore || LcssaStore->getParent() != ExitBlock)
1263 return false;
1264
1265 Value *MemRef = LcssaStore->getOperand(i_nocapture: 1);
1266 Type *ElemTy = LcssaStore->getOperand(i_nocapture: 0)->getType();
1267
1268 // LcssaStore stores the reduction result in BB.
1269 // When the reduction is initialized from a constant value, we need to load
1270 // from the memory object into the target basic block of the inner loop. This
1271 // means the memory reference was used prematurely. So we must ensure that the
1272 // memory reference does not dominate the target basic block.
1273 // TODO: Move the memory reference definition into the loop header.
1274 if (!DT->dominates(Def: dyn_cast<Instruction>(Val: MemRef), BB: L->getHeader())) {
1275 LLVM_DEBUG(dbgs() << "Only supported when memory reference dominate "
1276 "the inner loop.\n");
1277 ORE->emit(RemarkBuilder: [&]() {
1278 return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedInnerReduction",
1279 L->getStartLoc(), L->getHeader())
1280 << "Only supported when memory reference dominate the inner "
1281 "loop.";
1282 });
1283 return false;
1284 }
1285
1286 // Found a reduction in the inner loop.
1287 InnerReduction SR;
1288 SR.Reduction = Phi;
1289 SR.Init = Init;
1290 SR.Next = Next;
1291 SR.LcssaPhi = Lcssa;
1292 SR.LcssaStore = LcssaStore;
1293 SR.MemRef = MemRef;
1294 SR.ElemTy = ElemTy;
1295
1296 InnerReductions.push_back(Elt: SR);
1297 return true;
1298}
1299
1300bool LoopInterchangeLegality::checkInductionsAndReductions(Loop *OuterLoop) {
1301 auto ChildLoop = [](Loop *L) {
1302 assert(L->getSubLoops().size() <= 1 &&
1303 "Expect at most one child loop for now.");
1304 return L->getSubLoops().empty() ? nullptr : L->getSubLoops().front();
1305 };
1306
1307 Loop *InnerLoop = ChildLoop(OuterLoop);
1308 for (Loop *CurLoop = OuterLoop; CurLoop; CurLoop = ChildLoop(CurLoop)) {
1309 for (PHINode &PHI : CurLoop->getHeader()->phis()) {
1310 InductionDescriptor ID;
1311 if (InductionDescriptor::isInductionPHI(Phi: &PHI, L: CurLoop, SE, D&: ID)) {
1312 if (CurLoop == InnerLoop) {
1313 const SCEV *Step = ID.getStep();
1314 if (!SE->isLoopInvariant(S: Step, L: OuterLoop))
1315 return false;
1316 InnerLoopInductions.push_back(Elt: &PHI);
1317 }
1318 continue;
1319 }
1320
1321 if (CurLoop == OuterLoop) {
1322 // PHIs in inner loops need to be part of a reduction in the outer loop,
1323 if (PHI.getNumIncomingValues() != 2) {
1324 LLVM_DEBUG(dbgs() << "Only PHI nodes in the outer loop header with 2 "
1325 "incoming values are supported.\n");
1326 return false;
1327 }
1328 // Check if we have a PHI node in the outer loop that has a reduction
1329 // result from the inner loop as an incoming value.
1330 Value *V = followLCSSA(
1331 SV: PHI.getIncomingValueForBlock(BB: OuterLoop->getLoopLatch()));
1332 PHINode *InnerRedPhi = findInnerReductionPhi(
1333 L: InnerLoop, V, HasNoWrapInsts&: HasNoWrapReductions, HasNoInfInsts);
1334
1335 // Reject if PHI has users other than InnerRedPhi. The typical case is
1336 // as follows:
1337 //
1338 // o.header:
1339 // %red.o = phi [ 0, ... ], [ %red.next, %o.latch ]
1340 // br label %i.header
1341 //
1342 // i.header:
1343 // %red.i = phi [ %red.o, %o.header ], [ %red.next, %i.latch ]
1344 // br label %i.body
1345 //
1346 // i.body:
1347 // store %red.o to %mem
1348 // ...
1349 //
1350 if (!InnerRedPhi ||
1351 !llvm::is_contained(Range: InnerRedPhi->incoming_values(), Element: &PHI) ||
1352 !all_of(Range: PHI.users(),
1353 P: [InnerRedPhi](User *U) { return U == InnerRedPhi; })) {
1354 LLVM_DEBUG(
1355 dbgs()
1356 << "Failed to recognize PHI as an induction or reduction.\n");
1357 ORE->emit(RemarkBuilder: [&]() {
1358 return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedPHIOuter",
1359 OuterLoop->getStartLoc(),
1360 OuterLoop->getHeader())
1361 << "Only outer loops with induction or reduction PHI nodes "
1362 "can be interchanged currently.";
1363 });
1364 return false;
1365 }
1366
1367 OuterInnerReductions.insert(Ptr: &PHI);
1368 OuterInnerReductions.insert(Ptr: InnerRedPhi);
1369 } else {
1370 if (OuterInnerReductions.count(Ptr: &PHI)) {
1371 LLVM_DEBUG(dbgs() << "Found a reduction across the outer loop.\n");
1372 } else if (EnableReduction2Memory &&
1373 isInnerReduction(L: CurLoop, Phi: &PHI, HasNoWrapInsts&: HasNoWrapReductions)) {
1374 LLVM_DEBUG(dbgs() << "Found a reduction in the inner loop: \n"
1375 << PHI << '\n');
1376 } else {
1377 ORE->emit(RemarkBuilder: [&]() {
1378 return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedPHIInner",
1379 CurLoop->getStartLoc(),
1380 CurLoop->getHeader())
1381 << "Only inner loops with induction or reduction PHI nodes "
1382 "can be interchanged currently.";
1383 });
1384 return false;
1385 }
1386 }
1387 }
1388
1389 // For now we only support at most one reduction.
1390 if (InnerReductions.size() > 1) {
1391 LLVM_DEBUG(dbgs() << "Only supports at most one reduction.\n");
1392 ORE->emit(RemarkBuilder: [&]() {
1393 return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedInnerReduction",
1394 CurLoop->getStartLoc(),
1395 CurLoop->getHeader())
1396 << "Only supports at most one reduction.";
1397 });
1398 return false;
1399 }
1400 }
1401
1402 return !InnerLoopInductions.empty();
1403}
1404
1405// This function indicates the current limitations in the transform as a result
1406// of which we do not proceed.
1407bool LoopInterchangeLegality::currentLimitations() {
1408 BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
1409
1410 // transform currently expects the loop latches to also be the exiting
1411 // blocks.
1412 if (InnerLoop->getExitingBlock() != InnerLoopLatch ||
1413 OuterLoop->getExitingBlock() != OuterLoop->getLoopLatch() ||
1414 !isa<CondBrInst>(Val: InnerLoopLatch->getTerminator()) ||
1415 !isa<CondBrInst>(Val: OuterLoop->getLoopLatch()->getTerminator())) {
1416 LLVM_DEBUG(
1417 dbgs() << "Loops where the latch is not the exiting block are not"
1418 << " supported currently.\n");
1419 ORE->emit(RemarkBuilder: [&]() {
1420 return OptimizationRemarkMissed(DEBUG_TYPE, "ExitingNotLatch",
1421 OuterLoop->getStartLoc(),
1422 OuterLoop->getHeader())
1423 << "Loops where the latch is not the exiting block cannot be"
1424 " interchange currently.";
1425 });
1426 return true;
1427 }
1428
1429 // TODO: Triangular loops are not handled for now.
1430 if (!isLoopStructureUnderstood()) {
1431 LLVM_DEBUG(dbgs() << "Loop structure not understood by pass\n");
1432 ORE->emit(RemarkBuilder: [&]() {
1433 return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedStructureInner",
1434 InnerLoop->getStartLoc(),
1435 InnerLoop->getHeader())
1436 << "Inner loop structure not understood currently.";
1437 });
1438 return true;
1439 }
1440
1441 // Currently, we do not support loops that have a predecessor entering the
1442 // loop via an indirectbr.
1443 for (Loop *L : {OuterLoop, InnerLoop}) {
1444 BasicBlock *Header = L->getHeader();
1445 for (BasicBlock *Pred : predecessors(BB: Header)) {
1446 if (L->contains(BB: Pred))
1447 continue;
1448 if (isa<IndirectBrInst>(Val: Pred->getTerminator())) {
1449 LLVM_DEBUG(
1450 dbgs() << "Indirect branch found in the loop predecessor.\n");
1451 ORE->emit(RemarkBuilder: [&]() {
1452 return OptimizationRemarkMissed(DEBUG_TYPE, "IndirectBranchPreheader",
1453 L->getStartLoc(), L->getHeader())
1454 << "Indirect branch found in the loop predecessor.";
1455 });
1456 return true;
1457 }
1458 }
1459 }
1460
1461 // Currently, we do not support loops where the inner loop header has
1462 // duplicate successors.
1463 SmallPtrSet<BasicBlock *, 2> InnerLoopHeaderSuccs;
1464 for (BasicBlock *Succ : successors(BB: InnerLoop->getHeader()))
1465 if (!InnerLoopHeaderSuccs.insert(Ptr: Succ).second)
1466 return true;
1467
1468 return false;
1469}
1470
1471/// We currently only support LCSSA PHI nodes in the inner loop exit if their
1472/// users are either of the following:
1473///
1474/// - Reduction PHIs
1475/// - PHIs outside the outer loop
1476/// - PHIs belonging to the latch of the outer loop
1477///
1478/// These conditions mean that we are only interested in the final value after
1479/// the inner loop.
1480static bool
1481areInnerLoopExitPHIsSupported(Loop *OuterL, Loop *InnerL,
1482 SmallPtrSetImpl<PHINode *> &Reductions,
1483 PHINode *LcssaReduction) {
1484 BasicBlock *InnerExit = InnerL->getUniqueExitBlock();
1485 for (PHINode &PHI : InnerExit->phis()) {
1486 // The reduction LCSSA PHI will have only one incoming block, which comes
1487 // from the loop latch.
1488 if (PHI.getNumIncomingValues() > 1)
1489 return false;
1490 // The reduction LCSSA PHI's store user is rewritten by reduction2Memory();
1491 // skip its user-check but keep validating the remaining LCSSA PHIs.
1492 if (&PHI == LcssaReduction)
1493 continue;
1494 if (any_of(Range: PHI.users(), P: [&Reductions, OuterL](User *U) {
1495 PHINode *PN = dyn_cast<PHINode>(Val: U);
1496 if (!PN)
1497 return true;
1498 if (Reductions.count(Ptr: PN))
1499 return false;
1500 BasicBlock *PB = PN->getParent();
1501 if (!OuterL->contains(BB: PB))
1502 return false;
1503 return PB != OuterL->getLoopLatch();
1504 }))
1505 return false;
1506 }
1507 return true;
1508}
1509
1510// We currently support LCSSA PHI nodes in the outer loop exit, if their
1511// incoming values do not come from the outer loop latch or if the
1512// outer loop latch has a single predecessor. In that case, the value will
1513// be available if both the inner and outer loop conditions are true, which
1514// will still be true after interchanging. If we have multiple predecessor,
1515// that may not be the case, e.g. because the outer loop latch may be executed
1516// if the inner loop is not executed.
1517static bool areOuterLoopExitPHIsSupported(Loop *OuterLoop, Loop *InnerLoop) {
1518 BasicBlock *LoopNestExit = OuterLoop->getUniqueExitBlock();
1519 for (PHINode &PHI : LoopNestExit->phis()) {
1520 for (Value *Incoming : PHI.incoming_values()) {
1521 Instruction *IncomingI = dyn_cast<Instruction>(Val: Incoming);
1522 if (!IncomingI || IncomingI->getParent() != OuterLoop->getLoopLatch())
1523 continue;
1524
1525 // The incoming value is defined in the outer loop latch. Currently we
1526 // only support that in case the outer loop latch has a single predecessor.
1527 // This guarantees that the outer loop latch is executed if and only if
1528 // the inner loop is executed (because tightlyNested() guarantees that the
1529 // outer loop header only branches to the inner loop or the outer loop
1530 // latch).
1531 // FIXME: We could weaken this logic and allow multiple predecessors,
1532 // if the values are produced outside the loop latch. We would need
1533 // additional logic to update the PHI nodes in the exit block as
1534 // well.
1535 if (OuterLoop->getLoopLatch()->getUniquePredecessor() == nullptr)
1536 return false;
1537 }
1538 }
1539 return true;
1540}
1541
1542/// The transform partially clones the inner loop's latch block, but PHI nodes
1543/// cannot be cloned this way. This function follows the instruction trees that
1544/// would be cloned and checks whether any PHI node other than the induction
1545/// PHIs feeds them. If such a PHI is found, the interchange is rejected.
1546///
1547/// TODO: This check strongly depends on the current implementation of the
1548/// transform. Ideally, the transform should be able to handle such PHI nodes in
1549/// the inner loop latch.
1550static bool areInnerLoopLatchPHIsSupported(Loop *InnerLoop,
1551 ArrayRef<PHINode *> InductionPHIs) {
1552 BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
1553
1554 // Seed the worklist with the roots of the use-def chains the transform
1555 // clones: the latch's exit condition and the incoming values of the induction
1556 // PHIs from the latch.
1557 SmallSetVector<Instruction *, 8> Worklist;
1558 if (auto *LatchBI = dyn_cast<CondBrInst>(Val: InnerLoopLatch->getTerminator()))
1559 if (auto *CondI = dyn_cast<Instruction>(Val: LatchBI->getCondition()))
1560 Worklist.insert(X: CondI);
1561 for (PHINode *InductionPHI : InductionPHIs) {
1562 if (auto *IncomingI = dyn_cast<Instruction>(
1563 Val: InductionPHI->getIncomingValueForBlock(BB: InnerLoopLatch)))
1564 if (!is_contained(Range&: InductionPHIs, Element: IncomingI))
1565 Worklist.insert(X: IncomingI);
1566 }
1567
1568 // Bail if a PHI node other than the induction PHIs feeds the cloned
1569 // instructions, walking the operand trees within the inner loop.
1570 SmallPtrSet<Instruction *, 4> InductionPHISet(InductionPHIs.begin(),
1571 InductionPHIs.end());
1572 for (unsigned I = 0; I < Worklist.size(); ++I) {
1573 Instruction *Cur = Worklist[I];
1574 if (isa<PHINode>(Val: Cur) && !InductionPHISet.contains(Ptr: Cur))
1575 return false;
1576 for (Value *Op : Cur->operands())
1577 if (auto *OpI = dyn_cast<Instruction>(Val: Op))
1578 if (InnerLoop->contains(Inst: OpI))
1579 Worklist.insert(X: OpI);
1580 }
1581 return true;
1582}
1583
1584bool LoopInterchangeLegality::canInterchangeLoops(unsigned InnerLoopId,
1585 unsigned OuterLoopId,
1586 CharMatrix &DepMatrix) {
1587 if (!isLegalToInterChangeLoops(DepMatrix, InnerLoopId, OuterLoopId)) {
1588 LLVM_DEBUG(dbgs() << "Failed interchange InnerLoopId = " << InnerLoopId
1589 << " and OuterLoopId = " << OuterLoopId
1590 << " due to dependence\n");
1591 ORE->emit(RemarkBuilder: [&]() {
1592 return OptimizationRemarkMissed(DEBUG_TYPE, "Dependence",
1593 InnerLoop->getStartLoc(),
1594 InnerLoop->getHeader())
1595 << "Cannot interchange loops due to dependences.";
1596 });
1597 return false;
1598 }
1599 // Check if outer and inner loop contain legal instructions only.
1600 for (auto *BB : OuterLoop->blocks())
1601 for (Instruction &I : *BB) {
1602 // Loads and stores are checked separately, so we can skip them here.
1603 if (isa<LoadInst, StoreInst, PseudoProbeInst>(Val: &I))
1604 continue;
1605
1606 // We cannot ignore potential memory reads, e.g., loads inside the called
1607 // function.
1608 if (!I.mayHaveSideEffects() && !I.mayReadFromMemory())
1609 continue;
1610
1611 LLVM_DEBUG(
1612 dbgs()
1613 << "Loops contain instructions that cannot be safely interchanged\n");
1614 ORE->emit(RemarkBuilder: [&]() {
1615 return OptimizationRemarkMissed(DEBUG_TYPE, "UnsafeInst",
1616 I.getDebugLoc(), I.getParent())
1617 << "Cannot interchange loops due to instruction that is "
1618 "potentially unsafe to interchange.";
1619 });
1620
1621 return false;
1622 }
1623
1624 if (!checkInductionsAndReductions(OuterLoop)) {
1625 LLVM_DEBUG(dbgs() << "Failed to find inner loop inductions or found "
1626 "unsupported reductions.\n");
1627 return false;
1628 }
1629
1630 if (!areInnerLoopLatchPHIsSupported(InnerLoop, InductionPHIs: InnerLoopInductions)) {
1631 LLVM_DEBUG(dbgs() << "Found unsupported PHI nodes in inner loop latch.\n");
1632 ORE->emit(RemarkBuilder: [&]() {
1633 return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedInnerLatchPHI",
1634 InnerLoop->getStartLoc(),
1635 InnerLoop->getHeader())
1636 << "Cannot interchange loops because unsupported PHI nodes found "
1637 "in inner loop latch.";
1638 });
1639 return false;
1640 }
1641
1642 FreezeInst *Freeze = findFreezeInReNestedBlocks(OuterLoop, InnerLoop);
1643 if (!Freeze)
1644 Freeze = findFreezeInInnerLatchCloneSet(InnerLoop, InnerLoopInductions);
1645 if (Freeze) {
1646 LLVM_DEBUG(dbgs() << "Interchange would re-nest or duplicate freeze\n");
1647 ORE->emit(RemarkBuilder: [&]() {
1648 return OptimizationRemarkMissed(DEBUG_TYPE, "UnsafeInst",
1649 Freeze->getDebugLoc(),
1650 Freeze->getParent())
1651 << "Cannot interchange loops because re-nesting or duplicating "
1652 "freeze may change its sampling behavior.";
1653 });
1654 return false;
1655 }
1656
1657 // TODO: The loops could not be interchanged due to current limitations in the
1658 // transform module.
1659 if (currentLimitations()) {
1660 LLVM_DEBUG(dbgs() << "Not legal because of current transform limitation\n");
1661 return false;
1662 }
1663
1664 // Check if the loops are tightly nested.
1665 if (!tightlyNested(OuterLoop, InnerLoop)) {
1666 LLVM_DEBUG(dbgs() << "Loops not tightly nested\n");
1667 ORE->emit(RemarkBuilder: [&]() {
1668 return OptimizationRemarkMissed(DEBUG_TYPE, "NotTightlyNested",
1669 InnerLoop->getStartLoc(),
1670 InnerLoop->getHeader())
1671 << "Cannot interchange loops because they are not tightly "
1672 "nested.";
1673 });
1674 return false;
1675 }
1676
1677 // The LCSSA PHI for the reduction has passed checks before; its user
1678 // is a store instruction.
1679 PHINode *LcssaReduction = nullptr;
1680 assert(InnerReductions.size() <= 1 &&
1681 "So far we only support at most one reduction.");
1682 if (InnerReductions.size() == 1)
1683 LcssaReduction = InnerReductions[0].LcssaPhi;
1684
1685 if (!areInnerLoopExitPHIsSupported(OuterL: OuterLoop, InnerL: InnerLoop, Reductions&: OuterInnerReductions,
1686 LcssaReduction)) {
1687 LLVM_DEBUG(dbgs() << "Found unsupported PHI nodes in inner loop exit.\n");
1688 ORE->emit(RemarkBuilder: [&]() {
1689 return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedExitPHI",
1690 InnerLoop->getStartLoc(),
1691 InnerLoop->getHeader())
1692 << "Found unsupported PHI node in loop exit.";
1693 });
1694 return false;
1695 }
1696
1697 if (!areOuterLoopExitPHIsSupported(OuterLoop, InnerLoop)) {
1698 LLVM_DEBUG(dbgs() << "Found unsupported PHI nodes in outer loop exit.\n");
1699 ORE->emit(RemarkBuilder: [&]() {
1700 return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedExitPHI",
1701 OuterLoop->getStartLoc(),
1702 OuterLoop->getHeader())
1703 << "Found unsupported PHI node in loop exit.";
1704 });
1705 return false;
1706 }
1707
1708 if (any_of(Range: OuterLoop->getLoopLatch()->phis(),
1709 P: [](PHINode &PHI) { return PHI.getNumIncomingValues() != 1; })) {
1710 LLVM_DEBUG(dbgs() << "Only outer loop latch PHI nodes with one incoming "
1711 "value are supported.\n");
1712 ORE->emit(RemarkBuilder: [&]() {
1713 return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedLatchPHI",
1714 OuterLoop->getStartLoc(),
1715 OuterLoop->getHeader())
1716 << "Only outer loop latch PHI nodes with one incoming value are "
1717 "supported.";
1718 });
1719 return false;
1720 }
1721
1722 // Regarding def-use chains that begin at an LCSSA PHI in the inner loop exit
1723 // and end at any instruction in the outer loop latch, we currently support
1724 // only the case where the chain contains only PHI nodes. Since we already
1725 // call `tightlyNested()`, we know that if there is a def-use chain that we
1726 // don't support (i.e., a chain that contains a non-PHI user), then the
1727 // non-PHI user must be in the outer loop latch.
1728 if (InnerLoop->getExitBlock() != OuterLoop->getLoopLatch())
1729 for (PHINode &PHI : OuterLoop->getLoopLatch()->phis())
1730 if (any_of(Range: PHI.users(), P: [](const User *U) { return !isa<PHINode>(Val: U); })) {
1731 LLVM_DEBUG(dbgs() << "Outer loop latch PHI has a non-PHI user.\n");
1732 ORE->emit(RemarkBuilder: [&]() {
1733 return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedLatchPHI",
1734 OuterLoop->getStartLoc(),
1735 OuterLoop->getHeader())
1736 << "Cannot interchange loops because an outer loop latch PHI "
1737 "node has a non-PHI user.";
1738 });
1739 return false;
1740 }
1741
1742 return true;
1743}
1744
1745void CacheCostManager::computeIfUnitinialized() {
1746 if (CC.has_value())
1747 return;
1748
1749 LLVM_DEBUG(dbgs() << "Compute CacheCost.\n");
1750 CC = CacheCost::getCacheCost(Root&: *OutermostLoop, AR&: *AR, DI&: *DI);
1751 // Obtain the loop vector returned from loop cache analysis beforehand,
1752 // and put each <Loop, index> pair into a map for constant time query
1753 // later. Indices in loop vector reprsent the optimal order of the
1754 // corresponding loop, e.g., given a loopnest with depth N, index 0
1755 // indicates the loop should be placed as the outermost loop and index N
1756 // indicates the loop should be placed as the innermost loop.
1757 //
1758 // For the old pass manager CacheCost would be null.
1759 if (*CC != nullptr)
1760 for (const auto &[Idx, Cost] : enumerate(First: (*CC)->getLoopCosts()))
1761 CostMap[Cost.first] = Idx;
1762}
1763
1764CacheCost *CacheCostManager::getCacheCost() {
1765 computeIfUnitinialized();
1766 return CC->get();
1767}
1768
1769const DenseMap<const Loop *, unsigned> &CacheCostManager::getCostMap() {
1770 computeIfUnitinialized();
1771 return CostMap;
1772}
1773
1774/// If \S contains an affine addrec for \p L, return the step recurrence of it.
1775/// If \S is loop invariant with respect to \p L, return nullptr. Otherwise,
1776/// return std::nullopt, which indicates we cannot determine the coefficient of
1777/// the addrec for \p L in \S.
1778/// TODO: Handle more complex cases. Maybe using SCEVTraversal is a good way to
1779/// do that.
1780static std::optional<const SCEV *>
1781getAddRecCoefficient(ScalarEvolution &SE, const SCEV *S, const Loop *L) {
1782 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Val: S);
1783 if (!AR) {
1784 if (SE.isLoopInvariant(S, L))
1785 return nullptr;
1786 return std::nullopt;
1787 }
1788
1789 if (!AR->isAffine()) {
1790 LLVM_DEBUG(dbgs() << "Unexpected non-affine addrec\n");
1791 return std::nullopt;
1792 }
1793
1794 std::optional<const SCEV *> Coeff =
1795 getAddRecCoefficient(SE, S: AR->getStart(), L);
1796 if (!Coeff.has_value())
1797 return std::nullopt;
1798
1799 if (AR->getLoop() == L) {
1800 assert(!*Coeff && "Found more than one addrec for the same loop");
1801 Coeff = AR->getStepRecurrence(SE);
1802 }
1803 return Coeff;
1804}
1805
1806int LoopInterchangeProfitability::getInstrOrderCost() {
1807 SmallPtrSet<const SCEV *, 4> GoodBasePtrs, BadBasePtrs;
1808 for (BasicBlock *BB : InnerLoop->blocks()) {
1809 for (Instruction &Ins : *BB) {
1810 if (!isa<LoadInst, StoreInst>(Val: &Ins))
1811 continue;
1812 const SCEV *Access = SE->getSCEV(V: getLoadStorePointerOperand(V: &Ins));
1813 const SCEV *BasePtr = SE->getPointerBase(V: Access);
1814 std::optional<const SCEV *> OuterCoeff =
1815 getAddRecCoefficient(SE&: *SE, S: Access, L: OuterLoop);
1816 std::optional<const SCEV *> InnerCoeff =
1817 getAddRecCoefficient(SE&: *SE, S: Access, L: InnerLoop);
1818
1819 if (!OuterCoeff.has_value() || !*OuterCoeff || !InnerCoeff.has_value() ||
1820 !*InnerCoeff)
1821 continue;
1822
1823 // This heuristic assumes that a smaller step recurrence implies that the
1824 // induction variable corresponding to the loop is used in the inner
1825 // dimension of the array. Placing such a loop in the inner position would
1826 // be beneficial in terms of locality. If the array access is of the form
1827 // like `A[3*i + 2*j]`, this heuristic may lead to an unprofitable
1828 // interchange, but we expect such cases to be rare.
1829 const SCEV *OuterStep = SE->getAbsExpr(Op: *OuterCoeff, /*IsNSW=*/false);
1830 const SCEV *InnerStep = SE->getAbsExpr(Op: *InnerCoeff, /*IsNSW=*/false);
1831 // If we find the inner induction after an outer induction e.g.
1832 //
1833 // for(int i=0;i<N;i++)
1834 // for(int j=0;j<N;j++)
1835 // A[i][j] = A[i-1][j-1]+k;
1836 //
1837 //
1838 // then it is a good order. If we find the outer induction after an inner
1839 // induction e.g.
1840 //
1841 // for(int i=0;i<N;i++)
1842 // for(int j=0;j<N;j++)
1843 // A[j][i] = A[j-1][i-1]+k;
1844 //
1845 // then it is a bad order.
1846 //
1847 // To avoid counting the same base pointers multiple times, we deduplicate
1848 // them by using a set of base pointers.
1849 if (SE->isKnownPredicate(Pred: ICmpInst::ICMP_SLT, LHS: InnerStep, RHS: OuterStep))
1850 GoodBasePtrs.insert(Ptr: BasePtr);
1851 else if (SE->isKnownPredicate(Pred: ICmpInst::ICMP_SLT, LHS: OuterStep, RHS: InnerStep))
1852 BadBasePtrs.insert(Ptr: BasePtr);
1853 }
1854 }
1855
1856 int GoodOrder = GoodBasePtrs.size();
1857 int BadOrder = BadBasePtrs.size();
1858 return GoodOrder - BadOrder;
1859}
1860
1861std::optional<bool>
1862LoopInterchangeProfitability::isProfitablePerLoopCacheAnalysis(
1863 const DenseMap<const Loop *, unsigned> &CostMap, CacheCost *CC) {
1864 // This is the new cost model returned from loop cache analysis.
1865 // A smaller index means the loop should be placed an outer loop, and vice
1866 // versa.
1867 auto InnerLoopIt = CostMap.find(Val: InnerLoop);
1868 if (InnerLoopIt == CostMap.end())
1869 return std::nullopt;
1870 auto OuterLoopIt = CostMap.find(Val: OuterLoop);
1871 if (OuterLoopIt == CostMap.end())
1872 return std::nullopt;
1873
1874 if (CC->getLoopCost(L: *OuterLoop) == CC->getLoopCost(L: *InnerLoop))
1875 return std::nullopt;
1876 unsigned InnerIndex = InnerLoopIt->second;
1877 unsigned OuterIndex = OuterLoopIt->second;
1878 LLVM_DEBUG(dbgs() << "InnerIndex = " << InnerIndex
1879 << ", OuterIndex = " << OuterIndex << "\n");
1880 assert(InnerIndex != OuterIndex && "CostMap should assign unique "
1881 "numbers to each loop");
1882 return std::optional<bool>(InnerIndex < OuterIndex);
1883}
1884
1885std::optional<bool>
1886LoopInterchangeProfitability::isProfitablePerInstrOrderCost() {
1887 // Legacy cost model: this is rough cost estimation algorithm. It counts the
1888 // good and bad order of induction variables in the instruction and allows
1889 // reordering if number of bad orders is more than good.
1890 int Cost = getInstrOrderCost();
1891 LLVM_DEBUG(dbgs() << "Cost = " << Cost << "\n");
1892 if (Cost < 0 && Cost < LoopInterchangeCostThreshold)
1893 return std::optional<bool>(true);
1894
1895 return std::nullopt;
1896}
1897
1898/// Return true if we can vectorize the loop specified by \p LoopId.
1899static bool canVectorize(const CharMatrix &DepMatrix, unsigned LoopId) {
1900 for (const auto &Dep : DepMatrix) {
1901 char Dir = Dep[LoopId];
1902 char DepType = Dep.back();
1903 assert((DepType == '<' || DepType == '*') &&
1904 "Unexpected element in dependency vector");
1905
1906 // There are no loop-carried dependencies.
1907 if (Dir == '=' || Dir == 'I')
1908 continue;
1909
1910 // DepType being '<' means that this direction vector represents a forward
1911 // dependency. In principle, a loop with '<' direction can be vectorized in
1912 // this case.
1913 if (Dir == '<' && DepType == '<')
1914 continue;
1915
1916 // We cannot prove that the loop is vectorizable.
1917 return false;
1918 }
1919 return true;
1920}
1921
1922std::optional<bool> LoopInterchangeProfitability::isProfitableForVectorization(
1923 unsigned InnerLoopId, unsigned OuterLoopId, CharMatrix &DepMatrix) {
1924 // If the outer loop cannot be vectorized, it is not profitable to move this
1925 // to inner position.
1926 if (!canVectorize(DepMatrix, LoopId: OuterLoopId))
1927 return false;
1928
1929 // If the inner loop cannot be vectorized but the outer loop can be, then it
1930 // is profitable to interchange to enable inner loop parallelism.
1931 if (!canVectorize(DepMatrix, LoopId: InnerLoopId))
1932 return true;
1933
1934 // If both the inner and the outer loop can be vectorized, it is necessary to
1935 // check the cost of each vectorized loop for profitability decision. At this
1936 // time we do not have a cost model to estimate them, so return nullopt.
1937 // TODO: Estimate the cost of vectorized loop when both the outer and the
1938 // inner loop can be vectorized.
1939 return std::nullopt;
1940}
1941
1942bool LoopInterchangeProfitability::isProfitable(
1943 const Loop *InnerLoop, const Loop *OuterLoop, unsigned InnerLoopId,
1944 unsigned OuterLoopId, CharMatrix &DepMatrix, CacheCostManager &CCM) {
1945 // Do not consider loops with a backedge that isn't taken, e.g. an
1946 // unconditional branch true/false, as candidates for interchange.
1947 // TODO: when interchange is forced, we should probably also allow
1948 // interchange for these loops, and thus this logic should be moved just
1949 // below the cost-model ignore check below. But this check is done first
1950 // to avoid the issue in #163954.
1951 const SCEV *InnerBTC = SE->getBackedgeTakenCount(L: InnerLoop);
1952 const SCEV *OuterBTC = SE->getBackedgeTakenCount(L: OuterLoop);
1953 if (InnerBTC && InnerBTC->isZero()) {
1954 LLVM_DEBUG(dbgs() << "Inner loop back-edge isn't taken, rejecting "
1955 "single iteration loop\n");
1956 return false;
1957 }
1958 if (OuterBTC && OuterBTC->isZero()) {
1959 LLVM_DEBUG(dbgs() << "Outer loop back-edge isn't taken, rejecting "
1960 "single iteration loop\n");
1961 return false;
1962 }
1963
1964 // Return true if interchange is forced and the cost-model ignored.
1965 if (Profitabilities.size() == 1 && Profitabilities[0] == RuleTy::Ignore)
1966 return true;
1967 assert(noDuplicateRulesAndIgnore(Profitabilities) &&
1968 "Duplicate rules and option 'ignore' are not allowed");
1969
1970 // isProfitable() is structured to avoid endless loop interchange. If the
1971 // highest priority rule (isProfitablePerLoopCacheAnalysis by default) could
1972 // decide the profitability then, profitability check will stop and return the
1973 // analysis result. If it failed to determine it (e.g., cache analysis failed
1974 // to analyze the loopnest due to delinearization issues) then go ahead the
1975 // second highest priority rule (isProfitablePerInstrOrderCost by default).
1976 // Likewise, if it failed to analysis the profitability then only, the last
1977 // rule (isProfitableForVectorization by default) will decide.
1978 std::optional<bool> shouldInterchange;
1979 for (RuleTy RT : Profitabilities) {
1980 switch (RT) {
1981 case RuleTy::PerLoopCacheAnalysis: {
1982 CacheCost *CC = CCM.getCacheCost();
1983 const DenseMap<const Loop *, unsigned> &CostMap = CCM.getCostMap();
1984 shouldInterchange = isProfitablePerLoopCacheAnalysis(CostMap, CC);
1985 break;
1986 }
1987 case RuleTy::PerInstrOrderCost:
1988 shouldInterchange = isProfitablePerInstrOrderCost();
1989 break;
1990 case RuleTy::ForVectorization:
1991 shouldInterchange =
1992 isProfitableForVectorization(InnerLoopId, OuterLoopId, DepMatrix);
1993 break;
1994 case RuleTy::Ignore:
1995 llvm_unreachable("Option 'ignore' is not supported with other options");
1996 break;
1997 }
1998
1999 // If this rule could determine the profitability, don't call subsequent
2000 // rules.
2001 if (shouldInterchange.has_value())
2002 break;
2003 }
2004
2005 if (!shouldInterchange.has_value()) {
2006 ORE->emit(RemarkBuilder: [&]() {
2007 return OptimizationRemarkMissed(DEBUG_TYPE, "InterchangeNotProfitable",
2008 InnerLoop->getStartLoc(),
2009 InnerLoop->getHeader())
2010 << "Insufficient information to calculate the cost of loop for "
2011 "interchange.";
2012 });
2013 return false;
2014 } else if (!shouldInterchange.value()) {
2015 ORE->emit(RemarkBuilder: [&]() {
2016 return OptimizationRemarkMissed(DEBUG_TYPE, "InterchangeNotProfitable",
2017 InnerLoop->getStartLoc(),
2018 InnerLoop->getHeader())
2019 << "Interchanging loops is not considered to improve cache "
2020 "locality nor vectorization.";
2021 });
2022 return false;
2023 }
2024 return true;
2025}
2026
2027void LoopInterchangeTransform::removeChildLoop(Loop *OuterLoop,
2028 Loop *InnerLoop) {
2029 for (Loop *L : *OuterLoop)
2030 if (L == InnerLoop) {
2031 OuterLoop->removeChildLoop(Child: L);
2032 return;
2033 }
2034 llvm_unreachable("Couldn't find loop");
2035}
2036
2037/// Update LoopInfo, after interchanging. NewInner and NewOuter refer to the
2038/// new inner and outer loop after interchanging: NewInner is the original
2039/// outer loop and NewOuter is the original inner loop.
2040///
2041/// Before interchanging, we have the following structure
2042/// Outer preheader
2043// Outer header
2044// Inner preheader
2045// Inner header
2046// Inner body
2047// Inner latch
2048// outer bbs
2049// Outer latch
2050//
2051// After interchanging:
2052// Inner preheader
2053// Inner header
2054// Outer preheader
2055// Outer header
2056// Inner body
2057// outer bbs
2058// Outer latch
2059// Inner latch
2060void LoopInterchangeTransform::restructureLoops(
2061 Loop *NewInner, Loop *NewOuter, BasicBlock *OrigInnerPreHeader,
2062 BasicBlock *OrigOuterPreHeader) {
2063 Loop *OuterLoopParent = OuterLoop->getParentLoop();
2064 // The original inner loop preheader moves from the new inner loop to
2065 // the parent loop, if there is one.
2066 NewInner->removeBlockFromLoop(BB: OrigInnerPreHeader);
2067 LI->changeLoopFor(BB: OrigInnerPreHeader, L: OuterLoopParent);
2068
2069 // Switch the loop levels.
2070 if (OuterLoopParent) {
2071 // Remove the loop from its parent loop.
2072 removeChildLoop(OuterLoop: OuterLoopParent, InnerLoop: NewInner);
2073 removeChildLoop(OuterLoop: NewInner, InnerLoop: NewOuter);
2074 OuterLoopParent->addChildLoop(NewChild: NewOuter);
2075 } else {
2076 removeChildLoop(OuterLoop: NewInner, InnerLoop: NewOuter);
2077 LI->changeTopLevelLoop(OldLoop: NewInner, NewLoop: NewOuter);
2078 }
2079 while (!NewOuter->isInnermost())
2080 NewInner->addChildLoop(NewChild: NewOuter->removeChildLoop(I: NewOuter->begin()));
2081 NewOuter->addChildLoop(NewChild: NewInner);
2082
2083 // BBs from the original inner loop.
2084 SmallVector<BasicBlock *, 8> OrigInnerBBs(NewOuter->blocks());
2085
2086 // Add BBs from the original outer loop to the original inner loop (excluding
2087 // BBs already in inner loop)
2088 for (BasicBlock *BB : NewInner->blocks())
2089 if (LI->getLoopFor(BB) == NewInner)
2090 NewOuter->addBlockEntry(BB);
2091
2092 // Now remove inner loop header and latch from the new inner loop and move
2093 // other BBs (the loop body) to the new inner loop.
2094 BasicBlock *OuterHeader = NewOuter->getHeader();
2095 BasicBlock *OuterLatch = NewOuter->getLoopLatch();
2096 for (BasicBlock *BB : OrigInnerBBs) {
2097 // Nothing will change for BBs in child loops.
2098 if (LI->getLoopFor(BB) != NewOuter)
2099 continue;
2100 // Remove the new outer loop header and latch from the new inner loop.
2101 if (BB == OuterHeader || BB == OuterLatch)
2102 NewInner->removeBlockFromLoop(BB);
2103 else
2104 LI->changeLoopFor(BB, L: NewInner);
2105 }
2106
2107 // The preheader of the original outer loop becomes part of the new
2108 // outer loop.
2109 NewOuter->addBlockEntry(BB: OrigOuterPreHeader);
2110 LI->changeLoopFor(BB: OrigOuterPreHeader, L: NewOuter);
2111
2112 // Tell SE that we move the loops around.
2113 SE->forgetLoop(L: NewOuter);
2114}
2115
2116/// User can write, or optimizers can generate the reduction for inner loop.
2117/// To make the interchange valid, apply Reduction2Mem by moving the
2118/// initializer and store instructions into the inner loop. So far we only
2119/// handle cases where the reduction variable is initialized to a constant.
2120/// For example, below code:
2121///
2122/// loop:
2123/// re = phi<0.0, next>
2124/// next = re op ...
2125/// endloop
2126/// reduc_sum = phi<next> // lcssa phi
2127/// MEM_REF[idx] = reduc_sum // LcssaStore
2128///
2129/// is transformed into:
2130///
2131/// loop:
2132/// tmp = MEM_REF[idx];
2133/// new_var = !first_iteration ? tmp : 0.0;
2134/// next = new_var op ...
2135/// MEM_REF[idx] = next; // after moving
2136/// endloop
2137///
2138/// In this way the initial const is used in the first iteration of loop.
2139void LoopInterchangeTransform::reduction2Memory() {
2140 ArrayRef<LoopInterchangeLegality::InnerReduction> InnerReductions =
2141 LIL.getInnerReductions();
2142
2143 assert(InnerReductions.size() == 1 &&
2144 "So far we only support at most one reduction.");
2145
2146 LoopInterchangeLegality::InnerReduction SR = InnerReductions[0];
2147 BasicBlock *InnerLoopHeader = InnerLoop->getHeader();
2148 IRBuilder<> Builder(InnerLoopHeader, InnerLoopHeader->getFirstNonPHIIt());
2149
2150 // Check if it's the first iteration.
2151 LLVMContext &Context = InnerLoopHeader->getContext();
2152 PHINode *FirstIter =
2153 Builder.CreatePHI(Ty: Type::getInt1Ty(C&: Context), NumReservedValues: 2, Name: "first.iter");
2154 FirstIter->addIncoming(V: ConstantInt::get(Ty: Type::getInt1Ty(C&: Context), V: 1),
2155 BB: InnerLoop->getLoopPreheader());
2156 FirstIter->addIncoming(V: ConstantInt::get(Ty: Type::getInt1Ty(C&: Context), V: 0),
2157 BB: InnerLoop->getLoopLatch());
2158 assert(FirstIter->isComplete() && "The FirstIter PHI node is not complete.");
2159
2160 // When the reduction is initialized from a constant value, we need to add
2161 // a stmt loading from the memory object to target basic block in inner
2162 // loop.
2163 Instruction *LoadMem = Builder.CreateLoad(Ty: SR.ElemTy, Ptr: SR.MemRef);
2164
2165 // Init new_var to MEM_REF or CONST depending on if it is the first iteration.
2166 Value *NewVar = Builder.CreateSelect(C: FirstIter, True: SR.Init, False: LoadMem, Name: "new.var");
2167
2168 // Replace all uses of the reduction variable with a new variable.
2169 SR.Reduction->replaceAllUsesWith(V: NewVar);
2170
2171 // Move store instruction into inner loop, just after reduction next's
2172 // definition.
2173 SR.LcssaStore->setOperand(i_nocapture: 0, Val_nocapture: SR.Next);
2174 SR.LcssaStore->moveAfter(MovePos: dyn_cast<Instruction>(Val: SR.Next));
2175}
2176
2177void LoopInterchangeTransform::transform(
2178 ArrayRef<Instruction *> DropNoWrapInsts,
2179 ArrayRef<Instruction *> DropNoInfInsts) {
2180
2181 ArrayRef<LoopInterchangeLegality::InnerReduction> InnerReductions =
2182 LIL.getInnerReductions();
2183 if (InnerReductions.size() == 1)
2184 reduction2Memory();
2185
2186 LLVM_DEBUG(dbgs() << "Splitting the inner loop latch\n");
2187 auto &InductionPHIs = LIL.getInnerLoopInductions();
2188 assert(!InductionPHIs.empty() &&
2189 "Expected at least one induction variable in the inner loop");
2190
2191 SmallVector<Instruction *, 8> InnerIndexVarList;
2192 for (PHINode *CurInductionPHI : InductionPHIs) {
2193 Instruction *IncomingValue = dyn_cast<Instruction>(
2194 Val: CurInductionPHI->getIncomingValueForBlock(BB: InnerLoop->getLoopLatch()));
2195 assert(IncomingValue &&
2196 "Incoming value from loop latch isn't an instruction");
2197 if (is_contained(Range: InductionPHIs, Element: IncomingValue))
2198 continue;
2199 InnerIndexVarList.push_back(Elt: IncomingValue);
2200 }
2201
2202 // Create a new latch block for the inner loop. We split at the
2203 // current latch's terminator and then move the condition and all
2204 // operands that are not either loop-invariant or the induction PHI into the
2205 // new latch block.
2206 BasicBlock *NewLatch =
2207 SplitBlock(Old: InnerLoop->getLoopLatch(),
2208 SplitPt: InnerLoop->getLoopLatch()->getTerminator(), DT, LI);
2209
2210 // Keep these seeds and the operand filter aligned with
2211 // findFreezeInInnerLatchCloneSet.
2212 SmallSetVector<Instruction *, 4> WorkList;
2213 unsigned i = 0;
2214 auto MoveInstructions = [&i, &WorkList, this, &InductionPHIs, NewLatch]() {
2215 for (; i < WorkList.size(); i++) {
2216 // PHI nodes cannot be cloned and moved here; the legality check
2217 // (areInnerLoopLatchPHIsSupported) ensures none reach the worklist.
2218 assert(!isa<PHINode>(WorkList[i]) &&
2219 "MoveInstructions does not support PHI nodes");
2220 // Duplicate instruction and move it to the new latch. Update uses that
2221 // have been moved.
2222 Instruction *NewI = WorkList[i]->clone();
2223 NewI->insertBefore(InsertPos: NewLatch->getFirstNonPHIIt());
2224 assert(!NewI->mayHaveSideEffects() &&
2225 "Moving instructions with side-effects may change behavior of "
2226 "the loop nest!");
2227 for (Use &U : llvm::make_early_inc_range(Range: WorkList[i]->uses())) {
2228 Instruction *UserI = cast<Instruction>(Val: U.getUser());
2229 if (!InnerLoop->contains(BB: UserI->getParent()) ||
2230 UserI->getParent() == NewLatch ||
2231 llvm::is_contained(Range: InductionPHIs, Element: UserI))
2232 U.set(NewI);
2233 }
2234 // Add operands of moved instruction to the worklist, except if they are
2235 // outside the inner loop or are the induction PHI.
2236 for (Value *Op : WorkList[i]->operands()) {
2237 Instruction *OpI = dyn_cast<Instruction>(Val: Op);
2238 if (!OpI || this->LI->getLoopFor(BB: OpI->getParent()) != this->InnerLoop ||
2239 llvm::is_contained(Range: InductionPHIs, Element: OpI))
2240 continue;
2241 WorkList.insert(X: OpI);
2242 }
2243 }
2244 };
2245
2246 // FIXME: Should we interchange when we have a constant condition?
2247 Instruction *CondI = dyn_cast<Instruction>(
2248 Val: cast<CondBrInst>(Val: InnerLoop->getLoopLatch()->getTerminator())
2249 ->getCondition());
2250 if (CondI)
2251 WorkList.insert(X: CondI);
2252 MoveInstructions();
2253 for (Instruction *InnerIndexVar : InnerIndexVarList)
2254 WorkList.insert(X: cast<Instruction>(Val: InnerIndexVar));
2255 MoveInstructions();
2256
2257 // Split the inner header so that it has a unique successor.
2258 BasicBlock *InnerLoopHeader = InnerLoop->getHeader();
2259 SplitBlock(Old: InnerLoopHeader, SplitPt: InnerLoopHeader->getFirstNonPHIIt(), DT, LI);
2260 LLVM_DEBUG(dbgs() << "splitting InnerLoopHeader done\n");
2261
2262 // Instructions in the original inner loop preheader may depend on values
2263 // defined in the outer loop header. Move them there, because the original
2264 // inner loop preheader will become the entry into the interchanged loop nest.
2265 // Currently we move all instructions and rely on LICM to move invariant
2266 // instructions outside the loop nest.
2267 BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
2268 BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
2269
2270 if (InnerLoopPreHeader != OuterLoopHeader) {
2271 // Eliminate PHIs in the inner-loop preheader.
2272 for (PHINode &P : make_early_inc_range(Range: InnerLoopPreHeader->phis())) {
2273 assert(all_equal(P.incoming_values()) &&
2274 "Expected equivalent incoming values in inner loop preheader");
2275 P.replaceAllUsesWith(V: P.getIncomingValue(i: 0));
2276 P.eraseFromParent();
2277 }
2278 for (Instruction &I :
2279 make_early_inc_range(Range: make_range(x: InnerLoopPreHeader->begin(),
2280 y: std::prev(x: InnerLoopPreHeader->end()))))
2281 I.moveBeforePreserving(MovePos: OuterLoopHeader->getTerminator()->getIterator());
2282 }
2283
2284 adjustLoopLinks();
2285
2286 // Finally, drop the nsw/nuw/ninf flags from the instructions for reduction
2287 // calculations.
2288 for (Instruction *Reduction : DropNoWrapInsts) {
2289 Reduction->setHasNoSignedWrap(false);
2290 Reduction->setHasNoUnsignedWrap(false);
2291 }
2292 for (Instruction *I : DropNoInfInsts)
2293 I->setHasNoInfs(false);
2294}
2295
2296/// \brief Move all instructions except the terminator from FromBB right before
2297/// InsertBefore
2298static void moveBBContents(BasicBlock *FromBB, Instruction *InsertBefore) {
2299 BasicBlock *ToBB = InsertBefore->getParent();
2300
2301 ToBB->splice(ToIt: InsertBefore->getIterator(), FromBB, FromBeginIt: FromBB->begin(),
2302 FromEndIt: FromBB->getTerminator()->getIterator());
2303}
2304
2305/// Swap instructions between \p BB1 and \p BB2 but keep terminators intact.
2306static void swapBBContents(BasicBlock *BB1, BasicBlock *BB2) {
2307 // Save all non-terminator instructions of BB1 into TempInstrs and unlink them
2308 // from BB1 afterwards.
2309 auto Iter = map_range(C&: *BB1, F: [](Instruction &I) { return &I; });
2310 SmallVector<Instruction *, 4> TempInstrs(Iter.begin(), std::prev(x: Iter.end()));
2311 for (Instruction *I : TempInstrs)
2312 I->removeFromParent();
2313
2314 // Move instructions from BB2 to BB1.
2315 moveBBContents(FromBB: BB2, InsertBefore: BB1->getTerminator());
2316
2317 // Move instructions from TempInstrs to BB2.
2318 for (Instruction *I : TempInstrs)
2319 I->insertBefore(InsertPos: BB2->getTerminator()->getIterator());
2320}
2321
2322// Update BI to jump to NewBB instead of OldBB. Records updates to the
2323// dominator tree in DTUpdates. If \p MustUpdateOnce is true, assert that
2324// \p OldBB is exactly once in BI's successor list.
2325static void updateSuccessor(Instruction *Term, BasicBlock *OldBB,
2326 BasicBlock *NewBB,
2327 std::vector<DominatorTree::UpdateType> &DTUpdates,
2328 bool MustUpdateOnce = true) {
2329 assert((!MustUpdateOnce || llvm::count(successors(Term), OldBB) == 1) &&
2330 "BI must jump to OldBB exactly once.");
2331 bool Changed = false;
2332 for (Use &Op : Term->operands())
2333 if (Op == OldBB) {
2334 Op.set(NewBB);
2335 Changed = true;
2336 }
2337
2338 if (Changed) {
2339 DTUpdates.push_back(
2340 x: {DominatorTree::UpdateKind::Insert, Term->getParent(), NewBB});
2341 DTUpdates.push_back(
2342 x: {DominatorTree::UpdateKind::Delete, Term->getParent(), OldBB});
2343 }
2344 assert(Changed && "Expected a successor to be updated");
2345}
2346
2347// Move Lcssa PHIs to the right place.
2348static void moveLCSSAPhis(BasicBlock *InnerExit, BasicBlock *InnerHeader,
2349 BasicBlock *InnerLatch, BasicBlock *OuterHeader,
2350 BasicBlock *OuterLatch, BasicBlock *OuterExit,
2351 Loop *InnerLoop, LoopInfo *LI) {
2352
2353 // Deal with LCSSA PHI nodes in the exit block of the inner loop, that are
2354 // defined either in the header or latch. Those blocks will become header and
2355 // latch of the new outer loop, and the only possible users can PHI nodes
2356 // in the exit block of the loop nest or the outer loop header (reduction
2357 // PHIs, in that case, the incoming value must be defined in the inner loop
2358 // header). We can just substitute the user with the incoming value and remove
2359 // the PHI.
2360 for (PHINode &P : make_early_inc_range(Range: InnerExit->phis())) {
2361 assert(P.getNumIncomingValues() == 1 &&
2362 "Only loops with a single exit are supported!");
2363
2364 Value *IncomingValue = P.getIncomingValueForBlock(BB: InnerLatch);
2365 auto *IncI = dyn_cast<Instruction>(Val: IncomingValue);
2366 if (!IncI) {
2367 // If the incoming value is not an instruction, it must be loop invariant.
2368 // In that case, we can just replace the PHI with the incoming value and
2369 // remove the PHI.
2370 assert(InnerLoop->isLoopInvariant(IncomingValue) &&
2371 "Expected non-instruction incoming value to be loop invariant");
2372 P.replaceAllUsesWith(V: IncomingValue);
2373 P.eraseFromParent();
2374 continue;
2375 }
2376
2377 // In case of multi-level nested loops, follow LCSSA to find the incoming
2378 // value defined from the innermost loop.
2379 auto *IncIInnerMost = dyn_cast<Instruction>(Val: followLCSSA(SV: IncI));
2380 // Skip phis when:
2381 // - they are not an instruction, e.g. incoming values are constants.
2382 // - Incomming values from the inner loop body, excluding the header and
2383 // latch.
2384 if (!IncIInnerMost || (IncIInnerMost->getParent() != InnerLatch &&
2385 IncIInnerMost->getParent() != InnerHeader))
2386 continue;
2387
2388 assert(all_of(P.users(),
2389 [OuterHeader, OuterExit, IncI, InnerHeader](User *U) {
2390 return (cast<PHINode>(U)->getParent() == OuterHeader &&
2391 IncI->getParent() == InnerHeader) ||
2392 cast<PHINode>(U)->getParent() == OuterExit;
2393 }) &&
2394 "Can only replace phis iff the uses are in the loop nest exit or "
2395 "the incoming value is defined in the inner header (it will "
2396 "dominate all loop blocks after interchanging)");
2397 P.replaceAllUsesWith(V: IncI);
2398 P.eraseFromParent();
2399 }
2400
2401 SmallVector<PHINode *, 8> LcssaInnerExit(
2402 llvm::make_pointer_range(Range: InnerExit->phis()));
2403
2404 SmallVector<PHINode *, 8> LcssaInnerLatch(
2405 llvm::make_pointer_range(Range: InnerLatch->phis()));
2406
2407 // Lcssa PHIs for values used outside the inner loop are in InnerExit.
2408 // If a PHI node has users outside of InnerExit, it has a use outside the
2409 // interchanged loop and we have to preserve it. We move these to
2410 // InnerLatch, which will become the new exit block for the innermost
2411 // loop after interchanging.
2412 for (PHINode *P : LcssaInnerExit)
2413 P->moveBefore(InsertPos: InnerLatch->getFirstNonPHIIt());
2414
2415 // If the inner loop latch contains LCSSA PHIs, those come from a child loop
2416 // and we have to move them to the new inner latch.
2417 for (PHINode *P : LcssaInnerLatch)
2418 P->moveBefore(InsertPos: InnerExit->getFirstNonPHIIt());
2419
2420 // Deal with LCSSA PHI nodes in the loop nest exit block. For PHIs that have
2421 // incoming values defined in the outer loop, we have to add a new PHI
2422 // in the inner loop latch, which became the exit block of the outer loop,
2423 // after interchanging.
2424 if (OuterExit) {
2425 for (PHINode &P : OuterExit->phis()) {
2426 if (P.getNumIncomingValues() != 1)
2427 continue;
2428 // Skip Phis with incoming values defined in the inner loop. Those should
2429 // already have been updated.
2430 auto I = dyn_cast<Instruction>(Val: P.getIncomingValue(i: 0));
2431 if (!I || LI->getLoopFor(BB: I->getParent()) == InnerLoop)
2432 continue;
2433
2434 PHINode *NewPhi = dyn_cast<PHINode>(Val: P.clone());
2435 NewPhi->setIncomingValue(i: 0, V: P.getIncomingValue(i: 0));
2436 NewPhi->setIncomingBlock(i: 0, BB: OuterLatch);
2437 // We might have incoming edges from other BBs, i.e., the original outer
2438 // header.
2439 for (auto *Pred : predecessors(BB: InnerLatch)) {
2440 if (Pred == OuterLatch)
2441 continue;
2442 NewPhi->addIncoming(V: P.getIncomingValue(i: 0), BB: Pred);
2443 }
2444 NewPhi->insertBefore(InsertPos: InnerLatch->getFirstNonPHIIt());
2445 P.setIncomingValue(i: 0, V: NewPhi);
2446 }
2447 }
2448
2449 // Now adjust the incoming blocks for the LCSSA PHIs.
2450 // For PHIs moved from Inner's exit block, we need to replace Inner's latch
2451 // with the new latch.
2452 InnerLatch->replacePhiUsesWith(Old: InnerLatch, New: OuterLatch);
2453}
2454
2455/// This deals with a corner case when a LCSSA phi node appears in a non-exit
2456/// block: the outer loop latch block does not need to be exit block of the
2457/// inner loop. Consider a loop that was in LCSSA form, but then some
2458/// transformation like loop-unswitch comes along and creates an empty block,
2459/// where BB5 in this example is the outer loop latch block:
2460///
2461/// BB4:
2462/// br label %BB5
2463/// BB5:
2464/// %old.cond.lcssa = phi i16 [ %cond, %BB4 ]
2465/// br outer.header
2466///
2467/// Interchange then brings it in LCSSA form again resulting in this chain of
2468/// single-input phi nodes:
2469///
2470/// BB4:
2471/// %new.cond.lcssa = phi i16 [ %cond, %BB3 ]
2472/// br label %BB5
2473/// BB5:
2474/// %old.cond.lcssa = phi i16 [ %new.cond.lcssa, %BB4 ]
2475///
2476/// The problem is that interchange can reoder blocks BB4 and BB5 placing the
2477/// use before the def if we don't check this. The solution is to simplify
2478/// lcssa phi nodes (remove) if they appear in non-exit blocks.
2479///
2480static void simplifyLCSSAPhis(Loop *OuterLoop, Loop *InnerLoop) {
2481 BasicBlock *InnerLoopExit = InnerLoop->getExitBlock();
2482 BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
2483
2484 // Do not modify lcssa phis where they actually belong, i.e. in exit blocks.
2485 if (OuterLoopLatch == InnerLoopExit)
2486 return;
2487
2488 // Collect and remove phis in non-exit blocks if they have 1 input.
2489 SmallVector<PHINode *, 8> Phis(
2490 llvm::make_pointer_range(Range: OuterLoopLatch->phis()));
2491 for (PHINode *Phi : Phis) {
2492 assert(Phi->getNumIncomingValues() == 1 && "Single input phi expected");
2493 LLVM_DEBUG(dbgs() << "Removing 1-input phi in non-exit block: " << *Phi
2494 << "\n");
2495 Phi->replaceAllUsesWith(V: Phi->getIncomingValue(i: 0));
2496 Phi->eraseFromParent();
2497 }
2498}
2499
2500void LoopInterchangeTransform::adjustLoopBranches() {
2501 LLVM_DEBUG(dbgs() << "adjustLoopBranches called\n");
2502 std::vector<DominatorTree::UpdateType> DTUpdates;
2503
2504 BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();
2505 BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
2506
2507 assert(OuterLoopPreHeader != OuterLoop->getHeader() &&
2508 InnerLoopPreHeader != InnerLoop->getHeader() && OuterLoopPreHeader &&
2509 InnerLoopPreHeader && "Guaranteed by loop-simplify form");
2510
2511 simplifyLCSSAPhis(OuterLoop, InnerLoop);
2512
2513 // Ensure that both preheaders do not contain PHI nodes and have single
2514 // predecessors. This allows us to move them easily. We use
2515 // InsertPreHeaderForLoop to create an 'extra' preheader, if the existing
2516 // preheaders do not satisfy those conditions.
2517 if (isa<PHINode>(Val: OuterLoopPreHeader->begin()) ||
2518 !OuterLoopPreHeader->getUniquePredecessor())
2519 OuterLoopPreHeader =
2520 InsertPreheaderForLoop(L: OuterLoop, DT, LI, MSSAU: nullptr, PreserveLCSSA: true);
2521 if (InnerLoopPreHeader == OuterLoop->getHeader())
2522 InnerLoopPreHeader =
2523 InsertPreheaderForLoop(L: InnerLoop, DT, LI, MSSAU: nullptr, PreserveLCSSA: true);
2524
2525 // Adjust the loop preheader
2526 BasicBlock *InnerLoopHeader = InnerLoop->getHeader();
2527 BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
2528 BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
2529 BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
2530 BasicBlock *OuterLoopPredecessor = OuterLoopPreHeader->getUniquePredecessor();
2531 BasicBlock *InnerLoopLatchPredecessor =
2532 InnerLoopLatch->getUniquePredecessor();
2533 BasicBlock *InnerLoopLatchSuccessor;
2534 BasicBlock *OuterLoopLatchSuccessor;
2535
2536 CondBrInst *OuterLoopLatchBI =
2537 dyn_cast<CondBrInst>(Val: OuterLoopLatch->getTerminator());
2538 CondBrInst *InnerLoopLatchBI =
2539 dyn_cast<CondBrInst>(Val: InnerLoopLatch->getTerminator());
2540 Instruction *OuterLoopHeaderBI = OuterLoopHeader->getTerminator();
2541 Instruction *InnerLoopHeaderBI = InnerLoopHeader->getTerminator();
2542
2543 assert(OuterLoopPredecessor && InnerLoopLatchPredecessor &&
2544 "Failed to find a unique predecessor");
2545 assert(OuterLoopLatchBI && InnerLoopLatchBI &&
2546 "Failed to find a conditional branch");
2547
2548 Instruction *InnerLoopLatchPredecessorBI =
2549 InnerLoopLatchPredecessor->getTerminator();
2550 Instruction *OuterLoopPredecessorBI = OuterLoopPredecessor->getTerminator();
2551
2552 BasicBlock *InnerLoopHeaderSuccessor = InnerLoopHeader->getUniqueSuccessor();
2553 assert(InnerLoopHeaderSuccessor &&
2554 "Failed to find a unique successor for the inner loop header");
2555
2556 // Adjust Loop Preheader and headers.
2557 // The branches in the outer loop predecessor and the outer loop header can
2558 // be unconditional branches or conditional branches with duplicates. Consider
2559 // this when updating the successors.
2560 updateSuccessor(Term: OuterLoopPredecessorBI, OldBB: OuterLoopPreHeader,
2561 NewBB: InnerLoopPreHeader, DTUpdates, /*MustUpdateOnce=*/false);
2562 // The outer loop header might or might not branch to the outer latch.
2563 // We are guaranteed to branch to the inner loop preheader.
2564 if (llvm::is_contained(Range: successors(I: OuterLoopHeaderBI), Element: OuterLoopLatch)) {
2565 // In this case the outerLoopHeader should branch to the InnerLoopLatch.
2566 updateSuccessor(Term: OuterLoopHeaderBI, OldBB: OuterLoopLatch, NewBB: InnerLoopLatch,
2567 DTUpdates,
2568 /*MustUpdateOnce=*/false);
2569 }
2570 updateSuccessor(Term: OuterLoopHeaderBI, OldBB: InnerLoopPreHeader,
2571 NewBB: InnerLoopHeaderSuccessor, DTUpdates,
2572 /*MustUpdateOnce=*/false);
2573
2574 // Adjust reduction PHI's now that the incoming block has changed.
2575 InnerLoopHeaderSuccessor->replacePhiUsesWith(Old: InnerLoopHeader,
2576 New: OuterLoopHeader);
2577
2578 updateSuccessor(Term: InnerLoopHeaderBI, OldBB: InnerLoopHeaderSuccessor,
2579 NewBB: OuterLoopPreHeader, DTUpdates);
2580
2581 // -------------Adjust loop latches-----------
2582 if (InnerLoopLatchBI->getSuccessor(i: 0) == InnerLoopHeader)
2583 InnerLoopLatchSuccessor = InnerLoopLatchBI->getSuccessor(i: 1);
2584 else
2585 InnerLoopLatchSuccessor = InnerLoopLatchBI->getSuccessor(i: 0);
2586
2587 updateSuccessor(Term: InnerLoopLatchPredecessorBI, OldBB: InnerLoopLatch,
2588 NewBB: InnerLoopLatchSuccessor, DTUpdates);
2589
2590 if (OuterLoopLatchBI->getSuccessor(i: 0) == OuterLoopHeader)
2591 OuterLoopLatchSuccessor = OuterLoopLatchBI->getSuccessor(i: 1);
2592 else
2593 OuterLoopLatchSuccessor = OuterLoopLatchBI->getSuccessor(i: 0);
2594
2595 updateSuccessor(Term: InnerLoopLatchBI, OldBB: InnerLoopLatchSuccessor,
2596 NewBB: OuterLoopLatchSuccessor, DTUpdates);
2597 updateSuccessor(Term: OuterLoopLatchBI, OldBB: OuterLoopLatchSuccessor, NewBB: InnerLoopLatch,
2598 DTUpdates);
2599
2600 DT->applyUpdates(Updates: DTUpdates);
2601 restructureLoops(NewInner: OuterLoop, NewOuter: InnerLoop, OrigInnerPreHeader: InnerLoopPreHeader,
2602 OrigOuterPreHeader: OuterLoopPreHeader);
2603
2604 moveLCSSAPhis(InnerExit: InnerLoopLatchSuccessor, InnerHeader: InnerLoopHeader, InnerLatch: InnerLoopLatch,
2605 OuterHeader: OuterLoopHeader, OuterLatch: OuterLoopLatch, OuterExit: InnerLoop->getExitBlock(),
2606 InnerLoop, LI);
2607 // For PHIs in the exit block of the outer loop, outer's latch has been
2608 // replaced by Inners'.
2609 OuterLoopLatchSuccessor->replacePhiUsesWith(Old: OuterLoopLatch, New: InnerLoopLatch);
2610
2611 auto &OuterInnerReductions = LIL.getOuterInnerReductions();
2612 // Now update the reduction PHIs in the inner and outer loop headers.
2613 SmallVector<PHINode *, 4> InnerLoopPHIs, OuterLoopPHIs;
2614 for (PHINode &PHI : InnerLoopHeader->phis())
2615 if (OuterInnerReductions.contains(Ptr: &PHI))
2616 InnerLoopPHIs.push_back(Elt: &PHI);
2617
2618 for (PHINode &PHI : OuterLoopHeader->phis())
2619 if (OuterInnerReductions.contains(Ptr: &PHI))
2620 OuterLoopPHIs.push_back(Elt: &PHI);
2621
2622 // Now move the remaining reduction PHIs from outer to inner loop header and
2623 // vice versa. The PHI nodes must be part of a reduction across the inner and
2624 // outer loop and all the remains to do is and updating the incoming blocks.
2625 for (PHINode *PHI : OuterLoopPHIs) {
2626 LLVM_DEBUG(dbgs() << "Outer loop reduction PHIs:\n"; PHI->dump(););
2627 PHI->moveBefore(InsertPos: InnerLoopHeader->getFirstNonPHIIt());
2628 assert(OuterInnerReductions.count(PHI) && "Expected a reduction PHI node");
2629 }
2630 for (PHINode *PHI : InnerLoopPHIs) {
2631 LLVM_DEBUG(dbgs() << "Inner loop reduction PHIs:\n"; PHI->dump(););
2632 PHI->moveBefore(InsertPos: OuterLoopHeader->getFirstNonPHIIt());
2633 assert(OuterInnerReductions.count(PHI) && "Expected a reduction PHI node");
2634 }
2635
2636 // Update the incoming blocks for moved PHI nodes.
2637 OuterLoopHeader->replacePhiUsesWith(Old: InnerLoopPreHeader, New: OuterLoopPreHeader);
2638 OuterLoopHeader->replacePhiUsesWith(Old: InnerLoopLatch, New: OuterLoopLatch);
2639 InnerLoopHeader->replacePhiUsesWith(Old: OuterLoopPreHeader, New: InnerLoopPreHeader);
2640 InnerLoopHeader->replacePhiUsesWith(Old: OuterLoopLatch, New: InnerLoopLatch);
2641
2642 // Values defined in the outer loop header could be used in the inner loop
2643 // latch. In that case, we need to create LCSSA phis for them, because after
2644 // interchanging they will be defined in the new inner loop and used in the
2645 // new outer loop.
2646 SmallVector<Instruction *, 4> MayNeedLCSSAPhis;
2647 for (Instruction &I :
2648 make_range(x: OuterLoopHeader->begin(), y: std::prev(x: OuterLoopHeader->end())))
2649 MayNeedLCSSAPhis.push_back(Elt: &I);
2650 formLCSSAForInstructions(Worklist&: MayNeedLCSSAPhis, DT: *DT, LI: *LI, SE);
2651}
2652
2653void LoopInterchangeTransform::adjustLoopLinks() {
2654 // Adjust all branches in the inner and outer loop.
2655 adjustLoopBranches();
2656
2657 // We have interchanged the preheaders so we need to interchange the data in
2658 // the preheaders as well. This is because the content of the inner
2659 // preheader was previously executed inside the outer loop.
2660 BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();
2661 BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
2662 swapBBContents(BB1: OuterLoopPreHeader, BB2: InnerLoopPreHeader);
2663}
2664
2665PreservedAnalyses LoopInterchangePass::run(LoopNest &LN,
2666 LoopAnalysisManager &AM,
2667 LoopStandardAnalysisResults &AR,
2668 LPMUpdater &U) {
2669 Function &F = *LN.getParent();
2670 SmallVector<Loop *, 8> LoopList(LN.getLoops());
2671
2672 OptimizationRemarkEmitter ORE(&F);
2673
2674 // Ensure minimum depth of the loop nest to do the interchange.
2675 if (!hasSupportedLoopDepth(LoopList, ORE))
2676 return PreservedAnalyses::all();
2677 // Ensure computable loop nest.
2678 if (!isComputableLoopNest(SE: &AR.SE, LoopList)) {
2679 LLVM_DEBUG(dbgs() << "Not valid loop candidate for interchange\n");
2680 return PreservedAnalyses::all();
2681 }
2682
2683 ORE.emit(RemarkBuilder: [&]() {
2684 return OptimizationRemarkAnalysis(DEBUG_TYPE, "Dependence",
2685 LN.getOutermostLoop().getStartLoc(),
2686 LN.getOutermostLoop().getHeader())
2687 << "Computed dependence info, invoking the transform.";
2688 });
2689
2690 DependenceInfo DI(&F, &AR.AA, &AR.SE, &AR.LI);
2691 if (!LoopInterchange(&AR.SE, &AR.LI, &DI, &AR.DT, &AR, &ORE).run(LN))
2692 return PreservedAnalyses::all();
2693 U.markLoopNestChanged(Changed: true);
2694 return getLoopPassPreservedAnalyses();
2695}
2696