Implement support for using modeling implicit-zero-extension on x86-64

with SUBREG_TO_REG, teach SimpleRegisterCoalescing to coalesce
SUBREG_TO_REG instructions (which are similar to INSERT_SUBREG
instructions), and teach the DAGCombiner to take advantage of this on
targets which support it. This eliminates many redundant
zero-extension operations on x86-64.

This adds a new TargetLowering hook, isZExtFree. It's similar to
isTruncateFree, except it only applies to actual definitions, and not
no-op truncates which may not zero the high bits.

Also, this adds a new optimization to SimplifyDemandedBits: transform
operations like x+y into (zext (add (trunc x), (trunc y))) on targets
where all the casts are no-ops. In contexts where the high part of the
add is explicitly masked off, this allows the mask operation to be
eliminated. Fix the DAGCombiner to avoid undoing these transformations
to eliminate casts on targets where the casts are no-ops.

Also, this adds a new two-address lowering heuristic. Since
two-address lowering runs before coalescing, it helps to be able to
look through copies when deciding whether commuting and/or
three-address conversion are profitable.

Also, fix a bug in LiveInterval::MergeInClobberRanges. It didn't handle
the case that a clobber range extended both before and beyond an
existing live range. In that case, multiple live ranges need to be
added. This was exposed by the new subreg coalescing code.

Remove 2008-05-06-SpillerBug.ll. It was bugpoint-reduced, and the
spiller behavior it was looking for no longer occurrs with the new
instruction selection.


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

9 files changed, 215 insertions, 44 deletions

diff --git a/test/CodeGen/X86/2008-05-06-SpillerBug.ll b/test/CodeGen/X86/2008-05-06-SpillerBug.ll
deleted file mode 100644
index e13f398062..0000000000
--- a/test/CodeGen/X86/2008-05-06-SpillerBug.ll
+++ /dev/null
@@ -1,39 +0,0 @@
-; RUN: llvm-as < %s | llc -mtriple=i386-apple-darwin -relocation-model=pic -disable-fp-elim | grep addb | grep ebp
-
-	%struct.rc4_state = type { i32, i32, [256 x i32] }
-@.str1 = internal constant [65 x i8] c"m[%d] = 0x%02x, m[%d] = 0x%02x, 0x%02x, k = %d, key[k] = 0x%02x\0A\00"		; <[65 x i8]*> [#uses=1]
-@keys = internal constant [7 x [30 x i8]] [ [30 x i8] c"\08\01#Eg\89\AB\CD\EF\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00", [30 x i8] c"\08\01#Eg\89\AB\CD\EF\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00", [30 x i8] c"\08\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00", [30 x i8] c"\04\EF\01#E\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00", [30 x i8] c"\08\01#Eg\89\AB\CD\EF\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00", [30 x i8] c"\04\EF\01#E\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00", [30 x i8] zeroinitializer ]		; <[7 x [30 x i8]]*> [#uses=1]
-
-declare i32 @printf(i8*, ...) nounwind 
-
-define i32 @main(i32 %argc, i8** %argv) nounwind  {
-entry:
-	br label %bb25
-
-bb25:		; preds = %bb25, %entry
-  %foo = phi i1 [ 0, %bb25], [ 1, %entry]
-	br i1 %foo, label %bb.i, label %bb25
-
-bb.i:		; preds = %bb.i, %bb25
-  %foo2 = phi i1 [ 0, %bb.i], [1, %bb25]
-	br i1 %foo2, label %bb21.i, label %bb.i
-
-bb21.i:		; preds = %bb21.i, %bb.i
-	%k.0.reg2mem.0.i = phi i32 [ %k.1.i, %bb21.i ], [ 0, %bb.i ]		; <i32> [#uses=2]
-	%j.0.reg2mem.0.i = phi i8 [ %tmp35.i, %bb21.i ], [ 0, %bb.i ]		; <i8> [#uses=1]
-	%tmp25.i = load i32* null, align 4		; <i32> [#uses=4]
-	%tmp2829.i = trunc i32 %tmp25.i to i8		; <i8> [#uses=1]
-	%.sum = add i32 %k.0.reg2mem.0.i, 1		; <i32> [#uses=3]
-	%tmp33.i = getelementptr [7 x [30 x i8]]* @keys, i32 0, i32 0, i32 %.sum		; <i8*> [#uses=1]
-	%tmp34.i = load i8* %tmp33.i, align 1		; <i8> [#uses=1]
-	%tmp30.i = add i8 %tmp2829.i, %j.0.reg2mem.0.i		; <i8> [#uses=1]
-	%tmp35.i = add i8 %tmp30.i, %tmp34.i		; <i8> [#uses=2]
-	%tmp3536.i = zext i8 %tmp35.i to i32		; <i32> [#uses=2]
-	%tmp39.i = getelementptr %struct.rc4_state* null, i32 0, i32 2, i32 %tmp3536.i		; <i32*> [#uses=1]
-	store i32 %tmp25.i, i32* %tmp39.i, align 4
-	%tmp60.i = load i32* null, align 4		; <i32> [#uses=1]
-	%tmp65.i = call i32 (i8*, ...)* @printf( i8* getelementptr ([65 x i8]* @.str1, i32 0, i32 0), i32 0, i32 %tmp60.i, i32 %tmp3536.i, i32 %tmp25.i, i32 %tmp25.i, i32 %k.0.reg2mem.0.i, i32 0 ) nounwind 		; <i32> [#uses=0]
-	%tmp70.i = icmp slt i32 %.sum, 8		; <i1> [#uses=1]
-	%k.1.i = select i1 %tmp70.i, i32 %.sum, i32 0		; <i32> [#uses=1]
-	br label %bb21.i
-}
diff --git a/test/CodeGen/X86/byval7.ll b/test/CodeGen/X86/byval7.ll
index fcbc59b838..6b64c6ce4d 100644
--- a/test/CodeGen/X86/byval7.ll
+++ b/test/CodeGen/X86/byval7.ll
@@ -1,4 +1,4 @@
-; RUN: llvm-as < %s | llc -march=x86 -mcpu=yonah | grep add | grep 16
+; RUN: llvm-as < %s | llc -march=x86 -mcpu=yonah | egrep {add|lea} | grep 16
 
 	%struct.S = type { <2 x i64>, <2 x i64>, <2 x i64>, <2 x i64>,
                            <2 x i64> }
diff --git a/test/CodeGen/X86/iv-users-in-other-loops.ll b/test/CodeGen/X86/iv-users-in-other-loops.ll
index b47b856052..b21586173f 100644
--- a/test/CodeGen/X86/iv-users-in-other-loops.ll
+++ b/test/CodeGen/X86/iv-users-in-other-loops.ll
@@ -1,7 +1,7 @@
 ; RUN: llvm-as < %s | llc -march=x86-64 -f -o %t
 ; RUN: grep inc %t | count 2
 ; RUN: grep addq %t | count 13
-; RUN: grep leaq %t | count 10
+; RUN: grep leaq %t | count 9
 ; RUN: grep movq %t | count 5
 
 ; IV users in each of the loops from other loops shouldn't cause LSR
diff --git a/test/CodeGen/X86/subreg-to-reg-1.ll b/test/CodeGen/X86/subreg-to-reg-1.ll
index 4e487e1847..cf9f2d8142 100644
--- a/test/CodeGen/X86/subreg-to-reg-1.ll
+++ b/test/CodeGen/X86/subreg-to-reg-1.ll
@@ -1,6 +1,9 @@
-; RUN: llvm-as < %s | llc -march=x86-64 | grep {movl	%e.\*, %e.\*} | count 1
+; RUN: llvm-as < %s | llc -march=x86-64 | grep {leal	.*), %e.\*} | count 1
 
 ; Don't eliminate or coalesce away the explicit zero-extension!
+; This is currently using an leal because of a 3-addressification detail,
+; though this isn't necessary; The point of this test is to make sure
+; a 32-bit add is used.
 
 define i64 @foo(i64 %a) {
   %b = add i64 %a, 4294967295
diff --git a/test/CodeGen/X86/subreg-to-reg-3.ll b/test/CodeGen/X86/subreg-to-reg-3.ll
new file mode 100644
index 0000000000..6634538c2a
--- /dev/null
+++ b/test/CodeGen/X86/subreg-to-reg-3.ll
@@ -0,0 +1,10 @@
+; RUN: llvm-as < %s | llc -march=x86-64 | grep imull
+
+; Don't eliminate or coalesce away the explicit zero-extension!
+
+define i64 @foo(i64 %a) {
+  %b = mul i64 %a, 7823
+  %c = and i64 %b, 4294967295
+  %d = add i64 %c, 1
+  ret i64 %d
+}
diff --git a/test/CodeGen/X86/subreg-to-reg-4.ll b/test/CodeGen/X86/subreg-to-reg-4.ll
new file mode 100644
index 0000000000..bb6af3988c
--- /dev/null
+++ b/test/CodeGen/X86/subreg-to-reg-4.ll
@@ -0,0 +1,135 @@
+; RUN: llvm-as < %s | llc -march=x86-64 > %t
+; RUN: not grep leaq %t
+; RUN: not grep incq %t
+; RUN: not grep decq %t
+; RUN: not grep negq %t
+; RUN: not grep addq %t
+; RUN: not grep subq %t
+; RUN: not grep {movl	%} %t
+
+; Utilize implicit zero-extension on x86-64 to eliminate explicit
+; zero-extensions. Shrink 64-bit adds to 32-bit when the high
+; 32-bits will be zeroed.
+
+define void @bar(i64 %x, i64 %y, i64* %z) nounwind readnone {
+entry:
+	%t0 = add i64 %x, %y
+	%t1 = and i64 %t0, 4294967295
+        store i64 %t1, i64* %z
+	ret void
+}
+define void @easy(i32 %x, i32 %y, i64* %z) nounwind readnone {
+entry:
+	%t0 = add i32 %x, %y
+        %tn = zext i32 %t0 to i64
+	%t1 = and i64 %tn, 4294967295
+        store i64 %t1, i64* %z
+	ret void
+}
+define void @cola(i64 *%x, i64 %y, i64* %z, i64 %u) nounwind readnone {
+entry:
+        %p = load i64* %x
+	%t0 = add i64 %p, %y
+	%t1 = and i64 %t0, 4294967295
+        %t2 = xor i64 %t1, %u
+        store i64 %t2, i64* %z
+	ret void
+}
+define void @yaks(i64 *%x, i64 %y, i64* %z, i64 %u) nounwind readnone {
+entry:
+        %p = load i64* %x
+	%t0 = add i64 %p, %y
+        %t1 = xor i64 %t0, %u
+	%t2 = and i64 %t1, 4294967295
+        store i64 %t2, i64* %z
+	ret void
+}
+define void @foo(i64 *%x, i64 *%y, i64* %z) nounwind readnone {
+entry:
+        %a = load i64* %x
+        %b = load i64* %y
+	%t0 = add i64 %a, %b
+	%t1 = and i64 %t0, 4294967295
+        store i64 %t1, i64* %z
+	ret void
+}
+define void @avo(i64 %x, i64* %z, i64 %u) nounwind readnone {
+entry:
+	%t0 = add i64 %x, 734847
+	%t1 = and i64 %t0, 4294967295
+        %t2 = xor i64 %t1, %u
+        store i64 %t2, i64* %z
+	ret void
+}
+define void @phe(i64 %x, i64* %z, i64 %u) nounwind readnone {
+entry:
+	%t0 = add i64 %x, 734847
+        %t1 = xor i64 %t0, %u
+	%t2 = and i64 %t1, 4294967295
+        store i64 %t2, i64* %z
+	ret void
+}
+define void @oze(i64 %y, i64* %z) nounwind readnone {
+entry:
+	%t0 = add i64 %y, 1
+	%t1 = and i64 %t0, 4294967295
+        store i64 %t1, i64* %z
+	ret void
+}
+
+define void @sbar(i64 %x, i64 %y, i64* %z) nounwind readnone {
+entry:
+	%t0 = sub i64 %x, %y
+	%t1 = and i64 %t0, 4294967295
+        store i64 %t1, i64* %z
+	ret void
+}
+define void @seasy(i32 %x, i32 %y, i64* %z) nounwind readnone {
+entry:
+	%t0 = sub i32 %x, %y
+        %tn = zext i32 %t0 to i64
+	%t1 = and i64 %tn, 4294967295
+        store i64 %t1, i64* %z
+	ret void
+}
+define void @scola(i64 *%x, i64 %y, i64* %z, i64 %u) nounwind readnone {
+entry:
+        %p = load i64* %x
+	%t0 = sub i64 %p, %y
+	%t1 = and i64 %t0, 4294967295
+        %t2 = xor i64 %t1, %u
+        store i64 %t2, i64* %z
+	ret void
+}
+define void @syaks(i64 *%x, i64 %y, i64* %z, i64 %u) nounwind readnone {
+entry:
+        %p = load i64* %x
+	%t0 = sub i64 %p, %y
+        %t1 = xor i64 %t0, %u
+	%t2 = and i64 %t1, 4294967295
+        store i64 %t2, i64* %z
+	ret void
+}
+define void @sfoo(i64 *%x, i64 *%y, i64* %z) nounwind readnone {
+entry:
+        %a = load i64* %x
+        %b = load i64* %y
+	%t0 = sub i64 %a, %b
+	%t1 = and i64 %t0, 4294967295
+        store i64 %t1, i64* %z
+	ret void
+}
+define void @swya(i64 %y, i64* %z) nounwind readnone {
+entry:
+	%t0 = sub i64 0, %y
+	%t1 = and i64 %t0, 4294967295
+        store i64 %t1, i64* %z
+	ret void
+}
+define void @soze(i64 %y, i64* %z) nounwind readnone {
+entry:
+	%t0 = sub i64 %y, 1
+	%t1 = and i64 %t0, 4294967295
+        store i64 %t1, i64* %z
+	ret void
+}
diff --git a/test/CodeGen/X86/subreg-to-reg-5.ll b/test/CodeGen/X86/subreg-to-reg-5.ll
new file mode 100644
index 0000000000..eee751a87d
--- /dev/null
+++ b/test/CodeGen/X86/subreg-to-reg-5.ll
@@ -0,0 +1,34 @@
+; RUN: llvm-as < %s | llc -march=x86-64 > %t
+; RUN: grep addl %t
+; RUN: not egrep {movl|movq} %t
+
+define float @foo(float* %B) nounwind {
+entry:
+	br label %bb2
+
+bb2:		; preds = %bb3, %entry
+	%B_addr.0.rec = phi i64 [ %indvar.next154, %bb3 ], [ 0, %entry ]		; <i64> [#uses=2]
+	br i1 false, label %bb3, label %bb4
+
+bb3:		; preds = %bb2
+	%indvar.next154 = add i64 %B_addr.0.rec, 1		; <i64> [#uses=1]
+	br label %bb2
+
+bb4:		; preds = %bb2
+	%B_addr.0 = getelementptr float* %B, i64 %B_addr.0.rec		; <float*> [#uses=1]
+	%t1 = ptrtoint float* %B_addr.0 to i64		; <i64> [#uses=1]
+	%t2 = and i64 %t1, 15		; <i64> [#uses=1]
+	%t3 = icmp eq i64 %t2, 0		; <i1> [#uses=1]
+	br i1 %t3, label %bb5, label %bb10.preheader
+
+bb10.preheader:		; preds = %bb4
+	br label %bb9
+
+bb5:		; preds = %bb4
+	unreachable
+
+bb9:		; preds = %bb10.preheader
+	%t5 = getelementptr float* %B, i64 0		; <float*> [#uses=1]
+	%t7 = load float* %t5		; <float> [#uses=1]
+	ret float %t7
+}
diff --git a/test/CodeGen/X86/subreg-to-reg-6.ll b/test/CodeGen/X86/subreg-to-reg-6.ll
new file mode 100644
index 0000000000..f18eef7d19
--- /dev/null
+++ b/test/CodeGen/X86/subreg-to-reg-6.ll
@@ -0,0 +1,29 @@
+; RUN: llvm-as < %s | llc -march=x86-64
+
+define i64 @foo() nounwind {
+entry:
+	%t0 = load i32* null, align 8
+	switch i32 %t0, label %bb65 [
+		i32 16, label %bb
+		i32 12, label %bb56
+	]
+
+bb:
+	br label %bb65
+
+bb56:
+	unreachable
+
+bb65:
+	%a = phi i64 [ 0, %bb ], [ 0, %entry ]
+	tail call void asm "", "{cx}"(i64 %a) nounwind
+	%t15 = and i64 %a, 4294967295
+	ret i64 %t15
+}
+
+define i64 @bar(i64 %t0) nounwind {
+	call void asm "", "{cx}"(i64 0) nounwind
+	%t1 = sub i64 0, %t0
+	%t2 = and i64 %t1, 4294967295
+	ret i64 %t2
+}
diff --git a/test/CodeGen/X86/twoaddr-coalesce.ll b/test/CodeGen/X86/twoaddr-coalesce.ll
index ba98ae8252..5293b77879 100644
--- a/test/CodeGen/X86/twoaddr-coalesce.ll
+++ b/test/CodeGen/X86/twoaddr-coalesce.ll
@@ -1,5 +1,4 @@
-; RUN: llvm-as < %s | llc -march=x86 -stats |& \
-; RUN:   grep {twoaddrinstr} | grep {Number of instructions aggressively commuted}
+; RUN: llvm-as < %s | llc -march=x86 | grep mov | count 5
 ; rdar://6523745
 
 @"\01LC" = internal constant [4 x i8] c"%d\0A\00"		; <[4 x i8]*> [#uses=1]