contrib/llvm/lib/Analysis/LegacyDivergenceAnalysis.cpp

   1 //===- LegacyDivergenceAnalysis.cpp --------- Legacy Divergence Analysis
   2 //Implementation -==//
   3 //
   4 //                     The LLVM Compiler Infrastructure
   5 //
   6 // This file is distributed under the University of Illinois Open Source
   7 // License. See LICENSE.TXT for details.
   8 //
   9 //===----------------------------------------------------------------------===//
  10 //
  11 // This file implements divergence analysis which determines whether a branch
  12 // in a GPU program is divergent.It can help branch optimizations such as jump
  13 // threading and loop unswitching to make better decisions.
  14 //
  15 // GPU programs typically use the SIMD execution model, where multiple threads
  16 // in the same execution group have to execute in lock-step. Therefore, if the
  17 // code contains divergent branches (i.e., threads in a group do not agree on
  18 // which path of the branch to take), the group of threads has to execute all
  19 // the paths from that branch with different subsets of threads enabled until
  20 // they converge at the immediately post-dominating BB of the paths.
  21 //
  22 // Due to this execution model, some optimizations such as jump
  23 // threading and loop unswitching can be unfortunately harmful when performed on
  24 // divergent branches. Therefore, an analysis that computes which branches in a
  25 // GPU program are divergent can help the compiler to selectively run these
  26 // optimizations.
  27 //
  28 // This file defines divergence analysis which computes a conservative but
  29 // non-trivial approximation of all divergent branches in a GPU program. It
  30 // partially implements the approach described in
  31 //
  32 //   Divergence Analysis
  33 //   Sampaio, Souza, Collange, Pereira
  34 //   TOPLAS '13
  35 //
  36 // The divergence analysis identifies the sources of divergence (e.g., special
  37 // variables that hold the thread ID), and recursively marks variables that are
  38 // data or sync dependent on a source of divergence as divergent.
  39 //
  40 // While data dependency is a well-known concept, the notion of sync dependency
  41 // is worth more explanation. Sync dependence characterizes the control flow
  42 // aspect of the propagation of branch divergence. For example,
  43 //
  44 //   %cond = icmp slt i32 %tid, 10
  45 //   br i1 %cond, label %then, label %else
  46 // then:
  47 //   br label %merge
  48 // else:
  49 //   br label %merge
  50 // merge:
  51 //   %a = phi i32 [ 0, %then ], [ 1, %else ]
  52 //
  53 // Suppose %tid holds the thread ID. Although %a is not data dependent on %tid
  54 // because %tid is not on its use-def chains, %a is sync dependent on %tid
  55 // because the branch "br i1 %cond" depends on %tid and affects which value %a
  56 // is assigned to.
  57 //
  58 // The current implementation has the following limitations:
  59 // 1. intra-procedural. It conservatively considers the arguments of a
  60 //    non-kernel-entry function and the return value of a function call as
  61 //    divergent.
  62 // 2. memory as black box. It conservatively considers values loaded from
  63 //    generic or local address as divergent. This can be improved by leveraging
  64 //    pointer analysis.
  65 //
  66 //===----------------------------------------------------------------------===//
  67
  68 #include "llvm/ADT/PostOrderIterator.h"
  69 #include "llvm/Analysis/CFG.h"
  70 #include "llvm/Analysis/DivergenceAnalysis.h"
  71 #include "llvm/Analysis/LegacyDivergenceAnalysis.h"
  72 #include "llvm/Analysis/Passes.h"
  73 #include "llvm/Analysis/PostDominators.h"
  74 #include "llvm/Analysis/TargetTransformInfo.h"
  75 #include "llvm/IR/Dominators.h"
  76 #include "llvm/IR/InstIterator.h"
  77 #include "llvm/IR/Instructions.h"
  78 #include "llvm/IR/Value.h"
  79 #include "llvm/Support/Debug.h"
  80 #include "llvm/Support/raw_ostream.h"
  81 #include <vector>
  82 using namespace llvm;
  83
  84 #define DEBUG_TYPE "divergence"
  85
  86 // transparently use the GPUDivergenceAnalysis
  87 static cl::opt<bool> UseGPUDA("use-gpu-divergence-analysis", cl::init(false),
  88                               cl::Hidden,
  89                               cl::desc("turn the LegacyDivergenceAnalysis into "
  90                                        "a wrapper for GPUDivergenceAnalysis"));
  91
  92 namespace {
  93
  94 class DivergencePropagator {
  95 public:
  96   DivergencePropagator(Function &F, TargetTransformInfo &TTI, DominatorTree &DT,
  97                        PostDominatorTree &PDT, DenseSet<const Value *> &DV)
  98       : F(F), TTI(TTI), DT(DT), PDT(PDT), DV(DV) {}
  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;
 119   PostDominatorTree &PDT;
 120   std::vector<Value *> Worklist; // Stack for DFS.
 121   DenseSet<const Value *> &DV;   // Stores all divergent values.
 122 };
 123
 124 void DivergencePropagator::populateWithSourcesOfDivergence() {
 125   Worklist.clear();
 126   DV.clear();
 127   for (auto &I : instructions(F)) {
 128     if (TTI.isSourceOfDivergence(&I)) {
 129       Worklist.push_back(&I);
 130       DV.insert(&I);
 131     }
 132   }
 133   for (auto &Arg : F.args()) {
 134     if (TTI.isSourceOfDivergence(&Arg)) {
 135       Worklist.push_back(&Arg);
 136       DV.insert(&Arg);
 137     }
 138   }
 139 }
 140
 141 void DivergencePropagator::exploreSyncDependency(Instruction *TI) {
 142   // Propagation rule 1: if branch TI is divergent, all PHINodes in TI's
 143   // immediate post dominator are divergent. This rule handles if-then-else
 144   // patterns. For example,
 145   //
 146   // if (tid < 5)
 147   //   a1 = 1;
 148   // else
 149   //   a2 = 2;
 150   // a = phi(a1, a2); // sync dependent on (tid < 5)
 151   BasicBlock *ThisBB = TI->getParent();
 152
 153   // Unreachable blocks may not be in the dominator tree.
 154   if (!DT.isReachableFromEntry(ThisBB))
 155     return;
 156
 157   // If the function has no exit blocks or doesn't reach any exit blocks, the
 158   // post dominator may be null.
 159   DomTreeNode *ThisNode = PDT.getNode(ThisBB);
 160   if (!ThisNode)
 161     return;
 162
 163   BasicBlock *IPostDom = ThisNode->getIDom()->getBlock();
 164   if (IPostDom == nullptr)
 165     return;
 166
 167   for (auto I = IPostDom->begin(); isa<PHINode>(I); ++I) {
 168     // A PHINode is uniform if it returns the same value no matter which path is
 169     // taken.
 170     if (!cast<PHINode>(I)->hasConstantOrUndefValue() && DV.insert(&*I).second)
 171       Worklist.push_back(&*I);
 172   }
 173
 174   // Propagation rule 2: if a value defined in a loop is used outside, the user
 175   // is sync dependent on the condition of the loop exits that dominate the
 176   // user. For example,
 177   //
 178   // int i = 0;
 179   // do {
 180   //   i++;
 181   //   if (foo(i)) ... // uniform
 182   // } while (i < tid);
 183   // if (bar(i)) ...   // divergent
 184   //
 185   // A program may contain unstructured loops. Therefore, we cannot leverage
 186   // LoopInfo, which only recognizes natural loops.
 187   //
 188   // The algorithm used here handles both natural and unstructured loops.  Given
 189   // a branch TI, we first compute its influence region, the union of all simple
 190   // paths from TI to its immediate post dominator (IPostDom). Then, we search
 191   // for all the values defined in the influence region but used outside. All
 192   // these users are sync dependent on TI.
 193   DenseSet<BasicBlock *> InfluenceRegion;
 194   computeInfluenceRegion(ThisBB, IPostDom, InfluenceRegion);
 195   // An insight that can speed up the search process is that all the in-region
 196   // values that are used outside must dominate TI. Therefore, instead of
 197   // searching every basic blocks in the influence region, we search all the
 198   // dominators of TI until it is outside the influence region.
 199   BasicBlock *InfluencedBB = ThisBB;
 200   while (InfluenceRegion.count(InfluencedBB)) {
 201     for (auto &I : *InfluencedBB)
 202       findUsersOutsideInfluenceRegion(I, InfluenceRegion);
 203     DomTreeNode *IDomNode = DT.getNode(InfluencedBB)->getIDom();
 204     if (IDomNode == nullptr)
 205       break;
 206     InfluencedBB = IDomNode->getBlock();
 207   }
 208 }
 209
 210 void DivergencePropagator::findUsersOutsideInfluenceRegion(
 211     Instruction &I, const DenseSet<BasicBlock *> &InfluenceRegion) {
 212   for (User *U : I.users()) {
 213     Instruction *UserInst = cast<Instruction>(U);
 214     if (!InfluenceRegion.count(UserInst->getParent())) {
 215       if (DV.insert(UserInst).second)
 216         Worklist.push_back(UserInst);
 217     }
 218   }
 219 }
 220
 221 // A helper function for computeInfluenceRegion that adds successors of "ThisBB"
 222 // to the influence region.
 223 static void
 224 addSuccessorsToInfluenceRegion(BasicBlock *ThisBB, BasicBlock *End,
 225                                DenseSet<BasicBlock *> &InfluenceRegion,
 226                                std::vector<BasicBlock *> &InfluenceStack) {
 227   for (BasicBlock *Succ : successors(ThisBB)) {
 228     if (Succ != End && InfluenceRegion.insert(Succ).second)
 229       InfluenceStack.push_back(Succ);
 230   }
 231 }
 232
 233 void DivergencePropagator::computeInfluenceRegion(
 234     BasicBlock *Start, BasicBlock *End,
 235     DenseSet<BasicBlock *> &InfluenceRegion) {
 236   assert(PDT.properlyDominates(End, Start) &&
 237          "End does not properly dominate Start");
 238
 239   // The influence region starts from the end of "Start" to the beginning of
 240   // "End". Therefore, "Start" should not be in the region unless "Start" is in
 241   // a loop that doesn't contain "End".
 242   std::vector<BasicBlock *> InfluenceStack;
 243   addSuccessorsToInfluenceRegion(Start, End, InfluenceRegion, InfluenceStack);
 244   while (!InfluenceStack.empty()) {
 245     BasicBlock *BB = InfluenceStack.back();
 246     InfluenceStack.pop_back();
 247     addSuccessorsToInfluenceRegion(BB, End, InfluenceRegion, InfluenceStack);
 248   }
 249 }
 250
 251 void DivergencePropagator::exploreDataDependency(Value *V) {
 252   // Follow def-use chains of V.
 253   for (User *U : V->users()) {
 254     Instruction *UserInst = cast<Instruction>(U);
 255     if (!TTI.isAlwaysUniform(U) && DV.insert(UserInst).second)
 256       Worklist.push_back(UserInst);
 257   }
 258 }
 259
 260 void DivergencePropagator::propagate() {
 261   // Traverse the dependency graph using DFS.
 262   while (!Worklist.empty()) {
 263     Value *V = Worklist.back();
 264     Worklist.pop_back();
 265     if (Instruction *I = dyn_cast<Instruction>(V)) {
 266       // Terminators with less than two successors won't introduce sync
 267       // dependency. Ignore them.
 268       if (I->isTerminator() && I->getNumSuccessors() > 1)
 269         exploreSyncDependency(I);
 270     }
 271     exploreDataDependency(V);
 272   }
 273 }
 274
 275 } // namespace
 276
 277 // Register this pass.
 278 char LegacyDivergenceAnalysis::ID = 0;
 279 INITIALIZE_PASS_BEGIN(LegacyDivergenceAnalysis, "divergence",
 280                       "Legacy Divergence Analysis", false, true)
 281 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 282 INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
 283 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 284 INITIALIZE_PASS_END(LegacyDivergenceAnalysis, "divergence",
 285                     "Legacy Divergence Analysis", false, true)
 286
 287 FunctionPass *llvm::createLegacyDivergenceAnalysisPass() {
 288   return new LegacyDivergenceAnalysis();
 289 }
 290
 291 void LegacyDivergenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
 292   AU.addRequired<DominatorTreeWrapperPass>();
 293   AU.addRequired<PostDominatorTreeWrapperPass>();
 294   if (UseGPUDA)
 295     AU.addRequired<LoopInfoWrapperPass>();
 296   AU.setPreservesAll();
 297 }
 298
 299 bool LegacyDivergenceAnalysis::shouldUseGPUDivergenceAnalysis(
 300     const Function &F) const {
 301   if (!UseGPUDA)
 302     return false;
 303
 304   // GPUDivergenceAnalysis requires a reducible CFG.
 305   auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
 306   using RPOTraversal = ReversePostOrderTraversal<const Function *>;
 307   RPOTraversal FuncRPOT(&F);
 308   return !containsIrreducibleCFG<const BasicBlock *, const RPOTraversal,
 309                                  const LoopInfo>(FuncRPOT, LI);
 310 }
 311
 312 bool LegacyDivergenceAnalysis::runOnFunction(Function &F) {
 313   auto *TTIWP = getAnalysisIfAvailable<TargetTransformInfoWrapperPass>();
 314   if (TTIWP == nullptr)
 315     return false;
 316
 317   TargetTransformInfo &TTI = TTIWP->getTTI(F);
 318   // Fast path: if the target does not have branch divergence, we do not mark
 319   // any branch as divergent.
 320   if (!TTI.hasBranchDivergence())
 321     return false;
 322
 323   DivergentValues.clear();
 324   gpuDA = nullptr;
 325
 326   auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 327   auto &PDT = getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
 328
 329   if (shouldUseGPUDivergenceAnalysis(F)) {
 330     // run the new GPU divergence analysis
 331     auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
 332     gpuDA = llvm::make_unique<GPUDivergenceAnalysis>(F, DT, PDT, LI, TTI);
 333
 334   } else {
 335     // run LLVM's existing DivergenceAnalysis
 336     DivergencePropagator DP(F, TTI, DT, PDT, DivergentValues);
 337     DP.populateWithSourcesOfDivergence();
 338     DP.propagate();
 339   }
 340
 341   LLVM_DEBUG(dbgs() << "\nAfter divergence analysis on " << F.getName()
 342                     << ":\n";
 343              print(dbgs(), F.getParent()));
 344
 345   return false;
 346 }
 347
 348 bool LegacyDivergenceAnalysis::isDivergent(const Value *V) const {
 349   if (gpuDA) {
 350     return gpuDA->isDivergent(*V);
 351   }
 352   return DivergentValues.count(V);
 353 }
 354
 355 void LegacyDivergenceAnalysis::print(raw_ostream &OS, const Module *) const {
 356   if ((!gpuDA || !gpuDA->hasDivergence()) && DivergentValues.empty())
 357     return;
 358
 359   const Function *F = nullptr;
 360   if (!DivergentValues.empty()) {
 361     const Value *FirstDivergentValue = *DivergentValues.begin();
 362     if (const Argument *Arg = dyn_cast<Argument>(FirstDivergentValue)) {
 363       F = Arg->getParent();
 364     } else if (const Instruction *I =
 365                    dyn_cast<Instruction>(FirstDivergentValue)) {
 366       F = I->getParent()->getParent();
 367     } else {
 368       llvm_unreachable("Only arguments and instructions can be divergent");
 369     }
 370   } else if (gpuDA) {
 371     F = &gpuDA->getFunction();
 372   }
 373   if (!F)
 374     return;
 375
 376   // Dumps all divergent values in F, arguments and then instructions.
 377   for (auto &Arg : F->args()) {
 378     OS << (isDivergent(&Arg) ? "DIVERGENT: " : "           ");
 379     OS << Arg << "\n";
 380   }
 381   // Iterate instructions using instructions() to ensure a deterministic order.
 382   for (auto BI = F->begin(), BE = F->end(); BI != BE; ++BI) {
 383     auto &BB = *BI;
 384     OS << "\n           " << BB.getName() << ":\n";
 385     for (auto &I : BB.instructionsWithoutDebug()) {
 386       OS << (isDivergent(&I) ? "DIVERGENT:     " : "               ");
 387       OS << I << "\n";
 388     }
 389   }
 390   OS << "\n";
 391 }