GVN.cpp File Reference

#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/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 <utility>

Go to the source code of this file.

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

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

Macros
#define	DEBUG_TYPE   "gvn"

Enumerations
enum	AvailabilityState : char { AvailabilityState::Unavailable = 0, AvailabilityState::Available = 1, AvailabilityState::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 (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. More...
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. More...
static LoadInst *	findDominatingLoad (Value *Ptr, Type *LoadTy, SelectInst *Sel, DominatorTree &DT)
static bool	isLifetimeStart (const Instruction *Inst)
static bool	liesBetween (const Instruction *From, Instruction *Between, const Instruction *To, DominatorTree *DT)
	Assuming To can be reached from both From and Between, does Between lie on every path from From to To? More...
static void	reportMayClobberedLoad (LoadInst *Load, MemDepResult DepInfo, DominatorTree *DT, OptimizationRemarkEmitter *ORE)
	Try to locate the three instruction involved in a missed load-elimination case that is due to an intervening store. More...
static Optional< AvailableValue >	tryToConvertLoadOfPtrSelect (BasicBlock *DepBB, BasicBlock::iterator End, Value *Address, Type *LoadTy, DominatorTree &DT, AAResults *AA)
	Check if a load from pointer-select Address in DepBB can be converted to a value select. More...
static void	reportLoadElim (LoadInst *Load, Value *AvailableValue, OptimizationRemarkEmitter *ORE)
static bool	impliesEquivalanceIfTrue (CmpInst *Cmp)
static bool	impliesEquivalanceIfFalse (CmpInst *Cmp)
static bool	hasUsersIn (Value *V, BasicBlock *BB)
static void	patchAndReplaceAllUsesWith (Instruction *I, Value *Repl)
static bool	isOnlyReachableViaThisEdge (const BasicBlockEdge &E, DominatorTree *DT)
	There is an edge from 'Src' to 'Dst'. More...

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< 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)"))

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "gvn"

Definition at line 86 of file GVN.cpp.

Enumeration Type Documentation

AvailabilityState

enum 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 773 of file GVN.cpp.

Function Documentation

ConstructSSAForLoadSet()

static 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 911 of file GVN.cpp.

References llvm::SSAUpdater::AddAvailableValue(), assert(), BB, llvm::GVNPass::getDominatorTree(), llvm::SSAUpdater::GetValueInMiddleOfBlock(), llvm::SSAUpdater::HasValueForBlock(), llvm::SSAUpdater::Initialize(), llvm::SPII::Load, and llvm::DominatorTreeBase< NodeT, IsPostDom >::properlyDominates().

findDominatingLoad()

static LoadInst* findDominatingLoad ( Value *  Ptr, Type *  LoadTy, SelectInst *  Sel, DominatorTree &  DT  )

static

Definition at line 954 of file GVN.cpp.

References llvm::DominatorTree::dominates(), llvm::Instruction::getParent(), and llvm::Value::users().

Referenced by llvm::gvn::AvailableValue::MaterializeAdjustedValue().

hasUsersIn()

static bool hasUsersIn ( Value *  V, BasicBlock *  BB  )

static

Definition at line 1881 of file GVN.cpp.

References BB, getParent(), and llvm::Value::users().

impliesEquivalanceIfFalse()

static bool impliesEquivalanceIfFalse ( CmpInst *  Cmp )

static

Definition at line 1854 of file GVN.cpp.

References isZero(), LHS, and RHS.

impliesEquivalanceIfTrue()

static bool impliesEquivalanceIfTrue ( CmpInst *  Cmp )

static

Definition at line 1828 of file GVN.cpp.

References isZero(), LHS, and RHS.

isLifetimeStart()

static bool isLifetimeStart ( const Instruction *  Inst )

static

Definition at line 1023 of file GVN.cpp.

Referenced by sinkLifetimeStartMarkers().

isOnlyReachableViaThisEdge()

static 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 2253 of file GVN.cpp.

References assert(), and E.

IsValueFullyAvailableInBlock()

static 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 793 of file GVN.cpp.

References llvm::SmallVectorImpl< T >::append(), assert(), Available, BB, llvm::SmallVectorImpl< T >::clear(), llvm::SmallVectorImpl< T >::emplace_back(), llvm::SmallSet< T, N, C >::empty(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::end(), llvm::SmallSet< T, N, C >::erase(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::find(), llvm::SmallSet< T, N, C >::insert(), int, 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< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::try_emplace(), and Unavailable.

liesBetween()

static bool liesBetween ( const Instruction *  From, Instruction *  Between, const Instruction *  To, 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 1031 of file GVN.cpp.

References llvm::DominatorTree::dominates(), From, llvm::Instruction::getParent(), llvm::SmallSet< T, N, C >::insert(), and llvm::isPotentiallyReachable().

Referenced by reportMayClobberedLoad().

patchAndReplaceAllUsesWith()

static void patchAndReplaceAllUsesWith ( Instruction *  I, Value *  Repl  )

static

Definition at line 2026 of file GVN.cpp.

References I, and llvm::patchReplacementInstruction().

reportLoadElim()

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

static

Definition at line 1726 of file GVN.cpp.

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

reportMayClobberedLoad()

static void reportMayClobberedLoad ( LoadInst *  Load, MemDepResult  DepInfo, 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 1042 of file GVN.cpp.

References assert(), DEBUG_TYPE, llvm::DominatorTree::dominates(), llvm::OptimizationRemarkEmitter::emit(), getFunction(), llvm::MemDepResult::getInst(), llvm::isPotentiallyReachable(), liesBetween(), and llvm::SPII::Load.

STATISTIC() [1/10]

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

STATISTIC() [2/10]

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

STATISTIC() [3/10]

STATISTIC	(	NumGVNBlocks	,
		"Number of blocks merged"
	)

STATISTIC() [4/10]

STATISTIC	(	NumGVNEqProp	,
		"Number of equalities propagated"
	)

STATISTIC() [5/10]

STATISTIC	(	NumGVNInstr	,
		"Number of instructions deleted"
	)

STATISTIC() [6/10]

STATISTIC	(	NumGVNLoad	,
		"Number of loads deleted"
	)

STATISTIC() [7/10]

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

STATISTIC() [8/10]

STATISTIC	(	NumGVNSimpl	,
		"Number of instructions simplified"
	)

STATISTIC() [9/10]

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

STATISTIC() [10/10]

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

tryToConvertLoadOfPtrSelect()

static Optional<AvailableValue> tryToConvertLoadOfPtrSelect ( BasicBlock *  DepBB, BasicBlock::iterator  End, Value *  Address, Type *  LoadTy, DominatorTree &  DT, AAResults *  AA  )

static

Check if a load from pointer-select Address in DepBB can be converted to a value select.

The following conditions need to be satisfied:

1. The pointer select (Address) must be defined in DepBB.
2. Both value operands of the pointer select must be loaded in the same basic block, before the pointer select.
3. There must be no instructions between the found loads and End that may clobber the loads.

Definition at line 1110 of file GVN.cpp.

Variable Documentation

GVNEnableLoadInLoopPRE

cl::opt<bool> GVNEnableLoadInLoopPRE("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))

static

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

GVNEnableMemDep

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

static

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

GVNEnablePRE

cl::opt<bool> GVNEnablePRE("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))

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)"))

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)"))

static