Transforms/Scalar/GVNHoist.cpp

//===- GVNHoist.cpp - Hoist scalar and load expressions -------------------===//
//
// 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 hoists expressions from branches to a common dominator. It uses
// GVN (global value numbering) to discover expressions computing the same
// values. The primary goals of code-hoisting are:
// 1. To reduce the code size.
// 2. In some cases reduce critical path (by exposing more ILP).
//
// The algorithm factors out the reachability of values such that multiple
// queries to find reachability of values are fast. This is based on finding the
// ANTIC points in the CFG which do not change during hoisting. The ANTIC points
// are basically the dominance-frontiers in the inverse graph. So we introduce a
// data structure (CHI nodes) to keep track of values flowing out of a basic
// block. We only do this for values with multiple occurrences in the function
// as they are the potential hoistable candidates. This approach allows us to
// hoist instructions to a basic block with more than two successors, as well as
// deal with infinite loops in a trivial way.
//
// Limitations: This pass does not hoist fully redundant expressions because
// they are already handled by GVN-PRE. It is advisable to run gvn-hoist before
// and after gvn-pre because gvn-pre creates opportunities for more instructions
// to be hoisted.
//
// Hoisting may affect the performance in some cases. To mitigate that, hoisting
// is disabled in the following cases.
// 1. Scalars across calls.
// 2. geps when corresponding load/store cannot be hoisted.
//===----------------------------------------------------------------------===//

#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/iterator_range.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/IteratedDominanceFrontier.h"
#include "llvm/Analysis/MemoryDependenceAnalysis.h"
#include "llvm/Analysis/MemorySSA.h"
#include "llvm/Analysis/MemorySSAUpdater.h"
#include "llvm/Analysis/PostDominators.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/Argument.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/Use.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Scalar/GVN.h"
#include "llvm/Transforms/Utils/Local.h"
#include <algorithm>
#include <cassert>
#include <memory>
#include <utility>
#include <vector>

using namespace llvm;

#define DEBUG_TYPE "gvn-hoist"

STATISTIC(NumHoisted, "Number of instructions hoisted");
STATISTIC(NumRemoved, "Number of instructions removed");
STATISTIC(NumLoadsHoisted, "Number of loads hoisted");
STATISTIC(NumLoadsRemoved, "Number of loads removed");
STATISTIC(NumStoresHoisted, "Number of stores hoisted");
STATISTIC(NumStoresRemoved, "Number of stores removed");
STATISTIC(NumCallsHoisted, "Number of calls hoisted");
STATISTIC(NumCallsRemoved, "Number of calls removed");

static cl::opt<int>
    MaxHoistedThreshold("gvn-max-hoisted", cl::Hidden, cl::init(-1),
                        cl::desc("Max number of instructions to hoist "
                                 "(default unlimited = -1)"));

static cl::opt<int> MaxNumberOfBBSInPath(
    "gvn-hoist-max-bbs", cl::Hidden, cl::init(4),
    cl::desc("Max number of basic blocks on the path between "
             "hoisting locations (default = 4, unlimited = -1)"));

static cl::opt<int> MaxDepthInBB(
    "gvn-hoist-max-depth", cl::Hidden, cl::init(100),
    cl::desc("Hoist instructions from the beginning of the BB up to the "
             "maximum specified depth (default = 100, unlimited = -1)"));

static cl::opt<int>
    MaxChainLength("gvn-hoist-max-chain-length", cl::Hidden, cl::init(10),
                   cl::desc("Maximum length of dependent chains to hoist "
                            "(default = 10, unlimited = -1)"));

namespace llvm {

using BBSideEffectsSet = DenseMap<const BasicBlock *, bool>;
using SmallVecInsn = SmallVector<Instruction *, 4>;
using SmallVecImplInsn = SmallVectorImpl<Instruction *>;

// Each element of a hoisting list contains the basic block where to hoist and
// a list of instructions to be hoisted.
using HoistingPointInfo = std::pair<BasicBlock *, SmallVecInsn>;

using HoistingPointList = SmallVector<HoistingPointInfo, 4>;

// A map from a pair of VNs to all the instructions with those VNs.
using VNType = std::pair<unsigned, uintptr_t>;

using VNtoInsns = DenseMap<VNType, SmallVector<Instruction *, 4>>;

// CHI keeps information about values flowing out of a basic block.  It is
// similar to PHI but in the inverse graph, and used for outgoing values on each
// edge. For conciseness, it is computed only for instructions with multiple
// occurrences in the CFG because they are the only hoistable candidates.
//     A (CHI[{V, B, I1}, {V, C, I2}]
//  /     \
// /       \
// B(I1)  C (I2)
// The Value number for both I1 and I2 is V, the CHI node will save the
// instruction as well as the edge where the value is flowing to.
struct CHIArg {
  VNType VN;

  // Edge destination (shows the direction of flow), may not be where the I is.
  BasicBlock *Dest;

  // The instruction (VN) which uses the values flowing out of CHI.
  Instruction *I;

  bool operator==(const CHIArg &A) const { return VN == A.VN; }
  bool operator!=(const CHIArg &A) const { return !(*this == A); }
};

using CHIIt = SmallVectorImpl<CHIArg>::iterator;
using CHIArgs = iterator_range<CHIIt>;
using OutValuesType = DenseMap<BasicBlock *, SmallVector<CHIArg, 2>>;
using InValuesType =
    DenseMap<BasicBlock *, SmallVector<std::pair<VNType, Instruction *>, 2>>;

// An invalid value number Used when inserting a single value number into
// VNtoInsns.
enum : uintptr_t { InvalidVN = ~(uintptr_t)2 };

// Records all scalar instructions candidate for code hoisting.
class InsnInfo {
  VNtoInsns VNtoScalars;

public:
  // Inserts I and its value number in VNtoScalars.
  void insert(Instruction *I, GVNPass::ValueTable &VN) {
    // Scalar instruction.
    unsigned V = VN.lookupOrAdd(I);
    VNtoScalars[{V, InvalidVN}].push_back(I);
  }

  const VNtoInsns &getVNTable() const { return VNtoScalars; }
};

// Records all load instructions candidate for code hoisting.
class LoadInfo {
  VNtoInsns VNtoLoads;

public:
  // Insert Load and the value number of its memory address in VNtoLoads.
  void insert(LoadInst *Load, GVNPass::ValueTable &VN) {
    if (Load->isSimple()) {
      unsigned V = VN.lookupOrAdd(Load->getPointerOperand());
      // With opaque pointers we may have loads from the same pointer with
      // different result types, which should be disambiguated.
      VNtoLoads[{V, (uintptr_t)Load->getType()}].push_back(Load);
    }
  }

  const VNtoInsns &getVNTable() const { return VNtoLoads; }
};

// Records all store instructions candidate for code hoisting.
class StoreInfo {
  VNtoInsns VNtoStores;

public:
  // Insert the Store and a hash number of the store address and the stored
  // value in VNtoStores.
  void insert(StoreInst *Store, GVNPass::ValueTable &VN) {
    if (!Store->isSimple())
      return;
    // Hash the store address and the stored value.
    Value *Ptr = Store->getPointerOperand();
    Value *Val = Store->getValueOperand();
    VNtoStores[{VN.lookupOrAdd(Ptr), VN.lookupOrAdd(Val)}].push_back(Store);
  }

  const VNtoInsns &getVNTable() const { return VNtoStores; }
};

// Records all call instructions candidate for code hoisting.
class CallInfo {
  VNtoInsns VNtoCallsScalars;
  VNtoInsns VNtoCallsLoads;
  VNtoInsns VNtoCallsStores;

public:
  // Insert Call and its value numbering in one of the VNtoCalls* containers.
  void insert(CallInst *Call, GVNPass::ValueTable &VN) {
    // A call that doesNotAccessMemory is handled as a Scalar,
    // onlyReadsMemory will be handled as a Load instruction,
    // all other calls will be handled as stores.
    unsigned V = VN.lookupOrAdd(Call);
    auto Entry = std::make_pair(V, InvalidVN);

    if (Call->doesNotAccessMemory())
      VNtoCallsScalars[Entry].push_back(Call);
    else if (Call->onlyReadsMemory())
      VNtoCallsLoads[Entry].push_back(Call);
    else
      VNtoCallsStores[Entry].push_back(Call);
  }

  const VNtoInsns &getScalarVNTable() const { return VNtoCallsScalars; }
  const VNtoInsns &getLoadVNTable() const { return VNtoCallsLoads; }
  const VNtoInsns &getStoreVNTable() const { return VNtoCallsStores; }
};

// This pass hoists common computations across branches sharing common
// dominator. The primary goal is to reduce the code size, and in some
// cases reduce critical path (by exposing more ILP).
class GVNHoist {
public:
  GVNHoist(DominatorTree *DT, PostDominatorTree *PDT, AliasAnalysis *AA,
           MemoryDependenceResults *MD, MemorySSA *MSSA)
      : DT(DT), PDT(PDT), AA(AA), MD(MD), MSSA(MSSA),
        MSSAUpdater(std::make_unique<MemorySSAUpdater>(MSSA)) {
    MSSA->ensureOptimizedUses();
  }

  bool run(Function &F);

  // Copied from NewGVN.cpp
  // This function provides global ranking of operations so that we can place
  // them in a canonical order.  Note that rank alone is not necessarily enough
  // for a complete ordering, as constants all have the same rank.  However,
  // generally, we will simplify an operation with all constants so that it
  // doesn't matter what order they appear in.
  unsigned int rank(const Value *V) const;

private:
  GVNPass::ValueTable VN;
  DominatorTree *DT;
  PostDominatorTree *PDT;
  AliasAnalysis *AA;
  MemoryDependenceResults *MD;
  MemorySSA *MSSA;
  std::unique_ptr<MemorySSAUpdater> MSSAUpdater;
  DenseMap<const Value *, unsigned> DFSNumber;
  BBSideEffectsSet BBSideEffects;
  DenseSet<const BasicBlock *> HoistBarrier;
  SmallVector<BasicBlock *, 32> IDFBlocks;
  unsigned NumFuncArgs;
  const bool HoistingGeps = false;

  enum InsKind { Unknown, Scalar, Load, Store };

  // Return true when there are exception handling in BB.
  bool hasEH(const BasicBlock *BB);

  // Return true when I1 appears before I2 in the instructions of BB.
  bool firstInBB(const Instruction *I1, const Instruction *I2) {
    assert(I1->getParent() == I2->getParent());
    unsigned I1DFS = DFSNumber.lookup(I1);
    unsigned I2DFS = DFSNumber.lookup(I2);
    assert(I1DFS && I2DFS);
    return I1DFS < I2DFS;
  }

  // Return true when there are memory uses of Def in BB.
  bool hasMemoryUse(const Instruction *NewPt, MemoryDef *Def,
                    const BasicBlock *BB);

  bool hasEHhelper(const BasicBlock *BB, const BasicBlock *SrcBB,
                   int &NBBsOnAllPaths);

  // Return true when there are exception handling or loads of memory Def
  // between Def and NewPt.  This function is only called for stores: Def is
  // the MemoryDef of the store to be hoisted.

  // Decrement by 1 NBBsOnAllPaths for each block between HoistPt and BB, and
  // return true when the counter NBBsOnAllPaths reaces 0, except when it is
  // initialized to -1 which is unlimited.
  bool hasEHOrLoadsOnPath(const Instruction *NewPt, MemoryDef *Def,
                          int &NBBsOnAllPaths);

  // Return true when there are exception handling between HoistPt and BB.
  // Decrement by 1 NBBsOnAllPaths for each block between HoistPt and BB, and
  // return true when the counter NBBsOnAllPaths reaches 0, except when it is
  // initialized to -1 which is unlimited.
  bool hasEHOnPath(const BasicBlock *HoistPt, const BasicBlock *SrcBB,
                   int &NBBsOnAllPaths);

  // Return true when it is safe to hoist a memory load or store U from OldPt
  // to NewPt.
  bool safeToHoistLdSt(const Instruction *NewPt, const Instruction *OldPt,
                       MemoryUseOrDef *U, InsKind K, int &NBBsOnAllPaths);

  // Return true when it is safe to hoist scalar instructions from all blocks in
  // WL to HoistBB.
  bool safeToHoistScalar(const BasicBlock *HoistBB, const BasicBlock *BB,
                         int &NBBsOnAllPaths) {
    return !hasEHOnPath(HoistBB, BB, NBBsOnAllPaths);
  }

  // In the inverse CFG, the dominance frontier of basic block (BB) is the
  // point where ANTIC needs to be computed for instructions which are going
  // to be hoisted. Since this point does not change during gvn-hoist,
  // we compute it only once (on demand).
  // The ides is inspired from:
  // "Partial Redundancy Elimination in SSA Form"
  // ROBERT KENNEDY, SUN CHAN, SHIN-MING LIU, RAYMOND LO, PENG TU and FRED CHOW
  // They use similar idea in the forward graph to find fully redundant and
  // partially redundant expressions, here it is used in the inverse graph to
  // find fully anticipable instructions at merge point (post-dominator in
  // the inverse CFG).
  // Returns the edge via which an instruction in BB will get the values from.

  // Returns true when the values are flowing out to each edge.
  bool valueAnticipable(CHIArgs C, Instruction *TI) const;

  // Check if it is safe to hoist values tracked by CHI in the range
  // [Begin, End) and accumulate them in Safe.
  void checkSafety(CHIArgs C, BasicBlock *BB, InsKind K,
                   SmallVectorImpl<CHIArg> &Safe);

  using RenameStackType = DenseMap<VNType, SmallVector<Instruction *, 2>>;

  // Push all the VNs corresponding to BB into RenameStack.
  void fillRenameStack(BasicBlock *BB, InValuesType &ValueBBs,
                       RenameStackType &RenameStack);

  void fillChiArgs(BasicBlock *BB, OutValuesType &CHIBBs,
                   RenameStackType &RenameStack);

  // Walk the post-dominator tree top-down and use a stack for each value to
  // store the last value you see. When you hit a CHI from a given edge, the
  // value to use as the argument is at the top of the stack, add the value to
  // CHI and pop.
  void insertCHI(InValuesType &ValueBBs, OutValuesType &CHIBBs) {
    auto Root = PDT->getNode(nullptr);
    if (!Root)
      return;
    // Depth first walk on PDom tree to fill the CHIargs at each PDF.
    for (auto *Node : depth_first(Root)) {
      BasicBlock *BB = Node->getBlock();
      if (!BB)
        continue;

      RenameStackType RenameStack;
      // Collect all values in BB and push to stack.
      fillRenameStack(BB, ValueBBs, RenameStack);

      // Fill outgoing values in each CHI corresponding to BB.
      fillChiArgs(BB, CHIBBs, RenameStack);
    }
  }

  // Walk all the CHI-nodes to find ones which have a empty-entry and remove
  // them Then collect all the instructions which are safe to hoist and see if
  // they form a list of anticipable values. OutValues contains CHIs
  // corresponding to each basic block.
  void findHoistableCandidates(OutValuesType &CHIBBs, InsKind K,
                               HoistingPointList &HPL);

  // Compute insertion points for each values which can be fully anticipated at
  // a dominator. HPL contains all such values.
  void computeInsertionPoints(const VNtoInsns &Map, HoistingPointList &HPL,
                              InsKind K) {
    // Sort VNs based on their rankings
    std::vector<VNType> Ranks;
    for (const auto &Entry : Map) {
      Ranks.push_back(Entry.first);
    }

    // TODO: Remove fully-redundant expressions.
    // Get instruction from the Map, assume that all the Instructions
    // with same VNs have same rank (this is an approximation).
    llvm::sort(Ranks, [this, &Map](const VNType &r1, const VNType &r2) {
      return (rank(*Map.lookup(r1).begin()) < rank(*Map.lookup(r2).begin()));
    });

    // - Sort VNs according to their rank, and start with lowest ranked VN
    // - Take a VN and for each instruction with same VN
    //   - Find the dominance frontier in the inverse graph (PDF)
    //   - Insert the chi-node at PDF
    // - Remove the chi-nodes with missing entries
    // - Remove values from CHI-nodes which do not truly flow out, e.g.,
    //   modified along the path.
    // - Collect the remaining values that are still anticipable
    SmallVector<BasicBlock *, 2> IDFBlocks;
    ReverseIDFCalculator IDFs(*PDT);
    OutValuesType OutValue;
    InValuesType InValue;
    for (const auto &R : Ranks) {
      const SmallVecInsn &V = Map.lookup(R);
      if (V.size() < 2)
        continue;
      const VNType &VN = R;
      SmallPtrSet<BasicBlock *, 2> VNBlocks;
      for (const auto &I : V) {
        BasicBlock *BBI = I->getParent();
        if (!hasEH(BBI))
          VNBlocks.insert(BBI);
      }
      // Compute the Post Dominance Frontiers of each basic block
      // The dominance frontier of a live block X in the reverse
      // control graph is the set of blocks upon which X is control
      // dependent. The following sequence computes the set of blocks
      // which currently have dead terminators that are control
      // dependence sources of a block which is in NewLiveBlocks.
      IDFs.setDefiningBlocks(VNBlocks);
      IDFBlocks.clear();
      IDFs.calculate(IDFBlocks);

      // Make a map of BB vs instructions to be hoisted.
      for (unsigned i = 0; i < V.size(); ++i) {
        InValue[V[i]->getParent()].push_back(std::make_pair(VN, V[i]));
      }
      // Insert empty CHI node for this VN. This is used to factor out
      // basic blocks where the ANTIC can potentially change.
      CHIArg EmptyChi = {VN, nullptr, nullptr};
      for (auto *IDFBB : IDFBlocks) {
        for (unsigned i = 0; i < V.size(); ++i) {
          // Ignore spurious PDFs.
          if (DT->properlyDominates(IDFBB, V[i]->getParent())) {
            OutValue[IDFBB].push_back(EmptyChi);
            LLVM_DEBUG(dbgs() << "\nInserting a CHI for BB: "
                              << IDFBB->getName() << ", for Insn: " << *V[i]);
          }
        }
      }
    }

    // Insert CHI args at each PDF to iterate on factored graph of
    // control dependence.
    insertCHI(InValue, OutValue);
    // Using the CHI args inserted at each PDF, find fully anticipable values.
    findHoistableCandidates(OutValue, K, HPL);
  }

  // Return true when all operands of Instr are available at insertion point
  // HoistPt. When limiting the number of hoisted expressions, one could hoist
  // a load without hoisting its access function. So before hoisting any
  // expression, make sure that all its operands are available at insert point.
  bool allOperandsAvailable(const Instruction *I,
                            const BasicBlock *HoistPt) const;

  // Same as allOperandsAvailable with recursive check for GEP operands.
  bool allGepOperandsAvailable(const Instruction *I,
                               const BasicBlock *HoistPt) const;

  // Make all operands of the GEP available.
  void makeGepsAvailable(Instruction *Repl, BasicBlock *HoistPt,
                         const SmallVecInsn &InstructionsToHoist,
                         Instruction *Gep) const;

  void updateAlignment(Instruction *I, Instruction *Repl);

  // Remove all the instructions in Candidates and replace their usage with
  // Repl. Returns the number of instructions removed.
  unsigned rauw(const SmallVecInsn &Candidates, Instruction *Repl,
                MemoryUseOrDef *NewMemAcc);

  // Replace all Memory PHI usage with NewMemAcc.
  void raMPHIuw(MemoryUseOrDef *NewMemAcc);

  // Remove all other instructions and replace them with Repl.
  unsigned removeAndReplace(const SmallVecInsn &Candidates, Instruction *Repl,
                            BasicBlock *DestBB, bool MoveAccess);

  // In the case Repl is a load or a store, we make all their GEPs
  // available: GEPs are not hoisted by default to avoid the address
  // computations to be hoisted without the associated load or store.
  bool makeGepOperandsAvailable(Instruction *Repl, BasicBlock *HoistPt,
                                const SmallVecInsn &InstructionsToHoist) const;

  std::pair<unsigned, unsigned> hoist(HoistingPointList &HPL);

  // Hoist all expressions. Returns Number of scalars hoisted
  // and number of non-scalars hoisted.
  std::pair<unsigned, unsigned> hoistExpressions(Function &F);
};

bool GVNHoist::run(Function &F) {
  NumFuncArgs = F.arg_size();
  VN.setDomTree(DT);
  VN.setAliasAnalysis(AA);
  VN.setMemDep(MD);
  bool Res = false;
  // Perform DFS Numbering of instructions.
  unsigned BBI = 0;
  for (const BasicBlock *BB : depth_first(&F.getEntryBlock())) {
    DFSNumber[BB] = ++BBI;
    unsigned I = 0;
    for (const auto &Inst : *BB)
      DFSNumber[&Inst] = ++I;
  }

  int ChainLength = 0;

  // FIXME: use lazy evaluation of VN to avoid the fix-point computation.
  while (true) {
    if (MaxChainLength != -1 && ++ChainLength >= MaxChainLength)
      return Res;

    auto HoistStat = hoistExpressions(F);
    if (HoistStat.first + HoistStat.second == 0)
      return Res;

    if (HoistStat.second > 0)
      // To address a limitation of the current GVN, we need to rerun the
      // hoisting after we hoisted loads or stores in order to be able to
      // hoist all scalars dependent on the hoisted ld/st.
      VN.clear();

    Res = true;
  }

  return Res;
}

unsigned int GVNHoist::rank(const Value *V) const {
  // Prefer constants to undef to anything else
  // Undef is a constant, have to check it first.
  // Prefer smaller constants to constantexprs
  if (isa<ConstantExpr>(V))
    return 2;
  if (isa<UndefValue>(V))
    return 1;
  if (isa<Constant>(V))
    return 0;
  else if (auto *A = dyn_cast<Argument>(V))
    return 3 + A->getArgNo();

  // Need to shift the instruction DFS by number of arguments + 3 to account
  // for the constant and argument ranking above.
  auto Result = DFSNumber.lookup(V);
  if (Result > 0)
    return 4 + NumFuncArgs + Result;
  // Unreachable or something else, just return a really large number.
  return ~0;
}

bool GVNHoist::hasEH(const BasicBlock *BB) {
  auto It = BBSideEffects.find(BB);
  if (It != BBSideEffects.end())
    return It->second;

  if (BB->isEHPad() || BB->hasAddressTaken()) {
    BBSideEffects[BB] = true;
    return true;
  }

  if (BB->getTerminator()->mayThrow()) {
    BBSideEffects[BB] = true;
    return true;
  }

  BBSideEffects[BB] = false;
  return false;
}

bool GVNHoist::hasMemoryUse(const Instruction *NewPt, MemoryDef *Def,
                            const BasicBlock *BB) {
  const MemorySSA::AccessList *Acc = MSSA->getBlockAccesses(BB);
  if (!Acc)
    return false;

  Instruction *OldPt = Def->getMemoryInst();
  const BasicBlock *OldBB = OldPt->getParent();
  const BasicBlock *NewBB = NewPt->getParent();
  bool ReachedNewPt = false;

  for (const MemoryAccess &MA : *Acc)
    if (const MemoryUse *MU = dyn_cast<MemoryUse>(&MA)) {
      Instruction *Insn = MU->getMemoryInst();

      // Do not check whether MU aliases Def when MU occurs after OldPt.
      if (BB == OldBB && firstInBB(OldPt, Insn))
        break;

      // Do not check whether MU aliases Def when MU occurs before NewPt.
      if (BB == NewBB) {
        if (!ReachedNewPt) {
          if (firstInBB(Insn, NewPt))
            continue;
          ReachedNewPt = true;
        }
      }
      if (MemorySSAUtil::defClobbersUseOrDef(Def, MU, *AA))
        return true;
    }

  return false;
}

bool GVNHoist::hasEHhelper(const BasicBlock *BB, const BasicBlock *SrcBB,
                           int &NBBsOnAllPaths) {
  // Stop walk once the limit is reached.
  if (NBBsOnAllPaths == 0)
    return true;

  // Impossible to hoist with exceptions on the path.
  if (hasEH(BB))
    return true;

  // No such instruction after HoistBarrier in a basic block was
  // selected for hoisting so instructions selected within basic block with
  // a hoist barrier can be hoisted.
  if ((BB != SrcBB) && HoistBarrier.count(BB))
    return true;

  return false;
}

bool GVNHoist::hasEHOrLoadsOnPath(const Instruction *NewPt, MemoryDef *Def,
                                  int &NBBsOnAllPaths) {
  const BasicBlock *NewBB = NewPt->getParent();
  const BasicBlock *OldBB = Def->getBlock();
  assert(DT->dominates(NewBB, OldBB) && "invalid path");
  assert(DT->dominates(Def->getDefiningAccess()->getBlock(), NewBB) &&
         "def does not dominate new hoisting point");

  // Walk all basic blocks reachable in depth-first iteration on the inverse
  // CFG from OldBB to NewBB. These blocks are all the blocks that may be
  // executed between the execution of NewBB and OldBB. Hoisting an expression
  // from OldBB into NewBB has to be safe on all execution paths.
  for (auto I = idf_begin(OldBB), E = idf_end(OldBB); I != E;) {
    const BasicBlock *BB = *I;
    if (BB == NewBB) {
      // Stop traversal when reaching HoistPt.
      I.skipChildren();
      continue;
    }

    if (hasEHhelper(BB, OldBB, NBBsOnAllPaths))
      return true;

    // Check that we do not move a store past loads.
    if (hasMemoryUse(NewPt, Def, BB))
      return true;

    // -1 is unlimited number of blocks on all paths.
    if (NBBsOnAllPaths != -1)
      --NBBsOnAllPaths;

    ++I;
  }

  return false;
}

bool GVNHoist::hasEHOnPath(const BasicBlock *HoistPt, const BasicBlock *SrcBB,
                           int &NBBsOnAllPaths) {
  assert(DT->dominates(HoistPt, SrcBB) && "Invalid path");

  // Walk all basic blocks reachable in depth-first iteration on
  // the inverse CFG from BBInsn to NewHoistPt. These blocks are all the
  // blocks that may be executed between the execution of NewHoistPt and
  // BBInsn. Hoisting an expression from BBInsn into NewHoistPt has to be safe
  // on all execution paths.
  for (auto I = idf_begin(SrcBB), E = idf_end(SrcBB); I != E;) {
    const BasicBlock *BB = *I;
    if (BB == HoistPt) {
      // Stop traversal when reaching NewHoistPt.
      I.skipChildren();
      continue;
    }

    if (hasEHhelper(BB, SrcBB, NBBsOnAllPaths))
      return true;

    // -1 is unlimited number of blocks on all paths.
    if (NBBsOnAllPaths != -1)
      --NBBsOnAllPaths;

    ++I;
  }

  return false;
}

bool GVNHoist::safeToHoistLdSt(const Instruction *NewPt,
                               const Instruction *OldPt, MemoryUseOrDef *U,
                               GVNHoist::InsKind K, int &NBBsOnAllPaths) {
  // In place hoisting is safe.
  if (NewPt == OldPt)
    return true;

  const BasicBlock *NewBB = NewPt->getParent();
  const BasicBlock *OldBB = OldPt->getParent();
  const BasicBlock *UBB = U->getBlock();

  // Check for dependences on the Memory SSA.
  MemoryAccess *D = U->getDefiningAccess();
  BasicBlock *DBB = D->getBlock();
  if (DT->properlyDominates(NewBB, DBB))
    // Cannot move the load or store to NewBB above its definition in DBB.
    return false;

  if (NewBB == DBB && !MSSA->isLiveOnEntryDef(D))
    if (auto *UD = dyn_cast<MemoryUseOrDef>(D))
      if (!firstInBB(UD->getMemoryInst(), NewPt))
        // Cannot move the load or store to NewPt above its definition in D.
        return false;

  // Check for unsafe hoistings due to side effects.
  if (K == InsKind::Store) {
    if (hasEHOrLoadsOnPath(NewPt, cast<MemoryDef>(U), NBBsOnAllPaths))
      return false;
  } else if (hasEHOnPath(NewBB, OldBB, NBBsOnAllPaths))
    return false;

  if (UBB == NewBB) {
    if (DT->properlyDominates(DBB, NewBB))
      return true;
    assert(UBB == DBB);
    assert(MSSA->locallyDominates(D, U));
  }

  // No side effects: it is safe to hoist.
  return true;
}

bool GVNHoist::valueAnticipable(CHIArgs C, Instruction *TI) const {
  if (TI->getNumSuccessors() > (unsigned)size(C))
    return false; // Not enough args in this CHI.

  for (auto CHI : C) {
    // Find if all the edges have values flowing out of BB.
    if (!llvm::is_contained(successors(TI), CHI.Dest))
      return false;
  }
  return true;
}

void GVNHoist::checkSafety(CHIArgs C, BasicBlock *BB, GVNHoist::InsKind K,
                           SmallVectorImpl<CHIArg> &Safe) {
  int NumBBsOnAllPaths = MaxNumberOfBBSInPath;
  const Instruction *T = BB->getTerminator();
  for (auto CHI : C) {
    Instruction *Insn = CHI.I;
    if (!Insn) // No instruction was inserted in this CHI.
      continue;
    // If the Terminator is some kind of "exotic terminator" that produces a
    // value (such as InvokeInst, CallBrInst, or CatchSwitchInst) which the CHI
    // uses, it is not safe to hoist the use above the def.
    if (!T->use_empty() && is_contained(Insn->operands(), cast<const Value>(T)))
      continue;
    if (K == InsKind::Scalar) {
      if (safeToHoistScalar(BB, Insn->getParent(), NumBBsOnAllPaths))
        Safe.push_back(CHI);
    } else {
      if (MemoryUseOrDef *UD = MSSA->getMemoryAccess(Insn))
        if (safeToHoistLdSt(T, Insn, UD, K, NumBBsOnAllPaths))
          Safe.push_back(CHI);
    }
  }
}

void GVNHoist::fillRenameStack(BasicBlock *BB, InValuesType &ValueBBs,
                               GVNHoist::RenameStackType &RenameStack) {
  auto it1 = ValueBBs.find(BB);
  if (it1 != ValueBBs.end()) {
    // Iterate in reverse order to keep lower ranked values on the top.
    LLVM_DEBUG(dbgs() << "\nVisiting: " << BB->getName()
                      << " for pushing instructions on stack";);
    for (std::pair<VNType, Instruction *> &VI : reverse(it1->second)) {
      // Get the value of instruction I
      LLVM_DEBUG(dbgs() << "\nPushing on stack: " << *VI.second);
      RenameStack[VI.first].push_back(VI.second);
    }
  }
}

void GVNHoist::fillChiArgs(BasicBlock *BB, OutValuesType &CHIBBs,
                           GVNHoist::RenameStackType &RenameStack) {
  // For each *predecessor* (because Post-DOM) of BB check if it has a CHI
  for (auto *Pred : predecessors(BB)) {
    auto P = CHIBBs.find(Pred);
    if (P == CHIBBs.end()) {
      continue;
    }
    LLVM_DEBUG(dbgs() << "\nLooking at CHIs in: " << Pred->getName(););
    // A CHI is found (BB -> Pred is an edge in the CFG)
    // Pop the stack until Top(V) = Ve.
    auto &VCHI = P->second;
    for (auto It = VCHI.begin(), E = VCHI.end(); It != E;) {
      CHIArg &C = *It;
      if (!C.Dest) {
        auto si = RenameStack.find(C.VN);
        // The Basic Block where CHI is must dominate the value we want to
        // track in a CHI. In the PDom walk, there can be values in the
        // stack which are not control dependent e.g., nested loop.
        if (si != RenameStack.end() && si->second.size() &&
            DT->properlyDominates(Pred, si->second.back()->getParent())) {
          C.Dest = BB;                     // Assign the edge
          C.I = si->second.pop_back_val(); // Assign the argument
          LLVM_DEBUG(dbgs()
                     << "\nCHI Inserted in BB: " << C.Dest->getName() << *C.I
                     << ", VN: " << C.VN.first << ", " << C.VN.second);
        }
        // Move to next CHI of a different value
        It = std::find_if(It, VCHI.end(), [It](CHIArg &A) { return A != *It; });
      } else
        ++It;
    }
  }
}

void GVNHoist::findHoistableCandidates(OutValuesType &CHIBBs,
                                       GVNHoist::InsKind K,
                                       HoistingPointList &HPL) {
  auto cmpVN = [](const CHIArg &A, const CHIArg &B) { return A.VN < B.VN; };

  // CHIArgs now have the outgoing values, so check for anticipability and
  // accumulate hoistable candidates in HPL.
  for (std::pair<BasicBlock *, SmallVector<CHIArg, 2>> &A : CHIBBs) {
    BasicBlock *BB = A.first;
    SmallVectorImpl<CHIArg> &CHIs = A.second;
    // Vector of PHIs contains PHIs for different instructions.
    // Sort the args according to their VNs, such that identical
    // instructions are together.
    llvm::stable_sort(CHIs, cmpVN);
    auto TI = BB->getTerminator();
    auto B = CHIs.begin();
    // [PreIt, PHIIt) form a range of CHIs which have identical VNs.
    auto PHIIt = llvm::find_if(CHIs, [B](CHIArg &A) { return A != *B; });
    auto PrevIt = CHIs.begin();
    while (PrevIt != PHIIt) {
      // Collect values which satisfy safety checks.
      SmallVector<CHIArg, 2> Safe;
      // We check for safety first because there might be multiple values in
      // the same path, some of which are not safe to be hoisted, but overall
      // each edge has at least one value which can be hoisted, making the
      // value anticipable along that path.
      checkSafety(make_range(PrevIt, PHIIt), BB, K, Safe);

      // List of safe values should be anticipable at TI.
      if (valueAnticipable(make_range(Safe.begin(), Safe.end()), TI)) {
        HPL.push_back({BB, SmallVecInsn()});
        SmallVecInsn &V = HPL.back().second;
        for (auto B : Safe)
          V.push_back(B.I);
      }

      // Check other VNs
      PrevIt = PHIIt;
      PHIIt = std::find_if(PrevIt, CHIs.end(),
                           [PrevIt](CHIArg &A) { return A != *PrevIt; });
    }
  }
}

bool GVNHoist::allOperandsAvailable(const Instruction *I,
                                    const BasicBlock *HoistPt) const {
  for (const Use &Op : I->operands())
    if (const auto *Inst = dyn_cast<Instruction>(&Op))
      if (!DT->dominates(Inst->getParent(), HoistPt))
        return false;

  return true;
}

bool GVNHoist::allGepOperandsAvailable(const Instruction *I,
                                       const BasicBlock *HoistPt) const {
  for (const Use &Op : I->operands())
    if (const auto *Inst = dyn_cast<Instruction>(&Op))
      if (!DT->dominates(Inst->getParent(), HoistPt)) {
        if (const GetElementPtrInst *GepOp =
                dyn_cast<GetElementPtrInst>(Inst)) {
          if (!allGepOperandsAvailable(GepOp, HoistPt))
            return false;
          // Gep is available if all operands of GepOp are available.
        } else {
          // Gep is not available if it has operands other than GEPs that are
          // defined in blocks not dominating HoistPt.
          return false;
        }
      }
  return true;
}

void GVNHoist::makeGepsAvailable(Instruction *Repl, BasicBlock *HoistPt,
                                 const SmallVecInsn &InstructionsToHoist,
                                 Instruction *Gep) const {
  assert(allGepOperandsAvailable(Gep, HoistPt) && "GEP operands not available");

  Instruction *ClonedGep = Gep->clone();
  for (unsigned i = 0, e = Gep->getNumOperands(); i != e; ++i)
    if (Instruction *Op = dyn_cast<Instruction>(Gep->getOperand(i))) {
      // Check whether the operand is already available.
      if (DT->dominates(Op->getParent(), HoistPt))
        continue;

      // As a GEP can refer to other GEPs, recursively make all the operands
      // of this GEP available at HoistPt.
      if (GetElementPtrInst *GepOp = dyn_cast<GetElementPtrInst>(Op))
        makeGepsAvailable(ClonedGep, HoistPt, InstructionsToHoist, GepOp);
    }

  // Copy Gep and replace its uses in Repl with ClonedGep.
  ClonedGep->insertBefore(HoistPt->getTerminator()->getIterator());

  // Conservatively discard any optimization hints, they may differ on the
  // other paths.
  ClonedGep->dropUnknownNonDebugMetadata();

  // If we have optimization hints which agree with each other along different
  // paths, preserve them.
  for (const Instruction *OtherInst : InstructionsToHoist) {
    const GetElementPtrInst *OtherGep;
    if (auto *OtherLd = dyn_cast<LoadInst>(OtherInst))
      OtherGep = cast<GetElementPtrInst>(OtherLd->getPointerOperand());
    else
      OtherGep = cast<GetElementPtrInst>(
          cast<StoreInst>(OtherInst)->getPointerOperand());
    ClonedGep->andIRFlags(OtherGep);

    // Merge debug locations of GEPs, because the hoisted GEP replaces those
    // in branches. When cloning, ClonedGep preserves the debug location of
    // Gepd, so Gep is skipped to avoid merging it twice.
    if (OtherGep != Gep) {
      ClonedGep->applyMergedLocation(ClonedGep->getDebugLoc(),
                                     OtherGep->getDebugLoc());
    }
  }

  // Replace uses of Gep with ClonedGep in Repl.
  Repl->replaceUsesOfWith(Gep, ClonedGep);
}

void GVNHoist::updateAlignment(Instruction *I, Instruction *Repl) {
  if (auto *ReplacementLoad = dyn_cast<LoadInst>(Repl)) {
    ReplacementLoad->setAlignment(
        std::min(ReplacementLoad->getAlign(), cast<LoadInst>(I)->getAlign()));
    ++NumLoadsRemoved;
  } else if (auto *ReplacementStore = dyn_cast<StoreInst>(Repl)) {
    ReplacementStore->setAlignment(
        std::min(ReplacementStore->getAlign(), cast<StoreInst>(I)->getAlign()));
    ++NumStoresRemoved;
  } else if (auto *ReplacementAlloca = dyn_cast<AllocaInst>(Repl)) {
    ReplacementAlloca->setAlignment(std::max(ReplacementAlloca->getAlign(),
                                             cast<AllocaInst>(I)->getAlign()));
  } else if (isa<CallInst>(Repl)) {
    ++NumCallsRemoved;
  }
}

unsigned GVNHoist::rauw(const SmallVecInsn &Candidates, Instruction *Repl,
                        MemoryUseOrDef *NewMemAcc) {
  unsigned NR = 0;
  for (Instruction *I : Candidates) {
    if (I != Repl) {
      ++NR;
      updateAlignment(I, Repl);
      if (NewMemAcc) {
        // Update the uses of the old MSSA access with NewMemAcc.
        MemoryAccess *OldMA = MSSA->getMemoryAccess(I);
        OldMA->replaceAllUsesWith(NewMemAcc);
        MSSAUpdater->removeMemoryAccess(OldMA);
      }

      combineMetadataForCSE(Repl, I, true);
      Repl->andIRFlags(I);
      I->replaceAllUsesWith(Repl);
      // Also invalidate the Alias Analysis cache.
      MD->removeInstruction(I);
      I->eraseFromParent();
    }
  }
  return NR;
}

void GVNHoist::raMPHIuw(MemoryUseOrDef *NewMemAcc) {
  SmallPtrSet<MemoryPhi *, 4> UsePhis;
  for (User *U : NewMemAcc->users())
    if (MemoryPhi *Phi = dyn_cast<MemoryPhi>(U))
      UsePhis.insert(Phi);

  for (MemoryPhi *Phi : UsePhis) {
    auto In = Phi->incoming_values();
    if (llvm::all_of(In, [&](Use &U) { return U == NewMemAcc; })) {
      Phi->replaceAllUsesWith(NewMemAcc);
      MSSAUpdater->removeMemoryAccess(Phi);
    }
  }
}

unsigned GVNHoist::removeAndReplace(const SmallVecInsn &Candidates,
                                    Instruction *Repl, BasicBlock *DestBB,
                                    bool MoveAccess) {
  MemoryUseOrDef *NewMemAcc = MSSA->getMemoryAccess(Repl);
  if (MoveAccess && NewMemAcc) {
    // The definition of this ld/st will not change: ld/st hoisting is
    // legal when the ld/st is not moved past its current definition.
    MSSAUpdater->moveToPlace(NewMemAcc, DestBB, MemorySSA::BeforeTerminator);
  }

  // Replace all other instructions with Repl with memory access NewMemAcc.
  unsigned NR = rauw(Candidates, Repl, NewMemAcc);

  // Remove MemorySSA phi nodes with the same arguments.
  if (NewMemAcc)
    raMPHIuw(NewMemAcc);
  return NR;
}

bool GVNHoist::makeGepOperandsAvailable(
    Instruction *Repl, BasicBlock *HoistPt,
    const SmallVecInsn &InstructionsToHoist) const {
  // Check whether the GEP of a ld/st can be synthesized at HoistPt.
  GetElementPtrInst *Gep = nullptr;
  Instruction *Val = nullptr;
  if (auto *Ld = dyn_cast<LoadInst>(Repl)) {
    Gep = dyn_cast<GetElementPtrInst>(Ld->getPointerOperand());
  } else if (auto *St = dyn_cast<StoreInst>(Repl)) {
    Gep = dyn_cast<GetElementPtrInst>(St->getPointerOperand());
    Val = dyn_cast<Instruction>(St->getValueOperand());
    // Check that the stored value is available.
    if (Val) {
      if (isa<GetElementPtrInst>(Val)) {
        // Check whether we can compute the GEP at HoistPt.
        if (!allGepOperandsAvailable(Val, HoistPt))
          return false;
      } else if (!DT->dominates(Val->getParent(), HoistPt))
        return false;
    }
  }

  // Check whether we can compute the Gep at HoistPt.
  if (!Gep || !allGepOperandsAvailable(Gep, HoistPt))
    return false;

  makeGepsAvailable(Repl, HoistPt, InstructionsToHoist, Gep);

  if (Val && isa<GetElementPtrInst>(Val))
    makeGepsAvailable(Repl, HoistPt, InstructionsToHoist, Val);

  return true;
}

std::pair<unsigned, unsigned> GVNHoist::hoist(HoistingPointList &HPL) {
  unsigned NI = 0, NL = 0, NS = 0, NC = 0, NR = 0;
  for (const HoistingPointInfo &HP : HPL) {
    // Find out whether we already have one of the instructions in HoistPt,
    // in which case we do not have to move it.
    BasicBlock *DestBB = HP.first;
    const SmallVecInsn &InstructionsToHoist = HP.second;
    Instruction *Repl = nullptr;
    for (Instruction *I : InstructionsToHoist)
      if (I->getParent() == DestBB)
        // If there are two instructions in HoistPt to be hoisted in place:
        // update Repl to be the first one, such that we can rename the uses
        // of the second based on the first.
        if (!Repl || firstInBB(I, Repl))
          Repl = I;

    // Keep track of whether we moved the instruction so we know whether we
    // should move the MemoryAccess.
    bool MoveAccess = true;
    if (Repl) {
      // Repl is already in HoistPt: it remains in place.
      assert(allOperandsAvailable(Repl, DestBB) &&
             "instruction depends on operands that are not available");
      MoveAccess = false;
    } else {
      // When we do not find Repl in HoistPt, select the first in the list
      // and move it to HoistPt.
      Repl = InstructionsToHoist.front();

      // We can move Repl in HoistPt only when all operands are available.
      // The order in which hoistings are done may influence the availability
      // of operands.
      if (!allOperandsAvailable(Repl, DestBB)) {
        // When HoistingGeps there is nothing more we can do to make the
        // operands available: just continue.
        if (HoistingGeps)
          continue;

        // When not HoistingGeps we need to copy the GEPs.
        if (!makeGepOperandsAvailable(Repl, DestBB, InstructionsToHoist))
          continue;
      }

      // Move the instruction at the end of HoistPt.
      Instruction *Last = DestBB->getTerminator();
      MD->removeInstruction(Repl);
      Repl->moveBefore(Last->getIterator());

      DFSNumber[Repl] = DFSNumber[Last]++;
    }

    // Drop debug location as per debug info update guide.
    Repl->dropLocation();
    NR += removeAndReplace(InstructionsToHoist, Repl, DestBB, MoveAccess);

    if (isa<LoadInst>(Repl))
      ++NL;
    else if (isa<StoreInst>(Repl))
      ++NS;
    else if (isa<CallInst>(Repl))
      ++NC;
    else // Scalar
      ++NI;
  }

  if (MSSA && VerifyMemorySSA)
    MSSA->verifyMemorySSA();

  NumHoisted += NL + NS + NC + NI;
  NumRemoved += NR;
  NumLoadsHoisted += NL;
  NumStoresHoisted += NS;
  NumCallsHoisted += NC;
  return {NI, NL + NC + NS};
}

std::pair<unsigned, unsigned> GVNHoist::hoistExpressions(Function &F) {
  InsnInfo II;
  LoadInfo LI;
  StoreInfo SI;
  CallInfo CI;
  for (BasicBlock *BB : depth_first(&F.getEntryBlock())) {
    int InstructionNb = 0;
    for (Instruction &I1 : *BB) {
      // If I1 cannot guarantee progress, subsequent instructions
      // in BB cannot be hoisted anyways.
      if (!isGuaranteedToTransferExecutionToSuccessor(&I1)) {
        HoistBarrier.insert(BB);
        break;
      }
      // Only hoist the first instructions in BB up to MaxDepthInBB. Hoisting
      // deeper may increase the register pressure and compilation time.
      if (MaxDepthInBB != -1 && InstructionNb++ >= MaxDepthInBB)
        break;

      // Do not value number terminator instructions.
      if (I1.isTerminator())
        break;

      if (auto *Load = dyn_cast<LoadInst>(&I1))
        LI.insert(Load, VN);
      else if (auto *Store = dyn_cast<StoreInst>(&I1))
        SI.insert(Store, VN);
      else if (auto *Call = dyn_cast<CallInst>(&I1)) {
        if (auto *Intr = dyn_cast<IntrinsicInst>(Call)) {
          if (isa<DbgInfoIntrinsic>(Intr) ||
              Intr->getIntrinsicID() == Intrinsic::assume ||
              Intr->getIntrinsicID() == Intrinsic::sideeffect)
            continue;
        }
        if (Call->mayHaveSideEffects())
          break;

        if (Call->isConvergent())
          break;

        CI.insert(Call, VN);
      } else if (HoistingGeps || !isa<GetElementPtrInst>(&I1))
        // Do not hoist scalars past calls that may write to memory because
        // that could result in spills later. geps are handled separately.
        // TODO: We can relax this for targets like AArch64 as they have more
        // registers than X86.
        II.insert(&I1, VN);
    }
  }

  HoistingPointList HPL;
  computeInsertionPoints(II.getVNTable(), HPL, InsKind::Scalar);
  computeInsertionPoints(LI.getVNTable(), HPL, InsKind::Load);
  computeInsertionPoints(SI.getVNTable(), HPL, InsKind::Store);
  computeInsertionPoints(CI.getScalarVNTable(), HPL, InsKind::Scalar);
  computeInsertionPoints(CI.getLoadVNTable(), HPL, InsKind::Load);
  computeInsertionPoints(CI.getStoreVNTable(), HPL, InsKind::Store);
  return hoist(HPL);
}

} // end namespace llvm

PreservedAnalyses GVNHoistPass::run(Function &F, FunctionAnalysisManager &AM) {
  DominatorTree &DT = AM.getResult<DominatorTreeAnalysis>(F);
  PostDominatorTree &PDT = AM.getResult<PostDominatorTreeAnalysis>(F);
  AliasAnalysis &AA = AM.getResult<AAManager>(F);
  MemoryDependenceResults &MD = AM.getResult<MemoryDependenceAnalysis>(F);
  MemorySSA &MSSA = AM.getResult<MemorySSAAnalysis>(F).getMSSA();
  GVNHoist G(&DT, &PDT, &AA, &MD, &MSSA);
  if (!G.run(F))
    return PreservedAnalyses::all();

  PreservedAnalyses PA;
  PA.preserve<DominatorTreeAnalysis>();
  PA.preserve<MemorySSAAnalysis>();
  return PA;
}