[DivergenceAnalysis] Add methods for querying divergence at use

[foad]

Summary

The existing isDivergent(Value) methods query whether a value is
divergent at its definition. However even if a value is uniform at its
definition, a use of it in another basic block can be divergent because
of divergent control flow between the def and the use.

This patch adds new isDivergent(Use) methods to DivergenceAnalysis,
LegacyDivergenceAnalysis and GPUDivergenceAnalysis.

This might allow D63953 or other similar workarounds to be removed.

[nhaehnle]

Nice work! It's missing tests though -- I'm not sure if we want to print this additional information in the divergence printer, but definitely a test for the atomic optimizer pass is required.

llvm/lib/Analysis/LegacyDivergenceAnalysis.cpp

204–206 ↗

(On Diff #211284)

Please put braces around the for body (multi-line body).

365 ↗

(On Diff #211284)

What's the rationale for checking the user here as well?

For example, if the user is a binary operation that is divergent only because the other use is divergent, then I'd expect this function to return false...

[foad]

Address review comments.

Rename the new methods to make it clear that they take a Use. Otherwise,
since there's an implicit conversion from Use to Value*, it's too hard
to be sure which overload you are calling.

Fix an egregious typo in LegacyDivergenceAnalysis::isDivergentUse.

Add a test for the atomic optimizer usage.

[foad]

It's missing tests though -- I'm not sure if we want to print this additional information in the divergence printer

Me neither. I'm open to suggestions.

llvm/lib/Analysis/LegacyDivergenceAnalysis.cpp

365 ↗

(On Diff #211284)

This was a subtle typo, getUser() instead of get(). Thanks for catching it.

[arsenm]

Does this avoid the need to run LCSSA for isel, assuming the DAG switches to checking the use instead of the def?

[foad]

In D65141#1599322, @arsenm wrote:

Does this avoid the need to run LCSSA for isel, assuming the DAG switches to checking the use instead of the def?

That's my hope, and that's what I meant by "this might allow D63953 or other similar workarounds to be removed", but I really don't know enough about divergence driven isel to be sure.

[nhaehnle]

I do prefer the explicit isDivergentUse!

To @arsenm 's question: at least for the SelectionDAG, the key is in SITargetLowering::isSDNodeSourceOfDivergence, which calls isDivergent on a value.

The way the SelectionDAG works, we have in our hands at this point a live value that comes into a basic block via a register. This suggests an isDivergentInBB. Would it be possible to do that instead / on top? For the new DA this seems very natural, and for the old DA this seems at least possible by storing a set of divergent (Value, BasicBlock) pairs instead of divergent uses. Alternatively, we'd have to scan the uses for one that lives in the appropriate basic block, which is slow since it means traversing a linked list... or perhaps there are other thoughts on this.

[foad]

In D65141#1600938, @nhaehnle wrote:

To @arsenm 's question: at least for the SelectionDAG, the key is in SITargetLowering::isSDNodeSourceOfDivergence, which calls isDivergent on a value.

The way the SelectionDAG works, we have in our hands at this point a live value that comes into a basic block via a register. This suggests an isDivergentInBB.

Is it guaranteed that the basic block does contain a use of the value? If not, I think this will be difficult to implement in LegacyDivergenceAnalysis.

llvm/trunk/include/llvm/Analysis/DivergenceAnalysis.h

public:
 
   /// \brief Whether any value was marked or analyzed to be divergent.
   bool hasDetectedDivergence() const { return !DivergentValues.empty(); }
 
   /// \brief Whether \p Val will always return a uniform value regardless of its
   /// operands
   bool isAlwaysUniform(const Value &Val) const;
 
-  /// \brief Whether \p Val is a divergent value
+  /// \brief Whether \p Val is divergent at its definition.
   bool isDivergent(const Value &Val) const;
 
+  /// \brief Whether \p U is divergent. Uses of a uniform value can be divergent.
+  bool isDivergentUse(const Use &U) const;
+
   void print(raw_ostream &OS, const Module *) const;
 
 private:
   bool updateTerminator(const Instruction &Term) const;
   bool updatePHINode(const PHINode &Phi) const;
 
   /// \brief Computes whether \p Inst is divergent based on the
   /// divergence of its operands.
GPUDivergenceAnalysis(Function &F, const DominatorTree &DT,
                         const TargetTransformInfo &TTI);
 
   /// Whether any divergence was detected.
   bool hasDivergence() const { return DA.hasDetectedDivergence(); }
 
   /// The GPU kernel this analysis result is for
   const Function &getFunction() const { return DA.getFunction(); }
 
-  /// Whether \p V is divergent.
+  /// Whether \p V is divergent at its definition.
   bool isDivergent(const Value &V) const;
 
-  /// Whether \p V is uniform/non-divergent
+  /// Whether \p U is divergent. Uses of a uniform value can be divergent.
+  bool isDivergentUse(const Use &U) const;
+
+  /// Whether \p V is uniform/non-divergent.
   bool isUniform(const Value &V) const { return !isDivergent(V); }
 
+  /// Whether \p U is uniform/non-divergent. Uses of a uniform value can be
+  /// divergent.
+  bool isUniformUse(const Use &U) const { return !isDivergentUse(U); }
+
   /// Print all divergent values in the kernel.
   void print(raw_ostream &OS, const Module *) const;
 };
 
 } // namespace llvm
 
 #endif // LLVM_ANALYSIS_DIVERGENCE_ANALYSIS_H

llvm/trunk/include/llvm/Analysis/LegacyDivergenceAnalysis.h

public:
   void getAnalysisUsage(AnalysisUsage &AU) const override;
 
   bool runOnFunction(Function &F) override;
 
   // Print all divergent branches in the function.
   void print(raw_ostream &OS, const Module *) const override;
 
   // Returns true if V is divergent at its definition.
-  //
-  // Even if this function returns false, V may still be divergent when used
-  // in a different basic block.
   bool isDivergent(const Value *V) const;
 
+  // Returns true if U is divergent. Uses of a uniform value can be divergent.
+  bool isDivergentUse(const Use *U) const;
+
   // Returns true if V is uniform/non-divergent.
-  //
-  // Even if this function returns true, V may still be divergent when used
-  // in a different basic block.
   bool isUniform(const Value *V) const { return !isDivergent(V); }
 
+  // Returns true if U is uniform/non-divergent. Uses of a uniform value can be
+  // divergent.
+  bool isUniformUse(const Use *U) const { return !isDivergentUse(U); }
+
   // Keep the analysis results uptodate by removing an erased value.
   void removeValue(const Value *V) { DivergentValues.erase(V); }
 
 private:
   // Whether analysis should be performed by GPUDivergenceAnalysis.
   bool shouldUseGPUDivergenceAnalysis(const Function &F) const;
 
   // (optional) handle to new DivergenceAnalysis
   std::unique_ptr<GPUDivergenceAnalysis> gpuDA;
 
   // Stores all divergent values.
   DenseSet<const Value *> DivergentValues;
+
+  // Stores divergent uses of possibly uniform values.
+  DenseSet<const Use *> DivergentUses;
 };
 } // End llvm namespace
 
 #endif //LLVM_ANALYSIS_LEGACY_DIVERGENCE_ANALYSIS_H

llvm/trunk/lib/Analysis/DivergenceAnalysis.cpp

 bool DivergenceAnalysis::isAlwaysUniform(const Value &V) const {
   return UniformOverrides.find(&V) != UniformOverrides.end();
 }
 
 bool DivergenceAnalysis::isDivergent(const Value &V) const {
   return DivergentValues.find(&V) != DivergentValues.end();
 }
 
+bool DivergenceAnalysis::isDivergentUse(const Use &U) const {
+  Value &V = *U.get();
+  Instruction &I = *cast<Instruction>(U.getUser());
+  return isDivergent(V) || isTemporalDivergent(*I.getParent(), V);
+}
+
 void DivergenceAnalysis::print(raw_ostream &OS, const Module *) const {
   if (DivergentValues.empty())
     return;
   // iterate instructions using instructions() to ensure a deterministic order.
   for (auto &I : instructions(F)) {
     if (isDivergent(I))
       OS << "DIVERGENT:" << I << '\n';
   }
GPUDivergenceAnalysis::GPUDivergenceAnalysis(Function &F,
 
   DA.compute();
 }
 
 bool GPUDivergenceAnalysis::isDivergent(const Value &val) const {
   return DA.isDivergent(val);
 }
 
+bool GPUDivergenceAnalysis::isDivergentUse(const Use &use) const {
+  return DA.isDivergentUse(use);
+}
+
 void GPUDivergenceAnalysis::print(raw_ostream &OS, const Module *mod) const {
   OS << "Divergence of kernel " << DA.getFunction().getName() << " {\n";
   DA.print(OS, mod);
   OS << "}\n";
 }

llvm/trunk/lib/Analysis/LegacyDivergenceAnalysis.cpp

static cl::opt<bool> UseGPUDA("use-gpu-divergence-analysis", cl::init(false),
                               cl::desc("turn the LegacyDivergenceAnalysis into "
                                        "a wrapper for GPUDivergenceAnalysis"));
 
 namespace {
 
 class DivergencePropagator {
 public:
   DivergencePropagator(Function &F, TargetTransformInfo &TTI, DominatorTree &DT,
-                       PostDominatorTree &PDT, DenseSet<const Value *> &DV)
-      : F(F), TTI(TTI), DT(DT), PDT(PDT), DV(DV) {}
+                       PostDominatorTree &PDT, DenseSet<const Value *> &DV,
+                       DenseSet<const Use *> &DU)
+      : F(F), TTI(TTI), DT(DT), PDT(PDT), DV(DV), DU(DU) {}
   void populateWithSourcesOfDivergence();
   void propagate();
 
 private:
   // A helper function that explores data dependents of V.
   void exploreDataDependency(Value *V);
   // A helper function that explores sync dependents of TI.
   void exploreSyncDependency(Instruction *TI);
   // Computes the influence region from Start to End. This region includes all
   // basic blocks on any simple path from Start to End.
   void computeInfluenceRegion(BasicBlock *Start, BasicBlock *End,
                               DenseSet<BasicBlock *> &InfluenceRegion);
   // Finds all users of I that are outside the influence region, and add these
   // users to Worklist.
   void findUsersOutsideInfluenceRegion(
       Instruction &I, const DenseSet<BasicBlock *> &InfluenceRegion);
 
   Function &F;
   TargetTransformInfo &TTI;
   DominatorTree &DT;
   PostDominatorTree &PDT;
   std::vector<Value *> Worklist; // Stack for DFS.
   DenseSet<const Value *> &DV;   // Stores all divergent values.
+  DenseSet<const Use *> &DU;   // Stores divergent uses of possibly uniform
+                               // values.
 };
 
 void DivergencePropagator::populateWithSourcesOfDivergence() {
   Worklist.clear();
   DV.clear();
+  DU.clear();
   for (auto &I : instructions(F)) {
     if (TTI.isSourceOfDivergence(&I)) {
       Worklist.push_back(&I);
       DV.insert(&I);
     }
   }
   for (auto &Arg : F.args()) {
     if (TTI.isSourceOfDivergence(&Arg)) {
void DivergencePropagator::exploreSyncDependency(Instruction *TI) {
   DenseSet<BasicBlock *> InfluenceRegion;
   computeInfluenceRegion(ThisBB, IPostDom, InfluenceRegion);
   // An insight that can speed up the search process is that all the in-region
   // values that are used outside must dominate TI. Therefore, instead of
   // searching every basic blocks in the influence region, we search all the
   // dominators of TI until it is outside the influence region.
   BasicBlock *InfluencedBB = ThisBB;
   while (InfluenceRegion.count(InfluencedBB)) {
-    for (auto &I : *InfluencedBB)
+    for (auto &I : *InfluencedBB) {
+      if (!DV.count(&I))
         findUsersOutsideInfluenceRegion(I, InfluenceRegion);
+    }
     DomTreeNode *IDomNode = DT.getNode(InfluencedBB)->getIDom();
     if (IDomNode == nullptr)
       break;
     InfluencedBB = IDomNode->getBlock();
   }
 }
 
 void DivergencePropagator::findUsersOutsideInfluenceRegion(
     Instruction &I, const DenseSet<BasicBlock *> &InfluenceRegion) {
-  for (User *U : I.users()) {
-    Instruction *UserInst = cast<Instruction>(U);
+  for (Use &Use : I.uses()) {
+    Instruction *UserInst = cast<Instruction>(Use.getUser());
     if (!InfluenceRegion.count(UserInst->getParent())) {
+      DU.insert(&Use);
       if (DV.insert(UserInst).second)
         Worklist.push_back(UserInst);
     }
   }
 }
 
 // A helper function for computeInfluenceRegion that adds successors of "ThisBB"
 // to the influence region.
bool LegacyDivergenceAnalysis::runOnFunction(Function &F) {
 
   TargetTransformInfo &TTI = TTIWP->getTTI(F);
   // Fast path: if the target does not have branch divergence, we do not mark
   // any branch as divergent.
   if (!TTI.hasBranchDivergence())
     return false;
 
   DivergentValues.clear();
+  DivergentUses.clear();
   gpuDA = nullptr;
 
   auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
   auto &PDT = getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
 
   if (shouldUseGPUDivergenceAnalysis(F)) {
     // run the new GPU divergence analysis
     auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
     gpuDA = llvm::make_unique<GPUDivergenceAnalysis>(F, DT, PDT, LI, TTI);
 
   } else {
     // run LLVM's existing DivergenceAnalysis
-    DivergencePropagator DP(F, TTI, DT, PDT, DivergentValues);
+    DivergencePropagator DP(F, TTI, DT, PDT, DivergentValues, DivergentUses);
     DP.populateWithSourcesOfDivergence();
     DP.propagate();
   }
 
   LLVM_DEBUG(dbgs() << "\nAfter divergence analysis on " << F.getName()
                     << ":\n";
              print(dbgs(), F.getParent()));
 
   return false;
 }
 
 bool LegacyDivergenceAnalysis::isDivergent(const Value *V) const {
   if (gpuDA) {
     return gpuDA->isDivergent(*V);
   }
   return DivergentValues.count(V);
 }
 
+bool LegacyDivergenceAnalysis::isDivergentUse(const Use *U) const {
+  if (gpuDA) {
+    return gpuDA->isDivergentUse(*U);
+  }
+  return DivergentValues.count(U->get()) || DivergentUses.count(U);
+}
+
 void LegacyDivergenceAnalysis::print(raw_ostream &OS, const Module *) const {
   if ((!gpuDA || !gpuDA->hasDivergence()) && DivergentValues.empty())
     return;
 
   const Function *F = nullptr;
   if (!DivergentValues.empty()) {
     const Value *FirstDivergentValue = *DivergentValues.begin();
     if (const Argument *Arg = dyn_cast<Argument>(FirstDivergentValue)) {

llvm/trunk/lib/Target/AMDGPU/AMDGPUAtomicOptimizer.cpp

case AtomicRMWInst::UMin:
     break;
   }
 
   const unsigned PtrIdx = 0;
   const unsigned ValIdx = 1;
 
   // If the pointer operand is divergent, then each lane is doing an atomic
   // operation on a different address, and we cannot optimize that.
-  if (DA->isDivergent(I.getOperand(PtrIdx))) {
+  if (DA->isDivergentUse(&I.getOperandUse(PtrIdx))) {
     return;
   }
 
-  const bool ValDivergent = DA->isDivergent(I.getOperand(ValIdx));
+  const bool ValDivergent = DA->isDivergentUse(&I.getOperandUse(ValIdx));
 
   // If the value operand is divergent, each lane is contributing a different
   // value to the atomic calculation. We can only optimize divergent values if
   // we have DPP available on our subtarget, and the atomic operation is 32
   // bits.
   if (ValDivergent && (!HasDPP || (DL->getTypeSizeInBits(I.getType()) != 32))) {
     return;
   }
void AMDGPUAtomicOptimizer::visitIntrinsicInst(IntrinsicInst &I) {
   case Intrinsic::amdgcn_struct_buffer_atomic_umax:
   case Intrinsic::amdgcn_raw_buffer_atomic_umax:
     Op = AtomicRMWInst::UMax;
     break;
   }
 
   const unsigned ValIdx = 0;
 
-  const bool ValDivergent = DA->isDivergent(I.getOperand(ValIdx));
+  const bool ValDivergent = DA->isDivergentUse(&I.getOperandUse(ValIdx));
 
   // If the value operand is divergent, each lane is contributing a different
   // value to the atomic calculation. We can only optimize divergent values if
   // we have DPP available on our subtarget, and the atomic operation is 32
   // bits.
   if (ValDivergent && (!HasDPP || (DL->getTypeSizeInBits(I.getType()) != 32))) {
     return;
   }
 
   // If any of the other arguments to the intrinsic are divergent, we can't
   // optimize the operation.
   for (unsigned Idx = 1; Idx < I.getNumOperands(); Idx++) {
-    if (DA->isDivergent(I.getOperand(Idx))) {
+    if (DA->isDivergentUse(&I.getOperandUse(Idx))) {
       return;
     }
   }
 
   // If we get here, we can optimize the atomic using a single wavefront-wide
   // atomic operation to do the calculation for the entire wavefront, so
   // remember the instruction so we can come back to it.
   const ReplacementInfo Info = {&I, Op, ValIdx, ValDivergent};

llvm/trunk/test/CodeGen/AMDGPU/divergence-at-use.ll

+; RUN: llc -march=amdgcn -mcpu=gfx900 -amdgpu-atomic-optimizations=true < %s | FileCheck %s
+; RUN: llc -march=amdgcn -mcpu=gfx900 -amdgpu-atomic-optimizations=true < %s -use-gpu-divergence-analysis | FileCheck %s
+
+@local = addrspace(3) global i32 undef
+
+define void @reducible(i32 %x) {
+; CHECK-LABEL: reducible:
+; CHECK-NOT: dpp
+entry:
+  br label %loop
+loop:
+  %i = phi i32 [ 0, %entry ], [ %i1, %loop ]
+  %gep = getelementptr i32, i32 addrspace(3)* @local, i32 %i
+  %cond = icmp ult i32 %i, %x
+  %i1 = add i32 %i, 1
+  br i1 %cond, label %loop, label %exit
+exit:
+  %old = atomicrmw add i32 addrspace(3)* %gep, i32 %x acq_rel
+  ret void
+}