RegBankSelect: Fix copy insertion point for terminators

[arsenm]

Summary

If a copy was needed to handle the condition of brcond, it was being
inserted before the defining instruction. Add tests for iterator edge
cases.

I find the existing code here suspect for the case where it's looking
for terminators that modify the register. It's going to insert a copy
in the middle of the terminators, which isn't allowed (it might be
necessary to have a COPY_terminator if anybody actually needs this).

Also legalize brcond for AMDGPU.

[qcolombet]

Hi Matt,

I find the existing code here suspect for the case where it's looking for terminators that modify the register. It's going to insert a copy in the middle of the terminators, which isn't allowed (it might be necessary to have a COPY_terminator if anybody actually needs this).

This patch does not address that part right?
And I agree, this is wrong, we would need to do some basic block splitting.

Looking back at this code, I wonder if instead of being "clever" about the placement of split point we shouldn't always put then right after the definition of the related instruction and let the machine sinking do the right placement.

Cheers,
-Quentin

lib/CodeGen/GlobalISel/RegBankSelect.cpp

736

Add a comment that at this point we are sure to be right before the first terminator.

[arsenm]

Assert if a copy is needed between terminators

[arsenm]

In D55872#1337787, @qcolombet wrote:

Hi Matt,

I find the existing code here suspect for the case where it's looking for terminators that modify the register. It's going to insert a copy in the middle of the terminators, which isn't allowed (it might be necessary to have a COPY_terminator if anybody actually needs this).

This patch does not address that part right?

No, I switched it to an assert in version 2

And I agree, this is wrong, we would need to do some basic block splitting.

Looking back at this code, I wonder if instead of being "clever" about the placement of split point we shouldn't always put then right after the definition of the related instruction and let the machine sinking do the right placement.

I thought about this, but figured since in this case it's most likely for not really copyable condition registers it might end up being problematic

[qcolombet]

I thought about this, but figured since in this case it's most likely for not really copyable condition registers it might end up being problematic

Good point. Also we have to potentially deal with physical registers (because of ABI constraints for instance) and I think the idea was to keep the live-ranges as small as possible when repairing.

Something that occurred to me is that originally I planned to declare an insertion point between two terminators as being a split point (using InsertionPoint::HasSplit). I gave up on the idea because

1. I didn't have a use case
2. The APIs for querying the terminators are actually clunky and don't allow to properly update the successors list.

See the comments in InstrInsertPoint::materialize if you're curious, but that would be the right way of doing IMHO.

Anyway, LGTM.

Cheers,
-Quentin

[arsenm]

r350595

lib/CodeGen/GlobalISel/RegBankSelect.cpp

else
       addInsertPoint(*It, /*Before*/ false);
   } else {
     // - Terminators must be the last instructions:
     //   * Before, move the insert point before the first terminator.
     //   * After, we have to split the outcoming edges.
     unsigned Reg = MO.getReg();
     if (Before) {
       // Check whether Reg is defined by any terminator.
-      MachineBasicBlock::iterator It = MI;
-      for (auto Begin = MI.getParent()->begin();
-           --It != Begin && It->isTerminator();)
+      MachineBasicBlock::reverse_iterator It = MI;
+      auto REnd = MI.getParent()->rend();
+
+      for (; It != REnd && It->isTerminator(); ++It) {
         if (It->modifiesRegister(Reg, &TRI)) {
           // Insert the repairing code right after the definition.
           addInsertPoint(*It, /*Before*/ false);
           return;
         }
-      addInsertPoint(*It, /*Before*/ true);
+      }
+
+      if (It == REnd) {
+        addInsertPoint(*MI.getParent()->begin(), true);
+        return;
+      }
+
+      addInsertPoint(*It, /*Before*/ false);
       return;
     }
     // Make sure Reg is not redefined by other terminators, otherwise
     // we do not know how to split.
     for (MachineBasicBlock::iterator It = MI, End = MI.getParent()->end();
          ++It != End;)
       // The machine verifier should reject this kind of code.
       assert(It->modifiesRegister(Reg, &TRI) && "Do not know where to split");

lib/Target/AMDGPU/AMDGPULegalizerInfo.cpp

AMDGPULegalizerInfo::AMDGPULegalizerInfo(const GCNSubtarget &ST,
   const LLT AddrSpaces[] = {
     GlobalPtr,
     ConstantPtr,
     LocalPtr,
     FlatPtr,
     PrivatePtr
   };
 
+  setAction({G_BRCOND, S1}, Legal);
+
   setAction({G_ADD, S32}, Legal);
   setAction({G_SUB, S32}, Legal);
   setAction({G_MUL, S32}, Legal);
   setAction({G_AND, S32}, Legal);
   setAction({G_OR, S32}, Legal);
   setAction({G_XOR, S32}, Legal);
 
   getActionDefinitionsBuilder({G_UADDO, G_SADDO, G_USUBO, G_SSUBO,

lib/Target/AMDGPU/AMDGPURegisterBankInfo.cpp

const InstructionMapping &VVMapping = getInstructionMapping(1, 1,
                           AMDGPU::getValueMapping(AMDGPU::SGPRRegBankID, 1),
                           AMDGPU::getValueMapping(AMDGPU::VGPRRegBankID, Size),
                           AMDGPU::getValueMapping(AMDGPU::VGPRRegBankID, Size),
                           AMDGPU::getValueMapping(AMDGPU::SGPRRegBankID, 1)}),
       5); // Num Operands
     AltMappings.push_back(&VVMapping);
     return AltMappings;
   }
+  case AMDGPU::G_BRCOND: {
+    assert(MRI.getType(MI.getOperand(0).getReg()).getSizeInBits() == 1);
+
+    const InstructionMapping &SMapping = getInstructionMapping(
+      1, 1, getOperandsMapping(
+        {AMDGPU::getValueMapping(AMDGPU::SCCRegBankID, 1), nullptr}),
+      2); // Num Operands
+    AltMappings.push_back(&SMapping);
+
+    const InstructionMapping &VMapping = getInstructionMapping(
+      1, 1, getOperandsMapping(
+        {AMDGPU::getValueMapping(AMDGPU::SGPRRegBankID, 1), nullptr }),
+      2); // Num Operands
+    AltMappings.push_back(&VMapping);
+    return AltMappings;
+  }
   default:
     break;
   }
   return RegisterBankInfo::getInstrAlternativeMappings(MI);
 }
 
 void AMDGPURegisterBankInfo::applyMappingImpl(
     const OperandsMapper &OpdMapper) const {
AMDGPURegisterBankInfo::getInstrMapping(const MachineInstr &MI) const {
   case AMDGPU::G_ATOMICRMW_XOR:
   case AMDGPU::G_ATOMICRMW_MAX:
   case AMDGPU::G_ATOMICRMW_MIN:
   case AMDGPU::G_ATOMICRMW_UMAX:
   case AMDGPU::G_ATOMICRMW_UMIN:
   case AMDGPU::G_ATOMIC_CMPXCHG: {
     return getDefaultMappingAllVGPR(MI);
   }
+  case AMDGPU::G_BRCOND: {
+    unsigned Bank = getRegBankID(MI.getOperand(0).getReg(), MRI, *TRI,
+                                 AMDGPU::SGPRRegBankID);
+    assert(MRI.getType(MI.getOperand(0).getReg()).getSizeInBits() == 1);
+    if (Bank != AMDGPU::SCCRegBankID)
+      Bank = AMDGPU::SGPRRegBankID;
+
+    OpdsMapping[0] = AMDGPU::getValueMapping(Bank, 1);
+    break;
+  }
   }
 
   return getInstructionMapping(1, 1, getOperandsMapping(OpdsMapping),
                                MI.getNumOperands());
 }

test/CodeGen/AMDGPU/GlobalISel/legalize-brcond.mir

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+# RUN: llc -mtriple=amdgcn-mesa-mesa3d -mcpu=fiji -O0 -run-pass=legalizer %s -o - | FileCheck %s
+
+---
+name: legal_brcond
+body:             |
+  ; CHECK-LABEL: name: legal_brcond
+  ; CHECK: bb.0.entry:
+  ; CHECK:   successors: %bb.1(0x80000000)
+  ; CHECK:   [[COPY:%[0-9]+]]:_(s32) = COPY $vgpr0
+  ; CHECK:   [[COPY1:%[0-9]+]]:_(s32) = COPY $vgpr1
+  ; CHECK:   [[ICMP:%[0-9]+]]:_(s1) = G_ICMP intpred(ne), [[COPY]](s32), [[COPY1]]
+  ; CHECK:   G_BRCOND [[ICMP]](s1), %bb.1
+  ; CHECK: bb.1:
+  bb.0.entry:
+    successors: %bb.1
+    liveins: $vgpr0, $vgpr1
+    %0:_(s32) = COPY $vgpr0
+    %1:_(s32) = COPY $vgpr1
+    %2:_(s1) = G_ICMP intpred(ne), %0, %1
+    G_BRCOND %2, %bb.1
+
+  bb.1:
+...

test/CodeGen/AMDGPU/GlobalISel/regbankselect-brcond.mir

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+# RUN: llc -march=amdgcn -mcpu=fiji -run-pass=regbankselect %s -verify-machineinstrs -o - -regbankselect-fast | FileCheck %s
+# RUN: llc -march=amdgcn -mcpu=fiji -run-pass=regbankselect %s -verify-machineinstrs -o - -regbankselect-greedy | FileCheck %s
+
+---
+name: brcond_vcc_cond
+legalized: true
+body:             |
+  ; CHECK-LABEL: name: brcond_vcc_cond
+  ; CHECK: bb.0.entry:
+  ; CHECK:   successors: %bb.1(0x80000000)
+  ; CHECK:   [[COPY:%[0-9]+]]:vgpr(s32) = COPY $vgpr0
+  ; CHECK:   [[COPY1:%[0-9]+]]:vgpr(s32) = COPY $vgpr1
+  ; CHECK:   [[ICMP:%[0-9]+]]:sgpr(s1) = G_ICMP intpred(ne), [[COPY]](s32), [[COPY1]]
+  ; CHECK:   G_BRCOND [[ICMP]](s1), %bb.1
+  ; CHECK: bb.1:
+  bb.0.entry:
+    successors: %bb.1
+    liveins: $vgpr0, $vgpr1
+    %0:_(s32) = COPY $vgpr0
+    %1:_(s32) = COPY $vgpr1
+    %2:_(s1) = G_ICMP intpred(ne), %0, %1
+    G_BRCOND %2, %bb.1
+
+  bb.1:
+...
+
+---
+name: brcond_scc_cond
+legalized: true
+body:             |
+  ; CHECK-LABEL: name: brcond_scc_cond
+  ; CHECK: bb.0.entry:
+  ; CHECK:   successors: %bb.1(0x80000000)
+  ; CHECK:   [[COPY:%[0-9]+]]:sgpr(s32) = COPY $sgpr0
+  ; CHECK:   [[COPY1:%[0-9]+]]:sgpr(s32) = COPY $sgpr1
+  ; CHECK:   [[ICMP:%[0-9]+]]:scc(s1) = G_ICMP intpred(ne), [[COPY]](s32), [[COPY1]]
+  ; CHECK:   G_BRCOND [[ICMP]](s1), %bb.1
+  ; CHECK: bb.1:
+  bb.0.entry:
+    successors: %bb.1
+    liveins: $sgpr0, $sgpr1
+    %0:_(s32) = COPY $sgpr0
+    %1:_(s32) = COPY $sgpr1
+    %2:_(s1) = G_ICMP intpred(ne), %0, %1
+    G_BRCOND %2, %bb.1
+
+  bb.1:
+...
+
+---
+name: brcond_sgpr_cond
+legalized: true
+body:             |
+  ; CHECK-LABEL: name: brcond_sgpr_cond
+  ; CHECK: bb.0.entry:
+  ; CHECK:   successors: %bb.1(0x80000000)
+  ; CHECK:   [[COPY:%[0-9]+]]:sgpr(s32) = COPY $sgpr0
+  ; CHECK:   [[TRUNC:%[0-9]+]]:sgpr(s1) = G_TRUNC [[COPY]](s32)
+  ; CHECK:   G_BRCOND [[TRUNC]](s1), %bb.1
+  ; CHECK: bb.1:
+  bb.0.entry:
+    successors: %bb.1
+    liveins: $sgpr0
+    %0:_(s32) = COPY $sgpr0
+    %1:_(s1) = G_TRUNC %0
+    G_BRCOND %1, %bb.1
+
+  bb.1:
+...
+
+---
+name: brcond_vgpr_cond
+legalized: true
+body:             |
+  ; CHECK-LABEL: name: brcond_vgpr_cond
+  ; CHECK: bb.0.entry:
+  ; CHECK:   successors: %bb.1(0x80000000)
+  ; CHECK:   [[COPY:%[0-9]+]]:vgpr(s32) = COPY $vgpr0
+  ; CHECK:   [[TRUNC:%[0-9]+]]:vgpr(s1) = G_TRUNC [[COPY]](s32)
+  ; CHECK:   [[COPY1:%[0-9]+]]:sgpr(s1) = COPY [[TRUNC]](s1)
+  ; CHECK:   G_BRCOND [[COPY1]](s1), %bb.1
+  ; CHECK: bb.1:
+  bb.0.entry:
+    successors: %bb.1
+    liveins: $vgpr0
+    %0:_(s32) = COPY $vgpr0
+    %1:_(s1) = G_TRUNC %0
+    G_BRCOND %1, %bb.1
+
+  bb.1:
+...
+
+
+# The terminator that needs handling is the only instruction in the
+# block.
+
+---
+name: empty_block_vgpr_brcond
+legalized: true
+body:             |
+  ; CHECK-LABEL: name: empty_block_vgpr_brcond
+  ; CHECK: bb.0.entry:
+  ; CHECK:   successors: %bb.1(0x80000000)
+  ; CHECK:   [[COPY:%[0-9]+]]:vgpr(s32) = COPY $vgpr0
+  ; CHECK:   [[TRUNC:%[0-9]+]]:vgpr(s1) = G_TRUNC [[COPY]](s32)
+  ; CHECK: bb.1:
+  ; CHECK:   successors: %bb.1(0x40000000), %bb.2(0x40000000)
+  ; CHECK:   [[COPY1:%[0-9]+]]:sgpr(s1) = COPY [[TRUNC]](s1)
+  ; CHECK:   G_BRCOND [[COPY1]](s1), %bb.1
+  ; CHECK: bb.2:
+  bb.0.entry:
+    successors: %bb.1
+    liveins: $vgpr0
+    %0:_(s32) = COPY $vgpr0
+    %1:_(s1) = G_TRUNC %0
+
+  bb.1:
+    G_BRCOND %1, %bb.1
+
+  bb.2:
+...
+
+
+# Make sure the first instruction in the block isn't skipped.
+---
+name: copy_first_inst_brcond
+legalized: true
+body:             |
+  ; CHECK-LABEL: name: copy_first_inst_brcond
+  ; CHECK: bb.0.entry:
+  ; CHECK:   successors: %bb.1(0x80000000)
+  ; CHECK:   [[COPY:%[0-9]+]]:vgpr(s32) = COPY $vgpr0
+  ; CHECK: bb.1:
+  ; CHECK:   successors: %bb.1(0x40000000), %bb.2(0x40000000)
+  ; CHECK:   [[TRUNC:%[0-9]+]]:vgpr(s1) = G_TRUNC [[COPY]](s32)
+  ; CHECK:   [[COPY1:%[0-9]+]]:sgpr(s1) = COPY [[TRUNC]](s1)
+  ; CHECK:   G_BRCOND [[COPY1]](s1), %bb.1
+  ; CHECK: bb.2:
+  bb.0.entry:
+    successors: %bb.1
+    liveins: $vgpr0
+    %0:_(s32) = COPY $vgpr0
+
+  bb.1:
+    %1:_(s1) = G_TRUNC %0
+    G_BRCOND %1, %bb.1
+
+  bb.2:
+...
+
+# Extra instruction separates brcond from the condition def
+---
+name: copy_middle_inst_brcond
+legalized: true
+body:             |
+  ; CHECK-LABEL: name: copy_middle_inst_brcond
+  ; CHECK: bb.0.entry:
+  ; CHECK:   successors: %bb.1(0x80000000)
+  ; CHECK:   [[COPY:%[0-9]+]]:vgpr(s32) = COPY $vgpr0
+  ; CHECK: bb.1:
+  ; CHECK:   successors: %bb.1(0x40000000), %bb.2(0x40000000)
+  ; CHECK:   [[TRUNC:%[0-9]+]]:vgpr(s1) = G_TRUNC [[COPY]](s32)
+  ; CHECK:   S_NOP 0
+  ; CHECK:   [[COPY1:%[0-9]+]]:sgpr(s1) = COPY [[TRUNC]](s1)
+  ; CHECK:   G_BRCOND [[COPY1]](s1), %bb.1
+  ; CHECK: bb.2:
+  bb.0.entry:
+    successors: %bb.1
+    liveins: $vgpr0
+    %0:_(s32) = COPY $vgpr0
+
+  bb.1:
+    %1:_(s1) = G_TRUNC %0
+    S_NOP 0
+    G_BRCOND %1, %bb.1
+
+  bb.2:
+...