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/PointerIntPair.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/AssumptionCache.h"
#include "llvm/Analysis/CFG.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/MemoryDependenceAnalysis.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/Analysis/PHITransAddr.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Config/llvm-config.h"
#include "llvm/IR/Attributes.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CallSite.h"
#include "llvm/IR/Constant.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/IR/DomTreeUpdater.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/Intrinsics.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Metadata.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/Operator.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/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/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>
#include <vector>

Go to the source code of this file.

Classes
struct	llvm::GVN::Expression
struct	llvm::DenseMapInfo< GVN::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 class represents lattice values for constants.

Macros
#define	DEBUG_TYPE   "gvn"

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")
static bool	IsValueFullyAvailableInBlock (BasicBlock *BB, DenseMap< BasicBlock *, char > &FullyAvailableBlocks, uint32_t RecurseDepth)
	Return true if we can prove that the value we're analyzing is fully available in the specified block. More...
static Value *	ConstructSSAForLoadSet (LoadInst *LI, SmallVectorImpl< AvailableValueInBlock > &ValuesPerBlock, GVN &gvn)
	Given a set of loads specified by ValuesPerBlock, construct SSA form, allowing us to eliminate LI. More...
static bool	isLifetimeStart (const Instruction *Inst)
static void	reportMayClobberedLoad (LoadInst *LI, 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 void	reportLoadElim (LoadInst *LI, 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'. More...

Variables
static cl::opt< bool >	EnablePRE ("enable-pre", cl::init(true), cl::Hidden)
static cl::opt< bool >	EnableLoadPRE ("enable-load-pre", cl::init(true))
static cl::opt< bool >	EnableMemDep ("enable-gvn-memdep", cl::init(true))
static cl::opt< uint32_t >	MaxRecurseDepth ("gvn-max-recurse-depth", cl::Hidden, cl::init(1000), cl::ZeroOrMore, cl::desc("Max recurse depth in GVN (default = 1000)"))
static cl::opt< uint32_t >	MaxNumDeps ("gvn-max-num-deps", cl::Hidden, cl::init(100), cl::ZeroOrMore, cl::desc("Max number of dependences to attempt Load PRE (default = 100)"))

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "gvn"

Definition at line 88 of file GVN.cpp.

Referenced by reportLoadElim(), and reportMayClobberedLoad().

Function Documentation

ConstructSSAForLoadSet()

static Value* ConstructSSAForLoadSet ( LoadInst *  LI, SmallVectorImpl< AvailableValueInBlock > &  ValuesPerBlock, GVN &  gvn  )

static

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

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

Definition at line 746 of file GVN.cpp.

References llvm::SSAUpdater::AddAvailableValue(), assert(), llvm::GVN::getDominatorTree(), llvm::Value::getName(), llvm::Instruction::getParent(), llvm::Value::getType(), llvm::SSAUpdater::GetValueInMiddleOfBlock(), llvm::SSAUpdater::HasValueForBlock(), llvm::SSAUpdater::Initialize(), llvm::DominatorTreeBase< NodeT, IsPostDom >::properlyDominates(), and llvm::SmallVectorBase::size().

Referenced by reportLoadElim(), and reportMayClobberedLoad().

isLifetimeStart()

static bool isLifetimeStart ( const Instruction *  Inst )

static

Definition at line 835 of file GVN.cpp.

References llvm::Intrinsic::lifetime_start.

Referenced by reportMayClobberedLoad().

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

References llvm::PHINode::addIncoming(), llvm::any_of(), assert(), llvm::Intrinsic::assume, B, llvm::BasicBlock::begin(), llvm::Function::begin(), llvm::iplist_impl< IntrusiveListT, TraitsT >::clear(), llvm::Instruction::clone(), llvm::PHINode::Create(), llvm::dbgs(), llvm::Value::deleteValue(), llvm::depth_first(), llvm::dyn_cast(), E, llvm::DomTreeUpdater::Eager, llvm::SmallVectorBase::empty(), EnablePRE, llvm::BasicBlock::end(), llvm::Function::end(), llvm::Instruction::eraseFromParent(), F(), llvm::CmpInst::FCMP_OEQ, llvm::CmpInst::FCMP_UNE, first, llvm::BasicBlock::front(), llvm::ConstantInt::get(), llvm::BasicBlock::getContext(), llvm::Module::getDataLayout(), llvm::Instruction::getDebugLoc(), llvm::BasicBlockEdge::getEnd(), llvm::Function::getEntryBlock(), llvm::ConstantInt::getFalse(), llvm::IntrinsicInst::getIntrinsicID(), llvm::Instruction::getModule(), llvm::Value::getName(), llvm::User::getNumOperands(), llvm::User::getOperand(), llvm::Instruction::getParent(), llvm::BasicBlock::getParent(), llvm::BasicBlock::getSinglePredecessor(), llvm::BasicBlockEdge::getStart(), llvm::GetSuccessorNumber(), llvm::BasicBlock::getTerminator(), llvm::ConstantInt::getTrue(), llvm::Value::getType(), llvm::Value::hasOneUse(), I, llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_NE, llvm::Instruction::insertBefore(), llvm::isCriticalEdge(), llvm::isInstructionTriviallyDead(), llvm::Type::isIntegerTy(), llvm::ConstantInt::isMinusOne(), llvm::Type::isPtrOrPtrVectorTy(), llvm::isSafeToSpeculativelyExecute(), llvm::Instruction::isTerminator(), llvm::Type::isVoidTy(), isZero(), LLVM_DEBUG, llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, InlineBuckets, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::lookup(), llvm::PatternMatch::m_And(), llvm::PatternMatch::m_Or(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), llvm::Instruction::mayHaveSideEffects(), llvm::Instruction::mayReadFromMemory(), llvm::MergeBlockIntoPredecessor(), llvm::User::operands(), P, patchAndReplaceAllUsesWith(), llvm::patchReplacementInstruction(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::predecessors(), llvm::SmallVectorTemplateBase< T >::push_back(), llvm::Value::replaceAllUsesWith(), llvm::replaceDominatedUsesWith(), llvm::salvageDebugInfo(), second, llvm::Instruction::setDebugLoc(), llvm::Value::setName(), llvm::User::setOperand(), SI, llvm::SimplifyInstruction(), llvm::SplitCriticalEdge(), llvm::success, std::swap(), and llvm::Value::use_empty().

IsValueFullyAvailableInBlock()

static bool IsValueFullyAvailableInBlock ( BasicBlock *  BB, DenseMap< BasicBlock *, char > &  FullyAvailableBlocks, uint32_t  RecurseDepth  )

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. 3) we are speculating for this block and have used that to speculate for other blocks.

Definition at line 673 of file GVN.cpp.

References llvm::SmallVectorImpl< T >::append(), llvm::SmallVectorBase::empty(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::insert(), MaxRecurseDepth, llvm::SmallVectorImpl< T >::pop_back_val(), llvm::pred_begin(), llvm::pred_end(), llvm::SmallVectorTemplateBase< T >::push_back(), llvm::succ_begin(), and llvm::succ_end().

Referenced by reportMayClobberedLoad().

patchAndReplaceAllUsesWith()

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

static

Definition at line 1447 of file GVN.cpp.

References llvm::dbgs(), Expressions, llvm::LoadInst::getPointerOperand(), llvm::Value::getType(), llvm::MemDepResult::isClobber(), llvm::MemDepResult::isDef(), llvm::MemDepResult::isNonLocal(), llvm::Type::isPtrOrPtrVectorTy(), llvm::LoadInst::isUnordered(), LLVM_DEBUG, llvm::gvn::AvailableValue::MaterializeAdjustedValue(), llvm::patchReplacementInstruction(), llvm::Value::printAsOperand(), llvm::Value::replaceAllUsesWith(), reportLoadElim(), and llvm::Value::use_empty().

Referenced by isOnlyReachableViaThisEdge().

reportLoadElim()

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

static

Definition at line 1288 of file GVN.cpp.

References assert(), llvm::Intrinsic::assume, ConstructSSAForLoadSet(), llvm::dbgs(), DEBUG_TYPE, llvm::dyn_cast(), llvm::OptimizationRemarkEmitter::emit(), EnableLoadPRE, EnablePRE, GEP, llvm::UndefValue::get(), llvm::CallBase::getArgOperand(), llvm::Instruction::getDebugLoc(), llvm::Type::getInt8Ty(), llvm::IntrinsicInst::getIntrinsicID(), llvm::Constant::getNullValue(), llvm::User::getOperand(), llvm::Instruction::getParent(), llvm::BasicBlock::getParent(), llvm::Type::getPointerTo(), llvm::ConstantInt::getTrue(), llvm::Value::getType(), llvm::Function::hasFnAttribute(), llvm::Type::isPtrOrPtrVectorTy(), LLVM_DEBUG, MaxNumDeps, llvm::Value::printAsOperand(), llvm::Value::replaceAllUsesWith(), llvm::Attribute::SanitizeAddress, llvm::Attribute::SanitizeHWAddress, llvm::Instruction::setDebugLoc(), llvm::Successor, llvm::successors(), std::swap(), and llvm::Value::takeName().

Referenced by patchAndReplaceAllUsesWith().

reportMayClobberedLoad()

static void reportMayClobberedLoad ( LoadInst *  LI, 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 843 of file GVN.cpp.

References llvm::Address, llvm::VNCoercion::analyzeLoadFromClobberingLoad(), llvm::VNCoercion::analyzeLoadFromClobberingMemInst(), llvm::VNCoercion::analyzeLoadFromClobberingStore(), assert(), llvm::SmallVectorTemplateCommon< T >::back(), llvm::VNCoercion::canCoerceMustAliasedValueToLoad(), ConstructSSAForLoadSet(), llvm::MapVector< KeyT, ValueT, MapType, VectorType >::count(), llvm::dbgs(), DEBUG_TYPE, llvm::DominatorTree::dominates(), llvm::OptimizationRemarkEmitter::emit(), llvm::SmallVectorBase::empty(), llvm::gvn::AvailableValue::get(), llvm::gvn::AvailableValueInBlock::get(), llvm::UndefValue::get(), llvm::Instruction::getAAMetadata(), llvm::LoadInst::getAlignment(), llvm::Module::getDataLayout(), llvm::Instruction::getDebugLoc(), llvm::MemDepResult::getInst(), llvm::gvn::AvailableValue::getLoad(), llvm::Instruction::getMetadata(), llvm::gvn::AvailableValue::getMI(), llvm::Instruction::getModule(), llvm::Value::getName(), llvm::Constant::getNullValue(), llvm::Instruction::getNumSuccessors(), llvm::LoadInst::getOrdering(), llvm::Instruction::getParent(), llvm::LoadInst::getPointerOperand(), llvm::BasicBlock::getSinglePredecessor(), llvm::LoadInst::getSyncScopeID(), llvm::BasicBlock::getTerminator(), llvm::Value::getType(), llvm::gvn::AvailableValueInBlock::getUndef(), llvm::Instruction::isAtomic(), llvm::isCallocLikeFn(), llvm::MemDepResult::isClobber(), llvm::MemDepResult::isDef(), isLifetimeStart(), llvm::isMallocLikeFn(), llvm::Type::isPtrOrPtrVectorTy(), llvm::isSafeToSpeculativelyExecute(), llvm::LoadInst::isUnordered(), IsValueFullyAvailableInBlock(), llvm::LoadInst::isVolatile(), llvm::ARM_MB::LD, LLVM_DEBUG, llvm::LLVMContext::MD_invariant_group, llvm::LLVMContext::MD_invariant_load, llvm::LLVMContext::MD_range, llvm::SmallVectorImpl< T >::pop_back_val(), llvm::predecessors(), llvm::Value::printAsOperand(), llvm::SmallVectorTemplateBase< T >::push_back(), llvm::Value::replaceAllUsesWith(), llvm::Instruction::setDebugLoc(), llvm::SmallVectorBase::size(), llvm::MapVector< KeyT, ValueT, MapType, VectorType >::size(), llvm::Value::takeName(), and llvm::Value::users().

STATISTIC() [1/7]

STATISTIC	(	NumGVNInstr	,
		"Number of instructions deleted"
	)

STATISTIC() [2/7]

STATISTIC	(	NumGVNLoad	,
		"Number of loads deleted"
	)

STATISTIC() [3/7]

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

STATISTIC() [4/7]

STATISTIC	(	NumGVNBlocks	,
		"Number of blocks merged"
	)

STATISTIC() [5/7]

STATISTIC	(	NumGVNSimpl	,
		"Number of instructions simplified"
	)

STATISTIC() [6/7]

STATISTIC	(	NumGVNEqProp	,
		"Number of equalities propagated"
	)

STATISTIC() [7/7]

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

Variable Documentation

EnableLoadPRE

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

static

Referenced by reportLoadElim().

EnableMemDep

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

static

EnablePRE

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

static

Referenced by isOnlyReachableViaThisEdge(), and reportLoadElim().

MaxNumDeps

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

static

Referenced by reportLoadElim().

MaxRecurseDepth

cl::opt<uint32_t> MaxRecurseDepth("gvn-max-recurse-depth", cl::Hidden, cl::init(1000), cl::ZeroOrMore, cl::desc("Max recurse depth in GVN (default = 1000)"))

static

Referenced by IsValueFullyAvailableInBlock().