[ValueTracking] Understand more select patterns in ComputeKnownBits

Some patterns of select+compare allow us to know exactly the value of the uppermost bits in the select result. For example:

  %b = icmp ugt i32 %a, 5
  %c = select i1 %b, i32 2, i32 %a

Here we know that %c is bounded by 5, and therefore KnownZero = ~APInt(5).getActiveBits() = ~7.

There are several such patterns, and this patch attempts to understand a reasonable subset of them - namely when the base values are the same (as above), and when they are related by a simple (add nsw), for example (add nsw %a, 4) and %a.

llvm-svn: 257769

1 files changed, 62 insertions, 0 deletions

diff --git a/llvm/test/Analysis/ValueTracking/select-maxbits.ll b/llvm/test/Analysis/ValueTracking/select-maxbits.ll
new file mode 100644
index 00000000000..4b121745048
--- /dev/null
+++ b/llvm/test/Analysis/ValueTracking/select-maxbits.ll
@@ -0,0 +1,62 @@
+; RUN: opt -S -instsimplify < %s | FileCheck %s
+
+; CHECK-LABEL: @one
+define i32 @one(i32 %a) {
+; CHECK: ret i32 0
+  %b = icmp ugt i32 %a, 5
+  %c = select i1 %b, i32 2, i32 %a
+  %d = lshr i32 %c, 24
+  ret i32 %d
+}
+
+; CHECK-LABEL: @two
+define i32 @two(i32 %a) {
+; CHECK: ret i32 0
+  %x = add nsw i32 %a, 4
+  %b = icmp ugt i32 %x, 5
+  %c = select i1 %b, i32 2, i32 %a
+  %d = lshr i32 %c, 24
+  ret i32 %d
+}
+
+; CHECK-LABEL: @two_no_nsw
+define i32 @two_no_nsw(i32 %a) {
+; CHECK: ret i32 %d
+  %x = add i32 %a, 4
+  %b = icmp ugt i32 %x, 5
+  %c = select i1 %b, i32 2, i32 %a
+  %d = lshr i32 %c, 24
+  ret i32 %d
+}
+
+; CHECK-LABEL: @three
+define i32 @three(i32 %a) {
+; CHECK: ret i32 0
+  %x = add nsw i32 %a, -4
+  %b = icmp ugt i32 %a, 5
+  %c = select i1 %b, i32 2, i32 %x
+  %d = lshr i32 %c, 24
+  ret i32 %d
+}
+
+; CHECK-LABEL: @four
+define i32 @four(i32 %a) {
+; CHECK: ret i32 0
+  %x = add nsw i32 %a, 42
+  %y = add nsw i32 %a, 64
+  %b = icmp ugt i32 %y, 5
+  %c = select i1 %b, i32 2, i32 %x
+  %d = lshr i32 %c, 24
+  ret i32 %d
+}
+
+; CHECK-LABEL: @four_swapped
+define i32 @four_swapped(i32 %a) {
+; CHECK: ret i32 %d
+  %x = add nsw i32 %a, 42
+  %y = add nsw i32 %a, 64
+  %b = icmp ugt i32 %x, 5
+  %c = select i1 %b, i32 2, i32 %y
+  %d = lshr i32 %c, 24
+  ret i32 %d
+}
\ No newline at end of file