[llvm][Uniformity] consistently handle uniform instructions

[sameerds]

Summary

An instruction that is "always uniform" is so even if it occurs in an
irreducible cycle. The output produced by such an instruction may depend on the
implementation defined cycle hierarchy, but that does not affect the uniformity
of the output. In other words, an "always uniform" instruction is uniform even
if it is not m-converged.

[ronlieb]

LGTM, as this resolves our downstream assertions seen in our CI

[ruiling]

In D145572#4178109, @ronlieb wrote:

LGTM, as this resolves our downstream assertions seen in our CI

Why would this fix an assertion? The description sounds like this is just an improvement. I think we need a reproducer for the assertion.

[sameerds]

In D145572#4180375, @ruiling wrote:

In D145572#4178109, @ronlieb wrote:

LGTM, as this resolves our downstream assertions seen in our CI

Why would this fix an assertion? The description sounds like this is just an improvement. I think we need a reproducer for the assertion.

Please see the comment regarding pushUsers().

llvm/lib/Analysis/UniformityAnalysis.cpp

62

This is the assertion that got fired. Earlier, if an operation X occurred in a cycle C that was assumed to be divergent, would assume that X is also divergent even if it is always uniform. Then when we try to call pushUsers() on X, it would assert. The lit test in this change is an example of exactly that happening.

[ruiling]

In D145572#4180384, @sameerds wrote:

In D145572#4180375, @ruiling wrote:

In D145572#4178109, @ronlieb wrote:

LGTM, as this resolves our downstream assertions seen in our CI

Why would this fix an assertion? The description sounds like this is just an improvement. I think we need a reproducer for the assertion.

Please see the comment regarding pushUsers().

Thanks for the point. Another question is does this affect a value defined in a divergent loop but used outside the loop case? For that situation, we still have to say the value is divergent.

[sameerds]

In D145572#4180441, @ruiling wrote:

In D145572#4180384, @sameerds wrote:

In D145572#4180375, @ruiling wrote:

In D145572#4178109, @ronlieb wrote:

LGTM, as this resolves our downstream assertions seen in our CI

Why would this fix an assertion? The description sounds like this is just an improvement. I think we need a reproducer for the assertion.

Please see the comment regarding pushUsers().

Thanks for the point. Another question is does this affect a value defined in a divergent loop but used outside the loop case? For that situation, we still have to say the value is divergent.

I am not sure what your question is:

1. Cycle is assumed to be divergent because it is irreducible. But operations that are always uniform need not be assumed to be divergent. That is this case.
2. Cycle has divergent exit. Value that is always uniform may still be divergent at its used. That is separately handled by temporal divergence.

[ruiling]

I am not sure what your question is:

1. Cycle is assumed to be divergent because it is irreducible. But operations that are always uniform need not be assumed to be divergent. That is this case.
2. Cycle has divergent exit. Value that is always uniform may still be divergent at its used. That is separately handled by temporal divergence.

I am asking for the second. thanks for the explanation.

[sameerds]

Updated the docs to clearly describe the new behaviour around m-converged
property and uniformity.

[ruiling]

LGTM

llvm/docs/ConvergenceAndUniformity.rst

 
 A non-uniform value is said to be *divergent*.
 
 For a set ``S`` of threads, the uniformity of each output of a static
 instance is determined as follows:
 
 1. The semantics of the instruction may specify the output to be
    uniform.
-2. Otherwise, if it is a PHI node, its output is uniform if and only
+2. Otherwise, the output is divergent if the static instance is not
+   :ref:`m-converged <convergence-m-converged>`.
+3. Otherwise, if the static instance is m-converged:
+
+   1. If it is a PHI node, its output is uniform if and only
       if for every pair of converged dynamic instances produced by all
       threads in ``S``:
 
       a. Both instances choose the same output from converged
          dynamic instances, and,
       b. That output is uniform for all threads in ``S``.
-3. Otherwise, the output is uniform if and only if the input
+   2. Otherwise, the output is uniform if and only if the input
       operands are uniform for all threads in ``S``.
 
 Divergent Cycle Exits
 ---------------------
 
 When a divergent branch occurs inside a cycle, it is possible that a
 diverged path continues to an exit of the cycle. This is called a
 divergent cycle exit. If the cycle is irreducible, the diverged path
 may re-enter and eventually reach a join within the cycle. Such a join

 
 Irreducible control flow results in different cycle hierarchies
 depending on the choice of headers during depth-first traversal. As a
 result, a static analysis cannot always determine the convergence of
 nodes in irreducible cycles, and any uniformity analysis is limited to
 those static instances whose convergence is independent of the cycle
 hierarchy:
 
+.. _convergence-m-converged:
+
   **m-converged static instances:**
 
   A static instance ``X`` is *m-converged* for a given CFG if and only
   if the maximal converged-with relation for its dynamic instances is
   the same in every cycle hierarchy that can be constructed for that CFG.
 
   .. note::
 

 
 .. note::
 
    A reducible cycle :ref:`trivially satisfies
    <convergence-reducible-cycle>` the above conditions. In particular,
    if the whole CFG is reducible, then all nodes in the CFG are
    m-converged.
 
-If a static instance is not m-converged, then every output is assumed
-to be divergent. Otherwise, for an m-converged static instance, the
-uniformity of each output is determined using the criteria
+The uniformity of each output of a static instance
+is determined using the criteria
 :ref:`described earlier <convergence-uniformity>`. The discovery of
 divergent outputs may cause their uses (including branches) to also
 become divergent. The analysis propagates this divergence until a
 fixed point is reached.
 
 The convergence inferred using these criteria is a safe subset of the
 maximal converged-with relation for any cycle hierarchy. In
 particular, it is sufficient to determine if a static instance is

llvm/include/llvm/ADT/GenericUniformityImpl.h

if (I.isTerminator()) {
     if (DivergentTermBlocks.insert(I.getParent()).second) {
       LLVM_DEBUG(dbgs() << "marked divergent term block: "
                         << Context.print(I.getParent()) << "\n");
       return true;
     }
     return false;
   }
 
+  if (isAlwaysUniform(I))
+    return false;
+
   return markDefsDivergent(I);
 }
 
 template <typename ContextT>
 bool GenericUniformityAnalysisImpl<ContextT>::markDivergent(
     ConstValueRefT Val) {
   if (DivergentValues.insert(Val).second) {
     LLVM_DEBUG(dbgs() << "marked divergent: " << Context.print(Val) << "\n");
void GenericUniformityAnalysisImpl<ContextT>::taintAndPushAllDefs(
   LLVM_DEBUG(dbgs() << "taintAndPushAllDefs " << Context.print(&BB) << "\n");
   for (const auto &I : instrs(BB)) {
     // Terminators do not produce values; they are divergent only if
     // the condition is divergent. That is handled when the divergent
     // condition is placed in the worklist.
     if (I.isTerminator())
       break;
 
-    // Mark this as divergent. We don't check if the instruction is
-    // always uniform. In a cycle where the thread convergence is not
-    // statically known, the instruction is not statically converged,
-    // and its outputs cannot be statically uniform.
     if (markDivergent(I))
       Worklist.push_back(&I);
   }
 }
 
 /// Mark divergent phi nodes in a join block
 template <typename ContextT>
 void GenericUniformityAnalysisImpl<ContextT>::taintAndPushPhiNodes(

llvm/lib/Analysis/UniformityAnalysis.cpp

for (auto &Arg : F.args()) {
     }
   }
 }
 
 template <>
 void llvm::GenericUniformityAnalysisImpl<SSAContext>::pushUsers(
     const Value *V) {
   for (const auto *User : V->users()) {
-    const auto *UserInstr = dyn_cast<const Instruction>(User);
-    if (!UserInstr)
-      continue;
-    if (isAlwaysUniform(*UserInstr))
-      continue;
+    if (const auto *UserInstr = dyn_cast<const Instruction>(User)) {
       if (markDivergent(*UserInstr)) {
         Worklist.push_back(UserInstr);
       }
     }
   }
+}
 
 template <>
 void llvm::GenericUniformityAnalysisImpl<SSAContext>::pushUsers(
     const Instruction &Instr) {
   assert(!isAlwaysUniform(Instr));
   if (Instr.isTerminator())
     return;
   pushUsers(cast<Value>(&Instr));
 }
 
 template <>
 bool llvm::GenericUniformityAnalysisImpl<SSAContext>::usesValueFromCycle(
     const Instruction &I, const Cycle &DefCycle) const {

llvm/lib/CodeGen/MachineUniformityAnalysis.cpp

void llvm::GenericUniformityAnalysisImpl<MachineSSAContext>::initialize() {
   }
 }
 
 template <>
 void llvm::GenericUniformityAnalysisImpl<MachineSSAContext>::pushUsers(
     Register Reg) {
   const auto &RegInfo = F.getRegInfo();
   for (MachineInstr &UserInstr : RegInfo.use_instructions(Reg)) {
-    if (isAlwaysUniform(UserInstr))
-      continue;
     if (markDivergent(UserInstr))
       Worklist.push_back(&UserInstr);
   }
 }
 
 template <>
 void llvm::GenericUniformityAnalysisImpl<MachineSSAContext>::pushUsers(
     const MachineInstr &Instr) {

llvm/test/Analysis/DivergenceAnalysis/AMDGPU/irreducible/irreducible-2.ll

 
 C:
   br i1 %uni.cond, label %X, label %E1
 
 X:
   ret void
 }
 
+define amdgpu_kernel void @always_uniform() {
+; CHECK-LABEL: UniformityInfo for function 'always_uniform':
+; CHECK: CYCLES ASSSUMED DIVERGENT:
+; CHECK:   depth=1: entries(bb2 bb3)
+
+bb:
+  %inst = tail call i32 @llvm.amdgcn.mbcnt.hi(i32 0, i32 0)
+  %inst1 = icmp ugt i32 %inst, 0
+  br i1 %inst1, label %bb3, label %bb2
+; CHECK:   DIVERGENT:   %inst = tail call i32 @llvm.amdgcn.mbcnt.hi(i32 0, i32 0)
+; CHECK:   DIVERGENT:   %inst1 = icmp ugt i32 %inst, 0
+; CHECK:   DIVERGENT:   br i1 %inst1, label %bb3, label %bb2
+
+bb2:                                              ; preds = %bb3, %bb
+  br label %bb3
+
+bb3:                                              ; preds = %bb2, %bb
+  %inst4 = tail call i64 @llvm.amdgcn.icmp.i64.i16(i16 0, i16 0, i32 0)
+  %inst5 = trunc i64 %inst4 to i32
+  %inst6 = and i32 0, %inst5
+  br label %bb2
+; CHECK-LABEL: BLOCK bb3
+; CHECK-NOT: DIVERGENT: {{.*}} call i64 @llvm.amdgcn.icmp.i64.i16
+; CHECK:   DIVERGENT:   %inst5 = trunc i64 %inst4 to i32
+; CHECK:   DIVERGENT:   %inst6 = and i32 0, %inst5
+}
+
+declare i32 @llvm.amdgcn.mbcnt.hi(i32, i32)
+
+declare i64 @llvm.amdgcn.icmp.i64.i16(i16, i16, i32 immarg)
+
 declare i32 @llvm.amdgcn.workitem.id.x() #0
 
 attributes #0 = { nounwind readnone }