Diff 86147

llvm/trunk/include/llvm/Transforms/Utils/MemorySSA.h

Show First 20 Lines • Show All 67 Lines • ▼ Show 20 Lines
// definitions, which would require multiple phis, and multiple memoryaccesses		// definitions, which would require multiple phis, and multiple memoryaccesses
// per instruction.		// per instruction.
//===----------------------------------------------------------------------===//		//===----------------------------------------------------------------------===//

#ifndef LLVM_TRANSFORMS_UTILS_MEMORYSSA_H		#ifndef LLVM_TRANSFORMS_UTILS_MEMORYSSA_H
#define LLVM_TRANSFORMS_UTILS_MEMORYSSA_H		#define LLVM_TRANSFORMS_UTILS_MEMORYSSA_H

#include "llvm/ADT/DenseMap.h"		#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/GraphTraits.h"		#include "llvm/ADT/GraphTraits.h"
#include "llvm/ADT/SmallPtrSet.h"		#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"		#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/ilist.h"		#include "llvm/ADT/ilist.h"
#include "llvm/ADT/ilist_node.h"		#include "llvm/ADT/ilist_node.h"
#include "llvm/ADT/iterator.h"		#include "llvm/ADT/iterator.h"
#include "llvm/ADT/iterator_range.h"		#include "llvm/ADT/iterator_range.h"
#include "llvm/Analysis/AliasAnalysis.h"		#include "llvm/Analysis/AliasAnalysis.h"
Show All 20 Lines
namespace llvm {		namespace llvm {

class Function;		class Function;
class Instruction;		class Instruction;
class MemoryAccess;		class MemoryAccess;
class LLVMContext;		class LLVMContext;
class raw_ostream;		class raw_ostream;
namespace MSSAHelpers {		namespace MSSAHelpers {

struct AllAccessTag {};		struct AllAccessTag {};
struct DefsOnlyTag {};		struct DefsOnlyTag {};
}		}

enum {		enum {
// Used to signify what the default invalid ID is for MemoryAccess's		// Used to signify what the default invalid ID is for MemoryAccess's
// getID()		// getID()
INVALID_MEMORYACCESS_ID = 0		INVALID_MEMORYACCESS_ID = 0
▲ Show 20 Lines • Show All 77 Lines • ▼ Show 20 Lines

protected:		protected:
friend class MemorySSA;		friend class MemorySSA;
friend class MemoryUseOrDef;		friend class MemoryUseOrDef;
friend class MemoryUse;		friend class MemoryUse;
friend class MemoryDef;		friend class MemoryDef;
friend class MemoryPhi;		friend class MemoryPhi;

		/// \brief Used by MemorySSA to change the block of a MemoryAccess when it is
		/// moved.
		void setBlock(BasicBlock *BB) { Block = BB; }

/// \brief Used for debugging and tracking things about MemoryAccesses.		/// \brief Used for debugging and tracking things about MemoryAccesses.
/// Guaranteed unique among MemoryAccesses, no guarantees otherwise.		/// Guaranteed unique among MemoryAccesses, no guarantees otherwise.
virtual unsigned getID() const = 0;		virtual unsigned getID() const = 0;

MemoryAccess(LLVMContext &C, unsigned Vty, BasicBlock *BB,		MemoryAccess(LLVMContext &C, unsigned Vty, BasicBlock *BB,
unsigned NumOperands)		unsigned NumOperands)
: User(Type::getVoidTy(C), Vty, nullptr, NumOperands), Block(BB) {}		: User(Type::getVoidTy(C), Vty, nullptr, NumOperands), Block(BB) {}

Show All 28 Lines	public:

static inline bool classof(const MemoryUseOrDef *) { return true; }		static inline bool classof(const MemoryUseOrDef *) { return true; }
static inline bool classof(const Value *MA) {		static inline bool classof(const Value *MA) {
return MA->getValueID() == MemoryUseVal \|\| MA->getValueID() == MemoryDefVal;		return MA->getValueID() == MemoryUseVal \|\| MA->getValueID() == MemoryDefVal;
}		}

protected:		protected:
friend class MemorySSA;		friend class MemorySSA;
		friend class MemorySSAUpdater;
MemoryUseOrDef(LLVMContext &C, MemoryAccess *DMA, unsigned Vty,		MemoryUseOrDef(LLVMContext &C, MemoryAccess *DMA, unsigned Vty,
Instruction MI, BasicBlock BB)		Instruction MI, BasicBlock BB)
: MemoryAccess(C, Vty, BB, 1), MemoryInst(MI) {		: MemoryAccess(C, Vty, BB, 1), MemoryInst(MI) {
setDefiningAccess(DMA);		setDefiningAccess(DMA);
}		}

void setDefiningAccess(MemoryAccess *DMA) { setOperand(0, DMA); }		void setDefiningAccess(MemoryAccess *DMA) { setOperand(0, DMA); }

▲ Show 20 Lines • Show All 361 Lines • ▼ Show 20 Lines	MemoryAccess createMemoryAccessInBB(Instruction I, MemoryAccess *Definition,
InsertionPlace Point);		InsertionPlace Point);

/// \brief Create a MemoryAccess in MemorySSA before or after an existing		/// \brief Create a MemoryAccess in MemorySSA before or after an existing
/// MemoryAccess.		/// MemoryAccess.
///		///
/// Returns the new MemoryAccess.		/// Returns the new MemoryAccess.
/// This should be called when a memory instruction is created that is being		/// 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		/// used to replace an existing memory instruction. It will not create PHI
/// nodes, or verify the clobbering definition. The clobbering definition		/// nodes, or verify the clobbering definition.
/// must be non-null.		///
/// Note: If a MemoryAccess already exists for I, this function will make it		/// Note: If a MemoryAccess already exists for I, this function will make it
/// inaccessible and it must have removeMemoryAccess called on it.		/// inaccessible and it must have removeMemoryAccess called on it.
MemoryUseOrDef createMemoryAccessBefore(Instruction I,		MemoryUseOrDef createMemoryAccessBefore(Instruction I,
MemoryAccess *Definition,		MemoryAccess *Definition,
MemoryUseOrDef *InsertPt);		MemoryUseOrDef *InsertPt);
MemoryUseOrDef createMemoryAccessAfter(Instruction I,		MemoryUseOrDef createMemoryAccessAfter(Instruction I,
MemoryAccess *Definition,		MemoryAccess *Definition,
MemoryAccess *InsertPt);		MemoryAccess *InsertPt);

// \brief Splice \p What to just before \p Where.
//
// In order to be efficient, the following conditions must be met:
// - \p Where dominates \p What,
// - All memory accesses in [\p Where, \p What) are no-alias with \p What.
//
// TODO: relax the MemoryDef requirement on Where.
void spliceMemoryAccessAbove(MemoryDef Where, MemoryUseOrDef What);

/// \brief Remove a MemoryAccess from MemorySSA, including updating all		/// \brief Remove a MemoryAccess from MemorySSA, including updating all
/// definitions and uses.		/// definitions and uses.
/// This should be called when a memory instruction that has a MemoryAccess		/// 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		/// associated with it is erased from the program. For example, if a store or
/// load is simply erased (not replaced), removeMemoryAccess should be called		/// load is simply erased (not replaced), removeMemoryAccess should be called
/// on the MemoryAccess for that store/load.		/// on the MemoryAccess for that store/load.
void removeMemoryAccess(MemoryAccess *);		void removeMemoryAccess(MemoryAccess *);

Show All 12 Lines	public:
/// \brief Verify that MemorySSA is self consistent (IE definitions dominate		/// \brief Verify that MemorySSA is self consistent (IE definitions dominate
/// all uses, uses appear in the right places). This is used by unit tests.		/// all uses, uses appear in the right places). This is used by unit tests.
void verifyMemorySSA() const;		void verifyMemorySSA() const;

protected:		protected:
// Used by Memory SSA annotater, dumpers, and wrapper pass		// Used by Memory SSA annotater, dumpers, and wrapper pass
friend class MemorySSAAnnotatedWriter;		friend class MemorySSAAnnotatedWriter;
friend class MemorySSAPrinterLegacyPass;		friend class MemorySSAPrinterLegacyPass;
		friend class MemorySSAUpdater;

void verifyDefUses(Function &F) const;		void verifyDefUses(Function &F) const;
void verifyDomination(Function &F) const;		void verifyDomination(Function &F) const;
void verifyOrdering(Function &F) const;		void verifyOrdering(Function &F) const;

// This is used by the use optimizer and updater.		// This is used by the use optimizer and updater.
AccessList getWritableBlockAccesses(const BasicBlock BB) const {		AccessList getWritableBlockAccesses(const BasicBlock BB) const {
auto It = PerBlockAccesses.find(BB);		auto It = PerBlockAccesses.find(BB);
return It == PerBlockAccesses.end() ? nullptr : It->second.get();		return It == PerBlockAccesses.end() ? nullptr : It->second.get();
}		}

// This is used by the use optimizer and updater.		// This is used by the use optimizer and updater.
DefsList getWritableBlockDefs(const BasicBlock BB) const {		DefsList getWritableBlockDefs(const BasicBlock BB) const {
auto It = PerBlockDefs.find(BB);		auto It = PerBlockDefs.find(BB);
return It == PerBlockDefs.end() ? nullptr : It->second.get();		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.
		void moveTo(MemoryUseOrDef What, BasicBlock BB, AccessList::iterator Where);

private:		private:
class CachingWalker;		class CachingWalker;
class OptimizeUses;		class OptimizeUses;

CachingWalker *getWalkerImpl();		CachingWalker *getWalkerImpl();
void buildMemorySSA();		void buildMemorySSA();
void optimizeUses();		void optimizeUses();

void verifyUseInDefs(MemoryAccess , MemoryAccess ) const;		void verifyUseInDefs(MemoryAccess , MemoryAccess ) const;
using AccessMap = DenseMap<const BasicBlock *, std::unique_ptr<AccessList>>;		using AccessMap = DenseMap<const BasicBlock *, std::unique_ptr<AccessList>>;
using DefsMap = DenseMap<const BasicBlock *, std::unique_ptr<DefsList>>;		using DefsMap = DenseMap<const BasicBlock *, std::unique_ptr<DefsList>>;

void		void
determineInsertionPoint(const SmallPtrSetImpl<BasicBlock *> &DefiningBlocks);		determineInsertionPoint(const SmallPtrSetImpl<BasicBlock *> &DefiningBlocks);
void computeDomLevels(DenseMap<DomTreeNode *, unsigned> &DomLevels);		void computeDomLevels(DenseMap<DomTreeNode *, unsigned> &DomLevels);
void markUnreachableAsLiveOnEntry(BasicBlock *BB);		void markUnreachableAsLiveOnEntry(BasicBlock *BB);
bool dominatesUse(const MemoryAccess , const MemoryAccess ) const;		bool dominatesUse(const MemoryAccess , const MemoryAccess ) const;
MemoryUseOrDef createNewAccess(Instruction );		MemoryUseOrDef createNewAccess(Instruction );
MemoryUseOrDef createDefinedAccess(Instruction , MemoryAccess *);		MemoryUseOrDef createDefinedAccess(Instruction , MemoryAccess *);
MemoryAccess findDominatingDef(BasicBlock , enum InsertionPlace);		MemoryAccess findDominatingDef(BasicBlock , enum InsertionPlace);
void removeFromLookups(MemoryAccess *);		void removeFromLookups(MemoryAccess *);
		void removeFromLists(MemoryAccess *, bool ShouldDelete = true);

void placePHINodes(const SmallPtrSetImpl<BasicBlock *> &,		void placePHINodes(const SmallPtrSetImpl<BasicBlock *> &,
const DenseMap<const BasicBlock *, unsigned int> &);		const DenseMap<const BasicBlock *, unsigned int> &);
MemoryAccess renameBlock(BasicBlock , MemoryAccess *);		MemoryAccess renameBlock(BasicBlock , MemoryAccess *);
void renamePass(DomTreeNode , MemoryAccess IncomingVal,		void renamePass(DomTreeNode , MemoryAccess IncomingVal,
SmallPtrSet<BasicBlock *, 16> &Visited);		SmallPtrSet<BasicBlock *, 16> &Visited);
AccessList getOrCreateAccessList(const BasicBlock );		AccessList getOrCreateAccessList(const BasicBlock );
DefsList getOrCreateDefsList(const BasicBlock );		DefsList getOrCreateDefsList(const BasicBlock );
Show All 24 Lines	private:
mutable SmallPtrSet<const BasicBlock *, 16> BlockNumberingValid;		mutable SmallPtrSet<const BasicBlock *, 16> BlockNumberingValid;
mutable DenseMap<const MemoryAccess *, unsigned long> BlockNumbering;		mutable DenseMap<const MemoryAccess *, unsigned long> BlockNumbering;

// Memory SSA building info		// Memory SSA building info
std::unique_ptr<CachingWalker> Walker;		std::unique_ptr<CachingWalker> Walker;
unsigned NextID;		unsigned NextID;
};		};

		// An automatic updater for MemorySSA that handles arbitrary insertion,
		// deletion, and moves. It performs phi insertion where necessary, and
		// automatically updates the MemorySSA IR to be correct.
		// While updating loads or removing instructions is often easy enough to not
		// need this, updating stores should generally not be attemped outside this
		// API.
		//
		// Basic API usage:
		// Create the memory access you want for the instruction (this is mainly so
		// we know where it is, without having to duplicate the entire set of create
		// functions MemorySSA supports).
		// Call insertDef or insertUse depending on whether it's a MemoryUse or a
		// MemoryDef.
		// That's it.
		//
		// For moving, first, move the instruction itself using the normal SSA
		// instruction moving API, then just call moveBefore or moveAfter with the right
		// arguments.
		//
		class MemorySSAUpdater {
		private:
		MemorySSA *MSSA;
		SmallVector<MemoryPhi *, 8> InsertedPHIs;
		SmallPtrSet<BasicBlock *, 8> VisitedBlocks;

		public:
		MemorySSAUpdater(MemorySSA *MSSA) : MSSA(MSSA) {}
		void insertDef(MemoryDef *Def);
		void insertUse(MemoryUse *Use);
		void moveBefore(MemoryUseOrDef What, MemoryUseOrDef Where);
		void moveAfter(MemoryUseOrDef What, MemoryUseOrDef Where);

		private:
		void moveTo(MemoryUseOrDef What, BasicBlock BB,
		MemorySSA::AccessList::iterator Where);
		MemoryAccess getPreviousDef(MemoryAccess );
		MemoryAccess getPreviousDefInBlock(MemoryAccess );
		MemoryAccess getPreviousDefFromEnd(BasicBlock );
		MemoryAccess getPreviousDefRecursive(BasicBlock );
		MemoryAccess recursePhi(MemoryAccess Phi);
		template <class RangeType>
		MemoryAccess tryRemoveTrivialPhi(MemoryPhi Phi, RangeType &Operands);
		void fixupDefs(const SmallVectorImpl<MemoryAccess *> &);
		};

// This pass does eager building and then printing of MemorySSA. It is used by		// This pass does eager building and then printing of MemorySSA. It is used by
// the tests to be able to build, dump, and verify Memory SSA.		// the tests to be able to build, dump, and verify Memory SSA.
class MemorySSAPrinterLegacyPass : public FunctionPass {		class MemorySSAPrinterLegacyPass : public FunctionPass {
public:		public:
MemorySSAPrinterLegacyPass();		MemorySSAPrinterLegacyPass();

bool runOnFunction(Function &) override;		bool runOnFunction(Function &) override;
void getAnalysisUsage(AnalysisUsage &AU) const override;		void getAnalysisUsage(AnalysisUsage &AU) const override;
▲ Show 20 Lines • Show All 333 Lines • Show Last 20 Lines

llvm/trunk/lib/Transforms/Utils/MemorySSA.cpp

Show First 20 Lines • Show All 1,620 Lines • ▼ Show 20 Lines	if (WasEnd) {
if (InsertPt == Accesses->end())		if (InsertPt == Accesses->end())
Defs->push_back(*What);		Defs->push_back(*What);
else		else
Defs->insert(InsertPt->getDefsIterator(), *What);		Defs->insert(InsertPt->getDefsIterator(), *What);
}		}
}		}
}		}

		// Move What before Where in the IR. The end result is taht What will belong to
		// the right lists and have the right Block set, but will not otherwise be
		// correct. It will not have the right defining access, and if it is a def,
		// things below it will not properly be updated.
		void MemorySSA::moveTo(MemoryUseOrDef What, BasicBlock BB,
		AccessList::iterator Where) {
		// Keep it in the lookup tables, remove from the lists
		removeFromLists(What, false);
		What->setBlock(BB);
		insertIntoListsBefore(What, BB, Where);
		}

MemoryPhi MemorySSA::createMemoryPhi(BasicBlock BB) {		MemoryPhi MemorySSA::createMemoryPhi(BasicBlock BB) {
assert(!getMemoryAccess(BB) && "MemoryPhi already exists for this BB");		assert(!getMemoryAccess(BB) && "MemoryPhi already exists for this BB");
MemoryPhi *Phi = new MemoryPhi(BB->getContext(), BB, NextID++);		MemoryPhi *Phi = new MemoryPhi(BB->getContext(), BB, NextID++);
insertIntoListsForBlock(Phi, BB, Beginning);		insertIntoListsForBlock(Phi, BB, Beginning);
ValueToMemoryAccess[BB] = Phi;		ValueToMemoryAccess[BB] = Phi;
// Phi's always are placed at the front of the block.		// Phi's always are placed at the front of the block.
BlockNumberingValid.erase(BB);		BlockNumberingValid.erase(BB);
return Phi;		return Phi;
Show All 39 Lines	assert(I->getParent() == InsertPt->getBlock() &&
"New and old access must be in the same block");		"New and old access must be in the same block");
MemoryUseOrDef *NewAccess = createDefinedAccess(I, Definition);		MemoryUseOrDef *NewAccess = createDefinedAccess(I, Definition);
BlockNumberingValid.erase(InsertPt->getBlock());		BlockNumberingValid.erase(InsertPt->getBlock());
insertIntoListsBefore(NewAccess, InsertPt->getBlock(),		insertIntoListsBefore(NewAccess, InsertPt->getBlock(),
++(InsertPt->getIterator()));		++(InsertPt->getIterator()));
return NewAccess;		return NewAccess;
}		}

void MemorySSA::spliceMemoryAccessAbove(MemoryDef *Where,
MemoryUseOrDef *What) {
assert(What != getLiveOnEntryDef() && Where != getLiveOnEntryDef() &&
"Can't splice (above) LOE.");
assert(dominates(Where, What) && "Only upwards splices are permitted.");

if (Where == What)
return;
if (isa<MemoryDef>(What)) {
// TODO: possibly use removeMemoryAccess' more efficient RAUW
What->replaceAllUsesWith(What->getDefiningAccess());
What->setDefiningAccess(Where->getDefiningAccess());
Where->setDefiningAccess(What);
}
AccessList *Src = getWritableBlockAccesses(What->getBlock());
AccessList *Dest = getWritableBlockAccesses(Where->getBlock());
Dest->splice(AccessList::iterator(Where), *Src, What);

BlockNumberingValid.erase(What->getBlock());
if (What->getBlock() != Where->getBlock())
BlockNumberingValid.erase(Where->getBlock());
}

/// \brief Helper function to create new memory accesses		/// \brief Helper function to create new memory accesses
MemoryUseOrDef MemorySSA::createNewAccess(Instruction I) {		MemoryUseOrDef MemorySSA::createNewAccess(Instruction I) {
// The assume intrinsic has a control dependency which we model by claiming		// The assume intrinsic has a control dependency which we model by claiming
// that it writes arbitrarily. Ignore that fake memory dependency here.		// that it writes arbitrarily. Ignore that fake memory dependency here.
// FIXME: Replace this special casing with a more accurate modelling of		// FIXME: Replace this special casing with a more accurate modelling of
// assume's control dependency.		// assume's control dependency.
if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I))		if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I))
if (II->getIntrinsicID() == Intrinsic::assume)		if (II->getIntrinsicID() == Intrinsic::assume)
▲ Show 20 Lines • Show All 75 Lines • ▼ Show 20 Lines	if (!MA)
MA = cast<MemoryAccess>(Arg);		MA = cast<MemoryAccess>(Arg);
else if (MA != Arg)		else if (MA != Arg)
return nullptr;		return nullptr;
}		}
return MA;		return MA;
}		}

/// \brief Properly remove \p MA from all of MemorySSA's lookup tables.		/// \brief Properly remove \p MA from all of MemorySSA's lookup tables.
///
/// Because of the way the intrusive list and use lists work, it is important to
/// do removal in the right order.
void MemorySSA::removeFromLookups(MemoryAccess *MA) {		void MemorySSA::removeFromLookups(MemoryAccess *MA) {
assert(MA->use_empty() &&		assert(MA->use_empty() &&
"Trying to remove memory access that still has uses");		"Trying to remove memory access that still has uses");
BlockNumbering.erase(MA);		BlockNumbering.erase(MA);
if (MemoryUseOrDef *MUD = dyn_cast<MemoryUseOrDef>(MA))		if (MemoryUseOrDef *MUD = dyn_cast<MemoryUseOrDef>(MA))
MUD->setDefiningAccess(nullptr);		MUD->setDefiningAccess(nullptr);
// Invalidate our walker's cache if necessary		// Invalidate our walker's cache if necessary
if (!isa<MemoryUse>(MA))		if (!isa<MemoryUse>(MA))
Walker->invalidateInfo(MA);		Walker->invalidateInfo(MA);
// The call below to erase will destroy MA, so we can't change the order we		// The call below to erase will destroy MA, so we can't change the order we
// are doing things here		// are doing things here
Value *MemoryInst;		Value *MemoryInst;
if (MemoryUseOrDef *MUD = dyn_cast<MemoryUseOrDef>(MA)) {		if (MemoryUseOrDef *MUD = dyn_cast<MemoryUseOrDef>(MA)) {
MemoryInst = MUD->getMemoryInst();		MemoryInst = MUD->getMemoryInst();
} else {		} else {
MemoryInst = MA->getBlock();		MemoryInst = MA->getBlock();
}		}
auto VMA = ValueToMemoryAccess.find(MemoryInst);		auto VMA = ValueToMemoryAccess.find(MemoryInst);
if (VMA->second == MA)		if (VMA->second == MA)
ValueToMemoryAccess.erase(VMA);		ValueToMemoryAccess.erase(VMA);
		}

		/// \brief Properly remove \p MA from all of MemorySSA's lists.
		///
		/// Because of the way the intrusive list and use lists work, it is important to
		/// do removal in the right order.
		/// ShouldDelete defaults to true, and will cause the memory access to also be
		/// deleted, not just removed.
		void MemorySSA::removeFromLists(MemoryAccess *MA, bool ShouldDelete) {
// The access list owns the reference, so we erase it from the non-owning list		// The access list owns the reference, so we erase it from the non-owning list
// first.		// first.
if (!isa<MemoryUse>(MA)) {		if (!isa<MemoryUse>(MA)) {
auto DefsIt = PerBlockDefs.find(MA->getBlock());		auto DefsIt = PerBlockDefs.find(MA->getBlock());
std::unique_ptr<DefsList> &Defs = DefsIt->second;		std::unique_ptr<DefsList> &Defs = DefsIt->second;
Defs->remove(*MA);		Defs->remove(*MA);
if (Defs->empty())		if (Defs->empty())
PerBlockDefs.erase(DefsIt);		PerBlockDefs.erase(DefsIt);
}		}

		// The erase call here will delete it. If we don't want it deleted, we call
		// remove instead.
auto AccessIt = PerBlockAccesses.find(MA->getBlock());		auto AccessIt = PerBlockAccesses.find(MA->getBlock());
std::unique_ptr<AccessList> &Accesses = AccessIt->second;		std::unique_ptr<AccessList> &Accesses = AccessIt->second;
		if (ShouldDelete)
Accesses->erase(MA);		Accesses->erase(MA);
		else
		Accesses->remove(MA);

if (Accesses->empty())		if (Accesses->empty())
PerBlockAccesses.erase(AccessIt);		PerBlockAccesses.erase(AccessIt);
}		}

void MemorySSA::removeMemoryAccess(MemoryAccess *MA) {		void MemorySSA::removeMemoryAccess(MemoryAccess *MA) {
assert(!isLiveOnEntryDef(MA) && "Trying to remove the live on entry def");		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		// We can only delete phi nodes if they have no uses, or we can replace all
// uses with a single definition.		// uses with a single definition.
MemoryAccess *NewDefTarget = nullptr;		MemoryAccess *NewDefTarget = nullptr;
if (MemoryPhi *MP = dyn_cast<MemoryPhi>(MA)) {		if (MemoryPhi *MP = dyn_cast<MemoryPhi>(MA)) {
// Note that it is sufficient to know that all edges of the phi node have		// 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		// 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,		// (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		// and thus, must dominate the phi's uses, and so we will not hit the assert
// below.		// below.
NewDefTarget = onlySingleValue(MP);		NewDefTarget = onlySingleValue(MP);
assert((NewDefTarget \|\| MP->use_empty()) &&		assert((NewDefTarget \|\| MP->use_empty()) &&
"We can't delete this memory phi");		"We can't delete this memory phi");
} else {		} else {
NewDefTarget = cast<MemoryUseOrDef>(MA)->getDefiningAccess();		NewDefTarget = cast<MemoryUseOrDef>(MA)->getDefiningAccess();
}		}

// Re-point the uses at our defining access		// Re-point the uses at our defining access
if (!MA->use_empty()) {		if (!isa<MemoryUse>(MA) && !MA->use_empty()) {
// Reset optimized on users of this store, and reset the uses.		// Reset optimized on users of this store, and reset the uses.
// A few notes:		// A few notes:
// 1. This is a slightly modified version of RAUW to avoid walking the		// 1. This is a slightly modified version of RAUW to avoid walking the
// uses twice here.		// uses twice here.
// 2. If we wanted to be complete, we would have to reset the optimized		// 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		// 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		// the same arguments. Instead, we prefer users to removeMemoryAccess those
// phi nodes, because doing it here would be N^3.		// phi nodes, because doing it here would be N^3.
if (MA->hasValueHandle())		if (MA->hasValueHandle())
ValueHandleBase::ValueIsRAUWd(MA, NewDefTarget);		ValueHandleBase::ValueIsRAUWd(MA, NewDefTarget);
// Note: We assume MemorySSA is not used in metadata since it's not really		// Note: We assume MemorySSA is not used in metadata since it's not really
// part of the IR.		// part of the IR.

while (!MA->use_empty()) {		while (!MA->use_empty()) {
Use &U = *MA->use_begin();		Use &U = *MA->use_begin();
if (MemoryUse *MU = dyn_cast<MemoryUse>(U.getUser()))		if (MemoryUse *MU = dyn_cast<MemoryUse>(U.getUser()))
MU->resetOptimized();		MU->resetOptimized();
U.set(NewDefTarget);		U.set(NewDefTarget);
}		}
}		}

// The call below to erase will destroy MA, so we can't change the order we		// The call below to erase will destroy MA, so we can't change the order we
// are doing things here		// are doing things here
removeFromLookups(MA);		removeFromLookups(MA);
		removeFromLists(MA);
}		}

void MemorySSA::print(raw_ostream &OS) const {		void MemorySSA::print(raw_ostream &OS) const {
MemorySSAAnnotatedWriter Writer(this);		MemorySSAAnnotatedWriter Writer(this);
F.print(OS, &Writer);		F.print(OS, &Writer);
}		}

void MemorySSA::dump() const {		void MemorySSA::dump() const {
▲ Show 20 Lines • Show All 500 Lines • ▼ Show 20 Lines
}		}

MemoryAccess *DoNothingMemorySSAWalker::getClobberingMemoryAccess(		MemoryAccess *DoNothingMemorySSAWalker::getClobberingMemoryAccess(
MemoryAccess *StartingAccess, const MemoryLocation &) {		MemoryAccess *StartingAccess, const MemoryLocation &) {
if (auto *Use = dyn_cast<MemoryUseOrDef>(StartingAccess))		if (auto *Use = dyn_cast<MemoryUseOrDef>(StartingAccess))
return Use->getDefiningAccess();		return Use->getDefiningAccess();
return StartingAccess;		return StartingAccess;
}		}
		// This is the marker algorithm from "Simple and Efficient Construction of
		// Static Single Assignment Form"
		// The simple, non-marker algorithm places phi nodes at any join
		// Here, we place markers, and only place phi nodes if they end up necessary.
		// They are only necessary if they break a cycle (IE we recursively visit
		// ourselves again), or we discover, while getting the value of the operands,
		// that there are two or more definitions needing to be merged.
		// This still will leave non-minimal form in the case of irreducible control
		// flow, where phi nodes may be in cycles with themselves, but unnecessary.
		MemoryAccess MemorySSAUpdater::getPreviousDefRecursive(BasicBlock BB) {
		// Single predecessor case, just recurse, we can only have one definition.
		if (BasicBlock *Pred = BB->getSinglePredecessor()) {
		return getPreviousDefFromEnd(Pred);
		} else if (VisitedBlocks.count(BB)) {
		// We hit our node again, meaning we had a cycle, we must insert a phi
		// node to break it so we have an operand. The only case this will
		// insert useless phis is if we have irreducible control flow.
		return MSSA->createMemoryPhi(BB);
		} else if (VisitedBlocks.insert(BB).second) {
		// Mark us visited so we can detect a cycle
		SmallVector<MemoryAccess *, 8> PhiOps;

		// Recurse to get the values in our predecessors for placement of a
		// potential phi node. This will insert phi nodes if we cycle in order to
		// break the cycle and have an operand.
		for (auto *Pred : predecessors(BB))
		PhiOps.push_back(getPreviousDefFromEnd(Pred));

		// Now try to simplify the ops to avoid placing a phi.
		// This may return null if we never created a phi yet, that's okay
		MemoryPhi *Phi = dyn_cast_or_null<MemoryPhi>(MSSA->getMemoryAccess(BB));
		bool PHIExistsButNeedsUpdate = false;
		// See if the existing phi operands match what we need.
		// Unlike normal SSA, we only allow one phi node per block, so we can't just
		// create a new one.
		if (Phi && Phi->getNumOperands() != 0)
		if (!std::equal(Phi->op_begin(), Phi->op_end(), PhiOps.begin())) {
		PHIExistsButNeedsUpdate = true;
		}

		// See if we can avoid the phi by simplifying it.
		auto *Result = tryRemoveTrivialPhi(Phi, PhiOps);
		// If we couldn't simplify, we may have to create a phi
		if (Result == Phi) {
		if (!Phi)
		Phi = MSSA->createMemoryPhi(BB);

		// These will have been filled in by the recursive read we did above.
		if (PHIExistsButNeedsUpdate) {
		std::copy(PhiOps.begin(), PhiOps.end(), Phi->op_begin());
		std::copy(pred_begin(BB), pred_end(BB), Phi->block_begin());
		} else {
		unsigned i = 0;
		for (auto *Pred : predecessors(BB))
		Phi->addIncoming(PhiOps[i++], Pred);
		}

		Result = Phi;
		}
		if (MemoryPhi *MP = dyn_cast<MemoryPhi>(Result))
		InsertedPHIs.push_back(MP);
		// Set ourselves up for the next variable by resetting visited state.
		VisitedBlocks.erase(BB);
		return Result;
		}
		llvm_unreachable("Should have hit one of the three cases above");
		}

		// This starts at the memory access, and goes backwards in the block to find the
		// previous definition. If a definition is not found the block of the access,
		// it continues globally, creating phi nodes to ensure we have a single
		// definition.
		MemoryAccess MemorySSAUpdater::getPreviousDef(MemoryAccess MA) {
		auto *LocalResult = getPreviousDefInBlock(MA);

		return LocalResult ? LocalResult : getPreviousDefRecursive(MA->getBlock());
		}

		// This starts at the memory access, and goes backwards in the block to the find
		// the previous definition. If the definition is not found in the block of the
		// access, it returns nullptr.
		MemoryAccess MemorySSAUpdater::getPreviousDefInBlock(MemoryAccess MA) {
		auto *Defs = MSSA->getWritableBlockDefs(MA->getBlock());

		// It's possible there are no defs, or we got handed the first def to start.
		if (Defs) {
		// If this is a def, we can just use the def iterators.
		if (!isa<MemoryUse>(MA)) {
		auto Iter = MA->getReverseDefsIterator();
		++Iter;
		if (Iter != Defs->rend())
		return &*Iter;
		} else {
		// Otherwise, have to walk the all access iterator.
		auto Iter = MA->getReverseIterator();
		++Iter;
		while (&Iter != &Defs->begin()) {
		if (!isa<MemoryUse>(*Iter))
		return &*Iter;
		--Iter;
		}
		// At this point it must be pointing at firstdef
		assert(&Iter == &Defs->begin() &&
		"Should have hit first def walking backwards");
		return &*Iter;
		}
		}
		return nullptr;
		}

		// This starts at the end of block
		MemoryAccess MemorySSAUpdater::getPreviousDefFromEnd(BasicBlock BB) {
		auto *Defs = MSSA->getWritableBlockDefs(BB);

		if (Defs)
		return &*Defs->rbegin();

		return getPreviousDefRecursive(BB);
		}
		// Recurse over a set of phi uses to eliminate the trivial ones
		MemoryAccess MemorySSAUpdater::recursePhi(MemoryAccess Phi) {
		if (!Phi)
		return nullptr;
		TrackingVH<MemoryAccess> Res(Phi);
		SmallVector<TrackingVH<Value>, 8> Uses;
		std::copy(Phi->user_begin(), Phi->user_end(), std::back_inserter(Uses));
		for (auto &U : Uses) {
		if (MemoryPhi UsePhi = dyn_cast<MemoryPhi>(&U)) {
		auto OperRange = UsePhi->operands();
		tryRemoveTrivialPhi(UsePhi, OperRange);
		}
		}
		return Res;
		}

		// Eliminate trivial phis
		// Phis are trivial if they are defined either by themselves, or all the same
		// argument.
		// IE phi(a, a) or b = phi(a, b) or c = phi(a, a, c)
		// We recursively try to remove them.
		template <class RangeType>
		MemoryAccess MemorySSAUpdater::tryRemoveTrivialPhi(MemoryPhi Phi,
		RangeType &Operands) {
		// Detect equal or self arguments
		MemoryAccess *Same = nullptr;
		for (auto &Op : Operands) {
		// If the same or self, good so far
		if (Op == Phi \|\| Op == Same)
		continue;
		// not the same, return the phi since it's not eliminatable by us
		if (Same)
		return Phi;
		Same = cast<MemoryAccess>(Op);
		}
		// Never found a non-self reference, the phi is undef
		if (Same == nullptr)
		return MSSA->getLiveOnEntryDef();
		if (Phi) {
		Phi->replaceAllUsesWith(Same);
		MSSA->removeMemoryAccess(Phi);
		}

		// We should only end up recursing in case we replaced something, in which
		// case, we may have made other Phis trivial.
		return recursePhi(Same);
		}

		void MemorySSAUpdater::insertUse(MemoryUse *MU) {
		InsertedPHIs.clear();
		MU->setDefiningAccess(getPreviousDef(MU));
		// Unlike for defs, there is no extra work to do. Because uses do not create
		// new may-defs, there are only two cases:
		//
		// 1. There was a def already below us, and therefore, we should not have
		// created a phi node because it was already needed for the def.
		//
		// 2. There is no def below us, and therefore, there is no extra renaming work
		// to do.
		}

		void setMemoryPhiValueForBlock(MemoryPhi MP, const BasicBlock BB,
		MemoryAccess *NewDef) {
		// Replace any operand with us an incoming block with the new defining
		// access.
		int i = MP->getBasicBlockIndex(BB);
		assert(i != -1 && "Should have found the basic block in the phi");
		while (MP->getIncomingBlock(i) == BB) {
		// Unlike above, there is already a phi node here, so we only need
		// to set the right value.
		MP->setIncomingValue(i, NewDef);
		++i;
		}
		}

		// A brief description of the algorithm:
		// First, we compute what should define the new def, using the SSA
		// construction algorithm.
		// Then, we update the defs below us (and any new phi nodes) in the graph to
		// point to the correct new defs, to ensure we only have one variable, and no
		// disconnected stores.
		void MemorySSAUpdater::insertDef(MemoryDef *MD) {
		InsertedPHIs.clear();

		// See if we had a local def, and if not, go hunting.
		MemoryAccess *DefBefore = getPreviousDefInBlock(MD);
		bool DefBeforeSameBlock = DefBefore != nullptr;
		if (!DefBefore)
		DefBefore = getPreviousDefRecursive(MD->getBlock());

		// There is a def before us, which means we can replace any store/phi uses
		// of that thing with us, since we are in the way of whatever was there
		// before.
		// We now define that def's memorydefs and memoryphis
		for (auto UI = DefBefore->use_begin(), UE = DefBefore->use_end(); UI != UE;) {
		Use &U = *UI++;
		// Leave the uses alone
		if (isa<MemoryUse>(U.getUser()))
		continue;
		U.set(MD);
		}
		// and that def is now our defining access.
		// We change them in this order otherwise we will appear in the use list
		// above and reset ourselves.
		MD->setDefiningAccess(DefBefore);

		SmallVector<MemoryAccess *, 8> FixupList(InsertedPHIs.begin(),
		InsertedPHIs.end());
		if (!DefBeforeSameBlock) {
		// If there was a local def before us, we must have the same effect it
		// did. Because every may-def is the same, any phis/etc we would create, it
		// would also have created. If there was no local def before us, we
		// performed a global update, and have to search all successors and make
		// sure we update the first def in each of them (following all paths until
		// we hit the first def along each path). This may also insert phi nodes.
		// TODO: There are other cases we can skip this work, such as when we have a
		// single successor, and only used a straight line of single pred blocks
		// backwards to find the def. To make that work, we'd have to track whether
		// getDefRecursive only ever used the single predecessor case. These types
		// of paths also only exist in between CFG simplifications.
		FixupList.push_back(MD);
		}

		while (!FixupList.empty()) {
		unsigned StartingPHISize = InsertedPHIs.size();
		fixupDefs(FixupList);
		FixupList.clear();
		// Put any new phis on the fixup list, and process them
		FixupList.append(InsertedPHIs.end() - StartingPHISize, InsertedPHIs.end());
		}
		}

		void MemorySSAUpdater::fixupDefs(const SmallVectorImpl<MemoryAccess *> &Vars) {
		SmallPtrSet<const BasicBlock *, 8> Seen;
		SmallVector<const BasicBlock *, 16> Worklist;
		for (auto *NewDef : Vars) {
		// First, see if there is a local def after the operand.
		auto *Defs = MSSA->getWritableBlockDefs(NewDef->getBlock());
		auto DefIter = NewDef->getDefsIterator();

		// If there is a local def after us, we only have to rename that.
		if (++DefIter != Defs->end()) {
		cast<MemoryDef>(DefIter)->setDefiningAccess(NewDef);
		continue;
		}

		// Otherwise, we need to search down through the CFG.
		// For each of our successors, handle it directly if their is a phi, or
		// place on the fixup worklist.
		for (const auto *S : successors(NewDef->getBlock())) {
		if (auto *MP = MSSA->getMemoryAccess(S))
		setMemoryPhiValueForBlock(MP, NewDef->getBlock(), NewDef);
		else
		Worklist.push_back(S);
		}

		while (!Worklist.empty()) {
		const BasicBlock *FixupBlock = Worklist.back();
		Worklist.pop_back();

		// Get the first def in the block that isn't a phi node.
		if (auto *Defs = MSSA->getWritableBlockDefs(FixupBlock)) {
		auto FirstDef = &Defs->begin();
		// The loop above and below should have taken care of phi nodes
		assert(!isa<MemoryPhi>(FirstDef) &&
		"Should have already handled phi nodes!");
		// We are now this def's defining access, make sure we actually dominate
		// it
		assert(MSSA->dominates(NewDef, FirstDef) &&
		"Should have dominated the new access");

		// This may insert new phi nodes, because we are not guaranteed the
		// block we are processing has a single pred, and depending where the
		// store was inserted, it may require phi nodes below it.
		cast<MemoryDef>(FirstDef)->setDefiningAccess(getPreviousDef(FirstDef));
		return;
		}
		// We didn't find a def, so we must continue.
		for (const auto *S : successors(FixupBlock)) {
		// If there is a phi node, handle it.
		// Otherwise, put the block on the worklist
		if (auto *MP = MSSA->getMemoryAccess(S))
		setMemoryPhiValueForBlock(MP, FixupBlock, NewDef);
		else {
		// If we cycle, we should have ended up at a phi node that we already
		// processed. FIXME: Double check this
		if (!Seen.insert(S).second)
		continue;
		Worklist.push_back(S);
		}
		}
		}
		}
		}

		// Move What before Where in the MemorySSA IR.
		void MemorySSAUpdater::moveTo(MemoryUseOrDef What, BasicBlock BB,
		MemorySSA::AccessList::iterator Where) {
		// Replace all our users with our defining access.
		What->replaceAllUsesWith(What->getDefiningAccess());

		// Let MemorySSA take care of moving it around in the lists.
		MSSA->moveTo(What, BB, Where);

		// Now reinsert it into the IR and do whatever fixups needed.
		if (auto *MD = dyn_cast<MemoryDef>(What))
		insertDef(MD);
		else
		insertUse(cast<MemoryUse>(What));
		}
		// Move What before Where in the MemorySSA IR.
		void MemorySSAUpdater::moveBefore(MemoryUseOrDef What, MemoryUseOrDef Where) {
		moveTo(What, Where->getBlock(), Where->getIterator());
		}

		// Move What after Where in the MemorySSA IR.
		void MemorySSAUpdater::moveAfter(MemoryUseOrDef What, MemoryUseOrDef Where) {
		moveTo(What, Where->getBlock(), ++Where->getIterator());
		}

} // namespace llvm		} // namespace llvm

llvm/trunk/unittests/Transforms/Utils/MemorySSA.cpp

Show First 20 Lines • Show All 98 Lines • ▼ Show 20 Lines	TEST_F(MemorySSATest, CreateALoad) {

// Create the load memory acccess		// Create the load memory acccess
MemoryUse *LoadAccess = cast<MemoryUse>(		MemoryUse *LoadAccess = cast<MemoryUse>(
MSSA.createMemoryAccessInBB(LoadInst, MP, Merge, MemorySSA::Beginning));		MSSA.createMemoryAccessInBB(LoadInst, MP, Merge, MemorySSA::Beginning));
MemoryAccess *DefiningAccess = LoadAccess->getDefiningAccess();		MemoryAccess *DefiningAccess = LoadAccess->getDefiningAccess();
EXPECT_TRUE(isa<MemoryPhi>(DefiningAccess));		EXPECT_TRUE(isa<MemoryPhi>(DefiningAccess));
MSSA.verifyMemorySSA();		MSSA.verifyMemorySSA();
}		}
		TEST_F(MemorySSATest, CreateLoadsAndStoreUpdater) {
		// We create a diamond, then build memoryssa with no memory accesses, and
		// incrementally update it by inserting a store in the, entry, a load in the
		// merge point, then a store in the branch, another load in the merge point,
		// and then a store in the entry.
		F = Function::Create(
		FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
		GlobalValue::ExternalLinkage, "F", &M);
		BasicBlock *Entry(BasicBlock::Create(C, "", F));
		BasicBlock *Left(BasicBlock::Create(C, "", F));
		BasicBlock *Right(BasicBlock::Create(C, "", F));
		BasicBlock *Merge(BasicBlock::Create(C, "", F));
		B.SetInsertPoint(Entry);
		B.CreateCondBr(B.getTrue(), Left, Right);
		B.SetInsertPoint(Left, Left->begin());
		Argument PointerArg = &F->arg_begin();
		B.SetInsertPoint(Left);
		B.CreateBr(Merge);
		B.SetInsertPoint(Right);
		B.CreateBr(Merge);

		setupAnalyses();
		MemorySSA &MSSA = *Analyses->MSSA;
		MemorySSAUpdater Updater(&MSSA);
		// Add the store
		B.SetInsertPoint(Entry, Entry->begin());
		StoreInst *EntryStore = B.CreateStore(B.getInt8(16), PointerArg);
		MemoryAccess *EntryStoreAccess = MSSA.createMemoryAccessInBB(
		EntryStore, nullptr, Entry, MemorySSA::Beginning);
		Updater.insertDef(cast<MemoryDef>(EntryStoreAccess));

		// Add the load
		B.SetInsertPoint(Merge, Merge->begin());
		LoadInst *FirstLoad = B.CreateLoad(PointerArg);

		// MemoryPHI should not already exist.
		MemoryPhi *MP = MSSA.getMemoryAccess(Merge);
		EXPECT_EQ(MP, nullptr);

		// Create the load memory access
		MemoryUse *FirstLoadAccess = cast<MemoryUse>(MSSA.createMemoryAccessInBB(
		FirstLoad, nullptr, Merge, MemorySSA::Beginning));
		Updater.insertUse(FirstLoadAccess);
		// Should just have a load using the entry access, because it should discover
		// the phi is trivial
		EXPECT_EQ(FirstLoadAccess->getDefiningAccess(), EntryStoreAccess);

		// Create a store on the left
		// Add the store
		B.SetInsertPoint(Left, Left->begin());
		StoreInst *LeftStore = B.CreateStore(B.getInt8(16), PointerArg);
		MemoryAccess *LeftStoreAccess = MSSA.createMemoryAccessInBB(
		LeftStore, nullptr, Left, MemorySSA::Beginning);
		Updater.insertDef(cast<MemoryDef>(LeftStoreAccess));
		// We don't touch existing loads, so we need to create a new one to get a phi
		// Add the second load
		B.SetInsertPoint(Merge, Merge->begin());
		LoadInst *SecondLoad = B.CreateLoad(PointerArg);

		// MemoryPHI should not already exist.
		MP = MSSA.getMemoryAccess(Merge);
		EXPECT_EQ(MP, nullptr);

		// Create the load memory access
		MemoryUse *SecondLoadAccess = cast<MemoryUse>(MSSA.createMemoryAccessInBB(
		SecondLoad, nullptr, Merge, MemorySSA::Beginning));
		Updater.insertUse(SecondLoadAccess);
		// Now the load should be a phi of the entry store and the left store
		MemoryPhi *MergePhi =
		dyn_cast<MemoryPhi>(SecondLoadAccess->getDefiningAccess());
		EXPECT_NE(MergePhi, nullptr);
		EXPECT_EQ(MergePhi->getIncomingValue(0), EntryStoreAccess);
		EXPECT_EQ(MergePhi->getIncomingValue(1), LeftStoreAccess);
		// 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(
		SecondEntryStore, nullptr, Entry, MemorySSA::End);
		Updater.insertDef(cast<MemoryDef>(SecondEntryStoreAccess));
		// and make sure the phi below it got updated, despite being blocks away
		MergePhi = dyn_cast<MemoryPhi>(SecondLoadAccess->getDefiningAccess());
		EXPECT_NE(MergePhi, nullptr);
		EXPECT_EQ(MergePhi->getIncomingValue(0), SecondEntryStoreAccess);
		EXPECT_EQ(MergePhi->getIncomingValue(1), LeftStoreAccess);
		MSSA.verifyMemorySSA();
		}

		TEST_F(MemorySSATest, CreateALoadUpdater) {
		// We create a diamond, then build memoryssa with no memory accesses, and
		// incrementally update it by inserting a store in one of the branches, and a
		// load in the merge point
		F = Function::Create(
		FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
		GlobalValue::ExternalLinkage, "F", &M);
		BasicBlock *Entry(BasicBlock::Create(C, "", F));
		BasicBlock *Left(BasicBlock::Create(C, "", F));
		BasicBlock *Right(BasicBlock::Create(C, "", F));
		BasicBlock *Merge(BasicBlock::Create(C, "", F));
		B.SetInsertPoint(Entry);
		B.CreateCondBr(B.getTrue(), Left, Right);
		B.SetInsertPoint(Left, Left->begin());
		Argument PointerArg = &F->arg_begin();
		B.SetInsertPoint(Left);
		B.CreateBr(Merge);
		B.SetInsertPoint(Right);
		B.CreateBr(Merge);

		setupAnalyses();
		MemorySSA &MSSA = *Analyses->MSSA;
		MemorySSAUpdater Updater(&MSSA);
		B.SetInsertPoint(Left, Left->begin());
		// Add the store
		StoreInst *SI = B.CreateStore(B.getInt8(16), PointerArg);
		MemoryAccess *StoreAccess =
		MSSA.createMemoryAccessInBB(SI, nullptr, Left, MemorySSA::Beginning);
		Updater.insertDef(cast<MemoryDef>(StoreAccess));

		// Add the load
		B.SetInsertPoint(Merge, Merge->begin());
		LoadInst *LoadInst = B.CreateLoad(PointerArg);

		// MemoryPHI should not already exist.
		MemoryPhi *MP = MSSA.getMemoryAccess(Merge);
		EXPECT_EQ(MP, nullptr);

		// Create the load memory acccess
		MemoryUse *LoadAccess = cast<MemoryUse>(MSSA.createMemoryAccessInBB(
		LoadInst, nullptr, Merge, MemorySSA::Beginning));
		Updater.insertUse(LoadAccess);
		MemoryAccess *DefiningAccess = LoadAccess->getDefiningAccess();
		EXPECT_TRUE(isa<MemoryPhi>(DefiningAccess));
		MSSA.verifyMemorySSA();
		}

TEST_F(MemorySSATest, MoveAStore) {		TEST_F(MemorySSATest, MoveAStore) {
// We create a diamond where there is a in the entry, a store on one side, and		// We create a diamond where there is a in the entry, a store on one side, and
// a load at the end. After building MemorySSA, we test updating by moving		// a load at the end. After building MemorySSA, we test updating by moving
// the store from the side block to the entry block.		// the store from the side block to the entry block. This destroys the old
		// access.
F = Function::Create(		F = Function::Create(
FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),		FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
GlobalValue::ExternalLinkage, "F", &M);		GlobalValue::ExternalLinkage, "F", &M);
BasicBlock *Entry(BasicBlock::Create(C, "", F));		BasicBlock *Entry(BasicBlock::Create(C, "", F));
BasicBlock *Left(BasicBlock::Create(C, "", F));		BasicBlock *Left(BasicBlock::Create(C, "", F));
BasicBlock *Right(BasicBlock::Create(C, "", F));		BasicBlock *Right(BasicBlock::Create(C, "", F));
BasicBlock *Merge(BasicBlock::Create(C, "", F));		BasicBlock *Merge(BasicBlock::Create(C, "", F));
B.SetInsertPoint(Entry);		B.SetInsertPoint(Entry);
Show All 15 Lines	TEST_F(MemorySSATest, MoveAStore) {
MemoryAccess *SideStoreAccess = MSSA.getMemoryAccess(SideStore);		MemoryAccess *SideStoreAccess = MSSA.getMemoryAccess(SideStore);
MemoryAccess *NewStoreAccess = MSSA.createMemoryAccessAfter(		MemoryAccess *NewStoreAccess = MSSA.createMemoryAccessAfter(
SideStore, EntryStoreAccess, EntryStoreAccess);		SideStore, EntryStoreAccess, EntryStoreAccess);
EntryStoreAccess->replaceAllUsesWith(NewStoreAccess);		EntryStoreAccess->replaceAllUsesWith(NewStoreAccess);
MSSA.removeMemoryAccess(SideStoreAccess);		MSSA.removeMemoryAccess(SideStoreAccess);
MSSA.verifyMemorySSA();		MSSA.verifyMemorySSA();
}		}

		TEST_F(MemorySSATest, MoveAStoreUpdater) {
		// We create a diamond where there is a in the entry, a store on one side, and
		// a load at the end. After building MemorySSA, we test updating by moving
		// the store from the side block to the entry block. This destroys the old
		// access.
		F = Function::Create(
		FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
		GlobalValue::ExternalLinkage, "F", &M);
		BasicBlock *Entry(BasicBlock::Create(C, "", F));
		BasicBlock *Left(BasicBlock::Create(C, "", F));
		BasicBlock *Right(BasicBlock::Create(C, "", F));
		BasicBlock *Merge(BasicBlock::Create(C, "", F));
		B.SetInsertPoint(Entry);
		Argument PointerArg = &F->arg_begin();
		StoreInst *EntryStore = B.CreateStore(B.getInt8(16), PointerArg);
		B.CreateCondBr(B.getTrue(), Left, Right);
		B.SetInsertPoint(Left);
		auto *SideStore = B.CreateStore(B.getInt8(16), PointerArg);
		BranchInst::Create(Merge, Left);
		BranchInst::Create(Merge, Right);
		B.SetInsertPoint(Merge);
		auto *MergeLoad = B.CreateLoad(PointerArg);
		setupAnalyses();
		MemorySSA &MSSA = *Analyses->MSSA;
		MemorySSAUpdater Updater(&MSSA);

		// Move the store
		SideStore->moveBefore(Entry->getTerminator());
		auto *EntryStoreAccess = MSSA.getMemoryAccess(EntryStore);
		auto *SideStoreAccess = MSSA.getMemoryAccess(SideStore);
		auto *NewStoreAccess = MSSA.createMemoryAccessAfter(
		SideStore, EntryStoreAccess, EntryStoreAccess);
		// Before, the load will point to a phi of the EntryStore and SideStore.
		auto *LoadAccess = cast<MemoryUse>(MSSA.getMemoryAccess(MergeLoad));
		EXPECT_TRUE(isa<MemoryPhi>(LoadAccess->getDefiningAccess()));
		MemoryPhi *MergePhi = cast<MemoryPhi>(LoadAccess->getDefiningAccess());
		EXPECT_EQ(MergePhi->getIncomingValue(1), EntryStoreAccess);
		EXPECT_EQ(MergePhi->getIncomingValue(0), SideStoreAccess);
		MSSA.removeMemoryAccess(SideStoreAccess);
		Updater.insertDef(cast<MemoryDef>(NewStoreAccess));
		// After it's a phi of the new side store access.
		EXPECT_EQ(MergePhi->getIncomingValue(0), NewStoreAccess);
		EXPECT_EQ(MergePhi->getIncomingValue(1), NewStoreAccess);
		MSSA.verifyMemorySSA();
		}

		TEST_F(MemorySSATest, MoveAStoreUpdaterMove) {
		// We create a diamond where there is a in the entry, a store on one side, and
		// a load at the end. After building MemorySSA, we test updating by moving
		// the store from the side block to the entry block. This does not destroy
		// the old access.
		F = Function::Create(
		FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
		GlobalValue::ExternalLinkage, "F", &M);
		BasicBlock *Entry(BasicBlock::Create(C, "", F));
		BasicBlock *Left(BasicBlock::Create(C, "", F));
		BasicBlock *Right(BasicBlock::Create(C, "", F));
		BasicBlock *Merge(BasicBlock::Create(C, "", F));
		B.SetInsertPoint(Entry);
		Argument PointerArg = &F->arg_begin();
		StoreInst *EntryStore = B.CreateStore(B.getInt8(16), PointerArg);
		B.CreateCondBr(B.getTrue(), Left, Right);
		B.SetInsertPoint(Left);
		auto *SideStore = B.CreateStore(B.getInt8(16), PointerArg);
		BranchInst::Create(Merge, Left);
		BranchInst::Create(Merge, Right);
		B.SetInsertPoint(Merge);
		auto *MergeLoad = B.CreateLoad(PointerArg);
		setupAnalyses();
		MemorySSA &MSSA = *Analyses->MSSA;
		MemorySSAUpdater Updater(&MSSA);

		// Move the store
		auto *EntryStoreAccess = MSSA.getMemoryAccess(EntryStore);
		auto *SideStoreAccess = MSSA.getMemoryAccess(SideStore);
		// Before, the load will point to a phi of the EntryStore and SideStore.
		auto *LoadAccess = cast<MemoryUse>(MSSA.getMemoryAccess(MergeLoad));
		EXPECT_TRUE(isa<MemoryPhi>(LoadAccess->getDefiningAccess()));
		MemoryPhi *MergePhi = cast<MemoryPhi>(LoadAccess->getDefiningAccess());
		EXPECT_EQ(MergePhi->getIncomingValue(1), EntryStoreAccess);
		EXPECT_EQ(MergePhi->getIncomingValue(0), SideStoreAccess);
		SideStore->moveBefore(*EntryStore->getParent(), ++EntryStore->getIterator());
		Updater.moveAfter(SideStoreAccess, EntryStoreAccess);
		// After, it's a phi of the side store.
		EXPECT_EQ(MergePhi->getIncomingValue(0), SideStoreAccess);
		EXPECT_EQ(MergePhi->getIncomingValue(1), SideStoreAccess);

		MSSA.verifyMemorySSA();
		}

TEST_F(MemorySSATest, RemoveAPhi) {		TEST_F(MemorySSATest, RemoveAPhi) {
// We create a diamond where there is a store on one side, and then a load		// We create a diamond where there is a store on one side, and then a load
// after the merge point. This enables us to test a bunch of different		// after the merge point. This enables us to test a bunch of different
// removal cases.		// removal cases.
F = Function::Create(		F = Function::Create(
FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),		FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
GlobalValue::ExternalLinkage, "F", &M);		GlobalValue::ExternalLinkage, "F", &M);
BasicBlock *Entry(BasicBlock::Create(C, "", F));		BasicBlock *Entry(BasicBlock::Create(C, "", F));
▲ Show 20 Lines • Show All 329 Lines • ▼ Show 20 Lines	TEST_F(MemorySSATest, WalkerReopt) {
// Create the load memory access pointing to an unoptimized place.		// Create the load memory access pointing to an unoptimized place.
MemoryUse *NewLoadAccess = cast<MemoryUse>(MSSA.createMemoryAccessInBB(		MemoryUse *NewLoadAccess = cast<MemoryUse>(MSSA.createMemoryAccessInBB(
LIA, MSSA.getMemoryAccess(SIB), LIA->getParent(), MemorySSA::End));		LIA, MSSA.getMemoryAccess(SIB), LIA->getParent(), MemorySSA::End));
// This should it cause it to be optimized		// This should it cause it to be optimized
EXPECT_EQ(Walker->getClobberingMemoryAccess(NewLoadAccess), LoadClobber);		EXPECT_EQ(Walker->getClobberingMemoryAccess(NewLoadAccess), LoadClobber);
EXPECT_EQ(NewLoadAccess->getDefiningAccess(), LoadClobber);		EXPECT_EQ(NewLoadAccess->getDefiningAccess(), LoadClobber);
}		}

#if 0		// Test out MemorySSAUpdater::moveBefore
// Test out MemorySSA::spliceMemoryAccessAbove.		TEST_F(MemorySSATest, MoveAboveMemoryDef) {
TEST_F(MemorySSATest, SpliceAboveMemoryDef) {
F = Function::Create(FunctionType::get(B.getVoidTy(), {}, false),		F = Function::Create(FunctionType::get(B.getVoidTy(), {}, false),
GlobalValue::ExternalLinkage, "F", &M);		GlobalValue::ExternalLinkage, "F", &M);
B.SetInsertPoint(BasicBlock::Create(C, "", F));		B.SetInsertPoint(BasicBlock::Create(C, "", F));

Type *Int8 = Type::getInt8Ty(C);		Type *Int8 = Type::getInt8Ty(C);
Value *A = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "A");		Value *A = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "A");
Value *B_ = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "B");		Value *B_ = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "B");
Value *C = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "C");		Value *C = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "C");

StoreInst *StoreA0 = B.CreateStore(ConstantInt::get(Int8, 0), A);		StoreInst *StoreA0 = B.CreateStore(ConstantInt::get(Int8, 0), A);
StoreInst *StoreB = B.CreateStore(ConstantInt::get(Int8, 0), B_);		StoreInst *StoreB = B.CreateStore(ConstantInt::get(Int8, 0), B_);
LoadInst *LoadB = B.CreateLoad(B_);		LoadInst *LoadB = B.CreateLoad(B_);
StoreInst *StoreA1 = B.CreateStore(ConstantInt::get(Int8, 4), A);		StoreInst *StoreA1 = B.CreateStore(ConstantInt::get(Int8, 4), A);
// splice this above StoreB
StoreInst *StoreC = B.CreateStore(ConstantInt::get(Int8, 4), C);		StoreInst *StoreC = B.CreateStore(ConstantInt::get(Int8, 4), C);
StoreInst *StoreA2 = B.CreateStore(ConstantInt::get(Int8, 4), A);		StoreInst *StoreA2 = B.CreateStore(ConstantInt::get(Int8, 4), A);
LoadInst *LoadC = B.CreateLoad(C);		LoadInst *LoadC = B.CreateLoad(C);

setupAnalyses();		setupAnalyses();
MemorySSA &MSSA = *Analyses->MSSA;		MemorySSA &MSSA = *Analyses->MSSA;
MemorySSAWalker &Walker = *Analyses->Walker;		MemorySSAWalker &Walker = *Analyses->Walker;

		MemorySSAUpdater Updater(&MSSA);
StoreC->moveBefore(StoreB);		StoreC->moveBefore(StoreB);
MSSA.spliceMemoryAccessAbove(cast<MemoryDef>(MSSA.getMemoryAccess(StoreB)),		Updater.moveBefore(cast<MemoryDef>(MSSA.getMemoryAccess(StoreC)),
MSSA.getMemoryAccess(StoreC));		cast<MemoryDef>(MSSA.getMemoryAccess(StoreB)));

MSSA.verifyMemorySSA();		MSSA.verifyMemorySSA();

EXPECT_EQ(MSSA.getMemoryAccess(StoreB)->getDefiningAccess(),		EXPECT_EQ(MSSA.getMemoryAccess(StoreB)->getDefiningAccess(),
MSSA.getMemoryAccess(StoreC));		MSSA.getMemoryAccess(StoreC));
EXPECT_EQ(MSSA.getMemoryAccess(StoreC)->getDefiningAccess(),		EXPECT_EQ(MSSA.getMemoryAccess(StoreC)->getDefiningAccess(),
MSSA.getMemoryAccess(StoreA0));		MSSA.getMemoryAccess(StoreA0));
EXPECT_EQ(MSSA.getMemoryAccess(StoreA2)->getDefiningAccess(),		EXPECT_EQ(MSSA.getMemoryAccess(StoreA2)->getDefiningAccess(),
MSSA.getMemoryAccess(StoreA1));		MSSA.getMemoryAccess(StoreA1));
EXPECT_EQ(Walker.getClobberingMemoryAccess(LoadB),		EXPECT_EQ(Walker.getClobberingMemoryAccess(LoadB),
MSSA.getMemoryAccess(StoreB));		MSSA.getMemoryAccess(StoreB));
EXPECT_EQ(Walker.getClobberingMemoryAccess(LoadC),		EXPECT_EQ(Walker.getClobberingMemoryAccess(LoadC),
MSSA.getMemoryAccess(StoreC));		MSSA.getMemoryAccess(StoreC));

// exercise block numbering		// exercise block numbering
EXPECT_TRUE(MSSA.locallyDominates(MSSA.getMemoryAccess(StoreC),		EXPECT_TRUE(MSSA.locallyDominates(MSSA.getMemoryAccess(StoreC),
MSSA.getMemoryAccess(StoreB)));		MSSA.getMemoryAccess(StoreB)));
EXPECT_TRUE(MSSA.locallyDominates(MSSA.getMemoryAccess(StoreA1),		EXPECT_TRUE(MSSA.locallyDominates(MSSA.getMemoryAccess(StoreA1),
MSSA.getMemoryAccess(StoreA2)));		MSSA.getMemoryAccess(StoreA2)));
}		}
#endif
		TEST_F(MemorySSATest, Irreducible) {
		// Create the equivalent of
		// x = something
		// if (...)
		// goto second_loop_entry
		// while (...) {
		// second_loop_entry:
		// }
		// use(x)

		SmallVector<PHINode *, 8> Inserted;
		IRBuilder<> B(C);
		F = Function::Create(
		FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
		GlobalValue::ExternalLinkage, "F", &M);

		// Make blocks
		BasicBlock *IfBB = BasicBlock::Create(C, "if", F);
		BasicBlock *LoopStartBB = BasicBlock::Create(C, "loopstart", F);
		BasicBlock *LoopMainBB = BasicBlock::Create(C, "loopmain", F);
		BasicBlock *AfterLoopBB = BasicBlock::Create(C, "afterloop", F);
		B.SetInsertPoint(IfBB);
		B.CreateCondBr(B.getTrue(), LoopMainBB, LoopStartBB);
		B.SetInsertPoint(LoopStartBB);
		B.CreateBr(LoopMainBB);
		B.SetInsertPoint(LoopMainBB);
		B.CreateCondBr(B.getTrue(), LoopStartBB, AfterLoopBB);
		B.SetInsertPoint(AfterLoopBB);
		Argument FirstArg = &F->arg_begin();
		setupAnalyses();
		MemorySSA &MSSA = *Analyses->MSSA;
		MemorySSAUpdater Updater(&MSSA);
		// Create the load memory acccess
		LoadInst *LoadInst = B.CreateLoad(FirstArg);
		MemoryUse *LoadAccess = cast<MemoryUse>(MSSA.createMemoryAccessInBB(
		LoadInst, nullptr, AfterLoopBB, MemorySSA::Beginning));
		Updater.insertUse(LoadAccess);
		MSSA.verifyMemorySSA();
		}

This is an archive of the discontinued LLVM Phabricator instance.

Introduce a basic MemorySSA updater, that supports insertDef and insertUse operations.
ClosedPublic

Details

Diff Detail

Event Timeline

Revision Contents

Diff 86147

llvm/trunk/include/llvm/Transforms/Utils/MemorySSA.h

llvm/trunk/lib/Transforms/Utils/MemorySSA.cpp

llvm/trunk/unittests/Transforms/Utils/MemorySSA.cpp

This is an archive of the discontinued LLVM Phabricator instance.

Introduce a basic MemorySSA updater, that supports insertDef and insertUse operations.ClosedPublic

Details

Diff Detail

Event Timeline

Revision Contents

Diff 86147

llvm/trunk/include/llvm/Transforms/Utils/MemorySSA.h

llvm/trunk/lib/Transforms/Utils/MemorySSA.cpp

llvm/trunk/unittests/Transforms/Utils/MemorySSA.cpp

Introduce a basic MemorySSA updater, that supports insertDef and insertUse operations.
ClosedPublic