LLVM  6.0.0svn
Classes | Namespaces | Typedefs | Enumerations | Functions
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/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
 
class  llvm::MemoryUseOrDef
 Class that has the common methods + fields of memory uses/defs. More...
 
struct  llvm::OperandTraits< MemoryUseOrDef >
 
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 >
 
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
 Compute iterated dominance frontiers using a linear time algorithm.
 
 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  { llvm::INVALID_MEMORYACCESS_ID = 0 }
 

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.