[ARM] Set Defs = [CPSR] for COPY_STRUCT_BYVAL, as it clobbers CPSR.

[fhahn]

Summary

Fixes PR35023.

[t.p.northover]

lib/CodeGen/ExpandISelPseudos.cpp

75 ↗

(On Diff #179002)

I think the logic needed here is a little more complicated. Fortunately, someone else has already been scarred for life by working it out (I expect) and you can just call addLiveIns from LivePhysRegs.h

[t.p.northover]

lib/CodeGen/ExpandISelPseudos.cpp

75 ↗

(On Diff #179002)

Actually, shouldn't whatever's doing the splitting update liveness too? For all ExpandISelPseudos knows there could be a dozen new blocks scattered across the function that need updating.

[qcolombet]

lib/CodeGen/ExpandISelPseudos.cpp

75 ↗

(On Diff #179002)

+1

[fhahn]

lib/CodeGen/ExpandISelPseudos.cpp

75 ↗

(On Diff #179002)

Actually, shouldn't whatever's doing the splitting update liveness too? For all ExpandISelPseudos knows there could be a dozen new blocks scattered across the function that need updating.

We could push the responsibility to the lowering code, but it would mean that we have to go through all lowering code. Doing it in ExpandISelLowering potentially misses cases as well though.

I'll take a look at the lowering code, a common pattern seems to be calling MBB->splice & MBB->transferSuccessorsAndPHIs in the lowering code (I checked ARM and X86). In some cases, there is manual handling for CPSR already, in some cases (like COPY_STRUCT_BYVAL_I32) it is missing.

[fhahn]

Use LivePhysRegs for liveins computation, pushed code to ARMISelLowering, handled all cases I could spot there. Adding Eli, as he fixed a similar problem in D54192, which I think should also be handled by the general liveins computation.

[efriedma]

I'm a little concerned computeAndAddLiveIns is more expensive than checkAndUpdateCPSRKill. In theory, they're both quadratic, but in practice I would expect checkAndUpdateCPSRKill is much cheaper: it only tracks one register, and quits immediately when it finds a def of CPSR.

[fhahn]

In D55909#1338002, @efriedma wrote:

I'm a little concerned computeAndAddLiveIns is more expensive than checkAndUpdateCPSRKill. In theory, they're both quadratic, but in practice I would expect checkAndUpdateCPSRKill is much cheaper: it only tracks one register, and quits immediately when it finds a def of CPSR.

Right, but don't we have to handle all relevant physical registers, e.g. if we would have a use of a physical register after tMOVCCr_pseudo in test_slt_not ? It might not be very likely in practice, but it seems like there is nothing preventing that from happening (it is quite easy to construct a MIR test that fails the machine verifier after expand-isel-pseudos). But maybe I am missing some constraint here?

The way we iterate over the instructions in ExpandISelPesudos also means that we end up doing more work than necessary if we have multiple pseudos introducing new MBBs in the original MBB, but we might be able to visit instructions in reverse order or something like that.

[efriedma]

The interesting constraint here is that ExpandISelPesudos runs immediately after ISel. And if you have an instruction which produces physical registers from an allocatable register class, ISel will COPY the values to virtual registers immediately after that instruction (and similarly for instructions that consume physical registers). So in practice, on ARM, the only physical register with a non-trivial live interval in ExpandISelPesudos is CPSR.

Granted, that's a bit fragile, and it isn't formally enforced anywhere.

[fhahn]

In D55909#1338092, @efriedma wrote:

The interesting constraint here is that ExpandISelPesudos runs immediately after ISel. And if you have an instruction which produces physical registers from an allocatable register class, ISel will COPY the values to virtual registers immediately after that instruction (and similarly for instructions that consume physical registers). So in practice, on ARM, the only physical register with a non-trivial live interval in ExpandISelPesudos is CPSR.

Granted, that's a bit fragile, and it isn't formally enforced anywhere.

Thanks Eli, I guess we can just go with only handling CPSR. I will update the patch!

[fhahn]

Reduced patch to just add CPSR to live-ins of newly created blocks, if required.

[efriedma]

lib/Target/ARM/ARMISelLowering.cpp

9009

Hang on... doesn't the loop clobber CPSR? I think rather than add the live-in marking like this, we need to mark COPY_STRUCT_BYVAL_I32 with "Defs = [CPSR]".

[qcolombet]

Could we just say that ExpandISelPseudo doesn't preserve the liveness and have it be recomputed when needed?

Basically, is the complexity we add here worth the compile time we save?
In particular, I am worried that we will do a lot of recomputations if there are a lot of copy_struct_by_val operations around, whereas we would do only one by recomputing the liveness lazily.

[fhahn]

lib/Target/ARM/ARMISelLowering.cpp

9009

Yes, at least when not in Thumb1, we define CPSR in the loop. I guess something could still potentially use CPSR after the COPY_STRUCT_BYVAL, then we would still need it in the live-ins. Not sure if that would make sense though.

[efriedma]

lib/Target/ARM/ARMISelLowering.cpp

9009

Presumably nothing is ever going to use the CPSR def of a COPY_STRUCT_BYVAL... we would have to add explicit logic for that, and the loop sets CPSR to a fixed value which isn't generally useful.

[fhahn]

Updated to just use Defs = [CPSR], as suggested by Eli.

[fhahn]

lib/Target/ARM/ARMISelLowering.cpp

9009

Right thanks, so for now I guess we can just mark it with Defs = [CPSR].

[efriedma]

LGTM

lib/Target/ARM/ARMISelLowering.cpp

BuildMI(*BB, Pos, dl, TII->get(StOpc), AddrOut)
         .addReg(Data)
         .addReg(AddrIn)
         .addReg(0)
         .addImm(StSize)
         .add(predOps(ARMCC::AL));
   }
 }
 
+// Returns true if CPSR is used/live before another definition.
+static bool isCPSRLiveBeforeDefinition(const MachineBasicBlock &BB,
+                                       const TargetRegisterInfo *TRI) {
+  // Scan forward through BB for a use/def of CPSR.
+  MachineBasicBlock::const_iterator miI = BB.begin();
+  for (MachineBasicBlock::const_iterator miE = BB.end(); miI != miE; ++miI) {
+    const MachineInstr &mi = *miI;
+    if (mi.readsRegister(ARM::CPSR))
+      return true;
+    if (mi.definesRegister(ARM::CPSR))
+      break; // Should have kill-flag - update below.
+  }
+
+  // If we hit the end of the block, check whether CPSR is live into a
+  // successor.
+  if (miI == BB.end())
+    return any_of(BB.successors(), [](const MachineBasicBlock *Succ) {
+      return Succ->isLiveIn(ARM::CPSR);
+    });
+
+  return false;
+}
+
 MachineBasicBlock *
 ARMTargetLowering::EmitStructByval(MachineInstr &MI,
                                    MachineBasicBlock *BB) const {
   // This pseudo instruction has 3 operands: dst, src, size
   // We expand it to a loop if size > Subtarget->getMaxInlineSizeThreshold().
   // Otherwise, we will generate unrolled scalar copies.
   const TargetInstrInfo *TII = Subtarget->getInstrInfo();
   const BasicBlock *LLVM_BB = BB->getBasicBlock();
ARMTargetLowering::EmitStructByval(MachineInstr &MI,
   MF->insert(It, loopMBB);
   MF->insert(It, exitMBB);
 
   // Transfer the remainder of BB and its successor edges to exitMBB.
   exitMBB->splice(exitMBB->begin(), BB,
                   std::next(MachineBasicBlock::iterator(MI)), BB->end());
   exitMBB->transferSuccessorsAndUpdatePHIs(BB);
 
+  // Check whether CPSR is live past the pseudo instruction.
+  const TargetRegisterInfo *TRI = Subtarget->getRegisterInfo();
+  if (isCPSRLiveBeforeDefinition(*exitMBB, TRI)) {
+    loopMBB->addLiveIn(ARM::CPSR);
+    exitMBB->addLiveIn(ARM::CPSR);
+  }
+
   // Load an immediate to varEnd.
   unsigned varEnd = MRI.createVirtualRegister(TRC);
   if (Subtarget->useMovt(*MF)) {
     unsigned Vtmp = varEnd;
     if ((LoopSize & 0xFFFF0000) != 0)
       Vtmp = MRI.createVirtualRegister(TRC);
     BuildMI(BB, dl, TII->get(IsThumb ? ARM::t2MOVi16 : ARM::MOVi16), Vtmp)
         .addImm(LoopSize & 0xFFFF)
BuildMI(*MBB, MI, DL, TII->get(ARM::t2Bcc))
       .addMBB(TrapBB)
       .addImm(ARMCC::EQ)
       .addReg(ARM::CPSR);
 
   MI.eraseFromParent();
   return ContBB;
 }
 
-// The CPSR operand of SelectItr might be missing a kill marker
-// because there were multiple uses of CPSR, and ISel didn't know
-// which to mark. Figure out whether SelectItr should have had a
-// kill marker, and set it if it should. Returns the correct kill
-// marker value.
-static bool checkAndUpdateCPSRKill(MachineBasicBlock::iterator SelectItr,
-                                   MachineBasicBlock* BB,
-                                   const TargetRegisterInfo* TRI) {
-  // Scan forward through BB for a use/def of CPSR.
-  MachineBasicBlock::iterator miI(std::next(SelectItr));
-  for (MachineBasicBlock::iterator miE = BB->end(); miI != miE; ++miI) {
-    const MachineInstr& mi = *miI;
-    if (mi.readsRegister(ARM::CPSR))
-      return false;
-    if (mi.definesRegister(ARM::CPSR))
-      break; // Should have kill-flag - update below.
-  }
-
-  // If we hit the end of the block, check whether CPSR is live into a
-  // successor.
-  if (miI == BB->end()) {
-    for (MachineBasicBlock::succ_iterator sItr = BB->succ_begin(),
-                                          sEnd = BB->succ_end();
-         sItr != sEnd; ++sItr) {
-      MachineBasicBlock* succ = *sItr;
-      if (succ->isLiveIn(ARM::CPSR))
-        return false;
-    }
-  }
-
-  // We found a def, or hit the end of the basic block and CPSR wasn't live
-  // out. SelectMI should have a kill flag on CPSR.
-  SelectItr->addRegisterKilled(ARM::CPSR, TRI);
-  return true;
-}
-
 MachineBasicBlock *
 ARMTargetLowering::EmitInstrWithCustomInserter(MachineInstr &MI,
                                                MachineBasicBlock *BB) const {
   const TargetInstrInfo *TII = Subtarget->getInstrInfo();
   DebugLoc dl = MI.getDebugLoc();
   bool isThumb2 = Subtarget->isThumb2();
   switch (MI.getOpcode()) {
   default: {
case ARM::tMOVCCr_pseudo: {
     MachineFunction *F = BB->getParent();
     MachineBasicBlock *copy0MBB = F->CreateMachineBasicBlock(LLVM_BB);
     MachineBasicBlock *sinkMBB  = F->CreateMachineBasicBlock(LLVM_BB);
     F->insert(It, copy0MBB);
     F->insert(It, sinkMBB);
 
     // Check whether CPSR is live past the tMOVCCr_pseudo.
     const TargetRegisterInfo *TRI = Subtarget->getRegisterInfo();
-    if (!MI.killsRegister(ARM::CPSR) &&
-        !checkAndUpdateCPSRKill(MI, thisMBB, TRI)) {
-      copy0MBB->addLiveIn(ARM::CPSR);
-      sinkMBB->addLiveIn(ARM::CPSR);
-    }
 
     // Transfer the remainder of BB and its successor edges to sinkMBB.
     sinkMBB->splice(sinkMBB->begin(), BB,
                     std::next(MachineBasicBlock::iterator(MI)), BB->end());
     sinkMBB->transferSuccessorsAndUpdatePHIs(BB);
 
+    if (!MI.killsRegister(ARM::CPSR)) {
+      // The CPSR operand of MI might be missing a kill marker
+      // because there were multiple uses of CPSR, and ISel didn't know
+      // which to mark. Figure out whether MI should have had a
+      // kill marker, and set it if it should.
+      if (isCPSRLiveBeforeDefinition(*sinkMBB, TRI)) {
+        copy0MBB->addLiveIn(ARM::CPSR);
+        sinkMBB->addLiveIn(ARM::CPSR);
+      } else
+        // MI is the last use of CPSR, we can kill it.
+        MI.addRegisterKilled(ARM::CPSR, TRI);
+    }
+
     BB->addSuccessor(copy0MBB);
     BB->addSuccessor(sinkMBB);
 
     BuildMI(BB, dl, TII->get(ARM::tBcc))
         .addMBB(sinkMBB)
         .addImm(MI.getOperand(3).getImm())
         .addReg(MI.getOperand(4).getReg());
 

test/CodeGen/ARM/expand-isel-pseudos-liveins.mir

+# Check liveins are properly set when new MBBs are created in
+# expand-isel-pseudos.
+
+# RUN: llc -mtriple=arm-unknown- -run-pass=expand-isel-pseudos %s -o - | FileCheck %s
+--- |
+
+  define i32 @test_copy_struct_byval(i32 %x) {
+  entry:
+    unreachable
+  }
+
+  define { i32, i32 } @test_slt_not(i32 %c, i32 %d, i64 %a, i64 %b) {
+  entry:
+    %cmp = icmp slt i64 %a, %b
+    %not = xor i1 %cmp, true
+    %r1 = zext i1 %cmp to i32
+    %r2 = zext i1 %not to i32
+    %z = insertvalue { i32, i32 } undef, i32 %r1, 0
+    %z2 = insertvalue { i32, i32 } %z, i32 %r2, 1
+    ret { i32, i32 } %z2
+  }
+...
+---
+# CHECK-LABEL: name: test_copy_struct_byval
+# CHECK-LABEL: bb.2.entry:
+# CHECK-NEXT: liveins: $cpsr
+name:            test_copy_struct_byval
+alignment:       2
+tracksRegLiveness: true
+registers:
+  - { id: 0, class: gpr, preferred-register: '' }
+  - { id: 1, class: gpr, preferred-register: '' }
+  - { id: 2, class: gpr, preferred-register: '' }
+  - { id: 3, class: gpr, preferred-register: '' }
+  - { id: 4, class: gpr, preferred-register: '' }
+  - { id: 5, class: gpr, preferred-register: '' }
+  - { id: 6, class: gpr, preferred-register: '' }
+  - { id: 7, class: gpr, preferred-register: '' }
+  - { id: 8, class: gpr, preferred-register: '' }
+  - { id: 9, class: gpr, preferred-register: '' }
+  - { id: 10, class: gpr, preferred-register: '' }
+  - { id: 11, class: gpr, preferred-register: '' }
+  - { id: 12, class: gpr, preferred-register: '' }
+liveins:
+  - { reg: '$r0', virtual-reg: '%0' }
+  - { reg: '$r1', virtual-reg: '%1' }
+body:             |
+  bb.0.entry:
+    liveins: $r0, $r1
+
+    %1:gpr = COPY $r1
+    %0:gpr = COPY $r0
+    %2:gpr = LDRi12 %0, 0, 14, $noreg :: (load 4)
+    %3:gpr = LDRi12 %0, 4, 14, $noreg :: (load 4)
+    ADJCALLSTACKDOWN 136, 0, 14, $noreg, implicit-def dead $sp, implicit $sp
+    %4:gpr = ADDri %1, 16, 14, $noreg, $noreg
+    %5:gpr = LDRi12 %1, 0, 14, $noreg :: (load 4)
+    %6:gpr = LDRi12 %1, 4, 14, $noreg :: (load 4)
+    %7:gpr = LDRi12 %1, 8, 14, $noreg :: (load 4)
+    %8:gpr = LDRi12 %1, 12, 14, $noreg :: (load 4)
+    %9:gpr = COPY $sp
+    COPY_STRUCT_BYVAL_I32 %9, killed %4, 56, 8
+    %10:gpr = SUBri %2, 1, 14, $noreg, def $cpsr
+    STRi12 killed %10, %9, 128, 14, $noreg :: (store 4 into stack + 128)
+    %11:gpr = ADDri %9, 56, 14, $noreg, $noreg
+    COPY_STRUCT_BYVAL_I32 killed %11, %1, 72, 8
+    %12:gpr = SUBri killed %2, 1, 14, $noreg, $cpsr
+    STRi12 killed %12, %9, 132, 14, $noreg :: (store 4 into stack + 132)
+    $r0 = COPY %5
+    $r1 = COPY %6
+    $r2 = COPY %7
+    $r3 = COPY %8
+    ADJCALLSTACKUP 136, 0, 14, $noreg, implicit-def dead $sp, implicit $sp
+    BX_RET 14, $noreg
+
+...
+---
+# CHECK-LABEL: name: test_slt_not
+# CHECK-LABEL: bb.1.entry:
+# CHECK-NEXT: successors:
+# CHECK-NEXT: liveins: $cpsr
+# CHECK-LABEL: bb.2.entry:
+# CHECK-NEXT: successors:
+# CHECK-NEXT: liveins: $cpsr
+name:            test_slt_not
+alignment:       1
+tracksRegLiveness: true
+hasWinCFI:       false
+registers:
+  - { id: 0, class: tgpr, preferred-register: '' }
+  - { id: 1, class: tgpr, preferred-register: '' }
+  - { id: 2, class: tgpr, preferred-register: '' }
+  - { id: 3, class: tgpr, preferred-register: '' }
+  - { id: 4, class: tgpr, preferred-register: '' }
+  - { id: 5, class: tgpr, preferred-register: '' }
+  - { id: 6, class: tgpr, preferred-register: '' }
+  - { id: 7, class: tgpr, preferred-register: '' }
+  - { id: 8, class: tgpr, preferred-register: '' }
+  - { id: 9, class: tgpr, preferred-register: '' }
+  - { id: 10, class: tgpr, preferred-register: '' }
+  - { id: 11, class: tgpr, preferred-register: '' }
+liveins:
+  - { reg: '$r2', virtual-reg: '%2' }
+  - { reg: '$r3', virtual-reg: '%3' }
+frameInfo:
+fixedStack:
+  - { id: 0, type: default, offset: 4, size: 4, alignment: 4, stack-id: 0,
+      isImmutable: true, isAliased: false, callee-saved-register: '', callee-saved-restored: true,
+      debug-info-variable: '', debug-info-expression: '', debug-info-location: '' }
+  - { id: 1, type: default, offset: 0, size: 4, alignment: 8, stack-id: 0,
+      isImmutable: true, isAliased: false, callee-saved-register: '', callee-saved-restored: true,
+      debug-info-variable: '', debug-info-expression: '', debug-info-location: '' }
+stack:           []
+constants:       []
+body:             |
+  bb.0.entry:
+    liveins: $r2, $r3
+
+    %3:tgpr = COPY $r3
+    %2:tgpr = COPY $r2
+    %4:tgpr, dead $cpsr = tMOVi8 1, 14, $noreg
+    %5:tgpr, dead $cpsr = tMOVi8 0, 14, $noreg
+    %6:tgpr = tLDRspi %fixed-stack.0, 0, 14, $noreg :: (load 4 from %fixed-stack.0)
+    %7:tgpr = tLDRspi %fixed-stack.1, 0, 14, $noreg :: (load 4 from %fixed-stack.1, align 8)
+    %8:tgpr, $cpsr = tSUBrr %2, killed %7, 14, $noreg
+    %9:tgpr, $cpsr = tSBC %3, %6, 14, $noreg, implicit $cpsr
+    %10:tgpr = tMOVCCr_pseudo %5, %4, 11, $cpsr
+    %11:tgpr = tMOVCCr_pseudo %5, %4, 10, $cpsr
+    $r0 = COPY %10
+    $r1 = COPY %11
+    %12:tgpr, $cpsr = tSBC %3, killed %6, 14, $noreg, implicit $cpsr
+    STRi12 killed %12, %2, 132, 14, $noreg :: (store 4 into stack + 132)
+    tBX_RET 14, $noreg, implicit $r0, implicit $r1
+...