LLVM  6.0.0svn
DivergenceAnalysis.cpp
Go to the documentation of this file.
1 //===- DivergenceAnalysis.cpp --------- Divergence Analysis Implementation -==//
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 // This file implements divergence analysis which determines whether a branch
11 // in a GPU program is divergent.It can help branch optimizations such as jump
12 // threading and loop unswitching to make better decisions.
13 //
14 // GPU programs typically use the SIMD execution model, where multiple threads
15 // in the same execution group have to execute in lock-step. Therefore, if the
16 // code contains divergent branches (i.e., threads in a group do not agree on
17 // which path of the branch to take), the group of threads has to execute all
18 // the paths from that branch with different subsets of threads enabled until
19 // they converge at the immediately post-dominating BB of the paths.
20 //
21 // Due to this execution model, some optimizations such as jump
22 // threading and loop unswitching can be unfortunately harmful when performed on
23 // divergent branches. Therefore, an analysis that computes which branches in a
24 // GPU program are divergent can help the compiler to selectively run these
25 // optimizations.
26 //
27 // This file defines divergence analysis which computes a conservative but
28 // non-trivial approximation of all divergent branches in a GPU program. It
29 // partially implements the approach described in
30 //
31 // Divergence Analysis
32 // Sampaio, Souza, Collange, Pereira
33 // TOPLAS '13
34 //
35 // The divergence analysis identifies the sources of divergence (e.g., special
36 // variables that hold the thread ID), and recursively marks variables that are
37 // data or sync dependent on a source of divergence as divergent.
38 //
39 // While data dependency is a well-known concept, the notion of sync dependency
40 // is worth more explanation. Sync dependence characterizes the control flow
41 // aspect of the propagation of branch divergence. For example,
42 //
43 // %cond = icmp slt i32 %tid, 10
44 // br i1 %cond, label %then, label %else
45 // then:
46 // br label %merge
47 // else:
48 // br label %merge
49 // merge:
50 // %a = phi i32 [ 0, %then ], [ 1, %else ]
51 //
52 // Suppose %tid holds the thread ID. Although %a is not data dependent on %tid
53 // because %tid is not on its use-def chains, %a is sync dependent on %tid
54 // because the branch "br i1 %cond" depends on %tid and affects which value %a
55 // is assigned to.
56 //
57 // The current implementation has the following limitations:
58 // 1. intra-procedural. It conservatively considers the arguments of a
59 // non-kernel-entry function and the return value of a function call as
60 // divergent.
61 // 2. memory as black box. It conservatively considers values loaded from
62 // generic or local address as divergent. This can be improved by leveraging
63 // pointer analysis.
64 //
65 //===----------------------------------------------------------------------===//
66 
68 #include "llvm/Analysis/Passes.h"
71 #include "llvm/IR/Dominators.h"
72 #include "llvm/IR/InstIterator.h"
73 #include "llvm/IR/Instructions.h"
74 #include "llvm/IR/IntrinsicInst.h"
75 #include "llvm/IR/Value.h"
76 #include "llvm/Support/Debug.h"
78 #include <vector>
79 using namespace llvm;
80 
81 namespace {
82 
83 class DivergencePropagator {
84 public:
85  DivergencePropagator(Function &F, TargetTransformInfo &TTI, DominatorTree &DT,
87  : F(F), TTI(TTI), DT(DT), PDT(PDT), DV(DV) {}
88  void populateWithSourcesOfDivergence();
89  void propagate();
90 
91 private:
92  // A helper function that explores data dependents of V.
93  void exploreDataDependency(Value *V);
94  // A helper function that explores sync dependents of TI.
95  void exploreSyncDependency(TerminatorInst *TI);
96  // Computes the influence region from Start to End. This region includes all
97  // basic blocks on any simple path from Start to End.
98  void computeInfluenceRegion(BasicBlock *Start, BasicBlock *End,
99  DenseSet<BasicBlock *> &InfluenceRegion);
100  // Finds all users of I that are outside the influence region, and add these
101  // users to Worklist.
102  void findUsersOutsideInfluenceRegion(
103  Instruction &I, const DenseSet<BasicBlock *> &InfluenceRegion);
104 
105  Function &F;
106  TargetTransformInfo &TTI;
107  DominatorTree &DT;
108  PostDominatorTree &PDT;
109  std::vector<Value *> Worklist; // Stack for DFS.
110  DenseSet<const Value *> &DV; // Stores all divergent values.
111 };
112 
113 void DivergencePropagator::populateWithSourcesOfDivergence() {
114  Worklist.clear();
115  DV.clear();
116  for (auto &I : instructions(F)) {
117  if (TTI.isSourceOfDivergence(&I)) {
118  Worklist.push_back(&I);
119  DV.insert(&I);
120  }
121  }
122  for (auto &Arg : F.args()) {
123  if (TTI.isSourceOfDivergence(&Arg)) {
124  Worklist.push_back(&Arg);
125  DV.insert(&Arg);
126  }
127  }
128 }
129 
130 void DivergencePropagator::exploreSyncDependency(TerminatorInst *TI) {
131  // Propagation rule 1: if branch TI is divergent, all PHINodes in TI's
132  // immediate post dominator are divergent. This rule handles if-then-else
133  // patterns. For example,
134  //
135  // if (tid < 5)
136  // a1 = 1;
137  // else
138  // a2 = 2;
139  // a = phi(a1, a2); // sync dependent on (tid < 5)
140  BasicBlock *ThisBB = TI->getParent();
141 
142  // Unreachable blocks may not be in the dominator tree.
143  if (!DT.isReachableFromEntry(ThisBB))
144  return;
145 
146  // If the function has no exit blocks or doesn't reach any exit blocks, the
147  // post dominator may be null.
148  DomTreeNode *ThisNode = PDT.getNode(ThisBB);
149  if (!ThisNode)
150  return;
151 
152  BasicBlock *IPostDom = ThisNode->getIDom()->getBlock();
153  if (IPostDom == nullptr)
154  return;
155 
156  for (auto I = IPostDom->begin(); isa<PHINode>(I); ++I) {
157  // A PHINode is uniform if it returns the same value no matter which path is
158  // taken.
159  if (!cast<PHINode>(I)->hasConstantOrUndefValue() && DV.insert(&*I).second)
160  Worklist.push_back(&*I);
161  }
162 
163  // Propagation rule 2: if a value defined in a loop is used outside, the user
164  // is sync dependent on the condition of the loop exits that dominate the
165  // user. For example,
166  //
167  // int i = 0;
168  // do {
169  // i++;
170  // if (foo(i)) ... // uniform
171  // } while (i < tid);
172  // if (bar(i)) ... // divergent
173  //
174  // A program may contain unstructured loops. Therefore, we cannot leverage
175  // LoopInfo, which only recognizes natural loops.
176  //
177  // The algorithm used here handles both natural and unstructured loops. Given
178  // a branch TI, we first compute its influence region, the union of all simple
179  // paths from TI to its immediate post dominator (IPostDom). Then, we search
180  // for all the values defined in the influence region but used outside. All
181  // these users are sync dependent on TI.
182  DenseSet<BasicBlock *> InfluenceRegion;
183  computeInfluenceRegion(ThisBB, IPostDom, InfluenceRegion);
184  // An insight that can speed up the search process is that all the in-region
185  // values that are used outside must dominate TI. Therefore, instead of
186  // searching every basic blocks in the influence region, we search all the
187  // dominators of TI until it is outside the influence region.
188  BasicBlock *InfluencedBB = ThisBB;
189  while (InfluenceRegion.count(InfluencedBB)) {
190  for (auto &I : *InfluencedBB)
191  findUsersOutsideInfluenceRegion(I, InfluenceRegion);
192  DomTreeNode *IDomNode = DT.getNode(InfluencedBB)->getIDom();
193  if (IDomNode == nullptr)
194  break;
195  InfluencedBB = IDomNode->getBlock();
196  }
197 }
198 
199 void DivergencePropagator::findUsersOutsideInfluenceRegion(
200  Instruction &I, const DenseSet<BasicBlock *> &InfluenceRegion) {
201  for (User *U : I.users()) {
202  Instruction *UserInst = cast<Instruction>(U);
203  if (!InfluenceRegion.count(UserInst->getParent())) {
204  if (DV.insert(UserInst).second)
205  Worklist.push_back(UserInst);
206  }
207  }
208 }
209 
210 // A helper function for computeInfluenceRegion that adds successors of "ThisBB"
211 // to the influence region.
212 static void
213 addSuccessorsToInfluenceRegion(BasicBlock *ThisBB, BasicBlock *End,
214  DenseSet<BasicBlock *> &InfluenceRegion,
215  std::vector<BasicBlock *> &InfluenceStack) {
216  for (BasicBlock *Succ : successors(ThisBB)) {
217  if (Succ != End && InfluenceRegion.insert(Succ).second)
218  InfluenceStack.push_back(Succ);
219  }
220 }
221 
222 void DivergencePropagator::computeInfluenceRegion(
223  BasicBlock *Start, BasicBlock *End,
224  DenseSet<BasicBlock *> &InfluenceRegion) {
225  assert(PDT.properlyDominates(End, Start) &&
226  "End does not properly dominate Start");
227 
228  // The influence region starts from the end of "Start" to the beginning of
229  // "End". Therefore, "Start" should not be in the region unless "Start" is in
230  // a loop that doesn't contain "End".
231  std::vector<BasicBlock *> InfluenceStack;
232  addSuccessorsToInfluenceRegion(Start, End, InfluenceRegion, InfluenceStack);
233  while (!InfluenceStack.empty()) {
234  BasicBlock *BB = InfluenceStack.back();
235  InfluenceStack.pop_back();
236  addSuccessorsToInfluenceRegion(BB, End, InfluenceRegion, InfluenceStack);
237  }
238 }
239 
240 void DivergencePropagator::exploreDataDependency(Value *V) {
241  // Follow def-use chains of V.
242  for (User *U : V->users()) {
243  Instruction *UserInst = cast<Instruction>(U);
244  if (!TTI.isAlwaysUniform(U) && DV.insert(UserInst).second)
245  Worklist.push_back(UserInst);
246  }
247 }
248 
250  // Traverse the dependency graph using DFS.
251  while (!Worklist.empty()) {
252  Value *V = Worklist.back();
253  Worklist.pop_back();
254  if (TerminatorInst *TI = dyn_cast<TerminatorInst>(V)) {
255  // Terminators with less than two successors won't introduce sync
256  // dependency. Ignore them.
257  if (TI->getNumSuccessors() > 1)
258  exploreSyncDependency(TI);
259  }
260  exploreDataDependency(V);
261  }
262 }
263 
264 } /// end namespace anonymous
265 
266 // Register this pass.
267 char DivergenceAnalysis::ID = 0;
268 INITIALIZE_PASS_BEGIN(DivergenceAnalysis, "divergence", "Divergence Analysis",
269  false, true)
273  false, true)
274 
276  return new DivergenceAnalysis();
277 }
278 
282  AU.setPreservesAll();
283 }
284 
286  auto *TTIWP = getAnalysisIfAvailable<TargetTransformInfoWrapperPass>();
287  if (TTIWP == nullptr)
288  return false;
289 
290  TargetTransformInfo &TTI = TTIWP->getTTI(F);
291  // Fast path: if the target does not have branch divergence, we do not mark
292  // any branch as divergent.
293  if (!TTI.hasBranchDivergence())
294  return false;
295 
296  DivergentValues.clear();
297  auto &PDT = getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
298  DivergencePropagator DP(F, TTI,
299  getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
300  PDT, DivergentValues);
301  DP.populateWithSourcesOfDivergence();
302  DP.propagate();
303  return false;
304 }
305 
306 void DivergenceAnalysis::print(raw_ostream &OS, const Module *) const {
307  if (DivergentValues.empty())
308  return;
309  const Value *FirstDivergentValue = *DivergentValues.begin();
310  const Function *F;
311  if (const Argument *Arg = dyn_cast<Argument>(FirstDivergentValue)) {
312  F = Arg->getParent();
313  } else if (const Instruction *I =
314  dyn_cast<Instruction>(FirstDivergentValue)) {
315  F = I->getParent()->getParent();
316  } else {
317  llvm_unreachable("Only arguments and instructions can be divergent");
318  }
319 
320  // Dumps all divergent values in F, arguments and then instructions.
321  for (auto &Arg : F->args()) {
322  if (DivergentValues.count(&Arg))
323  OS << "DIVERGENT: " << Arg << "\n";
324  }
325  // Iterate instructions using instructions() to ensure a deterministic order.
326  for (auto &I : instructions(F)) {
327  if (DivergentValues.count(&I))
328  OS << "DIVERGENT:" << I << "\n";
329  }
330 }
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
This class represents an incoming formal argument to a Function.
Definition: Argument.h:30
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:63
Implements a dense probed hash-table based set.
Definition: DenseSet.h:221
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass...
F(f)
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:252
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
bool hasBranchDivergence() const
Return true if branch divergence exists.
FunctionPass * createDivergenceAnalysisPass()
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:140
NodeT * getBlock() const
Subclasses of this class are all able to terminate a basic block.
Definition: InstrTypes.h:54
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
void print(raw_ostream &OS, const Module *) const override
print - Print out the internal state of the pass.
DomTreeNodeBase * getIDom() const
Represent the analysis usage information of a pass.
const Instruction & back() const
Definition: BasicBlock.h:266
static const unsigned End
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Divergence Analysis
static char ID
end namespace anonymous
void setPreservesAll()
Set by analyses that do not transform their input at all.
iterator_range< user_iterator > users()
Definition: Value.h:401
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
static void propagate(InstantiatedValue From, InstantiatedValue To, MatchState State, ReachabilitySet &ReachSet, std::vector< WorkListItem > &WorkList)
amdgpu Simplify well known AMD library false Value Value * Arg
Basic Alias true
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:108
#define I(x, y, z)
Definition: MD5.cpp:58
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
Definition: DenseSet.h:91
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
unsigned getNumSuccessors() const
Return the number of successors that this terminator has.
LLVM Value Representation.
Definition: Value.h:73
succ_range successors(BasicBlock *BB)
Definition: CFG.h:143
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:44
inst_range instructions(Function *F)
Definition: InstIterator.h:134
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:267
This pass exposes codegen information to IR-level passes.
INITIALIZE_PASS_BEGIN(DivergenceAnalysis, "divergence", "Divergence Analysis", false, true) INITIALIZE_PASS_END(DivergenceAnalysis
iterator_range< arg_iterator > args()
Definition: Function.h:621
const BasicBlock * getParent() const
Definition: Instruction.h:66