AMDGPU : Fix common dominator of two incoming blocks terminates with uniform branch issue.

[wdng]

Summary

We don't need to fix the PHI if the common dominator of the two incoming blocks terminates with a uniform branch. But looks like the condition is not strong enough to find two blocks with a uniform branch, which bring loop iteration order regression.

MI:
  %vreg5<def> = PHI %vreg125, <BB#1>, %vreg12, <BB#3>; SReg_64:%vreg5,%vreg125,%vreg12
  
MBB0:
BB#1: derived from LLVM BB %for.body.preheader
    Predecessors according to CFG: BB#0
	%vreg126<def> = S_MOV_B32 0; SReg_32_XM0:%vreg126
	%vreg125<def> = S_MOV_B64 0; SReg_64:%vreg125
	S_BRANCH <BB#3>
    Successors according to CFG: BB#3(?%)

MBB1:
BB#3: derived from LLVM BB %for.body
    Predecessors according to CFG: BB#1 BB#3
	%vreg5<def> = PHI %vreg125, <BB#1>, %vreg12, <BB#3>; SReg_64:%vreg5,%vreg125,%vreg12
	%vreg6<def> = PHI %vreg1, <BB#1>, %vreg9, <BB#3>; VGPR_32:%vreg6,%vreg1,%vreg9
	%vreg7<def> = PHI %vreg126, <BB#1>, %vreg11, <BB#3>; SReg_32_XM0:%vreg7,%vreg126,%vreg11
	%vreg8<def> = PHI %vreg2, <BB#1>, %vreg10, <BB#3>; VGPR_32:%vreg8,%vreg2,%vreg10
	%vreg127<def,tied6> = V_MAC_F32_e64 0, %vreg6, 0, %vreg6, 0, %vreg1<tied0>, 0, 0, %EXEC<imp-use>; VGPR_32:%vreg127,%vreg6,%vreg6,%vreg1
	%vreg9<def> = V_MAD_F32 1, %vreg8, 0, %vreg8, 0, %vreg127<kill>, 0, 0, %EXEC<imp-use>; VGPR_32:%vreg9,%vreg8,%vreg8,%vreg127
	%vreg128<def> = V_ADD_F32_e64 0, %vreg6, 0, %vreg6, 0, 0, %EXEC<imp-use>; VGPR_32:%vreg128,%vreg6,%vreg6
	%vreg10<def,tied6> = V_MAC_F32_e64 0, %vreg128<kill>, 0, %vreg8, 0, %vreg2<tied0>, 0, 0, %EXEC<imp-use>; VGPR_32:%vreg10,%vreg128,%vreg8,%vreg2
	%vreg129<def> = S_MOV_B32 1; SReg_32_XM0:%vreg129
	%vreg11<def> = S_ADD_I32 %vreg7, %vreg129<kill>, %SCC<imp-def,dead>; SReg_32_XM0:%vreg11,%vreg7,%vreg129
	%vreg130<def> = V_MUL_F32_e64 0, %vreg10, 0, %vreg10, 0, 0, %EXEC<imp-use>; VGPR_32:%vreg130,%vreg10,%vreg10
	%vreg131<def,tied6> = V_MAC_F32_e64 0, %vreg9, 0, %vreg9, 0, %vreg130<tied0>, 0, 0, %EXEC<imp-use>; VGPR_32:%vreg131,%vreg9,%vreg9,%vreg130
	%vreg132<def> = V_MOV_B32_e32 1082130432, %EXEC<imp-use>; VGPR_32:%vreg132
	%vreg133<def> = V_CMP_NLE_F32_e64 0, %vreg131<kill>, 0, %vreg132<kill>, 0, 0, %EXEC<imp-use>; SReg_64:%vreg133 VGPR_32:%vreg131,%vreg132
	%vreg135<def> = COPY %vreg21; VGPR_32:%vreg135 SReg_32_XM0:%vreg21
	%vreg134<def> = V_CMP_GE_U32_e64 %vreg11, %vreg135, %EXEC<imp-use>; SReg_64:%vreg134 SReg_32_XM0:%vreg11 VGPR_32:%vreg135
	%vreg136<def> = S_OR_B64 %vreg134<kill>, %vreg133<kill>, %SCC<imp-def,dead>; SReg_64:%vreg136,%vreg134,%vreg133
	%vreg12<def> = SI_IF_BREAK %vreg136<kill>, %vreg5, %SCC<imp-def,dead>; SReg_64:%vreg12,%vreg136,%vreg5
	SI_LOOP %vreg12, <BB#3>, %EXEC<imp-def,dead>, %SCC<imp-def,dead>, %EXEC<imp-use>; SReg_64:%vreg12
	S_BRANCH <BB#4>
    Successors according to CFG: BB#4(0x04000000 / 0x80000000 = 3.12%) BB#3(0x7c000000 / 0x80000000 = 96.88%)

NCD: 
BB#1: derived from LLVM BB %for.body.preheader
    Predecessors according to CFG: BB#0
	%vreg126<def> = S_MOV_B32 0; SReg_32_XM0:%vreg126
	%vreg125<def> = S_MOV_B64 0; SReg_64:%vreg125
	S_BRANCH <BB#3>
    Successors according to CFG: BB#3(?%)

[arsenm]

This needs a test and is not correct. The direct predecessors could themselves be divergent blocks. You need to identify whether this phi is in a divergent region

[wdng]

Add conditions to identify whether this phi is in a divergent region.

[wdng]

Completely remove weak if condition for checking whether two blocks with a uniform branch, current implementation uses divergence analysis to detect whether two blocks with a uniform branch. If all conditions on all paths leading to a block are uniform, block is uniform.

[rampitec]

In D31350#714741, @wdng wrote:

Completely remove weak if condition for checking whether two blocks with a uniform branch, current implementation uses divergence analysis to detect whether two blocks with a uniform branch. If all conditions on all paths leading to a block are uniform, block is uniform.

I do not see divergence analysis used. I see that you are checking for PHI to be a constant, which is way stronger than just uniform.

lib/Target/AMDGPU/SIFixSGPRCopies.cpp

394

Please use nullptr instead of NULL.

[arsenm]

lib/Target/AMDGPU/SIFixSGPRCopies.cpp

394

if (IPostDom)

396

This isn't going to do anything. PHINodes are IR constructs

[arsenm]

This is still approaching this from the wrong direction. You need to move all SGPR phis in the entire region unless the inputs are from the control flow intrinsics. There also needs to be a test

[wdng]

Based on Matt' comments, check conditions whether inputs are from the control flow intrinsics.

[wdng]

Tests will be added later once we decide to use this approach. Thanks!

[rampitec]

lib/Target/AMDGPU/SIFixSGPRCopies.cpp

395

I do not understand this. If we speak about %vreg5 from the code in the description, it is not defined by the post dominator. Its definitions are in BB#1 and BB#3 and both needs to be checked.

[wdng]

Address code reviews: check terminators for all predecessors.

[rampitec]

lib/Target/AMDGPU/SIFixSGPRCopies.cpp

331

You need recursive search to do it.

334

Weird brace indention.

[wdng]

lib/Target/AMDGPU/SIFixSGPRCopies.cpp

331

http://llvm.org/docs/ProgrammersManual.html#iterating-over-predecessors-successors-of-blocks, looks like this has iterated over of all predecessors of a BB, right?

[rampitec]

lib/Target/AMDGPU/SIFixSGPRCopies.cpp

331

All immediate predecessors.

[wdng]

Use BFS to search for all intermediate predecessors to check whether it has terminators.

[rampitec]

lib/Target/AMDGPU/SIFixSGPRCopies.cpp

332

You do not need two queues. In fact it is usually done with a SmallVector.

[wdng]

lib/Target/AMDGPU/SIFixSGPRCopies.cpp

332

BFS can be implemented in different ways, either using one queue or two. Are there any benefits to use SmallVector? Thanks!

[rampitec]

lib/Target/AMDGPU/SIFixSGPRCopies.cpp

332

You definitely do not need two. Then llvm preferrs to use its own containers over std.

[wdng]

lib/Target/AMDGPU/SIFixSGPRCopies.cpp

332

I agree to use LLVM's own container, but implementing BFS using vectors is not a good data structure choice although it's doable.

[arsenm]

lib/Target/AMDGPU/SIFixSGPRCopies.cpp

334

There needs to be a set because there can be loops

test/CodeGen/AMDGPU/sgprcopies.ll

1 ↗

(On Diff #94442)

s/SI GCN.

Also needs -verify-machineinstrs

3 ↗

(On Diff #94442)

Should have better name and secretion of what this is really checking

12 ↗

(On Diff #94442)

Should have instnamer run on this and the test could be simplified a bit

[wdng]

1. Add hash set to avoid processing cycles in CFG.
2. This LIT test is based on changes of ocltst, renaming lit test function name.

[wdng]

Upload correct diff.

[wdng]

Use LLVM provided container for implementation.

[wdng]

Ping.

[rampitec]

lib/Target/AMDGPU/SIFixSGPRCopies.cpp

332

Usually it is called Visited.

333

And this is usually Worklist.

336

Not needed.

338

SmallVector<MachineBasicBlock*, 4> Worklist(MBB->pred_begin(), MBB->pred_end());
while (!Worklist.empty())

340

pop_back_val.

342

if (Visited.insert(mbb).second) continue;

347

pred, not preds. Anyway, Worklist.insert(Worklist.end(), mbb->pred_begin(), mbb->pred_end()).

[wdng]

Code changes based on code reviews.

[rampitec]

lib/Target/AMDGPU/SIFixSGPRCopies.cpp

343

If you use Visited.insert(mbb).second it is one search in the set instead of two.

[wdng]

lib/Target/AMDGPU/SIFixSGPRCopies.cpp

343

Looks like this is not correct. We need to check whether this node has visited before, then add into Visited if not found instead of inserting first and then search, correct?

[rampitec]

lib/Target/AMDGPU/SIFixSGPRCopies.cpp

343

http://llvm.org/docs/doxygen/html/DenseMap_8h_source.html#l00169

[wdng]

Address code reviews. Thanks Stas!

[wdng]

Fix other 3 LIT tests regression caused by code changes.

[arsenm]

lib/Target/AMDGPU/SIFixSGPRCopies.cpp

330

This is a bad name because most blocks have terminators. Almost all should at this point, this needs to specify that it is divergent terminator

332

You could maybe make this a map and cache the result so that every single block that needs to be visited doesn't need to walk all the way up each time

[wdng]

lib/Target/AMDGPU/SIFixSGPRCopies.cpp

332

Visited is used to check whether the visiting node has been visited before, once is has been visited before it's predecessors won't be processed again. For example:

   D
 /   \
A     C
|  \  |
B     E 
 \   /
   F

Assume starting from node F, trace down F->B->A->D, when visiting from F to E, A and D won't be processed again. So I don't think there is a need to save results like A and D.

[wdng]

Change function name.

[wdng]

Ping.

[arsenm]

lib/Target/AMDGPU/SIFixSGPRCopies.cpp

78

This should be the first included llvm header

332

If you consider the entire function, the same predecessors will be visited for phis in other blocks

test/CodeGen/AMDGPU/sgprcopies.ll

6 ↗

(On Diff #94979)

This should be marked amdgpu_kernel

[wdng]

1. Address code reviews.
2. Will create another patch for optimized searching of divergent terminator.

[rampitec]

test/CodeGen/AMDGPU/sgprcopies.ll

6 ↗

(On Diff #95055)

Calling convention, not function name.

[wdng]

Address code review.

[rampitec]

LGTM

[wdng]

lib/Target/AMDGPU/SIFixSGPRCopies.cpp

332

A separate patch will be created for optimized search divergent terminators.

lib/Target/AMDGPU/SIFixSGPRCopies.cpp

 #include "SIInstrInfo.h"
 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Target/TargetMachine.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "si-fix-sgpr-copies"
 
 namespace {
 
 class SIFixSGPRCopies : public MachineFunctionPass {
 
static bool isSafeToFoldImmIntoCopy(const MachineInstr *Copy,
   case AMDGPU::V_MOV_B64_PSEUDO:
     SMovOp = AMDGPU::S_MOV_B64;
     break;
   }
   Imm = ImmOp->getImm();
   return true;
 }
 
 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>();
 
   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) {
       MachineInstr &MI = *I;
 
       switch (MI.getOpcode()) {
       default:
         continue;
       case AMDGPU::COPY: {
         // If the destination register is a physical register there isn't really
         // much we can do to fix this.
         if (!TargetRegisterInfo::isVirtualRegister(MI.getOperand(0).getReg()))
           continue;
 
for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end();
 
         // We don't need to fix the PHI if the common dominator of the
         // two incoming blocks terminates with a uniform branch.
         if (MI.getNumExplicitOperands() == 5) {
           MachineBasicBlock *MBB0 = MI.getOperand(2).getMBB();
           MachineBasicBlock *MBB1 = MI.getOperand(4).getMBB();
 
           MachineBasicBlock *NCD = MDT->findNearestCommonDominator(MBB0, MBB1);
-          if (NCD && !hasTerminatorThatModifiesExec(*NCD, *TRI)) {
+          if (NCD && !hasTerminatorThatModifiesExec(*MBB0, *TRI) &&
+                     !hasTerminatorThatModifiesExec(*MBB1, *TRI)) {
             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.
         //
         // Also, if a PHI node defines an SGPR and has all SGPR operands
         // we must move it to the VALU, because the SGPR operands will
         // all end up being assigned the same register, which means
         // there is a potential for a conflict if different threads take
         // different control flow paths.
         //
         // For Example:
         //