From 9753f0b9b4ab33919c5010acb6a7b2dc1e875aff Mon Sep 17 00:00:00 2001 From: Nadav Rotem Date: Tue, 28 Aug 2012 10:01:43 +0000 Subject: Teach InstCombine to canonicalize [SU]div+[AL]shl patterns. For example: %1 = lshr i32 %x, 2 %2 = udiv i32 %1, 100 rdar://12182093 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162743 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/InstCombine/InstCombineMulDivRem.cpp | 20 ++++++++++++++++++++ 1 file changed, 20 insertions(+) (limited to 'lib/Transforms/InstCombine/InstCombineMulDivRem.cpp') diff --git a/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp b/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp index 35a0bbb..e104a0a 100644 --- a/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp +++ b/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp @@ -462,6 +462,16 @@ Instruction *InstCombiner::visitUDiv(BinaryOperator &I) { } } + // Udiv ((Lshl x, c1) , c2) -> x / (C1 * 1<(Op1)) { + Value *X = 0, *C1 = 0; + if (match(Op0, m_LShr(m_Value(X), m_Value(C1)))) { + uint64_t NC = cast(C)->getZExtValue() * + (1<< cast(C1)->getZExtValue()); + return BinaryOperator::CreateUDiv(X, ConstantInt::get(I.getType(), NC)); + } + } + // X udiv (C1 << N), where C1 is "1< X >> (N+C2) { const APInt *CI; Value *N; if (match(Op1, m_Shl(m_Power2(CI), m_Value(N))) || @@ -533,6 +543,16 @@ Instruction *InstCombiner::visitSDiv(BinaryOperator &I) { ConstantExpr::getNeg(RHS)); } + // Sdiv ((Ashl x, c1) , c2) -> x / (C1 * 1<(Op1)) { + Value *X = 0, *C1 = 0; + if (match(Op0, m_AShr(m_Value(X), m_Value(C1)))) { + uint64_t NC = cast(C)->getZExtValue() * + (1<< cast(C1)->getZExtValue()); + return BinaryOperator::CreateSDiv(X, ConstantInt::get(I.getType(), NC)); + } + } + // If the sign bits of both operands are zero (i.e. we can prove they are // unsigned inputs), turn this into a udiv. if (I.getType()->isIntegerTy()) { -- cgit v1.1 From a694e2a6910a33596ca706e2c6fc713f02b64c50 Mon Sep 17 00:00:00 2001 From: Nadav Rotem Date: Tue, 28 Aug 2012 12:23:22 +0000 Subject: Make sure that we don't call getZExtValue on values > 64 bits. Thanks Benjamin for noticing this. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162749 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/InstCombine/InstCombineMulDivRem.cpp | 16 ++++++++-------- 1 file changed, 8 insertions(+), 8 deletions(-) (limited to 'lib/Transforms/InstCombine/InstCombineMulDivRem.cpp') diff --git a/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp b/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp index e104a0a..5eba463 100644 --- a/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp +++ b/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp @@ -462,11 +462,11 @@ Instruction *InstCombiner::visitUDiv(BinaryOperator &I) { } } - // Udiv ((Lshl x, c1) , c2) -> x / (C1 * 1<(Op1)) { + // Udiv ((Lshl x, C1) , C2) -> x / (C2 * 1<(Op1)) { Value *X = 0, *C1 = 0; - if (match(Op0, m_LShr(m_Value(X), m_Value(C1)))) { - uint64_t NC = cast(C)->getZExtValue() * + if (match(Op0, m_LShr(m_Value(X), m_Value(C1))) && C2->getBitWidth() < 65) { + uint64_t NC = cast(C2)->getZExtValue() * (1<< cast(C1)->getZExtValue()); return BinaryOperator::CreateUDiv(X, ConstantInt::get(I.getType(), NC)); } @@ -543,11 +543,11 @@ Instruction *InstCombiner::visitSDiv(BinaryOperator &I) { ConstantExpr::getNeg(RHS)); } - // Sdiv ((Ashl x, c1) , c2) -> x / (C1 * 1<(Op1)) { + // Sdiv ((Ashl x, C1) , C2) -> x / (C2 * 1<(Op1)) { Value *X = 0, *C1 = 0; - if (match(Op0, m_AShr(m_Value(X), m_Value(C1)))) { - uint64_t NC = cast(C)->getZExtValue() * + if (match(Op0, m_AShr(m_Value(X), m_Value(C1))) && C2->getBitWidth() < 65) { + uint64_t NC = cast(C2)->getZExtValue() * (1<< cast(C1)->getZExtValue()); return BinaryOperator::CreateSDiv(X, ConstantInt::get(I.getType(), NC)); } -- cgit v1.1 From aac7c650a6cac09d42c5fda8d3761bc9c871ff03 Mon Sep 17 00:00:00 2001 From: Benjamin Kramer Date: Tue, 28 Aug 2012 13:08:13 +0000 Subject: InstCombine: Guard the transform introduced in r162743 against large ints and non-const shifts. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162751 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/InstCombine/InstCombineMulDivRem.cpp | 20 ++++++++++---------- 1 file changed, 10 insertions(+), 10 deletions(-) (limited to 'lib/Transforms/InstCombine/InstCombineMulDivRem.cpp') diff --git a/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp b/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp index 5eba463..65a64b8 100644 --- a/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp +++ b/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp @@ -464,11 +464,11 @@ Instruction *InstCombiner::visitUDiv(BinaryOperator &I) { // Udiv ((Lshl x, C1) , C2) -> x / (C2 * 1<(Op1)) { - Value *X = 0, *C1 = 0; - if (match(Op0, m_LShr(m_Value(X), m_Value(C1))) && C2->getBitWidth() < 65) { - uint64_t NC = cast(C2)->getZExtValue() * - (1<< cast(C1)->getZExtValue()); - return BinaryOperator::CreateUDiv(X, ConstantInt::get(I.getType(), NC)); + Value *X; + ConstantInt *C1; + if (match(Op0, m_LShr(m_Value(X), m_ConstantInt(C1)))) { + APInt NC = C2->getValue().shl(C1->getZExtValue()); + return BinaryOperator::CreateUDiv(X, Builder->getInt(NC)); } } @@ -545,11 +545,11 @@ Instruction *InstCombiner::visitSDiv(BinaryOperator &I) { // Sdiv ((Ashl x, C1) , C2) -> x / (C2 * 1<(Op1)) { - Value *X = 0, *C1 = 0; - if (match(Op0, m_AShr(m_Value(X), m_Value(C1))) && C2->getBitWidth() < 65) { - uint64_t NC = cast(C2)->getZExtValue() * - (1<< cast(C1)->getZExtValue()); - return BinaryOperator::CreateSDiv(X, ConstantInt::get(I.getType(), NC)); + Value *X; + ConstantInt *C1; + if (match(Op0, m_AShr(m_Value(X), m_ConstantInt(C1)))) { + APInt NC = C2->getValue().shl(C1->getZExtValue()); + return BinaryOperator::CreateSDiv(X, Builder->getInt(NC)); } } -- cgit v1.1 From 37dca6331d6bfadfb80b3c68a1cabd6bdf1a13be Mon Sep 17 00:00:00 2001 From: Benjamin Kramer Date: Tue, 28 Aug 2012 13:59:23 +0000 Subject: InstCombine: Defensively avoid undefined shifts by limiting the amount to the bit width. No test case, undefined shifts get folded early, but can occur when other transforms generate a constant. Thanks to Duncan for bringing this up. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162755 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/InstCombine/InstCombineMulDivRem.cpp | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'lib/Transforms/InstCombine/InstCombineMulDivRem.cpp') diff --git a/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp b/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp index 65a64b8..2119115 100644 --- a/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp +++ b/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp @@ -467,7 +467,7 @@ Instruction *InstCombiner::visitUDiv(BinaryOperator &I) { Value *X; ConstantInt *C1; if (match(Op0, m_LShr(m_Value(X), m_ConstantInt(C1)))) { - APInt NC = C2->getValue().shl(C1->getZExtValue()); + APInt NC = C2->getValue().shl(C1->getLimitedValue(C1->getBitWidth()-1)); return BinaryOperator::CreateUDiv(X, Builder->getInt(NC)); } } @@ -548,7 +548,7 @@ Instruction *InstCombiner::visitSDiv(BinaryOperator &I) { Value *X; ConstantInt *C1; if (match(Op0, m_AShr(m_Value(X), m_ConstantInt(C1)))) { - APInt NC = C2->getValue().shl(C1->getZExtValue()); + APInt NC = C2->getValue().shl(C1->getLimitedValue(C1->getBitWidth()-1)); return BinaryOperator::CreateSDiv(X, Builder->getInt(NC)); } } -- cgit v1.1 From 639570c3117aaabb0c97b34a9bf05d09f8903ef4 Mon Sep 17 00:00:00 2001 From: Nadav Rotem Date: Thu, 30 Aug 2012 11:23:20 +0000 Subject: It is illegal to transform (sdiv (ashr X c1) c2) -> (sdiv x (2^c1 * c2)), because C always rounds towards zero. Thanks Dirk and Ben. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162899 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/InstCombine/InstCombineMulDivRem.cpp | 10 ---------- 1 file changed, 10 deletions(-) (limited to 'lib/Transforms/InstCombine/InstCombineMulDivRem.cpp') diff --git a/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp b/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp index 2119115..003dc55 100644 --- a/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp +++ b/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp @@ -543,16 +543,6 @@ Instruction *InstCombiner::visitSDiv(BinaryOperator &I) { ConstantExpr::getNeg(RHS)); } - // Sdiv ((Ashl x, C1) , C2) -> x / (C2 * 1<(Op1)) { - Value *X; - ConstantInt *C1; - if (match(Op0, m_AShr(m_Value(X), m_ConstantInt(C1)))) { - APInt NC = C2->getValue().shl(C1->getLimitedValue(C1->getBitWidth()-1)); - return BinaryOperator::CreateSDiv(X, Builder->getInt(NC)); - } - } - // If the sign bits of both operands are zero (i.e. we can prove they are // unsigned inputs), turn this into a udiv. if (I.getType()->isIntegerTy()) { -- cgit v1.1 From c81fe9cab545a93a61c059b1c2813f622aef43ae Mon Sep 17 00:00:00 2001 From: Benjamin Kramer Date: Thu, 30 Aug 2012 15:07:40 +0000 Subject: InstCombine: Fix comment to reflect the code. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162911 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/InstCombine/InstCombineMulDivRem.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib/Transforms/InstCombine/InstCombineMulDivRem.cpp') diff --git a/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp b/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp index 003dc55..2a7182f 100644 --- a/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp +++ b/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp @@ -462,7 +462,7 @@ Instruction *InstCombiner::visitUDiv(BinaryOperator &I) { } } - // Udiv ((Lshl x, C1) , C2) -> x / (C2 * 1< x udiv (C2 << C1) if (ConstantInt *C2 = dyn_cast(Op1)) { Value *X; ConstantInt *C1; -- cgit v1.1