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