Add BFI in constanthoisting pass and do the hoisting selectively

[wmi]

Summary

Existing constant hoisting pass will merge a group of contants in a small range and hoist the const materialization code to the common dominator of their uses.

However, if the uses are all in cold pathes, we may hoist the materialization code from cold pathes to a hot place. This may hurt performance. The patch simply introduces BFI to the pass and does the hoisting only when the common dominator is colder than the sum of execution freq of all the uses to be merged.

Now usage of BFI is guarded by an option consthoist-with-block-frequency which is off by default. I did the compile time evaluation using spec2006 when the option was on and the compile time increase was in noise range: about 0.5% on averange (ranged from -2% ~ 2% for the 21 C/C++ benchmarks).

[davidxl]

Using profile data to throttle transformations in canonicalization passs is generally frowned upon. This pass does not look like a canonicalization pass (other reviewers may have different opinions). Having said that, I also wonder if a more general profile driven code sinking pass (before CGP), similar to look sink is worth the effort.

lib/Transforms/Scalar/ConstantHoisting.cpp

259–271

This is a redundant check.

273

Since we have profile information, it might be worth to find the optimal solution to the insertion problem -- for a given set of use BBs, find a second set of BBs such that

1. a BB in the original set is either included in the second set or dominated by a BB
2. the total frequency of second set is minimized.

The constant materialization instructions are inserted in the BBs in the solution set.

[wmi]

lib/Transforms/Scalar/ConstantHoisting.cpp

259–271

Indeed.

273

Sure. I will implement that if it is ok to use BFI in consthoisting.

[wmi]

Update the patch according to suggestion from David: using BFI to find the optimal solution to the insertion problem.

[davidxl]

lib/Transforms/Scalar/ConstantHoisting.cpp

164

assert !BBs.count(Entry) is true

170

It is simpler to document like this:

WorkSet includes any block 'BB' that is not strictly dominated by any other blocks in set 'BBs', and all nodes in the path in the dominator tree from Entry to 'BB'.

Also name WorkSet as Candidates?

178

In the first iteration, this is always false, so perhaps change the loop into a do-while:

bool isCandidate = false;
do {

Path.insert(Node);
 if (Node == Entry) {
      isCandidate = true;
      break;
 }
 Node = getIDom(Node);

} while (!BBs.count(Node));

201

early return when MadeChange == false?

231

NodesInBBs can not be true for Entry node.

234

Why return empty BBs?

[wmi]

lib/Transforms/Scalar/ConstantHoisting.cpp

164

Ok.

170

Ok, will fix it.

178

That looks simpler. Will fix it.

201

MadeChange == false here just means we didn't find a BB from BBs dominated by another one in BBs, but we may still do hoisting work in the following, like hoist a const materialization out of loop.

234

BBs return the locations where to insert hoisted const materialization. If we decide not to hoist anything, i.e., MadeChange is false, we will return empty BBs saying nothing will be inserted.

[davidxl]

lib/Transforms/Scalar/ConstantHoisting.cpp

230

The exit handling code can probably be simplified a little:

if (Node == Entry) {

   BBs.clear();
   if (InsertPtsFreq >= BFI.getBlockFreq(Node)) {
        BBs.insert(Entry);
         MadeChange = true;
    } else if (MadeChange) {
        BBs.insert(InsertPts.begin(), InsertPts.end());
    }
   break;
}

[wmi]

Addressed David's comments.

[davidxl]

include/llvm/Transforms/Scalar/ConstantHoisting.h

130

Add a documentation about what it returns and what it means when empty set is returned.

lib/Transforms/Scalar/ConstantHoisting.cpp

696

It does not seem correct to skip base const materialization. Also the second condition should always be true?

[wmi]

lib/Transforms/Scalar/ConstantHoisting.cpp

696

You are right. I realize it is not right to skip base const materialization when we need to rebase some use. Will fix it.

The second condition is not necessarily true. We have multiple uses and multiple insertion points chosen. Every use will be dominated by exactly one insertion point but we don't know which one.

[wmi]

Remove MadeChange. We will still need to insert const materialization code even if there is no hoisting or merging for BBs.

[davidxl]

lib/Transforms/Scalar/ConstantHoisting.cpp

673

I am not sure why this is needed. If nothing is changed, it should be fine to skip the transformation for the constant (as well as rebase in uses) completely. Without skipping, it basically force rebasing?

678

There are three cases:

1. new insertion point introduced
2. the BB originally has a base constant use
3. the BB originally has a constant use but need rebase.

For case 1) and 3), new insertion is needed, but for 2) it can be skipped.

684

The right way to fix is to move the rebasing code out of the IPSet traversal loop after all new base constant materialization insertion are done. Only those that got dropped in findConstantInsertionPoint need to be handled.

[davidxl]

lib/Transforms/Scalar/ConstantHoisting.cpp

678

Correction: 2) can only be skipped when there are no other uses dominated by it -- so it is probably better to not to skip and rewrite the original use

684

Discard the second part of the last comment.

[wmi]

lib/Transforms/Scalar/ConstantHoisting.cpp

678

I thought it was not going to change the generated code if we do a rebase for a base constant use. That is why for the code simplicity, I choose to insert materialization and rebase code anyway.

It will change

BB:
%inc = add i64 %5, 214748364701

to

BB:
%const = bitcase i64 214748364701 to i64
...
%inc = add i64 %5, %const

Because 214748364701 is a very large number (The precondition it is treated as constant hoisting candidate) and it cannot be encoded in add instruction, we need the materialization code %const = ... anyway in the end.

[davidxl]

lib/Transforms/Scalar/ConstantHoisting.cpp

678

Ok makes sense.

694

Should !BFI check removed? It just improves compile time a little for the non-default path. To save compile time for more generally, do 'if (IPSet->size() == 1 || DT->dominates(...)) instead?

Also is it better to keep track of the base constants rewritten and assert at the end that all uses are rewritten.

[wmi]

lib/Transforms/Scalar/ConstantHoisting.cpp

694

Good suggestions. Fixed as suggested.

[wmi]

Make change to save compile time and add assertion per David's suggestions.

[davidxl]

lgtm

include/llvm/Transforms/Scalar/ConstantHoisting.h

 // This optimization is only applied to integer constants in instructions and
 // simple (this means not nested) constant cast expressions. For example:
 // %0 = load i64* inttoptr (i64 big_constant to i64*)
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H
 #define LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H
 
+#include "llvm/Analysis/BlockFrequencyInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/PassManager.h"
 
 namespace llvm {
 
 /// A private "module" namespace for types and utilities used by
 /// ConstantHoisting. These are implementation details and should not be used by

 }
 
 class ConstantHoistingPass : public PassInfoMixin<ConstantHoistingPass> {
 public:
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 
   // Glue for old PM.
   bool runImpl(Function &F, TargetTransformInfo &TTI, DominatorTree &DT,
-               BasicBlock &Entry);
+               BlockFrequencyInfo *BFI, BasicBlock &Entry);
 
   void releaseMemory() {
     ConstantVec.clear();
     ClonedCastMap.clear();
     ConstCandVec.clear();
   }
 
 private:
   typedef DenseMap<ConstantInt *, unsigned> ConstCandMapType;
   typedef std::vector<consthoist::ConstantCandidate> ConstCandVecType;
 
   const TargetTransformInfo *TTI;
   DominatorTree *DT;
+  BlockFrequencyInfo *BFI;
   BasicBlock *Entry;
 
   /// Keeps track of constant candidates found in the function.
   ConstCandVecType ConstCandVec;
 
   /// Keep track of cast instructions we already cloned.
   SmallDenseMap<Instruction *, Instruction *> ClonedCastMap;
 
   /// These are the final constants we decided to hoist.
   SmallVector<consthoist::ConstantInfo, 8> ConstantVec;
 
   Instruction *findMatInsertPt(Instruction *Inst, unsigned Idx = ~0U) const;
-  Instruction *findConstantInsertionPoint(
-      const consthoist::ConstantInfo &ConstInfo) const;
+  SmallPtrSet<Instruction *, 8>
+  findConstantInsertionPoint(const consthoist::ConstantInfo &ConstInfo) const;
   void collectConstantCandidates(ConstCandMapType &ConstCandMap,
                                  Instruction *Inst, unsigned Idx,
                                  ConstantInt *ConstInt);
   void collectConstantCandidates(ConstCandMapType &ConstCandMap,
                                  Instruction *Inst);
   void collectConstantCandidates(Function &Fn);
   void findAndMakeBaseConstant(ConstCandVecType::iterator S,
                                ConstCandVecType::iterator E);

lib/Transforms/Scalar/ConstantHoisting.cpp

 using namespace llvm;
 using namespace consthoist;
 
 #define DEBUG_TYPE "consthoist"
 
 STATISTIC(NumConstantsHoisted, "Number of constants hoisted");
 STATISTIC(NumConstantsRebased, "Number of constants rebased");
 
+static cl::opt<bool> ConstHoistWithBlockFrequency(
+    "consthoist-with-block-frequency", cl::init(true), cl::Hidden,
+    cl::desc("Enable the use of the block frequency analysis to reduce the "
+             "chance to execute const materialization more frequently than "
+             "without hoisting."));
+
 namespace {
 /// \brief The constant hoisting pass.
 class ConstantHoistingLegacyPass : public FunctionPass {
 public:
   static char ID; // Pass identification, replacement for typeid
   ConstantHoistingLegacyPass() : FunctionPass(ID) {
     initializeConstantHoistingLegacyPassPass(*PassRegistry::getPassRegistry());
   }
 
   bool runOnFunction(Function &Fn) override;
 
   StringRef getPassName() const override { return "Constant Hoisting"; }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.setPreservesCFG();
+    if (ConstHoistWithBlockFrequency)
+      AU.addRequired<BlockFrequencyInfoWrapperPass>();
     AU.addRequired<DominatorTreeWrapperPass>();
     AU.addRequired<TargetTransformInfoWrapperPass>();
   }
 
   void releaseMemory() override { Impl.releaseMemory(); }
 
 private:
   ConstantHoistingPass Impl;
 };
 }
 
 char ConstantHoistingLegacyPass::ID = 0;
 INITIALIZE_PASS_BEGIN(ConstantHoistingLegacyPass, "consthoist",
                       "Constant Hoisting", false, false)
+INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
 INITIALIZE_PASS_END(ConstantHoistingLegacyPass, "consthoist",
                     "Constant Hoisting", false, false)
 
 FunctionPass *llvm::createConstantHoistingPass() {
   return new ConstantHoistingLegacyPass();
 }
 
 /// \brief Perform the constant hoisting optimization for the given function.
 bool ConstantHoistingLegacyPass::runOnFunction(Function &Fn) {
   if (skipFunction(Fn))
     return false;
 
   DEBUG(dbgs() << "********** Begin Constant Hoisting **********\n");
   DEBUG(dbgs() << "********** Function: " << Fn.getName() << '\n');
 
-  bool MadeChange = Impl.runImpl(
-      Fn, getAnalysis<TargetTransformInfoWrapperPass>().getTTI(Fn),
-      getAnalysis<DominatorTreeWrapperPass>().getDomTree(), Fn.getEntryBlock());
+  bool MadeChange =
+      Impl.runImpl(Fn, getAnalysis<TargetTransformInfoWrapperPass>().getTTI(Fn),
+                   getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
+                   ConstHoistWithBlockFrequency
+                       ? &getAnalysis<BlockFrequencyInfoWrapperPass>().getBFI()
+                       : nullptr,
+                   Fn.getEntryBlock());
 
   if (MadeChange) {
     DEBUG(dbgs() << "********** Function after Constant Hoisting: "
                  << Fn.getName() << '\n');
     DEBUG(dbgs() << Fn);
   }
   DEBUG(dbgs() << "********** End Constant Hoisting **********\n");
 
Instruction *ConstantHoistingPass::findMatInsertPt(Instruction *Inst,
   assert(Entry != Inst->getParent() && "PHI or landing pad in entry block!");
   if (Idx != ~0U && isa<PHINode>(Inst))
     return cast<PHINode>(Inst)->getIncomingBlock(Idx)->getTerminator();
 
   BasicBlock *IDom = DT->getNode(Inst->getParent())->getIDom()->getBlock();
   return IDom->getTerminator();
 }
 
+/// \brief Given \p BBs as input, find another set of BBs which collectively
+/// dominates \p BBs and have the minimal sum of frequencies. Return the BB
+/// set found in \p BBs.
+void findBestInsertionSet(DominatorTree &DT, BlockFrequencyInfo &BFI,
+                          BasicBlock *Entry,
+                          SmallPtrSet<BasicBlock *, 8> &BBs) {
+  assert(!BBs.count(Entry) && "Assume Entry is not in BBs");
+  // Nodes on the current path to the root.
+  SmallPtrSet<BasicBlock *, 8> Path;
+  // Candidates includes any block 'BB' in set 'BBs' that is not strictly
+  // dominated by any other blocks in set 'BBs', and all nodes in the path
+  // in the dominator tree from Entry to 'BB'.
+  SmallPtrSet<BasicBlock *, 16> Candidates;
+  for (auto BB : BBs) {
+    Path.clear();
+    // Walk up the dominator tree until Entry or another BB in BBs
+    // is reached. Insert the nodes on the way to the Path.
+    BasicBlock *Node = BB;
+    // The "Path" is a candidate path to be added into Candidates set.
+    bool isCandidate = false;
+    do {
+      Path.insert(Node);
+      if (Node == Entry) {
+        isCandidate = true;
+        break;
+      }
+      assert(DT.getNode(Node)->getIDom() &&
+             "Entry doens't dominate current Node");
+      Node = DT.getNode(Node)->getIDom()->getBlock();
+    } while (!BBs.count(Node));
+
+    // If isCandidate is false, Node is another Block in BBs dominating
+    // current 'BB'. Drop the nodes on the Path.
+    if (!isCandidate)
+      continue;
+
+    // Add nodes on the Path into Candidates.
+    Candidates.insert(Path.begin(), Path.end());
+  }
+
+  // Sort the nodes in Candidates in top-down order and save the nodes
+  // in Orders.
+  unsigned Idx = 0;
+  SmallVector<BasicBlock *, 16> Orders;
+  Orders.push_back(Entry);
+  while (Idx != Orders.size()) {
+    BasicBlock *Node = Orders[Idx++];
+    for (auto ChildDomNode : DT.getNode(Node)->getChildren()) {
+      if (Candidates.count(ChildDomNode->getBlock()))
+        Orders.push_back(ChildDomNode->getBlock());
+    }
+  }
+
+  // Visit Orders in bottom-up order.
+  typedef std::pair<SmallPtrSet<BasicBlock *, 16>, BlockFrequency>
+      InsertPtsCostPair;
+  // InsertPtsMap is a map from a BB to the best insertion points for the
+  // subtree of BB (subtree not including the BB itself).
+  DenseMap<BasicBlock *, InsertPtsCostPair> InsertPtsMap;
+  InsertPtsMap.reserve(Orders.size() + 1);
+  for (auto RIt = Orders.rbegin(); RIt != Orders.rend(); RIt++) {
+    BasicBlock *Node = *RIt;
+    bool NodeInBBs = BBs.count(Node);
+    SmallPtrSet<BasicBlock *, 16> &InsertPts = InsertPtsMap[Node].first;
+    BlockFrequency &InsertPtsFreq = InsertPtsMap[Node].second;
+
+    // Return the optimal insert points in BBs.
+    if (Node == Entry) {
+      BBs.clear();
+      if (InsertPtsFreq > BFI.getBlockFreq(Node))
+        BBs.insert(Entry);
+      else
+        BBs.insert(InsertPts.begin(), InsertPts.end());
+      break;
+    }
+
+    BasicBlock *Parent = DT.getNode(Node)->getIDom()->getBlock();
+    // Initially, ParentInsertPts is empty and ParentPtsFreq is 0. Every child
+    // will update its parent's ParentInsertPts and ParentPtsFreq.
+    SmallPtrSet<BasicBlock *, 16> &ParentInsertPts = InsertPtsMap[Parent].first;
+    BlockFrequency &ParentPtsFreq = InsertPtsMap[Parent].second;
+    // Choose to insert in Node or in subtree of Node.
+    if (InsertPtsFreq > BFI.getBlockFreq(Node) || NodeInBBs) {
+      ParentInsertPts.insert(Node);
+      ParentPtsFreq += BFI.getBlockFreq(Node);
+    } else {
+      ParentInsertPts.insert(InsertPts.begin(), InsertPts.end());
+      ParentPtsFreq += InsertPtsFreq;
+    }
+  }
+}
+
 /// \brief Find an insertion point that dominates all uses.
-Instruction *ConstantHoistingPass::findConstantInsertionPoint(
+SmallPtrSet<Instruction *, 8> ConstantHoistingPass::findConstantInsertionPoint(
     const ConstantInfo &ConstInfo) const {
   assert(!ConstInfo.RebasedConstants.empty() && "Invalid constant info entry.");
   // Collect all basic blocks.
   SmallPtrSet<BasicBlock *, 8> BBs;
+  SmallPtrSet<Instruction *, 8> InsertPts;
   for (auto const &RCI : ConstInfo.RebasedConstants)
     for (auto const &U : RCI.Uses)
       BBs.insert(findMatInsertPt(U.Inst, U.OpndIdx)->getParent());
 
-  if (BBs.count(Entry))
-    return &Entry->front();
+  if (BBs.count(Entry)) {
+    InsertPts.insert(&Entry->front());
+    return InsertPts;
+  }
+
+  if (BFI) {
+    findBestInsertionSet(*DT, *BFI, Entry, BBs);
+    for (auto BB : BBs) {
+      Instruction &FirstInst = BB->front();
+      InsertPts.insert(findMatInsertPt(&FirstInst));
+    }
+    return InsertPts;
+  }
 
   while (BBs.size() >= 2) {
     BasicBlock *BB, *BB1, *BB2;
     BB1 = *BBs.begin();
     BB2 = *std::next(BBs.begin());
     BB = DT->findNearestCommonDominator(BB1, BB2);
-    if (BB == Entry)
-      return &Entry->front();
+    if (BB == Entry) {
+      InsertPts.insert(&Entry->front());
+      return InsertPts;
+    }
     BBs.erase(BB1);
     BBs.erase(BB2);
     BBs.insert(BB);
   }
   assert((BBs.size() == 1) && "Expected only one element.");
   Instruction &FirstInst = (*BBs.begin())->front();
-  return findMatInsertPt(&FirstInst);
+  InsertPts.insert(&FirstInst);
+  return InsertPts;
 }
 
 
 /// \brief Record constant integer ConstInt for instruction Inst at operand
 /// index Idx.
 ///
 /// The operand at index Idx is not necessarily the constant integer itself. It
 /// could also be a cast instruction or a constant expression that uses the

 }
 
 /// \brief Hoist and hide the base constant behind a bitcast and emit
 /// materialization code for derived constants.
 bool ConstantHoistingPass::emitBaseConstants() {
   bool MadeChange = false;
   for (auto const &ConstInfo : ConstantVec) {
     // Hoist and hide the base constant behind a bitcast.
-    Instruction *IP = findConstantInsertionPoint(ConstInfo);
+    SmallPtrSet<Instruction *, 8> IPSet = findConstantInsertionPoint(ConstInfo);
+    assert(!IPSet.empty() && "IPSet is empty");
+
+    for (Instruction *IP : IPSet) {
       IntegerType *Ty = ConstInfo.BaseConstant->getType();
       Instruction *Base =
           new BitCastInst(ConstInfo.BaseConstant, Ty, "const", IP);
-    DEBUG(dbgs() << "Hoist constant (" << *ConstInfo.BaseConstant << ") to BB "
-                 << IP->getParent()->getName() << '\n' << *Base << '\n');
-    NumConstantsHoisted++;
+      DEBUG(dbgs() << "Hoist constant (" << *ConstInfo.BaseConstant
+                   << ") to BB " << IP->getParent()->getName() << '\n'
+                   << *Base << '\n');
 
       // Emit materialization code for all rebased constants.
       for (auto const &RCI : ConstInfo.RebasedConstants) {
-      NumConstantsRebased++;
-      for (auto const &U : RCI.Uses)
+        for (auto const &U : RCI.Uses) {
+          BasicBlock *OrigMatInsertBB =
+              findMatInsertPt(U.Inst, U.OpndIdx)->getParent();
+          // If BFI is nullptr, IPSet will contains only one Instruction.
+          // All the rebases will use the same Base so skip the dominate
+          // test.
+          // If BFI is not nullptr, the size of IPSet can be larger than 1,
+          // different uses will use different Bases. The proper Base for
+          // a use is the Base dominating the use.
+          if (!BFI || DT->dominates(Base->getParent(), OrigMatInsertBB)) {
             emitBaseConstants(Base, RCI.Offset, U);
           }
+        }
+      }
 
       // Use the same debug location as the last user of the constant.
       assert(!Base->use_empty() && "The use list is empty!?");
       assert(isa<Instruction>(Base->user_back()) &&
              "All uses should be instructions.");
       Base->setDebugLoc(cast<Instruction>(Base->user_back())->getDebugLoc());
+    }
+
+    NumConstantsHoisted++;
+
+    // Base constant is also included in ConstInfo.RebasedConstants, so
+    // deduct 1 from ConstInfo.RebasedConstants.size().
+    NumConstantsRebased = ConstInfo.RebasedConstants.size() - 1;
 
-    // Correct for base constant, which we counted above too.
-    NumConstantsRebased--;
     MadeChange = true;
   }
   return MadeChange;
 }
 
 /// \brief Check all cast instructions we made a copy of and remove them if they
 /// have no more users.
 void ConstantHoistingPass::deleteDeadCastInst() const {
   for (auto const &I : ClonedCastMap)
     if (I.first->use_empty())
       I.first->eraseFromParent();
 }
 
 /// \brief Optimize expensive integer constants in the given function.
 bool ConstantHoistingPass::runImpl(Function &Fn, TargetTransformInfo &TTI,
-                                   DominatorTree &DT, BasicBlock &Entry) {
+                                   DominatorTree &DT, BlockFrequencyInfo *BFI,
+                                   BasicBlock &Entry) {
   this->TTI = &TTI;
   this->DT = &DT;
+  this->BFI = BFI;
   this->Entry = &Entry;  
   // Collect all constant candidates.
   collectConstantCandidates(Fn);
 
   // There are no constant candidates to worry about.
   if (ConstCandVec.empty())
     return false;
 
bool ConstantHoistingPass::runImpl(Function &Fn, TargetTransformInfo &TTI,
 
   return MadeChange;
 }
 
 PreservedAnalyses ConstantHoistingPass::run(Function &F,
                                             FunctionAnalysisManager &AM) {
   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
   auto &TTI = AM.getResult<TargetIRAnalysis>(F);
-  if (!runImpl(F, TTI, DT, F.getEntryBlock()))
+  auto BFI = ConstHoistWithBlockFrequency
+                 ? &AM.getResult<BlockFrequencyAnalysis>(F)
+                 : nullptr;
+  if (!runImpl(F, TTI, DT, BFI, F.getEntryBlock()))
     return PreservedAnalyses::all();
 
   PreservedAnalyses PA;
   PA.preserveSet<CFGAnalyses>();
   return PA;
 }

test/CodeGen/X86/constant-hoisting-bfi.ll

+; RUN: opt -consthoist -mtriple=x86_64-unknown-linux-gnu -consthoist-with-block-frequency=true -S < %s | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+; Check when BFI is enabled for constant hoisting, constant 214748364701
+; will not be hoisted to the func entry.
+; CHECK-LABEL: @foo(
+; CHECK: entry:
+; CHECK-NOT: bitcast i64 214748364701 to i64
+; CHECK: if.then:
+
+; Function Attrs: norecurse nounwind uwtable
+define i64 @foo(i64* nocapture %a) {
+entry:
+  %arrayidx = getelementptr inbounds i64, i64* %a, i64 9
+  %t0 = load i64, i64* %arrayidx, align 8
+  %cmp = icmp slt i64 %t0, 564
+  br i1 %cmp, label %if.then, label %if.else5
+
+if.then:                                          ; preds = %entry
+  %arrayidx1 = getelementptr inbounds i64, i64* %a, i64 5
+  %t1 = load i64, i64* %arrayidx1, align 8
+  %cmp2 = icmp slt i64 %t1, 1009
+  br i1 %cmp2, label %if.then3, label %return
+
+if.then3:                                         ; preds = %if.then
+  %arrayidx4 = getelementptr inbounds i64, i64* %a, i64 6
+  %t2 = load i64, i64* %arrayidx4, align 8
+  %inc = add nsw i64 %t2, 1
+  store i64 %inc, i64* %arrayidx4, align 8
+  br label %return
+
+if.else5:                                         ; preds = %entry
+  %arrayidx6 = getelementptr inbounds i64, i64* %a, i64 6
+  %t3 = load i64, i64* %arrayidx6, align 8
+  %cmp7 = icmp slt i64 %t3, 3512
+  br i1 %cmp7, label %if.then8, label %return
+
+if.then8:                                         ; preds = %if.else5
+  %arrayidx9 = getelementptr inbounds i64, i64* %a, i64 7
+  %t4 = load i64, i64* %arrayidx9, align 8
+  %inc10 = add nsw i64 %t4, 1
+  store i64 %inc10, i64* %arrayidx9, align 8
+  br label %return
+
+return:                                           ; preds = %if.else5, %if.then, %if.then8, %if.then3
+  %retval.0 = phi i64 [ 214748364701, %if.then3 ], [ 214748364701, %if.then8 ], [ 250148364702, %if.then ], [ 256148364704, %if.else5 ]
+  ret i64 %retval.0
+}
+
+; Check when BFI is enabled for constant hoisting, constant 214748364701
+; in while.body will be hoisted to while.body.preheader. 214748364701 in
+; if.then16 and if.else10 will be merged and hoisted to the beginning of
+; if.else10 because if.else10 dominates if.then16.
+; CHECK-LABEL: @goo(
+; CHECK: entry:
+; CHECK-NOT: bitcast i64 214748364701 to i64
+; CHECK: while.body.preheader:
+; CHECK-NEXT: bitcast i64 214748364701 to i64
+; CHECK-NOT: bitcast i64 214748364701 to i64
+; CHECK: if.else10:
+; CHECK-NEXT: bitcast i64 214748364701 to i64
+; CHECK-NOT: bitcast i64 214748364701 to i64
+define i64 @goo(i64* nocapture %a) {
+entry:
+  %arrayidx = getelementptr inbounds i64, i64* %a, i64 9
+  %t0 = load i64, i64* %arrayidx, align 8
+  %cmp = icmp ult i64 %t0, 56
+  br i1 %cmp, label %if.then, label %if.else10, !prof !0
+
+if.then:                                          ; preds = %entry
+  %arrayidx1 = getelementptr inbounds i64, i64* %a, i64 5
+  %t1 = load i64, i64* %arrayidx1, align 8
+  %cmp2 = icmp ult i64 %t1, 10
+  br i1 %cmp2, label %while.cond.preheader, label %return, !prof !0
+
+while.cond.preheader:                             ; preds = %if.then
+  %arrayidx7 = getelementptr inbounds i64, i64* %a, i64 6
+  %t2 = load i64, i64* %arrayidx7, align 8
+  %cmp823 = icmp ugt i64 %t2, 10000
+  br i1 %cmp823, label %while.body.preheader, label %return
+
+while.body.preheader:                             ; preds = %while.cond.preheader
+  br label %while.body
+
+while.body:                                       ; preds = %while.body.preheader, %while.body
+  %t3 = phi i64 [ %add, %while.body ], [ %t2, %while.body.preheader ]
+  %add = add i64 %t3, 214748364701
+  %cmp8 = icmp ugt i64 %add, 10000
+  br i1 %cmp8, label %while.body, label %while.cond.return.loopexit_crit_edge
+
+if.else10:                                        ; preds = %entry
+  %arrayidx11 = getelementptr inbounds i64, i64* %a, i64 6
+  %t4 = load i64, i64* %arrayidx11, align 8
+  %add2 = add i64 %t4, 214748364701
+  %cmp12 = icmp ult i64 %add2, 35
+  br i1 %cmp12, label %if.then16, label %return, !prof !0
+
+if.then16:                                        ; preds = %if.else10
+  %arrayidx17 = getelementptr inbounds i64, i64* %a, i64 7
+  %t5 = load i64, i64* %arrayidx17, align 8
+  %inc = add i64 %t5, 1
+  store i64 %inc, i64* %arrayidx17, align 8
+  br label %return
+
+while.cond.return.loopexit_crit_edge:             ; preds = %while.body
+  store i64 %add, i64* %arrayidx7, align 8
+  br label %return
+
+return:                                           ; preds = %while.cond.preheader, %while.cond.return.loopexit_crit_edge, %if.else10, %if.then, %if.then16
+  %retval.0 = phi i64 [ 214748364701, %if.then16 ], [ 0, %if.then ], [ 0, %if.else10 ], [ 0, %while.cond.return.loopexit_crit_edge ], [ 0, %while.cond.preheader ]
+  ret i64 %retval.0
+}
+
+!0 = !{!"branch_weights", i32 1, i32 2000}

test/CodeGen/X86/fold-tied-op.ll

 ; RUN: llc -verify-machineinstrs -mtriple=i386--netbsd < %s | FileCheck %s
 ; Regression test for http://reviews.llvm.org/D5701
 
 ; ModuleID = 'xxhash.i'
 target datalayout = "e-m:e-p:32:32-f64:32:64-f80:32-n8:16:32-S128"
 target triple = "i386--netbsd"
 
 ; CHECK-LABEL: fn1
 ; CHECK:       addl  {{.*#+}} 4-byte Folded Reload
-; CHECK:       addl  {{.*#+}} 4-byte Folded Reload
 ; CHECK:       imull {{.*#+}} 4-byte Folded Reload
 ; CHECK:       orl   {{.*#+}} 4-byte Folded Reload
 ; CHECK:       retl
 
 %struct.XXH_state64_t = type { i32, i32, i64, i64, i64 }
 
 @a = common global i32 0, align 4
 @b = common global i64 0, align 8