LLVM
15.0.0git
|
#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)")) |
|
strong |
|
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().
|
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().
|
static |
Definition at line 1881 of file GVN.cpp.
References BB, getParent(), and llvm::Value::users().
|
static |
|
static |
|
static |
Definition at line 1023 of file GVN.cpp.
Referenced by sinkLifetimeStartMarkers().
|
static |
|
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.
|
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().
|
static |
Definition at line 2026 of file GVN.cpp.
References I, and llvm::patchReplacementInstruction().
|
static |
Definition at line 1726 of file GVN.cpp.
References DEBUG_TYPE, llvm::OptimizationRemarkEmitter::emit(), and llvm::SPII::Load.
|
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 | ( | 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" | |||
) |
STATISTIC | ( | NumGVNBlocks | , |
"Number of blocks merged" | |||
) |
STATISTIC | ( | NumGVNEqProp | , |
"Number of equalities propagated" | |||
) |
STATISTIC | ( | NumGVNInstr | , |
"Number of instructions deleted" | |||
) |
STATISTIC | ( | NumGVNLoad | , |
"Number of loads deleted" | |||
) |
STATISTIC | ( | NumGVNPRE | , |
"Number of instructions PRE'd" | |||
) |
STATISTIC | ( | NumGVNSimpl | , |
"Number of instructions simplified" | |||
) |
|
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:
Address
) must be defined in DepBB
.End
that may clobber the loads. Referenced by llvm::GVNPass::isLoadInLoopPREEnabled().
Referenced by llvm::GVNPass::isLoadPREEnabled().
Referenced by llvm::GVNPass::isMemDepEnabled().
Referenced by llvm::GVNPass::isPREEnabled().
|
static |
Referenced by llvm::GVNPass::isLoadPRESplitBackedgeEnabled().
|
static |
Referenced by IsValueFullyAvailableInBlock().