SIFixSGPRCopies should not change non-divergent PHI

[alex-t]

Summary

According to the comment in the code SIFixSGPRCopies claims that it check if PHI is uniform by examination of the terminator of the nearest common dominator of the joined values.

1. nearest common dominator check is not sufficient for control dependency analysis (see https://www.cs.rice.edu/~keith/EMBED/dom.pdf for details)
2. Current code does not even does what the comments claims. It really turn PHI (and all it's uses) to vector if any of the PHI's parent block predecessors is divergent.

This change introduces post-dominance frontiers computing procedure and uses the results to decide if the PHI is divergent.

[rampitec]

lib/Target/AMDGPU/SIFixSGPRCopies.cpp

116 ↗

(On Diff #124565)

Check for NDEBUG here.

[arsenm]

lib/Target/AMDGPU/SIFixSGPRCopies.cpp

391–422 ↗

(On Diff #124565)

These aren't used anymore and should be deleted

571 ↗

(On Diff #124565)

Reformat entire function

600 ↗

(On Diff #124565)

Single quotes

602 ↗

(On Diff #124565)

Single quotes

680–681 ↗

(On Diff #124565)

References?

[alex-t]

updated according to the comments

[rampitec]

LGTM

[hakzsam]

Hi guys,

This change appears to introduce a regression. It hangs nier:automata with the RADV Vulkan driver, reverting the commit fixes the issue.

Here's the full LLVM IR of that shader https://hastebin.com/minayakiri

I have also tried to reduce the testcase, but I'm not 100% sure it's correct, in case you want to have a look too https://hastebin.com/olatenegej

After comparing with/without that change, it appears that some VGPR PHIs are SGPR PHIs now.

I know this is why this change has been submitted initially (ie. to not use VGPR PHIs when the control flow is uniform), but I wonder if the new postdominance frontier is correct is *all* situations.

The concept of VGPR/SGPR PHIs seems tricky and I'm not sure to fully understand it.

Can you check (and/or explain) if the SGPR PHIs in that shader are expected?

Thanks in advance,
Samuel.

[alex-t]

Hi Samuel,

sure I will look at this. I'll let you know when I get an idea of what
going wrong there.

Alexander

[nhaehnle]

Is this related to D40547? I sent a ping on that, but no response...

[alex-t]

I m looking on this.

17 марта 2018 г. 3:27 PM пользователь "Nicolai Hähnle via Phabricator" <
[e-mail]> написал:

nhaehnle added a comment.

Is this related to https://reviews.llvm.org/D40547? I sent a ping on
that, but no response...

Repository:

rL LLVM

https://reviews.llvm.org/D40556

[alex-t]

It seems like this patch should be reverted. Recently we have no reliable
way to determine the PHI (or whatever else) divergence on the MI level.
The only correct way is to add the DA algorithm that re-computes all the MI
divergence.
Since we're going to remove the SGPRFix stuff as soon as diverence driven
ISel is ready I consider this patch is not necessary.

[hakzsam]

In D40556#1061436, @alex-t wrote:

It seems like this patch should be reverted. Recently we have no reliable
way to determine the PHI (or whatever else) divergence on the MI level.
The only correct way is to add the DA algorithm that re-computes all the MI
divergence.
Since we're going to remove the SGPRFix stuff as soon as diverence driven
ISel is ready I consider this patch is not necessary.

Thanks for looking into this. The main issue I see with a revert is that we will need a backport to LLVM 6.

Though, if it's the only solution for now, this sounds good to me.

[alex-t]

In fact yes. This is the most correct solution. The stuff in
SIFixSGPRCopies.cpp has got to gone.
So it does not make sense to spend efforts on it. Moreover there is no
correct solution at all
unless we implement one more DivergenceAnalysis upon the machine IR.
So, if it's okay I'd prefer to revert.

[hakzsam]

In D40556#1062962, @alex-t wrote:

In fact yes. This is the most correct solution. The stuff in
SIFixSGPRCopies.cpp has got to gone.
So it does not make sense to spend efforts on it. Moreover there is no
correct solution at all
unless we implement one more DivergenceAnalysis upon the machine IR.
So, if it's okay I'd prefer to revert.

I'm fine with the revert because this change introduces hangs in a bunch of games apparently.

Do you think it's doable to backport the revert to LLVM 6 as well?

Thanks!

[alex-t]

I have no idea how to backport yet.
I 'my going to submit revert patch.
This change existed for a few months and I' my not sure what may be broken
if reverted. I have to figure out this. Some precheckin tests needed.

пт, 13 апр. 2018 г., 10:36 Samuel Pitoiset via Phabricator <
[e-mail]>:

hakzsam added a comment.

In https://reviews.llvm.org/D40556#1062962, @alex-t wrote:

In fact yes. This is the most correct solution. The stuff in
SIFixSGPRCopies.cpp has got to gone.
So it does not make sense to spend efforts on it. Moreover there is no
correct solution at all
unless we implement one more DivergenceAnalysis upon the machine IR.
So, if it's okay I'd prefer to revert.

I'm fine with the revert because this change introduces hangs in a bunch
of games apparently.

Do you think it's doable to backport the revert to LLVM 6 as well?

Thanks!

Repository:

rL LLVM

https://reviews.llvm.org/D40556

[hakzsam]

Hi,

Any news on the revert? Thanks!

[alex-t]

Sorry for the delay. Just submitted to trunk.
It was not about the reverse patch only. I had to change tests accordingly.

[hakzsam]

In D40556#1077975, @alex-t wrote:

Sorry for the delay. Just submitted to trunk.
It was not about the reverse patch only. I had to change tests accordingly.

Thanks a lot!

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

 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineOperand.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/MachinePostDominators.h"
 #include "llvm/CodeGen/TargetRegisterInfo.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/CodeGen.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Target/TargetMachine.h"
 #include <cassert>
static cl::opt<bool> EnableM0Merge(
   "amdgpu-enable-merge-m0",
   cl::desc("Merge and hoist M0 initializations"),
   cl::init(false));
 
 namespace {
 
 class SIFixSGPRCopies : public MachineFunctionPass {
   MachineDominatorTree *MDT;
-
+  MachinePostDominatorTree *MPDT;
+  DenseMap<MachineBasicBlock *, SetVector<MachineBasicBlock*>> PDF;
+  void computePDF(MachineFunction * MF);
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+  void printPDF();
+#endif
 public:
   static char ID;
 
   SIFixSGPRCopies() : MachineFunctionPass(ID) {}
 
   bool runOnMachineFunction(MachineFunction &MF) override;
 
   StringRef getPassName() const override { return "SI Fix SGPR copies"; }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<MachineDominatorTree>();
     AU.addPreserved<MachineDominatorTree>();
+    AU.addRequired<MachinePostDominatorTree>();
+    AU.addPreserved<MachinePostDominatorTree>();
     AU.setPreservesCFG();
     MachineFunctionPass::getAnalysisUsage(AU);
   }
 };
 
 } // end anonymous namespace
 
 INITIALIZE_PASS_BEGIN(SIFixSGPRCopies, DEBUG_TYPE,
if (Predicate(MBB))
       return true;
 
     Worklist.append(MBB->pred_begin(), MBB->pred_end());
   }
 
   return false;
 }
 
-static bool predsHasDivergentTerminator(MachineBasicBlock *MBB,
-                                        const TargetRegisterInfo *TRI) {
-  return searchPredecessors(MBB, nullptr, [TRI](MachineBasicBlock *MBB) {
-           return hasTerminatorThatModifiesExec(*MBB, *TRI); });
-}
-
 // Checks if there is potential path From instruction To instruction.
 // If CutOff is specified and it sits in between of that path we ignore
 // a higher portion of the path and report it is not reachable.
 static bool isReachable(const MachineInstr *From,
                         const MachineInstr *To,
                         const MachineBasicBlock *CutOff,
                         MachineDominatorTree &MDT) {
   // If either From block dominates To block or instructions are in the same
static bool hoistAndMergeSGPRInits(unsigned Reg,
   }
 
   if (Changed)
     MRI.clearKillFlags(Reg);
 
   return Changed;
 }
 
+void SIFixSGPRCopies::computePDF(MachineFunction *MF) {
+  MachineFunction::iterator B = MF->begin();
+  MachineFunction::iterator E = MF->end();
+  for (; B != E; ++B) {
+    if (B->succ_size() > 1) {
+      for (auto S : B->successors()) {
+        MachineDomTreeNode *runner = MPDT->getNode(&*S);
+        MachineDomTreeNode *sentinel = MPDT->getNode(&*B)->getIDom();
+        while (runner && runner != sentinel) {
+          PDF[runner->getBlock()].insert(&*B);
+          runner = runner->getIDom();
+        }
+      }
+    }
+  }
+}
+
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+void SIFixSGPRCopies::printPDF() {
+  dbgs() << "\n######## PostDominanceFrontiers set #########\n";
+  for (auto &I : PDF) {
+    dbgs() << "PDF[ " << I.first->getNumber() << "] : ";
+    for (auto &J : I.second) {
+      dbgs() << J->getNumber() << ' ';
+    }
+    dbgs() << '\n';
+  }
+  dbgs() << "\n##############################################\n";
+}
+#endif
+
 bool SIFixSGPRCopies::runOnMachineFunction(MachineFunction &MF) {
   const SISubtarget &ST = MF.getSubtarget<SISubtarget>();
   MachineRegisterInfo &MRI = MF.getRegInfo();
   const SIRegisterInfo *TRI = ST.getRegisterInfo();
   const SIInstrInfo *TII = ST.getInstrInfo();
   MDT = &getAnalysis<MachineDominatorTree>();
+  MPDT = &getAnalysis<MachinePostDominatorTree>();
+  PDF.clear();
+  computePDF(&MF);
+  DEBUG(printPDF());
 
   SmallVector<MachineInstr *, 16> Worklist;
 
   for (MachineFunction::iterator BI = MF.begin(), BE = MF.end();
                                                   BI != BE; ++BI) {
     MachineBasicBlock &MBB = *BI;
     for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end();
          I != E; ++I) {
for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end();
 
         break;
       }
       case AMDGPU::PHI: {
         unsigned Reg = MI.getOperand(0).getReg();
         if (!TRI->isSGPRClass(MRI.getRegClass(Reg)))
           break;
 
-        // We don't need to fix the PHI if the common dominator of the
-        // two incoming blocks terminates with a uniform branch.
+        // We don't need to fix the PHI if all the source blocks
+        // have no divergent control dependecies
         bool HasVGPROperand = phiHasVGPROperands(MI, MRI, TRI, TII);
-        if (MI.getNumExplicitOperands() == 5 && !HasVGPROperand) {
-          MachineBasicBlock *MBB0 = MI.getOperand(2).getMBB();
-          MachineBasicBlock *MBB1 = MI.getOperand(4).getMBB();
-
-          if (!predsHasDivergentTerminator(MBB0, TRI) &&
-              !predsHasDivergentTerminator(MBB1, TRI)) {
+        if (!HasVGPROperand) {
+          bool Uniform = true;
+          MachineBasicBlock * Join = MI.getParent();
+          for (auto &O : MI.explicit_operands()) {
+            if (O.isMBB()) {
+              MachineBasicBlock * Source = O.getMBB();
+              SetVector<MachineBasicBlock*> &SourcePDF = PDF[Source];
+              SetVector<MachineBasicBlock*> &JoinPDF   = PDF[Join];
+              SetVector<MachineBasicBlock*> CDList;
+              for (auto &I : SourcePDF) {
+                if (!JoinPDF.count(I) || /* back edge */MDT->dominates(Join, I)) {
+                  if (hasTerminatorThatModifiesExec(*I, *TRI))
+                    Uniform = false;
+                }
+              }
+            }
+          }
+          if (Uniform) {
             DEBUG(dbgs() << "Not fixing PHI for uniform branch: " << MI << '\n');
             break;
           }
         }
 
         // If a PHI node defines an SGPR and any of its operands are VGPRs,
         // then we need to move it to the VALU.
         //

llvm/trunk/test/CodeGen/AMDGPU/control-flow-fastregalloc.ll

 
 endif:
   %tmp4 = phi i32 [ %val, %if ], [ 0, %entry ]
   store i32 %tmp4, i32 addrspace(1)* %out
   ret void
 }
 
 ; GCN-LABEL: {{^}}divergent_loop:
-; VGPR: workitem_private_segment_byte_size = 16{{$}}
+; VGPR: workitem_private_segment_byte_size = 12{{$}}
 
 ; GCN: {{^}}; BB#0:
 
 ; GCN: s_mov_b32 m0, -1
 ; GCN: ds_read_b32 [[LOAD0:v[0-9]+]]
 
 ; GCN: v_cmp_eq_u32_e64 [[CMP0:s\[[0-9]+:[0-9]\]]], s{{[0-9]+}}, v0
 

 
 ; GCN-NEXT: ; mask branch [[END:BB[0-9]+_[0-9]+]]
 ; GCN-NEXT: s_cbranch_execz [[END]]
 
 
 ; GCN: [[LOOP:BB[0-9]+_[0-9]+]]:
 ; GCN: buffer_load_dword v[[VAL_LOOP_RELOAD:[0-9]+]], off, s[0:3], s7 offset:4 ; 4-byte Folded Reload
 ; GCN: v_subrev_i32_e32 [[VAL_LOOP:v[0-9]+]], vcc, v{{[0-9]+}}, v[[VAL_LOOP_RELOAD]]
-; GCN: v_cmp_ne_u32_e32 vcc,
-; GCN: s_and_b64 vcc, exec, vcc
+; GCN: s_cmp_lg_u32 s{{[0-9]+}}, s{{[0-9]+}}
 ; GCN: buffer_store_dword [[VAL_LOOP]], off, s[0:3], s7 offset:[[VAL_SUB_OFFSET:[0-9]+]] ; 4-byte Folded Spill
-; GCN-NEXT: s_cbranch_vccnz [[LOOP]]
+; GCN-NEXT: s_cbranch_scc1 [[LOOP]]
 
 
 ; GCN: [[END]]:
 ; VGPR: v_readlane_b32 s[[S_RELOAD_SAVEEXEC_LO:[0-9]+]], [[SPILL_VGPR]], [[SAVEEXEC_LO_LANE]]
 ; VGPR: v_readlane_b32 s[[S_RELOAD_SAVEEXEC_HI:[0-9]+]], [[SPILL_VGPR]], [[SAVEEXEC_HI_LANE]]
 
 ; VMEM: buffer_load_dword v[[V_RELOAD_SAVEEXEC_LO:[0-9]+]], off, s[0:3], s7 offset:20 ; 4-byte Folded Reload
 ; VMEM: s_waitcnt vmcnt(0)

llvm/trunk/test/CodeGen/AMDGPU/uniform-PHI.ll

+; RUN: llc -march=amdgcn -mcpu=fiji -verify-machineinstrs < %s | FileCheck -check-prefix=GCN %s
+
+; GCN-LABEL: BB0_2
+; GCN-NOT: v_readfirstlane
+
+
+target triple = "amdgcn--amdhsa"
+define amdgpu_kernel void @uniform-PHI(i32 addrspace(1)* nocapture readonly %arg, i32 addrspace(1)* nocapture %arg1, i32 %arg2) {
+bb:
+  %tmp = sext i32 %arg2 to i64
+  %tmp3 = tail call i64 @_Z13get_global_idj(i32 0) #2
+  %tmp4 = icmp ugt i64 %tmp3, %tmp
+  %tmp5 = icmp sgt i32 %arg2, 0
+  %tmp6 = and i1 %tmp4, %tmp5
+  br i1 %tmp6, label %bb7, label %bb17
+
+bb7:                                              ; preds = %bb
+  br label %bb8
+
+bb8:                                              ; preds = %bb8, %bb7
+  %tmp9 = phi i32 [ %tmp15, %bb8 ], [ 0, %bb7 ]
+  %tmp10 = phi i32 [ %tmp14, %bb8 ], [ 0, %bb7 ]
+  %tmp11 = zext i32 %tmp9 to i64
+  %tmp12 = getelementptr inbounds i32, i32 addrspace(1)* %arg, i64 %tmp11
+  %tmp13 = load i32, i32 addrspace(1)* %tmp12, align 4
+  %tmp14 = add nsw i32 %tmp13, %tmp10
+  %tmp15 = add nuw nsw i32 %tmp9, 1
+  %tmp16 = icmp eq i32 %tmp15, %arg2
+  br i1 %tmp16, label %bb17, label %bb8
+
+bb17:                                             ; preds = %bb8, %bb
+  %tmp18 = phi i32 [ 0, %bb ], [ %tmp14, %bb8 ]
+  store i32 %tmp18, i32 addrspace(1)* %arg1, align 4
+  ret void
+}
+
+declare i64 @_Z13get_global_idj(i32) local_unnamed_addr #1
+attributes #1 = { convergent nounwind readnone "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="fiji" "target-features"="+16-bit-insts,+dpp,+fp64-fp16-denormals,+s-memrealtime,-fp32-denormals" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #2 = { convergent nounwind readnone }

llvm/trunk/test/CodeGen/AMDGPU/uniform-loop-inside-nonuniform.ll

 ; RUN: llc -march=amdgcn -mcpu=verde < %s | FileCheck %s
 
 ; Test a simple uniform loop that lives inside non-uniform control flow.
 
 ; CHECK-LABEL: {{^}}test1:
 ; CHECK: v_cmp_ne_u32_e32 vcc, 0
 ; CHECK: s_and_saveexec_b64
 ; CHECK-NEXT: ; mask branch
-; CHECK-NEXT: s_cbranch_execz BB{{[0-9]+_[0-9]+}}
 ; CHECK-NEXT: BB{{[0-9]+_[0-9]+}}: ; %loop_body.preheader
 
 ; CHECK: [[LOOP_BODY_LABEL:BB[0-9]+_[0-9]+]]:
-; CHECK: s_cbranch_vccz [[LOOP_BODY_LABEL]]
+; CHECK: s_cbranch_scc0 [[LOOP_BODY_LABEL]]
 
 ; CHECK: s_endpgm
 define amdgpu_ps void @test1(<8 x i32> inreg %rsrc, <2 x i32> %addr.base, i32 %y, i32 %p) {
 main_body:
   %cc = icmp eq i32 %p, 0
   br i1 %cc, label %out, label %loop_body
 
 loop_body:
   %counter = phi i32 [ 0, %main_body ], [ %incr, %loop_body ]
 
   ; Prevent the loop from being optimized out
   call void asm sideeffect "", "" ()
 
   %incr = add i32 %counter, 1
   %lc = icmp sge i32 %incr, 1000
   br i1 %lc, label %out, label %loop_body
 
 out:
   ret void
 }
 
 ; CHECK-LABEL: {{^}}test2:
 ; CHECK: s_and_saveexec_b64
 ; CHECK-NEXT: ; mask branch
-; CHECK-NEXT: s_cbranch_execz
 define amdgpu_kernel void @test2(i32 addrspace(1)* %out, i32 %a, i32 %b) {
 main_body:
   %tid = call i32 @llvm.amdgcn.workitem.id.x() #1
   %cc = icmp eq i32 %tid, 0
   br i1 %cc, label %done1, label %if
 
 if:
   %cmp = icmp eq i32 %a, 0

llvm/trunk/test/CodeGen/AMDGPU/valu-i1.ll

 ; SI-NEXT: ; mask branch
 ; SI-NEXT: s_cbranch_execz [[LABEL_EXIT:BB[0-9]+_[0-9]+]]
 
 ; SI: s_mov_b64 {{s\[[0-9]+:[0-9]+\]}}, 0{{$}}
 
 ; SI: [[LABEL_LOOP:BB[0-9]+_[0-9]+]]:
 ; SI: buffer_load_dword
 ; SI-DAG: buffer_store_dword
-; SI-DAG: v_cmp_eq_u32_e32 vcc, 0x100
-; SI: s_cbranch_vccz [[LABEL_LOOP]]
+; SI-DAG: s_cmpk_eq_i32 s{{[0-9]+}}, 0x100
+; SI: s_cbranch_scc0 [[LABEL_LOOP]]
 ; SI: [[LABEL_EXIT]]:
 ; SI: s_endpgm
 
 define amdgpu_kernel void @simple_test_v_loop(i32 addrspace(1)* %dst, i32 addrspace(1)* %src) #1 {
 entry:
   %tid = call i32 @llvm.amdgcn.workitem.id.x() nounwind readnone
   %is.0 = icmp ne i32 %tid, 0
   %limit = add i32 %tid, 64