LLVM  13.0.0git
Classes | Namespaces | Macros | Enumerations | 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/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/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/Config/llvm-config.h"
#include "llvm/IR/Attributes.h"
#include "llvm/IR/BasicBlock.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/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.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>
#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
 

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 (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 ValueConstructSSAForLoadSet (LoadInst *Load, SmallVectorImpl< AvailableValueInBlock > &ValuesPerBlock, GVN &gvn)
 Given a set of loads specified by ValuesPerBlock, construct SSA form, allowing us to eliminate Load. More...
 
static bool isLifetimeStart (const Instruction *Inst)
 
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 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(true))
 
static cl::opt< bool > GVNEnableMemDep ("enable-gvn-memdep", cl::init(true))
 
static cl::opt< uint32_tMaxNumDeps ("gvn-max-num-deps", cl::Hidden, cl::init(100), cl::ZeroOrMore, cl::desc("Max number of dependences to attempt Load PRE (default = 100)"))
 
static cl::opt< uint32_tMaxBBSpeculations ("gvn-max-block-speculations", cl::Hidden, cl::init(600), cl::ZeroOrMore, 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 92 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 699 of file GVN.cpp.

Function Documentation

◆ ConstructSSAForLoadSet()

static Value* ConstructSSAForLoadSet ( LoadInst Load,
SmallVectorImpl< AvailableValueInBlock > &  ValuesPerBlock,
GVN 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 837 of file GVN.cpp.

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

◆ hasUsersIn()

static bool hasUsersIn ( Value V,
BasicBlock BB 
)
static

Definition at line 1603 of file GVN.cpp.

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

◆ impliesEquivalanceIfFalse()

static bool impliesEquivalanceIfFalse ( CmpInst Cmp)
static

Definition at line 1576 of file GVN.cpp.

References isZero().

◆ impliesEquivalanceIfTrue()

static bool impliesEquivalanceIfTrue ( CmpInst Cmp)
static

Definition at line 1550 of file GVN.cpp.

References isZero().

◆ isLifetimeStart()

static bool isLifetimeStart ( const Instruction Inst)
static

Definition at line 927 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 1973 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 719 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, 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.

◆ patchAndReplaceAllUsesWith()

static void patchAndReplaceAllUsesWith ( Instruction I,
Value Repl 
)
static

Definition at line 1748 of file GVN.cpp.

References I, and llvm::patchReplacementInstruction().

◆ reportLoadElim()

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

Definition at line 1450 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 935 of file GVN.cpp.

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

◆ STATISTIC() [1/9]

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

◆ STATISTIC() [2/9]

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

◆ STATISTIC() [3/9]

STATISTIC ( NumGVNBlocks  ,
"Number of blocks merged"   
)

◆ STATISTIC() [4/9]

STATISTIC ( NumGVNEqProp  ,
"Number of equalities propagated"   
)

◆ STATISTIC() [5/9]

STATISTIC ( NumGVNInstr  ,
"Number of instructions deleted"   
)

◆ STATISTIC() [6/9]

STATISTIC ( NumGVNLoad  ,
"Number of loads deleted"   
)

◆ STATISTIC() [7/9]

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

◆ STATISTIC() [8/9]

STATISTIC ( NumGVNSimpl  ,
"Number of instructions simplified"   
)

◆ STATISTIC() [9/9]

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

Variable Documentation

◆ GVNEnableLoadInLoopPRE

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

◆ GVNEnableLoadPRE

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

◆ GVNEnableMemDep

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

◆ GVNEnablePRE

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

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

◆ GVNEnableSplitBackedgeInLoadPRE

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

◆ MaxBBSpeculations

cl::opt<uint32_t> MaxBBSpeculations("gvn-max-block-speculations", cl::Hidden, cl::init(600), cl::ZeroOrMore, 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

◆ 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