LLVM  8.0.0svn
DivergenceAnalysis.h
Go to the documentation of this file.
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"
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.
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).
52  const Loop *getRegionLoop() const { return RegionLoop; }
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.
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.
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).
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.
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 } // namespace llvm
177 
178 #endif // LLVM_ANALYSIS_DIVERGENCE_ANALYSIS_H
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:64
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:250
Generic divergence analysis for reducible CFGs.
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.
const Function & getFunction() const
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:145
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
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).
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:459
#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 a divergent value.
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
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:46
void print(raw_ostream &OS, const Module *) const