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