LLVM
13.0.0git
|
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 | 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 () | |
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 |
DominatorTree & | getDomTree () 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... | |
Friends | |
class | MemorySSAAnnotatedWriter |
class | MemorySSAPrinterLegacyPass |
class | MemorySSAUpdater |
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition at line 704 of file MemorySSA.h.
Definition at line 754 of file MemorySSA.h.
Definition at line 756 of file MemorySSA.h.
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 791 of file MemorySSA.h.
MemorySSA::MemorySSA | ( | Function & | Func, |
AliasAnalysis * | AA, | ||
DominatorTree * | DT | ||
) |
Definition at line 1237 of file MemorySSA.cpp.
References assert(), and getWalker().
|
delete |
MemorySSA::~MemorySSA | ( | ) |
Definition at line 1255 of file MemorySSA.cpp.
References llvm::User::dropAllReferences().
|
protected |
Definition at line 1705 of file MemorySSA.cpp.
References assert(), I, llvm::MemoryUseOrDef::setDefiningAccess(), and Template.
Referenced by llvm::MemorySSAUpdater::createMemoryAccessAfter(), llvm::MemorySSAUpdater::createMemoryAccessBefore(), and llvm::MemorySSAUpdater::createMemoryAccessInBB().
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 2114 of file MemorySSA.cpp.
References llvm::DominatorTree::dominates(), llvm::MemoryAccess::getBlock(), isLiveOnEntryDef(), and locallyDominates().
Referenced by llvm::canSinkOrHoistInst(), dominates(), and verifyOrderingDominationAndDefUses().
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 2127 of file MemorySSA.cpp.
References llvm::DominatorTree::dominates(), dominates(), llvm::MemoryAccess::getBlock(), llvm::Use::getUser(), and locallyDominates().
LLVM_DUMP_METHOD void MemorySSA::dump | ( | ) | const |
Definition at line 1864 of file MemorySSA.cpp.
References llvm::dbgs(), and print().
|
inline |
Return the list of MemoryAccess's for a given basic block.
This list is not modifiable by the user.
Definition at line 761 of file MemorySSA.h.
References BB.
Referenced by llvm::canSinkOrHoistInst(), foreachMemoryAccess(), llvm::SinkAndHoistLICMFlags::SinkAndHoistLICMFlags(), verifyDominationNumbers(), and verifyOrderingDominationAndDefUses().
|
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 769 of file MemorySSA.h.
References BB.
Referenced by getNewDefiningAccessForClone(), llvm::MemorySSAUpdater::insertUse(), pointerInvalidatedByBlockWithMSSA(), unswitchAllTrivialConditions(), verifyOrderingDominationAndDefUses(), and verifyPrevDefInPhis().
|
inline |
Definition at line 729 of file MemorySSA.h.
Referenced by llvm::MemorySSAUpdater::insertDef().
|
inline |
Definition at line 745 of file MemorySSA.h.
Referenced by llvm::MemorySSA::OptimizeUses::optimizeUses().
|
inline |
Definition at line 725 of file MemorySSA.h.
References BB.
|
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 721 of file MemorySSA.h.
References I.
Referenced by llvm::canSinkOrHoistInst(), llvm::MemorySSAUpdater::changeCondBranchToUnconditionalTo(), llvm::MemorySSAUpdater::changeToUnreachable(), cloneInstructionInExitBlock(), llvm::MemorySSAAnnotatedWriter::emitBasicBlockStartAnnot(), llvm::MemorySSAAnnotatedWriter::emitInstructionAnnot(), llvm::MemorySSAWalker::getClobberingMemoryAccess(), getNewDefiningAccessForClone(), llvm::hasPartialIVCondition(), llvm::MemorySSAUpdater::insertDef(), llvm::Loop::makeLoopInvariant(), moveInstructionBefore(), llvm::MemorySSAUpdater::moveToPlace(), llvm::MemorySSAUpdater::removeBlocks(), llvm::MemorySSAUpdater::removeDuplicatePhiEdgesBetween(), llvm::MemorySSAUpdater::removeEdge(), llvm::MemorySSAUpdater::removeMemoryAccess(), simplifyLoopInst(), sinkInstruction(), turnGuardIntoBranch(), llvm::MemorySSAUpdater::updateForClonedBlockIntoPred(), llvm::MemorySSAUpdater::updateForClonedLoop(), llvm::MemorySSAUpdater::updatePhisWhenInsertingUniqueBackedgeBlock(), verifyOrderingDominationAndDefUses(), verifyPrevDefInPhis(), and llvm::MemorySSAUpdater::wireOldPredecessorsToNewImmediatePredecessor().
MemorySSAWalker * MemorySSA::getSkipSelfWalker | ( | ) |
Definition at line 1581 of file MemorySSA.cpp.
Referenced by llvm::canSinkOrHoistInst(), and pointerInvalidatedByLoopWithMSSA().
MemorySSAWalker * MemorySSA::getWalker | ( | ) |
Definition at line 1566 of file MemorySSA.cpp.
Referenced by MemorySSA(), and removeFromLookups().
|
inlineprotected |
Definition at line 804 of file MemorySSA.h.
References BB.
Referenced by insertIntoListsBefore(), llvm::MemorySSAUpdater::removeBlocks(), llvm::MemorySSAUpdater::updateForClonedLoop(), and llvm::MemorySSAUpdater::wireOldPredecessorsToNewImmediatePredecessor().
|
inlineprotected |
Definition at line 810 of file MemorySSA.h.
References BB, and llvm::simple_ilist< T, Options >::end().
Referenced by llvm::MemorySSAUpdater::insertDef(), and llvm::MemorySSAUpdater::insertUse().
|
protected |
Definition at line 1630 of file MemorySSA.cpp.
References BB, and getWritableBlockAccesses().
Referenced by llvm::MemorySSAUpdater::createMemoryAccessAfter(), llvm::MemorySSAUpdater::createMemoryAccessBefore(), and moveTo().
|
protected |
Definition at line 1598 of file MemorySSA.cpp.
References BB, Beginning, and llvm::find_if_not().
Referenced by llvm::MemorySSAUpdater::createMemoryAccessInBB(), and moveTo().
|
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 741 of file MemorySSA.h.
Referenced by llvm::canSinkOrHoistInst(), dominates(), getNewDefiningAccessForClone(), hasUndefContentsMSSA(), locallyDominates(), pointerInvalidatedByLoopWithMSSA(), llvm::MemorySSAUpdater::removeMemoryAccess(), and llvm::MemorySSAUpdater::updateForClonedLoop().
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
.
Dominator
dominates Dominatee
. Definition at line 2083 of file MemorySSA.cpp.
References assert(), llvm::MemoryAccess::getBlock(), and isLiveOnEntryDef().
Referenced by dominates(), and pointerInvalidatedByBlockWithMSSA().
|
protected |
Definition at line 1680 of file MemorySSA.cpp.
References assert(), BB, Beginning, llvm::MemoryAccess::getBlock(), and insertIntoListsForBlock().
|
protected |
Definition at line 1674 of file MemorySSA.cpp.
References BB, and insertIntoListsBefore().
Referenced by llvm::MemorySSAUpdater::wireOldPredecessorsToNewImmediatePredecessor().
void MemorySSA::print | ( | raw_ostream & | OS | ) | const |
Definition at line 1858 of file MemorySSA.cpp.
References F.
Referenced by llvm::MemoryAccess::dump(), dump(), llvm::MemoryAccess::print(), llvm::MemorySSAWrapperPass::print(), llvm::MemorySSAPrinterPass::run(), and llvm::MemorySSAPrinterLegacyPass::runOnFunction().
|
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 1831 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().
|
protected |
Properly remove MA
from all of MemorySSA's lookup tables.
Definition at line 1804 of file MemorySSA.cpp.
References assert(), llvm::MemoryAccess::getBlock(), llvm::MemoryUseOrDef::getMemoryInst(), getWalker(), llvm::MemorySSAWalker::invalidateInfo(), llvm::MemoryUseOrDef::setDefiningAccess(), and llvm::Value::use_empty().
Referenced by llvm::MemorySSAUpdater::removeBlocks(), and llvm::MemorySSAUpdater::removeMemoryAccess().
|
inlineprotected |
Definition at line 823 of file MemorySSA.h.
References BB.
Referenced by llvm::MemorySSAUpdater::insertDef(), and llvm::MemorySSAUpdater::insertUse().
Verify that all of the blocks we believe to have valid domination numbers actually have valid domination numbers.
Definition at line 1919 of file MemorySSA.cpp.
References assert(), BB, llvm::SmallPtrSetImpl< PtrType >::count(), llvm::SmallPtrSetImplBase::empty(), llvm::SmallPtrSetImpl< PtrType >::erase(), F, and getBlockAccesses().
Referenced by 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 1867 of file MemorySSA.cpp.
References F, verifyDominationNumbers(), verifyOrderingDominationAndDefUses(), and verifyPrevDefInPhis().
Referenced by llvm::deleteDeadLoop(), llvm::hoistRegion(), mergeBlocksIntoPredecessors(), llvm::LoopRotatePass::run(), llvm::LoopInstSimplifyPass::run(), llvm::SimpleLoopUnswitchPass::run(), llvm::FunctionToLoopPassAdaptor::run(), llvm::MemCpyOptPass::runImpl(), llvm::MemorySSAPrinterLegacyPass::runOnFunction(), simplifyLoopInst(), simplifyOneLoop(), llvm::sinkRegion(), llvm::splitBlockBefore(), turnGuardIntoBranch(), unswitchNontrivialInvariants(), unswitchTrivialBranch(), unswitchTrivialSwitch(), and llvm::MemorySSAWrapperPass::verifyAnalysis().
|
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 1961 of file MemorySSA.cpp.
References llvm::AArch64CC::AL, assert(), B, llvm::MachineBasicBlock::begin(), llvm::SmallVectorImpl< T >::clear(), DL, dominates(), E, llvm::MachineBasicBlock::end(), F, 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().
|
protected |
Definition at line 1883 of file MemorySSA.cpp.
References assert(), BB, E, F, getBlockDefs(), llvm::MemoryPhi::getIncomingBlock(), llvm::MemoryPhi::getIncomingValue(), getMemoryAccess(), llvm::DominatorTreeBase< NodeT, IsPostDom >::getNode(), llvm::MemoryPhi::getNumIncomingValues(), and I.
Referenced by verifyMemorySSA().
|
friend |
Definition at line 795 of file MemorySSA.h.
|
friend |
Definition at line 796 of file MemorySSA.h.
|
friend |
Definition at line 797 of file MemorySSA.h.