llvm/lib/Transforms/Scalar/GVNHoist.cpp

//===- GVNHoist.cpp - Hoist scalar and load expressions -------------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// 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/SmallPtrSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/IteratedDominanceFrontier.h"
#include "llvm/Analysis/MemorySSA.h"
#include "llvm/Analysis/MemorySSAUpdater.h"
#include "llvm/Analysis/PostDominators.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Scalar/GVN.h"
#include "llvm/Transforms/Utils/Local.h"

#include <stack>

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 {

typedef DenseMap<const BasicBlock *, bool> BBSideEffectsSet;
typedef SmallVector<Instruction *, 4> SmallVecInsn;
typedef SmallVectorImpl<Instruction *> SmallVecImplInsn;
// Each element of a hoisting list contains the basic block where to hoist and
// a list of instructions to be hoisted.
typedef std::pair<BasicBlock *, SmallVecInsn> HoistingPointInfo;
typedef SmallVector<HoistingPointInfo, 4> HoistingPointList;
// A map from a pair of VNs to all the instructions with those VNs.
typedef std::pair<unsigned, unsigned> VNType;
typedef DenseMap<VNType, SmallVector<Instruction *, 4>> VNtoInsns;

// 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) { return VN == A.VN; }
  bool operator!=(const CHIArg &A) { return !(*this == A); }
};

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

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

// 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, GVN::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, GVN::ValueTable &VN) {
    if (Load->isSimple()) {
      unsigned V = VN.lookupOrAdd(Load->getPointerOperand());
      VNtoLoads[{V, InvalidVN}].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, GVN::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, GVN::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; }
};

static void combineKnownMetadata(Instruction *ReplInst, Instruction *I) {
  static const unsigned KnownIDs[] = {
      LLVMContext::MD_tbaa,           LLVMContext::MD_alias_scope,
      LLVMContext::MD_noalias,        LLVMContext::MD_range,
      LLVMContext::MD_fpmath,         LLVMContext::MD_invariant_load,
      LLVMContext::MD_invariant_group};
  combineMetadata(ReplInst, I, KnownIDs);
}

// 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(make_unique<MemorySSAUpdater>(MSSA)),
        HoistingGeps(false) {}

  bool 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 (auto &Inst : *BB)
        DFSNumber[&Inst] = ++I;
    }

    int ChainLength = 0;

    // FIXME: use lazy evaluation of VN to avoid the fix-point computation.
    while (1) {
      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;
  }

  // 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 {
    // 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;
  }

private:
  GVN::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;

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

  // Return true when there are exception handling in BB.
  bool 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;
  }

  // Return true when a successor of BB dominates A.
  bool successorDominate(const BasicBlock *BB, const BasicBlock *A) {
    for (const BasicBlock *Succ : BB->getTerminator()->successors())
      if (DT->dominates(Succ, A))
        return true;

    return false;
  }

  /* 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) {
    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 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;
  }

  // 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) {
    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;
  }

  // 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) {
    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;
  }

  // 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) {

    // 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(NewPt, UD->getMemoryInst()))
          // 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, dyn_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;
  }

  // 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 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, TerminatorInst *TI) const {
    if (TI->getNumSuccessors() > std::distance(C.begin(), C.end()))
      return false; // Not enough args in this CHI.

    for (auto CHI : C) {
      BasicBlock *Dest = CHI.Dest;
      // Find if all the edges have values flowing out of BB.
      bool Found = any_of(TI->successors(), [Dest](const BasicBlock *BB) {
          return BB == Dest; });
      if (!Found)
        return false;
    }
    return true;
  }

  // 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) {
    int NumBBsOnAllPaths = MaxNumberOfBBSInPath;
    for (auto CHI : C) {
      Instruction *Insn = CHI.I;
      if (!Insn) // No instruction was inserted in this CHI.
        continue;
      if (K == InsKind::Scalar) {
        if (safeToHoistScalar(BB, Insn->getParent(), NumBBsOnAllPaths))
          Safe.push_back(CHI);
      } else {
        MemoryUseOrDef *UD = MSSA->getMemoryAccess(Insn);
        if (safeToHoistLdSt(BB->getTerminator(), Insn, UD, K, NumBBsOnAllPaths))
          Safe.push_back(CHI);
      }
    }
  }

  typedef DenseMap<VNType, SmallVector<Instruction *, 2>> RenameStackType;
  // Push all the VNs corresponding to BB into RenameStack.
  void fillRenameStack(BasicBlock *BB, InValuesType &ValueBBs,
                       RenameStackType &RenameStack) {
    auto it1 = ValueBBs.find(BB);
    if (it1 != ValueBBs.end()) {
      // Iterate in reverse order to keep lower ranked values on the top.
      for (std::pair<VNType, Instruction *> &VI : reverse(it1->second)) {
        // Get the value of instruction I
        DEBUG(dbgs() << "\nPushing on stack: " << *VI.second);
        RenameStack[VI.first].push_back(VI.second);
      }
    }
  }

  void fillChiArgs(BasicBlock *BB, OutValuesType &CHIBBs,
                   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;
      }
      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->dominates(Pred, si->second.back()->getParent())) {
            C.Dest = BB;                     // Assign the edge
            C.I = si->second.pop_back_val(); // Assign the argument
            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;
      }
    }
  }

  // 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.
    RenameStackType RenameStack;
    for (auto Node : depth_first(Root)) {
      BasicBlock *BB = Node->getBlock();
      if (!BB)
        continue;

      // 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) {
    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.
      std::sort(CHIs.begin(), CHIs.end(), cmpVN);
      auto TI = BB->getTerminator();
      auto B = CHIs.begin();
      // [PreIt, PHIIt) form a range of CHIs which have identical VNs.
      auto PHIIt = std::find_if(CHIs.begin(), CHIs.end(),
                                 [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; });
      }
    }
  }

  // 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).
    std::sort(Ranks.begin(), Ranks.end(),
              [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 (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);
      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.
      for (auto IDFB : IDFBlocks) { // TODO: Prune out useless CHI insertions.
        for (unsigned i = 0; i < V.size(); ++i) {
          CHIArg C = {VN, nullptr, nullptr};
          if (DT->dominates(IDFB, V[i]->getParent())) { // Ignore spurious PDFs.
            // InValue[V[i]->getParent()].push_back(std::make_pair(VN, V[i]));
            OutValue[IDFB].push_back(C);
            DEBUG(dbgs() << "\nInsertion a CHI for BB: " << IDFB->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 {
    for (const Use &Op : I->operands())
      if (const auto *Inst = dyn_cast<Instruction>(&Op))
        if (!DT->dominates(Inst->getParent(), HoistPt))
          return false;

    return true;
  }

  // Same as allOperandsAvailable with recursive check for GEP operands.
  bool 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;
  }

  // Make all operands of the GEP available.
  void 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());

    // 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);
    }

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

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

  // 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) {
    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);
        }

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

  // Replace all Memory PHI usage with NewMemAcc.
  void 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 (all_of(In, [&](Use &U) { return U == NewMemAcc; })) {
        Phi->replaceAllUsesWith(NewMemAcc);
        MSSAUpdater->removeMemoryAccess(Phi);
      }
    }
  }

  // Remove all other instructions and replace them with Repl.
  unsigned 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::End);
    }

    // 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;
  }

  // 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 {
    // 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> 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);

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

      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;
    }

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

  // Hoist all expressions. Returns Number of scalars hoisted
  // and number of non-scalars hoisted.
  std::pair<unsigned, unsigned> 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 (isa<TerminatorInst>(&I1))
          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)
              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);
  }
};

class GVNHoistLegacyPass : public FunctionPass {
public:
  static char ID;

  GVNHoistLegacyPass() : FunctionPass(ID) {
    initializeGVNHoistLegacyPassPass(*PassRegistry::getPassRegistry());
  }

  bool runOnFunction(Function &F) override {
    if (skipFunction(F))
      return false;
    auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
    auto &PDT = getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
    auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
    auto &MD = getAnalysis<MemoryDependenceWrapperPass>().getMemDep();
    auto &MSSA = getAnalysis<MemorySSAWrapperPass>().getMSSA();

    GVNHoist G(&DT, &PDT, &AA, &MD, &MSSA);
    return G.run(F);
  }

  void getAnalysisUsage(AnalysisUsage &AU) const override {
    AU.addRequired<DominatorTreeWrapperPass>();
    AU.addRequired<PostDominatorTreeWrapperPass>();
    AU.addRequired<AAResultsWrapperPass>();
    AU.addRequired<MemoryDependenceWrapperPass>();
    AU.addRequired<MemorySSAWrapperPass>();
    AU.addPreserved<DominatorTreeWrapperPass>();
    AU.addPreserved<MemorySSAWrapperPass>();
    AU.addPreserved<GlobalsAAWrapperPass>();
  }
};
} // 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>();
  PA.preserve<GlobalsAA>();
  return PA;
}

char GVNHoistLegacyPass::ID = 0;
INITIALIZE_PASS_BEGIN(GVNHoistLegacyPass, "gvn-hoist",
                      "Early GVN Hoisting of Expressions", false, false)
INITIALIZE_PASS_DEPENDENCY(MemoryDependenceWrapperPass)
INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
INITIALIZE_PASS_END(GVNHoistLegacyPass, "gvn-hoist",
                    "Early GVN Hoisting of Expressions", false, false)

FunctionPass *llvm::createGVNHoistPass() { return new GVNHoistLegacyPass(); }