LLVM  9.0.0svn
LegacyDivergenceAnalysis.cpp
Go to the documentation of this file.
1 //===- LegacyDivergenceAnalysis.cpp --------- Legacy Divergence Analysis
2 //Implementation -==//
3 //
4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5 // See https://llvm.org/LICENSE.txt for license information.
6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
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/CFG.h"
71 #include "llvm/Analysis/Passes.h"
74 #include "llvm/IR/Dominators.h"
75 #include "llvm/IR/InstIterator.h"
76 #include "llvm/IR/Instructions.h"
77 #include "llvm/IR/Value.h"
78 #include "llvm/Support/Debug.h"
80 #include <vector>
81 using namespace llvm;
82 
83 #define DEBUG_TYPE "divergence"
84 
85 // transparently use the GPUDivergenceAnalysis
86 static cl::opt<bool> UseGPUDA("use-gpu-divergence-analysis", cl::init(false),
87  cl::Hidden,
88  cl::desc("turn the LegacyDivergenceAnalysis into "
89  "a wrapper for GPUDivergenceAnalysis"));
90 
91 namespace {
92 
94 public:
97  : F(F), TTI(TTI), DT(DT), PDT(PDT), DV(DV) {}
98  void populateWithSourcesOfDivergence();
99  void propagate();
100 
101 private:
102  // A helper function that explores data dependents of V.
103  void exploreDataDependency(Value *V);
104  // A helper function that explores sync dependents of TI.
105  void exploreSyncDependency(Instruction *TI);
106  // Computes the influence region from Start to End. This region includes all
107  // basic blocks on any simple path from Start to End.
108  void computeInfluenceRegion(BasicBlock *Start, BasicBlock *End,
109  DenseSet<BasicBlock *> &InfluenceRegion);
110  // Finds all users of I that are outside the influence region, and add these
111  // users to Worklist.
112  void findUsersOutsideInfluenceRegion(
113  Instruction &I, const DenseSet<BasicBlock *> &InfluenceRegion);
114 
115  Function &F;
116  TargetTransformInfo &TTI;
117  DominatorTree &DT;
119  std::vector<Value *> Worklist; // Stack for DFS.
120  DenseSet<const Value *> &DV; // Stores all divergent values.
121 };
122 
123 void DivergencePropagator::populateWithSourcesOfDivergence() {
124  Worklist.clear();
125  DV.clear();
126  for (auto &I : instructions(F)) {
127  if (TTI.isSourceOfDivergence(&I)) {
128  Worklist.push_back(&I);
129  DV.insert(&I);
130  }
131  }
132  for (auto &Arg : F.args()) {
133  if (TTI.isSourceOfDivergence(&Arg)) {
134  Worklist.push_back(&Arg);
135  DV.insert(&Arg);
136  }
137  }
138 }
139 
140 void DivergencePropagator::exploreSyncDependency(Instruction *TI) {
141  // Propagation rule 1: if branch TI is divergent, all PHINodes in TI's
142  // immediate post dominator are divergent. This rule handles if-then-else
143  // patterns. For example,
144  //
145  // if (tid < 5)
146  // a1 = 1;
147  // else
148  // a2 = 2;
149  // a = phi(a1, a2); // sync dependent on (tid < 5)
150  BasicBlock *ThisBB = TI->getParent();
151 
152  // Unreachable blocks may not be in the dominator tree.
153  if (!DT.isReachableFromEntry(ThisBB))
154  return;
155 
156  // If the function has no exit blocks or doesn't reach any exit blocks, the
157  // post dominator may be null.
158  DomTreeNode *ThisNode = PDT.getNode(ThisBB);
159  if (!ThisNode)
160  return;
161 
162  BasicBlock *IPostDom = ThisNode->getIDom()->getBlock();
163  if (IPostDom == nullptr)
164  return;
165 
166  for (auto I = IPostDom->begin(); isa<PHINode>(I); ++I) {
167  // A PHINode is uniform if it returns the same value no matter which path is
168  // taken.
169  if (!cast<PHINode>(I)->hasConstantOrUndefValue() && DV.insert(&*I).second)
170  Worklist.push_back(&*I);
171  }
172 
173  // Propagation rule 2: if a value defined in a loop is used outside, the user
174  // is sync dependent on the condition of the loop exits that dominate the
175  // user. For example,
176  //
177  // int i = 0;
178  // do {
179  // i++;
180  // if (foo(i)) ... // uniform
181  // } while (i < tid);
182  // if (bar(i)) ... // divergent
183  //
184  // A program may contain unstructured loops. Therefore, we cannot leverage
185  // LoopInfo, which only recognizes natural loops.
186  //
187  // The algorithm used here handles both natural and unstructured loops. Given
188  // a branch TI, we first compute its influence region, the union of all simple
189  // paths from TI to its immediate post dominator (IPostDom). Then, we search
190  // for all the values defined in the influence region but used outside. All
191  // these users are sync dependent on TI.
192  DenseSet<BasicBlock *> InfluenceRegion;
193  computeInfluenceRegion(ThisBB, IPostDom, InfluenceRegion);
194  // An insight that can speed up the search process is that all the in-region
195  // values that are used outside must dominate TI. Therefore, instead of
196  // searching every basic blocks in the influence region, we search all the
197  // dominators of TI until it is outside the influence region.
198  BasicBlock *InfluencedBB = ThisBB;
199  while (InfluenceRegion.count(InfluencedBB)) {
200  for (auto &I : *InfluencedBB)
201  findUsersOutsideInfluenceRegion(I, InfluenceRegion);
202  DomTreeNode *IDomNode = DT.getNode(InfluencedBB)->getIDom();
203  if (IDomNode == nullptr)
204  break;
205  InfluencedBB = IDomNode->getBlock();
206  }
207 }
208 
209 void DivergencePropagator::findUsersOutsideInfluenceRegion(
210  Instruction &I, const DenseSet<BasicBlock *> &InfluenceRegion) {
211  for (User *U : I.users()) {
212  Instruction *UserInst = cast<Instruction>(U);
213  if (!InfluenceRegion.count(UserInst->getParent())) {
214  if (DV.insert(UserInst).second)
215  Worklist.push_back(UserInst);
216  }
217  }
218 }
219 
220 // A helper function for computeInfluenceRegion that adds successors of "ThisBB"
221 // to the influence region.
222 static void
223 addSuccessorsToInfluenceRegion(BasicBlock *ThisBB, BasicBlock *End,
224  DenseSet<BasicBlock *> &InfluenceRegion,
225  std::vector<BasicBlock *> &InfluenceStack) {
226  for (BasicBlock *Succ : successors(ThisBB)) {
227  if (Succ != End && InfluenceRegion.insert(Succ).second)
228  InfluenceStack.push_back(Succ);
229  }
230 }
231 
232 void DivergencePropagator::computeInfluenceRegion(
233  BasicBlock *Start, BasicBlock *End,
234  DenseSet<BasicBlock *> &InfluenceRegion) {
235  assert(PDT.properlyDominates(End, Start) &&
236  "End does not properly dominate Start");
237 
238  // The influence region starts from the end of "Start" to the beginning of
239  // "End". Therefore, "Start" should not be in the region unless "Start" is in
240  // a loop that doesn't contain "End".
241  std::vector<BasicBlock *> InfluenceStack;
242  addSuccessorsToInfluenceRegion(Start, End, InfluenceRegion, InfluenceStack);
243  while (!InfluenceStack.empty()) {
244  BasicBlock *BB = InfluenceStack.back();
245  InfluenceStack.pop_back();
246  addSuccessorsToInfluenceRegion(BB, End, InfluenceRegion, InfluenceStack);
247  }
248 }
249 
250 void DivergencePropagator::exploreDataDependency(Value *V) {
251  // Follow def-use chains of V.
252  for (User *U : V->users()) {
253  Instruction *UserInst = cast<Instruction>(U);
254  if (!TTI.isAlwaysUniform(U) && DV.insert(UserInst).second)
255  Worklist.push_back(UserInst);
256  }
257 }
258 
260  // Traverse the dependency graph using DFS.
261  while (!Worklist.empty()) {
262  Value *V = Worklist.back();
263  Worklist.pop_back();
264  if (Instruction *I = dyn_cast<Instruction>(V)) {
265  // Terminators with less than two successors won't introduce sync
266  // dependency. Ignore them.
267  if (I->isTerminator() && I->getNumSuccessors() > 1)
268  exploreSyncDependency(I);
269  }
270  exploreDataDependency(V);
271  }
272 }
273 
274 } // namespace
275 
276 // Register this pass.
279  "Legacy Divergence Analysis", false, true)
284  "Legacy Divergence Analysis", false, true)
285 
287  return new LegacyDivergenceAnalysis();
288 }
289 
293  if (UseGPUDA)
295  AU.setPreservesAll();
296 }
297 
298 bool LegacyDivergenceAnalysis::shouldUseGPUDivergenceAnalysis(
299  const Function &F) const {
300  if (!UseGPUDA)
301  return false;
302 
303  // GPUDivergenceAnalysis requires a reducible CFG.
304  auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
305  using RPOTraversal = ReversePostOrderTraversal<const Function *>;
306  RPOTraversal FuncRPOT(&F);
307  return !containsIrreducibleCFG<const BasicBlock *, const RPOTraversal,
308  const LoopInfo>(FuncRPOT, LI);
309 }
310 
312  auto *TTIWP = getAnalysisIfAvailable<TargetTransformInfoWrapperPass>();
313  if (TTIWP == nullptr)
314  return false;
315 
316  TargetTransformInfo &TTI = TTIWP->getTTI(F);
317  // Fast path: if the target does not have branch divergence, we do not mark
318  // any branch as divergent.
319  if (!TTI.hasBranchDivergence())
320  return false;
321 
322  DivergentValues.clear();
323  gpuDA = nullptr;
324 
325  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
326  auto &PDT = getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
327 
328  if (shouldUseGPUDivergenceAnalysis(F)) {
329  // run the new GPU divergence analysis
330  auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
331  gpuDA = llvm::make_unique<GPUDivergenceAnalysis>(F, DT, PDT, LI, TTI);
332 
333  } else {
334  // run LLVM's existing DivergenceAnalysis
335  DivergencePropagator DP(F, TTI, DT, PDT, DivergentValues);
336  DP.populateWithSourcesOfDivergence();
337  DP.propagate();
338  }
339 
340  LLVM_DEBUG(dbgs() << "\nAfter divergence analysis on " << F.getName()
341  << ":\n";
342  print(dbgs(), F.getParent()));
343 
344  return false;
345 }
346 
348  if (gpuDA) {
349  return gpuDA->isDivergent(*V);
350  }
351  return DivergentValues.count(V);
352 }
353 
355  if ((!gpuDA || !gpuDA->hasDivergence()) && DivergentValues.empty())
356  return;
357 
358  const Function *F = nullptr;
359  if (!DivergentValues.empty()) {
360  const Value *FirstDivergentValue = *DivergentValues.begin();
361  if (const Argument *Arg = dyn_cast<Argument>(FirstDivergentValue)) {
362  F = Arg->getParent();
363  } else if (const Instruction *I =
364  dyn_cast<Instruction>(FirstDivergentValue)) {
365  F = I->getParent()->getParent();
366  } else {
367  llvm_unreachable("Only arguments and instructions can be divergent");
368  }
369  } else if (gpuDA) {
370  F = &gpuDA->getFunction();
371  }
372  if (!F)
373  return;
374 
375  // Dumps all divergent values in F, arguments and then instructions.
376  for (auto &Arg : F->args()) {
377  OS << (isDivergent(&Arg) ? "DIVERGENT: " : " ");
378  OS << Arg << "\n";
379  }
380  // Iterate instructions using instructions() to ensure a deterministic order.
381  for (auto BI = F->begin(), BE = F->end(); BI != BE; ++BI) {
382  auto &BB = *BI;
383  OS << "\n " << BB.getName() << ":\n";
384  for (auto &I : BB.instructionsWithoutDebug()) {
385  OS << (isDivergent(&I) ? "DIVERGENT: " : " ");
386  OS << I << "\n";
387  }
388  }
389  OS << "\n";
390 }
const Function & getFunction() const
Definition: Function.h:133
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
void print(raw_ostream &OS, const Module *) const override
print - Print out the internal state of the pass.
bool isDivergent(const Value *V) const
This class represents an incoming formal argument to a Function.
Definition: Argument.h:29
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
iterator end()
Definition: Function.h:674
static cl::opt< bool > UseGPUDA("use-gpu-divergence-analysis", cl::init(false), cl::Hidden, cl::desc("turn the LegacyDivergenceAnalysis into " "a wrapper for GPUDivergenceAnalysis"))
bool isTerminator() const
Definition: Instruction.h:128
bool properlyDominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
properlyDominates - Returns true iff A dominates B and A != B.
F(f)
const PostDominatorTree & PDT
block Block Frequency true
INITIALIZE_PASS_BEGIN(LegacyDivergenceAnalysis, "divergence", "Legacy Divergence Analysis", false, true) INITIALIZE_PASS_END(LegacyDivergenceAnalysis
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:299
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:268
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
bool hasBranchDivergence() const
Return true if branch divergence exists.
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass...
bool containsIrreducibleCFG(RPOTraversalT &RPOTraversal, const LoopInfoT &LI)
Return true if the control flow in RPOTraversal is irreducible.
Definition: CFG.h:143
iterator begin()
Definition: Function.h:672
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
unsigned getNumSuccessors() const
Return the number of successors that this instruction has.
NodeT * getBlock() const
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
iterator_range< filter_iterator< BasicBlock::const_iterator, std::function< bool(const Instruction &)> > > instructionsWithoutDebug() const
Return a const iterator range over the instructions in the block, skipping any debug instructions...
Definition: BasicBlock.cpp:94
DomTreeNodeBase * getIDom() const
DivergencePropagator(const FunctionRPOT &FuncRPOT, const DominatorTree &DT, const PostDominatorTree &PDT, const LoopInfo &LI)
Represent the analysis usage information of a pass.
const Instruction & back() const
Definition: BasicBlock.h:282
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
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.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
void setPreservesAll()
Set by analyses that do not transform their input at all.
iterator_range< user_iterator > users()
Definition: Value.h:399
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)
FunctionPass * createLegacyDivergenceAnalysisPass()
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:106
#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())
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:575
LLVM Value Representation.
Definition: Value.h:72
succ_range successors(Instruction *I)
Definition: CFG.h:259
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
The legacy pass manager&#39;s analysis pass to compute loop information.
Definition: LoopInfo.h:1138
inst_range instructions(Function *F)
Definition: InstIterator.h:133
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:259
This pass exposes codegen information to IR-level passes.
#define LLVM_DEBUG(X)
Definition: Debug.h:122
iterator_range< arg_iterator > args()
Definition: Function.h:705
const BasicBlock * getParent() const
Definition: Instruction.h:66