RegisterCoalescer: Fix joinReservedPhysReg()

[MatzeB]

Summary

• Some code cleanup
• Fix incorrect handling of early clobber definitions
• Allow multiple vreg uses

[kparzysz]

lib/CodeGen/RegisterCoalescer.cpp

1845

I think starting from the next index is somewhat dangerous. Consider this scenario: Hexagon has an instruction "J4_jumpsetr Rd, Rs, #bb", which is equivalent to "Rd = Rs; jump #bb". This one will not cause a problem here, but it inspired me to invent a new hypothetical instruction where the branch is indirect: "J4_jumprsetr Rd, Rs, Rt", defined as "Rd = Rs; jumpr Rt".

I converted the testcase to Hexagon (use R30 instead of FP), with the change that it now uses the invented instruction to define virtual register: "J4_jumprsetr %0, R0, R30". Before coalescing, this would be equivalent to "%0 = R0; jumpr R30", after coalescing it becomes "R30 = R0; jumpr R30". While with the Hexagon semantics the R30 in the target of the branch would still be the old value, I'm not sure that this can be said about any potential architecture (which would support this kind of instructions). Reserved physical registers may not obey the same use/def ordering, and there is no guarantee that the branch to R30 above would not be redirected to the newly defined value (or that is still a legal instruction to begin with).

Here's the modified testcase:

# RUN: llc -mtriple=hexagon -run-pass=simple-register-coalescing %s -o - | FileCheck %s
--- |
  define void @func1() { ret void }
...
---
name: func1
body: |
  bb.0:
    successors: %bb.3, %bb.4
    J2_jumpt undef %p0, %bb.3, implicit def %pc
    J2_jump %bb.4, implicit-def %pc

  bb.1:
    successors: %bb.2, %bb.5
    %r30 = COPY %0
    J2_jumpt undef %p0, %bb.2, implicit-def %pc
    J2_jump %bb.5, implicit-def %pc

  bb.2:
    successors: %bb.6
    %r30 = COPY %r0; outside the lifetime of %0, so shouldn't matter
    J2_jump %bb.6, implicit-def %pc

  bb.3:
    %r0 = COPY %r30 ; outside the lifetime of %0, so shouldn't matter
    J2_jumpr %r31, implicit-def %pc

  bb.5:
    S2_storeri_io %r30, 0, %r30
    J2_jumpr %r31, implicit-def %pc

  bb.6:
    J2_jumpr %r31, implicit-def %pc

  bb.4:
    successors: %bb.1
    %0 : intregs = J4_jumprsetr %r0, %r30, implicit-def %pc
...

You'd need to add a definition of it to the Hexagon target for the testcase to work, but you can change the testcase to use J4_jumpsetr (no "r" in the middle) to still get an instruction that uses R30.

Here's the output:

********** SIMPLE REGISTER COALESCING **********
********** Function: func1
********** JOINING INTERVALS ***********
(null):
64B     %R30<def> = COPY %vreg0; IntRegs:%vreg0
        Considering merging %vreg0 with %R30
                RHS = %vreg0 [48B,64r:0)[304r,320B:0)  0@304r
                Removing phys reg def of %R30 at 64B
                updated: 304B   %R30<def> = J4_jumprsetr %R0, %R30, %PC<imp-def>
        Success: %vreg0 -> %R30
        Result = %R30
(null):
(null):
128B    %R30<def> = COPY %R0
        Not coalescable.
(null):
(null):
176B    %R0<def> = COPY %R30
        Not coalescable.
(null):
(null):
Trying to inflate 0 regs.

and we end up with

288B    BB#6:
            Predecessors according to CFG: BB#0
304B            %R30<def> = J4_jumprsetr %R0, %R30, %PC<imp-def>
            Successors according to CFG: BB#1(0x80000000 / 0x80000000 = 100.00%)

[MatzeB]

lib/CodeGen/RegisterCoalescer.cpp

1845

Sorry, I am getting confused here. For my understand: Your concern is about the defining instruction of the virtual register. You think of "R30 = R0; jumpr R30" as execution in parallel (VLIW style). IN terms of register allocation/semantics this would be: read R0 and R30, the execute the two instructions; then write R30? That would match the semantics we model in our liveranges. If this is not the case we would need to set the definition to the earlyclobber register slot. You are right that this case is not handled correctly in the patch right now. I'll update.

[MatzeB]

Addressed Krzysztofs comments. I will try to extend the tests for those sneaky corner cases tomorrow.

[MatzeB]

I will try to update the tests tomorrow. BTW: For testing regalloc infrastructure I found that you do not need to invent new instructions, just take an existing one (like NOP) and add implicit def and use operands in your .mir test case :)

[MatzeB]

Add tests for early-clobber corner cases.

[kparzysz]

lib/CodeGen/RegisterCoalescer.cpp

1845

Yes, although I missed the earlyclobber solution (I was thinking about the concept of "late use" and the earlyclobber flag eluded me here).

[wmi]

Sorry to chime in late.

test/CodeGen/AArch64/regcoal-physreg.mir

116–123

If bb.4 has another successor to bb.5, after %0 = ADRP 0 is changed to %fp = ADRP 0, it may change the value of %fp in bb.5. So the original check that the def of physical register has no overlap with the interval of SrcReg is not enough in the case of complex control flow?

bb.4:
  successors: %bb.1(0x40000000), %bb.5(0x40000000)

  %fp = COPY %x3
  %0 : gpr64 = ADRP 0
  CBZX undef %x0, %bb.5
  B %bb.1

bb.5:
  STRXui %fp, %fp, 0
  RET_ReallyLR

[MatzeB]

Good catch Wei! Looks like the only sensible way to fix this today is to require the liverange to be whithin a single basic block.

I put this simple fix into a different review: https://reviews.llvm.org/D29436 that we can hopefully pick into the llvm 4.0 branch.
I will update this review as a followup patch to D29436 as it has grown some interesting features like proper support for earlyclobber defs and multiple uses of the vreg and some code cleanups (they are however not critical enough that they must go into the 4.0 branch).

[MatzeB]

Addressed review comments. Note that I put the fix of the original problem into D29611 now.

lib/CodeGen/RegisterCoalescer.cpp

class RegisterCoalescer : public MachineFunctionPass,
     /// was successfully coalesced away. If it is not currently possible to
     /// coalesce this interval, but it may be possible if other things get
     /// coalesced, then it returns true by reference in 'Again'.
     bool joinCopy(MachineInstr *TheCopy, bool &Again);
 
     /// Attempt to join these two intervals.  On failure, this
     /// returns false.  The output "SrcInt" will not have been modified, so we
     /// can use this information below to update aliases.
-    bool joinIntervals(CoalescerPair &CP);
+    bool joinIntervals(CoalescerPair &CP, MachineInstr &CopyMI);
 
     /// Attempt joining two virtual registers. Return true on success.
     bool joinVirtRegs(CoalescerPair &CP);
 
     /// Attempt joining with a reserved physreg.
-    bool joinReservedPhysReg(CoalescerPair &CP);
+    bool joinReservedPhysReg(CoalescerPair &CP, MachineInstr &CopyMI);
 
     /// Add the LiveRange @p ToMerge as a subregister liverange of @p LI.
     /// Subranges in @p LI which only partially interfere with the desired
     /// LaneMask are split as necessary. @p LaneMask are the lanes that
     /// @p ToMerge will occupy in the coalescer register. @p LI has its subrange
     /// lanemasks already adjusted to the coalesced register.
     void mergeSubRangeInto(LiveInterval &LI, const LiveRange &ToMerge,
                            LaneBitmask LaneMask, CoalescerPair &CP);
bool RegisterCoalescer::joinCopy(MachineInstr *CopyMI, bool &Again) {
 
   ShrinkMask = LaneBitmask::getNone();
   ShrinkMainRange = false;
 
   // Okay, attempt to join these two intervals.  On failure, this returns false.
   // Otherwise, if one of the intervals being joined is a physreg, this method
   // always canonicalizes DstInt to be it.  The output "SrcInt" will not have
   // been modified, so we can use this information below to update aliases.
-  if (!joinIntervals(CP)) {
+  if (!joinIntervals(CP, *CopyMI)) {
     // Coalescing failed.
 
     // If definition of source is defined by trivial computation, try
     // rematerializing it.
     bool IsDefCopy;
     if (reMaterializeTrivialDef(CP, CopyMI, IsDefCopy))
       return true;
 
else
       dbgs() << LIS->getInterval(CP.getDstReg());
     dbgs() << '\n';
   });
 
   ++numJoins;
   return true;
 }
 
-bool RegisterCoalescer::joinReservedPhysReg(CoalescerPair &CP) {
+bool RegisterCoalescer::joinReservedPhysReg(CoalescerPair &CP,
+                                            MachineInstr &CopyMI) {
   unsigned DstReg = CP.getDstReg();
   unsigned SrcReg = CP.getSrcReg();
   assert(CP.isPhys() && "Must be a physreg copy");
   assert(MRI->isReserved(DstReg) && "Not a reserved register");
   LiveInterval &RHS = LIS->getInterval(SrcReg);
   DEBUG(dbgs() << "\t\tRHS = " << RHS << '\n');
 
-  assert(RHS.containsOneValue() && "Invalid join with reserved register");
+  if (!MRI->hasOneDef(SrcReg))
+    return false;
 
   // Optimization for reserved registers like ESP. We can only merge with a
   // reserved physreg if RHS has a single value that is a copy of DstReg.
   // The live range of the reserved register will look like a set of dead defs
   // - we don't properly track the live range of reserved registers.
 
   // Deny any overlapping intervals.  This depends on all the reserved
   // register live ranges to look like dead defs.
if (!MRI->isConstantPhysReg(DstReg)) {
     }
   }
 
   // Skip any value computations, we are not adding new values to the
   // reserved register.  Also skip merging the live ranges, the reserved
   // register live range doesn't need to be accurate as long as all the
   // defs are there.
 
-  // Delete the identity copy.
-  MachineInstr *CopyMI;
   if (CP.isFlipped()) {
     // Physreg is copied into vreg
     //   %vregY = COPY %X
     //   ...  //< no other def of %X here
     //   use %vregY
     // =>
     //   ...
     //   use %X
-    CopyMI = MRI->getVRegDef(SrcReg);
+
+    // We already tested for definitions of DstReg above.
   } else {
     // VReg is copied into physreg:
     //   %vregX = def
     //   ... //< no other def or use of %Y here
     //   %Y = COPY %vregX
     // =>
     //   %Y = def
     //   ...
-    if (!MRI->hasOneNonDBGUse(SrcReg)) {
-      DEBUG(dbgs() << "\t\tMultiple vreg uses!\n");
-      return false;
-    }
+    const MachineOperand &DefMO = *MRI->def_begin(SrcReg);
+    const MachineInstr &DestMI = *DefMO.getParent();
+    SlotIndex DestRegIdx =
+      LIS->getInstructionIndex(DestMI).getRegSlot(DefMO.isEarlyClobber());
+    SlotIndex CopyIdx = LIS->getInstructionIndex(CopyMI).getRegSlot();
 
-    if (!LIS->intervalIsInOneMBB(RHS)) {
-      DEBUG(dbgs() << "\t\tComplex control flow!\n");
+    if (!MRI->isConstantPhysReg(DstReg)) {
+      // We do not track exact physreg liveranges so this is only valid within
+      // a basic block. Otherwise we may miss reads on other CFG paths.
+      if (!LIS->intervalIsInOneMBB(RHS))
         return false;
-    }
 
-    MachineInstr &DestMI = *MRI->getVRegDef(SrcReg);
-    CopyMI = &*MRI->use_instr_nodbg_begin(SrcReg);
-    SlotIndex CopyRegIdx = LIS->getInstructionIndex(*CopyMI).getRegSlot();
-    SlotIndex DestRegIdx = LIS->getInstructionIndex(DestMI).getRegSlot();
+      assert(RHS.size() == 1 && "Liverange must be a single segment");
 
-    if (!MRI->isConstantPhysReg(DstReg)) {
       // We checked above that there are no interfering defs of the physical
       // register. However, for this case, where we intent to move up the def of
-      // the physical register, we also need to check for interfering uses.
-      SlotIndexes *Indexes = LIS->getSlotIndexes();
-      for (SlotIndex SI = Indexes->getNextNonNullIndex(DestRegIdx);
-           SI != CopyRegIdx; SI = Indexes->getNextNonNullIndex(SI)) {
-        MachineInstr *MI = LIS->getInstructionFromIndex(SI);
-        if (MI->readsRegister(DstReg, TRI)) {
-          DEBUG(dbgs() << "\t\tInterference (read): " << *MI);
+      // the physical register, we also need to check that there are no uses
+      // of DstReg during the lifetime of SrcReg.
+      SlotIndexes &Indexes = *LIS->getSlotIndexes();
+      // Check instructions after the definition, for early clobber defs even
+      // the defining instruction.
+      const LiveRange::Segment &S = *RHS.begin();
+      SlotIndex Start =
+        DefMO.isEarlyClobber() ? S.start : Indexes.getNextNonNullIndex(S.start);
+
+      assert(Start <= CopyIdx && CopyIdx <= S.end && "valid segment");
+
+      // Check instructions in range for uses of DstReg.
+      for (SlotIndex SI = Start; SI < CopyIdx;
+           SI = Indexes.getNextNonNullIndex(SI)) {
+        MachineInstr &MI = *LIS->getInstructionFromIndex(SI);
+        if (MI.readsRegister(DstReg, TRI)) {
+          DEBUG(dbgs() << "\t\tInterference (read): " << MI);
           return false;
         }
       }
     }
 
     // We're going to remove the copy which defines a physical reserved
     // register, so remove its valno, etc.
     DEBUG(dbgs() << "\t\tRemoving phys reg def of " << PrintReg(DstReg, TRI)
-          << " at " << CopyRegIdx << "\n");
+          << " at " << CopyIdx << "\n");
 
-    LIS->removePhysRegDefAt(DstReg, CopyRegIdx);
+    LIS->removePhysRegDefAt(DstReg, CopyIdx);
     // Create a new dead def at the new def location.
     for (MCRegUnitIterator UI(DstReg, TRI); UI.isValid(); ++UI) {
       LiveRange &LR = LIS->getRegUnit(*UI);
       LR.createDeadDef(DestRegIdx, LIS->getVNInfoAllocator());
     }
   }
 
-  LIS->RemoveMachineInstrFromMaps(*CopyMI);
-  CopyMI->eraseFromParent();
+  // Delete the identity copy.
+  LIS->RemoveMachineInstrFromMaps(CopyMI);
+  CopyMI.eraseFromParent();
 
   // We don't track kills for reserved registers.
   MRI->clearKillFlags(CP.getSrcReg());
 
   return true;
 }
 
 //===----------------------------------------------------------------------===//
DEBUG({
       dbgs() << ":  " << LHS << '\n';
     });
     LIS->extendToIndices((LiveRange&)LHS, EndPoints);
   }
 
   return true;
 }
 
-bool RegisterCoalescer::joinIntervals(CoalescerPair &CP) {
-  return CP.isPhys() ? joinReservedPhysReg(CP) : joinVirtRegs(CP);
+bool RegisterCoalescer::joinIntervals(CoalescerPair &CP, MachineInstr &CopyMI) {
+  return CP.isPhys() ? joinReservedPhysReg(CP, CopyMI) : joinVirtRegs(CP);
 }
 
 namespace {
 /// Information concerning MBB coalescing priority.
 struct MBBPriorityInfo {
   MachineBasicBlock *MBB;
   unsigned Depth;
   bool IsSplit;

test/CodeGen/AArch64/regcoal-physreg.mir

bb.0:
     ; Cannot coalesce when there are reads of the physreg.
     ; CHECK-NOT: %fp = SUBXri %fp, 8, 0
     ; CHECK: %9 = SUBXri %fp, 8, 0
     ; CHECK: STRXui %fp, %fp, 0
     ; CHECK: %fp = COPY %9
     %9 : gpr64sp = SUBXri %fp, 8, 0
     STRXui %fp, %fp, 0
     %fp = COPY %9
+
+    ; Multiple uses should not stop coalescing.
+    ; CHECK: %fp = SUBXri %fp, 12, 0
+    ; CHECK: STRXui undef %x0, %fp, 0
+    ; CHECK-NOT: %p = COPY
+    %10 : gpr64sp = SUBXri %fp, 12, 0
+    STRXui undef %x0, %10, 0
+    %fp = COPY %10
+
+    ; Cannot coalesce when vreg definition is an earlyclobber slot and the
+    ; physreg is read in the same instruction.
+    ; CHECK-NOT: HINT 0, implicit %fp, implicit-def early-clobber %fp
+    ; CHECK: HINT 0, implicit %fp, implicit-def early-clobber %11
+    ; CHECK: %fp = COPY %11
+    HINT 0, implicit %fp, implicit-def early-clobber %11 : gpr64
+    %fp = COPY %11
 ...
 ---
 # Check coalescing of COPYs from reserved physregs.
 # CHECK-LABEL: name: func1
 name: func1
 body: |
   bb.0:
     successors: %bb.1, %bb.2
     ; Cannot coalesce physreg because we have reads on other CFG paths (we
     ; currently abort for any control flow)
     ; CHECK-NOT: %fp = SUBXri
     ; CHECK: %0 = SUBXri %fp, 12, 0
     ; CHECK: CBZX undef %x0, %bb.1
     ; CHECK: B %bb.2
     %0 : gpr64sp = SUBXri %fp, 12, 0
     CBZX undef %x0, %bb.1
     B %bb.2
 
   bb.1:
     %fp = COPY %0
     RET_ReallyLR
 
   bb.2:
     STRXui %fp, %fp, 0
     RET_ReallyLR
 ...
 ---

test/CodeGen/SPARC/2013-05-17-CallFrame.ll

 ; RUN: llc -march=sparc   < %s | FileCheck %s --check-prefix=V8
 ; RUN: llc -march=sparcv9 < %s | FileCheck %s --check-prefix=SPARC64
 
 ; V8-LABEL: variable_alloca_with_adj_call_stack
 ; V8:       save %sp, -96, %sp
 ; (this should ideally be doing "add 4+7; and -8", instead of
 ;  "add 7; and -8; add 8"; see comments in LowerDYNAMIC_STACKALLOC)
 ; V8:       add %i0, 7, %i0
 ; V8-NEXT:  and %i0, -8, %i0
 ; V8-NEXT:  add %i0, 8, %i0
-; V8-NEXT:  sub %sp, %i0, %i0
-; V8-NEXT:  add %i0, 96, %o0
+; V8-NEXT:  sub %sp, %i0, %sp
+; V8-NEXT:  add %sp, 96, %o0
 ; V8:       add %sp, -16, %sp
 ; V8:       call foo
 ; V8:       add %sp, 16, %sp
 
 ; SPARC64-LABEL: variable_alloca_with_adj_call_stack
 ; SPARC64:       save %sp, -128, %sp
 ; SPARC64:       add {{.+}}, 2175, %o0
 ; SPARC64:       add %sp, -80, %sp