#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:

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 ClobberAlias	instructionClobbersQuery (const MemoryDef MD, const MemoryLocation &UseLoc, const Instruction UseInst, AliasAnalysisType &AA)

template<typename AliasAnalysisType >
static ClobberAlias	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 419 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 2508 of file MemorySSA.cpp.

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

◆ 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 ClobberAlias instructionClobbersQuery	(	const MemoryDef *	MD,
		const MemoryLocation &	UseLoc,
		const Instruction *	UseInst,
		AliasAnalysisType &	AA
	)

static

Definition at line 299 of file MemorySSA.cpp.

References areLoadsReorderable(), assert(), llvm::MemoryUseOrDef::getMemoryInst(), I, llvm::isModOrRefSet(), llvm::isModSet(), llvm::isMustSet(), llvm_unreachable, llvm::AliasResult::MayAlias, llvm::AliasResult::MustAlias, and llvm::AliasResult::NoAlias.

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

◆ instructionClobbersQuery() [2/2]

template<typename AliasAnalysisType >

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

static

Definition at line 347 of file MemorySSA.cpp.

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

◆ isOrdered()

static bool isOrdered ( const Instruction * I )

inlinestatic

Definition at line 1763 of file MemorySSA.cpp.

References I, and SI.

Referenced by llvm::VPReductionPHIRecipe::execute(), and llvm::MemoryDependenceResults::getNonLocalPointerDependency().

◆ isUseTriviallyOptimizableToLiveOnEntry()

template<typename AliasAnalysisType >

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

static

Definition at line 393 of file MemorySSA.cpp.

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

◆ 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().