1//===- DivergenceAnalysis.cpp ------ Divergence Analysis ------------------===// 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 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. 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#include <vector> 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" 82using namespace llvm; 83 84#define DEBUG_TYPE "divergence" 85 86namespace { 87class DivergenceAnalysis : public FunctionPass { 88public: 89 static char ID; 90 91 DivergenceAnalysis() : FunctionPass(ID) { 92 initializeDivergenceAnalysisPass(*PassRegistry::getPassRegistry()); 93 } 94 95 void getAnalysisUsage(AnalysisUsage &AU) const override { 96 AU.addRequired<DominatorTreeWrapperPass>(); 97 AU.addRequired<PostDominatorTree>(); 98 AU.setPreservesAll(); 99 } 100 101 bool runOnFunction(Function &F) override; 102 103 // Print all divergent branches in the function. 104 void print(raw_ostream &OS, const Module *) const override; 105 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); } 110 111private: 112 // Stores all divergent values. 113 DenseSet<const Value *> DivergentValues; 114}; 115} // End of anonymous namespace 116 117// Register this pass. 118char DivergenceAnalysis::ID = 0; 119INITIALIZE_PASS_BEGIN(DivergenceAnalysis, "divergence", "Divergence Analysis", 120 false, true) 121INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 122INITIALIZE_PASS_DEPENDENCY(PostDominatorTree) 123INITIALIZE_PASS_END(DivergenceAnalysis, "divergence", "Divergence Analysis", 124 false, true) 125 126namespace { 127 128class DivergencePropagator { 129public: 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(); 135 void propagate(); 136 137private: 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); 150 151 Function &F; 152 TargetTransformInfo &TTI; 153 DominatorTree &DT; 154 PostDominatorTree &PDT; 155 std::vector<Value *> Worklist; // Stack for DFS. 156 DenseSet<const Value *> &DV; // Stores all divergent values. 157}; 158 159void DivergencePropagator::populateWithSourcesOfDivergence() { 160 Worklist.clear(); 161 DV.clear(); 162 for (auto &I : inst_range(F)) { 163 if (TTI.isSourceOfDivergence(&I)) { 164 Worklist.push_back(&I); 165 DV.insert(&I); 166 } 167 } 168 for (auto &Arg : F.args()) { 169 if (TTI.isSourceOfDivergence(&Arg)) { 170 Worklist.push_back(&Arg); 171 DV.insert(&Arg); 172 } 173 } 174} 175 176void 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, 180 // 181 // if (tid < 5) 182 // a1 = 1; 183 // else 184 // a2 = 2; 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) 189 return; 190 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 193 // taken. 194 if (!cast<PHINode>(I)->hasConstantValue() && DV.insert(I).second) 195 Worklist.push_back(I); 196 } 197 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, 201 // 202 // int i = 0; 203 // do { 204 // i++; 205 // if (foo(i)) ... // uniform 206 // } while (i < tid); 207 // if (bar(i)) ... // divergent 208 // 209 // A program may contain unstructured loops. Therefore, we cannot leverage 210 // LoopInfo, which only recognizes natural loops. 211 // 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) 229 break; 230 InfluencedBB = IDomNode->getBlock(); 231 } 232} 233 234void 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); 241 } 242 } 243} 244 245void 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); 259 } 260 } 261} 262 263void 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); 269 } 270} 271 272void DivergencePropagator::propagate() { 273 // Traverse the dependency graph using DFS. 274 while (!Worklist.empty()) { 275 Value *V = Worklist.back(); 276 Worklist.pop_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); 282 } 283 exploreDataDependency(V); 284 } 285} 286 287} /// end namespace anonymous 288 289FunctionPass *llvm::createDivergenceAnalysisPass() { 290 return new DivergenceAnalysis(); 291} 292 293bool DivergenceAnalysis::runOnFunction(Function &F) { 294 auto *TTIWP = getAnalysisIfAvailable<TargetTransformInfoWrapperPass>(); 295 if (TTIWP == nullptr) 296 return false; 297 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()) 302 return false; 303 304 DivergentValues.clear(); 305 DivergencePropagator DP(F, TTI, 306 getAnalysis<DominatorTreeWrapperPass>().getDomTree(), 307 getAnalysis<PostDominatorTree>(), DivergentValues); 308 DP.populateWithSourcesOfDivergence(); 309 DP.propagate(); 310 return false; 311} 312 313void DivergenceAnalysis::print(raw_ostream &OS, const Module *) const { 314 if (DivergentValues.empty()) 315 return; 316 const Value *FirstDivergentValue = *DivergentValues.begin(); 317 const Function *F; 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(); 323 } else { 324 llvm_unreachable("Only arguments and instructions can be divergent"); 325 } 326 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"; 331 } 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"; 336 } 337} 338