Encapsulates MemorySSA, including all data associated with memory accesses. More...

#include "llvm/Analysis/MemorySSA.h"

Classes
class	CachingWalker
	A MemorySSAWalker that does AA walks to disambiguate accesses. More...

class	ClobberWalkerBase

class	OptimizeUses
	This class is a batch walker of all MemoryUse's in the program, and points their defining access at the thing that actually clobbers them. More...

class	SkipSelfWalker

Public Types
enum	InsertionPlace { Beginning, End }
	Used in various insertion functions to specify whether we are talking about the beginning or end of a block. More...

using	AccessList = iplist< MemoryAccess, ilist_tag< MSSAHelpers::AllAccessTag > >

using	DefsList = simple_ilist< MemoryAccess, ilist_tag< MSSAHelpers::DefsOnlyTag > >

Public Member Functions
	MemorySSA (Function &, AliasAnalysis , DominatorTree )

	~MemorySSA ()

MemorySSAWalker *	getWalker ()

MemorySSAWalker *	getSkipSelfWalker ()

MemoryUseOrDef *	getMemoryAccess (const Instruction *I) const
	Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it. More...

MemoryPhi *	getMemoryAccess (const BasicBlock *BB) const

void	dump () const

void	print (raw_ostream &) const

bool	isLiveOnEntryDef (const MemoryAccess *MA) const
	Return true if `MA` represents the live on entry value. More...

MemoryAccess *	getLiveOnEntryDef () const

const AccessList *	getBlockAccesses (const BasicBlock *BB) const
	Return the list of MemoryAccess's for a given basic block. More...

const DefsList *	getBlockDefs (const BasicBlock *BB) const
	Return the list of MemoryDef's and MemoryPhi's for a given basic block. More...

bool	locallyDominates (const MemoryAccess A, const MemoryAccess B) const
	Given two memory accesses in the same basic block, determine whether MemoryAccess `A` dominates MemoryAccess `B`. More...

bool	dominates (const MemoryAccess A, const MemoryAccess B) const
	Given two memory accesses in potentially different blocks, determine whether MemoryAccess `A` dominates MemoryAccess `B`. More...

bool	dominates (const MemoryAccess *A, const Use &B) const
	Given a MemoryAccess and a Use, determine whether MemoryAccess `A` dominates Use `B`. More...

void	verifyMemorySSA () const
	Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right places). More...

void	checkClobberSanityAccess (const MemoryAccess *MA) const
	Check clobber sanity for an access. More...

Protected Member Functions
void	verifyDefUses (Function &F) const
	Verify the immediate use information, by walking all the memory accesses and verifying that, for each use, it appears in the appropriate def's use list. More...

void	verifyDomination (Function &F) const
	Verify the domination properties of MemorySSA by checking that each definition dominates all of its uses. More...

void	verifyOrdering (Function &F) const
	Verify that the order and existence of MemoryAccesses matches the order and existence of memory affecting instructions. More...

void	verifyDominationNumbers (const Function &F) const
	Verify that all of the blocks we believe to have valid domination numbers actually have valid domination numbers. More...

void	verifyClobberSanity (const Function &F) const

AccessList *	getWritableBlockAccesses (const BasicBlock *BB) const

DefsList *	getWritableBlockDefs (const BasicBlock *BB) const

void	moveTo (MemoryUseOrDef What, BasicBlock BB, AccessList::iterator Where)

void	moveTo (MemoryAccess What, BasicBlock BB, InsertionPlace Point)

void	renamePass (BasicBlock BB, MemoryAccess IncomingVal, SmallPtrSetImpl< BasicBlock *> &Visited)

void	removeFromLookups (MemoryAccess *)
	Properly remove `MA` from all of MemorySSA's lookup tables. More...

void	removeFromLists (MemoryAccess *, bool ShouldDelete=true)
	Properly remove `MA` from all of MemorySSA's lists. More...

void	insertIntoListsForBlock (MemoryAccess , const BasicBlock , InsertionPlace)

void	insertIntoListsBefore (MemoryAccess , const BasicBlock , AccessList::iterator)

MemoryUseOrDef *	createDefinedAccess (Instruction , MemoryAccess , const MemoryUseOrDef *Template=nullptr)

Friends
class	MemorySSAAnnotatedWriter

class	MemorySSAPrinterLegacyPass

class	MemorySSAUpdater

Detailed Description

Encapsulates MemorySSA, including all data associated with memory accesses.

Definition at line 701 of file MemorySSA.h.

Member Typedef Documentation

◆ AccessList

using llvm::MemorySSA::AccessList = iplist<MemoryAccess, ilist_tag<MSSAHelpers::AllAccessTag> >

Definition at line 744 of file MemorySSA.h.

◆ DefsList

using llvm::MemorySSA::DefsList = simple_ilist<MemoryAccess, ilist_tag<MSSAHelpers::DefsOnlyTag> >

Definition at line 746 of file MemorySSA.h.

Member Enumeration Documentation

◆ InsertionPlace

enum llvm::MemorySSA::InsertionPlace

Used in various insertion functions to specify whether we are talking about the beginning or end of a block.

Enumerator
Beginning
End

Definition at line 784 of file MemorySSA.h.

Constructor & Destructor Documentation

◆ MemorySSA()

MemorySSA::MemorySSA	(	Function &	Func,
		AliasAnalysis *	AA,
		DominatorTree *	DT
	)

Definition at line 1156 of file MemorySSA.cpp.

◆ ~MemorySSA()

MemorySSA::~MemorySSA ( )

Definition at line 1162 of file MemorySSA.cpp.

References llvm::User::dropAllReferences(), and llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert().

Member Function Documentation

◆ checkClobberSanityAccess()

void MemorySSA::checkClobberSanityAccess ( const MemoryAccess * MA ) const

Check clobber sanity for an access.

Check sanity of the clobbering instruction for access MA.

Definition at line 1786 of file MemorySSA.cpp.

References checkClobberSanity(), llvm::MemoryLocation::getOrNone(), and llvm::None.

Referenced by verifyClobberSanity().

◆ createDefinedAccess()

MemoryUseOrDef * MemorySSA::createDefinedAccess	(	Instruction *	I,
		MemoryAccess *	Definition,
		const MemoryUseOrDef *	Template = `nullptr`
	)

protected

Definition at line 1618 of file MemorySSA.cpp.

References assert(), and llvm::MemoryUseOrDef::setDefiningAccess().

Referenced by llvm::MemorySSAUpdater::removeDuplicatePhiEdgesBetween().

◆ dominates() [1/2]

bool MemorySSA::dominates	(	const MemoryAccess *	A,
		const MemoryAccess *	B
	)		const

Given two memory accesses in potentially different blocks, determine whether MemoryAccess A dominates MemoryAccess B.

Definition at line 2029 of file MemorySSA.cpp.

References llvm::MemoryAccess::getBlock(), isLiveOnEntryDef(), and locallyDominates().

Referenced by dominates(), llvm::MemorySSAUpdater::insertDef(), and verifyDomination().

◆ dominates() [2/2]

bool MemorySSA::dominates	(	const MemoryAccess *	A,
		const Use &	B
	)		const

Given a MemoryAccess and a Use, determine whether MemoryAccess A dominates Use B.

Definition at line 2042 of file MemorySSA.cpp.

References dominates(), llvm::MemoryAccess::getBlock(), llvm::Use::getUser(), and locallyDominates().

◆ dump()

LLVM_DUMP_METHOD void MemorySSA::dump ( ) const

Definition at line 1773 of file MemorySSA.cpp.

References llvm::dbgs(), and print().

◆ getBlockAccesses()

const AccessList* llvm::MemorySSA::getBlockAccesses ( const BasicBlock * BB ) const

inline

Return the list of MemoryAccess's for a given basic block.

This list is not modifiable by the user.

Definition at line 751 of file MemorySSA.h.

Referenced by isLoadInvariantInLoop(), llvm::GVNHoist::rank(), llvm::MemorySSAUpdater::removeDuplicatePhiEdgesBetween(), verifyClobberSanity(), verifyDefUses(), verifyDominationNumbers(), and verifyOrdering().

◆ getBlockDefs()

const DefsList* llvm::MemorySSA::getBlockDefs ( const BasicBlock * BB ) const

inline

Return the list of MemoryDef's and MemoryPhi's for a given basic block.

This list is not modifiable by the user.

Definition at line 759 of file MemorySSA.h.

References B.

Referenced by isLoadInvariantInLoop(), and verifyOrdering().

◆ getLiveOnEntryDef()

MemoryAccess* llvm::MemorySSA::getLiveOnEntryDef ( ) const

inline

Definition at line 735 of file MemorySSA.h.

Referenced by llvm::MemorySSAUpdater::applyInsertUpdates(), and llvm::MemorySSA::ClobberWalkerBase::getClobberingMemoryAccessBase().

◆ getMemoryAccess() [1/2]

MemoryUseOrDef* llvm::MemorySSA::getMemoryAccess ( const Instruction * I ) const

inline

Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.

If passed a basic block gets the memory phi node that exists for that block, if there is one. Otherwise, this will get a MemoryUseOrDef.

Definition at line 713 of file MemorySSA.h.

Referenced by llvm::canSinkOrHoistInst(), CloneInstructionInExitBlock(), llvm::MemorySSAAnnotatedWriter::emitBasicBlockStartAnnot(), llvm::MemorySSAAnnotatedWriter::emitInstructionAnnot(), hoist(), llvm::MemorySSAUpdater::insertDef(), moveTo(), llvm::GVNHoist::rank(), llvm::MemorySSAUpdater::removeDuplicatePhiEdgesBetween(), llvm::MemorySSAUpdater::removeEdge(), llvm::MemorySSAUpdater::removeMemoryAccess(), simplifyLoopInst(), turnGuardIntoBranch(), llvm::MemorySSAUpdater::updateForClonedBlockIntoPred(), llvm::MemorySSAUpdater::updateForClonedLoop(), verifyDefUses(), verifyDomination(), and verifyOrdering().

◆ getMemoryAccess() [2/2]

MemoryPhi* llvm::MemorySSA::getMemoryAccess ( const BasicBlock * BB ) const

inline

Definition at line 717 of file MemorySSA.h.

References llvm::dump(), and print().

◆ getSkipSelfWalker()

MemorySSAWalker * MemorySSA::getSkipSelfWalker ( )

Definition at line 1496 of file MemorySSA.cpp.

Referenced by llvm::canSinkOrHoistInst(), and pointerInvalidatedByLoopWithMSSA().

◆ getWalker()

MemorySSAWalker * MemorySSA::getWalker ( )

Definition at line 1483 of file MemorySSA.cpp.

Referenced by llvm::MemorySSA::OptimizeUses::OptimizeUses().

◆ getWritableBlockAccesses()

AccessList* llvm::MemorySSA::getWritableBlockAccesses ( const BasicBlock * BB ) const

inlineprotected

Definition at line 799 of file MemorySSA.h.

Referenced by insertIntoListsBefore(), and llvm::MemorySSAUpdater::updateForClonedLoop().

◆ getWritableBlockDefs()

DefsList* llvm::MemorySSA::getWritableBlockDefs ( const BasicBlock * BB ) const

inlineprotected

Definition at line 805 of file MemorySSA.h.

References llvm::simple_ilist< T, Options >::end().

Referenced by llvm::MemorySSAUpdater::applyInsertUpdates(), and llvm::MemorySSAUpdater::insertDef().

◆ insertIntoListsBefore()

void MemorySSA::insertIntoListsBefore	(	MemoryAccess *	What,
		const BasicBlock *	BB,
		AccessList::iterator	InsertPt
	)

protected

Definition at line 1543 of file MemorySSA.cpp.

References getWritableBlockAccesses(), removeFromLists(), and llvm::MemoryAccess::setBlock().

Referenced by moveTo().

◆ insertIntoListsForBlock()

void MemorySSA::insertIntoListsForBlock	(	MemoryAccess *	NewAccess,
		const BasicBlock *	BB,
		InsertionPlace	Point
	)

protected

Definition at line 1511 of file MemorySSA.cpp.

References Beginning, and llvm::find_if_not().

Referenced by moveTo(), and llvm::MemorySSAUpdater::removeDuplicatePhiEdgesBetween().

◆ isLiveOnEntryDef()

bool llvm::MemorySSA::isLiveOnEntryDef ( const MemoryAccess * MA ) const

inline

Return true if MA represents the live on entry value.

Loads and stores from pointer arguments and other global values may be defined by memory operations that do not occur in the current function, so they may be live on entry to the function. MemorySSA represents such memory state by the live on entry definition, which is guaranteed to occur before any other memory access in the function.

Definition at line 731 of file MemorySSA.h.

Referenced by llvm::canSinkOrHoistInst(), dominates(), llvm::MemorySSA::ClobberWalkerBase::getClobberingMemoryAccessBase(), locallyDominates(), pointerInvalidatedByLoopWithMSSA(), llvm::GVNHoist::rank(), llvm::MemorySSAUpdater::removeDuplicatePhiEdgesBetween(), llvm::MemorySSAUpdater::updateForClonedLoop(), and verifyDomination().

◆ locallyDominates()

bool MemorySSA::locallyDominates	(	const MemoryAccess *	Dominator,
		const MemoryAccess *	Dominatee
	)		const

Given two memory accesses in the same basic block, determine whether MemoryAccess A dominates MemoryAccess B.

Determine, for two memory accesses in the same block, whether Dominator dominates Dominatee.

Returns: True if Dominator dominates Dominatee.

Definition at line 1998 of file MemorySSA.cpp.

References assert(), llvm::MemoryAccess::getBlock(), and isLiveOnEntryDef().

Referenced by dominates(), and llvm::GVNHoist::rank().

◆ moveTo() [1/2]

void MemorySSA::moveTo	(	MemoryUseOrDef *	What,
		BasicBlock *	BB,
		AccessList::iterator	Where
	)

protected

Definition at line 1587 of file MemorySSA.cpp.

References insertIntoListsBefore().

◆ moveTo() [2/2]

void MemorySSA::moveTo	(	MemoryAccess *	What,
		BasicBlock *	BB,
		InsertionPlace	Point
	)

protected

Definition at line 1593 of file MemorySSA.cpp.

References assert(), Beginning, llvm::MemoryAccess::getBlock(), llvm::BasicBlock::getContext(), getMemoryAccess(), insertIntoListsForBlock(), and second.

◆ print()

void MemorySSA::print ( raw_ostream & OS ) const

Definition at line 1767 of file MemorySSA.cpp.

References F.

Referenced by llvm::MemoryAccess::dump(), dump(), and llvm::MemoryAccess::print().

◆ removeFromLists()

void MemorySSA::removeFromLists	(	MemoryAccess *	MA,
		bool	ShouldDelete = `true`
	)

protected

Properly remove 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.

Definition at line 1740 of file MemorySSA.cpp.

References llvm::MemoryAccess::getBlock().

Referenced by insertIntoListsBefore().

◆ removeFromLookups()

void MemorySSA::removeFromLookups ( MemoryAccess * MA )

protected

Properly remove MA from all of MemorySSA's lookup tables.

Definition at line 1713 of file MemorySSA.cpp.

References assert(), llvm::MemoryAccess::getBlock(), and llvm::Value::use_empty().

◆ renamePass()

void llvm::MemorySSA::renamePass	(	BasicBlock *	BB,
		MemoryAccess *	IncomingVal,
		SmallPtrSetImpl< BasicBlock *> &	Visited
	)

inlineprotected

Definition at line 818 of file MemorySSA.h.

References F().

Referenced by llvm::MemorySSAUpdater::insertDef(), llvm::MemorySSA::OptimizeUses::optimizeUses(), and llvm::MemorySSA::SkipSelfWalker::verify().

◆ verifyClobberSanity()

void MemorySSA::verifyClobberSanity ( const Function & F ) const

protected

Definition at line 1800 of file MemorySSA.cpp.

References checkClobberSanityAccess(), and getBlockAccesses().

Referenced by verifyMemorySSA().

◆ verifyDefUses()

void MemorySSA::verifyDefUses ( Function & F ) const

protected

Verify the immediate use information, by walking all the memory accesses and verifying that, for each use, it appears in the appropriate def's use list.

Definition at line 1954 of file MemorySSA.cpp.

References llvm::AArch64CC::AL, assert(), B, E, llvm::find(), getBlockAccesses(), getMemoryAccess(), I, llvm::pred_begin(), llvm::pred_end(), and llvm::predecessors().

Referenced by verifyMemorySSA().

◆ verifyDomination()

void MemorySSA::verifyDomination ( Function & F ) const

protected

Verify the domination properties of MemorySSA by checking that each definition dominates all of its uses.

Definition at line 1917 of file MemorySSA.cpp.

References assert(), B, llvm::tgtok::Def, dominates(), getMemoryAccess(), llvm::is_contained(), isLiveOnEntryDef(), llvm::Value::users(), and llvm::Value::uses().

Referenced by verifyMemorySSA().

◆ verifyDominationNumbers()

void MemorySSA::verifyDominationNumbers ( const Function & F ) const

protected

Verify that all of the blocks we believe to have valid domination numbers actually have valid domination numbers.

Definition at line 1814 of file MemorySSA.cpp.

References assert(), llvm::SmallPtrSetImpl< PtrType >::count(), llvm::SmallPtrSetImplBase::empty(), llvm::SmallPtrSetImpl< PtrType >::erase(), and getBlockAccesses().

Referenced by verifyMemorySSA().

◆ verifyMemorySSA()

void MemorySSA::verifyMemorySSA ( ) const

Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right places).

This is used by unit tests.

Definition at line 1776 of file MemorySSA.cpp.

References F, verifyClobberSanity(), verifyDefUses(), verifyDomination(), verifyDominationNumbers(), and verifyOrdering().

Referenced by CloneLoop(), FindLIVLoopCondition(), llvm::hoistRegion(), llvm::LoopRotation(), llvm::LoopRotatePass::run(), llvm::LoopInstSimplifyPass::run(), llvm::LoopSimplifyCFGPass::run(), llvm::SimpleLoopUnswitchPass::run(), simplifyLoopInst(), llvm::sinkRegion(), turnGuardIntoBranch(), unswitchNontrivialInvariants(), unswitchTrivialBranch(), and unswitchTrivialSwitch().

◆ verifyOrdering()

void MemorySSA::verifyOrdering ( Function & F ) const

protected

Verify that the order and existence of MemoryAccesses matches the order and existence of memory affecting instructions.

Definition at line 1852 of file MemorySSA.cpp.

References llvm::AArch64CC::AL, assert(), B, llvm::SmallVectorTemplateCommon< T >::begin(), llvm::SmallVectorImpl< T >::clear(), llvm::SmallVectorTemplateCommon< T >::end(), getBlockAccesses(), getBlockDefs(), getMemoryAccess(), llvm::SmallVectorTemplateBase< T >::push_back(), and llvm::SmallVectorBase::size().

Referenced by verifyMemorySSA().

Friends And Related Function Documentation

◆ MemorySSAAnnotatedWriter

friend class MemorySSAAnnotatedWriter

friend

Definition at line 788 of file MemorySSA.h.

◆ MemorySSAPrinterLegacyPass

friend class MemorySSAPrinterLegacyPass

friend

Definition at line 789 of file MemorySSA.h.

◆ MemorySSAUpdater

friend class MemorySSAUpdater

friend

Definition at line 790 of file MemorySSA.h.

The documentation for this class was generated from the following files:

include/llvm/Analysis/MemorySSA.h
lib/Analysis/MemorySSA.cpp

Classes

Public Types

Public Member Functions

Protected Member Functions

Friends

Detailed Description

Member Typedef Documentation

◆ AccessList

◆ DefsList

Member Enumeration Documentation

◆ InsertionPlace

Constructor & Destructor Documentation

◆ MemorySSA()

◆ ~MemorySSA()

Member Function Documentation

◆ checkClobberSanityAccess()

◆ createDefinedAccess()

◆ dominates() [1/2]

◆ dominates() [2/2]

◆ dump()

◆ getBlockAccesses()

◆ getBlockDefs()

◆ getLiveOnEntryDef()

◆ getMemoryAccess() [1/2]

◆ getMemoryAccess() [2/2]

◆ getSkipSelfWalker()

◆ getWalker()

◆ getWritableBlockAccesses()

◆ getWritableBlockDefs()

◆ insertIntoListsBefore()

◆ insertIntoListsForBlock()

◆ isLiveOnEntryDef()

◆ locallyDominates()

◆ moveTo() [1/2]

◆ moveTo() [2/2]

◆ print()

◆ removeFromLists()

◆ removeFromLookups()

◆ renamePass()

◆ verifyClobberSanity()

◆ verifyDefUses()

◆ verifyDomination()

◆ verifyDominationNumbers()

◆ verifyMemorySSA()

◆ verifyOrdering()

Friends And Related Function Documentation

◆ MemorySSAAnnotatedWriter

◆ MemorySSAPrinterLegacyPass

◆ MemorySSAUpdater