LLVM  10.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:
98  : F(F), TTI(TTI), DT(DT), PDT(PDT), DV(DV), DU(DU) {}
99  void populateWithSourcesOfDivergence();
100  void propagate();
101 
102 private:
103  // A helper function that explores data dependents of V.
104  void exploreDataDependency(Value *V);
105  // A helper function that explores sync dependents of TI.
106  void exploreSyncDependency(Instruction *TI);
107  // Computes the influence region from Start to End. This region includes all
108  // basic blocks on any simple path from Start to End.
109  void computeInfluenceRegion(BasicBlock *Start, BasicBlock *End,
110  DenseSet<BasicBlock *> &InfluenceRegion);
111  // Finds all users of I that are outside the influence region, and add these
112  // users to Worklist.
113  void findUsersOutsideInfluenceRegion(
114  Instruction &I, const DenseSet<BasicBlock *> &InfluenceRegion);
115 
116  Function &F;
117  TargetTransformInfo &TTI;
118  DominatorTree &DT;
120  std::vector<Value *> Worklist; // Stack for DFS.
121  DenseSet<const Value *> &DV; // Stores all divergent values.
122  DenseSet<const Use *> &DU; // Stores divergent uses of possibly uniform
123  // values.
124 };
125 
126 void DivergencePropagator::populateWithSourcesOfDivergence() {
127  Worklist.clear();
128  DV.clear();
129  DU.clear();
130  for (auto &I : instructions(F)) {
131  if (TTI.isSourceOfDivergence(&I)) {
132  Worklist.push_back(&I);
133  DV.insert(&I);
134  }
135  }
136  for (auto &Arg : F.args()) {
137  if (TTI.isSourceOfDivergence(&Arg)) {
138  Worklist.push_back(&Arg);
139  DV.insert(&Arg);
140  }
141  }
142 }
143 
144 void DivergencePropagator::exploreSyncDependency(Instruction *TI) {
145  // Propagation rule 1: if branch TI is divergent, all PHINodes in TI's
146  // immediate post dominator are divergent. This rule handles if-then-else
147  // patterns. For example,
148  //
149  // if (tid < 5)
150  // a1 = 1;
151  // else
152  // a2 = 2;
153  // a = phi(a1, a2); // sync dependent on (tid < 5)
154  BasicBlock *ThisBB = TI->getParent();
155 
156  // Unreachable blocks may not be in the dominator tree.
157  if (!DT.isReachableFromEntry(ThisBB))
158  return;
159 
160  // If the function has no exit blocks or doesn't reach any exit blocks, the
161  // post dominator may be null.
162  DomTreeNode *ThisNode = PDT.getNode(ThisBB);
163  if (!ThisNode)
164  return;
165 
166  BasicBlock *IPostDom = ThisNode->getIDom()->getBlock();
167  if (IPostDom == nullptr)
168  return;
169 
170  for (auto I = IPostDom->begin(); isa<PHINode>(I); ++I) {
171  // A PHINode is uniform if it returns the same value no matter which path is
172  // taken.
173  if (!cast<PHINode>(I)->hasConstantOrUndefValue() && DV.insert(&*I).second)
174  Worklist.push_back(&*I);
175  }
176 
177  // Propagation rule 2: if a value defined in a loop is used outside, the user
178  // is sync dependent on the condition of the loop exits that dominate the
179  // user. For example,
180  //
181  // int i = 0;
182  // do {
183  // i++;
184  // if (foo(i)) ... // uniform
185  // } while (i < tid);
186  // if (bar(i)) ... // divergent
187  //
188  // A program may contain unstructured loops. Therefore, we cannot leverage
189  // LoopInfo, which only recognizes natural loops.
190  //
191  // The algorithm used here handles both natural and unstructured loops. Given
192  // a branch TI, we first compute its influence region, the union of all simple
193  // paths from TI to its immediate post dominator (IPostDom). Then, we search
194  // for all the values defined in the influence region but used outside. All
195  // these users are sync dependent on TI.
196  DenseSet<BasicBlock *> InfluenceRegion;
197  computeInfluenceRegion(ThisBB, IPostDom, InfluenceRegion);
198  // An insight that can speed up the search process is that all the in-region
199  // values that are used outside must dominate TI. Therefore, instead of
200  // searching every basic blocks in the influence region, we search all the
201  // dominators of TI until it is outside the influence region.
202  BasicBlock *InfluencedBB = ThisBB;
203  while (InfluenceRegion.count(InfluencedBB)) {
204  for (auto &I : *InfluencedBB) {
205  if (!DV.count(&I))
206  findUsersOutsideInfluenceRegion(I, InfluenceRegion);
207  }
208  DomTreeNode *IDomNode = DT.getNode(InfluencedBB)->getIDom();
209  if (IDomNode == nullptr)
210  break;
211  InfluencedBB = IDomNode->getBlock();
212  }
213 }
214 
215 void DivergencePropagator::findUsersOutsideInfluenceRegion(
216  Instruction &I, const DenseSet<BasicBlock *> &InfluenceRegion) {
217  for (Use &Use : I.uses()) {
218  Instruction *UserInst = cast<Instruction>(Use.getUser());
219  if (!InfluenceRegion.count(UserInst->getParent())) {
220  DU.insert(&Use);
221  if (DV.insert(UserInst).second)
222  Worklist.push_back(UserInst);
223  }
224  }
225 }
226 
227 // A helper function for computeInfluenceRegion that adds successors of "ThisBB"
228 // to the influence region.
229 static void
230 addSuccessorsToInfluenceRegion(BasicBlock *ThisBB, BasicBlock *End,
231  DenseSet<BasicBlock *> &InfluenceRegion,
232  std::vector<BasicBlock *> &InfluenceStack) {
233  for (BasicBlock *Succ : successors(ThisBB)) {
234  if (Succ != End && InfluenceRegion.insert(Succ).second)
235  InfluenceStack.push_back(Succ);
236  }
237 }
238 
239 void DivergencePropagator::computeInfluenceRegion(
240  BasicBlock *Start, BasicBlock *End,
241  DenseSet<BasicBlock *> &InfluenceRegion) {
242  assert(PDT.properlyDominates(End, Start) &&
243  "End does not properly dominate Start");
244 
245  // The influence region starts from the end of "Start" to the beginning of
246  // "End". Therefore, "Start" should not be in the region unless "Start" is in
247  // a loop that doesn't contain "End".
248  std::vector<BasicBlock *> InfluenceStack;
249  addSuccessorsToInfluenceRegion(Start, End, InfluenceRegion, InfluenceStack);
250  while (!InfluenceStack.empty()) {
251  BasicBlock *BB = InfluenceStack.back();
252  InfluenceStack.pop_back();
253  addSuccessorsToInfluenceRegion(BB, End, InfluenceRegion, InfluenceStack);
254  }
255 }
256 
257 void DivergencePropagator::exploreDataDependency(Value *V) {
258  // Follow def-use chains of V.
259  for (User *U : V->users()) {
260  if (!TTI.isAlwaysUniform(U) && DV.insert(U).second)
261  Worklist.push_back(U);
262  }
263 }
264 
266  // Traverse the dependency graph using DFS.
267  while (!Worklist.empty()) {
268  Value *V = Worklist.back();
269  Worklist.pop_back();
270  if (Instruction *I = dyn_cast<Instruction>(V)) {
271  // Terminators with less than two successors won't introduce sync
272  // dependency. Ignore them.
273  if (I->isTerminator() && I->getNumSuccessors() > 1)
274  exploreSyncDependency(I);
275  }
276  exploreDataDependency(V);
277  }
278 }
279 
280 } // namespace
281 
282 // Register this pass.
285  "Legacy Divergence Analysis", false, true)
290  "Legacy Divergence Analysis", false, true)
291 
293  return new LegacyDivergenceAnalysis();
294 }
295 
299  if (UseGPUDA)
301  AU.setPreservesAll();
302 }
303 
304 bool LegacyDivergenceAnalysis::shouldUseGPUDivergenceAnalysis(
305  const Function &F) const {
306  if (!UseGPUDA)
307  return false;
308 
309  // GPUDivergenceAnalysis requires a reducible CFG.
310  auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
311  using RPOTraversal = ReversePostOrderTraversal<const Function *>;
312  RPOTraversal FuncRPOT(&F);
313  return !containsIrreducibleCFG<const BasicBlock *, const RPOTraversal,
314  const LoopInfo>(FuncRPOT, LI);
315 }
316 
318  auto *TTIWP = getAnalysisIfAvailable<TargetTransformInfoWrapperPass>();
319  if (TTIWP == nullptr)
320  return false;
321 
322  TargetTransformInfo &TTI = TTIWP->getTTI(F);
323  // Fast path: if the target does not have branch divergence, we do not mark
324  // any branch as divergent.
325  if (!TTI.hasBranchDivergence())
326  return false;
327 
328  DivergentValues.clear();
329  DivergentUses.clear();
330  gpuDA = nullptr;
331 
332  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
333  auto &PDT = getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
334 
335  if (shouldUseGPUDivergenceAnalysis(F)) {
336  // run the new GPU divergence analysis
337  auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
338  gpuDA = std::make_unique<GPUDivergenceAnalysis>(F, DT, PDT, LI, TTI);
339 
340  } else {
341  // run LLVM's existing DivergenceAnalysis
342  DivergencePropagator DP(F, TTI, DT, PDT, DivergentValues, DivergentUses);
343  DP.populateWithSourcesOfDivergence();
344  DP.propagate();
345  }
346 
347  LLVM_DEBUG(dbgs() << "\nAfter divergence analysis on " << F.getName()
348  << ":\n";
349  print(dbgs(), F.getParent()));
350 
351  return false;
352 }
353 
355  if (gpuDA) {
356  return gpuDA->isDivergent(*V);
357  }
358  return DivergentValues.count(V);
359 }
360 
362  if (gpuDA) {
363  return gpuDA->isDivergentUse(*U);
364  }
365  return DivergentValues.count(U->get()) || DivergentUses.count(U);
366 }
367 
369  if ((!gpuDA || !gpuDA->hasDivergence()) && DivergentValues.empty())
370  return;
371 
372  const Function *F = nullptr;
373  if (!DivergentValues.empty()) {
374  const Value *FirstDivergentValue = *DivergentValues.begin();
375  if (const Argument *Arg = dyn_cast<Argument>(FirstDivergentValue)) {
376  F = Arg->getParent();
377  } else if (const Instruction *I =
378  dyn_cast<Instruction>(FirstDivergentValue)) {
379  F = I->getParent()->getParent();
380  } else {
381  llvm_unreachable("Only arguments and instructions can be divergent");
382  }
383  } else if (gpuDA) {
384  F = &gpuDA->getFunction();
385  }
386  if (!F)
387  return;
388 
389  // Dumps all divergent values in F, arguments and then instructions.
390  for (auto &Arg : F->args()) {
391  OS << (isDivergent(&Arg) ? "DIVERGENT: " : " ");
392  OS << Arg << "\n";
393  }
394  // Iterate instructions using instructions() to ensure a deterministic order.
395  for (auto BI = F->begin(), BE = F->end(); BI != BE; ++BI) {
396  auto &BB = *BI;
397  OS << "\n " << BB.getName() << ":\n";
398  for (auto &I : BB.instructionsWithoutDebug()) {
399  OS << (isDivergent(&I) ? "DIVERGENT: " : " ");
400  OS << I << "\n";
401  }
402  }
403  OS << "\n";
404 }
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.
iterator_range< use_iterator > uses()
Definition: Value.h:375
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:66
iterator end()
Definition: Function.h:687
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:273
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
bool hasBranchDivergence() const
Return true if branch divergence exists.
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
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:145
User * getUser() const LLVM_READONLY
Returns the User that contains this Use.
Definition: Use.cpp:40
iterator begin()
Definition: Function.h:685
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:287
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:420
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:74
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:1208
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:724
const BasicBlock * getParent() const
Definition: Instruction.h:66