From 8d7285d0e5eb5937a6682e884b883516377e903d Mon Sep 17 00:00:00 2001
From: Cameron Zwarich <zwarich@apple.com>
Date: Mon, 21 Feb 2011 00:22:02 +0000
Subject: [PATCH] The signed version of our "magic number" computation for the
 integer approximation of a constant had a minor typo introduced when copying
 it from the book, which caused it to favor negative approximations over
 positive approximations in many cases. Positive approximations require fewer
 operations beyond the multiplication.

In the case of division by 3, we still generate code that is a single instruction
larger than GCC's code.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@126097 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Support/APInt.cpp                  |  2 +-
 lib/Target/X86/README.txt              | 10 ++++------
 test/CodeGen/X86/divide-by-constant.ll |  2 +-
 unittests/ADT/APIntTest.cpp            | 18 ++++++++++++++++++
 4 files changed, 24 insertions(+), 8 deletions(-)

diff --git a/lib/Support/APInt.cpp b/lib/Support/APInt.cpp
index 77033428b57..08f36d2af3a 100644
--- a/lib/Support/APInt.cpp
+++ b/lib/Support/APInt.cpp
@@ -1505,7 +1505,7 @@ APInt::ms APInt::magic() const {
       r2 = r2 - ad;
     }
     delta = ad - r2;
-  } while (q1.ule(delta) || (q1 == delta && r1 == 0));
+  } while (q1.ult(delta) || (q1 == delta && r1 == 0));
 
   mag.m = q2 + 1;
   if (d.isNegative()) mag.m = -mag.m;   // resulting magic number
diff --git a/lib/Target/X86/README.txt b/lib/Target/X86/README.txt
index c10e1709f66..ed3bff150bc 100644
--- a/lib/Target/X86/README.txt
+++ b/lib/Target/X86/README.txt
@@ -1888,12 +1888,10 @@ Compiles to: $clang t.c -S -o - -O3 -mkernel -fomit-frame-pointer
 
 _t:                                     ## @t
 	movslq	%edi, %rax
-	imulq	$-1431655765, %rax, %rcx ## imm = 0xFFFFFFFFAAAAAAAB
-	shrq	$32, %rcx
-	addl	%ecx, %eax
-	movl	%eax, %ecx
-	shrl	$31, %ecx
-	shrl	%eax
+	imulq	$1431655766, %rax, %rax ## imm = 0x55555556
+	movq	%rax, %rcx
+	shrq	$63, %rcx
+	shrq	$32, %rax
 	addl	%ecx, %eax
 	movsbl	%al, %eax
 	ret
diff --git a/test/CodeGen/X86/divide-by-constant.ll b/test/CodeGen/X86/divide-by-constant.ll
index 7ceb972f61b..fe335b9369c 100644
--- a/test/CodeGen/X86/divide-by-constant.ll
+++ b/test/CodeGen/X86/divide-by-constant.ll
@@ -40,7 +40,7 @@ entry:
 	%div = sdiv i16 %x, 33		; <i32> [#uses=1]
 	ret i16 %div
 ; CHECK: test4:
-; CHECK: imull	$-1985, %ecx, %ecx 
+; CHECK: imull	$1986, %eax, %eax 
 }
 
 define i32 @test5(i32 %A) nounwind {
diff --git a/unittests/ADT/APIntTest.cpp b/unittests/ADT/APIntTest.cpp
index 557d835bacd..e05bdbfc710 100644
--- a/unittests/ADT/APIntTest.cpp
+++ b/unittests/ADT/APIntTest.cpp
@@ -332,6 +332,24 @@ TEST(APIntTest, Log2) {
   EXPECT_EQ(APInt(15, 9).exactLogBase2(), -1);
 }
 
+TEST(APIntTest, magic) {
+  EXPECT_EQ(APInt(32, 3).magic().m, APInt(32, "55555556", 16));
+  EXPECT_EQ(APInt(32, 3).magic().s, 0U);
+  EXPECT_EQ(APInt(32, 5).magic().m, APInt(32, "66666667", 16));
+  EXPECT_EQ(APInt(32, 5).magic().s, 1U);
+  EXPECT_EQ(APInt(32, 7).magic().m, APInt(32, "92492493", 16));
+  EXPECT_EQ(APInt(32, 7).magic().s, 2U);
+}
+
+TEST(APIntTest, magicu) {
+  EXPECT_EQ(APInt(32, 3).magicu().m, APInt(32, "AAAAAAAB", 16));
+  EXPECT_EQ(APInt(32, 3).magicu().s, 1U);
+  EXPECT_EQ(APInt(32, 5).magicu().m, APInt(32, "CCCCCCCD", 16));
+  EXPECT_EQ(APInt(32, 5).magicu().s, 2U);
+  EXPECT_EQ(APInt(32, 7).magicu().m, APInt(32, "24924925", 16));
+  EXPECT_EQ(APInt(32, 7).magicu().s, 3U);
+}
+
 #ifdef GTEST_HAS_DEATH_TEST
 #ifndef NDEBUG
 TEST(APIntTest, StringDeath) {
-- 
2.11.0