[MemDepAnalysis] Allow caller to pass in an OrderedBasicBlock.

[fhahn]

Summary

If the caller can preserve the OBB, we can avoid recomputing the order
for each getDependency call.

[rnk]

I was working on restarting the in-instruction order tracking discussion, but the pathological test case I came up with didn't benefit from it:

const std::vector<unsigned> &lookup(std::string k) {
  static std::map<std::string, std::vector<unsigned>> the_map = {
    {"s", {1, 2, 3}},
    {"s", {1, 2, 3}},
    ... repeat 200x, or arbitrarily long
  };
  return the_map[k];
}

This causes clang to generate a very large BB that DSE spends a lot of time on. However, invalidating the order numbers only on removal wasn't enough to drastically improve performance, so I lost the motivation to drive it through. The ordering helped significantly with my less simplified test case (std::map<unsigned, std::vector<StringRef>>, see rC345329 which removed it), but I wasn't happy with it.

llvm/include/llvm/Analysis/MemoryDependenceAnalysis.h

456–457

This function only has one real call site, which is in getPointerDependencyFrom. Can you make these parameters non-optional?

llvm/lib/Analysis/MemoryDependenceAnalysis.cpp

446–450

I've seen this pattern across LLVM, and I've never particularly liked it. I don't think it's as easy to optimize as the author probably thought it was. I think this would be simpler:

unsigned DefaultLimit = BlockScanLimit;
if (!Limit)
  Limit = &DefaultLimit;
...

[fhahn]

Addressed comments, thanks!

[fhahn]

In D59788#1441992, @rnk wrote:

I was working on restarting the in-instruction order tracking discussion, but the pathological test case I came up with didn't benefit from it:

const std::vector<unsigned> &lookup(std::string k) {
  static std::map<std::string, std::vector<unsigned>> the_map = {
    {"s", {1, 2, 3}},
    {"s", {1, 2, 3}},
    ... repeat 200x, or arbitrarily long
  };
  return the_map[k];
}

This causes clang to generate a very large BB that DSE spends a lot of time on. However, invalidating the order numbers only on removal wasn't enough to drastically improve performance, so I lost the motivation to drive it through. The ordering helped significantly with my less simplified test case (std::map<unsigned, std::vector<StringRef>>, see rC345329 which removed it), but I wasn't happy with it.

Yes, it looks like there is another compile time problem in DSE, which is independent of the order query issue. I have an input file with a huge number of stores, and the majority of the time is spent getting dependency info (but not in OrderedBB). It is probably the same issue you are seeing. Did you create a PR for it already?

[rnk]

In D59788#1443448, @fhahn wrote:

Yes, it looks like there is another compile time problem in DSE, which is independent of the order query issue. I have an input file with a huge number of stores, and the majority of the time is spent getting dependency info (but not in OrderedBB). It is probably the same issue you are seeing. Did you create a PR for it already?

Nope, go for it.

[fhahn]

In D59788#1443490, @rnk wrote:

Nope, go for it.

I'll do it tomorrow. Does the patch look ok to you now?

[fhahn]

In D59788#1443448, @fhahn wrote:

In D59788#1441992, @rnk wrote:

I was working on restarting the in-instruction order tracking discussion, but the pathological test case I came up with didn't benefit from it:

const std::vector<unsigned> &lookup(std::string k) {
  static std::map<std::string, std::vector<unsigned>> the_map = {
    {"s", {1, 2, 3}},
    {"s", {1, 2, 3}},
    ... repeat 200x, or arbitrarily long
  };
  return the_map[k];
}

This causes clang to generate a very large BB that DSE spends a lot of time on. However, invalidating the order numbers only on removal wasn't enough to drastically improve performance, so I lost the motivation to drive it through. The ordering helped significantly with my less simplified test case (std::map<unsigned, std::vector<StringRef>>, see rC345329 which removed it), but I wasn't happy with it.

@rnk is there any chance you still have the full reproducer? I did not manage to reproduce the long time spent in DSE with the snippet above and I cannot share the reproducer I have unfortunately :(

[rnk]

In D59788#1444721, @fhahn wrote:

@rnk is there any chance you still have the full reproducer? I did not manage to reproduce the long time spent in DSE with the snippet above and I cannot share the reproducer I have unfortunately :(

Try this bitcode I attached in the tracker:
https://bugs.llvm.org/attachment.cgi?id=21689

This is the time report I see for it:

$ opt -time-passes -O2 longbbinit.bc -o NUL
===-------------------------------------------------------------------------===
                      ... Pass execution timing report ...
===-------------------------------------------------------------------------===
  Total Execution Time: 16.4531 seconds (16.4770 wall clock)

   ---User Time---   --System Time--   --User+System--   ---Wall Time---  --- Name ---
   9.8281 ( 64.8%)   1.2188 ( 95.1%)  11.0469 ( 67.1%)  11.0376 ( 67.0%)  Dead Store Elimination
   1.7344 ( 11.4%)   0.0000 (  0.0%)   1.7344 ( 10.5%)   1.6974 ( 10.3%)  Global Value Numbering
   0.6563 (  4.3%)   0.0156 (  1.2%)   0.6719 (  4.1%)   0.6795 (  4.1%)  Function Integration/Inlining
   0.3750 (  2.5%)   0.0000 (  0.0%)   0.3750 (  2.3%)   0.3846 (  2.3%)  Value Propagation
   0.3750 (  2.5%)   0.0000 (  0.0%)   0.3750 (  2.3%)   0.3743 (  2.3%)  Value Propagation #2
   0.2344 (  1.5%)   0.0156 (  1.2%)   0.2500 (  1.5%)   0.2515 (  1.5%)  Bitcode Writer

I'm not sure it's the exact issue you're looking at here, though.

[fhahn]

In D59788#1444919, @rnk wrote:

In D59788#1444721, @fhahn wrote:

@rnk is there any chance you still have the full reproducer? I did not manage to reproduce the long time spent in DSE with the snippet above and I cannot share the reproducer I have unfortunately :(

Try this bitcode I attached in the tracker:
https://bugs.llvm.org/attachment.cgi?id=21689

This is the time report I see for it:

$ opt -time-passes -O2 longbbinit.bc -o NUL
===-------------------------------------------------------------------------===
                      ... Pass execution timing report ...
===-------------------------------------------------------------------------===
  Total Execution Time: 16.4531 seconds (16.4770 wall clock)

   ---User Time---   --System Time--   --User+System--   ---Wall Time---  --- Name ---
   9.8281 ( 64.8%)   1.2188 ( 95.1%)  11.0469 ( 67.1%)  11.0376 ( 67.0%)  Dead Store Elimination
   1.7344 ( 11.4%)   0.0000 (  0.0%)   1.7344 ( 10.5%)   1.6974 ( 10.3%)  Global Value Numbering
   0.6563 (  4.3%)   0.0156 (  1.2%)   0.6719 (  4.1%)   0.6795 (  4.1%)  Function Integration/Inlining
   0.3750 (  2.5%)   0.0000 (  0.0%)   0.3750 (  2.3%)   0.3846 (  2.3%)  Value Propagation
   0.3750 (  2.5%)   0.0000 (  0.0%)   0.3750 (  2.3%)   0.3743 (  2.3%)  Value Propagation #2
   0.2344 (  1.5%)   0.0156 (  1.2%)   0.2500 (  1.5%)   0.2515 (  1.5%)  Bitcode Writer

I'm not sure it's the exact issue you're looking at here, though.

Thanks, that looks promising!

Are you happy with the update to this patch?

[rnk]

Yep, lgtm!

llvm/include/llvm/Analysis/MemoryDependenceAnalysis.h

public:
   /// The return value of this method is the default limit that will be
   /// used if no limit is explicitly passed in.
   unsigned getDefaultBlockScanLimit() const;
 
   /// Returns the instruction on which a memory operation depends.
   ///
   /// See the class comment for more details. It is illegal to call this on
   /// non-memory instructions.
-  MemDepResult getDependency(Instruction *QueryInst);
+  MemDepResult getDependency(Instruction *QueryInst,
+                             OrderedBasicBlock *OBB = nullptr);
 
   /// Perform a full dependency query for the specified call, returning the set
   /// of blocks that the value is potentially live across.
   ///
   /// The returned set of results will include a "NonLocal" result for all
   /// blocks where the value is live across.
   ///
   /// This method assumes the instruction returns a "NonLocal" dependency
public:
   /// the number of instructions left to examine. If a null pointer is passed
   /// in, the limit will default to the value of -memdep-block-scan-limit.
   ///
   /// Note that this is an uncached query, and thus may be inefficient.
   MemDepResult getPointerDependencyFrom(const MemoryLocation &Loc, bool isLoad,
                                         BasicBlock::iterator ScanIt,
                                         BasicBlock *BB,
                                         Instruction *QueryInst = nullptr,
-                                        unsigned *Limit = nullptr);
+                                        unsigned *Limit = nullptr,
+                                        OrderedBasicBlock *OBB = nullptr);
 
-  MemDepResult getSimplePointerDependencyFrom(const MemoryLocation &MemLoc,
-                                              bool isLoad,
-                                              BasicBlock::iterator ScanIt,
-                                              BasicBlock *BB,
-                                              Instruction *QueryInst,
-                                              unsigned *Limit = nullptr);
+  MemDepResult getSimplePointerDependencyFrom(
+      const MemoryLocation &MemLoc, bool isLoad, BasicBlock::iterator ScanIt,
+      BasicBlock *BB, Instruction *QueryInst, unsigned *Limit = nullptr,
+      OrderedBasicBlock *OBB = nullptr);
 
   /// This analysis looks for other loads and stores with invariant.group
   /// metadata and the same pointer operand. Returns Unknown if it does not
   /// find anything, and Def if it can be assumed that 2 instructions load or
   /// store the same value and NonLocal which indicate that non-local Def was
   /// found, which can be retrieved by calling getNonLocalPointerDependency
   /// with the same queried instruction.
   MemDepResult getInvariantGroupPointerDependency(LoadInst *LI, BasicBlock *BB);

llvm/lib/Analysis/MemoryDependenceAnalysis.cpp

if (auto *SI = dyn_cast<StoreInst>(Inst))
     return SI->isVolatile();
   if (auto *AI = dyn_cast<AtomicCmpXchgInst>(Inst))
     return AI->isVolatile();
   return false;
 }
 
 MemDepResult MemoryDependenceResults::getPointerDependencyFrom(
     const MemoryLocation &MemLoc, bool isLoad, BasicBlock::iterator ScanIt,
-    BasicBlock *BB, Instruction *QueryInst, unsigned *Limit) {
+    BasicBlock *BB, Instruction *QueryInst, unsigned *Limit,
+    OrderedBasicBlock *OBB) {
   MemDepResult InvariantGroupDependency = MemDepResult::getUnknown();
   if (QueryInst != nullptr) {
     if (auto *LI = dyn_cast<LoadInst>(QueryInst)) {
       InvariantGroupDependency = getInvariantGroupPointerDependency(LI, BB);
 
       if (InvariantGroupDependency.isDef())
         return InvariantGroupDependency;
     }
   }
   MemDepResult SimpleDep = getSimplePointerDependencyFrom(
-      MemLoc, isLoad, ScanIt, BB, QueryInst, Limit);
+      MemLoc, isLoad, ScanIt, BB, QueryInst, Limit, OBB);
   if (SimpleDep.isDef())
     return SimpleDep;
   // Non-local invariant group dependency indicates there is non local Def
   // (it only returns nonLocal if it finds nonLocal def), which is better than
   // local clobber and everything else.
   if (InvariantGroupDependency.isNonLocal())
     return InvariantGroupDependency;
 
NonLocalDefsCache.try_emplace(
       LI, NonLocalDepResult(ClosestDependency->getParent(),
                             MemDepResult::getDef(ClosestDependency), nullptr));
   ReverseNonLocalDefsCache[ClosestDependency].insert(LI);
   return MemDepResult::getNonLocal();
 }
 
 MemDepResult MemoryDependenceResults::getSimplePointerDependencyFrom(
     const MemoryLocation &MemLoc, bool isLoad, BasicBlock::iterator ScanIt,
-    BasicBlock *BB, Instruction *QueryInst, unsigned *Limit) {
+    BasicBlock *BB, Instruction *QueryInst, unsigned *Limit,
+    OrderedBasicBlock *OBB) {
   bool isInvariantLoad = false;
 
   if (!Limit) {
     unsigned DefaultLimit = BlockScanLimit;
     return getSimplePointerDependencyFrom(MemLoc, isLoad, ScanIt, BB, QueryInst,
-                                          &DefaultLimit);
+                                          &DefaultLimit, OBB);
   }
 
   // We must be careful with atomic accesses, as they may allow another thread
   //   to touch this location, clobbering it. We are conservative: if the
   //   QueryInst is not a simple (non-atomic) memory access, we automatically
   //   return getClobber.
   // If it is simple, we know based on the results of
   // "Compiler testing via a theory of sound optimisations in the C11/C++11
   //   memory model" in PLDI 2013, that a non-atomic location can only be
MemDepResult MemoryDependenceResults::getSimplePointerDependencyFrom(
   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
+  // If the caller did not provide an ordered basic block,
+  // create one 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);
+  OrderedBasicBlock OBBTmp(BB);
+  if (!OBB)
+    OBB = &OBBTmp;
 
   // Return "true" if and only if the instruction I is either a non-simple
   // load or a non-simple store.
   auto isNonSimpleLoadOrStore = [](Instruction *I) -> bool {
     if (auto *LI = dyn_cast<LoadInst>(I))
       return !LI->isSimple();
     if (auto *SI = dyn_cast<StoreInst>(I))
       return !SI->isSimple();
#endif
     if (FenceInst *FI = dyn_cast<FenceInst>(Inst))
       if (isLoad && FI->getOrdering() == AtomicOrdering::Release)
         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 (isModAndRefSet(MR))
-      MR = AA.callCapturesBefore(Inst, MemLoc, &DT, &OBB);
+      MR = AA.callCapturesBefore(Inst, MemLoc, &DT, OBB);
     switch (clearMust(MR)) {
     case ModRefInfo::NoModRef:
       // If the call has no effect on the queried pointer, just ignore it.
       continue;
     case ModRefInfo::Mod:
       return MemDepResult::getClobber(Inst);
     case ModRefInfo::Ref:
       // If the call is known to never store to the pointer, and if this is a
#endif
 
   // No dependence found.  If this is the entry block of the function, it is
   // unknown, otherwise it is non-local.
   if (BB != &BB->getParent()->getEntryBlock())
     return MemDepResult::getNonLocal();
   return MemDepResult::getNonFuncLocal();
 }
 
-MemDepResult MemoryDependenceResults::getDependency(Instruction *QueryInst) {
+MemDepResult MemoryDependenceResults::getDependency(Instruction *QueryInst,
+                                                    OrderedBasicBlock *OBB) {
   Instruction *ScanPos = QueryInst;
 
   // Check for a cached result
   MemDepResult &LocalCache = LocalDeps[QueryInst];
 
   // If the cached entry is non-dirty, just return it.  Note that this depends
   // on MemDepResult's default constructing to 'dirty'.
   if (!LocalCache.isDirty())
if (BasicBlock::iterator(QueryInst) == QueryParent->begin()) {
     MemoryLocation MemLoc;
     ModRefInfo MR = GetLocation(QueryInst, MemLoc, TLI);
     if (MemLoc.Ptr) {
       // If we can do a pointer scan, make it happen.
       bool isLoad = !isModSet(MR);
       if (auto *II = dyn_cast<IntrinsicInst>(QueryInst))
         isLoad |= II->getIntrinsicID() == Intrinsic::lifetime_start;
 
-      LocalCache = getPointerDependencyFrom(
-          MemLoc, isLoad, ScanPos->getIterator(), QueryParent, QueryInst);
+      LocalCache =
+          getPointerDependencyFrom(MemLoc, isLoad, ScanPos->getIterator(),
+                                   QueryParent, QueryInst, nullptr, OBB);
     } else if (auto *QueryCall = dyn_cast<CallBase>(QueryInst)) {
       bool isReadOnly = AA.onlyReadsMemory(QueryCall);
       LocalCache = getCallDependencyFrom(QueryCall, isReadOnly,
                                          ScanPos->getIterator(), QueryParent);
     } else
       // Non-memory instruction.
       LocalCache = MemDepResult::getUnknown();
   }