[llvm][Uniformity] a phi with an undef argument is not always divergent

[sameerds]

Summary

The uniformity analysis treated an undef argument to phi to be distinct from any
other argument, equivalent to calling PHINode::hasConstantValue() instead of
PHINode::hasConstantOrUndefValue(). Such a phi was reported as divergent. This
is different from the older divergence analysis which treats such a phi as
uniform. Fixed uniformity analysis to match the older behaviour.

[foad]

I like this but I will leave it to the other reviewers to approve, since I know they have expressed doubts in the past.

llvm/include/llvm/ADT/GenericSSAContext.h

62 ↗

(On Diff #498311)

Commit this file separately?

[ruiling]

Although I wanted the optimization for the undef case to be bring back in a more defined way, I think it is acceptable to match with existing divergence analysis. This would help with the transition to uniform analysis, so LGTM. Please also address Jay's suggestion. Could you also add some FIXME around the code like: optimally reporting uniform with undef input should be done in more defined way. In general CFG, it might be broken?

llvm/include/llvm/ADT/GenericUniformityImpl.h

 
 /// 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()) {
-    if (ContextT::isConstantValuePhi(Phi))
+    // 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);
   }
 }
 
 /// Add \p Candidate to \p Cycles if it is not already contained in \p Cycles.
 ///

llvm/include/llvm/CodeGen/MachineSSAContext.h

public:
   static MachineBasicBlock *getEntryBlock(MachineFunction &F);
   static void appendBlockDefs(SmallVectorImpl<Register> &defs,
                               const MachineBasicBlock &block);
   static void appendBlockTerms(SmallVectorImpl<MachineInstr *> &terms,
                                MachineBasicBlock &block);
   static void appendBlockTerms(SmallVectorImpl<const MachineInstr *> &terms,
                                const MachineBasicBlock &block);
   MachineBasicBlock *getDefBlock(Register) const;
-  static bool isConstantValuePhi(const MachineInstr &Phi);
+  static bool isConstantOrUndefValuePhi(const MachineInstr &Phi);
 
   Printable print(const MachineBasicBlock *Block) const;
   Printable print(const MachineInstr *Inst) const;
   Printable print(Register Value) const;
 };
 
 using MachineSSAContext = GenericSSAContext<MachineFunction>;
 } // namespace llvm
 
 #endif // LLVM_CODEGEN_MACHINESSACONTEXT_H

llvm/include/llvm/IR/SSAContext.h

static void appendBlockDefs(SmallVectorImpl<const Value *> &defs,
                               const BasicBlock &block);
 
   static void appendBlockTerms(SmallVectorImpl<Instruction *> &terms,
                                BasicBlock &block);
   static void appendBlockTerms(SmallVectorImpl<const Instruction *> &terms,
                                const BasicBlock &block);
 
   static bool comesBefore(const Instruction *lhs, const Instruction *rhs);
-  static bool isConstantValuePhi(const Instruction &Instr);
+  static bool isConstantOrUndefValuePhi(const Instruction &Instr);
   const BasicBlock *getDefBlock(const Value *value) const;
 
   Printable print(const BasicBlock *Block) const;
   Printable print(const Instruction *Inst) const;
   Printable print(const Value *Value) const;
 };
 
 using SSAContext = GenericSSAContext<Function>;
 
 } // namespace llvm
 
 #endif // LLVM_IR_SSACONTEXT_H

llvm/lib/CodeGen/MachineSSAContext.cpp

 
 /// Get the defining block of a value.
 MachineBasicBlock *MachineSSAContext::getDefBlock(Register value) const {
   if (!value)
     return nullptr;
   return RegInfo->getVRegDef(value)->getParent();
 }
 
-bool MachineSSAContext::isConstantValuePhi(const MachineInstr &Phi) {
+bool MachineSSAContext::isConstantOrUndefValuePhi(const MachineInstr &Phi) {
   return Phi.isConstantValuePHI();
 }
 
 Printable MachineSSAContext::print(const MachineBasicBlock *Block) const {
   if (!Block)
     return Printable([](raw_ostream &Out) { Out << "<nullptr>"; });
   return Printable([Block](raw_ostream &Out) { Block->printName(Out); });
 }

llvm/lib/IR/SSAContext.cpp

if (const auto *instruction = dyn_cast<Instruction>(value))
     return instruction->getParent();
   return nullptr;
 }
 
 bool SSAContext::comesBefore(const Instruction *lhs, const Instruction *rhs) {
   return lhs->comesBefore(rhs);
 }
 
-bool SSAContext::isConstantValuePhi(const Instruction &Instr) {
+bool SSAContext::isConstantOrUndefValuePhi(const Instruction &Instr) {
   if (auto *Phi = dyn_cast<PHINode>(&Instr))
-    return Phi->hasConstantValue();
+    return Phi->hasConstantOrUndefValue();
   return false;
 }
 
 Printable SSAContext::print(const Value *V) const {
   return Printable([V](raw_ostream &Out) { V->print(Out); });
 }
 
 Printable SSAContext::print(const Instruction *Inst) const {

llvm/test/Analysis/DivergenceAnalysis/AMDGPU/phi-undef.ll

-; RUN: opt -mtriple amdgcn-- -passes='print<divergence>' -disable-output %s 2>&1 | FileCheck %s --check-prefixes=CHECK,LOOPDA
-; RUN: opt -mtriple amdgcn-- -passes='print<uniformity>' -disable-output %s 2>&1 | FileCheck %s --check-prefixes=CHECK,CYCLEDA
+; RUN: opt -mtriple amdgcn-- -passes='print<divergence>' -disable-output %s 2>&1 | FileCheck %s
+; RUN: opt -mtriple amdgcn-- -passes='print<uniformity>' -disable-output %s 2>&1 | FileCheck %s
 
 ; CHECK-LABEL: 'test1':
 ; CHECK: DIVERGENT: i32 %bound
-; CYCLEDA: DIVERGENT: %counter =
-; LOOPDA: {{^  *}} %counter =
-; CHECK-NEXT: DIVERGENT: %break = icmp sge i32 %counter, %bound
-; CYCLEDA: DIVERGENT: %counter.next =
-; CYCLEDA: DIVERGENT: %counter.footer =
-; LOOPDA: {{^  *}}%counter.next =
-; LOOPDA: {{^  *}}%counter.footer =
+; CHECK: {{^  *}} %counter =
+; CHECK: DIVERGENT: %break = icmp sge i32 %counter, %bound
+; CHECK: DIVERGENT: br i1 %break, label %footer, label %body
+; CHECK: {{^  *}}%counter.next =
+; CHECK: {{^  *}}%counter.footer =
+; CHECK: DIVERGENT: br i1 %break, label %end, label %header
 
 ; Note: %counter is not divergent!
 
 define amdgpu_ps void @test1(i32 %bound) {
 entry:
   br label %header
 
 header: