[LLVM][Uniformity] Propagate divergence only along divergent outputs.

[sameerds]

Summary

When an instruction is determined to be divergent, not all its outputs are
divergent. The users of only divergent outputs should now be examined for
divergence.

Also, replaced a repeating pattern of "if new divergent instruction, then add to
worklist" by combining it into a single function. This does not cause any change
in functionality.

[foad]

LGTM with or without nits addressed.

llvm/include/llvm/ADT/GenericUniformityImpl.h

358–362

Maybe it's time to comment each function separately? The one you've changed no longer returns anything.

793–795

else after return looks odd and it seems easy to avoid it here.

[sameerds]

• added a small but important fix
• eliminated return-after-else

[sameerds]

Requesting a fresh review because I added a fix. markDefsDivergent() only records divergent outputs of a multi-output instruction, but pushUsers() was blindly propagating divergence along the uses of the uniform outputs. The change was small and related to what I was doing, so didn't create a separate review. This eliminates a FIXME in an existing MIR test.

[foad]

llvm/test/Analysis/UniformityAnalysis/AMDGPU/MIR/always-uniform-gmir.mir

100

Just checking my understanding: this should have said "FIXME: first output of below inline asm should be uniform"?

[sameerds]

llvm/test/Analysis/UniformityAnalysis/AMDGPU/MIR/always-uniform-gmir.mir

100

That is my understanding too! After recent changes, it is certainly true that the s32 output should be uniform, and this current change ensures that its use in the COPY instruction also remains uniform. If I revert the current change but keep this test, then the CHECK-NOT fails for %4.

llvm/include/llvm/ADT/GenericUniformityImpl.h

public:
 
   void initialize();
 
   const FunctionT &getFunction() const { return F; }
 
   /// \brief Mark \p UniVal as a value that is always uniform.
   void addUniformOverride(const InstructionT &Instr);
 
-  /// \brief Mark \p DivVal as a value that is always divergent.
+  /// \brief Examine \p I for divergent outputs and add to the worklist.
+  void markDivergent(const InstructionT &I);
+
+  /// \brief Mark \p DivVal as a divergent value.
   /// \returns Whether the tracked divergence state of \p DivVal changed.
-  bool markDivergent(const InstructionT &I);
   bool markDivergent(ConstValueRefT DivVal);
+
+  /// \brief Mark outputs of \p Instr as divergent.
+  /// \returns Whether the tracked divergence state of any output has changed.
   bool markDefsDivergent(const InstructionT &Instr);
 
   /// \brief Propagate divergence to all instructions in the region.
   /// Divergence is seeded by calls to \p markDivergent.
   void compute();
 
   /// \brief Whether any value was marked or analyzed to be divergent.
   bool hasDivergence() const { return !DivergentValues.empty(); }
auto llvm::GenericSyncDependenceAnalysis<ContextT>::getJoinBlocks(
 
   auto ItInserted =
       CachedControlDivDescs.try_emplace(DivTermBlock, std::move(DivDesc));
   assert(ItInserted.second);
   return *ItInserted.first->second;
 }
 
 template <typename ContextT>
-bool GenericUniformityAnalysisImpl<ContextT>::markDivergent(
+void GenericUniformityAnalysisImpl<ContextT>::markDivergent(
     const InstructionT &I) {
+  if (isAlwaysUniform(I))
+    return;
+  bool Marked = false;
   if (I.isTerminator()) {
-    if (DivergentTermBlocks.insert(I.getParent()).second) {
+    Marked = DivergentTermBlocks.insert(I.getParent()).second;
+    if (Marked) {
       LLVM_DEBUG(dbgs() << "marked divergent term block: "
                         << Context.print(I.getParent()) << "\n");
-      return true;
     }
-    return false;
+  } else {
+    Marked = markDefsDivergent(I);
   }
 
-  if (isAlwaysUniform(I))
-    return false;
-
-  return markDefsDivergent(I);
+  if (Marked)
+    Worklist.push_back(&I);
 }
 
 template <typename ContextT>
 bool GenericUniformityAnalysisImpl<ContextT>::markDivergent(
     ConstValueRefT Val) {
   if (DivergentValues.insert(Val).second) {
     LLVM_DEBUG(dbgs() << "marked divergent: " << Context.print(Val) << "\n");
     return true;

 template <typename ContextT>
 void GenericUniformityAnalysisImpl<ContextT>::analyzeCycleExitDivergence(
     const CycleT &DefCycle) {
   SmallVector<BlockT *> Exits;
   DefCycle.getExitBlocks(Exits);
   for (auto *Exit : Exits) {
     for (auto &Phi : Exit->phis()) {
       if (usesValueFromCycle(Phi, DefCycle)) {
-        if (markDivergent(Phi))
-          Worklist.push_back(&Phi);
+        markDivergent(Phi);
       }
     }
   }
 
   for (auto *BB : DefCycle.blocks()) {
     if (!llvm::any_of(Exits,
                      [&](BlockT *Exit) { return DT.dominates(BB, Exit); }))
       continue;
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;
 
-    if (markDivergent(I))
-      Worklist.push_back(&I);
+    markDivergent(I);
   }
 }
 
 /// Mark divergent phi nodes in a join block
 template <typename ContextT>
 void GenericUniformityAnalysisImpl<ContextT>::taintAndPushPhiNodes(
     const BlockT &JoinBlock) {
   LLVM_DEBUG(dbgs() << "taintAndPushPhiNodes in " << Context.print(&JoinBlock)
                     << "\n");
   for (const auto &Phi : JoinBlock.phis()) {
     // FIXME: The non-undef value is not constant per se; it just happens to be
     // uniform and may not dominate this PHI. So assuming that the same value
     // reaches along all incoming edges may itself be undefined behaviour. This
     // particular interpretation of the undef value was added to
     // DivergenceAnalysis in the following review:
     //
     // https://reviews.llvm.org/D19013
     if (ContextT::isConstantOrUndefValuePhi(Phi))
       continue;
-    if (markDivergent(Phi))
-      Worklist.push_back(&Phi);
+    markDivergent(Phi);
   }
 }
 
 /// Add \p Candidate to \p Cycles if it is not already contained in \p Cycles.
 ///
 /// \return true iff \p Candidate was added to \p Cycles.
 template <typename CycleT>
 static bool insertIfNotContained(SmallVector<CycleT *> &Cycles,

llvm/lib/Analysis/UniformityAnalysis.cpp

 bool llvm::GenericUniformityAnalysisImpl<SSAContext>::hasDivergentDefs(
     const Instruction &I) const {
   return isDivergent((const Value *)&I);
 }
 
 template <>
 bool llvm::GenericUniformityAnalysisImpl<SSAContext>::markDefsDivergent(
     const Instruction &Instr) {
-  return markDivergent(&Instr);
+  return markDivergent(cast<Value>(&Instr));
 }
 
 template <> void llvm::GenericUniformityAnalysisImpl<SSAContext>::initialize() {
   for (auto &I : instructions(F)) {
     if (TTI->isSourceOfDivergence(&I))
       markDivergent(I);
     else if (TTI->isAlwaysUniform(&I))
       addUniformOverride(I);
   }
   for (auto &Arg : F.args()) {
     if (TTI->isSourceOfDivergence(&Arg)) {
       markDivergent(&Arg);
     }
   }
 }
 
 template <>
 void llvm::GenericUniformityAnalysisImpl<SSAContext>::pushUsers(
     const Value *V) {
   for (const auto *User : V->users()) {
     if (const auto *UserInstr = dyn_cast<const Instruction>(User)) {
-      if (markDivergent(*UserInstr)) {
-        Worklist.push_back(UserInstr);
-      }
+      markDivergent(*UserInstr);
     }
   }
 }
 
 template <>
 void llvm::GenericUniformityAnalysisImpl<SSAContext>::pushUsers(
     const Instruction &Instr) {
   assert(!isAlwaysUniform(Instr));
void llvm::GenericUniformityAnalysisImpl<
     SSAContext>::propagateTemporalDivergence(const Instruction &I,
                                              const Cycle &DefCycle) {
   if (isDivergent(I))
     return;
   for (auto *User : I.users()) {
     auto *UserInstr = cast<Instruction>(User);
     if (DefCycle.contains(UserInstr->getParent()))
       continue;
-    if (markDivergent(*UserInstr))
-      Worklist.push_back(UserInstr);
+    markDivergent(*UserInstr);
   }
 }
 
 template <>
 bool llvm::GenericUniformityAnalysisImpl<SSAContext>::isDivergentUse(
     const Use &U) const {
   const auto *V = U.get();
   if (isDivergent(V))

llvm/lib/CodeGen/MachineUniformityAnalysis.cpp

for (const MachineBasicBlock &block : F) {
     for (const MachineInstr &instr : block) {
       auto uniformity = InstrInfo.getInstructionUniformity(instr);
       if (uniformity == InstructionUniformity::AlwaysUniform) {
         addUniformOverride(instr);
         continue;
       }
 
       if (uniformity == InstructionUniformity::NeverUniform) {
-        if (markDivergent(instr))
-          Worklist.push_back(&instr);
+        markDivergent(instr);
       }
     }
   }
 }
 
 template <>
 void llvm::GenericUniformityAnalysisImpl<MachineSSAContext>::pushUsers(
     Register Reg) {
+  assert(isDivergent(Reg));
   const auto &RegInfo = F.getRegInfo();
   for (MachineInstr &UserInstr : RegInfo.use_instructions(Reg)) {
-    if (markDivergent(UserInstr))
-      Worklist.push_back(&UserInstr);
+    markDivergent(UserInstr);
   }
 }
 
 template <>
 void llvm::GenericUniformityAnalysisImpl<MachineSSAContext>::pushUsers(
     const MachineInstr &Instr) {
   assert(!isAlwaysUniform(Instr));
   if (Instr.isTerminator())
     return;
   for (const MachineOperand &op : Instr.operands()) {
-    if (op.isReg() && op.isDef() && op.getReg().isVirtual())
-      pushUsers(op.getReg());
+    if (!op.isReg() || !op.isDef())
+      continue;
+    auto Reg = op.getReg();
+    if (isDivergent(Reg))
+      pushUsers(Reg);
   }
 }
 
 template <>
 bool llvm::GenericUniformityAnalysisImpl<MachineSSAContext>::usesValueFromCycle(
     const MachineInstr &I, const MachineCycle &DefCycle) const {
   assert(!isAlwaysUniform(I));
   for (auto &Op : I.operands()) {
for (auto &Op : I.operands()) {
     if (!Op.getReg().isVirtual())
       continue;
     auto Reg = Op.getReg();
     if (isDivergent(Reg))
       continue;
     for (MachineInstr &UserInstr : RegInfo.use_instructions(Reg)) {
       if (DefCycle.contains(UserInstr.getParent()))
         continue;
-      if (markDivergent(UserInstr))
-        Worklist.push_back(&UserInstr);
+      markDivergent(UserInstr);
     }
   }
 }
 
 template <>
 bool llvm::GenericUniformityAnalysisImpl<MachineSSAContext>::isDivergentUse(
     const MachineOperand &U) const {
   if (!U.isReg())

llvm/test/Analysis/UniformityAnalysis/AMDGPU/MIR/always-uniform-gmir.mir

bb.0:
     %2:vgpr_32 = COPY %0(s32)
     INLINEASM &"; def $0, $1", 0 /* attdialect */, 1966090 /* regdef:SReg_32 */, def %1, 1835017 /* reguse:VGPR_32 */, %2
     %3:_(s32) = COPY %1
     $vgpr0 = COPY %3(s32)
     SI_RETURN implicit $vgpr0
 
 ...
 
-# FIXME :: BELOW INLINE ASM SHOULD BE DIVERGENT
 ---
 name:            asm_mixed_sgpr_vgpr
 registers:
   - { id: 0, class: _, preferred-register: '' }
   - { id: 1, class: sreg_32, preferred-register: '' }
   - { id: 2, class: vgpr_32, preferred-register: '' }
   - { id: 3, class: vgpr_32, preferred-register: '' }
   - { id: 4, class: _, preferred-register: '' }
   - { id: 5, class: _, preferred-register: '' }
   - { id: 6, class: _, preferred-register: '' }
 liveins:         []
 frameInfo:
 body:             |
   bb.0:
     liveins: $vgpr0
     ; CHECK-LABEL: MachineUniformityInfo for function: asm_mixed_sgpr_vgpr
     ; CHECK: DIVERGENT: %0:
     ; CHECK: DIVERGENT: %3:
+    ; CHECK-NOT: DIVERGENT: %1:
     ; CHECK: DIVERGENT: %2:
+    ; CHECK-NOT: DIVERGENT: %4:
     ; CHECK: DIVERGENT: %5:
     %0:_(s32) = COPY $vgpr0
     %6:_(p1) = G_IMPLICIT_DEF
     %3:vgpr_32 = COPY %0(s32)
     INLINEASM &"; def $0, $1, $2", 0 /* attdialect */, 1966090 /* regdef:SReg_32 */, def %1, 1835018 /* regdef:VGPR_32 */, def %2, 1835017 /* reguse:VGPR_32 */, %3
     %4:_(s32) = COPY %1
     %5:_(s32) = COPY %2
     G_STORE %5(s32), %6(p1) :: (store (s32) into `i32 addrspace(1)* undef`, addrspace 1)
     SI_RETURN
 
 ...