#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"
"Number of block queries that were completely cached");
// Limit for the number of instructions to scan in a block.
-static const int BlockScanLimit = 100;
+static const unsigned int BlockScanLimit = 100;
+
+// Limit on the number of memdep results to process.
+static const unsigned int NumResultsLimit = 100;
char MemoryDependenceAnalysis::ID = 0;
// Register this pass...
INITIALIZE_PASS_BEGIN(MemoryDependenceAnalysis, "memdep",
"Memory Dependence Analysis", false, true)
+INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
INITIALIZE_PASS_END(MemoryDependenceAnalysis, "memdep",
"Memory Dependence Analysis", false, true)
PredCache->clear();
}
-
-
/// getAnalysisUsage - Does not modify anything. It uses Alias Analysis.
///
void MemoryDependenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesAll();
+ AU.addRequired<AssumptionCacheTracker>();
AU.addRequiredTransitive<AliasAnalysis>();
}
-bool MemoryDependenceAnalysis::runOnFunction(Function &) {
+bool MemoryDependenceAnalysis::runOnFunction(Function &F) {
AA = &getAnalysis<AliasAnalysis>();
+ AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>();
DL = DLP ? &DLP->getDataLayout() : nullptr;
DominatorTreeWrapperPass *DTWP =
}
}
+static bool isVolatile(Instruction *Inst) {
+ if (LoadInst *LI = dyn_cast<LoadInst>(Inst))
+ return LI->isVolatile();
+ else if (StoreInst *SI = dyn_cast<StoreInst>(Inst))
+ return SI->isVolatile();
+ else if (AtomicCmpXchgInst *AI = dyn_cast<AtomicCmpXchgInst>(Inst))
+ return AI->isVolatile();
+ return false;
+}
+
+
/// getPointerDependencyFrom - Return the instruction on which a memory
/// location depends. If isLoad is true, this routine ignores may-aliases with
/// read-only operations. If isLoad is false, this routine ignores may-aliases
}
// Walk backwards through the basic block, looking for dependencies.
- while (ScanIt != BB->begin()) {
+ // We can stop before processing PHIs or dbg intrinsics.
+ const BasicBlock::iterator Begin(BB->getFirstNonPHIOrDbg());
+ while (ScanIt != Begin) {
Instruction *Inst = --ScanIt;
if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst))
// does not alias with when this atomic load indicates that another thread may
// be accessing the location.
if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
+
+ // While volatile access cannot be eliminated, they do not have to clobber
+ // non-aliasing locations, as normal accesses, for example, can be safely
+ // reordered with volatile accesses.
+ if (LI->isVolatile()) {
+ if (!QueryInst)
+ // Original QueryInst *may* be volatile
+ return MemDepResult::getClobber(LI);
+ if (isVolatile(QueryInst))
+ // Ordering required if QueryInst is itself volatile
+ return MemDepResult::getClobber(LI);
+ // Otherwise, volatile doesn't imply any special ordering
+ }
+
// Atomic loads have complications involved.
// A Monotonic (or higher) load is OK if the query inst is itself not atomic.
// An Acquire (or higher) load sets the HasSeenAcquire flag, so that any
// release store will know to return getClobber.
// FIXME: This is overly conservative.
- if (!LI->isUnordered()) {
+ if (LI->isAtomic() && LI->getOrdering() > Unordered) {
if (!QueryInst)
return MemDepResult::getClobber(LI);
- if (auto *QueryLI = dyn_cast<LoadInst>(QueryInst))
+ if (auto *QueryLI = dyn_cast<LoadInst>(QueryInst)) {
if (!QueryLI->isSimple())
return MemDepResult::getClobber(LI);
- if (auto *QuerySI = dyn_cast<StoreInst>(QueryInst))
+ } else if (auto *QuerySI = dyn_cast<StoreInst>(QueryInst)) {
if (!QuerySI->isSimple())
return MemDepResult::getClobber(LI);
+ } else if (QueryInst->mayReadOrWriteMemory()) {
+ return MemDepResult::getClobber(LI);
+ }
+
if (isAtLeastAcquire(LI->getOrdering()))
HasSeenAcquire = true;
}
- // FIXME: this is overly conservative.
- // While volatile access cannot be eliminated, they do not have to clobber
- // non-aliasing locations, as normal accesses can for example be reordered
- // with volatile accesses.
- if (LI->isVolatile())
- return MemDepResult::getClobber(LI);
-
AliasAnalysis::Location LoadLoc = AA->getLocation(LI);
// If we found a pointer, check if it could be the same as our pointer.
if (!SI->isUnordered()) {
if (!QueryInst)
return MemDepResult::getClobber(SI);
- if (auto *QueryLI = dyn_cast<LoadInst>(QueryInst))
+ if (auto *QueryLI = dyn_cast<LoadInst>(QueryInst)) {
if (!QueryLI->isSimple())
return MemDepResult::getClobber(SI);
- if (auto *QuerySI = dyn_cast<StoreInst>(QueryInst))
+ } else if (auto *QuerySI = dyn_cast<StoreInst>(QueryInst)) {
if (!QuerySI->isSimple())
return MemDepResult::getClobber(SI);
+ } else if (QueryInst->mayReadOrWriteMemory()) {
+ return MemDepResult::getClobber(SI);
+ }
+
if (HasSeenAcquire && isAtLeastRelease(SI->getOrdering()))
return MemDepResult::getClobber(SI);
}
DirtyBlocks.pop_back();
// Already processed this block?
- if (!Visited.insert(DirtyBB))
+ if (!Visited.insert(DirtyBB).second)
continue;
// Do a binary search to see if we already have an entry for this block in
/// own block.
///
void MemoryDependenceAnalysis::
-getNonLocalPointerDependency(const AliasAnalysis::Location &Loc, bool isLoad,
- BasicBlock *FromBB,
+getNonLocalPointerDependency(Instruction *QueryInst,
SmallVectorImpl<NonLocalDepResult> &Result) {
+
+ auto getLocation = [](AliasAnalysis *AA, Instruction *Inst) {
+ if (auto *I = dyn_cast<LoadInst>(Inst))
+ return AA->getLocation(I);
+ else if (auto *I = dyn_cast<StoreInst>(Inst))
+ return AA->getLocation(I);
+ else if (auto *I = dyn_cast<VAArgInst>(Inst))
+ return AA->getLocation(I);
+ else if (auto *I = dyn_cast<AtomicCmpXchgInst>(Inst))
+ return AA->getLocation(I);
+ else if (auto *I = dyn_cast<AtomicRMWInst>(Inst))
+ return AA->getLocation(I);
+ else
+ llvm_unreachable("unsupported memory instruction");
+ };
+
+ const AliasAnalysis::Location Loc = getLocation(AA, QueryInst);
+ bool isLoad = isa<LoadInst>(QueryInst);
+ BasicBlock *FromBB = QueryInst->getParent();
+ assert(FromBB);
+
assert(Loc.Ptr->getType()->isPointerTy() &&
"Can't get pointer deps of a non-pointer!");
Result.clear();
+
+ // This routine does not expect to deal with volatile instructions.
+ // Doing so would require piping through the QueryInst all the way through.
+ // TODO: volatiles can't be elided, but they can be reordered with other
+ // non-volatile accesses.
+
+ // We currently give up on any instruction which is ordered, but we do handle
+ // atomic instructions which are unordered.
+ // TODO: Handle ordered instructions
+ auto isOrdered = [](Instruction *Inst) {
+ if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
+ return !LI->isUnordered();
+ } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
+ return !SI->isUnordered();
+ }
+ return false;
+ };
+ if (isVolatile(QueryInst) || isOrdered(QueryInst)) {
+ Result.push_back(NonLocalDepResult(FromBB,
+ MemDepResult::getUnknown(),
+ const_cast<Value *>(Loc.Ptr)));
+ return;
+ }
- PHITransAddr Address(const_cast<Value *>(Loc.Ptr), DL);
+
+ PHITransAddr Address(const_cast<Value *>(Loc.Ptr), DL, AC);
// This is the set of blocks we've inspected, and the pointer we consider in
// each block. Because of critical edges, we currently bail out if querying
// a block with multiple different pointers. This can happen during PHI
// translation.
DenseMap<BasicBlock*, Value*> Visited;
- if (!getNonLocalPointerDepFromBB(Address, Loc, isLoad, FromBB,
+ if (!getNonLocalPointerDepFromBB(QueryInst, Address, Loc, isLoad, FromBB,
Result, Visited, true))
return;
Result.clear();
/// lookup (which may use dirty cache info if available). If we do a lookup,
/// add the result to the cache.
MemDepResult MemoryDependenceAnalysis::
-GetNonLocalInfoForBlock(const AliasAnalysis::Location &Loc,
+GetNonLocalInfoForBlock(Instruction *QueryInst,
+ const AliasAnalysis::Location &Loc,
bool isLoad, BasicBlock *BB,
NonLocalDepInfo *Cache, unsigned NumSortedEntries) {
}
// Scan the block for the dependency.
- MemDepResult Dep = getPointerDependencyFrom(Loc, isLoad, ScanPos, BB);
+ MemDepResult Dep = getPointerDependencyFrom(Loc, isLoad, ScanPos, BB,
+ QueryInst);
// If we had a dirty entry for the block, update it. Otherwise, just add
// a new entry.
/// not compute dependence information for some reason. This should be treated
/// as a clobber dependence on the first instruction in the predecessor block.
bool MemoryDependenceAnalysis::
-getNonLocalPointerDepFromBB(const PHITransAddr &Pointer,
+getNonLocalPointerDepFromBB(Instruction *QueryInst,
+ const PHITransAddr &Pointer,
const AliasAnalysis::Location &Loc,
bool isLoad, BasicBlock *StartBB,
SmallVectorImpl<NonLocalDepResult> &Result,
} else if (CacheInfo->Size > Loc.Size) {
// This query's Size is less than the cached one. Conservatively restart
// the query using the greater size.
- return getNonLocalPointerDepFromBB(Pointer,
+ return getNonLocalPointerDepFromBB(QueryInst, Pointer,
Loc.getWithNewSize(CacheInfo->Size),
isLoad, StartBB, Result, Visited,
SkipFirstBlock);
CacheInfo->NonLocalDeps.clear();
}
if (Loc.AATags)
- return getNonLocalPointerDepFromBB(Pointer, Loc.getWithoutAATags(),
+ return getNonLocalPointerDepFromBB(QueryInst,
+ Pointer, Loc.getWithoutAATags(),
isLoad, StartBB, Result, Visited,
SkipFirstBlock);
}
while (!Worklist.empty()) {
BasicBlock *BB = Worklist.pop_back_val();
+ // If we do process a large number of blocks it becomes very expensive and
+ // likely it isn't worth worrying about
+ if (Result.size() > NumResultsLimit) {
+ Worklist.clear();
+ // Sort it now (if needed) so that recursive invocations of
+ // getNonLocalPointerDepFromBB and other routines that could reuse the
+ // cache value will only see properly sorted cache arrays.
+ if (Cache && NumSortedEntries != Cache->size()) {
+ SortNonLocalDepInfoCache(*Cache, NumSortedEntries);
+ }
+ // Since we bail out, the "Cache" set won't contain all of the
+ // results for the query. This is ok (we can still use it to accelerate
+ // specific block queries) but we can't do the fastpath "return all
+ // results from the set". Clear out the indicator for this.
+ CacheInfo->Pair = BBSkipFirstBlockPair();
+ return true;
+ }
+
// Skip the first block if we have it.
if (!SkipFirstBlock) {
// Analyze the dependency of *Pointer in FromBB. See if we already have
// Get the dependency info for Pointer in BB. If we have cached
// information, we will use it, otherwise we compute it.
DEBUG(AssertSorted(*Cache, NumSortedEntries));
- MemDepResult Dep = GetNonLocalInfoForBlock(Loc, isLoad, BB, Cache,
+ MemDepResult Dep = GetNonLocalInfoForBlock(QueryInst,
+ Loc, isLoad, BB, Cache,
NumSortedEntries);
// If we got a Def or Clobber, add this to the list of results.
// result conflicted with the Visited list; we have to conservatively
// assume it is unknown, but this also does not block PRE of the load.
if (!CanTranslate ||
- getNonLocalPointerDepFromBB(PredPointer,
+ getNonLocalPointerDepFromBB(QueryInst, PredPointer,
Loc.getWithNewPtr(PredPtrVal),
isLoad, Pred,
Result, Visited)) {
if (I->getBB() != BB)
continue;
- assert(I->getResult().isNonLocal() &&
+ assert((I->getResult().isNonLocal() || !DT->isReachableFromEntry(BB)) &&
"Should only be here with transparent block");
I->setResult(MemDepResult::getUnknown());
Result.push_back(NonLocalDepResult(I->getBB(), I->getResult(),
projects / oota-llvm.git / blobdiff