From 9c64030445cbe6ac486b90c5f459f91e06770474 Mon Sep 17 00:00:00 2001 From: Benjamin Kramer Date: Fri, 8 Jul 2011 10:31:30 +0000 Subject: [PATCH] Emit a more efficient magic number multiplication for exact sdivs. We have to do this in DAGBuilder instead of DAGCombiner, because the exact bit is lost after building. struct foo { char x[24]; }; long bar(struct foo *a, struct foo *b) { return a-b; } is now compiled into movl 4(%esp), %eax subl 8(%esp), %eax sarl $3, %eax imull $-1431655765, %eax, %eax instead of movl 4(%esp), %eax subl 8(%esp), %eax movl $715827883, %ecx imull %ecx movl %edx, %eax shrl $31, %eax sarl $2, %edx addl %eax, %edx movl %edx, %eax git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@134695 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Target/TargetLowering.h | 2 ++ lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp | 16 +++++++++++++++ lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h | 2 +- lib/CodeGen/SelectionDAG/TargetLowering.cpp | 26 ++++++++++++++++++++++++ test/CodeGen/X86/sdiv-exact.ll | 18 ++++++++++++++++ 5 files changed, 63 insertions(+), 1 deletion(-) create mode 100644 test/CodeGen/X86/sdiv-exact.ll diff --git a/include/llvm/Target/TargetLowering.h b/include/llvm/Target/TargetLowering.h index f684163475b..533c3ac8784 100644 --- a/include/llvm/Target/TargetLowering.h +++ b/include/llvm/Target/TargetLowering.h @@ -1540,6 +1540,8 @@ public: //===--------------------------------------------------------------------===// // Div utility functions // + SDValue BuildExactSDIV(SDValue Op1, SDValue Op2, DebugLoc dl, + SelectionDAG &DAG) const; SDValue BuildSDIV(SDNode *N, SelectionDAG &DAG, std::vector* Created) const; SDValue BuildUDIV(SDNode *N, SelectionDAG &DAG, diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp index fc8f0d29964..2a362ebfc2d 100644 --- a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp +++ b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp @@ -2501,6 +2501,22 @@ void SelectionDAGBuilder::visitShift(const User &I, unsigned Opcode) { Op1.getValueType(), Op1, Op2)); } +void SelectionDAGBuilder::visitSDiv(const User &I) { + const BinaryOperator *BO = cast(&I); + SDValue Op1 = getValue(I.getOperand(0)); + SDValue Op2 = getValue(I.getOperand(1)); + + // Turn exact SDivs into multiplications. + // FIXME: This should be in DAGCombiner, but it doesn't have access to the + // exact bit. + if (BO->isExact() && !isa(Op1) && + isa(Op2) && !cast(Op2)->isNullValue()) + setValue(&I, TLI.BuildExactSDIV(Op1, Op2, getCurDebugLoc(), DAG)); + else + setValue(&I, DAG.getNode(ISD::SDIV, getCurDebugLoc(), Op1.getValueType(), + Op1, Op2)); +} + void SelectionDAGBuilder::visitICmp(const User &I) { ICmpInst::Predicate predicate = ICmpInst::BAD_ICMP_PREDICATE; if (const ICmpInst *IC = dyn_cast(&I)) diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h index a1ca8911484..a0884ebf5d5 100644 --- a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h +++ b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h @@ -467,7 +467,7 @@ private: void visitSRem(const User &I) { visitBinary(I, ISD::SREM); } void visitFRem(const User &I) { visitBinary(I, ISD::FREM); } void visitUDiv(const User &I) { visitBinary(I, ISD::UDIV); } - void visitSDiv(const User &I) { visitBinary(I, ISD::SDIV); } + void visitSDiv(const User &I); void visitFDiv(const User &I) { visitBinary(I, ISD::FDIV); } void visitAnd (const User &I) { visitBinary(I, ISD::AND); } void visitOr (const User &I) { visitBinary(I, ISD::OR); } diff --git a/lib/CodeGen/SelectionDAG/TargetLowering.cpp b/lib/CodeGen/SelectionDAG/TargetLowering.cpp index 91e2a4a3e36..f827f0124ce 100644 --- a/lib/CodeGen/SelectionDAG/TargetLowering.cpp +++ b/lib/CodeGen/SelectionDAG/TargetLowering.cpp @@ -3211,6 +3211,32 @@ bool TargetLowering::isLegalAddressingMode(const AddrMode &AM, return true; } +/// BuildExactDiv - Given an exact SDIV by a constant, create a multiplication +/// with the multiplicative inverse of the constant. +SDValue TargetLowering::BuildExactSDIV(SDValue Op1, SDValue Op2, DebugLoc dl, + SelectionDAG &DAG) const { + ConstantSDNode *C = cast(Op2); + APInt d = C->getAPIntValue(); + assert(d != 0 && "Division by zero!"); + + // Shift the value upfront if it is even, so the LSB is one. + unsigned ShAmt = d.countTrailingZeros(); + if (ShAmt) { + // TODO: For UDIV use SRL instead of SRA. + SDValue Amt = DAG.getConstant(ShAmt, getShiftAmountTy(Op1.getValueType())); + Op1 = DAG.getNode(ISD::SRA, dl, Op1.getValueType(), Op1, Amt); + d = d.ashr(ShAmt); + } + + // Calculate the multiplicative inverse, using Newton's method. + APInt t, xn = d; + while ((t = d*xn) != 1) + xn *= APInt(d.getBitWidth(), 2) - t; + + Op2 = DAG.getConstant(xn, Op1.getValueType()); + return DAG.getNode(ISD::MUL, dl, Op1.getValueType(), Op1, Op2); +} + /// BuildSDIVSequence - Given an ISD::SDIV node expressing a divide by constant, /// return a DAG expression to select that will generate the same value by /// multiplying by a magic number. See: diff --git a/test/CodeGen/X86/sdiv-exact.ll b/test/CodeGen/X86/sdiv-exact.ll new file mode 100644 index 00000000000..48bb8836e89 --- /dev/null +++ b/test/CodeGen/X86/sdiv-exact.ll @@ -0,0 +1,18 @@ +; RUN: llc -march=x86 < %s | FileCheck %s + +define i32 @test1(i32 %x) { + %div = sdiv exact i32 %x, 25 + ret i32 %div +; CHECK: test1: +; CHECK: imull $-1030792151, 4(%esp) +; CHECK-NEXT: ret +} + +define i32 @test2(i32 %x) { + %div = sdiv exact i32 %x, 24 + ret i32 %div +; CHECK: test2: +; CHECK: sarl $3 +; CHECK-NEXT: imull $-1431655765 +; CHECK-NEXT: ret +} -- 2.11.0