[CaptureTracker] Provide a numbered basic block to PointerMayBeCapturedBefore

[bruno]

Summary

This patch is a follow up from r240560 and is a step further into trying
to mitigate the compile time performance issues in the path DeadStoreElimination -> MepDepAnalysis ->
CaptureTracking. I've basically moved the "cached numbered BB" out of the CaptureTracker.

By providing the CaptureTracker with the "cached numbered BB" instead of
computing it every time, MemDepAnalysis can use the same "cached numbered BB"
throughout its calls to AA->callCapturesBefore, avoiding to recompute it for
every scanned instruction. In the same testcase used in r240560, compile time goes
down from 2min to 30s.

[bruno]

Ping :-)

[• dberlin]

I know you didn't build the original code that is being moved out here, and I really appreciate you taking the time to work on this :)

However, looking at it, while it seems okay for an internal implementation detail, moving it out into it's own class makes me think it needs a little work on the interface/implementation.
Hope that is okay.

include/llvm/Analysis/AliasAnalysis.h

479 ↗

(On Diff #30180)

While you are here, can you please document the function and its arguments properly?

include/llvm/Analysis/NumberedBasicBlock.h

34 ↗

(On Diff #30180)

Given the description of what this class does, why is it called numbered anything?
Shouldn't it be "OrderedBasicBlock"?

You are just describing and querying things about the order
The fact that you maintain the order using numbering is an implementation detail (and in fact i've seen proposals to change how BB's are laid out so that ordering would not require numbering.)

38 ↗

(On Diff #30180)

Can you add comments describing what these represent?

43 ↗

(On Diff #30180)

The implementation here seems confusing. Find doesn't find anything, instead, it is really trying to give a before relationship (IE it is literally answering the dominates query)

If you want to return the instruction, i'd call this "first_of" or something.
But i'm not clear on why it returns an instruction, instead of being called "comesBefore" and returning a boolean.

All returning the instruction does is make the logic of the caller more confusing :)

lib/Analysis/AliasAnalysis.cpp

348 ↗

(On Diff #30180)

While you are here, can you please document the function and its arguments properly?

lib/Analysis/CaptureTracking.cpp

196 ↗

(On Diff #30180)

Errr, it looks like this duplicates the logic below, just to avoid the construction cost of the object all the time?

If so, is there a reason you don't just new and delete one?

lib/Analysis/NumberedBasicBlock.cpp

71 ↗

(On Diff #30180)

I have to admit i'm not a fan of treating the unsigneds like booleans values.
If you are going to do this, can you use explicit compares or something?

Or at least, explain the logic of all of this?

It only works because lookup default constructs values :)

At the very least, i would add a comment as to what this block of code is doing, like

"First we lookup the instructions. If they don't exist, lookup will give us back zero. If they both exist, we compare the numbers. Otherwise, if NA exists and NB doesn't, it means NA must come before NB because we would have numbered NB as well if it didn't. The same is true for NB. If it exists, but NA does not, NA must come after it.

If neither exist, we need to number the block".

(Note also that the last line of code would make more sense if the function was comesBefore or something, or if it returned a boolean)
Then it would be return comesBefore(A, B))

[hfinkel]

In the same testcase used in r240560, compile time goes down from 2min to 30s.

Nice!

include/llvm/Analysis/NumberedBasicBlock.h

10 ↗

(On Diff #30180)

defines NumberedBasicBlock class -> defines the NumberedBasicBlock class

14 ↗

(On Diff #30180)

NumberedBasicBlock lazily built after -> NumberedBasicBlock is lazily built [on|off of|around]

lib/Analysis/NumberedBasicBlock.cpp

15 ↗

(On Diff #30180)

NumberedBasicBlock lazily built after -> NumberedBasicBlock is lazily built [on|off of|around]

37 ↗

(On Diff #30180)

Indentation looks off here.

70 ↗

(On Diff #30180)

So it seems you start numbering from 1 (that should be in a comment somewhere). Then, for every instruction you've not already visited you insert an implicit 0 entry in the map for it. You then replace this entry with another number when you call find. I'd rather we not insert implicit entries, instead, just test the iterators.

auto NAI = NumberedInsts.find(A);
auto NBI = NumberedInsts.find(B);

if (NAI != NumberedInsts.end() && NBI != NumberedInsts.end()) {
  ...

with that done, you can start numbering from 0, which I think makes more sense in general.

71 ↗

(On Diff #30180)

Otherwise, if NA exists and NB doesn't, it means NA must come before NB because we would have numbered NB as well if it didn't. The same is true for NB. If it exists, but NA does not, NA must come after it.

Does this embed an assumption on the relative orderings of the calls to the function by the client. What if I start querying in the middle of the block somewhere using some previously-visited instruction and another I've not yet visited? I understand why CaptureTracking, which is following use/def chains walking from defs to uses, does not do this, but as a general utility, we either need to be more careful, or very carefully document the assumptions.

[bruno]

Thanks Hal and Daniel for the review, really appreciated your feedback.

include/llvm/Analysis/NumberedBasicBlock.h

34 ↗

(On Diff #30180)

Right. Done!

43 ↗

(On Diff #30180)

comesBefore + retuning bool seems like a better approach indeed!

lib/Analysis/CaptureTracking.cpp

196 ↗

(On Diff #30180)

OK

lib/Analysis/NumberedBasicBlock.cpp

70 ↗

(On Diff #30180)

OK

71 ↗

(On Diff #30180)

If you're using some previously-visited instruction (call it A) and another you've not yet visited (B), it's just like Daniel explained in his comment; either B is already cached (when we first looked up A) if it was somewhere between BB.begin() and A, in this case it B comesBefore A. If B isn't cached, it means it must come after. Doesn't matter if you start querying in the middle of the block, if it's not in the map, it will search from BB.begin() (or resume from the last position it scanned) until it finds either A or B. Let me know if I didn't get your question right :-)

[bruno]

Updated a new version of the patch!

[hfinkel]

LGTM.

include/llvm/Analysis/CaptureTracking.h

46 ↗

(On Diff #30817)

capture tracker queries -> capture-tracker queries

lib/Analysis/AliasAnalysis.cpp

347 ↗

(On Diff #30817)

instruction ordering queries -> instruction-ordering queries

lib/Analysis/NumberedBasicBlock.cpp

71 ↗

(On Diff #30180)

Indeed, I re-read the code and now I understand. Sorry for being bothersome about this. For some reason, I thought that find(A, B) might only number the instructions in between A and B. But it always numbers from the beginning until A or B.

llvm/trunk/include/llvm/Analysis/AliasAnalysis.h

 class VAArgInst;
 class DataLayout;
 class TargetLibraryInfo;
 class Pass;
 class AnalysisUsage;
 class MemTransferInst;
 class MemIntrinsic;
 class DominatorTree;
+class OrderedBasicBlock;
 
 /// The possible results of an alias query.
 ///
 /// These results are always computed between two MemoryLocation objects as
 /// a query to some alias analysis.
 ///
 /// Note that these are unscoped enumerations because we would like to support
 /// implicitly testing a result for the existence of any possible aliasing with
public:
   ModRefInfo getModRefInfo(Instruction *I, ImmutableCallSite Call);
 
   /// Return information about whether two call sites may refer to the same set
   /// of memory locations. See the AA documentation for details:
   ///   http://llvm.org/docs/AliasAnalysis.html#ModRefInfo
   virtual ModRefInfo getModRefInfo(ImmutableCallSite CS1,
                                    ImmutableCallSite CS2);
 
-  /// Return information about whether a particular call site modifies or reads
-  /// the specified memory location.
+  /// \brief Return information about whether a particular call site modifies
+  /// or reads the specified memory location \p MemLoc before instruction \p I
+  /// in a BasicBlock. A ordered basic block \p OBB can be used to speed up
+  /// instruction ordering queries inside the BasicBlock containing \p I.
   ModRefInfo callCapturesBefore(const Instruction *I,
-                                const MemoryLocation &MemLoc,
-                                DominatorTree *DT);
+                                const MemoryLocation &MemLoc, DominatorTree *DT,
+                                OrderedBasicBlock *OBB = nullptr);
 
-  /// A convenience wrapper to synthesize a memory location.
+  /// \brief A convenience wrapper to synthesize a memory location.
   ModRefInfo callCapturesBefore(const Instruction *I, const Value *P,
-                                uint64_t Size, DominatorTree *DT) {
-    return callCapturesBefore(I, MemoryLocation(P, Size), DT);
+                                uint64_t Size, DominatorTree *DT,
+                                OrderedBasicBlock *OBB = nullptr) {
+    return callCapturesBefore(I, MemoryLocation(P, Size), DT, OBB);
   }
 
   /// @}
   //===--------------------------------------------------------------------===//
   /// \name Higher level methods for querying mod/ref information.
   /// @{
 
   /// Check if it is possible for execution of the specified basic block to

llvm/trunk/include/llvm/Analysis/CaptureTracking.h

 #define LLVM_ANALYSIS_CAPTURETRACKING_H
 
 namespace llvm {
 
   class Value;
   class Use;
   class Instruction;
   class DominatorTree;
+  class OrderedBasicBlock;
 
   /// PointerMayBeCaptured - Return true if this pointer value may be captured
   /// by the enclosing function (which is required to exist).  This routine can
   /// be expensive, so consider caching the results.  The boolean ReturnCaptures
   /// specifies whether returning the value (or part of it) from the function
   /// counts as capturing it or not.  The boolean StoreCaptures specified
   /// whether storing the value (or part of it) into memory anywhere
   /// automatically counts as capturing it or not.
   bool PointerMayBeCaptured(const Value *V,
                             bool ReturnCaptures,
                             bool StoreCaptures);
 
   /// PointerMayBeCapturedBefore - Return true if this pointer value may be
   /// captured by the enclosing function (which is required to exist). If a
   /// DominatorTree is provided, only captures which happen before the given
   /// instruction are considered. This routine can be expensive, so consider
   /// caching the results.  The boolean ReturnCaptures specifies whether
   /// returning the value (or part of it) from the function counts as capturing
   /// it or not.  The boolean StoreCaptures specified whether storing the value
   /// (or part of it) into memory anywhere automatically counts as capturing it
   /// or not. Captures by the provided instruction are considered if the
-  /// final parameter is true.
+  /// final parameter is true. An ordered basic block in \p OBB could be used
+  /// to speed up capture-tracker queries.
   bool PointerMayBeCapturedBefore(const Value *V, bool ReturnCaptures,
                                   bool StoreCaptures, const Instruction *I,
-                                  DominatorTree *DT, bool IncludeI = false);
+                                  DominatorTree *DT, bool IncludeI = false,
+                                  OrderedBasicBlock *OBB = nullptr);
 
   /// This callback is used in conjunction with PointerMayBeCaptured. In
   /// addition to the interface here, you'll need to provide your own getters
   /// to see whether anything was captured.
   struct CaptureTracker {
     virtual ~CaptureTracker();
 
     /// tooManyUses - The depth of traversal has breached a limit. There may be

llvm/trunk/include/llvm/Analysis/OrderedBasicBlock.h

+//===- llvm/Analysis/OrderedBasicBlock.h --------------------- -*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines the OrderedBasicBlock class. OrderedBasicBlock maintains
+// an interface where clients can query if one instruction comes before another
+// in a BasicBlock. Since BasicBlock currently lacks a reliable way to query
+// relative position between instructions one can use OrderedBasicBlock to do
+// such queries. OrderedBasicBlock is lazily built on a source BasicBlock and
+// maintains an internal Instruction -> Position map. A OrderedBasicBlock
+// instance should be discarded whenever the source BasicBlock changes.
+//
+// It's currently used by the CaptureTracker in order to find relative
+// positions of a pair of instructions inside a BasicBlock.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_ORDEREDBASICBLOCK_H
+#define LLVM_ANALYSIS_ORDEREDBASICBLOCK_H
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/IR/BasicBlock.h"
+
+namespace llvm {
+
+class Instruction;
+class BasicBlock;
+
+class OrderedBasicBlock {
+private:
+  /// \brief Map a instruction to its position in a BasicBlock.
+  SmallDenseMap<const Instruction *, unsigned, 32> NumberedInsts;
+
+  /// \brief Keep track of last instruction inserted into \p NumberedInsts.
+  /// It speeds up queries for uncached instructions by providing a start point
+  /// for new queries in OrderedBasicBlock::comesBefore.
+  BasicBlock::const_iterator LastInstFound;
+
+  /// \brief The position/number to tag the next instruction to be found.
+  unsigned NextInstPos;
+
+  /// \brief The source BasicBlock to map.
+  const BasicBlock *BB;
+
+  /// \brief Given no cached results, find if \p A comes before \p B in \p BB.
+  /// Cache and number out instruction while walking \p BB.
+  bool comesBefore(const Instruction *A, const Instruction *B);
+
+public:
+  OrderedBasicBlock(const BasicBlock *BasicB);
+
+  /// \brief Find out whether \p A dominates \p B, meaning whether \p A
+  /// comes before \p B in \p BB. This is a simplification that considers
+  /// cached instruction positions and ignores other basic blocks, being
+  /// only relevant to compare relative instructions positions inside \p BB.
+  bool dominates(const Instruction *A, const Instruction *B);
+};
+
+} // End llvm namespace
+
+#endif

llvm/trunk/lib/Analysis/AliasAnalysis.cpp

ModRefInfo AliasAnalysis::getModRefInfo(const AtomicRMWInst *RMW,
 
   // If the atomicrmw address does not alias the location, it does not access it.
   if (Loc.Ptr && !alias(MemoryLocation::get(RMW), Loc))
     return MRI_NoModRef;
 
   return MRI_ModRef;
 }
 
-// FIXME: this is really just shoring-up a deficiency in alias analysis.
-// BasicAA isn't willing to spend linear time determining whether an alloca
-// was captured before or after this particular call, while we are. However,
-// with a smarter AA in place, this test is just wasting compile time.
+/// \brief Return information about whether a particular call site modifies
+/// or reads the specified memory location \p MemLoc before instruction \p I
+/// in a BasicBlock. A ordered basic block \p OBB can be used to speed up
+/// instruction-ordering queries inside the BasicBlock containing \p I.
+/// FIXME: this is really just shoring-up a deficiency in alias analysis.
+/// BasicAA isn't willing to spend linear time determining whether an alloca
+/// was captured before or after this particular call, while we are. However,
+/// with a smarter AA in place, this test is just wasting compile time.
 ModRefInfo AliasAnalysis::callCapturesBefore(const Instruction *I,
                                              const MemoryLocation &MemLoc,
-                                             DominatorTree *DT) {
+                                             DominatorTree *DT,
+                                             OrderedBasicBlock *OBB) {
   if (!DT)
     return MRI_ModRef;
 
   const Value *Object = GetUnderlyingObject(MemLoc.Ptr, *DL);
   if (!isIdentifiedObject(Object) || isa<GlobalValue>(Object) ||
       isa<Constant>(Object))
     return MRI_ModRef;
 
   ImmutableCallSite CS(I);
   if (!CS.getInstruction() || CS.getInstruction() == Object)
     return MRI_ModRef;
 
   if (llvm::PointerMayBeCapturedBefore(Object, /* ReturnCaptures */ true,
                                        /* StoreCaptures */ true, I, DT,
-                                       /* include Object */ true))
+                                       /* include Object */ true,
+                                       /* OrderedBasicBlock */ OBB))
     return MRI_ModRef;
 
   unsigned ArgNo = 0;
   ModRefInfo R = MRI_NoModRef;
   for (ImmutableCallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end();
        CI != CE; ++CI, ++ArgNo) {
     // Only look at the no-capture or byval pointer arguments.  If this
     // pointer were passed to arguments that were neither of these, then it

llvm/trunk/lib/Analysis/CMakeLists.txt

add_llvm_library(LLVMAnalysis
   LoopPass.cpp
   MemDepPrinter.cpp
   MemDerefPrinter.cpp
   MemoryBuiltins.cpp
   MemoryDependenceAnalysis.cpp
   MemoryLocation.cpp
   ModuleDebugInfoPrinter.cpp
   NoAliasAnalysis.cpp
+  OrderedBasicBlock.cpp
   PHITransAddr.cpp
   PostDominators.cpp
   PtrUseVisitor.cpp
   RegionInfo.cpp
   RegionPass.cpp
   RegionPrinter.cpp
   ScalarEvolution.cpp
   ScalarEvolutionAliasAnalysis.cpp

llvm/trunk/lib/Analysis/CaptureTracking.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/CaptureTracking.h"
+#include "llvm/Analysis/OrderedBasicBlock.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Instructions.h"
 
 using namespace llvm;
 
 CaptureTracker::~CaptureTracker() {}
bool captured(const Use *U) override {
       return true;
     }
 
     bool ReturnCaptures;
 
     bool Captured;
   };
 
-  struct NumberedInstCache {
-    SmallDenseMap<const Instruction *, unsigned, 32> NumberedInsts;
-    BasicBlock::const_iterator LastInstFound;
-    unsigned LastInstPos;
-    const BasicBlock *BB;
-
-    NumberedInstCache(const BasicBlock *BasicB) : LastInstPos(0), BB(BasicB) {
-      LastInstFound = BB->end();
-    }
-
-    /// \brief Find the first instruction 'A' or 'B' in 'BB'. Number out
-    /// instruction while walking 'BB'.
-    const Instruction *find(const Instruction *A, const Instruction *B) {
-      const Instruction *Inst = nullptr;
-      assert(!(LastInstFound == BB->end() && LastInstPos != 0) &&
-             "Instruction supposed to be in NumberedInsts");
-
-      // Start the search with the instruction found in the last lookup round.
-      auto II = BB->begin();
-      auto IE = BB->end();
-      if (LastInstFound != IE)
-        II = std::next(LastInstFound);
-
-      // Number all instructions up to the point where we find 'A' or 'B'.
-      for (++LastInstPos; II != IE; ++II, ++LastInstPos) {
-        Inst = cast<Instruction>(II);
-        NumberedInsts[Inst] = LastInstPos;
-        if (Inst == A || Inst == B)
-          break;
-      }
-
-      assert(II != IE && "Instruction not found?");
-      LastInstFound = II;
-      return Inst;
-    }
-
-    /// \brief Find out whether 'A' dominates 'B', meaning whether 'A'
-    /// comes before 'B' in 'BB'. This is a simplification that considers
-    /// cached instruction positions and ignores other basic blocks, being
-    /// only relevant to compare relative instructions positions inside 'BB'.
-    bool dominates(const Instruction *A, const Instruction *B) {
-      assert(A->getParent() == B->getParent() &&
-             "Instructions must be in the same basic block!");
-
-      unsigned NA = NumberedInsts.lookup(A);
-      unsigned NB = NumberedInsts.lookup(B);
-      if (NA && NB)
-        return NA < NB;
-      if (NA)
-        return true;
-      if (NB)
-        return false;
-
-      return A == find(A, B);
-    }
-  };
-
   /// Only find pointer captures which happen before the given instruction. Uses
   /// the dominator tree to determine whether one instruction is before another.
   /// Only support the case where the Value is defined in the same basic block
   /// as the given instruction and the use.
   struct CapturesBefore : public CaptureTracker {
 
     CapturesBefore(bool ReturnCaptures, const Instruction *I, DominatorTree *DT,
-                   bool IncludeI)
-      : LocalInstCache(I->getParent()), BeforeHere(I), DT(DT),
+                   bool IncludeI, OrderedBasicBlock *IC)
+      : OrderedBB(IC), BeforeHere(I), DT(DT),
         ReturnCaptures(ReturnCaptures), IncludeI(IncludeI), Captured(false) {}
 
     void tooManyUses() override { Captured = true; }
 
     bool isSafeToPrune(Instruction *I) {
       BasicBlock *BB = I->getParent();
       // We explore this usage only if the usage can reach "BeforeHere".
       // If use is not reachable from entry, there is no need to explore.
       if (BeforeHere != I && !DT->isReachableFromEntry(BB))
         return true;
 
       // Compute the case where both instructions are inside the same basic
       // block. Since instructions in the same BB as BeforeHere are numbered in
-      // 'LocalInstCache', avoid using 'dominates' and 'isPotentiallyReachable'
+      // 'OrderedBB', avoid using 'dominates' and 'isPotentiallyReachable'
       // which are very expensive for large basic blocks.
       if (BB == BeforeHere->getParent()) {
         // 'I' dominates 'BeforeHere' => not safe to prune.
         //
         // The value defined by an invoke dominates an instruction only if it
         // dominates every instruction in UseBB. A PHI is dominated only if
         // the instruction dominates every possible use in the UseBB. Since
         // UseBB == BB, avoid pruning.
         if (isa<InvokeInst>(BeforeHere) || isa<PHINode>(I) || I == BeforeHere)
           return false;
-        if (!LocalInstCache.dominates(BeforeHere, I))
+        if (!OrderedBB->dominates(BeforeHere, I))
           return false;
 
         // 'BeforeHere' comes before 'I', it's safe to prune if we also
         // guarantee that 'I' never reaches 'BeforeHere' through a back-edge or
         // by its successors, i.e, prune if:
         //
         //  (1) BB is an entry block or have no sucessors.
         //  (2) There's no path coming back through BB sucessors.
bool captured(const Use *U) override {
 
       if (!shouldExplore(U))
         return false;
 
       Captured = true;
       return true;
     }
 
-    NumberedInstCache LocalInstCache;
+    OrderedBasicBlock *OrderedBB;
     const Instruction *BeforeHere;
     DominatorTree *DT;
 
     bool ReturnCaptures;
     bool IncludeI;
 
     bool Captured;
   };

 /// PointerMayBeCapturedBefore - Return true if this pointer value may be
 /// captured by the enclosing function (which is required to exist). If a
 /// DominatorTree is provided, only captures which happen before the given
 /// instruction are considered. This routine can be expensive, so consider
 /// caching the results.  The boolean ReturnCaptures specifies whether
 /// returning the value (or part of it) from the function counts as capturing
 /// it or not.  The boolean StoreCaptures specified whether storing the value
 /// (or part of it) into memory anywhere automatically counts as capturing it
-/// or not.
+/// or not. A ordered basic block \p OBB can be used in order to speed up
+/// queries about relative order among instructions in the same basic block.
 bool llvm::PointerMayBeCapturedBefore(const Value *V, bool ReturnCaptures,
                                       bool StoreCaptures, const Instruction *I,
-                                      DominatorTree *DT, bool IncludeI) {
+                                      DominatorTree *DT, bool IncludeI,
+                                      OrderedBasicBlock *OBB) {
   assert(!isa<GlobalValue>(V) &&
          "It doesn't make sense to ask whether a global is captured.");
+  bool UseNewOBB = OBB == nullptr;
 
   if (!DT)
     return PointerMayBeCaptured(V, ReturnCaptures, StoreCaptures);
+  if (UseNewOBB)
+    OBB = new OrderedBasicBlock(I->getParent());
 
   // TODO: See comment in PointerMayBeCaptured regarding what could be done
   // with StoreCaptures.
 
-  CapturesBefore CB(ReturnCaptures, I, DT, IncludeI);
+  CapturesBefore CB(ReturnCaptures, I, DT, IncludeI, OBB);
   PointerMayBeCaptured(V, &CB);
+
+  if (UseNewOBB)
+    delete OBB;
   return CB.Captured;
 }
 
 /// TODO: Write a new FunctionPass AliasAnalysis so that it can keep
 /// a cache. Then we can move the code from BasicAliasAnalysis into
 /// that path, and remove this threshold.
 static int const Threshold = 20;
 

llvm/trunk/lib/Analysis/MemoryDependenceAnalysis.cpp

 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/Analysis/PHITransAddr.h"
+#include "llvm/Analysis/OrderedBasicBlock.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/PredIteratorCache.h"
MemDepResult MemoryDependenceAnalysis::getPointerDependencyFrom(
   if (isLoad && QueryInst) {
     LoadInst *LI = dyn_cast<LoadInst>(QueryInst);
     if (LI && LI->getMetadata(LLVMContext::MD_invariant_load) != nullptr)
       isInvariantLoad = true;
   }
 
   const DataLayout &DL = BB->getModule()->getDataLayout();
 
+  // Create a numbered basic block to lazily compute and cache instruction
+  // positions inside a BB. This is used to provide fast queries for relative
+  // position between two instructions in a BB and can be used by
+  // AliasAnalysis::callCapturesBefore.
+  OrderedBasicBlock OBB(BB);
+
   // Walk backwards through the basic block, looking for dependencies.
   while (ScanIt != BB->begin()) {
     Instruction *Inst = --ScanIt;
 
     if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst))
       // Debug intrinsics don't (and can't) cause dependencies.
       if (isa<DbgInfoIntrinsic>(II)) continue;
 
#endif
 
     if (isInvariantLoad)
        continue;
 
     // See if this instruction (e.g. a call or vaarg) mod/ref's the pointer.
     ModRefInfo MR = AA->getModRefInfo(Inst, MemLoc);
     // If necessary, perform additional analysis.
     if (MR == MRI_ModRef)
-      MR = AA->callCapturesBefore(Inst, MemLoc, DT);
+      MR = AA->callCapturesBefore(Inst, MemLoc, DT, &OBB);
     switch (MR) {
     case MRI_NoModRef:
       // If the call has no effect on the queried pointer, just ignore it.
       continue;
     case MRI_Mod:
       return MemDepResult::getClobber(Inst);
     case MRI_Ref:
       // If the call is known to never store to the pointer, and if this is a

llvm/trunk/lib/Analysis/OrderedBasicBlock.cpp

+//===- OrderedBasicBlock.cpp --------------------------------- -*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements the OrderedBasicBlock class. OrderedBasicBlock
+// maintains an interface where clients can query if one instruction comes
+// before another in a BasicBlock. Since BasicBlock currently lacks a reliable
+// way to query relative position between instructions one can use
+// OrderedBasicBlock to do such queries. OrderedBasicBlock is lazily built on a
+// source BasicBlock and maintains an internal Instruction -> Position map. A
+// OrderedBasicBlock instance should be discarded whenever the source
+// BasicBlock changes.
+//
+// It's currently used by the CaptureTracker in order to find relative
+// positions of a pair of instructions inside a BasicBlock.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/OrderedBasicBlock.h"
+#include "llvm/IR/Instruction.h"
+using namespace llvm;
+
+OrderedBasicBlock::OrderedBasicBlock(const BasicBlock *BasicB)
+    : NextInstPos(0), BB(BasicB) {
+  LastInstFound = BB->end();
+}
+
+/// \brief Given no cached results, find if \p A comes before \p B in \p BB.
+/// Cache and number out instruction while walking \p BB.
+bool OrderedBasicBlock::comesBefore(const Instruction *A,
+                                    const Instruction *B) {
+  const Instruction *Inst = nullptr;
+  assert(!(LastInstFound == BB->end() && NextInstPos != 0) &&
+         "Instruction supposed to be in NumberedInsts");
+
+  // Start the search with the instruction found in the last lookup round.
+  auto II = BB->begin();
+  auto IE = BB->end();
+  if (LastInstFound != IE)
+    II = std::next(LastInstFound);
+
+  // Number all instructions up to the point where we find 'A' or 'B'.
+  for (; II != IE; ++II) {
+    Inst = cast<Instruction>(II);
+    NumberedInsts[Inst] = NextInstPos++;
+    if (Inst == A || Inst == B)
+      break;
+  }
+
+  assert(II != IE && "Instruction not found?");
+  assert((Inst == A || Inst == B) && "Should find A or B");
+  LastInstFound = II;
+  return Inst == A;
+}
+
+/// \brief Find out whether \p A dominates \p B, meaning whether \p A
+/// comes before \p B in \p BB. This is a simplification that considers
+/// cached instruction positions and ignores other basic blocks, being
+/// only relevant to compare relative instructions positions inside \p BB.
+bool OrderedBasicBlock::dominates(const Instruction *A, const Instruction *B) {
+  assert(A->getParent() == B->getParent() &&
+         "Instructions must be in the same basic block!");
+
+  // First we lookup the instructions. If they don't exist, lookup will give us
+  // back ::end(). If they both exist, we compare the numbers. Otherwise, if NA
+  // exists and NB doesn't, it means NA must come before NB because we would
+  // have numbered NB as well if it didn't. The same is true for NB. If it
+  // exists, but NA does not, NA must come after it. If neither exist, we need
+  // to number the block and cache the results (by calling comesBefore).
+  auto NAI = NumberedInsts.find(A);
+  auto NBI = NumberedInsts.find(B);
+  if (NAI != NumberedInsts.end() && NBI != NumberedInsts.end())
+    return NAI->second < NBI->second;
+  if (NAI != NumberedInsts.end())
+    return true;
+  if (NBI != NumberedInsts.end())
+    return false;
+
+  return comesBefore(A, B);
+}