[AArch64][GlobalISel] Fixup <32b heterogeneous regbanks of G_PHIs just before selection.

[aemerson]

Summary

Since all types <32b on gpr end up being assigned gpr32 regclasses, we can end up with PHIs here which try to select between a gpr32 and an fpr16. Ideally RBS shouldn't be selecting heterogenous regbanks for operands if possible, but we still need to be able to deal with it here.

To fix this, if we have a gpr-bank operand < 32b in size and at least one other operand is on the fpr bank, then we add cross-bank copies to homogenize the operand banks. For simplicity the bank that we choose to settle on is whatever bank the def operand has. For example:

%endbb:
      %dst:gpr(s16) = G_PHI %in1:gpr(s16), %bb1, %in2:fpr(s16), %bb2
     =>
%bb2:
      ...
      %in2_copy:gpr(s16) = COPY %in2:fpr(s16)
      ...
%endbb:
      %dst:gpr(s16) = G_PHI %in1:gpr(s16), %bb1, %in2_copy:gpr(s16), %bb2

[qcolombet]

Hi Amara,

Why do you have to fix-up the PHIs before selection?

I would expect G_PHI to be selected to PHI (i.e., just a opcode change) and then the phi elimination pass will insert the cross copies for you.

Where is this going wrong?

Cheers,
-Quentin

[aemerson]

I would expect G_PHI to be selected to PHI (i.e., just a opcode change) and then the phi elimination pass will insert the cross copies for you.

Where is this going wrong?

Thanks for taking a look. Yes the G_PHI gets selected to PHI. This is normally ok even in the case where we have operands with different regbanks. However on AArch64 this doesn't work when the type size is less than 32 bits. If this happens, the PHI operand with a GPR RegBank gets the gpr32 regclass assigned to it (we don't have anything smaller to represent types like s16 on GPR on AArch64). Then the FPR bank operand gets the appropriately sized FPR16 regclass assigned. These two registers have different sizes, and copyPhysReg doesn't know how to deal with copies between a gpr32 and an fpr16 or vice versa. I thought about maybe teaching copyPhysReg to deal with that, but the fact that we have to deal with subregisters (because of the differing sizes) makes me nervous and didn't seem like the best place to fix it.

I also tried to fix RegBankSelect to add fixups if we detect this case but this is an AArch64 specific issue, and it messed up a lot of existing PHI handling (which assumes we can just look at one operand to decide the RegBank).

[aemerson]

Forgot to answer your first question:

Why do you have to fix-up the PHIs before selection?

The reason I'm doing this before selection is that by the time we get to a G_PHI, if it's part of a cycle, then an operand register will also be a selected instruction. If I do it before selection, then they should still have generic types and regbanks, and adding COPY instructions is simple because the existing COPY selection code can be harnessed to generate the right SUBREG_TO_REG/whatever.

[qcolombet]

Thanks for the clarification Amara.

Now a follow-up question:

If this happens, the PHI operand with a GPR RegBank gets the gpr32 regclass assigned to it (we don't have anything smaller to represent types like s16 on GPR on AArch64).

How do you represent s16 values into gpr32?

I would have expected that if you have to widen the size when assigning the actual register class, then legalization should have actually widen the value. Otherwise, that means we have to manually deal with "dangling" bits everywhere else.

[aemerson]

In D75086#1893996, @qcolombet wrote:

Thanks for the clarification Amara.

Now a follow-up question:

If this happens, the PHI operand with a GPR RegBank gets the gpr32 regclass assigned to it (we don't have anything smaller to represent types like s16 on GPR on AArch64).

How do you represent s16 values into gpr32?

s16 operations, if legal, just get selected to gpr32 regclass instructions. E.g.

%ld:gpr(s16) = G_LOAD ...
=>
%ld:gpr32 = LDR_16 ...

For things like G_ADD we legalize to s32, but s16 itself as a type isn't illegal.

I would have expected that if you have to widen the size when assigning the actual register class, then legalization should have actually widen the value. Otherwise, that means we have to manually deal with "dangling" bits everywhere else.

[qcolombet]

s16 operations, if legal, just get selected to gpr32 regclass instructions. E.g.

%ld:gpr(s16) = G_LOAD ...
=>
%ld:gpr32 = LDR_16 ...

That's interesting, because that means you have inreg extension where you would have regular extension in the IR.
E.g.,

s16 = G_LOAD
s32 = G_ZEXT s16

>

gpr32 = LDR_16
gpr32 = G_ZEXT gpr32

I would have expected that instead we would have combined loads with the related extension to from an extended load.

Anyway, I guess this ship has sailed.

LGTM.

[aemerson]

In D75086#1894223, @qcolombet wrote:

s16 operations, if legal, just get selected to gpr32 regclass instructions. E.g.

%ld:gpr(s16) = G_LOAD ...
=>
%ld:gpr32 = LDR_16 ...

That's interesting, because that means you have inreg extension where you would have regular extension in the IR.
E.g.,

s16 = G_LOAD
s32 = G_ZEXT s16

>

gpr32 = LDR_16
gpr32 = G_ZEXT gpr32

I would have expected that instead we would have combined loads with the related extension to from an extended load.

Yes, on AArch64 all sub-32bit loads give a free ZEXT. We catch this case in the selector if for some reason we have a redundant ZEXT.

Anyway, I guess this ship has sailed.

LGTM.

[qcolombet]

Something just stroke me, why don't you use the FPR bank for all 16-bit values then?

Put differently I feel this is a work around other issue, either legalization or reg bank select. Bottom line, I really don't like this patch, but I let you judge what is the best way to move forward.

[aemerson]

I committed before I saw your message.

In D75086#1894402, @qcolombet wrote:

Something just stroke me, why don't you use the FPR bank for all 16-bit values then?

Off the top of my head: we would lose the distinction between a gpr and fpr load. For example, the following:

define i16 @bitwise(i16 *%a, i16 *%b) {
  %res = load i16, i16 *%a
  %x = xor i16 %res, 12345
  store i16 %x, i16 *%b
  ret i16 %x
}

would end up having RegBank assignments like this:

body:             |
  bb.1 (%ir-block.0):
    liveins: $x0, $x1
  
    %0:gpr(p0) = COPY $x0
    %1:gpr(p0) = COPY $x1
    %2:fpr(s16) = G_LOAD %0(p0) :: (load 2 from %ir.a)
    %copy:gpr(s16) = COPY %2(s16) ; Need a cross-bank copy here because of the ANYEXT+XOR.
    %6:gpr(s32) = G_ANYEXT %copy(s16)
    %7:gpr(s32) = G_CONSTANT i32 12345
    %8:gpr(s32) = G_XOR %6, %7
    %4:gpr(s16) = G_TRUNC %8(s32)
    %copy2:fpr(s16) = COPY %4(s16) ; Likewise here to get back to an fpr s16 value.
    G_STORE %copy2(s16), %1(p0) :: (store 2 into %ir.b)
    %5:gpr(s32) = COPY %8(s32)
    $w0 = COPY %5(s32)
    RET_ReallyLR implicit $w0

This results in cross-bank copies which are bad for performance. We can't eliminate s16 GPRs completely because things like trunc/extend need to be able to deal with them, as well as G_EXTRACT/INSERT. Maybe there's a way to deal with those issues too, I'm not sure.

Put differently I feel this is a work around other issue, either legalization or reg bank select. Bottom line, I really don't like this patch, but I let you judge what is the best way to move forward.

I think this ultimately stems from the fact that we lost fp/integer type information in the translator and trying to patch this back together from defs and uses is prone to failure. For performance reasons it there's probably no good reason to have G_PHIs with separate regbanks, but RBS is difficult to change. Not only that but in this case if you have a cyclic phi you can't even tell completely whether or not you have this problem because not every user has had a RegBank assigned yet.

[qcolombet]

I understand that cross copies are bad, but what I don't understand is why don't we form an extended load? That would apply nicely to your example.

Put differently, (I am being pedantic just for the sake of the argument), I would argue that:
s16 = G_LOAD
maps to
fpr16 = LDR

not
gpr32 = LDR16
since we're effectively sneaking in an extension in that load.

gpr32 = LDR16 would better match ANYEXT(G_LOAD).

All in all I understand your solution and why you're doing that. I am afraid we are actually building technical debt here, but I trust your judgement on what you think is best to move forward here.

To go back on RBS, we could "fix" it to issue only PHIs with the same bank, but effectively, we would just move the copies around and basically still have the weirdly sized cross copies [1] appearing as COPY instead of PHIs and in different blocks.

Like you noted with PHIs in loops, ideally we would like to have RBS to make its decision globally. That would indeed require some work and also, I believe that would only make the weird sized copies less likely to happen but not impossible. Therefore I really think this is a legalization issue.

[1] they are only weirdly sized after selection which is why I think we are actually not modeling this right :)

[aemerson]

In D75086#1894721, @qcolombet wrote:

I understand that cross copies are bad, but what I don't understand is why don't we form an extended load? That would apply nicely to your example.

I see what you mean. Essentially we would take the code size/perf hit with the specific MIR example I used, but instead try harder to form the extending load ops and ensure those are assigned to gpr banks. There might be other issues with G_EXTRACT but we'll see.

Since this patch fixes a compiler crash I'm going to leave it in, but I'll investigate this approach as a follow up.

Put differently, (I am being pedantic just for the sake of the argument), I would argue that:
s16 = G_LOAD
maps to
fpr16 = LDR

not
gpr32 = LDR16
since we're effectively sneaking in an extension in that load.

gpr32 = LDR16 would better match ANYEXT(G_LOAD).

All in all I understand your solution and why you're doing that. I am afraid we are actually building technical debt here, but I trust your judgement on what you think is best to move forward here.

To go back on RBS, we could "fix" it to issue only PHIs with the same bank, but effectively, we would just move the copies around and basically still have the weirdly sized cross copies [1] appearing as COPY instead of PHIs and in different blocks.

Like you noted with PHIs in loops, ideally we would like to have RBS to make its decision globally. That would indeed require some work and also, I believe that would only make the weird sized copies less likely to happen but not impossible. Therefore I really think this is a legalization issue.

[1] they are only weirdly sized after selection which is why I think we are actually not modeling this right :)

llvm/lib/Target/AArch64/AArch64InstructionSelector.cpp

void setupMF(MachineFunction &MF, GISelKnownBits &KB,
                CodeGenCoverage &CoverageInfo) override {
     InstructionSelector::setupMF(MF, KB, CoverageInfo);
 
     // hasFnAttribute() is expensive to call on every BRCOND selection, so
     // cache it here for each run of the selector.
     ProduceNonFlagSettingCondBr =
         !MF.getFunction().hasFnAttribute(Attribute::SpeculativeLoadHardening);
     MFReturnAddr = Register();
+
+    processPHIs(MF);
   }
 
 private:
   /// tblgen-erated 'select' implementation, used as the initial selector for
   /// the patterns that don't require complex C++.
   bool selectImpl(MachineInstr &I, CodeGenCoverage &CoverageInfo) const;
 
   // A lowering phase that runs before any selection attempts.
   // Returns true if the instruction was modified.
   bool preISelLower(MachineInstr &I);
 
   // An early selection function that runs before the selectImpl() call.
   bool earlySelect(MachineInstr &I) const;
 
+  // Do some preprocessing of G_PHIs before we begin selection.
+  void processPHIs(MachineFunction &MF);
+
   bool earlySelectSHL(MachineInstr &I, MachineRegisterInfo &MRI) const;
 
   /// Eliminate same-sized cross-bank copies into stores before selectImpl().
   bool contractCrossBankCopyIntoStore(MachineInstr &I,
                                       MachineRegisterInfo &MRI);
 
   bool convertPtrAddToAdd(MachineInstr &I, MachineRegisterInfo &MRI);
 
bool AArch64InstructionSelector::isDef32(const MachineInstr &MI) const {
   case TargetOpcode::COPY:
   case TargetOpcode::G_BITCAST:
   case TargetOpcode::G_TRUNC:
   case TargetOpcode::G_PHI:
     return false;
   }
 }
 
+
+// Perform fixups on the given PHI instruction's operands to force them all
+// to be the same as the destination regbank.
+static void fixupPHIOpBanks(MachineInstr &MI, MachineRegisterInfo &MRI,
+                            const AArch64RegisterBankInfo &RBI) {
+  assert(MI.getOpcode() == TargetOpcode::G_PHI && "Expected a G_PHI");
+  Register DstReg = MI.getOperand(0).getReg();
+  const RegisterBank *DstRB = MRI.getRegBankOrNull(DstReg);
+  assert(DstRB && "Expected PHI dst to have regbank assigned");
+  MachineIRBuilder MIB(MI);
+
+  // Go through each operand and ensure it has the same regbank.
+  for (unsigned OpIdx = 1; OpIdx < MI.getNumOperands(); ++OpIdx) {
+    MachineOperand &MO = MI.getOperand(OpIdx);
+    if (!MO.isReg())
+      continue;
+    Register OpReg = MO.getReg();
+    const RegisterBank *RB = MRI.getRegBankOrNull(OpReg);
+    if (RB != DstRB) {
+      // Insert a cross-bank copy.
+      auto *OpDef = MRI.getVRegDef(OpReg);
+      const LLT &Ty = MRI.getType(OpReg);
+      MIB.setInsertPt(*OpDef->getParent(), std::next(OpDef->getIterator()));
+      auto Copy = MIB.buildCopy(Ty, OpReg);
+      MRI.setRegBank(Copy.getReg(0), *DstRB);
+      MO.setReg(Copy.getReg(0));
+    }
+  }
+}
+
+void AArch64InstructionSelector::processPHIs(MachineFunction &MF) {
+  // We're looking for PHIs, build a list so we don't invalidate iterators.
+  MachineRegisterInfo &MRI = MF.getRegInfo();
+  SmallVector<MachineInstr *, 32> Phis;
+  for (auto &BB : MF) {
+    for (auto &MI : BB) {
+      if (MI.getOpcode() == TargetOpcode::G_PHI)
+        Phis.emplace_back(&MI);
+    }
+  }
+
+  for (auto *MI : Phis) {
+    // We need to do some work here if the operand types are < 16 bit and they
+    // are split across fpr/gpr banks. Since all types <32b on gpr
+    // end up being assigned gpr32 regclasses, we can end up with PHIs here
+    // which try to select between a gpr32 and an fpr16. Ideally RBS shouldn't
+    // be selecting heterogenous regbanks for operands if possible, but we
+    // still need to be able to deal with it here.
+    //
+    // To fix this, if we have a gpr-bank operand < 32b in size and at least
+    // one other operand is on the fpr bank, then we add cross-bank copies
+    // to homogenize the operand banks. For simplicity the bank that we choose
+    // to settle on is whatever bank the def operand has. For example:
+    //
+    // %endbb:
+    //   %dst:gpr(s16) = G_PHI %in1:gpr(s16), %bb1, %in2:fpr(s16), %bb2
+    //  =>
+    // %bb2:
+    //   ...
+    //   %in2_copy:gpr(s16) = COPY %in2:fpr(s16)
+    //   ...
+    // %endbb:
+    //   %dst:gpr(s16) = G_PHI %in1:gpr(s16), %bb1, %in2_copy:gpr(s16), %bb2
+    bool HasGPROp = false, HasFPROp = false;
+    for (unsigned OpIdx = 1; OpIdx < MI->getNumOperands(); ++OpIdx) {
+      const auto &MO = MI->getOperand(OpIdx);
+      if (!MO.isReg())
+        continue;
+      const LLT &Ty = MRI.getType(MO.getReg());
+      if (!Ty.isValid() || !Ty.isScalar())
+        break;
+      if (Ty.getSizeInBits() >= 32)
+        break;
+      const RegisterBank *RB = MRI.getRegBankOrNull(MO.getReg());
+      // If for some reason we don't have a regbank yet. Don't try anything.
+      if (!RB)
+        break;
+
+      if (RB->getID() == AArch64::GPRRegBankID)
+        HasGPROp = true;
+      else
+        HasFPROp = true;
+    }
+    // We have heterogenous regbanks, need to fixup.
+    if (HasGPROp && HasFPROp)
+      fixupPHIOpBanks(*MI, MRI, RBI);
+  }
+}
+
 namespace llvm {
 InstructionSelector *
 createAArch64InstructionSelector(const AArch64TargetMachine &TM,
                                  AArch64Subtarget &Subtarget,
                                  AArch64RegisterBankInfo &RBI) {
   return new AArch64InstructionSelector(TM, Subtarget, RBI);
 }
 }

llvm/test/CodeGen/AArch64/GlobalISel/preselect-process-phis.mir

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+# RUN: llc -verify-machineinstrs -mtriple aarch64--- -run-pass=instruction-select -global-isel %s -o - | FileCheck %s
+---
+name:            test_loop_phi_fpr_to_gpr
+alignment:       4
+legalized:       true
+regBankSelected: true
+selected:        false
+failedISel:      false
+tracksRegLiveness: true
+liveins:         []
+machineFunctionInfo: {}
+body:             |
+  ; CHECK-LABEL: name: test_loop_phi_fpr_to_gpr
+  ; CHECK: bb.0:
+  ; CHECK:   successors: %bb.1(0x80000000)
+  ; CHECK:   [[DEF:%[0-9]+]]:gpr32 = IMPLICIT_DEF
+  ; CHECK:   [[DEF1:%[0-9]+]]:gpr64common = IMPLICIT_DEF
+  ; CHECK:   [[MOVi32imm:%[0-9]+]]:gpr32 = MOVi32imm 2143289344
+  ; CHECK:   [[COPY:%[0-9]+]]:fpr32 = COPY [[MOVi32imm]]
+  ; CHECK: bb.1:
+  ; CHECK:   successors: %bb.2(0x80000000)
+  ; CHECK:   [[DEF2:%[0-9]+]]:gpr32 = IMPLICIT_DEF
+  ; CHECK:   $wzr = ANDSWri [[DEF]], 0, implicit-def $nzcv
+  ; CHECK:   [[CSELWr:%[0-9]+]]:gpr32 = CSELWr [[DEF2]], [[DEF2]], 1, implicit $nzcv
+  ; CHECK: bb.2:
+  ; CHECK:   successors: %bb.2(0x80000000)
+  ; CHECK:   [[PHI:%[0-9]+]]:gpr32 = PHI [[CSELWr]], %bb.1, %8, %bb.2
+  ; CHECK:   [[FCVTHSr:%[0-9]+]]:fpr16 = FCVTHSr [[COPY]]
+  ; CHECK:   [[SUBREG_TO_REG:%[0-9]+]]:fpr32 = SUBREG_TO_REG 0, [[FCVTHSr]], %subreg.hsub
+  ; CHECK:   [[COPY1:%[0-9]+]]:gpr32all = COPY [[SUBREG_TO_REG]]
+  ; CHECK:   STRHHui [[PHI]], [[DEF1]], 0 :: (store 2 into `half* undef`)
+  ; CHECK:   B %bb.2
+  bb.0:
+    successors: %bb.1(0x80000000)
+
+    %0:gpr(s1) = G_IMPLICIT_DEF
+    %4:gpr(p0) = G_IMPLICIT_DEF
+    %8:fpr(s32) = G_FCONSTANT float 0x7FF8000000000000
+
+  bb.1:
+    successors: %bb.2(0x80000000)
+
+    %6:gpr(s32) = G_IMPLICIT_DEF
+    %7:gpr(s32) = G_SELECT %0(s1), %6, %6
+    %1:gpr(s16) = G_TRUNC %7(s32)
+
+  bb.2:
+    successors: %bb.2(0x80000000)
+
+    %3:gpr(s16) = G_PHI %1(s16), %bb.1, %5(s16), %bb.2
+    %5:fpr(s16) = G_FPTRUNC %8(s32)
+    G_STORE %3(s16), %4(p0) :: (store 2 into `half* undef`)
+    G_BR %bb.2
+
+...
+---
+name:            test_loop_phi_gpr_to_fpr
+alignment:       4
+legalized:       true
+regBankSelected: true
+selected:        false
+failedISel:      false
+tracksRegLiveness: true
+liveins:         []
+machineFunctionInfo: {}
+body:             |
+  ; CHECK-LABEL: name: test_loop_phi_gpr_to_fpr
+  ; CHECK: bb.0:
+  ; CHECK:   successors: %bb.1(0x80000000)
+  ; CHECK:   [[DEF:%[0-9]+]]:gpr32 = IMPLICIT_DEF
+  ; CHECK:   [[DEF1:%[0-9]+]]:gpr64common = IMPLICIT_DEF
+  ; CHECK:   [[MOVi32imm:%[0-9]+]]:gpr32 = MOVi32imm 2143289344
+  ; CHECK:   [[COPY:%[0-9]+]]:fpr32 = COPY [[MOVi32imm]]
+  ; CHECK: bb.1:
+  ; CHECK:   successors: %bb.2(0x80000000)
+  ; CHECK:   [[DEF2:%[0-9]+]]:gpr32 = IMPLICIT_DEF
+  ; CHECK:   $wzr = ANDSWri [[DEF]], 0, implicit-def $nzcv
+  ; CHECK:   [[CSELWr:%[0-9]+]]:gpr32 = CSELWr [[DEF2]], [[DEF2]], 1, implicit $nzcv
+  ; CHECK:   [[COPY1:%[0-9]+]]:fpr32 = COPY [[CSELWr]]
+  ; CHECK:   [[COPY2:%[0-9]+]]:fpr16 = COPY [[COPY1]].hsub
+  ; CHECK: bb.2:
+  ; CHECK:   successors: %bb.2(0x80000000)
+  ; CHECK:   [[PHI:%[0-9]+]]:fpr16 = PHI %7, %bb.2, [[COPY2]], %bb.1
+  ; CHECK:   [[FCVTHSr:%[0-9]+]]:fpr16 = FCVTHSr [[COPY]]
+  ; CHECK:   STRHui [[PHI]], [[DEF1]], 0 :: (store 2 into `half* undef`)
+  ; CHECK:   B %bb.2
+  bb.0:
+    successors: %bb.1(0x80000000)
+
+    %0:gpr(s1) = G_IMPLICIT_DEF
+    %4:gpr(p0) = G_IMPLICIT_DEF
+    %8:fpr(s32) = G_FCONSTANT float 0x7FF8000000000000
+
+  bb.1:
+    successors: %bb.2(0x80000000)
+
+    %6:gpr(s32) = G_IMPLICIT_DEF
+    %7:gpr(s32) = G_SELECT %0(s1), %6, %6
+    %1:gpr(s16) = G_TRUNC %7(s32)
+
+  bb.2:
+    successors: %bb.2(0x80000000)
+
+    %3:fpr(s16) = G_PHI %5(s16), %bb.2, %1(s16), %bb.1
+    %5:fpr(s16) = G_FPTRUNC %8(s32)
+    G_STORE %3(s16), %4(p0) :: (store 2 into `half* undef`)
+    G_BR %bb.2
+
+...