[GVN] Simple GVN hoist - scalars

[chill]

Summary

RFC/discussion: https://lists.llvm.org/pipermail/llvm-dev/2021-September/152665.html

This patch implements simple hoisting of instructions from two
single-predecessor blocks to their common predecessor, as a subroutine
in the GVN pass.

The patch pairs two instructions (A and B) with the same value number,
moves A to the predecessor block, replaces all uses of B with A, and
deletes B.

Outline of the algorithm follows:

First we scan the then-block to collect hoist candidates ("then-" and "else-"
prefixes are purely naming and have no connection to the condition in the
predecessor block)

Then we scan the else-block for hoist candidates, that match some already
selected instruction from the then-block.

During both scans, instructions, which are not guaranteed to transfer control to
the following instruction act as "hoist barriers" - after we encounter such an
instruction, we select for potential hoisting/merge only instructions, which are
safe to execute speculatively.

Next we try hoist to hoist each candidate pair. We begin by trying to hoist
operands of the then-instruction. Every such operand must already be in a
dominating block or in itself paired with an instruction from the else-block. If
we cannot hoist an operand for whatever reason, the we stop trying to hoist the
pair.

Now that all the operands of the then-instruction are in a dominating block, we
check the operands of the else-instruction. They all must already be in a
dominating block, either initially or as a result of hoisting operands of the
then-instruction. If any of the operands is still in the else-block, we stop
trying to hoist the pair.

As a last step, we move the then-instruction to the predecessor block and delete
the else-instruction.

[mkazantsev]

llvm/include/llvm/Transforms/Scalar/GVN.h

246

Not entirely clear from description which pairs does this store. What if we have N equivalent instructions in different paths, none dominating other? How many (and which) pairs is it going to store?

llvm/lib/Transforms/Scalar/GVN.cpp

3073

What worries me is that when we meet a non-guaranteed-to-transfer-execution instruction, we add it to HoistPairs before we actually raise the flag. Does it mean we can sometimes hoist such instructions?

3076

nit: space after "barrier".

3181

Why not RPOT?

[chill]

llvm/include/llvm/Transforms/Scalar/GVN.h

246

This map stores pairs of instructions from two blocks having a single common predecessor for the duration of a single top level iteration in performHoist.

I will update the comment in that sense.

llvm/lib/Transforms/Scalar/GVN.cpp

3073

Yes, that's right, we can hoist such instructions. Should be fine, as we only hoist/merge *pairs* from the two sibling blocks.

In principle, we can hoist (some) following instructions as well, if the two "barrier" instructions are themselves hoisted, but that's sort of expensive to check, so that's a limitation of the algorithm.

3076

Printing the instruction adds two spaces.

3181

That is to prevent hoisting an instruction more than once. Alternatively, we could track how many blocks/instructions up an instruction moves, but that entails an auxiliary data structure.

[mkazantsev]

llvm/lib/Transforms/Scalar/GVN.cpp

3181

But RPOT is that guarantees you that it doesn't hoist twice. Note that RPOT stands for *reverse* post order traversal, which is topological up-down traversal. It has a property (on DAG) that all block's predecessors are handled before the block.

Here is example:

   A
   |  \
   B   C
   | /  \
   D     E
  /  \
F     G

If you chose DFS traversal, it may take A B D F G C E. You could hoist (F, G) -> D when processing D and then (D, E) -> C when processing C, which is hoisting same instruction twice.

RPOT will protect you from this.

[mkazantsev]

llvm/lib/Transforms/Scalar/GVN.cpp

3073

Then you have a problem with ICF (see comment below).

3076

That's tricky :)

3170

Since you move instructions with implicit control flow (i.e. non guaranteed to pass execution), this s incorrect treatment of ICF. You need to remove both EiseI and ThenI from ICF *before* you move it, and then add the moved instruction to ICF in the new block.

3181

Maybe not the best example because current implementation doesn't hoist D->C, but still... RPOT looks safer.

[mkazantsev]

Marking "Request changes" because of ICF mistreatment.

[chill]

• Updated to update the ICF tracking
• traverse the CFG in RPO-rder

[mkazantsev]

llvm/test/Transforms/GVN/gc_relocate.ll

2–3

Why disable it here? It should be interesting to see how it improves.

[mkazantsev]

llvm/lib/Transforms/Scalar/GVN.cpp

3062

Re-reading the patch, I noticed that it might be missing aliasing notion. How do we prevent hoisting loads across aliasing store?

[chill]

llvm/lib/Transforms/Scalar/GVN.cpp

3062

In this part we don't hoist loads and stores at all, since they have unique value numbers.

[mkazantsev]

llvm/lib/Transforms/Scalar/GVN.cpp

3062

Could you please add assert that hoisted instruction does not read or write memory? We don't want to miss this once this changes.

[mkazantsev]

Looks good now, thanks.

llvm/include/llvm/Transforms/Scalar/GVN.h

367

nit: please give them some names.

llvm/lib/Transforms/Scalar/GVN.cpp

129

nit: gvn-hoist

3069

Looks like it also makes sense to skip Phis, just to not bother computing their hashes.

llvm/test/Transforms/GVN/simple-gvnhoist-scalars.ll

1

Unless there is a reason to not do so, please use update_test_checks script & precommit the test.

[efriedma]

llvm/lib/Transforms/Scalar/GVN.cpp

3205

BasicBlock::size() is almost never something you want to call. Issues:

1. It's O(n) in the number of instructions in the block.
2. It's sensitive to debug intrinsic calls, so using it to drive a heuristic is inherently broken.

[chill]

llvm/lib/Transforms/Scalar/GVN.cpp

3205

Ack.

[hiraditya]

i fixed PR46874 last year in case this was the issue https://reviews.llvm.org/D108425. If there are further bugs with GVNHoist, i'm happy to fix them.

llvm/include/llvm/Transforms/Scalar/GVN.h

private:
   struct LeaderTableEntry {
     Value *Val;
     const BasicBlock *BB;
     LeaderTableEntry *Next;
   };
   DenseMap<uint32_t, LeaderTableEntry> LeaderTable;
   BumpPtrAllocator TableAllocator;
 
+  /// A mapping from value numbers to a pair of instructions. This map
+  /// stores pairs of instructions with the same value number, from two blocks
+  /// having a single common predecessor, for the duration of a single top level
+  /// iteration in `performHoist`.
+  using HoistMap = DenseMap<uint32_t, std::pair<Instruction *, Instruction *>>;
+  HoistMap HoistPairs;
+
   // Block-local map of equivalent values to their leader, does not
   // propagate to any successors. Entries added mid-block are applied
   // to the remaining instructions in the block.
   SmallMapVector<Value *, Value *, 4> ReplaceOperandsWithMap;
   SmallVector<Instruction *, 8> InstrsToErase;
 
   // Map the block to reversed postorder traversal number. It is used to
   // find back edge easily.
private:
   bool processInstruction(Instruction *I);
   bool processBlock(BasicBlock *BB);
   void dump(DenseMap<uint32_t, Value *> &d) const;
   bool iterateOnFunction(Function &F);
   bool performPRE(Function &F);
   bool performScalarPRE(Instruction *I);
   bool performScalarPREInsertion(Instruction *Instr, BasicBlock *Pred,
                                  BasicBlock *Curr, unsigned int ValNo);
+  bool performHoist(Function &F);
+  void collectHoistCandidates(BasicBlock *ThenBB);
+  void matchHoistCandidates(BasicBlock *ElseBB);
+  void replaceInstruction(Instruction *I, Instruction *Repl);
+  std::pair<bool, bool> hoistPair(BasicBlock *DestBB, BasicBlock *ThenBB,
+                                  BasicBlock *ElseBB, Instruction *ThenI,
+                                  Instruction *ElseI);
   Value *findLeader(const BasicBlock *BB, uint32_t num);
   void cleanupGlobalSets();
   void verifyRemoved(const Instruction *I) const;
   bool splitCriticalEdges();
   BasicBlock *splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ);
   bool replaceOperandsForInBlockEquality(Instruction *I) const;
   bool propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root,
                          bool DominatesByEdge);

llvm/lib/Transforms/Scalar/GVN.cpp

 
 // This is based on IsValueFullyAvailableInBlockNumSpeculationsMax stat.
 static cl::opt<uint32_t> MaxBBSpeculations(
     "gvn-max-block-speculations", cl::Hidden, cl::init(600), cl::ZeroOrMore,
     cl::desc("Max number of blocks we're willing to speculate on (and recurse "
              "into) when deducing if a value is fully available or not in GVN "
              "(default = 600)"));
 
+static cl::opt<bool> GVNEnableSimpleGVNHoist("enable-simple-gvn-hoist",
+                                             cl::init(true));
+
 struct llvm::GVN::Expression {
   uint32_t opcode;
   bool commutative = false;
   Type *type = nullptr;
   SmallVector<uint32_t, 4> varargs;
 
   Expression(uint32_t o = ~2U) : opcode(o) {}
 
if (isPREEnabled()) {
     assignValNumForDeadCode();
     bool PREChanged = true;
     while (PREChanged) {
       PREChanged = performPRE(F);
       Changed |= PREChanged;
     }
   }
 
+  if (GVNEnableSimpleGVNHoist) {
+    LeaderTable.clear();
+    Changed |= performHoist(F);
+  }
+
   // FIXME: Should perform GVN again after PRE does something.  PRE can move
   // computations into blocks where they become fully redundant.  Note that
   // we can't do this until PRE's critical edge splitting updates memdep.
   // Actually, when this happens, we should just fully integrate PRE into GVN.
 
   cleanupGlobalSets();
   // Do not cleanup DeadBlocks in cleanupGlobalSets() as it's called for each
   // iteration.
void GVN::assignValNumForDeadCode() {
   for (BasicBlock *BB : DeadBlocks) {
     for (Instruction &Inst : *BB) {
       unsigned ValNum = VN.lookupOrAdd(&Inst);
       addToLeaderTable(ValNum, &Inst, BB);
     }
   }
 }
 
+// Won't reorder above these instructions.
+static bool isHoistBarrier(const Instruction &I) {
+  return !isGuaranteedToTransferExecutionToSuccessor(&I);
+}
+
+void GVN::collectHoistCandidates(BasicBlock *BB) {
+  bool HasHoistBarrier = false;
+  for (Instruction &I : *BB) {
+    if (I.isTerminator())
+      break;
+    if (isa<PHINode>(I))
+      continue;
+
+    if (!HasHoistBarrier || isSafeToSpeculativelyExecute(&I))
+      HoistPairs[VN.lookupOrAdd(&I)].first = &I;
+
+    if ((HasHoistBarrier |= isHoistBarrier(I)))
+      LLVM_DEBUG(dbgs() << "Simple GVNHoist: reached hoist barrier" << I
+                        << '\n';);
+  }
+}
+
+void GVN::matchHoistCandidates(BasicBlock *BB) {
+  bool HasHoistBarrier = false;
+  for (Instruction &I : *BB) {
+    if (I.isTerminator())
+      break;
+    if (isa<PHINode>(I))
+      continue;
+
+    if (!HasHoistBarrier || isSafeToSpeculativelyExecute(&I)) {
+      uint32_t N = VN.lookupOrAdd(&I);
+      auto It = HoistPairs.find(N);
+      if (It != HoistPairs.end())
+        It->second.second = &I;
+    }
+
+    if ((HasHoistBarrier |= isHoistBarrier(I)))
+      LLVM_DEBUG(dbgs() << "Simple GVNHoist: reached hoist barrier" << I
+                        << '\n';);
+  }
+}
+
+void GVN::replaceInstruction(Instruction *I, Instruction *Repl) {
+  LLVM_DEBUG(dbgs() << "Simple GVNHoist: replacing" << *I << " by" << *Repl
+                    << '\n';);
+  patchReplacementInstruction(I, Repl);
+  ICF->removeUsersOf(I);
+  I->replaceAllUsesWith(Repl);
+  salvageKnowledge(I, AC);
+  salvageDebugInfo(*I);
+  if (MD)
+    MD->removeInstruction(I);
+  if (MSSAU)
+    MSSAU->removeMemoryAccess(I);
+  VN.erase(I);
+  ICF->removeInstruction(I);
+  LLVM_DEBUG(verifyRemoved(I));
+  I->eraseFromParent();
+}
+
+// Only hoist instructions from the "then" block.
+// Each hoisted instructions must be paired with an instruction from the "else"
+// block.
+std::pair<bool, bool> GVN::hoistPair(BasicBlock *DestBB, BasicBlock *ThenBB,
+                                     BasicBlock *ElseBB, Instruction *ThenI,
+                                     Instruction *ElseI) {
+  // If the instruction is moved out of the "then" block there's nothing to do.
+  if (ThenI->getParent() != ThenBB)
+    return {false, false};
+
+  // Instruction must have already been selected for hoisting and matched with
+  // another instruction.
+  auto It = HoistPairs.find(VN.lookupOrAdd(ThenI));
+  if (It == HoistPairs.end())
+    return {false, true};
+
+  assert((ElseI == nullptr || ElseI == It->second.second) &&
+         "Attempt to hoist two not paired instructions.");
+
+  if (LLVM_LIKELY(ElseI == nullptr) && (ElseI = It->second.second) == nullptr)
+    return {false, true};
+  It->second.second = nullptr;
+
+  assert(ElseI->getParent() == ElseBB && "Instruction already removed");
+  assert(!ThenI->mayReadOrWriteMemory() && !ElseI->mayReadOrWriteMemory() &&
+         "Memory read/write instructions must not be hoisted.");
+  bool Change = false;
+
+  // Hoist operands. Begin by hoisting all of the operands of the "then"
+  // instruction, then check all of the operands of the "else" instruction
+  // dominate its block.
+  for (unsigned I = 0, N = ThenI->getNumOperands(); I < N; ++I) {
+    auto *Op = dyn_cast<Instruction>(ThenI->getOperand(I));
+    if (Op == nullptr)
+      continue;
+    bool OpChange, CantHoist;
+    std::tie(OpChange, CantHoist) =
+        hoistPair(DestBB, ThenBB, ElseBB, Op, nullptr);
+    Change |= OpChange;
+    if (CantHoist)
+      return {Change, true};
+  }
+
+  for (unsigned I = 0, N = ElseI->getNumOperands(); I < N; ++I) {
+    auto *Op = dyn_cast<Instruction>(ElseI->getOperand(I));
+    if (Op == nullptr)
+      continue;
+    if (Op->getParent() == ElseBB)
+      return {Change, true};
+  }
+
+  // Hoist one of the instructions and replace all uses of the other with it.
+  ICF->removeInstruction(ThenI);
+  ICF->insertInstructionTo(ThenI, DestBB);
+  ThenI->moveBefore(DestBB->getTerminator());
+  replaceInstruction(ElseI, ThenI);
+
+  return {true, false};
+}
+
+// Perform trivial hoisting of values from two blocks to their common
+// predecessor.
+bool GVN::performHoist(Function &F) {
+  LLVM_DEBUG(dbgs() << "Simple GVNHoist: running on function " << F.getName()
+                    << '\n';);
+  bool Change = false;
+  ReversePostOrderTraversal<Function *> RPOT(&F);
+  for (BasicBlock *BB : RPOT) {
+    // Check we have a block of the desired shape.
+    auto *BI = dyn_cast<BranchInst>(BB->getTerminator());
+    if (!BI || !BI->isConditional())
+      continue;
+
+    BasicBlock *Then = BI->getSuccessor(0);
+    BasicBlock *Else = BI->getSuccessor(1);
+
+    if (!Then->getSinglePredecessor() || !Else->getSinglePredecessor())
+      continue;
+
+    LLVM_DEBUG(dbgs() << "Simple GVNHoist: looking at block " << BB->getName()
+                      << '\n');
+
+    // Collect all hoistable instructions from the smaller block, then match
+    // them by value number with the instructions from the other block.
+    if (Then->size() > Else->size())
+      std::swap(Then, Else);
+
+    HoistPairs.clear();
+    collectHoistCandidates(Then);
+    matchHoistCandidates(Else);
+
+    // Hoist matched pairs.
+    for (const auto &P : HoistPairs) {
+      bool LocalChange, _;
+      std::tie(LocalChange, _) =
+          hoistPair(BB, Then, Else, P.second.first, P.second.second);
+      Change |= LocalChange;
+    }
+  }
+
+  return Change;
+}
+
 class llvm::gvn::GVNLegacyPass : public FunctionPass {
 public:
   static char ID; // Pass identification, replacement for typeid
 
   explicit GVNLegacyPass(bool NoMemDepAnalysis = !GVNEnableMemDep)
       : FunctionPass(ID), Impl(GVNOptions().setMemDep(!NoMemDepAnalysis)) {
     initializeGVNLegacyPassPass(*PassRegistry::getPassRegistry());
   }

llvm/test/Transforms/GVN/PRE/local-pre.ll

-; RUN: opt < %s -gvn -enable-pre -S | FileCheck %s
-; RUN: opt < %s -passes="gvn<pre>" -enable-pre=false -S | FileCheck %s
+; RUN: opt < %s -gvn -enable-pre -enable-simple-gvn-hoist=false -S | FileCheck %s
+; RUN: opt < %s -passes="gvn<pre>" -enable-pre=false -enable-simple-gvn-hoist=false -S | FileCheck %s
 
 declare void @may_exit() nounwind
 
 declare void @may_exit_1(i32) nounwind
 
 define i32 @main(i32 %p, i32 %q) {
 
 ; CHECK-LABEL: @main(

llvm/test/Transforms/GVN/PRE/phi-translate.ll

-; RUN: opt -basic-aa -gvn -S < %s | FileCheck %s
+; RUN: opt -basic-aa -gvn -enable-simple-gvn-hoist=false -S < %s | FileCheck %s
 
 target datalayout = "e-p:64:64:64"
 
 ; CHECK-LABEL: @foo(
 ; CHECK: entry.end_crit_edge:
 ; CHECK: %[[INDEX:[a-z0-9.]+]] = sext i32 %x to i64{{$}}
 ; CHECK: %[[ADDRESS:[a-z0-9.]+]] = getelementptr [100 x i32], [100 x i32]* @G, i64 0, i64 %[[INDEX]]{{$}}
 ; CHECK:   %n.pre = load i32, i32* %[[ADDRESS]], align 4, !dbg [[N_LOC:![0-9]+]]

llvm/test/Transforms/GVN/PRE/pre-basic-add.ll

-; RUN: opt < %s -gvn -enable-pre -S | FileCheck %s
-; RUN: opt < %s -passes="gvn<pre>" -enable-pre=false -S | FileCheck %s
+; RUN: opt < %s -gvn -enable-pre  -enable-simple-gvn-hoist=false -S | FileCheck %s
+; RUN: opt < %s -passes="gvn<pre>" -enable-pre=false -enable-simple-gvn-hoist=false -S | FileCheck %s
 
 @H = common global i32 0    ; <i32*> [#uses=2]
 @G = common global i32 0    ; <i32*> [#uses=1]
 
 define i32 @test() nounwind {
 entry:
   %0 = load i32, i32* @H, align 4    ; <i32> [#uses=2]
   %1 = call i32 (...) @foo() nounwind    ; <i32> [#uses=1]

llvm/test/Transforms/GVN/PRE/pre-load.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt < %s -basic-aa -gvn -enable-load-pre -S | FileCheck %s
-; RUN: opt < %s -aa-pipeline=basic-aa -passes="gvn<load-pre>" -enable-load-pre=false -S | FileCheck %s
+; RUN: opt < %s -basic-aa -gvn -enable-load-pre -enable-simple-gvn-hoist=false -S | FileCheck %s
+; RUN: opt < %s -aa-pipeline=basic-aa -passes="gvn<load-pre>" -enable-load-pre=false -enable-simple-gvn-hoist=false -S | FileCheck %s
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
 
 define i32 @test1(i32* %p, i1 %C) {
 ; CHECK-LABEL: @test1(
 ; CHECK-NEXT:  block1:
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[BLOCK2:%.*]], label [[BLOCK3:%.*]]
 ; CHECK:       block2:
 ; CHECK-NEXT:    [[PRE_PRE:%.*]] = load i32, i32* [[P:%.*]], align 4

llvm/test/Transforms/GVN/PRE/pre-no-cost-phi.ll

-; RUN: opt < %s -gvn -S | FileCheck %s
+; RUN: opt < %s -gvn -enable-simple-gvn-hoist=false -S | FileCheck %s
 ; This testcase tests insertion of no-cost phis.  That is,
 ; when the value is already available in every predecessor,
 ; and we just need to insert a phi node to merge the available values.
 
 @c = global i32 0, align 4
 @d = global i32 0, align 4
 
 

llvm/test/Transforms/GVN/PRE/pre-poison-add.ll

-; RUN: opt < %s -gvn -enable-pre -S | FileCheck %s
+; RUN: opt < %s -gvn -enable-pre -enable-simple-gvn-hoist=false -S | FileCheck %s
+; RUN: opt < %s --passes="gvn<pre>" -S | FileCheck %s --check-prefix=CHECK-HOIST
 
 @H = common global i32 0
 @G = common global i32 0
 
 define i32 @test1(i1 %cond, i32 %v) nounwind {
 ; CHECK-LABEL: @test1
 entry:
     br i1 %cond, label %bb, label %bb1

 ; CHECK-NEXT: ret i32 0
     %add.2 = add i32 %v, 42
     store i32 %add.2, i32* @H, align 4
     ret i32 0
 }
 
 define i32 @test2(i1 %cond, i32 %v) nounwind {
 ; CHECK-LABEL: @test2
+; CHECK-HOIST-LABEL: @test2
 entry:
     br i1 %cond, label %bb, label %bb1
 
+; CHECK-HOIST: entry:
+; CHECK-HOIST: %.pre = add i32 %v, 42
 bb:
     %add.1 = add i32 %v, 42
 ; CHECK: %add.1 = add i32 %v, 42
     store i32 %add.1, i32* @G, align 4
     br label %return
 
 bb1:
 ; CHECK: %.pre = add nuw nsw i32 %v, 42

llvm/test/Transforms/GVN/freeze.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt < %s -gvn -S | FileCheck %s
-; RUN: opt < %s -passes=gvn -S | FileCheck %s
+; RUN: opt < %s -gvn -enable-simple-gvn-hoist=false -S | FileCheck %s
+; RUN: opt < %s -passes=gvn -enable-simple-gvn-hoist=false -S | FileCheck %s
+; RUN: opt < %s -passes=gvn -S | FileCheck %s --check-prefix=CHECK-HOIST
 
 define i1 @f(i1 %a) {
 ; CHECK-LABEL: @f(
 ; CHECK-NEXT:    [[B:%.*]] = freeze i1 [[A:%.*]]
 ; CHECK-NEXT:    ret i1 [[B]]
 ;
+; CHECK-HOIST-LABEL: @f(
+; CHECK-HOIST-NEXT:    [[B:%.*]] = freeze i1 [[A:%.*]]
+; CHECK-HOIST-NEXT:    ret i1 [[B]]
+;
   %b = freeze i1 %a
   %c = freeze i1 %a
   %d = and i1 %b, %b
   ret i1 %d
 }
 
 define void @f_multipleuses(i1 %a) {
 ; CHECK-LABEL: @f_multipleuses(
 ; CHECK-NEXT:    [[B:%.*]] = freeze i1 [[A:%.*]]
 ; CHECK-NEXT:    call void @use1(i1 [[B]])
 ; CHECK-NEXT:    call void @use1(i1 [[B]])
 ; CHECK-NEXT:    call void @use1(i1 [[B]])
 ; CHECK-NEXT:    ret void
 ;
+; CHECK-HOIST-LABEL: @f_multipleuses(
+; CHECK-HOIST-NEXT:    [[B:%.*]] = freeze i1 [[A:%.*]]
+; CHECK-HOIST-NEXT:    call void @use1(i1 [[B]])
+; CHECK-HOIST-NEXT:    call void @use1(i1 [[B]])
+; CHECK-HOIST-NEXT:    call void @use1(i1 [[B]])
+; CHECK-HOIST-NEXT:    ret void
+;
   %b = freeze i1 %a
   %c = freeze i1 %a
   call void @use1(i1 %b)
   call void @use1(i1 %c)
   call void @use1(i1 %c)
   ret void
 }
 
 define void @f_dom(i1 %cond, i1 %a) {
 ; CHECK-LABEL: @f_dom(
 ; CHECK-NEXT:    br i1 [[COND:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
 ; CHECK:       BB1:
 ; CHECK-NEXT:    [[X:%.*]] = freeze i1 [[A:%.*]]
 ; CHECK-NEXT:    call void @use1(i1 [[X]])
 ; CHECK-NEXT:    ret void
 ; CHECK:       BB2:
 ; CHECK-NEXT:    [[Y:%.*]] = freeze i1 [[A]]
 ; CHECK-NEXT:    call void @use2(i1 [[Y]])
 ; CHECK-NEXT:    ret void
 ;
+; CHECK-HOIST-LABEL: @f_dom(
+; CHECK-HOIST-NEXT:    [[X:%.*]] = freeze i1 [[A:%.*]]
+; CHECK-HOIST-NEXT:    br i1 [[COND:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK-HOIST:       BB1:
+; CHECK-HOIST-NEXT:    call void @use1(i1 [[X]])
+; CHECK-HOIST-NEXT:    ret void
+; CHECK-HOIST:       BB2:
+; CHECK-HOIST-NEXT:    call void @use2(i1 [[X]])
+; CHECK-HOIST-NEXT:    ret void
+;
   br i1 %cond, label %BB1, label %BB2
 BB1:
   %x = freeze i1 %a
   call void @use1(i1 %x)
   ret void
 BB2:
   %y = freeze i1 %a
   call void @use2(i1 %y) ; cannot use %x
   ret void
 }
 declare void @use1(i1)
 declare void @use2(i1)
 

llvm/test/Transforms/GVN/gc_relocate.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt -basic-aa -gvn -S < %s | FileCheck %s
+; RUN: opt -basic-aa -gvn --enable-simple-gvn-hoist=false -S < %s | FileCheck %s
+; RUN: opt -basic-aa -gvn                                 -S < %s | FileCheck %s --check-prefix=HOIST
 
 declare void @func()
 declare i32 @"personality_function"()
 
 define i1 @test_trivial(i32 addrspace(1)* %in) gc "statepoint-example" {
 ; CHECK-LABEL: @test_trivial(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[SAFEPOINT_TOKEN:%.*]] = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* @func, i32 0, i32 0, i32 0, i32 0) [ "gc-live"(i32 addrspace(1)* [[IN:%.*]]) ]
 ; CHECK-NEXT:    [[A:%.*]] = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token [[SAFEPOINT_TOKEN]], i32 0, i32 0)
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 addrspace(1)* [[A]], null
 ; CHECK-NEXT:    ret i1 [[CMP1]]
 ;
+; HOIST-LABEL: @test_trivial(
+; HOIST-NEXT:  entry:
+; HOIST-NEXT:    [[SAFEPOINT_TOKEN:%.*]] = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* @func, i32 0, i32 0, i32 0, i32 0) [ "gc-live"(i32 addrspace(1)* [[IN:%.*]]) ]
+; HOIST-NEXT:    [[A:%.*]] = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token [[SAFEPOINT_TOKEN]], i32 0, i32 0)
+; HOIST-NEXT:    [[CMP1:%.*]] = icmp eq i32 addrspace(1)* [[A]], null
+; HOIST-NEXT:    ret i1 [[CMP1]]
+;
 entry:
   %safepoint_token = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* @func, i32 0, i32 0, i32 0, i32 0) ["gc-live"(i32 addrspace(1)* %in)]
   %a = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token %safepoint_token,  i32 0, i32 0)
   %b = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token %safepoint_token,  i32 0, i32 0)
   %cmp1 = icmp eq i32 addrspace(1)* %a, null
   %cmp2 = icmp eq i32 addrspace(1)* %b, null
   %cmp = and i1 %cmp1, %cmp2
   ret i1 %cmp
 }
 
 @G = external global i32
 
 define i1 @test_readnone(i32 addrspace(1)* %in) gc "statepoint-example" {
 ; CHECK-LABEL: @test_readnone(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[SAFEPOINT_TOKEN:%.*]] = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* @func, i32 0, i32 0, i32 0, i32 0) [ "gc-live"(i32 addrspace(1)* [[IN:%.*]]) ]
 ; CHECK-NEXT:    [[A:%.*]] = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token [[SAFEPOINT_TOKEN]], i32 0, i32 0)
 ; CHECK-NEXT:    store i32 0, i32* @G, align 4
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 addrspace(1)* [[A]], null
 ; CHECK-NEXT:    ret i1 [[CMP1]]
 ;
+; HOIST-LABEL: @test_readnone(
+; HOIST-NEXT:  entry:
+; HOIST-NEXT:    [[SAFEPOINT_TOKEN:%.*]] = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* @func, i32 0, i32 0, i32 0, i32 0) [ "gc-live"(i32 addrspace(1)* [[IN:%.*]]) ]
+; HOIST-NEXT:    [[A:%.*]] = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token [[SAFEPOINT_TOKEN]], i32 0, i32 0)
+; HOIST-NEXT:    store i32 0, i32* @G, align 4
+; HOIST-NEXT:    [[CMP1:%.*]] = icmp eq i32 addrspace(1)* [[A]], null
+; HOIST-NEXT:    ret i1 [[CMP1]]
+;
 entry:
   %safepoint_token = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* @func, i32 0, i32 0, i32 0, i32 0) ["gc-live"(i32 addrspace(1)* %in)]
   %a = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token %safepoint_token,  i32 0, i32 0)
   store i32 0, i32* @G
   %b = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token %safepoint_token,  i32 0, i32 0)
   %cmp1 = icmp eq i32 addrspace(1)* %a, null
   %cmp2 = icmp eq i32 addrspace(1)* %b, null
   %cmp = and i1 %cmp1, %cmp2
   ret i1 %cmp
 }
 
 define i1 @test_call(i32 addrspace(1)* %in) gc "statepoint-example" {
 ; CHECK-LABEL: @test_call(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[SAFEPOINT_TOKEN:%.*]] = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* @func, i32 0, i32 0, i32 0, i32 0) [ "gc-live"(i32 addrspace(1)* [[IN:%.*]], i32 addrspace(1)* [[IN]]) ]
 ; CHECK-NEXT:    [[BASE:%.*]] = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token [[SAFEPOINT_TOKEN]], i32 0, i32 0)
 ; CHECK-NEXT:    [[SAFEPOINT_TOKEN2:%.*]] = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* @func, i32 0, i32 0, i32 0, i32 0) [ "gc-live"(i32 addrspace(1)* [[BASE]], i32 addrspace(1)* [[BASE]]) ]
 ; CHECK-NEXT:    [[BASE_RELOC:%.*]] = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token [[SAFEPOINT_TOKEN2]], i32 0, i32 0)
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 addrspace(1)* [[BASE_RELOC]], null
 ; CHECK-NEXT:    ret i1 [[CMP1]]
 ;
+; HOIST-LABEL: @test_call(
+; HOIST-NEXT:  entry:
+; HOIST-NEXT:    [[SAFEPOINT_TOKEN:%.*]] = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* @func, i32 0, i32 0, i32 0, i32 0) [ "gc-live"(i32 addrspace(1)* [[IN:%.*]], i32 addrspace(1)* [[IN]]) ]
+; HOIST-NEXT:    [[BASE:%.*]] = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token [[SAFEPOINT_TOKEN]], i32 0, i32 0)
+; HOIST-NEXT:    [[SAFEPOINT_TOKEN2:%.*]] = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* @func, i32 0, i32 0, i32 0, i32 0) [ "gc-live"(i32 addrspace(1)* [[BASE]], i32 addrspace(1)* [[BASE]]) ]
+; HOIST-NEXT:    [[BASE_RELOC:%.*]] = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token [[SAFEPOINT_TOKEN2]], i32 0, i32 0)
+; HOIST-NEXT:    [[CMP1:%.*]] = icmp eq i32 addrspace(1)* [[BASE_RELOC]], null
+; HOIST-NEXT:    ret i1 [[CMP1]]
+;
 entry:
   %safepoint_token = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* @func, i32 0, i32 0, i32 0, i32 0) ["gc-live"(i32 addrspace(1)* %in, i32 addrspace(1)* %in)]
   %base = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token %safepoint_token,  i32 0, i32 0)
   %derived = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token %safepoint_token,  i32 0, i32 1)
   %safepoint_token2 = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* @func, i32 0, i32 0, i32 0, i32 0) ["gc-live"(i32 addrspace(1)* %base, i32 addrspace(1)* %derived)]
   br label %next
 
 next:

 ; CHECK-NEXT:    [[SAFEPOINT_TOKEN:%.*]] = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* @func, i32 0, i32 0, i32 0, i32 0) [ "gc-live"(i32 addrspace(1)* [[IN1:%.*]], i32 addrspace(1)* [[IN2:%.*]]) ]
 ; CHECK-NEXT:    [[IN1_RELOC1:%.*]] = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token [[SAFEPOINT_TOKEN]], i32 0, i32 0)
 ; CHECK-NEXT:    [[IN2_RELOC1:%.*]] = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token [[SAFEPOINT_TOKEN]], i32 1, i32 1)
 ; CHECK-NEXT:    [[SAFEPOINT_TOKEN2:%.*]] = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* @func, i32 0, i32 0, i32 0, i32 0) [ "gc-live"(i32 addrspace(1)* [[IN1_RELOC1]], i32 addrspace(1)* [[IN2_RELOC1]]) ]
 ; CHECK-NEXT:    [[IN1_RELOC2:%.*]] = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token [[SAFEPOINT_TOKEN2]], i32 0, i32 1)
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 addrspace(1)* [[IN1_RELOC2]], null
 ; CHECK-NEXT:    ret i1 [[CMP1]]
 ;
+; HOIST-LABEL: @test_two_calls(
+; HOIST-NEXT:  entry:
+; HOIST-NEXT:    [[SAFEPOINT_TOKEN:%.*]] = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* @func, i32 0, i32 0, i32 0, i32 0) [ "gc-live"(i32 addrspace(1)* [[IN1:%.*]], i32 addrspace(1)* [[IN2:%.*]]) ]
+; HOIST-NEXT:    [[IN1_RELOC1:%.*]] = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token [[SAFEPOINT_TOKEN]], i32 0, i32 0)
+; HOIST-NEXT:    [[IN2_RELOC1:%.*]] = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token [[SAFEPOINT_TOKEN]], i32 1, i32 1)
+; HOIST-NEXT:    [[SAFEPOINT_TOKEN2:%.*]] = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* @func, i32 0, i32 0, i32 0, i32 0) [ "gc-live"(i32 addrspace(1)* [[IN1_RELOC1]], i32 addrspace(1)* [[IN2_RELOC1]]) ]
+; HOIST-NEXT:    [[IN1_RELOC2:%.*]] = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token [[SAFEPOINT_TOKEN2]], i32 0, i32 1)
+; HOIST-NEXT:    [[CMP1:%.*]] = icmp eq i32 addrspace(1)* [[IN1_RELOC2]], null
+; HOIST-NEXT:    ret i1 [[CMP1]]
+;
 entry:
   %safepoint_token = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* @func, i32 0, i32 0, i32 0, i32 0) ["gc-live"(i32 addrspace(1)* %in1, i32 addrspace(1)* %in2)]
   %in1.reloc1 = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token %safepoint_token,  i32 0, i32 0)
   %in2.reloc1 = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token %safepoint_token,  i32 1, i32 1)
   %safepoint_token2 = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* @func, i32 0, i32 0, i32 0, i32 0) ["gc-live"(i32 addrspace(1)* %in1.reloc1, i32 addrspace(1)* %in2.reloc1)]
   %in1.reloc2 = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token %safepoint_token2,  i32 0, i32 1)
   %in2.reloc2 = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token %safepoint_token2,  i32 0, i32 1)
   %cmp1 = icmp eq i32 addrspace(1)* %in1.reloc2, null

 ; CHECK-NEXT:    [[OUT:%.*]] = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token [[SAFEPOINT_TOKEN]], i32 0, i32 0)
 ; CHECK-NEXT:    ret i32 addrspace(1)* [[OUT]]
 ; CHECK:       exceptional_return:
 ; CHECK-NEXT:    [[LANDING_PAD:%.*]] = landingpad token
 ; CHECK-NEXT:    cleanup
 ; CHECK-NEXT:    [[OUT1:%.*]] = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token [[LANDING_PAD]], i32 0, i32 0)
 ; CHECK-NEXT:    ret i32 addrspace(1)* [[OUT1]]
 ;
+; HOIST-LABEL: @test_invoke(
+; HOIST-NEXT:    [[SAFEPOINT_TOKEN:%.*]] = invoke token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* @func, i32 0, i32 0, i32 0, i32 0) [ "gc-live"(i32 addrspace(1)* [[IN:%.*]]) ]
+; HOIST-NEXT:    to label [[INVOKE_NORMAL_DEST:%.*]] unwind label [[EXCEPTIONAL_RETURN:%.*]]
+; HOIST:       invoke_normal_dest:
+; HOIST-NEXT:    [[OUT:%.*]] = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token [[SAFEPOINT_TOKEN]], i32 0, i32 0)
+; HOIST-NEXT:    ret i32 addrspace(1)* [[OUT]]
+; HOIST:       exceptional_return:
+; HOIST-NEXT:    [[LANDING_PAD:%.*]] = landingpad token
+; HOIST-NEXT:    cleanup
+; HOIST-NEXT:    [[OUT1:%.*]] = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token [[LANDING_PAD]], i32 0, i32 0)
+; HOIST-NEXT:    ret i32 addrspace(1)* [[OUT1]]
+;
   %safepoint_token = invoke token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* @func, i32 0, i32 0, i32 0, i32 0) ["gc-live"(i32 addrspace(1)* %in)]
   to label %invoke_normal_dest unwind label %exceptional_return
 
 invoke_normal_dest:
   %out = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token %safepoint_token,  i32 0, i32 0)
   ret i32 addrspace(1)* %out
 
 exceptional_return:

 ; CHECK-NEXT:    [[A:%.*]] = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token [[SAFEPOINT_TOKEN]], i32 0, i32 0)
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 addrspace(1)* [[A]], null
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ; CHECK:       untaken:
 ; CHECK-NEXT:    [[B:%.*]] = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token [[SAFEPOINT_TOKEN]], i32 0, i32 0)
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp eq i32 addrspace(1)* [[B]], null
 ; CHECK-NEXT:    ret i1 [[CMP2]]
 ;
+; HOIST-LABEL: @test_non_dominating(
+; HOIST-NEXT:  entry:
+; HOIST-NEXT:    [[SAFEPOINT_TOKEN:%.*]] = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* @func, i32 0, i32 0, i32 0, i32 0) [ "gc-live"(i32 addrspace(1)* [[IN:%.*]]) ]
+; HOIST-NEXT:    [[A:%.*]] = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token [[SAFEPOINT_TOKEN]], i32 0, i32 0)
+; HOIST-NEXT:    [[CMP:%.*]] = icmp eq i32 addrspace(1)* [[A]], null
+; HOIST-NEXT:    br i1 [[C:%.*]], label [[TAKEN:%.*]], label [[UNTAKEN:%.*]]
+; HOIST:       taken:
+; HOIST-NEXT:    ret i1 [[CMP]]
+; HOIST:       untaken:
+; HOIST-NEXT:    ret i1 [[CMP]]
+;
 entry:
   %safepoint_token = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* @func, i32 0, i32 0, i32 0, i32 0) ["gc-live"(i32 addrspace(1)* %in)]
   br i1 %c, label %taken, label %untaken
 taken:
   %a = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token %safepoint_token,  i32 0, i32 0)
   %cmp = icmp eq i32 addrspace(1)* %a, null
   ret i1 %cmp
 untaken:
   %b = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token %safepoint_token,  i32 0, i32 0)
   %cmp2 = icmp eq i32 addrspace(1)* %b, null
   ret i1 %cmp2
 }
 
 declare token @llvm.experimental.gc.statepoint.p0f_isVoidf(i64, i32, void ()*, i32, i32, ...)
 declare i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token, i32, i32)

llvm/test/Transforms/GVN/simple-gvnhoist-scalars.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt --passes=gvn -S %s | FileCheck %s
 
 target triple = "aarch64-unknown-linux"
 
 ; everything hoisted
 define dso_local i32 @everything_hoisted(i1 %cc, i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @everything_hoisted(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    br i1 [[CC:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
-; CHECK:       if.then:
 ; CHECK-NEXT:    [[TMP0:%.*]] = add nsw i32 [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    [[TMP1:%.*]] = sdiv i32 [[C:%.*]], [[TMP0]]
+; CHECK-NEXT:    br i1 [[CC:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
+; CHECK:       if.then:
 ; CHECK-NEXT:    br label [[IF_END:%.*]]
 ; CHECK:       if.else:
-; CHECK-NEXT:    [[TMP2:%.*]] = add nsw i32 [[A]], [[B]]
-; CHECK-NEXT:    [[TMP3:%.*]] = sdiv i32 [[C]], [[TMP2]]
 ; CHECK-NEXT:    br label [[IF_END]]
 ; CHECK:       if.end:
-; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[TMP1]], [[IF_THEN]] ], [ [[TMP3]], [[IF_ELSE]] ]
+; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[TMP1]], [[IF_THEN]] ], [ [[TMP1]], [[IF_ELSE]] ]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
 entry:
   br i1 %cc, label %if.then, label %if.else
 
 if.then:
   %0 = add nsw i32 %a, %b
   %1 = sdiv i32 %c, %0
   br label %if.end
 
 if.else:
   %2 = add nsw i32 %a, %b
   %3 = sdiv i32 %c, %2
   br label %if.end
 
 if.end:
   %r = phi i32 [%1, %if.then], [%3, %if.else]
   ret i32 %r
 }
 
 ; speculation barrier
 define dso_local i32 @spec_barrier0(i1 %cc, i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @spec_barrier0(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = add nsw i32 [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    br i1 [[CC:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
 ; CHECK:       if.then:
 ; CHECK-NEXT:    call void @h()
-; CHECK-NEXT:    [[TMP0:%.*]] = add nsw i32 [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    [[TMP1:%.*]] = sdiv i32 [[C:%.*]], [[TMP0]]
 ; CHECK-NEXT:    br label [[IF_END:%.*]]
 ; CHECK:       if.else:
 ; CHECK-NEXT:    call void @h()
-; CHECK-NEXT:    [[TMP2:%.*]] = add nsw i32 [[A]], [[B]]
-; CHECK-NEXT:    [[TMP3:%.*]] = sdiv i32 [[C]], [[TMP2]]
+; CHECK-NEXT:    [[TMP2:%.*]] = sdiv i32 [[C]], [[TMP0]]
 ; CHECK-NEXT:    br label [[IF_END]]
 ; CHECK:       if.end:
-; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[TMP1]], [[IF_THEN]] ], [ [[TMP3]], [[IF_ELSE]] ]
+; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[TMP1]], [[IF_THEN]] ], [ [[TMP2]], [[IF_ELSE]] ]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
 entry:
   br i1 %cc, label %if.then, label %if.else
 
 if.then:
   call void @h()
   %0 = add nsw i32 %a, %b
if.end:
   %r = phi i32 [%1, %if.then], [%3, %if.else]
   ret i32 %r
 }
 
 ; speculation barrier
 define dso_local i32 @spec_barrier1(i1 %cc, i32 %a, i32 %b, i32 %c, i32* %p) {
 ; CHECK-LABEL: @spec_barrier1(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = add nsw i32 [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    br i1 [[CC:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
 ; CHECK:       if.then:
 ; CHECK-NEXT:    store volatile i32 0, i32* [[P:%.*]], align 4
-; CHECK-NEXT:    [[TMP0:%.*]] = add nsw i32 [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    [[TMP1:%.*]] = sdiv i32 [[C:%.*]], [[TMP0]]
 ; CHECK-NEXT:    br label [[IF_END:%.*]]
 ; CHECK:       if.else:
 ; CHECK-NEXT:    store volatile i32 0, i32* [[P]], align 4
-; CHECK-NEXT:    [[TMP2:%.*]] = add nsw i32 [[A]], [[B]]
-; CHECK-NEXT:    [[TMP3:%.*]] = sdiv i32 [[C]], [[TMP2]]
+; CHECK-NEXT:    [[TMP2:%.*]] = sdiv i32 [[C]], [[TMP0]]
 ; CHECK-NEXT:    br label [[IF_END]]
 ; CHECK:       if.end:
-; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[TMP1]], [[IF_THEN]] ], [ [[TMP3]], [[IF_ELSE]] ]
+; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[TMP1]], [[IF_THEN]] ], [ [[TMP2]], [[IF_ELSE]] ]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
 entry:
   br i1 %cc, label %if.then, label %if.else
 
 if.then:
   store volatile i32 0, i32* %p
   %0 = add nsw i32 %a, %b
if.end:
   %r = phi i32 [%1, %if.then], [%3, %if.else]
   ret i32 %r
 }
 
 ; no speculation barrier
 define dso_local i32 @no_spec_barrier0(i1 %cc, i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @no_spec_barrier0(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = sdiv i32 [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = add nsw i32 [[C:%.*]], [[TMP0]]
 ; CHECK-NEXT:    br i1 [[CC:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
 ; CHECK:       if.then:
 ; CHECK-NEXT:    call void @will_return()
-; CHECK-NEXT:    [[TMP0:%.*]] = sdiv i32 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[TMP1:%.*]] = add nsw i32 [[C:%.*]], [[TMP0]]
 ; CHECK-NEXT:    br label [[IF_END:%.*]]
 ; CHECK:       if.else:
 ; CHECK-NEXT:    call void @will_return()
-; CHECK-NEXT:    [[TMP2:%.*]] = sdiv i32 [[A]], [[B]]
-; CHECK-NEXT:    [[TMP3:%.*]] = add nsw i32 [[C]], [[TMP2]]
 ; CHECK-NEXT:    br label [[IF_END]]
 ; CHECK:       if.end:
-; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[TMP1]], [[IF_THEN]] ], [ [[TMP3]], [[IF_ELSE]] ]
+; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[TMP1]], [[IF_THEN]] ], [ [[TMP1]], [[IF_ELSE]] ]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
 entry:
   br i1 %cc, label %if.then, label %if.else
 
 if.then:
   call void @will_return()
   %0 = sdiv i32 %a, %b
if.end:
   %r = phi i32 [%1, %if.then], [%3, %if.else]
   ret i32 %r
 }
 
 ; no speculation barrier
 define dso_local i32 @no_spec_barrier1(i1 %cc, i32 %a, i32 %b, i32 %c, i32* %p) {
 ; CHECK-LABEL: @no_spec_barrier1(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = sdiv i32 [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = add nsw i32 [[C:%.*]], [[TMP0]]
 ; CHECK-NEXT:    br i1 [[CC:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
 ; CHECK:       if.then:
-; CHECK-NEXT:    [[TMP0:%.*]] = load atomic volatile i32, i32* [[P:%.*]] acquire, align 4
-; CHECK-NEXT:    [[TMP1:%.*]] = sdiv i32 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = add nsw i32 [[C:%.*]], [[TMP1]]
-; CHECK-NEXT:    [[TMP3:%.*]] = mul nsw i32 [[TMP0]], [[TMP2]]
+; CHECK-NEXT:    [[TMP2:%.*]] = load atomic volatile i32, i32* [[P:%.*]] acquire, align 4
+; CHECK-NEXT:    [[TMP3:%.*]] = mul nsw i32 [[TMP2]], [[TMP1]]
 ; CHECK-NEXT:    br label [[IF_END:%.*]]
 ; CHECK:       if.else:
 ; CHECK-NEXT:    [[TMP4:%.*]] = load atomic volatile i32, i32* [[P]] acquire, align 4
-; CHECK-NEXT:    [[TMP5:%.*]] = sdiv i32 [[A]], [[B]]
-; CHECK-NEXT:    [[TMP6:%.*]] = add nsw i32 [[C]], [[TMP5]]
-; CHECK-NEXT:    [[TMP7:%.*]] = mul nsw i32 [[TMP4]], [[TMP6]]
+; CHECK-NEXT:    [[TMP5:%.*]] = mul nsw i32 [[TMP4]], [[TMP1]]
 ; CHECK-NEXT:    br label [[IF_END]]
 ; CHECK:       if.end:
-; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[TMP3]], [[IF_THEN]] ], [ [[TMP7]], [[IF_ELSE]] ]
+; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[TMP3]], [[IF_THEN]] ], [ [[TMP5]], [[IF_ELSE]] ]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
 entry:
   br i1 %cc, label %if.then, label %if.else
 
 if.then:
   %0 = load atomic volatile i32, i32* %p acquire, align 4
   %1 = sdiv i32 %a, %b
if.end:
   %r = phi i32 [%3, %if.then], [%7, %if.else]
   ret i32 %r
 }
 
 ; multiple uses of a hoisted instruction
 define dso_local i32 @multiple_use(i1 %cc, i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @multiple_use(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    br i1 [[CC:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
-; CHECK:       if.then:
 ; CHECK-NEXT:    [[TMP0:%.*]] = add nsw i32 [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    [[TMP1:%.*]] = mul nsw i32 [[TMP0]], [[C:%.*]]
 ; CHECK-NEXT:    [[TMP2:%.*]] = add nsw i32 [[TMP0]], [[TMP1]]
+; CHECK-NEXT:    br i1 [[CC:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
+; CHECK:       if.then:
 ; CHECK-NEXT:    br label [[IF_END:%.*]]
 ; CHECK:       if.else:
-; CHECK-NEXT:    [[TMP3:%.*]] = add nsw i32 [[A]], [[B]]
-; CHECK-NEXT:    [[TMP4:%.*]] = mul nsw i32 [[TMP3]], [[C]]
-; CHECK-NEXT:    [[TMP5:%.*]] = add nsw i32 [[TMP3]], [[TMP4]]
 ; CHECK-NEXT:    br label [[IF_END]]
 ; CHECK:       if.end:
-; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[TMP2]], [[IF_THEN]] ], [ [[TMP5]], [[IF_ELSE]] ]
+; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[TMP2]], [[IF_THEN]] ], [ [[TMP2]], [[IF_ELSE]] ]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
 entry:
   br i1 %cc, label %if.then, label %if.else
 
 if.then:
   %0 = add nsw i32 %a, %b
   %1 = mul nsw i32 %0, %c
if.end:
   %r = phi i32 [%2, %if.then], [%5, %if.else]
   ret i32 %r
 }
 
 ; Different operand order in commutative operations
 define dso_local i32 @commutative_ops(i1 %cc, i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @commutative_ops(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    br i1 [[CC:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
-; CHECK:       if.then:
 ; CHECK-NEXT:    [[TMP0:%.*]] = add nsw i32 [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    [[TMP1:%.*]] = add nsw i32 [[TMP0]], [[C:%.*]]
 ; CHECK-NEXT:    [[TMP2:%.*]] = sdiv i32 [[TMP0]], [[TMP1]]
+; CHECK-NEXT:    br i1 [[CC:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
+; CHECK:       if.then:
 ; CHECK-NEXT:    br label [[IF_END:%.*]]
 ; CHECK:       if.else:
-; CHECK-NEXT:    [[TMP3:%.*]] = add nsw i32 [[A]], [[B]]
-; CHECK-NEXT:    [[TMP4:%.*]] = add nsw i32 [[C]], [[TMP3]]
-; CHECK-NEXT:    [[TMP5:%.*]] = sdiv i32 [[TMP3]], [[TMP4]]
 ; CHECK-NEXT:    br label [[IF_END]]
 ; CHECK:       if.end:
-; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[TMP2]], [[IF_THEN]] ], [ [[TMP5]], [[IF_ELSE]] ]
+; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[TMP2]], [[IF_THEN]] ], [ [[TMP2]], [[IF_ELSE]] ]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
 entry:
   br i1 %cc, label %if.then, label %if.else
 
 if.then:
   %0 = add nsw i32 %a, %b
   %1 = add nsw i32 %0, %c

llvm/test/Transforms/InstCombine/phi-equal-incoming-pointers.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -passes=instcombine,verify -S < %s | FileCheck %s --check-prefixes=ALL,INSTCOMBINE
 
 ; Make sure GVN won't undo the transformation:
-; RUN: opt -passes=instcombine,gvn -S < %s | FileCheck %s --check-prefixes=ALL,INSTCOMBINEGVN
+; RUN: opt -passes=instcombine,gvn --enable-simple-gvn-hoist=false -S < %s | FileCheck %s --check-prefixes=ALL,INSTCOMBINEGVN
 
 declare i8* @get_ptr.i8()
 declare i32* @get_ptr.i32()
 declare void @foo.i8(i8*)
 declare void @foo.i32(i32*)
 
 define i32 @test_gep_and_bitcast(i1 %cond, i1 %cond2) {
 ; ALL-LABEL: @test_gep_and_bitcast(

llvm/test/Transforms/PhaseOrdering/AArch64/hoisting-sinking-required-for-vectorization.ll

 ; CHECK-NEXT:    [[BROADCAST_SPLAT:%.*]] = shufflevector <4 x float> [[BROADCAST_SPLATINSERT]], <4 x float> poison, <4 x i32> zeroinitializer
 ; CHECK-NEXT:    br label [[VECTOR_BODY:%.*]]
 ; CHECK:       vector.body:
 ; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ]
 ; CHECK-NEXT:    [[TMP2:%.*]] = getelementptr inbounds i32, i32* [[C]], i64 [[INDEX]]
 ; CHECK-NEXT:    [[TMP3:%.*]] = bitcast i32* [[TMP2]] to <4 x i32>*
 ; CHECK-NEXT:    [[WIDE_LOAD:%.*]] = load <4 x i32>, <4 x i32>* [[TMP3]], align 4, !alias.scope !8
 ; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq <4 x i32> [[WIDE_LOAD]], <i32 20, i32 20, i32 20, i32 20>
-; CHECK-NEXT:    [[TMP5:%.*]] = getelementptr inbounds float, float* [[A]], i64 [[INDEX]]
-; CHECK-NEXT:    [[TMP6:%.*]] = bitcast float* [[TMP5]] to <4 x float>*
-; CHECK-NEXT:    [[WIDE_LOAD14:%.*]] = load <4 x float>, <4 x float>* [[TMP6]], align 4, !alias.scope !11
-; CHECK-NEXT:    [[TMP7:%.*]] = fmul <4 x float> [[WIDE_LOAD14]], [[BROADCAST_SPLAT]]
-; CHECK-NEXT:    [[TMP8:%.*]] = getelementptr inbounds float, float* [[B]], i64 [[INDEX]]
-; CHECK-NEXT:    [[TMP9:%.*]] = bitcast float* [[TMP8]] to <4 x float>*
+; CHECK-NEXT:    [[TMP5:%.*]] = getelementptr inbounds float, float* [[B]], i64 [[INDEX]]
+; CHECK-NEXT:    [[TMP6:%.*]] = getelementptr inbounds float, float* [[A]], i64 [[INDEX]]
+; CHECK-NEXT:    [[TMP7:%.*]] = bitcast float* [[TMP6]] to <4 x float>*
+; CHECK-NEXT:    [[WIDE_LOAD14:%.*]] = load <4 x float>, <4 x float>* [[TMP7]], align 4, !alias.scope !11
+; CHECK-NEXT:    [[TMP8:%.*]] = fmul <4 x float> [[WIDE_LOAD14]], [[BROADCAST_SPLAT]]
+; CHECK-NEXT:    [[TMP9:%.*]] = bitcast float* [[TMP5]] to <4 x float>*
 ; CHECK-NEXT:    [[WIDE_LOAD15:%.*]] = load <4 x float>, <4 x float>* [[TMP9]], align 4, !alias.scope !13, !noalias !15
-; CHECK-NEXT:    [[TMP10:%.*]] = fadd <4 x float> [[TMP7]], [[WIDE_LOAD15]]
-; CHECK-NEXT:    [[PREDPHI:%.*]] = select <4 x i1> [[TMP4]], <4 x float> [[TMP7]], <4 x float> [[TMP10]]
-; CHECK-NEXT:    [[TMP11:%.*]] = bitcast float* [[TMP8]] to <4 x float>*
+; CHECK-NEXT:    [[TMP10:%.*]] = fadd <4 x float> [[TMP8]], [[WIDE_LOAD15]]
+; CHECK-NEXT:    [[PREDPHI:%.*]] = select <4 x i1> [[TMP4]], <4 x float> [[TMP8]], <4 x float> [[TMP10]]
+; CHECK-NEXT:    [[TMP11:%.*]] = bitcast float* [[TMP5]] to <4 x float>*
 ; CHECK-NEXT:    store <4 x float> [[PREDPHI]], <4 x float>* [[TMP11]], align 4, !alias.scope !13, !noalias !15
 ; CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
 ; CHECK-NEXT:    [[TMP12:%.*]] = icmp eq i64 [[INDEX_NEXT]], 10000
 ; CHECK-NEXT:    br i1 [[TMP12]], label [[EXIT:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP16:![0-9]+]]
 ; CHECK:       loop.body:
 ; CHECK-NEXT:    [[IV1:%.*]] = phi i64 [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ], [ 0, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    [[C_GEP:%.*]] = getelementptr inbounds i32, i32* [[C]], i64 [[IV1]]
 ; CHECK-NEXT:    [[C_LV:%.*]] = load i32, i32* [[C_GEP]], align 4
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[C_LV]], 20
+; CHECK-NEXT:    [[B_GEP_0:%.*]] = getelementptr inbounds float, float* [[B]], i64 [[IV1]]
 ; CHECK-NEXT:    [[A_GEP_0:%.*]] = getelementptr inbounds float, float* [[A]], i64 [[IV1]]
 ; CHECK-NEXT:    [[A_LV_0:%.*]] = load float, float* [[A_GEP_0]], align 4
 ; CHECK-NEXT:    [[MUL2_I81_I:%.*]] = fmul float [[A_LV_0]], [[X]]
-; CHECK-NEXT:    [[B_GEP_0:%.*]] = getelementptr inbounds float, float* [[B]], i64 [[IV1]]
 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP_LATCH]], label [[ELSE:%.*]]
 ; CHECK:       else:
 ; CHECK-NEXT:    [[B_LV:%.*]] = load float, float* [[B_GEP_0]], align 4
 ; CHECK-NEXT:    [[ADD:%.*]] = fadd float [[MUL2_I81_I]], [[B_LV]]
 ; CHECK-NEXT:    br label [[LOOP_LATCH]]
 ; CHECK:       loop.latch:
-; CHECK-NEXT:    [[ADD_SINK:%.*]] = phi float [ [[ADD]], [[ELSE]] ], [ [[MUL2_I81_I]], [[LOOP_BODY]] ]
-; CHECK-NEXT:    store float [[ADD_SINK]], float* [[B_GEP_0]], align 4
+; CHECK-NEXT:    [[STOREMERGE:%.*]] = phi float [ [[ADD]], [[ELSE]] ], [ [[MUL2_I81_I]], [[LOOP_BODY]] ]
+; CHECK-NEXT:    store float [[STOREMERGE]], float* [[B_GEP_0]], align 4
 ; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i64 [[IV1]], 1
 ; CHECK-NEXT:    [[CMP_0:%.*]] = icmp ult i64 [[IV1]], 9999
 ; CHECK-NEXT:    br i1 [[CMP_0]], label [[LOOP_BODY]], label [[EXIT]], !llvm.loop [[LOOP17:![0-9]+]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %loop.header