AMDGPU: Add SIWholeQuadMode pass

[nhaehnle]

Summary

Whole quad mode is already enabled for pixel shaders that compute
derivatives, but it must be suspended for instructions that cause a
shader to have side effects (i.e. stores and atomics).

This pass addresses the issue by storing the real (initial) live mask
in a register, masking EXEC before instructions that require exact
execution and (re-)enabling WQM where required.

This pass is run before register coalescing so that we can use
machine SSA for analysis.

The changes in this patch expose a problem with the second machine
scheduling pass: target independent instructions like COPY implicitly
use EXEC when they operate on VGPRs, but this fact is not encoded in
the MIR. This can lead to miscompilation because instructions are
moved past changes to EXEC.

This patch fixes the problem by adding use-implicit operands to
target independent instructions. Some general codegen passes are
relaxed to work with such implicit use operands.

[nhaehnle]

In the fast case where we have WQM but don't need to switch back and forth,
also mark COPYs as implicitly using EXEC in the entry block.

Noticed this in a more involved shader in a piglit run.

[• tstellarAMD]

The target independent changes might get more visibility if they were in a separate patch.

The changes in this patch expose a problem with the second machine
scheduling pass: target independent instructions like COPY implicitly
use EXEC when they operate on VGPRs, but this fact is not encoded in
the MIR. This can lead to miscompilation because instructions are
moved past changes to EXEC.

Is the Scheduler the only pass we need to worry about? Would we be able to avoid the problem by implementing TargetInstrInfo::isSchedulingBoundry() ?

[nhaehnle]

In D18162#376804, @tstellarAMD wrote:

The target independent changes might get more visibility if they were in a separate patch.

The changes in this patch expose a problem with the second machine
scheduling pass: target independent instructions like COPY implicitly
use EXEC when they operate on VGPRs, but this fact is not encoded in
the MIR. This can lead to miscompilation because instructions are
moved past changes to EXEC.

Is the Scheduler the only pass we need to worry about? Would we be able to avoid the problem by implementing TargetInstrInfo::isSchedulingBoundry() ?

Hmm, I wasn't aware of that function. Yes, customizing that function so that it considers instructions with EXEC defs as scheduling boundaries should work as well.

It's a slightly more conservative solution because it also prevents movement of SALU and SMEM instructions. Then again, it should not impact the initial DAG-based scheduling. Also, I notice that the target-independent code mentions that considering stack pointer modifications to be scheduling boundaries is profitable, and the same logic likely applies to EXEC. Plus, it's a more robust solution.

I'll modify the patch to use isSchedulingBoundary instead.

[nhaehnle]

[This time with the correct --update parameter for arc]

Use isSchedulingBoundary instead of implicit-use of EXEC, which gets rid of
the target-independent modifications.

This is indeed more conservative, as you can tell from the change in
si-scheduler.ll: previously, the later scheduling passes managed to move the
initial s_wqm_b64 after the s_load_dwordx4 & x8, i.e. we lose slightly in
latency hiding.

The impact should be small, and it does make sense to land a more conservative
and robust patch initially.

[• tstellarAMD]

lib/Target/AMDGPU/AMDGPUInstrInfo.cpp

67

This should go in SIInstrInfo, since it is SI specific.

70–72

Can we just call TargetInstrInfo::isSchedulingBoundary() at the end of the function rather than have this check.

[nhaehnle]

Makes sense, here's an updated patch.

[• tstellarAMD]

LGTM, just a few things to fix before you commit.

lib/Target/AMDGPU/AMDGPUInstrInfo.h

65

Extra whitespace change.

lib/Target/AMDGPU/SIWholeQuadMode.cpp

311

Coding Style. Brace on new line.

327

Coding Style: Brace on new line.

[arsenm]

Should wqm related instructions be marked as convergent?

[nhaehnle]

Thanks for the feedback Tom. I'll work in those changes before I commit.

Matt, I'm not sure "convergent" really captures the properties. In practice, I doubt it's a problem because the relevant instructions define EXEC - as far as I can tell, this means they're left alone by the passes that care about convergence, because EXEC is a physical register.

[arsenm]

In D18162#378648, @nhaehnle wrote:

Thanks for the feedback Tom. I'll work in those changes before I commit.

Matt, I'm not sure "convergent" really captures the properties. In practice, I doubt it's a problem because the relevant instructions define EXEC - as far as I can tell, this means they're left alone by the passes that care about convergence, because EXEC is a physical register.

It's more likely to be a problem for the corresponding IR intrinsics

[nhaehnle]

Ah okay. There are two intrinsic (types) related to all this:

1. The kill intrinsic. This is marked as having side effects, which I think should imply convergent.

2. The load / store / atomic intrinsics. They themselves don't involve derivatives. If their results are used in a derivative computation, then it is sufficient to ensure that they are always executed when the consumer is executed, but that automatically follows from plain data flow (just like any other normal computations).

So I think we're fine without convergent attributes anywhere.

[nhaehnle]

As an addendum: In part, correctness depends on the guarantees for derivatives that are required by GLSL. For example, if you have:

%tmp = call <2 x i32> @llvm.amdgcn.image.load.v2i32(...)
%coords = bitcast and extract from %tmp
...
br i1 %cc, label %IF, label %ELSE

IF:
%texel = call <4 x float> @llvm.SI.image.sample.v2i32(<2 x i32> %coord, ...)
...

ELSE:
... %coord not used here or later ...

The derivative taken by the llvm.SI.image.sample is undefined in GLSL if the control-flow is dynamically non-uniform, so it is perfectly legal to sink the llvm.amdgcn.image.load into the IF block (and the same applies to any other computation that leads to a derivative).

[arsenm]

In D18162#378648, @nhaehnle wrote:

Thanks for the feedback Tom. I'll work in those changes before I commit.

Matt, I'm not sure "convergent" really captures the properties. In practice, I doubt it's a problem because the relevant instructions define EXEC - as far as I can tell, this means they're left alone by the passes that care about convergence, because EXEC is a physical register.

It's more likely to be a problem for the corresponding IR intrinsics

In D18162#378751, @nhaehnle wrote:

Ah okay. There are two intrinsic (types) related to all this:

1. The kill intrinsic. This is marked as having side effects, which I think should imply convergent.

Side effects do not imply convergent

2. The load / store / atomic intrinsics. They themselves don't involve derivatives. If their results are used in a derivative computation, then it is sufficient to ensure that they are always executed when the consumer is executed, but that automatically follows from plain data flow (just like any other normal computations).

It shouldn't be necessary for these

[arsenm]

In D18162#378752, @nhaehnle wrote:

The derivative taken by the llvm.SI.image.sample is undefined in GLSL if the control-flow is dynamically non-uniform, so it is perfectly legal to sink the llvm.amdgcn.image.load into the IF block (and the same applies to any other computation that leads to a derivative).

This is the same situation as barriers, so I think this should still be convergent. The problem it is solving is if LLVM introduces uses that do not hit uniform control flow, like introducing a call in either side of an if/then block

[nhaehnle]

For kill: Okay, side effects do not imply convergent, but the kill can only be moved in a way that preserves its execution. So IR-level optimizations are allowed to move a kill into both the if and the else branch of a subsequent if-else block, but this still results in correct code: both branches may mask away some bits of EXEC, but since the control flow is joined again with a bit-wise OR, that's okay.

In D18162#379477, @arsenm wrote:

In D18162#378752, @nhaehnle wrote:

The derivative taken by the llvm.SI.image.sample is undefined in GLSL if the control-flow is dynamically non-uniform, so it is perfectly legal to sink the llvm.amdgcn.image.load into the IF block (and the same applies to any other computation that leads to a derivative).

This is the same situation as barriers, so I think this should still be convergent. The problem it is solving is if LLVM introduces uses that do not hit uniform control flow, like introducing a call in either side of an if/then block

I do not think this is the same situation as barriers. In barriers, they need to be convergent because all threads have to execute the same barrier instruction (at the same program counter) for the semantics to remain correct.

If (plain) loads are pushed down into either side of an if/else block, that's inefficient but correct (of course assuming no stores in between etc.). There is no synchronization or data exchange between threads, so all that matters is that the right value is loaded into the right register on a per-thread basis; which instructions do the job at which program counter value is not important.

If I am still misunderstanding you, perhaps an example would be helpful.

lib/CodeGen/ProcessImplicitDefs.cpp

 
 bool ProcessImplicitDefs::canTurnIntoImplicitDef(MachineInstr *MI) {
   if (!MI->isCopyLike() &&
       !MI->isInsertSubreg() &&
       !MI->isRegSequence() &&
       !MI->isPHI())
     return false;
   for (const MachineOperand &MO : MI->operands())
-    if (MO.isReg() && MO.isUse() && MO.readsReg() && !MO.isImplicit())
+    if (MO.isReg() && MO.isUse() && MO.readsReg())
       return false;
   return true;
 }
 
 void ProcessImplicitDefs::processImplicitDef(MachineInstr *MI) {
   DEBUG(dbgs() << "Processing " << *MI);
   unsigned Reg = MI->getOperand(0).getReg();
 

lib/CodeGen/TwoAddressInstructionPass.cpp

bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &Func) {
 
   return MadeChange;
 }
 
 /// Eliminate a REG_SEQUENCE instruction as part of the de-ssa process.
 ///
 /// The instruction is turned into a sequence of sub-register copies:
 ///
-///   %dst = REG_SEQUENCE %v1, ssub0, %v2, ssub1, [implicit uses]
+///   %dst = REG_SEQUENCE %v1, ssub0, %v2, ssub1
 ///
 /// Becomes:
 ///
-///   %dst:ssub0<def,undef> = COPY %v1, [implicit uses]
-///   %dst:ssub1<def> = COPY %v2, [implicit uses]
+///   %dst:ssub0<def,undef> = COPY %v1
+///   %dst:ssub1<def> = COPY %v2
 ///
 void TwoAddressInstructionPass::
 eliminateRegSequence(MachineBasicBlock::iterator &MBBI) {
   MachineInstr *MI = MBBI;
   unsigned DstReg = MI->getOperand(0).getReg();
-  unsigned NumTrailingImplicit = 0;
-
-  for (unsigned i = MI->getNumOperands(); i > 0; --i) {
-    const MachineOperand &MO = MI->getOperand(i - 1);
-    if (!MO.isReg() || !MO.isImplicit())
-      break;
-    NumTrailingImplicit++;
-  }
-
-  unsigned NumOperands = MI->getNumOperands() - NumTrailingImplicit;
-
   if (MI->getOperand(0).getSubReg() ||
       TargetRegisterInfo::isPhysicalRegister(DstReg) ||
-      !(NumOperands & 1)) {
+      !(MI->getNumOperands() & 1)) {
     DEBUG(dbgs() << "Illegal REG_SEQUENCE instruction:" << *MI);
     llvm_unreachable(nullptr);
   }
 
   SmallVector<unsigned, 4> OrigRegs;
   if (LIS) {
     OrigRegs.push_back(MI->getOperand(0).getReg());
-    for (unsigned i = 1; i < NumOperands; i += 2)
+    for (unsigned i = 1, e = MI->getNumOperands(); i < e; i += 2)
       OrigRegs.push_back(MI->getOperand(i).getReg());
   }
 
   bool DefEmitted = false;
-  for (unsigned i = 1; i < NumOperands; i += 2) {
+  for (unsigned i = 1, e = MI->getNumOperands(); i < e; i += 2) {
     MachineOperand &UseMO = MI->getOperand(i);
     unsigned SrcReg = UseMO.getReg();
     unsigned SubIdx = MI->getOperand(i+1).getImm();
     // Nothing needs to be inserted for <undef> operands.
     if (UseMO.isUndef())
       continue;
 
     // Defer any kill flag to the last operand using SrcReg. Otherwise, we
     // might insert a COPY that uses SrcReg after is was killed.
     bool isKill = UseMO.isKill();
     if (isKill)
-      for (unsigned j = i + 2; j < NumOperands; j += 2)
+      for (unsigned j = i + 2; j < e; j += 2)
         if (MI->getOperand(j).getReg() == SrcReg) {
           MI->getOperand(j).setIsKill();
           UseMO.setIsKill(false);
           isKill = false;
           break;
         }
 
     // Insert the sub-register copy.
     MachineInstr *CopyMI = BuildMI(*MI->getParent(), MI, MI->getDebugLoc(),
                                    TII->get(TargetOpcode::COPY))
       .addReg(DstReg, RegState::Define, SubIdx)
       .addOperand(UseMO);
 
-    for (unsigned j = 0; j < NumTrailingImplicit; ++j)
-      CopyMI->addOperand(MI->getOperand(NumOperands + j));
-
     // The first def needs an <undef> flag because there is no live register
     // before it.
     if (!DefEmitted) {
       CopyMI->getOperand(0).setIsUndef(true);
       // Return an iterator pointing to the first inserted instr.
       MBBI = CopyMI;
     }
     DefEmitted = true;
 
     // Update LiveVariables' kill info.
     if (LV && isKill && !TargetRegisterInfo::isPhysicalRegister(SrcReg))
       LV->replaceKillInstruction(SrcReg, MI, CopyMI);
 
     DEBUG(dbgs() << "Inserted: " << *CopyMI);
   }
 
   MachineBasicBlock::iterator EndMBBI =
       std::next(MachineBasicBlock::iterator(MI));
 
   if (!DefEmitted) {
     DEBUG(dbgs() << "Turned: " << *MI << " into an IMPLICIT_DEF");
     MI->setDesc(TII->get(TargetOpcode::IMPLICIT_DEF));
-    for (int j = NumOperands - 1, ee = 0; j > ee; --j)
+    for (int j = MI->getNumOperands() - 1, ee = 0; j > ee; --j)
       MI->RemoveOperand(j);
   } else {
     DEBUG(dbgs() << "Eliminated: " << *MI);
     MI->eraseFromParent();
   }
 
   // Udpate LiveIntervals.
   if (LIS)
     LIS->repairIntervalsInRange(MBB, MBBI, EndMBBI, OrigRegs);
 }

lib/Target/AMDGPU/AMDGPUInstrInfo.h

public:
   int getIndirectIndexEnd(const MachineFunction &MF) const;
 
   bool enableClusterLoads() const override;
 
   bool shouldScheduleLoadsNear(SDNode *Load1, SDNode *Load2,
                                int64_t Offset1, int64_t Offset2,
                                unsigned NumLoads) const override;
 
+  bool isSchedulingBoundary(const MachineInstr *MI,
+                            const MachineBasicBlock *MBB,
+                            const MachineFunction &MF) const override;
 
   /// \brief Return a target-specific opcode if Opcode is a pseudo instruction.
   /// Return -1 if the target-specific opcode for the pseudo instruction does
   /// not exist. If Opcode is not a pseudo instruction, this is identity.
   int pseudoToMCOpcode(int Opcode) const;
 
 //===---------------------------------------------------------------------===//
 // Pure virtual funtions to be implemented by sub-classes.
 //===---------------------------------------------------------------------===//

lib/Target/AMDGPU/AMDGPUInstrInfo.cpp

assert(Offset1 > Offset0 &&
          "Second offset should be larger than first offset!");
   // If we have less than 16 loads in a row, and the offsets are within 64
   // bytes, then schedule together.
 
   // A cacheline is 64 bytes (for global memory).
   return (NumLoads <= 16 && (Offset1 - Offset0) < 64);
 }
 
+bool AMDGPUInstrInfo::isSchedulingBoundary(const MachineInstr *MI,
+                                           const MachineBasicBlock *MBB,
+                                           const MachineFunction &MF) const {
+  // Terminators and labels can't be scheduled around.
+  if (MI->isTerminator() || MI->isPosition())
+    return true;
+
+  // Target-independent instructions do not have an implicit-use of EXEC, even
+  // when they operate on VGPRs. Treating EXEC modifications as scheduling
+  // boundaries prevents incorrect movements of such instructions.
+  const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
+  if (MI->modifiesRegister(AMDGPU::EXEC, TRI))
+    return true;
+
+  return false;
+}
+
 int AMDGPUInstrInfo::getIndirectIndexBegin(const MachineFunction &MF) const {
   const MachineRegisterInfo &MRI = MF.getRegInfo();
   const MachineFrameInfo *MFI = MF.getFrameInfo();
   int Offset = -1;
 
   if (MFI->getNumObjects() == 0) {
     return -1;
   }

lib/Target/AMDGPU/SIWholeQuadMode.cpp

char SIWholeQuadMode::analyzeFunction(const MachineFunction &MF) {
   }
 
   return GlobalFlags;
 }
 
 void SIWholeQuadMode::toExact(MachineBasicBlock &MBB,
                               MachineBasicBlock::iterator Before,
                               unsigned SaveWQM, unsigned LiveMaskReg)
 {
   if (SaveWQM) {
     BuildMI(MBB, Before, DebugLoc(), TII->get(AMDGPU::S_AND_SAVEEXEC_B64),
             SaveWQM)
         .addReg(LiveMaskReg);
   } else {
     BuildMI(MBB, Before, DebugLoc(), TII->get(AMDGPU::S_AND_B64),
             AMDGPU::EXEC)
         .addReg(AMDGPU::EXEC)
         .addReg(LiveMaskReg);
   }
 }
 
 void SIWholeQuadMode::toWQM(MachineBasicBlock &MBB,
                             MachineBasicBlock::iterator Before,
                             unsigned SavedWQM)
 {
   if (SavedWQM) {
     BuildMI(MBB, Before, DebugLoc(), TII->get(AMDGPU::COPY), AMDGPU::EXEC)
         .addReg(SavedWQM);
   } else {
     BuildMI(MBB, Before, DebugLoc(), TII->get(AMDGPU::S_WQM_B64),
             AMDGPU::EXEC)
         .addReg(AMDGPU::EXEC);
   }
while (II != IE) {
     // coalescing or be lowered to SALU or VALU instructions.
     if (TargetInstrInfo::isGenericOpcode(MI.getOpcode())) {
       if (MI.getNumExplicitOperands() >= 1) {
         const MachineOperand &Op = MI.getOperand(0);
         if (Op.isReg()) {
           if (TRI->isSGPRReg(*MRI, Op.getReg())) {
             // SGPR instructions are not affected by EXEC
             continue;
-          } else {
-            // Generic instructions on VGPRs must be marked as implicitly using
-            // EXEC or subsequent passes might reschedule them incorrectly.
-            MI.addOperand(MachineOperand::CreateReg(AMDGPU::EXEC, false, true));
           }
         }
       }
     }
 
     char Needs = 0;
     char OutNeeds = 0;
     auto InstrInfoIt = Instructions.find(&MI);
bool SIWholeQuadMode::runOnMachineFunction(MachineFunction &MF) {
 
   MachineBasicBlock &Entry = MF.front();
   MachineInstr *EntryMI = Entry.getFirstNonPHI();
 
   if (GlobalFlags == StateWQM) {
     // For a shader that needs only WQM, we can just set it once.
     BuildMI(Entry, EntryMI, DebugLoc(), TII->get(AMDGPU::S_WQM_B64),
             AMDGPU::EXEC).addReg(AMDGPU::EXEC);
-
-    for (MachineInstr &MI : Entry) {
-      if (TargetInstrInfo::isGenericOpcode(MI.getOpcode()) &&
-          MI.getNumExplicitOperands() >= 1) {
-        const MachineOperand &Op = MI.getOperand(0);
-        if (Op.isReg()) {
-          if (!TRI->isSGPRReg(*MRI, Op.getReg())) {
-            // Generic instructions on VGPRs must be marked as implicitly using
-            // EXEC or subsequent passes might reschedule them incorrectly.
-            MI.addOperand(MachineOperand::CreateReg(AMDGPU::EXEC, false, true));
-          }
-        }
-      }
-    }
-
     return true;
   }
 
   // Handle the general case
   unsigned LiveMaskReg = MRI->createVirtualRegister(&AMDGPU::SReg_64RegClass);
   BuildMI(Entry, EntryMI, DebugLoc(), TII->get(AMDGPU::COPY), LiveMaskReg)
       .addReg(AMDGPU::EXEC);
 
   for (const auto &BII : Blocks)
     processBlock(const_cast<MachineBasicBlock &>(*BII.first), LiveMaskReg,
                  BII.first == &*MF.begin());
 
   return true;
 }

test/CodeGen/AMDGPU/si-scheduler.ll

 ; RUN: llc -march=amdgcn -mcpu=SI --misched=si < %s | FileCheck %s
 
 ; The test checks the "si" machine scheduler pass works correctly.
 
 ; CHECK-LABEL: {{^}}main:
+; CHECK: s_wqm
 ; CHECK: s_load_dwordx4
 ; CHECK: s_load_dwordx8
-; CHECK: s_wqm
 ; CHECK: s_waitcnt lgkmcnt(0)
 ; CHECK: image_sample
 ; CHECK: s_waitcnt vmcnt(0)
 ; CHECK: exp
 ; CHECK: s_endpgm
 define void @main([6 x <16 x i8>] addrspace(2)* byval %arg, [17 x <16 x i8>] addrspace(2)* byval %arg1, [17 x <4 x i32>] addrspace(2)* byval %arg2, [34 x <8 x i32>] addrspace(2)* byval %arg3, float inreg %arg4, i32 inreg %arg5, <2 x i32> %arg6, <2 x i32> %arg7, <2 x i32> %arg8, <3 x i32> %arg9, <2 x i32> %arg10, <2 x i32> %arg11, <2 x i32> %arg12, float %arg13, float %arg14, float %arg15, float %arg16, float %arg17, float %arg18, i32 %arg19, float %arg20, float %arg21) #0 {
 main_body:
   %tmp = bitcast [34 x <8 x i32>] addrspace(2)* %arg3 to <32 x i8> addrspace(2)*