blob: 2fac9c8b4b343732402bf71b1aa1f5e5ccefbc5e [file] [log] [blame] [edit]
//===- llvm/Analysis/DivergenceAnalysis.h - Divergence Analysis -*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// \file
// The divergence analysis determines which instructions and branches are
// divergent given a set of divergent source instructions.
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_ANALYSIS_DIVERGENCE_ANALYSIS_H
#define LLVM_ANALYSIS_DIVERGENCE_ANALYSIS_H
#include "llvm/ADT/DenseSet.h"
#include "llvm/Analysis/SyncDependenceAnalysis.h"
#include "llvm/IR/Function.h"
#include "llvm/Pass.h"
#include <vector>
namespace llvm {
class Module;
class Value;
class Instruction;
class Loop;
class raw_ostream;
class TargetTransformInfo;
/// \brief 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.
class DivergenceAnalysis {
public:
/// \brief This instance will analyze the whole function \p F or the loop \p
/// RegionLoop.
///
/// \param RegionLoop if non-null the analysis is restricted to \p RegionLoop.
/// Otherwise the whole function is analyzed.
/// \param IsLCSSAForm whether the analysis may assume that the IR in the
/// region in in LCSSA form.
DivergenceAnalysis(const Function &F, const Loop *RegionLoop,
const DominatorTree &DT, const LoopInfo &LI,
SyncDependenceAnalysis &SDA, bool IsLCSSAForm);
/// \brief The loop that defines the analyzed region (if any).
const Loop *getRegionLoop() const { return RegionLoop; }
const Function &getFunction() const { return F; }
/// \brief Whether \p BB is part of the region.
bool inRegion(const BasicBlock &BB) const;
/// \brief Whether \p I is part of the region.
bool inRegion(const Instruction &I) const;
/// \brief Mark \p UniVal as a value that is always uniform.
void addUniformOverride(const Value &UniVal);
/// \brief Mark \p DivVal as a value that is always divergent.
void markDivergent(const Value &DivVal);
/// \brief Propagate divergence to all instructions in the region.
/// Divergence is seeded by calls to \p markDivergent.
void compute();
/// \brief Whether any value was marked or analyzed to be divergent.
bool hasDetectedDivergence() const { return !DivergentValues.empty(); }
/// \brief Whether \p Val will always return a uniform value regardless of its
/// operands
bool isAlwaysUniform(const Value &Val) const;
/// \brief Whether \p Val is divergent at its definition.
bool isDivergent(const Value &Val) const;
/// \brief Whether \p U is divergent. Uses of a uniform value can be divergent.
bool isDivergentUse(const Use &U) const;
void print(raw_ostream &OS, const Module *) const;
private:
bool updateTerminator(const Instruction &Term) const;
bool updatePHINode(const PHINode &Phi) const;
/// \brief Computes whether \p Inst is divergent based on the
/// divergence of its operands.
///
/// \returns Whether \p Inst is divergent.
///
/// This should only be called for non-phi, non-terminator instructions.
bool updateNormalInstruction(const Instruction &Inst) const;
/// \brief Mark users of live-out users as divergent.
///
/// \param LoopHeader the header of the divergent loop.
///
/// Marks all users of live-out values of the loop headed by \p LoopHeader
/// as divergent and puts them on the worklist.
void taintLoopLiveOuts(const BasicBlock &LoopHeader);
/// \brief Push all users of \p Val (in the region) to the worklist
void pushUsers(const Value &I);
/// \brief Push all phi nodes in @block to the worklist
void pushPHINodes(const BasicBlock &Block);
/// \brief Mark \p Block as join divergent
///
/// A block is join divergent if two threads may reach it from different
/// incoming blocks at the same time.
void markBlockJoinDivergent(const BasicBlock &Block) {
DivergentJoinBlocks.insert(&Block);
}
/// \brief Whether \p Val is divergent when read in \p ObservingBlock.
bool isTemporalDivergent(const BasicBlock &ObservingBlock,
const Value &Val) const;
/// \brief Whether \p Block is join divergent
///
/// (see markBlockJoinDivergent).
bool isJoinDivergent(const BasicBlock &Block) const {
return DivergentJoinBlocks.find(&Block) != DivergentJoinBlocks.end();
}
/// \brief Propagate control-induced divergence to users (phi nodes and
/// instructions).
//
// \param JoinBlock is a divergent loop exit or join point of two disjoint
// paths.
// \returns Whether \p JoinBlock is a divergent loop exit of \p TermLoop.
bool propagateJoinDivergence(const BasicBlock &JoinBlock,
const Loop *TermLoop);
/// \brief Propagate induced value divergence due to control divergence in \p
/// Term.
void propagateBranchDivergence(const Instruction &Term);
/// \brief Propagate divergent caused by a divergent loop exit.
///
/// \param ExitingLoop is a divergent loop.
void propagateLoopDivergence(const Loop &ExitingLoop);
private:
const Function &F;
// If regionLoop != nullptr, analysis is only performed within \p RegionLoop.
// Otw, analyze the whole function
const Loop *RegionLoop;
const DominatorTree &DT;
const LoopInfo &LI;
// Recognized divergent loops
DenseSet<const Loop *> DivergentLoops;
// The SDA links divergent branches to divergent control-flow joins.
SyncDependenceAnalysis &SDA;
// Use simplified code path for LCSSA form.
bool IsLCSSAForm;
// Set of known-uniform values.
DenseSet<const Value *> UniformOverrides;
// Blocks with joining divergent control from different predecessors.
DenseSet<const BasicBlock *> DivergentJoinBlocks;
// Detected/marked divergent values.
DenseSet<const Value *> DivergentValues;
// Internal worklist for divergence propagation.
std::vector<const Instruction *> Worklist;
};
/// \brief Divergence analysis frontend for GPU kernels.
class GPUDivergenceAnalysis {
SyncDependenceAnalysis SDA;
DivergenceAnalysis DA;
public:
/// Runs the divergence analysis on @F, a GPU kernel
GPUDivergenceAnalysis(Function &F, const DominatorTree &DT,
const PostDominatorTree &PDT, const LoopInfo &LI,
const TargetTransformInfo &TTI);
/// Whether any divergence was detected.
bool hasDivergence() const { return DA.hasDetectedDivergence(); }
/// The GPU kernel this analysis result is for
const Function &getFunction() const { return DA.getFunction(); }
/// Whether \p V is divergent at its definition.
bool isDivergent(const Value &V) const;
/// Whether \p U is divergent. Uses of a uniform value can be divergent.
bool isDivergentUse(const Use &U) const;
/// Whether \p V is uniform/non-divergent.
bool isUniform(const Value &V) const { return !isDivergent(V); }
/// Whether \p U is uniform/non-divergent. Uses of a uniform value can be
/// divergent.
bool isUniformUse(const Use &U) const { return !isDivergentUse(U); }
/// Print all divergent values in the kernel.
void print(raw_ostream &OS, const Module *) const;
};
} // namespace llvm
#endif // LLVM_ANALYSIS_DIVERGENCE_ANALYSIS_H