class SampleProfileLoaderBaseImpl

Declaration

template <typename BT>
class SampleProfileLoaderBaseImpl { /* full declaration omitted */ };

Declared at: llvm/include/llvm/Transforms/Utils/SampleProfileLoaderBaseImpl.h:81

Templates

BT

Member Variables

protected DenseMap<const llvm::DILocation*, const llvm::sampleprof::FunctionSamples*> DILocation2SampleMap

protected llvm::SampleProfileLoaderBaseImpl::BlockWeightMap BlockWeights

The weight of a basic block is defined to be the maximum of all the instruction weights in that block.

protected llvm::SampleProfileLoaderBaseImpl::EdgeWeightMap EdgeWeights

Edge weights are computed by propagating basic block weights in SampleProfile::propagateWeights.

protected SmallPtrSet< const llvm::SampleProfileLoaderBaseImpl:: BasicBlockT*, 32> VisitedBlocks

Set of visited blocks during propagation.

protected SmallSet<llvm::SampleProfileLoaderBaseImpl::Edge, 32> VisitedEdges

Set of visited edges during propagation.

protected llvm::SampleProfileLoaderBaseImpl:: EquivalenceClassMap EquivalenceClass

Two blocks BB1 and BB2 are in the same equivalence class if they dominate and post-dominate each other, and they are in the same loop nest. When this happens, the two blocks are guaranteed to execute the same number of times.

protected llvm::SampleProfileLoaderBaseImpl:: DominatorTreePtrT DT

Dominance, post-dominance and loop information.

protected llvm::SampleProfileLoaderBaseImpl:: PostDominatorTreePtrT PDT

protected llvm::SampleProfileLoaderBaseImpl::LoopInfoPtrT LI

protected llvm::SampleProfileLoaderBaseImpl::BlockEdgeMap Predecessors

Predecessors for each basic block in the CFG.

protected llvm::SampleProfileLoaderBaseImpl::BlockEdgeMap Successors

Successors for each basic block in the CFG.

protected llvm::sampleprofutil::SampleCoverageTracker CoverageTracker

Profile coverage tracker.

protected std::unique_ptr<SampleProfileReader> Reader

Profile reader object.

protected llvm::sampleprof::FunctionSamples* Samples = nullptr

Samples collected for the body of this function.

protected std::string Filename

Name of the profile file to load.

protected std::string RemappingFilename

Name of the profile remapping file to load.

protected llvm::ProfileSummaryInfo* PSI = nullptr

Profile Summary Info computed from sample profile.

protected llvm::SampleProfileLoaderBaseImpl:: OptRemarkEmitterT* ORE = nullptr

Optimization Remark Emitter used to emit diagnostic remarks.

Method Overview

• public SampleProfileLoaderBaseImpl<BT>(std::string Name, std::string RemapName)
• protected void applyProfi(llvm::SampleProfileLoaderBaseImpl::FunctionT & F, llvm::SampleProfileLoaderBaseImpl::BlockEdgeMap & Successors, llvm::SampleProfileLoaderBaseImpl::BlockWeightMap & SampleBlockWeights, llvm::SampleProfileLoaderBaseImpl::BlockWeightMap & BlockWeights, llvm::SampleProfileLoaderBaseImpl::EdgeWeightMap & EdgeWeights)
• protected void buildEdges(llvm::SampleProfileLoaderBaseImpl::FunctionT & F)
• protected void clearFunctionData(bool ResetDT = true)
• protected bool computeAndPropagateWeights(llvm::SampleProfileLoaderBaseImpl::FunctionT & F, const DenseSet<GlobalValue::GUID> & InlinedGUIDs)
• protected bool computeBlockWeights(llvm::SampleProfileLoaderBaseImpl::FunctionT & F)
• protected void computeDominanceAndLoopInfo(llvm::SampleProfileLoaderBaseImpl::FunctionT & F)
• public void dump()
• protected void emitCoverageRemarks(llvm::SampleProfileLoaderBaseImpl::FunctionT & F)
• protected void finalizeWeightPropagation(llvm::SampleProfileLoaderBaseImpl::FunctionT & F, const DenseSet<GlobalValue::GUID> & InlinedGUIDs)
• protected void findEquivalenceClasses(llvm::SampleProfileLoaderBaseImpl::FunctionT & F)
• protected void findEquivalencesFor(llvm::SampleProfileLoaderBaseImpl::BasicBlockT * BB1, ArrayRef<llvm::SampleProfileLoaderBaseImpl::BasicBlockT *> Descendants, llvm::SampleProfileLoaderBaseImpl::PostDominatorTreeT * DomTree)
• protected virtual const llvm::sampleprof::FunctionSamples * findFunctionSamples(const llvm::SampleProfileLoaderBaseImpl::InstructionT & I) const
• protected ErrorOr<uint64_t> getBlockWeight(const llvm::SampleProfileLoaderBaseImpl::BasicBlockT * BB)
• protected const llvm::SampleProfileLoaderBaseImpl::BasicBlockT * getEntryBB(const llvm::SampleProfileLoaderBaseImpl::FunctionT * F)
• protected llvm::Function & getFunction(llvm::SampleProfileLoaderBaseImpl::FunctionT & F)
• protected unsigned int getFunctionLoc(llvm::SampleProfileLoaderBaseImpl::FunctionT & Func)
• protected virtual ErrorOr<uint64_t> getInstWeight(const llvm::SampleProfileLoaderBaseImpl::InstructionT & Inst)
• protected ErrorOr<uint64_t> getInstWeightImpl(const llvm::SampleProfileLoaderBaseImpl::InstructionT & Inst)
• protected llvm::SampleProfileLoaderBaseImpl::PredRangeT getPredecessors(llvm::SampleProfileLoaderBaseImpl::BasicBlockT * BB)
• protected llvm::SampleProfileLoaderBaseImpl::SuccRangeT getSuccessors(llvm::SampleProfileLoaderBaseImpl::BasicBlockT * BB)
• protected void initWeightPropagation(llvm::SampleProfileLoaderBaseImpl::FunctionT & F, const DenseSet<GlobalValue::GUID> & InlinedGUIDs)
• protected void printBlockEquivalence(llvm::raw_ostream & OS, const llvm::SampleProfileLoaderBaseImpl::BasicBlockT * BB)
• protected void printBlockWeight(llvm::raw_ostream & OS, const llvm::SampleProfileLoaderBaseImpl::BasicBlockT * BB) const
• protected void printEdgeWeight(llvm::raw_ostream & OS, llvm::SampleProfileLoaderBaseImpl::Edge E)
• protected bool propagateThroughEdges(llvm::SampleProfileLoaderBaseImpl::FunctionT & F, bool UpdateBlockCount)
• protected void propagateWeights(llvm::SampleProfileLoaderBaseImpl::FunctionT & F)
• protected uint64_t visitEdge(llvm::SampleProfileLoaderBaseImpl::Edge E, unsigned int * NumUnknownEdges, llvm::SampleProfileLoaderBaseImpl::Edge * UnknownEdge)
• protected ~SampleProfileLoaderBaseImpl<BT>()

Methods

¶SampleProfileLoaderBaseImpl<BT>(
    std::string Name,
    std::string RemapName)

Declared at: llvm/include/llvm/Transforms/Utils/SampleProfileLoaderBaseImpl.h:83

Parameters

std::string Name

std::string RemapName

¶void applyProfi(
    llvm::SampleProfileLoaderBaseImpl::FunctionT&
        F,
    llvm::SampleProfileLoaderBaseImpl::
        BlockEdgeMap& Successors,
    llvm::SampleProfileLoaderBaseImpl::
        BlockWeightMap& SampleBlockWeights,
    llvm::SampleProfileLoaderBaseImpl::
        BlockWeightMap& BlockWeights,
    llvm::SampleProfileLoaderBaseImpl::
        EdgeWeightMap& EdgeWeights)

Declared at: llvm/include/llvm/Transforms/Utils/SampleProfileLoaderBaseImpl.h:149

Parameters

llvm::SampleProfileLoaderBaseImpl::FunctionT& F

llvm::SampleProfileLoaderBaseImpl::BlockEdgeMap& Successors

llvm::SampleProfileLoaderBaseImpl::BlockWeightMap& SampleBlockWeights

llvm::SampleProfileLoaderBaseImpl::BlockWeightMap& BlockWeights

llvm::SampleProfileLoaderBaseImpl::EdgeWeightMap& EdgeWeights

¶void buildEdges(
    llvm::SampleProfileLoaderBaseImpl::FunctionT&
        F)

Description

Build in/out edge lists for each basic block in the CFG. We are interested in unique edges. If a block B1 has multiple edges to another block B2, we only add a single B1->B2 edge.

Declared at: llvm/include/llvm/Transforms/Utils/SampleProfileLoaderBaseImpl.h:153

Parameters

llvm::SampleProfileLoaderBaseImpl::FunctionT& F

¶void clearFunctionData(bool ResetDT = true)

Description

Clear all the per-function data used to load samples and propagate weights.

Declared at: llvm/include/llvm/Transforms/Utils/SampleProfileLoaderBaseImpl.h:155

Parameters

bool ResetDT = true

¶bool computeAndPropagateWeights(
    llvm::SampleProfileLoaderBaseImpl::FunctionT&
        F,
    const DenseSet<GlobalValue::GUID>&
        InlinedGUIDs)

Description

Generate branch weight metadata for all branches in \p F. Branch weights are computed out of instruction samples using a propagation heuristic. Propagation proceeds in 3 phases: 1- Assignment of block weights. All the basic blocks in the function are initial assigned the same weight as their most frequently executed instruction. 2- Creation of equivalence classes. Since samples may be missing from blocks, we can fill in the gaps by setting the weights of all the blocks in the same equivalence class to the same weight. To compute the concept of equivalence, we use dominance and loop information. Two blocks B1 and B2 are in the same equivalence class if B1 dominates B2, B2 post-dominates B1 and both are in the same loop. 3- Propagation of block weights into edges. This uses a simple propagation heuristic. The following rules are applied to every block BB in the CFG: - If BB has a single predecessor/successor, then the weight of that edge is the weight of the block. - If all the edges are known except one, and the weight of the block is already known, the weight of the unknown edge will be the weight of the block minus the sum of all the known edges. If the sum of all the known edges is larger than BB's weight, we set the unknown edge weight to zero. - If there is a self-referential edge, and the weight of the block is known, the weight for that edge is set to the weight of the block minus the weight of the other incoming edges to that block (if known). Since this propagation is not guaranteed to finalize for every CFG, we only allow it to proceed for a limited number of iterations (controlled by -sample-profile-max-propagate-iterations). FIXME: Try to replace this propagation heuristic with a scheme that is guaranteed to finalize. A work-list approach similar to the standard value propagation algorithm used by SSA-CCP might work here.

Declared at: llvm/include/llvm/Transforms/Utils/SampleProfileLoaderBaseImpl.h:158

Parameters

llvm::SampleProfileLoaderBaseImpl::FunctionT& F

The function to query.

const DenseSet<GlobalValue::GUID>& InlinedGUIDs

Returns

true if \p F was modified. Returns false, otherwise.

¶bool computeBlockWeights(
    llvm::SampleProfileLoaderBaseImpl::FunctionT&
        F)

Description

Compute and store the weights of every basic block. This populates the BlockWeights map by computing the weights of every basic block in the CFG.

Declared at: llvm/include/llvm/Transforms/Utils/SampleProfileLoaderBaseImpl.h:143

Parameters

llvm::SampleProfileLoaderBaseImpl::FunctionT& F

The function to query.

¶void computeDominanceAndLoopInfo(
    llvm::SampleProfileLoaderBaseImpl::FunctionT&
        F)

Declared at: llvm/include/llvm/Transforms/Utils/SampleProfileLoaderBaseImpl.h:156

Parameters

llvm::SampleProfileLoaderBaseImpl::FunctionT& F

¶void dump()

Declared at: llvm/include/llvm/Transforms/Utils/SampleProfileLoaderBaseImpl.h:85

¶void emitCoverageRemarks(
    llvm::SampleProfileLoaderBaseImpl::FunctionT&
        F)

Declared at: llvm/include/llvm/Transforms/Utils/SampleProfileLoaderBaseImpl.h:165

Parameters

llvm::SampleProfileLoaderBaseImpl::FunctionT& F

¶void finalizeWeightPropagation(
    llvm::SampleProfileLoaderBaseImpl::FunctionT&
        F,
    const DenseSet<GlobalValue::GUID>&
        InlinedGUIDs)

Declared at: llvm/include/llvm/Transforms/Utils/SampleProfileLoaderBaseImpl.h:163

Parameters

llvm::SampleProfileLoaderBaseImpl::FunctionT& F

const DenseSet<GlobalValue::GUID>& InlinedGUIDs

¶void findEquivalenceClasses(
    llvm::SampleProfileLoaderBaseImpl::FunctionT&
        F)

Description

Find equivalence classes. Since samples may be missing from blocks, we can fill in the gaps by setting the weights of all the blocks in the same equivalence class to the same weight. To compute the concept of equivalence, we use dominance and loop information. Two blocks B1 and B2 are in the same equivalence class if B1 dominates B2, B2 post-dominates B1 and both are in the same loop.

Declared at: llvm/include/llvm/Transforms/Utils/SampleProfileLoaderBaseImpl.h:144

Parameters

llvm::SampleProfileLoaderBaseImpl::FunctionT& F

The function to query.

¶void findEquivalencesFor(
    llvm::SampleProfileLoaderBaseImpl::
        BasicBlockT* BB1,
    ArrayRef<llvm::SampleProfileLoaderBaseImpl::
                 BasicBlockT*> Descendants,
    llvm::SampleProfileLoaderBaseImpl::
        PostDominatorTreeT* DomTree)

Description

Find equivalence classes for the given block. This finds all the blocks that are guaranteed to execute the same number of times as \p BB1. To do this, it traverses all the descendants of \p BB1 in the dominator or post-dominator tree. A block BB2 will be in the same equivalence class as \p BB1 if the following holds: 1- \p BB1 is a descendant of BB2 in the opposite tree. So, if BB2 is a descendant of \p BB1 in the dominator tree, then BB2 should dominate BB1 in the post-dominator tree. 2- Both BB2 and \p BB1 must be in the same loop. For every block BB2 that meets those two requirements, we set BB2's equivalence class to \p BB1.

Declared at: llvm/include/llvm/Transforms/Utils/SampleProfileLoaderBaseImpl.h:145

Parameters

llvm::SampleProfileLoaderBaseImpl::BasicBlockT* BB1

Block to check.

ArrayRef<llvm::SampleProfileLoaderBaseImpl:: BasicBlockT*> Descendants

Descendants of \p BB1 in either the dom or pdom tree.

llvm::SampleProfileLoaderBaseImpl:: PostDominatorTreeT* DomTree

Opposite dominator tree. If \p Descendants is filled with blocks from \p BB1's dominator tree, then this is the post-dominator tree, and vice versa.

¶virtual const llvm::sampleprof::FunctionSamples*
findFunctionSamples(
    const llvm::SampleProfileLoaderBaseImpl::
        InstructionT& I) const

Description

Get the FunctionSamples for an instruction. The FunctionSamples of an instruction \p Inst is the inlined instance in which that instruction is coming from. We traverse the inline stack of that instruction, and match it with the tree nodes in the profile.

Declared at: llvm/include/llvm/Transforms/Utils/SampleProfileLoaderBaseImpl.h:139

Parameters

const llvm::SampleProfileLoaderBaseImpl:: InstructionT& I

Returns

the FunctionSamples pointer to the inlined instance.

¶ErrorOr<uint64_t> getBlockWeight(
    const llvm::SampleProfileLoaderBaseImpl::
        BasicBlockT* BB)

Description

Compute the weight of a basic block. The weight of basic block \p BB is the maximum weight of all the instructions in BB.

Declared at: llvm/include/llvm/Transforms/Utils/SampleProfileLoaderBaseImpl.h:135

Parameters

const llvm::SampleProfileLoaderBaseImpl:: BasicBlockT* BB

The basic block to query.

Returns

the weight for \p BB.

¶const llvm::SampleProfileLoaderBaseImpl::
    BasicBlockT*
    getEntryBB(
        const llvm::SampleProfileLoaderBaseImpl::
            FunctionT* F)

Declared at: llvm/include/llvm/Transforms/Utils/SampleProfileLoaderBaseImpl.h:122

Parameters

const llvm::SampleProfileLoaderBaseImpl:: FunctionT* F

¶llvm::Function& getFunction(
    llvm::SampleProfileLoaderBaseImpl::FunctionT&
        F)

Declared at: llvm/include/llvm/Transforms/Utils/SampleProfileLoaderBaseImpl.h:119

Parameters

llvm::SampleProfileLoaderBaseImpl::FunctionT& F

¶unsigned int getFunctionLoc(
    llvm::SampleProfileLoaderBaseImpl::FunctionT&
        Func)

Description

Get the line number for the function header. This looks up function \p F in the current compilation unit and retrieves the line number where the function is defined. This is line 0 for all the samples read from the profile file. Every line number is relative to this line.

Declared at: llvm/include/llvm/Transforms/Utils/SampleProfileLoaderBaseImpl.h:132

Parameters

llvm::SampleProfileLoaderBaseImpl::FunctionT& Func

Returns

the line number where \p F is defined. If it returns 0, it means that there is no debug information available for \p F.

¶virtual ErrorOr<uint64_t> getInstWeight(
    const llvm::SampleProfileLoaderBaseImpl::
        InstructionT& Inst)

Description

Get the weight for an instruction. The "weight" of an instruction \p Inst is the number of samples collected on that instruction at runtime. To retrieve it, we need to compute the line number of \p Inst relative to the start of its function. We use HeaderLineno to compute the offset. We then look up the samples collected for \p Inst using BodySamples.

Declared at: llvm/include/llvm/Transforms/Utils/SampleProfileLoaderBaseImpl.h:133

Parameters

const llvm::SampleProfileLoaderBaseImpl:: InstructionT& Inst

Instruction to query.

Returns

the weight of \p Inst.

¶ErrorOr<uint64_t> getInstWeightImpl(
    const llvm::SampleProfileLoaderBaseImpl::
        InstructionT& Inst)

Declared at: llvm/include/llvm/Transforms/Utils/SampleProfileLoaderBaseImpl.h:134

Parameters

const llvm::SampleProfileLoaderBaseImpl:: InstructionT& Inst

¶llvm::SampleProfileLoaderBaseImpl::PredRangeT
getPredecessors(
    llvm::SampleProfileLoaderBaseImpl::
        BasicBlockT* BB)

Declared at: llvm/include/llvm/Transforms/Utils/SampleProfileLoaderBaseImpl.h:125

Parameters

llvm::SampleProfileLoaderBaseImpl::BasicBlockT* BB

¶llvm::SampleProfileLoaderBaseImpl::SuccRangeT
getSuccessors(llvm::SampleProfileLoaderBaseImpl::
                  BasicBlockT* BB)

Declared at: llvm/include/llvm/Transforms/Utils/SampleProfileLoaderBaseImpl.h:128

Parameters

llvm::SampleProfileLoaderBaseImpl::BasicBlockT* BB

¶void initWeightPropagation(
    llvm::SampleProfileLoaderBaseImpl::FunctionT&
        F,
    const DenseSet<GlobalValue::GUID>&
        InlinedGUIDs)

Declared at: llvm/include/llvm/Transforms/Utils/SampleProfileLoaderBaseImpl.h:160

Parameters

llvm::SampleProfileLoaderBaseImpl::FunctionT& F

const DenseSet<GlobalValue::GUID>& InlinedGUIDs

¶void printBlockEquivalence(
    llvm::raw_ostream& OS,
    const llvm::SampleProfileLoaderBaseImpl::
        BasicBlockT* BB)

Description

Print the equivalence class of block \p BB on stream \p OS.

Declared at: llvm/include/llvm/Transforms/Utils/SampleProfileLoaderBaseImpl.h:142

Parameters

llvm::raw_ostream& OS

Stream to emit the output to.

const llvm::SampleProfileLoaderBaseImpl:: BasicBlockT* BB

Block to print.

¶void printBlockWeight(
    llvm::raw_ostream& OS,
    const llvm::SampleProfileLoaderBaseImpl::
        BasicBlockT* BB) const

Description

Print the weight of block \p BB on stream \p OS.

Declared at: llvm/include/llvm/Transforms/Utils/SampleProfileLoaderBaseImpl.h:141

Parameters

llvm::raw_ostream& OS

Stream to emit the output to.

const llvm::SampleProfileLoaderBaseImpl:: BasicBlockT* BB

Block to print.

¶void printEdgeWeight(
    llvm::raw_ostream& OS,
    llvm::SampleProfileLoaderBaseImpl::Edge E)

Description

Print the weight of edge \p E on stream \p OS.

Declared at: llvm/include/llvm/Transforms/Utils/SampleProfileLoaderBaseImpl.h:140

Parameters

llvm::raw_ostream& OS

Stream to emit the output to.

llvm::SampleProfileLoaderBaseImpl::Edge E

Edge to print.

¶bool propagateThroughEdges(
    llvm::SampleProfileLoaderBaseImpl::FunctionT&
        F,
    bool UpdateBlockCount)

Description

Propagate weights through incoming/outgoing edges. If the weight of a basic block is known, and there is only one edge with an unknown weight, we can calculate the weight of that edge. Similarly, if all the edges have a known count, we can calculate the count of the basic block, if needed.

Declared at: llvm/include/llvm/Transforms/Utils/SampleProfileLoaderBaseImpl.h:154

Parameters

llvm::SampleProfileLoaderBaseImpl::FunctionT& F

Function to process.

bool UpdateBlockCount

Whether we should update basic block counts that has already been annotated.

Returns

True if new weights were assigned to edges or blocks.

¶void propagateWeights(
    llvm::SampleProfileLoaderBaseImpl::FunctionT&
        F)

Description

Propagate weights into edges The following rules are applied to every block BB in the CFG: - If BB has a single predecessor/successor, then the weight of that edge is the weight of the block. - If all incoming or outgoing edges are known except one, and the weight of the block is already known, the weight of the unknown edge will be the weight of the block minus the sum of all the known edges. If the sum of all the known edges is larger than BB's weight, we set the unknown edge weight to zero. - If there is a self-referential edge, and the weight of the block is known, the weight for that edge is set to the weight of the block minus the weight of the other incoming edges to that block (if known).

Declared at: llvm/include/llvm/Transforms/Utils/SampleProfileLoaderBaseImpl.h:148

Parameters

llvm::SampleProfileLoaderBaseImpl::FunctionT& F

¶uint64_t visitEdge(
    llvm::SampleProfileLoaderBaseImpl::Edge E,
    unsigned int* NumUnknownEdges,
    llvm::SampleProfileLoaderBaseImpl::Edge*
        UnknownEdge)

Description

Visit the given edge to decide if it has a valid weight. If \p E has not been visited before, we copy to \p UnknownEdge and increment the count of unknown edges.

Declared at: llvm/include/llvm/Transforms/Utils/SampleProfileLoaderBaseImpl.h:152

Parameters

llvm::SampleProfileLoaderBaseImpl::Edge E

Edge to visit.

unsigned int* NumUnknownEdges

Current number of unknown edges.

llvm::SampleProfileLoaderBaseImpl::Edge* UnknownEdge

Set if E has not been visited before.

Returns

E's weight, if known. Otherwise, return 0.

¶~SampleProfileLoaderBaseImpl<BT>()

Declared at: llvm/include/llvm/Transforms/Utils/SampleProfileLoaderBaseImpl.h:116