#include "llvm/Analysis/MemorySSAUpdater.h"

Public Member Functions
	MemorySSAUpdater (MemorySSA *MSSA)
LLVM_ABI void	insertDef (MemoryDef *Def, bool RenameUses=false)
	Insert a definition into the MemorySSA IR.
LLVM_ABI void	insertUse (MemoryUse *Use, bool RenameUses=false)
LLVM_ABI void	removeEdge (BasicBlock From, BasicBlock To)
	Update the MemoryPhi in To following an edge deletion between From and To.
LLVM_ABI void	removeDuplicatePhiEdgesBetween (const BasicBlock From, const 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.
LLVM_ABI void	updatePhisWhenInsertingUniqueBackedgeBlock (BasicBlock LoopHeader, BasicBlock LoopPreheader, BasicBlock *BackedgeBlock)
	Update MemorySSA when inserting a unique backedge block for a loop.
LLVM_ABI 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.
LLVM_ABI void	updateForClonedBlockIntoPred (BasicBlock BB, BasicBlock P1, const ValueToValueMapTy &VM)
LLVM_ABI void	updateExitBlocksForClonedLoop (ArrayRef< BasicBlock * > ExitBlocks, const ValueToValueMapTy &VMap, DominatorTree &DT)
	Update phi nodes in exit block successors following cloning.
LLVM_ABI void	updateExitBlocksForClonedLoop (ArrayRef< BasicBlock * > ExitBlocks, ArrayRef< std::unique_ptr< ValueToValueMapTy > > VMaps, DominatorTree &DT)
LLVM_ABI void	applyUpdates (ArrayRef< CFGUpdate > Updates, DominatorTree &DT, bool UpdateDTFirst=false)
	Apply CFG updates, analogous with the DT edge updates.
LLVM_ABI void	applyInsertUpdates (ArrayRef< CFGUpdate > Updates, DominatorTree &DT)
	Apply CFG insert updates, analogous with the DT edge updates.
LLVM_ABI void	moveBefore (MemoryUseOrDef What, MemoryUseOrDef Where)
LLVM_ABI void	moveAfter (MemoryUseOrDef What, MemoryUseOrDef Where)
LLVM_ABI void	moveToPlace (MemoryUseOrDef What, BasicBlock BB, MemorySSA::InsertionPlace Where)
LLVM_ABI void	moveAllAfterSpliceBlocks (BasicBlock From, BasicBlock To, Instruction *Start)
	From block was spliced into From and To.
LLVM_ABI void	moveAllAfterMergeBlocks (BasicBlock From, BasicBlock To, Instruction *Start)
	From block was merged into To.
LLVM_ABI void	wireOldPredecessorsToNewImmediatePredecessor (BasicBlock Old, BasicBlock New, ArrayRef< BasicBlock * > Preds, bool IdenticalEdgesWereMerged=true)
	A new empty BasicBlock (New) now branches directly to Old.
LLVM_ABI MemoryAccess *	createMemoryAccessInBB (Instruction I, MemoryAccess Definition, const BasicBlock *BB, MemorySSA::InsertionPlace Point, bool CreationMustSucceed=true)
	Create a MemoryAccess in MemorySSA at a specified point in a block.
LLVM_ABI MemoryUseOrDef *	createMemoryAccessBefore (Instruction I, MemoryAccess Definition, MemoryUseOrDef *InsertPt)
	Create a MemoryAccess in MemorySSA before an existing MemoryAccess.
LLVM_ABI MemoryUseOrDef *	createMemoryAccessAfter (Instruction I, MemoryAccess Definition, MemoryAccess *InsertPt)
	Create a MemoryAccess in MemorySSA after an existing MemoryAccess.
LLVM_ABI void	removeMemoryAccess (MemoryAccess *, bool OptimizePhis=false)
	Remove a MemoryAccess from MemorySSA, including updating all definitions and uses.
void	removeMemoryAccess (const Instruction *I, bool OptimizePhis=false)
	Remove MemoryAccess for a given instruction, if a MemoryAccess exists.
LLVM_ABI void	removeBlocks (const SmallSetVector< BasicBlock *, 8 > &DeadBlocks)
	Remove all MemoryAcceses in a set of BasicBlocks about to be deleted.
LLVM_ABI void	changeToUnreachable (const Instruction *I)
	Instruction I will be changed to an unreachable.
MemorySSA *	getMemorySSA () const
	Get handle on MemorySSA.

Detailed Description

Definition at line 55 of file MemorySSAUpdater.h.

Constructor & Destructor Documentation

◆ MemorySSAUpdater()

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

inline

Definition at line 67 of file MemorySSAUpdater.h.

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 835 of file MemorySSAUpdater.cpp.

References applyInsertUpdates().

Referenced by applyInsertUpdates(), applyUpdates(), and unswitchTrivialBranch().

◆ applyUpdates()

void MemorySSAUpdater::applyUpdates	(	ArrayRef< CFGUpdate >	Updates,
		DominatorTree &	DT,
		bool	UpdateDTFirst = false )

Apply CFG updates, analogous with the DT edge updates.

By default, the DT is assumed to be already up to date. If UpdateDTFirst is true, first update the DT with the same updates.

Definition at line 784 of file MemorySSAUpdater.cpp.

References applyInsertUpdates(), llvm::DominatorTreeBase< NodeT, IsPostDom >::applyUpdates(), llvm::DominatorTreeBase< NodeT, IsPostDom >::Delete, DenseMapInfo< LocallyHashedType >::Empty, llvm::SmallVectorTemplateCommon< T, typename >::empty(), llvm::DominatorTreeBase< NodeT, IsPostDom >::Insert, llvm::SmallVectorTemplateBase< T, bool >::push_back(), and removeEdge().

Referenced by injectPendingInvariantConditions(), llvm::splitBlockBefore(), and unswitchTrivialSwitch().

◆ changeToUnreachable()

void MemorySSAUpdater::changeToUnreachable ( const Instruction * I )

Instruction I will be changed to an unreachable.

Remove all accesses in I's block that follow I (inclusive), and update the Phis in the blocks' successors.

Definition at line 1389 of file MemorySSAUpdater.cpp.

References llvm::BasicBlock::end(), I, llvm::SmallVectorTemplateBase< T, bool >::push_back(), removeDuplicatePhiEdgesBetween(), removeMemoryAccess(), llvm::Successor, and llvm::successors().

Referenced by llvm::changeToUnreachable().

◆ createMemoryAccessAfter()

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

Create a MemoryAccess in MemorySSA after an existing MemoryAccess.

See createMemoryAccessInBB() for usage details.

Definition at line 1430 of file MemorySSAUpdater.cpp.

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

◆ createMemoryAccessBefore()

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

Create a MemoryAccess in MemorySSA before an existing MemoryAccess.

See createMemoryAccessInBB() for usage details.

Definition at line 1420 of file MemorySSAUpdater.cpp.

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

◆ createMemoryAccessInBB()

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

Create a MemoryAccess in MemorySSA at a specified point in a block.

When used by itself, this method will only insert the new MemoryAccess into the access list, but not make any other changes, such as inserting MemoryPHI nodes, or updating users to point to the new MemoryAccess. You must specify a correct Definition in this case.

Usually, this API is instead combined with insertUse() or insertDef(), which will perform all the necessary MSSA updates. If these APIs are used, then nullptr can be used as Definition, as the correct defining access will be automatically determined.

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 1410 of file MemorySSAUpdater.cpp.

References I.

Referenced by buildPartialInvariantUnswitchConditionalBranch(), cloneInstructionInExitBlock(), llvm::promoteLoopAccessesToScalars(), and sinkInstruction().

◆ getMemorySSA()

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

inline

◆ 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 307 of file MemorySSAUpdater.cpp.

References assert(), llvm::IDFCalculatorBase< NodeTy, IsPostDom >::calculate(), llvm::cast_or_null(), llvm::dyn_cast(), llvm::dyn_cast_or_null(), llvm::MemoryAccess::getBlock(), llvm::MemoryUseOrDef::getDefiningAccess(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::SmallSet< T, N, C >::insert(), llvm::is_contained(), llvm::isa(), llvm::predecessors(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::Value::replaceUsesWithIf(), llvm::MemoryUseOrDef::setDefiningAccess(), llvm::IDFCalculatorBase< NodeTy, IsPostDom >::setDefiningBlocks(), and llvm::SmallSet< T, N, C >::size().

Referenced by cloneInstructionInExitBlock(), and sinkInstruction().

◆ insertUse()

void MemorySSAUpdater::insertUse	(	MemoryUse *	Use,
		bool	RenameUses = false )

Definition at line 238 of file MemorySSAUpdater.cpp.

References assert(), llvm::cast_or_null(), llvm::dyn_cast(), llvm::MemoryAccess::getBlock(), and llvm::MemoryUseOrDef::setDefiningAccess().

Referenced by cloneInstructionInExitBlock(), llvm::promoteLoopAccessesToScalars(), and sinkInstruction().

◆ moveAfter()

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

Definition at line 1177 of file MemorySSAUpdater.cpp.

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

◆ 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 1239 of file MemorySSAUpdater.cpp.

References assert(), llvm::BasicBlock::getUniquePredecessor(), 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 1228 of file MemorySSAUpdater.cpp.

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

Referenced by SplitBlockImpl(), turnGuardIntoBranch(), and turnSelectIntoBranch().

◆ moveBefore()

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

Definition at line 1172 of file MemorySSAUpdater.cpp.

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

Referenced by moveToPlace().

◆ moveToPlace()

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

Definition at line 1181 of file MemorySSAUpdater.cpp.

References llvm::MemorySSA::BeforeTerminator, llvm::MemorySSA::End, llvm::BasicBlock::getTerminator(), and moveBefore().

Referenced by llvm::Loop::makeLoopInvariant(), llvm::MergeBlockIntoPredecessor(), moveInstructionBefore(), runMoveAutoInit(), sinkInstruction(), and turnGuardIntoBranch().

◆ removeBlocks()

void MemorySSAUpdater::removeBlocks ( const SmallSetVector< BasicBlock *, 8 > & 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 1353 of file MemorySSAUpdater.cpp.

References assert(), llvm::SetVector< T, Vector, Set, N >::count(), llvm::User::dropAllReferences(), llvm::BasicBlock::getTerminator(), llvm::make_early_inc_range(), and llvm::successors().

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

◆ removeDuplicatePhiEdgesBetween()

void MemorySSAUpdater::removeDuplicatePhiEdgesBetween	(	const BasicBlock *	From,
		const 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 529 of file MemorySSAUpdater.cpp.

References B().

Referenced by changeToUnreachable(), 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 522 of file MemorySSAUpdater.cpp.

Referenced by applyUpdates(), DoFlattenLoopPair(), unswitchNontrivialInvariants(), and unswitchTrivialBranch().

◆ removeMemoryAccess() [1/2]

void llvm::MemorySSAUpdater::removeMemoryAccess	(	const Instruction *	I,
		bool	OptimizePhis = false )

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 223 of file MemorySSAUpdater.h.

References I, and removeMemoryAccess().

◆ removeMemoryAccess() [2/2]

void MemorySSAUpdater::removeMemoryAccess	(	MemoryAccess *	MA,
		bool	OptimizePhis = false )

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 1286 of file MemorySSAUpdater.cpp.

References assert(), llvm::SetVector< T, Vector, Set, N >::begin(), llvm::cast(), llvm::cast_or_null(), llvm::SetVector< T, Vector, Set, N >::clear(), llvm::dyn_cast(), llvm::SetVector< T, Vector, Set, N >::empty(), llvm::SetVector< T, Vector, Set, N >::end(), llvm::Value::hasValueHandle(), llvm::SetVector< T, Vector, Set, N >::insert(), llvm::isa(), onlySingleValue(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateCommon< T, typename >::size(), llvm::Value::use_begin(), llvm::Value::use_empty(), and llvm::ValueHandleBase::ValueIsRAUWd().

Referenced by changeToUnreachable(), eraseInstruction(), llvm::RecursivelyDeleteTriviallyDeadInstructions(), removeMemoryAccess(), and updateForClonedLoop().

◆ updateExitBlocksForClonedLoop() [1/2]

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

Definition at line 770 of file MemorySSAUpdater.cpp.

References I.

◆ updateExitBlocksForClonedLoop() [2/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 762 of file MemorySSAUpdater.cpp.

Referenced by unswitchNontrivialInvariants().

◆ updateForClonedBlockIntoPred()

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

Definition at line 729 of file MemorySSAUpdater.cpp.

◆ 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 660 of file MemorySSAUpdater.cpp.

References assert(), llvm::cast(), llvm::cast_or_null(), llvm::concat(), llvm::SetVector< T, Vector, Set, N >::contains(), llvm::SmallPtrSetImpl< PtrType >::count(), llvm::from_range, getNewDefiningAccessForClone(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::lookup(), llvm::ValueMap< KeyT, ValueT, Config >::lookup(), onlySingleValue(), llvm::predecessors(), ProcessBlock(), and removeMemoryAccess().

Referenced by unswitchNontrivialInvariants().

◆ updatePhisWhenInsertingUniqueBackedgeBlock()

void MemorySSAUpdater::updatePhisWhenInsertingUniqueBackedgeBlock	(	BasicBlock *	LoopHeader,
		BasicBlock *	LoopPreheader,
		BasicBlock *	BackedgeBlock )

Update MemorySSA when inserting a unique backedge block for a loop.

Definition at line 621 of file MemorySSAUpdater.cpp.

References I, and IV.

Referenced by insertUniqueBackedgeBlock().

◆ 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 1249 of file MemorySSAUpdater.cpp.

References llvm::MemoryPhi::addIncoming(), assert(), B(), llvm::MemorySSA::Beginning, llvm::SmallPtrSetImpl< PtrType >::count(), llvm::ArrayRef< T >::empty(), llvm::SmallPtrSetImpl< PtrType >::erase(), llvm::from_range, llvm::BasicBlock::hasNPredecessors(), llvm::pred_size(), llvm::ArrayRef< T >::size(), and llvm::SmallPtrSetImplBase::size().

Referenced by 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()

◆ changeToUnreachable()

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

◆ updatePhisWhenInsertingUniqueBackedgeBlock()

◆ wireOldPredecessorsToNewImmediatePredecessor()