class DivergenceAnalysisImpl

Declaration

class DivergenceAnalysisImpl { /* full declaration omitted */ };

Description

Generic divergence analysis for reducible CFGs.

This analysis propagates divergence in a data-parallel context from sources of divergence to all users. It requires reducible CFGs. All assignments should be in SSA form.

Declared at: llvm/include/llvm/Analysis/DivergenceAnalysis.h:36

Member Variables

private const llvm::Function& F
private const llvm::Loop* RegionLoop
private const llvm::DominatorTree& DT
private const llvm::LoopInfo& LI
private DenseSet<const llvm::Loop*> DivergentLoops
private llvm::SyncDependenceAnalysis& SDA
private bool IsLCSSAForm
private DenseSet<const llvm::Value*> UniformOverrides
private DenseSet<const llvm::Value*> DivergentValues
private std::vector<const Instruction*> Worklist

Method Overview

Methods

DivergenceAnalysisImpl(
    const llvm::Function& F,
    const llvm::Loop* RegionLoop,
    const llvm::DominatorTree& DT,
    const llvm::LoopInfo& LI,
    llvm::SyncDependenceAnalysis& SDA,
    bool IsLCSSAForm)

Description

This instance will analyze the whole function \p F or the loop \p RegionLoop.

Declared at: llvm/include/llvm/Analysis/DivergenceAnalysis.h:45

Parameters

const llvm::Function& F
const llvm::Loop* RegionLoop
if non-null the analysis is restricted to \p RegionLoop. Otherwise the whole function is analyzed.
const llvm::DominatorTree& DT
const llvm::LoopInfo& LI
llvm::SyncDependenceAnalysis& SDA
bool IsLCSSAForm
whether the analysis may assume that the IR in the region in LCSSA form.

void addUniformOverride(const llvm::Value& UniVal)

Description

Mark \p UniVal as a value that is always uniform.

Declared at: llvm/include/llvm/Analysis/DivergenceAnalysis.h:59

Parameters

const llvm::Value& UniVal

void analyzeControlDivergence(
    const llvm::Instruction& Term)

Description

Mark \p Term as divergent and push all Instructions that become divergent as a result on the worklist.

Declared at: llvm/include/llvm/Analysis/DivergenceAnalysis.h:87

Parameters

const llvm::Instruction& Term

void analyzeLoopExitDivergence(
    const llvm::BasicBlock& DivExit,
    const llvm::Loop& OuterDivLoop)

Description

Internal implementation function for propagateLoopExitDivergence.

Declared at: llvm/include/llvm/Analysis/DivergenceAnalysis.h:99

Parameters

const llvm::BasicBlock& DivExit
const llvm::Loop& OuterDivLoop

void analyzeTemporalDivergence(
    const llvm::Instruction& I,
    const llvm::Loop& OuterDivLoop)

Description

Mark all instruction as divergent that use a value defined in \p OuterDivLoop. Push their users on the worklist.

Declared at: llvm/include/llvm/Analysis/DivergenceAnalysis.h:104

Parameters

const llvm::Instruction& I
const llvm::Loop& OuterDivLoop

void compute()

Description

Propagate divergence to all instructions in the region. Divergence is seeded by calls to \p markDivergent.

Declared at: llvm/include/llvm/Analysis/DivergenceAnalysis.h:68

const llvm::Function& getFunction() const

Declared at: llvm/include/llvm/Analysis/DivergenceAnalysis.h:51

const llvm::Loop* getRegionLoop() const

Description

The loop that defines the analyzed region (if any).

Declared at: llvm/include/llvm/Analysis/DivergenceAnalysis.h:50

bool hasDetectedDivergence() const

Description

Whether any value was marked or analyzed to be divergent.

Declared at: llvm/include/llvm/Analysis/DivergenceAnalysis.h:71

bool inRegion(const llvm::BasicBlock& BB) const

Description

Whether \p BB is part of the region.

Declared at: llvm/include/llvm/Analysis/DivergenceAnalysis.h:54

Parameters

const llvm::BasicBlock& BB

bool inRegion(const llvm::Instruction& I) const

Description

Whether \p I is part of the region.

Declared at: llvm/include/llvm/Analysis/DivergenceAnalysis.h:56

Parameters

const llvm::Instruction& I

bool isAlwaysUniform(const llvm::Value& Val) const

Description

Whether \p Val will always return a uniform value regardless of its operands

Declared at: llvm/include/llvm/Analysis/DivergenceAnalysis.h:75

Parameters

const llvm::Value& Val

bool isDivergent(const llvm::Value& Val) const

Description

Whether \p Val is divergent at its definition.

Declared at: llvm/include/llvm/Analysis/DivergenceAnalysis.h:78

Parameters

const llvm::Value& Val

bool isDivergentUse(const llvm::Use& U) const

Description

Whether \p U is divergent. Uses of a uniform value can be divergent.

Declared at: llvm/include/llvm/Analysis/DivergenceAnalysis.h:82

Parameters

const llvm::Use& U

bool isTemporalDivergent(
    const llvm::BasicBlock& ObservingBlock,
    const llvm::Value& Val) const

Description

Whether \p Val is divergent when read in \p ObservingBlock.

Declared at: llvm/include/llvm/Analysis/DivergenceAnalysis.h:111

Parameters

const llvm::BasicBlock& ObservingBlock
const llvm::Value& Val

bool markDivergent(const llvm::Value& DivVal)

Description

Mark \p DivVal as a value that is always divergent. Will not do so if `isAlwaysUniform(DivVal)`.

Declared at: llvm/include/llvm/Analysis/DivergenceAnalysis.h:64

Parameters

const llvm::Value& DivVal

Returns

Whether the tracked divergence state of \p DivVal changed.

void propagateLoopExitDivergence(
    const llvm::BasicBlock& DivExit,
    const llvm::Loop& DivLoop)

Description

Identify all Instructions that become divergent because \p DivExit is a divergent loop exit of \p DivLoop. Mark those instructions as divergent and push them on the worklist.

Declared at: llvm/include/llvm/Analysis/DivergenceAnalysis.h:95

Parameters

const llvm::BasicBlock& DivExit
const llvm::Loop& DivLoop

void pushUsers(const llvm::Value& I)

Description

Push all users of \p Val (in the region) to the worklist.

Declared at: llvm/include/llvm/Analysis/DivergenceAnalysis.h:108

Parameters

const llvm::Value& I

void taintAndPushPhiNodes(
    const llvm::BasicBlock& JoinBlock)

Description

Mark all phi nodes in \p JoinBlock as divergent and push them on the worklist.

Declared at: llvm/include/llvm/Analysis/DivergenceAnalysis.h:90

Parameters

const llvm::BasicBlock& JoinBlock