LLVM  15.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/PassManager.h"
21 #include <vector>
22 
23 namespace llvm {
24 class Function;
25 class Instruction;
26 class Loop;
27 class raw_ostream;
28 class TargetTransformInfo;
29 class Value;
30 
31 /// \brief Generic divergence analysis for reducible CFGs.
32 ///
33 /// This analysis propagates divergence in a data-parallel context from sources
34 /// of divergence to all users. It requires reducible CFGs. All assignments
35 /// should be in SSA form.
37 public:
38  /// \brief This instance will analyze the whole function \p F or the loop \p
39  /// RegionLoop.
40  ///
41  /// \param RegionLoop if non-null the analysis is restricted to \p RegionLoop.
42  /// Otherwise the whole function is analyzed.
43  /// \param IsLCSSAForm whether the analysis may assume that the IR in the
44  /// region in LCSSA form.
45  DivergenceAnalysisImpl(const Function &F, const Loop *RegionLoop,
46  const DominatorTree &DT, const LoopInfo &LI,
47  SyncDependenceAnalysis &SDA, bool IsLCSSAForm);
48 
49  /// \brief The loop that defines the analyzed region (if any).
50  const Loop *getRegionLoop() const { return RegionLoop; }
51  const Function &getFunction() const { return F; }
52 
53  /// \brief Whether \p BB is part of the region.
54  bool inRegion(const BasicBlock &BB) const;
55  /// \brief Whether \p I is part of the region.
56  bool inRegion(const Instruction &I) const;
57 
58  /// \brief Mark \p UniVal as a value that is always uniform.
59  void addUniformOverride(const Value &UniVal);
60 
61  /// \brief Mark \p DivVal as a value that is always divergent. Will not do so
62  /// if `isAlwaysUniform(DivVal)`.
63  /// \returns Whether the tracked divergence state of \p DivVal changed.
64  bool markDivergent(const Value &DivVal);
65 
66  /// \brief Propagate divergence to all instructions in the region.
67  /// Divergence is seeded by calls to \p markDivergent.
68  void compute();
69 
70  /// \brief Whether any value was marked or analyzed to be divergent.
71  bool hasDetectedDivergence() const { return !DivergentValues.empty(); }
72 
73  /// \brief Whether \p Val will always return a uniform value regardless of its
74  /// operands
75  bool isAlwaysUniform(const Value &Val) const;
76 
77  /// \brief Whether \p Val is divergent at its definition.
78  bool isDivergent(const Value &Val) const;
79 
80  /// \brief Whether \p U is divergent. Uses of a uniform value can be
81  /// divergent.
82  bool isDivergentUse(const Use &U) const;
83 
84 private:
85  /// \brief Mark \p Term as divergent and push all Instructions that become
86  /// divergent as a result on the worklist.
87  void analyzeControlDivergence(const Instruction &Term);
88  /// \brief Mark all phi nodes in \p JoinBlock as divergent and push them on
89  /// the worklist.
90  void taintAndPushPhiNodes(const BasicBlock &JoinBlock);
91 
92  /// \brief Identify all Instructions that become divergent because \p DivExit
93  /// is a divergent loop exit of \p DivLoop. Mark those instructions as
94  /// divergent and push them on the worklist.
95  void propagateLoopExitDivergence(const BasicBlock &DivExit,
96  const Loop &DivLoop);
97 
98  /// \brief Internal implementation function for propagateLoopExitDivergence.
99  void analyzeLoopExitDivergence(const BasicBlock &DivExit,
100  const Loop &OuterDivLoop);
101 
102  /// \brief Mark all instruction as divergent that use a value defined in \p
103  /// OuterDivLoop. Push their users on the worklist.
104  void analyzeTemporalDivergence(const Instruction &I,
105  const Loop &OuterDivLoop);
106 
107  /// \brief Push all users of \p Val (in the region) to the worklist.
108  void pushUsers(const Value &I);
109 
110  /// \brief Whether \p Val is divergent when read in \p ObservingBlock.
111  bool isTemporalDivergent(const BasicBlock &ObservingBlock,
112  const Value &Val) const;
113 
114 private:
115  const Function &F;
116  // If regionLoop != nullptr, analysis is only performed within \p RegionLoop.
117  // Otherwise, analyze the whole function
118  const Loop *RegionLoop;
119 
120  const DominatorTree &DT;
121  const LoopInfo &LI;
122 
123  // Recognized divergent loops
124  DenseSet<const Loop *> DivergentLoops;
125 
126  // The SDA links divergent branches to divergent control-flow joins.
128 
129  // Use simplified code path for LCSSA form.
130  bool IsLCSSAForm;
131 
132  // Set of known-uniform values.
133  DenseSet<const Value *> UniformOverrides;
134 
135  // Detected/marked divergent values.
136  DenseSet<const Value *> DivergentValues;
137 
138  // Internal worklist for divergence propagation.
139  std::vector<const Instruction *> Worklist;
140 };
141 
143  Function &F;
144 
145  // If the function contains an irreducible region the divergence
146  // analysis can run indefinitely. We set ContainsIrreducible and no
147  // analysis is actually performed on the function. All values in
148  // this function are conservatively reported as divergent instead.
149  bool ContainsIrreducible = false;
150  std::unique_ptr<SyncDependenceAnalysis> SDA;
151  std::unique_ptr<DivergenceAnalysisImpl> DA;
152 
153 public:
155  const PostDominatorTree &PDT, const LoopInfo &LI,
156  const TargetTransformInfo &TTI, bool KnownReducible);
157 
158  /// Whether any divergence was detected.
159  bool hasDivergence() const {
160  return ContainsIrreducible || DA->hasDetectedDivergence();
161  }
162 
163  /// The GPU kernel this analysis result is for
164  const Function &getFunction() const { return F; }
165 
166  /// Whether \p V is divergent at its definition.
167  bool isDivergent(const Value &V) const {
168  return ContainsIrreducible || DA->isDivergent(V);
169  }
170 
171  /// Whether \p U is divergent. Uses of a uniform value can be divergent.
172  bool isDivergentUse(const Use &U) const {
173  return ContainsIrreducible || DA->isDivergentUse(U);
174  }
175 
176  /// Whether \p V is uniform/non-divergent.
177  bool isUniform(const Value &V) const { return !isDivergent(V); }
178 
179  /// Whether \p U is uniform/non-divergent. Uses of a uniform value can be
180  /// divergent.
181  bool isUniformUse(const Use &U) const { return !isDivergentUse(U); }
182 };
183 
184 /// \brief Divergence analysis frontend for GPU kernels.
185 class DivergenceAnalysis : public AnalysisInfoMixin<DivergenceAnalysis> {
187 
188  static AnalysisKey Key;
189 
190 public:
192 
193  /// Runs the divergence analysis on @F, a GPU kernel
195 };
196 
197 /// Printer pass to dump divergence analysis results.
199  : public PassInfoMixin<DivergenceAnalysisPrinterPass> {
201 
203 
204 private:
205  raw_ostream &OS;
206 }; // class DivergenceAnalysisPrinterPass
207 
208 } // namespace llvm
209 
210 #endif // LLVM_ANALYSIS_DIVERGENCEANALYSIS_H
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::DivergenceAnalysisImpl::isDivergentUse
bool isDivergentUse(const Use &U) const
Whether U is divergent.
Definition: DivergenceAnalysis.cpp:340
llvm::PassInfoMixin
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:371
llvm::Function
Definition: Function.h:60
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:546
llvm::DivergenceAnalysisImpl::getRegionLoop
const Loop * getRegionLoop() const
The loop that defines the analyzed region (if any).
Definition: DivergenceAnalysis.h:50
llvm::DivergenceAnalysisImpl::isAlwaysUniform
bool isAlwaysUniform(const Value &Val) const
Whether Val will always return a uniform value regardless of its operands.
Definition: DivergenceAnalysis.cpp:332
llvm::DivergenceAnalysisImpl::addUniformOverride
void addUniformOverride(const Value &UniVal)
Mark UniVal as a value that is always uniform.
Definition: DivergenceAnalysis.cpp:106
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:168
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
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:346
llvm::DivergenceAnalysisImpl::inRegion
bool inRegion(const BasicBlock &BB) const
Whether BB is part of the region.
Definition: DivergenceAnalysis.cpp:131
llvm::DivergenceAnalysis::run
Result run(Function &F, FunctionAnalysisManager &AM)
Runs the divergence analysis on @F, a GPU kernel.
Definition: DivergenceAnalysis.cpp:382
llvm::DivergenceInfo::isUniform
bool isUniform(const Value &V) const
Whether V is uniform/non-divergent.
Definition: DivergenceAnalysis.h:177
llvm::DivergenceAnalysisPrinterPass
Printer pass to dump divergence analysis results.
Definition: DivergenceAnalysis.h:198
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::DivergenceAnalysisImpl::compute
void compute()
Propagate divergence to all instructions in the region.
Definition: DivergenceAnalysis.cpp:312
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
SyncDependenceAnalysis.h
DenseSet.h
llvm::Instruction
Definition: Instruction.h:42
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:54
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:159
llvm::DivergenceInfo::isUniformUse
bool isUniformUse(const Use &U) const
Whether U is uniform/non-divergent.
Definition: DivergenceAnalysis.h:181
llvm::AnalysisKey
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:69
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::M68kBeads::Term
@ Term
Definition: M68kBaseInfo.h:71
llvm::DivergenceInfo::isDivergent
bool isDivergent(const Value &V) const
Whether V is divergent at its definition.
Definition: DivergenceAnalysis.h:167
llvm::detail::DenseSetImpl::empty
bool empty() const
Definition: DenseSet.h:80
llvm::DivergenceAnalysisImpl
Generic divergence analysis for reducible CFGs.
Definition: DivergenceAnalysis.h:36
llvm::AnalysisInfoMixin
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:394
llvm::DivergenceAnalysisPrinterPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM)
Definition: DivergenceAnalysis.cpp:392
llvm::LoopInfo
Definition: LoopInfo.h:1102
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:172
llvm::SyncDependenceAnalysis
Relates points of divergent control to join points in reducible CFGs.
Definition: SyncDependenceAnalysis.h:60
llvm::DivergenceInfo
Definition: DivergenceAnalysis.h:142
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:92
llvm::DivergenceInfo::getFunction
const Function & getFunction() const
The GPU kernel this analysis result is for.
Definition: DivergenceAnalysis.h:164
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
PassManager.h
llvm::DivergenceAnalysisImpl::isDivergent
bool isDivergent(const Value &Val) const
Whether Val is divergent at its definition.
Definition: DivergenceAnalysis.cpp:336
llvm::DivergenceAnalysisImpl::hasDetectedDivergence
bool hasDetectedDivergence() const
Whether any value was marked or analyzed to be divergent.
Definition: DivergenceAnalysis.h:71
llvm::DivergenceAnalysis
Divergence analysis frontend for GPU kernels.
Definition: DivergenceAnalysis.h:185
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
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:200
llvm::DivergenceAnalysisImpl::markDivergent
bool markDivergent(const Value &DivVal)
Mark DivVal as a value that is always divergent.
Definition: DivergenceAnalysis.cpp:98
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::codeview::PublicSymFlags::Function
@ Function
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
llvm::DivergenceAnalysisImpl::getFunction
const Function & getFunction() const
Definition: DivergenceAnalysis.h:51