1 //===- DivergenceAnalysis.cpp ------ Divergence Analysis ------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines divergence analysis which determines whether a branch in a
11 // GPU program is divergent. It can help branch optimizations such as jump
12 // threading and loop unswitching to make better decisions.
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.
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
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
31 // Divergence Analysis
32 // Sampaio, Souza, Collange, Pereira
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.
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,
43 // %cond = icmp slt i32 %tid, 10
44 // br i1 %cond, label %then, label %else
50 // %a = phi i32 [ 0, %then ], [ 1, %else ]
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
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
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
64 //===----------------------------------------------------------------------===//
67 #include "llvm/IR/Dominators.h"
68 #include "llvm/ADT/DenseSet.h"
69 #include "llvm/Analysis/Passes.h"
70 #include "llvm/Analysis/PostDominators.h"
71 #include "llvm/Analysis/TargetTransformInfo.h"
72 #include "llvm/IR/Function.h"
73 #include "llvm/IR/InstIterator.h"
74 #include "llvm/IR/Instructions.h"
75 #include "llvm/IR/IntrinsicInst.h"
76 #include "llvm/IR/Value.h"
77 #include "llvm/Pass.h"
78 #include "llvm/Support/CommandLine.h"
79 #include "llvm/Support/Debug.h"
80 #include "llvm/Support/raw_ostream.h"
81 #include "llvm/Transforms/Scalar.h"
84 #define DEBUG_TYPE "divergence"
87 class DivergenceAnalysis : public FunctionPass {
91 DivergenceAnalysis() : FunctionPass(ID) {
92 initializeDivergenceAnalysisPass(*PassRegistry::getPassRegistry());
95 void getAnalysisUsage(AnalysisUsage &AU) const override {
96 AU.addRequired<DominatorTreeWrapperPass>();
97 AU.addRequired<PostDominatorTree>();
101 bool runOnFunction(Function &F) override;
103 // Print all divergent branches in the function.
104 void print(raw_ostream &OS, const Module *) const override;
106 // Returns true if V is divergent.
107 bool isDivergent(const Value *V) const { return DivergentValues.count(V); }
108 // Returns true if V is uniform/non-divergent.
109 bool isUniform(const Value *V) const { return !isDivergent(V); }
112 // Stores all divergent values.
113 DenseSet<const Value *> DivergentValues;
115 } // End of anonymous namespace
117 // Register this pass.
118 char DivergenceAnalysis::ID = 0;
119 INITIALIZE_PASS_BEGIN(DivergenceAnalysis, "divergence", "Divergence Analysis",
121 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
122 INITIALIZE_PASS_DEPENDENCY(PostDominatorTree)
123 INITIALIZE_PASS_END(DivergenceAnalysis, "divergence", "Divergence Analysis",
128 class DivergencePropagator {
130 DivergencePropagator(Function &F, TargetTransformInfo &TTI,
131 DominatorTree &DT, PostDominatorTree &PDT,
132 DenseSet<const Value *> &DV)
133 : F(F), TTI(TTI), DT(DT), PDT(PDT), DV(DV) {}
134 void populateWithSourcesOfDivergence();
138 // A helper function that explores data dependents of V.
139 void exploreDataDependency(Value *V);
140 // A helper function that explores sync dependents of TI.
141 void exploreSyncDependency(TerminatorInst *TI);
142 // Computes the influence region from Start to End. This region includes all
143 // basic blocks on any path from Start to End.
144 void computeInfluenceRegion(BasicBlock *Start, BasicBlock *End,
145 DenseSet<BasicBlock *> &InfluenceRegion);
146 // Finds all users of I that are outside the influence region, and add these
147 // users to Worklist.
148 void findUsersOutsideInfluenceRegion(
149 Instruction &I, const DenseSet<BasicBlock *> &InfluenceRegion);
152 TargetTransformInfo &TTI;
154 PostDominatorTree &PDT;
155 std::vector<Value *> Worklist; // Stack for DFS.
156 DenseSet<const Value *> &DV; // Stores all divergent values.
159 void DivergencePropagator::populateWithSourcesOfDivergence() {
162 for (auto &I : inst_range(F)) {
163 if (TTI.isSourceOfDivergence(&I)) {
164 Worklist.push_back(&I);
168 for (auto &Arg : F.args()) {
169 if (TTI.isSourceOfDivergence(&Arg)) {
170 Worklist.push_back(&Arg);
176 void DivergencePropagator::exploreSyncDependency(TerminatorInst *TI) {
177 // Propagation rule 1: if branch TI is divergent, all PHINodes in TI's
178 // immediate post dominator are divergent. This rule handles if-then-else
179 // patterns. For example,
185 // a = phi(a1, a2); // sync dependent on (tid < 5)
186 BasicBlock *ThisBB = TI->getParent();
187 BasicBlock *IPostDom = PDT.getNode(ThisBB)->getIDom()->getBlock();
188 if (IPostDom == nullptr)
191 for (auto I = IPostDom->begin(); isa<PHINode>(I); ++I) {
192 // A PHINode is uniform if it returns the same value no matter which path is
194 if (!cast<PHINode>(I)->hasConstantValue() && DV.insert(I).second)
195 Worklist.push_back(I);
198 // Propagation rule 2: if a value defined in a loop is used outside, the user
199 // is sync dependent on the condition of the loop exits that dominate the
200 // user. For example,
205 // if (foo(i)) ... // uniform
206 // } while (i < tid);
207 // if (bar(i)) ... // divergent
209 // A program may contain unstructured loops. Therefore, we cannot leverage
210 // LoopInfo, which only recognizes natural loops.
212 // The algorithm used here handles both natural and unstructured loops. Given
213 // a branch TI, we first compute its influence region, the union of all simple
214 // paths from TI to its immediate post dominator (IPostDom). Then, we search
215 // for all the values defined in the influence region but used outside. All
216 // these users are sync dependent on TI.
217 DenseSet<BasicBlock *> InfluenceRegion;
218 computeInfluenceRegion(ThisBB, IPostDom, InfluenceRegion);
219 // An insight that can speed up the search process is that all the in-region
220 // values that are used outside must dominate TI. Therefore, instead of
221 // searching every basic blocks in the influence region, we search all the
222 // dominators of TI until it is outside the influence region.
223 BasicBlock *InfluencedBB = ThisBB;
224 while (InfluenceRegion.count(InfluencedBB)) {
225 for (auto &I : *InfluencedBB)
226 findUsersOutsideInfluenceRegion(I, InfluenceRegion);
227 DomTreeNode *IDomNode = DT.getNode(InfluencedBB)->getIDom();
228 if (IDomNode == nullptr)
230 InfluencedBB = IDomNode->getBlock();
234 void DivergencePropagator::findUsersOutsideInfluenceRegion(
235 Instruction &I, const DenseSet<BasicBlock *> &InfluenceRegion) {
236 for (User *U : I.users()) {
237 Instruction *UserInst = cast<Instruction>(U);
238 if (!InfluenceRegion.count(UserInst->getParent())) {
239 if (DV.insert(UserInst).second)
240 Worklist.push_back(UserInst);
245 void DivergencePropagator::computeInfluenceRegion(
246 BasicBlock *Start, BasicBlock *End,
247 DenseSet<BasicBlock *> &InfluenceRegion) {
248 assert(PDT.properlyDominates(End, Start) &&
249 "End does not properly dominate Start");
250 std::vector<BasicBlock *> InfluenceStack;
251 InfluenceStack.push_back(Start);
252 InfluenceRegion.insert(Start);
253 while (!InfluenceStack.empty()) {
254 BasicBlock *BB = InfluenceStack.back();
255 InfluenceStack.pop_back();
256 for (BasicBlock *Succ : successors(BB)) {
257 if (End != Succ && InfluenceRegion.insert(Succ).second)
258 InfluenceStack.push_back(Succ);
263 void DivergencePropagator::exploreDataDependency(Value *V) {
264 // Follow def-use chains of V.
265 for (User *U : V->users()) {
266 Instruction *UserInst = cast<Instruction>(U);
267 if (DV.insert(UserInst).second)
268 Worklist.push_back(UserInst);
272 void DivergencePropagator::propagate() {
273 // Traverse the dependency graph using DFS.
274 while (!Worklist.empty()) {
275 Value *V = Worklist.back();
277 if (TerminatorInst *TI = dyn_cast<TerminatorInst>(V)) {
278 // Terminators with less than two successors won't introduce sync
279 // dependency. Ignore them.
280 if (TI->getNumSuccessors() > 1)
281 exploreSyncDependency(TI);
283 exploreDataDependency(V);
287 } /// end namespace anonymous
289 FunctionPass *llvm::createDivergenceAnalysisPass() {
290 return new DivergenceAnalysis();
293 bool DivergenceAnalysis::runOnFunction(Function &F) {
294 auto *TTIWP = getAnalysisIfAvailable<TargetTransformInfoWrapperPass>();
295 if (TTIWP == nullptr)
298 TargetTransformInfo &TTI = TTIWP->getTTI(F);
299 // Fast path: if the target does not have branch divergence, we do not mark
300 // any branch as divergent.
301 if (!TTI.hasBranchDivergence())
304 DivergentValues.clear();
305 DivergencePropagator DP(F, TTI,
306 getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
307 getAnalysis<PostDominatorTree>(), DivergentValues);
308 DP.populateWithSourcesOfDivergence();
313 void DivergenceAnalysis::print(raw_ostream &OS, const Module *) const {
314 if (DivergentValues.empty())
316 const Value *FirstDivergentValue = *DivergentValues.begin();
318 if (const Argument *Arg = dyn_cast<Argument>(FirstDivergentValue)) {
319 F = Arg->getParent();
320 } else if (const Instruction *I =
321 dyn_cast<Instruction>(FirstDivergentValue)) {
322 F = I->getParent()->getParent();
324 llvm_unreachable("Only arguments and instructions can be divergent");
327 // Dumps all divergent values in F, arguments and then instructions.
328 for (auto &Arg : F->args()) {
329 if (DivergentValues.count(&Arg))
330 OS << "DIVERGENT: " << Arg << "\n";
332 // Iterate instructions using inst_range to ensure a deterministic order.
333 for (auto &I : inst_range(F)) {
334 if (DivergentValues.count(&I))
335 OS << "DIVERGENT:" << I << "\n";