[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

8986

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

8986

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

8986

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

8986

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

[efriedma]

LGTM

include/llvm/CodeGen/LivePhysRegs.h

 /// Adds registers contained in \p LiveRegs to the block live-in list of \p MBB.
 /// Does not add reserved registers.
 void addLiveIns(MachineBasicBlock &MBB, const LivePhysRegs &LiveRegs);
 
 /// Convenience function combining computeLiveIns() and addLiveIns().
 void computeAndAddLiveIns(LivePhysRegs &LiveRegs,
                           MachineBasicBlock &MBB);
 
+/// Convenience function combining computeLiveIns() and addLiveIns() for \p MBB.
+void computeAndAddLiveIns(MachineBasicBlock &MBB);
+
 /// Convenience function for recomputing live-in's for \p MBB.
 static inline void recomputeLiveIns(MachineBasicBlock &MBB) {
   LivePhysRegs LPR;
   MBB.clearLiveIns();
   computeAndAddLiveIns(LPR, MBB);
 }
 
 } // end namespace llvm
 
 #endif // LLVM_CODEGEN_LIVEPHYSREGS_H

lib/CodeGen/LivePhysRegs.cpp

void llvm::recomputeLivenessFlags(MachineBasicBlock &MBB) {
   }
 }
 
 void llvm::computeAndAddLiveIns(LivePhysRegs &LiveRegs,
                                 MachineBasicBlock &MBB) {
   computeLiveIns(LiveRegs, MBB);
   addLiveIns(MBB, LiveRegs);
 }
+
+void llvm::computeAndAddLiveIns(MachineBasicBlock &MBB) {
+  LivePhysRegs LPR;
+  computeAndAddLiveIns(LPR, MBB);
+}

lib/Target/ARM/ARMISelLowering.cpp

exitMBB->splice(exitMBB->begin(), BB,
                   std::next(MachineBasicBlock::iterator(MI)), BB->end());
   exitMBB->transferSuccessorsAndUpdatePHIs(BB);
 
   // 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)
         .add(predOps(ARMCC::AL));
 
     if ((LoopSize & 0xFFFF0000) != 0)
       BuildMI(BB, dl, TII->get(IsThumb ? ARM::t2MOVTi16 : ARM::MOVTi16), varEnd)
           .addReg(Vtmp)
           .addImm(LoopSize >> 16)
emitPostLd(BB, StartOfExit, TII, dl, 1, scratch, srcIn, srcOut,
                IsThumb1, IsThumb2);
     emitPostSt(BB, StartOfExit, TII, dl, 1, scratch, destIn, destOut,
                IsThumb1, IsThumb2);
     srcIn = srcOut;
     destIn = destOut;
   }
 
   MI.eraseFromParent(); // The instruction is gone now.
+  computeAndAddLiveIns(*exitMBB);
   return BB;
 }
 
 MachineBasicBlock *
 ARMTargetLowering::EmitLowered__chkstk(MachineInstr &MI,
                                        MachineBasicBlock *MBB) const {
   const TargetMachine &TM = getTargetMachine();
   const TargetInstrInfo &TII = *Subtarget->getInstrInfo();
BuildMI(*MBB, MI, DL, TII->get(ARM::tCMPi8))
       .addImm(0)
       .add(predOps(ARMCC::AL));
   BuildMI(*MBB, MI, DL, TII->get(ARM::t2Bcc))
       .addMBB(TrapBB)
       .addImm(ARMCC::EQ)
       .addReg(ARM::CPSR);
 
   MI.eraseFromParent();
+  computeAndAddLiveIns(*ContBB);
   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: {
     //   fallthrough --> copy0MBB
     MachineBasicBlock *thisMBB  = BB;
     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);
 
     BB->addSuccessor(copy0MBB);
     BB->addSuccessor(sinkMBB);
 
case ARM::tMOVCCr_pseudo: {
     BB = sinkMBB;
     BuildMI(*BB, BB->begin(), dl, TII->get(ARM::PHI), MI.getOperand(0).getReg())
         .addReg(MI.getOperand(1).getReg())
         .addMBB(copy0MBB)
         .addReg(MI.getOperand(2).getReg())
         .addMBB(thisMBB);
 
     MI.eraseFromParent(); // The pseudo instruction is gone now.
+    computeAndAddLiveIns(*sinkMBB);
+    computeAndAddLiveIns(*copy0MBB);
     return BB;
   }
 
   case ARM::BCCi64:
   case ARM::BCCZi64: {
     // If there is an unconditional branch to the other successor, remove it.
     BB->erase(std::next(MachineBasicBlock::iterator(MI)), BB->end());
 

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

+# RUN: llc -mtriple=thumbv7-unknown-windows-itanium -run-pass=expand-isel-pseudos %s -o - | FileCheck %s
+--- |
+  target triple = "thumbv7-unknown-windows-itanium"
+
+  @r = common global i32 0, align 4
+  @c = common global i32 0, align 4
+
+  define arm_aapcs_vfpcc i32 @test1(i32 %n, i32 %d) {
+  entry:
+    %retval = alloca i32, align 4
+    %n.addr = alloca i32, align 4
+    %d.addr = alloca i32, align 4
+    store i32 %n, i32* %n.addr, align 4
+    store i32 %d, i32* %d.addr, align 4
+    %0 = load i32, i32* %n.addr, align 4
+    %1 = load i32, i32* %d.addr, align 4
+    %div = sdiv i32 %0, %1
+    %tobool = icmp ne i32 %div, 0
+    br i1 %tobool, label %if.then, label %if.end
+
+  if.then:                                          ; preds = %entry
+    store i32 1, i32* %retval, align 4
+    br label %return
+
+  if.end:                                           ; preds = %entry
+    store i32 0, i32* %retval, align 4
+    br label %return
+
+  return:                                           ; preds = %if.end, %if.then
+    %2 = load i32, i32* %retval, align 4
+    ret i32 %2
+  }
+
+...
+---
+name:            test1
+alignment:       1
+tracksRegLiveness: true
+hasWinCFI:       false
+registers:
+  - { id: 0, class: gpr, preferred-register: '' }
+  - { id: 1, class: tgpr, preferred-register: '' }
+  - { id: 2, class: gprnopc, preferred-register: '' }
+  - { id: 3, class: rgpr, preferred-register: '' }
+  - { id: 4, class: rgpr, preferred-register: '' }
+  - { id: 5, class: gpr, preferred-register: '' }
+liveins:
+  - { reg: '$r0', virtual-reg: '%0' }
+  - { reg: '$r1', virtual-reg: '%1' }
+frameInfo:
+  adjustsStack:    true
+  hasCalls:        true
+fixedStack:      []
+stack:
+  - { id: 0, name: retval, type: default, offset: 0, size: 4, alignment: 4,
+      stack-id: 0, callee-saved-register: '', callee-saved-restored: true,
+      debug-info-variable: '', debug-info-expression: '', debug-info-location: '' }
+  - { id: 1, name: n.addr, type: default, offset: 0, size: 4, alignment: 4,
+      stack-id: 0, callee-saved-register: '', callee-saved-restored: true,
+      debug-info-variable: '', debug-info-expression: '', debug-info-location: '' }
+  - { id: 2, name: d.addr, type: default, offset: 0, size: 4, alignment: 4,
+      stack-id: 0, callee-saved-register: '', callee-saved-restored: true,
+      debug-info-variable: '', debug-info-expression: '', debug-info-location: '' }
+constants:       []
+body:             |
+  bb.0.entry:
+    successors: %bb.1(0x50000000), %bb.2(0x30000000)
+    liveins: $r0, $r1
+
+    %1:tgpr = COPY $r1
+    %0:gpr = COPY $r0
+    t2STRi12 %1, %stack.2.d.addr, 0, 14, $noreg :: (store 4 into %ir.d.addr)
+    WIN__DBZCHK %1, implicit-def dead $cpsr
+    t2STRi12 %0, %stack.1.n.addr, 0, 14, $noreg :: (store 4 into %ir.n.addr)
+    ADJCALLSTACKDOWN 0, 0, 14, $noreg, implicit-def dead $sp, implicit $sp
+    tBL 14, $noreg, &__rt_sdiv, csr_aapcs, implicit-def dead $lr, implicit $sp, implicit $r0, implicit $r1, implicit-def $sp, implicit-def $r0
+    ADJCALLSTACKUP 0, 0, 14, $noreg, implicit-def dead $sp, implicit $sp
+    %2:gprnopc = COPY $r0
+    t2CMPri %2, 0, 14, $noreg, implicit-def $cpsr
+    t2Bcc %bb.2, 0, $cpsr
+    t2B %bb.1, 14, $noreg
+
+  bb.1.if.then:
+    successors: %bb.3(0x80000000)
+
+    %4:rgpr = t2MOVi 1, 14, $noreg, $noreg
+    t2STRi12 killed %4, %stack.0.retval, 0, 14, $noreg :: (store 4 into %ir.retval)
+    t2B %bb.3, 14, $noreg
+
+  bb.2.if.end:
+    successors: %bb.3(0x80000000)
+
+    %3:rgpr = t2MOVi 0, 14, $noreg, $noreg
+    t2STRi12 killed %3, %stack.0.retval, 0, 14, $noreg :: (store 4 into %ir.retval)
+
+  bb.3.return:
+    %5:gpr = t2LDRi12 %stack.0.retval, 0, 14, $noreg :: (dereferenceable load 4 from %ir.retval)
+    $r0 = COPY %5
+    tBX_RET 14, $noreg, implicit $r0
+
+...
+# CHECK-LABEL: name: test1
+# CHECK-LABEL: bb.4:
+# CHECK-NEXT: successors:
+# CHECK-NEXT: liveins: $r1, $r0

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

+# Check liveins are properly setwhen new MBBs are created in
+# expand-isel-pseudos.
+
+# RUN: llc -run-pass=expand-isel-pseudos %s -o - | FileCheck %s
+--- |
+  target triple = "thumb-unknown-unknown-eabi"
+
+  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: $r1
+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: '' }
+liveins:
+  - { reg: '$r0', virtual-reg: '%0' }
+  - { reg: '$r1', virtual-reg: '%1' }
+body:             |
+  bb.0.entry:
+    liveins: $r0, $r1
+    %0:gpr = COPY $r1
+    ADJCALLSTACKDOWN 136, 0, 14, $noreg, implicit-def dead $sp, implicit $sp
+    %1:gpr = COPY $sp
+    %2:gpr = COPY $r0
+    COPY_STRUCT_BYVAL_I32 %2, %0, 72, 8
+    COPY_STRUCT_BYVAL_I32 %2, %0, 72, 8
+    %3:gpr = COPY $r1
+    STRi12 killed %3, %1, 132, 14, $noreg :: (store 4 into stack + 132)
+    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
+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: '' }
+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, killed %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
+    tBX_RET 14, $noreg, implicit $r0, implicit $r1
+
+...