summaryrefslogtreecommitdiffstats
path: root/llvm
diff options
context:
space:
mode:
Diffstat (limited to 'llvm')
-rw-r--r--llvm/include/llvm/Transforms/Utils/MemorySSA.h75
-rw-r--r--llvm/include/llvm/Transforms/Utils/MemorySSAUpdater.h85
-rw-r--r--llvm/lib/Transforms/Scalar/EarlyCSE.cpp8
-rw-r--r--llvm/lib/Transforms/Scalar/GVNHoist.cpp22
-rw-r--r--llvm/lib/Transforms/Utils/MemorySSA.cpp119
-rw-r--r--llvm/lib/Transforms/Utils/MemorySSAUpdater.cpp92
-rw-r--r--llvm/unittests/Transforms/Utils/MemorySSA.cpp50
7 files changed, 220 insertions, 231 deletions
diff --git a/llvm/include/llvm/Transforms/Utils/MemorySSA.h b/llvm/include/llvm/Transforms/Utils/MemorySSA.h
index ef5367735f5..7d8a106805a 100644
--- a/llvm/include/llvm/Transforms/Utils/MemorySSA.h
+++ b/llvm/include/llvm/Transforms/Utils/MemorySSA.h
@@ -593,55 +593,6 @@ public:
return getWritableBlockDefs(BB);
}
- /// \brief Create an empty MemoryPhi in MemorySSA for a given basic block.
- /// Only one MemoryPhi for a block exists at a time, so this function will
- /// assert if you try to create one where it already exists.
- MemoryPhi *createMemoryPhi(BasicBlock *BB);
-
- enum InsertionPlace { Beginning, End };
-
- /// \brief Create a MemoryAccess in MemorySSA at a specified point in a block,
- /// with a specified clobbering definition.
- ///
- /// Returns the new MemoryAccess.
- /// This should be called when a memory instruction is created that is being
- /// used to replace an existing memory instruction. It will *not* create PHI
- /// nodes, or verify the clobbering definition. The insertion place is used
- /// solely to determine where in the memoryssa access lists the instruction
- /// will be placed. The caller is expected to keep ordering the same as
- /// instructions.
- /// It will return the new MemoryAccess.
- /// Note: If a MemoryAccess already exists for I, this function will make it
- /// inaccessible and it *must* have removeMemoryAccess called on it.
- MemoryAccess *createMemoryAccessInBB(Instruction *I, MemoryAccess *Definition,
- const BasicBlock *BB,
- InsertionPlace Point);
-
- /// \brief Create a MemoryAccess in MemorySSA before or after an existing
- /// MemoryAccess.
- ///
- /// Returns the new MemoryAccess.
- /// This should be called when a memory instruction is created that is being
- /// used to replace an existing memory instruction. It will *not* create PHI
- /// nodes, or verify the clobbering definition.
- ///
- /// Note: If a MemoryAccess already exists for I, this function will make it
- /// inaccessible and it *must* have removeMemoryAccess called on it.
- MemoryUseOrDef *createMemoryAccessBefore(Instruction *I,
- MemoryAccess *Definition,
- MemoryUseOrDef *InsertPt);
- MemoryUseOrDef *createMemoryAccessAfter(Instruction *I,
- MemoryAccess *Definition,
- MemoryAccess *InsertPt);
-
- /// \brief Remove a MemoryAccess from MemorySSA, including updating all
- /// definitions and uses.
- /// This should be called when a memory instruction that has a MemoryAccess
- /// associated with it is erased from the program. For example, if a store or
- /// load is simply erased (not replaced), removeMemoryAccess should be called
- /// on the MemoryAccess for that store/load.
- void removeMemoryAccess(MemoryAccess *);
-
/// \brief Given two memory accesses in the same basic block, determine
/// whether MemoryAccess \p A dominates MemoryAccess \p B.
bool locallyDominates(const MemoryAccess *A, const MemoryAccess *B) const;
@@ -658,6 +609,10 @@ public:
/// all uses, uses appear in the right places). This is used by unit tests.
void verifyMemorySSA() const;
+ /// Used in various insertion functions to specify whether we are talking
+ /// about the beginning or end of a block.
+ enum InsertionPlace { Beginning, End };
+
protected:
// Used by Memory SSA annotater, dumpers, and wrapper pass
friend class MemorySSAAnnotatedWriter;
@@ -680,9 +635,10 @@ protected:
return It == PerBlockDefs.end() ? nullptr : It->second.get();
}
- // This is used by the updater to perform the internal memoryssa machinations
- // for moves. It does not always leave the IR in a correct state, and relies
- // on the updater to fixup what it breaks, so it is not public.
+ // These is used by the updater to perform various internal MemorySSA
+ // machinsations. They do not always leave the IR in a correct state, and
+ // relies on the updater to fixup what it breaks, so it is not public.
+
void moveTo(MemoryUseOrDef *What, BasicBlock *BB, AccessList::iterator Where);
void moveTo(MemoryUseOrDef *What, BasicBlock *BB, InsertionPlace Point);
// Rename the dominator tree branch rooted at BB.
@@ -690,6 +646,13 @@ protected:
SmallPtrSetImpl<BasicBlock *> &Visited) {
renamePass(DT->getNode(BB), IncomingVal, Visited, true, true);
}
+ void removeFromLookups(MemoryAccess *);
+ void removeFromLists(MemoryAccess *, bool ShouldDelete = true);
+ void insertIntoListsForBlock(MemoryAccess *, const BasicBlock *,
+ InsertionPlace);
+ void insertIntoListsBefore(MemoryAccess *, const BasicBlock *,
+ AccessList::iterator);
+ MemoryUseOrDef *createDefinedAccess(Instruction *, MemoryAccess *);
private:
class CachingWalker;
@@ -708,11 +671,9 @@ private:
void computeDomLevels(DenseMap<DomTreeNode *, unsigned> &DomLevels);
void markUnreachableAsLiveOnEntry(BasicBlock *BB);
bool dominatesUse(const MemoryAccess *, const MemoryAccess *) const;
+ MemoryPhi *createMemoryPhi(BasicBlock *BB);
MemoryUseOrDef *createNewAccess(Instruction *);
- MemoryUseOrDef *createDefinedAccess(Instruction *, MemoryAccess *);
MemoryAccess *findDominatingDef(BasicBlock *, enum InsertionPlace);
- void removeFromLookups(MemoryAccess *);
- void removeFromLists(MemoryAccess *, bool ShouldDelete = true);
void placePHINodes(const SmallPtrSetImpl<BasicBlock *> &,
const DenseMap<const BasicBlock *, unsigned int> &);
MemoryAccess *renameBlock(BasicBlock *, MemoryAccess *, bool);
@@ -723,10 +684,6 @@ private:
AccessList *getOrCreateAccessList(const BasicBlock *);
DefsList *getOrCreateDefsList(const BasicBlock *);
void renumberBlock(const BasicBlock *) const;
- void insertIntoListsForBlock(MemoryAccess *, const BasicBlock *,
- InsertionPlace);
- void insertIntoListsBefore(MemoryAccess *, const BasicBlock *,
- AccessList::iterator);
AliasAnalysis *AA;
DominatorTree *DT;
Function &F;
diff --git a/llvm/include/llvm/Transforms/Utils/MemorySSAUpdater.h b/llvm/include/llvm/Transforms/Utils/MemorySSAUpdater.h
index 8b754902b6a..91e6fbe50b8 100644
--- a/llvm/include/llvm/Transforms/Utils/MemorySSAUpdater.h
+++ b/llvm/include/llvm/Transforms/Utils/MemorySSAUpdater.h
@@ -63,23 +63,23 @@ private:
public:
MemorySSAUpdater(MemorySSA *MSSA) : MSSA(MSSA) {}
- // Insert a definition into the MemorySSA IR. RenameUses will rename any use
- // below the new def block (and any inserted phis). RenameUses should be set
- // to true if the definition may cause new aliases for loads below it. This
- // is not the case for hoisting or sinking or other forms of code *movement*.
- // It *is* the case for straight code insertion.
- // For example:
- // store a
- // if (foo) { }
- // load a
- //
- // Moving the store into the if block, and calling insertDef, does not
- // require RenameUses.
- // However, changing it to:
- // store a
- // if (foo) { store b }
- // load a
- // Where a mayalias b, *does* require RenameUses be set to true.
+ /// Insert a definition into the MemorySSA IR. RenameUses will rename any use
+ /// below the new def block (and any inserted phis). RenameUses should be set
+ /// to true if the definition may cause new aliases for loads below it. This
+ /// is not the case for hoisting or sinking or other forms of code *movement*.
+ /// It *is* the case for straight code insertion.
+ /// For example:
+ /// store a
+ /// if (foo) { }
+ /// load a
+ ///
+ /// Moving the store into the if block, and calling insertDef, does not
+ /// require RenameUses.
+ /// However, changing it to:
+ /// store a
+ /// if (foo) { store b }
+ /// load a
+ /// Where a mayalias b, *does* require RenameUses be set to true.
void insertDef(MemoryDef *Def, bool RenameUses = false);
void insertUse(MemoryUse *Use);
void moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where);
@@ -87,11 +87,58 @@ public:
void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB,
MemorySSA::InsertionPlace Where);
+ // The below are utility functions. Other than creation of accesses to pass
+ // to insertDef, and removeAccess to remove accesses, you should generally
+ // not attempt to update memoryssa yourself. It is very non-trivial to get
+ // the edge cases right, and the above calls already operate in near-optimal
+ // time bounds.
+
+ /// \brief Create a MemoryAccess in MemorySSA at a specified point in a block,
+ /// with a specified clobbering definition.
+ ///
+ /// Returns the new MemoryAccess.
+ /// This should be called when a memory instruction is created that is being
+ /// used to replace an existing memory instruction. It will *not* create PHI
+ /// nodes, or verify the clobbering definition. The insertion place is used
+ /// solely to determine where in the memoryssa access lists the instruction
+ /// will be placed. The caller is expected to keep ordering the same as
+ /// instructions.
+ /// It will return the new MemoryAccess.
+ /// Note: If a MemoryAccess already exists for I, this function will make it
+ /// inaccessible and it *must* have removeMemoryAccess called on it.
+ MemoryAccess *createMemoryAccessInBB(Instruction *I, MemoryAccess *Definition,
+ const BasicBlock *BB,
+ MemorySSA::InsertionPlace Point);
+
+ /// \brief Create a MemoryAccess in MemorySSA before or after an existing
+ /// MemoryAccess.
+ ///
+ /// Returns the new MemoryAccess.
+ /// This should be called when a memory instruction is created that is being
+ /// used to replace an existing memory instruction. It will *not* create PHI
+ /// nodes, or verify the clobbering definition.
+ ///
+ /// Note: If a MemoryAccess already exists for I, this function will make it
+ /// inaccessible and it *must* have removeMemoryAccess called on it.
+ MemoryUseOrDef *createMemoryAccessBefore(Instruction *I,
+ MemoryAccess *Definition,
+ MemoryUseOrDef *InsertPt);
+ MemoryUseOrDef *createMemoryAccessAfter(Instruction *I,
+ MemoryAccess *Definition,
+ MemoryAccess *InsertPt);
+
+ /// \brief Remove a MemoryAccess from MemorySSA, including updating all
+ /// definitions and uses.
+ /// This should be called when a memory instruction that has a MemoryAccess
+ /// associated with it is erased from the program. For example, if a store or
+ /// load is simply erased (not replaced), removeMemoryAccess should be called
+ /// on the MemoryAccess for that store/load.
+ void removeMemoryAccess(MemoryAccess *);
+
private:
// Move What before Where in the MemorySSA IR.
template <class WhereType>
- void moveTo(MemoryUseOrDef *What, BasicBlock *BB,
- WhereType Where);
+ void moveTo(MemoryUseOrDef *What, BasicBlock *BB, WhereType Where);
MemoryAccess *getPreviousDef(MemoryAccess *);
MemoryAccess *getPreviousDefInBlock(MemoryAccess *);
MemoryAccess *getPreviousDefFromEnd(BasicBlock *);
diff --git a/llvm/lib/Transforms/Scalar/EarlyCSE.cpp b/llvm/lib/Transforms/Scalar/EarlyCSE.cpp
index 5fc0dab9047..a5b19cde002 100644
--- a/llvm/lib/Transforms/Scalar/EarlyCSE.cpp
+++ b/llvm/lib/Transforms/Scalar/EarlyCSE.cpp
@@ -33,6 +33,7 @@
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/MemorySSA.h"
+#include "llvm/Transforms/Utils/MemorySSAUpdater.h"
#include <deque>
using namespace llvm;
using namespace llvm::PatternMatch;
@@ -253,6 +254,7 @@ public:
DominatorTree &DT;
AssumptionCache &AC;
MemorySSA *MSSA;
+ std::unique_ptr<MemorySSAUpdater> MSSAUpdater;
typedef RecyclingAllocator<
BumpPtrAllocator, ScopedHashTableVal<SimpleValue, Value *>> AllocatorTy;
typedef ScopedHashTable<SimpleValue, Value *, DenseMapInfo<SimpleValue>,
@@ -315,7 +317,9 @@ public:
/// \brief Set up the EarlyCSE runner for a particular function.
EarlyCSE(const TargetLibraryInfo &TLI, const TargetTransformInfo &TTI,
DominatorTree &DT, AssumptionCache &AC, MemorySSA *MSSA)
- : TLI(TLI), TTI(TTI), DT(DT), AC(AC), MSSA(MSSA), CurrentGeneration(0) {}
+ : TLI(TLI), TTI(TTI), DT(DT), AC(AC), MSSA(MSSA),
+ MSSAUpdater(make_unique<MemorySSAUpdater>(MSSA)), CurrentGeneration(0) {
+ }
bool run();
@@ -517,7 +521,7 @@ private:
if (MemoryPhi *MP = dyn_cast<MemoryPhi>(U))
PhisToCheck.push_back(MP);
- MSSA->removeMemoryAccess(WI);
+ MSSAUpdater->removeMemoryAccess(WI);
for (MemoryPhi *MP : PhisToCheck) {
MemoryAccess *FirstIn = MP->getIncomingValue(0);
diff --git a/llvm/lib/Transforms/Scalar/GVNHoist.cpp b/llvm/lib/Transforms/Scalar/GVNHoist.cpp
index 90c26e13db7..00d8e5e4c4c 100644
--- a/llvm/lib/Transforms/Scalar/GVNHoist.cpp
+++ b/llvm/lib/Transforms/Scalar/GVNHoist.cpp
@@ -27,6 +27,7 @@
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/MemorySSA.h"
+#include "llvm/Transforms/Utils/MemorySSAUpdater.h"
using namespace llvm;
@@ -201,11 +202,13 @@ class GVNHoist {
public:
GVNHoist(DominatorTree *DT, AliasAnalysis *AA, MemoryDependenceResults *MD,
MemorySSA *MSSA, bool OptForMinSize)
- : DT(DT), AA(AA), MD(MD), MSSA(MSSA), OptForMinSize(OptForMinSize),
- HoistingGeps(OptForMinSize), HoistedCtr(0) {
- // Hoist as far as possible when optimizing for code-size.
- if (OptForMinSize)
- MaxNumberOfBBSInPath = -1;
+ : DT(DT), AA(AA), MD(MD), MSSA(MSSA),
+ MSSAUpdater(make_unique<MemorySSAUpdater>(MSSA)),
+ OptForMinSize(OptForMinSize), HoistingGeps(OptForMinSize),
+ HoistedCtr(0) {
+ // Hoist as far as possible when optimizing for code-size.
+ if (OptForMinSize)
+ MaxNumberOfBBSInPath = -1;
}
bool run(Function &F) {
@@ -251,6 +254,7 @@ private:
AliasAnalysis *AA;
MemoryDependenceResults *MD;
MemorySSA *MSSA;
+ std::unique_ptr<MemorySSAUpdater> MSSAUpdater;
const bool OptForMinSize;
const bool HoistingGeps;
DenseMap<const Value *, unsigned> DFSNumber;
@@ -817,9 +821,9 @@ private:
// legal when the ld/st is not moved past its current definition.
MemoryAccess *Def = OldMemAcc->getDefiningAccess();
NewMemAcc =
- MSSA->createMemoryAccessInBB(Repl, Def, HoistPt, MemorySSA::End);
+ MSSAUpdater->createMemoryAccessInBB(Repl, Def, HoistPt, MemorySSA::End);
OldMemAcc->replaceAllUsesWith(NewMemAcc);
- MSSA->removeMemoryAccess(OldMemAcc);
+ MSSAUpdater->removeMemoryAccess(OldMemAcc);
}
}
@@ -858,7 +862,7 @@ private:
// Update the uses of the old MSSA access with NewMemAcc.
MemoryAccess *OldMA = MSSA->getMemoryAccess(I);
OldMA->replaceAllUsesWith(NewMemAcc);
- MSSA->removeMemoryAccess(OldMA);
+ MSSAUpdater->removeMemoryAccess(OldMA);
}
Repl->andIRFlags(I);
@@ -880,7 +884,7 @@ private:
auto In = Phi->incoming_values();
if (all_of(In, [&](Use &U) { return U == NewMemAcc; })) {
Phi->replaceAllUsesWith(NewMemAcc);
- MSSA->removeMemoryAccess(Phi);
+ MSSAUpdater->removeMemoryAccess(Phi);
}
}
}
diff --git a/llvm/lib/Transforms/Utils/MemorySSA.cpp b/llvm/lib/Transforms/Utils/MemorySSA.cpp
index f8c3a4c06ab..8438ad00dcc 100644
--- a/llvm/lib/Transforms/Utils/MemorySSA.cpp
+++ b/llvm/lib/Transforms/Utils/MemorySSA.cpp
@@ -1691,37 +1691,6 @@ MemoryUseOrDef *MemorySSA::createDefinedAccess(Instruction *I,
return NewAccess;
}
-MemoryAccess *MemorySSA::createMemoryAccessInBB(Instruction *I,
- MemoryAccess *Definition,
- const BasicBlock *BB,
- InsertionPlace Point) {
- MemoryUseOrDef *NewAccess = createDefinedAccess(I, Definition);
- insertIntoListsForBlock(NewAccess, BB, Point);
- return NewAccess;
-}
-
-MemoryUseOrDef *MemorySSA::createMemoryAccessBefore(Instruction *I,
- MemoryAccess *Definition,
- MemoryUseOrDef *InsertPt) {
- assert(I->getParent() == InsertPt->getBlock() &&
- "New and old access must be in the same block");
- MemoryUseOrDef *NewAccess = createDefinedAccess(I, Definition);
- insertIntoListsBefore(NewAccess, InsertPt->getBlock(),
- InsertPt->getIterator());
- return NewAccess;
-}
-
-MemoryUseOrDef *MemorySSA::createMemoryAccessAfter(Instruction *I,
- MemoryAccess *Definition,
- MemoryAccess *InsertPt) {
- assert(I->getParent() == InsertPt->getBlock() &&
- "New and old access must be in the same block");
- MemoryUseOrDef *NewAccess = createDefinedAccess(I, Definition);
- insertIntoListsBefore(NewAccess, InsertPt->getBlock(),
- ++(InsertPt->getIterator()));
- return NewAccess;
-}
-
/// \brief Helper function to create new memory accesses
MemoryUseOrDef *MemorySSA::createNewAccess(Instruction *I) {
// The assume intrinsic has a control dependency which we model by claiming
@@ -1754,33 +1723,6 @@ MemoryUseOrDef *MemorySSA::createNewAccess(Instruction *I) {
return MUD;
}
-MemoryAccess *MemorySSA::findDominatingDef(BasicBlock *UseBlock,
- enum InsertionPlace Where) {
- // Handle the initial case
- if (Where == Beginning)
- // The only thing that could define us at the beginning is a phi node
- if (MemoryPhi *Phi = getMemoryAccess(UseBlock))
- return Phi;
-
- DomTreeNode *CurrNode = DT->getNode(UseBlock);
- // Need to be defined by our dominator
- if (Where == Beginning)
- CurrNode = CurrNode->getIDom();
- Where = End;
- while (CurrNode) {
- auto It = PerBlockAccesses.find(CurrNode->getBlock());
- if (It != PerBlockAccesses.end()) {
- auto &Accesses = It->second;
- for (MemoryAccess &RA : reverse(*Accesses)) {
- if (isa<MemoryDef>(RA) || isa<MemoryPhi>(RA))
- return &RA;
- }
- }
- CurrNode = CurrNode->getIDom();
- }
- return LiveOnEntryDef.get();
-}
-
/// \brief Returns true if \p Replacer dominates \p Replacee .
bool MemorySSA::dominatesUse(const MemoryAccess *Replacer,
const MemoryAccess *Replacee) const {
@@ -1798,20 +1740,6 @@ bool MemorySSA::dominatesUse(const MemoryAccess *Replacer,
return true;
}
-/// \brief If all arguments of a MemoryPHI are defined by the same incoming
-/// argument, return that argument.
-static MemoryAccess *onlySingleValue(MemoryPhi *MP) {
- MemoryAccess *MA = nullptr;
-
- for (auto &Arg : MP->operands()) {
- if (!MA)
- MA = cast<MemoryAccess>(Arg);
- else if (MA != Arg)
- return nullptr;
- }
- return MA;
-}
-
/// \brief Properly remove \p MA from all of MemorySSA's lookup tables.
void MemorySSA::removeFromLookups(MemoryAccess *MA) {
assert(MA->use_empty() &&
@@ -1865,53 +1793,6 @@ void MemorySSA::removeFromLists(MemoryAccess *MA, bool ShouldDelete) {
PerBlockAccesses.erase(AccessIt);
}
-void MemorySSA::removeMemoryAccess(MemoryAccess *MA) {
- assert(!isLiveOnEntryDef(MA) && "Trying to remove the live on entry def");
- // We can only delete phi nodes if they have no uses, or we can replace all
- // uses with a single definition.
- MemoryAccess *NewDefTarget = nullptr;
- if (MemoryPhi *MP = dyn_cast<MemoryPhi>(MA)) {
- // Note that it is sufficient to know that all edges of the phi node have
- // the same argument. If they do, by the definition of dominance frontiers
- // (which we used to place this phi), that argument must dominate this phi,
- // and thus, must dominate the phi's uses, and so we will not hit the assert
- // below.
- NewDefTarget = onlySingleValue(MP);
- assert((NewDefTarget || MP->use_empty()) &&
- "We can't delete this memory phi");
- } else {
- NewDefTarget = cast<MemoryUseOrDef>(MA)->getDefiningAccess();
- }
-
- // Re-point the uses at our defining access
- if (!isa<MemoryUse>(MA) && !MA->use_empty()) {
- // Reset optimized on users of this store, and reset the uses.
- // A few notes:
- // 1. This is a slightly modified version of RAUW to avoid walking the
- // uses twice here.
- // 2. If we wanted to be complete, we would have to reset the optimized
- // flags on users of phi nodes if doing the below makes a phi node have all
- // the same arguments. Instead, we prefer users to removeMemoryAccess those
- // phi nodes, because doing it here would be N^3.
- if (MA->hasValueHandle())
- ValueHandleBase::ValueIsRAUWd(MA, NewDefTarget);
- // Note: We assume MemorySSA is not used in metadata since it's not really
- // part of the IR.
-
- while (!MA->use_empty()) {
- Use &U = *MA->use_begin();
- if (MemoryUse *MU = dyn_cast<MemoryUse>(U.getUser()))
- MU->resetOptimized();
- U.set(NewDefTarget);
- }
- }
-
- // The call below to erase will destroy MA, so we can't change the order we
- // are doing things here
- removeFromLookups(MA);
- removeFromLists(MA);
-}
-
void MemorySSA::print(raw_ostream &OS) const {
MemorySSAAnnotatedWriter Writer(this);
F.print(OS, &Writer);
diff --git a/llvm/lib/Transforms/Utils/MemorySSAUpdater.cpp b/llvm/lib/Transforms/Utils/MemorySSAUpdater.cpp
index 3b90ab72f04..7e043956171 100644
--- a/llvm/lib/Transforms/Utils/MemorySSAUpdater.cpp
+++ b/llvm/lib/Transforms/Utils/MemorySSAUpdater.cpp
@@ -189,7 +189,7 @@ MemoryAccess *MemorySSAUpdater::tryRemoveTrivialPhi(MemoryPhi *Phi,
return MSSA->getLiveOnEntryDef();
if (Phi) {
Phi->replaceAllUsesWith(Same);
- MSSA->removeMemoryAccess(Phi);
+ removeMemoryAccess(Phi);
}
// We should only end up recursing in case we replaced something, in which
@@ -401,4 +401,94 @@ void MemorySSAUpdater::moveToPlace(MemoryUseOrDef *What, BasicBlock *BB,
MemorySSA::InsertionPlace Where) {
return moveTo(What, BB, Where);
}
+
+/// \brief If all arguments of a MemoryPHI are defined by the same incoming
+/// argument, return that argument.
+static MemoryAccess *onlySingleValue(MemoryPhi *MP) {
+ MemoryAccess *MA = nullptr;
+
+ for (auto &Arg : MP->operands()) {
+ if (!MA)
+ MA = cast<MemoryAccess>(Arg);
+ else if (MA != Arg)
+ return nullptr;
+ }
+ return MA;
+}
+void MemorySSAUpdater::removeMemoryAccess(MemoryAccess *MA) {
+ assert(!MSSA->isLiveOnEntryDef(MA) &&
+ "Trying to remove the live on entry def");
+ // We can only delete phi nodes if they have no uses, or we can replace all
+ // uses with a single definition.
+ MemoryAccess *NewDefTarget = nullptr;
+ if (MemoryPhi *MP = dyn_cast<MemoryPhi>(MA)) {
+ // Note that it is sufficient to know that all edges of the phi node have
+ // the same argument. If they do, by the definition of dominance frontiers
+ // (which we used to place this phi), that argument must dominate this phi,
+ // and thus, must dominate the phi's uses, and so we will not hit the assert
+ // below.
+ NewDefTarget = onlySingleValue(MP);
+ assert((NewDefTarget || MP->use_empty()) &&
+ "We can't delete this memory phi");
+ } else {
+ NewDefTarget = cast<MemoryUseOrDef>(MA)->getDefiningAccess();
+ }
+
+ // Re-point the uses at our defining access
+ if (!isa<MemoryUse>(MA) && !MA->use_empty()) {
+ // Reset optimized on users of this store, and reset the uses.
+ // A few notes:
+ // 1. This is a slightly modified version of RAUW to avoid walking the
+ // uses twice here.
+ // 2. If we wanted to be complete, we would have to reset the optimized
+ // flags on users of phi nodes if doing the below makes a phi node have all
+ // the same arguments. Instead, we prefer users to removeMemoryAccess those
+ // phi nodes, because doing it here would be N^3.
+ if (MA->hasValueHandle())
+ ValueHandleBase::ValueIsRAUWd(MA, NewDefTarget);
+ // Note: We assume MemorySSA is not used in metadata since it's not really
+ // part of the IR.
+
+ while (!MA->use_empty()) {
+ Use &U = *MA->use_begin();
+ if (MemoryUse *MU = dyn_cast<MemoryUse>(U.getUser()))
+ MU->resetOptimized();
+ U.set(NewDefTarget);
+ }
+ }
+
+ // The call below to erase will destroy MA, so we can't change the order we
+ // are doing things here
+ MSSA->removeFromLookups(MA);
+ MSSA->removeFromLists(MA);
+}
+
+MemoryAccess *MemorySSAUpdater::createMemoryAccessInBB(
+ Instruction *I, MemoryAccess *Definition, const BasicBlock *BB,
+ MemorySSA::InsertionPlace Point) {
+ MemoryUseOrDef *NewAccess = MSSA->createDefinedAccess(I, Definition);
+ MSSA->insertIntoListsForBlock(NewAccess, BB, Point);
+ return NewAccess;
+}
+
+MemoryUseOrDef *MemorySSAUpdater::createMemoryAccessBefore(
+ Instruction *I, MemoryAccess *Definition, MemoryUseOrDef *InsertPt) {
+ assert(I->getParent() == InsertPt->getBlock() &&
+ "New and old access must be in the same block");
+ MemoryUseOrDef *NewAccess = MSSA->createDefinedAccess(I, Definition);
+ MSSA->insertIntoListsBefore(NewAccess, InsertPt->getBlock(),
+ InsertPt->getIterator());
+ return NewAccess;
+}
+
+MemoryUseOrDef *MemorySSAUpdater::createMemoryAccessAfter(
+ Instruction *I, MemoryAccess *Definition, MemoryAccess *InsertPt) {
+ assert(I->getParent() == InsertPt->getBlock() &&
+ "New and old access must be in the same block");
+ MemoryUseOrDef *NewAccess = MSSA->createDefinedAccess(I, Definition);
+ MSSA->insertIntoListsBefore(NewAccess, InsertPt->getBlock(),
+ ++InsertPt->getIterator());
+ return NewAccess;
+}
+
} // namespace llvm
diff --git a/llvm/unittests/Transforms/Utils/MemorySSA.cpp b/llvm/unittests/Transforms/Utils/MemorySSA.cpp
index fb57acd2ec4..0f283f5e330 100644
--- a/llvm/unittests/Transforms/Utils/MemorySSA.cpp
+++ b/llvm/unittests/Transforms/Utils/MemorySSA.cpp
@@ -90,6 +90,7 @@ TEST_F(MemorySSATest, CreateALoad) {
setupAnalyses();
MemorySSA &MSSA = *Analyses->MSSA;
+ MemorySSAUpdater Updater(&MSSA);
// Add the load
B.SetInsertPoint(Merge);
LoadInst *LoadInst = B.CreateLoad(PointerArg);
@@ -99,8 +100,8 @@ TEST_F(MemorySSATest, CreateALoad) {
EXPECT_NE(MP, nullptr);
// Create the load memory acccess
- MemoryUse *LoadAccess = cast<MemoryUse>(
- MSSA.createMemoryAccessInBB(LoadInst, MP, Merge, MemorySSA::Beginning));
+ MemoryUse *LoadAccess = cast<MemoryUse>(Updater.createMemoryAccessInBB(
+ LoadInst, MP, Merge, MemorySSA::Beginning));
MemoryAccess *DefiningAccess = LoadAccess->getDefiningAccess();
EXPECT_TRUE(isa<MemoryPhi>(DefiningAccess));
MSSA.verifyMemorySSA();
@@ -132,7 +133,7 @@ TEST_F(MemorySSATest, CreateLoadsAndStoreUpdater) {
// Add the store
B.SetInsertPoint(Entry, Entry->begin());
StoreInst *EntryStore = B.CreateStore(B.getInt8(16), PointerArg);
- MemoryAccess *EntryStoreAccess = MSSA.createMemoryAccessInBB(
+ MemoryAccess *EntryStoreAccess = Updater.createMemoryAccessInBB(
EntryStore, nullptr, Entry, MemorySSA::Beginning);
Updater.insertDef(cast<MemoryDef>(EntryStoreAccess));
@@ -145,7 +146,7 @@ TEST_F(MemorySSATest, CreateLoadsAndStoreUpdater) {
EXPECT_EQ(MP, nullptr);
// Create the load memory access
- MemoryUse *FirstLoadAccess = cast<MemoryUse>(MSSA.createMemoryAccessInBB(
+ MemoryUse *FirstLoadAccess = cast<MemoryUse>(Updater.createMemoryAccessInBB(
FirstLoad, nullptr, Merge, MemorySSA::Beginning));
Updater.insertUse(FirstLoadAccess);
// Should just have a load using the entry access, because it should discover
@@ -156,7 +157,7 @@ TEST_F(MemorySSATest, CreateLoadsAndStoreUpdater) {
// Add the store
B.SetInsertPoint(Left, Left->begin());
StoreInst *LeftStore = B.CreateStore(B.getInt8(16), PointerArg);
- MemoryAccess *LeftStoreAccess = MSSA.createMemoryAccessInBB(
+ MemoryAccess *LeftStoreAccess = Updater.createMemoryAccessInBB(
LeftStore, nullptr, Left, MemorySSA::Beginning);
Updater.insertDef(cast<MemoryDef>(LeftStoreAccess), false);
// We don't touch existing loads, so we need to create a new one to get a phi
@@ -169,7 +170,7 @@ TEST_F(MemorySSATest, CreateLoadsAndStoreUpdater) {
EXPECT_EQ(MP, nullptr);
// Create the load memory access
- MemoryUse *SecondLoadAccess = cast<MemoryUse>(MSSA.createMemoryAccessInBB(
+ MemoryUse *SecondLoadAccess = cast<MemoryUse>(Updater.createMemoryAccessInBB(
SecondLoad, nullptr, Merge, MemorySSA::Beginning));
Updater.insertUse(SecondLoadAccess);
// Now the load should be a phi of the entry store and the left store
@@ -181,7 +182,7 @@ TEST_F(MemorySSATest, CreateLoadsAndStoreUpdater) {
// Now create a store below the existing one in the entry
B.SetInsertPoint(Entry, --Entry->end());
StoreInst *SecondEntryStore = B.CreateStore(B.getInt8(16), PointerArg);
- MemoryAccess *SecondEntryStoreAccess = MSSA.createMemoryAccessInBB(
+ MemoryAccess *SecondEntryStoreAccess = Updater.createMemoryAccessInBB(
SecondEntryStore, nullptr, Entry, MemorySSA::End);
// Insert it twice just to test renaming
Updater.insertDef(cast<MemoryDef>(SecondEntryStoreAccess), false);
@@ -223,7 +224,7 @@ TEST_F(MemorySSATest, CreateALoadUpdater) {
// Add the store
StoreInst *SI = B.CreateStore(B.getInt8(16), PointerArg);
MemoryAccess *StoreAccess =
- MSSA.createMemoryAccessInBB(SI, nullptr, Left, MemorySSA::Beginning);
+ Updater.createMemoryAccessInBB(SI, nullptr, Left, MemorySSA::Beginning);
Updater.insertDef(cast<MemoryDef>(StoreAccess));
// Add the load
@@ -235,7 +236,7 @@ TEST_F(MemorySSATest, CreateALoadUpdater) {
EXPECT_EQ(MP, nullptr);
// Create the load memory acccess
- MemoryUse *LoadAccess = cast<MemoryUse>(MSSA.createMemoryAccessInBB(
+ MemoryUse *LoadAccess = cast<MemoryUse>(Updater.createMemoryAccessInBB(
LoadInst, nullptr, Merge, MemorySSA::Beginning));
Updater.insertUse(LoadAccess);
MemoryAccess *DefiningAccess = LoadAccess->getDefiningAccess();
@@ -267,15 +268,15 @@ TEST_F(MemorySSATest, MoveAStore) {
B.CreateLoad(PointerArg);
setupAnalyses();
MemorySSA &MSSA = *Analyses->MSSA;
-
+ MemorySSAUpdater Updater(&MSSA);
// Move the store
SideStore->moveBefore(Entry->getTerminator());
MemoryAccess *EntryStoreAccess = MSSA.getMemoryAccess(EntryStore);
MemoryAccess *SideStoreAccess = MSSA.getMemoryAccess(SideStore);
- MemoryAccess *NewStoreAccess = MSSA.createMemoryAccessAfter(
+ MemoryAccess *NewStoreAccess = Updater.createMemoryAccessAfter(
SideStore, EntryStoreAccess, EntryStoreAccess);
EntryStoreAccess->replaceAllUsesWith(NewStoreAccess);
- MSSA.removeMemoryAccess(SideStoreAccess);
+ Updater.removeMemoryAccess(SideStoreAccess);
MSSA.verifyMemorySSA();
}
@@ -309,7 +310,7 @@ TEST_F(MemorySSATest, MoveAStoreUpdater) {
SideStore->moveBefore(Entry->getTerminator());
auto *EntryStoreAccess = MSSA.getMemoryAccess(EntryStore);
auto *SideStoreAccess = MSSA.getMemoryAccess(SideStore);
- auto *NewStoreAccess = MSSA.createMemoryAccessAfter(
+ auto *NewStoreAccess = Updater.createMemoryAccessAfter(
SideStore, EntryStoreAccess, EntryStoreAccess);
// Before, the load will point to a phi of the EntryStore and SideStore.
auto *LoadAccess = cast<MemoryUse>(MSSA.getMemoryAccess(MergeLoad));
@@ -317,7 +318,7 @@ TEST_F(MemorySSATest, MoveAStoreUpdater) {
MemoryPhi *MergePhi = cast<MemoryPhi>(LoadAccess->getDefiningAccess());
EXPECT_EQ(MergePhi->getIncomingValue(1), EntryStoreAccess);
EXPECT_EQ(MergePhi->getIncomingValue(0), SideStoreAccess);
- MSSA.removeMemoryAccess(SideStoreAccess);
+ Updater.removeMemoryAccess(SideStoreAccess);
Updater.insertDef(cast<MemoryDef>(NewStoreAccess));
// After it's a phi of the new side store access.
EXPECT_EQ(MergePhi->getIncomingValue(0), NewStoreAccess);
@@ -448,13 +449,15 @@ TEST_F(MemorySSATest, RemoveAPhi) {
setupAnalyses();
MemorySSA &MSSA = *Analyses->MSSA;
+ MemorySSAUpdater Updater(&MSSA);
+
// Before, the load will be a use of a phi<store, liveonentry>.
MemoryUse *LoadAccess = cast<MemoryUse>(MSSA.getMemoryAccess(LoadInst));
MemoryDef *StoreAccess = cast<MemoryDef>(MSSA.getMemoryAccess(StoreInst));
MemoryAccess *DefiningAccess = LoadAccess->getDefiningAccess();
EXPECT_TRUE(isa<MemoryPhi>(DefiningAccess));
// Kill the store
- MSSA.removeMemoryAccess(StoreAccess);
+ Updater.removeMemoryAccess(StoreAccess);
MemoryPhi *MP = cast<MemoryPhi>(DefiningAccess);
// Verify the phi ended up as liveonentry, liveonentry
for (auto &Op : MP->incoming_values())
@@ -464,7 +467,7 @@ TEST_F(MemorySSATest, RemoveAPhi) {
// Verify the load is now defined by liveOnEntryDef
EXPECT_TRUE(MSSA.isLiveOnEntryDef(LoadAccess->getDefiningAccess()));
// Remove the PHI
- MSSA.removeMemoryAccess(MP);
+ Updater.removeMemoryAccess(MP);
MSSA.verifyMemorySSA();
}
@@ -492,6 +495,7 @@ TEST_F(MemorySSATest, RemoveMemoryAccess) {
setupAnalyses();
MemorySSA &MSSA = *Analyses->MSSA;
MemorySSAWalker *Walker = Analyses->Walker;
+ MemorySSAUpdater Updater(&MSSA);
// Before, the load will be a use of a phi<store, liveonentry>. It should be
// the same after.
@@ -502,7 +506,7 @@ TEST_F(MemorySSATest, RemoveMemoryAccess) {
// The load is currently clobbered by one of the phi arguments, so the walker
// should determine the clobbering access as the phi.
EXPECT_EQ(DefiningAccess, Walker->getClobberingMemoryAccess(LoadInst));
- MSSA.removeMemoryAccess(StoreAccess);
+ Updater.removeMemoryAccess(StoreAccess);
MSSA.verifyMemorySSA();
// After the removeaccess, let's see if we got the right accesses
// The load should still point to the phi ...
@@ -526,7 +530,7 @@ TEST_F(MemorySSATest, RemoveMemoryAccess) {
}
// Now we try to remove the single valued phi
- MSSA.removeMemoryAccess(DefiningAccess);
+ Updater.removeMemoryAccess(DefiningAccess);
MSSA.verifyMemorySSA();
// Now the load should be a load of live on entry.
EXPECT_TRUE(MSSA.isLiveOnEntryDef(LoadAccess->getDefiningAccess()));
@@ -680,10 +684,11 @@ TEST_F(MemorySSATest, PartialWalkerCacheWithPhis) {
setupAnalyses();
MemorySSA &MSSA = *Analyses->MSSA;
MemorySSAWalker *Walker = Analyses->Walker;
+ MemorySSAUpdater Updater(&MSSA);
// Kill `KillStore`; it exists solely so that the load after it won't be
// optimized to FirstStore.
- MSSA.removeMemoryAccess(MSSA.getMemoryAccess(KillStore));
+ Updater.removeMemoryAccess(MSSA.getMemoryAccess(KillStore));
KillStore->eraseFromParent();
auto *ALoadMA = cast<MemoryUse>(MSSA.getMemoryAccess(ALoad));
EXPECT_EQ(ALoadMA->getDefiningAccess(), MSSA.getMemoryAccess(BStore));
@@ -755,15 +760,16 @@ TEST_F(MemorySSATest, WalkerReopt) {
setupAnalyses();
MemorySSA &MSSA = *Analyses->MSSA;
MemorySSAWalker *Walker = Analyses->Walker;
+ MemorySSAUpdater Updater(&MSSA);
MemoryAccess *LoadClobber = Walker->getClobberingMemoryAccess(LIA);
MemoryUse *LoadAccess = cast<MemoryUse>(MSSA.getMemoryAccess(LIA));
EXPECT_EQ(LoadClobber, MSSA.getMemoryAccess(SIA));
EXPECT_TRUE(MSSA.isLiveOnEntryDef(Walker->getClobberingMemoryAccess(SIA)));
- MSSA.removeMemoryAccess(LoadAccess);
+ Updater.removeMemoryAccess(LoadAccess);
// Create the load memory access pointing to an unoptimized place.
- MemoryUse *NewLoadAccess = cast<MemoryUse>(MSSA.createMemoryAccessInBB(
+ MemoryUse *NewLoadAccess = cast<MemoryUse>(Updater.createMemoryAccessInBB(
LIA, MSSA.getMemoryAccess(SIB), LIA->getParent(), MemorySSA::End));
// This should it cause it to be optimized
EXPECT_EQ(Walker->getClobberingMemoryAccess(NewLoadAccess), LoadClobber);
@@ -852,7 +858,7 @@ TEST_F(MemorySSATest, Irreducible) {
MemorySSAUpdater Updater(&MSSA);
// Create the load memory acccess
LoadInst *LoadInst = B.CreateLoad(FirstArg);
- MemoryUse *LoadAccess = cast<MemoryUse>(MSSA.createMemoryAccessInBB(
+ MemoryUse *LoadAccess = cast<MemoryUse>(Updater.createMemoryAccessInBB(
LoadInst, nullptr, AfterLoopBB, MemorySSA::Beginning));
Updater.insertUse(LoadAccess);
MSSA.verifyMemorySSA();
OpenPOWER on IntegriCloud