#include "llvm/Analysis/MemorySSAUpdater.h"

Public Member Functions
	MemorySSAUpdater (MemorySSA *MSSA)

void	insertDef (MemoryDef *Def, bool RenameUses=false)
	Insert a definition into the MemorySSA IR. More...

void	insertUse (MemoryUse *Use)

void	removeEdge (BasicBlock From, BasicBlock To)
	Update the MemoryPhi in `To` following an edge deletion between `From` and `To`. More...

void	removeDuplicatePhiEdgesBetween (BasicBlock From, BasicBlock To)
	Update the MemoryPhi in `To` to have a single incoming edge from `From`, following a CFG change that replaced multiple edges (switch) with a direct branch. More...

void	updateForClonedLoop (const LoopBlocksRPO &LoopBlocks, ArrayRef< BasicBlock *> ExitBlocks, const ValueToValueMapTy &VM, bool IgnoreIncomingWithNoClones=false)
	Update MemorySSA after a loop was cloned, given the blocks in RPO order, the exit blocks and a 1:1 mapping of all blocks and instructions cloned. More...

void	updateForClonedBlockIntoPred (BasicBlock BB, BasicBlock P1, const ValueToValueMapTy &VM)

void	updateExitBlocksForClonedLoop (ArrayRef< BasicBlock *> ExitBlocks, const ValueToValueMapTy &VMap, DominatorTree &DT)
	Update phi nodes in exit block successors following cloning. More...

void	updateExitBlocksForClonedLoop (ArrayRef< BasicBlock *> ExitBlocks, ArrayRef< std::unique_ptr< ValueToValueMapTy >> VMaps, DominatorTree &DT)

void	applyUpdates (ArrayRef< CFGUpdate > Updates, DominatorTree &DT)
	Apply CFG updates, analogous with the DT edge updates. More...

void	applyInsertUpdates (ArrayRef< CFGUpdate > Updates, DominatorTree &DT)
	Apply CFG insert updates, analogous with the DT edge updates. More...

void	moveBefore (MemoryUseOrDef What, MemoryUseOrDef Where)

void	moveAfter (MemoryUseOrDef What, MemoryUseOrDef Where)

void	moveToPlace (MemoryUseOrDef What, BasicBlock BB, MemorySSA::InsertionPlace Where)

void	moveAllAfterSpliceBlocks (BasicBlock From, BasicBlock To, Instruction *Start)
	`From` block was spliced into `From` and `To`. More...

void	moveAllAfterMergeBlocks (BasicBlock From, BasicBlock To, Instruction *Start)
	`From` block was merged into `To`. More...

void	wireOldPredecessorsToNewImmediatePredecessor (BasicBlock Old, BasicBlock New, ArrayRef< BasicBlock *> Preds, bool IdenticalEdgesWereMerged=true)
	A new empty BasicBlock (New) now branches directly to Old. More...

MemoryAccess *	createMemoryAccessInBB (Instruction I, MemoryAccess Definition, const BasicBlock *BB, MemorySSA::InsertionPlace Point)
	Create a MemoryAccess in MemorySSA at a specified point in a block, with a specified clobbering definition. More...

MemoryUseOrDef *	createMemoryAccessBefore (Instruction I, MemoryAccess Definition, MemoryUseOrDef *InsertPt)
	Create a MemoryAccess in MemorySSA before or after an existing MemoryAccess. More...

MemoryUseOrDef *	createMemoryAccessAfter (Instruction I, MemoryAccess Definition, MemoryAccess *InsertPt)

void	removeMemoryAccess (MemoryAccess *)
	Remove a MemoryAccess from MemorySSA, including updating all definitions and uses. More...

void	removeMemoryAccess (const Instruction *I)
	Remove MemoryAccess for a given instruction, if a MemoryAccess exists. More...

void	removeBlocks (const SmallPtrSetImpl< BasicBlock *> &DeadBlocks)
	Remove all MemoryAcceses in a set of BasicBlocks about to be deleted. More...

MemorySSA *	getMemorySSA () const
	Get handle on MemorySSA. More...

Detailed Description

Definition at line 70 of file MemorySSAUpdater.h.

Constructor & Destructor Documentation

◆ MemorySSAUpdater()

llvm::MemorySSAUpdater::MemorySSAUpdater ( MemorySSA * MSSA )

inline

Definition at line 82 of file MemorySSAUpdater.h.

References applyInsertUpdates(), applyUpdates(), llvm::tgtok::Def, From, insertDef(), insertUse(), moveAfter(), moveAllAfterSpliceBlocks(), moveBefore(), moveToPlace(), removeDuplicatePhiEdgesBetween(), removeEdge(), updateExitBlocksForClonedLoop(), updateForClonedBlockIntoPred(), and updateForClonedLoop().

Member Function Documentation

◆ applyInsertUpdates()

void MemorySSAUpdater::applyInsertUpdates	(	ArrayRef< CFGUpdate >	Updates,
		DominatorTree &	DT
	)

Apply CFG insert updates, analogous with the DT edge updates.

Definition at line 620 of file MemorySSAUpdater.cpp.

References llvm::MemoryPhi::addIncoming(), assert(), llvm::SmallVectorTemplateCommon< T >::begin(), llvm::BasicBlock::begin(), llvm::IDFCalculator< NodeTy, IsPostDom >::calculate(), llvm::dbgs(), llvm::DominatorTree::dominates(), llvm::dyn_cast(), E, llvm::SmallVectorBase::empty(), llvm::simple_ilist< T, Options >::end(), llvm::SmallVectorTemplateCommon< T >::end(), llvm::DominatorTreeBase< NodeT, IsPostDom >::findNearestCommonDominator(), llvm::DomTreeNodeBase< NodeT >::getBlock(), llvm::MemoryAccess::getBlock(), llvm::MemoryUseOrDef::getDefiningAccess(), llvm::DomTreeNodeBase< NodeT >::getIDom(), llvm::MemorySSA::getLiveOnEntryDef(), llvm::DominatorTreeBase< NodeT, IsPostDom >::getNode(), llvm::User::getNumOperands(), llvm::Use::getUser(), llvm::MemorySSA::getWritableBlockDefs(), I, llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, InlineBuckets, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::insert(), llvm::SmallPtrSetImpl< PtrType >::insert(), insertDef(), insertUse(), LLVM_DEBUG, llvm_unreachable, llvm::pred_size(), llvm::SmallVectorTemplateBase< T >::push_back(), removeMemoryAccess(), llvm::Value::replaceAllUsesWith(), llvm::Use::set(), llvm::IDFCalculator< NodeTy, IsPostDom >::setDefiningBlocks(), llvm::Value::use_begin(), and llvm::Value::users().

Referenced by applyUpdates(), getMemorySSA(), MemorySSAUpdater(), unswitchNontrivialInvariants(), unswitchTrivialBranch(), and updateForClonedBlockIntoPred().

◆ applyUpdates()

void MemorySSAUpdater::applyUpdates	(	ArrayRef< CFGUpdate >	Updates,
		DominatorTree &	DT
	)

Apply CFG updates, analogous with the DT edge updates.

Definition at line 589 of file MemorySSAUpdater.cpp.

References applyInsertUpdates(), llvm::SmallVectorBase::empty(), llvm::DominatorTreeBase< NodeT, IsPostDom >::Insert, llvm::SmallVectorTemplateBase< T >::push_back(), and removeEdge().

Referenced by MemorySSAUpdater(), and unswitchTrivialSwitch().

◆ createMemoryAccessAfter()

MemoryUseOrDef * MemorySSAUpdater::createMemoryAccessAfter	(	Instruction *	I,
		MemoryAccess *	Definition,
		MemoryAccess *	InsertPt
	)

Definition at line 1154 of file MemorySSAUpdater.cpp.

References assert(), llvm::MemoryAccess::getBlock(), llvm::MemoryAccess::getIterator(), and llvm::Instruction::getParent().

◆ createMemoryAccessBefore()

MemoryUseOrDef * MemorySSAUpdater::createMemoryAccessBefore	(	Instruction *	I,
		MemoryAccess *	Definition,
		MemoryUseOrDef *	InsertPt
	)

Create a MemoryAccess in MemorySSA before or after an existing MemoryAccess.

Returns the new MemoryAccess. This should be called when a memory instruction is created that is being used to replace an existing memory instruction. It will not create PHI nodes, or verify the clobbering definition.

Note: If a MemoryAccess already exists for I, this function will make it inaccessible and it must have removeMemoryAccess called on it.

Definition at line 1144 of file MemorySSAUpdater.cpp.

References assert(), llvm::MemoryAccess::getBlock(), llvm::MemoryAccess::getIterator(), and llvm::Instruction::getParent().

◆ createMemoryAccessInBB()

MemoryAccess * MemorySSAUpdater::createMemoryAccessInBB	(	Instruction *	I,
		MemoryAccess *	Definition,
		const BasicBlock *	BB,
		MemorySSA::InsertionPlace	Point
	)

Create a MemoryAccess in MemorySSA at a specified point in a block, with a specified clobbering definition.

Returns the new MemoryAccess. This should be called when a memory instruction is created that is being used to replace an existing memory instruction. It will not create PHI nodes, or verify the clobbering definition. The insertion place is used solely to determine where in the memoryssa access lists the instruction will be placed. The caller is expected to keep ordering the same as instructions. It will return the new MemoryAccess. Note: If a MemoryAccess already exists for I, this function will make it inaccessible and it must have removeMemoryAccess called on it.

Definition at line 1136 of file MemorySSAUpdater.cpp.

Referenced by CloneInstructionInExitBlock().

◆ getMemorySSA()

MemorySSA* llvm::MemorySSAUpdater::getMemorySSA ( ) const

inline

Get handle on MemorySSA.

Definition at line 245 of file MemorySSAUpdater.h.

References applyInsertUpdates().

Referenced by llvm::canSinkOrHoistInst(), CloneInstructionInExitBlock(), hoist(), llvm::hoistRegion(), isLoadInvariantInLoop(), llvm::LoopRotation(), simplifyLoopInst(), llvm::sinkRegion(), turnGuardIntoBranch(), unswitchNontrivialInvariants(), unswitchTrivialBranch(), and unswitchTrivialSwitch().

◆ insertDef()

void MemorySSAUpdater::insertDef	(	MemoryDef *	Def,
		bool	RenameUses = `false`
	)

Insert a definition into the MemorySSA IR.

RenameUses will rename any use below the new def block (and any inserted phis). RenameUses should be set to true if the definition may cause new aliases for loads below it. This is not the case for hoisting or sinking or other forms of code movement. It is the case for straight code insertion. For example: store a if (foo) { } load a

Moving the store into the if block, and calling insertDef, does not require RenameUses. However, changing it to: store a if (foo) { store b } load a Where a mayalias b, does require RenameUses be set to true.

Definition at line 254 of file MemorySSAUpdater.cpp.

References assert(), llvm::SmallVectorTemplateCommon< T >::back(), llvm::simple_ilist< T, Options >::begin(), llvm::MemorySSA::dominates(), llvm::SmallVectorBase::empty(), llvm::MemoryAccess::getBlock(), llvm::MemoryUseOrDef::getDefiningAccess(), llvm::MemoryAccess::getDefsIterator(), llvm::MemorySSA::getMemoryAccess(), llvm::Use::getUser(), llvm::MemorySSA::getWritableBlockDefs(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::SmallVectorTemplateBase< T >::pop_back(), llvm::SmallVectorTemplateBase< T >::push_back(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::MemorySSA::renamePass(), llvm::Use::set(), llvm::MemoryUseOrDef::setDefiningAccess(), setMemoryPhiValueForBlock(), llvm::successors(), llvm::Value::use_begin(), and llvm::Value::use_end().

Referenced by applyInsertUpdates(), CloneInstructionInExitBlock(), and MemorySSAUpdater().

◆ insertUse()

void MemorySSAUpdater::insertUse ( MemoryUse * Use )

Definition at line 217 of file MemorySSAUpdater.cpp.

References llvm::MemoryUseOrDef::setDefiningAccess().

Referenced by applyInsertUpdates(), CloneInstructionInExitBlock(), and MemorySSAUpdater().

◆ moveAfter()

void MemorySSAUpdater::moveAfter	(	MemoryUseOrDef *	What,
		MemoryUseOrDef *	Where
	)

Definition at line 944 of file MemorySSAUpdater.cpp.

References llvm::MemoryAccess::getBlock(), and llvm::MemoryAccess::getIterator().

Referenced by MemorySSAUpdater().

◆ moveAllAfterMergeBlocks()

void MemorySSAUpdater::moveAllAfterMergeBlocks	(	BasicBlock *	From,
		BasicBlock *	To,
		Instruction *	Start
	)

From block was merged into To.

There is a CFG edge from To to From.To still branches to From, but all instructions were moved and From is now an empty block; From is about to be deleted. Move all accesses from From to To starting at instruction Start. To may have multiple successors, From has a single predecessor. From may have successors with MPhi nodes, replace their incoming block with To. |---—| |---—|

To		To
	=>

\/ | | |---—| | | <- Start | From | | | |---—| |---—|

Definition at line 993 of file MemorySSAUpdater.cpp.

References assert(), llvm::BasicBlock::getSinglePredecessor(), and llvm::successors().

Referenced by llvm::MergeBlockIntoPredecessor().

◆ moveAllAfterSpliceBlocks()

void MemorySSAUpdater::moveAllAfterSpliceBlocks	(	BasicBlock *	From,
		BasicBlock *	To,
		Instruction *	Start
	)

From block was spliced into From and To.

There is a CFG edge from From to To. Move all accesses from From to To starting at instruction Start. To is newly created BB, so empty of MemorySSA::MemoryAccesses. Edges are already updated, so successors of To with MPhi nodes need to update incoming block. |---—| |---—|

From		From

| | => \/ | | |---—| <- Start | | | To | |---—| |---—|

Definition at line 982 of file MemorySSAUpdater.cpp.

References assert(), and llvm::successors().

Referenced by MemorySSAUpdater(), llvm::SplitBlock(), and turnGuardIntoBranch().

◆ moveBefore()

void MemorySSAUpdater::moveBefore	(	MemoryUseOrDef *	What,
		MemoryUseOrDef *	Where
	)

Definition at line 939 of file MemorySSAUpdater.cpp.

References llvm::MemoryAccess::getBlock(), and llvm::MemoryAccess::getIterator().

Referenced by MemorySSAUpdater().

◆ moveToPlace()

void MemorySSAUpdater::moveToPlace	(	MemoryUseOrDef *	What,
		BasicBlock *	BB,
		MemorySSA::InsertionPlace	Where
	)

Definition at line 948 of file MemorySSAUpdater.cpp.

References From.

Referenced by hoist(), MemorySSAUpdater(), and turnGuardIntoBranch().

◆ removeBlocks()

void MemorySSAUpdater::removeBlocks ( const SmallPtrSetImpl< BasicBlock *> & DeadBlocks )

Remove all MemoryAcceses in a set of BasicBlocks about to be deleted.

Assumption we make here: all uses of deleted defs and phi must either occur in blocks about to be deleted (thus will be deleted as well), or they occur in phis that will simply lose an incoming value. Deleted blocks still have successor info, but their predecessor edges and Phi nodes may already be updated. Instructions in DeadBlocks should be deleted after this call.

Definition at line 1103 of file MemorySSAUpdater.cpp.

References assert(), llvm::User::dropAllReferences(), llvm::BasicBlock::getTerminator(), removeMemoryAccess(), and llvm::successors().

Referenced by deleteDeadBlocksFromLoop(), deleteDeadClonedBlocks(), getOnlyLiveSuccessor(), removeMemoryAccess(), and llvm::removeUnreachableBlocks().

◆ removeDuplicatePhiEdgesBetween()

void MemorySSAUpdater::removeDuplicatePhiEdgesBetween	(	BasicBlock *	From,
		BasicBlock *	To
	)

Update the MemoryPhi in To to have a single incoming edge from From, following a CFG change that replaced multiple edges (switch) with a direct branch.

Definition at line 404 of file MemorySSAUpdater.cpp.

References assert(), B, llvm::MemorySSA::createDefinedAccess(), llvm::MemorySSA::End, llvm::MemorySSA::getBlockAccesses(), llvm::MemorySSA::getMemoryAccess(), llvm::MemorySSA::insertIntoListsForBlock(), llvm::MemorySSA::isLiveOnEntryDef(), llvm::ValueMap< KeyT, ValueT, Config >::lookup(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::lookup(), and removeMemoryAccess().

Referenced by getOnlyLiveSuccessor(), MemorySSAUpdater(), and unswitchNontrivialInvariants().

◆ removeEdge()

void MemorySSAUpdater::removeEdge	(	BasicBlock *	From,
		BasicBlock *	To
	)

Update the MemoryPhi in To following an edge deletion between From and To.

If To becomes unreachable, a call to removeBlocks should be made.

Definition at line 396 of file MemorySSAUpdater.cpp.

References llvm::MemorySSA::getMemoryAccess(), and removeMemoryAccess().

Referenced by applyUpdates(), getOnlyLiveSuccessor(), MemorySSAUpdater(), unswitchNontrivialInvariants(), and unswitchTrivialBranch().

◆ removeMemoryAccess() [1/2]

void MemorySSAUpdater::removeMemoryAccess ( MemoryAccess * MA )

Remove a MemoryAccess from MemorySSA, including updating all definitions and uses.

This should be called when a memory instruction that has a MemoryAccess associated with it is erased from the program. For example, if a store or load is simply erased (not replaced), removeMemoryAccess should be called on the MemoryAccess for that store/load.

Definition at line 1055 of file MemorySSAUpdater.cpp.

References assert(), llvm::Use::getUser(), llvm::Value::hasValueHandle(), onlySingleValue(), llvm::Use::set(), llvm::Value::use_begin(), llvm::Value::use_empty(), and llvm::ValueHandleBase::ValueIsRAUWd().

Referenced by applyInsertUpdates(), eraseInstruction(), llvm::RecursivelyDeleteTriviallyDeadInstructions(), removeBlocks(), removeDuplicatePhiEdgesBetween(), removeEdge(), removeMemoryAccess(), and wireOldPredecessorsToNewImmediatePredecessor().

◆ removeMemoryAccess() [2/2]

void llvm::MemorySSAUpdater::removeMemoryAccess ( const Instruction * I )

inline

Remove MemoryAccess for a given instruction, if a MemoryAccess exists.

This should be called when an instruction (load/store) is deleted from the program.

Definition at line 230 of file MemorySSAUpdater.h.

References llvm::MemorySSA::getMemoryAccess(), removeBlocks(), and removeMemoryAccess().

◆ updateExitBlocksForClonedLoop() [1/2]

void MemorySSAUpdater::updateExitBlocksForClonedLoop	(	ArrayRef< BasicBlock *>	ExitBlocks,
		const ValueToValueMapTy &	VMap,
		DominatorTree &	DT
	)

Update phi nodes in exit block successors following cloning.

Exit blocks that were not cloned don't have additional predecessors added.

Definition at line 567 of file MemorySSAUpdater.cpp.

References llvm::sys::path::begin(), and llvm::sys::path::end().

Referenced by MemorySSAUpdater(), and unswitchNontrivialInvariants().

◆ updateExitBlocksForClonedLoop() [2/2]

void MemorySSAUpdater::updateExitBlocksForClonedLoop	(	ArrayRef< BasicBlock *>	ExitBlocks,
		ArrayRef< std::unique_ptr< ValueToValueMapTy >>	VMaps,
		DominatorTree &	DT
	)

Definition at line 575 of file MemorySSAUpdater.cpp.

References I.

◆ updateForClonedBlockIntoPred()

void MemorySSAUpdater::updateForClonedBlockIntoPred	(	BasicBlock *	BB,
		BasicBlock *	P1,
		const ValueToValueMapTy &	VM
	)

Definition at line 539 of file MemorySSAUpdater.cpp.

References applyInsertUpdates(), llvm::MemorySSA::getMemoryAccess(), llvm::Instruction::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::DominatorTreeBase< NodeT, IsPostDom >::Insert, llvm::ValueMap< KeyT, ValueT, Config >::lookup(), llvm::make_range(), and llvm::SmallVectorTemplateBase< T >::push_back().

Referenced by MemorySSAUpdater().

◆ updateForClonedLoop()

void MemorySSAUpdater::updateForClonedLoop	(	const LoopBlocksRPO &	LoopBlocks,
		ArrayRef< BasicBlock *>	ExitBlocks,
		const ValueToValueMapTy &	VM,
		bool	IgnoreIncomingWithNoClones = `false`
	)

Update MemorySSA after a loop was cloned, given the blocks in RPO order, the exit blocks and a 1:1 mapping of all blocks and instructions cloned.

This involves duplicating all defs and uses in the cloned blocks Updating phi nodes in exit block successors is done separately.

Definition at line 463 of file MemorySSAUpdater.cpp.

References llvm::MemoryPhi::addIncoming(), assert(), llvm::SmallPtrSetImpl< PtrType >::count(), E, llvm::MemoryPhi::getIncomingBlock(), llvm::MemoryPhi::getIncomingValue(), llvm::MemorySSA::getMemoryAccess(), llvm::MemoryPhi::getNumIncomingValues(), llvm::MemorySSA::getWritableBlockAccesses(), llvm::MemorySSA::isLiveOnEntryDef(), llvm::ValueMap< KeyT, ValueT, Config >::lookup(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::lookup(), llvm::pred_begin(), llvm::pred_end(), and ProcessBlock().

Referenced by MemorySSAUpdater(), and unswitchNontrivialInvariants().

◆ wireOldPredecessorsToNewImmediatePredecessor()

void MemorySSAUpdater::wireOldPredecessorsToNewImmediatePredecessor	(	BasicBlock *	Old,
		BasicBlock *	New,
		ArrayRef< BasicBlock *>	Preds,
		bool	IdenticalEdgesWereMerged = `true`
	)

A new empty BasicBlock (New) now branches directly to Old.

Some of Old's predecessors (Preds) are now branching to New instead of Old. If New is the only predecessor, move Old's Phi, if present, to New. Otherwise, add a new Phi in New with appropriate incoming values, and update the incoming values in Old's Phi node too, if present.

Definition at line 1017 of file MemorySSAUpdater.cpp.

References assert(), B, llvm::ArrayRef< T >::begin(), llvm::MemorySSA::Beginning, llvm::ArrayRef< T >::empty(), llvm::ArrayRef< T >::end(), llvm::BasicBlock::hasNPredecessors(), onlySingleValue(), llvm::pred_size(), removeMemoryAccess(), and llvm::ArrayRef< T >::size().

Referenced by llvm::sinkRegion(), llvm::SplitCriticalEdge(), and UpdateAnalysisInformation().

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

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

Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ MemorySSAUpdater()

Member Function Documentation

◆ applyInsertUpdates()

◆ applyUpdates()

◆ createMemoryAccessAfter()

◆ createMemoryAccessBefore()

◆ createMemoryAccessInBB()

◆ getMemorySSA()

◆ insertDef()

◆ insertUse()

◆ moveAfter()

◆ moveAllAfterMergeBlocks()

◆ moveAllAfterSpliceBlocks()

◆ moveBefore()

◆ moveToPlace()

◆ removeBlocks()

◆ removeDuplicatePhiEdgesBetween()

◆ removeEdge()

◆ removeMemoryAccess() [1/2]

◆ removeMemoryAccess() [2/2]

◆ updateExitBlocksForClonedLoop() [1/2]

◆ updateExitBlocksForClonedLoop() [2/2]

◆ updateForClonedBlockIntoPred()

◆ updateForClonedLoop()

◆ wireOldPredecessorsToNewImmediatePredecessor()