LLVM 17.0.0git
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
69#include "llvm/Analysis/CFG.h"
75#include "llvm/IR/Dominators.h"
78#include "llvm/IR/Value.h"
81#include "llvm/Support/Debug.h"
83#include <vector>
84using namespace llvm;
85
86#define DEBUG_TYPE "divergence"
87
88// transparently use the GPUDivergenceAnalysis
89static cl::opt<bool> UseGPUDA("use-gpu-divergence-analysis", cl::init(false),
91 cl::desc("turn the LegacyDivergenceAnalysis into "
92 "a wrapper for GPUDivergenceAnalysis"));
93
94namespace {
95
97public:
101 : F(F), TTI(TTI), DT(DT), PDT(PDT), DV(DV), DU(DU) {}
102 void populateWithSourcesOfDivergence();
103 void propagate();
104
105private:
106 // A helper function that explores data dependents of V.
107 void exploreDataDependency(Value *V);
108 // A helper function that explores sync dependents of TI.
109 void exploreSyncDependency(Instruction *TI);
110 // Computes the influence region from Start to End. This region includes all
111 // basic blocks on any simple path from Start to End.
112 void computeInfluenceRegion(BasicBlock *Start, BasicBlock *End,
113 DenseSet<BasicBlock *> &InfluenceRegion);
114 // Finds all users of I that are outside the influence region, and add these
115 // users to Worklist.
116 void findUsersOutsideInfluenceRegion(
117 Instruction &I, const DenseSet<BasicBlock *> &InfluenceRegion);
118
119 Function &F;
123 std::vector<Value *> Worklist; // Stack for DFS.
124 DenseSet<const Value *> &DV; // Stores all divergent values.
125 DenseSet<const Use *> &DU; // Stores divergent uses of possibly uniform
126 // values.
127};
128
129void DivergencePropagator::populateWithSourcesOfDivergence() {
130 Worklist.clear();
131 DV.clear();
132 DU.clear();
133 for (auto &I : instructions(F)) {
134 if (TTI.isSourceOfDivergence(&I)) {
135 Worklist.push_back(&I);
136 DV.insert(&I);
137 }
138 }
139 for (auto &Arg : F.args()) {
141 Worklist.push_back(&Arg);
142 DV.insert(&Arg);
143 }
144 }
145}
146
147void DivergencePropagator::exploreSyncDependency(Instruction *TI) {
148 // Propagation rule 1: if branch TI is divergent, all PHINodes in TI's
149 // immediate post dominator are divergent. This rule handles if-then-else
150 // patterns. For example,
151 //
152 // if (tid < 5)
153 // a1 = 1;
154 // else
155 // a2 = 2;
156 // a = phi(a1, a2); // sync dependent on (tid < 5)
157 BasicBlock *ThisBB = TI->getParent();
158
159 // Unreachable blocks may not be in the dominator tree.
160 if (!DT.isReachableFromEntry(ThisBB))
161 return;
162
163 // If the function has no exit blocks or doesn't reach any exit blocks, the
164 // post dominator may be null.
165 DomTreeNode *ThisNode = PDT.getNode(ThisBB);
166 if (!ThisNode)
167 return;
168
169 BasicBlock *IPostDom = ThisNode->getIDom()->getBlock();
170 if (IPostDom == nullptr)
171 return;
172
173 for (auto I = IPostDom->begin(); isa<PHINode>(I); ++I) {
174 // A PHINode is uniform if it returns the same value no matter which path is
175 // taken.
176 if (!cast<PHINode>(I)->hasConstantOrUndefValue() && DV.insert(&*I).second)
177 Worklist.push_back(&*I);
178 }
179
180 // Propagation rule 2: if a value defined in a loop is used outside, the user
181 // is sync dependent on the condition of the loop exits that dominate the
182 // user. For example,
183 //
184 // int i = 0;
185 // do {
186 // i++;
187 // if (foo(i)) ... // uniform
188 // } while (i < tid);
189 // if (bar(i)) ... // divergent
190 //
191 // A program may contain unstructured loops. Therefore, we cannot leverage
192 // LoopInfo, which only recognizes natural loops.
193 //
194 // The algorithm used here handles both natural and unstructured loops. Given
195 // a branch TI, we first compute its influence region, the union of all simple
196 // paths from TI to its immediate post dominator (IPostDom). Then, we search
197 // for all the values defined in the influence region but used outside. All
198 // these users are sync dependent on TI.
199 DenseSet<BasicBlock *> InfluenceRegion;
200 computeInfluenceRegion(ThisBB, IPostDom, InfluenceRegion);
201 // An insight that can speed up the search process is that all the in-region
202 // values that are used outside must dominate TI. Therefore, instead of
203 // searching every basic blocks in the influence region, we search all the
204 // dominators of TI until it is outside the influence region.
205 BasicBlock *InfluencedBB = ThisBB;
206 while (InfluenceRegion.count(InfluencedBB)) {
207 for (auto &I : *InfluencedBB) {
208 if (!DV.count(&I))
209 findUsersOutsideInfluenceRegion(I, InfluenceRegion);
210 }
211 DomTreeNode *IDomNode = DT.getNode(InfluencedBB)->getIDom();
212 if (IDomNode == nullptr)
213 break;
214 InfluencedBB = IDomNode->getBlock();
215 }
216}
217
218void DivergencePropagator::findUsersOutsideInfluenceRegion(
219 Instruction &I, const DenseSet<BasicBlock *> &InfluenceRegion) {
220 for (Use &Use : I.uses()) {
221 Instruction *UserInst = cast<Instruction>(Use.getUser());
222 if (!InfluenceRegion.count(UserInst->getParent())) {
223 DU.insert(&Use);
224 if (DV.insert(UserInst).second)
225 Worklist.push_back(UserInst);
226 }
227 }
228}
229
230// A helper function for computeInfluenceRegion that adds successors of "ThisBB"
231// to the influence region.
232static void
233addSuccessorsToInfluenceRegion(BasicBlock *ThisBB, BasicBlock *End,
234 DenseSet<BasicBlock *> &InfluenceRegion,
235 std::vector<BasicBlock *> &InfluenceStack) {
236 for (BasicBlock *Succ : successors(ThisBB)) {
237 if (Succ != End && InfluenceRegion.insert(Succ).second)
238 InfluenceStack.push_back(Succ);
239 }
240}
241
242void DivergencePropagator::computeInfluenceRegion(
243 BasicBlock *Start, BasicBlock *End,
244 DenseSet<BasicBlock *> &InfluenceRegion) {
245 assert(PDT.properlyDominates(End, Start) &&
246 "End does not properly dominate Start");
247
248 // The influence region starts from the end of "Start" to the beginning of
249 // "End". Therefore, "Start" should not be in the region unless "Start" is in
250 // a loop that doesn't contain "End".
251 std::vector<BasicBlock *> InfluenceStack;
252 addSuccessorsToInfluenceRegion(Start, End, InfluenceRegion, InfluenceStack);
253 while (!InfluenceStack.empty()) {
254 BasicBlock *BB = InfluenceStack.back();
255 InfluenceStack.pop_back();
256 addSuccessorsToInfluenceRegion(BB, End, InfluenceRegion, InfluenceStack);
257 }
258}
259
260void DivergencePropagator::exploreDataDependency(Value *V) {
261 // Follow def-use chains of V.
262 for (User *U : V->users()) {
263 if (!TTI.isAlwaysUniform(U) && DV.insert(U).second)
264 Worklist.push_back(U);
265 }
266}
267
268void DivergencePropagator::propagate() {
269 // Traverse the dependency graph using DFS.
270 while (!Worklist.empty()) {
271 Value *V = Worklist.back();
272 Worklist.pop_back();
273 if (Instruction *I = dyn_cast<Instruction>(V)) {
274 // Terminators with less than two successors won't introduce sync
275 // dependency. Ignore them.
276 if (I->isTerminator() && I->getNumSuccessors() > 1)
277 exploreSyncDependency(I);
278 }
279 exploreDataDependency(V);
280 }
281}
282
283} // namespace
284
285// Register this pass.
289}
291 "Legacy Divergence Analysis", false, true)
296 "Legacy Divergence Analysis", false, true)
297
299 return new LegacyDivergenceAnalysis();
300}
301
303 const Function &F, const TargetTransformInfo &TTI, const LoopInfo &LI) {
305 return false;
306
307 // GPUDivergenceAnalysis requires a reducible CFG.
309 RPOTraversal FuncRPOT(&F);
310 return !containsIrreducibleCFG<const BasicBlock *, const RPOTraversal,
311 const LoopInfo>(FuncRPOT, LI);
312}
313
318 const llvm::LoopInfo &LI) {
320 // run the new GPU divergence analysis
321 gpuDA = std::make_unique<DivergenceInfo>(F, DT, PDT, LI, TTI,
322 /* KnownReducible = */ true);
323
324 } else {
325 // run LLVM's existing DivergenceAnalysis
327 DP.populateWithSourcesOfDivergence();
328 DP.propagate();
329 }
330}
331
333 if (gpuDA) {
334 return gpuDA->isDivergent(*V);
335 }
336 return DivergentValues.count(V);
337}
338
340 if (gpuDA) {
341 return gpuDA->isDivergentUse(*U);
342 }
343 return DivergentValues.count(U->get()) || DivergentUses.count(U);
344}
345
347 const Module *) const {
348 if ((!gpuDA || !gpuDA->hasDivergence()) && DivergentValues.empty())
349 return;
350
351 const Function *F = nullptr;
352 if (!DivergentValues.empty()) {
353 const Value *FirstDivergentValue = *DivergentValues.begin();
354 if (const Argument *Arg = dyn_cast<Argument>(FirstDivergentValue)) {
355 F = Arg->getParent();
356 } else if (const Instruction *I =
357 dyn_cast<Instruction>(FirstDivergentValue)) {
358 F = I->getParent()->getParent();
359 } else {
360 llvm_unreachable("Only arguments and instructions can be divergent");
361 }
362 } else if (gpuDA) {
363 F = &gpuDA->getFunction();
364 }
365 if (!F)
366 return;
367
368 // Dumps all divergent values in F, arguments and then instructions.
369 for (const auto &Arg : F->args()) {
370 OS << (isDivergent(&Arg) ? "DIVERGENT: " : " ");
371 OS << Arg << "\n";
372 }
373 // Iterate instructions using instructions() to ensure a deterministic order.
374 for (const BasicBlock &BB : *F) {
375 OS << "\n " << BB.getName() << ":\n";
376 for (const auto &I : BB.instructionsWithoutDebug()) {
377 OS << (isDivergent(&I) ? "DIVERGENT: " : " ");
378 OS << I << "\n";
379 }
380 }
381 OS << "\n";
382}
383
388 AU.setPreservesAll();
389}
390
392 auto *TTIWP = getAnalysisIfAvailable<TargetTransformInfoWrapperPass>();
393 if (TTIWP == nullptr)
394 return false;
395
396 TargetTransformInfo &TTI = TTIWP->getTTI(F);
397 // Fast path: if the target does not have branch divergence, we do not mark
398 // any branch as divergent.
400 return false;
401
403 DivergentUses.clear();
404 gpuDA = nullptr;
405
406 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
407 auto &PDT = getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
408 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
410 LLVM_DEBUG(dbgs() << "\nAfter divergence analysis on " << F.getName()
411 << ":\n";
413
414 return false;
415}
416
419 auto &TTI = AM.getResult<TargetIRAnalysis>(F);
421 return PreservedAnalyses::all();
422
423 DivergentValues.clear();
424 DivergentUses.clear();
425 gpuDA = nullptr;
426
427 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
428 auto &PDT = AM.getResult<PostDominatorTreeAnalysis>(F);
429 auto &LI = AM.getResult<LoopAnalysis>(F);
431 LLVM_DEBUG(dbgs() << "\nAfter divergence analysis on " << F.getName()
432 << ":\n";
434 return PreservedAnalyses::all();
435}
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
basic Basic Alias true
block Block Frequency Analysis
#define LLVM_DEBUG(X)
Definition: Debug.h:101
static cl::opt< bool > UseGPUDA("use-gpu-divergence-analysis", cl::init(false), cl::Hidden, cl::desc("turn the LegacyDivergenceAnalysis into " "a wrapper for GPUDivergenceAnalysis"))
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
print must be executed print the must be executed context for all instructions
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:55
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:59
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:52
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
raw_pwrite_stream & OS
This pass exposes codegen information to IR-level passes.
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:774
Represent the analysis usage information of a pass.
void setPreservesAll()
Set by analyses that do not transform their input at all.
AnalysisUsage & addRequiredTransitive()
This class represents an incoming formal argument to a Function.
Definition: Argument.h:28
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:323
iterator_range< filter_iterator< BasicBlock::const_iterator, std::function< bool(const Instruction &)> > > instructionsWithoutDebug(bool SkipPseudoOp=true) const
Return a const iterator range over the instructions in the block, skipping any debug instructions.
Definition: BasicBlock.cpp:103
const Instruction & back() const
Definition: BasicBlock.h:337
Implements a dense probed hash-table based set.
Definition: DenseSet.h:271
Compute divergence starting with a divergent branch.
DomTreeNodeBase * getIDom() const
NodeT * getBlock() const
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:279
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:314
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
const BasicBlock * getParent() const
Definition: Instruction.h:90
std::unique_ptr< DivergenceInfo > gpuDA
void run(Function &F, TargetTransformInfo &TTI, DominatorTree &DT, PostDominatorTree &PDT, const LoopInfo &LI)
bool shouldUseGPUDivergenceAnalysis(const Function &F, const TargetTransformInfo &TTI, const LoopInfo &LI)
void print(raw_ostream &OS, const Module *) const
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:1268
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:1293
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Analysis pass which computes a PostDominatorTree.
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
Analysis pass providing the TargetTransformInfo.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
bool isAlwaysUniform(const Value *V) const
bool hasBranchDivergence() const
Return true if branch divergence exists.
bool isSourceOfDivergence(const Value *V) const
Returns whether V is a source of divergence.
bool useGPUDivergenceAnalysis() const
Return true if the target prefers to use GPU divergence analysis to replace the legacy version.
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
User * getUser() const
Returns the User that contains this Use.
Definition: Use.h:72
LLVM Value Representation.
Definition: Value.h:74
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:308
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
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:97
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:445
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
auto successors(const MachineBasicBlock *BB)
bool containsIrreducibleCFG(RPOTraversalT &RPOTraversal, const LoopInfoT &LI)
Return true if the control flow in RPOTraversal is irreducible.
Definition: CFG.h:136
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
FunctionPass * createLegacyDivergenceAnalysisPass()
void initializeLegacyDivergenceAnalysisPass(PassRegistry &)
TargetTransformInfo TTI