Allow the RegisterCoalescer to remove copies to reserved registers

[hfinkel]

Summary

Hi everyone,

Please review this patch that allows the RegisterCoalescer to join "non-flipped" range pairs with a physical destination register. This allows the RegisterCoalescer to remove copies like this:

<vreg> = something (maybe a load, for example)
... (things that don't use PHYSREG)
PHYSREG = COPY <vreg>

(with all of the restrictions normally applied by the RegisterCoalescer: having compatible register classes, etc. )

Currently, RegisterCoalescer handles only the opposite case (copying *from* a physical register). I don't handle the problem fully here, but try to get the common case where there is only one use of <vreg> (the COPY).

One thing that is not clear to me: Do I need to do anything special to update the 'dead def' live range corresponding to the updated PHYSREG?

Once this functionality is committed, I'll commit a change to the PowerPC backend to make this pattern *very* common, and so it is important that the RegisterCoalescer can eliminate it when that's profitable.

Thanks again!

[qcolombet]

Hi Hal,

I am worry about the approach here.
With this approach, we are propagating constraints on the allocation problem that we cannot recover from. We cannot split physical register live-ranges. The bottom line is it may introduce more spilling or more expensive splitting.

I would suggest instead to extend the copy propagation pass to handle such cases, since at that time the allocation has all been done. IIRC the copy propagation pass is top down, but we may be able to add a bottom up pass that would catch this.

What do you think?

Cheers,
-Quentin

[hfinkel]

In D6978#108843, @qcolombet wrote:

Hi Hal,

I am worry about the approach here.
With this approach, we are propagating constraints on the allocation problem that we cannot recover from. We cannot split physical register live-ranges. The bottom line is it may introduce more spilling or more expensive splitting.

Good point. I was thinking about my motivating use case, where the physical register involved was reserved. In this case, removing the vreg makes the allocation problem strictly easier. Perhaps we should restrict to the case of a reserved physical register?

At least for that case, I'd like to do this before register allocation.

When I looked at our regression tests for where this changed something, it seems to pick up this case as well (on x86, rbp is reserved in that test case; on ARM, sp is reserved).

I would suggest instead to extend the copy propagation pass to handle such cases, since at that time the allocation has all been done. IIRC the copy propagation pass is top down, but we may be able to add a bottom up pass that would catch this.

I can certainly try that if you don't like my suggestion above.

Thanks again!

What do you think?

Cheers,
-Quentin

[qcolombet]

Perhaps we should restrict to the case of a reserved physical register?

Reserved registers are a different story and in that case, by all means, this is a good idea :).

I can certainly try that if you don't like my suggestion above.

I like your suggestion, the copy propagation improvement is just another angle of attack I was envisioning. It may be generally useful, but if we do not have motivating example, I would leave that for later.

Thanks,
-Quentin

[hfinkel]

In D6978#108879, @qcolombet wrote:

Perhaps we should restrict to the case of a reserved physical register?

Reserved registers are a different story and in that case, by all means, this is a good idea :).

Good, will do :)

One more thing, I had asked:

One thing that is not clear to me: Do I need to do anything special to update the 'dead def' live range corresponding to the updated PHYSREG?

Do you know if I need to do anything specific here, or will the register replacement code that already exists take care of this in a sufficient way?

Thanks again!

I can certainly try that if you don't like my suggestion above.

I like your suggestion, the copy propagation improvement is just another angle of attack I was envisioning. It may be generally useful, but if we do not have motivating example, I would leave that for later.

Thanks,
-Quentin

[qcolombet]

Do you know if I need to do anything specific here, or will the register replacement code that already exists take care of this in a sufficient way?

Ah sorry, I forgot to reply to this as I first pushed for the copy propagation :).
The existing register replacement code should handle this case just fine. Thought that may not be well tested :P.

Thanks,
Q.

[hfinkel]

In D6978#108887, @qcolombet wrote:

Do you know if I need to do anything specific here, or will the register replacement code that already exists take care of this in a sufficient way?

Ah sorry, I forgot to reply to this as I first pushed for the copy propagation :).
The existing register replacement code should handle this case just fine. Thought that may not be well tested :P.

Sounds good; we'll find out ;) -- Also, as it turns out, this entire thing only applies to reserved registers:

/// Return true if a copy involving a physreg should be joined.
bool RegisterCoalescer::canJoinPhys(const CoalescerPair &CP) {
  /// Always join simple intervals that are defined by a single copy from a
  /// reserved register. This doesn't increase register pressure, so it is
  /// always beneficial.
  if (!MRI->isReserved(CP.getDstReg())) {
    DEBUG(dbgs() << "\tCan only merge into reserved registers.\n");
    return false;
  }

  ...

So we're good as-is.

Thanks,
Q.

[hfinkel]

r226071, thanks!

lib/CodeGen/RegisterCoalescer.cpp

bool RegisterCoalescer::canJoinPhys(const CoalescerPair &CP) {
   /// reserved register. This doesn't increase register pressure, so it is
   /// always beneficial.
   if (!MRI->isReserved(CP.getDstReg())) {
     DEBUG(dbgs() << "\tCan only merge into reserved registers.\n");
     return false;
   }
 
   LiveInterval &JoinVInt = LIS->getInterval(CP.getSrcReg());
-  if (CP.isFlipped() && JoinVInt.containsOneValue())
+  if (JoinVInt.containsOneValue())
     return true;
 
-  DEBUG(dbgs() << "\tCannot join defs into reserved register.\n");
+  DEBUG(dbgs() << "\tCannot join complex intervals into reserved register.\n");
   return false;
 }
 
 /// Attempt to join intervals corresponding to SrcReg/DstReg,
 /// which are the src/dst of the copy instruction CopyMI.  This returns true
 /// if the copy 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'.

 
 /// Attempt joining with a reserved physreg.
 bool RegisterCoalescer::joinReservedPhysReg(CoalescerPair &CP) {
   assert(CP.isPhys() && "Must be a physreg copy");
   assert(MRI->isReserved(CP.getDstReg()) && "Not a reserved register");
   LiveInterval &RHS = LIS->getInterval(CP.getSrcReg());
   DEBUG(dbgs() << "\t\tRHS = " << RHS << '\n');
 
-  assert(CP.isFlipped() && RHS.containsOneValue() &&
-         "Invalid join with reserved register");
+  assert(RHS.containsOneValue() && "Invalid join with reserved register");
 
   // 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 CP.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.
   for (MCRegUnitIterator UI(CP.getDstReg(), TRI); UI.isValid(); ++UI)
     if (RHS.overlaps(LIS->getRegUnit(*UI))) {
       DEBUG(dbgs() << "\t\tInterference: " << PrintRegUnit(*UI, TRI) << '\n');
       return false;
     }
 
   // 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 = MRI->getVRegDef(RHS.reg);
+  MachineInstr *CopyMI;
+  if (CP.isFlipped()) {
+    CopyMI = MRI->getVRegDef(RHS.reg);
+  } else {
+    if (!MRI->hasOneNonDBGUse(RHS.reg)) {
+      DEBUG(dbgs() << "\t\tMultiple vreg uses\n");
+      return false;
+    }
+
+    CopyMI = &*MRI->use_instr_nodbg_begin(RHS.reg);
+  }
+  
   LIS->RemoveMachineInstrFromMaps(CopyMI);
   CopyMI->eraseFromParent();
 
   // We don't track kills for reserved registers.
   MRI->clearKillFlags(CP.getSrcReg());
 
   return true;
 }

test/CodeGen/ARM/dyn-stackalloc.ll

-; RUN: llc -mtriple=arm-eabi %s -o /dev/null
+; RUN: llc -mcpu=generic -mtriple=arm-eabi < %s | FileCheck %s
 
 %struct.comment = type { i8**, i32*, i32, i8* }
 %struct.info = type { i32, i32, i32, i32, i32, i32, i32, i8* }
 %struct.state = type { i32, %struct.info*, float**, i32, i32, i32, i32, i32, i32, i32, i32, i32, i64, i64, i64, i64, i64, i64, i8* }
 
 @str215 = external global [2 x i8]
 
 define void @t1(%struct.state* %v) {
+
+; Make sure we generate:
+;   sub sp, sp, r1
+; instead of:
+;   sub r1, sp, r1
+;   mov sp, r1
+
+; CHECK-LABEL: @t1
+; CHECK: bic [[REG1:r[0-9]+]],
+; CHECK-NOT: sub r{{[0-9]+}}, sp, [[REG1]]
+; CHECK: sub sp, sp, [[REG1]]
+
   %tmp6 = load i32* null
   %tmp8 = alloca float, i32 %tmp6
   store i32 1, i32* null
   br i1 false, label %bb123.preheader, label %return
 
 bb123.preheader:                                  ; preds = %0
   br i1 false, label %bb43, label %return
 

test/CodeGen/X86/2009-02-12-DebugInfoVLA.ll

 ; RUN: llc < %s
-; RUN: llc < %s -march=x86-64
+; RUN: llc < %s -march=x86-64 | FileCheck %s
 ; PR3538
 target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:128:128"
 target triple = "i386-apple-darwin9"
 define signext i8 @foo(i8* %s1) nounwind ssp {
+
+; Make sure we generate:
+;  movq -40(%rbp), %rsp
+; Instead of:
+;  movq -40(%rbp), %rax
+;  movq %rax, %rsp
+
+; CHECK-LABEL: @foo
+; CHECK: movq -40(%rbp), %rsp
+
 entry:
   %s1_addr = alloca i8*                           ; <i8**> [#uses=2]
   %retval = alloca i32                            ; <i32*> [#uses=2]
   %saved_stack.1 = alloca i8*                     ; <i8**> [#uses=2]
   %0 = alloca i32                                 ; <i32*> [#uses=2]
   %str.0 = alloca [0 x i8]*                       ; <[0 x i8]**> [#uses=3]
   %1 = alloca i64                                 ; <i64*> [#uses=2]
   %2 = alloca i64                                 ; <i64*> [#uses=1]