MemorySSA.h File Reference

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

#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/GraphTraits.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/ilist.h"
#include "llvm/ADT/ilist_node.h"
#include "llvm/ADT/iterator.h"
#include "llvm/ADT/iterator_range.h"
#include "llvm/ADT/simple_ilist.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/MemoryLocation.h"
#include "llvm/Analysis/PHITransAddr.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/DerivedUser.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Use.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/Pass.h"
#include "llvm/Support/Casting.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.

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

Namespaces
	llvm
	This class represents lattice values for constants.
	llvm::MSSAHelpers

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

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

Functions
raw_ostream &	llvm::operator<< (raw_ostream &OS, const MemoryAccess &MA)
upward_defs_iterator	llvm::upward_defs_begin (const MemoryAccessPair &Pair)
upward_defs_iterator	llvm::upward_defs_end ()
iterator_range< upward_defs_iterator >	llvm::upward_defs (const MemoryAccessPair &Pair)
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)

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 () #0 { entry: call = call noalias i8* (i64 4) #2 %0 = bitcast i8* call to i32* call1 = call noalias i8* (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 () #0 { entry: ; 1 = MemoryDef(0) call = call noalias i8* (i64 4) #3 %2 = bitcast i8* call to i32* ; 2 = MemoryDef(1) call1 = call noalias i8* (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.

Definition in file MemorySSA.h.