MemorySSA.cpp File Reference

#include "llvm/Analysis/MemorySSA.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DenseMapInfo.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/Hashing.h"
#include "llvm/ADT/None.h"
#include "llvm/ADT/Optional.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/ADT/iterator.h"
#include "llvm/ADT/iterator_range.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/CFGPrinter.h"
#include "llvm/Analysis/IteratedDominanceFrontier.h"
#include "llvm/Analysis/MemoryLocation.h"
#include "llvm/Config/llvm-config.h"
#include "llvm/IR/AssemblyAnnotationWriter.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Operator.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/Use.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.h"
#include "llvm/Support/AtomicOrdering.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/FormattedStream.h"
#include "llvm/Support/GraphWriter.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cassert>
#include <iterator>
#include <memory>
#include <utility>

Include dependency graph for MemorySSA.cpp:

Go to the source code of this file.

Classes
struct	llvm::DenseMapInfo< MemoryLocOrCall >
class	llvm::MemorySSA::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...
class	DOTFuncMSSAInfo
struct	llvm::GraphTraits< DOTFuncMSSAInfo * >
struct	llvm::DOTGraphTraits< DOTFuncMSSAInfo * >

Namespaces
	llvm
	This is an optimization pass for GlobalISel generic memory operations.

Macros
#define	DEBUG_TYPE   "memoryssa"

Functions
	INITIALIZE_PASS_BEGIN (MemorySSAWrapperPass, "memoryssa", "Memory SSA", false, true) INITIALIZE_PASS_END(MemorySSAWrapperPass
Memory true	INITIALIZE_PASS_BEGIN (MemorySSAPrinterLegacyPass, "print-memoryssa", "Memory SSA Printer", false, false) INITIALIZE_PASS_END(MemorySSAPrinterLegacyPass
Memory true print Memory SSA static false cl::opt< unsigned >	MaxCheckLimit ("memssa-check-limit", cl::Hidden, cl::init(100), cl::desc("The maximum number of stores/phis MemorySSA" "will consider trying to walk past (default = 100)"))
static bool	areLoadsReorderable (const LoadInst *Use, const LoadInst *MayClobber)
	This does one-way checks to see if Use could theoretically be hoisted above MayClobber. More...
template<typename AliasAnalysisType >
static bool	instructionClobbersQuery (const MemoryDef *MD, const MemoryLocation &UseLoc, const Instruction *UseInst, AliasAnalysisType &AA)
template<typename AliasAnalysisType >
static bool	instructionClobbersQuery (MemoryDef *MD, const MemoryUseOrDef *MU, const MemoryLocOrCall &UseMLOC, AliasAnalysisType &AA)
template<typename AliasAnalysisType >
static bool	isUseTriviallyOptimizableToLiveOnEntry (AliasAnalysisType &AA, const Instruction *I)
template<typename AliasAnalysisType >
static LLVM_ATTRIBUTE_UNUSED void	checkClobberSanity (const MemoryAccess *Start, MemoryAccess *ClobberAt, const MemoryLocation &StartLoc, const MemorySSA &MSSA, const UpwardsMemoryQuery &Query, AliasAnalysisType &AA, bool AllowImpreciseClobber=false)
	Verifies that Start is clobbered by ClobberAt, and that nothing inbetween Start and ClobberAt can clobbers Start. More...
static bool	isOrdered (const Instruction *I)
static const Instruction *	getInvariantGroupClobberingInstruction (Instruction &I, DominatorTree &DT)

Variables
static cl::opt< std::string >	DotCFGMSSA ("dot-cfg-mssa", cl::value_desc("file name for generated dot file"), cl::desc("file name for generated dot file"), cl::init(""))
	memoryssa
Memory	SSA
Memory	false
Memory true print Memory SSA	Printer
static cl::opt< bool, true >	VerifyMemorySSAX ("verify-memoryssa", cl::location(VerifyMemorySSA), cl::Hidden, cl::desc("Enable verification of MemorySSA."))
const static char	LiveOnEntryStr [] = "liveOnEntry"

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "memoryssa"

Definition at line 62 of file MemorySSA.cpp.

Function Documentation

areLoadsReorderable()

static bool areLoadsReorderable ( const LoadInst *  Use, const LoadInst *  MayClobber  )

static

This does one-way checks to see if Use could theoretically be hoisted above MayClobber.

This will not check the other way around.

This assumes that, for the purposes of MemorySSA, Use comes directly after MayClobber, with no potentially clobbering operations in between them. (Where potentially clobbering ops are memory barriers, aliased stores, etc.)

Definition at line 262 of file MemorySSA.cpp.

References llvm::Acquire, llvm::LoadInst::getOrdering(), llvm::isAtLeastOrStrongerThan(), llvm::LoadInst::isVolatile(), and llvm::SequentiallyConsistent.

Referenced by instructionClobbersQuery().

checkClobberSanity()

template<typename AliasAnalysisType >

static LLVM_ATTRIBUTE_UNUSED void checkClobberSanity ( const MemoryAccess *  Start, MemoryAccess *  ClobberAt, const MemoryLocation &  StartLoc, const MemorySSA &  MSSA, const UpwardsMemoryQuery &  Query, AliasAnalysisType &  AA, bool  AllowImpreciseClobber = false  )

static

Verifies that Start is clobbered by ClobberAt, and that nothing inbetween Start and ClobberAt can clobbers Start.

This is meant to be as simple and self-contained as possible. Because it uses no cache, etc., it can be relatively expensive.

Parameters

Start	The MemoryAccess that we want to walk from.
ClobberAt	A clobber for Start.
StartLoc	The MemoryLocation for Start.
MSSA	The MemorySSA instance that Start and ClobberAt belong to.
Query	The UpwardsMemoryQuery we used for our search.
AA	The AliasAnalysis we used for our search.
AllowImpreciseClobber	Always false, unless we do relaxed verify.

Definition at line 403 of file MemorySSA.cpp.

References assert(), llvm::def_chain(), llvm::MemorySSA::dominates(), llvm::SmallVectorImpl< T >::emplace_back(), llvm::MemorySSA::getDomTree(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert(), instructionClobbersQuery(), llvm::MemorySSA::isLiveOnEntryDef(), llvm::DominatorTree::isReachableFromEntry(), MAP, llvm::SmallVectorImpl< T >::pop_back_val(), llvm::upward_defs_begin(), and llvm::upward_defs_end().

getInvariantGroupClobberingInstruction()

static const Instruction* getInvariantGroupClobberingInstruction ( Instruction &  I, DominatorTree &  DT  )

static

Definition at line 2461 of file MemorySSA.cpp.

References assert(), llvm::DominatorTree::dominates(), GEP, llvm::getLoadStorePointerOperand(), I, llvm::SmallVectorImpl< T >::pop_back_val(), Ptr, and llvm::Value::stripPointerCasts().

INITIALIZE_PASS_BEGIN() [1/2]

Memory true INITIALIZE_PASS_BEGIN	(	MemorySSAPrinterLegacyPass	,
		"print-memoryssa"	,
		"Memory SSA Printer"	,
		false	,
		false
	)

INITIALIZE_PASS_BEGIN() [2/2]

INITIALIZE_PASS_BEGIN	(	MemorySSAWrapperPass	,
		"memoryssa"	,
		"Memory SSA"	,
		false	,
		true
	)

instructionClobbersQuery() [1/2]

template<typename AliasAnalysisType >

static bool instructionClobbersQuery ( const MemoryDef *  MD, const MemoryLocation &  UseLoc, const Instruction *  UseInst, AliasAnalysisType &  AA  )

static

Definition at line 288 of file MemorySSA.cpp.

References areLoadsReorderable(), assert(), llvm::MemoryUseOrDef::getMemoryInst(), I, llvm::isModOrRefSet(), llvm::isModSet(), and llvm_unreachable.

Referenced by checkClobberSanity(), llvm::MemorySSAUtil::defClobbersUseOrDef(), and instructionClobbersQuery().

instructionClobbersQuery() [2/2]

template<typename AliasAnalysisType >

static bool instructionClobbersQuery ( MemoryDef *  MD, const MemoryUseOrDef *  MU, const MemoryLocOrCall &  UseMLOC, AliasAnalysisType &  AA  )

static

Definition at line 332 of file MemorySSA.cpp.

References llvm::MemoryUseOrDef::getMemoryInst(), and instructionClobbersQuery().

isOrdered()

static bool isOrdered ( const Instruction *  I )

inlinestatic

Definition at line 1715 of file MemorySSA.cpp.

References I, and SI.

Referenced by llvm::MemoryDependenceResults::getNonLocalPointerDependency().

isUseTriviallyOptimizableToLiveOnEntry()

template<typename AliasAnalysisType >

static bool isUseTriviallyOptimizableToLiveOnEntry ( AliasAnalysisType &  AA, const Instruction *  I  )

static

Definition at line 376 of file MemorySSA.cpp.

References llvm::MemoryLocation::get(), I, and llvm::isModSet().

MaxCheckLimit()

Memory true print Memory SSA static false cl::opt<unsigned> MaxCheckLimit ( "memssa-check-limit"  , cl::Hidden  , cl::init(100)  , cl::desc("The maximum number of stores/phis MemorySSA" "will consider trying to walk past (default = 100)")    )

static

Variable Documentation

DotCFGMSSA

cl::opt<std::string> DotCFGMSSA("dot-cfg-mssa", cl::value_desc("file name for generated dot file"), cl::desc("file name for generated dot file"), cl::init(""))

static

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

false

Memory true print Memory SSA false

Definition at line 73 of file MemorySSA.cpp.

LiveOnEntryStr

const static char LiveOnEntryStr[] = "liveOnEntry"

static

Definition at line 98 of file MemorySSA.cpp.

Referenced by llvm::MemoryUse::print(), llvm::MemoryDef::print(), and llvm::MemoryPhi::print().

memoryssa

Memory true print memoryssa

Definition at line 73 of file MemorySSA.cpp.

Printer

Memory true print Memory SSA Printer

Definition at line 80 of file MemorySSA.cpp.

Referenced by llvm::LLVMTargetMachine::addPassesToEmitMC(), llvm::AVRMCInstLower::AVRMCInstLower(), llvm::createGCInfoPrinter(), llvm::MCInst::dump_pretty(), llvm::pdb::SymbolGroup::formatFromChecksumsOffset(), llvm::pdb::SymbolGroup::formatFromFileName(), formatInternal(), GetSymbolRef(), llvm::pdb::operator<<(), llvm::printAmdKernelCodeField(), llvm::VPlan::printDOT(), llvm::ScopedPrinter::printList(), llvm::printMIR(), llvm::codeview::printTypeIndex(), and SimplifyShortMoveForm().

SSA

Memory SSA

Definition at line 73 of file MemorySSA.cpp.

Referenced by llvm::promoteLoopAccessesToScalars(), and RewriteUsesOfClonedInstructions().

VerifyMemorySSAX

cl::opt<bool, true> VerifyMemorySSAX("verify-memoryssa", cl::location(VerifyMemorySSA), cl::Hidden, cl::desc("Enable verification of MemorySSA."))

static