diff options
author | Andrew Lenharth <andrewl@lenharth.org> | 2006-04-02 20:13:57 +0000 |
---|---|---|
committer | Andrew Lenharth <andrewl@lenharth.org> | 2006-04-02 20:13:57 +0000 |
commit | ed5d1afffb08bc389a0ae4e5c7382dee4d6f6f10 (patch) | |
tree | 1921a25bf012695d1905bd6aee93a221906a1dc2 /lib/Target/Alpha/AlphaISelLowering.cpp | |
parent | 0c5f7931d936bfebda65e0d3b4834c8d73b37496 (diff) | |
download | llvm-ed5d1afffb08bc389a0ae4e5c7382dee4d6f6f10.tar.gz llvm-ed5d1afffb08bc389a0ae4e5c7382dee4d6f6f10.tar.bz2 llvm-ed5d1afffb08bc389a0ae4e5c7382dee4d6f6f10.tar.xz |
This will be needed soon
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@27362 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib/Target/Alpha/AlphaISelLowering.cpp')
-rw-r--r-- | lib/Target/Alpha/AlphaISelLowering.cpp | 147 |
1 files changed, 146 insertions, 1 deletions
diff --git a/lib/Target/Alpha/AlphaISelLowering.cpp b/lib/Target/Alpha/AlphaISelLowering.cpp index b0d5be3e78..3eb38e6451 100644 --- a/lib/Target/Alpha/AlphaISelLowering.cpp +++ b/lib/Target/Alpha/AlphaISelLowering.cpp @@ -25,6 +25,151 @@ #include <iostream> using namespace llvm; +//Shamelessly adapted from PPC32 +// Structure used to return the necessary information to codegen an SDIV as +// a multiply. +struct ms { + int64_t m; // magic number + int64_t s; // shift amount +}; + +struct mu { + uint64_t m; // magic number + int64_t a; // add indicator + int64_t s; // shift amount +}; + +/// magic - calculate the magic numbers required to codegen an integer sdiv as +/// a sequence of multiply and shifts. Requires that the divisor not be 0, 1, +/// or -1. +static struct ms magic(int64_t d) { + int64_t p; + uint64_t ad, anc, delta, q1, r1, q2, r2, t; + const uint64_t two63 = 9223372036854775808ULL; // 2^63 + struct ms mag; + + ad = llabs(d); + t = two63 + ((uint64_t)d >> 63); + anc = t - 1 - t%ad; // absolute value of nc + p = 63; // initialize p + q1 = two63/anc; // initialize q1 = 2p/abs(nc) + r1 = two63 - q1*anc; // initialize r1 = rem(2p,abs(nc)) + q2 = two63/ad; // initialize q2 = 2p/abs(d) + r2 = two63 - q2*ad; // initialize r2 = rem(2p,abs(d)) + do { + p = p + 1; + q1 = 2*q1; // update q1 = 2p/abs(nc) + r1 = 2*r1; // update r1 = rem(2p/abs(nc)) + if (r1 >= anc) { // must be unsigned comparison + q1 = q1 + 1; + r1 = r1 - anc; + } + q2 = 2*q2; // update q2 = 2p/abs(d) + r2 = 2*r2; // update r2 = rem(2p/abs(d)) + if (r2 >= ad) { // must be unsigned comparison + q2 = q2 + 1; + r2 = r2 - ad; + } + delta = ad - r2; + } while (q1 < delta || (q1 == delta && r1 == 0)); + + mag.m = q2 + 1; + if (d < 0) mag.m = -mag.m; // resulting magic number + mag.s = p - 64; // resulting shift + return mag; +} + +/// magicu - calculate the magic numbers required to codegen an integer udiv as +/// a sequence of multiply, add and shifts. Requires that the divisor not be 0. +static struct mu magicu(uint64_t d) +{ + int64_t p; + uint64_t nc, delta, q1, r1, q2, r2; + struct mu magu; + magu.a = 0; // initialize "add" indicator + nc = - 1 - (-d)%d; + p = 63; // initialize p + q1 = 0x8000000000000000ull/nc; // initialize q1 = 2p/nc + r1 = 0x8000000000000000ull - q1*nc; // initialize r1 = rem(2p,nc) + q2 = 0x7FFFFFFFFFFFFFFFull/d; // initialize q2 = (2p-1)/d + r2 = 0x7FFFFFFFFFFFFFFFull - q2*d; // initialize r2 = rem((2p-1),d) + do { + p = p + 1; + if (r1 >= nc - r1 ) { + q1 = 2*q1 + 1; // update q1 + r1 = 2*r1 - nc; // update r1 + } + else { + q1 = 2*q1; // update q1 + r1 = 2*r1; // update r1 + } + if (r2 + 1 >= d - r2) { + if (q2 >= 0x7FFFFFFFFFFFFFFFull) magu.a = 1; + q2 = 2*q2 + 1; // update q2 + r2 = 2*r2 + 1 - d; // update r2 + } + else { + if (q2 >= 0x8000000000000000ull) magu.a = 1; + q2 = 2*q2; // update q2 + r2 = 2*r2 + 1; // update r2 + } + delta = d - 1 - r2; + } while (p < 64 && (q1 < delta || (q1 == delta && r1 == 0))); + magu.m = q2 + 1; // resulting magic number + magu.s = p - 64; // resulting shift + return magu; +} + +/// 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: +/// <http://the.wall.riscom.net/books/proc/ppc/cwg/code2.html> +static SDOperand BuildSDIVSequence(SDOperand N, SelectionDAG* ISelDAG) { + int64_t d = (int64_t)cast<ConstantSDNode>(N.getOperand(1))->getSignExtended(); + ms magics = magic(d); + // Multiply the numerator (operand 0) by the magic value + SDOperand Q = ISelDAG->getNode(ISD::MULHS, MVT::i64, N.getOperand(0), + ISelDAG->getConstant(magics.m, MVT::i64)); + // If d > 0 and m < 0, add the numerator + if (d > 0 && magics.m < 0) + Q = ISelDAG->getNode(ISD::ADD, MVT::i64, Q, N.getOperand(0)); + // If d < 0 and m > 0, subtract the numerator. + if (d < 0 && magics.m > 0) + Q = ISelDAG->getNode(ISD::SUB, MVT::i64, Q, N.getOperand(0)); + // Shift right algebraic if shift value is nonzero + if (magics.s > 0) + Q = ISelDAG->getNode(ISD::SRA, MVT::i64, Q, + ISelDAG->getConstant(magics.s, MVT::i64)); + // Extract the sign bit and add it to the quotient + SDOperand T = + ISelDAG->getNode(ISD::SRL, MVT::i64, Q, ISelDAG->getConstant(63, MVT::i64)); + return ISelDAG->getNode(ISD::ADD, MVT::i64, Q, T); +} + +/// BuildUDIVSequence - Given an ISD::UDIV 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: +/// <http://the.wall.riscom.net/books/proc/ppc/cwg/code2.html> +static SDOperand BuildUDIVSequence(SDOperand N, SelectionDAG* ISelDAG) { + unsigned d = + (unsigned)cast<ConstantSDNode>(N.getOperand(1))->getSignExtended(); + mu magics = magicu(d); + // Multiply the numerator (operand 0) by the magic value + SDOperand Q = ISelDAG->getNode(ISD::MULHU, MVT::i64, N.getOperand(0), + ISelDAG->getConstant(magics.m, MVT::i64)); + if (magics.a == 0) { + Q = ISelDAG->getNode(ISD::SRL, MVT::i64, Q, + ISelDAG->getConstant(magics.s, MVT::i64)); + } else { + SDOperand NPQ = ISelDAG->getNode(ISD::SUB, MVT::i64, N.getOperand(0), Q); + NPQ = ISelDAG->getNode(ISD::SRL, MVT::i64, NPQ, + ISelDAG->getConstant(1, MVT::i64)); + NPQ = ISelDAG->getNode(ISD::ADD, MVT::i64, NPQ, Q); + Q = ISelDAG->getNode(ISD::SRL, MVT::i64, NPQ, + ISelDAG->getConstant(magics.s-1, MVT::i64)); + } + return Q; +} /// AddLiveIn - This helper function adds the specified physical register to the /// MachineFunction as a live in value. It also creates a corresponding virtual @@ -283,7 +428,7 @@ AlphaTargetLowering::LowerArguments(Function &F, SelectionDAG &DAG) break; } - //return the arguments + //return the arguments+ return ArgValues; } |