LoopInterchange.cpp

Go to the documentation of this file.

//===- LoopInterchange.cpp - Loop interchange pass-------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This Pass handles loop interchange transform.
// This pass interchanges loops to provide a more cache-friendly memory access
// patterns.
//
//===----------------------------------------------------------------------===//
 
#include "llvm/Transforms/Scalar/LoopInterchange.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/StringMap.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/Analysis/DependenceAnalysis.h"
#include "llvm/Analysis/LoopCacheAnalysis.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopNestAnalysis.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/DiagnosticInfo.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.h"
#include "llvm/IR/Verifier.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Scalar/LoopPassManager.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include <cassert>
#include <utility>
#include <vector>
 
using namespace llvm;
 
#define DEBUG_TYPE "loop-interchange"
 
STATISTIC(LoopsInterchanged, "Number of loops interchanged");
 
static cl::opt<int> LoopInterchangeCostThreshold(
    "loop-interchange-threshold", cl::init(0), cl::Hidden,
    cl::desc("Interchange if you gain more than this number"));
 
static cl::opt<unsigned int> MaxMemInstrRatio(
    "loop-interchange-max-mem-instr-ratio", cl::init(4), cl::Hidden,
    cl::desc("Maximum number of load/store instructions squared in relation to "
             "the total number of instructions. Higher value may lead to more "
             "interchanges at the cost of compile-time"));
 
namespace {
 
using LoopVector = SmallVector<Loop *, 8>;
 
/// A list of direction vectors. Each entry represents a direction vector
/// corresponding to one or more dependencies existing in the loop nest. The
/// length of all direction vectors is equal and is N + 1, where N is the depth
/// of the loop nest. The first N elements correspond to the dependency
/// direction of each N loops. The last one indicates whether this entry is
/// forward dependency ('<') or not ('*'). The term "forward" aligns with what
/// is defined in LoopAccessAnalysis.
// TODO: Check if we can use a sparse matrix here.
using CharMatrix = std::vector<std::vector<char>>;
 
/// Types of rules used in profitability check.
enum class RuleTy {
  PerLoopCacheAnalysis,
  PerInstrOrderCost,
  ForVectorization,
  Ignore
};
 
} // end anonymous namespace
 
// Minimum loop depth supported.
static cl::opt<unsigned int> MinLoopNestDepth(
    "loop-interchange-min-loop-nest-depth", cl::init(2), cl::Hidden,
    cl::desc("Minimum depth of loop nest considered for the transform"));
 
// Maximum loop depth supported.
static cl::opt<unsigned int> MaxLoopNestDepth(
    "loop-interchange-max-loop-nest-depth", cl::init(10), cl::Hidden,
    cl::desc("Maximum depth of loop nest considered for the transform"));
 
// We prefer cache cost to vectorization by default.
static cl::list<RuleTy> Profitabilities(
    "loop-interchange-profitabilities", cl::MiscFlags::CommaSeparated,
    cl::Hidden,
    cl::desc("List of profitability heuristics to be used. They are applied in "
             "the given order"),
    cl::list_init<RuleTy>({RuleTy::PerInstrOrderCost,
                           RuleTy::ForVectorization}),
    cl::values(clEnumValN(RuleTy::PerLoopCacheAnalysis, "cache",
                          "Prioritize loop cache cost"),
               clEnumValN(RuleTy::PerInstrOrderCost, "instorder",
                          "Prioritize the IVs order of each instruction"),
               clEnumValN(RuleTy::ForVectorization, "vectorize",
                          "Prioritize vectorization"),
               clEnumValN(RuleTy::Ignore, "ignore",
                          "Ignore profitability, force interchange (does not "
                          "work with other options)")));
 
// Support for the inner-loop reduction pattern.
static cl::opt<bool> EnableReduction2Memory(
    "loop-interchange-reduction-to-mem", cl::init(false), cl::Hidden,
    cl::desc("Support for the inner-loop reduction pattern."));
 
#ifndef NDEBUG
static bool noDuplicateRulesAndIgnore(ArrayRef<RuleTy> Rules) {
  SmallSet<RuleTy, 4> Set;
  for (RuleTy Rule : Rules) {
    if (!Set.insert(Rule).second)
      return false;
    if (Rule == RuleTy::Ignore)
      return false;
  }
  return true;
}
 
static void printDepMatrix(CharMatrix &DepMatrix) {
  for (auto &Row : DepMatrix) {
    // Drop the last element because it is a flag indicating whether this is
    // forward dependency or not, which doesn't affect the legality check.
    for (char D : drop_end(Row))
      LLVM_DEBUG(dbgs() << D << " ");
    LLVM_DEBUG(dbgs() << "\n");
  }
}
 
/// Return true if \p Src appears before \p Dst in the same basic block.
/// Precondition: \p Src and \Dst are distinct instructions within the same
/// basic block.
static bool inThisOrder(const Instruction *Src, const Instruction *Dst) {
  assert(Src->getParent() == Dst->getParent() && Src != Dst &&
         "Expected Src and Dst to be different instructions in the same BB");
 
  bool FoundSrc = false;
  for (const Instruction &I : *(Src->getParent())) {
    if (&I == Src) {
      FoundSrc = true;
      continue;
    }
    if (&I == Dst)
      return FoundSrc;
  }
 
  llvm_unreachable("Dst not found");
}
#endif
 
static bool populateDependencyMatrix(CharMatrix &DepMatrix, unsigned Level,
                                     Loop *L, DependenceInfo *DI,
                                     ScalarEvolution *SE,
                                     OptimizationRemarkEmitter *ORE) {
  using ValueVector = SmallVector<Value *, 16>;
 
  ValueVector MemInstr;
  unsigned NumInsts = 0;
 
  // For each block.
  for (BasicBlock *BB : L->blocks()) {
    // Scan the BB and collect legal loads and stores.
    for (Instruction &I : *BB) {
      NumInsts++;
      if (auto *Ld = dyn_cast<LoadInst>(&I)) {
        if (!Ld->isSimple())
          return false;
        MemInstr.push_back(&I);
      } else if (auto *St = dyn_cast<StoreInst>(&I)) {
        if (!St->isSimple())
          return false;
        MemInstr.push_back(&I);
      }
    }
  }
 
  // To populate the dependence matrix, we perform dependence test for each pair
  // of memory instructions, which has O(NumMemInstr^2) complexity. This implies
  // that even if the number of memory instructions is small, the analysis can
  // still be expensive if the most of the instructions in the loop are memory
  // instructions. On the other hand, if the number of memory instructions is
  // not small, but the loop is large (i.e., it contains many non-memory
  // instructions), the analysis can still be affordable.
  unsigned NumMemInstr = MemInstr.size();
  LLVM_DEBUG(dbgs() << "Found " << NumMemInstr
                    << " Loads and Stores to analyze\n");
  if (MaxMemInstrRatio * NumInsts < NumMemInstr * NumMemInstr) {
    ORE->emit([&]() {
      return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedLoop",
                                      L->getStartLoc(), L->getHeader())
             << "Number of loads/stores exceeded, the supported maximum can be "
                "increased with option -loop-interchange-max-mem-instr-ratio.";
    });
    return false;
  }
  ValueVector::iterator I, IE, J, JE;
 
  // Manage direction vectors that are already seen. Map each direction vector
  // to an index of DepMatrix at which it is stored.
  StringMap<unsigned> Seen;
 
  for (I = MemInstr.begin(), IE = MemInstr.end(); I != IE; ++I) {
    for (J = I, JE = MemInstr.end(); J != JE; ++J) {
      std::vector<char> Dep;
      Instruction *Src = cast<Instruction>(*I);
      Instruction *Dst = cast<Instruction>(*J);
      // Ignore Input dependencies.
      if (isa<LoadInst>(Src) && isa<LoadInst>(Dst))
        continue;
      // Track Output, Flow, and Anti dependencies.
      if (auto D = DI->depends(Src, Dst)) {
        assert(D->isOrdered() && "Expected an output, flow or anti dep.");
        // If the direction vector is negative, normalize it to
        // make it non-negative.
        if (D->normalize(SE))
          LLVM_DEBUG(dbgs() << "Negative dependence vector normalized.\n");
        LLVM_DEBUG(StringRef DepType =
                       D->isFlow() ? "flow" : D->isAnti() ? "anti" : "output";
                   dbgs() << "Found " << DepType
                          << " dependency between Src and Dst\n"
                          << " Src:" << *Src << "\n Dst:" << *Dst << '\n');
        unsigned Levels = D->getLevels();
        char Direction;
        for (unsigned II = 1; II <= Levels; ++II) {
          // `DVEntry::LE` is converted to `*`. This is because `LE` means `<`
          // or `=`, for which we don't have an equivalent representation, so
          // that the conservative approximation is necessary. The same goes for
          // `DVEntry::GE`.
          // TODO: Use of fine-grained expressions allows for more accurate
          // analysis.
          unsigned Dir = D->getDirection(II);
          if (Dir == Dependence::DVEntry::LT)
            Direction = '<';
          else if (Dir == Dependence::DVEntry::GT)
            Direction = '>';
          else if (Dir == Dependence::DVEntry::EQ)
            Direction = '=';
          else
            Direction = '*';
          Dep.push_back(Direction);
        }
 
        // If the Dependence object doesn't have any information, fill the
        // dependency vector with '*'.
        if (D->isConfused()) {
          assert(Dep.empty() && "Expected empty dependency vector");
          Dep.assign(Level, '*');
        }
 
        while (Dep.size() != Level) {
          Dep.push_back('I');
        }
 
        // If all the elements of any direction vector have only '*', legality
        // can't be proven. Exit early to save compile time.
        if (all_of(Dep, equal_to('*'))) {
          ORE->emit([&]() {
            return OptimizationRemarkMissed(DEBUG_TYPE, "Dependence",
                                            L->getStartLoc(), L->getHeader())
                   << "All loops have dependencies in all directions.";
          });
          return false;
        }
 
        // Test whether the dependency is forward or not.
        bool IsKnownForward = true;
        if (Src->getParent() != Dst->getParent()) {
          // In general, when Src and Dst are in different BBs, the execution
          // order of them within a single iteration is not guaranteed. Treat
          // conservatively as not-forward dependency in this case.
          IsKnownForward = false;
        } else {
          // Src and Dst are in the same BB. If they are the different
          // instructions, Src should appear before Dst in the BB as they are
          // stored to MemInstr in that order.
          assert((Src == Dst || inThisOrder(Src, Dst)) &&
                 "Unexpected instructions");
 
          // If the Dependence object is reversed (due to normalization), it
          // represents the dependency from Dst to Src, meaning it is a backward
          // dependency. Otherwise it should be a forward dependency.
          bool IsReversed = D->getSrc() != Src;
          if (IsReversed)
            IsKnownForward = false;
        }
 
        // Initialize the last element. Assume forward dependencies only; it
        // will be updated later if there is any non-forward dependency.
        Dep.push_back('<');
 
        // The last element should express the "summary" among one or more
        // direction vectors whose first N elements are the same (where N is
        // the depth of the loop nest). Hence we exclude the last element from
        // the Seen map.
        auto [Ite, Inserted] = Seen.try_emplace(
            StringRef(Dep.data(), Dep.size() - 1), DepMatrix.size());
 
        // Make sure we only add unique entries to the dependency matrix.
        if (Inserted)
          DepMatrix.push_back(Dep);
 
        // If we cannot prove that this dependency is forward, change the last
        // element of the corresponding entry. Since a `[... *]` dependency
        // includes a `[... <]` dependency, we do not need to keep both and
        // change the existing entry instead.
        if (!IsKnownForward)
          DepMatrix[Ite->second].back() = '*';
      }
    }
  }
 
  return true;
}
 
// A loop is moved from index 'from' to an index 'to'. Update the Dependence
// matrix by exchanging the two columns.
static void interChangeDependencies(CharMatrix &DepMatrix, unsigned FromIndx,
                                    unsigned ToIndx) {
  for (auto &Row : DepMatrix)
    std::swap(Row[ToIndx], Row[FromIndx]);
}
 
// Check if a direction vector is lexicographically positive. Return true if it
// is positive, nullopt if it is "zero", otherwise false.
// [Theorem] A permutation of the loops in a perfect nest is legal if and only
// if the direction matrix, after the same permutation is applied to its
// columns, has no ">" direction as the leftmost non-"=" direction in any row.
static std::optional<bool>
isLexicographicallyPositive(ArrayRef<char> DV, unsigned Begin, unsigned End) {
  for (unsigned char Direction : DV.slice(Begin, End - Begin)) {
    if (Direction == '<')
      return true;
    if (Direction == '>' || Direction == '*')
      return false;
  }
  return std::nullopt;
}
 
// Checks if it is legal to interchange 2 loops.
static bool isLegalToInterChangeLoops(CharMatrix &DepMatrix,
                                      unsigned InnerLoopId,
                                      unsigned OuterLoopId) {
  unsigned NumRows = DepMatrix.size();
  std::vector<char> Cur;
  // For each row check if it is valid to interchange.
  for (unsigned Row = 0; Row < NumRows; ++Row) {
    // Create temporary DepVector check its lexicographical order
    // before and after swapping OuterLoop vs InnerLoop
    Cur = DepMatrix[Row];
 
    // If the surrounding loops already ensure that the direction vector is
    // lexicographically positive, nothing within the loop will be able to break
    // the dependence. In such a case we can skip the subsequent check.
    if (isLexicographicallyPositive(Cur, 0, OuterLoopId) == true)
      continue;
 
    // Check if the direction vector is lexicographically positive (or zero)
    // for both before/after exchanged. Ignore the last element because it
    // doesn't affect the legality.
    if (isLexicographicallyPositive(Cur, OuterLoopId, Cur.size() - 1) == false)
      return false;
    std::swap(Cur[InnerLoopId], Cur[OuterLoopId]);
    if (isLexicographicallyPositive(Cur, OuterLoopId, Cur.size() - 1) == false)
      return false;
  }
  return true;
}
 
static void populateWorklist(Loop &L, LoopVector &LoopList) {
  LLVM_DEBUG(dbgs() << "Calling populateWorklist on Func: "
                    << L.getHeader()->getParent()->getName() << " Loop: %"
                    << L.getHeader()->getName() << '\n');
  assert(LoopList.empty() && "LoopList should initially be empty!");
  Loop *CurrentLoop = &L;
  const std::vector<Loop *> *Vec = &CurrentLoop->getSubLoops();
  while (!Vec->empty()) {
    // The current loop has multiple subloops in it hence it is not tightly
    // nested.
    // Discard all loops above it added into Worklist.
    if (Vec->size() != 1) {
      LoopList = {};
      return;
    }
 
    LoopList.push_back(CurrentLoop);
    CurrentLoop = Vec->front();
    Vec = &CurrentLoop->getSubLoops();
  }
  LoopList.push_back(CurrentLoop);
}
 
static bool hasSupportedLoopDepth(ArrayRef<Loop *> LoopList,
                                  OptimizationRemarkEmitter &ORE) {
  unsigned LoopNestDepth = LoopList.size();
  if (LoopNestDepth < MinLoopNestDepth || LoopNestDepth > MaxLoopNestDepth) {
    LLVM_DEBUG(dbgs() << "Unsupported depth of loop nest " << LoopNestDepth
                      << ", the supported range is [" << MinLoopNestDepth
                      << ", " << MaxLoopNestDepth << "].\n");
    Loop *OuterLoop = LoopList.front();
    ORE.emit([&]() {
      return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedLoopNestDepth",
                                      OuterLoop->getStartLoc(),
                                      OuterLoop->getHeader())
             << "Unsupported depth of loop nest, the supported range is ["
             << std::to_string(MinLoopNestDepth) << ", "
             << std::to_string(MaxLoopNestDepth) << "].\n";
    });
    return false;
  }
  return true;
}
 
static bool isComputableLoopNest(ScalarEvolution *SE,
                                 ArrayRef<Loop *> LoopList) {
  for (Loop *L : LoopList) {
    const SCEV *ExitCountOuter = SE->getBackedgeTakenCount(L);
    if (isa<SCEVCouldNotCompute>(ExitCountOuter)) {
      LLVM_DEBUG(dbgs() << "Couldn't compute backedge count\n");
      return false;
    }
    if (L->getNumBackEdges() != 1) {
      LLVM_DEBUG(dbgs() << "NumBackEdges is not equal to 1\n");
      return false;
    }
    if (!L->getExitingBlock()) {
      LLVM_DEBUG(dbgs() << "Loop doesn't have unique exit block\n");
      return false;
    }
  }
  return true;
}
 
namespace {
 
/// LoopInterchangeLegality checks if it is legal to interchange the loop.
class LoopInterchangeLegality {
public:
  LoopInterchangeLegality(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
                          OptimizationRemarkEmitter *ORE, DominatorTree *DT)
      : OuterLoop(Outer), InnerLoop(Inner), SE(SE), DT(DT), ORE(ORE) {}
 
  /// Check if the loops can be interchanged.
  bool canInterchangeLoops(unsigned InnerLoopId, unsigned OuterLoopId,
                           CharMatrix &DepMatrix);
 
  /// Check if the loop structure is understood. We do not handle triangular
  /// loops for now.
  bool isLoopStructureUnderstood();
 
  bool currentLimitations();
 
  const SmallPtrSetImpl<PHINode *> &getOuterInnerReductions() const {
    return OuterInnerReductions;
  }
 
  const ArrayRef<PHINode *> getInnerLoopInductions() const {
    return InnerLoopInductions;
  }
 
  ArrayRef<Instruction *> getHasNoWrapReductions() const {
    return HasNoWrapReductions;
  }
 
  ArrayRef<Instruction *> getHasNoInfInsts() const { return HasNoInfInsts; }
 
  /// Record reductions in the inner loop. Currently supported reductions:
  /// - initialized from a constant.
  /// - reduction PHI node has only one user.
  /// - located in the innermost loop.
  struct InnerReduction {
    /// The reduction itself.
    PHINode *Reduction;
    Value *Init;
    Value *Next;
    /// The Lcssa PHI.
    PHINode *LcssaPhi;
    /// Store reduction result into memory object.
    StoreInst *LcssaStore;
    /// The memory Location.
    Value *MemRef;
    Type *ElemTy;
  };
 
  ArrayRef<InnerReduction> getInnerReductions() const {
    return InnerReductions;
  }
 
private:
  bool tightlyNested(Loop *Outer, Loop *Inner);
  bool containsUnsafeInstructions(BasicBlock *BB, Instruction *Skip);
 
  /// Traverse all PHI nodes in the header of each loop in the loop nest
  /// starting from \p OuterLoop, and perform the following checks:
  ///
  /// - Identify induction variables in the child loop of \p OuterLoop.
  /// - Check for reductions across the inner loop and \p OuterLoop.
  /// - Detect unsupported PHI nodes.
  ///
  /// Return false if any unsupported PHI node is found or if no induction
  /// variable is found in the child loop of \p OuterLoop. Otherwise return
  /// true.
  bool checkInductionsAndReductions(Loop *OuterLoop);
 
  /// Detect and record the reduction of the inner loop. Add them to
  /// InnerReductions.
  ///
  ///    innerloop:
  ///        Re = phi<0.0, Next>
  ///        Next = Re op ...
  ///    OuterLoopLatch:
  ///        Lcssa = phi<Next>    ; lcssa phi
  ///        store Lcssa, MemRef  ; LcssaStore
  ///
  bool isInnerReduction(Loop *L, PHINode *Phi,
                        SmallVectorImpl<Instruction *> &HasNoWrapInsts);
 
  Loop *OuterLoop;
  Loop *InnerLoop;
 
  ScalarEvolution *SE;
  DominatorTree *DT;
 
  /// Interface to emit optimization remarks.
  OptimizationRemarkEmitter *ORE;
 
  /// Set of reduction PHIs taking part of a reduction across the inner and
  /// outer loop.
  SmallPtrSet<PHINode *, 4> OuterInnerReductions;
 
  /// Set of inner loop induction PHIs
  SmallVector<PHINode *, 8> InnerLoopInductions;
 
  /// Hold instructions that have nuw/nsw flags and involved in reductions,
  /// like integer addition/multiplication. Those flags must be dropped when
  /// interchanging the loops.
  SmallVector<Instruction *, 4> HasNoWrapReductions;
 
  /// Hold instructions that have ninf flags and involved in reductions. Those
  /// flags must be dropped when interchanging the loops.
  SmallVector<Instruction *, 4> HasNoInfInsts;
 
  /// Vector of reductions in the inner loop.
  SmallVector<InnerReduction, 8> InnerReductions;
};
 
/// Manages information utilized by the profitability check for cache. The main
/// purpose of this class is to delay the computation of CacheCost until it is
/// actually needed.
class CacheCostManager {
  Loop *OutermostLoop;
  LoopStandardAnalysisResults *AR;
  DependenceInfo *DI;
 
  /// CacheCost for \ref OutermostLoop. Once it is computed, it is cached. Note
  /// that the result can be nullptr.
  std::optional<std::unique_ptr<CacheCost>> CC;
 
  /// Maps each loop to an index representing the optimal position within the
  /// loop-nest, as determined by the cache cost analysis.
  DenseMap<const Loop *, unsigned> CostMap;
 
  void computeIfUnitinialized();
 
public:
  CacheCostManager(Loop *OutermostLoop, LoopStandardAnalysisResults *AR,
                   DependenceInfo *DI)
      : OutermostLoop(OutermostLoop), AR(AR), DI(DI) {}
  CacheCost *getCacheCost();
  const DenseMap<const Loop *, unsigned> &getCostMap();
};
 
/// LoopInterchangeProfitability checks if it is profitable to interchange the
/// loop.
class LoopInterchangeProfitability {
public:
  LoopInterchangeProfitability(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
                               OptimizationRemarkEmitter *ORE)
      : OuterLoop(Outer), InnerLoop(Inner), SE(SE), ORE(ORE) {}
 
  /// Check if the loop interchange is profitable.
  bool isProfitable(const Loop *InnerLoop, const Loop *OuterLoop,
                    unsigned InnerLoopId, unsigned OuterLoopId,
                    CharMatrix &DepMatrix, CacheCostManager &CCM);
 
private:
  int getInstrOrderCost();
  std::optional<bool> isProfitablePerLoopCacheAnalysis(
      const DenseMap<const Loop *, unsigned> &CostMap, CacheCost *CC);
  std::optional<bool> isProfitablePerInstrOrderCost();
  std::optional<bool> isProfitableForVectorization(unsigned InnerLoopId,
                                                   unsigned OuterLoopId,
                                                   CharMatrix &DepMatrix);
  Loop *OuterLoop;
  Loop *InnerLoop;
 
  /// Scev analysis.
  ScalarEvolution *SE;
 
  /// Interface to emit optimization remarks.
  OptimizationRemarkEmitter *ORE;
};
 
/// LoopInterchangeTransform interchanges the loop.
class LoopInterchangeTransform {
public:
  LoopInterchangeTransform(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
                           LoopInfo *LI, DominatorTree *DT,
                           const LoopInterchangeLegality &LIL)
      : OuterLoop(Outer), InnerLoop(Inner), SE(SE), LI(LI), DT(DT), LIL(LIL) {}
 
  /// Interchange OuterLoop and InnerLoop.
  void transform(ArrayRef<Instruction *> DropNoWrapInsts,
                 ArrayRef<Instruction *> DropNoInfInsts);
  void reduction2Memory();
  void restructureLoops(Loop *NewInner, Loop *NewOuter,
                        BasicBlock *OrigInnerPreHeader,
                        BasicBlock *OrigOuterPreHeader);
  void removeChildLoop(Loop *OuterLoop, Loop *InnerLoop);
 
private:
  void adjustLoopBranches();
 
  Loop *OuterLoop;
  Loop *InnerLoop;
 
  /// Scev analysis.
  ScalarEvolution *SE;
 
  LoopInfo *LI;
  DominatorTree *DT;
 
  const LoopInterchangeLegality &LIL;
};
 
struct LoopInterchange {
  ScalarEvolution *SE = nullptr;
  LoopInfo *LI = nullptr;
  DependenceInfo *DI = nullptr;
  DominatorTree *DT = nullptr;
  LoopStandardAnalysisResults *AR = nullptr;
 
  /// Interface to emit optimization remarks.
  OptimizationRemarkEmitter *ORE;
 
  LoopInterchange(ScalarEvolution *SE, LoopInfo *LI, DependenceInfo *DI,
                  DominatorTree *DT, LoopStandardAnalysisResults *AR,
                  OptimizationRemarkEmitter *ORE)
      : SE(SE), LI(LI), DI(DI), DT(DT), AR(AR), ORE(ORE) {}
 
  bool run(Loop *L) {
    if (L->getParentLoop())
      return false;
    SmallVector<Loop *, 8> LoopList;
    populateWorklist(*L, LoopList);
    return processLoopList(LoopList);
  }
 
  bool run(LoopNest &LN) {
    SmallVector<Loop *, 8> LoopList(LN.getLoops());
    for (unsigned I = 1; I < LoopList.size(); ++I)
      if (LoopList[I]->getParentLoop() != LoopList[I - 1])
        return false;
    return processLoopList(LoopList);
  }
 
  unsigned selectLoopForInterchange(ArrayRef<Loop *> LoopList) {
    // TODO: Add a better heuristic to select the loop to be interchanged based
    // on the dependence matrix. Currently we select the innermost loop.
    return LoopList.size() - 1;
  }
 
  bool processLoopList(SmallVectorImpl<Loop *> &LoopList) {
    bool Changed = false;
 
    // Ensure proper loop nest depth.
    assert(hasSupportedLoopDepth(LoopList, *ORE) &&
           "Unsupported depth of loop nest.");
 
    unsigned LoopNestDepth = LoopList.size();
 
    LLVM_DEBUG({
      dbgs() << "Processing LoopList of size = " << LoopNestDepth
             << " containing the following loops:\n";
      for (auto *L : LoopList) {
        dbgs() << "  - ";
        L->print(dbgs());
      }
    });
 
    CharMatrix DependencyMatrix;
    Loop *OuterMostLoop = *(LoopList.begin());
    if (!populateDependencyMatrix(DependencyMatrix, LoopNestDepth,
                                  OuterMostLoop, DI, SE, ORE)) {
      LLVM_DEBUG(dbgs() << "Populating dependency matrix failed\n");
      return false;
    }
 
    LLVM_DEBUG(dbgs() << "Dependency matrix before interchange:\n";
               printDepMatrix(DependencyMatrix));
 
    // Get the Outermost loop exit.
    BasicBlock *LoopNestExit = OuterMostLoop->getExitBlock();
    if (!LoopNestExit) {
      LLVM_DEBUG(dbgs() << "OuterMostLoop '" << OuterMostLoop->getName()
                        << "' needs an unique exit block");
      return false;
    }
 
    unsigned SelecLoopId = selectLoopForInterchange(LoopList);
    CacheCostManager CCM(LoopList[0], AR, DI);
    // We try to achieve the globally optimal memory access for the loopnest,
    // and do interchange based on a bubble-sort fasion. We start from
    // the innermost loop, move it outwards to the best possible position
    // and repeat this process.
    for (unsigned j = SelecLoopId; j > 0; j--) {
      bool ChangedPerIter = false;
      for (unsigned i = SelecLoopId; i > SelecLoopId - j; i--) {
        bool Interchanged =
            processLoop(LoopList, i, i - 1, DependencyMatrix, CCM);
        ChangedPerIter |= Interchanged;
        Changed |= Interchanged;
      }
      // Early abort if there was no interchange during an entire round of
      // moving loops outwards.
      if (!ChangedPerIter)
        break;
    }
    return Changed;
  }
 
  bool processLoop(SmallVectorImpl<Loop *> &LoopList, unsigned InnerLoopId,
                   unsigned OuterLoopId,
                   std::vector<std::vector<char>> &DependencyMatrix,
                   CacheCostManager &CCM) {
    Loop *OuterLoop = LoopList[OuterLoopId];
    Loop *InnerLoop = LoopList[InnerLoopId];
    LLVM_DEBUG(dbgs() << "Processing InnerLoopId = " << InnerLoopId
                      << " and OuterLoopId = " << OuterLoopId << "\n");
    LoopInterchangeLegality LIL(OuterLoop, InnerLoop, SE, ORE, DT);
    if (!LIL.canInterchangeLoops(InnerLoopId, OuterLoopId, DependencyMatrix)) {
      LLVM_DEBUG(dbgs() << "Cannot prove legality, not interchanging loops '"
                        << OuterLoop->getName() << "' and '"
                        << InnerLoop->getName() << "'\n");
      return false;
    }
    LLVM_DEBUG(dbgs() << "Loops '" << OuterLoop->getName() << "' and '"
                      << InnerLoop->getName()
                      << "' are legal to interchange\n");
    LoopInterchangeProfitability LIP(OuterLoop, InnerLoop, SE, ORE);
    if (!LIP.isProfitable(InnerLoop, OuterLoop, InnerLoopId, OuterLoopId,
                          DependencyMatrix, CCM)) {
      LLVM_DEBUG(dbgs() << "Interchanging loops '" << OuterLoop->getName()
                        << "' and '" << InnerLoop->getName()
                        << "' not profitable.\n");
      return false;
    }
 
    ORE->emit([&]() {
      return OptimizationRemark(DEBUG_TYPE, "Interchanged",
                                InnerLoop->getStartLoc(),
                                InnerLoop->getHeader())
             << "Loop interchanged with enclosing loop.";
    });
 
    LoopInterchangeTransform LIT(OuterLoop, InnerLoop, SE, LI, DT, LIL);
    LIT.transform(LIL.getHasNoWrapReductions(), LIL.getHasNoInfInsts());
    LLVM_DEBUG(dbgs() << "Loops interchanged: outer loop '"
                      << OuterLoop->getName() << "' and inner loop '"
                      << InnerLoop->getName() << "'\n");
    LoopsInterchanged++;
 
    llvm::formLCSSARecursively(*OuterLoop, *DT, LI, SE);
 
    // Loops interchanged, update LoopList accordingly.
    std::swap(LoopList[OuterLoopId], LoopList[InnerLoopId]);
    // Update the DependencyMatrix
    interChangeDependencies(DependencyMatrix, InnerLoopId, OuterLoopId);
 
    LLVM_DEBUG(dbgs() << "Dependency matrix after interchange:\n";
               printDepMatrix(DependencyMatrix));
 
    return true;
  }
};
 
} // end anonymous namespace
 
bool LoopInterchangeLegality::containsUnsafeInstructions(BasicBlock *BB,
                                                         Instruction *Skip) {
  return any_of(*BB, [Skip](const Instruction &I) {
    if (&I == Skip)
      return false;
    return I.mayHaveSideEffects() || I.mayReadFromMemory();
  });
}
 
static FreezeInst *findFreezeInReNestedBlocks(Loop *OuterLoop,
                                              Loop *InnerLoop) {
  // adjustLoopBranches swaps the preheader bodies after changing their loop
  // roles, so the original outer-preheader body remains outside the new outer
  // loop and retains its execution count.
  BasicBlock *Blocks[] = {
      OuterLoop->getHeader(),
      OuterLoop->getLoopLatch(),
      InnerLoop->getLoopPreheader(),
      InnerLoop->getExitBlock(),
  };
  for (BasicBlock *BB : Blocks)
    if (BB)
      for (Instruction &I : *BB)
        if (auto *Freeze = dyn_cast<FreezeInst>(&I))
          return Freeze;
  return nullptr;
}
 
static FreezeInst *
findFreezeInInnerLatchCloneSet(Loop *InnerLoop,
                               ArrayRef<PHINode *> InnerLoopInductions) {
  // Mirror the latch-condition and induction-update operand closure cloned by
  // MoveInstructions in LoopInterchangeTransform::transform.
  SmallSetVector<Instruction *, 8> Worklist;
  auto IsDirectInnerLoopBlock = [InnerLoop](BasicBlock *BB) {
    return InnerLoop->contains(BB) &&
           none_of(InnerLoop->getSubLoops(),
                   [BB](Loop *SubLoop) { return SubLoop->contains(BB); });
  };
  auto *LatchBranch =
      dyn_cast<CondBrInst>(InnerLoop->getLoopLatch()->getTerminator());
  if (LatchBranch)
    if (auto *Condition = dyn_cast<Instruction>(LatchBranch->getCondition()))
      Worklist.insert(Condition);
 
  for (PHINode *Induction : InnerLoopInductions) {
    auto *Incoming = dyn_cast<Instruction>(
        Induction->getIncomingValueForBlock(InnerLoop->getLoopLatch()));
    if (Incoming && !is_contained(InnerLoopInductions, Incoming))
      Worklist.insert(Incoming);
  }
 
  for (unsigned I = 0; I < Worklist.size(); ++I) {
    Instruction *Current = Worklist[I];
    if (auto *Freeze = dyn_cast<FreezeInst>(Current))
      return Freeze;
    for (Value *Operand : Current->operands()) {
      auto *OperandI = dyn_cast<Instruction>(Operand);
      if (!OperandI || !IsDirectInnerLoopBlock(OperandI->getParent()) ||
          is_contained(InnerLoopInductions, OperandI))
        continue;
      Worklist.insert(OperandI);
    }
  }
  return nullptr;
}
 
bool LoopInterchangeLegality::tightlyNested(Loop *OuterLoop, Loop *InnerLoop) {
  BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
  BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
  BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
 
  LLVM_DEBUG(dbgs() << "Checking if loops '" << OuterLoop->getName()
                    << "' and '" << InnerLoop->getName()
                    << "' are tightly nested\n");
 
  // In a perfectly nested loop the outer header branches only into the inner
  // loop. If it can also reach the outer latch, it conditionally guards the
  // inner loop (an imperfect nest), so the inner loop runs on only a subset of
  // the outer iterations. Interchanging such a nest would run the inner loop on
  // every outer iteration, including the guarded-off ones, which is illegal
  // when the inner loop relies on the guard to terminate (e.g. an eq/ne exit
  // whose trip count is degenerate once the guard is false). Reject by allowing
  // the outer header to branch only into the inner loop.
  //
  // TODO: This is conservative. A guarded nest is still safe to interchange
  // when the inner loop has a computable trip count that is empty exactly when
  // the guard is false, e.g.:
  //   for (i = 0; i < N; i++)
  //     if (M > 0)                  // loop-invariant guard
  //       for (j = 0; j < M; j++)   // empty when M <= 0
  //         A[j][i] = ...;
  // Interchanging is legal here because the inner loop runs zero times on the
  // guarded-off iterations.
  for (BasicBlock *Succ : successors(OuterLoopHeader))
    if (Succ != InnerLoopPreHeader && Succ != InnerLoop->getHeader())
      return false;
 
  LLVM_DEBUG(dbgs() << "Checking instructions in Loop header and Loop latch\n");
 
  // The inner loop reduction pattern requires storing the LCSSA PHI in
  // the OuterLoop Latch. Therefore, when reduction2Memory is enabled, skip
  // that store during checks.
  Instruction *Skip = nullptr;
  assert(InnerReductions.size() <= 1 &&
         "So far we only support at most one reduction.");
  if (InnerReductions.size() == 1)
    Skip = InnerReductions[0].LcssaStore;
 
  // We do not have any basic block in between now make sure the outer header
  // and outer loop latch doesn't contain any unsafe instructions.
  if (containsUnsafeInstructions(OuterLoopHeader, Skip) ||
      containsUnsafeInstructions(OuterLoopLatch, Skip))
    return false;
 
  // Also make sure the inner loop preheader does not contain any unsafe
  // instructions. Note that all instructions in the preheader will be moved to
  // the outer loop header when interchanging.
  if (InnerLoopPreHeader != OuterLoopHeader &&
      containsUnsafeInstructions(InnerLoopPreHeader, Skip))
    return false;
 
  BasicBlock *InnerLoopExit = InnerLoop->getExitBlock();
  // Ensure the inner loop exit block flows to the outer loop latch possibly
  // through empty blocks.
  const BasicBlock &SuccInner =
      LoopNest::skipEmptyBlockUntil(InnerLoopExit, OuterLoopLatch);
  if (&SuccInner != OuterLoopLatch) {
    LLVM_DEBUG(dbgs() << "Inner loop exit block " << *InnerLoopExit
                      << " does not lead to the outer loop latch.\n";);
    return false;
  }
  // The inner loop exit block does flow to the outer loop latch and not some
  // other BBs, now make sure it contains safe instructions, since it will be
  // moved into the (new) inner loop after interchange.
  if (containsUnsafeInstructions(InnerLoopExit, Skip))
    return false;
 
  LLVM_DEBUG(dbgs() << "Loops are perfectly nested\n");
  // We have a perfect loop nest.
  return true;
}
 
bool LoopInterchangeLegality::isLoopStructureUnderstood() {
  BasicBlock *InnerLoopPreheader = InnerLoop->getLoopPreheader();
  for (PHINode *InnerInduction : InnerLoopInductions) {
    unsigned Num = InnerInduction->getNumOperands();
    for (unsigned i = 0; i < Num; ++i) {
      Value *Val = InnerInduction->getOperand(i);
      if (isa<Constant>(Val))
        continue;
      Instruction *I = dyn_cast<Instruction>(Val);
      if (!I)
        return false;
      // TODO: Handle triangular loops.
      // e.g. for(int i=0;i<N;i++)
      //        for(int j=i;j<N;j++)
      unsigned IncomBlockIndx = PHINode::getIncomingValueNumForOperand(i);
      if (InnerInduction->getIncomingBlock(IncomBlockIndx) ==
              InnerLoopPreheader &&
          !OuterLoop->isLoopInvariant(I)) {
        return false;
      }
    }
  }
 
  // TODO: Handle triangular loops of another form.
  // e.g. for(int i=0;i<N;i++)
  //        for(int j=0;j<i;j++)
  // or,
  //      for(int i=0;i<N;i++)
  //        for(int j=0;j*i<N;j++)
  BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
  CondBrInst *InnerLoopLatchBI =
      dyn_cast<CondBrInst>(InnerLoopLatch->getTerminator());
  if (!InnerLoopLatchBI)
    return false;
 
  CmpInst *InnerLoopCmp = dyn_cast<CmpInst>(InnerLoopLatchBI->getCondition());
  if (!InnerLoopCmp)
    return false;
 
  Value *Op0 = InnerLoopCmp->getOperand(0);
  Value *Op1 = InnerLoopCmp->getOperand(1);
 
  // LHS and RHS of the inner loop exit condition, e.g.,
  // in "for(int j=0;j<i;j++)", LHS is j and RHS is i.
  Value *Left = nullptr;
  Value *Right = nullptr;
 
  // Check if V only involves inner loop induction variable.
  // Return true if V is InnerInduction, or a cast from
  // InnerInduction, or a binary operator that involves
  // InnerInduction and a constant.
  std::function<bool(Value *)> IsPathToInnerIndVar;
  IsPathToInnerIndVar = [this, &IsPathToInnerIndVar](const Value *V) -> bool {
    if (llvm::is_contained(InnerLoopInductions, V))
      return true;
    if (isa<Constant>(V))
      return true;
    const Instruction *I = dyn_cast<Instruction>(V);
    if (!I)
      return false;
    if (isa<CastInst>(I))
      return IsPathToInnerIndVar(I->getOperand(0));
    if (isa<BinaryOperator>(I))
      return IsPathToInnerIndVar(I->getOperand(0)) &&
             IsPathToInnerIndVar(I->getOperand(1));
    return false;
  };
 
  // In case of multiple inner loop indvars, it is okay if LHS and RHS
  // are both inner indvar related variables.
  if (IsPathToInnerIndVar(Op0) && IsPathToInnerIndVar(Op1))
    return true;
 
  // Otherwise we check if the cmp instruction compares an inner indvar
  // related variable (Left) with a outer loop invariant (Right).
  if (IsPathToInnerIndVar(Op0) && !isa<Constant>(Op0)) {
    Left = Op0;
    Right = Op1;
  } else if (IsPathToInnerIndVar(Op1) && !isa<Constant>(Op1)) {
    Left = Op1;
    Right = Op0;
  }
 
  if (Left == nullptr)
    return false;
 
  const SCEV *S = SE->getSCEV(Right);
  if (!SE->isLoopInvariant(S, OuterLoop))
    return false;
 
  return true;
}
 
// If SV is a LCSSA PHI node with a single incoming value, return the incoming
// value.
static Value *followLCSSA(Value *SV) {
  PHINode *PHI = dyn_cast<PHINode>(SV);
  if (!PHI)
    return SV;
 
  if (PHI->getNumIncomingValues() != 1)
    return SV;
  return followLCSSA(PHI->getIncomingValue(0));
}
 
static bool checkReductionKind(Loop *L, PHINode *PHI,
                               SmallVectorImpl<Instruction *> &HasNoWrapInsts,
                               SmallVectorImpl<Instruction *> &HasNoInfInsts) {
  RecurrenceDescriptor RD;
  if (RecurrenceDescriptor::isReductionPHI(PHI, L, RD)) {
    // Detect floating point reduction only when it can be reordered.
    if (RD.getExactFPMathInst() != nullptr)
      return false;
 
    // The extra uses of a reduction phi outside of its reduction chain make
    // the order in which the elements are visited observable.
    if (RD.hasUsesOutsideReductionChain())
      return false;
 
    RecurKind RK = RD.getRecurrenceKind();
    switch (RK) {
    case RecurKind::Or:
    case RecurKind::And:
    case RecurKind::Xor:
    case RecurKind::SMin:
    case RecurKind::SMax:
    case RecurKind::UMin:
    case RecurKind::UMax:
      return true;
 
    // Interchanging the loops that contain AnyOf reduction is not always legal.
    // Especially, when the result value of the AnyOf is not loop-invariant with
    // respect to the outer loop, interchanging may change the semantics. The
    // following is an example of such case:
    //   int A = {{ 1, 0 }, { 0, 1 }};
    //   int red = 0;
    //   for (int i = 0; i < 2; i++)
    //     for (int j = 0; j < 2; j++)
    //       red = (A[j][i] == 0) ? i + 1 : red;
    //
    // TODO: We may be able to support interchanging loops with AnyOf reduction
    // by checking the operand of the reduction is loop-invariant with respect
    // to the outer loop as well.
    case RecurKind::AnyOf:
      return false;
 
    // Changing the order of floating-point operations may alter the results. If
    // a certain instruction has the ninf flag, it means that reordering can
    // produce a poison value, which may lead to undefined behavior. To prevent
    // this, we must drop the ninf flags if we decide to apply the
    // transformation.
    case RecurKind::FAdd:
    case RecurKind::FMul:
    case RecurKind::FMin:
    case RecurKind::FMax:
    case RecurKind::FMinimum:
    case RecurKind::FMaximum:
    case RecurKind::FMinimumNum:
    case RecurKind::FMaximumNum:
    case RecurKind::FMulAdd:
      for (Instruction *I : RD.getReductionOpChain(PHI, L))
        if (isa<FPMathOperator>(I) && I->hasNoInfs())
          HasNoInfInsts.push_back(I);
      return true;
 
    // Change the order of integer addition/multiplication may change the
    // semantics. Consider the following case:
    //
    //  int A[2][2] = {{ INT_MAX, INT_MAX }, { INT_MIN, INT_MIN }};
    //  int sum = 0;
    //  for (int i = 0; i < 2; i++)
    //    for (int j = 0; j < 2; j++)
    //      sum += A[j][i];
    //
    // If the above loops are exchanged, the addition will cause an
    // overflow. To prevent this, we must drop the nuw/nsw flags from the
    // addition/multiplication instructions when we actually exchanges the
    // loops.
    case RecurKind::Add:
    case RecurKind::Mul: {
      unsigned OpCode = RecurrenceDescriptor::getOpcode(RK);
      SmallVector<Instruction *, 4> Ops = RD.getReductionOpChain(PHI, L);
 
      // Bail out when we fail to collect reduction instructions chain.
      if (Ops.empty())
        return false;
 
      for (Instruction *I : Ops) {
        assert(I->getOpcode() == OpCode &&
               "Expected the instruction to be the reduction operation");
        (void)OpCode;
 
        // If the instruction has nuw/nsw flags, we must drop them when the
        // transformation is actually performed.
        if (I->hasNoSignedWrap() || I->hasNoUnsignedWrap())
          HasNoWrapInsts.push_back(I);
      }
      return true;
    }
 
    default:
      return false;
    }
  } else
    return false;
}
 
// Check V's users to see if it is involved in a reduction in L.
static PHINode *
findInnerReductionPhi(Loop *L, Value *V,
                      SmallVectorImpl<Instruction *> &HasNoWrapInsts,
                      SmallVectorImpl<Instruction *> &HasNoInfInsts) {
  // Reduction variables cannot be constants.
  if (isa<Constant>(V))
    return nullptr;
 
  for (Value *User : V->users()) {
    if (PHINode *PHI = dyn_cast<PHINode>(User)) {
      if (PHI->getNumIncomingValues() == 1)
        continue;
 
      if (checkReductionKind(L, PHI, HasNoWrapInsts, HasNoInfInsts))
        return PHI;
      else
        return nullptr;
    }
  }
 
  return nullptr;
}
 
bool LoopInterchangeLegality::isInnerReduction(
    Loop *L, PHINode *Phi, SmallVectorImpl<Instruction *> &HasNoWrapInsts) {
 
  // Only support reduction2Mem when the loop nest to be interchanged is
  // the innermost two loops.
  if (!L->isInnermost()) {
    LLVM_DEBUG(dbgs() << "Only supported when the loop is the innermost.\n");
    ORE->emit([&]() {
      return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedInnerReduction",
                                      L->getStartLoc(), L->getHeader())
             << "Only supported when the loop is the innermost.";
    });
    return false;
  }
 
  if (Phi->getNumIncomingValues() != 2)
    return false;
 
  Value *Init = Phi->getIncomingValueForBlock(L->getLoopPreheader());
  Value *Next = Phi->getIncomingValueForBlock(L->getLoopLatch());
 
  // So far only supports constant initial value.
  if (!isa<Constant>(Init)) {
    LLVM_DEBUG(
        dbgs()
        << "Only supported for the reduction with a constant initial value.\n");
    ORE->emit([&]() {
      return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedInnerReduction",
                                      L->getStartLoc(), L->getHeader())
             << "Only supported for the reduction with a constant initial "
                "value.";
    });
    return false;
  }
 
  // The reduction result must live in the inner loop.
  if (Instruction *I = dyn_cast<Instruction>(Next)) {
    BasicBlock *BB = I->getParent();
    if (!L->contains(BB))
      return false;
  }
 
  // The reduction should have only one user.
  if (!Phi->hasOneUser())
    return false;
 
  // Check the reduction kind.
  if (!checkReductionKind(L, Phi, HasNoWrapInsts, HasNoInfInsts))
    return false;
 
  // Find lcssa_phi in OuterLoop's Latch
  BasicBlock *ExitBlock = L->getExitBlock();
  if (!ExitBlock)
    return false;
 
  PHINode *Lcssa = NULL;
  for (auto *U : Next->users()) {
    if (auto *P = dyn_cast<PHINode>(U)) {
      if (P == Phi)
        continue;
 
      if (Lcssa == NULL && P->getParent() == ExitBlock &&
          P->getIncomingValueForBlock(L->getLoopLatch()) == Next)
        Lcssa = P;
      else
        return false;
    } else
      return false;
  }
  if (!Lcssa)
    return false;
 
  if (!Lcssa->hasOneUser()) {
    LLVM_DEBUG(dbgs() << "Only supported when the reduction is used once in "
                         "the outer loop.\n");
    ORE->emit([&]() {
      return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedInnerReduction",
                                      L->getStartLoc(), L->getHeader())
             << "Only supported when the reduction is used once in the outer "
                "loop.";
    });
    return false;
  }
 
  StoreInst *LcssaStore =
      dyn_cast<StoreInst>(Lcssa->getUniqueUndroppableUser());
  if (!LcssaStore || LcssaStore->getParent() != ExitBlock)
    return false;
 
  Value *MemRef = LcssaStore->getOperand(1);
  Type *ElemTy = LcssaStore->getOperand(0)->getType();
 
  // LcssaStore stores the reduction result in BB.
  // When the reduction is initialized from a constant value, we need to load
  // from the memory object into the target basic block of the inner loop. This
  // means the memory reference was used prematurely. So we must ensure that the
  // memory reference does not dominate the target basic block.
  // TODO: Move the memory reference definition into the loop header.
  if (!DT->dominates(dyn_cast<Instruction>(MemRef), L->getHeader())) {
    LLVM_DEBUG(dbgs() << "Only supported when memory reference dominate "
                         "the inner loop.\n");
    ORE->emit([&]() {
      return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedInnerReduction",
                                      L->getStartLoc(), L->getHeader())
             << "Only supported when memory reference dominate the inner "
                "loop.";
    });
    return false;
  }
 
  // Found a reduction in the inner loop.
  InnerReduction SR;
  SR.Reduction = Phi;
  SR.Init = Init;
  SR.Next = Next;
  SR.LcssaPhi = Lcssa;
  SR.LcssaStore = LcssaStore;
  SR.MemRef = MemRef;
  SR.ElemTy = ElemTy;
 
  InnerReductions.push_back(SR);
  return true;
}
 
bool LoopInterchangeLegality::checkInductionsAndReductions(Loop *OuterLoop) {
  auto ChildLoop = [](Loop *L) {
    assert(L->getSubLoops().size() <= 1 &&
           "Expect at most one child loop for now.");
    return L->getSubLoops().empty() ? nullptr : L->getSubLoops().front();
  };
 
  Loop *InnerLoop = ChildLoop(OuterLoop);
  for (Loop *CurLoop = OuterLoop; CurLoop; CurLoop = ChildLoop(CurLoop)) {
    for (PHINode &PHI : CurLoop->getHeader()->phis()) {
      InductionDescriptor ID;
      if (InductionDescriptor::isInductionPHI(&PHI, CurLoop, SE, ID)) {
        if (CurLoop == InnerLoop) {
          const SCEV *Step = ID.getStep();
          if (!SE->isLoopInvariant(Step, OuterLoop))
            return false;
          InnerLoopInductions.push_back(&PHI);
        }
        continue;
      }
 
      if (CurLoop == OuterLoop) {
        // PHIs in inner loops need to be part of a reduction in the outer loop,
        if (PHI.getNumIncomingValues() != 2) {
          LLVM_DEBUG(dbgs() << "Only PHI nodes in the outer loop header with 2 "
                               "incoming values are supported.\n");
          return false;
        }
        // Check if we have a PHI node in the outer loop that has a reduction
        // result from the inner loop as an incoming value.
        Value *V = followLCSSA(
            PHI.getIncomingValueForBlock(OuterLoop->getLoopLatch()));
        PHINode *InnerRedPhi = findInnerReductionPhi(
            InnerLoop, V, HasNoWrapReductions, HasNoInfInsts);
 
        // Reject if PHI has users other than InnerRedPhi. The typical case is
        // as follows:
        //
        //   o.header:
        //     %red.o = phi [ 0, ... ], [ %red.next, %o.latch ]
        //     br label %i.header
        //
        //   i.header:
        //     %red.i = phi [ %red.o, %o.header ], [ %red.next, %i.latch ]
        //     br label %i.body
        //
        //   i.body:
        //     store %red.o to %mem
        //     ...
        //
        if (!InnerRedPhi ||
            !llvm::is_contained(InnerRedPhi->incoming_values(), &PHI) ||
            !all_of(PHI.users(),
                    [InnerRedPhi](User *U) { return U == InnerRedPhi; })) {
          LLVM_DEBUG(
              dbgs()
              << "Failed to recognize PHI as an induction or reduction.\n");
          ORE->emit([&]() {
            return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedPHIOuter",
                                            OuterLoop->getStartLoc(),
                                            OuterLoop->getHeader())
                   << "Only outer loops with induction or reduction PHI nodes "
                      "can be interchanged currently.";
          });
          return false;
        }
 
        OuterInnerReductions.insert(&PHI);
        OuterInnerReductions.insert(InnerRedPhi);
      } else {
        if (OuterInnerReductions.count(&PHI)) {
          LLVM_DEBUG(dbgs() << "Found a reduction across the outer loop.\n");
        } else if (EnableReduction2Memory &&
                   isInnerReduction(CurLoop, &PHI, HasNoWrapReductions)) {
          LLVM_DEBUG(dbgs() << "Found a reduction in the inner loop: \n"
                            << PHI << '\n');
        } else {
          ORE->emit([&]() {
            return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedPHIInner",
                                            CurLoop->getStartLoc(),
                                            CurLoop->getHeader())
                   << "Only inner loops with induction or reduction PHI nodes "
                      "can be interchanged currently.";
          });
          return false;
        }
      }
    }
 
    // For now we only support at most one reduction.
    if (InnerReductions.size() > 1) {
      LLVM_DEBUG(dbgs() << "Only supports at most one reduction.\n");
      ORE->emit([&]() {
        return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedInnerReduction",
                                        CurLoop->getStartLoc(),
                                        CurLoop->getHeader())
               << "Only supports at most one reduction.";
      });
      return false;
    }
  }
 
  return !InnerLoopInductions.empty();
}
 
// This function indicates the current limitations in the transform as a result
// of which we do not proceed.
bool LoopInterchangeLegality::currentLimitations() {
  BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
 
  // transform currently expects the loop latches to also be the exiting
  // blocks.
  if (InnerLoop->getExitingBlock() != InnerLoopLatch ||
      OuterLoop->getExitingBlock() != OuterLoop->getLoopLatch() ||
      !isa<CondBrInst>(InnerLoopLatch->getTerminator()) ||
      !isa<CondBrInst>(OuterLoop->getLoopLatch()->getTerminator())) {
    LLVM_DEBUG(
        dbgs() << "Loops where the latch is not the exiting block are not"
               << " supported currently.\n");
    ORE->emit([&]() {
      return OptimizationRemarkMissed(DEBUG_TYPE, "ExitingNotLatch",
                                      OuterLoop->getStartLoc(),
                                      OuterLoop->getHeader())
             << "Loops where the latch is not the exiting block cannot be"
                " interchange currently.";
    });
    return true;
  }
 
  // TODO: Triangular loops are not handled for now.
  if (!isLoopStructureUnderstood()) {
    LLVM_DEBUG(dbgs() << "Loop structure not understood by pass\n");
    ORE->emit([&]() {
      return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedStructureInner",
                                      InnerLoop->getStartLoc(),
                                      InnerLoop->getHeader())
             << "Inner loop structure not understood currently.";
    });
    return true;
  }
 
  // Currently, we do not support loops that have a predecessor entering the
  // loop via an indirectbr.
  for (Loop *L : {OuterLoop, InnerLoop}) {
    BasicBlock *Header = L->getHeader();
    for (BasicBlock *Pred : predecessors(Header)) {
      if (L->contains(Pred))
        continue;
      if (isa<IndirectBrInst>(Pred->getTerminator())) {
        LLVM_DEBUG(
            dbgs() << "Indirect branch found in the loop predecessor.\n");
        ORE->emit([&]() {
          return OptimizationRemarkMissed(DEBUG_TYPE, "IndirectBranchPreheader",
                                          L->getStartLoc(), L->getHeader())
                 << "Indirect branch found in the loop predecessor.";
        });
        return true;
      }
    }
  }
 
  // Currently, we do not support loops where the inner loop header has
  // duplicate successors.
  SmallPtrSet<BasicBlock *, 2> InnerLoopHeaderSuccs;
  for (BasicBlock *Succ : successors(InnerLoop->getHeader()))
    if (!InnerLoopHeaderSuccs.insert(Succ).second)
      return true;
 
  return false;
}
 
/// We currently only support LCSSA PHI nodes in the inner loop exit if their
/// users are either of the following:
///
/// - Reduction PHIs
/// - PHIs outside the outer loop
/// - PHIs belonging to the latch of the outer loop
///
/// These conditions mean that we are only interested in the final value after
/// the inner loop.
static bool
areInnerLoopExitPHIsSupported(Loop *OuterL, Loop *InnerL,
                              SmallPtrSetImpl<PHINode *> &Reductions,
                              PHINode *LcssaReduction) {
  BasicBlock *InnerExit = InnerL->getUniqueExitBlock();
  for (PHINode &PHI : InnerExit->phis()) {
    // The reduction LCSSA PHI will have only one incoming block, which comes
    // from the loop latch.
    if (PHI.getNumIncomingValues() > 1)
      return false;
    // The reduction LCSSA PHI's store user is rewritten by reduction2Memory();
    // skip its user-check but keep validating the remaining LCSSA PHIs.
    if (&PHI == LcssaReduction)
      continue;
    if (any_of(PHI.users(), [&Reductions, OuterL](User *U) {
          PHINode *PN = dyn_cast<PHINode>(U);
          if (!PN)
            return true;
          if (Reductions.count(PN))
            return false;
          BasicBlock *PB = PN->getParent();
          if (!OuterL->contains(PB))
            return false;
          return PB != OuterL->getLoopLatch();
        }))
      return false;
  }
  return true;
}
 
// We currently support LCSSA PHI nodes in the outer loop exit, if their
// incoming values do not come from the outer loop latch or if the
// outer loop latch has a single predecessor. In that case, the value will
// be available if both the inner and outer loop conditions are true, which
// will still be true after interchanging. If we have multiple predecessor,
// that may not be the case, e.g. because the outer loop latch may be executed
// if the inner loop is not executed.
static bool areOuterLoopExitPHIsSupported(Loop *OuterLoop, Loop *InnerLoop) {
  BasicBlock *LoopNestExit = OuterLoop->getUniqueExitBlock();
  for (PHINode &PHI : LoopNestExit->phis()) {
    for (Value *Incoming : PHI.incoming_values()) {
      Instruction *IncomingI = dyn_cast<Instruction>(Incoming);
      if (!IncomingI || IncomingI->getParent() != OuterLoop->getLoopLatch())
        continue;
 
      // The incoming value is defined in the outer loop latch. Currently we
      // only support that in case the outer loop latch has a single predecessor.
      // This guarantees that the outer loop latch is executed if and only if
      // the inner loop is executed (because tightlyNested() guarantees that the
      // outer loop header only branches to the inner loop or the outer loop
      // latch).
      // FIXME: We could weaken this logic and allow multiple predecessors,
      //        if the values are produced outside the loop latch. We would need
      //        additional logic to update the PHI nodes in the exit block as
      //        well.
      if (OuterLoop->getLoopLatch()->getUniquePredecessor() == nullptr)
        return false;
    }
  }
  return true;
}
 
/// The transform partially clones the inner loop's latch block, but PHI nodes
/// cannot be cloned this way. This function follows the instruction trees that
/// would be cloned and checks whether any PHI node other than the induction
/// PHIs feeds them. If such a PHI is found, the interchange is rejected.
///
/// TODO: This check strongly depends on the current implementation of the
/// transform. Ideally, the transform should be able to handle such PHI nodes in
/// the inner loop latch.
static bool areInnerLoopLatchPHIsSupported(Loop *InnerLoop,
                                           ArrayRef<PHINode *> InductionPHIs) {
  BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
 
  // Seed the worklist with the roots of the use-def chains the transform
  // clones: the latch's exit condition and the incoming values of the induction
  // PHIs from the latch.
  SmallSetVector<Instruction *, 8> Worklist;
  if (auto *LatchBI = dyn_cast<CondBrInst>(InnerLoopLatch->getTerminator()))
    if (auto *CondI = dyn_cast<Instruction>(LatchBI->getCondition()))
      Worklist.insert(CondI);
  for (PHINode *InductionPHI : InductionPHIs) {
    if (auto *IncomingI = dyn_cast<Instruction>(
            InductionPHI->getIncomingValueForBlock(InnerLoopLatch)))
      if (!is_contained(InductionPHIs, IncomingI))
        Worklist.insert(IncomingI);
  }
 
  // Bail if a PHI node other than the induction PHIs feeds the cloned
  // instructions, walking the operand trees within the inner loop.
  SmallPtrSet<Instruction *, 4> InductionPHISet(InductionPHIs.begin(),
                                                InductionPHIs.end());
  for (unsigned I = 0; I < Worklist.size(); ++I) {
    Instruction *Cur = Worklist[I];
    if (isa<PHINode>(Cur) && !InductionPHISet.contains(Cur))
      return false;
    for (Value *Op : Cur->operands())
      if (auto *OpI = dyn_cast<Instruction>(Op))
        if (InnerLoop->contains(OpI))
          Worklist.insert(OpI);
  }
  return true;
}
 
bool LoopInterchangeLegality::canInterchangeLoops(unsigned InnerLoopId,
                                                  unsigned OuterLoopId,
                                                  CharMatrix &DepMatrix) {
  if (!isLegalToInterChangeLoops(DepMatrix, InnerLoopId, OuterLoopId)) {
    LLVM_DEBUG(dbgs() << "Failed interchange InnerLoopId = " << InnerLoopId
                      << " and OuterLoopId = " << OuterLoopId
                      << " due to dependence\n");
    ORE->emit([&]() {
      return OptimizationRemarkMissed(DEBUG_TYPE, "Dependence",
                                      InnerLoop->getStartLoc(),
                                      InnerLoop->getHeader())
             << "Cannot interchange loops due to dependences.";
    });
    return false;
  }
  // Check if outer and inner loop contain legal instructions only.
  for (auto *BB : OuterLoop->blocks())
    for (Instruction &I : *BB) {
      // Loads and stores are checked separately, so we can skip them here.
      if (isa<LoadInst, StoreInst, PseudoProbeInst>(&I))
        continue;
 
      // We cannot ignore potential memory reads, e.g., loads inside the called
      // function.
      if (!I.mayHaveSideEffects() && !I.mayReadFromMemory())
        continue;
 
      LLVM_DEBUG(
          dbgs()
          << "Loops contain instructions that cannot be safely interchanged\n");
      ORE->emit([&]() {
        return OptimizationRemarkMissed(DEBUG_TYPE, "UnsafeInst",
                                        I.getDebugLoc(), I.getParent())
               << "Cannot interchange loops due to instruction that is "
                  "potentially unsafe to interchange.";
      });
 
      return false;
    }
 
  if (!checkInductionsAndReductions(OuterLoop)) {
    LLVM_DEBUG(dbgs() << "Failed to find inner loop inductions or found "
                         "unsupported reductions.\n");
    return false;
  }
 
  if (!areInnerLoopLatchPHIsSupported(InnerLoop, InnerLoopInductions)) {
    LLVM_DEBUG(dbgs() << "Found unsupported PHI nodes in inner loop latch.\n");
    ORE->emit([&]() {
      return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedInnerLatchPHI",
                                      InnerLoop->getStartLoc(),
                                      InnerLoop->getHeader())
             << "Cannot interchange loops because unsupported PHI nodes found "
                "in inner loop latch.";
    });
    return false;
  }
 
  FreezeInst *Freeze = findFreezeInReNestedBlocks(OuterLoop, InnerLoop);
  if (!Freeze)
    Freeze = findFreezeInInnerLatchCloneSet(InnerLoop, InnerLoopInductions);
  if (Freeze) {
    LLVM_DEBUG(dbgs() << "Interchange would re-nest or duplicate freeze\n");
    ORE->emit([&]() {
      return OptimizationRemarkMissed(DEBUG_TYPE, "UnsafeInst",
                                      Freeze->getDebugLoc(),
                                      Freeze->getParent())
             << "Cannot interchange loops because re-nesting or duplicating "
                "freeze may change its sampling behavior.";
    });
    return false;
  }
 
  // TODO: The loops could not be interchanged due to current limitations in the
  // transform module.
  if (currentLimitations()) {
    LLVM_DEBUG(dbgs() << "Not legal because of current transform limitation\n");
    return false;
  }
 
  // Check if the loops are tightly nested.
  if (!tightlyNested(OuterLoop, InnerLoop)) {
    LLVM_DEBUG(dbgs() << "Loops not tightly nested\n");
    ORE->emit([&]() {
      return OptimizationRemarkMissed(DEBUG_TYPE, "NotTightlyNested",
                                      InnerLoop->getStartLoc(),
                                      InnerLoop->getHeader())
             << "Cannot interchange loops because they are not tightly "
                "nested.";
    });
    return false;
  }
 
  // The LCSSA PHI for the reduction has passed checks before; its user
  // is a store instruction.
  PHINode *LcssaReduction = nullptr;
  assert(InnerReductions.size() <= 1 &&
         "So far we only support at most one reduction.");
  if (InnerReductions.size() == 1)
    LcssaReduction = InnerReductions[0].LcssaPhi;
 
  if (!areInnerLoopExitPHIsSupported(OuterLoop, InnerLoop, OuterInnerReductions,
                                     LcssaReduction)) {
    LLVM_DEBUG(dbgs() << "Found unsupported PHI nodes in inner loop exit.\n");
    ORE->emit([&]() {
      return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedExitPHI",
                                      InnerLoop->getStartLoc(),
                                      InnerLoop->getHeader())
             << "Found unsupported PHI node in loop exit.";
    });
    return false;
  }
 
  if (!areOuterLoopExitPHIsSupported(OuterLoop, InnerLoop)) {
    LLVM_DEBUG(dbgs() << "Found unsupported PHI nodes in outer loop exit.\n");
    ORE->emit([&]() {
      return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedExitPHI",
                                      OuterLoop->getStartLoc(),
                                      OuterLoop->getHeader())
             << "Found unsupported PHI node in loop exit.";
    });
    return false;
  }
 
  if (any_of(OuterLoop->getLoopLatch()->phis(),
             [](PHINode &PHI) { return PHI.getNumIncomingValues() != 1; })) {
    LLVM_DEBUG(dbgs() << "Only outer loop latch PHI nodes with one incoming "
                         "value are supported.\n");
    ORE->emit([&]() {
      return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedLatchPHI",
                                      OuterLoop->getStartLoc(),
                                      OuterLoop->getHeader())
             << "Only outer loop latch PHI nodes with one incoming value are "
                "supported.";
    });
    return false;
  }
 
  // Regarding def-use chains that begin at an LCSSA PHI in the inner loop exit
  // and end at any instruction in the outer loop latch, we currently support
  // only the case where the chain contains only PHI nodes. Since we already
  // call `tightlyNested()`, we know that if there is a def-use chain that we
  // don't support (i.e., a chain that contains a non-PHI user), then the
  // non-PHI user must be in the outer loop latch.
  if (InnerLoop->getExitBlock() != OuterLoop->getLoopLatch())
    for (PHINode &PHI : OuterLoop->getLoopLatch()->phis())
      if (any_of(PHI.users(), [](const User *U) { return !isa<PHINode>(U); })) {
        LLVM_DEBUG(dbgs() << "Outer loop latch PHI has a non-PHI user.\n");
        ORE->emit([&]() {
          return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedLatchPHI",
                                          OuterLoop->getStartLoc(),
                                          OuterLoop->getHeader())
                 << "Cannot interchange loops because an outer loop latch PHI "
                    "node has a non-PHI user.";
        });
        return false;
      }
 
  return true;
}
 
void CacheCostManager::computeIfUnitinialized() {
  if (CC.has_value())
    return;
 
  LLVM_DEBUG(dbgs() << "Compute CacheCost.\n");
  CC = CacheCost::getCacheCost(*OutermostLoop, *AR, *DI);
  // Obtain the loop vector returned from loop cache analysis beforehand,
  // and put each <Loop, index> pair into a map for constant time query
  // later. Indices in loop vector reprsent the optimal order of the
  // corresponding loop, e.g., given a loopnest with depth N, index 0
  // indicates the loop should be placed as the outermost loop and index N
  // indicates the loop should be placed as the innermost loop.
  //
  // For the old pass manager CacheCost would be null.
  if (*CC != nullptr)
    for (const auto &[Idx, Cost] : enumerate((*CC)->getLoopCosts()))
      CostMap[Cost.first] = Idx;
}
 
CacheCost *CacheCostManager::getCacheCost() {
  computeIfUnitinialized();
  return CC->get();
}
 
const DenseMap<const Loop *, unsigned> &CacheCostManager::getCostMap() {
  computeIfUnitinialized();
  return CostMap;
}
 
/// If \S contains an affine addrec for \p L, return the step recurrence of it.
/// If \S is loop invariant with respect to \p L, return nullptr. Otherwise,
/// return std::nullopt, which indicates we cannot determine the coefficient of
/// the addrec for \p L in \S.
/// TODO: Handle more complex cases. Maybe using SCEVTraversal is a good way to
/// do that.
static std::optional<const SCEV *>
getAddRecCoefficient(ScalarEvolution &SE, const SCEV *S, const Loop *L) {
  const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S);
  if (!AR) {
    if (SE.isLoopInvariant(S, L))
      return nullptr;
    return std::nullopt;
  }
 
  if (!AR->isAffine()) {
    LLVM_DEBUG(dbgs() << "Unexpected non-affine addrec\n");
    return std::nullopt;
  }
 
  std::optional<const SCEV *> Coeff =
      getAddRecCoefficient(SE, AR->getStart(), L);
  if (!Coeff.has_value())
    return std::nullopt;
 
  if (AR->getLoop() == L) {
    assert(!*Coeff && "Found more than one addrec for the same loop");
    Coeff = AR->getStepRecurrence(SE);
  }
  return Coeff;
}
 
int LoopInterchangeProfitability::getInstrOrderCost() {
  SmallPtrSet<const SCEV *, 4> GoodBasePtrs, BadBasePtrs;
  for (BasicBlock *BB : InnerLoop->blocks()) {
    for (Instruction &Ins : *BB) {
      if (!isa<LoadInst, StoreInst>(&Ins))
        continue;
      const SCEV *Access = SE->getSCEV(getLoadStorePointerOperand(&Ins));
      const SCEV *BasePtr = SE->getPointerBase(Access);
      std::optional<const SCEV *> OuterCoeff =
          getAddRecCoefficient(*SE, Access, OuterLoop);
      std::optional<const SCEV *> InnerCoeff =
          getAddRecCoefficient(*SE, Access, InnerLoop);
 
      if (!OuterCoeff.has_value() || !*OuterCoeff || !InnerCoeff.has_value() ||
          !*InnerCoeff)
        continue;
 
      // This heuristic assumes that a smaller step recurrence implies that the
      // induction variable corresponding to the loop is used in the inner
      // dimension of the array. Placing such a loop in the inner position would
      // be beneficial in terms of locality. If the array access is of the form
      // like `A[3*i + 2*j]`, this heuristic may lead to an unprofitable
      // interchange, but we expect such cases to be rare.
      const SCEV *OuterStep = SE->getAbsExpr(*OuterCoeff, /*IsNSW=*/false);
      const SCEV *InnerStep = SE->getAbsExpr(*InnerCoeff, /*IsNSW=*/false);
      // If we find the inner induction after an outer induction e.g.
      //
      //   for(int i=0;i<N;i++)
      //     for(int j=0;j<N;j++)
      //       A[i][j] = A[i-1][j-1]+k;
      //
      //
      // then it is a good order. If we find the outer induction after an inner
      // induction e.g.
      //
      //   for(int i=0;i<N;i++)
      //     for(int j=0;j<N;j++)
      //       A[j][i] = A[j-1][i-1]+k;
      //
      // then it is a bad order.
      //
      // To avoid counting the same base pointers multiple times, we deduplicate
      // them by using a set of base pointers.
      if (SE->isKnownPredicate(ICmpInst::ICMP_SLT, InnerStep, OuterStep))
        GoodBasePtrs.insert(BasePtr);
      else if (SE->isKnownPredicate(ICmpInst::ICMP_SLT, OuterStep, InnerStep))
        BadBasePtrs.insert(BasePtr);
    }
  }
 
  int GoodOrder = GoodBasePtrs.size();
  int BadOrder = BadBasePtrs.size();
  return GoodOrder - BadOrder;
}
 
std::optional<bool>
LoopInterchangeProfitability::isProfitablePerLoopCacheAnalysis(
    const DenseMap<const Loop *, unsigned> &CostMap, CacheCost *CC) {
  // This is the new cost model returned from loop cache analysis.
  // A smaller index means the loop should be placed an outer loop, and vice
  // versa.
  auto InnerLoopIt = CostMap.find(InnerLoop);
  if (InnerLoopIt == CostMap.end())
    return std::nullopt;
  auto OuterLoopIt = CostMap.find(OuterLoop);
  if (OuterLoopIt == CostMap.end())
    return std::nullopt;
 
  if (CC->getLoopCost(*OuterLoop) == CC->getLoopCost(*InnerLoop))
    return std::nullopt;
  unsigned InnerIndex = InnerLoopIt->second;
  unsigned OuterIndex = OuterLoopIt->second;
  LLVM_DEBUG(dbgs() << "InnerIndex = " << InnerIndex
                    << ", OuterIndex = " << OuterIndex << "\n");
  assert(InnerIndex != OuterIndex && "CostMap should assign unique "
                                     "numbers to each loop");
  return std::optional<bool>(InnerIndex < OuterIndex);
}
 
std::optional<bool>
LoopInterchangeProfitability::isProfitablePerInstrOrderCost() {
  // Legacy cost model: this is rough cost estimation algorithm. It counts the
  // good and bad order of induction variables in the instruction and allows
  // reordering if number of bad orders is more than good.
  int Cost = getInstrOrderCost();
  LLVM_DEBUG(dbgs() << "Cost = " << Cost << "\n");
  if (Cost < 0 && Cost < LoopInterchangeCostThreshold)
    return std::optional<bool>(true);
 
  return std::nullopt;
}
 
/// Return true if we can vectorize the loop specified by \p LoopId.
static bool canVectorize(const CharMatrix &DepMatrix, unsigned LoopId) {
  for (const auto &Dep : DepMatrix) {
    char Dir = Dep[LoopId];
    char DepType = Dep.back();
    assert((DepType == '<' || DepType == '*') &&
           "Unexpected element in dependency vector");
 
    // There are no loop-carried dependencies.
    if (Dir == '=' || Dir == 'I')
      continue;
 
    // DepType being '<' means that this direction vector represents a forward
    // dependency. In principle, a loop with '<' direction can be vectorized in
    // this case.
    if (Dir == '<' && DepType == '<')
      continue;
 
    // We cannot prove that the loop is vectorizable.
    return false;
  }
  return true;
}
 
std::optional<bool> LoopInterchangeProfitability::isProfitableForVectorization(
    unsigned InnerLoopId, unsigned OuterLoopId, CharMatrix &DepMatrix) {
  // If the outer loop cannot be vectorized, it is not profitable to move this
  // to inner position.
  if (!canVectorize(DepMatrix, OuterLoopId))
    return false;
 
  // If the inner loop cannot be vectorized but the outer loop can be, then it
  // is profitable to interchange to enable inner loop parallelism.
  if (!canVectorize(DepMatrix, InnerLoopId))
    return true;
 
  // If both the inner and the outer loop can be vectorized, it is necessary to
  // check the cost of each vectorized loop for profitability decision. At this
  // time we do not have a cost model to estimate them, so return nullopt.
  // TODO: Estimate the cost of vectorized loop when both the outer and the
  // inner loop can be vectorized.
  return std::nullopt;
}
 
bool LoopInterchangeProfitability::isProfitable(
    const Loop *InnerLoop, const Loop *OuterLoop, unsigned InnerLoopId,
    unsigned OuterLoopId, CharMatrix &DepMatrix, CacheCostManager &CCM) {
  // Do not consider loops with a backedge that isn't taken, e.g. an
  // unconditional branch true/false, as candidates for interchange.
  // TODO: when interchange is forced, we should probably also allow
  // interchange for these loops, and thus this logic should be moved just
  // below the cost-model ignore check below. But this check is done first
  // to avoid the issue in #163954.
  const SCEV *InnerBTC = SE->getBackedgeTakenCount(InnerLoop);
  const SCEV *OuterBTC = SE->getBackedgeTakenCount(OuterLoop);
  if (InnerBTC && InnerBTC->isZero()) {
    LLVM_DEBUG(dbgs() << "Inner loop back-edge isn't taken, rejecting "
                         "single iteration loop\n");
    return false;
  }
  if (OuterBTC && OuterBTC->isZero()) {
    LLVM_DEBUG(dbgs() << "Outer loop back-edge isn't taken, rejecting "
                         "single iteration loop\n");
    return false;
  }
 
  // Return true if interchange is forced and the cost-model ignored.
  if (Profitabilities.size() == 1 && Profitabilities[0] == RuleTy::Ignore)
    return true;
  assert(noDuplicateRulesAndIgnore(Profitabilities) &&
         "Duplicate rules and option 'ignore' are not allowed");
 
  // isProfitable() is structured to avoid endless loop interchange. If the
  // highest priority rule (isProfitablePerLoopCacheAnalysis by default) could
  // decide the profitability then, profitability check will stop and return the
  // analysis result. If it failed to determine it (e.g., cache analysis failed
  // to analyze the loopnest due to delinearization issues) then go ahead the
  // second highest priority rule (isProfitablePerInstrOrderCost by default).
  // Likewise, if it failed to analysis the profitability then only, the last
  // rule (isProfitableForVectorization by default) will decide.
  std::optional<bool> shouldInterchange;
  for (RuleTy RT : Profitabilities) {
    switch (RT) {
    case RuleTy::PerLoopCacheAnalysis: {
      CacheCost *CC = CCM.getCacheCost();
      const DenseMap<const Loop *, unsigned> &CostMap = CCM.getCostMap();
      shouldInterchange = isProfitablePerLoopCacheAnalysis(CostMap, CC);
      break;
    }
    case RuleTy::PerInstrOrderCost:
      shouldInterchange = isProfitablePerInstrOrderCost();
      break;
    case RuleTy::ForVectorization:
      shouldInterchange =
          isProfitableForVectorization(InnerLoopId, OuterLoopId, DepMatrix);
      break;
    case RuleTy::Ignore:
      llvm_unreachable("Option 'ignore' is not supported with other options");
      break;
    }
 
    // If this rule could determine the profitability, don't call subsequent
    // rules.
    if (shouldInterchange.has_value())
      break;
  }
 
  if (!shouldInterchange.has_value()) {
    ORE->emit([&]() {
      return OptimizationRemarkMissed(DEBUG_TYPE, "InterchangeNotProfitable",
                                      InnerLoop->getStartLoc(),
                                      InnerLoop->getHeader())
             << "Insufficient information to calculate the cost of loop for "
                "interchange.";
    });
    return false;
  } else if (!shouldInterchange.value()) {
    ORE->emit([&]() {
      return OptimizationRemarkMissed(DEBUG_TYPE, "InterchangeNotProfitable",
                                      InnerLoop->getStartLoc(),
                                      InnerLoop->getHeader())
             << "Interchanging loops is not considered to improve cache "
                "locality nor vectorization.";
    });
    return false;
  }
  return true;
}
 
void LoopInterchangeTransform::removeChildLoop(Loop *OuterLoop,
                                               Loop *InnerLoop) {
  for (Loop *L : *OuterLoop)
    if (L == InnerLoop) {
      OuterLoop->removeChildLoop(L);
      return;
    }
  llvm_unreachable("Couldn't find loop");
}
 
/// Update LoopInfo, after interchanging. NewInner and NewOuter refer to the
/// new inner and outer loop after interchanging: NewInner is the original
/// outer loop and NewOuter is the original inner loop.
///
/// Before interchanging, we have the following structure
/// Outer preheader
//  Outer header
//    Inner preheader
//    Inner header
//      Inner body
//      Inner latch
//   outer bbs
//   Outer latch
//
// After interchanging:
// Inner preheader
// Inner header
//   Outer preheader
//   Outer header
//     Inner body
//     outer bbs
//     Outer latch
//   Inner latch
void LoopInterchangeTransform::restructureLoops(
    Loop *NewInner, Loop *NewOuter, BasicBlock *OrigInnerPreHeader,
    BasicBlock *OrigOuterPreHeader) {
  Loop *OuterLoopParent = OuterLoop->getParentLoop();
  // The original inner loop preheader moves from the new inner loop to
  // the parent loop, if there is one.
  NewInner->removeBlockFromLoop(OrigInnerPreHeader);
  LI->changeLoopFor(OrigInnerPreHeader, OuterLoopParent);
 
  // Switch the loop levels.
  if (OuterLoopParent) {
    // Remove the loop from its parent loop.
    removeChildLoop(OuterLoopParent, NewInner);
    removeChildLoop(NewInner, NewOuter);
    OuterLoopParent->addChildLoop(NewOuter);
  } else {
    removeChildLoop(NewInner, NewOuter);
    LI->changeTopLevelLoop(NewInner, NewOuter);
  }
  while (!NewOuter->isInnermost())
    NewInner->addChildLoop(NewOuter->removeChildLoop(NewOuter->begin()));
  NewOuter->addChildLoop(NewInner);
 
  // BBs from the original inner loop.
  SmallVector<BasicBlock *, 8> OrigInnerBBs(NewOuter->blocks());
 
  // Add BBs from the original outer loop to the original inner loop (excluding
  // BBs already in inner loop)
  for (BasicBlock *BB : NewInner->blocks())
    if (LI->getLoopFor(BB) == NewInner)
      NewOuter->addBlockEntry(BB);
 
  // Now remove inner loop header and latch from the new inner loop and move
  // other BBs (the loop body) to the new inner loop.
  BasicBlock *OuterHeader = NewOuter->getHeader();
  BasicBlock *OuterLatch = NewOuter->getLoopLatch();
  for (BasicBlock *BB : OrigInnerBBs) {
    // Nothing will change for BBs in child loops.
    if (LI->getLoopFor(BB) != NewOuter)
      continue;
    // Remove the new outer loop header and latch from the new inner loop.
    if (BB == OuterHeader || BB == OuterLatch)
      NewInner->removeBlockFromLoop(BB);
    else
      LI->changeLoopFor(BB, NewInner);
  }
 
  // The preheader of the original outer loop becomes part of the new
  // outer loop.
  NewOuter->addBlockEntry(OrigOuterPreHeader);
  LI->changeLoopFor(OrigOuterPreHeader, NewOuter);
 
  // Tell SE that we move the loops around.
  SE->forgetLoop(NewOuter);
}
 
///  User can write, or optimizers can generate the reduction for inner loop.
///  To make the interchange valid, apply Reduction2Mem by moving the
///  initializer and store instructions into the inner loop. So far we only
///  handle cases where the reduction variable is initialized to a constant.
///  For example, below code:
///
///  loop:
///    re = phi<0.0, next>
///    next = re op ...
///  endloop
///  reduc_sum = phi<next>       // lcssa phi
///  MEM_REF[idx] = reduc_sum    // LcssaStore
///
///  is transformed into:
///
///  loop:
///    tmp = MEM_REF[idx];
///    new_var = !first_iteration ? tmp : 0.0;
///    next = new_var op ...
///    MEM_REF[idx] = next;   // after moving
///  endloop
///
///  In this way the initial const is used in the first iteration of loop.
void LoopInterchangeTransform::reduction2Memory() {
  ArrayRef<LoopInterchangeLegality::InnerReduction> InnerReductions =
      LIL.getInnerReductions();
 
  assert(InnerReductions.size() == 1 &&
         "So far we only support at most one reduction.");
 
  LoopInterchangeLegality::InnerReduction SR = InnerReductions[0];
  BasicBlock *InnerLoopHeader = InnerLoop->getHeader();
  IRBuilder<> Builder(InnerLoopHeader, InnerLoopHeader->getFirstNonPHIIt());
 
  // Check if it's the first iteration.
  LLVMContext &Context = InnerLoopHeader->getContext();
  PHINode *FirstIter =
      Builder.CreatePHI(Type::getInt1Ty(Context), 2, "first.iter");
  FirstIter->addIncoming(ConstantInt::get(Type::getInt1Ty(Context), 1),
                         InnerLoop->getLoopPreheader());
  FirstIter->addIncoming(ConstantInt::get(Type::getInt1Ty(Context), 0),
                         InnerLoop->getLoopLatch());
  assert(FirstIter->isComplete() && "The FirstIter PHI node is not complete.");
 
  // When the reduction is initialized from a constant value, we need to add
  // a stmt loading from the memory object to target basic block in inner
  // loop.
  Instruction *LoadMem = Builder.CreateLoad(SR.ElemTy, SR.MemRef);
 
  // Init new_var to MEM_REF or CONST depending on if it is the first iteration.
  Value *NewVar = Builder.CreateSelect(FirstIter, SR.Init, LoadMem, "new.var");
 
  // Replace all uses of the reduction variable with a new variable.
  SR.Reduction->replaceAllUsesWith(NewVar);
 
  // Move store instruction into inner loop, just after reduction next's
  // definition.
  SR.LcssaStore->setOperand(0, SR.Next);
  SR.LcssaStore->moveAfter(dyn_cast<Instruction>(SR.Next));
}
 
void LoopInterchangeTransform::transform(
    ArrayRef<Instruction *> DropNoWrapInsts,
    ArrayRef<Instruction *> DropNoInfInsts) {
 
  ArrayRef<LoopInterchangeLegality::InnerReduction> InnerReductions =
      LIL.getInnerReductions();
  if (InnerReductions.size() == 1)
    reduction2Memory();
 
  LLVM_DEBUG(dbgs() << "Splitting the inner loop latch\n");
  auto &InductionPHIs = LIL.getInnerLoopInductions();
  assert(!InductionPHIs.empty() &&
         "Expected at least one induction variable in the inner loop");
 
  SmallVector<Instruction *, 8> InnerIndexVarList;
  for (PHINode *CurInductionPHI : InductionPHIs) {
    Instruction *IncomingValue = dyn_cast<Instruction>(
        CurInductionPHI->getIncomingValueForBlock(InnerLoop->getLoopLatch()));
    assert(IncomingValue &&
           "Incoming value from loop latch isn't an instruction");
    if (is_contained(InductionPHIs, IncomingValue))
      continue;
    InnerIndexVarList.push_back(IncomingValue);
  }
 
  // Create a new latch block for the inner loop. We split at the
  // current latch's terminator and then move the condition and all
  // operands that are not either loop-invariant or the induction PHI into the
  // new latch block.
  BasicBlock *NewLatch =
      SplitBlock(InnerLoop->getLoopLatch(),
                 InnerLoop->getLoopLatch()->getTerminator(), DT, LI);
 
  // Keep these seeds and the operand filter aligned with
  // findFreezeInInnerLatchCloneSet.
  SmallSetVector<Instruction *, 4> WorkList;
  unsigned i = 0;
  auto MoveInstructions = [&i, &WorkList, this, &InductionPHIs, NewLatch]() {
    for (; i < WorkList.size(); i++) {
      // PHI nodes cannot be cloned and moved here; the legality check
      // (areInnerLoopLatchPHIsSupported) ensures none reach the worklist.
      assert(!isa<PHINode>(WorkList[i]) &&
             "MoveInstructions does not support PHI nodes");
      // Duplicate instruction and move it to the new latch. Update uses that
      // have been moved.
      Instruction *NewI = WorkList[i]->clone();
      NewI->insertBefore(NewLatch->getFirstNonPHIIt());
      assert(!NewI->mayHaveSideEffects() &&
             "Moving instructions with side-effects may change behavior of "
             "the loop nest!");
      for (Use &U : llvm::make_early_inc_range(WorkList[i]->uses())) {
        Instruction *UserI = cast<Instruction>(U.getUser());
        if (!InnerLoop->contains(UserI->getParent()) ||
            UserI->getParent() == NewLatch ||
            llvm::is_contained(InductionPHIs, UserI))
          U.set(NewI);
      }
      // Add operands of moved instruction to the worklist, except if they are
      // outside the inner loop or are the induction PHI.
      for (Value *Op : WorkList[i]->operands()) {
        Instruction *OpI = dyn_cast<Instruction>(Op);
        if (!OpI || this->LI->getLoopFor(OpI->getParent()) != this->InnerLoop ||
            llvm::is_contained(InductionPHIs, OpI))
          continue;
        WorkList.insert(OpI);
      }
    }
  };
 
  // FIXME: Should we interchange when we have a constant condition?
  Instruction *CondI = dyn_cast<Instruction>(
      cast<CondBrInst>(InnerLoop->getLoopLatch()->getTerminator())
          ->getCondition());
  if (CondI)
    WorkList.insert(CondI);
  MoveInstructions();
  for (Instruction *InnerIndexVar : InnerIndexVarList)
    WorkList.insert(cast<Instruction>(InnerIndexVar));
  MoveInstructions();
 
  // Split the inner header so that it has a unique successor.
  BasicBlock *InnerLoopHeader = InnerLoop->getHeader();
  SplitBlock(InnerLoopHeader, InnerLoopHeader->getFirstNonPHIIt(), DT, LI);
  LLVM_DEBUG(dbgs() << "splitting InnerLoopHeader done\n");
 
  // Instructions in the original inner loop preheader may depend on values
  // defined in the outer loop header. Move them there, because the original
  // inner loop preheader will become the entry into the interchanged loop nest.
  // Currently we move all instructions and rely on LICM to move invariant
  // instructions outside the loop nest.
  BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
  BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
 
  if (InnerLoopPreHeader != OuterLoopHeader) {
    // Eliminate PHIs in the inner-loop preheader.
    for (PHINode &P : make_early_inc_range(InnerLoopPreHeader->phis())) {
      assert(all_equal(P.incoming_values()) &&
             "Expected equivalent incoming values in inner loop preheader");
      P.replaceAllUsesWith(P.getIncomingValue(0));
      P.eraseFromParent();
    }
    for (Instruction &I :
         make_early_inc_range(make_range(InnerLoopPreHeader->begin(),
                                         std::prev(InnerLoopPreHeader->end()))))
      I.moveBeforePreserving(OuterLoopHeader->getTerminator()->getIterator());
  }
 
  adjustLoopBranches();
 
  // Finally, drop the nsw/nuw/ninf flags from the instructions for reduction
  // calculations.
  for (Instruction *Reduction : DropNoWrapInsts) {
    Reduction->setHasNoSignedWrap(false);
    Reduction->setHasNoUnsignedWrap(false);
  }
  for (Instruction *I : DropNoInfInsts)
    I->setHasNoInfs(false);
}
 
/// \brief Move all instructions except the terminator from FromBB right before
/// InsertBefore
static void moveBBContents(BasicBlock *FromBB, Instruction *InsertBefore) {
  BasicBlock *ToBB = InsertBefore->getParent();
 
  ToBB->splice(InsertBefore->getIterator(), FromBB, FromBB->begin(),
               FromBB->getTerminator()->getIterator());
}
 
/// Swap instructions between \p BB1 and \p BB2 but keep terminators intact.
static void swapBBContents(BasicBlock *BB1, BasicBlock *BB2) {
  // Save all non-terminator instructions of BB1 into TempInstrs and unlink them
  // from BB1 afterwards.
  auto Iter = map_range(*BB1, [](Instruction &I) { return &I; });
  SmallVector<Instruction *, 4> TempInstrs(Iter.begin(), std::prev(Iter.end()));
  for (Instruction *I : TempInstrs)
    I->removeFromParent();
 
  // Move instructions from BB2 to BB1.
  moveBBContents(BB2, BB1->getTerminator());
 
  // Move instructions from TempInstrs to BB2.
  for (Instruction *I : TempInstrs)
    I->insertBefore(BB2->getTerminator()->getIterator());
}
 
// Update BI to jump to NewBB instead of OldBB. Records updates to the
// dominator tree in DTUpdates. If \p MustUpdateOnce is true, assert that
// \p OldBB  is exactly once in BI's successor list.
static void updateSuccessor(Instruction *Term, BasicBlock *OldBB,
                            BasicBlock *NewBB,
                            std::vector<DominatorTree::UpdateType> &DTUpdates,
                            bool MustUpdateOnce = true) {
  assert((!MustUpdateOnce || llvm::count(successors(Term), OldBB) == 1) &&
         "BI must jump to OldBB exactly once.");
  bool Changed = false;
  for (Use &Op : Term->operands())
    if (Op == OldBB) {
      Op.set(NewBB);
      Changed = true;
    }
 
  if (Changed) {
    DTUpdates.push_back(
        {DominatorTree::UpdateKind::Insert, Term->getParent(), NewBB});
    DTUpdates.push_back(
        {DominatorTree::UpdateKind::Delete, Term->getParent(), OldBB});
  }
  assert(Changed && "Expected a successor to be updated");
}
 
// Move Lcssa PHIs to the right place.
static void moveLCSSAPhis(BasicBlock *InnerExit, BasicBlock *InnerHeader,
                          BasicBlock *InnerLatch, BasicBlock *OuterHeader,
                          BasicBlock *OuterLatch, BasicBlock *OuterExit,
                          Loop *InnerLoop, LoopInfo *LI) {
 
  // Deal with LCSSA PHI nodes in the exit block of the inner loop, that are
  // defined either in the header or latch. Those blocks will become header and
  // latch of the new outer loop, and the only possible users can PHI nodes
  // in the exit block of the loop nest or the outer loop header (reduction
  // PHIs, in that case, the incoming value must be defined in the inner loop
  // header). We can just substitute the user with the incoming value and remove
  // the PHI.
  for (PHINode &P : make_early_inc_range(InnerExit->phis())) {
    assert(P.getNumIncomingValues() == 1 &&
           "Only loops with a single exit are supported!");
 
    Value *IncomingValue = P.getIncomingValueForBlock(InnerLatch);
    auto *IncI = dyn_cast<Instruction>(IncomingValue);
    if (!IncI) {
      // If the incoming value is not an instruction, it must be loop invariant.
      // In that case, we can just replace the PHI with the incoming value and
      // remove the PHI.
      assert(InnerLoop->isLoopInvariant(IncomingValue) &&
             "Expected non-instruction incoming value to be loop invariant");
      P.replaceAllUsesWith(IncomingValue);
      P.eraseFromParent();
      continue;
    }
 
    // In case of multi-level nested loops, follow LCSSA to find the incoming
    // value defined from the innermost loop.
    auto *IncIInnerMost = dyn_cast<Instruction>(followLCSSA(IncI));
    // Skip phis when:
    // - they are not an instruction, e.g. incoming values are constants.
    // - Incomming values from the inner loop body, excluding the header and
    //   latch.
    if (!IncIInnerMost || (IncIInnerMost->getParent() != InnerLatch &&
                           IncIInnerMost->getParent() != InnerHeader))
      continue;
 
    assert(all_of(P.users(),
                  [OuterHeader, OuterExit, IncI, InnerHeader](User *U) {
                    return (cast<PHINode>(U)->getParent() == OuterHeader &&
                            IncI->getParent() == InnerHeader) ||
                           cast<PHINode>(U)->getParent() == OuterExit;
                  }) &&
           "Can only replace phis iff the uses are in the loop nest exit or "
           "the incoming value is defined in the inner header (it will "
           "dominate all loop blocks after interchanging)");
    P.replaceAllUsesWith(IncI);
    P.eraseFromParent();
  }
 
  SmallVector<PHINode *, 8> LcssaInnerExit(
      llvm::make_pointer_range(InnerExit->phis()));
 
  SmallVector<PHINode *, 8> LcssaInnerLatch(
      llvm::make_pointer_range(InnerLatch->phis()));
 
  // Lcssa PHIs for values used outside the inner loop are in InnerExit.
  // If a PHI node has users outside of InnerExit, it has a use outside the
  // interchanged loop and we have to preserve it. We move these to
  // InnerLatch, which will become the new exit block for the innermost
  // loop after interchanging.
  for (PHINode *P : LcssaInnerExit)
    P->moveBefore(InnerLatch->getFirstNonPHIIt());
 
  // If the inner loop latch contains LCSSA PHIs, those come from a child loop
  // and we have to move them to the new inner latch.
  for (PHINode *P : LcssaInnerLatch)
    P->moveBefore(InnerExit->getFirstNonPHIIt());
 
  // Deal with LCSSA PHI nodes in the loop nest exit block. For PHIs that have
  // incoming values defined in the outer loop, we have to add a new PHI
  // in the inner loop latch, which became the exit block of the outer loop,
  // after interchanging.
  if (OuterExit) {
    for (PHINode &P : OuterExit->phis()) {
      if (P.getNumIncomingValues() != 1)
        continue;
      // Skip Phis with incoming values defined in the inner loop. Those should
      // already have been updated.
      auto I = dyn_cast<Instruction>(P.getIncomingValue(0));
      if (!I || LI->getLoopFor(I->getParent()) == InnerLoop)
        continue;
 
      PHINode *NewPhi = dyn_cast<PHINode>(P.clone());
      NewPhi->setIncomingValue(0, P.getIncomingValue(0));
      NewPhi->setIncomingBlock(0, OuterLatch);
      // We might have incoming edges from other BBs, i.e., the original outer
      // header.
      for (auto *Pred : predecessors(InnerLatch)) {
        if (Pred == OuterLatch)
          continue;
        NewPhi->addIncoming(P.getIncomingValue(0), Pred);
      }
      NewPhi->insertBefore(InnerLatch->getFirstNonPHIIt());
      P.setIncomingValue(0, NewPhi);
    }
  }
 
  // Now adjust the incoming blocks for the LCSSA PHIs.
  // For PHIs moved from Inner's exit block, we need to replace Inner's latch
  // with the new latch.
  InnerLatch->replacePhiUsesWith(InnerLatch, OuterLatch);
}
 
/// This deals with a corner case when a LCSSA phi node appears in a non-exit
/// block: the outer loop latch block does not need to be exit block of the
/// inner loop. Consider a loop that was in LCSSA form, but then some
/// transformation like loop-unswitch comes along and creates an empty block,
/// where BB5 in this example is the outer loop latch block:
///
///   BB4:
///     br label %BB5
///   BB5:
///     %old.cond.lcssa = phi i16 [ %cond, %BB4 ]
///     br outer.header
///
/// Interchange then brings it in LCSSA form again resulting in this chain of
/// single-input phi nodes:
///
///   BB4:
///     %new.cond.lcssa = phi i16 [ %cond, %BB3 ]
///     br label %BB5
///   BB5:
///     %old.cond.lcssa = phi i16 [ %new.cond.lcssa, %BB4 ]
///
/// The problem is that interchange can reoder blocks BB4 and BB5 placing the
/// use before the def if we don't check this. The solution is to simplify
/// lcssa phi nodes (remove) if they appear in non-exit blocks.
///
static void simplifyLCSSAPhis(Loop *OuterLoop, Loop *InnerLoop) {
  BasicBlock *InnerLoopExit = InnerLoop->getExitBlock();
  BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
 
  // Do not modify lcssa phis where they actually belong, i.e. in exit blocks.
  if (OuterLoopLatch == InnerLoopExit)
    return;
 
  // Collect and remove phis in non-exit blocks if they have 1 input.
  SmallVector<PHINode *, 8> Phis(
      llvm::make_pointer_range(OuterLoopLatch->phis()));
  for (PHINode *Phi : Phis) {
    assert(Phi->getNumIncomingValues() == 1 && "Single input phi expected");
    LLVM_DEBUG(dbgs() << "Removing 1-input phi in non-exit block: " << *Phi
                      << "\n");
    Phi->replaceAllUsesWith(Phi->getIncomingValue(0));
    Phi->eraseFromParent();
  }
}
 
void LoopInterchangeTransform::adjustLoopBranches() {
  LLVM_DEBUG(dbgs() << "adjustLoopBranches called\n");
  std::vector<DominatorTree::UpdateType> DTUpdates;
 
  BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();
  BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
 
  assert(OuterLoopPreHeader != OuterLoop->getHeader() &&
         InnerLoopPreHeader != InnerLoop->getHeader() && OuterLoopPreHeader &&
         InnerLoopPreHeader && "Guaranteed by loop-simplify form");
 
  simplifyLCSSAPhis(OuterLoop, InnerLoop);
 
  // Ensure that both preheaders do not contain PHI nodes and have single
  // predecessors. This allows us to move them easily. We use
  // InsertPreHeaderForLoop to create an 'extra' preheader, if the existing
  // preheaders do not satisfy those conditions.
  if (isa<PHINode>(OuterLoopPreHeader->begin()) ||
      !OuterLoopPreHeader->getUniquePredecessor())
    OuterLoopPreHeader =
        InsertPreheaderForLoop(OuterLoop, DT, LI, nullptr, true);
  if (InnerLoopPreHeader == OuterLoop->getHeader())
    InnerLoopPreHeader =
        InsertPreheaderForLoop(InnerLoop, DT, LI, nullptr, true);
 
  // Adjust the loop preheader
  BasicBlock *InnerLoopHeader = InnerLoop->getHeader();
  BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
  BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
  BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
  BasicBlock *OuterLoopPredecessor = OuterLoopPreHeader->getUniquePredecessor();
  BasicBlock *InnerLoopLatchPredecessor =
      InnerLoopLatch->getUniquePredecessor();
  BasicBlock *InnerLoopLatchSuccessor;
  BasicBlock *OuterLoopLatchSuccessor;
 
  CondBrInst *OuterLoopLatchBI =
      dyn_cast<CondBrInst>(OuterLoopLatch->getTerminator());
  CondBrInst *InnerLoopLatchBI =
      dyn_cast<CondBrInst>(InnerLoopLatch->getTerminator());
  Instruction *OuterLoopHeaderBI = OuterLoopHeader->getTerminator();
  Instruction *InnerLoopHeaderBI = InnerLoopHeader->getTerminator();
 
  assert(OuterLoopPredecessor && InnerLoopLatchPredecessor &&
         "Failed to find a unique predecessor");
  assert(OuterLoopLatchBI && InnerLoopLatchBI &&
         "Failed to find a conditional branch");
 
  Instruction *InnerLoopLatchPredecessorBI =
      InnerLoopLatchPredecessor->getTerminator();
  Instruction *OuterLoopPredecessorBI = OuterLoopPredecessor->getTerminator();
 
  BasicBlock *InnerLoopHeaderSuccessor = InnerLoopHeader->getUniqueSuccessor();
  assert(InnerLoopHeaderSuccessor &&
         "Failed to find a unique successor for the inner loop header");
 
  // Adjust Loop Preheader and headers.
  // The branches in the outer loop predecessor and the outer loop header can
  // be unconditional branches or conditional branches with duplicates. Consider
  // this when updating the successors.
  updateSuccessor(OuterLoopPredecessorBI, OuterLoopPreHeader,
                  InnerLoopPreHeader, DTUpdates, /*MustUpdateOnce=*/false);
  // The outer loop header might or might not branch to the outer latch.
  // We are guaranteed to branch to the inner loop preheader.
  if (llvm::is_contained(successors(OuterLoopHeaderBI), OuterLoopLatch)) {
    // In this case the outerLoopHeader should branch to the InnerLoopLatch.
    updateSuccessor(OuterLoopHeaderBI, OuterLoopLatch, InnerLoopLatch,
                    DTUpdates,
                    /*MustUpdateOnce=*/false);
  }
  updateSuccessor(OuterLoopHeaderBI, InnerLoopPreHeader,
                  InnerLoopHeaderSuccessor, DTUpdates,
                  /*MustUpdateOnce=*/false);
 
  // Adjust reduction PHI's now that the incoming block has changed.
  InnerLoopHeaderSuccessor->replacePhiUsesWith(InnerLoopHeader,
                                               OuterLoopHeader);
 
  updateSuccessor(InnerLoopHeaderBI, InnerLoopHeaderSuccessor,
                  OuterLoopPreHeader, DTUpdates);
 
  // -------------Adjust loop latches-----------
  if (InnerLoopLatchBI->getSuccessor(0) == InnerLoopHeader)
    InnerLoopLatchSuccessor = InnerLoopLatchBI->getSuccessor(1);
  else
    InnerLoopLatchSuccessor = InnerLoopLatchBI->getSuccessor(0);
 
  updateSuccessor(InnerLoopLatchPredecessorBI, InnerLoopLatch,
                  InnerLoopLatchSuccessor, DTUpdates);
 
  if (OuterLoopLatchBI->getSuccessor(0) == OuterLoopHeader)
    OuterLoopLatchSuccessor = OuterLoopLatchBI->getSuccessor(1);
  else
    OuterLoopLatchSuccessor = OuterLoopLatchBI->getSuccessor(0);
 
  updateSuccessor(InnerLoopLatchBI, InnerLoopLatchSuccessor,
                  OuterLoopLatchSuccessor, DTUpdates);
  updateSuccessor(OuterLoopLatchBI, OuterLoopLatchSuccessor, InnerLoopLatch,
                  DTUpdates);
 
  DT->applyUpdates(DTUpdates);
  restructureLoops(OuterLoop, InnerLoop, InnerLoopPreHeader,
                   OuterLoopPreHeader);
 
  moveLCSSAPhis(InnerLoopLatchSuccessor, InnerLoopHeader, InnerLoopLatch,
                OuterLoopHeader, OuterLoopLatch, InnerLoop->getExitBlock(),
                InnerLoop, LI);
  // For PHIs in the exit block of the outer loop, outer's latch has been
  // replaced by Inners'.
  OuterLoopLatchSuccessor->replacePhiUsesWith(OuterLoopLatch, InnerLoopLatch);
 
  auto &OuterInnerReductions = LIL.getOuterInnerReductions();
  // Now update the reduction PHIs in the inner and outer loop headers.
  SmallVector<PHINode *, 4> InnerLoopPHIs, OuterLoopPHIs;
  for (PHINode &PHI : InnerLoopHeader->phis())
    if (OuterInnerReductions.contains(&PHI))
      InnerLoopPHIs.push_back(&PHI);
 
  for (PHINode &PHI : OuterLoopHeader->phis())
    if (OuterInnerReductions.contains(&PHI))
      OuterLoopPHIs.push_back(&PHI);
 
  // Now move the remaining reduction PHIs from outer to inner loop header and
  // vice versa. The PHI nodes must be part of a reduction across the inner and
  // outer loop and all the remains to do is and updating the incoming blocks.
  for (PHINode *PHI : OuterLoopPHIs) {
    LLVM_DEBUG(dbgs() << "Outer loop reduction PHIs:\n"; PHI->dump(););
    PHI->moveBefore(InnerLoopHeader->getFirstNonPHIIt());
    assert(OuterInnerReductions.count(PHI) && "Expected a reduction PHI node");
  }
  for (PHINode *PHI : InnerLoopPHIs) {
    LLVM_DEBUG(dbgs() << "Inner loop reduction PHIs:\n"; PHI->dump(););
    PHI->moveBefore(OuterLoopHeader->getFirstNonPHIIt());
    assert(OuterInnerReductions.count(PHI) && "Expected a reduction PHI node");
  }
 
  // Update the incoming blocks for moved PHI nodes.
  OuterLoopHeader->replacePhiUsesWith(InnerLoopPreHeader, OuterLoopPreHeader);
  OuterLoopHeader->replacePhiUsesWith(InnerLoopLatch, OuterLoopLatch);
  InnerLoopHeader->replacePhiUsesWith(OuterLoopPreHeader, InnerLoopPreHeader);
  InnerLoopHeader->replacePhiUsesWith(OuterLoopLatch, InnerLoopLatch);
 
  // Swap the preheader contents so each definition sits in the preheader of the
  // loop it now belongs to. This runs before the LCSSA rebuild below so that
  // any definition referenced across the interchanged levels dominates its uses
  // when formLCSSAForInstructions runs.
  swapBBContents(OuterLoop->getLoopPreheader(), InnerLoop->getLoopPreheader());
 
  // Values defined in the outer loop header could be used in the inner loop
  // latch. In that case, we need to create LCSSA phis for them, because after
  // interchanging they will be defined in the new inner loop and used in the
  // new outer loop.
  SmallVector<Instruction *, 4> MayNeedLCSSAPhis;
  for (Instruction &I :
       make_range(OuterLoopHeader->begin(), std::prev(OuterLoopHeader->end())))
    MayNeedLCSSAPhis.push_back(&I);
 
#ifndef NDEBUG
  assert(!verifyFunction(*OuterLoopHeader->getParent(), &errs()) &&
         "LoopInterchange handed dominance-broken IR to LCSSA rebuild");
#endif
 
  formLCSSAForInstructions(MayNeedLCSSAPhis, *DT, *LI, SE);
}
 
PreservedAnalyses LoopInterchangePass::run(LoopNest &LN,
                                           LoopAnalysisManager &AM,
                                           LoopStandardAnalysisResults &AR,
                                           LPMUpdater &U) {
  Function &F = *LN.getParent();
  SmallVector<Loop *, 8> LoopList(LN.getLoops());
 
  OptimizationRemarkEmitter ORE(&F);
 
  // Ensure minimum depth of the loop nest to do the interchange.
  if (!hasSupportedLoopDepth(LoopList, ORE))
    return PreservedAnalyses::all();
  // Ensure computable loop nest.
  if (!isComputableLoopNest(&AR.SE, LoopList)) {
    LLVM_DEBUG(dbgs() << "Not valid loop candidate for interchange\n");
    return PreservedAnalyses::all();
  }
 
  ORE.emit([&]() {
    return OptimizationRemarkAnalysis(DEBUG_TYPE, "Dependence",
                                      LN.getOutermostLoop().getStartLoc(),
                                      LN.getOutermostLoop().getHeader())
           << "Computed dependence info, invoking the transform.";
  });
 
  DependenceInfo DI(&F, &AR.AA, &AR.SE, &AR.LI);
  if (!LoopInterchange(&AR.SE, &AR.LI, &DI, &AR.DT, &AR, &ORE).run(LN))
    return PreservedAnalyses::all();
  U.markLoopNestChanged(true);
  return getLoopPassPreservedAnalyses();
}