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 class	VerificationLevel { Fast , Full }
enum	InsertionPlace { Beginning , End , BeforeTerminator }
	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

Public Member Functions
LLVM_ABI	MemorySSA (Function &, AliasAnalysis , DominatorTree )
LLVM_ABI	MemorySSA (Loop &, AliasAnalysis , DominatorTree )
	MemorySSA (MemorySSA &&)=delete
LLVM_ABI	~MemorySSA ()
LLVM_ABI MemorySSAWalker *	getWalker ()
LLVM_ABI MemorySSAWalker *	getSkipSelfWalker ()
MemoryUseOrDef *	getMemoryAccess (const Instruction *I) const
	Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.
MemoryPhi *	getMemoryAccess (const BasicBlock *BB) const
DominatorTree &	getDomTree () const
LLVM_ABI void	dump () const
LLVM_ABI void	print (raw_ostream &) const
bool	isLiveOnEntryDef (const MemoryAccess *MA) const
	Return true if `MA` represents the live on entry value.
MemoryAccess *	getLiveOnEntryDef () const
const AccessList *	getBlockAccesses (const BasicBlock *BB) const
	Return the list of MemoryAccess's for a given basic block.
const DefsList *	getBlockDefs (const BasicBlock *BB) const
	Return the list of MemoryDef's and MemoryPhi's for a given basic block.
LLVM_ABI 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`.
LLVM_ABI bool	dominates (const MemoryAccess A, const MemoryAccess B) const
	Given two memory accesses in potentially different blocks, determine whether MemoryAccess `A` dominates MemoryAccess `B`.
LLVM_ABI bool	dominates (const MemoryAccess *A, const Use &B) const
	Given a MemoryAccess and a Use, determine whether MemoryAccess `A` dominates Use `B`.
LLVM_ABI void	verifyMemorySSA (VerificationLevel=VerificationLevel::Fast) const
	Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right places).
LLVM_ABI void	ensureOptimizedUses ()
	By default, uses are not optimized during MemorySSA construction.
AliasAnalysis &	getAA ()

Protected Member Functions
template<typename IterT>
void	verifyOrderingDominationAndDefUses (IterT Blocks, VerificationLevel=VerificationLevel::Fast) const
	Verify ordering: the order and existence of MemoryAccesses matches the order and existence of memory affecting instructions.
template<typename IterT>
void	verifyDominationNumbers (IterT Blocks) const
	Verify that all of the blocks we believe to have valid domination numbers actually have valid domination numbers.
template<typename IterT>
void	verifyPrevDefInPhis (IterT Blocks) const
AccessList *	getWritableBlockAccesses (const BasicBlock *BB) const
DefsList *	getWritableBlockDefs (const BasicBlock *BB) const
LLVM_ABI void	moveTo (MemoryUseOrDef What, BasicBlock BB, AccessList::iterator Where)
LLVM_ABI void	moveTo (MemoryAccess What, BasicBlock BB, InsertionPlace Point)
void	renamePass (BasicBlock BB, MemoryAccess IncomingVal, SmallPtrSetImpl< BasicBlock * > &Visited)
LLVM_ABI void	removeFromLookups (MemoryAccess *)
	Properly remove `MA` from all of MemorySSA's lookup tables.
LLVM_ABI void	removeFromLists (MemoryAccess *, bool ShouldDelete=true)
	Properly remove `MA` from all of MemorySSA's lists.
LLVM_ABI void	insertIntoListsForBlock (MemoryAccess , const BasicBlock , InsertionPlace)
LLVM_ABI void	insertIntoListsBefore (MemoryAccess , const BasicBlock , AccessList::iterator)
LLVM_ABI MemoryUseOrDef *	createDefinedAccess (Instruction , MemoryAccess , const MemoryUseOrDef *Template=nullptr, bool CreationMustSucceed=true)

Friends
class	MemorySSAUpdater

Detailed Description

Encapsulates MemorySSA, including all data associated with memory accesses.

Definition at line 702 of file MemorySSA.h.

Member Typedef Documentation

◆ AccessList

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

Definition at line 753 of file MemorySSA.h.

◆ DefsList

using llvm::MemorySSA::DefsList

Initial value:

simple_ilist<MemoryAccess, ilist_tag<MSSAHelpers::DefsOnlyTag>>

llvm::simple_ilist

A simple intrusive list implementation.

Definition simple_ilist.h:81

Definition at line 754 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
BeforeTerminator

Definition at line 793 of file MemorySSA.h.

◆ VerificationLevel

enum class llvm::MemorySSA::VerificationLevel

strong

Enumerator
Fast
Full

Definition at line 785 of file MemorySSA.h.

Constructor & Destructor Documentation

◆ MemorySSA() [1/3]

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

Definition at line 1233 of file MemorySSA.cpp.

References assert(), getWalker(), and llvm::iterator_range().

Referenced by llvm::MemorySSA::ClobberWalkerBase::ClobberWalkerBase(), MemorySSA(), and llvm::MemorySSA::OptimizeUses::OptimizeUses().

◆ MemorySSA() [2/3]

MemorySSA::MemorySSA	(	Loop &	L,
		AliasAnalysis *	AA,
		DominatorTree *	DT )

Definition at line 1251 of file MemorySSA.cpp.

References assert(), getWalker(), and llvm::map_range().

◆ MemorySSA() [3/3]

llvm::MemorySSA::MemorySSA ( MemorySSA && )

delete

References getSkipSelfWalker(), getWalker(), LLVM_ABI, and MemorySSA().

◆ ~MemorySSA()

MemorySSA::~MemorySSA ( )

Definition at line 1272 of file MemorySSA.cpp.

References llvm::User::dropAllReferences().

Member Function Documentation

◆ createDefinedAccess()

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

protected

Definition at line 1725 of file MemorySSA.cpp.

References assert(), I, llvm::isa(), llvm::MemoryUseOrDef::setDefiningAccess(), and Template.

◆ 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 2173 of file MemorySSA.cpp.

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

Referenced by checkClobberSanity(), dominates(), getMatchingValue(), noConflictingReadWrites(), verifyOrderingDominationAndDefUses(), and writtenBetween().

◆ 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 2186 of file MemorySSA.cpp.

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

◆ dump()

LLVM_DUMP_METHOD void MemorySSA::dump ( ) const

Definition at line 1902 of file MemorySSA.cpp.

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

◆ ensureOptimizedUses()

void MemorySSA::ensureOptimizedUses ( )

By default, uses are not optimized during MemorySSA construction.

Calling this method will attempt to optimize all MemoryUses, if this has not happened yet for this MemorySSA instance. This should be done if you plan to query the clobbering access for most uses, or if you walk the def-use chain of uses.

Definition at line 2200 of file MemorySSA.cpp.

References llvm::MemorySSA::OptimizeUses::optimizeUses().

Referenced by llvm::MemorySSAPrinterPass::run().

◆ getAA()

AliasAnalysis & llvm::MemorySSA::getAA ( )

inline

Definition at line 802 of file MemorySSA.h.

Referenced by pointerInvalidatedByLoop(), and usersDominator().

◆ 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 760 of file MemorySSA.h.

References getWritableBlockAccesses().

Referenced by foreachMemoryAccess(), noConflictingReadWrites(), llvm::SinkAndHoistLICMFlags::SinkAndHoistLICMFlags(), verifyDominationNumbers(), and verifyOrderingDominationAndDefUses().

◆ 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 768 of file MemorySSA.h.

References getWritableBlockDefs().

Referenced by pointerInvalidatedByBlock(), unswitchAllTrivialConditions(), verifyOrderingDominationAndDefUses(), and verifyPrevDefInPhis().

◆ getDomTree()

DominatorTree & llvm::MemorySSA::getDomTree ( ) const

inline

Definition at line 728 of file MemorySSA.h.

Referenced by checkClobberSanity().

◆ getLiveOnEntryDef()

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

inline

Definition at line 744 of file MemorySSA.h.

◆ getMemoryAccess() [1/2]

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

inline

Definition at line 724 of file MemorySSA.h.

References llvm::cast(), and llvm::cast_or_null().

◆ getMemoryAccess() [2/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 720 of file MemorySSA.h.

References llvm::cast_or_null(), and I.

Referenced by buildPartialInvariantUnswitchConditionalBranch(), llvm::canSinkOrHoistInst(), cloneInstructionInExitBlock(), getMatchingValue(), getNewDefiningAccessForClone(), llvm::hasPartialIVCondition(), llvm::Loop::makeLoopInvariant(), llvm::MergeBlockIntoPredecessor(), moveInstructionBefore(), noConflictingReadWrites(), overreadUndefContents(), runMoveAutoInit(), simplifyLoopInst(), sinkInstruction(), turnGuardIntoBranch(), usersDominator(), verifyOrderingDominationAndDefUses(), and verifyPrevDefInPhis().

◆ getSkipSelfWalker()

MemorySSAWalker * MemorySSA::getSkipSelfWalker ( )

Definition at line 1603 of file MemorySSA.cpp.

Referenced by getClobberingMemoryAccess(), and MemorySSA().

◆ getWalker()

MemorySSAWalker * MemorySSA::getWalker ( )

Definition at line 1590 of file MemorySSA.cpp.

Referenced by getMatchingValue(), llvm::AMDGPU::isClobberedInFunction(), MemorySSA(), MemorySSA(), MemorySSA(), overreadUndefContents(), removeFromLookups(), and writtenBetween().

◆ getWritableBlockAccesses()

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

inlineprotected

Definition at line 815 of file MemorySSA.h.

Referenced by getBlockAccesses(), and insertIntoListsBefore().

◆ getWritableBlockDefs()

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

inlineprotected

Definition at line 821 of file MemorySSA.h.

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

Referenced by getBlockDefs().

◆ insertIntoListsBefore()

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

protected

Definition at line 1650 of file MemorySSA.cpp.

References Accesses, getWritableBlockAccesses(), and llvm::isa().

Referenced by moveTo().

◆ insertIntoListsForBlock()

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

protected

Definition at line 1618 of file MemorySSA.cpp.

References Accesses, Beginning, llvm::find_if_not(), and llvm::isa().

Referenced by moveTo().

◆ 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 740 of file MemorySSA.h.

Referenced by checkClobberSanity(), dominates(), getNewDefiningAccessForClone(), hasUndefContents(), llvm::AMDGPU::isClobberedInFunction(), locallyDominates(), noConflictingReadWrites(), and pointerInvalidatedByLoop().

◆ 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 2142 of file MemorySSA.cpp.

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

Referenced by dominates(), dominates(), and pointerInvalidatedByBlock().

◆ moveTo() [1/2]

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

protected

Definition at line 1700 of file MemorySSA.cpp.

References assert(), Beginning, llvm::MemoryAccess::getBlock(), insertIntoListsForBlock(), and llvm::isa().

◆ moveTo() [2/2]

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

protected

Definition at line 1694 of file MemorySSA.cpp.

References insertIntoListsBefore().

◆ print()

void MemorySSA::print ( raw_ostream & OS ) const

Definition at line 1893 of file MemorySSA.cpp.

References llvm::GlobalValue::getParent(), and llvm::Module::print().

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

◆ 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 1866 of file MemorySSA.cpp.

References Accesses, llvm::MemoryAccess::getBlock(), and llvm::isa().

◆ removeFromLookups()

void MemorySSA::removeFromLookups ( MemoryAccess * MA )

protected

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

Definition at line 1839 of file MemorySSA.cpp.

References assert(), llvm::dyn_cast(), llvm::BasicBlock::erase(), llvm::MemoryAccess::getBlock(), llvm::MemoryUseOrDef::getMemoryInst(), getWalker(), llvm::MemorySSAWalker::invalidateInfo(), llvm::isa(), llvm::MemoryUseOrDef::setDefiningAccess(), and llvm::Value::use_empty().

◆ renamePass()

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

inlineprotected

Definition at line 836 of file MemorySSA.h.

References renamePass().

Referenced by renamePass().

◆ verifyDominationNumbers()

template<typename IterT>

void MemorySSA::verifyDominationNumbers ( IterT Blocks ) const

protected

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

Definition at line 1979 of file MemorySSA.cpp.

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

Referenced by MemorySSAUpdater, and verifyMemorySSA().

◆ verifyMemorySSA()

void MemorySSA::verifyMemorySSA ( VerificationLevel VL = VerificationLevel::Fast ) 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 1905 of file MemorySSA.cpp.

References assert(), Full, llvm::iterator_range(), llvm::map_range(), verifyDominationNumbers(), verifyOrderingDominationAndDefUses(), and verifyPrevDefInPhis().

Referenced by llvm::deleteDeadLoop(), llvm::hoistRegion(), injectPendingInvariantConditions(), mergeBlocksIntoPredecessors(), llvm::promoteLoopAccessesToScalars(), llvm::FunctionToLoopPassAdaptor::run(), llvm::LoopFlattenPass::run(), llvm::LoopInstSimplifyPass::run(), llvm::LoopRotatePass::run(), llvm::SimpleLoopUnswitchPass::run(), llvm::MemCpyOptPass::runImpl(), runMoveAutoInit(), simplifyLoopInst(), simplifyOneLoop(), llvm::sinkRegion(), llvm::splitBlockBefore(), turnGuardIntoBranch(), turnSelectIntoBranch(), unswitchNontrivialInvariants(), unswitchTrivialBranch(), and unswitchTrivialSwitch().

◆ verifyOrderingDominationAndDefUses()

template<typename IterT>

void MemorySSA::verifyOrderingDominationAndDefUses	(	IterT	Blocks,
		VerificationLevel	VL = VerificationLevel::Fast ) const

protected

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

Verify domination: each definition dominates all of its uses. Verify def-uses: the immediate use information - walk all the memory accesses and verifying that, for each use, it appears in the appropriate def's use list

Definition at line 2021 of file MemorySSA.cpp.

References assert(), B(), llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::SmallVectorImpl< T >::clear(), DL, dominates(), llvm::dyn_cast(), llvm::SmallVectorTemplateCommon< T, typename >::end(), Full, getBlockAccesses(), getBlockDefs(), llvm::MemoryUseOrDef::getDefiningAccess(), getMemoryAccess(), I, llvm::is_contained(), llvm::isa(), llvm::pred_size(), llvm::predecessors(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::SmallVectorTemplateCommon< T, typename >::size(), and llvm::Value::uses().

Referenced by MemorySSAUpdater, and verifyMemorySSA().

◆ verifyPrevDefInPhis()

template<typename IterT>

void MemorySSA::verifyPrevDefInPhis ( IterT Blocks ) const

protected

Definition at line 1942 of file MemorySSA.cpp.

References assert(), getBlockDefs(), getMemoryAccess(), and I.

Referenced by MemorySSAUpdater, and verifyMemorySSA().

◆ MemorySSAUpdater

friend class MemorySSAUpdater

friend

Definition at line 806 of file MemorySSA.h.

References Fast, MemorySSAUpdater, verifyDominationNumbers(), verifyOrderingDominationAndDefUses(), and verifyPrevDefInPhis().

Referenced by MemorySSAUpdater.

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

◆ VerificationLevel

Constructor & Destructor Documentation

◆ MemorySSA() [1/3]

◆ MemorySSA() [2/3]

◆ MemorySSA() [3/3]

◆ ~MemorySSA()

Member Function Documentation

◆ createDefinedAccess()

◆ dominates() [1/2]

◆ dominates() [2/2]

◆ dump()

◆ ensureOptimizedUses()

◆ getAA()

◆ getBlockAccesses()

◆ getBlockDefs()

◆ getDomTree()

◆ 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()

◆ verifyDominationNumbers()

◆ verifyMemorySSA()

◆ verifyOrderingDominationAndDefUses()

◆ verifyPrevDefInPhis()

Friends And Related Symbol Documentation

◆ MemorySSAUpdater