lib/Analysis/DivergenceAnalysis.cpp

   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"
  82 using namespace llvm;
  83
  84 #define DEBUG_TYPE "divergence"
  85
  86 namespace {
  87 class DivergenceAnalysis : public FunctionPass {
  88 public:
  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
 111 private:
 112   // Stores all divergent values.
 113   DenseSet<const Value *> DivergentValues;
 114 };
 115 } // End of anonymous namespace
 116
 117 // Register this pass.
 118 char DivergenceAnalysis::ID = 0;
 119 INITIALIZE_PASS_BEGIN(DivergenceAnalysis, "divergence", "Divergence Analysis",
 120                       false, true)
 121 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 122 INITIALIZE_PASS_DEPENDENCY(PostDominatorTree)
 123 INITIALIZE_PASS_END(DivergenceAnalysis, "divergence", "Divergence Analysis",
 124                     false, true)
 125
 126 namespace {
 127
 128 class DivergencePropagator {
 129 public:
 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
 137 private:
 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
 159 void DivergencePropagator::populateWithSourcesOfDivergence() {
 160   Worklist.clear();
 161   DV.clear();
 162   for (auto &I : instructions(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
 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,
 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
 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);
 241     }
 242   }
 243 }
 244
 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);
 259     }
 260   }
 261 }
 262
 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);
 269   }
 270 }
 271
 272 void 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
 289 FunctionPass *llvm::createDivergenceAnalysisPass() {
 290   return new DivergenceAnalysis();
 291 }
 292
 293 bool 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
 313 void 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 instructions() to ensure a deterministic order.
 333   for (auto &I : instructions(F)) {
 334     if (DivergentValues.count(&I))
 335       OS << "DIVERGENT:" << I << "\n";
 336   }
 337 }