RegScavenging: Add scavengeRegisterBackwards()

Re-apply r276044/r279124/r305516. Fixed a problem where we would refuse
to place spills as the very first instruciton of a basic block and thus
artifically increase pressure (test in
test/CodeGen/PowerPC/scavenging.mir:spill_at_begin)

This is a variant of scavengeRegister() that works for
enterBasicBlockEnd()/backward(). The benefit of the backward mode is
that it is not affected by incomplete kill flags.

This patch also changes
PrologEpilogInserter::doScavengeFrameVirtualRegs() to use the register
scavenger in backwards mode.

Differential Revision: http://reviews.llvm.org/D21885

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@305625 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 62 insertions, 5 deletions

diff --git a/test/CodeGen/PowerPC/scavenging.mir b/test/CodeGen/PowerPC/scavenging.mir
index 8b5c26230bc..a72aaa443a0 100644
--- a/test/CodeGen/PowerPC/scavenging.mir
+++ b/test/CodeGen/PowerPC/scavenging.mir
@@ -6,7 +6,7 @@ tracksRegLiveness: true
 body: |
   bb.0:
     ; CHECK: [[REG0:%r[0-9]+]] = LI 42
-    ; CHECK-NEXT: NOP implicit [[REG0]]
+    ; CHECK-NEXT: NOP implicit killed [[REG0]]
     %0 : gprc = LI 42
     NOP implicit %0
 
@@ -14,7 +14,7 @@ body: |
     ; CHECK-NEXT: NOP
     ; CHECK-NEXT: NOP implicit [[REG1]]
     ; CHECK-NEXT: NOP
-    ; CHECK-NEXT: NOP implicit [[REG1]]
+    ; CHECK-NEXT: NOP implicit killed [[REG1]]
     %1 : gprc = LI 42
     NOP
     NOP implicit %1
@@ -48,8 +48,8 @@ body: |
     ; CHECK-NOT: %x30 = LI 42
     ; CHECK: [[REG3:%r[0-9]+]] = LI 42
     ; CHECK-NEXT: %x5 = IMPLICIT_DEF
-    ; CHECK-NEXT: NOP implicit [[REG2]]
-    ; CHECK-NEXT: NOP implicit [[REG3]]
+    ; CHECK-NEXT: NOP implicit killed [[REG2]]
+    ; CHECK-NEXT: NOP implicit killed [[REG3]]
     %3 : gprc = LI 42
     %x5 = IMPLICIT_DEF
     NOP implicit %2
@@ -110,7 +110,7 @@ body: |
 
     ; CHECK: STD killed [[SPILLEDREG:%x[0-9]+]]
     ; CHECK: [[SPILLEDREG]] = LI8 42
-    ; CHECK: NOP implicit [[SPILLEDREG]]
+    ; CHECK: NOP implicit killed [[SPILLEDREG]]
     ; CHECK: [[SPILLEDREG]] = LD
     %0 : g8rc = LI8 42
     NOP implicit %0
@@ -147,3 +147,60 @@ body: |
     NOP implicit %x29
     NOP implicit %x30
 ...
+---
+# Check for bug where we would refuse to spill before the first instruction in a
+# block.
+# CHECK-LABEL: name: spill_at_begin
+# CHECK: bb.0:
+# CHECK: liveins:
+# CHECK: STD killed [[REG:%x[0-9]+]]{{.*}}(store 8 into %stack.{{[0-9]+}})
+# CHECK: [[REG]] = LIS8 0
+# CHECK: [[REG]] = ORI8 killed [[REG]], 48
+# CHECK: NOP implicit killed [[REG]]
+# CHEKC: [[REG]] = LD{{.*}}(load 8 from %stack.{{[0-9]+}})
+name: spill_at_begin
+tracksRegLiveness: true
+stack:
+  # variable-sized object should be a reason to reserve an emergency spillslot
+  # in the RegScavenger
+  - { id: 0, type: variable-sized, offset: -32, alignment: 1 }
+body: |
+  bb.0:
+    liveins: %x0, %x1, %x2, %x3, %x4, %x5, %x6, %x7, %x8, %x9, %x10, %x11, %x12, %x13, %x14, %x15, %x16, %x17, %x18, %x19, %x20, %x21, %x22, %x23, %x24, %x25, %x26, %x27, %x28, %x29, %x30, %x31
+    %0 : g8rc = LIS8 0
+    %1 : g8rc = ORI8 %0, 48
+    NOP implicit %1
+
+    NOP implicit %x0
+    NOP implicit %x1
+    NOP implicit %x2
+    NOP implicit %x3
+    NOP implicit %x4
+    NOP implicit %x5
+    NOP implicit %x6
+    NOP implicit %x7
+    NOP implicit %x8
+    NOP implicit %x9
+    NOP implicit %x10
+    NOP implicit %x11
+    NOP implicit %x12
+    NOP implicit %x13
+    NOP implicit %x14
+    NOP implicit %x15
+    NOP implicit %x16
+    NOP implicit %x17
+    NOP implicit %x18
+    NOP implicit %x19
+    NOP implicit %x20
+    NOP implicit %x21
+    NOP implicit %x22
+    NOP implicit %x23
+    NOP implicit %x24
+    NOP implicit %x25
+    NOP implicit %x26
+    NOP implicit %x27
+    NOP implicit %x28
+    NOP implicit %x29
+    NOP implicit %x30
+    NOP implicit %x31
+...