1//===- LoopInterchange.cpp - Loop interchange pass-------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This Pass handles loop interchange transform.
10// This pass interchanges loops to provide a more cache-friendly memory access
11// patterns.
12//
13//===----------------------------------------------------------------------===//
14
15#include "llvm/Transforms/Scalar/LoopInterchange.h"
16#include "llvm/ADT/STLExtras.h"
17#include "llvm/ADT/SmallVector.h"
18#include "llvm/ADT/Statistic.h"
19#include "llvm/ADT/StringRef.h"
20#include "llvm/Analysis/DependenceAnalysis.h"
21#include "llvm/Analysis/LoopCacheAnalysis.h"
22#include "llvm/Analysis/LoopInfo.h"
23#include "llvm/Analysis/LoopNestAnalysis.h"
24#include "llvm/Analysis/LoopPass.h"
25#include "llvm/Analysis/OptimizationRemarkEmitter.h"
26#include "llvm/Analysis/ScalarEvolution.h"
27#include "llvm/Analysis/ScalarEvolutionExpressions.h"
28#include "llvm/IR/BasicBlock.h"
29#include "llvm/IR/Constants.h"
30#include "llvm/IR/DiagnosticInfo.h"
31#include "llvm/IR/Dominators.h"
32#include "llvm/IR/Function.h"
33#include "llvm/IR/IRBuilder.h"
34#include "llvm/IR/InstrTypes.h"
35#include "llvm/IR/Instruction.h"
36#include "llvm/IR/Instructions.h"
37#include "llvm/IR/User.h"
38#include "llvm/IR/Value.h"
39#include "llvm/InitializePasses.h"
40#include "llvm/Pass.h"
41#include "llvm/Support/Casting.h"
42#include "llvm/Support/CommandLine.h"
43#include "llvm/Support/Debug.h"
44#include "llvm/Support/ErrorHandling.h"
45#include "llvm/Support/raw_ostream.h"
46#include "llvm/Transforms/Scalar.h"
47#include "llvm/Transforms/Scalar/LoopPassManager.h"
48#include "llvm/Transforms/Utils/BasicBlockUtils.h"
49#include "llvm/Transforms/Utils/LoopUtils.h"
50#include <cassert>
51#include <utility>
52#include <vector>
53
54using namespace llvm;
55
56#define DEBUG_TYPE "loop-interchange"
57
58STATISTIC(LoopsInterchanged, "Number of loops interchanged");
59
60static cl::opt<int> LoopInterchangeCostThreshold(
61    "loop-interchange-threshold", cl::init(0), cl::Hidden,
62    cl::desc("Interchange if you gain more than this number"));
63
64namespace {
65
66using LoopVector = SmallVector<Loop *, 8>;
67
68// TODO: Check if we can use a sparse matrix here.
69using CharMatrix = std::vector<std::vector<char>>;
70
71} // end anonymous namespace
72
73// Maximum number of dependencies that can be handled in the dependency matrix.
74static const unsigned MaxMemInstrCount = 100;
75
76// Maximum loop depth supported.
77static const unsigned MaxLoopNestDepth = 10;
78
79#ifdef DUMP_DEP_MATRICIES
80static void printDepMatrix(CharMatrix &DepMatrix) {
81  for (auto &Row : DepMatrix) {
82    for (auto D : Row)
83      LLVM_DEBUG(dbgs() << D << " ");
84    LLVM_DEBUG(dbgs() << "\n");
85  }
86}
87#endif
88
89static bool populateDependencyMatrix(CharMatrix &DepMatrix, unsigned Level,
90                                     Loop *L, DependenceInfo *DI,
91                                     ScalarEvolution *SE) {
92  using ValueVector = SmallVector<Value *, 16>;
93
94  ValueVector MemInstr;
95
96  // For each block.
97  for (BasicBlock *BB : L->blocks()) {
98    // Scan the BB and collect legal loads and stores.
99    for (Instruction &I : *BB) {
100      if (!isa<Instruction>(I))
101        return false;
102      if (auto *Ld = dyn_cast<LoadInst>(&I)) {
103        if (!Ld->isSimple())
104          return false;
105        MemInstr.push_back(&I);
106      } else if (auto *St = dyn_cast<StoreInst>(&I)) {
107        if (!St->isSimple())
108          return false;
109        MemInstr.push_back(&I);
110      }
111    }
112  }
113
114  LLVM_DEBUG(dbgs() << "Found " << MemInstr.size()
115                    << " Loads and Stores to analyze\n");
116
117  ValueVector::iterator I, IE, J, JE;
118
119  for (I = MemInstr.begin(), IE = MemInstr.end(); I != IE; ++I) {
120    for (J = I, JE = MemInstr.end(); J != JE; ++J) {
121      std::vector<char> Dep;
122      Instruction *Src = cast<Instruction>(*I);
123      Instruction *Dst = cast<Instruction>(*J);
124      // Ignore Input dependencies.
125      if (isa<LoadInst>(Src) && isa<LoadInst>(Dst))
126        continue;
127      // Track Output, Flow, and Anti dependencies.
128      if (auto D = DI->depends(Src, Dst, true)) {
129        assert(D->isOrdered() && "Expected an output, flow or anti dep.");
130        // If the direction vector is negative, normalize it to
131        // make it non-negative.
132        if (D->normalize(SE))
133          LLVM_DEBUG(dbgs() << "Negative dependence vector normalized.\n");
134        LLVM_DEBUG(StringRef DepType =
135                       D->isFlow() ? "flow" : D->isAnti() ? "anti" : "output";
136                   dbgs() << "Found " << DepType
137                          << " dependency between Src and Dst\n"
138                          << " Src:" << *Src << "\n Dst:" << *Dst << '\n');
139        unsigned Levels = D->getLevels();
140        char Direction;
141        for (unsigned II = 1; II <= Levels; ++II) {
142          if (D->isScalar(II)) {
143            Direction = 'S';
144            Dep.push_back(Direction);
145          } else {
146            unsigned Dir = D->getDirection(II);
147            if (Dir == Dependence::DVEntry::LT ||
148                Dir == Dependence::DVEntry::LE)
149              Direction = '<';
150            else if (Dir == Dependence::DVEntry::GT ||
151                     Dir == Dependence::DVEntry::GE)
152              Direction = '>';
153            else if (Dir == Dependence::DVEntry::EQ)
154              Direction = '=';
155            else
156              Direction = '*';
157            Dep.push_back(Direction);
158          }
159        }
160        while (Dep.size() != Level) {
161          Dep.push_back('I');
162        }
163
164        DepMatrix.push_back(Dep);
165        if (DepMatrix.size() > MaxMemInstrCount) {
166          LLVM_DEBUG(dbgs() << "Cannot handle more than " << MaxMemInstrCount
167                            << " dependencies inside loop\n");
168          return false;
169        }
170      }
171    }
172  }
173
174  return true;
175}
176
177// A loop is moved from index 'from' to an index 'to'. Update the Dependence
178// matrix by exchanging the two columns.
179static void interChangeDependencies(CharMatrix &DepMatrix, unsigned FromIndx,
180                                    unsigned ToIndx) {
181  for (unsigned I = 0, E = DepMatrix.size(); I < E; ++I)
182    std::swap(DepMatrix[I][ToIndx], DepMatrix[I][FromIndx]);
183}
184
185// After interchanging, check if the direction vector is valid.
186// [Theorem] A permutation of the loops in a perfect nest is legal if and only
187// if the direction matrix, after the same permutation is applied to its
188// columns, has no ">" direction as the leftmost non-"=" direction in any row.
189static bool isLexicographicallyPositive(std::vector<char> &DV) {
190  for (unsigned Level = 0; Level < DV.size(); ++Level) {
191    unsigned char Direction = DV[Level];
192    if (Direction == '<')
193      return true;
194    if (Direction == '>' || Direction == '*')
195      return false;
196  }
197  return true;
198}
199
200// Checks if it is legal to interchange 2 loops.
201static bool isLegalToInterChangeLoops(CharMatrix &DepMatrix,
202                                      unsigned InnerLoopId,
203                                      unsigned OuterLoopId) {
204  unsigned NumRows = DepMatrix.size();
205  std::vector<char> Cur;
206  // For each row check if it is valid to interchange.
207  for (unsigned Row = 0; Row < NumRows; ++Row) {
208    // Create temporary DepVector check its lexicographical order
209    // before and after swapping OuterLoop vs InnerLoop
210    Cur = DepMatrix[Row];
211    if (!isLexicographicallyPositive(Cur))
212      return false;
213    std::swap(Cur[InnerLoopId], Cur[OuterLoopId]);
214    if (!isLexicographicallyPositive(Cur))
215      return false;
216  }
217  return true;
218}
219
220static void populateWorklist(Loop &L, LoopVector &LoopList) {
221  LLVM_DEBUG(dbgs() << "Calling populateWorklist on Func: "
222                    << L.getHeader()->getParent()->getName() << " Loop: %"
223                    << L.getHeader()->getName() << '\n');
224  assert(LoopList.empty() && "LoopList should initially be empty!");
225  Loop *CurrentLoop = &L;
226  const std::vector<Loop *> *Vec = &CurrentLoop->getSubLoops();
227  while (!Vec->empty()) {
228    // The current loop has multiple subloops in it hence it is not tightly
229    // nested.
230    // Discard all loops above it added into Worklist.
231    if (Vec->size() != 1) {
232      LoopList = {};
233      return;
234    }
235
236    LoopList.push_back(CurrentLoop);
237    CurrentLoop = Vec->front();
238    Vec = &CurrentLoop->getSubLoops();
239  }
240  LoopList.push_back(CurrentLoop);
241}
242
243namespace {
244
245/// LoopInterchangeLegality checks if it is legal to interchange the loop.
246class LoopInterchangeLegality {
247public:
248  LoopInterchangeLegality(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
249                          OptimizationRemarkEmitter *ORE)
250      : OuterLoop(Outer), InnerLoop(Inner), SE(SE), ORE(ORE) {}
251
252  /// Check if the loops can be interchanged.
253  bool canInterchangeLoops(unsigned InnerLoopId, unsigned OuterLoopId,
254                           CharMatrix &DepMatrix);
255
256  /// Discover induction PHIs in the header of \p L. Induction
257  /// PHIs are added to \p Inductions.
258  bool findInductions(Loop *L, SmallVectorImpl<PHINode *> &Inductions);
259
260  /// Check if the loop structure is understood. We do not handle triangular
261  /// loops for now.
262  bool isLoopStructureUnderstood();
263
264  bool currentLimitations();
265
266  const SmallPtrSetImpl<PHINode *> &getOuterInnerReductions() const {
267    return OuterInnerReductions;
268  }
269
270  const SmallVectorImpl<PHINode *> &getInnerLoopInductions() const {
271    return InnerLoopInductions;
272  }
273
274private:
275  bool tightlyNested(Loop *Outer, Loop *Inner);
276  bool containsUnsafeInstructions(BasicBlock *BB);
277
278  /// Discover induction and reduction PHIs in the header of \p L. Induction
279  /// PHIs are added to \p Inductions, reductions are added to
280  /// OuterInnerReductions. When the outer loop is passed, the inner loop needs
281  /// to be passed as \p InnerLoop.
282  bool findInductionAndReductions(Loop *L,
283                                  SmallVector<PHINode *, 8> &Inductions,
284                                  Loop *InnerLoop);
285
286  Loop *OuterLoop;
287  Loop *InnerLoop;
288
289  ScalarEvolution *SE;
290
291  /// Interface to emit optimization remarks.
292  OptimizationRemarkEmitter *ORE;
293
294  /// Set of reduction PHIs taking part of a reduction across the inner and
295  /// outer loop.
296  SmallPtrSet<PHINode *, 4> OuterInnerReductions;
297
298  /// Set of inner loop induction PHIs
299  SmallVector<PHINode *, 8> InnerLoopInductions;
300};
301
302/// LoopInterchangeProfitability checks if it is profitable to interchange the
303/// loop.
304class LoopInterchangeProfitability {
305public:
306  LoopInterchangeProfitability(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
307                               OptimizationRemarkEmitter *ORE)
308      : OuterLoop(Outer), InnerLoop(Inner), SE(SE), ORE(ORE) {}
309
310  /// Check if the loop interchange is profitable.
311  bool isProfitable(const Loop *InnerLoop, const Loop *OuterLoop,
312                    unsigned InnerLoopId, unsigned OuterLoopId,
313                    CharMatrix &DepMatrix,
314                    const DenseMap<const Loop *, unsigned> &CostMap,
315                    std::unique_ptr<CacheCost> &CC);
316
317private:
318  int getInstrOrderCost();
319  std::optional<bool> isProfitablePerLoopCacheAnalysis(
320      const DenseMap<const Loop *, unsigned> &CostMap,
321      std::unique_ptr<CacheCost> &CC);
322  std::optional<bool> isProfitablePerInstrOrderCost();
323  std::optional<bool> isProfitableForVectorization(unsigned InnerLoopId,
324                                                   unsigned OuterLoopId,
325                                                   CharMatrix &DepMatrix);
326  Loop *OuterLoop;
327  Loop *InnerLoop;
328
329  /// Scev analysis.
330  ScalarEvolution *SE;
331
332  /// Interface to emit optimization remarks.
333  OptimizationRemarkEmitter *ORE;
334};
335
336/// LoopInterchangeTransform interchanges the loop.
337class LoopInterchangeTransform {
338public:
339  LoopInterchangeTransform(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
340                           LoopInfo *LI, DominatorTree *DT,
341                           const LoopInterchangeLegality &LIL)
342      : OuterLoop(Outer), InnerLoop(Inner), SE(SE), LI(LI), DT(DT), LIL(LIL) {}
343
344  /// Interchange OuterLoop and InnerLoop.
345  bool transform();
346  void restructureLoops(Loop *NewInner, Loop *NewOuter,
347                        BasicBlock *OrigInnerPreHeader,
348                        BasicBlock *OrigOuterPreHeader);
349  void removeChildLoop(Loop *OuterLoop, Loop *InnerLoop);
350
351private:
352  bool adjustLoopLinks();
353  bool adjustLoopBranches();
354
355  Loop *OuterLoop;
356  Loop *InnerLoop;
357
358  /// Scev analysis.
359  ScalarEvolution *SE;
360
361  LoopInfo *LI;
362  DominatorTree *DT;
363
364  const LoopInterchangeLegality &LIL;
365};
366
367struct LoopInterchange {
368  ScalarEvolution *SE = nullptr;
369  LoopInfo *LI = nullptr;
370  DependenceInfo *DI = nullptr;
371  DominatorTree *DT = nullptr;
372  std::unique_ptr<CacheCost> CC = nullptr;
373
374  /// Interface to emit optimization remarks.
375  OptimizationRemarkEmitter *ORE;
376
377  LoopInterchange(ScalarEvolution *SE, LoopInfo *LI, DependenceInfo *DI,
378                  DominatorTree *DT, std::unique_ptr<CacheCost> &CC,
379                  OptimizationRemarkEmitter *ORE)
380      : SE(SE), LI(LI), DI(DI), DT(DT), CC(std::move(CC)), ORE(ORE) {}
381
382  bool run(Loop *L) {
383    if (L->getParentLoop())
384      return false;
385    SmallVector<Loop *, 8> LoopList;
386    populateWorklist(*L, LoopList);
387    return processLoopList(LoopList);
388  }
389
390  bool run(LoopNest &LN) {
391    SmallVector<Loop *, 8> LoopList(LN.getLoops().begin(), LN.getLoops().end());
392    for (unsigned I = 1; I < LoopList.size(); ++I)
393      if (LoopList[I]->getParentLoop() != LoopList[I - 1])
394        return false;
395    return processLoopList(LoopList);
396  }
397
398  bool isComputableLoopNest(ArrayRef<Loop *> LoopList) {
399    for (Loop *L : LoopList) {
400      const SCEV *ExitCountOuter = SE->getBackedgeTakenCount(L);
401      if (isa<SCEVCouldNotCompute>(ExitCountOuter)) {
402        LLVM_DEBUG(dbgs() << "Couldn't compute backedge count\n");
403        return false;
404      }
405      if (L->getNumBackEdges() != 1) {
406        LLVM_DEBUG(dbgs() << "NumBackEdges is not equal to 1\n");
407        return false;
408      }
409      if (!L->getExitingBlock()) {
410        LLVM_DEBUG(dbgs() << "Loop doesn't have unique exit block\n");
411        return false;
412      }
413    }
414    return true;
415  }
416
417  unsigned selectLoopForInterchange(ArrayRef<Loop *> LoopList) {
418    // TODO: Add a better heuristic to select the loop to be interchanged based
419    // on the dependence matrix. Currently we select the innermost loop.
420    return LoopList.size() - 1;
421  }
422
423  bool processLoopList(SmallVectorImpl<Loop *> &LoopList) {
424    bool Changed = false;
425    unsigned LoopNestDepth = LoopList.size();
426    if (LoopNestDepth < 2) {
427      LLVM_DEBUG(dbgs() << "Loop doesn't contain minimum nesting level.\n");
428      return false;
429    }
430    if (LoopNestDepth > MaxLoopNestDepth) {
431      LLVM_DEBUG(dbgs() << "Cannot handle loops of depth greater than "
432                        << MaxLoopNestDepth << "\n");
433      return false;
434    }
435    if (!isComputableLoopNest(LoopList)) {
436      LLVM_DEBUG(dbgs() << "Not valid loop candidate for interchange\n");
437      return false;
438    }
439
440    LLVM_DEBUG(dbgs() << "Processing LoopList of size = " << LoopNestDepth
441                      << "\n");
442
443    CharMatrix DependencyMatrix;
444    Loop *OuterMostLoop = *(LoopList.begin());
445    if (!populateDependencyMatrix(DependencyMatrix, LoopNestDepth,
446                                  OuterMostLoop, DI, SE)) {
447      LLVM_DEBUG(dbgs() << "Populating dependency matrix failed\n");
448      return false;
449    }
450#ifdef DUMP_DEP_MATRICIES
451    LLVM_DEBUG(dbgs() << "Dependence before interchange\n");
452    printDepMatrix(DependencyMatrix);
453#endif
454
455    // Get the Outermost loop exit.
456    BasicBlock *LoopNestExit = OuterMostLoop->getExitBlock();
457    if (!LoopNestExit) {
458      LLVM_DEBUG(dbgs() << "OuterMostLoop needs an unique exit block");
459      return false;
460    }
461
462    unsigned SelecLoopId = selectLoopForInterchange(LoopList);
463    // Obtain the loop vector returned from loop cache analysis beforehand,
464    // and put each <Loop, index> pair into a map for constant time query
465    // later. Indices in loop vector reprsent the optimal order of the
466    // corresponding loop, e.g., given a loopnest with depth N, index 0
467    // indicates the loop should be placed as the outermost loop and index N
468    // indicates the loop should be placed as the innermost loop.
469    //
470    // For the old pass manager CacheCost would be null.
471    DenseMap<const Loop *, unsigned> CostMap;
472    if (CC != nullptr) {
473      const auto &LoopCosts = CC->getLoopCosts();
474      for (unsigned i = 0; i < LoopCosts.size(); i++) {
475        CostMap[LoopCosts[i].first] = i;
476      }
477    }
478    // We try to achieve the globally optimal memory access for the loopnest,
479    // and do interchange based on a bubble-sort fasion. We start from
480    // the innermost loop, move it outwards to the best possible position
481    // and repeat this process.
482    for (unsigned j = SelecLoopId; j > 0; j--) {
483      bool ChangedPerIter = false;
484      for (unsigned i = SelecLoopId; i > SelecLoopId - j; i--) {
485        bool Interchanged = processLoop(LoopList[i], LoopList[i - 1], i, i - 1,
486                                        DependencyMatrix, CostMap);
487        if (!Interchanged)
488          continue;
489        // Loops interchanged, update LoopList accordingly.
490        std::swap(LoopList[i - 1], LoopList[i]);
491        // Update the DependencyMatrix
492        interChangeDependencies(DependencyMatrix, i, i - 1);
493#ifdef DUMP_DEP_MATRICIES
494        LLVM_DEBUG(dbgs() << "Dependence after interchange\n");
495        printDepMatrix(DependencyMatrix);
496#endif
497        ChangedPerIter |= Interchanged;
498        Changed |= Interchanged;
499      }
500      // Early abort if there was no interchange during an entire round of
501      // moving loops outwards.
502      if (!ChangedPerIter)
503        break;
504    }
505    return Changed;
506  }
507
508  bool processLoop(Loop *InnerLoop, Loop *OuterLoop, unsigned InnerLoopId,
509                   unsigned OuterLoopId,
510                   std::vector<std::vector<char>> &DependencyMatrix,
511                   const DenseMap<const Loop *, unsigned> &CostMap) {
512    LLVM_DEBUG(dbgs() << "Processing InnerLoopId = " << InnerLoopId
513                      << " and OuterLoopId = " << OuterLoopId << "\n");
514    LoopInterchangeLegality LIL(OuterLoop, InnerLoop, SE, ORE);
515    if (!LIL.canInterchangeLoops(InnerLoopId, OuterLoopId, DependencyMatrix)) {
516      LLVM_DEBUG(dbgs() << "Not interchanging loops. Cannot prove legality.\n");
517      return false;
518    }
519    LLVM_DEBUG(dbgs() << "Loops are legal to interchange\n");
520    LoopInterchangeProfitability LIP(OuterLoop, InnerLoop, SE, ORE);
521    if (!LIP.isProfitable(InnerLoop, OuterLoop, InnerLoopId, OuterLoopId,
522                          DependencyMatrix, CostMap, CC)) {
523      LLVM_DEBUG(dbgs() << "Interchanging loops not profitable.\n");
524      return false;
525    }
526
527    ORE->emit([&]() {
528      return OptimizationRemark(DEBUG_TYPE, "Interchanged",
529                                InnerLoop->getStartLoc(),
530                                InnerLoop->getHeader())
531             << "Loop interchanged with enclosing loop.";
532    });
533
534    LoopInterchangeTransform LIT(OuterLoop, InnerLoop, SE, LI, DT, LIL);
535    LIT.transform();
536    LLVM_DEBUG(dbgs() << "Loops interchanged.\n");
537    LoopsInterchanged++;
538
539    llvm::formLCSSARecursively(*OuterLoop, *DT, LI, SE);
540    return true;
541  }
542};
543
544} // end anonymous namespace
545
546bool LoopInterchangeLegality::containsUnsafeInstructions(BasicBlock *BB) {
547  return any_of(*BB, [](const Instruction &I) {
548    return I.mayHaveSideEffects() || I.mayReadFromMemory();
549  });
550}
551
552bool LoopInterchangeLegality::tightlyNested(Loop *OuterLoop, Loop *InnerLoop) {
553  BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
554  BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
555  BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
556
557  LLVM_DEBUG(dbgs() << "Checking if loops are tightly nested\n");
558
559  // A perfectly nested loop will not have any branch in between the outer and
560  // inner block i.e. outer header will branch to either inner preheader and
561  // outerloop latch.
562  BranchInst *OuterLoopHeaderBI =
563      dyn_cast<BranchInst>(OuterLoopHeader->getTerminator());
564  if (!OuterLoopHeaderBI)
565    return false;
566
567  for (BasicBlock *Succ : successors(OuterLoopHeaderBI))
568    if (Succ != InnerLoopPreHeader && Succ != InnerLoop->getHeader() &&
569        Succ != OuterLoopLatch)
570      return false;
571
572  LLVM_DEBUG(dbgs() << "Checking instructions in Loop header and Loop latch\n");
573  // We do not have any basic block in between now make sure the outer header
574  // and outer loop latch doesn't contain any unsafe instructions.
575  if (containsUnsafeInstructions(OuterLoopHeader) ||
576      containsUnsafeInstructions(OuterLoopLatch))
577    return false;
578
579  // Also make sure the inner loop preheader does not contain any unsafe
580  // instructions. Note that all instructions in the preheader will be moved to
581  // the outer loop header when interchanging.
582  if (InnerLoopPreHeader != OuterLoopHeader &&
583      containsUnsafeInstructions(InnerLoopPreHeader))
584    return false;
585
586  BasicBlock *InnerLoopExit = InnerLoop->getExitBlock();
587  // Ensure the inner loop exit block flows to the outer loop latch possibly
588  // through empty blocks.
589  const BasicBlock &SuccInner =
590      LoopNest::skipEmptyBlockUntil(InnerLoopExit, OuterLoopLatch);
591  if (&SuccInner != OuterLoopLatch) {
592    LLVM_DEBUG(dbgs() << "Inner loop exit block " << *InnerLoopExit
593                      << " does not lead to the outer loop latch.\n";);
594    return false;
595  }
596  // The inner loop exit block does flow to the outer loop latch and not some
597  // other BBs, now make sure it contains safe instructions, since it will be
598  // moved into the (new) inner loop after interchange.
599  if (containsUnsafeInstructions(InnerLoopExit))
600    return false;
601
602  LLVM_DEBUG(dbgs() << "Loops are perfectly nested\n");
603  // We have a perfect loop nest.
604  return true;
605}
606
607bool LoopInterchangeLegality::isLoopStructureUnderstood() {
608  BasicBlock *InnerLoopPreheader = InnerLoop->getLoopPreheader();
609  for (PHINode *InnerInduction : InnerLoopInductions) {
610    unsigned Num = InnerInduction->getNumOperands();
611    for (unsigned i = 0; i < Num; ++i) {
612      Value *Val = InnerInduction->getOperand(i);
613      if (isa<Constant>(Val))
614        continue;
615      Instruction *I = dyn_cast<Instruction>(Val);
616      if (!I)
617        return false;
618      // TODO: Handle triangular loops.
619      // e.g. for(int i=0;i<N;i++)
620      //        for(int j=i;j<N;j++)
621      unsigned IncomBlockIndx = PHINode::getIncomingValueNumForOperand(i);
622      if (InnerInduction->getIncomingBlock(IncomBlockIndx) ==
623              InnerLoopPreheader &&
624          !OuterLoop->isLoopInvariant(I)) {
625        return false;
626      }
627    }
628  }
629
630  // TODO: Handle triangular loops of another form.
631  // e.g. for(int i=0;i<N;i++)
632  //        for(int j=0;j<i;j++)
633  // or,
634  //      for(int i=0;i<N;i++)
635  //        for(int j=0;j*i<N;j++)
636  BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
637  BranchInst *InnerLoopLatchBI =
638      dyn_cast<BranchInst>(InnerLoopLatch->getTerminator());
639  if (!InnerLoopLatchBI->isConditional())
640    return false;
641  if (CmpInst *InnerLoopCmp =
642          dyn_cast<CmpInst>(InnerLoopLatchBI->getCondition())) {
643    Value *Op0 = InnerLoopCmp->getOperand(0);
644    Value *Op1 = InnerLoopCmp->getOperand(1);
645
646    // LHS and RHS of the inner loop exit condition, e.g.,
647    // in "for(int j=0;j<i;j++)", LHS is j and RHS is i.
648    Value *Left = nullptr;
649    Value *Right = nullptr;
650
651    // Check if V only involves inner loop induction variable.
652    // Return true if V is InnerInduction, or a cast from
653    // InnerInduction, or a binary operator that involves
654    // InnerInduction and a constant.
655    std::function<bool(Value *)> IsPathToInnerIndVar;
656    IsPathToInnerIndVar = [this, &IsPathToInnerIndVar](const Value *V) -> bool {
657      if (llvm::is_contained(InnerLoopInductions, V))
658        return true;
659      if (isa<Constant>(V))
660        return true;
661      const Instruction *I = dyn_cast<Instruction>(V);
662      if (!I)
663        return false;
664      if (isa<CastInst>(I))
665        return IsPathToInnerIndVar(I->getOperand(0));
666      if (isa<BinaryOperator>(I))
667        return IsPathToInnerIndVar(I->getOperand(0)) &&
668               IsPathToInnerIndVar(I->getOperand(1));
669      return false;
670    };
671
672    // In case of multiple inner loop indvars, it is okay if LHS and RHS
673    // are both inner indvar related variables.
674    if (IsPathToInnerIndVar(Op0) && IsPathToInnerIndVar(Op1))
675      return true;
676
677    // Otherwise we check if the cmp instruction compares an inner indvar
678    // related variable (Left) with a outer loop invariant (Right).
679    if (IsPathToInnerIndVar(Op0) && !isa<Constant>(Op0)) {
680      Left = Op0;
681      Right = Op1;
682    } else if (IsPathToInnerIndVar(Op1) && !isa<Constant>(Op1)) {
683      Left = Op1;
684      Right = Op0;
685    }
686
687    if (Left == nullptr)
688      return false;
689
690    const SCEV *S = SE->getSCEV(Right);
691    if (!SE->isLoopInvariant(S, OuterLoop))
692      return false;
693  }
694
695  return true;
696}
697
698// If SV is a LCSSA PHI node with a single incoming value, return the incoming
699// value.
700static Value *followLCSSA(Value *SV) {
701  PHINode *PHI = dyn_cast<PHINode>(SV);
702  if (!PHI)
703    return SV;
704
705  if (PHI->getNumIncomingValues() != 1)
706    return SV;
707  return followLCSSA(PHI->getIncomingValue(0));
708}
709
710// Check V's users to see if it is involved in a reduction in L.
711static PHINode *findInnerReductionPhi(Loop *L, Value *V) {
712  // Reduction variables cannot be constants.
713  if (isa<Constant>(V))
714    return nullptr;
715
716  for (Value *User : V->users()) {
717    if (PHINode *PHI = dyn_cast<PHINode>(User)) {
718      if (PHI->getNumIncomingValues() == 1)
719        continue;
720      RecurrenceDescriptor RD;
721      if (RecurrenceDescriptor::isReductionPHI(PHI, L, RD)) {
722        // Detect floating point reduction only when it can be reordered.
723        if (RD.getExactFPMathInst() != nullptr)
724          return nullptr;
725        return PHI;
726      }
727      return nullptr;
728    }
729  }
730
731  return nullptr;
732}
733
734bool LoopInterchangeLegality::findInductionAndReductions(
735    Loop *L, SmallVector<PHINode *, 8> &Inductions, Loop *InnerLoop) {
736  if (!L->getLoopLatch() || !L->getLoopPredecessor())
737    return false;
738  for (PHINode &PHI : L->getHeader()->phis()) {
739    RecurrenceDescriptor RD;
740    InductionDescriptor ID;
741    if (InductionDescriptor::isInductionPHI(&PHI, L, SE, ID))
742      Inductions.push_back(&PHI);
743    else {
744      // PHIs in inner loops need to be part of a reduction in the outer loop,
745      // discovered when checking the PHIs of the outer loop earlier.
746      if (!InnerLoop) {
747        if (!OuterInnerReductions.count(&PHI)) {
748          LLVM_DEBUG(dbgs() << "Inner loop PHI is not part of reductions "
749                               "across the outer loop.\n");
750          return false;
751        }
752      } else {
753        assert(PHI.getNumIncomingValues() == 2 &&
754               "Phis in loop header should have exactly 2 incoming values");
755        // Check if we have a PHI node in the outer loop that has a reduction
756        // result from the inner loop as an incoming value.
757        Value *V = followLCSSA(PHI.getIncomingValueForBlock(L->getLoopLatch()));
758        PHINode *InnerRedPhi = findInnerReductionPhi(InnerLoop, V);
759        if (!InnerRedPhi ||
760            !llvm::is_contained(InnerRedPhi->incoming_values(), &PHI)) {
761          LLVM_DEBUG(
762              dbgs()
763              << "Failed to recognize PHI as an induction or reduction.\n");
764          return false;
765        }
766        OuterInnerReductions.insert(&PHI);
767        OuterInnerReductions.insert(InnerRedPhi);
768      }
769    }
770  }
771  return true;
772}
773
774// This function indicates the current limitations in the transform as a result
775// of which we do not proceed.
776bool LoopInterchangeLegality::currentLimitations() {
777  BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
778
779  // transform currently expects the loop latches to also be the exiting
780  // blocks.
781  if (InnerLoop->getExitingBlock() != InnerLoopLatch ||
782      OuterLoop->getExitingBlock() != OuterLoop->getLoopLatch() ||
783      !isa<BranchInst>(InnerLoopLatch->getTerminator()) ||
784      !isa<BranchInst>(OuterLoop->getLoopLatch()->getTerminator())) {
785    LLVM_DEBUG(
786        dbgs() << "Loops where the latch is not the exiting block are not"
787               << " supported currently.\n");
788    ORE->emit([&]() {
789      return OptimizationRemarkMissed(DEBUG_TYPE, "ExitingNotLatch",
790                                      OuterLoop->getStartLoc(),
791                                      OuterLoop->getHeader())
792             << "Loops where the latch is not the exiting block cannot be"
793                " interchange currently.";
794    });
795    return true;
796  }
797
798  SmallVector<PHINode *, 8> Inductions;
799  if (!findInductionAndReductions(OuterLoop, Inductions, InnerLoop)) {
800    LLVM_DEBUG(
801        dbgs() << "Only outer loops with induction or reduction PHI nodes "
802               << "are supported currently.\n");
803    ORE->emit([&]() {
804      return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedPHIOuter",
805                                      OuterLoop->getStartLoc(),
806                                      OuterLoop->getHeader())
807             << "Only outer loops with induction or reduction PHI nodes can be"
808                " interchanged currently.";
809    });
810    return true;
811  }
812
813  Inductions.clear();
814  // For multi-level loop nests, make sure that all phi nodes for inner loops
815  // at all levels can be recognized as a induction or reduction phi. Bail out
816  // if a phi node at a certain nesting level cannot be properly recognized.
817  Loop *CurLevelLoop = OuterLoop;
818  while (!CurLevelLoop->getSubLoops().empty()) {
819    // We already made sure that the loop nest is tightly nested.
820    CurLevelLoop = CurLevelLoop->getSubLoops().front();
821    if (!findInductionAndReductions(CurLevelLoop, Inductions, nullptr)) {
822      LLVM_DEBUG(
823          dbgs() << "Only inner loops with induction or reduction PHI nodes "
824                << "are supported currently.\n");
825      ORE->emit([&]() {
826        return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedPHIInner",
827                                        CurLevelLoop->getStartLoc(),
828                                        CurLevelLoop->getHeader())
829              << "Only inner loops with induction or reduction PHI nodes can be"
830                  " interchange currently.";
831      });
832      return true;
833    }
834  }
835
836  // TODO: Triangular loops are not handled for now.
837  if (!isLoopStructureUnderstood()) {
838    LLVM_DEBUG(dbgs() << "Loop structure not understood by pass\n");
839    ORE->emit([&]() {
840      return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedStructureInner",
841                                      InnerLoop->getStartLoc(),
842                                      InnerLoop->getHeader())
843             << "Inner loop structure not understood currently.";
844    });
845    return true;
846  }
847
848  return false;
849}
850
851bool LoopInterchangeLegality::findInductions(
852    Loop *L, SmallVectorImpl<PHINode *> &Inductions) {
853  for (PHINode &PHI : L->getHeader()->phis()) {
854    InductionDescriptor ID;
855    if (InductionDescriptor::isInductionPHI(&PHI, L, SE, ID))
856      Inductions.push_back(&PHI);
857  }
858  return !Inductions.empty();
859}
860
861// We currently only support LCSSA PHI nodes in the inner loop exit, if their
862// users are either reduction PHIs or PHIs outside the outer loop (which means
863// the we are only interested in the final value after the loop).
864static bool
865areInnerLoopExitPHIsSupported(Loop *InnerL, Loop *OuterL,
866                              SmallPtrSetImpl<PHINode *> &Reductions) {
867  BasicBlock *InnerExit = OuterL->getUniqueExitBlock();
868  for (PHINode &PHI : InnerExit->phis()) {
869    // Reduction lcssa phi will have only 1 incoming block that from loop latch.
870    if (PHI.getNumIncomingValues() > 1)
871      return false;
872    if (any_of(PHI.users(), [&Reductions, OuterL](User *U) {
873          PHINode *PN = dyn_cast<PHINode>(U);
874          return !PN ||
875                 (!Reductions.count(PN) && OuterL->contains(PN->getParent()));
876        })) {
877      return false;
878    }
879  }
880  return true;
881}
882
883// We currently support LCSSA PHI nodes in the outer loop exit, if their
884// incoming values do not come from the outer loop latch or if the
885// outer loop latch has a single predecessor. In that case, the value will
886// be available if both the inner and outer loop conditions are true, which
887// will still be true after interchanging. If we have multiple predecessor,
888// that may not be the case, e.g. because the outer loop latch may be executed
889// if the inner loop is not executed.
890static bool areOuterLoopExitPHIsSupported(Loop *OuterLoop, Loop *InnerLoop) {
891  BasicBlock *LoopNestExit = OuterLoop->getUniqueExitBlock();
892  for (PHINode &PHI : LoopNestExit->phis()) {
893    for (unsigned i = 0; i < PHI.getNumIncomingValues(); i++) {
894      Instruction *IncomingI = dyn_cast<Instruction>(PHI.getIncomingValue(i));
895      if (!IncomingI || IncomingI->getParent() != OuterLoop->getLoopLatch())
896        continue;
897
898      // The incoming value is defined in the outer loop latch. Currently we
899      // only support that in case the outer loop latch has a single predecessor.
900      // This guarantees that the outer loop latch is executed if and only if
901      // the inner loop is executed (because tightlyNested() guarantees that the
902      // outer loop header only branches to the inner loop or the outer loop
903      // latch).
904      // FIXME: We could weaken this logic and allow multiple predecessors,
905      //        if the values are produced outside the loop latch. We would need
906      //        additional logic to update the PHI nodes in the exit block as
907      //        well.
908      if (OuterLoop->getLoopLatch()->getUniquePredecessor() == nullptr)
909        return false;
910    }
911  }
912  return true;
913}
914
915// In case of multi-level nested loops, it may occur that lcssa phis exist in
916// the latch of InnerLoop, i.e., when defs of the incoming values are further
917// inside the loopnest. Sometimes those incoming values are not available
918// after interchange, since the original inner latch will become the new outer
919// latch which may have predecessor paths that do not include those incoming
920// values.
921// TODO: Handle transformation of lcssa phis in the InnerLoop latch in case of
922// multi-level loop nests.
923static bool areInnerLoopLatchPHIsSupported(Loop *OuterLoop, Loop *InnerLoop) {
924  if (InnerLoop->getSubLoops().empty())
925    return true;
926  // If the original outer latch has only one predecessor, then values defined
927  // further inside the looploop, e.g., in the innermost loop, will be available
928  // at the new outer latch after interchange.
929  if (OuterLoop->getLoopLatch()->getUniquePredecessor() != nullptr)
930    return true;
931
932  // The outer latch has more than one predecessors, i.e., the inner
933  // exit and the inner header.
934  // PHI nodes in the inner latch are lcssa phis where the incoming values
935  // are defined further inside the loopnest. Check if those phis are used
936  // in the original inner latch. If that is the case then bail out since
937  // those incoming values may not be available at the new outer latch.
938  BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
939  for (PHINode &PHI : InnerLoopLatch->phis()) {
940    for (auto *U : PHI.users()) {
941      Instruction *UI = cast<Instruction>(U);
942      if (InnerLoopLatch == UI->getParent())
943        return false;
944    }
945  }
946  return true;
947}
948
949bool LoopInterchangeLegality::canInterchangeLoops(unsigned InnerLoopId,
950                                                  unsigned OuterLoopId,
951                                                  CharMatrix &DepMatrix) {
952  if (!isLegalToInterChangeLoops(DepMatrix, InnerLoopId, OuterLoopId)) {
953    LLVM_DEBUG(dbgs() << "Failed interchange InnerLoopId = " << InnerLoopId
954                      << " and OuterLoopId = " << OuterLoopId
955                      << " due to dependence\n");
956    ORE->emit([&]() {
957      return OptimizationRemarkMissed(DEBUG_TYPE, "Dependence",
958                                      InnerLoop->getStartLoc(),
959                                      InnerLoop->getHeader())
960             << "Cannot interchange loops due to dependences.";
961    });
962    return false;
963  }
964  // Check if outer and inner loop contain legal instructions only.
965  for (auto *BB : OuterLoop->blocks())
966    for (Instruction &I : BB->instructionsWithoutDebug())
967      if (CallInst *CI = dyn_cast<CallInst>(&I)) {
968        // readnone functions do not prevent interchanging.
969        if (CI->onlyWritesMemory())
970          continue;
971        LLVM_DEBUG(
972            dbgs() << "Loops with call instructions cannot be interchanged "
973                   << "safely.");
974        ORE->emit([&]() {
975          return OptimizationRemarkMissed(DEBUG_TYPE, "CallInst",
976                                          CI->getDebugLoc(),
977                                          CI->getParent())
978                 << "Cannot interchange loops due to call instruction.";
979        });
980
981        return false;
982      }
983
984  if (!findInductions(InnerLoop, InnerLoopInductions)) {
985    LLVM_DEBUG(dbgs() << "Cound not find inner loop induction variables.\n");
986    return false;
987  }
988
989  if (!areInnerLoopLatchPHIsSupported(OuterLoop, InnerLoop)) {
990    LLVM_DEBUG(dbgs() << "Found unsupported PHI nodes in inner loop latch.\n");
991    ORE->emit([&]() {
992      return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedInnerLatchPHI",
993                                      InnerLoop->getStartLoc(),
994                                      InnerLoop->getHeader())
995             << "Cannot interchange loops because unsupported PHI nodes found "
996                "in inner loop latch.";
997    });
998    return false;
999  }
1000
1001  // TODO: The loops could not be interchanged due to current limitations in the
1002  // transform module.
1003  if (currentLimitations()) {
1004    LLVM_DEBUG(dbgs() << "Not legal because of current transform limitation\n");
1005    return false;
1006  }
1007
1008  // Check if the loops are tightly nested.
1009  if (!tightlyNested(OuterLoop, InnerLoop)) {
1010    LLVM_DEBUG(dbgs() << "Loops not tightly nested\n");
1011    ORE->emit([&]() {
1012      return OptimizationRemarkMissed(DEBUG_TYPE, "NotTightlyNested",
1013                                      InnerLoop->getStartLoc(),
1014                                      InnerLoop->getHeader())
1015             << "Cannot interchange loops because they are not tightly "
1016                "nested.";
1017    });
1018    return false;
1019  }
1020
1021  if (!areInnerLoopExitPHIsSupported(OuterLoop, InnerLoop,
1022                                     OuterInnerReductions)) {
1023    LLVM_DEBUG(dbgs() << "Found unsupported PHI nodes in inner loop exit.\n");
1024    ORE->emit([&]() {
1025      return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedExitPHI",
1026                                      InnerLoop->getStartLoc(),
1027                                      InnerLoop->getHeader())
1028             << "Found unsupported PHI node in loop exit.";
1029    });
1030    return false;
1031  }
1032
1033  if (!areOuterLoopExitPHIsSupported(OuterLoop, InnerLoop)) {
1034    LLVM_DEBUG(dbgs() << "Found unsupported PHI nodes in outer loop exit.\n");
1035    ORE->emit([&]() {
1036      return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedExitPHI",
1037                                      OuterLoop->getStartLoc(),
1038                                      OuterLoop->getHeader())
1039             << "Found unsupported PHI node in loop exit.";
1040    });
1041    return false;
1042  }
1043
1044  return true;
1045}
1046
1047int LoopInterchangeProfitability::getInstrOrderCost() {
1048  unsigned GoodOrder, BadOrder;
1049  BadOrder = GoodOrder = 0;
1050  for (BasicBlock *BB : InnerLoop->blocks()) {
1051    for (Instruction &Ins : *BB) {
1052      if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(&Ins)) {
1053        unsigned NumOp = GEP->getNumOperands();
1054        bool FoundInnerInduction = false;
1055        bool FoundOuterInduction = false;
1056        for (unsigned i = 0; i < NumOp; ++i) {
1057          // Skip operands that are not SCEV-able.
1058          if (!SE->isSCEVable(GEP->getOperand(i)->getType()))
1059            continue;
1060
1061          const SCEV *OperandVal = SE->getSCEV(GEP->getOperand(i));
1062          const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(OperandVal);
1063          if (!AR)
1064            continue;
1065
1066          // If we find the inner induction after an outer induction e.g.
1067          // for(int i=0;i<N;i++)
1068          //   for(int j=0;j<N;j++)
1069          //     A[i][j] = A[i-1][j-1]+k;
1070          // then it is a good order.
1071          if (AR->getLoop() == InnerLoop) {
1072            // We found an InnerLoop induction after OuterLoop induction. It is
1073            // a good order.
1074            FoundInnerInduction = true;
1075            if (FoundOuterInduction) {
1076              GoodOrder++;
1077              break;
1078            }
1079          }
1080          // If we find the outer induction after an inner induction e.g.
1081          // for(int i=0;i<N;i++)
1082          //   for(int j=0;j<N;j++)
1083          //     A[j][i] = A[j-1][i-1]+k;
1084          // then it is a bad order.
1085          if (AR->getLoop() == OuterLoop) {
1086            // We found an OuterLoop induction after InnerLoop induction. It is
1087            // a bad order.
1088            FoundOuterInduction = true;
1089            if (FoundInnerInduction) {
1090              BadOrder++;
1091              break;
1092            }
1093          }
1094        }
1095      }
1096    }
1097  }
1098  return GoodOrder - BadOrder;
1099}
1100
1101std::optional<bool>
1102LoopInterchangeProfitability::isProfitablePerLoopCacheAnalysis(
1103    const DenseMap<const Loop *, unsigned> &CostMap,
1104    std::unique_ptr<CacheCost> &CC) {
1105  // This is the new cost model returned from loop cache analysis.
1106  // A smaller index means the loop should be placed an outer loop, and vice
1107  // versa.
1108  if (CostMap.find(InnerLoop) != CostMap.end() &&
1109      CostMap.find(OuterLoop) != CostMap.end()) {
1110    unsigned InnerIndex = 0, OuterIndex = 0;
1111    InnerIndex = CostMap.find(InnerLoop)->second;
1112    OuterIndex = CostMap.find(OuterLoop)->second;
1113    LLVM_DEBUG(dbgs() << "InnerIndex = " << InnerIndex
1114                      << ", OuterIndex = " << OuterIndex << "\n");
1115    if (InnerIndex < OuterIndex)
1116      return std::optional<bool>(true);
1117    assert(InnerIndex != OuterIndex && "CostMap should assign unique "
1118                                       "numbers to each loop");
1119    if (CC->getLoopCost(*OuterLoop) == CC->getLoopCost(*InnerLoop))
1120      return std::nullopt;
1121    return std::optional<bool>(false);
1122  }
1123  return std::nullopt;
1124}
1125
1126std::optional<bool>
1127LoopInterchangeProfitability::isProfitablePerInstrOrderCost() {
1128  // Legacy cost model: this is rough cost estimation algorithm. It counts the
1129  // good and bad order of induction variables in the instruction and allows
1130  // reordering if number of bad orders is more than good.
1131  int Cost = getInstrOrderCost();
1132  LLVM_DEBUG(dbgs() << "Cost = " << Cost << "\n");
1133  if (Cost < 0 && Cost < LoopInterchangeCostThreshold)
1134    return std::optional<bool>(true);
1135
1136  return std::nullopt;
1137}
1138
1139std::optional<bool> LoopInterchangeProfitability::isProfitableForVectorization(
1140    unsigned InnerLoopId, unsigned OuterLoopId, CharMatrix &DepMatrix) {
1141  for (auto &Row : DepMatrix) {
1142    // If the inner loop is loop independent or doesn't carry any dependency
1143    // it is not profitable to move this to outer position, since we are
1144    // likely able to do inner loop vectorization already.
1145    if (Row[InnerLoopId] == 'I' || Row[InnerLoopId] == '=')
1146      return std::optional<bool>(false);
1147
1148    // If the outer loop is not loop independent it is not profitable to move
1149    // this to inner position, since doing so would not enable inner loop
1150    // parallelism.
1151    if (Row[OuterLoopId] != 'I' && Row[OuterLoopId] != '=')
1152      return std::optional<bool>(false);
1153  }
1154  // If inner loop has dependence and outer loop is loop independent then it
1155  // is/ profitable to interchange to enable inner loop parallelism.
1156  // If there are no dependences, interchanging will not improve anything.
1157  return std::optional<bool>(!DepMatrix.empty());
1158}
1159
1160bool LoopInterchangeProfitability::isProfitable(
1161    const Loop *InnerLoop, const Loop *OuterLoop, unsigned InnerLoopId,
1162    unsigned OuterLoopId, CharMatrix &DepMatrix,
1163    const DenseMap<const Loop *, unsigned> &CostMap,
1164    std::unique_ptr<CacheCost> &CC) {
1165  // isProfitable() is structured to avoid endless loop interchange.
1166  // If loop cache analysis could decide the profitability then,
1167  // profitability check will stop and return the analysis result.
1168  // If cache analysis failed to analyze the loopnest (e.g.,
1169  // due to delinearization issues) then only check whether it is
1170  // profitable for InstrOrderCost. Likewise, if InstrOrderCost failed to
1171  // analysis the profitability then only, isProfitableForVectorization
1172  // will decide.
1173  std::optional<bool> shouldInterchange =
1174      isProfitablePerLoopCacheAnalysis(CostMap, CC);
1175  if (!shouldInterchange.has_value()) {
1176    shouldInterchange = isProfitablePerInstrOrderCost();
1177    if (!shouldInterchange.has_value())
1178      shouldInterchange =
1179          isProfitableForVectorization(InnerLoopId, OuterLoopId, DepMatrix);
1180  }
1181  if (!shouldInterchange.has_value()) {
1182    ORE->emit([&]() {
1183      return OptimizationRemarkMissed(DEBUG_TYPE, "InterchangeNotProfitable",
1184                                      InnerLoop->getStartLoc(),
1185                                      InnerLoop->getHeader())
1186             << "Insufficient information to calculate the cost of loop for "
1187                "interchange.";
1188    });
1189    return false;
1190  } else if (!shouldInterchange.value()) {
1191    ORE->emit([&]() {
1192      return OptimizationRemarkMissed(DEBUG_TYPE, "InterchangeNotProfitable",
1193                                      InnerLoop->getStartLoc(),
1194                                      InnerLoop->getHeader())
1195             << "Interchanging loops is not considered to improve cache "
1196                "locality nor vectorization.";
1197    });
1198    return false;
1199  }
1200  return true;
1201}
1202
1203void LoopInterchangeTransform::removeChildLoop(Loop *OuterLoop,
1204                                               Loop *InnerLoop) {
1205  for (Loop *L : *OuterLoop)
1206    if (L == InnerLoop) {
1207      OuterLoop->removeChildLoop(L);
1208      return;
1209    }
1210  llvm_unreachable("Couldn't find loop");
1211}
1212
1213/// Update LoopInfo, after interchanging. NewInner and NewOuter refer to the
1214/// new inner and outer loop after interchanging: NewInner is the original
1215/// outer loop and NewOuter is the original inner loop.
1216///
1217/// Before interchanging, we have the following structure
1218/// Outer preheader
1219//  Outer header
1220//    Inner preheader
1221//    Inner header
1222//      Inner body
1223//      Inner latch
1224//   outer bbs
1225//   Outer latch
1226//
1227// After interchanging:
1228// Inner preheader
1229// Inner header
1230//   Outer preheader
1231//   Outer header
1232//     Inner body
1233//     outer bbs
1234//     Outer latch
1235//   Inner latch
1236void LoopInterchangeTransform::restructureLoops(
1237    Loop *NewInner, Loop *NewOuter, BasicBlock *OrigInnerPreHeader,
1238    BasicBlock *OrigOuterPreHeader) {
1239  Loop *OuterLoopParent = OuterLoop->getParentLoop();
1240  // The original inner loop preheader moves from the new inner loop to
1241  // the parent loop, if there is one.
1242  NewInner->removeBlockFromLoop(OrigInnerPreHeader);
1243  LI->changeLoopFor(OrigInnerPreHeader, OuterLoopParent);
1244
1245  // Switch the loop levels.
1246  if (OuterLoopParent) {
1247    // Remove the loop from its parent loop.
1248    removeChildLoop(OuterLoopParent, NewInner);
1249    removeChildLoop(NewInner, NewOuter);
1250    OuterLoopParent->addChildLoop(NewOuter);
1251  } else {
1252    removeChildLoop(NewInner, NewOuter);
1253    LI->changeTopLevelLoop(NewInner, NewOuter);
1254  }
1255  while (!NewOuter->isInnermost())
1256    NewInner->addChildLoop(NewOuter->removeChildLoop(NewOuter->begin()));
1257  NewOuter->addChildLoop(NewInner);
1258
1259  // BBs from the original inner loop.
1260  SmallVector<BasicBlock *, 8> OrigInnerBBs(NewOuter->blocks());
1261
1262  // Add BBs from the original outer loop to the original inner loop (excluding
1263  // BBs already in inner loop)
1264  for (BasicBlock *BB : NewInner->blocks())
1265    if (LI->getLoopFor(BB) == NewInner)
1266      NewOuter->addBlockEntry(BB);
1267
1268  // Now remove inner loop header and latch from the new inner loop and move
1269  // other BBs (the loop body) to the new inner loop.
1270  BasicBlock *OuterHeader = NewOuter->getHeader();
1271  BasicBlock *OuterLatch = NewOuter->getLoopLatch();
1272  for (BasicBlock *BB : OrigInnerBBs) {
1273    // Nothing will change for BBs in child loops.
1274    if (LI->getLoopFor(BB) != NewOuter)
1275      continue;
1276    // Remove the new outer loop header and latch from the new inner loop.
1277    if (BB == OuterHeader || BB == OuterLatch)
1278      NewInner->removeBlockFromLoop(BB);
1279    else
1280      LI->changeLoopFor(BB, NewInner);
1281  }
1282
1283  // The preheader of the original outer loop becomes part of the new
1284  // outer loop.
1285  NewOuter->addBlockEntry(OrigOuterPreHeader);
1286  LI->changeLoopFor(OrigOuterPreHeader, NewOuter);
1287
1288  // Tell SE that we move the loops around.
1289  SE->forgetLoop(NewOuter);
1290}
1291
1292bool LoopInterchangeTransform::transform() {
1293  bool Transformed = false;
1294
1295  if (InnerLoop->getSubLoops().empty()) {
1296    BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1297    LLVM_DEBUG(dbgs() << "Splitting the inner loop latch\n");
1298    auto &InductionPHIs = LIL.getInnerLoopInductions();
1299    if (InductionPHIs.empty()) {
1300      LLVM_DEBUG(dbgs() << "Failed to find the point to split loop latch \n");
1301      return false;
1302    }
1303
1304    SmallVector<Instruction *, 8> InnerIndexVarList;
1305    for (PHINode *CurInductionPHI : InductionPHIs) {
1306      if (CurInductionPHI->getIncomingBlock(0) == InnerLoopPreHeader)
1307        InnerIndexVarList.push_back(
1308            dyn_cast<Instruction>(CurInductionPHI->getIncomingValue(1)));
1309      else
1310        InnerIndexVarList.push_back(
1311            dyn_cast<Instruction>(CurInductionPHI->getIncomingValue(0)));
1312    }
1313
1314    // Create a new latch block for the inner loop. We split at the
1315    // current latch's terminator and then move the condition and all
1316    // operands that are not either loop-invariant or the induction PHI into the
1317    // new latch block.
1318    BasicBlock *NewLatch =
1319        SplitBlock(InnerLoop->getLoopLatch(),
1320                   InnerLoop->getLoopLatch()->getTerminator(), DT, LI);
1321
1322    SmallSetVector<Instruction *, 4> WorkList;
1323    unsigned i = 0;
1324    auto MoveInstructions = [&i, &WorkList, this, &InductionPHIs, NewLatch]() {
1325      for (; i < WorkList.size(); i++) {
1326        // Duplicate instruction and move it the new latch. Update uses that
1327        // have been moved.
1328        Instruction *NewI = WorkList[i]->clone();
1329        NewI->insertBefore(NewLatch->getFirstNonPHI());
1330        assert(!NewI->mayHaveSideEffects() &&
1331               "Moving instructions with side-effects may change behavior of "
1332               "the loop nest!");
1333        for (Use &U : llvm::make_early_inc_range(WorkList[i]->uses())) {
1334          Instruction *UserI = cast<Instruction>(U.getUser());
1335          if (!InnerLoop->contains(UserI->getParent()) ||
1336              UserI->getParent() == NewLatch ||
1337              llvm::is_contained(InductionPHIs, UserI))
1338            U.set(NewI);
1339        }
1340        // Add operands of moved instruction to the worklist, except if they are
1341        // outside the inner loop or are the induction PHI.
1342        for (Value *Op : WorkList[i]->operands()) {
1343          Instruction *OpI = dyn_cast<Instruction>(Op);
1344          if (!OpI ||
1345              this->LI->getLoopFor(OpI->getParent()) != this->InnerLoop ||
1346              llvm::is_contained(InductionPHIs, OpI))
1347            continue;
1348          WorkList.insert(OpI);
1349        }
1350      }
1351    };
1352
1353    // FIXME: Should we interchange when we have a constant condition?
1354    Instruction *CondI = dyn_cast<Instruction>(
1355        cast<BranchInst>(InnerLoop->getLoopLatch()->getTerminator())
1356            ->getCondition());
1357    if (CondI)
1358      WorkList.insert(CondI);
1359    MoveInstructions();
1360    for (Instruction *InnerIndexVar : InnerIndexVarList)
1361      WorkList.insert(cast<Instruction>(InnerIndexVar));
1362    MoveInstructions();
1363  }
1364
1365  // Ensure the inner loop phi nodes have a separate basic block.
1366  BasicBlock *InnerLoopHeader = InnerLoop->getHeader();
1367  if (InnerLoopHeader->getFirstNonPHI() != InnerLoopHeader->getTerminator()) {
1368    SplitBlock(InnerLoopHeader, InnerLoopHeader->getFirstNonPHI(), DT, LI);
1369    LLVM_DEBUG(dbgs() << "splitting InnerLoopHeader done\n");
1370  }
1371
1372  // Instructions in the original inner loop preheader may depend on values
1373  // defined in the outer loop header. Move them there, because the original
1374  // inner loop preheader will become the entry into the interchanged loop nest.
1375  // Currently we move all instructions and rely on LICM to move invariant
1376  // instructions outside the loop nest.
1377  BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1378  BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
1379  if (InnerLoopPreHeader != OuterLoopHeader) {
1380    SmallPtrSet<Instruction *, 4> NeedsMoving;
1381    for (Instruction &I :
1382         make_early_inc_range(make_range(InnerLoopPreHeader->begin(),
1383                                         std::prev(InnerLoopPreHeader->end()))))
1384      I.moveBefore(OuterLoopHeader->getTerminator());
1385  }
1386
1387  Transformed |= adjustLoopLinks();
1388  if (!Transformed) {
1389    LLVM_DEBUG(dbgs() << "adjustLoopLinks failed\n");
1390    return false;
1391  }
1392
1393  return true;
1394}
1395
1396/// \brief Move all instructions except the terminator from FromBB right before
1397/// InsertBefore
1398static void moveBBContents(BasicBlock *FromBB, Instruction *InsertBefore) {
1399  BasicBlock *ToBB = InsertBefore->getParent();
1400
1401  ToBB->splice(InsertBefore->getIterator(), FromBB, FromBB->begin(),
1402               FromBB->getTerminator()->getIterator());
1403}
1404
1405/// Swap instructions between \p BB1 and \p BB2 but keep terminators intact.
1406static void swapBBContents(BasicBlock *BB1, BasicBlock *BB2) {
1407  // Save all non-terminator instructions of BB1 into TempInstrs and unlink them
1408  // from BB1 afterwards.
1409  auto Iter = map_range(*BB1, [](Instruction &I) { return &I; });
1410  SmallVector<Instruction *, 4> TempInstrs(Iter.begin(), std::prev(Iter.end()));
1411  for (Instruction *I : TempInstrs)
1412    I->removeFromParent();
1413
1414  // Move instructions from BB2 to BB1.
1415  moveBBContents(BB2, BB1->getTerminator());
1416
1417  // Move instructions from TempInstrs to BB2.
1418  for (Instruction *I : TempInstrs)
1419    I->insertBefore(BB2->getTerminator());
1420}
1421
1422// Update BI to jump to NewBB instead of OldBB. Records updates to the
1423// dominator tree in DTUpdates. If \p MustUpdateOnce is true, assert that
1424// \p OldBB  is exactly once in BI's successor list.
1425static void updateSuccessor(BranchInst *BI, BasicBlock *OldBB,
1426                            BasicBlock *NewBB,
1427                            std::vector<DominatorTree::UpdateType> &DTUpdates,
1428                            bool MustUpdateOnce = true) {
1429  assert((!MustUpdateOnce ||
1430          llvm::count_if(successors(BI),
1431                         [OldBB](BasicBlock *BB) {
1432                           return BB == OldBB;
1433                         }) == 1) && "BI must jump to OldBB exactly once.");
1434  bool Changed = false;
1435  for (Use &Op : BI->operands())
1436    if (Op == OldBB) {
1437      Op.set(NewBB);
1438      Changed = true;
1439    }
1440
1441  if (Changed) {
1442    DTUpdates.push_back(
1443        {DominatorTree::UpdateKind::Insert, BI->getParent(), NewBB});
1444    DTUpdates.push_back(
1445        {DominatorTree::UpdateKind::Delete, BI->getParent(), OldBB});
1446  }
1447  assert(Changed && "Expected a successor to be updated");
1448}
1449
1450// Move Lcssa PHIs to the right place.
1451static void moveLCSSAPhis(BasicBlock *InnerExit, BasicBlock *InnerHeader,
1452                          BasicBlock *InnerLatch, BasicBlock *OuterHeader,
1453                          BasicBlock *OuterLatch, BasicBlock *OuterExit,
1454                          Loop *InnerLoop, LoopInfo *LI) {
1455
1456  // Deal with LCSSA PHI nodes in the exit block of the inner loop, that are
1457  // defined either in the header or latch. Those blocks will become header and
1458  // latch of the new outer loop, and the only possible users can PHI nodes
1459  // in the exit block of the loop nest or the outer loop header (reduction
1460  // PHIs, in that case, the incoming value must be defined in the inner loop
1461  // header). We can just substitute the user with the incoming value and remove
1462  // the PHI.
1463  for (PHINode &P : make_early_inc_range(InnerExit->phis())) {
1464    assert(P.getNumIncomingValues() == 1 &&
1465           "Only loops with a single exit are supported!");
1466
1467    // Incoming values are guaranteed be instructions currently.
1468    auto IncI = cast<Instruction>(P.getIncomingValueForBlock(InnerLatch));
1469    // In case of multi-level nested loops, follow LCSSA to find the incoming
1470    // value defined from the innermost loop.
1471    auto IncIInnerMost = cast<Instruction>(followLCSSA(IncI));
1472    // Skip phis with incoming values from the inner loop body, excluding the
1473    // header and latch.
1474    if (IncIInnerMost->getParent() != InnerLatch &&
1475        IncIInnerMost->getParent() != InnerHeader)
1476      continue;
1477
1478    assert(all_of(P.users(),
1479                  [OuterHeader, OuterExit, IncI, InnerHeader](User *U) {
1480                    return (cast<PHINode>(U)->getParent() == OuterHeader &&
1481                            IncI->getParent() == InnerHeader) ||
1482                           cast<PHINode>(U)->getParent() == OuterExit;
1483                  }) &&
1484           "Can only replace phis iff the uses are in the loop nest exit or "
1485           "the incoming value is defined in the inner header (it will "
1486           "dominate all loop blocks after interchanging)");
1487    P.replaceAllUsesWith(IncI);
1488    P.eraseFromParent();
1489  }
1490
1491  SmallVector<PHINode *, 8> LcssaInnerExit;
1492  for (PHINode &P : InnerExit->phis())
1493    LcssaInnerExit.push_back(&P);
1494
1495  SmallVector<PHINode *, 8> LcssaInnerLatch;
1496  for (PHINode &P : InnerLatch->phis())
1497    LcssaInnerLatch.push_back(&P);
1498
1499  // Lcssa PHIs for values used outside the inner loop are in InnerExit.
1500  // If a PHI node has users outside of InnerExit, it has a use outside the
1501  // interchanged loop and we have to preserve it. We move these to
1502  // InnerLatch, which will become the new exit block for the innermost
1503  // loop after interchanging.
1504  for (PHINode *P : LcssaInnerExit)
1505    P->moveBefore(InnerLatch->getFirstNonPHI());
1506
1507  // If the inner loop latch contains LCSSA PHIs, those come from a child loop
1508  // and we have to move them to the new inner latch.
1509  for (PHINode *P : LcssaInnerLatch)
1510    P->moveBefore(InnerExit->getFirstNonPHI());
1511
1512  // Deal with LCSSA PHI nodes in the loop nest exit block. For PHIs that have
1513  // incoming values defined in the outer loop, we have to add a new PHI
1514  // in the inner loop latch, which became the exit block of the outer loop,
1515  // after interchanging.
1516  if (OuterExit) {
1517    for (PHINode &P : OuterExit->phis()) {
1518      if (P.getNumIncomingValues() != 1)
1519        continue;
1520      // Skip Phis with incoming values defined in the inner loop. Those should
1521      // already have been updated.
1522      auto I = dyn_cast<Instruction>(P.getIncomingValue(0));
1523      if (!I || LI->getLoopFor(I->getParent()) == InnerLoop)
1524        continue;
1525
1526      PHINode *NewPhi = dyn_cast<PHINode>(P.clone());
1527      NewPhi->setIncomingValue(0, P.getIncomingValue(0));
1528      NewPhi->setIncomingBlock(0, OuterLatch);
1529      // We might have incoming edges from other BBs, i.e., the original outer
1530      // header.
1531      for (auto *Pred : predecessors(InnerLatch)) {
1532        if (Pred == OuterLatch)
1533          continue;
1534        NewPhi->addIncoming(P.getIncomingValue(0), Pred);
1535      }
1536      NewPhi->insertBefore(InnerLatch->getFirstNonPHI());
1537      P.setIncomingValue(0, NewPhi);
1538    }
1539  }
1540
1541  // Now adjust the incoming blocks for the LCSSA PHIs.
1542  // For PHIs moved from Inner's exit block, we need to replace Inner's latch
1543  // with the new latch.
1544  InnerLatch->replacePhiUsesWith(InnerLatch, OuterLatch);
1545}
1546
1547bool LoopInterchangeTransform::adjustLoopBranches() {
1548  LLVM_DEBUG(dbgs() << "adjustLoopBranches called\n");
1549  std::vector<DominatorTree::UpdateType> DTUpdates;
1550
1551  BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();
1552  BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1553
1554  assert(OuterLoopPreHeader != OuterLoop->getHeader() &&
1555         InnerLoopPreHeader != InnerLoop->getHeader() && OuterLoopPreHeader &&
1556         InnerLoopPreHeader && "Guaranteed by loop-simplify form");
1557  // Ensure that both preheaders do not contain PHI nodes and have single
1558  // predecessors. This allows us to move them easily. We use
1559  // InsertPreHeaderForLoop to create an 'extra' preheader, if the existing
1560  // preheaders do not satisfy those conditions.
1561  if (isa<PHINode>(OuterLoopPreHeader->begin()) ||
1562      !OuterLoopPreHeader->getUniquePredecessor())
1563    OuterLoopPreHeader =
1564        InsertPreheaderForLoop(OuterLoop, DT, LI, nullptr, true);
1565  if (InnerLoopPreHeader == OuterLoop->getHeader())
1566    InnerLoopPreHeader =
1567        InsertPreheaderForLoop(InnerLoop, DT, LI, nullptr, true);
1568
1569  // Adjust the loop preheader
1570  BasicBlock *InnerLoopHeader = InnerLoop->getHeader();
1571  BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
1572  BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
1573  BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
1574  BasicBlock *OuterLoopPredecessor = OuterLoopPreHeader->getUniquePredecessor();
1575  BasicBlock *InnerLoopLatchPredecessor =
1576      InnerLoopLatch->getUniquePredecessor();
1577  BasicBlock *InnerLoopLatchSuccessor;
1578  BasicBlock *OuterLoopLatchSuccessor;
1579
1580  BranchInst *OuterLoopLatchBI =
1581      dyn_cast<BranchInst>(OuterLoopLatch->getTerminator());
1582  BranchInst *InnerLoopLatchBI =
1583      dyn_cast<BranchInst>(InnerLoopLatch->getTerminator());
1584  BranchInst *OuterLoopHeaderBI =
1585      dyn_cast<BranchInst>(OuterLoopHeader->getTerminator());
1586  BranchInst *InnerLoopHeaderBI =
1587      dyn_cast<BranchInst>(InnerLoopHeader->getTerminator());
1588
1589  if (!OuterLoopPredecessor || !InnerLoopLatchPredecessor ||
1590      !OuterLoopLatchBI || !InnerLoopLatchBI || !OuterLoopHeaderBI ||
1591      !InnerLoopHeaderBI)
1592    return false;
1593
1594  BranchInst *InnerLoopLatchPredecessorBI =
1595      dyn_cast<BranchInst>(InnerLoopLatchPredecessor->getTerminator());
1596  BranchInst *OuterLoopPredecessorBI =
1597      dyn_cast<BranchInst>(OuterLoopPredecessor->getTerminator());
1598
1599  if (!OuterLoopPredecessorBI || !InnerLoopLatchPredecessorBI)
1600    return false;
1601  BasicBlock *InnerLoopHeaderSuccessor = InnerLoopHeader->getUniqueSuccessor();
1602  if (!InnerLoopHeaderSuccessor)
1603    return false;
1604
1605  // Adjust Loop Preheader and headers.
1606  // The branches in the outer loop predecessor and the outer loop header can
1607  // be unconditional branches or conditional branches with duplicates. Consider
1608  // this when updating the successors.
1609  updateSuccessor(OuterLoopPredecessorBI, OuterLoopPreHeader,
1610                  InnerLoopPreHeader, DTUpdates, /*MustUpdateOnce=*/false);
1611  // The outer loop header might or might not branch to the outer latch.
1612  // We are guaranteed to branch to the inner loop preheader.
1613  if (llvm::is_contained(OuterLoopHeaderBI->successors(), OuterLoopLatch)) {
1614    // In this case the outerLoopHeader should branch to the InnerLoopLatch.
1615    updateSuccessor(OuterLoopHeaderBI, OuterLoopLatch, InnerLoopLatch,
1616                    DTUpdates,
1617                    /*MustUpdateOnce=*/false);
1618  }
1619  updateSuccessor(OuterLoopHeaderBI, InnerLoopPreHeader,
1620                  InnerLoopHeaderSuccessor, DTUpdates,
1621                  /*MustUpdateOnce=*/false);
1622
1623  // Adjust reduction PHI's now that the incoming block has changed.
1624  InnerLoopHeaderSuccessor->replacePhiUsesWith(InnerLoopHeader,
1625                                               OuterLoopHeader);
1626
1627  updateSuccessor(InnerLoopHeaderBI, InnerLoopHeaderSuccessor,
1628                  OuterLoopPreHeader, DTUpdates);
1629
1630  // -------------Adjust loop latches-----------
1631  if (InnerLoopLatchBI->getSuccessor(0) == InnerLoopHeader)
1632    InnerLoopLatchSuccessor = InnerLoopLatchBI->getSuccessor(1);
1633  else
1634    InnerLoopLatchSuccessor = InnerLoopLatchBI->getSuccessor(0);
1635
1636  updateSuccessor(InnerLoopLatchPredecessorBI, InnerLoopLatch,
1637                  InnerLoopLatchSuccessor, DTUpdates);
1638
1639  if (OuterLoopLatchBI->getSuccessor(0) == OuterLoopHeader)
1640    OuterLoopLatchSuccessor = OuterLoopLatchBI->getSuccessor(1);
1641  else
1642    OuterLoopLatchSuccessor = OuterLoopLatchBI->getSuccessor(0);
1643
1644  updateSuccessor(InnerLoopLatchBI, InnerLoopLatchSuccessor,
1645                  OuterLoopLatchSuccessor, DTUpdates);
1646  updateSuccessor(OuterLoopLatchBI, OuterLoopLatchSuccessor, InnerLoopLatch,
1647                  DTUpdates);
1648
1649  DT->applyUpdates(DTUpdates);
1650  restructureLoops(OuterLoop, InnerLoop, InnerLoopPreHeader,
1651                   OuterLoopPreHeader);
1652
1653  moveLCSSAPhis(InnerLoopLatchSuccessor, InnerLoopHeader, InnerLoopLatch,
1654                OuterLoopHeader, OuterLoopLatch, InnerLoop->getExitBlock(),
1655                InnerLoop, LI);
1656  // For PHIs in the exit block of the outer loop, outer's latch has been
1657  // replaced by Inners'.
1658  OuterLoopLatchSuccessor->replacePhiUsesWith(OuterLoopLatch, InnerLoopLatch);
1659
1660  auto &OuterInnerReductions = LIL.getOuterInnerReductions();
1661  // Now update the reduction PHIs in the inner and outer loop headers.
1662  SmallVector<PHINode *, 4> InnerLoopPHIs, OuterLoopPHIs;
1663  for (PHINode &PHI : InnerLoopHeader->phis())
1664    if (OuterInnerReductions.contains(&PHI))
1665      InnerLoopPHIs.push_back(&PHI);
1666
1667  for (PHINode &PHI : OuterLoopHeader->phis())
1668    if (OuterInnerReductions.contains(&PHI))
1669      OuterLoopPHIs.push_back(&PHI);
1670
1671  // Now move the remaining reduction PHIs from outer to inner loop header and
1672  // vice versa. The PHI nodes must be part of a reduction across the inner and
1673  // outer loop and all the remains to do is and updating the incoming blocks.
1674  for (PHINode *PHI : OuterLoopPHIs) {
1675    LLVM_DEBUG(dbgs() << "Outer loop reduction PHIs:\n"; PHI->dump(););
1676    PHI->moveBefore(InnerLoopHeader->getFirstNonPHI());
1677    assert(OuterInnerReductions.count(PHI) && "Expected a reduction PHI node");
1678  }
1679  for (PHINode *PHI : InnerLoopPHIs) {
1680    LLVM_DEBUG(dbgs() << "Inner loop reduction PHIs:\n"; PHI->dump(););
1681    PHI->moveBefore(OuterLoopHeader->getFirstNonPHI());
1682    assert(OuterInnerReductions.count(PHI) && "Expected a reduction PHI node");
1683  }
1684
1685  // Update the incoming blocks for moved PHI nodes.
1686  OuterLoopHeader->replacePhiUsesWith(InnerLoopPreHeader, OuterLoopPreHeader);
1687  OuterLoopHeader->replacePhiUsesWith(InnerLoopLatch, OuterLoopLatch);
1688  InnerLoopHeader->replacePhiUsesWith(OuterLoopPreHeader, InnerLoopPreHeader);
1689  InnerLoopHeader->replacePhiUsesWith(OuterLoopLatch, InnerLoopLatch);
1690
1691  // Values defined in the outer loop header could be used in the inner loop
1692  // latch. In that case, we need to create LCSSA phis for them, because after
1693  // interchanging they will be defined in the new inner loop and used in the
1694  // new outer loop.
1695  IRBuilder<> Builder(OuterLoopHeader->getContext());
1696  SmallVector<Instruction *, 4> MayNeedLCSSAPhis;
1697  for (Instruction &I :
1698       make_range(OuterLoopHeader->begin(), std::prev(OuterLoopHeader->end())))
1699    MayNeedLCSSAPhis.push_back(&I);
1700  formLCSSAForInstructions(MayNeedLCSSAPhis, *DT, *LI, SE, Builder);
1701
1702  return true;
1703}
1704
1705bool LoopInterchangeTransform::adjustLoopLinks() {
1706  // Adjust all branches in the inner and outer loop.
1707  bool Changed = adjustLoopBranches();
1708  if (Changed) {
1709    // We have interchanged the preheaders so we need to interchange the data in
1710    // the preheaders as well. This is because the content of the inner
1711    // preheader was previously executed inside the outer loop.
1712    BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();
1713    BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
1714    swapBBContents(OuterLoopPreHeader, InnerLoopPreHeader);
1715  }
1716  return Changed;
1717}
1718
1719namespace {
1720/// Main LoopInterchange Pass.
1721struct LoopInterchangeLegacyPass : public LoopPass {
1722  static char ID;
1723
1724  LoopInterchangeLegacyPass() : LoopPass(ID) {
1725    initializeLoopInterchangeLegacyPassPass(*PassRegistry::getPassRegistry());
1726  }
1727
1728  void getAnalysisUsage(AnalysisUsage &AU) const override {
1729    AU.addRequired<DependenceAnalysisWrapperPass>();
1730    AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
1731
1732    getLoopAnalysisUsage(AU);
1733  }
1734
1735  bool runOnLoop(Loop *L, LPPassManager &LPM) override {
1736    if (skipLoop(L))
1737      return false;
1738
1739    auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
1740    auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1741    auto *DI = &getAnalysis<DependenceAnalysisWrapperPass>().getDI();
1742    auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1743    auto *ORE = &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
1744    std::unique_ptr<CacheCost> CC = nullptr;
1745    return LoopInterchange(SE, LI, DI, DT, CC, ORE).run(L);
1746  }
1747};
1748} // namespace
1749
1750char LoopInterchangeLegacyPass::ID = 0;
1751
1752INITIALIZE_PASS_BEGIN(LoopInterchangeLegacyPass, "loop-interchange",
1753                      "Interchanges loops for cache reuse", false, false)
1754INITIALIZE_PASS_DEPENDENCY(LoopPass)
1755INITIALIZE_PASS_DEPENDENCY(DependenceAnalysisWrapperPass)
1756INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass)
1757
1758INITIALIZE_PASS_END(LoopInterchangeLegacyPass, "loop-interchange",
1759                    "Interchanges loops for cache reuse", false, false)
1760
1761Pass *llvm::createLoopInterchangePass() {
1762  return new LoopInterchangeLegacyPass();
1763}
1764
1765PreservedAnalyses LoopInterchangePass::run(LoopNest &LN,
1766                                           LoopAnalysisManager &AM,
1767                                           LoopStandardAnalysisResults &AR,
1768                                           LPMUpdater &U) {
1769  Function &F = *LN.getParent();
1770
1771  DependenceInfo DI(&F, &AR.AA, &AR.SE, &AR.LI);
1772  std::unique_ptr<CacheCost> CC =
1773      CacheCost::getCacheCost(LN.getOutermostLoop(), AR, DI);
1774  OptimizationRemarkEmitter ORE(&F);
1775  if (!LoopInterchange(&AR.SE, &AR.LI, &DI, &AR.DT, CC, &ORE).run(LN))
1776    return PreservedAnalyses::all();
1777  U.markLoopNestChanged(true);
1778  return getLoopPassPreservedAnalyses();
1779}
1780