Index: include/llvm/Analysis/MemoryLocation.h =================================================================== --- include/llvm/Analysis/MemoryLocation.h +++ include/llvm/Analysis/MemoryLocation.h @@ -160,6 +160,21 @@ return OS; } +enum MemoryLocationFlags { + /// The memory location is known to be a local object in the function. + MLK_KnownToBeLocalObject = 1, + /// The memory location is known to be (or possibly be) a non-local object in + /// the function. + MLK_KnownCouldBeNonLocalObject = 2, + /// The memory location is known to not escape the function. The minimum + /// standard for this flag to be permissible is that PointerMayBeCaptured(V, + /// false, true) must be false. It's acceptable to be more conservative than + /// that at the cost of pessimizing the analysis but not less conservative. + MLK_KnownToBeNonEscaping = 4, + /// The memory location may possibly escape from the function. + MLK_KnownMayEscape = 8, +}; + /// Representation for a specific memory location. /// /// This abstraction can be used to represent a specific location in memory. @@ -192,6 +207,14 @@ /// member is null if that kind of information is unavailable). AAMDNodes AATags; + /// Some things are rather expensive to discover by analyses such as AA and we + /// should minimize the frequency with which we query them. We can inform such + /// analyses that something is already known through these flags. + /// + /// One example of an expensive check that we may already know the result of + /// is the isNonEscapingLocalObject() that AA uses. + uint8_t KnownFlags = 0; + /// Return a location with information about the memory reference by the given /// instruction. static MemoryLocation get(const LoadInst *LI); @@ -261,6 +284,17 @@ return Copy; } + bool isKnownToBeLocalObject() const { + return KnownFlags & MLK_KnownToBeLocalObject; + } + bool isKnownCouldBeNonLocalObject() const { + return KnownFlags & MLK_KnownCouldBeNonLocalObject; + } + bool isKnownToBeNonEscaping() const { + return KnownFlags & MLK_KnownToBeNonEscaping; + } + bool isKnownMayEscape() const { return KnownFlags & MLK_KnownMayEscape; } + bool operator==(const MemoryLocation &Other) const { return Ptr == Other.Ptr && Size == Other.Size && AATags == Other.AATags; } Index: lib/Analysis/BasicAliasAnalysis.cpp =================================================================== --- lib/Analysis/BasicAliasAnalysis.cpp +++ lib/Analysis/BasicAliasAnalysis.cpp @@ -812,11 +812,19 @@ !CI->getAttributes().hasAttrSomewhere(Attribute::ByVal)) return ModRefInfo::NoModRef; + assert( + (!Loc.isKnownToBeLocalObject() || !Loc.isKnownCouldBeNonLocalObject()) && + "Location cannot be both known local and known non-local"); + assert((!Loc.isKnownToBeNonEscaping() || !Loc.isKnownMayEscape()) && + "Location cannot be both known non escaping and known it may escape"); + // If the pointer is to a locally allocated object that does not escape, // then the call can not mod/ref the pointer unless the call takes the pointer // as an argument, and itself doesn't capture it. if (!isa(Object) && CS.getInstruction() != Object && - isNonEscapingLocalObject(Object)) { + ((Loc.isKnownToBeLocalObject() && Loc.isKnownToBeNonEscaping()) || + (!Loc.isKnownCouldBeNonLocalObject() && !Loc.isKnownMayEscape() && + isNonEscapingLocalObject(Object)))) { // Optimistically assume that call doesn't touch Object and check this // assumption in the following loop. Index: lib/Transforms/Scalar/DeadStoreElimination.cpp =================================================================== --- lib/Transforms/Scalar/DeadStoreElimination.cpp +++ lib/Transforms/Scalar/DeadStoreElimination.cpp @@ -746,11 +746,11 @@ /// ... /// store i32 1, i32* %A /// ret void -static bool handleEndBlock(BasicBlock &BB, AliasAnalysis *AA, - MemoryDependenceResults *MD, - const TargetLibraryInfo *TLI, - InstOverlapIntervalsTy &IOL, - DenseMap *InstrOrdering) { +static bool +handleEndBlock(BasicBlock &BB, AliasAnalysis *AA, MemoryDependenceResults *MD, + const TargetLibraryInfo *TLI, InstOverlapIntervalsTy &IOL, + DenseMap *InstrOrdering, + DenseMap &CachedMemLocFlags) { bool MadeChange = false; // Keep track of all of the stack objects that are dead at the end of the @@ -760,13 +760,31 @@ // Find all of the alloca'd pointers in the entry block. BasicBlock &Entry = BB.getParent()->front(); for (Instruction &I : Entry) { - if (isa(&I)) + if (isa(&I)) { DeadStackObjects.insert(&I); + if (CachedMemLocFlags.count(&I) == 0) { + unsigned KnownFlags = MLK_KnownToBeLocalObject; + // If it's an alloca and we already know that the functions we call + // can't possibly load via a pointer (whether via args or indirectly) + // then we know it's not escaping into any of the functions we're going + // to call. Setting this flag and providing it to AA->getModRefInfo() + // will prevent AA from re-discovering this fact for every call site and + // alloca. This can be a significant saving in compile time when there's + // lots of allocas and lots of noreturn functions (e.g. assert) + KnownFlags |= PointerMayBeCaptured(&I, false, true) + ? MLK_KnownMayEscape + : MLK_KnownToBeNonEscaping; + CachedMemLocFlags[&I] = (MemoryLocationFlags)KnownFlags; + } + } // Okay, so these are dead heap objects, but if the pointer never escapes // then it's leaked by this function anyways. - else if (isAllocLikeFn(&I, TLI) && !PointerMayBeCaptured(&I, true, true)) + else if (isAllocLikeFn(&I, TLI) && !PointerMayBeCaptured(&I, true, true)) { DeadStackObjects.insert(&I); + CachedMemLocFlags[&I] = (MemoryLocationFlags)(MLK_KnownToBeLocalObject | + MLK_KnownToBeNonEscaping); + } } // Treat byval or inalloca arguments the same, stores to them are dead at the @@ -849,8 +867,13 @@ // the call is live. DeadStackObjects.remove_if([&](Value *I) { // See if the call site touches the value. - return isRefSet(AA->getModRefInfo(CS, I, getPointerSize(I, DL, *TLI, - BB.getParent()))); + MemoryLocation Loc(I, getPointerSize(I, DL, *TLI, BB.getParent())); + + const auto &MemLocFlags = CachedMemLocFlags.find(I); + if (MemLocFlags != CachedMemLocFlags.end()) + Loc.KnownFlags = MemLocFlags->second; + + return isRefSet(AA->getModRefInfo(CS, Loc)); }); // If all of the allocas were clobbered by the call then we're not going @@ -1067,9 +1090,11 @@ return false; } -static bool eliminateDeadStores(BasicBlock &BB, AliasAnalysis *AA, - MemoryDependenceResults *MD, DominatorTree *DT, - const TargetLibraryInfo *TLI) { +static bool +eliminateDeadStores(BasicBlock &BB, AliasAnalysis *AA, + MemoryDependenceResults *MD, DominatorTree *DT, + const TargetLibraryInfo *TLI, + DenseMap &CachedMemLocFlags) { const DataLayout &DL = BB.getModule()->getDataLayout(); bool MadeChange = false; @@ -1303,23 +1328,44 @@ if (EnablePartialOverwriteTracking) MadeChange |= removePartiallyOverlappedStores(AA, DL, IOL); + // Flushing the cache in response to changes isn't particularly urgent since + // stale data is conservatively correct because: + // * A non-escaping local is still non-escaping so long as we don't + // introduce new methods of capturing/escaping. + // * An escaping local may become non-escaping as a result of the + // deletion/rewrite. + // + // That said, we flush it here because handleEndBlock() is about to use the + // cache and we want to discover any newly non-escaping objects. + if (MadeChange) + CachedMemLocFlags.clear(); + + bool MadeChangeInHandleEndBlock = false; // If this block ends in a return, unwind, or unreachable, all allocas are // dead at its end, which means stores to them are also dead. - if (BB.getTerminator()->getNumSuccessors() == 0) - MadeChange |= handleEndBlock(BB, AA, MD, TLI, IOL, &InstrOrdering); + if (BB.getTerminator()->getNumSuccessors() == 0) { + MadeChangeInHandleEndBlock = + handleEndBlock(BB, AA, MD, TLI, IOL, &InstrOrdering, CachedMemLocFlags); + MadeChange |= MadeChangeInHandleEndBlock; + } + + // Also flush it if handleEndBlock made a change. + if (MadeChangeInHandleEndBlock) + CachedMemLocFlags.clear(); return MadeChange; } -static bool eliminateDeadStores(Function &F, AliasAnalysis *AA, - MemoryDependenceResults *MD, DominatorTree *DT, - const TargetLibraryInfo *TLI) { +static bool +eliminateDeadStores(Function &F, AliasAnalysis *AA, MemoryDependenceResults *MD, + DominatorTree *DT, const TargetLibraryInfo *TLI, + DenseMap &CachedMemLocFlags) { bool MadeChange = false; for (BasicBlock &BB : F) // Only check non-dead blocks. Dead blocks may have strange pointer // cycles that will confuse alias analysis. if (DT->isReachableFromEntry(&BB)) - MadeChange |= eliminateDeadStores(BB, AA, MD, DT, TLI); + MadeChange |= eliminateDeadStores(BB, AA, MD, DT, TLI, CachedMemLocFlags); return MadeChange; } @@ -1333,7 +1379,8 @@ MemoryDependenceResults *MD = &AM.getResult(F); const TargetLibraryInfo *TLI = &AM.getResult(F); - if (!eliminateDeadStores(F, AA, MD, DT, TLI)) + DenseMap CachedMemLocFlags; + if (!eliminateDeadStores(F, AA, MD, DT, TLI, CachedMemLocFlags)) return PreservedAnalyses::all(); PreservedAnalyses PA; @@ -1365,7 +1412,8 @@ const TargetLibraryInfo *TLI = &getAnalysis().getTLI(); - return eliminateDeadStores(F, AA, MD, DT, TLI); + DenseMap CachedMemLocFlags; + return eliminateDeadStores(F, AA, MD, DT, TLI, CachedMemLocFlags); } void getAnalysisUsage(AnalysisUsage &AU) const override {