LLVM  14.0.0git
DivergenceAnalysis.h
Go to the documentation of this file.
1 //===- llvm/Analysis/DivergenceAnalysis.h - Divergence Analysis -*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // \file
10 // The divergence analysis determines which instructions and branches are
11 // divergent given a set of divergent source instructions.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #ifndef LLVM_ANALYSIS_DIVERGENCEANALYSIS_H
16 #define LLVM_ANALYSIS_DIVERGENCEANALYSIS_H
17 
18 #include "llvm/ADT/DenseSet.h"
20 #include "llvm/IR/Function.h"
21 #include "llvm/Pass.h"
22 #include <vector>
23 
24 namespace llvm {
25 class Module;
26 class Value;
27 class Instruction;
28 class Loop;
29 class raw_ostream;
30 class TargetTransformInfo;
31 
32 /// \brief Generic divergence analysis for reducible CFGs.
33 ///
34 /// This analysis propagates divergence in a data-parallel context from sources
35 /// of divergence to all users. It requires reducible CFGs. All assignments
36 /// should be in SSA form.
38 public:
39  /// \brief This instance will analyze the whole function \p F or the loop \p
40  /// RegionLoop.
41  ///
42  /// \param RegionLoop if non-null the analysis is restricted to \p RegionLoop.
43  /// Otherwise the whole function is analyzed.
44  /// \param IsLCSSAForm whether the analysis may assume that the IR in the
45  /// region in in LCSSA form.
46  DivergenceAnalysisImpl(const Function &F, const Loop *RegionLoop,
47  const DominatorTree &DT, const LoopInfo &LI,
48  SyncDependenceAnalysis &SDA, bool IsLCSSAForm);
49 
50  /// \brief The loop that defines the analyzed region (if any).
51  const Loop *getRegionLoop() const { return RegionLoop; }
52  const Function &getFunction() const { return F; }
53 
54  /// \brief Whether \p BB is part of the region.
55  bool inRegion(const BasicBlock &BB) const;
56  /// \brief Whether \p I is part of the region.
57  bool inRegion(const Instruction &I) const;
58 
59  /// \brief Mark \p UniVal as a value that is always uniform.
60  void addUniformOverride(const Value &UniVal);
61 
62  /// \brief Mark \p DivVal as a value that is always divergent. Will not do so
63  /// if `isAlwaysUniform(DivVal)`.
64  /// \returns Whether the tracked divergence state of \p DivVal changed.
65  bool markDivergent(const Value &DivVal);
66 
67  /// \brief Propagate divergence to all instructions in the region.
68  /// Divergence is seeded by calls to \p markDivergent.
69  void compute();
70 
71  /// \brief Whether any value was marked or analyzed to be divergent.
72  bool hasDetectedDivergence() const { return !DivergentValues.empty(); }
73 
74  /// \brief Whether \p Val will always return a uniform value regardless of its
75  /// operands
76  bool isAlwaysUniform(const Value &Val) const;
77 
78  /// \brief Whether \p Val is divergent at its definition.
79  bool isDivergent(const Value &Val) const;
80 
81  /// \brief Whether \p U is divergent. Uses of a uniform value can be
82  /// divergent.
83  bool isDivergentUse(const Use &U) const;
84 
85 private:
86  /// \brief Mark \p Term as divergent and push all Instructions that become
87  /// divergent as a result on the worklist.
88  void analyzeControlDivergence(const Instruction &Term);
89  /// \brief Mark all phi nodes in \p JoinBlock as divergent and push them on
90  /// the worklist.
91  void taintAndPushPhiNodes(const BasicBlock &JoinBlock);
92 
93  /// \brief Identify all Instructions that become divergent because \p DivExit
94  /// is a divergent loop exit of \p DivLoop. Mark those instructions as
95  /// divergent and push them on the worklist.
96  void propagateLoopExitDivergence(const BasicBlock &DivExit,
97  const Loop &DivLoop);
98 
99  /// \brief Internal implementation function for propagateLoopExitDivergence.
100  void analyzeLoopExitDivergence(const BasicBlock &DivExit,
101  const Loop &OuterDivLoop);
102 
103  /// \brief Mark all instruction as divergent that use a value defined in \p
104  /// OuterDivLoop. Push their users on the worklist.
105  void analyzeTemporalDivergence(const Instruction &I,
106  const Loop &OuterDivLoop);
107 
108  /// \brief Push all users of \p Val (in the region) to the worklist.
109  void pushUsers(const Value &I);
110 
111  /// \brief Whether \p Val is divergent when read in \p ObservingBlock.
112  bool isTemporalDivergent(const BasicBlock &ObservingBlock,
113  const Value &Val) const;
114 
115 private:
116  const Function &F;
117  // If regionLoop != nullptr, analysis is only performed within \p RegionLoop.
118  // Otherwise, analyze the whole function
119  const Loop *RegionLoop;
120 
121  const DominatorTree &DT;
122  const LoopInfo &LI;
123 
124  // Recognized divergent loops
125  DenseSet<const Loop *> DivergentLoops;
126 
127  // The SDA links divergent branches to divergent control-flow joins.
129 
130  // Use simplified code path for LCSSA form.
131  bool IsLCSSAForm;
132 
133  // Set of known-uniform values.
134  DenseSet<const Value *> UniformOverrides;
135 
136  // Detected/marked divergent values.
137  DenseSet<const Value *> DivergentValues;
138 
139  // Internal worklist for divergence propagation.
140  std::vector<const Instruction *> Worklist;
141 };
142 
144  Function &F;
145 
146  // If the function contains an irreducible region the divergence
147  // analysis can run indefinitely. We set ContainsIrreducible and no
148  // analysis is actually performed on the function. All values in
149  // this function are conservatively reported as divergent instead.
150  bool ContainsIrreducible;
151  std::unique_ptr<SyncDependenceAnalysis> SDA;
152  std::unique_ptr<DivergenceAnalysisImpl> DA;
153 
154 public:
156  const PostDominatorTree &PDT, const LoopInfo &LI,
157  const TargetTransformInfo &TTI, bool KnownReducible);
158 
159  /// Whether any divergence was detected.
160  bool hasDivergence() const {
161  return ContainsIrreducible || DA->hasDetectedDivergence();
162  }
163 
164  /// The GPU kernel this analysis result is for
165  const Function &getFunction() const { return F; }
166 
167  /// Whether \p V is divergent at its definition.
168  bool isDivergent(const Value &V) const {
169  return ContainsIrreducible || DA->isDivergent(V);
170  }
171 
172  /// Whether \p U is divergent. Uses of a uniform value can be divergent.
173  bool isDivergentUse(const Use &U) const {
174  return ContainsIrreducible || DA->isDivergentUse(U);
175  }
176 
177  /// Whether \p V is uniform/non-divergent.
178  bool isUniform(const Value &V) const { return !isDivergent(V); }
179 
180  /// Whether \p U is uniform/non-divergent. Uses of a uniform value can be
181  /// divergent.
182  bool isUniformUse(const Use &U) const { return !isDivergentUse(U); }
183 };
184 
185 /// \brief Divergence analysis frontend for GPU kernels.
186 class DivergenceAnalysis : public AnalysisInfoMixin<DivergenceAnalysis> {
188 
189  static AnalysisKey Key;
190 
191 public:
193 
194  /// Runs the divergence analysis on @F, a GPU kernel
196 };
197 
198 /// Printer pass to dump divergence analysis results.
200  : public PassInfoMixin<DivergenceAnalysisPrinterPass> {
202 
204 
205 private:
206  raw_ostream &OS;
207 }; // class DivergenceAnalysisPrinterPass
208 
209 } // namespace llvm
210 
211 #endif // LLVM_ANALYSIS_DIVERGENCEANALYSIS_H
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
llvm::DivergenceAnalysisImpl::isDivergentUse
bool isDivergentUse(const Use &U) const
Whether U is divergent.
Definition: DivergenceAnalysis.cpp:341
llvm::PassInfoMixin
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:374
llvm::Function
Definition: Function.h:62
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
Pass.h
llvm::DivergenceAnalysisImpl::getRegionLoop
const Loop * getRegionLoop() const
The loop that defines the analyzed region (if any).
Definition: DivergenceAnalysis.h:51
llvm::DivergenceAnalysisImpl::isAlwaysUniform
bool isAlwaysUniform(const Value &Val) const
Whether Val will always return a uniform value regardless of its operands.
Definition: DivergenceAnalysis.cpp:333
llvm::DivergenceAnalysisImpl::addUniformOverride
void addUniformOverride(const Value &UniVal)
Mark UniVal as a value that is always uniform.
Definition: DivergenceAnalysis.cpp:107
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:169
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
FAM
FunctionAnalysisManager FAM
Definition: PassBuilderBindings.cpp:59
llvm::DivergenceInfo::DivergenceInfo
DivergenceInfo(Function &F, const DominatorTree &DT, const PostDominatorTree &PDT, const LoopInfo &LI, const TargetTransformInfo &TTI, bool KnownReducible)
Definition: DivergenceAnalysis.cpp:347
llvm::DivergenceAnalysisImpl::inRegion
bool inRegion(const BasicBlock &BB) const
Whether BB is part of the region.
Definition: DivergenceAnalysis.cpp:132
llvm::DivergenceAnalysis::run
Result run(Function &F, FunctionAnalysisManager &AM)
Runs the divergence analysis on @F, a GPU kernel.
Definition: DivergenceAnalysis.cpp:383
llvm::DivergenceInfo::isUniform
bool isUniform(const Value &V) const
Whether V is uniform/non-divergent.
Definition: DivergenceAnalysis.h:178
llvm::DivergenceAnalysisPrinterPass
Printer pass to dump divergence analysis results.
Definition: DivergenceAnalysis.h:199
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::DivergenceAnalysisImpl::compute
void compute()
Propagate divergence to all instructions in the region.
Definition: DivergenceAnalysis.cpp:313
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
SyncDependenceAnalysis.h
DenseSet.h
llvm::Instruction
Definition: Instruction.h:45
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
llvm::DenseSet
Implements a dense probed hash-table based set.
Definition: DenseSet.h:268
llvm::DivergenceInfo::hasDivergence
bool hasDivergence() const
Whether any divergence was detected.
Definition: DivergenceAnalysis.h:160
llvm::M68kBeads::Term
@ Term
Definition: M68kBaseInfo.h:71
llvm::DivergenceInfo::isUniformUse
bool isUniformUse(const Use &U) const
Whether U is uniform/non-divergent.
Definition: DivergenceAnalysis.h:182
llvm::AnalysisKey
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:72
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::DivergenceInfo::isDivergent
bool isDivergent(const Value &V) const
Whether V is divergent at its definition.
Definition: DivergenceAnalysis.h:168
llvm::detail::DenseSetImpl::empty
bool empty() const
Definition: DenseSet.h:80
llvm::DivergenceAnalysisImpl
Generic divergence analysis for reducible CFGs.
Definition: DivergenceAnalysis.h:37
llvm::AnalysisInfoMixin
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:397
llvm::DivergenceAnalysisPrinterPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM)
Definition: DivergenceAnalysis.cpp:393
llvm::LoopInfo
Definition: LoopInfo.h:1083
llvm::PostDominatorTree
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
Definition: PostDominators.h:28
llvm::DivergenceInfo::isDivergentUse
bool isDivergentUse(const Use &U) const
Whether U is divergent. Uses of a uniform value can be divergent.
Definition: DivergenceAnalysis.h:173
Module
Machine Check Debug Module
Definition: MachineCheckDebugify.cpp:122
llvm::SyncDependenceAnalysis
Relates points of divergent control to join points in reducible CFGs.
Definition: SyncDependenceAnalysis.h:60
llvm::DivergenceInfo
Definition: DivergenceAnalysis.h:143
llvm::DivergenceAnalysisImpl::DivergenceAnalysisImpl
DivergenceAnalysisImpl(const Function &F, const Loop *RegionLoop, const DominatorTree &DT, const LoopInfo &LI, SyncDependenceAnalysis &SDA, bool IsLCSSAForm)
This instance will analyze the whole function F or the loop RegionLoop.
Definition: DivergenceAnalysis.cpp:93
llvm::DivergenceInfo::getFunction
const Function & getFunction() const
The GPU kernel this analysis result is for.
Definition: DivergenceAnalysis.h:165
Function.h
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
llvm::DivergenceAnalysisImpl::isDivergent
bool isDivergent(const Value &Val) const
Whether Val is divergent at its definition.
Definition: DivergenceAnalysis.cpp:337
llvm::DivergenceAnalysisImpl::hasDetectedDivergence
bool hasDetectedDivergence() const
Whether any value was marked or analyzed to be divergent.
Definition: DivergenceAnalysis.h:72
llvm::DivergenceAnalysis
Divergence analysis frontend for GPU kernels.
Definition: DivergenceAnalysis.h:186
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::DivergenceAnalysisPrinterPass::DivergenceAnalysisPrinterPass
DivergenceAnalysisPrinterPass(raw_ostream &OS)
Definition: DivergenceAnalysis.h:201
llvm::DivergenceAnalysisImpl::markDivergent
bool markDivergent(const Value &DivVal)
Mark DivVal as a value that is always divergent.
Definition: DivergenceAnalysis.cpp:99
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
llvm::DivergenceAnalysisImpl::getFunction
const Function & getFunction() const
Definition: DivergenceAnalysis.h:52