Remove Merge Functions pointer comparisons

Summary:
This patch removes two remaining places where pointer value comparisons
are used to order functions: comparing range annotation metadata, and comparing
block address constants. (These are both rare cases, and so no actual
non-determinism was observed from either case).

The fix for range metadata is simple: the annotation always consists of a pair
of integers, so we just order by those integers.

The fix for block addresses is more subtle. Two constants are the same if they
are the same basic block in the same function, or if they refer to corresponding
basic blocks in each respective function. Note that in the first case, merging
is trivially correct. In the second, the correctness of merging relies on the
fact that the the values of block addresses cannot be compared. This change is
actually an enhancement, as these functions could not previously be merged (see
merge-block-address.ll).

There is still a problem with cross function block addresses, in that constants
pointing to a basic block in a merged function is not updated.

This also more robustly compares floating point constants by all fields of their
semantics, and fixes a dyn_cast/cast mixup.

Author: jrkoenig
Reviewers: dschuff, nlewycky, jfb
Subscribers llvm-commits
Differential revision: http://reviews.llvm.org/D12376

llvm-svn: 246305

5 files changed, 341 insertions, 0 deletions

diff --git a/llvm/test/Transforms/MergeFunc/merge-block-address-other-function.ll b/llvm/test/Transforms/MergeFunc/merge-block-address-other-function.ll
new file mode 100644
index 00000000000..ca1a6f2fe2a
--- /dev/null
+++ b/llvm/test/Transforms/MergeFunc/merge-block-address-other-function.ll
@@ -0,0 +1,49 @@
+; RUN: opt -S -mergefunc < %s | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define i32 @_Z1fi(i32 %i) #0 {
+entry:
+  %retval = alloca i32, align 4
+  %i.addr = alloca i32, align 4
+  store i32 %i, i32* %i.addr, align 4
+  %0 = load i32, i32* %i.addr, align 4
+  %cmp = icmp eq i32 %0, 1
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:
+  store i32 3, i32* %retval
+  br label %return
+
+if.end:
+  %1 = load i32, i32* %i.addr, align 4
+  %cmp1 = icmp eq i32 %1, 3
+  br i1 %cmp1, label %if.then.2, label %if.end.3
+
+if.then.2:
+  store i32 56, i32* %retval
+  br label %return
+
+if.end.3:
+  store i32 0, i32* %retval
+  br label %return
+
+return:
+  %2 = load i32, i32* %retval
+  ret i32 %2
+}
+
+
+define internal i8* @Afunc(i32* %P) {
+  store i32 1, i32* %P
+  store i32 3, i32* %P
+  ret i8* blockaddress(@_Z1fi, %if.then.2)
+}
+
+define internal i8* @Bfunc(i32* %P) {
+; CHECK-NOT: @Bfunc
+  store i32 1, i32* %P
+  store i32 3, i32* %P
+  ret i8* blockaddress(@_Z1fi, %if.then.2)
+}
diff --git a/llvm/test/Transforms/MergeFunc/merge-block-address.ll b/llvm/test/Transforms/MergeFunc/merge-block-address.ll
new file mode 100644
index 00000000000..4ce13e5da87
--- /dev/null
+++ b/llvm/test/Transforms/MergeFunc/merge-block-address.ll
@@ -0,0 +1,91 @@
+; RUN: opt -S -mergefunc < %s | FileCheck %s
+
+; These two functions are identical. The basic block labels are the same, and
+; induce the same CFG. We are testing that block addresses within different
+; functions are compared by their value, and not based on order. Both functions
+; come from the same C-code, but in the first the two val_0/val_1 basic blocks
+; are in a different order (they were manually switched post-compilation).
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define i32 @_Z1fi(i32 %i) #0 {
+entry:
+  %i.addr = alloca i32, align 4
+  %ret = alloca i32, align 4
+  %l = alloca i8*, align 8
+  store i32 %i, i32* %i.addr, align 4
+  store i32 0, i32* %ret, align 4
+  store i8* blockaddress(@_Z1fi, %val_0), i8** %l, align 8
+  %0 = load i32, i32* %i.addr, align 4
+  %and = and i32 %0, 256
+  %cmp = icmp eq i32 %and, 0
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:
+  store i8* blockaddress(@_Z1fi, %val_1), i8** %l, align 8
+  br label %if.end
+
+if.end:
+  %1 = load i8*, i8** %l, align 8
+  br label %indirectgoto
+
+val_1:
+  store i32 42, i32* %ret, align 4
+  br label %end
+
+val_0:
+  store i32 12, i32* %ret, align 4
+  br label %end
+
+
+end:
+  %2 = load i32, i32* %ret, align 4
+  ret i32 %2
+
+indirectgoto:
+  %indirect.goto.dest = phi i8* [ %1, %if.end ]
+  indirectbr i8* %indirect.goto.dest, [label %val_0, label %val_1]
+}
+
+define i32 @_Z1gi(i32 %i) #0 {
+; CHECK-LABEL: define i32 @_Z1gi
+; CHECK-NEXT: tail call i32 @_Z1fi
+; CHECK-NEXT: ret
+entry:
+  %i.addr = alloca i32, align 4
+  %ret = alloca i32, align 4
+  %l = alloca i8*, align 8
+  store i32 %i, i32* %i.addr, align 4
+  store i32 0, i32* %ret, align 4
+  store i8* blockaddress(@_Z1gi, %val_0), i8** %l, align 8
+  %0 = load i32, i32* %i.addr, align 4
+  %and = and i32 %0, 256
+  %cmp = icmp eq i32 %and, 0
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:
+  store i8* blockaddress(@_Z1gi, %val_1), i8** %l, align 8
+  br label %if.end
+
+if.end:
+  %1 = load i8*, i8** %l, align 8
+  br label %indirectgoto
+
+val_0:
+  store i32 12, i32* %ret, align 4
+  br label %end
+
+val_1:
+  store i32 42, i32* %ret, align 4
+  br label %end
+
+end:
+  %2 = load i32, i32* %ret, align 4
+  ret i32 %2
+
+indirectgoto:
+  %indirect.goto.dest = phi i8* [ %1, %if.end ]
+  indirectbr i8* %indirect.goto.dest, [label %val_0, label %val_1]
+}
+
diff --git a/llvm/test/Transforms/MergeFunc/no-merge-block-address-different-labels.ll b/llvm/test/Transforms/MergeFunc/no-merge-block-address-different-labels.ll
new file mode 100644
index 00000000000..3024a9a76a7
--- /dev/null
+++ b/llvm/test/Transforms/MergeFunc/no-merge-block-address-different-labels.ll
@@ -0,0 +1,96 @@
+; RUN: opt -S -mergefunc < %s | FileCheck %s
+
+; There is a slight different in these two functions, in that the label values
+; are switched. They are thus not mergeable. This tests that block addresses
+; referring to blocks within each respective compared function are correctly
+; ordered.
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; Function Attrs: nounwind uwtable
+define i32 @_Z1fi(i32 %i) #0 {
+; CHECK-LABEL: define i32 @_Z1fi
+; CHECK-NEXT: entry:
+; CHECK-NEXT: alloca
+entry:
+  %i.addr = alloca i32, align 4
+  %ret = alloca i32, align 4
+  %l = alloca i8*, align 8
+  store i32 %i, i32* %i.addr, align 4
+  store i32 0, i32* %ret, align 4
+; Right here, this is val_0, and later the if might assign val_1
+  store i8* blockaddress(@_Z1fi, %val_0), i8** %l, align 8
+  %0 = load i32, i32* %i.addr, align 4
+  %and = and i32 %0, 256
+  %cmp = icmp eq i32 %and, 0
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:
+  store i8* blockaddress(@_Z1fi, %val_1), i8** %l, align 8
+  br label %if.end
+
+if.end:
+  %1 = load i8*, i8** %l, align 8
+  br label %indirectgoto
+
+val_0:
+  store i32 12, i32* %ret, align 4
+  br label %end
+
+val_1:
+  store i32 42, i32* %ret, align 4
+  br label %end
+
+end:
+  %2 = load i32, i32* %ret, align 4
+  ret i32 %2
+
+indirectgoto:
+  %indirect.goto.dest = phi i8* [ %1, %if.end ]
+  indirectbr i8* %indirect.goto.dest, [label %val_0, label %val_1]
+}
+
+; Function Attrs: nounwind uwtable
+define i32 @_Z1gi(i32 %i) #0 {
+; CHECK-LABEL: define i32 @_Z1gi
+; CHECK-NEXT: entry:
+; CHECK-NEXT: alloca
+entry:
+  %i.addr = alloca i32, align 4
+  %ret = alloca i32, align 4
+  %l = alloca i8*, align 8
+  store i32 %i, i32* %i.addr, align 4
+  store i32 0, i32* %ret, align 4
+; This time, we store val_1 initially, and later the if might assign val_0
+  store i8* blockaddress(@_Z1gi, %val_1), i8** %l, align 8
+  %0 = load i32, i32* %i.addr, align 4
+  %and = and i32 %0, 256
+  %cmp = icmp eq i32 %and, 0
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:
+  store i8* blockaddress(@_Z1gi, %val_0), i8** %l, align 8
+  br label %if.end
+
+if.end:
+  %1 = load i8*, i8** %l, align 8
+  br label %indirectgoto
+
+val_0:
+  store i32 12, i32* %ret, align 4
+  br label %end
+
+val_1:
+  store i32 42, i32* %ret, align 4
+  br label %end
+
+end:
+  %2 = load i32, i32* %ret, align 4
+  ret i32 %2
+
+indirectgoto:
+  %indirect.goto.dest = phi i8* [ %1, %if.end ]
+  indirectbr i8* %indirect.goto.dest, [label %val_1, label %val_0]
+}
+
diff --git a/llvm/test/Transforms/MergeFunc/no-merge-block-address-other-function.ll b/llvm/test/Transforms/MergeFunc/no-merge-block-address-other-function.ll
new file mode 100644
index 00000000000..e1aa30ac55a
--- /dev/null
+++ b/llvm/test/Transforms/MergeFunc/no-merge-block-address-other-function.ll
@@ -0,0 +1,61 @@
+; RUN: opt -S -mergefunc < %s | FileCheck %s
+
+; We should not merge these two functions, because the blocks are different.
+; This tests the handling of block addresses from different functions.
+; ModuleID = '<stdin>'
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+
+define internal i8* @Afunc(i32* %P) {
+; CHECK-LABEL: @Afunc
+; CHECK-NEXT: store
+; CHECK-NEXT: store
+; CHECK-NEXT: ret
+  store i32 1, i32* %P
+  store i32 3, i32* %P
+  ret i8* blockaddress(@_Z1fi, %if.then)
+}
+
+define internal i8* @Bfunc(i32* %P) {
+; CHECK-LABEL: @Bfunc
+; CHECK-NEXT: store
+; CHECK-NEXT: store
+; CHECK-NEXT: ret
+  store i32 1, i32* %P
+  store i32 3, i32* %P
+  ret i8* blockaddress(@_Z1fi, %if.then.2)
+}
+
+
+; Function Attrs: nounwind uwtable
+define i32 @_Z1fi(i32 %i) #0 {
+entry:
+  %retval = alloca i32, align 4
+  %i.addr = alloca i32, align 4
+  store i32 %i, i32* %i.addr, align 4
+  %0 = load i32, i32* %i.addr, align 4
+  %cmp = icmp eq i32 %0, 1
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:
+  store i32 3, i32* %retval
+  br label %return
+
+if.end:
+  %1 = load i32, i32* %i.addr, align 4
+  %cmp1 = icmp eq i32 %1, 3
+  br i1 %cmp1, label %if.then.2, label %if.end.3
+
+if.then.2:
+  store i32 56, i32* %retval
+  br label %return
+
+if.end.3:
+  store i32 0, i32* %retval
+  br label %return
+
+return:
+  %2 = load i32, i32* %retval
+  ret i32 %2
+}
diff --git a/llvm/test/Transforms/MergeFunc/ranges-multiple.ll b/llvm/test/Transforms/MergeFunc/ranges-multiple.ll
new file mode 100644
index 00000000000..bfa775d217a
--- /dev/null
+++ b/llvm/test/Transforms/MergeFunc/ranges-multiple.ll
@@ -0,0 +1,44 @@
+; RUN: opt -mergefunc -S < %s | FileCheck %s
+define i1 @cmp_with_range(i8*, i8*) {
+  %v1 = load i8, i8* %0, !range !0
+  %v2 = load i8, i8* %1, !range !0
+  %out = icmp eq i8 %v1, %v2
+  ret i1 %out
+}
+
+define i1 @cmp_no_range(i8*, i8*) {
+; CHECK-LABEL: @cmp_no_range
+; CHECK-NEXT: %v1 = load i8, i8* %0
+; CHECK-NEXT:  %v2 = load i8, i8* %1
+; CHECK-NEXT:  %out = icmp eq i8 %v1, %v2
+; CHECK-NEXT:  ret i1 %out
+  %v1 = load i8, i8* %0
+  %v2 = load i8, i8* %1
+  %out = icmp eq i8 %v1, %v2
+  ret i1 %out
+}
+
+define i1 @cmp_different_range(i8*, i8*) {
+; CHECK-LABEL: @cmp_different_range
+; CHECK-NEXT:  %v1 = load i8, i8* %0, !range !1
+; CHECK-NEXT:  %v2 = load i8, i8* %1, !range !1
+; CHECK-NEXT:  %out = icmp eq i8 %v1, %v2
+; CHECK-NEXT:  ret i1 %out
+  %v1 = load i8, i8* %0, !range !1
+  %v2 = load i8, i8* %1, !range !1
+  %out = icmp eq i8 %v1, %v2
+  ret i1 %out
+}
+
+define i1 @cmp_with_same_range(i8*, i8*) {
+; CHECK-LABEL: @cmp_with_same_range
+; CHECK: tail call i1 @cmp_with_range
+  %v1 = load i8, i8* %0, !range !0
+  %v2 = load i8, i8* %1, !range !0
+  %out = icmp eq i8 %v1, %v2
+  ret i1 %out
+}
+
+; The comparison must check every element of the range, not just the first pair.
+!0 = !{i8 0, i8 2, i8 21, i8 30}
+!1 = !{i8 0, i8 2, i8 21, i8 25}