diff options
| author | Cameron Zwarich <zwarich@apple.com> | 2011-02-21 00:22:02 +0000 |
|---|---|---|
| committer | Cameron Zwarich <zwarich@apple.com> | 2011-02-21 00:22:02 +0000 |
| commit | 8d7285d0e5eb5937a6682e884b883516377e903d (patch) | |
| tree | ccf0591dff9fa8874d00e480674cd7e77c84bbdf | |
| parent | 0b85d07d4611e7d704bf6550fbc624aff36a53b4 (diff) | |
| download | llvm-8d7285d0e5eb5937a6682e884b883516377e903d.tar.gz llvm-8d7285d0e5eb5937a6682e884b883516377e903d.tar.bz2 llvm-8d7285d0e5eb5937a6682e884b883516377e903d.tar.xz | |
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
| -rw-r--r-- | lib/Support/APInt.cpp | 2 | ||||
| -rw-r--r-- | lib/Target/X86/README.txt | 10 | ||||
| -rw-r--r-- | test/CodeGen/X86/divide-by-constant.ll | 2 | ||||
| -rw-r--r-- | 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 77033428b5..08f36d2af3 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 c10e1709f6..ed3bff150b 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 7ceb972f61..fe335b9369 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 557d835bac..e05bdbfc71 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) { |