[CaptureTracker] Provide an ordered basic block to PointerMayBeCapturedBefore
This patch is a follow up from r240560 and is a step further into
mitigating the compile time performance issues in CaptureTracker.
By providing the CaptureTracker with a "cached ordered basic block"
instead of computing it every time, MemDepAnalysis can use this cache
throughout its calls to AA->callCapturesBefore, avoiding to recompute it
for every scanned instruction. In the same testcase used in r240560,
compile time is reduced from 2min to 30s.
This also fixes PR22348.
rdar://problem/19230319
Differential Revision: http://reviews.llvm.org/D11364
llvm-svn: 243750
diff --git a/llvm/lib/Analysis/AliasAnalysis.cpp b/llvm/lib/Analysis/AliasAnalysis.cpp
index 22ef773..9e69342 100644
--- a/llvm/lib/Analysis/AliasAnalysis.cpp
+++ b/llvm/lib/Analysis/AliasAnalysis.cpp
@@ -335,13 +335,18 @@
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;
@@ -356,7 +361,8 @@
if (llvm::PointerMayBeCapturedBefore(Object, /* ReturnCaptures */ true,
/* StoreCaptures */ true, I, DT,
- /* include Object */ true))
+ /* include Object */ true,
+ /* OrderedBasicBlock */ OBB))
return MRI_ModRef;
unsigned ArgNo = 0;
diff --git a/llvm/lib/Analysis/CMakeLists.txt b/llvm/lib/Analysis/CMakeLists.txt
index 3ec79ad..399c0e7 100644
--- a/llvm/lib/Analysis/CMakeLists.txt
+++ b/llvm/lib/Analysis/CMakeLists.txt
@@ -45,6 +45,7 @@
MemoryLocation.cpp
ModuleDebugInfoPrinter.cpp
NoAliasAnalysis.cpp
+ OrderedBasicBlock.cpp
PHITransAddr.cpp
PostDominators.cpp
PtrUseVisitor.cpp
diff --git a/llvm/lib/Analysis/CaptureTracking.cpp b/llvm/lib/Analysis/CaptureTracking.cpp
index 52ef807..fc23aa5 100644
--- a/llvm/lib/Analysis/CaptureTracking.cpp
+++ b/llvm/lib/Analysis/CaptureTracking.cpp
@@ -21,6 +21,7 @@
#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"
@@ -52,63 +53,6 @@
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
@@ -116,8 +60,8 @@
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; }
@@ -131,7 +75,7 @@
// 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.
@@ -142,7 +86,7 @@
// 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
@@ -196,7 +140,7 @@
return true;
}
- NumberedInstCache LocalInstCache;
+ OrderedBasicBlock *OrderedBB;
const Instruction *BeforeHere;
DominatorTree *DT;
@@ -238,21 +182,29 @@
/// 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;
}
diff --git a/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp b/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp
index 5ac6fdf..54ac1b6 100644
--- a/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp
+++ b/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp
@@ -22,6 +22,7 @@
#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"
@@ -420,6 +421,12 @@
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;
@@ -623,7 +630,7 @@
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.
diff --git a/llvm/lib/Analysis/OrderedBasicBlock.cpp b/llvm/lib/Analysis/OrderedBasicBlock.cpp
new file mode 100644
index 0000000..0f0016f
--- /dev/null
+++ b/llvm/lib/Analysis/OrderedBasicBlock.cpp
@@ -0,0 +1,85 @@
+//===- 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);
+}