include/llvm/Analysis/DivergenceAnalysis.h

   1 //===- llvm/Analysis/DivergenceAnalysis.h - Divergence Analysis -*- C++ -*-===//
   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 // \file
  11 // The divergence analysis determines which instructions and branches are
  12 // divergent given a set of divergent source instructions.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #ifndef LLVM_ANALYSIS_DIVERGENCE_ANALYSIS_H
  17 #define LLVM_ANALYSIS_DIVERGENCE_ANALYSIS_H
  18
  19 #include "llvm/ADT/DenseSet.h"
  20 #include "llvm/Analysis/SyncDependenceAnalysis.h"
  21 #include "llvm/IR/Function.h"
  22 #include "llvm/Pass.h"
  23 #include <vector>
  24
  25 namespace llvm {
  26 class Module;
  27 class Value;
  28 class Instruction;
  29 class Loop;
  30 class raw_ostream;
  31 class TargetTransformInfo;
  32
  33 /// \brief Generic divergence analysis for reducible CFGs.
  34 ///
  35 /// This analysis propagates divergence in a data-parallel context from sources
  36 /// of divergence to all users. It requires reducible CFGs. All assignments
  37 /// should be in SSA form.
  38 class DivergenceAnalysis {
  39 public:
  40   /// \brief This instance will analyze the whole function \p F or the loop \p
  41   /// RegionLoop.
  42   ///
  43   /// \param RegionLoop if non-null the analysis is restricted to \p RegionLoop.
  44   /// Otherwise the whole function is analyzed.
  45   /// \param IsLCSSAForm whether the analysis may assume that the IR in the
  46   /// region in in LCSSA form.
  47   DivergenceAnalysis(const Function &F, const Loop *RegionLoop,
  48                      const DominatorTree &DT, const LoopInfo &LI,
  49                      SyncDependenceAnalysis &SDA, bool IsLCSSAForm);
  50
  51   /// \brief The loop that defines the analyzed region (if any).
  52   const Loop *getRegionLoop() const { return RegionLoop; }
  53   const Function &getFunction() const { return F; }
  54
  55   /// \brief Whether \p BB is part of the region.
  56   bool inRegion(const BasicBlock &BB) const;
  57   /// \brief Whether \p I is part of the region.
  58   bool inRegion(const Instruction &I) const;
  59
  60   /// \brief Mark \p UniVal as a value that is always uniform.
  61   void addUniformOverride(const Value &UniVal);
  62
  63   /// \brief Mark \p DivVal as a value that is always divergent.
  64   void markDivergent(const Value &DivVal);
  65
  66   /// \brief Propagate divergence to all instructions in the region.
  67   /// Divergence is seeded by calls to \p markDivergent.
  68   void compute();
  69
  70   /// \brief Whether any value was marked or analyzed to be divergent.
  71   bool hasDetectedDivergence() const { return !DivergentValues.empty(); }
  72
  73   /// \brief Whether \p Val will always return a uniform value regardless of its
  74   /// operands
  75   bool isAlwaysUniform(const Value &Val) const;
  76
  77   /// \brief Whether \p Val is a divergent value
  78   bool isDivergent(const Value &Val) const;
  79
  80   void print(raw_ostream &OS, const Module *) const;
  81
  82 private:
  83   bool updateTerminator(const Instruction &Term) const;
  84   bool updatePHINode(const PHINode &Phi) const;
  85
  86   /// \brief Computes whether \p Inst is divergent based on the
  87   /// divergence of its operands.
  88   ///
  89   /// \returns Whether \p Inst is divergent.
  90   ///
  91   /// This should only be called for non-phi, non-terminator instructions.
  92   bool updateNormalInstruction(const Instruction &Inst) const;
  93
  94   /// \brief Mark users of live-out users as divergent.
  95   ///
  96   /// \param LoopHeader the header of the divergent loop.
  97   ///
  98   /// Marks all users of live-out values of the loop headed by \p LoopHeader
  99   /// as divergent and puts them on the worklist.
 100   void taintLoopLiveOuts(const BasicBlock &LoopHeader);
 101
 102   /// \brief Push all users of \p Val (in the region) to the worklist
 103   void pushUsers(const Value &I);
 104
 105   /// \brief Push all phi nodes in @block to the worklist
 106   void pushPHINodes(const BasicBlock &Block);
 107
 108   /// \brief Mark \p Block as join divergent
 109   ///
 110   /// A block is join divergent if two threads may reach it from different
 111   /// incoming blocks at the same time.
 112   void markBlockJoinDivergent(const BasicBlock &Block) {
 113     DivergentJoinBlocks.insert(&Block);
 114   }
 115
 116   /// \brief Whether \p Val is divergent when read in \p ObservingBlock.
 117   bool isTemporalDivergent(const BasicBlock &ObservingBlock,
 118                            const Value &Val) const;
 119
 120   /// \brief Whether \p Block is join divergent
 121   ///
 122   /// (see markBlockJoinDivergent).
 123   bool isJoinDivergent(const BasicBlock &Block) const {
 124     return DivergentJoinBlocks.find(&Block) != DivergentJoinBlocks.end();
 125   }
 126
 127   /// \brief Propagate control-induced divergence to users (phi nodes and
 128   /// instructions).
 129   //
 130   // \param JoinBlock is a divergent loop exit or join point of two disjoint
 131   // paths.
 132   // \returns Whether \p JoinBlock is a divergent loop exit of \p TermLoop.
 133   bool propagateJoinDivergence(const BasicBlock &JoinBlock,
 134                                const Loop *TermLoop);
 135
 136   /// \brief Propagate induced value divergence due to control divergence in \p
 137   /// Term.
 138   void propagateBranchDivergence(const Instruction &Term);
 139
 140   /// \brief Propagate divergent caused by a divergent loop exit.
 141   ///
 142   /// \param ExitingLoop is a divergent loop.
 143   void propagateLoopDivergence(const Loop &ExitingLoop);
 144
 145 private:
 146   const Function &F;
 147   // If regionLoop != nullptr, analysis is only performed within \p RegionLoop.
 148   // Otw, analyze the whole function
 149   const Loop *RegionLoop;
 150
 151   const DominatorTree &DT;
 152   const LoopInfo &LI;
 153
 154   // Recognized divergent loops
 155   DenseSet<const Loop *> DivergentLoops;
 156
 157   // The SDA links divergent branches to divergent control-flow joins.
 158   SyncDependenceAnalysis &SDA;
 159
 160   // Use simplified code path for LCSSA form.
 161   bool IsLCSSAForm;
 162
 163   // Set of known-uniform values.
 164   DenseSet<const Value *> UniformOverrides;
 165
 166   // Blocks with joining divergent control from different predecessors.
 167   DenseSet<const BasicBlock *> DivergentJoinBlocks;
 168
 169   // Detected/marked divergent values.
 170   DenseSet<const Value *> DivergentValues;
 171
 172   // Internal worklist for divergence propagation.
 173   std::vector<const Instruction *> Worklist;
 174 };
 175
 176 /// \brief Divergence analysis frontend for GPU kernels.
 177 class GPUDivergenceAnalysis {
 178   SyncDependenceAnalysis SDA;
 179   DivergenceAnalysis DA;
 180
 181 public:
 182   /// Runs the divergence analysis on @F, a GPU kernel
 183   GPUDivergenceAnalysis(Function &F, const DominatorTree &DT,
 184                         const PostDominatorTree &PDT, const LoopInfo &LI,
 185                         const TargetTransformInfo &TTI);
 186
 187   /// Whether any divergence was detected.
 188   bool hasDivergence() const { return DA.hasDetectedDivergence(); }
 189
 190   /// The GPU kernel this analysis result is for
 191   const Function &getFunction() const { return DA.getFunction(); }
 192
 193   /// Whether \p V is divergent.
 194   bool isDivergent(const Value &V) const;
 195
 196   /// Whether \p V is uniform/non-divergent
 197   bool isUniform(const Value &V) const { return !isDivergent(V); }
 198
 199   /// Print all divergent values in the kernel.
 200   void print(raw_ostream &OS, const Module *) const;
 201 };
 202
 203 } // namespace llvm
 204
 205 #endif // LLVM_ANALYSIS_DIVERGENCE_ANALYSIS_H