LoopFuse.cpp

Go to the documentation of this file.

//===- LoopFuse.cpp - Loop Fusion 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
//
//===----------------------------------------------------------------------===//
///
/// \file
/// This file implements the loop fusion pass.
/// The implementation is largely based on the following document:
///
///       Code Transformations to Augment the Scope of Loop Fusion in a
///         Production Compiler
///       Christopher Mark Barton
///       MSc Thesis
///       https://webdocs.cs.ualberta.ca/~amaral/thesis/ChristopherBartonMSc.pdf
///
/// The general approach taken is to collect sets of control flow equivalent
/// loops and test whether they can be fused. The necessary conditions for
/// fusion are:
///    1. The loops must be adjacent (there cannot be any statements between
///       the two loops).
///    2. The loops must be conforming (they must execute the same number of
///       iterations).
///    3. The loops must be control flow equivalent (if one loop executes, the
///       other is guaranteed to execute).
///    4. There cannot be any negative distance dependencies between the loops.
/// If all of these conditions are satisfied, it is safe to fuse the loops.
///
/// This implementation creates FusionCandidates that represent the loop and the
/// necessary information needed by fusion. It then operates on the fusion
/// candidates, first confirming that the candidate is eligible for fusion. The
/// candidates are then collected into control flow equivalent sets, sorted in
/// dominance order. Each set of control flow equivalent candidates is then
/// traversed, attempting to fuse pairs of candidates in the set. If all
/// requirements for fusion are met, the two candidates are fused, creating a
/// new (fused) candidate which is then added back into the set to consider for
/// additional fusion.
///
/// This implementation currently does not make any modifications to remove
/// conditions for fusion. Code transformations to make loops conform to each of
/// the conditions for fusion are discussed in more detail in the document
/// above. These can be added to the current implementation in the future.
//===----------------------------------------------------------------------===//
 
#include "llvm/Transforms/Scalar/LoopFuse.h"
#include "ScalarOptions.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/DependenceAnalysis.h"
#include "llvm/Analysis/DomTreeUpdater.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopNestAnalysis.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/Analysis/PostDominators.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/Verifier.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/CodeMoverUtils.h"
#include "llvm/Transforms/Utils/LoopPeel.h"
#include "llvm/Transforms/Utils/LoopSimplify.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include <list>
#include <tuple>
 
using namespace llvm;
 
#define DEBUG_TYPE "loop-fusion"
 
STATISTIC(FuseCounter, "Loops fused");
STATISTIC(NumFusionCandidates, "Number of candidates for loop fusion");
STATISTIC(InvalidLoopStructure, "Loop has invalid structure");
STATISTIC(AddressTakenBB, "Basic block has address taken");
STATISTIC(MayThrowException, "Loop may throw an exception");
STATISTIC(ContainsVolatileAccess, "Loop contains a volatile access");
STATISTIC(ContainsAtomicAccess, "Loop contains an atomic access");
STATISTIC(NotSimplifiedForm, "Loop is not in simplified form");
STATISTIC(InvalidDependencies, "Dependencies prevent fusion");
STATISTIC(UnknownTripCount, "Loop has unknown trip count");
STATISTIC(UncomputableTripCount, "SCEV cannot compute trip count of loop");
STATISTIC(NonEqualTripCount, "Loop trip counts are not the same");
STATISTIC(
    NonEmptyPreheader,
    "Loop has a non-empty preheader with instructions that cannot be moved");
STATISTIC(InsufficientReuse,
          "Fusion has insufficient cross-loop reused values");
STATISTIC(NonIdenticalGuards, "Candidates have different guards");
STATISTIC(NonEmptyExitBlock, "Candidate has a non-empty exit block with "
                             "instructions that cannot be moved");
STATISTIC(NonEmptyGuardBlock, "Candidate has a non-empty guard block with "
                              "instructions that cannot be moved");
STATISTIC(NotRotated, "Candidate is not rotated");
STATISTIC(OnlySecondCandidateIsGuarded,
          "The second candidate is guarded while the first one is not");
STATISTIC(NumHoistedInsts, "Number of hoisted preheader instructions.");
STATISTIC(NumSunkInsts, "Number of sunk preheader instructions.");
STATISTIC(NumDA, "DA checks passed");
 
namespace {
 
using ReusedValueSet = SmallPtrSet<const Instruction *, 4>;
 
/// This class is used to represent a candidate for loop fusion. When it is
/// constructed, it checks the conditions for loop fusion to ensure that it
/// represents a valid candidate. It caches several parts of a loop that are
/// used throughout loop fusion (e.g., loop preheader, loop header, etc) instead
/// of continually querying the underlying Loop to retrieve these values. It is
/// assumed these will not change throughout loop fusion.
///
/// The invalidate method should be used to indicate that the FusionCandidate is
/// no longer a valid candidate for fusion. Similarly, the isValid() method can
/// be used to ensure that the FusionCandidate is still valid for fusion.
struct FusionCandidate {
  /// Cache of parts of the loop used throughout loop fusion. These should not
  /// need to change throughout the analysis and transformation.
  /// These parts are cached to avoid repeatedly looking up in the Loop class.
 
  /// Preheader of the loop this candidate represents
  BasicBlock *Preheader;
  /// Header of the loop this candidate represents
  BasicBlock *Header;
  /// Blocks in the loop that exit the loop
  BasicBlock *ExitingBlock;
  /// The successor block of this loop (where the exiting blocks go to)
  BasicBlock *ExitBlock;
  /// Latch of the loop
  BasicBlock *Latch;
  /// The loop that this fusion candidate represents
  Loop *L;
  /// Vector of instructions in this loop that read from memory
  SmallVector<Instruction *, 16> MemReads;
  /// Vector of instructions in this loop that write to memory
  SmallVector<Instruction *, 16> MemWrites;
  /// Are all of the members of this fusion candidate still valid
  bool Valid;
  /// Guard branch of the loop, if it exists
  CondBrInst *GuardBranch;
  /// Peeling Paramaters of the Loop.
  TTI::PeelingPreferences PP;
  /// Can you Peel this Loop?
  bool AbleToPeel;
  /// Has this loop been Peeled
  bool Peeled;
 
  DominatorTree &DT;
  const PostDominatorTree *PDT;
 
  OptimizationRemarkEmitter &ORE;
 
  FusionCandidate(Loop *L, DominatorTree &DT, const PostDominatorTree *PDT,
                  OptimizationRemarkEmitter &ORE, TTI::PeelingPreferences PP)
      : Preheader(L->getLoopPreheader()), Header(L->getHeader()),
        ExitingBlock(L->getExitingBlock()), ExitBlock(L->getExitBlock()),
        Latch(L->getLoopLatch()), L(L), Valid(true),
        GuardBranch(L->getLoopGuardBranch()), PP(PP), AbleToPeel(canPeel(L)),
        Peeled(false), DT(DT), PDT(PDT), ORE(ORE) {
 
    // Walk over all blocks in the loop and check for conditions that may
    // prevent fusion. For each block, walk over all instructions and collect
    // the memory reads and writes If any instructions that prevent fusion are
    // found, invalidate this object and return.
    for (BasicBlock *BB : L->blocks()) {
      if (BB->hasAddressTaken()) {
        invalidate();
        ++AddressTakenBB;
        reportInvalidCandidate("AddressTakenBB",
                               "Basic block has address taken");
        return;
      }
 
      for (Instruction &I : *BB) {
        if (I.mayThrow()) {
          invalidate();
          ++MayThrowException;
          reportInvalidCandidate("MayThrowException",
                                 "Loop may throw an exception");
          return;
        }
        if (I.isVolatile()) {
          invalidate();
          ++ContainsVolatileAccess;
          reportInvalidCandidate("ContainsVolatileAccess",
                                 "Loop contains a volatile access");
          return;
        }
        // Atomic accesses impose ordering/synchronization constraints that the
        // dependence analysis used for fusion does not model, so reordering
        // them across the fused body could be unsafe.
        if (I.isAtomic()) {
          invalidate();
          ++ContainsAtomicAccess;
          reportInvalidCandidate("ContainsAtomicAccess",
                                 "Loop contains an atomic access");
          return;
        }
        if (I.mayWriteToMemory())
          MemWrites.push_back(&I);
        if (I.mayReadFromMemory())
          MemReads.push_back(&I);
      }
    }
  }
 
  /// Check if all members of the class are valid.
  bool isValid() const {
    return Preheader && ExitingBlock && ExitBlock && Latch && L &&
           !L->isInvalid() && Valid;
  }
 
  /// Verify that all members are in sync with the Loop object.
  void verify() const {
    assert(isValid() && "Candidate is not valid!!");
    assert(!L->isInvalid() && "Loop is invalid!");
    assert(Preheader == L->getLoopPreheader() && "Preheader is out of sync");
    assert(Header == L->getHeader() && "Header is out of sync");
    assert(ExitingBlock == L->getExitingBlock() &&
           "Exiting Blocks is out of sync");
    assert(ExitBlock == L->getExitBlock() && "Exit block is out of sync");
    assert(Latch == L->getLoopLatch() && "Latch is out of sync");
  }
 
  /// Get the entry block for this fusion candidate.
  ///
  /// If this fusion candidate represents a guarded loop, the entry block is the
  /// loop guard block. If it represents an unguarded loop, the entry block is
  /// the preheader of the loop.
  BasicBlock *getEntryBlock() const {
    if (GuardBranch)
      return GuardBranch->getParent();
    return Preheader;
  }
 
  /// After Peeling the loop is modified quite a bit, hence all of the Blocks
  /// need to be updated accordingly.
  void updateAfterPeeling() {
    Preheader = L->getLoopPreheader();
    Header = L->getHeader();
    ExitingBlock = L->getExitingBlock();
    ExitBlock = L->getExitBlock();
    Latch = L->getLoopLatch();
    verify();
  }
 
  /// Given a guarded loop, get the successor of the guard that is not in the
  /// loop.
  ///
  /// This method returns the successor of the loop guard that is not located
  /// within the loop (i.e., the successor of the guard that is not the
  /// preheader).
  /// This method is only valid for guarded loops.
  BasicBlock *getNonLoopBlock() const {
    assert(GuardBranch && "Only valid on guarded loops.");
    if (Peeled)
      return GuardBranch->getSuccessor(1);
    return (GuardBranch->getSuccessor(0) == Preheader)
               ? GuardBranch->getSuccessor(1)
               : GuardBranch->getSuccessor(0);
  }
 
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  LLVM_DUMP_METHOD void dump() const {
    dbgs() << "\tGuardBranch: ";
    if (GuardBranch)
      dbgs() << *GuardBranch;
    else
      dbgs() << "nullptr";
    dbgs() << "\n"
           << (GuardBranch ? GuardBranch->getName() : "nullptr") << "\n"
           << "\tPreheader: " << (Preheader ? Preheader->getName() : "nullptr")
           << "\n"
           << "\tHeader: " << (Header ? Header->getName() : "nullptr") << "\n"
           << "\tExitingBB: "
           << (ExitingBlock ? ExitingBlock->getName() : "nullptr") << "\n"
           << "\tExitBB: " << (ExitBlock ? ExitBlock->getName() : "nullptr")
           << "\n"
           << "\tLatch: " << (Latch ? Latch->getName() : "nullptr") << "\n"
           << "\tEntryBlock: "
           << (getEntryBlock() ? getEntryBlock()->getName() : "nullptr")
           << "\n";
  }
#endif
 
  /// Determine if a fusion candidate (representing a loop) is eligible for
  /// fusion. Note that this only checks whether a single loop can be fused - it
  /// does not check whether it is *legal* to fuse two loops together.
  bool isEligibleForFusion(ScalarEvolution &SE) const {
    if (!isValid()) {
      LLVM_DEBUG(dbgs() << "FC has invalid CFG requirements!\n");
      assert(Header && "Header should be guaranteed to exist!");
      ++InvalidLoopStructure;
      return false;
    }
 
    // Require ScalarEvolution to be able to determine a trip count.
    if (!SE.hasLoopInvariantBackedgeTakenCount(L)) {
      LLVM_DEBUG(dbgs() << "Loop " << L->getName()
                        << " trip count not computable!\n");
      ++UnknownTripCount;
      return reportInvalidCandidate("UnknownTripCount",
                                    "Loop has unknown trip count");
    }
 
    if (!L->isLoopSimplifyForm()) {
      LLVM_DEBUG(dbgs() << "Loop " << L->getName()
                        << " is not in simplified form!\n");
      ++NotSimplifiedForm;
      return reportInvalidCandidate("NotSimplifiedForm",
                                    "Loop is not in simplified form");
    }
 
    if (!L->isRotatedForm()) {
      LLVM_DEBUG(dbgs() << "Loop " << L->getName() << " is not rotated!\n");
      ++NotRotated;
      return reportInvalidCandidate("NotRotated", "Candidate is not rotated");
    }
 
    return true;
  }
 
private:
  // This is only used internally for now, to clear the MemWrites and MemReads
  // list and setting Valid to false. I can't envision other uses of this right
  // now, since once FusionCandidates are put into the FusionCandidateList they
  // are immutable. Thus, any time we need to change/update a FusionCandidate,
  // we must create a new one and insert it into the FusionCandidateList to
  // ensure the FusionCandidateList remains ordered correctly.
  void invalidate() {
    MemWrites.clear();
    MemReads.clear();
    Valid = false;
  }
 
  // Emit an analysis remark explaining why this loop cannot be fused. The
  // remark is built from explicit strings so it does not depend on whether
  // statistics are enabled. \p RemarkName is the -Rpass remark identifier and
  // \p RemarkMsg the human-readable reason.
  bool reportInvalidCandidate(StringRef RemarkName, StringRef RemarkMsg) const {
    using namespace ore;
    ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE, "InvalidCandidate",
                                        L->getStartLoc(), L->getHeader())
             << "Loop is not a candidate for fusion");
 
    ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE, RemarkName,
                                        L->getStartLoc(), L->getHeader())
             << "[" << L->getHeader()->getParent()->getName() << "]: "
             << "Loop is not a candidate for fusion: " << RemarkMsg);
    return false;
  }
};
} // namespace
 
using LoopVector = SmallVector<Loop *, 4>;
 
// List of adjacent fusion candidates in order. Thus, if FC0 comes *before* FC1
// in a FusionCandidateList, then FC0 dominates FC1, FC1 post-dominates FC0,
// and they are adjacent.
using FusionCandidateList = std::list<FusionCandidate>;
using FusionCandidateCollection = SmallVector<FusionCandidateList, 4>;
 
#ifndef NDEBUG
static void printLoopVector(const LoopVector &LV) {
  dbgs() << "****************************\n";
  for (const Loop *L : LV)
    printLoop(*L, dbgs());
  dbgs() << "****************************\n";
}
 
static raw_ostream &operator<<(raw_ostream &OS, const FusionCandidate &FC) {
  if (FC.isValid())
    OS << FC.Preheader->getName();
  else
    OS << "<Invalid>";
 
  return OS;
}
 
static raw_ostream &operator<<(raw_ostream &OS,
                               const FusionCandidateList &CandList) {
  for (const FusionCandidate &FC : CandList)
    OS << FC << '\n';
 
  return OS;
}
 
static void
printFusionCandidates(const FusionCandidateCollection &FusionCandidates) {
  dbgs() << "Fusion Candidates: \n";
  for (const auto &CandidateList : FusionCandidates) {
    dbgs() << "*** Fusion Candidate List ***\n";
    dbgs() << CandidateList;
    dbgs() << "****************************\n";
  }
}
#endif // NDEBUG
 
/// Fold away an empty block on the "skip" edge of \p L's loop guard, if any.
///
/// Loop::getLoopGuardBranch() recognizes a guard only when the non-loop
/// successor of the guard branch is the block that the loop exit flows into
/// (looking through empty blocks on the exit side only). Passes such as
/// JumpThreading can leave an empty forwarding block on the guard side
/// instead:
///
///   Guard:    br %c, %Preheader, %Skip
///   Skip:     br %Merge             ; empty, only reachable from Guard
///   ...
///   Exit:     br %Merge
///   Merge:    ...
///
/// which makes getLoopGuardBranch() treat \p L as unguarded.
/// This function folds %Skip: it redirects the guard branch to %Merge and
/// deletes the empty %Skip block. Loop fusion calls this on every loop before
/// collecting fusion candidates so that a guarded loop left in this shape by
/// an earlier pass is still recognized as guarded and as adjacent to its
/// neighbor. Returns true if the CFG was changed.
static bool simplifyLoopGuard(Loop *L, DomTreeUpdater &DTU, LoopInfo &LI,
                              ScalarEvolution &SE) {
  if (!L->isLoopSimplifyForm() || !L->isRotatedForm())
    return false;
 
  BasicBlock *Preheader = L->getLoopPreheader();
  BasicBlock *ExitBlock = L->getUniqueExitBlock();
  if (!ExitBlock)
    return false;
 
  BasicBlock *GuardBB = Preheader->getUniquePredecessor();
  if (!GuardBB)
    return false;
 
  auto *GuardBI = dyn_cast<CondBrInst>(GuardBB->getTerminator());
  if (!GuardBI)
    return false;
 
  BasicBlock *SkipBB = GuardBI->getSuccessor(0) == Preheader
                           ? GuardBI->getSuccessor(1)
                           : GuardBI->getSuccessor(0);
  if (SkipBB == Preheader)
    return false;
 
  // The skip block must contain nothing but an unconditional branch and must
  // be reachable only from the guard, so that removing it cannot change any
  // other path.
  if (SkipBB->size() != 1 || !isa<UncondBrInst>(SkipBB->getTerminator()) ||
      SkipBB->hasAddressTaken() || SkipBB->getUniquePredecessor() != GuardBB)
    return false;
 
  BasicBlock *MergeBB = SkipBB->getUniqueSuccessor();
  if (!MergeBB || MergeBB == SkipBB || MergeBB == GuardBB ||
      LI.isLoopHeader(MergeBB))
    return false;
 
  // The loop exit must flow into the same block; otherwise the branch is
  // not a loop guard.
  if (&LoopNest::skipEmptyBlockUntil(ExitBlock, MergeBB,
                                     /*CheckUniquePred=*/true) != MergeBB)
    return false;
 
  LLVM_DEBUG(dbgs() << "Removing empty guard skip block " << SkipBB->getName()
                    << " of loop " << L->getHeader()->getName() << "\n");
 
  MergeBB->replacePhiUsesWith(SkipBB, GuardBB);
  GuardBI->replaceSuccessorWith(SkipBB, MergeBB);
  SkipBB->getTerminator()->eraseFromParent();
  new UnreachableInst(SkipBB->getContext(), SkipBB);
 
  DTU.applyUpdates({{DominatorTree::Delete, GuardBB, SkipBB},
                    {DominatorTree::Delete, SkipBB, MergeBB},
                    {DominatorTree::Insert, GuardBB, MergeBB}});
  LI.removeBlock(SkipBB);
  DTU.deleteBB(SkipBB);
  DTU.flush();
 
  return true;
}
 
namespace {
 
/// Collect all loops in function at the same nest level, starting at the
/// outermost level.
///
/// This data structure collects all loops at the same nest level for a
/// given function (specified by the LoopInfo object). It starts at the
/// outermost level.
struct LoopDepthTree {
  using LoopsOnLevelTy = SmallVector<LoopVector, 4>;
  using iterator = LoopsOnLevelTy::iterator;
  using const_iterator = LoopsOnLevelTy::const_iterator;
 
  LoopDepthTree(LoopInfo &LI) : Depth(1) {
    if (!LI.empty())
      LoopsOnLevel.emplace_back(LoopVector(LI.rbegin(), LI.rend()));
  }
 
  /// Test whether a given loop has been removed from the function, and thus is
  /// no longer valid.
  bool isRemovedLoop(const Loop *L) const { return RemovedLoops.count(L); }
 
  /// Record that a given loop has been removed from the function and is no
  /// longer valid.
  void removeLoop(const Loop *L) { RemovedLoops.insert(L); }
 
  /// Descend the tree to the next (inner) nesting level
  void descend() {
    LoopsOnLevelTy LoopsOnNextLevel;
 
    for (const LoopVector &LV : *this)
      for (Loop *L : LV)
        if (!isRemovedLoop(L) && L->begin() != L->end())
          LoopsOnNextLevel.emplace_back(LoopVector(L->begin(), L->end()));
 
    LoopsOnLevel = LoopsOnNextLevel;
    RemovedLoops.clear();
    Depth++;
  }
 
  bool empty() const { return size() == 0; }
  size_t size() const { return LoopsOnLevel.size() - RemovedLoops.size(); }
  unsigned getDepth() const { return Depth; }
 
  iterator begin() { return LoopsOnLevel.begin(); }
  iterator end() { return LoopsOnLevel.end(); }
  const_iterator begin() const { return LoopsOnLevel.begin(); }
  const_iterator end() const { return LoopsOnLevel.end(); }
 
private:
  /// Set of loops that have been removed from the function and are no longer
  /// valid.
  SmallPtrSet<const Loop *, 8> RemovedLoops;
 
  /// Depth of the current level, starting at 1 (outermost loops).
  unsigned Depth;
 
  /// Vector of loops at the current depth level that have the same parent loop
  LoopsOnLevelTy LoopsOnLevel;
};
 
struct LoopFuser {
private:
  const ScalarOptions &Opts;
 
  // Sets of control flow equivalent fusion candidates for a given nest level.
  FusionCandidateCollection FusionCandidates;
 
  LoopDepthTree LDT;
  DomTreeUpdater DTU;
 
  LoopInfo &LI;
  DominatorTree &DT;
  DependenceInfo &DI;
  AAResults &AA;
  ScalarEvolution &SE;
  PostDominatorTree &PDT;
  OptimizationRemarkEmitter &ORE;
  AssumptionCache &AC;
  const TargetTransformInfo &TTI;
 
public:
  LoopFuser(const ScalarOptions &Opts, LoopInfo &LI, DominatorTree &DT,
            DependenceInfo &DI, AAResults &AA, ScalarEvolution &SE,
            PostDominatorTree &PDT, OptimizationRemarkEmitter &ORE,
            AssumptionCache &AC, const TargetTransformInfo &TTI)
      : Opts(Opts), LDT(LI), DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy),
        LI(LI), DT(DT), DI(DI), AA(AA), SE(SE), PDT(PDT), ORE(ORE), AC(AC),
        TTI(TTI) {}
 
  /// This is the main entry point for loop fusion. It will traverse the
  /// specified function and collect candidate loops to fuse, starting at the
  /// outermost nesting level and working inwards.
  bool fuseLoops(Function &F) {
#ifndef NDEBUG
    if (Opts.loop_fusion_verbose_debug) {
      LI.print(dbgs());
    }
#endif
 
    LLVM_DEBUG(dbgs() << "Performing Loop Fusion on function " << F.getName()
                      << "\n");
    bool Changed = false;
 
    while (!LDT.empty()) {
      LLVM_DEBUG(dbgs() << "Got " << LDT.size() << " loop sets for depth "
                        << LDT.getDepth() << "\n";);
 
      for (const LoopVector &LV : LDT) {
        assert(LV.size() > 0 && "Empty loop set was build!");
 
        // Skip singleton loop sets as they do not offer fusion opportunities on
        // this level.
        if (LV.size() == 1)
          continue;
#ifndef NDEBUG
        if (Opts.loop_fusion_verbose_debug) {
          LLVM_DEBUG({
            dbgs() << "  Visit loop set (#" << LV.size() << "):\n";
            printLoopVector(LV);
          });
        }
#endif
 
        collectFusionCandidates(LV);
        Changed |= fuseCandidates();
        // All loops in the candidate sets have a common parent (or no parent).
        // Next loop vector will correspond to a different parent. It is safe
        // to remove all the candidates currently in the set.
        FusionCandidates.clear();
      }
 
      // Finished analyzing candidates at this level. Descend to the next level.
      LLVM_DEBUG(dbgs() << "Descend one level!\n");
      LDT.descend();
    }
 
    if (Changed)
      LLVM_DEBUG(dbgs() << "Function after Loop Fusion: \n"; F.dump(););
 
#ifndef NDEBUG
    assert(DT.verify());
    assert(PDT.verify());
    LI.verify();
    SE.verify();
#endif
 
    LLVM_DEBUG(dbgs() << "Loop Fusion complete\n");
    return Changed;
  }
 
private:
  /// Iterate over all loops in the given loop set and identify the loops that
  /// are eligible for fusion. Place all eligible fusion candidates into Control
  /// Flow Equivalent sets, sorted by dominance.
  void collectFusionCandidates(const LoopVector &LV) {
    for (Loop *L : LV) {
      TTI::PeelingPreferences PP =
          gatherPeelingPreferences(L, SE, TTI, std::nullopt, std::nullopt);
      FusionCandidate CurrCand(L, DT, &PDT, ORE, PP);
      if (!CurrCand.isEligibleForFusion(SE))
        continue;
 
      // Go through each list in FusionCandidates and determine if the first or
      // last loop in the list is strictly adjacent to L. If it is, append L.
      // If not, go to the next list.
      // If no suitable list is found, start another list and add it to
      // FusionCandidates.
      bool FoundAdjacent = false;
      for (auto &CurrCandList : FusionCandidates) {
        if (isStrictlyAdjacent(CurrCandList.back(), CurrCand)) {
          CurrCandList.push_back(CurrCand);
          FoundAdjacent = true;
          NumFusionCandidates++;
#ifndef NDEBUG
          if (Opts.loop_fusion_verbose_debug)
            LLVM_DEBUG(dbgs() << "Adding " << CurrCand
                              << " to existing candidate list\n");
#endif
          break;
        }
      }
      if (!FoundAdjacent) {
        // No list was found. Create a new list and add to FusionCandidates
#ifndef NDEBUG
        if (Opts.loop_fusion_verbose_debug)
          LLVM_DEBUG(dbgs() << "Adding " << CurrCand << " to new list\n");
#endif
        FusionCandidateList NewCandList;
        NewCandList.push_back(CurrCand);
        FusionCandidates.push_back(NewCandList);
      }
    }
  }
 
  /// Determine if it is beneficial to fuse two loops.
  bool isBeneficialFusion(unsigned ReusedValueCount) const {
    if (Opts.loop_fusion_disable_cost_model)
      return true;
    return ReusedValueCount >= Opts.loop_fusion_min_reused_values;
  }
 
  /// Computes the integer difference in trip counts:
  /// TripCount(FC0) - TripCount(FC1).
  ///
  /// \returns The integer difference, or std::nullopt if it
  ///          cannot be determined.
  std::optional<int64_t>
  calculateTripCountDiff(const FusionCandidate &FC0,
                         const FusionCandidate &FC1) const {
    const SCEV *TripCount0 = SE.getBackedgeTakenCount(FC0.L);
    if (isa<SCEVCouldNotCompute>(TripCount0)) {
      UncomputableTripCount++;
      LLVM_DEBUG(dbgs() << "Trip count of first loop could not be computed!");
      return std::nullopt;
    }
 
    const SCEV *TripCount1 = SE.getBackedgeTakenCount(FC1.L);
    if (isa<SCEVCouldNotCompute>(TripCount1)) {
      UncomputableTripCount++;
      LLVM_DEBUG(dbgs() << "Trip count of second loop could not be computed!");
      return std::nullopt;
    }
 
    LLVM_DEBUG(dbgs() << "\tTrip counts: " << *TripCount0 << " & "
                      << *TripCount1 << " are "
                      << (TripCount0 == TripCount1 ? "identical" : "different")
                      << "\n");
 
    if (TripCount0 == TripCount1)
      return 0;
 
    LLVM_DEBUG(dbgs() << "The loops do not have the same tripcount, "
                         "determining the difference between trip counts\n");
 
    // Currently only considering loops with a single exit point
    // and a non-constant trip count. Note that the return value
    // of getSmallConstantTripCount is a 32 bit number, based on
    // the existing implementation.
    const int64_t TC0 =
        static_cast<int64_t>(SE.getSmallConstantTripCount(FC0.L));
    const int64_t TC1 =
        static_cast<int64_t>(SE.getSmallConstantTripCount(FC1.L));
 
    // If any of the tripcounts are zero that means that loop(s) do not have
    // a single exit or a constant tripcount.
    if (TC0 == 0 || TC1 == 0) {
      LLVM_DEBUG(dbgs() << "Loop(s) do not have a single exit point or do not "
                           "have a constant number of iterations. Peeling "
                           "is not benefical\n");
      return std::nullopt;
    }
 
    return TC0 - TC1;
  }
 
  void peelFusionCandidate(FusionCandidate &FC0, const FusionCandidate &FC1,
                           unsigned PeelCount) {
    assert(FC0.AbleToPeel && "Should be able to peel loop");
 
    LLVM_DEBUG(dbgs() << "Attempting to peel first " << PeelCount
                      << " iterations of the first loop. \n");
 
    ValueToValueMapTy VMap;
    // LoopFusion is a function pass that neither requires nor preserves
    // LCSSA, so peelLoop need not preserve it across its internal
    // simplifyLoop call.
    peelLoop(FC0.L, PeelCount, /*PeelLast=*/false, &LI, &SE, DT, &AC,
             /*PreserveLCSSA=*/false, VMap);
    FC0.Peeled = true;
    LLVM_DEBUG(dbgs() << "Done Peeling\n");
 
#ifndef NDEBUG
    auto TCDiff = calculateTripCountDiff(FC0, FC1);
 
    assert(TCDiff && *TCDiff == 0 &&
           "Loops should have identical trip counts after peeling");
#endif
 
    FC0.PP.PeelCount += PeelCount;
 
    // Peeling does not update the PDT
    PDT.recalculate(*FC0.Preheader->getParent());
 
    FC0.updateAfterPeeling();
 
    // In this case the iterations of the loop are constant, so the first
    // loop will execute completely (will not jump from one of
    // the peeled blocks to the second loop). Here we are updating the
    // branch conditions of each of the peeled blocks, such that it will
    // branch to its successor which is not the preheader of the second loop
    // in the case of unguarded loops, or the succesors of the exit block of
    // the first loop otherwise. Doing this update will ensure that the entry
    // block of the first loop dominates the entry block of the second loop.
    BasicBlock *BB =
        FC0.GuardBranch ? FC0.ExitBlock->getUniqueSuccessor() : FC1.Preheader;
    if (BB) {
      SmallVector<DominatorTree::UpdateType, 8> TreeUpdates;
      SmallVector<Instruction *, 8> WorkList;
      for (BasicBlock *Pred : predecessors(BB)) {
        if (Pred != FC0.ExitBlock) {
          WorkList.emplace_back(Pred->getTerminator());
          TreeUpdates.emplace_back(
              DominatorTree::UpdateType(DominatorTree::Delete, Pred, BB));
        }
      }
      // Cannot modify the predecessors inside the above loop as it will cause
      // the iterators to be nullptrs, causing memory errors.
      for (Instruction *CurrentBranch : WorkList) {
        BasicBlock *Succ = CurrentBranch->getSuccessor(0);
        if (Succ == BB)
          Succ = CurrentBranch->getSuccessor(1);
        ReplaceInstWithInst(CurrentBranch, UncondBrInst::Create(Succ));
      }
 
      DTU.applyUpdates(TreeUpdates);
      DTU.flush();
    }
    LLVM_DEBUG(
        dbgs() << "Sucessfully peeled " << FC0.PP.PeelCount
               << " iterations from the first loop.\n"
                  "Both Loops have the same number of iterations now.\n");
  }
 
  /// Walk each set of strictly adjacent fusion candidates and attempt to fuse
  /// them. This does a single linear traversal of all candidates in the list.
  /// The conditions for legal fusion are checked at this point. If a pair of
  /// fusion candidates passes all legality checks, they are fused together and
  /// a new fusion candidate is created and added to the FusionCandidateList.
  /// The original fusion candidates are then removed, as they are no longer
  /// valid.
  bool fuseCandidates() {
    bool Fused = false;
    LLVM_DEBUG(printFusionCandidates(FusionCandidates));
    for (auto &CandidateList : FusionCandidates) {
      if (CandidateList.size() < 2)
        continue;
 
      LLVM_DEBUG(dbgs() << "Attempting fusion on Candidate List:\n"
                        << CandidateList << "\n");
 
      for (auto It = CandidateList.begin(), NextIt = std::next(It);
           NextIt != CandidateList.end(); It = NextIt, NextIt = std::next(It)) {
 
        const FusionCandidate &FC0 = *It;
        const FusionCandidate &FC1 = *NextIt;
 
        assert(!LDT.isRemovedLoop(FC0.L) &&
               "Should not have removed loops in CandidateList!");
        assert(!LDT.isRemovedLoop(FC1.L) &&
               "Should not have removed loops in CandidateList!");
 
        LLVM_DEBUG(dbgs() << "Attempting to fuse candidate \n"; FC0.dump();
                   dbgs() << " with\n"; FC1.dump(); dbgs() << "\n");
 
        FC0.verify();
        FC1.verify();
 
        std::optional<int64_t> TCDifference = calculateTripCountDiff(FC0, FC1);
        // Here we are checking that FC0 (the first loop) can be peeled, and
        // the first loop has a larger trip count. In this case it is possible
        // that the first loop is peeled to expose the fusion opportunity.
        // Peeling the second loop is not currently supported.
        bool WillPeel = FC0.AbleToPeel && TCDifference && *TCDifference > 0 &&
                        *TCDifference <= static_cast<int64_t>(
                                             Opts.loop_fusion_peel_max_count);
 
        if (!WillPeel && (!TCDifference || *TCDifference != 0)) {
          LLVM_DEBUG(dbgs() << "Fusion candidates do not have identical trip "
                               "counts and peeling is not supported for this "
                               "case. Not fusing.\n");
          ++NonEqualTripCount;
          reportLoopFusion<OptimizationRemarkMissed>(
              FC0, FC1, "NonEqualTripCount",
              "Loop trip counts are not the same");
          continue;
        }
 
        if ((!FC0.GuardBranch && FC1.GuardBranch) ||
            (FC0.GuardBranch && !FC1.GuardBranch)) {
          LLVM_DEBUG(dbgs() << "The one of candidate is guarded while the "
                               "another one is not. Not fusing.\n");
          ++OnlySecondCandidateIsGuarded;
          reportLoopFusion<OptimizationRemarkMissed>(
              FC0, FC1, "OnlySecondCandidateIsGuarded",
              "The second candidate is guarded while the first one is not");
          continue;
        }
 
        // If Loops are guarded, we expect the guards to be identical.
        // Currently peeling is supported only for loops with constant
        // iteration counts. If two loops have different loop guards
        // there is no mechanism in loop fusion to make their fusion legal.
        // The trivial case where the guards compare two constant values can be
        // ignored. Those guards will be optimized away by other passes.
        if (FC0.GuardBranch && FC1.GuardBranch &&
            !haveIdenticalGuards(FC0, FC1)) {
          LLVM_DEBUG(dbgs() << "Fusion candidates do not have identical "
                               "guards. Not Fusing.\n");
          ++NonIdenticalGuards;
          reportLoopFusion<OptimizationRemarkMissed>(
              FC0, FC1, "NonIdenticalGuards",
              "Candidates have different guards");
          continue;
        }
 
        if (FC0.GuardBranch) {
          assert(FC1.GuardBranch && "Expecting valid FC1 guard branch");
 
          if (!isSafeToMoveBefore(*FC0.ExitBlock,
                                  *FC1.ExitBlock->getFirstNonPHIOrDbg(), DT,
                                  &PDT, &DI)) {
            LLVM_DEBUG(dbgs() << "Fusion candidate contains unsafe "
                                 "instructions in exit block. Not fusing.\n");
            ++NonEmptyExitBlock;
            reportLoopFusion<OptimizationRemarkMissed>(
                FC0, FC1, "NonEmptyExitBlock",
                "Candidate has a non-empty exit block with "
                "instructions that cannot be moved");
            continue;
          }
 
          if (!isSafeToMoveBefore(
                  *FC1.GuardBranch->getParent(),
                  *FC0.GuardBranch->getParent()->getTerminator(), DT, &PDT,
                  &DI)) {
            LLVM_DEBUG(dbgs() << "Fusion candidate contains unsafe "
                                 "instructions in guard block. Not fusing.\n");
            ++NonEmptyGuardBlock;
            reportLoopFusion<OptimizationRemarkMissed>(
                FC0, FC1, "NonEmptyGuardBlock",
                "Candidate has a non-empty guard block with "
                "instructions that cannot be moved");
            continue;
          }
        }
 
        // Check the dependencies across the loops and do not fuse if it would
        // violate them.
        ReusedValueSet ReusedValues;
        if (!dependencesAllowFusion(FC0, FC1, &ReusedValues)) {
          LLVM_DEBUG(dbgs() << "Memory dependencies do not allow fusion!\n");
          ++InvalidDependencies;
          reportLoopFusion<OptimizationRemarkMissed>(
              FC0, FC1, "InvalidDependencies", "Dependencies prevent fusion");
          continue;
        }
 
        // If the second loop has instructions in the pre-header, attempt to
        // hoist them up to the first loop's pre-header or sink them into the
        // body of the second loop.
        SmallVector<Instruction *, 4> SafeToHoist;
        SmallVector<Instruction *, 4> SafeToSink;
        // At this point, this is the last remaining legality check.
        // Which means if we can make this pre-header empty, we can fuse
        // these loops
        if (!isEmptyPreheader(FC1)) {
          LLVM_DEBUG(dbgs() << "Fusion candidate does not have empty "
                               "preheader.\n");
 
          // If it is not safe to hoist/sink all instructions in the
          // pre-header, we cannot fuse these loops.
          if (!collectMovablePreheaderInsts(FC0, FC1, SafeToHoist,
                                            SafeToSink)) {
            LLVM_DEBUG(dbgs() << "Could not hoist/sink all instructions in "
                                 "Fusion Candidate Pre-header.\n"
                              << "Not Fusing.\n");
            ++NonEmptyPreheader;
            reportLoopFusion<OptimizationRemarkMissed>(
                FC0, FC1, "NonEmptyPreheader",
                "Loop has a non-empty preheader with instructions that "
                "cannot be moved");
            continue;
          }
        }
 
        unsigned ReusedValueCount = ReusedValues.size();
        bool BeneficialToFuse = isBeneficialFusion(ReusedValueCount);
        LLVM_DEBUG(dbgs() << "\tFusion appears to be "
                          << (BeneficialToFuse ? "" : "un") << "profitable!\n");
        if (!BeneficialToFuse) {
          ++InsufficientReuse;
          reportFusionInsufficientReuse(FC0, FC1, ReusedValueCount);
          continue;
        }
 
        // All analysis has completed and has determined that fusion is legal
        // and profitable. At this point, start transforming the code and
        // perform fusion.
 
        // Execute the hoist/sink operations on preheader instructions
        movePreheaderInsts(FC0, FC1, SafeToHoist, SafeToSink);
 
        LLVM_DEBUG(dbgs() << "\tFusion is performed: " << FC0 << " and " << FC1
                          << "\n");
 
        FusionCandidate FC0Copy = FC0;
        // Peel the loop after determining that fusion is legal. The Loops
        // will still be safe to fuse after the peeling is performed.
        bool Peel = TCDifference && *TCDifference > 0;
        if (Peel)
          peelFusionCandidate(FC0Copy, FC1, *TCDifference);
 
        // Report fusion to the Optimization Remarks.
        // Note this needs to be done *before* performFusion because
        // performFusion will change the original loops, making it not
        // possible to identify them after fusion is complete.
        ++FuseCounter;
        reportLoopFusion<OptimizationRemark>((Peel ? FC0Copy : FC0), FC1,
                                             "FuseCounter", "Loops fused");
 
        FusionCandidate FusedCand(performFusion((Peel ? FC0Copy : FC0), FC1),
                                  DT, &PDT, ORE, FC0Copy.PP);
        FusedCand.verify();
        assert(FusedCand.isEligibleForFusion(SE) &&
               "Fused candidate should be eligible for fusion!");
 
        // Notify the loop-depth-tree that these loops are not valid objects
        LDT.removeLoop(FC1.L);
 
        // Replace FC0 and FC1 with their fused loop
        It = CandidateList.erase(It);
        It = CandidateList.erase(It);
        It = CandidateList.insert(It, FusedCand);
 
        // Start from FusedCand in the next iteration
        NextIt = It;
 
        LLVM_DEBUG(dbgs() << "Candidate List (after fusion): " << CandidateList
                          << "\n");
 
        Fused = true;
      }
    }
    return Fused;
  }
 
  // Returns true if the instruction \p I can be hoisted to the end of the
  // preheader of \p FC0. \p SafeToHoist contains the instructions that are
  // known to be safe to hoist. The instructions encountered that cannot be
  // hoisted are in \p NotHoisting.
  // TODO: Move functionality into CodeMoverUtils
  bool canHoistInst(Instruction &I,
                    const SmallVector<Instruction *, 4> &SafeToHoist,
                    const SmallVector<Instruction *, 4> &NotHoisting,
                    const FusionCandidate &FC0) const {
    const BasicBlock *FC0PreheaderTarget = FC0.Preheader->getSingleSuccessor();
    assert(FC0PreheaderTarget &&
           "Expected single successor for loop preheader.");
 
    for (Use &Op : I.operands()) {
      if (auto *OpInst = dyn_cast<Instruction>(Op)) {
        bool OpHoisted = is_contained(SafeToHoist, OpInst);
        // Check if we have already decided to hoist this operand. In this
        // case, it does not dominate FC0 *yet*, but will after we hoist it.
        if (!(OpHoisted || DT.dominates(OpInst, FC0PreheaderTarget))) {
          return false;
        }
      }
    }
 
    // PHIs in FC1's header only have FC0 blocks as predecessors. PHIs
    // cannot be hoisted and should be sunk to the exit of the fused loop.
    if (isa<PHINode>(I))
      return false;
 
    // If this isn't a memory inst, hoisting is safe
    if (!I.mayReadOrWriteMemory())
      return true;
 
    LLVM_DEBUG(dbgs() << "Checking if this mem inst can be hoisted.\n");
    for (Instruction *NotHoistedInst : NotHoisting) {
      if (auto D = DI.depends(&I, NotHoistedInst)) {
        // Dependency is not read-before-write, write-before-read or
        // write-before-write
        if (D->isFlow() || D->isAnti() || D->isOutput()) {
          LLVM_DEBUG(dbgs() << "Inst depends on an instruction in FC1's "
                               "preheader that is not being hoisted.\n");
          return false;
        }
      }
    }
 
    for (Instruction *ReadInst : FC0.MemReads) {
      if (auto D = DI.depends(ReadInst, &I)) {
        // Dependency is not read-before-write
        if (D->isAnti()) {
          LLVM_DEBUG(dbgs() << "Inst depends on a read instruction in FC0.\n");
          return false;
        }
      }
    }
 
    for (Instruction *WriteInst : FC0.MemWrites) {
      if (auto D = DI.depends(WriteInst, &I)) {
        // Dependency is not write-before-read or write-before-write
        if (D->isFlow() || D->isOutput()) {
          LLVM_DEBUG(dbgs() << "Inst depends on a write instruction in FC0.\n");
          return false;
        }
      }
    }
    return true;
  }
 
  // Returns true if the instruction \p I can be sunk to the top of the exit
  // block of \p FC1.
  // TODO: Move functionality into CodeMoverUtils
  bool canSinkInst(Instruction &I, const FusionCandidate &FC1) const {
    for (User *U : I.users()) {
      if (auto *UI{dyn_cast<Instruction>(U)}) {
        // Cannot sink if user in loop
        // If FC1 has phi users of this value, we cannot sink it into FC1.
        if (FC1.L->contains(UI)) {
          // Cannot hoist or sink this instruction. No hoisting/sinking
          // should take place, loops should not fuse
          return false;
        }
      }
    }
 
    // If this isn't a memory inst, sinking is safe
    if (!I.mayReadOrWriteMemory())
      return true;
 
    for (Instruction *ReadInst : FC1.MemReads) {
      if (auto D = DI.depends(&I, ReadInst)) {
        // Dependency is not write-before-read
        if (D->isFlow()) {
          LLVM_DEBUG(dbgs() << "Inst depends on a read instruction in FC1.\n");
          return false;
        }
      }
    }
 
    for (Instruction *WriteInst : FC1.MemWrites) {
      if (auto D = DI.depends(&I, WriteInst)) {
        // Dependency is not write-before-write or read-before-write
        if (D->isOutput() || D->isAnti()) {
          LLVM_DEBUG(dbgs() << "Inst depends on a write instruction in FC1.\n");
          return false;
        }
      }
    }
 
    return true;
  }
 
  /// Collect instructions in the \p FC1 Preheader that can be hoisted
  /// to the \p FC0 Preheader or sunk into the \p FC1 Body
  bool collectMovablePreheaderInsts(
      const FusionCandidate &FC0, const FusionCandidate &FC1,
      SmallVector<Instruction *, 4> &SafeToHoist,
      SmallVector<Instruction *, 4> &SafeToSink) const {
    BasicBlock *FC1Preheader = FC1.Preheader;
    // Save the instructions that are not being hoisted, so we know not to hoist
    // mem insts that they dominate.
    SmallVector<Instruction *, 4> NotHoisting;
 
    for (Instruction &I : *FC1Preheader) {
      // Can't move a branch
      if (&I == FC1Preheader->getTerminator())
        continue;
      // If the instruction has side-effects, give up.
      // TODO: The case of mayReadFromMemory we can handle but requires
      // additional work with a dependence analysis so for now we give
      // up on memory reads.
      if (I.mayThrow() || !I.willReturn()) {
        LLVM_DEBUG(dbgs() << "Inst: " << I << " may throw or won't return.\n");
        return false;
      }
 
      LLVM_DEBUG(dbgs() << "Checking Inst: " << I << "\n");
 
      if (I.isAtomic() || I.isVolatile()) {
        LLVM_DEBUG(
            dbgs() << "\tInstruction is volatile or atomic. Cannot move it.\n");
        return false;
      }
 
      if (canHoistInst(I, SafeToHoist, NotHoisting, FC0)) {
        SafeToHoist.push_back(&I);
        LLVM_DEBUG(dbgs() << "\tSafe to hoist.\n");
      } else {
        LLVM_DEBUG(dbgs() << "\tCould not hoist. Trying to sink...\n");
        NotHoisting.push_back(&I);
 
        if (canSinkInst(I, FC1)) {
          SafeToSink.push_back(&I);
          LLVM_DEBUG(dbgs() << "\tSafe to sink.\n");
        } else {
          LLVM_DEBUG(dbgs() << "\tCould not sink.\n");
          return false;
        }
      }
    }
    LLVM_DEBUG(
        dbgs() << "All preheader instructions could be sunk or hoisted!\n");
    return true;
  }
 
  using AffineLoadKey = std::tuple<const SCEV *, const SCEV *>;
 
  std::optional<AffineLoadKey> getAffineLoadKey(const FusionCandidate &FC,
                                                Instruction &I) {
    auto *Load = dyn_cast<LoadInst>(&I);
    if (!Load)
      return std::nullopt;
 
    const auto *AR =
        dyn_cast<SCEVAddRecExpr>(SE.getSCEV(Load->getPointerOperand()));
    if (!AR || AR->getLoop() != FC.L || !AR->isAffine())
      return std::nullopt;
 
    return AffineLoadKey{AR->getStart(), AR->getStepRecurrence(SE)};
  }
 
  /// Return true if \p A is known to execute before \p B in an iteration of
  /// \p L. Keep accesses in nested loops conservative.
  bool isKnownBefore(const Instruction *A, const Instruction *B,
                     const Loop *L) const {
    return LI.getLoopFor(A->getParent()) == L &&
           LI.getLoopFor(B->getParent()) == L && DT.dominates(A, B);
  }
 
  /// Return true if a write between the corresponding loads may overwrite
  /// either loaded memory location.
  bool hasInterveningWrite(BatchAAResults &BAA, const LoadInst &Load0,
                           const LoadInst &Load1, const FusionCandidate &FC0,
                           const FusionCandidate &FC1) const {
    MemoryLocation Loc0 = MemoryLocation::get(&Load0);
    MemoryLocation Loc1 = MemoryLocation::get(&Load1);
    auto MayModify = [&](Instruction *Write) {
      return isModSet(BAA.getModRefInfo(Write, Loc0)) ||
             isModSet(BAA.getModRefInfo(Write, Loc1));
    };
 
    for (Instruction *Write : FC0.MemWrites)
      if (!isKnownBefore(Write, &Load0, FC0.L) && MayModify(Write))
        return true;
    for (Instruction *Write : FC1.MemWrites)
      if (!isKnownBefore(&Load1, Write, FC1.L) && MayModify(Write))
        return true;
    return false;
  }
 
  /// Collect distinct read-read addresses reused at corresponding iterations.
  ///
  /// This uses exact affine SCEV equality rather than adding a potentially
  /// expensive read-read DependenceAnalysis query for every load pair.
  void collectReadReadReuse(const FusionCandidate &FC0,
                            const FusionCandidate &FC1,
                            ReusedValueSet &ReusedValues) {
    if (ReusedValues.size() >= Opts.loop_fusion_min_reused_values)
      return;
 
    BatchAAResults BAA(AA);
    SmallDenseMap<AffineLoadKey, Instruction *, 8> LoadAccesses0;
    for (Instruction *ReadL0 : FC0.MemReads) {
      std::optional<AffineLoadKey> Key = getAffineLoadKey(FC0, *ReadL0);
      if (!Key)
        continue;
 
      LoadAccesses0.try_emplace(*Key, ReadL0);
    }
 
    for (Instruction *ReadL1 : FC1.MemReads) {
      std::optional<AffineLoadKey> Key = getAffineLoadKey(FC1, *ReadL1);
      if (!Key)
        continue;
 
      Instruction *MatchingLoad = LoadAccesses0.lookup(*Key);
      if (!MatchingLoad)
        continue;
 
      auto *Load0 = cast<LoadInst>(MatchingLoad);
      auto *Load1 = cast<LoadInst>(ReadL1);
      if (hasInterveningWrite(BAA, *Load0, *Load1, FC0, FC1))
        continue;
 
      ReusedValues.insert(MatchingLoad);
      LLVM_DEBUG(dbgs() << "Same-iteration read-read reuse via "
                        << *MatchingLoad << "\n");
      if (ReusedValues.size() >= Opts.loop_fusion_min_reused_values)
        return;
    }
  }
 
  /// Return true if the dependences between @p I0 (in @p L0) and @p I1 (in
  /// @p L1) allow loop fusion of @p L0 and @p L1.
  bool dependencesAllowFusion(const FusionCandidate &FC0,
                              const FusionCandidate &FC1, Instruction &I0,
                              Instruction &I1,
                              ReusedValueSet *ReusedValues = nullptr) {
#ifndef NDEBUG
    if (Opts.loop_fusion_verbose_debug) {
      LLVM_DEBUG(dbgs() << "Check dep: " << I0 << " vs " << I1 << "\n");
    }
#endif
    auto DepResult = DI.depends(&I0, &I1);
    if (!DepResult)
      return true;
    // If two stores write the same SSA value, fusion is safe regardless of
    // aliasing - writing the same value twice is idempotent.
    if (isa<StoreInst>(I0) && isa<StoreInst>(I1)) {
      auto *S0 = cast<StoreInst>(&I0);
      auto *S1 = cast<StoreInst>(&I1);
      if (S0->getValueOperand() == S1->getValueOperand())
        return true;
    }
#ifndef NDEBUG
    if (Opts.loop_fusion_verbose_debug) {
      LLVM_DEBUG(dbgs() << "DA res: "; DepResult->dump(dbgs());
                 dbgs() << " [#l: " << DepResult->getLevels() << "][Ordered: "
                        << (DepResult->isOrdered() ? "true" : "false")
                        << "]\n");
      LLVM_DEBUG(dbgs() << "DepResult Levels: " << DepResult->getLevels()
                        << "\n");
    }
#endif
    unsigned Levels = DepResult->getLevels();
    unsigned SameSDLevels = DepResult->getSameSDLevels();
    unsigned CurLoopLevel = FC0.L->getLoopDepth();
 
    // Check if DA is missing info regarding the current loop level
    if (CurLoopLevel > Levels + SameSDLevels)
      return false;
 
    // Iterating over the outer levels.
    for (unsigned Level = 1; Level <= std::min(CurLoopLevel - 1, Levels);
         ++Level) {
      unsigned Direction = DepResult->getDirection(Level, false);
 
      // Check if the direction vector does not include equality. If an outer
      // loop has a non-equal direction, outer indicies are different and it
      // is safe to fuse.
      if (!(Direction & Dependence::DVEntry::EQ)) {
        LLVM_DEBUG(dbgs() << "Safe to fuse due to non-equal acceses in the "
                             "outer loops\n");
        NumDA++;
        return true;
      }
    }
 
    assert(CurLoopLevel > Levels && "Fusion candidates are not separated");
 
    unsigned CurDir = DepResult->getDirection(CurLoopLevel, true);
 
    if (ReusedValues && !DepResult->isConfused() && DepResult->isFlow() &&
        CurDir == Dependence::DVEntry::EQ) {
      ReusedValues->insert(&I0);
      LLVM_DEBUG(dbgs() << "Same-iteration reuse via " << I0 << "\n");
    }
 
    if (DepResult->isScalar(CurLoopLevel, true)) {
      if (DepResult->isInput() || DepResult->isOutput()) {
        LLVM_DEBUG(dbgs() << "Safe to fuse due to a loop-invariant "
                          << (DepResult->isInput() ? "input" : "output")
                          << " dependency\n");
        NumDA++;
        return true;
      }
      // Same-iteration scalar flow/anti dependences between adjacent loops are
      // preserved by placing FC0's body before FC1's body in the fused loop.
      // This enables fusing accumulation chains such as:
      //   for (i)
      //     A[i] = ...;
      //   for (i)
      //     A[i] += ...;
      if (!(CurDir & Dependence::DVEntry::GT) &&
          !(CurDir & Dependence::DVEntry::LT)) {
        LLVM_DEBUG(dbgs() << "Safe to fuse same-iteration scalar dependence\n");
        NumDA++;
        return true;
      }
      LLVM_DEBUG(
          dbgs() << "Not safe to fuse due to a scalar flow dependency\n");
      return false;
    }
 
    // Check if the direction vector does not include greater direction. In
    // that case, the dependency is not a backward loop-carried and is legal
    // to fuse. For example here we have a forward dependency
    //    for (int i = 0; i < n; i++)
    //        A[i] = ...;
    //    for (int i = 0; i < n; i++)
    //        ... = A[i-1];
    if (!(CurDir & Dependence::DVEntry::GT)) {
      LLVM_DEBUG(dbgs() << "Safe to fuse with no backward loop-carried "
                           "dependency\n");
      NumDA++;
      return true;
    }
 
    if (DepResult->getNextPredecessor() || DepResult->getNextSuccessor())
      LLVM_DEBUG(dbgs() << "TODO: Implement pred/succ dependence handling!\n");
 
    return false;
  }
 
  /// Perform a dependence check and return if @p FC0 and @p FC1 can be fused.
  bool dependencesAllowFusion(const FusionCandidate &FC0,
                              const FusionCandidate &FC1,
                              ReusedValueSet *ReusedValues) {
    LLVM_DEBUG(dbgs() << "Check if " << FC0 << " can be fused with " << FC1
                      << "\n");
    assert(FC0.L->getLoopDepth() == FC1.L->getLoopDepth());
    assert(DT.dominates(FC0.getEntryBlock(), FC1.getEntryBlock()));
 
    // Walk through all uses in FC1. For each use, find the reaching def.
    // If the def is located in FC0 then it is not safe to fuse.
    for (BasicBlock *BB : FC1.L->blocks())
      for (Instruction &I : *BB)
        for (auto &Op : I.operands())
          if (Instruction *Def = dyn_cast<Instruction>(Op))
            if (FC0.L->contains(Def->getParent())) {
              return false;
            }
 
    for (Instruction *WriteL0 : FC0.MemWrites) {
      for (Instruction *WriteL1 : FC1.MemWrites)
        if (!dependencesAllowFusion(FC0, FC1, *WriteL0, *WriteL1)) {
          return false;
        }
      for (Instruction *ReadL1 : FC1.MemReads)
        if (!dependencesAllowFusion(FC0, FC1, *WriteL0, *ReadL1,
                                    ReusedValues)) {
          return false;
        }
    }
 
    // Write-write and write-read pairs are already covered above; only the
    // read-before-write pairs from FC0 reads to FC1 writes remain.
    for (Instruction *ReadL0 : FC0.MemReads)
      for (Instruction *WriteL1 : FC1.MemWrites)
        if (!dependencesAllowFusion(FC0, FC1, *ReadL0, *WriteL1)) {
          return false;
        }
 
    if (ReusedValues && !Opts.loop_fusion_disable_cost_model)
      collectReadReadReuse(FC0, FC1, *ReusedValues);
 
    return true;
  }
 
  /// Determine if two fusion candidates are strictly adjacent in the CFG.
  ///
  /// This method will determine if there are additional basic blocks in the CFG
  /// between the exit of \p FC0 and the entry of \p FC1.
  /// If the two candidates are guarded loops, then it checks whether the
  /// exit block of the \p FC0 is the predecessor of the \p FC1 preheader. This
  /// implicitly ensures that the non-loop successor of the \p FC0 guard branch
  /// is the entry block of \p FC1. If not, then the loops are not adjacent. If
  /// the two candidates are not guarded loops, then it checks whether the exit
  /// block of \p FC0 is the preheader of \p FC1.
  /// Strictly means there is no predecessor for FC1 unless it is from FC0,
  /// i.e., FC0 dominates FC1.
  bool isStrictlyAdjacent(const FusionCandidate &FC0,
                          const FusionCandidate &FC1) const {
    // If the successor of the guard branch is FC1, then the loops are adjacent
    if (FC0.GuardBranch)
      return DT.dominates(FC0.getEntryBlock(), FC1.getEntryBlock()) &&
             FC0.ExitBlock->getSingleSuccessor() == FC1.getEntryBlock();
    return FC0.ExitBlock == FC1.getEntryBlock();
  }
 
  bool isEmptyPreheader(const FusionCandidate &FC) const {
    return FC.Preheader->size() == 1;
  }
 
  /// Hoist \p FC1 Preheader instructions to \p FC0 Preheader
  /// and sink others into the body of \p FC1.
  void movePreheaderInsts(const FusionCandidate &FC0,
                          const FusionCandidate &FC1,
                          SmallVector<Instruction *, 4> &HoistInsts,
                          SmallVector<Instruction *, 4> &SinkInsts) const {
    // All preheader instructions except the branch must be hoisted or sunk
    assert(HoistInsts.size() + SinkInsts.size() == FC1.Preheader->size() - 1 &&
           "Attempting to sink and hoist preheader instructions, but not all "
           "the preheader instructions are accounted for.");
 
    NumHoistedInsts += HoistInsts.size();
    NumSunkInsts += SinkInsts.size();
 
    LLVM_DEBUG(if (Opts.loop_fusion_verbose_debug) {
      if (!HoistInsts.empty())
        dbgs() << "Hoisting: \n";
      for (Instruction *I : HoistInsts)
        dbgs() << *I << "\n";
      if (!SinkInsts.empty())
        dbgs() << "Sinking: \n";
      for (Instruction *I : SinkInsts)
        dbgs() << *I << "\n";
    });
 
    for (Instruction *I : HoistInsts) {
      assert(I->getParent() == FC1.Preheader);
      I->moveBefore(*FC0.Preheader,
                    FC0.Preheader->getTerminator()->getIterator());
    }
    // insert instructions in reverse order to maintain dominance relationship
    for (Instruction *I : reverse(SinkInsts)) {
      assert(I->getParent() == FC1.Preheader);
      if (isa<PHINode>(I)) {
        // The Phis to be sunk should have only one incoming value, as is
        // assured by the condition that the second loop is dominated by the
        // first one which is enforced by isStrictlyAdjacent().
        // Replace the phi uses with the corresponding incoming value to clean
        // up the code.
        assert(cast<PHINode>(I)->getNumIncomingValues() == 1 &&
               "Expected the sunk PHI node to have 1 incoming value.");
        I->replaceAllUsesWith(I->getOperand(0));
        I->eraseFromParent();
      } else
        I->moveBefore(*FC1.ExitBlock, FC1.ExitBlock->getFirstInsertionPt());
    }
  }
 
  /// Determine if two fusion candidates have identical guards
  ///
  /// This method will determine if two fusion candidates have the same guards.
  /// The guards are considered the same if:
  ///   1. The instructions to compute the condition used in the compare are
  ///      identical.
  ///   2. The successors of the guard have the same flow into/around the loop.
  /// If the compare instructions are identical, then the first successor of the
  /// guard must go to the same place (either the preheader of the loop or the
  /// NonLoopBlock). In other words, the first successor of both loops must
  /// both go into the loop (i.e., the preheader) or go around the loop (i.e.,
  /// the NonLoopBlock). The same must be true for the second successor.
  bool haveIdenticalGuards(const FusionCandidate &FC0,
                           const FusionCandidate &FC1) const {
    assert(FC0.GuardBranch && FC1.GuardBranch &&
           "Expecting FC0 and FC1 to be guarded loops.");
 
    auto *FC0CmpInst = dyn_cast<Instruction>(FC0.GuardBranch->getCondition());
    auto *FC1CmpInst = dyn_cast<Instruction>(FC1.GuardBranch->getCondition());
    if ((!FC0CmpInst || !FC1CmpInst) &&
        FC0.GuardBranch->getCondition() != FC1.GuardBranch->getCondition())
      return false;
 
    if (FC0CmpInst && FC1CmpInst && !FC0CmpInst->isIdenticalTo(FC1CmpInst))
      return false;
 
    // The compare instructions are identical.
    // Now make sure the successor of the guards have the same flow into/around
    // the loop
    if (FC0.GuardBranch->getSuccessor(0) == FC0.Preheader)
      return (FC1.GuardBranch->getSuccessor(0) == FC1.Preheader);
    return (FC1.GuardBranch->getSuccessor(1) == FC1.Preheader);
  }
 
  /// Modify the latch branch of FC to be unconditional since successors of the
  /// branch are the same.
  void simplifyLatchBranch(const FusionCandidate &FC) const {
    CondBrInst *FCLatchBranch = dyn_cast<CondBrInst>(FC.Latch->getTerminator());
    if (FCLatchBranch) {
      assert(FCLatchBranch->getSuccessor(0) == FCLatchBranch->getSuccessor(1) &&
             "Expecting the two successors of FCLatchBranch to be the same");
      UncondBrInst *NewBranch =
          UncondBrInst::Create(FCLatchBranch->getSuccessor(0));
      ReplaceInstWithInst(FCLatchBranch, NewBranch);
    }
  }
 
  /// Move instructions from FC0.Latch to FC1.Latch. If FC0.Latch has an unique
  /// successor, then merge FC0.Latch with its unique successor.
  void mergeLatch(const FusionCandidate &FC0, const FusionCandidate &FC1) {
    moveInstructionsToTheBeginning(*FC0.Latch, *FC1.Latch, DT, PDT, DI, SE);
    if (BasicBlock *Succ = FC0.Latch->getUniqueSuccessor()) {
      MergeBlockIntoPredecessor(Succ, &DTU, &LI);
      DTU.flush();
    }
  }
 
  /// Move FC1's header PHIs into FC0's header, insert the loop-carried PHIs
  /// needed to keep SSA valid when FC0 exits without taking its back-edge, and
  /// rewire both latches to form the fused loop. Latch dominator-tree updates
  /// are appended to \p TreeUpdates for the caller to apply.
  void rewireFusedHeaderPHIsAndLatches(
      const FusionCandidate &FC0, const FusionCandidate &FC1,
      const SmallVectorImpl<PHINode *> &OriginalFC0PHIs,
      SmallVectorImpl<DominatorTree::UpdateType> &TreeUpdates) {
    // Moves the phi nodes from the second to the first loops header block.
    while (PHINode *PHI = dyn_cast<PHINode>(&FC1.Header->front())) {
      if (SE.isSCEVable(PHI->getType()))
        SE.forgetValue(PHI);
      if (PHI->hasNUsesOrMore(1))
        PHI->moveBefore(FC0.Header->getFirstInsertionPt());
      else
        PHI->eraseFromParent();
    }
 
    // Introduce new phi nodes in the second loop header to ensure
    // exiting the first and jumping to the header of the second does not break
    // the SSA property of the phis originally in the first loop. See also the
    // comment above.
    BasicBlock::iterator L1HeaderIP = FC1.Header->begin();
    for (PHINode *LCPHI : OriginalFC0PHIs) {
      int L1LatchBBIdx = LCPHI->getBasicBlockIndex(FC1.Latch);
      assert(L1LatchBBIdx >= 0 &&
             "Expected loop carried value to be rewired at this point!");
 
      Value *LCV = LCPHI->getIncomingValue(L1LatchBBIdx);
 
      PHINode *L1HeaderPHI =
          PHINode::Create(LCV->getType(), 2, LCPHI->getName() + ".afterFC0");
      L1HeaderPHI->insertBefore(L1HeaderIP);
      L1HeaderPHI->addIncoming(LCV, FC0.Latch);
      L1HeaderPHI->addIncoming(PoisonValue::get(LCV->getType()),
                               FC0.ExitingBlock);
 
      LCPHI->setIncomingValue(L1LatchBBIdx, L1HeaderPHI);
    }
 
    // Replace latch terminator destinations.
    FC0.Latch->getTerminator()->replaceUsesOfWith(FC0.Header, FC1.Header);
    FC1.Latch->getTerminator()->replaceUsesOfWith(FC1.Header, FC0.Header);
 
    // Modify the latch branch of FC0 to be unconditional as both successors of
    // the branch are the same.
    simplifyLatchBranch(FC0);
 
    // If FC0.Latch and FC0.ExitingBlock are the same then we have already
    // performed the updates above.
    if (FC0.Latch != FC0.ExitingBlock)
      TreeUpdates.emplace_back(DominatorTree::UpdateType(
          DominatorTree::Insert, FC0.Latch, FC1.Header));
 
    TreeUpdates.emplace_back(DominatorTree::UpdateType(DominatorTree::Delete,
                                                       FC0.Latch, FC0.Header));
    TreeUpdates.emplace_back(DominatorTree::UpdateType(DominatorTree::Insert,
                                                       FC1.Latch, FC0.Header));
    TreeUpdates.emplace_back(DominatorTree::UpdateType(DominatorTree::Delete,
                                                       FC1.Latch, FC1.Header));
  }
 
  /// Forget cached SCEV state for both loops, move all of FC1's blocks and
  /// child loops into FC0, erase the now-empty FC1, and merge the latches.
  /// Returns the fused loop (FC0.L).
  Loop *finalizeFusedLoop(const FusionCandidate &FC0,
                          const FusionCandidate &FC1) {
    // Is there a way to keep SE up-to-date so we don't need to forget the loops
    // and rebuild the information in subsequent passes of fusion?
    // Note: Need to forget the loops before merging the loop latches, as
    // mergeLatch may remove the only block in FC1.
    SE.forgetLoop(FC1.L);
    SE.forgetLoop(FC0.L);
 
    // Merge the loops.
    SmallVector<BasicBlock *, 8> Blocks(FC1.L->blocks());
    for (BasicBlock *BB : Blocks) {
      FC0.L->addBlockEntry(BB);
      FC1.L->removeBlockFromLoop(BB);
      if (LI.getLoopFor(BB) != FC1.L)
        continue;
      LI.changeLoopFor(BB, FC0.L);
    }
    while (!FC1.L->isInnermost()) {
      const auto &ChildLoopIt = FC1.L->begin();
      Loop *ChildLoop = *ChildLoopIt;
      FC1.L->removeChildLoop(ChildLoopIt);
      FC0.L->addChildLoop(ChildLoop);
    }
 
    // Delete the now empty loop L1.
    LI.erase(FC1.L);
 
    // Forget block dispositions as well, so that there are no dangling
    // pointers to erased/free'ed blocks. It should be done after mergeLatch()
    // since merging the latches may affect the dispositions.
    SE.forgetBlockAndLoopDispositions();
 
    // Move instructions from FC0.Latch to FC1.Latch.
    // Note: mergeLatch requires an updated DT.
    mergeLatch(FC0, FC1);
 
#ifndef NDEBUG
    assert(!verifyFunction(*FC0.Header->getParent(), &errs()));
    assert(DT.verify(DominatorTree::VerificationLevel::Fast));
    assert(PDT.verify());
    LI.verify();
    SE.verify();
#endif
 
    LLVM_DEBUG(dbgs() << "Fusion done:\n");
 
    return FC0.L;
  }
 
  /// Fuse two fusion candidates, creating a new fused loop.
  ///
  /// This method contains the mechanics of fusing two loops, represented by \p
  /// FC0 and \p FC1. It is assumed that \p FC0 dominates \p FC1 and \p FC1
  /// postdominates \p FC0 (making them control flow equivalent). It also
  /// assumes that the other conditions for fusion have been met: adjacent,
  /// identical trip counts, and no negative distance dependencies exist that
  /// would prevent fusion. Thus, there is no checking for these conditions in
  /// this method.
  ///
  /// Fusion is performed by rewiring the CFG to update successor blocks of the
  /// components of tho loop. Specifically, the following changes are done:
  ///
  ///   1. The preheader of \p FC1 is removed as it is no longer necessary
  ///   (because it is currently only a single statement block).
  ///   2. The latch of \p FC0 is modified to jump to the header of \p FC1.
  ///   3. The latch of \p FC1 i modified to jump to the header of \p FC0.
  ///   4. All blocks from \p FC1 are removed from FC1 and added to FC0.
  ///
  /// All of these modifications are done with dominator tree updates, thus
  /// keeping the dominator (and post dominator) information up-to-date.
  ///
  /// This can be improved in the future by actually merging blocks during
  /// fusion. For example, the preheader of \p FC1 can be merged with the
  /// preheader of \p FC0. This would allow loops with more than a single
  /// statement in the preheader to be fused. Similarly, the latch blocks of the
  /// two loops could also be fused into a single block. This will require
  /// analysis to prove it is safe to move the contents of the block past
  /// existing code, which currently has not been implemented.
  Loop *performFusion(const FusionCandidate &FC0, const FusionCandidate &FC1) {
    assert(FC0.isValid() && FC1.isValid() &&
           "Expecting valid fusion candidates");
 
    LLVM_DEBUG(dbgs() << "Fusion Candidate 0: \n"; FC0.dump();
               dbgs() << "Fusion Candidate 1: \n"; FC1.dump(););
 
    // Move instructions from the preheader of FC1 to the end of the preheader
    // of FC0.
    moveInstructionsToTheEnd(*FC1.Preheader, *FC0.Preheader, DT, PDT, DI, SE);
 
    // Fusing guarded loops is handled slightly differently than non-guarded
    // loops and has been broken out into a separate method instead of trying to
    // intersperse the logic within a single method.
    if (FC0.GuardBranch)
      return fuseGuardedLoops(FC0, FC1);
 
    assert(FC1.Preheader ==
           (FC0.Peeled ? FC0.ExitBlock->getUniqueSuccessor() : FC0.ExitBlock));
    assert(FC1.Preheader->size() == 1 &&
           FC1.Preheader->getSingleSuccessor() == FC1.Header);
 
    // Remember the phi nodes originally in the header of FC0 in order to rewire
    // them later. However, this is only necessary if the new loop carried
    // values might not dominate the exiting branch. While we do not generally
    // test if this is the case but simply insert intermediate phi nodes, we
    // need to make sure these intermediate phi nodes have different
    // predecessors. To this end, we filter the special case where the exiting
    // block is the latch block of the first loop. Nothing needs to be done
    // anyway as all loop carried values dominate the latch and thereby also the
    // exiting branch.
    SmallVector<PHINode *, 8> OriginalFC0PHIs;
    if (FC0.ExitingBlock != FC0.Latch)
      for (PHINode &PHI : FC0.Header->phis())
        OriginalFC0PHIs.push_back(&PHI);
 
    // Replace incoming blocks for header PHIs first.
    FC1.Preheader->replaceSuccessorsPhiUsesWith(FC0.Preheader);
    FC0.Latch->replaceSuccessorsPhiUsesWith(FC1.Latch);
 
    // Then modify the control flow and update DT and PDT.
    SmallVector<DominatorTree::UpdateType, 8> TreeUpdates;
 
    // The old exiting block of the first loop (FC0) has to jump to the header
    // of the second as we need to execute the code in the second header block
    // regardless of the trip count. That is, if the trip count is 0, so the
    // back edge is never taken, we still have to execute both loop headers,
    // especially (but not only!) if the second is a do-while style loop.
    // However, doing so might invalidate the phi nodes of the first loop as
    // the new values do only need to dominate their latch and not the exiting
    // predicate. To remedy this potential problem we always introduce phi
    // nodes in the header of the second loop later that select the loop carried
    // value, if the second header was reached through an old latch of the
    // first, or undef otherwise. This is sound as exiting the first implies the
    // second will exit too, __without__ taking the back-edge. [Their
    // trip-counts are equal after all.
    // KB: Would this sequence be simpler to just make FC0.ExitingBlock go
    // to FC1.Header? I think this is basically what the three sequences are
    // trying to accomplish; however, doing this directly in the CFG may mean
    // the DT/PDT becomes invalid
    if (!FC0.Peeled) {
      FC0.ExitingBlock->getTerminator()->replaceUsesOfWith(FC1.Preheader,
                                                           FC1.Header);
      TreeUpdates.emplace_back(DominatorTree::UpdateType(
          DominatorTree::Delete, FC0.ExitingBlock, FC1.Preheader));
      TreeUpdates.emplace_back(DominatorTree::UpdateType(
          DominatorTree::Insert, FC0.ExitingBlock, FC1.Header));
    } else {
      TreeUpdates.emplace_back(DominatorTree::UpdateType(
          DominatorTree::Delete, FC0.ExitBlock, FC1.Preheader));
 
      // Remove the ExitBlock of the first Loop (also not needed)
      FC0.ExitingBlock->getTerminator()->replaceUsesOfWith(FC0.ExitBlock,
                                                           FC1.Header);
      TreeUpdates.emplace_back(DominatorTree::UpdateType(
          DominatorTree::Delete, FC0.ExitingBlock, FC0.ExitBlock));
      FC0.ExitBlock->getTerminator()->eraseFromParent();
      TreeUpdates.emplace_back(DominatorTree::UpdateType(
          DominatorTree::Insert, FC0.ExitingBlock, FC1.Header));
      new UnreachableInst(FC0.ExitBlock->getContext(), FC0.ExitBlock);
    }
 
    // The pre-header of L1 is not necessary anymore.
    assert(pred_empty(FC1.Preheader));
    FC1.Preheader->getTerminator()->eraseFromParent();
    new UnreachableInst(FC1.Preheader->getContext(), FC1.Preheader);
    TreeUpdates.emplace_back(DominatorTree::UpdateType(
        DominatorTree::Delete, FC1.Preheader, FC1.Header));
 
    rewireFusedHeaderPHIsAndLatches(FC0, FC1, OriginalFC0PHIs, TreeUpdates);
 
    // Update DT/PDT
    DTU.applyUpdates(TreeUpdates);
 
    LI.removeBlock(FC1.Preheader);
    DTU.deleteBB(FC1.Preheader);
    if (FC0.Peeled) {
      LI.removeBlock(FC0.ExitBlock);
      DTU.deleteBB(FC0.ExitBlock);
    }
 
    DTU.flush();
 
    return finalizeFusedLoop(FC0, FC1);
  }
 
  /// Report details on loop fusion opportunities.
  ///
  /// This template function can be used to report both successful and missed
  /// loop fusion opportunities, based on the RemarkKind. The RemarkKind should
  /// be one of:
  ///   - OptimizationRemarkMissed to report when loop fusion is unsuccessful
  ///     given two valid fusion candidates.
  ///   - OptimizationRemark to report successful fusion of two fusion
  ///     candidates.
  /// The remarks will be printed using the form:
  ///    <path/filename>:<line number>:<column number>: [<function name>]:
  ///       <Cand1 Preheader> and <Cand2 Preheader>: <Stat Description>
  template <typename RemarkKind>
  void reportLoopFusion(const FusionCandidate &FC0, const FusionCandidate &FC1,
                        StringRef RemarkName, StringRef RemarkMsg) {
    assert(FC0.Preheader && FC1.Preheader &&
           "Expecting valid fusion candidates");
    using namespace ore;
    ORE.emit(
        RemarkKind(DEBUG_TYPE, RemarkName, FC0.L->getStartLoc(), FC0.Preheader)
        << "[" << FC0.Preheader->getParent()->getName()
        << "]: " << NV("Cand1", StringRef(FC0.Preheader->getName())) << " and "
        << NV("Cand2", StringRef(FC1.Preheader->getName())) << ": "
        << RemarkMsg);
  }
 
  void reportFusionInsufficientReuse(const FusionCandidate &FC0,
                                     const FusionCandidate &FC1,
                                     unsigned ReusedValueCount) {
    assert(ReusedValueCount < Opts.loop_fusion_min_reused_values &&
           "Expected insufficient reuse");
 
    using namespace ore;
    ORE.emit(OptimizationRemarkMissed(DEBUG_TYPE, "InsufficientReuse",
                                      FC0.L->getStartLoc(), FC0.Preheader)
             << "[" << FC0.Preheader->getParent()->getName()
             << "]: " << NV("Cand1", StringRef(FC0.Preheader->getName()))
             << " and " << NV("Cand2", StringRef(FC1.Preheader->getName()))
             << ": found " << NV("ReusedValueCount", ReusedValueCount)
             << " cross-loop reused values; configured minimum is "
             << NV("MinimumReusedValues",
                   unsigned(Opts.loop_fusion_min_reused_values)));
  }
 
  /// Fuse two guarded fusion candidates, creating a new fused loop.
  ///
  /// Fusing guarded loops is handled much the same way as fusing non-guarded
  /// loops. The rewiring of the CFG is slightly different though, because of
  /// the presence of the guards around the loops and the exit blocks after the
  /// loop body. As such, the new loop is rewired as follows:
  ///    1. Keep the guard branch from FC0 and use the non-loop block target
  /// from the FC1 guard branch.
  ///    2. Remove the exit block from FC0 (this exit block should be empty
  /// right now).
  ///    3. Remove the guard branch for FC1
  ///    4. Remove the preheader for FC1.
  /// The exit block successor for the latch of FC0 is updated to be the header
  /// of FC1 and the non-exit block successor of the latch of FC1 is updated to
  /// be the header of FC0, thus creating the fused loop.
  Loop *fuseGuardedLoops(const FusionCandidate &FC0,
                         const FusionCandidate &FC1) {
    assert(FC0.GuardBranch && FC1.GuardBranch && "Expecting guarded loops");
 
    BasicBlock *FC0GuardBlock = FC0.GuardBranch->getParent();
    BasicBlock *FC1GuardBlock = FC1.GuardBranch->getParent();
    BasicBlock *FC0NonLoopBlock = FC0.getNonLoopBlock();
    BasicBlock *FC1NonLoopBlock = FC1.getNonLoopBlock();
    BasicBlock *FC0ExitBlockSuccessor = FC0.ExitBlock->getUniqueSuccessor();
 
    // Move instructions from the exit block of FC0 to the beginning of the exit
    // block of FC1, in the case that the FC0 loop has not been peeled. In the
    // case that FC0 loop is peeled, then move the instructions of the successor
    // of the FC0 Exit block to the beginning of the exit block of FC1.
    moveInstructionsToTheBeginning(
        (FC0.Peeled ? *FC0ExitBlockSuccessor : *FC0.ExitBlock), *FC1.ExitBlock,
        DT, PDT, DI, SE);
 
    // Move instructions from the guard block of FC1 to the end of the guard
    // block of FC0.
    moveInstructionsToTheEnd(*FC1GuardBlock, *FC0GuardBlock, DT, PDT, DI, SE);
 
    assert(FC0NonLoopBlock == FC1GuardBlock && "Loops are not adjacent");
 
    SmallVector<DominatorTree::UpdateType, 8> TreeUpdates;
 
    ////////////////////////////////////////////////////////////////////////////
    // Update the Loop Guard
    ////////////////////////////////////////////////////////////////////////////
    // The guard for FC0 is updated to guard both FC0 and FC1. This is done by
    // changing the NonLoopGuardBlock for FC0 to the NonLoopGuardBlock for FC1.
    // Thus, one path from the guard goes to the preheader for FC0 (and thus
    // executes the new fused loop) and the other path goes to the NonLoopBlock
    // for FC1 (where FC1 guard would have gone if FC1 was not executed).
    FC1NonLoopBlock->replacePhiUsesWith(FC1GuardBlock, FC0GuardBlock);
    FC0.GuardBranch->replaceUsesOfWith(FC0NonLoopBlock, FC1NonLoopBlock);
 
    BasicBlock *BBToUpdate = FC0.Peeled ? FC0ExitBlockSuccessor : FC0.ExitBlock;
    BBToUpdate->getTerminator()->replaceUsesOfWith(FC1GuardBlock, FC1.Header);
 
    // The guard of FC1 is not necessary anymore.
    FC1.GuardBranch->eraseFromParent();
    new UnreachableInst(FC1GuardBlock->getContext(), FC1GuardBlock);
 
    TreeUpdates.emplace_back(DominatorTree::UpdateType(
        DominatorTree::Delete, FC1GuardBlock, FC1.Preheader));
    TreeUpdates.emplace_back(DominatorTree::UpdateType(
        DominatorTree::Delete, FC1GuardBlock, FC1NonLoopBlock));
    TreeUpdates.emplace_back(DominatorTree::UpdateType(
        DominatorTree::Delete, FC0GuardBlock, FC1GuardBlock));
    TreeUpdates.emplace_back(DominatorTree::UpdateType(
        DominatorTree::Insert, FC0GuardBlock, FC1NonLoopBlock));
 
    if (FC0.Peeled) {
      TreeUpdates.emplace_back(DominatorTree::UpdateType(
          DominatorTree::Delete, FC0.ExitBlock, FC0ExitBlockSuccessor));
      // Remove the Block after the ExitBlock of FC0
      TreeUpdates.emplace_back(DominatorTree::UpdateType(
          DominatorTree::Delete, FC0ExitBlockSuccessor, FC1GuardBlock));
      FC0ExitBlockSuccessor->getTerminator()->eraseFromParent();
      new UnreachableInst(FC0ExitBlockSuccessor->getContext(),
                          FC0ExitBlockSuccessor);
    }
 
    assert(pred_empty(FC1GuardBlock) &&
           "Expecting guard block to have no predecessors");
    assert(succ_empty(FC1GuardBlock) &&
           "Expecting guard block to have no successors");
 
    // Remember the phi nodes originally in the header of FC0 in order to rewire
    // them later. However, this is only necessary if the new loop carried
    // values might not dominate the exiting branch. While we do not generally
    // test if this is the case but simply insert intermediate phi nodes, we
    // need to make sure these intermediate phi nodes have different
    // predecessors. To this end, we filter the special case where the exiting
    // block is the latch block of the first loop. Nothing needs to be done
    // anyway as all loop carried values dominate the latch and thereby also the
    // exiting branch.
    // KB: This is no longer necessary because FC0.ExitingBlock == FC0.Latch
    // (because the loops are rotated. Thus, nothing will ever be added to
    // OriginalFC0PHIs.
    SmallVector<PHINode *, 8> OriginalFC0PHIs;
    if (FC0.ExitingBlock != FC0.Latch)
      for (PHINode &PHI : FC0.Header->phis())
        OriginalFC0PHIs.push_back(&PHI);
 
    assert(OriginalFC0PHIs.empty() && "Expecting OriginalFC0PHIs to be empty!");
 
    // Replace incoming blocks for header PHIs first.
    FC1.Preheader->replaceSuccessorsPhiUsesWith(FC0.Preheader);
    FC0.Latch->replaceSuccessorsPhiUsesWith(FC1.Latch);
 
    // The old exiting block of the first loop (FC0) has to jump to the header
    // of the second as we need to execute the code in the second header block
    // regardless of the trip count. That is, if the trip count is 0, so the
    // back edge is never taken, we still have to execute both loop headers,
    // especially (but not only!) if the second is a do-while style loop.
    // However, doing so might invalidate the phi nodes of the first loop as
    // the new values do only need to dominate their latch and not the exiting
    // predicate. To remedy this potential problem we always introduce phi
    // nodes in the header of the second loop later that select the loop carried
    // value, if the second header was reached through an old latch of the
    // first, or undef otherwise. This is sound as exiting the first implies the
    // second will exit too, __without__ taking the back-edge (their
    // trip-counts are equal after all).
    FC0.ExitingBlock->getTerminator()->replaceUsesOfWith(FC0.ExitBlock,
                                                         FC1.Header);
 
    TreeUpdates.emplace_back(DominatorTree::UpdateType(
        DominatorTree::Delete, FC0.ExitingBlock, FC0.ExitBlock));
    TreeUpdates.emplace_back(DominatorTree::UpdateType(
        DominatorTree::Insert, FC0.ExitingBlock, FC1.Header));
 
    // Remove FC0 Exit Block
    // The exit block for FC0 is no longer needed since control will flow
    // directly to the header of FC1. Since it is an empty block, it can be
    // removed at this point.
    // TODO: In the future, we can handle non-empty exit blocks my merging any
    // instructions from FC0 exit block into FC1 exit block prior to removing
    // the block.
    assert(pred_empty(FC0.ExitBlock) && "Expecting exit block to be empty");
    FC0.ExitBlock->getTerminator()->eraseFromParent();
    new UnreachableInst(FC0.ExitBlock->getContext(), FC0.ExitBlock);
 
    // Remove FC1 Preheader
    // The pre-header of L1 is not necessary anymore.
    assert(pred_empty(FC1.Preheader));
    FC1.Preheader->getTerminator()->eraseFromParent();
    new UnreachableInst(FC1.Preheader->getContext(), FC1.Preheader);
    TreeUpdates.emplace_back(DominatorTree::UpdateType(
        DominatorTree::Delete, FC1.Preheader, FC1.Header));
 
    rewireFusedHeaderPHIsAndLatches(FC0, FC1, OriginalFC0PHIs, TreeUpdates);
 
    // All done
    // Apply the updates to the Dominator Tree and cleanup.
 
    assert(succ_empty(FC1GuardBlock) && "FC1GuardBlock has successors!!");
    assert(pred_empty(FC1GuardBlock) && "FC1GuardBlock has predecessors!!");
 
    // Update DT/PDT
    DTU.applyUpdates(TreeUpdates);
 
    LI.removeBlock(FC1GuardBlock);
    LI.removeBlock(FC1.Preheader);
    LI.removeBlock(FC0.ExitBlock);
    if (FC0.Peeled) {
      LI.removeBlock(FC0ExitBlockSuccessor);
      DTU.deleteBB(FC0ExitBlockSuccessor);
    }
    DTU.deleteBB(FC1GuardBlock);
    DTU.deleteBB(FC1.Preheader);
    DTU.deleteBB(FC0.ExitBlock);
    DTU.flush();
 
    return finalizeFusedLoop(FC0, FC1);
  }
};
} // namespace
 
PreservedAnalyses LoopFusePass::run(Function &F, FunctionAnalysisManager &AM) {
  auto &LI = AM.getResult<LoopAnalysis>(F);
  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
  auto &DI = AM.getResult<DependenceAnalysis>(F);
  auto &AA = AM.getResult<AAManager>(F);
  auto &SE = AM.getResult<ScalarEvolutionAnalysis>(F);
  auto &PDT = AM.getResult<PostDominatorTreeAnalysis>(F);
  auto &ORE = AM.getResult<OptimizationRemarkEmitterAnalysis>(F);
  auto &AC = AM.getResult<AssumptionAnalysis>(F);
  const TargetTransformInfo &TTI = AM.getResult<TargetIRAnalysis>(F);
 
  // Ensure loops are in simplifed form which is a pre-requisite for loop fusion
  // pass. Added only for new PM since the legacy PM has already added
  // LoopSimplify pass as a dependency.
  bool Changed = false;
  DomTreeUpdater DTU(&DT, DomTreeUpdater::UpdateStrategy::Lazy);
  for (auto &L : LI) {
    Changed |=
        simplifyLoop(L, &DT, &LI, &SE, &AC, nullptr, false /* PreserveLCSSA */);
  }
  for (Loop *L : LI.getLoopsInPreorder()) {
    Changed |= simplifyLoopGuard(L, DTU, LI, SE);
  }
 
  if (Changed)
    PDT.recalculate(F);
 
  LoopFuser LF(ScalarOptions::Global, LI, DT, DI, AA, SE, PDT, ORE, AC, TTI);
  Changed |= LF.fuseLoops(F);
  if (!Changed)
    return PreservedAnalyses::all();
 
  PreservedAnalyses PA;
  PA.preserve<DominatorTreeAnalysis>();
  PA.preserve<PostDominatorTreeAnalysis>();
  PA.preserve<ScalarEvolutionAnalysis>();
  PA.preserve<LoopAnalysis>();
  return PA;
}