From 9c64030445cbe6ac486b90c5f459f91e06770474 Mon Sep 17 00:00:00 2001 From: Benjamin Kramer Date: Fri, 8 Jul 2011 10:31:30 +0000 Subject: 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 --- lib/CodeGen/SelectionDAG/TargetLowering.cpp | 26 ++++++++++++++++++++++++++ 1 file changed, 26 insertions(+) (limited to 'lib/CodeGen/SelectionDAG/TargetLowering.cpp') diff --git a/lib/CodeGen/SelectionDAG/TargetLowering.cpp b/lib/CodeGen/SelectionDAG/TargetLowering.cpp index 91e2a4a..f827f01 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: -- cgit v1.1