summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Utils/MemorySSA.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/lib/Transforms/Utils/MemorySSA.cpp')
-rw-r--r--llvm/lib/Transforms/Utils/MemorySSA.cpp134
1 files changed, 100 insertions, 34 deletions
diff --git a/llvm/lib/Transforms/Utils/MemorySSA.cpp b/llvm/lib/Transforms/Utils/MemorySSA.cpp
index 7cff51e9866..7fe7f08059a 100644
--- a/llvm/lib/Transforms/Utils/MemorySSA.cpp
+++ b/llvm/lib/Transforms/Utils/MemorySSA.cpp
@@ -10,7 +10,6 @@
// This file implements the MemorySSA class.
//
//===----------------------------------------------------------------===//
-#include "llvm/Transforms/Utils/MemorySSA.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/DepthFirstIterator.h"
@@ -39,6 +38,7 @@
#include "llvm/Support/Debug.h"
#include "llvm/Support/FormattedStream.h"
#include "llvm/Transforms/Scalar.h"
+#include "llvm/Transforms/Utils/MemorySSA.h"
#include <algorithm>
#define DEBUG_TYPE "memoryssa"
@@ -55,7 +55,6 @@ INITIALIZE_PASS_END(MemorySSAWrapperPass, "memoryssa", "Memory SSA", false,
true)
namespace llvm {
-
/// \brief An assembly annotator class to print Memory SSA information in
/// comments.
class MemorySSAAnnotatedWriter : public AssemblyAnnotationWriter {
@@ -77,6 +76,74 @@ public:
OS << "; " << *MA << "\n";
}
};
+
+/// \brief A MemorySSAWalker that does AA walks and caching of lookups to
+/// disambiguate accesses.
+///
+/// FIXME: The current implementation of this can take quadratic space in rare
+/// cases. This can be fixed, but it is something to note until it is fixed.
+///
+/// In order to trigger this behavior, you need to store to N distinct locations
+/// (that AA can prove don't alias), perform M stores to other memory
+/// locations that AA can prove don't alias any of the initial N locations, and
+/// then load from all of the N locations. In this case, we insert M cache
+/// entries for each of the N loads.
+///
+/// For example:
+/// define i32 @foo() {
+/// %a = alloca i32, align 4
+/// %b = alloca i32, align 4
+/// store i32 0, i32* %a, align 4
+/// store i32 0, i32* %b, align 4
+///
+/// ; Insert M stores to other memory that doesn't alias %a or %b here
+///
+/// %c = load i32, i32* %a, align 4 ; Caches M entries in
+/// ; CachedUpwardsClobberingAccess for the
+/// ; MemoryLocation %a
+/// %d = load i32, i32* %b, align 4 ; Caches M entries in
+/// ; CachedUpwardsClobberingAccess for the
+/// ; MemoryLocation %b
+///
+/// ; For completeness' sake, loading %a or %b again would not cache *another*
+/// ; M entries.
+/// %r = add i32 %c, %d
+/// ret i32 %r
+/// }
+class MemorySSA::CachingWalker final : public MemorySSAWalker {
+public:
+ CachingWalker(MemorySSA *, AliasAnalysis *, DominatorTree *);
+ ~CachingWalker() override;
+
+ MemoryAccess *getClobberingMemoryAccess(const Instruction *) override;
+ MemoryAccess *getClobberingMemoryAccess(MemoryAccess *,
+ MemoryLocation &) override;
+ void invalidateInfo(MemoryAccess *) override;
+
+protected:
+ struct UpwardsMemoryQuery;
+ MemoryAccess *doCacheLookup(const MemoryAccess *, const UpwardsMemoryQuery &,
+ const MemoryLocation &);
+
+ void doCacheInsert(const MemoryAccess *, MemoryAccess *,
+ const UpwardsMemoryQuery &, const MemoryLocation &);
+
+ void doCacheRemove(const MemoryAccess *, const UpwardsMemoryQuery &,
+ const MemoryLocation &);
+
+private:
+ MemoryAccessPair UpwardsDFSWalk(MemoryAccess *, const MemoryLocation &,
+ UpwardsMemoryQuery &, bool);
+ MemoryAccess *getClobberingMemoryAccess(MemoryAccess *, UpwardsMemoryQuery &);
+ bool instructionClobbersQuery(const MemoryDef *, UpwardsMemoryQuery &,
+ const MemoryLocation &Loc) const;
+ void verifyRemoved(MemoryAccess *);
+ SmallDenseMap<ConstMemoryAccessPair, MemoryAccess *>
+ CachedUpwardsClobberingAccess;
+ DenseMap<const MemoryAccess *, MemoryAccess *> CachedUpwardsClobberingCall;
+ AliasAnalysis *AA;
+ DominatorTree *DT;
+};
}
namespace {
@@ -238,7 +305,7 @@ MemorySSAWalker *MemorySSA::getWalker() {
if (Walker)
return Walker.get();
- Walker = make_unique<CachingMemorySSAWalker>(this, AA, DT);
+ Walker = make_unique<CachingWalker>(this, AA, DT);
// We create an access to represent "live on entry", for things like
// arguments or users of globals, where the memory they use is defined before
@@ -862,13 +929,13 @@ void MemorySSAWrapperPass::print(raw_ostream &OS, const Module *M) const {
MemorySSAWalker::MemorySSAWalker(MemorySSA *M) : MSSA(M) {}
-CachingMemorySSAWalker::CachingMemorySSAWalker(MemorySSA *M, AliasAnalysis *A,
- DominatorTree *D)
+MemorySSA::CachingWalker::CachingWalker(MemorySSA *M, AliasAnalysis *A,
+ DominatorTree *D)
: MemorySSAWalker(M), AA(A), DT(D) {}
-CachingMemorySSAWalker::~CachingMemorySSAWalker() {}
+MemorySSA::CachingWalker::~CachingWalker() {}
-struct CachingMemorySSAWalker::UpwardsMemoryQuery {
+struct MemorySSA::CachingWalker::UpwardsMemoryQuery {
// True if we saw a phi whose predecessor was a backedge
bool SawBackedgePhi;
// True if our original query started off as a call
@@ -887,15 +954,17 @@ struct CachingMemorySSAWalker::UpwardsMemoryQuery {
SmallVector<const MemoryAccess *, 32> VisitedCalls;
// The MemoryAccess we actually got called with, used to test local domination
const MemoryAccess *OriginalAccess;
- // The Datalayout for the module we started in
- const DataLayout *DL;
UpwardsMemoryQuery()
: SawBackedgePhi(false), IsCall(false), Inst(nullptr),
- OriginalAccess(nullptr), DL(nullptr) {}
+ OriginalAccess(nullptr) {}
+
+ UpwardsMemoryQuery(const Instruction *Inst, const MemoryAccess *Access)
+ : SawBackedgePhi(false), IsCall(ImmutableCallSite(Inst)), Inst(Inst),
+ OriginalAccess(Access) {}
};
-void CachingMemorySSAWalker::invalidateInfo(MemoryAccess *MA) {
+void MemorySSA::CachingWalker::invalidateInfo(MemoryAccess *MA) {
// TODO: We can do much better cache invalidation with differently stored
// caches. For now, for MemoryUses, we simply remove them
@@ -929,19 +998,19 @@ void CachingMemorySSAWalker::invalidateInfo(MemoryAccess *MA) {
#endif
}
-void CachingMemorySSAWalker::doCacheRemove(const MemoryAccess *M,
- const UpwardsMemoryQuery &Q,
- const MemoryLocation &Loc) {
+void MemorySSA::CachingWalker::doCacheRemove(const MemoryAccess *M,
+ const UpwardsMemoryQuery &Q,
+ const MemoryLocation &Loc) {
if (Q.IsCall)
CachedUpwardsClobberingCall.erase(M);
else
CachedUpwardsClobberingAccess.erase({M, Loc});
}
-void CachingMemorySSAWalker::doCacheInsert(const MemoryAccess *M,
- MemoryAccess *Result,
- const UpwardsMemoryQuery &Q,
- const MemoryLocation &Loc) {
+void MemorySSA::CachingWalker::doCacheInsert(const MemoryAccess *M,
+ MemoryAccess *Result,
+ const UpwardsMemoryQuery &Q,
+ const MemoryLocation &Loc) {
// 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((Result != M || isa<MemoryPhi>(M)) &&
@@ -953,11 +1022,12 @@ void CachingMemorySSAWalker::doCacheInsert(const MemoryAccess *M,
CachedUpwardsClobberingAccess[{M, Loc}] = Result;
}
-MemoryAccess *CachingMemorySSAWalker::doCacheLookup(const MemoryAccess *M,
- const UpwardsMemoryQuery &Q,
- const MemoryLocation &Loc) {
+MemoryAccess *
+MemorySSA::CachingWalker::doCacheLookup(const MemoryAccess *M,
+ const UpwardsMemoryQuery &Q,
+ const MemoryLocation &Loc) {
++NumClobberCacheLookups;
- MemoryAccess *Result = nullptr;
+ MemoryAccess *Result;
if (Q.IsCall)
Result = CachedUpwardsClobberingCall.lookup(M);
@@ -969,7 +1039,7 @@ MemoryAccess *CachingMemorySSAWalker::doCacheLookup(const MemoryAccess *M,
return Result;
}
-bool CachingMemorySSAWalker::instructionClobbersQuery(
+bool MemorySSA::CachingWalker::instructionClobbersQuery(
const MemoryDef *MD, UpwardsMemoryQuery &Q,
const MemoryLocation &Loc) const {
Instruction *DefMemoryInst = MD->getMemoryInst();
@@ -985,7 +1055,7 @@ bool CachingMemorySSAWalker::instructionClobbersQuery(
return I != MRI_NoModRef;
}
-MemoryAccessPair CachingMemorySSAWalker::UpwardsDFSWalk(
+MemoryAccessPair MemorySSA::CachingWalker::UpwardsDFSWalk(
MemoryAccess *StartingAccess, const MemoryLocation &Loc,
UpwardsMemoryQuery &Q, bool FollowingBackedge) {
MemoryAccess *ModifyingAccess = nullptr;
@@ -1117,15 +1187,13 @@ MemoryAccessPair CachingMemorySSAWalker::UpwardsDFSWalk(
/// the MemoryAccess that actually clobbers Loc.
///
/// \returns our clobbering memory access
-MemoryAccess *
-CachingMemorySSAWalker::getClobberingMemoryAccess(MemoryAccess *StartingAccess,
- UpwardsMemoryQuery &Q) {
+MemoryAccess *MemorySSA::CachingWalker::getClobberingMemoryAccess(
+ MemoryAccess *StartingAccess, UpwardsMemoryQuery &Q) {
return UpwardsDFSWalk(StartingAccess, Q.StartingLoc, Q, false).first;
}
-MemoryAccess *
-CachingMemorySSAWalker::getClobberingMemoryAccess(MemoryAccess *StartingAccess,
- MemoryLocation &Loc) {
+MemoryAccess *MemorySSA::CachingWalker::getClobberingMemoryAccess(
+ MemoryAccess *StartingAccess, MemoryLocation &Loc) {
if (isa<MemoryPhi>(StartingAccess))
return StartingAccess;
@@ -1145,7 +1213,6 @@ CachingMemorySSAWalker::getClobberingMemoryAccess(MemoryAccess *StartingAccess,
Q.StartingLoc = Loc;
Q.Inst = StartingUseOrDef->getMemoryInst();
Q.IsCall = false;
- Q.DL = &Q.Inst->getModule()->getDataLayout();
if (auto CacheResult = doCacheLookup(StartingUseOrDef, Q, Q.StartingLoc))
return CacheResult;
@@ -1168,7 +1235,7 @@ CachingMemorySSAWalker::getClobberingMemoryAccess(MemoryAccess *StartingAccess,
}
MemoryAccess *
-CachingMemorySSAWalker::getClobberingMemoryAccess(const Instruction *I) {
+MemorySSA::CachingWalker::getClobberingMemoryAccess(const Instruction *I) {
// There should be no way to lookup an instruction and get a phi as the
// access, since we only map BB's to PHI's. So, this must be a use or def.
auto *StartingAccess = cast<MemoryUseOrDef>(MSSA->getMemoryAccess(I));
@@ -1185,7 +1252,6 @@ CachingMemorySSAWalker::getClobberingMemoryAccess(const Instruction *I) {
if (!Q.IsCall)
Q.StartingLoc = MemoryLocation::get(I);
Q.Inst = I;
- Q.DL = &Q.Inst->getModule()->getDataLayout();
if (auto CacheResult = doCacheLookup(StartingAccess, Q, Q.StartingLoc))
return CacheResult;
@@ -1219,7 +1285,7 @@ CachingMemorySSAWalker::getClobberingMemoryAccess(const Instruction *I) {
}
// Verify that MA doesn't exist in any of the caches.
-void CachingMemorySSAWalker::verifyRemoved(MemoryAccess *MA) {
+void MemorySSA::CachingWalker::verifyRemoved(MemoryAccess *MA) {
#ifndef NDEBUG
for (auto &P : CachedUpwardsClobberingAccess)
assert(P.first.first != MA && P.second != MA &&
OpenPOWER on IntegriCloud