1 //===- llvm/Analysis/DivergenceAnalysis.h - Divergence Analysis -*- C++ -*-===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // \file
11 // The divergence analysis determines which instructions and branches are
12 // divergent given a set of divergent source instructions.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #ifndef LLVM_ANALYSIS_DIVERGENCE_ANALYSIS_H
17 #define LLVM_ANALYSIS_DIVERGENCE_ANALYSIS_H
18 
19 #include "llvm/ADT/DenseSet.h"
20 #include "llvm/Analysis/SyncDependenceAnalysis.h"
21 #include "llvm/IR/Function.h"
22 #include "llvm/Pass.h"
23 #include <vector>
24 
25 namespace llvm {
26 class Module;
27 class Value;
28 class Instruction;
29 class Loop;
30 class raw_ostream;
31 class TargetTransformInfo;
32 
33 /// \brief Generic divergence analysis for reducible CFGs.
34 ///
35 /// This analysis propagates divergence in a data-parallel context from sources
36 /// of divergence to all users. It requires reducible CFGs. All assignments
37 /// should be in SSA form.
38 class DivergenceAnalysis {
39 public:
40   /// \brief This instance will analyze the whole function \p F or the loop \p
41   /// RegionLoop.
42   ///
43   /// \param RegionLoop if non-null the analysis is restricted to \p RegionLoop.
44   /// Otherwise the whole function is analyzed.
45   /// \param IsLCSSAForm whether the analysis may assume that the IR in the
46   /// region in in LCSSA form.
47   DivergenceAnalysis(const Function &F, const Loop *RegionLoop,
48                      const DominatorTree &DT, const LoopInfo &LI,
49                      SyncDependenceAnalysis &SDA, bool IsLCSSAForm);
50 
51   /// \brief The loop that defines the analyzed region (if any).
getRegionLoop()52   const Loop *getRegionLoop() const { return RegionLoop; }
getFunction()53   const Function &getFunction() const { return F; }
54 
55   /// \brief Whether \p BB is part of the region.
56   bool inRegion(const BasicBlock &BB) const;
57   /// \brief Whether \p I is part of the region.
58   bool inRegion(const Instruction &I) const;
59 
60   /// \brief Mark \p UniVal as a value that is always uniform.
61   void addUniformOverride(const Value &UniVal);
62 
63   /// \brief Mark \p DivVal as a value that is always divergent.
64   void 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.
hasDetectedDivergence()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 a divergent value
78   bool isDivergent(const Value &Val) const;
79 
80   void print(raw_ostream &OS, const Module *) const;
81 
82 private:
83   bool updateTerminator(const Instruction &Term) const;
84   bool updatePHINode(const PHINode &Phi) const;
85 
86   /// \brief Computes whether \p Inst is divergent based on the
87   /// divergence of its operands.
88   ///
89   /// \returns Whether \p Inst is divergent.
90   ///
91   /// This should only be called for non-phi, non-terminator instructions.
92   bool updateNormalInstruction(const Instruction &Inst) const;
93 
94   /// \brief Mark users of live-out users as divergent.
95   ///
96   /// \param LoopHeader the header of the divergent loop.
97   ///
98   /// Marks all users of live-out values of the loop headed by \p LoopHeader
99   /// as divergent and puts them on the worklist.
100   void taintLoopLiveOuts(const BasicBlock &LoopHeader);
101 
102   /// \brief Push all users of \p Val (in the region) to the worklist
103   void pushUsers(const Value &I);
104 
105   /// \brief Push all phi nodes in @block to the worklist
106   void pushPHINodes(const BasicBlock &Block);
107 
108   /// \brief Mark \p Block as join divergent
109   ///
110   /// A block is join divergent if two threads may reach it from different
111   /// incoming blocks at the same time.
markBlockJoinDivergent(const BasicBlock & Block)112   void markBlockJoinDivergent(const BasicBlock &Block) {
113     DivergentJoinBlocks.insert(&Block);
114   }
115 
116   /// \brief Whether \p Val is divergent when read in \p ObservingBlock.
117   bool isTemporalDivergent(const BasicBlock &ObservingBlock,
118                            const Value &Val) const;
119 
120   /// \brief Whether \p Block is join divergent
121   ///
122   /// (see markBlockJoinDivergent).
isJoinDivergent(const BasicBlock & Block)123   bool isJoinDivergent(const BasicBlock &Block) const {
124     return DivergentJoinBlocks.find(&Block) != DivergentJoinBlocks.end();
125   }
126 
127   /// \brief Propagate control-induced divergence to users (phi nodes and
128   /// instructions).
129   //
130   // \param JoinBlock is a divergent loop exit or join point of two disjoint
131   // paths.
132   // \returns Whether \p JoinBlock is a divergent loop exit of \p TermLoop.
133   bool propagateJoinDivergence(const BasicBlock &JoinBlock,
134                                const Loop *TermLoop);
135 
136   /// \brief Propagate induced value divergence due to control divergence in \p
137   /// Term.
138   void propagateBranchDivergence(const Instruction &Term);
139 
140   /// \brief Propagate divergent caused by a divergent loop exit.
141   ///
142   /// \param ExitingLoop is a divergent loop.
143   void propagateLoopDivergence(const Loop &ExitingLoop);
144 
145 private:
146   const Function &F;
147   // If regionLoop != nullptr, analysis is only performed within \p RegionLoop.
148   // Otw, analyze the whole function
149   const Loop *RegionLoop;
150 
151   const DominatorTree &DT;
152   const LoopInfo &LI;
153 
154   // Recognized divergent loops
155   DenseSet<const Loop *> DivergentLoops;
156 
157   // The SDA links divergent branches to divergent control-flow joins.
158   SyncDependenceAnalysis &SDA;
159 
160   // Use simplified code path for LCSSA form.
161   bool IsLCSSAForm;
162 
163   // Set of known-uniform values.
164   DenseSet<const Value *> UniformOverrides;
165 
166   // Blocks with joining divergent control from different predecessors.
167   DenseSet<const BasicBlock *> DivergentJoinBlocks;
168 
169   // Detected/marked divergent values.
170   DenseSet<const Value *> DivergentValues;
171 
172   // Internal worklist for divergence propagation.
173   std::vector<const Instruction *> Worklist;
174 };
175 
176 /// \brief Divergence analysis frontend for GPU kernels.
177 class GPUDivergenceAnalysis {
178   SyncDependenceAnalysis SDA;
179   DivergenceAnalysis DA;
180 
181 public:
182   /// Runs the divergence analysis on @F, a GPU kernel
183   GPUDivergenceAnalysis(Function &F, const DominatorTree &DT,
184                         const PostDominatorTree &PDT, const LoopInfo &LI,
185                         const TargetTransformInfo &TTI);
186 
187   /// Whether any divergence was detected.
hasDivergence()188   bool hasDivergence() const { return DA.hasDetectedDivergence(); }
189 
190   /// The GPU kernel this analysis result is for
getFunction()191   const Function &getFunction() const { return DA.getFunction(); }
192 
193   /// Whether \p V is divergent.
194   bool isDivergent(const Value &V) const;
195 
196   /// Whether \p V is uniform/non-divergent
isUniform(const Value & V)197   bool isUniform(const Value &V) const { return !isDivergent(V); }
198 
199   /// Print all divergent values in the kernel.
200   void print(raw_ostream &OS, const Module *) const;
201 };
202 
203 } // namespace llvm
204 
205 #endif // LLVM_ANALYSIS_DIVERGENCE_ANALYSIS_H
206