LLVM  16.0.0git
Classes | Public Types | Public Member Functions | Protected Member Functions | Friends | List of all members
llvm::MemorySSA Class Reference

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

#include "llvm/Analysis/MemorySSA.h"

Classes

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

Public Types

enum  VerificationLevel { VerificationLevel::Fast, VerificationLevel::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 = simple_ilist< MemoryAccess, ilist_tag< MSSAHelpers::DefsOnlyTag > >
 

Public Member Functions

 MemorySSA (Function &, AliasAnalysis *, DominatorTree *)
 
 MemorySSA (MemorySSA &&)=delete
 
 ~MemorySSA ()
 
MemorySSAWalkergetWalker ()
 
MemorySSAWalkergetSkipSelfWalker ()
 
MemoryUseOrDefgetMemoryAccess (const Instruction *I) const
 Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it. More...
 
MemoryPhigetMemoryAccess (const BasicBlock *BB) const
 
DominatorTreegetDomTree () 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...
 
MemoryAccessgetLiveOnEntryDef () const
 
const AccessListgetBlockAccesses (const BasicBlock *BB) const
 Return the list of MemoryAccess's for a given basic block. More...
 
const DefsListgetBlockDefs (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 (VerificationLevel=VerificationLevel::Fast) const
 Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right places). More...
 
void ensureOptimizedUses ()
 By default, uses are not optimized during MemorySSA construction. More...
 

Protected Member Functions

void verifyOrderingDominationAndDefUses (Function &F, VerificationLevel=VerificationLevel::Fast) const
 Verify ordering: 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 verifyPrevDefInPhis (Function &F) const
 
AccessListgetWritableBlockAccesses (const BasicBlock *BB) const
 
DefsListgetWritableBlockDefs (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)
 
MemoryUseOrDefcreateDefinedAccess (Instruction *, MemoryAccess *, const MemoryUseOrDef *Template=nullptr, bool CreationMustSucceed=true)
 

Friends

class MemorySSAPrinterLegacyPass
 
class MemorySSAUpdater
 

Detailed Description

Encapsulates MemorySSA, including all data associated with memory accesses.

Definition at line 700 of file MemorySSA.h.

Member Typedef Documentation

◆ AccessList

Definition at line 750 of file MemorySSA.h.

◆ DefsList

Definition at line 752 of file MemorySSA.h.

Member Enumeration Documentation

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

◆ VerificationLevel

Enumerator
Fast 
Full 

Definition at line 781 of file MemorySSA.h.

Constructor & Destructor Documentation

◆ MemorySSA() [1/2]

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

Definition at line 1234 of file MemorySSA.cpp.

References assert(), and getWalker().

◆ MemorySSA() [2/2]

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

◆ ~MemorySSA()

MemorySSA::~MemorySSA ( )

Definition at line 1252 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

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

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

Referenced by llvm::canSinkOrHoistInst(), checkClobberSanity(), dominates(), and verifyOrderingDominationAndDefUses().

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

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

◆ dump()

LLVM_DUMP_METHOD void MemorySSA::dump ( ) const

Definition at line 1862 of file MemorySSA.cpp.

References llvm::dbgs(), 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 2145 of file MemorySSA.cpp.

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

Referenced by llvm::GVNHoist::GVNHoist(), llvm::MemorySSAPrinterPass::run(), and llvm::MemorySSAPrinterLegacyPass::runOnFunction().

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

References BB.

Referenced by llvm::canSinkOrHoistInst(), foreachMemoryAccess(), llvm::MemorySSAUpdater::moveAllAfterSpliceBlocks(), 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 765 of file MemorySSA.h.

References BB.

Referenced by getNewDefiningAccessForClone(), llvm::MemorySSAUpdater::insertUse(), pointerInvalidatedByBlock(), unswitchAllTrivialConditions(), verifyOrderingDominationAndDefUses(), and verifyPrevDefInPhis().

◆ getDomTree()

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

Definition at line 725 of file MemorySSA.h.

Referenced by checkClobberSanity().

◆ getLiveOnEntryDef()

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

◆ getMemoryAccess() [1/2]

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

Definition at line 721 of file MemorySSA.h.

References BB.

◆ getMemoryAccess() [2/2]

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

◆ getSkipSelfWalker()

MemorySSAWalker * MemorySSA::getSkipSelfWalker ( )

Definition at line 1571 of file MemorySSA.cpp.

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

◆ getWalker()

MemorySSAWalker * MemorySSA::getWalker ( )

◆ getWritableBlockAccesses()

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

◆ getWritableBlockDefs()

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

◆ insertIntoListsBefore()

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

◆ insertIntoListsForBlock()

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

Definition at line 1588 of file MemorySSA.cpp.

References BB, Beginning, and llvm::find_if_not().

Referenced by llvm::MemorySSAUpdater::createMemoryAccessInBB(), and 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 737 of file MemorySSA.h.

Referenced by llvm::canSinkOrHoistInst(), checkClobberSanity(), dominates(), getNewDefiningAccessForClone(), hasUndefContents(), llvm::AMDGPU::isClobberedInFunction(), locallyDominates(), pointerInvalidatedByLoop(), llvm::MemorySSAUpdater::removeMemoryAccess(), and llvm::MemorySSAUpdater::updateForClonedLoop().

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

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

Referenced by dominates(), and pointerInvalidatedByBlock().

◆ moveTo() [1/2]

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

◆ moveTo() [2/2]

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

◆ print()

void MemorySSA::print ( raw_ostream OS) const

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

References BB, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::erase(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), and llvm::MemoryAccess::getBlock().

Referenced by llvm::MemorySSAUpdater::removeBlocks(), and llvm::MemorySSAUpdater::removeMemoryAccess().

◆ removeFromLookups()

void MemorySSA::removeFromLookups ( MemoryAccess MA)
protected

◆ renamePass()

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

Definition at line 827 of file MemorySSA.h.

References BB.

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

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

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

Referenced by verifyMemorySSA().

◆ verifyMemorySSA()

void MemorySSA::verifyMemorySSA ( VerificationLevel  VL = VerificationLevel::Fast) const

◆ verifyOrderingDominationAndDefUses()

void MemorySSA::verifyOrderingDominationAndDefUses ( Function F,
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 1965 of file MemorySSA.cpp.

References llvm::AArch64CC::AL, assert(), B, llvm::MachineBasicBlock::begin(), llvm::SmallVectorImpl< T >::clear(), DL, dominates(), E, llvm::MachineBasicBlock::end(), F, Full, getBlockAccesses(), getBlockDefs(), llvm::MemoryUseOrDef::getDefiningAccess(), llvm::MemoryPhi::getIncomingBlock(), llvm::MemoryPhi::getIncomingValue(), getMemoryAccess(), llvm::MemoryPhi::getNumIncomingValues(), llvm::User::getNumOperands(), I, llvm::is_contained(), llvm::pred_begin(), llvm::pred_end(), llvm::predecessors(), llvm::MachineBasicBlock::size(), and llvm::Value::uses().

Referenced by verifyMemorySSA().

◆ verifyPrevDefInPhis()

void MemorySSA::verifyPrevDefInPhis ( Function F) const
protected

Friends And Related Function Documentation

◆ MemorySSAPrinterLegacyPass

friend class MemorySSAPrinterLegacyPass
friend

Definition at line 799 of file MemorySSA.h.

◆ MemorySSAUpdater

friend class MemorySSAUpdater
friend

Definition at line 800 of file MemorySSA.h.


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