This patch adds the X86FixupLEAs pass, which will reduce instruction

latency for certain models of the Intel Atom family, by converting
instructions into their equivalent LEA instructions, when it is both
useful and possible to do so.




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

4 files changed, 174 insertions, 1 deletions

diff --git a/test/CodeGen/X86/atom-fixup-lea1.ll b/test/CodeGen/X86/atom-fixup-lea1.ll
new file mode 100644
index 0000000000..4651bf257f
--- /dev/null
+++ b/test/CodeGen/X86/atom-fixup-lea1.ll
@@ -0,0 +1,38 @@
+; RUN: llc < %s -mcpu=atom -mtriple=i686-linux | FileCheck %s
+; CHECK: addl
+; CHECK-NEXT:leal
+; CHECK-NEXT:decl
+; CHECK-NEXT:jne
+
+; Test for the FixupLEAs pre-emit pass. An LEA should be substituted for the ADD
+; that increments the array pointer because it is within 5 instructions of the
+; corresponding load. The ADD precedes the load by following the loop back edge.
+
+; Original C code
+;int test(int n, int * array)
+;{
+;  int sum = 0;
+;  for(int i = 0; i < n; i++)
+;    sum += array[i];
+;  return sum;
+;}
+
+define i32 @test(i32 %n, i32* nocapture %array) {
+entry:
+  %cmp4 = icmp sgt i32 %n, 0
+  br i1 %cmp4, label %for.body, label %for.end
+
+for.body:
+  %i.06 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
+  %sum.05 = phi i32 [ %add, %for.body ], [ 0, %entry ]
+  %arrayidx = getelementptr inbounds i32* %array, i32 %i.06
+  %0 = load i32* %arrayidx, align 4
+  %add = add nsw i32 %0, %sum.05
+  %inc = add nsw i32 %i.06, 1
+  %exitcond = icmp eq i32 %inc, %n
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:
+  %sum.0.lcssa = phi i32 [ 0, %entry ], [ %add, %for.body ]
+  ret i32 %sum.0.lcssa
+}
diff --git a/test/CodeGen/X86/atom-fixup-lea2.ll b/test/CodeGen/X86/atom-fixup-lea2.ll
new file mode 100644
index 0000000000..1855ea1d02
--- /dev/null
+++ b/test/CodeGen/X86/atom-fixup-lea2.ll
@@ -0,0 +1,84 @@
+; RUN: llc < %s -mcpu=atom -mtriple=i686-linux | FileCheck %s
+; CHECK:BB#5
+; CHECK-NEXT:leal
+; CHECK-NEXT:leal
+; CHECK-NEXT:leal
+; CHECK-NEXT:movl
+
+
+; Test for fixup lea pre-emit pass. LEA instructions should be substituted for
+; ADD instructions which compute the address and index of the load because they
+; precede the load within 5 instructions. An LEA should also be substituted for
+; an ADD which computes part of the index because it precedes the index LEA
+; within 5 instructions, this substitution is referred to as backwards chaining.
+
+; Original C Code
+;struct node_t
+;{
+;  int k, m, n, p;
+;  int * array;
+;};
+
+;extern struct node_t getnode();
+
+;int test()
+;{
+;  int sum = 0;
+;  struct node_t n = getnode();
+;  if(n.array != 0 && n.p > 0 && n.k > 0 && n.n > 0 && n.m > 0) {
+;    sum = ((int*)((int)n.array + n.p) )[ n.k + n.m + n.n ];
+;  }
+;  return sum;
+;}
+
+%struct.node_t = type { i32, i32, i32, i32, i32* }
+
+define i32 @test() {
+entry:
+  %n = alloca %struct.node_t, align 4
+  call void bitcast (void (%struct.node_t*, ...)* @getnode to void (%struct.node_t*)*)(%struct.node_t* sret %n)
+  %array = getelementptr inbounds %struct.node_t* %n, i32 0, i32 4
+  %0 = load i32** %array, align 4
+  %cmp = icmp eq i32* %0, null
+  br i1 %cmp, label %if.end, label %land.lhs.true
+
+land.lhs.true:
+  %p = getelementptr inbounds %struct.node_t* %n, i32 0, i32 3
+  %1 = load i32* %p, align 4
+  %cmp1 = icmp sgt i32 %1, 0
+  br i1 %cmp1, label %land.lhs.true2, label %if.end
+
+land.lhs.true2:
+  %k = getelementptr inbounds %struct.node_t* %n, i32 0, i32 0
+  %2 = load i32* %k, align 4
+  %cmp3 = icmp sgt i32 %2, 0
+  br i1 %cmp3, label %land.lhs.true4, label %if.end
+
+land.lhs.true4:
+  %n5 = getelementptr inbounds %struct.node_t* %n, i32 0, i32 2
+  %3 = load i32* %n5, align 4
+  %cmp6 = icmp sgt i32 %3, 0
+  br i1 %cmp6, label %land.lhs.true7, label %if.end
+
+land.lhs.true7:
+  %m = getelementptr inbounds %struct.node_t* %n, i32 0, i32 1
+  %4 = load i32* %m, align 4
+  %cmp8 = icmp sgt i32 %4, 0
+  br i1 %cmp8, label %if.then, label %if.end
+
+if.then:
+  %add = add i32 %3, %2
+  %add12 = add i32 %add, %4
+  %5 = ptrtoint i32* %0 to i32
+  %add15 = add nsw i32 %1, %5
+  %6 = inttoptr i32 %add15 to i32*
+  %arrayidx = getelementptr inbounds i32* %6, i32 %add12
+  %7 = load i32* %arrayidx, align 4
+  br label %if.end
+
+if.end:
+  %sum.0 = phi i32 [ %7, %if.then ], [ 0, %land.lhs.true7 ], [ 0, %land.lhs.true4 ], [ 0, %land.lhs.true2 ], [ 0, %land.lhs.true ], [ 0, %entry ]
+  ret i32 %sum.0
+}
+
+declare void @getnode(%struct.node_t* sret, ...)
diff --git a/test/CodeGen/X86/atom-fixup-lea3.ll b/test/CodeGen/X86/atom-fixup-lea3.ll
new file mode 100644
index 0000000000..311b0b3021
--- /dev/null
+++ b/test/CodeGen/X86/atom-fixup-lea3.ll
@@ -0,0 +1,51 @@
+; RUN: llc < %s -mcpu=atom -mtriple=i686-linux | FileCheck %s
+; CHECK: addl ([[reg:%[a-z]+]])
+; CHECK-NEXT: addl $4, [[reg]]
+
+; Test for the FixupLEAs pre-emit pass.
+; An LEA should NOT be substituted for the ADD instruction
+; that increments the array pointer if it is greater than 5 instructions
+; away from the memory reference that uses it.
+
+; Original C code: clang -m32 -S -O2
+;int test(int n, int * array, int * m, int * array2)
+;{
+;  int i, j = 0;
+;  int sum = 0;
+;  for (i = 0, j = 0; i < n;) {
+;    ++i;
+;    *m += array2[j++];
+;    sum += array[i];
+;  }
+;  return sum;
+;}
+
+define i32 @test(i32 %n, i32* nocapture %array, i32* nocapture %m, i32* nocapture %array2) #0 {
+entry:
+  %cmp7 = icmp sgt i32 %n, 0
+  br i1 %cmp7, label %for.body.lr.ph, label %for.end
+
+for.body.lr.ph:                                   ; preds = %entry
+  %.pre = load i32* %m, align 4
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %for.body.lr.ph
+  %0 = phi i32 [ %.pre, %for.body.lr.ph ], [ %add, %for.body ]
+  %sum.010 = phi i32 [ 0, %for.body.lr.ph ], [ %add3, %for.body ]
+  %j.09 = phi i32 [ 0, %for.body.lr.ph ], [ %inc1, %for.body ]
+  %inc1 = add nsw i32 %j.09, 1
+  %arrayidx = getelementptr inbounds i32* %array2, i32 %j.09
+  %1 = load i32* %arrayidx, align 4
+  %add = add nsw i32 %0, %1
+  store i32 %add, i32* %m, align 4
+  %arrayidx2 = getelementptr inbounds i32* %array, i32 %inc1
+  %2 = load i32* %arrayidx2, align 4
+  %add3 = add nsw i32 %2, %sum.010
+  %exitcond = icmp eq i32 %inc1, %n
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.body, %entry
+  %sum.0.lcssa = phi i32 [ 0, %entry ], [ %add3, %for.body ]
+  ret i32 %sum.0.lcssa
+}
+
diff --git a/test/CodeGen/X86/lsr-static-addr.ll b/test/CodeGen/X86/lsr-static-addr.ll
index 6566f56378..b2aea90500 100644
--- a/test/CodeGen/X86/lsr-static-addr.ll
+++ b/test/CodeGen/X86/lsr-static-addr.ll
@@ -17,7 +17,7 @@
 ; ATOM-NEXT: movsd A(,%rax,8)
 ; ATOM-NEXT: mulsd
 ; ATOM-NEXT: movsd
-; ATOM-NEXT: incq %rax
+; ATOM-NEXT: leaq 1(%rax), %rax
 
 @A = external global [0 x double]