Use alias analysis to check for real interference in cascade comparison

[christylee]

Summary

Passing in AliasAnalysis to MergeICmps, we can check for real interference using alias analysis when some other work is done in a comparison block.

[trentxintong]

This looks good to me. I will let @courbet to have the final say here.

[christylee]

Friendly ping @courbet :)

[courbet]

Thanks for the patch Christy !

lib/Transforms/Scalar/MergeICmps.cpp

200

What about instructions that do not write to memory but may throw ?

test/Transforms/MergeICmps/X86/alias-merge-blocks.ll

11

It's not clear what "this call" refers to.

[christylee]

For instructions that may have side effects, check that the instruction is a simple load or simple store before checking for alias. For things like function calls, we would have to check that they don't throw and have no read/write to memory. The function calls are potentially nested as well, it's probably better to just bail on those cases.

[christylee]

Removed clang-format changes unrelated to this patch.

[lebedev.ri]

test/Transforms/MergeICmps/X86/alias-merge-blocks.ll

2

Would be good to commit the test with current check-lines, so the diff is visible in the review.

[christylee]

test/Transforms/MergeICmps/X86/alias-merge-blocks.ll

2

Hi @lebedev.ri ! Sorry I'm new to LLVM, what do you mean by "check-lines"?

[lebedev.ri]

test/Transforms/MergeICmps/X86/alias-merge-blocks.ll

2

In other words, i was suggesting to commit this test file (with the correct output from
utils/update_test_checks.py), so this differential would then show
how the code change affects the test.

check-lines - the lines with prefixes specified in --check-prefix= of FileCheck, in this case, ; X86

[christylee]

test/Transforms/MergeICmps/X86/alias-merge-blocks.ll

2

Is this what you mean, @lebedev.ri ?

[courbet]

lib/Transforms/Scalar/MergeICmps.cpp

202

add a comment: "// Disallow stores that might alias the BCE operands"

test/Transforms/MergeICmps/X86/alias-merge-blocks.ll

2

I think what Roman means is: create another diff with just this file in it. Then the current diff will show what your change does.

[christylee]

Addressed @courbet comment

[christylee]

Addressed @lebedev.ri 's comment and added dependent child diff to show original check-lines.

[• usamavarikkottil]

This comment was removed by • usamavarikkottil.

[lebedev.ri]

In D51550#1233590, @christylee wrote:

Addressed @lebedev.ri 's comment and added dependent child diff to show original check-lines.

This is slightly backwards.
That one needs to be the parent differential, and this differential needs to be based on that one,
and show how the check lines are changed by this diff.

[christylee]

Fixed diff dependencies.

[lebedev.ri]

In D51550#1233741, @christylee wrote:

Fixed diff dependencies.

Phabricator is dumb, it only shows the patch you have uploaded, it does not diff anything.
So you need to manually generate this diff to be \as compared to D52044'.
In other words, this differential should not be adding the alias-merge-blocks.ll,
it should only show how the check-lines change in it.

[lebedev.ri]

test/Transforms/MergeICmps/X86/alias-merge-blocks.ll

2

This current revision is what i meant :) (other than -U99999)

[christylee]

Going back to previous revision to include the test in this revision.

[christylee]

@courbet , @lebedev.ri , I'm trying to commit the patch by first running "arc patch D51550", but it keeps saying unable to apply patch because llvm/trunk/test/Transforms/MergeICmps/X86/alias-merge-blocks.ll does not exists in index. How should I go about this?

(master)$ llvm-arc patch D51550
 INFO  Base commit is not in local repository; trying to fetch.
Created and checked out branch arcpatch-D51550.
 INFO  Base commit is not in local repository; trying to fetch.
Checking patch llvm/trunk/test/Transforms/MergeICmps/X86/alias-merge-blocks.ll...
error: llvm/trunk/test/Transforms/MergeICmps/X86/alias-merge-blocks.ll: does not exist in index

 Patch Failed!
Usage Exception: Unable to apply patch!

[christylee]

The changes were landed in D52433

lib/Transforms/Scalar/MergeICmps.cpp

 //  - There are less jumps, and therefore less opportunities for mispredictions
 //    and I-cache misses.
 //  - Code size is smaller, both because jumps are removed and because the
 //    encoding of a 2*n byte compare is smaller than that of two n-byte
 //    compares.
 
 //===----------------------------------------------------------------------===//
 
-#include <algorithm>
-#include <numeric>
-#include <utility>
-#include <vector>
 #include "llvm/Analysis/Loads.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/Pass.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Utils/BuildLibCalls.h"
+#include <algorithm>
+#include <numeric>
+#include <utility>
+#include <vector>
 
 using namespace llvm;
 
 namespace {
 
 #define DEBUG_TYPE "mergeicmps"
 
+// Returns true if the instruction is a simple load or a simple store
+static bool isSimpleLoadOrStore(const Instruction *I) {
+  if (const LoadInst *LI = dyn_cast<LoadInst>(I))
+    return LI->isSimple();
+  if (const StoreInst *SI = dyn_cast<StoreInst>(I))
+    return SI->isSimple();
+  return false;
+}
+
 // A BCE atom.
 struct BCEAtom {
   BCEAtom() : GEP(nullptr), LoadI(nullptr), Offset() {}
 
   const Value *Base() const { return GEP ? GEP->getPointerOperand() : nullptr; }
 
   bool operator<(const BCEAtom &O) const {
     assert(Base() && "invalid atom");

 // doesOtherWork() returns true. Under some conditions, the block can be
 // split into the atom comparison part and the "other work" part
 // (see canSplit()).
 // Note: the terminology is misleading: the comparison is symmetric, so there
 // is no real {l/r}hs. What we want though is to have the same base on the
 // left (resp. right), so that we can detect consecutive loads. To ensure this
 // we put the smallest atom on the left.
 class BCECmpBlock {
- public:
   BCECmpBlock() {}
 
   BCECmpBlock(BCEAtom L, BCEAtom R, int SizeBits)
       : Lhs_(L), Rhs_(R), SizeBits_(SizeBits) {
-    if (Rhs_ < Lhs_) std::swap(Rhs_, Lhs_);
+    if (Rhs_ < Lhs_)
+      std::swap(Rhs_, Lhs_);
   }
 
   bool IsValid() const {
     return Lhs_.Base() != nullptr && Rhs_.Base() != nullptr;
   }
 
   // Assert the block is consistent: If valid, it should also have
   // non-null members besides Lhs_ and Rhs_.
public:
   const BCEAtom &Rhs() const { return Rhs_; }
   int SizeBits() const { return SizeBits_; }
 
   // Returns true if the block does other works besides comparison.
   bool doesOtherWork() const;
 
   // Returns true if the non-BCE-cmp instructions can be separated from BCE-cmp
   // instructions in the block.
-  bool canSplit() const;
+  bool canSplit(AliasAnalysis *AA) const;
 
   // Return true if this all the relevant instructions in the BCE-cmp-block can
   // be sunk below this instruction. By doing this, we know we can separate the
   // BCE-cmp-block instructions from the non-BCE-cmp-block instructions in the
   // block.
-  bool canSinkBCECmpInst(const Instruction *, DenseSet<Instruction *> &) const;
+  bool canSinkBCECmpInst(const Instruction *, DenseSet<Instruction *> &,
+                         AliasAnalysis *AA) const;
 
   // We can separate the BCE-cmp-block instructions and the non-BCE-cmp-block
   // instructions. Split the old block and move all non-BCE-cmp-insts into the
   // new parent block.
-  void split(BasicBlock *NewParent) const;
+  void split(BasicBlock *NewParent, AliasAnalysis *AA) const;
 
   // The basic block where this comparison happens.
   BasicBlock *BB = nullptr;
   // The ICMP for this comparison.
   ICmpInst *CmpI = nullptr;
   // The terminating branch.
   BranchInst *BranchI = nullptr;
   // The block requires splitting.
   bool RequireSplit = false;
 
 private:
   BCEAtom Lhs_;
   BCEAtom Rhs_;
   int SizeBits_ = 0;
 };
 
 bool BCECmpBlock::canSinkBCECmpInst(const Instruction *Inst,
-                                    DenseSet<Instruction *> &BlockInsts) const {
+                                    DenseSet<Instruction *> &BlockInsts,
+                                    AliasAnalysis *AA) const {
   // If this instruction has side effects and its in middle of the BCE cmp block
   // instructions, then bail for now.
-  // TODO: use alias analysis to tell whether there is real interference.
-  if (Inst->mayHaveSideEffects())
+  if (Inst->mayHaveSideEffects()) {
+    // Bail if this is not a simple load or store
+    if (!isSimpleLoadOrStore(Inst))
+      return false;
+
+    MemoryLocation LLoc = MemoryLocation::get(Lhs_.LoadI);
+    MemoryLocation RLoc = MemoryLocation::get(Rhs_.LoadI);
+    if (isModSet(AA->getModRefInfo(Inst, LLoc)) ||
+        isModSet(AA->getModRefInfo(Inst, RLoc)))
       return false;
+  }
   // Make sure this instruction does not use any of the BCE cmp block
   // instructions as operand.
   for (auto BI : BlockInsts) {
     if (is_contained(Inst->operands(), BI))
       return false;
   }
   return true;
 }
 
-void BCECmpBlock::split(BasicBlock *NewParent) const {
+void BCECmpBlock::split(BasicBlock *NewParent, AliasAnalysis *AA) const {
   DenseSet<Instruction *> BlockInsts(
       {Lhs_.GEP, Rhs_.GEP, Lhs_.LoadI, Rhs_.LoadI, CmpI, BranchI});
   llvm::SmallVector<Instruction *, 4> OtherInsts;
   for (Instruction &Inst : *BB) {
     if (BlockInsts.count(&Inst))
       continue;
-    assert(canSinkBCECmpInst(&Inst, BlockInsts) && "Split unsplittable block");
+    assert(canSinkBCECmpInst(&Inst, BlockInsts, AA) &&
+           "Split unsplittable block");
     // This is a non-BCE-cmp-block instruction. And it can be separated
     // from the BCE-cmp-block instruction.
     OtherInsts.push_back(&Inst);
   }
 
   // Do the actual spliting.
   for (Instruction *Inst : reverse(OtherInsts)) {
     Inst->moveBefore(&*NewParent->begin());
   }
 }
 
-bool BCECmpBlock::canSplit() const {
+bool BCECmpBlock::canSplit(AliasAnalysis *AA) const {
   DenseSet<Instruction *> BlockInsts(
       {Lhs_.GEP, Rhs_.GEP, Lhs_.LoadI, Rhs_.LoadI, CmpI, BranchI});
   for (Instruction &Inst : *BB) {
     if (!BlockInsts.count(&Inst)) {
-      if (!canSinkBCECmpInst(&Inst, BlockInsts))
+      if (!canSinkBCECmpInst(&Inst, BlockInsts, AA))
         return false;
     }
   }
   return true;
 }
 
 bool BCECmpBlock::doesOtherWork() const {
   AssertConsistent();
if (!CmpI->hasOneUse()) {
     LLVM_DEBUG(dbgs() << "cmp has several uses\n");
     return {};
   }
   if (CmpI->getPredicate() == ExpectedPredicate) {
     LLVM_DEBUG(dbgs() << "cmp "
                       << (ExpectedPredicate == ICmpInst::ICMP_EQ ? "eq" : "ne")
                       << "\n");
     auto Lhs = visitICmpLoadOperand(CmpI->getOperand(0));
-    if (!Lhs.Base()) return {};
+    if (!Lhs.Base())
+      return {};
     auto Rhs = visitICmpLoadOperand(CmpI->getOperand(1));
-    if (!Rhs.Base()) return {};
+    if (!Rhs.Base())
+      return {};
     return BCECmpBlock(std::move(Lhs), std::move(Rhs),
                        CmpI->getOperand(0)->getType()->getScalarSizeInBits());
   }
   return {};
 }
 
 // Visit the given comparison block. If this is a comparison between two valid
 // BCE atoms, returns the comparison.
 BCECmpBlock visitCmpBlock(Value *const Val, BasicBlock *const Block,
                           const BasicBlock *const PhiBlock) {
-  if (Block->empty()) return {};
+  if (Block->empty())
+    return {};
   auto *const BranchI = dyn_cast<BranchInst>(Block->getTerminator());
-  if (!BranchI) return {};
+  if (!BranchI)
+    return {};
   LLVM_DEBUG(dbgs() << "branch\n");
   if (BranchI->isUnconditional()) {
     // In this case, we expect an incoming value which is the result of the
     // comparison. This is the last link in the chain of comparisons (note
     // that this does not mean that this is the last incoming value, blocks
     // can be reordered).
     auto *const CmpI = dyn_cast<ICmpInst>(Val);
-    if (!CmpI) return {};
+    if (!CmpI)
+      return {};
     LLVM_DEBUG(dbgs() << "icmp\n");
     auto Result = visitICmp(CmpI, ICmpInst::ICMP_EQ);
     Result.CmpI = CmpI;
     Result.BranchI = BranchI;
     return Result;
   } else {
     // In this case, we expect a constant incoming value (the comparison is
     // chained).
     const auto *const Const = dyn_cast<ConstantInt>(Val);
     LLVM_DEBUG(dbgs() << "const\n");
-    if (!Const->isZero()) return {};
+    if (!Const->isZero())
+      return {};
     LLVM_DEBUG(dbgs() << "false\n");
     auto *const CmpI = dyn_cast<ICmpInst>(BranchI->getCondition());
-    if (!CmpI) return {};
+    if (!CmpI)
+      return {};
     LLVM_DEBUG(dbgs() << "icmp\n");
     assert(BranchI->getNumSuccessors() == 2 && "expecting a cond branch");
     BasicBlock *const FalseBlock = BranchI->getSuccessor(1);
-    auto Result = visitICmp(
-        CmpI, FalseBlock == PhiBlock ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE);
+    auto Result = visitICmp(CmpI, FalseBlock == PhiBlock ? ICmpInst::ICMP_EQ
+                                                         : ICmpInst::ICMP_NE);
     Result.CmpI = CmpI;
     Result.BranchI = BranchI;
     return Result;
   }
   return {};
 }
 
 static inline void enqueueBlock(std::vector<BCECmpBlock> &Comparisons,
                                 BCECmpBlock &Comparison) {
   LLVM_DEBUG(dbgs() << "Block '" << Comparison.BB->getName()
                     << "': Found cmp of " << Comparison.SizeBits()
                     << " bits between " << Comparison.Lhs().Base() << " + "
                     << Comparison.Lhs().Offset << " and "
                     << Comparison.Rhs().Base() << " + "
                     << Comparison.Rhs().Offset << "\n");
   LLVM_DEBUG(dbgs() << "\n");
   Comparisons.push_back(Comparison);
 }
 
 // A chain of comparisons.
 class BCECmpChain {
- public:
-  BCECmpChain(const std::vector<BasicBlock *> &Blocks, PHINode &Phi);
+  BCECmpChain(const std::vector<BasicBlock *> &Blocks, PHINode &Phi,
+              AliasAnalysis *AA);
 
   int size() const { return Comparisons_.size(); }
 
 #ifdef MERGEICMPS_DOT_ON
   void dump() const;
-#endif  // MERGEICMPS_DOT_ON
+#endif // MERGEICMPS_DOT_ON
 
-  bool simplify(const TargetLibraryInfo *const TLI);
+  bool simplify(const TargetLibraryInfo *const TLI, AliasAnalysis *AA);
 
- private:
   static bool IsContiguous(const BCECmpBlock &First,
                            const BCECmpBlock &Second) {
     return First.Lhs().Base() == Second.Lhs().Base() &&
            First.Rhs().Base() == Second.Rhs().Base() &&
            First.Lhs().Offset + First.SizeBits() / 8 == Second.Lhs().Offset &&
            First.Rhs().Offset + First.SizeBits() / 8 == Second.Rhs().Offset;
   }
 
   // Merges the given comparison blocks into one memcmp block and update
   // branches. Comparisons are assumed to be continguous. If NextBBInChain is
   // null, the merged block will link to the phi block.
   void mergeComparisons(ArrayRef<BCECmpBlock> Comparisons,
                         BasicBlock *const NextBBInChain, PHINode &Phi,
-                        const TargetLibraryInfo *const TLI);
+                        const TargetLibraryInfo *const TLI, AliasAnalysis *AA);
 
   PHINode &Phi_;
   std::vector<BCECmpBlock> Comparisons_;
   // The original entry block (before sorting);
   BasicBlock *EntryBlock_;
 };
 
-BCECmpChain::BCECmpChain(const std::vector<BasicBlock *> &Blocks, PHINode &Phi)
+BCECmpChain::BCECmpChain(const std::vector<BasicBlock *> &Blocks, PHINode &Phi,
+                         AliasAnalysis *AA)
     : Phi_(Phi) {
   assert(!Blocks.empty() && "a chain should have at least one block");
   // Now look inside blocks to check for BCE comparisons.
   std::vector<BCECmpBlock> Comparisons;
   for (size_t BlockIdx = 0; BlockIdx < Blocks.size(); ++BlockIdx) {
     BasicBlock *const Block = Blocks[BlockIdx];
     assert(Block && "invalid block");
     BCECmpBlock Comparison = visitCmpBlock(Phi.getIncomingValueForBlock(Block),
if (Comparison.doesOtherWork()) {
         // work.
         //
         // As once split, there will still be instructions before the BCE cmp
         // instructions that do other work in program order, i.e. within the
         // chain before sorting. Unless we can abort the chain at this point
         // and start anew.
         //
         // NOTE: we only handle block with single predecessor for now.
-        if (Comparison.canSplit()) {
+        if (Comparison.canSplit(AA)) {
           LLVM_DEBUG(dbgs()
                      << "Split initial block '" << Comparison.BB->getName()
                      << "' that does extra work besides compare\n");
           Comparison.RequireSplit = true;
           enqueueBlock(Comparisons, Comparison);
         } else {
           LLVM_DEBUG(dbgs()
                      << "ignoring initial block '" << Comparison.BB->getName()
if (Comparisons.empty()) {
     LLVM_DEBUG(dbgs() << "chain with no BCE basic blocks, no merge\n");
     return;
   }
   EntryBlock_ = Comparisons[0].BB;
   Comparisons_ = std::move(Comparisons);
 #ifdef MERGEICMPS_DOT_ON
   errs() << "BEFORE REORDERING:\n\n";
   dump();
-#endif  // MERGEICMPS_DOT_ON
+#endif // MERGEICMPS_DOT_ON
   // Reorder blocks by LHS. We can do that without changing the
   // semantics because we are only accessing dereferencable memory.
   llvm::sort(Comparisons_.begin(), Comparisons_.end(),
              [](const BCECmpBlock &a, const BCECmpBlock &b) {
                return a.Lhs() < b.Lhs();
              });
 #ifdef MERGEICMPS_DOT_ON
   errs() << "AFTER REORDERING:\n\n";
   dump();
-#endif  // MERGEICMPS_DOT_ON
+#endif // MERGEICMPS_DOT_ON
 }
 
 #ifdef MERGEICMPS_DOT_ON
 void BCECmpChain::dump() const {
   errs() << "digraph dag {\n";
   errs() << " graph [bgcolor=transparent];\n";
   errs() << " node [color=black,style=filled,fillcolor=lightyellow];\n";
   errs() << " edge [color=black];\n";
   for (size_t I = 0; I < Comparisons_.size(); ++I) {
     const auto &Comparison = Comparisons_[I];
     errs() << " \"" << I << "\" [label=\"%"
            << Comparison.Lhs().Base()->getName() << " + "
            << Comparison.Lhs().Offset << " == %"
            << Comparison.Rhs().Base()->getName() << " + "
            << Comparison.Rhs().Offset << " (" << (Comparison.SizeBits() / 8)
            << " bytes)\"];\n";
     const Value *const Val = Phi_.getIncomingValueForBlock(Comparison.BB);
-    if (I > 0) errs() << " \"" << (I - 1) << "\" -> \"" << I << "\";\n";
+    if (I > 0)
+      errs() << " \"" << (I - 1) << "\" -> \"" << I << "\";\n";
     errs() << " \"" << I << "\" -> \"Phi\" [label=\"" << *Val << "\"];\n";
   }
   errs() << " \"Phi\" [label=\"Phi\"];\n";
   errs() << "}\n\n";
 }
-#endif  // MERGEICMPS_DOT_ON
+#endif // MERGEICMPS_DOT_ON
 
-bool BCECmpChain::simplify(const TargetLibraryInfo *const TLI) {
+bool BCECmpChain::simplify(const TargetLibraryInfo *const TLI,
+                           AliasAnalysis *AA) {
   // First pass to check if there is at least one merge. If not, we don't do
   // anything and we keep analysis passes intact.
   {
     bool AtLeastOneMerged = false;
     for (size_t I = 1; I < Comparisons_.size(); ++I) {
       if (IsContiguous(Comparisons_[I - 1], Comparisons_[I])) {
         AtLeastOneMerged = true;
         break;
       }
     }
-    if (!AtLeastOneMerged) return false;
+    if (!AtLeastOneMerged)
+      return false;
   }
 
   // Remove phi references to comparison blocks, they will be rebuilt as we
   // merge the blocks.
   for (const auto &Comparison : Comparisons_) {
     Phi_.removeIncomingValue(Comparison.BB, false);
   }
 
bool BCECmpChain::simplify(const TargetLibraryInfo *const TLI,
   int NumMerged = 1;
   for (size_t I = 1; I < Comparisons_.size(); ++I) {
     if (IsContiguous(Comparisons_[I - 1], Comparisons_[I])) {
       ++NumMerged;
     } else {
       // Merge all previous comparisons and start a new merge block.
       mergeComparisons(
           makeArrayRef(Comparisons_).slice(I - NumMerged, NumMerged),
-          Comparisons_[I].BB, Phi_, TLI);
+          Comparisons_[I].BB, Phi_, TLI, AA);
       NumMerged = 1;
     }
   }
   mergeComparisons(makeArrayRef(Comparisons_)
                        .slice(Comparisons_.size() - NumMerged, NumMerged),
-                   nullptr, Phi_, TLI);
+                   nullptr, Phi_, TLI, AA);
 
   return true;
 }
 
 void BCECmpChain::mergeComparisons(ArrayRef<BCECmpBlock> Comparisons,
                                    BasicBlock *const NextBBInChain,
                                    PHINode &Phi,
-                                   const TargetLibraryInfo *const TLI) {
+                                   const TargetLibraryInfo *const TLI,
+                                   AliasAnalysis *AA) {
   assert(!Comparisons.empty());
   const auto &FirstComparison = *Comparisons.begin();
   BasicBlock *const BB = FirstComparison.BB;
   LLVMContext &Context = BB->getContext();
 
   if (Comparisons.size() >= 2) {
     // If there is one block that requires splitting, we do it now, i.e.
     // just before we know we will collapse the chain. The instructions
     // can be executed before any of the instructions in the chain.
     auto C = std::find_if(Comparisons.begin(), Comparisons.end(),
                           [](const BCECmpBlock &B) { return B.RequireSplit; });
     if (C != Comparisons.end())
-      C->split(EntryBlock_);
+      C->split(EntryBlock_, AA);
 
     LLVM_DEBUG(dbgs() << "Merging " << Comparisons.size() << " comparisons\n");
     const auto TotalSize =
         std::accumulate(Comparisons.begin(), Comparisons.end(), 0,
                         [](int Size, const BCECmpBlock &C) {
                           return Size + C.SizeBits();
                         }) /
         8;
 
     // Incoming edges do not need to be updated, and both GEPs are already
     // computing the right address, we just need to:
     //   - replace the two loads and the icmp with the memcmp
     //   - update the branch
     //   - update the incoming values in the phi.
     FirstComparison.BranchI->eraseFromParent();
     FirstComparison.CmpI->eraseFromParent();
     FirstComparison.Lhs().LoadI->eraseFromParent();
     FirstComparison.Rhs().LoadI->eraseFromParent();
 
     IRBuilder<> Builder(BB);
     const auto &DL = Phi.getModule()->getDataLayout();
-    Value *const MemCmpCall = emitMemCmp(
-        FirstComparison.Lhs().GEP, FirstComparison.Rhs().GEP,
+    Value *const MemCmpCall =
+        emitMemCmp(FirstComparison.Lhs().GEP, FirstComparison.Rhs().GEP,
                    ConstantInt::get(DL.getIntPtrType(Context), TotalSize),
                    Builder, DL, TLI);
     Value *const MemCmpIsZero = Builder.CreateICmpEQ(
         MemCmpCall, ConstantInt::get(Type::getInt32Ty(Context), 0));
 
     // Add a branch to the next basic block in the chain.
     if (NextBBInChain) {
       Builder.CreateCondBr(MemCmpIsZero, NextBBInChain, Phi.getParent());
       Phi.addIncoming(ConstantInt::getFalse(Context), BB);
     } else {
if (NextBBInChain) {
       } else {
         LLVM_DEBUG(dbgs() << "unconditional -> unconditional\n");
         Phi.addIncoming(FirstComparison.CmpI, BB);
       }
     }
   }
 }
 
-std::vector<BasicBlock *> getOrderedBlocks(PHINode &Phi,
-                                           BasicBlock *const LastBlock,
-                                           int NumBlocks) {
+std::vector<BasicBlock *>
+getOrderedBlocks(PHINode &Phi, BasicBlock *const LastBlock, int NumBlocks) {
   // Walk up from the last block to find other blocks.
   std::vector<BasicBlock *> Blocks(NumBlocks);
   assert(LastBlock && "invalid last block");
   BasicBlock *CurBlock = LastBlock;
   for (int BlockIndex = NumBlocks - 1; BlockIndex > 0; --BlockIndex) {
     if (CurBlock->hasAddressTaken()) {
       // Somebody is jumping to the block through an address, all bets are
       // off.
if (Phi.getBasicBlockIndex(SinglePredecessor) < 0) {
       return {};
     }
     CurBlock = SinglePredecessor;
   }
   Blocks[0] = CurBlock;
   return Blocks;
 }
 
-bool processPhi(PHINode &Phi, const TargetLibraryInfo *const TLI) {
+bool processPhi(PHINode &Phi, const TargetLibraryInfo *const TLI,
+                AliasAnalysis *AA) {
   LLVM_DEBUG(dbgs() << "processPhi()\n");
   if (Phi.getNumIncomingValues() <= 1) {
     LLVM_DEBUG(dbgs() << "skip: only one incoming value in phi\n");
     return false;
   }
   // We are looking for something that has the following structure:
   //   bb1 --eq--> bb2 --eq--> bb3 --eq--> bb4 --+
   //     \            \           \               \
   //      ne           ne          ne              \
   //       \            \           \               v
   //        +------------+-----------+----------> bb_phi
   //
   //  - The last basic block (bb4 here) must branch unconditionally to bb_phi.
   //    It's the only block that contributes a non-constant value to the Phi.
   //  - All other blocks (b1, b2, b3) must have exactly two successors, one of
   //    them being the phi block.
   //  - All intermediate blocks (bb2, bb3) must have only one predecessor.
   //  - Blocks cannot do other work besides the comparison, see doesOtherWork()
 
   // The blocks are not necessarily ordered in the phi, so we start from the
   // last block and reconstruct the order.
   BasicBlock *LastBlock = nullptr;
   for (unsigned I = 0; I < Phi.getNumIncomingValues(); ++I) {
-    if (isa<ConstantInt>(Phi.getIncomingValue(I))) continue;
+    if (isa<ConstantInt>(Phi.getIncomingValue(I)))
+      continue;
     if (LastBlock) {
       // There are several non-constant values.
       LLVM_DEBUG(dbgs() << "skip: several non-constant values\n");
       return false;
     }
     if (!isa<ICmpInst>(Phi.getIncomingValue(I)) ||
         cast<ICmpInst>(Phi.getIncomingValue(I))->getParent() !=
             Phi.getIncomingBlock(I)) {
bool processPhi(PHINode &Phi, const TargetLibraryInfo *const TLI,
   }
   if (LastBlock->getSingleSuccessor() != Phi.getParent()) {
     LLVM_DEBUG(dbgs() << "skip: last block non-phi successor\n");
     return false;
   }
 
   const auto Blocks =
       getOrderedBlocks(Phi, LastBlock, Phi.getNumIncomingValues());
-  if (Blocks.empty()) return false;
-  BCECmpChain CmpChain(Blocks, Phi);
+  if (Blocks.empty())
+    return false;
+  BCECmpChain CmpChain(Blocks, Phi, AA);
 
   if (CmpChain.size() < 2) {
     LLVM_DEBUG(dbgs() << "skip: only one compare block\n");
     return false;
   }
 
-  return CmpChain.simplify(TLI);
+  return CmpChain.simplify(TLI, AA);
 }
 
 class MergeICmps : public FunctionPass {
- public:
   static char ID;
 
   MergeICmps() : FunctionPass(ID) {
     initializeMergeICmpsPass(*PassRegistry::getPassRegistry());
   }
 
   bool runOnFunction(Function &F) override {
-    if (skipFunction(F)) return false;
+    if (skipFunction(F))
+      return false;
     const auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
     const auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
-    auto PA = runImpl(F, &TLI, &TTI);
+    AliasAnalysis *AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
+    auto PA = runImpl(F, &TLI, &TTI, AA);
     return !PA.areAllPreserved();
   }
 
- private:
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<TargetLibraryInfoWrapperPass>();
     AU.addRequired<TargetTransformInfoWrapperPass>();
+    AU.addRequired<AAResultsWrapperPass>();
   }
 
   PreservedAnalyses runImpl(Function &F, const TargetLibraryInfo *TLI,
-                            const TargetTransformInfo *TTI);
+                            const TargetTransformInfo *TTI, AliasAnalysis *AA);
 };
 
 PreservedAnalyses MergeICmps::runImpl(Function &F, const TargetLibraryInfo *TLI,
-                                      const TargetTransformInfo *TTI) {
+                                      const TargetTransformInfo *TTI,
+                                      AliasAnalysis *AA) {
   LLVM_DEBUG(dbgs() << "MergeICmpsPass: " << F.getName() << "\n");
 
   // We only try merging comparisons if the target wants to expand memcmp later.
   // The rationale is to avoid turning small chains into memcmp calls.
-  if (!TTI->enableMemCmpExpansion(true)) return PreservedAnalyses::all();
+  if (!TTI->enableMemCmpExpansion(true))
+    return PreservedAnalyses::all();
 
   // If we don't have memcmp avaiable we can't emit calls to it.
   if (!TLI->has(LibFunc_memcmp))
     return PreservedAnalyses::all();
 
   bool MadeChange = false;
 
   for (auto BBIt = ++F.begin(); BBIt != F.end(); ++BBIt) {
     // A Phi operation is always first in a basic block.
     if (auto *const Phi = dyn_cast<PHINode>(&*BBIt->begin()))
-      MadeChange |= processPhi(*Phi, TLI);
+      MadeChange |= processPhi(*Phi, TLI, AA);
   }
 
-  if (MadeChange) return PreservedAnalyses::none();
+  if (MadeChange)
+    return PreservedAnalyses::none();
   return PreservedAnalyses::all();
 }
 
-}  // namespace
+} // namespace
 
 char MergeICmps::ID = 0;
 INITIALIZE_PASS_BEGIN(MergeICmps, "mergeicmps",
                       "Merge contiguous icmps into a memcmp", false, false)
 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
 INITIALIZE_PASS_END(MergeICmps, "mergeicmps",
                     "Merge contiguous icmps into a memcmp", false, false)
 
 Pass *llvm::createMergeICmpsPass() { return new MergeICmps(); }

test/CodeGen/AArch64/O3-pipeline.ll

 ; CHECK-NEXT:       Loop Data Prefetch
 ; CHECK-NEXT:       Falkor HW Prefetch Fix
 ; CHECK-NEXT:       Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:       Module Verifier
 ; CHECK-NEXT:       Canonicalize natural loops
 ; CHECK-NEXT:       Loop Pass Manager
 ; CHECK-NEXT:         Induction Variable Users
 ; CHECK-NEXT:         Loop Strength Reduction
+; CHECK-NEXT:       Basic Alias Analysis (stateless AA impl)
+; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:       Merge contiguous icmps into a memcmp
 ; CHECK-NEXT:       Expand memcmp() to load/stores
 ; CHECK-NEXT:       Lower Garbage Collection Instructions
 ; CHECK-NEXT:       Shadow Stack GC Lowering
 ; CHECK-NEXT:       Remove unreachable blocks from the CFG
 ; CHECK-NEXT:       Dominator Tree Construction
 ; CHECK-NEXT:       Natural Loop Information
 ; CHECK-NEXT:       Branch Probability Analysis

test/CodeGen/Generic/llc-start-stop.ll

 ; Note: -verify-machineinstrs is used in order to make this test compatible with EXPENSIVE_CHECKS.
 ; RUN: llc < %s -debug-pass=Structure -stop-after=loop-reduce -verify-machineinstrs -o /dev/null 2>&1 \
 ; RUN:   | FileCheck %s -check-prefix=STOP-AFTER
 ; STOP-AFTER: -loop-reduce
 ; STOP-AFTER: Dominator Tree Construction
 ; STOP-AFTER: Loop Strength Reduction
 ; STOP-AFTER-NEXT: Verify generated machine code
 ; STOP-AFTER-NEXT: MIR Printing Pass
 
 ; RUN: llc < %s -debug-pass=Structure -stop-before=loop-reduce -o /dev/null 2>&1 | FileCheck %s -check-prefix=STOP-BEFORE
 ; STOP-BEFORE-NOT: -loop-reduce
 ; STOP-BEFORE: Dominator Tree Construction
 ; STOP-BEFORE-NOT: Loop Strength Reduction
 
 ; RUN: llc < %s -debug-pass=Structure -start-after=loop-reduce -o /dev/null 2>&1 | FileCheck %s -check-prefix=START-AFTER
-; START-AFTER: -machine-branch-prob -mergeicmps
+; START-AFTER: -aa -mergeicmps
 ; START-AFTER: FunctionPass Manager
-; START-AFTER-NEXT: Merge contiguous icmps into a memcmp
+; START-AFTER-NEXT: Dominator Tree Construction
 
 ; RUN: llc < %s -debug-pass=Structure -start-before=loop-reduce -o /dev/null 2>&1 | FileCheck %s -check-prefix=START-BEFORE
 ; START-BEFORE: -machine-branch-prob -domtree
 ; START-BEFORE: FunctionPass Manager
 ; START-BEFORE: Loop Strength Reduction
-; START-BEFORE-NEXT: Merge contiguous icmps into a memcmp
+; START-BEFORE-NEXT: Basic Alias Analysis (stateless AA impl)
 
 ; RUN: not llc < %s -start-before=nonexistent -o /dev/null 2>&1 | FileCheck %s -check-prefix=NONEXISTENT-START-BEFORE
 ; RUN: not llc < %s -stop-before=nonexistent -o /dev/null 2>&1 | FileCheck %s -check-prefix=NONEXISTENT-STOP-BEFORE
 ; RUN: not llc < %s -start-after=nonexistent -o /dev/null 2>&1 | FileCheck %s -check-prefix=NONEXISTENT-START-AFTER
 ; RUN: not llc < %s -stop-after=nonexistent -o /dev/null 2>&1 | FileCheck %s -check-prefix=NONEXISTENT-STOP-AFTER
 ; NONEXISTENT-START-BEFORE: "nonexistent" pass is not registered.
 ; NONEXISTENT-STOP-BEFORE: "nonexistent" pass is not registered.
 ; NONEXISTENT-START-AFTER: "nonexistent" pass is not registered.
 ; NONEXISTENT-STOP-AFTER: "nonexistent" pass is not registered.
 
 ; RUN: not llc < %s -start-before=loop-reduce -start-after=loop-reduce -o /dev/null 2>&1 | FileCheck %s -check-prefix=DOUBLE-START
 ; RUN: not llc < %s -stop-before=loop-reduce -stop-after=loop-reduce -o /dev/null 2>&1 | FileCheck %s -check-prefix=DOUBLE-STOP
 ; DOUBLE-START: start-before and start-after specified!
 ; DOUBLE-STOP: stop-before and stop-after specified!

test/CodeGen/X86/O3-pipeline.ll

 ; CHECK-NEXT:       Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:       Module Verifier
 ; CHECK-NEXT:       Natural Loop Information
 ; CHECK-NEXT:       Canonicalize natural loops
 ; CHECK-NEXT:       Scalar Evolution Analysis
 ; CHECK-NEXT:       Loop Pass Manager
 ; CHECK-NEXT:         Induction Variable Users
 ; CHECK-NEXT:         Loop Strength Reduction
+; CHECK-NEXT:       Basic Alias Analysis (stateless AA impl)
+; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:       Merge contiguous icmps into a memcmp
 ; CHECK-NEXT:       Expand memcmp() to load/stores
 ; CHECK-NEXT:       Lower Garbage Collection Instructions
 ; CHECK-NEXT:       Shadow Stack GC Lowering
 ; CHECK-NEXT:       Remove unreachable blocks from the CFG
 ; CHECK-NEXT:       Dominator Tree Construction
 ; CHECK-NEXT:       Natural Loop Information
 ; CHECK-NEXT:       Branch Probability Analysis

test/Transforms/MergeICmps/X86/alias-merge-blocks.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -mergeicmps -mtriple=x86_64-unknown-unknown -S | FileCheck %s --check-prefix=X86
+
+%"struct.std::pair" = type { i32, i32, i32, i32 }
+
+; We can split %entry and create a memcmp(16 bytes).
+define zeroext i1 @opeq1(
+; X86-LABEL: @opeq1(
+;
+; Make sure the store is moved to the beginning of the entry block.
+; X86:      entry:
+; X86-NEXT:    [[PTR:%.*]] = alloca i32
+; X86-NEXT:    store i32 42, i32* [[PTR]]
+; X86-NEXT:    [[FIRST_I:%.*]] = getelementptr inbounds %"struct.std::pair", %"struct.std::pair"* [[A:%.*]], i64 0, i32 0
+; X86-NEXT:    [[FIRST1_I:%.*]] = getelementptr inbounds %"struct.std::pair", %"struct.std::pair"* [[B:%.*]], i64 0, i32 0
+; X86-NEXT:    [[CSTR:%.*]] = bitcast i32* [[FIRST_I]] to i8*
+; X86-NEXT:    [[CSTR1:%.*]] = bitcast i32* [[FIRST1_I]] to i8*
+; X86-NEXT:    [[MEMCMP:%.*]] = call i32 @memcmp(i8* [[CSTR]], i8* [[CSTR1]], i64 16)
+; X86-NEXT:    [[TMP0:%.*]] = icmp eq i32 [[MEMCMP]], 0
+; X86-NEXT:    br label [[OPEQ1_EXIT:%.*]]
+;
+  %"struct.std::pair"* nocapture readonly dereferenceable(16) %a,
+  %"struct.std::pair"* nocapture readonly dereferenceable(16) %b) local_unnamed_addr #0 {
+entry:
+  %ptr = alloca i32
+  %first.i = getelementptr inbounds %"struct.std::pair", %"struct.std::pair"* %a, i64 0, i32 0
+  %0 = load i32, i32* %first.i, align 4
+  %first1.i = getelementptr inbounds %"struct.std::pair", %"struct.std::pair"* %b, i64 0, i32 0
+  %1 = load i32, i32* %first1.i, align 4
+  ; Does other work, has no interference, merge block
+  store i32 42, i32* %ptr
+  %cmp.i = icmp eq i32 %0, %1
+  br i1 %cmp.i, label %land.rhs.i, label %opeq1.exit
+
+land.rhs.i:
+  %second.i = getelementptr inbounds %"struct.std::pair", %"struct.std::pair"* %a, i64 0, i32 1
+  %2 = load i32, i32* %second.i, align 4
+  %second2.i = getelementptr inbounds %"struct.std::pair", %"struct.std::pair"* %b, i64 0, i32 1
+  %3 = load i32, i32* %second2.i, align 4
+  %cmp2.i = icmp eq i32 %2, %3
+  br i1 %cmp2.i, label %land.rhs.i.2, label %opeq1.exit
+
+land.rhs.i.2:
+  %third.i = getelementptr inbounds %"struct.std::pair", %"struct.std::pair"* %a, i64 0, i32 2
+  %4 = load i32, i32* %third.i, align 4
+  %third2.i = getelementptr inbounds %"struct.std::pair", %"struct.std::pair"* %b, i64 0, i32 2
+  %5 = load i32, i32* %third2.i, align 4
+  %cmp3.i = icmp eq i32 %4, %5
+  br i1 %cmp3.i, label %land.rhs.i.3, label %opeq1.exit
+
+land.rhs.i.3:
+  %fourth.i = getelementptr inbounds %"struct.std::pair", %"struct.std::pair"* %a, i64 0, i32 3
+  %6 = load i32, i32* %fourth.i, align 4
+  %fourth2.i = getelementptr inbounds %"struct.std::pair", %"struct.std::pair"* %b, i64 0, i32 3
+  %7 = load i32, i32* %fourth2.i, align 4
+  %cmp4.i = icmp eq i32 %6, %7
+  br label %opeq1.exit
+
+opeq1.exit:
+  %8 = phi i1 [ false, %entry ], [ false, %land.rhs.i] , [ false, %land.rhs.i.2 ], [ %cmp4.i, %land.rhs.i.3 ]
+  ret i1 %8
+}