[FastISel] Sink local value materializations to first use

Summary:
Local values are constants, global addresses, and stack addresses that
can't be folded into the instruction that uses them. For example, when
storing the address of a global variable into memory, we need to
materialize that address into a register.

FastISel doesn't want to materialize any given local value more than
once, so it generates all local value materialization code at
EmitStartPt, which always dominates the current insertion point. This
allows it to maintain a map of local value registers, and it knows that
the local value area will always dominate the current insertion point.

The downside is that local value instructions are always emitted without
a source location. This is done to prevent jumpy line tables, but it
means that the local value area will be considered part of the previous
statement. Consider this C code:
  call1();      // line 1
  ++global;     // line 2
  ++global;     // line 3
  call2(&global, &local); // line 4

Today we end up with assembly and line tables like this:
  .loc 1 1
  callq call1
  leaq global(%rip), %rdi
  leaq local(%rsp), %rsi
  .loc 1 2
  addq $1, global(%rip)
  .loc 1 3
  addq $1, global(%rip)
  .loc 1 4
  callq call2

The LEA instructions in the local value area have no source location and
are treated as being on line 1. Stepping through the code in a debugger
and correlating it with the assembly won't make much sense, because
these materializations are only required for line 4.

This is actually problematic for the VS debugger "set next statement"
feature, which effectively assumes that there are no registers live
across statement boundaries. By sinking the local value code into the
statement and fixing up the source location, we can make that feature
work. This was filed as https://bugs.llvm.org/show_bug.cgi?id=35975 and
https://crbug.com/793819.

This change is obviously not enough to make this feature work reliably
in all cases, but I felt that it was worth doing anyway because it
usually generates smaller, more comprehensible -O0 code. I measured a
0.12% regression in code generation time with LLC on the sqlite3
amalgamation, so I think this is worth doing.

There are some special cases worth calling out in the commit message:
1. local values materialized for phis
2. local values used by no-op casts
3. dead local value code

Local values can be materialized for phis, and this does not show up as
a vreg use in MachineRegisterInfo. In this case, if there are no other
uses, this patch sinks the value to the first terminator, EH label, or
the end of the BB if nothing else exists.

Local values may also be used by no-op casts, which adds the register to
the RegFixups table. Without reversing the RegFixups map direction, we
don't have enough information to sink these instructions.

Lastly, if the local value register has no other uses, we can delete it.
This comes up when fastisel tries two instruction selection approaches
and the first materializes the value but fails and the second succeeds
without using the local value.

Reviewers: aprantl, dblaikie, qcolombet, MatzeB, vsk, echristo

Subscribers: dotdash, chandlerc, hans, sdardis, amccarth, javed.absar, zturner, llvm-commits, hiraditya

Differential Revision: https://reviews.llvm.org/D43093

llvm-svn: 327581

5 files changed, 77 insertions, 77 deletions

diff --git a/llvm/test/CodeGen/ARM/fast-isel-call.ll b/llvm/test/CodeGen/ARM/fast-isel-call.ll
index 1122867356b..61467a477ca 100644
--- a/llvm/test/CodeGen/ARM/fast-isel-call.ll
+++ b/llvm/test/CodeGen/ARM/fast-isel-call.ll
@@ -95,51 +95,54 @@ declare zeroext i1 @t9();
 define i32 @t10() {
 entry:
 ; ARM: @t10
-; ARM: movw [[R0:l?r[0-9]*]], #0
-; ARM: movw [[R1:l?r[0-9]*]], #248
-; ARM: movw [[R2:l?r[0-9]*]], #187
-; ARM: movw [[R3:l?r[0-9]*]], #28
-; ARM: movw [[R4:l?r[0-9]*]], #40
-; ARM: movw [[R5:l?r[0-9]*]], #186
-; ARM: and [[R0]], [[R0]], #255
-; ARM: and [[R1]], [[R1]], #255
-; ARM: and [[R2]], [[R2]], #255
-; ARM: and [[R3]], [[R3]], #255
-; ARM: and [[R4]], [[R4]], #255
-; ARM: str [[R4]], [sp]
-; ARM: and [[R4]], [[R5]], #255
-; ARM: str [[R4]], [sp, #4]
+; ARM-DAG: movw [[R0:l?r[0-9]*]], #0
+; ARM-DAG: movw [[R1:l?r[0-9]*]], #248
+; ARM-DAG: movw [[R2:l?r[0-9]*]], #187
+; ARM-DAG: movw [[R3:l?r[0-9]*]], #28
+; ARM-DAG: movw [[R4:l?r[0-9]*]], #40
+; ARM-DAG: movw [[R5:l?r[0-9]*]], #186
+; ARM-DAG: and [[R0]], [[R0]], #255
+; ARM-DAG: and [[R1]], [[R1]], #255
+; ARM-DAG: and [[R2]], [[R2]], #255
+; ARM-DAG: and [[R3]], [[R3]], #255
+; ARM-DAG: and [[R4]], [[R4]], #255
+; ARM-DAG: str [[R4]], [sp]
+; ARM-DAG: and [[R4]], [[R5]], #255
+; ARM-DAG: str [[R4]], [sp, #4]
 ; ARM: bl {{_?}}bar
-; ARM-LONG: @t10
+; ARM-LONG-LABEL: @t10
 
 ; ARM-LONG-MACHO: {{(movw)|(ldr)}} [[R:l?r[0-9]*]], {{(:lower16:L_bar\$non_lazy_ptr)|(.LCPI)}}
 ; ARM-LONG-MACHO: {{(movt [[R]], :upper16:L_bar\$non_lazy_ptr)?}}
-; ARM-LONG-MACHO: ldr [[R]], {{\[}}[[R]]{{\]}}
+; ARM-LONG-MACHO: str     [[R]], [r7, [[SLOT:#[-0-9]+]]]           @ 4-byte Spill
+; ARM-LONG-MACHO: ldr     [[R:l?r[0-9]*]], [r7, [[SLOT]]]           @ 4-byte Reload
 
 ; ARM-LONG-ELF: movw [[R:l?r[0-9]*]], :lower16:bar
 ; ARM-LONG-ELF: {{(movt [[R]], :upper16:L_bar\$non_lazy_ptr)?}}
 
 ; ARM-LONG: blx [[R]]
 ; THUMB: @t10
-; THUMB: movs [[R0:l?r[0-9]*]], #0
-; THUMB: movs [[R1:l?r[0-9]*]], #248
-; THUMB: movs [[R2:l?r[0-9]*]], #187
-; THUMB: movs [[R3:l?r[0-9]*]], #28
-; THUMB: movw [[R4:l?r[0-9]*]], #40
-; THUMB: movw [[R5:l?r[0-9]*]], #186
-; THUMB: and [[R0]], [[R0]], #255
-; THUMB: and [[R1]], [[R1]], #255
-; THUMB: and [[R2]], [[R2]], #255
-; THUMB: and [[R3]], [[R3]], #255
-; THUMB: and [[R4]], [[R4]], #255
-; THUMB: str.w [[R4]], [sp]
-; THUMB: and [[R4]], [[R5]], #255
-; THUMB: str.w [[R4]], [sp, #4]
+; THUMB-DAG: movs [[R0:l?r[0-9]*]], #0
+; THUMB-DAG: movs [[R1:l?r[0-9]*]], #248
+; THUMB-DAG: movs [[R2:l?r[0-9]*]], #187
+; THUMB-DAG: movs [[R3:l?r[0-9]*]], #28
+; THUMB-DAG: movw [[R4:l?r[0-9]*]], #40
+; THUMB-DAG: movw [[R5:l?r[0-9]*]], #186
+; THUMB-DAG: and [[R0]], [[R0]], #255
+; THUMB-DAG: and [[R1]], [[R1]], #255
+; THUMB-DAG: and [[R2]], [[R2]], #255
+; THUMB-DAG: and [[R3]], [[R3]], #255
+; THUMB-DAG: and [[R4]], [[R4]], #255
+; THUMB-DAG: str.w [[R4]], [sp]
+; THUMB-DAG: and [[R4]], [[R5]], #255
+; THUMB-DAG: str.w [[R4]], [sp, #4]
 ; THUMB: bl {{_?}}bar
-; THUMB-LONG: @t10
+; THUMB-LONG-LABEL: @t10
 ; THUMB-LONG: {{(movw)|(ldr.n)}} [[R:l?r[0-9]*]], {{(:lower16:L_bar\$non_lazy_ptr)|(.LCPI)}}
 ; THUMB-LONG: {{(movt [[R]], :upper16:L_bar\$non_lazy_ptr)?}}
 ; THUMB-LONG: ldr{{(.w)?}} [[R]], {{\[}}[[R]]{{\]}}
+; THUMB-LONG: str     [[R]], [sp, [[SLOT:#[-0-9]+]]]           @ 4-byte Spill
+; THUMB-LONG: ldr.w   [[R:l?r[0-9]*]], [sp, [[SLOT]]]           @ 4-byte Reload
 ; THUMB-LONG: blx [[R]]
   %call = call i32 @bar(i8 zeroext 0, i8 zeroext -8, i8 zeroext -69, i8 zeroext 28, i8 zeroext 40, i8 zeroext -70)
   ret i32 0
@@ -152,14 +155,15 @@ define i32 @bar0(i32 %i) nounwind {
 }
 
 define void @foo3() uwtable {
-; ARM: movw    r0, #0
-; ARM: {{(movw r1, :lower16:_?bar0)|(ldr r1, .LCPI)}}
-; ARM: {{(movt r1, :upper16:_?bar0)|(ldr r1, \[r1\])}}
-; ARM: blx     r1
-; THUMB: movs    r0, #0
-; THUMB: {{(movw r1, :lower16:_?bar0)|(ldr.n r1, .LCPI)}}
-; THUMB: {{(movt r1, :upper16:_?bar0)|(ldr r1, \[r1\])}}
-; THUMB: blx     r1
+; ARM: @foo3
+; ARM: {{(movw r[0-9]+, :lower16:_?bar0)|(ldr r[0-9]+, .LCPI)}}
+; ARM: {{(movt r[0-9]+, :upper16:_?bar0)|(ldr r[0-9]+, \[r[0-9]+\])}}
+; ARM: movw    {{r[0-9]+}}, #0
+; ARM: blx     {{r[0-9]+}}
+; THUMB: {{(movw r[0-9]+, :lower16:_?bar0)|(ldr.n r[0-9]+, .LCPI)}}
+; THUMB: {{(movt r[0-9]+, :upper16:_?bar0)|(ldr r[0-9]+, \[r[0-9]+\])}}
+; THUMB: movs    {{r[0-9]+}}, #0
+; THUMB: blx     {{r[0-9]+}}
   %fptr = alloca i32 (i32)*, align 8
   store i32 (i32)* @bar0, i32 (i32)** %fptr, align 8
   %1 = load i32 (i32)*, i32 (i32)** %fptr, align 8
@@ -171,7 +175,7 @@ define i32 @LibCall(i32 %a, i32 %b) {
 entry:
 ; ARM: LibCall
 ; ARM: bl {{___udivsi3|__aeabi_uidiv}}
-; ARM-LONG: LibCall
+; ARM-LONG-LABEL: LibCall
 
 ; ARM-LONG-MACHO: {{(movw r2, :lower16:L___udivsi3\$non_lazy_ptr)|(ldr r2, .LCPI)}}
 ; ARM-LONG-MACHO: {{(movt r2, :upper16:L___udivsi3\$non_lazy_ptr)?}}
@@ -183,7 +187,7 @@ entry:
 ; ARM-LONG: blx r2
 ; THUMB: LibCall
 ; THUMB: bl {{___udivsi3|__aeabi_uidiv}}
-; THUMB-LONG: LibCall
+; THUMB-LONG-LABEL: LibCall
 ; THUMB-LONG: {{(movw r2, :lower16:L___udivsi3\$non_lazy_ptr)|(ldr.n r2, .LCPI)}}
 ; THUMB-LONG: {{(movt r2, :upper16:L___udivsi3\$non_lazy_ptr)?}}
 ; THUMB-LONG: ldr r2, [r2]
diff --git a/llvm/test/CodeGen/ARM/fast-isel-intrinsic.ll b/llvm/test/CodeGen/ARM/fast-isel-intrinsic.ll
index 8d9c27b6f22..ad3648791ad 100644
--- a/llvm/test/CodeGen/ARM/fast-isel-intrinsic.ll
+++ b/llvm/test/CodeGen/ARM/fast-isel-intrinsic.ll
@@ -16,10 +16,10 @@ define void @t1() nounwind ssp {
 ; ARM-LABEL: t1:
 ; ARM: {{(movw r0, :lower16:_?message1)|(ldr r0, .LCPI)}}
 ; ARM: {{(movt r0, :upper16:_?message1)|(ldr r0, \[r0\])}}
-; ARM: add r0, r0, #5
-; ARM: movw r1, #64
-; ARM: movw r2, #10
-; ARM: and r1, r1, #255
+; ARM-DAG: add r0, r0, #5
+; ARM-DAG: movw r1, #64
+; ARM-DAG: movw r2, #10
+; ARM-DAG: and r1, r1, #255
 ; ARM: bl {{_?}}memset
 ; ARM-LONG-LABEL: t1:
 
@@ -36,8 +36,8 @@ define void @t1() nounwind ssp {
 ; THUMB: {{(movt r0, :upper16:_?message1)|(ldr r0, \[r0\])}}
 ; THUMB: adds r0, #5
 ; THUMB: movs r1, #64
-; THUMB: movs r2, #10
 ; THUMB: and r1, r1, #255
+; THUMB: movs r2, #10
 ; THUMB: bl {{_?}}memset
 ; THUMB-LONG-LABEL: t1:
 ; THUMB-LONG: movw r3, :lower16:L_memset$non_lazy_ptr
@@ -62,10 +62,10 @@ define void @t2() nounwind ssp {
 
 ; ARM: add r1, r0, #4
 ; ARM: add r0, r0, #16
-; ARM: movw r2, #17
 ; ARM: str r0, [sp[[SLOT:[, #0-9]*]]] @ 4-byte Spill
 ; ARM: mov r0, r1
 ; ARM: ldr r1, [sp[[SLOT]]] @ 4-byte Reload
+; ARM: movw r2, #17
 ; ARM: bl {{_?}}memcpy
 ; ARM-LONG-LABEL: t2:
 
@@ -83,10 +83,10 @@ define void @t2() nounwind ssp {
 ; THUMB: ldr r0, [r0]
 ; THUMB: adds r1, r0, #4
 ; THUMB: adds r0, #16
-; THUMB: movs r2, #17
 ; THUMB: str r0, [sp[[SLOT:[, #0-9]*]]] @ 4-byte Spill
 ; THUMB: mov r0, r1
 ; THUMB: ldr r1,  [sp[[SLOT]]] @ 4-byte Reload
+; THUMB: movs r2, #17
 ; THUMB: bl {{_?}}memcpy
 ; THUMB-LONG-LABEL: t2:
 ; THUMB-LONG: movw r3, :lower16:L_memcpy$non_lazy_ptr
@@ -112,8 +112,8 @@ define void @t3() nounwind ssp {
 
 ; ARM: add r1, r0, #4
 ; ARM: add r0, r0, #16
-; ARM: movw r2, #10
 ; ARM: mov r0, r1
+; ARM: movw r2, #10
 ; ARM: bl {{_?}}memmove
 ; ARM-LONG-LABEL: t3:
 
@@ -131,10 +131,10 @@ define void @t3() nounwind ssp {
 ; THUMB: ldr r0, [r0]
 ; THUMB: adds r1, r0, #4
 ; THUMB: adds r0, #16
-; THUMB: movs r2, #10
 ; THUMB: str r0, [sp[[SLOT:[, #0-9]*]]] @ 4-byte Spill
 ; THUMB: mov r0, r1
 ; THUMB: ldr r1,  [sp[[SLOT]]] @ 4-byte Reload
+; THUMB: movs r2, #10
 ; THUMB: bl {{_?}}memmove
 ; THUMB-LONG-LABEL: t3:
 ; THUMB-LONG: movw r3, :lower16:L_memmove$non_lazy_ptr
diff --git a/llvm/test/CodeGen/ARM/fast-isel-select.ll b/llvm/test/CodeGen/ARM/fast-isel-select.ll
index 4eef1d6bb98..d113711f7e1 100644
--- a/llvm/test/CodeGen/ARM/fast-isel-select.ll
+++ b/llvm/test/CodeGen/ARM/fast-isel-select.ll
@@ -6,16 +6,14 @@
 define i32 @t1(i1 %c) nounwind readnone {
 entry:
 ; ARM: t1
-; ARM: movw r{{[1-9]}}, #10
 ; ARM: tst r0, #1
-; ARM: moveq r{{[1-9]}}, #20
-; ARM: mov r0, r{{[1-9]}}
+; ARM: movw r0, #10
+; ARM: moveq r0, #20
 ; THUMB: t1
-; THUMB: movs r{{[1-9]}}, #10
 ; THUMB: tst.w r0, #1
+; THUMB: movw r0, #10
 ; THUMB: it eq
-; THUMB: moveq r{{[1-9]}}, #20
-; THUMB: mov r0, r{{[1-9]}}
+; THUMB: moveq r0, #20
   %0 = select i1 %c, i32 10, i32 20
   ret i32 %0
 }
@@ -26,7 +24,7 @@ entry:
 ; ARM: tst r0, #1
 ; ARM: moveq r{{[1-9]}}, #20
 ; ARM: mov r0, r{{[1-9]}}
-; THUMB: t2
+; THUMB-LABEL: t2
 ; THUMB: tst.w r0, #1
 ; THUMB: it eq
 ; THUMB: moveq r{{[1-9]}}, #20
@@ -54,16 +52,14 @@ entry:
 define i32 @t4(i1 %c) nounwind readnone {
 entry:
 ; ARM: t4
-; ARM: mvn r{{[1-9]}}, #9
 ; ARM: tst r0, #1
-; ARM: mvneq r{{[1-9]}}, #0
-; ARM: mov r0, r{{[1-9]}}
+; ARM: mvn r0, #9
+; ARM: mvneq r0, #0
 ; THUMB-LABEL: t4
-; THUMB: mvn [[REG:r[1-9]+]], #9
 ; THUMB: tst.w r0, #1
+; THUMB: mvn r0, #9
 ; THUMB: it eq
-; THUMB: mvneq [[REG]], #0
-; THUMB: mov r0, [[REG]]
+; THUMB: mvneq r0, #0
   %0 = select i1 %c, i32 -10, i32 -1
   ret i32 %0
 }
diff --git a/llvm/test/CodeGen/ARM/fast-isel-vararg.ll b/llvm/test/CodeGen/ARM/fast-isel-vararg.ll
index 35442eea100..d8c71e326be 100644
--- a/llvm/test/CodeGen/ARM/fast-isel-vararg.ll
+++ b/llvm/test/CodeGen/ARM/fast-isel-vararg.ll
@@ -17,23 +17,24 @@ entry:
   %4 = load i32, i32* %n, align 4
 ; ARM: VarArg
 ; ARM: mov [[FP:r[0-9]+]], sp
-; ARM: sub sp, sp, #32
-; ARM: movw r0, #5
+; ARM: sub sp, sp, #{{(36|40)}}
 ; ARM: ldr r1, {{\[}}[[FP]], #-4]
 ; ARM: ldr r2, {{\[}}[[FP]], #-8]
 ; ARM: ldr r3, {{\[}}[[FP]], #-12]
-; ARM: ldr [[Ra:r[0-9]+]], [sp, #16]
-; ARM: ldr [[Rb:[lr]+[0-9]*]], [sp, #12]
-; ARM: str [[Ra]], [sp]
+; ARM: ldr [[Ra:r[0-9]+]], {{\[}}[[FP]], #-16]
+; ARM: ldr [[Rb:[lr]+[0-9]*]], [sp, #{{(16|20)}}]
+; ARM: movw [[Rc:[lr]+[0-9]*]], #5
+;   Ra got spilled
+; ARM: mov r0, [[Rc]]
+; ARM: str {{.*}}, [sp]
 ; ARM: str [[Rb]], [sp, #4]
 ; ARM: bl {{_?CallVariadic}}
-; THUMB: sub sp, #32
-; THUMB: movs r0, #5
-; THUMB: ldr r1, [sp, #28]
-; THUMB: ldr r2, [sp, #24]
-; THUMB: ldr r3, [sp, #20]
+; THUMB: sub sp, #{{36}}
+; THUMB: ldr r1, [sp, #32]
+; THUMB: ldr r2, [sp, #28]
+; THUMB: ldr r3, [sp, #24]
+; THUMB: ldr {{[a-z0-9]+}}, [sp, #20]
 ; THUMB: ldr.w {{[a-z0-9]+}}, [sp, #16]
-; THUMB: ldr.w {{[a-z0-9]+}}, [sp, #12]
 ; THUMB: str.w {{[a-z0-9]+}}, [sp]
 ; THUMB: str.w {{[a-z0-9]+}}, [sp, #4]
 ; THUMB: bl {{_?}}CallVariadic
diff --git a/llvm/test/CodeGen/ARM/swifterror.ll b/llvm/test/CodeGen/ARM/swifterror.ll
index 8d1729df2ae..313fef5eb34 100644
--- a/llvm/test/CodeGen/ARM/swifterror.ll
+++ b/llvm/test/CodeGen/ARM/swifterror.ll
@@ -188,11 +188,10 @@ define float @foo_loop(%swift_error** swifterror %error_ptr_ref, i32 %cc, float
 ; CHECK-O0: mov r{{.*}}, r8
 ; CHECK-O0: cmp r{{.*}}, #0
 ; CHECK-O0: beq
-; CHECK-O0-DAG: movw r{{.*}}, #1
-; CHECK-O0-DAG: mov r{{.*}}, #16
+; CHECK-O0: mov r0, #16
 ; CHECK-O0: malloc
 ; CHECK-O0-DAG: mov [[ID:r[0-9]+]], r0
-; CHECK-O0-DAG: ldr [[ID2:r[0-9]+]], [sp{{.*}}]
+; CHECK-O0-DAG: movw [[ID2:.*]], #1
 ; CHECK-O0: strb [[ID2]], [{{.*}}[[ID]], #8]
 ; spill r0
 ; CHECK-O0: str r0, [sp{{.*}}]