LLVM  10.0.0svn
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_DIVERGENCE_ANALYSIS_H
16 #define LLVM_ANALYSIS_DIVERGENCE_ANALYSIS_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  DivergenceAnalysis(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.
63  void markDivergent(const Value &DivVal);
64 
65  /// \brief Propagate divergence to all instructions in the region.
66  /// Divergence is seeded by calls to \p markDivergent.
67  void compute();
68 
69  /// \brief Whether any value was marked or analyzed to be divergent.
70  bool hasDetectedDivergence() const { return !DivergentValues.empty(); }
71 
72  /// \brief Whether \p Val will always return a uniform value regardless of its
73  /// operands
74  bool isAlwaysUniform(const Value &Val) const;
75 
76  /// \brief Whether \p Val is divergent at its definition.
77  bool isDivergent(const Value &Val) const;
78 
79  /// \brief Whether \p U is divergent. Uses of a uniform value can be divergent.
80  bool isDivergentUse(const Use &U) const;
81 
82  void print(raw_ostream &OS, const Module *) const;
83 
84 private:
85  bool updateTerminator(const Instruction &Term) const;
86  bool updatePHINode(const PHINode &Phi) const;
87 
88  /// \brief Computes whether \p Inst is divergent based on the
89  /// divergence of its operands.
90  ///
91  /// \returns Whether \p Inst is divergent.
92  ///
93  /// This should only be called for non-phi, non-terminator instructions.
94  bool updateNormalInstruction(const Instruction &Inst) const;
95 
96  /// \brief Mark users of live-out users as divergent.
97  ///
98  /// \param LoopHeader the header of the divergent loop.
99  ///
100  /// Marks all users of live-out values of the loop headed by \p LoopHeader
101  /// as divergent and puts them on the worklist.
102  void taintLoopLiveOuts(const BasicBlock &LoopHeader);
103 
104  /// \brief Push all users of \p Val (in the region) to the worklist
105  void pushUsers(const Value &I);
106 
107  /// \brief Push all phi nodes in @block to the worklist
108  void pushPHINodes(const BasicBlock &Block);
109 
110  /// \brief Mark \p Block as join divergent
111  ///
112  /// A block is join divergent if two threads may reach it from different
113  /// incoming blocks at the same time.
114  void markBlockJoinDivergent(const BasicBlock &Block) {
115  DivergentJoinBlocks.insert(&Block);
116  }
117 
118  /// \brief Whether \p Val is divergent when read in \p ObservingBlock.
119  bool isTemporalDivergent(const BasicBlock &ObservingBlock,
120  const Value &Val) const;
121 
122  /// \brief Whether \p Block is join divergent
123  ///
124  /// (see markBlockJoinDivergent).
125  bool isJoinDivergent(const BasicBlock &Block) const {
126  return DivergentJoinBlocks.find(&Block) != DivergentJoinBlocks.end();
127  }
128 
129  /// \brief Propagate control-induced divergence to users (phi nodes and
130  /// instructions).
131  //
132  // \param JoinBlock is a divergent loop exit or join point of two disjoint
133  // paths.
134  // \returns Whether \p JoinBlock is a divergent loop exit of \p TermLoop.
135  bool propagateJoinDivergence(const BasicBlock &JoinBlock,
136  const Loop *TermLoop);
137 
138  /// \brief Propagate induced value divergence due to control divergence in \p
139  /// Term.
140  void propagateBranchDivergence(const Instruction &Term);
141 
142  /// \brief Propagate divergent caused by a divergent loop exit.
143  ///
144  /// \param ExitingLoop is a divergent loop.
145  void propagateLoopDivergence(const Loop &ExitingLoop);
146 
147 private:
148  const Function &F;
149  // If regionLoop != nullptr, analysis is only performed within \p RegionLoop.
150  // Otw, analyze the whole function
151  const Loop *RegionLoop;
152 
153  const DominatorTree &DT;
154  const LoopInfo &LI;
155 
156  // Recognized divergent loops
157  DenseSet<const Loop *> DivergentLoops;
158 
159  // The SDA links divergent branches to divergent control-flow joins.
161 
162  // Use simplified code path for LCSSA form.
163  bool IsLCSSAForm;
164 
165  // Set of known-uniform values.
166  DenseSet<const Value *> UniformOverrides;
167 
168  // Blocks with joining divergent control from different predecessors.
169  DenseSet<const BasicBlock *> DivergentJoinBlocks;
170 
171  // Detected/marked divergent values.
172  DenseSet<const Value *> DivergentValues;
173 
174  // Internal worklist for divergence propagation.
175  std::vector<const Instruction *> Worklist;
176 };
177 
178 /// \brief Divergence analysis frontend for GPU kernels.
182 
183 public:
184  /// Runs the divergence analysis on @F, a GPU kernel
186  const PostDominatorTree &PDT, const LoopInfo &LI,
187  const TargetTransformInfo &TTI);
188 
189  /// Whether any divergence was detected.
190  bool hasDivergence() const { return DA.hasDetectedDivergence(); }
191 
192  /// The GPU kernel this analysis result is for
193  const Function &getFunction() const { return DA.getFunction(); }
194 
195  /// Whether \p V is divergent at its definition.
196  bool isDivergent(const Value &V) const;
197 
198  /// Whether \p U is divergent. Uses of a uniform value can be divergent.
199  bool isDivergentUse(const Use &U) const;
200 
201  /// Whether \p V is uniform/non-divergent.
202  bool isUniform(const Value &V) const { return !isDivergent(V); }
203 
204  /// Whether \p U is uniform/non-divergent. Uses of a uniform value can be
205  /// divergent.
206  bool isUniformUse(const Use &U) const { return !isDivergentUse(U); }
207 
208  /// Print all divergent values in the kernel.
209  void print(raw_ostream &OS, const Module *) const;
210 };
211 
212 } // namespace llvm
213 
214 #endif // LLVM_ANALYSIS_DIVERGENCE_ANALYSIS_H
This class represents lattice values for constants.
Definition: AllocatorList.h:23
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:65
void addUniformOverride(const Value &UniVal)
Mark UniVal as a value that is always uniform.
Implements a dense probed hash-table based set.
Definition: DenseSet.h:249
Generic divergence analysis for reducible CFGs.
Divergence analysis frontend for GPU kernels.
DivergenceAnalysis(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.
void compute()
Propagate divergence to all instructions in the region.
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
const Function & getFunction() const
#define F(x, y, z)
Definition: MD5.cpp:55
const Function & getFunction() const
The GPU kernel this analysis result is for.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
bool isUniform(const Value &V) const
Whether V is uniform/non-divergent.
bool hasDetectedDivergence() const
Whether any value was marked or analyzed to be divergent.
Relates points of divergent control to join points in reducible CFGs.
const Loop * getRegionLoop() const
The loop that defines the analyzed region (if any).
bool hasDivergence() const
Whether any divergence was detected.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:509
#define I(x, y, z)
Definition: MD5.cpp:58
bool inRegion(const BasicBlock &BB) const
Whether BB is part of the region.
bool isDivergent(const Value &Val) const
Whether Val is divergent at its definition.
bool isUniformUse(const Use &U) const
Whether U is uniform/non-divergent.
bool isAlwaysUniform(const Value &Val) const
Whether Val will always return a uniform value regardless of its operands.
void markDivergent(const Value &DivVal)
Mark DivVal as a value that is always divergent.
LLVM Value Representation.
Definition: Value.h:73
bool isDivergentUse(const Use &U) const
Whether U is divergent. Uses of a uniform value can be divergent.
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
void print(raw_ostream &OS, const Module *) const