LLVM  6.0.0svn
Classes | Namespaces | Macros | Functions | Variables
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/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/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
 Compute iterated dominance frontiers using a linear time algorithm.
 

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 ValueConstructSSAForLoadSet (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 patchReplacementInstruction (Instruction *I, Value *Repl)
 
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< boolEnablePRE ("enable-pre", cl::init(true), cl::Hidden)
 
static cl::opt< boolEnableLoadPRE ("enable-load-pre", cl::init(true))
 
static cl::opt< uint32_tMaxRecurseDepth ("max-recurse-depth", cl::Hidden, cl::init(1000), cl::ZeroOrMore, cl::desc("Max recurse depth (default = 1000)"))
 

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "gvn"

Definition at line 85 of file GVN.cpp.

Referenced by reportLoadElim(), and reportMayClobberedLoad().

Function Documentation

◆ ConstructSSAForLoadSet()

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

◆ isLifetimeStart()

static bool isLifetimeStart ( const Instruction Inst)
static

Definition at line 821 of file GVN.cpp.

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

References llvm::PHINode::addIncoming(), llvm::any_of(), assert(), B, llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::begin(), llvm::SmallVectorTemplateCommon< T >::begin(), llvm::BasicBlock::begin(), llvm::Function::begin(), llvm::Instruction::clone(), llvm::PHINode::Create(), D, llvm::dbgs(), DEBUG, llvm::Value::deleteValue(), llvm::depth_first(), llvm::dyn_cast(), E, llvm::SmallVectorBase::empty(), EnablePRE, llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::end(), llvm::SmallVectorTemplateCommon< T >::end(), 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::UndefValue::get(), llvm::PHINode::getBasicBlockIndex(), llvm::BranchInst::getCondition(), 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::BranchInst::getSuccessor(), llvm::GetSuccessorNumber(), llvm::BasicBlock::getTerminator(), llvm::ConstantInt::getTrue(), llvm::Value::getType(), llvm::ConstantInt::getZExtValue(), llvm::Value::hasOneUse(), I, llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_NE, llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::insert(), llvm::SmallVectorImpl< T >::insert(), llvm::Instruction::insertBefore(), llvm::isCriticalEdge(), llvm::isInstructionTriviallyDead(), llvm::Type::isIntegerTy(), llvm::ConstantInt::isMinusOne(), llvm::Type::isPtrOrPtrVectorTy(), llvm::BranchInst::isUnconditional(), llvm::Type::isVoidTy(), isZero(), 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::SmallVectorImpl< T >::pop_back_val(), llvm::pred_begin(), llvm::pred_end(), llvm::predecessors(), llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back(), llvm::Value::replaceAllUsesWith(), llvm::replaceDominatedUsesWith(), second, llvm::Instruction::setDebugLoc(), llvm::PHINode::setIncomingValue(), llvm::Value::setName(), llvm::User::setOperand(), SI, llvm::SimplifyInstruction(), llvm::SmallVectorTemplateCommon< T >::size(), llvm::SplitCriticalEdge(), llvm::success, llvm::successors(), 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 670 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, isPodLike< T >::value >::push_back(), llvm::succ_begin(), and llvm::succ_end().

Referenced by reportMayClobberedLoad().

◆ patchAndReplaceAllUsesWith()

static void patchAndReplaceAllUsesWith ( Instruction I,
Value Repl 
)
static

◆ patchReplacementInstruction()

static void patchReplacementInstruction ( Instruction I,
Value Repl 
)
static

◆ reportLoadElim()

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

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

References llvm::dwarf::syntax::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, DEBUG_TYPE, llvm::DominatorTree::dominates(), llvm::OptimizationRemarkEmitter::emit(), llvm::SmallVectorBase::empty(), llvm::Instruction::eraseFromParent(), 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::TerminatorInst::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::LoadInst::isUnordered(), IsValueFullyAvailableInBlock(), llvm::LoadInst::isVolatile(), llvm::ARM_MB::LD, 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, isPodLike< T >::value >::push_back(), llvm::Value::replaceAllUsesWith(), llvm::Instruction::setDebugLoc(), llvm::MapVector< KeyT, ValueT, MapType, VectorType >::size(), llvm::SmallVectorTemplateCommon< T >::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().

◆ EnablePRE

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

◆ MaxRecurseDepth

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