LLVM  15.0.0git
Classes | Namespaces | Typedefs | Enumerations | Functions | Variables
MemorySSA.h File Reference
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/ilist_node.h"
#include "llvm/ADT/iterator_range.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/MemoryLocation.h"
#include "llvm/Analysis/PHITransAddr.h"
#include "llvm/IR/DerivedUser.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/User.h"
#include "llvm/Pass.h"
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <iterator>
#include <memory>
#include <utility>
Include dependency graph for MemorySSA.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.


struct  llvm::GraphTraits< GraphType >
struct  llvm::MSSAHelpers::AllAccessTag
struct  llvm::MSSAHelpers::DefsOnlyTag
class  llvm::memoryaccess_def_iterator_base< T >
 Iterator base class used to implement const and non-const iterators over the defining accesses of a MemoryAccess. More...
class  llvm::MemoryAccess
struct  llvm::ilist_alloc_traits< MemoryAccess >
class  llvm::MemoryUseOrDef
 Class that has the common methods + fields of memory uses/defs. More...
class  llvm::MemoryUse
 Represents read-only accesses to memory. More...
struct  llvm::OperandTraits< MemoryUse >
class  llvm::MemoryDef
 Represents a read-write access to memory, whether it is a must-alias, or a may-alias. More...
struct  llvm::OperandTraits< MemoryDef >
struct  llvm::OperandTraits< MemoryUseOrDef >
class  llvm::MemoryPhi
 Represents phi nodes for memory accesses. More...
struct  llvm::OperandTraits< MemoryPhi >
class  llvm::MemorySSA
 Encapsulates MemorySSA, including all data associated with memory accesses. More...
class  llvm::MemorySSAUtil
class  llvm::MemorySSAPrinterLegacyPass
class  llvm::MemorySSAAnalysis
 An analysis that produces MemorySSA for a function. More...
struct  llvm::MemorySSAAnalysis::Result
class  llvm::MemorySSAPrinterPass
 Printer pass for MemorySSA. More...
class  llvm::MemorySSAWalkerPrinterPass
 Printer pass for MemorySSA via the walker. More...
struct  llvm::MemorySSAVerifierPass
 Verifier pass for MemorySSA. More...
class  llvm::MemorySSAWrapperPass
 Legacy analysis pass which computes MemorySSA. More...
class  llvm::MemorySSAWalker
 This is the generic walker interface for walkers of MemorySSA. More...
class  llvm::DoNothingMemorySSAWalker
 A MemorySSAWalker that does no alias queries, or anything else. More...
class  llvm::memoryaccess_def_iterator_base< T >
 Iterator base class used to implement const and non-const iterators over the defining accesses of a MemoryAccess. More...
struct  llvm::GraphTraits< MemoryAccess * >
 GraphTraits for a MemoryAccess, which walks defs in the normal case, and uses in the inverse case. More...
struct  llvm::GraphTraits< Inverse< MemoryAccess * > >
class  llvm::upward_defs_iterator
 Provide an iterator that walks defs, giving both the memory access, and the current pointer location, updating the pointer location as it changes due to phi node translation. More...
struct  llvm::def_chain_iterator< T, UseOptimizedChain >
 Walks the defining accesses of MemoryDefs. More...


 This is an optimization pass for GlobalISel generic memory operations.


using llvm::memoryaccess_def_iterator = memoryaccess_def_iterator_base< MemoryAccess >
using llvm::const_memoryaccess_def_iterator = memoryaccess_def_iterator_base< const MemoryAccess >
using llvm::MemoryAccessPair = std::pair< MemoryAccess *, MemoryLocation >
using llvm::ConstMemoryAccessPair = std::pair< const MemoryAccess *, MemoryLocation >


enum  : unsigned { llvm::INVALID_MEMORYACCESS_ID = -1U }


raw_ostream & llvm::operator<< (raw_ostream &OS, const MemoryAccess &MA)
upward_defs_iterator llvm::upward_defs_begin (const MemoryAccessPair &Pair, DominatorTree &DT, bool *PerformedPhiTranslation=nullptr)
upward_defs_iterator llvm::upward_defs_end ()
iterator_range< upward_defs_iterator > llvm::upward_defs (const MemoryAccessPair &Pair, DominatorTree &DT)
template<class T >
iterator_range< def_chain_iterator< T > > llvm::def_chain (T MA, MemoryAccess *UpTo=nullptr)
template<class T >
iterator_range< def_chain_iterator< T, true > > llvm::optimized_def_chain (T MA)


bool llvm::VerifyMemorySSA = false
 Enables verification of MemorySSA. More...

Detailed Description

This file exposes an interface to building/using memory SSA to walk memory instructions using a use/def graph.

Memory SSA class builds an SSA form that links together memory access instructions such as loads, stores, atomics, and calls. Additionally, it does a trivial form of "heap versioning" Every time the memory state changes in the program, we generate a new heap version. It generates MemoryDef/Uses/Phis that are overlayed on top of the existing instructions.

As a trivial example, define i32 @main() #0 { entry: call = call noalias i8* @_Znwm(i64 4) #2 %0 = bitcast i8* call to i32* call1 = call noalias i8* @_Znwm(i64 4) #2 %1 = bitcast i8* call1 to i32* store i32 5, i32* %0, align 4 store i32 7, i32* %1, align 4 %2 = load i32* %0, align 4 %3 = load i32* %1, align 4 add = add nsw i32 %2, %3 ret i32 add }

Will become define i32 @main() #0 { entry: ; 1 = MemoryDef(0) call = call noalias i8* @_Znwm(i64 4) #3 %2 = bitcast i8* call to i32* ; 2 = MemoryDef(1) call1 = call noalias i8* @_Znwm(i64 4) #3 %4 = bitcast i8* call1 to i32* ; 3 = MemoryDef(2) store i32 5, i32* %2, align 4 ; 4 = MemoryDef(3) store i32 7, i32* %4, align 4 ; MemoryUse(3) %7 = load i32* %2, align 4 ; MemoryUse(4) %8 = load i32* %4, align 4 add = add nsw i32 %7, %8 ret i32 add }

Given this form, all the stores that could ever effect the load at %8 can be gotten by using the MemoryUse associated with it, and walking from use to def until you hit the top of the function.

Each def also has a list of users associated with it, so you can walk from both def to users, and users to defs. Note that we disambiguate MemoryUses, but not the RHS of MemoryDefs. You can see this above at %7, which would otherwise be a MemoryUse(4). Being disambiguated means that for a given store, all the MemoryUses on its use lists are may-aliases of that store (but the MemoryDefs on its use list may not be).

MemoryDefs are not disambiguated because it would require multiple reaching definitions, which would require multiple phis, and multiple memoryaccesses per instruction.

In addition to the def/use graph described above, MemoryDefs also contain an "optimized" definition use. The "optimized" use points to some def reachable through the memory def chain. The optimized def may (but is not required to) alias the original MemoryDef, but no def closer to the source def may alias it. As the name implies, the purpose of the optimized use is to allow caching of clobber searches for memory defs. The optimized def may be nullptr, in which case clients must walk the defining access chain.

When iterating the uses of a MemoryDef, both defining uses and optimized uses will be encountered. If only one type is needed, the client must filter the use walk.

Definition in file MemorySSA.h.