#include "llvm/Transforms/Scalar/GVN.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/Hashing.h"
#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/AssumeBundleQueries.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/CFG.h"
#include "llvm/Analysis/DomTreeUpdater.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/InstructionPrecedenceTracking.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/Loads.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/MemoryDependenceAnalysis.h"
#include "llvm/Analysis/MemorySSA.h"
#include "llvm/Analysis/MemorySSAUpdater.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/Analysis/PHITransAddr.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/Attributes.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Constant.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Metadata.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Use.h"
#include "llvm/IR/Value.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils/AssumeBundleBuilder.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/SSAUpdater.h"
#include "llvm/Transforms/Utils/VNCoercion.h"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <optional>
#include <utility>

Classes
struct	llvm::GVNPass::Expression
struct	llvm::DenseMapInfo< GVNPass::Expression >
struct	llvm::gvn::AvailableValue
	Represents a particular available value that we know how to materialize. More...
struct	llvm::gvn::AvailableValueInBlock
	Represents an AvailableValue which can be rematerialized at the end of the associated BasicBlock. More...
class	llvm::gvn::GVNLegacyPass

Macros
#define	DEBUG_TYPE "gvn"

Enumerations
enum class	AvailabilityState : char { Unavailable = 0 , Available = 1 , SpeculativelyAvailable = 2 }

Functions
	STATISTIC (NumGVNInstr, "Number of instructions deleted")
	STATISTIC (NumGVNLoad, "Number of loads deleted")
	STATISTIC (NumGVNPRE, "Number of instructions PRE'd")
	STATISTIC (NumGVNBlocks, "Number of blocks merged")
	STATISTIC (NumGVNSimpl, "Number of instructions simplified")
	STATISTIC (NumGVNEqProp, "Number of equalities propagated")
	STATISTIC (NumPRELoad, "Number of loads PRE'd")
	STATISTIC (NumPRELoopLoad, "Number of loop loads PRE'd")
	STATISTIC (NumPRELoadMoved2CEPred, "Number of loads moved to predecessor of a critical edge in PRE")
	STATISTIC (IsValueFullyAvailableInBlockNumSpeculationsMax, "Number of blocks speculated as available in " "IsValueFullyAvailableInBlock(), max")
	STATISTIC (MaxBBSpeculationCutoffReachedTimes, "Number of times we we reached gvn-max-block-speculations cut-off " "preventing further exploration")
static bool	IsValueFullyAvailableInBlock (BasicBlock BB, DenseMap< BasicBlock , AvailabilityState > &FullyAvailableBlocks)
	Return true if we can prove that the value we're analyzing is fully available in the specified block.
static void	replaceValuesPerBlockEntry (SmallVectorImpl< AvailableValueInBlock > &ValuesPerBlock, Value OldValue, Value NewValue)
	If the specified OldValue exists in ValuesPerBlock, replace its value with NewValue.
static Value *	ConstructSSAForLoadSet (LoadInst *Load, SmallVectorImpl< AvailableValueInBlock > &ValuesPerBlock, GVNPass &GVN)
	Given a set of loads specified by ValuesPerBlock, construct SSA form, allowing us to eliminate Load.
static bool	isLifetimeStart (const Instruction *Inst)
static bool	liesBetween (const Instruction From, Instruction Between, const Instruction To, const DominatorTree DT)
	Assuming To can be reached from both From and Between, does Between lie on every path from From to To?
static const Instruction *	findMayClobberedPtrAccess (LoadInst Load, const DominatorTree DT)
static void	reportMayClobberedLoad (LoadInst Load, MemDepResult DepInfo, const DominatorTree DT, OptimizationRemarkEmitter *ORE)
	Try to locate the three instruction involved in a missed load-elimination case that is due to an intervening store.
static Value *	findDominatingValue (const MemoryLocation &Loc, Type LoadTy, Instruction From, AAResults *AA)
static void	reportLoadElim (LoadInst Load, Value AvailableValue, OptimizationRemarkEmitter *ORE)
static void	patchAndReplaceAllUsesWith (Instruction I, Value Repl)
static bool	isOnlyReachableViaThisEdge (const BasicBlockEdge &E, DominatorTree *DT)
	There is an edge from 'Src' to 'Dst'.

Variables
static cl::opt< bool >	GVNEnablePRE ("enable-pre", cl::init(true), cl::Hidden)
static cl::opt< bool >	GVNEnableLoadPRE ("enable-load-pre", cl::init(true))
static cl::opt< bool >	GVNEnableLoadInLoopPRE ("enable-load-in-loop-pre", cl::init(true))
static cl::opt< bool >	GVNEnableSplitBackedgeInLoadPRE ("enable-split-backedge-in-load-pre", cl::init(false))
static cl::opt< bool >	GVNEnableMemDep ("enable-gvn-memdep", cl::init(true))
static cl::opt< bool >	GVNEnableMemorySSA ("enable-gvn-memoryssa", cl::init(false))
static cl::opt< uint32_t >	MaxNumDeps ("gvn-max-num-deps", cl::Hidden, cl::init(100), cl::desc("Max number of dependences to attempt Load PRE (default = 100)"))
static cl::opt< uint32_t >	MaxBBSpeculations ("gvn-max-block-speculations", cl::Hidden, cl::init(600), cl::desc("Max number of blocks we're willing to speculate on (and recurse " "into) when deducing if a value is fully available or not in GVN " "(default = 600)"))
static cl::opt< uint32_t >	MaxNumVisitedInsts ("gvn-max-num-visited-insts", cl::Hidden, cl::init(100), cl::desc("Max number of visited instructions when trying to find " "dominating value of select dependency (default = 100)"))
static cl::opt< uint32_t >	MaxNumInsnsPerBlock ("gvn-max-num-insns", cl::Hidden, cl::init(100), cl::desc("Max number of instructions to scan in each basic block in GVN " "(default = 100)"))

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE "gvn"

Definition at line 88 of file GVN.cpp.

Enumeration Type Documentation

◆ AvailabilityState

enum class AvailabilityState : char

strong

Enumerator

Unavailable

We know the block is not fully available. This is a fixpoint.

Available

We know the block is fully available. This is a fixpoint.

SpeculativelyAvailable

We do not know whether the block is fully available or not, but we are currently speculating that it will be.

If it would have turned out that the block was, in fact, not fully available, this would have been cleaned up into an Unavailable.

Definition at line 947 of file GVN.cpp.

Function Documentation

◆ ConstructSSAForLoadSet()

Value * ConstructSSAForLoadSet	(	LoadInst *	Load,
		SmallVectorImpl< AvailableValueInBlock > &	ValuesPerBlock,
		GVNPass &	GVN )

static

Given a set of loads specified by ValuesPerBlock, construct SSA form, allowing us to eliminate Load.

This returns the value that should be used at Load's definition site.

Definition at line 1102 of file GVN.cpp.

References llvm::SSAUpdater::AddAvailableValue(), assert(), llvm::GVNPass::getDominatorTree(), llvm::SSAUpdater::GetValueInMiddleOfBlock(), llvm::SSAUpdater::HasValueForBlock(), llvm::SSAUpdater::Initialize(), llvm::DominatorTreeBase< NodeT, IsPostDom >::properlyDominates(), and llvm::SmallVectorTemplateCommon< T, typename >::size().

◆ findDominatingValue()

Value * findDominatingValue	(	const MemoryLocation &	Loc,
		Type *	LoadTy,
		Instruction *	From,
		AAResults *	AA )

static

Definition at line 1303 of file GVN.cpp.

References llvm::dyn_cast(), llvm::BatchAAResults::getModRefInfo(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), llvm::ilist_node_with_parent< NodeTy, ParentTy, Options >::getPrevNode(), llvm::BasicBlock::getSinglePredecessor(), llvm::BasicBlock::getTerminator(), llvm::isModSet(), and MaxNumVisitedInsts.

◆ findMayClobberedPtrAccess()

const Instruction * findMayClobberedPtrAccess	(	LoadInst *	Load,
		const DominatorTree *	DT )

static

Definition at line 1227 of file GVN.cpp.

References assert(), llvm::cast(), llvm::DominatorTree::dominates(), llvm::Value::hasUseList(), I, llvm::isa(), llvm::isPotentiallyReachable(), liesBetween(), and llvm::Value::users().

Referenced by reportMayClobberedLoad().

◆ isLifetimeStart()

bool isLifetimeStart ( const Instruction * Inst )

static

Definition at line 1210 of file GVN.cpp.

References llvm::dyn_cast(), and II.

Referenced by sinkLifetimeStartMarkers().

◆ isOnlyReachableViaThisEdge()

bool isOnlyReachableViaThisEdge	(	const BasicBlockEdge &	E,
		DominatorTree *	DT )

static

There is an edge from 'Src' to 'Dst'.

Return true if every path from the entry block to 'Dst' passes via this edge. In particular 'Dst' must not be reachable via another edge from 'Src'.

Definition at line 2421 of file GVN.cpp.

References assert(), and E().

◆ IsValueFullyAvailableInBlock()

bool IsValueFullyAvailableInBlock	(	BasicBlock *	BB,
		DenseMap< BasicBlock *, AvailabilityState > &	FullyAvailableBlocks )

static

Return true if we can prove that the value we're analyzing is fully available in the specified block.

As we go, keep track of which blocks we know are fully alive in FullyAvailableBlocks. This map is actually a tri-state map with the following values: 0) we know the block is not fully available. 1) we know the block is fully available. 2) we do not know whether the block is fully available or not, but we are currently speculating that it will be.

Definition at line 967 of file GVN.cpp.

References llvm::SmallVectorImpl< T >::append(), assert(), Available, llvm::SmallVectorImpl< T >::clear(), llvm::SmallVectorImpl< T >::emplace_back(), llvm::SmallPtrSetImplBase::empty(), llvm::SmallVectorTemplateCommon< T, typename >::empty(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::SmallPtrSetImpl< PtrType >::erase(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), llvm::SmallPtrSetImpl< PtrType >::insert(), IV, MaxBBSpeculations, llvm::SmallVectorImpl< T >::pop_back_val(), llvm::pred_begin(), llvm::pred_empty(), llvm::pred_end(), SpeculativelyAvailable, llvm::succ_begin(), llvm::succ_end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::try_emplace(), and Unavailable.

◆ liesBetween()

bool liesBetween	(	const Instruction *	From,
		Instruction *	Between,
		const Instruction *	To,
		const DominatorTree *	DT )

static

Assuming To can be reached from both From and Between, does Between lie on every path from From to To?

Definition at line 1218 of file GVN.cpp.

References llvm::DominatorTree::dominates(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), llvm::SmallPtrSetImpl< PtrType >::insert(), and llvm::isPotentiallyReachable().

Referenced by findMayClobberedPtrAccess().

◆ patchAndReplaceAllUsesWith()

void patchAndReplaceAllUsesWith	(	Instruction *	I,
		Value *	Repl )

static

Definition at line 2144 of file GVN.cpp.

References I, and llvm::patchReplacementInstruction().

◆ replaceValuesPerBlockEntry()

void replaceValuesPerBlockEntry	(	SmallVectorImpl< AvailableValueInBlock > &	ValuesPerBlock,
		Value *	OldValue,
		Value *	NewValue )

static

If the specified OldValue exists in ValuesPerBlock, replace its value with NewValue.

Definition at line 1083 of file GVN.cpp.

◆ reportLoadElim()

void reportLoadElim	(	LoadInst *	Load,
		Value *	AvailableValue,
		OptimizationRemarkEmitter *	ORE )

static

Definition at line 1979 of file GVN.cpp.

References DEBUG_TYPE, and llvm::OptimizationRemarkEmitter::emit().

◆ reportMayClobberedLoad()

void reportMayClobberedLoad	(	LoadInst *	Load,
		MemDepResult	DepInfo,
		const DominatorTree *	DT,
		OptimizationRemarkEmitter *	ORE )

static

Try to locate the three instruction involved in a missed load-elimination case that is due to an intervening store.

Definition at line 1283 of file GVN.cpp.

References DEBUG_TYPE, llvm::OptimizationRemarkEmitter::emit(), findMayClobberedPtrAccess(), and llvm::MemDepResult::getInst().

◆ STATISTIC() [1/11]

STATISTIC	(	IsValueFullyAvailableInBlockNumSpeculationsMax	,
		"Number of blocks speculated as available in " "	IsValueFullyAvailableInBlock(),
		max"	)

◆ STATISTIC() [2/11]

STATISTIC	(	MaxBBSpeculationCutoffReachedTimes	,
		"Number of times we we reached gvn-max-block-speculations cut-off " "preventing further exploration"	)

◆ STATISTIC() [3/11]

STATISTIC	(	NumGVNBlocks	,
		"Number of blocks merged"	)

◆ STATISTIC() [4/11]

STATISTIC	(	NumGVNEqProp	,
		"Number of equalities propagated"	)

◆ STATISTIC() [5/11]

STATISTIC	(	NumGVNInstr	,
		"Number of instructions deleted"	)

◆ STATISTIC() [6/11]

STATISTIC	(	NumGVNLoad	,
		"Number of loads deleted"	)

◆ STATISTIC() [7/11]

STATISTIC	(	NumGVNPRE	,
		"Number of instructions PRE'd"	)

◆ STATISTIC() [8/11]

STATISTIC	(	NumGVNSimpl	,
		"Number of instructions simplified"	)

◆ STATISTIC() [9/11]

STATISTIC	(	NumPRELoad	,
		"Number of loads PRE'd"	)

◆ STATISTIC() [10/11]

STATISTIC	(	NumPRELoadMoved2CEPred	,
		"Number of loads moved to predecessor of a critical edge in PRE"	)

◆ STATISTIC() [11/11]

STATISTIC	(	NumPRELoopLoad	,
		"Number of loop loads PRE'd"	)

Variable Documentation

◆ GVNEnableLoadInLoopPRE

cl::opt< bool > GVNEnableLoadInLoopPRE("enable-load-in-loop-pre", cl::init(true))	(	"enable-load-in-loop-pre"	,
		cl::init(true)	)

static

Referenced by llvm::GVNPass::isLoadInLoopPREEnabled().

◆ GVNEnableLoadPRE

cl::opt< bool > GVNEnableLoadPRE("enable-load-pre", cl::init(true))	(	"enable-load-pre"	,
		cl::init(true)	)

static

Referenced by llvm::GVNPass::isLoadPREEnabled().

◆ GVNEnableMemDep

cl::opt< bool > GVNEnableMemDep("enable-gvn-memdep", cl::init(true))	(	"enable-gvn-memdep"	,
		cl::init(true)	)

static

Referenced by llvm::gvn::GVNLegacyPass::GVNLegacyPass(), and llvm::GVNPass::isMemDepEnabled().

◆ GVNEnableMemorySSA

cl::opt< bool > GVNEnableMemorySSA("enable-gvn-memoryssa", cl::init(false))	(	"enable-gvn-memoryssa"	,
		cl::init(false)	)

static

Referenced by llvm::gvn::GVNLegacyPass::GVNLegacyPass(), and llvm::GVNPass::isMemorySSAEnabled().

◆ GVNEnablePRE

cl::opt< bool > GVNEnablePRE("enable-pre", cl::init(true), cl::Hidden)	(	"enable-pre"	,
		cl::init(true)	,
		cl::Hidden	)

static

Referenced by llvm::GVNPass::isPREEnabled().

◆ GVNEnableSplitBackedgeInLoadPRE

cl::opt< bool > GVNEnableSplitBackedgeInLoadPRE("enable-split-backedge-in-load-pre", cl::init(false))	(	"enable-split-backedge-in-load-pre"	,
		cl::init(false)	)

static

Referenced by llvm::GVNPass::isLoadPRESplitBackedgeEnabled().

◆ MaxBBSpeculations

cl::opt< uint32_t > MaxBBSpeculations("gvn-max-block-speculations", cl::Hidden, cl::init(600), cl::desc("Max number of blocks we're willing to speculate on (and recurse " "into) when deducing if a value is fully available or not in GVN " "(default = 600)"))	(	"gvn-max-block-speculations"	,
		cl::Hidden	,
		cl::init(600)	,
		cl::desc("Max number of blocks we're willing to speculate on (and recurse " "into) when deducing if a value is fully available or not in GVN " "(default = 600)")	)

static

Referenced by IsValueFullyAvailableInBlock().

◆ MaxNumDeps

cl::opt< uint32_t > MaxNumDeps("gvn-max-num-deps", cl::Hidden, cl::init(100), cl::desc("Max number of dependences to attempt Load PRE (default = 100)"))	(	"gvn-max-num-deps"	,
		cl::Hidden	,
		cl::init(100)	,
		cl::desc("Max number of dependences to attempt Load PRE (default = 100)")	)

static

◆ MaxNumInsnsPerBlock

cl::opt< uint32_t > MaxNumInsnsPerBlock("gvn-max-num-insns", cl::Hidden, cl::init(100), cl::desc("Max number of instructions to scan in each basic block in GVN " "(default = 100)"))	(	"gvn-max-num-insns"	,
		cl::Hidden	,
		cl::init(100)	,
		cl::desc("Max number of instructions to scan in each basic block in GVN " "(default = 100)")	)

static

◆ MaxNumVisitedInsts

cl::opt< uint32_t > MaxNumVisitedInsts("gvn-max-num-visited-insts", cl::Hidden, cl::init(100), cl::desc("Max number of visited instructions when trying to find " "dominating value of select dependency (default = 100)"))	(	"gvn-max-num-visited-insts"	,
		cl::Hidden	,
		cl::init(100)	,
		cl::desc("Max number of visited instructions when trying to find " "dominating value of select dependency (default = 100)")	)

static

Referenced by findDominatingValue().

Classes

Macros

Enumerations

Functions

Variables

Macro Definition Documentation

◆ DEBUG_TYPE

Enumeration Type Documentation

◆ AvailabilityState

Function Documentation

◆ ConstructSSAForLoadSet()

◆ findDominatingValue()

◆ findMayClobberedPtrAccess()

◆ isLifetimeStart()

◆ isOnlyReachableViaThisEdge()

◆ IsValueFullyAvailableInBlock()

◆ liesBetween()

◆ patchAndReplaceAllUsesWith()

◆ replaceValuesPerBlockEntry()

◆ reportLoadElim()

◆ reportMayClobberedLoad()

◆ STATISTIC() [1/11]

◆ STATISTIC() [2/11]

◆ STATISTIC() [3/11]

◆ STATISTIC() [4/11]

◆ STATISTIC() [5/11]

◆ STATISTIC() [6/11]

◆ STATISTIC() [7/11]

◆ STATISTIC() [8/11]

◆ STATISTIC() [9/11]

◆ STATISTIC() [10/11]

◆ STATISTIC() [11/11]

Variable Documentation

◆ GVNEnableLoadInLoopPRE

◆ GVNEnableLoadPRE

◆ GVNEnableMemDep

◆ GVNEnableMemorySSA

◆ GVNEnablePRE

◆ GVNEnableSplitBackedgeInLoadPRE

◆ MaxBBSpeculations

◆ MaxNumDeps

◆ MaxNumInsnsPerBlock

◆ MaxNumVisitedInsts