Index: lib/Transforms/Utils/MemorySSA.cpp =================================================================== --- lib/Transforms/Utils/MemorySSA.cpp +++ lib/Transforms/Utils/MemorySSA.cpp @@ -323,58 +323,6 @@ AA.pointsToConstantMemory(I)); } -/// Cache for our caching MemorySSA walker. -class WalkerCache { - DenseMap Accesses; - DenseMap Calls; - -public: - MemoryAccess *lookup(const MemoryAccess *MA, const MemoryLocation &Loc, - bool IsCall) const { - ++NumClobberCacheLookups; - MemoryAccess *R = IsCall ? Calls.lookup(MA) : Accesses.lookup({MA, Loc}); - if (R) - ++NumClobberCacheHits; - return R; - } - - bool insert(const MemoryAccess *MA, MemoryAccess *To, - const MemoryLocation &Loc, bool IsCall) { - // This is fine for Phis, since there are times where we can't optimize - // them. Making a def its own clobber is never correct, though. - assert((MA != To || isa(MA)) && - "Something can't clobber itself!"); - - ++NumClobberCacheInserts; - bool Inserted; - if (IsCall) - Inserted = Calls.insert({MA, To}).second; - else - Inserted = Accesses.insert({{MA, Loc}, To}).second; - - return Inserted; - } - - bool remove(const MemoryAccess *MA, const MemoryLocation &Loc, bool IsCall) { - return IsCall ? Calls.erase(MA) : Accesses.erase({MA, Loc}); - } - - void clear() { - Accesses.clear(); - Calls.clear(); - } - - bool contains(const MemoryAccess *MA) const { - for (auto &P : Accesses) - if (P.first.first == MA || P.second == MA) - return true; - for (auto &P : Calls) - if (P.first == MA || P.second == MA) - return true; - return false; - } -}; - /// Verifies that `Start` is clobbered by `ClobberAt`, and that nothing /// inbetween `Start` and `ClobberAt` can clobbers `Start`. /// @@ -476,50 +424,12 @@ const MemorySSA &MSSA; AliasAnalysis &AA; DominatorTree &DT; - WalkerCache &WC; UpwardsMemoryQuery *Query; - bool UseCache; // Phi optimization bookkeeping SmallVector Paths; DenseSet VisitedPhis; - void setUseCache(bool Use) { UseCache = Use; } - bool shouldIgnoreCache() const { - // UseCache will only be false when we're debugging, or when expensive - // checks are enabled. In either case, we don't care deeply about speed. - return LLVM_UNLIKELY(!UseCache); - } - - void addCacheEntry(const MemoryAccess *What, MemoryAccess *To, - const MemoryLocation &Loc) const { -// EXPENSIVE_CHECKS because most of these queries are redundant. -#ifdef EXPENSIVE_CHECKS - assert(MSSA.dominates(To, What)); -#endif - if (shouldIgnoreCache()) - return; - WC.insert(What, To, Loc, Query->IsCall); - } - - MemoryAccess *lookupCache(const MemoryAccess *MA, - const MemoryLocation &Loc) const { - return shouldIgnoreCache() ? nullptr : WC.lookup(MA, Loc, Query->IsCall); - } - - void cacheDefPath(const DefPath &DN, MemoryAccess *Target) const { - if (shouldIgnoreCache()) - return; - - for (MemoryAccess *MA : def_chain(DN.First, DN.Last)) - addCacheEntry(MA, Target, DN.Loc); - - // DefPaths only express the path we walked. So, DN.Last could either be a - // thing we want to cache, or not. - if (DN.Last != Target) - addCacheEntry(DN.Last, Target, DN.Loc); - } - /// Find the nearest def or phi that `From` can legally be optimized to. const MemoryAccess *getWalkTarget(const MemoryPhi *From) const { assert(From->getNumOperands() && "Phi with no operands?"); @@ -541,7 +451,6 @@ /// both. MemoryAccess *Result; bool IsKnownClobber; - bool FromCache; }; /// Walk to the next Phi or Clobber in the def chain starting at Desc.Last. @@ -557,22 +466,17 @@ for (MemoryAccess *Current : def_chain(Desc.Last)) { Desc.Last = Current; if (Current == StopAt) - return {Current, false, false}; + return {Current, false}; if (auto *MD = dyn_cast(Current)) if (MSSA.isLiveOnEntryDef(MD) || instructionClobbersQuery(MD, Desc.Loc, Query->Inst, AA)) - return {MD, true, false}; - - // Cache checks must be done last, because if Current is a clobber, the - // cache will contain the clobber for Current. - if (MemoryAccess *MA = lookupCache(Current, Desc.Loc)) - return {MA, true, true}; + return {MD, true}; } assert(isa(Desc.Last) && "Ended at a non-clobber that's not a phi?"); - return {Desc.Last, false, false}; + return {Desc.Last, false}; } void addSearches(MemoryPhi *Phi, SmallVectorImpl &PausedSearches, @@ -637,11 +541,11 @@ UpwardsWalkResult Res = walkToPhiOrClobber(Node, /*StopAt=*/StopWhere); if (Res.IsKnownClobber) { - assert(Res.Result != StopWhere || Res.FromCache); + assert(Res.Result != StopWhere); // If this wasn't a cache hit, we hit a clobber when walking. That's a // failure. TerminatedPath Term{Res.Result, PathIndex}; - if (!Res.FromCache || !MSSA.dominates(Res.Result, StopWhere)) + if (!MSSA.dominates(Res.Result, StopWhere)) return Term; // Otherwise, it's a valid thing to potentially optimize to. @@ -778,8 +682,6 @@ // For the moment, this is fine, since we do nothing with blocker info. if (Optional Blocker = getBlockingAccess( Target, PausedSearches, NewPaused, TerminatedPaths)) { - // Cache our work on the blocking node, since we know that's correct. - cacheDefPath(Paths[Blocker->LastNode], Blocker->Clobber); // Find the node we started at. We can't search based on N->Last, since // we may have gone around a loop with a different MemoryLocation. @@ -882,35 +784,6 @@ } } - /// Caches everything in an OptznResult. - void cacheOptResult(const OptznResult &R) { - if (R.OtherClobbers.empty()) { - // If we're not going to be caching OtherClobbers, don't bother with - // marking visited/etc. - for (const DefPath &N : const_def_path(R.PrimaryClobber.LastNode)) - cacheDefPath(N, R.PrimaryClobber.Clobber); - return; - } - - // PrimaryClobber is our answer. If we can cache anything back, we need to - // stop caching when we visit PrimaryClobber. - SmallBitVector Visited(Paths.size()); - for (const DefPath &N : const_def_path(R.PrimaryClobber.LastNode)) { - Visited[defPathIndex(N)] = true; - cacheDefPath(N, R.PrimaryClobber.Clobber); - } - - for (const TerminatedPath &P : R.OtherClobbers) { - for (const DefPath &N : const_def_path(P.LastNode)) { - ListIndex NIndex = defPathIndex(N); - if (Visited[NIndex]) - break; - Visited[NIndex] = true; - cacheDefPath(N, P.Clobber); - } - } - } - void verifyOptResult(const OptznResult &R) const { assert(all_of(R.OtherClobbers, [&](const TerminatedPath &P) { return MSSA.dominates(P.Clobber, R.PrimaryClobber.Clobber); @@ -923,17 +796,14 @@ } public: - ClobberWalker(const MemorySSA &MSSA, AliasAnalysis &AA, DominatorTree &DT, - WalkerCache &WC) - : MSSA(MSSA), AA(AA), DT(DT), WC(WC), UseCache(true) {} + ClobberWalker(const MemorySSA &MSSA, AliasAnalysis &AA, DominatorTree &DT) + : MSSA(MSSA), AA(AA), DT(DT) {} void reset() {} /// Finds the nearest clobber for the given query, optimizing phis if /// possible. - MemoryAccess *findClobber(MemoryAccess *Start, UpwardsMemoryQuery &Q, - bool UseWalkerCache = true) { - setUseCache(UseWalkerCache); + MemoryAccess *findClobber(MemoryAccess *Start, UpwardsMemoryQuery &Q) { Query = &Q; MemoryAccess *Current = Start; @@ -948,13 +818,11 @@ UpwardsWalkResult WalkResult = walkToPhiOrClobber(FirstDesc); MemoryAccess *Result; if (WalkResult.IsKnownClobber) { - cacheDefPath(FirstDesc, WalkResult.Result); Result = WalkResult.Result; } else { OptznResult OptRes = tryOptimizePhi(cast(FirstDesc.Last), Current, Q.StartingLoc); verifyOptResult(OptRes); - cacheOptResult(OptRes); resetPhiOptznState(); Result = OptRes.PrimaryClobber.Clobber; } @@ -1019,7 +887,6 @@ /// ret i32 %r /// } class MemorySSA::CachingWalker final : public MemorySSAWalker { - WalkerCache Cache; ClobberWalker Walker; bool AutoResetWalker; @@ -2084,11 +1951,12 @@ MemorySSA::CachingWalker::CachingWalker(MemorySSA *M, AliasAnalysis *A, DominatorTree *D) - : MemorySSAWalker(M), Walker(*M, *A, *D, Cache), AutoResetWalker(true) {} + : MemorySSAWalker(M), Walker(*M, *A, *D), AutoResetWalker(true) {} MemorySSA::CachingWalker::~CachingWalker() {} void MemorySSA::CachingWalker::invalidateInfo(MemoryAccess *MA) { +#if 0 // TODO: We can do much better cache invalidation with differently stored // caches. For now, for MemoryUses, we simply remove them // from the cache, and kill the entire call/non-call cache for everything @@ -2109,9 +1977,6 @@ // If it is not a use, the best we can do right now is destroy the cache. Cache.clear(); } - -#ifdef EXPENSIVE_CHECKS - verifyRemoved(MA); #endif } @@ -2123,8 +1988,7 @@ MemoryAccess *StartingAccess, UpwardsMemoryQuery &Q) { MemoryAccess *New = Walker.findClobber(StartingAccess, Q); #ifdef EXPENSIVE_CHECKS - MemoryAccess *NewNoCache = - Walker.findClobber(StartingAccess, Q, /*UseWalkerCache=*/false); + MemoryAccess *NewNoCache = Walker.findClobber(StartingAccess, Q); assert(NewNoCache == New && "Cache made us hand back a different result?"); #endif if (AutoResetWalker) @@ -2154,9 +2018,6 @@ Q.Inst = I; Q.IsCall = false; - if (auto *CacheResult = Cache.lookup(StartingUseOrDef, Loc, Q.IsCall)) - return CacheResult; - // Unlike the other function, do not walk to the def of a def, because we are // handed something we already believe is the clobbering access. MemoryAccess *DefiningAccess = isa(StartingUseOrDef) @@ -2193,12 +2054,8 @@ if (!Q.IsCall && I->isFenceLike()) return StartingAccess; - if (auto *CacheResult = Cache.lookup(StartingAccess, Q.StartingLoc, Q.IsCall)) - return CacheResult; - if (isUseTriviallyOptimizableToLiveOnEntry(*MSSA->AA, I)) { MemoryAccess *LiveOnEntry = MSSA->getLiveOnEntryDef(); - Cache.insert(StartingAccess, LiveOnEntry, Q.StartingLoc, Q.IsCall); if (auto *MUD = dyn_cast(StartingAccess)) MUD->setDefiningAccess(LiveOnEntry, true); return LiveOnEntry; @@ -2223,11 +2080,6 @@ return Result; } -// Verify that MA doesn't exist in any of the caches. -void MemorySSA::CachingWalker::verifyRemoved(MemoryAccess *MA) { - assert(!Cache.contains(MA) && "Found removed MemoryAccess in cache."); -} - MemoryAccess * DoNothingMemorySSAWalker::getClobberingMemoryAccess(MemoryAccess *MA) { if (auto *Use = dyn_cast(MA))