[GVN] Simple GVN hoist

[chill]

Summary

RFC: 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.

Instructions are paired via sort/merge (could be hashing instead).

Certain instructions act as "hoist barriers" in the sense that they
stop scanning the block for more hoist candidates, thus preventing
instructions to be reordering above them. They themselves can be
hoisted, though, which creates opportunities to hoist other
instructions, which is achieved by consecutive iterations of the
transformation.

Consecutive iterations are also needed to handle loads, which have
unique value numbers.

Initial benchmarking on Neoverse N1 looks good (speedup, higher is
better):

500.perlbench_r 1.13%
502.gcc_r 0.00%
505.mcf_r -1.89%
520.omnetpp_r 0.00%
523.xalancbmk_r 0.00%
525.x264_r 7.67%
531.deepsjeng_r 0.60%
541.leela_r 0.24%
548.exchange2_r 0.00%
557.xz_r 0.75%

(There's that 2% regression in mcf that I've not investigated yet).

[chill]

llvm/lib/Transforms/Scalar/GVN.cpp

672

Oops, leftover change, will revert.

[SjoerdMeijer]

Quick question on the perf numbers. Do you know what the problem is with MCF? Would be good if we can avoid this regression, then the numbers are even better....

[xbolva00]

I believe the latest issues with gvnhoist were regressions, what about to take a look at this pass again and possibly enable (some “obviously” profitable) parts of gvnhoist again?

Did you run spec benchmarks with trunk+gvnhoist?

[junparser]

Thanks for your patch！

llvm/lib/Transforms/Scalar/GVN.cpp

2494

It is better to add parameter like gvn-hoist-max-chain-length in gvnhoist here based on running data from spec.

2842

can you give an example that when I can not transfer execution, how do subsequent instructions in BB to be hoisted? IMHO, collectHoistCandidates should stop here.

2860

Is there any reason not to handle GEPs?

3034

ditto

[junparser]

In D109760#3000216, @xbolva00 wrote:

I believe the latest issues with gvnhoist were regressions, what about to take a look at this pass again and possibly enable (some “obviously” profitable) parts of gvnhoist again?

Did you run spec benchmarks with trunk+gvnhoist?

I was testing spce cpu2017 with gvnhoist recently. perlbench and gcc have regression. It seems that the default value of gvnhoist parameters are too aggressive.

[junparser]

As for mcf, I guess it may casued by large register pressure due to hoist some expression from some huge successor. So simple cost model is necessary.

[chill]

In D109760#3000216, @xbolva00 wrote:

I believe the latest issues with gvnhoist were regressions, what about to take a look at this pass again and possibly enable (some “obviously” profitable) parts of gvnhoist again?

Did you run spec benchmarks with trunk+gvnhoist?

I did and indeed I got even better speedup, but with -O2 -mllvm -enable-gvnhoist. With -O3 there was no improvement (and maybe a regression) (due to unrolling, see thread on the mailing list).

In D109760#3001010, @junparser wrote:

As for mcf, I guess it may casued by large register pressure due to hoist some expression from some huge successor. So simple cost model is necessary.

In D109760#3000184, @SjoerdMeijer wrote:

Quick question on the perf numbers. Do you know what the problem is with MCF? Would be good if we can avoid this regression, then the numbers are even better....

No idea why MCF regresses. My plan was to look at MCF regressions and why -O2 -enable-gvnhoist gives better numbers than -O3 + this patch.

[xbolva00]

In D109760#3001467, @chill wrote:

In D109760#3000216, @xbolva00 wrote:

I believe the latest issues with gvnhoist were regressions, what about to take a look at this pass again and possibly enable (some “obviously” profitable) parts of gvnhoist again?

Did you run spec benchmarks with trunk+gvnhoist?

I did and indeed I got even better speedup, but with -O2 -mllvm -enable-gvnhoist. With -O3 there was no improvement (and maybe a regression) (due to unrolling, see thread on the mailing list).

In D109760#3001010, @junparser wrote:

As for mcf, I guess it may casued by large register pressure due to hoist some expression from some huge successor. So simple cost model is necessary.

In D109760#3000184, @SjoerdMeijer wrote:

Quick question on the perf numbers. Do you know what the problem is with MCF? Would be good if we can avoid this regression, then the numbers are even better....

No idea why MCF regresses. My plan was to look at MCF regressions and why -O2 -enable-gvnhoist gives better numbers than -O3 + this patch.

There is ongoing work to enhance slp with memory versioning by @fhahn - it should help

[chill]

llvm/lib/Transforms/Scalar/GVN.cpp

2842

For example:

define dso_local i32 @f2(i32 %c, i32 %a, i32 %b) {
entry:
  %tobool = icmp ne i32 %c, 0
  br i1 %tobool, label %if.then, label %if.else

if.then:
  call void @h()
  %0 = sdiv i32 %a, %b
  br label %if.end

if.else:
  call void @h()
  %1 = sdiv i32 %a, %b
  br label %if.end

if.end:
  %2  = phi i32 [%0, %if.then], [%1, %if.else]
  ret i32 %2
}

declare dso_local void @h() readnone

%0 and %1 will get the same value number, but should not be hoisted, unless call void @h() is also hoisted.
We would indeed stop the iteration in collectHoistCandidates, but hoist the call itself. Then on the next invocation of
performHoist we will have

define dso_local i32 @f2(i32 %c, i32 %a, i32 %b) {
entry:
  %tobool = icmp ne i32 %c, 0
  call void @h()
  br i1 %tobool, label %if.then, label %if.else

if.then:
  %0 = sdiv i32 %a, %b
  br label %if.end

if.else:
  %1 = sdiv i32 %a, %b
  br label %if.end

if.end:
  %2  = phi i32 [%0, %if.then], [%1, %if.else]
  ret i32 %2
}

declare dso_local void @h() readnone

and then we'll move the sdiv too.

2860

That's to avoid hoisting GEPs, but leaving their users behind. I was following the comment from GVNHoist.cpp

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.

I sort of assume someone measured and found that useful :D

3034

So, an instruction that reads or writes memory could be a local dependency. If you hoist such an instruction, it may turn the local dependency into a non-local one, thus allowing more hoisting.

I guess there are alternative approaches (see discussion on the ML) when we explicitly have a dependency instruction, e.g. a non-volatile load
followed by a non-volatile store, aliasing. Store can be hoisted only if the load is hoisted too.

Not clear what to do when we don't have an explicit dependency, e.g.

define dso_local i32 @f0(i32 %c, i32* %p, i32* %q) {
entry:
  %tobool = icmp ne i32 %c, 0
  br i1 %tobool, label %if.then, label %if.else

if.then:
  store volatile i32 0, i32* %p
  store volatile i32 0, i32* %q
  br label %if.end

if.else:
  store volatile i32 0, i32* %p
  store volatile i32 0, i32* %q
  br label %if.end

if.end:
  ret i32 0
}

(Current patch does not handle this case as well, I guess because of MemDep caching).

[junparser]

llvm/lib/Transforms/Scalar/GVN.cpp

2842

The thing is can we hoist instruction when isGuaranteedToTransferExecutionToSuccessor is true or isVolatile or maythrow. I'm not sure about this. I believe we should not hoist them.

3034

same issue with volatiled load/store.

[junparser]

In D109760#3001467, @chill wrote:

In D109760#3000216, @xbolva00 wrote:

I believe the latest issues with gvnhoist were regressions, what about to take a look at this pass again and possibly enable (some “obviously” profitable) parts of gvnhoist again?

Did you run spec benchmarks with trunk+gvnhoist?

I did and indeed I got even better speedup, but with -O2 -mllvm -enable-gvnhoist. With -O3 there was no improvement (and maybe a regression) (due to unrolling, see thread on the mailing list).

my test is under O3 + LTO

In D109760#3001010, @junparser wrote:

As for mcf, I guess it may casued by large register pressure due to hoist some expression from some huge successor. So simple cost model is necessary.

In D109760#3000184, @SjoerdMeijer wrote:

Quick question on the perf numbers. Do you know what the problem is with MCF? Would be good if we can avoid this regression, then the numbers are even better....

No idea why MCF regresses. My plan was to look at MCF regressions and why -O2 -enable-gvnhoist gives better numbers than -O3 + this patch.

With unrolling, hoist can infer longer lifetime for variable which may cause larger register pressure.

[chill]

This abandoned in favor of https://reviews.llvm.org/D110817 and https://reviews.llvm.org/D110822

llvm/lib/Transforms/Scalar/GVN.cpp

2494

It's in the works.

2842

We don't hoist individual instructions - only pairs. This is part of the way we make sure a we won't speculatively execute volatile/atomic instructions, nor we'd change the number and ordering of these in any execution sequence. If all other correctness conditions are satisfied, we can merge a volatile (or atomic) instruction with an instruction from the other block with the same volatile-ty and atomic ordering. This is fixed in the new series of patches.

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

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);
+  std::pair<bool, bool> performHoist(Function &F);
+  bool hoistPair(BasicBlock *DestBB, BasicBlock *ThenBB, BasicBlock *ElseBB,
+                 Instruction *ThenI, Instruction *ElseI);
+  void replaceInstruction(Instruction *, Instruction *);
+  void eraseInstruction(Instruction *);
   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-gvnhoist", 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) {}
 
PreservedAnalyses GVN::run(Function &F, FunctionAnalysisManager &AM) {
   // behavior, but until then don't change the order here.
   auto &AC = AM.getResult<AssumptionAnalysis>(F);
   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
   auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
   auto &AA = AM.getResult<AAManager>(F);
   auto *MemDep =
       isMemDepEnabled() ? &AM.getResult<MemoryDependenceAnalysis>(F) : nullptr;
   auto *LI = AM.getCachedResult<LoopAnalysis>(F);
   auto *MSSA = AM.getCachedResult<MemorySSAAnalysis>(F);
   auto &ORE = AM.getResult<OptimizationRemarkEmitterAnalysis>(F);
   bool Changed = runImpl(F, AC, DT, TLI, AA, MemDep, LI, &ORE,
                          MSSA ? &MSSA->getMSSA() : nullptr);
   if (!Changed)
     return PreservedAnalyses::all();
   PreservedAnalyses PA;
   PA.preserve<DominatorTreeAnalysis>();
   PA.preserve<TargetLibraryAnalysis>();
if (isPREEnabled()) {
     assignValNumForDeadCode();
     bool PREChanged = true;
     while (PREChanged) {
       PREChanged = performPRE(F);
       Changed |= PREChanged;
     }
   }
 
+  if (GVNEnableSimpleGVNHoist && MD) {
+    LeaderTable.clear();
+    bool RunAgain = true;
+    while (RunAgain) {
+      bool HoistedAny;
+      std::tie(HoistedAny, RunAgain) = performHoist(F);
+      Changed |= HoistedAny;
+      VN.clear();
+    }
+  }
+
   // 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.
for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
     // Avoid iterator invalidation.
     bool AtStart = BI == BB->begin();
     if (!AtStart)
       --BI;
 
     for (auto *I : InstrsToErase) {
       assert(I->getParent() == BB && "Removing instruction from wrong block?");
       LLVM_DEBUG(dbgs() << "GVN removed: " << *I << '\n');
-      salvageKnowledge(I, AC);
-      salvageDebugInfo(*I);
-      if (MD) MD->removeInstruction(I);
-      if (MSSAU)
-        MSSAU->removeMemoryAccess(I);
-      LLVM_DEBUG(verifyRemoved(I));
-      ICF->removeInstruction(I);
-      I->eraseFromParent();
+      eraseInstruction(I);
     }
     InstrsToErase.clear();
 
     if (AtStart)
       BI = BB->begin();
     else
       ++BI;
   }
for (BasicBlock *CurrentBlock : depth_first(&F.getEntryBlock())) {
     }
   }
 
   if (splitCriticalEdges())
     Changed = true;
 
   return Changed;
 }
+struct HoistCandidate {
+  HoistCandidate(uint32_t N, Instruction *I) : VN(N), Inst(I) {}
+  HoistCandidate(uint32_t N, uint32_t M, Instruction *I)
+      : VN((uint64_t(N) << 32) | M), Inst(I) {}
+  uint64_t VN;
+  Instruction *Inst;
+};
+
+// Won't reorder across these instructions, but still allow for them to be
+// hoisted.
+static bool isHoistBarrier(const Instruction &I) {
+  return I.isVolatile() || I.isAtomic() ||
+         !isGuaranteedToTransferExecutionToSuccessor(&I);
+}
+
+static void collectHoistCandidates(MemoryDependenceResults *MD,
+                                   GVN::ValueTable &VN, BasicBlock *BB,
+                                   std::vector<HoistCandidate> &Candidates,
+                                   bool Loads) {
+  bool HasHoistBarrier = false;
+  for (Instruction &I : *BB) {
+    if (HasHoistBarrier || I.isTerminator())
+      break;
+
+    if ((HasHoistBarrier = isHoistBarrier(I)))
+      LLVM_DEBUG(dbgs() << "Simple GVNHoist: reached hoist barrier" << I
+                        << '\n';);
+
+    // Don't initiate hoisting from GEPs (but they still can be hoisted if
+    // appearing as operands in hoisted instructions).
+    if (isa<GetElementPtrInst>(&I))
+      continue;
+
+    // Load and non-load instructions are collected separately.
+    if (Loads != isa<LoadInst>(I))
+      continue;
+
+    // Move loads and stores only if they depend on a memory access in some
+    // other block.
+    if (I.mayReadOrWriteMemory() && !MD->getDependency(&I).isNonLocal())
+      continue;
+
+    if (auto *LI = dyn_cast<LoadInst>(&I))
+      Candidates.emplace_back(VN.lookupOrAdd(LI->getPointerOperand()), &I);
+    else if (auto *SI = dyn_cast<StoreInst>(&I))
+      Candidates.emplace_back(VN.lookupOrAdd(SI->getPointerOperand()),
+                              VN.lookupOrAdd(SI->getValueOperand()), &I);
+    else
+      Candidates.emplace_back(VN.lookupOrAdd(&I), &I);
+  }
+}
+
+static void findMatchingPairs(
+    std::vector<HoistCandidate> &ThenC, std::vector<HoistCandidate> &ElseC,
+    SmallVectorImpl<std::pair<Instruction *, Instruction *>> &Match) {
+  auto Order = [](const HoistCandidate &A, const HoistCandidate &B) {
+    return A.VN < B.VN;
+  };
+  llvm::sort(ThenC, Order);
+  llvm::sort(ElseC, Order);
+  for (auto ThenI = ThenC.begin(), ThenE = ThenC.end(), ElseI = ElseC.begin(),
+            ElseE = ElseC.end();
+       ThenI != ThenE && ElseI != ElseE;
+       /* empty */) {
+    if (ThenI->VN < ElseI->VN) {
+      LLVM_DEBUG(dbgs() << "Simple GVNHoist: Skipping VN " << ThenI->VN << " "
+                        << *ThenI->Inst << '\n');
+      ++ThenI;
+    } else if (ElseI->VN < ThenI->VN) {
+      LLVM_DEBUG(dbgs() << "Simple GVNHoist: Skipping VN " << ElseI->VN << " "
+                        << *ElseI->Inst << '\n');
+      ++ElseI;
+    } else {
+      LLVM_DEBUG(dbgs() << "Simple GVNHoist: Found a matching pair:"
+                        << "\nSimple GVNHoist:   " << *ThenI->Inst
+                        << "\nSimple GVNHoist:   " << *ElseI->Inst << '\n');
+      Match.emplace_back(ThenI->Inst, ElseI->Inst);
+      ++ThenI;
+      ++ElseI;
+    }
+  }
+}
+
+void GVN::replaceInstruction(Instruction *I, Instruction *Repl) {
+  Repl->andIRFlags(I);
+
+  if (auto *LI = dyn_cast<LoadInst>(Repl))
+    LI->setAlignment(std::min(LI->getAlign(), cast<LoadInst>(I)->getAlign()));
+  else if (auto *SI = dyn_cast<StoreInst>(Repl))
+    SI->setAlignment(std::min(SI->getAlign(), cast<StoreInst>(I)->getAlign()));
+  else if (auto *AI = dyn_cast<AllocaInst>(Repl))
+    AI->setAlignment(std::max(AI->getAlign(), cast<AllocaInst>(I)->getAlign()));
+
+  combineMetadata(Repl, I,
+                  {LLVMContext::MD_access_group, LLVMContext::MD_alias_scope,
+                   LLVMContext::MD_fpmath, LLVMContext::MD_invariant_group,
+                   LLVMContext::MD_invariant_load, LLVMContext::MD_noalias,
+                   LLVMContext::MD_range, LLVMContext::MD_tbaa},
+                  true);
+
+  I->replaceAllUsesWith(Repl);
+  MD->invalidateCachedPointerInfo(I);
+  markInstructionForDeletion(I);
+}
+
+void GVN::eraseInstruction(Instruction *I) {
+  salvageKnowledge(I, AC);
+  salvageDebugInfo(*I);
+  if (MD)
+    MD->removeInstruction(I);
+  if (MSSAU)
+    MSSAU->removeMemoryAccess(I);
+  LLVM_DEBUG(verifyRemoved(I));
+  ICF->removeInstruction(I);
+  I->eraseFromParent();
+}
+
+bool GVN::hoistPair(BasicBlock *DestBB, BasicBlock *ThenBB, BasicBlock *ElseBB,
+                    Instruction *ThenI, Instruction *ElseI) {
+  // If one of the instructions is (already) in a dominating block, replace all
+  // users of the other one with it.
+  if (ThenI->getParent() != ThenBB) {
+    if (ElseI->getParent() == ElseBB) {
+      replaceInstruction(ElseI, ThenI);
+      return true;
+    }
+    return false;
+  }
+
+  if (ElseI->getParent() != ElseBB) {
+    assert(ThenI->getParent() == ThenBB);
+    replaceInstruction(ThenI, ElseI);
+    return true;
+  }
+
+  // Hoist operands.
+  for (unsigned I = 0, N = ThenI->getNumOperands(); I < N; ++I) {
+    auto *ThenOp = dyn_cast<Instruction>(ThenI->getOperand(I));
+    auto *ElseOp = dyn_cast<Instruction>(ElseI->getOperand(I));
+    if (ThenOp == nullptr || ElseOp == nullptr) {
+      assert(ThenOp == nullptr && ElseOp == nullptr);
+      continue;
+    }
+    (void)hoistPair(DestBB, ThenBB, ElseBB, ThenOp, ElseOp);
+  }
+
+  // Remove the intruction from the memory dependence cache, as the cache might
+  // keep a reference to the old block.
+  MD->removeInstruction(ThenI);
+
+  // Hoist one of the instructions and replace all uses of the other with it.
+  ThenI->moveBefore(DestBB->getTerminator());
+  if (MSSAU) {
+    if (MemoryUseOrDef *MA = MSSAU->getMemorySSA()->getMemoryAccess(ThenI))
+      MSSAU->moveToPlace(MA, DestBB,
+                         MemorySSA::InsertionPlace::BeforeTerminator);
+  }
+  replaceInstruction(ElseI, ThenI);
+
+  return true;
+}
+
+// Perform trivial hoisting of values from two blocks to their common
+// predecessor.
+std::pair<bool, bool> GVN::performHoist(Function &F) {
+  LLVM_DEBUG(dbgs() << "Simple GVNHoist: running on function " << F.getName()
+                    << '\n';);
+  bool RunAgain = false;
+  bool HoistedAny = false;
+  for (BasicBlock *BB : depth_first(&F.getEntryBlock())) {
+    // Check we have a block of the desired shape.
+    LLVM_DEBUG(dbgs() << "Simple GVNHoist: looking at block " << BB->getName()
+                      << '\n');
+    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;
+
+    // Collect pairs of instructions from each block with matching value
+    // numbers. Handle load instructions separately as they don't have their own
+    // value number (they reuse the value number of the address operand.)
+    std::vector<HoistCandidate> ThenCandidates, ElseCandidates;
+    collectHoistCandidates(MD, VN, Then, ThenCandidates, /* Loads = */ false);
+    collectHoistCandidates(MD, VN, Else, ElseCandidates, /* Loads = */ false);
+
+    SmallVector<std::pair<Instruction *, Instruction *>, 8> Match;
+    findMatchingPairs(ThenCandidates, ElseCandidates, Match);
+
+    ThenCandidates.clear();
+    ElseCandidates.clear();
+    collectHoistCandidates(MD, VN, Then, ThenCandidates, /* Loads = */ true);
+    collectHoistCandidates(MD, VN, Else, ElseCandidates, /* Loads = */ true);
+    findMatchingPairs(ThenCandidates, ElseCandidates, Match);
+
+    // Hoist all pairs.
+    for (const auto &P : Match) {
+      if (hoistPair(BB, Then, Else, P.first, P.second)) {
+        HoistedAny = true;
+        // Hoisting these creates opportunities for more hoisting.
+        if (P.first->mayReadOrWriteMemory() || isHoistBarrier(*P.first))
+          RunAgain = true;
+      }
+    }
+
+    // Remove dead instructions.
+    for (auto *I : InstrsToErase) {
+      assert((I->getParent() == Then || I->getParent() == Else) &&
+             "Removing instruction from the wrong block");
+      LLVM_DEBUG(dbgs() << "Simple GVNHoist: remove " << *I << '\n');
+      eraseInstruction(I);
+    }
+    InstrsToErase.clear();
+  }
+
+  return {HoistedAny, RunAgain};
+}
 
 /// Split the critical edge connecting the given two blocks, and return
 /// the block inserted to the critical edge.
 BasicBlock *GVN::splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ) {
   // GVN does not require loop-simplify, do not try to preserve it if it is not
   // possible.
   BasicBlock *BB = SplitCriticalEdge(
       Pred, Succ,

llvm/test/Analysis/TypeBasedAliasAnalysis/gvn-nonlocal-type-mismatch.ll

-; RUN: opt -tbaa -basic-aa -gvn -S < %s | FileCheck %s
+; RUN: opt -tbaa -basic-aa -gvn -enable-simple-gvnhoist=false -S < %s | FileCheck %s
 
 target datalayout = "e-p:64:64:64"
 
 ; GVN should ignore the store to p1 to see that the load from p is
 ; fully redundant.
 
 ; CHECK: @yes
 ; CHECK: if.then:

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

-; RUN: opt < %s -gvn -S | FileCheck %s
-; RUN: opt < %s -passes="gvn<load-pre>" -S | FileCheck %s
+; RUN: opt < %s -gvn -enable-simple-gvnhoist=false -S | FileCheck %s
+; RUN: opt < %s -passes="gvn<load-pre>" -enable-simple-gvnhoist=false -S | FileCheck %s
+; RUN: opt < %s -passes="gvn<load-pre>" -S | FileCheck %s -check-prefix=CHECK-HOIST
 
 target datalayout = "e-p:32:32:32-i1:8:32-i8:8:32-i16:16:32-i32:32:32-i64:32:32-f32:32:32-f64:32:32-v64:64:64-v128:128:128-a0:0:32-n32"
 
 @p = external global i32
 
 define i32 @test(i32 %n) nounwind {
 ; CHECK-LABEL: @test(
 entry:
   br label %for.cond
 
-; loads aligned greater than the memory should not be moved past conditionals
+; loads aligned greater than the memory should not be moved past conditionals ...
 ; CHECK-NOT: load
 ; CHECK: br i1
 
+; ... unless the same load is on both sides of the conditional.
+; CHECK-HOIST: load
+; CHECK-HOIST: br i1
 for.cond:
   %i.0 = phi i32 [ 0, %entry ], [ %indvar.next, %for.inc ]
   %cmp = icmp slt i32 %i.0, %n
   br i1 %cmp, label %for.body, label %for.cond.for.end_crit_edge
 
 for.cond.for.end_crit_edge:
 ; ...but PRE can still move the load out of for.end to here.
 ; CHECK: for.cond.for.end_crit_edge:

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-gvnhoist=false -S | FileCheck %s
+; RUN: opt < %s -passes="gvn<pre>" -enable-pre=false -enable-simple-gvnhoist=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-gvnhoist=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-gvnhoist=false -S | FileCheck %s
+; RUN: opt < %s -passes="gvn<pre>" -enable-pre=false -enable-simple-gvnhoist=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-gvnhoist=false -S | FileCheck %s
+; RUN: opt < %s -aa-pipeline=basic-aa -passes="gvn<load-pre>" -enable-load-pre=false -enable-simple-gvnhoist=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-gvnhoist=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-gvnhoist=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: %add.1 = 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/PRE/pre-single-pred.ll

-; RUN: opt < %s -gvn -enable-load-pre -S | FileCheck %s
-; RUN: opt < %s -passes="gvn<load-pre>" -enable-load-pre=false -S | FileCheck %s
+; RUN: opt < %s -gvn -enable-load-pre -enable-simple-gvnhoist=false -S | FileCheck %s
+; RUN: opt < %s -passes="gvn<load-pre>" -enable-load-pre=false -enable-simple-gvnhoist=false -S | FileCheck %s
 ; This testcase assumed we'll PRE the load into %for.cond, but we don't actually
 ; verify that doing so is safe.  If there didn't _happen_ to be a load in
 ; %for.end, we would actually be lengthening the execution on some paths, and
 ; we were never actually checking that case.  Now we actually do perform some
 ; conservative checking to make sure we don't make paths longer, but we don't
 ; currently get this case, which we got lucky on previously.
 ;
 ; Now that that faulty assumption is corrected, test that we DON'T incorrectly

llvm/test/Transforms/GVN/PRE/volatile.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; Tests that check our handling of volatile instructions encountered
 ; when scanning for dependencies
-; RUN: opt -basic-aa -gvn -S < %s | FileCheck %s
+; RUN: opt -basic-aa -gvn --enable-simple-gvnhoist=false -S < %s | FileCheck %s
 
 ; Check that we can bypass a volatile load when searching
 ; for dependencies of a non-volatile load
 define i32 @test1(i32* nocapture %p, i32* nocapture %q) {
 ; CHECK-LABEL: @test1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP0:%.*]] = load volatile i32, i32* [[Q:%.*]], align 4
 ; CHECK-NEXT:    ret i32 0

llvm/test/Transforms/GVN/condprop.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt < %s -basic-aa -gvn -S | FileCheck %s
+; RUN: opt < %s -basic-aa -gvn --enable-simple-gvnhoist=false -S | FileCheck %s
 
 @a = external global i32    ; <i32*> [#uses=7]
 
 define i32 @test1() nounwind {
 ; CHECK-LABEL: @test1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* @a, align 4
 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i32 [[TMP0]], 4

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-gvnhoist=false -S | FileCheck %s
+; RUN: opt < %s -passes=gvn -enable-simple-gvnhoist=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-gvnhoist=false -S < %s | FileCheck %s
 
 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:%.*]]) ]

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

+; RUN: opt -S --passes=gvn %s | FileCheck %s
+
+; Basic hoisting
+define i32 @basic_hoisting(i32 %a, i32 %b, i32 %c) {
+entry:
+  %cmp = icmp sgt i32 %a, 0
+  br i1 %cmp, label %if.then, label %if.else
+
+if.then:
+  %mul = mul nsw i32 %b, %c
+  %add = add nsw i32 %a, %mul
+  br label %return
+
+if.else:
+  %sub = sub nsw i32 0, %a
+  %mul1 = mul nsw i32 %b, %c
+  %add2 = add nsw i32 %sub, %mul1
+  br label %return
+
+return:
+  %retval.0 = phi i32 [ %add, %if.then ], [ %add2, %if.else ]
+  ret i32 %retval.0
+}
+; CHECK-LABEL: @basic_hoisting
+; CHECK: entry:
+; CHECK:   %mul = mul nsw i32 %b, %c
+; CHECK: if.then:
+; CHECK:   %add = add nsw i32 %a, %mul
+; CHECK: if.else:
+; CHECK:   %add2 = add nsw i32 %sub, %mul
+
+; No reorder across volatile instructions (a bit too conservative).
+define i32 @no_reorder_accross_volatile(i32 %a, i32 %b, i32 %c, i32* %v) {
+entry:
+  %cmp = icmp sgt i32 %a, 0
+  br i1 %cmp, label %if.then, label %if.else
+
+if.then:
+  %0 = load volatile i32, i32* %v, align 4
+  %mul = mul nsw i32 %b, %c
+  %add = add nsw i32 %a, %mul
+  br label %return
+
+if.else:
+  %sub = sub nsw i32 0, %a
+  %mul1 = mul nsw i32 %b, %c
+  %add2 = add nsw i32 %sub, %mul1
+  br label %return
+
+return:
+  %retval.0 = phi i32 [ %add, %if.then ], [ %add2, %if.else ]
+  ret i32 %retval.0
+}
+; CHECK-LABEL: @no_reorder_accross_volatile
+; CHECK: entry:
+; CHECK-NOT: load
+; CHECK-NOT: add
+; CHECK-NOT: sub
+; CHECK-NOT: mul
+; CHECK: if.then:
+; CHECK: if.else:
+
+; Volatile operations themselves can be hoisted.
+define i32 @can_hoist_volatile(i32 %a, i32 %b, i32* %v) {
+entry:
+  %cmp = icmp sgt i32 %a, 0
+  br i1 %cmp, label %if.then, label %if.else
+
+if.then:
+  %0 = load volatile i32, i32* %v, align 4
+  %mul = mul nsw i32 %b, %0
+  %add = add nsw i32 %a, %mul
+  br label %return
+
+if.else:
+  %1 = load volatile i32, i32* %v, align 4
+  %sub = sub nsw i32 0, %a
+  %mul1 = mul nsw i32 %b, %1
+  %add2 = add nsw i32 %sub, %mul1
+  br label %return
+
+return:
+  %retval.0 = phi i32 [ %add, %if.then ], [ %add2, %if.else ]
+  ret i32 %retval.0
+}
+; CHECK-LABEL: @can_hoist_volatile
+; CHECK: entry:
+; CHECK:   %0 = load volatile i32, i32* %v, align 4
+; CHECK:   %mul = mul nsw i32 %b, %0
+; CHECK: if.then:
+; CHECK:   %add = add nsw i32 %a, %mul
+; CHECK: if.else:
+; CHECK:   %add2 = add nsw i32 %sub, %mul
+
+; Don't reorder across implicit control flow.
+define i32 @no_reorder_across_icf(i32 %a, i32 %b, i32 %c) {
+entry:
+  %cmp = icmp sgt i32 %a, 0
+  br i1 %cmp, label %if.then, label %if.else
+
+if.then:
+  %0 = call i32 @g()
+  %mul = mul nsw i32 %b, %c
+  %add = add nsw i32 %a, %mul
+  br label %return
+
+if.else:
+  %sub = sub nsw i32 0, %a
+  %mul1 = mul nsw i32 %b, %c
+  %add2 = add nsw i32 %sub, %mul1
+  br label %return
+
+return:
+  %retval.0 = phi i32 [ %add, %if.then ], [ %add2, %if.else ]
+  ret i32 %retval.0
+}
+
+declare i32 @g() readnone
+; CHECK-LABEL: @no_reorder_across_icf
+; CHECK-NOT: call
+; CHECK-NOT: add
+; CHECK-NOT: sub
+; CHECK-NOT: mul
+; CHECK: if.then:
+; CHECK: if.else:
+
+; Can hoist above some calls
+define i32 @can_reorder_across_calls(i32 %a, i32 %b, i32 %c) {
+entry:
+  %cmp = icmp sgt i32 %a, 0
+  br i1 %cmp, label %if.then, label %if.else
+
+if.then:
+  %0 = call i32 @h()
+  %mul = mul nsw i32 %b, %c
+  %add = add nsw i32 %a, %mul
+  br label %return
+
+if.else:
+  %sub = sub nsw i32 0, %a
+  %mul1 = mul nsw i32 %b, %c
+  %add2 = add nsw i32 %sub, %mul1
+  br label %return
+
+return:
+  %retval.0 = phi i32 [ %add, %if.then ], [ %add2, %if.else ]
+  ret i32 %retval.0
+}
+
+declare i32 @h() readnone nounwind willreturn
+; CHECK-LABEL: @can_reorder_across_calls
+; CHECK: entry:
+; CHECK:   %mul = mul nsw i32 %b, %c
+; CHECK: if.then:
+; CHECK:   %0 = call i32 @h()
+; CHECK:   %add = add nsw i32 %a, %mul
+; CHECK: if.else:
+; CHECK:   %add2 = add nsw i32 %sub, %mul
+
+; Some calls themselves can be hoisted and merged
+define i32 @can_hoist_calls(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp sgt i32 %a, 0
+  br i1 %cmp, label %if.then, label %if.else
+
+if.then:
+  %0 = call i32 @h()
+  %mul = mul nsw i32 %b, %0
+  %add = add nsw i32 %a, %mul
+  br label %return
+
+if.else:
+  %sub = sub nsw i32 0, %a
+  %1 = call i32 @h()
+  %mul1 = mul nsw i32 %b, %1
+  %add2 = add nsw i32 %sub, %mul1
+  br label %return
+
+return:
+  %retval.0 = phi i32 [ %add, %if.then ], [ %add2, %if.else ]
+  ret i32 %retval.0
+}
+; CHECK: @can_hoist_calls
+; CHECK: entry:
+; CHECK:   %0 = call i32 @h()
+; CHECK:   %mul = mul nsw i32 %b, %0
+; CHECK: if.then:
+; CHECK:   %add = add nsw i32 %a, %mul
+; CHECK: if.else:
+; CHECK:   %add2 = add nsw i32 %sub, %mul
+
+; Merge instruction attributes
+define i32 @merge_instr_attr(i32 %a, i32 %b, i32* %c) {
+entry:
+  %cmp = icmp sgt i32 %a, 0
+  br i1 %cmp, label %if.then, label %if.else
+
+if.then:
+  %0 = load i32, i32* %c, align 4
+  %mul = mul nsw i32 %b, %0
+  %add = add nsw i32 %a, %mul
+  br label %return
+
+if.else:
+  %sub = sub nsw i32 0, %a
+  %1 = load i32, i32* %c, align 8
+  %mul1 = mul i32 %b, %1
+  %add2 = add nsw i32 %sub, %mul1
+  br label %return
+
+return:
+  %retval.0 = phi i32 [ %add, %if.then ], [ %add2, %if.else ]
+  ret i32 %retval.0
+}
+
+; CHECK-LABEL: @merge_instr_attr
+; CHECK: entry:
+; Merged alignment is the minimum of the incoming ones.
+; CHECK:   %0 = load i32, i32* %c, align 4
+; The mul loses the `nsw` flag.
+; CHECK:   %mul = mul i32 %b, %0
+; CHECK:   br i1 %cmp, label %if.then, label %if.else
+; CHECK: if.then:
+; CHECK:   %add = add nsw i32 %a, %mul
+; CHECK: if.else:
+; CHECK:   %add2 = add nsw i32 %sub, %mul
+
+; Do not merge loads of different sizes/types.
+define i32 @load_size_mismatch(i32 %a, i32 %b, i32* %c) {
+entry:
+  %cmp = icmp sgt i32 %a, 0
+  br i1 %cmp, label %if.then, label %if.else
+
+if.then:
+  %0 = load i32, i32* %c, align 4
+  %mul = mul nsw i32 %b, %0
+  %add = add nsw i32 %a, %mul
+  br label %return
+
+if.else:
+  %sub = sub nsw i32 0, %a
+  %1 = bitcast i32* %c to i16*
+  %2 = load i16, i16* %1, align 4
+  %3 = zext i16 %2 to i32
+  %mul1 = mul nsw i32 %b, %3
+  %add2 = add nsw i32 %sub, %mul1
+  br label %return
+
+return:
+  %retval.0 = phi i32 [ %add, %if.then ], [ %add2, %if.else ]
+  ret i32 %retval.0
+}
+; CHECK-LABEL: @load_size_mismatch
+; CHECK: entry:
+; CHECK-NOT: load
+; CHECK: if.then:
+; CHECK: load
+; CHECK: if.else:
+; CHECK: load
+
+; Don't reorder loads/stores if they alias.
+define i32 @aliasing_load_store(i32 %a, i32 %b, i32* %c, i32* %d) {
+entry:
+  %cmp = icmp sgt i32 %a, 0
+  br i1 %cmp, label %if.then, label %if.else
+
+if.then:
+  %0 = load i32, i32* %c, align 4
+  %mul = mul nsw i32 %b, %0
+  store i32 0, i32* %d, align 4
+  %add = add nsw i32 %a, %mul
+  br label %return
+
+if.else:
+  %sub = sub nsw i32 0, %a
+  %1 = bitcast i32* %c to i16*
+  %2 = load i16, i16* %1, align 4
+  %3 = zext i16 %2 to i32
+  %mul1 = mul nsw i32 %b, %3
+  store i32 0, i32* %d, align 4
+  %add2 = add nsw i32 %sub, %mul1
+  br label %return
+
+return:
+  %retval.0 = phi i32 [ %add, %if.then ], [ %add2, %if.else ]
+  ret i32 %retval.0
+}
+; CHECK-LABEL: @aliasing_load_store
+; CHECK: entry:
+; CHECK-NOT: load
+; CHECK-NOT: store
+; CHECK: if.then:
+; CHECK: load
+; CHECK: store
+; CHECK: if.else:
+; CHECK: load
+; CHECK: store
+
+; Can reorder non-aliasing loads/stores.
+define i32 @non_aliasing_load_store(i32 %a, i32 %b, i32* %ca, i32* %cb, i32* %d) {
+entry:
+  %cmp = icmp sgt i32 %a, 0
+  br i1 %cmp, label %if.then, label %if.else
+
+if.then:
+  %0 = load i32, i32* %ca, align 4, !tbaa !3
+  %mul = mul nsw i32 %b, %0
+  store i32 0, i32* %d, align 4, !tbaa !4
+  %add = add nsw i32 %a, %mul
+  br label %return
+
+if.else:
+  %sub = sub nsw i32 0, %a
+  %1 = load i32, i32* %cb, align 4, !tbaa !3
+  %mul1 = mul nsw i32 %b, %1
+  store i32 0, i32* %d, align 4, !tbaa !4
+  %add2 = add nsw i32 %sub, %mul1
+  br label %return
+
+return:
+  %retval.0 = phi i32 [ %add, %if.then ], [ %add2, %if.else ]
+  ret i32 %retval.0
+}
+
+!0 = !{!"Simple TBAA"}
+!1 = !{!"int", !0, i64 0}
+!2 = !{!"S", !1, i64 0, !1, i64 4}
+!3 = !{!2, !1, i64 0}
+!4 = !{!2, !1, i64 4}
+
+; CHECK-LABEL: @non_aliasing_load_store
+; CHECK: entry:
+; CHECK:  store i32 0, i32* %d, align 4, !tbaa
+; CHECK: if.then:
+; CHECK: load
+; CHECK: if.else:
+; CHECK: load

llvm/test/Transforms/GVNHoist/hoist-inline.ll

 ; RUN: opt -S -O2 -enable-gvn-hoist < %s | FileCheck %s
 
 ; Check that the inlined loads are hoisted.
 ; CHECK-LABEL: define i32 @fun(
 ; CHECK-LABEL: entry:
 ; CHECK: load i32, i32* @A
-; CHECK: if.then:
 
 @A = external global i32
 @B = external global i32
 @C = external global i32
 
 define i32 @loadA() {
    %a = load i32, i32* @A
    ret i32 %a

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-gvnhoist=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/InstMerge/st_sink_bugfix_22613.ll

 ; ModuleID = 'bug.c'
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
-; RUN: opt -O2 -S < %s | FileCheck %s
+; RUN: opt -O2 -S --enable-simple-gvnhoist=false < %s | FileCheck %s
+; RUN: opt -O2 -S                                < %s | FileCheck %s --check-prefix=CHECK-HOIST
 
 ; CHECK-LABEL: main
 ; CHECK: if.end
 ; CHECK: store
 ; CHECK: memset
 ; CHECK: if.then
+; CHECK: load
 ; CHECK: store
 ; CHECK: memset
 
+; CHECK-HOIST-LABEL: main
+; CHECK-HOIST: entry:
+; CHECK-HOIST: store
+; CHECK-HOIST: if.end
+; CHECK-HOIST: memset
+; CHECK-HOIST: if.then
+; CHECK-HOIST: load
+; CHECK-HOIST: memset
 @d = common global i32 0, align 4
 @b = common global i32 0, align 4
 @f = common global [1 x [3 x i8]] zeroinitializer, align 1
 @e = common global i32 0, align 4
 @c = common global i32 0, align 4
 @a = common global i32 0, align 4
 
 ; Function Attrs: nounwind uwtable