From 8f820e94954d2120055a4c7bfafb3c913fa0295a Mon Sep 17 00:00:00 2001
From: Benjamin Kramer <benny.kra@googlemail.com>
Date: Thu, 26 Mar 2015 17:12:06 +0000
Subject: [PATCH] InstCombine: fold (A << C) == (B << C) --> ((A^B) & (~0U >>
 C)) == 0

Anding and comparing with zero can be done in a single instruction on
most archs so this is a bit cheaper.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@233291 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Target/README.txt                         | 38 -------------------
 .../InstCombine/InstCombineCompares.cpp       | 15 ++++++++
 test/Transforms/InstCombine/icmp.ll           | 30 +++++++++++++++
 3 files changed, 45 insertions(+), 38 deletions(-)

diff --git a/lib/Target/README.txt b/lib/Target/README.txt
index 52a334a6174..282d9234c1a 100644
--- a/lib/Target/README.txt
+++ b/lib/Target/README.txt
@@ -1844,44 +1844,6 @@ we remove checking in code like
 
 //===---------------------------------------------------------------------===//
 
-This code (from Benchmarks/Dhrystone/dry.c):
-
-define i32 @Func1(i32, i32) nounwind readnone optsize ssp {
-entry:
-  %sext = shl i32 %0, 24
-  %conv = ashr i32 %sext, 24
-  %sext6 = shl i32 %1, 24
-  %conv4 = ashr i32 %sext6, 24
-  %cmp = icmp eq i32 %conv, %conv4
-  %. = select i1 %cmp, i32 10000, i32 0
-  ret i32 %.
-}
-
-Should be simplified into something like:
-
-define i32 @Func1(i32, i32) nounwind readnone optsize ssp {
-entry:
-  %sext = shl i32 %0, 24
-  %conv = and i32 %sext, 0xFF000000
-  %sext6 = shl i32 %1, 24
-  %conv4 = and i32 %sext6, 0xFF000000
-  %cmp = icmp eq i32 %conv, %conv4
-  %. = select i1 %cmp, i32 10000, i32 0
-  ret i32 %.
-}
-
-and then to:
-
-define i32 @Func1(i32, i32) nounwind readnone optsize ssp {
-entry:
-  %conv = and i32 %0, 0xFF
-  %conv4 = and i32 %1, 0xFF
-  %cmp = icmp eq i32 %conv, %conv4
-  %. = select i1 %cmp, i32 10000, i32 0
-  ret i32 %.
-}
-//===---------------------------------------------------------------------===//
-
 clang -O3 currently compiles this code
 
 int g(unsigned int a) {
diff --git a/lib/Transforms/InstCombine/InstCombineCompares.cpp b/lib/Transforms/InstCombine/InstCombineCompares.cpp
index 3434a62d9e1..803b50a88e5 100644
--- a/lib/Transforms/InstCombine/InstCombineCompares.cpp
+++ b/lib/Transforms/InstCombine/InstCombineCompares.cpp
@@ -3553,6 +3553,21 @@ Instruction *InstCombiner::visitICmpInst(ICmpInst &I) {
       }
     }
 
+    // (A << C) == (B << C) --> ((A^B) & (~0U >> C)) == 0
+    if (match(Op0, m_OneUse(m_Shl(m_Value(A), m_ConstantInt(Cst1)))) &&
+        match(Op1, m_OneUse(m_Shl(m_Value(B), m_Specific(Cst1))))) {
+      unsigned TypeBits = Cst1->getBitWidth();
+      unsigned ShAmt = (unsigned)Cst1->getLimitedValue(TypeBits);
+      if (ShAmt < TypeBits && ShAmt != 0) {
+        Value *Xor = Builder->CreateXor(A, B, I.getName() + ".unshifted");
+        APInt AndVal = APInt::getLowBitsSet(TypeBits, TypeBits - ShAmt);
+        Value *And = Builder->CreateAnd(Xor, Builder->getInt(AndVal),
+                                        I.getName() + ".mask");
+        return new ICmpInst(I.getPredicate(), And,
+                            Constant::getNullValue(Cst1->getType()));
+      }
+    }
+
     // Transform "icmp eq (trunc (lshr(X, cst1)), cst" to
     // "icmp (and X, mask), cst"
     uint64_t ShAmt = 0;
diff --git a/test/Transforms/InstCombine/icmp.ll b/test/Transforms/InstCombine/icmp.ll
index dd109837a40..edcf76d5a7d 100644
--- a/test/Transforms/InstCombine/icmp.ll
+++ b/test/Transforms/InstCombine/icmp.ll
@@ -1573,3 +1573,33 @@ define i32 @f5(i8 %a, i8 %b) {
   %sub7.sub = select i1 %cmp4, i32 %sub7, i32 %sub
   ret i32 %sub7.sub
 }
+
+; CHECK-LABEL: @f6
+; CHECK: %cmp.unshifted = xor i32 %a, %b
+; CHECK-NEXT: %cmp.mask = and i32 %cmp.unshifted, 255
+; CHECK-NEXT: %cmp = icmp eq i32 %cmp.mask, 0
+; CHECK-NEXT: %s = select i1 %cmp, i32 10000, i32 0
+; CHECK-NEXT: ret i32 %s
+define i32 @f6(i32 %a, i32 %b) {
+  %sext = shl i32 %a, 24
+  %conv = ashr i32 %sext, 24
+  %sext6 = shl i32 %b, 24
+  %conv4 = ashr i32 %sext6, 24
+  %cmp = icmp eq i32 %conv, %conv4
+  %s = select i1 %cmp, i32 10000, i32 0
+  ret i32 %s
+}
+
+; CHECK-LABEL: @f7
+; CHECK:   %cmp.unshifted = xor i32 %a, %b
+; CHECK-NEXT: %cmp.mask = and i32 %cmp.unshifted, 511
+; CHECK-NEXT: %cmp = icmp ne i32 %cmp.mask, 0
+; CHECK-NEXT: %s = select i1 %cmp, i32 10000, i32 0
+; CHECK-NEXT: ret i32 %s
+define i32 @f7(i32 %a, i32 %b) {
+  %sext = shl i32 %a, 23
+  %sext6 = shl i32 %b, 23
+  %cmp = icmp ne i32 %sext, %sext6
+  %s = select i1 %cmp, i32 10000, i32 0
+  ret i32 %s
+}
-- 
2.34.1