#include "llvm/Type.h"
#include "llvm/CodeGen/SelectionDAGNodes.h"
#include <map>
+#include <list>
namespace llvm {
class Value;
return LegalAddressScales.end();
}
+ //===--------------------------------------------------------------------===//
+ // Div utility functions
+ //
+ SDOperand BuildSDIV(SDNode *N, SelectionDAG &DAG,
+ std::list<SDNode*>* Created) const;
+ SDOperand BuildUDIV(SDNode *N, SelectionDAG &DAG,
+ std::list<SDNode*>* Created) const;
+
+
protected:
/// addLegalAddressScale - Add a integer (> 1) value which can be used as
/// scale in the target addressing mode. Note: the ordering matters so the
//===----------------------------------------------------------------------===//
-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 ms magic32(int32_t d) {
- int32_t p;
- uint32_t ad, anc, delta, q1, r1, q2, r2, t;
- const uint32_t two31 = 0x80000000U;
- struct ms mag;
-
- ad = abs(d);
- t = two31 + ((uint32_t)d >> 31);
- anc = t - 1 - t%ad; // absolute value of nc
- p = 31; // initialize p
- q1 = two31/anc; // initialize q1 = 2p/abs(nc)
- r1 = two31 - q1*anc; // initialize r1 = rem(2p,abs(nc))
- q2 = two31/ad; // initialize q2 = 2p/abs(d)
- r2 = two31 - 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 = (int32_t)(q2 + 1); // make sure to sign extend
- if (d < 0) mag.m = -mag.m; // resulting magic number
- mag.s = p - 32; // 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 mu magicu32(uint32_t d) {
- int32_t p;
- uint32_t nc, delta, q1, r1, q2, r2;
- struct mu magu;
- magu.a = 0; // initialize "add" indicator
- nc = - 1 - (-d)%d;
- p = 31; // initialize p
- q1 = 0x80000000/nc; // initialize q1 = 2p/nc
- r1 = 0x80000000 - q1*nc; // initialize r1 = rem(2p,nc)
- q2 = 0x7FFFFFFF/d; // initialize q2 = (2p-1)/d
- r2 = 0x7FFFFFFF - 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 >= 0x7FFFFFFF) magu.a = 1;
- q2 = 2*q2 + 1; // update q2
- r2 = 2*r2 + 1 - d; // update r2
- }
- else {
- if (q2 >= 0x80000000) 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 - 32; // resulting shift
- return magu;
-}
-
-/// 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 ms magic64(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 = d >= 0 ? d : -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 mu magicu64(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;
-}
-
// isSetCCEquivalent - Return true if this node is a setcc, or is a select_cc
// that selects between the values 1 and 0, making it equivalent to a setcc.
// Also, set the incoming LHS, RHS, and CC references to the appropriate
/// multiplying by a magic number. See:
/// <http://the.wall.riscom.net/books/proc/ppc/cwg/code2.html>
SDOperand DAGCombiner::BuildSDIV(SDNode *N) {
- MVT::ValueType VT = N->getValueType(0);
-
- // Check to see if we can do this.
- if (!TLI.isTypeLegal(VT) || (VT != MVT::i32 && VT != MVT::i64))
- return SDOperand(); // BuildSDIV only operates on i32 or i64
- if (!TLI.isOperationLegal(ISD::MULHS, VT))
- return SDOperand(); // Make sure the target supports MULHS.
-
- int64_t d = cast<ConstantSDNode>(N->getOperand(1))->getSignExtended();
- ms magics = (VT == MVT::i32) ? magic32(d) : magic64(d);
-
- // Multiply the numerator (operand 0) by the magic value
- SDOperand Q = DAG.getNode(ISD::MULHS, VT, N->getOperand(0),
- DAG.getConstant(magics.m, VT));
- // If d > 0 and m < 0, add the numerator
- if (d > 0 && magics.m < 0) {
- Q = DAG.getNode(ISD::ADD, VT, Q, N->getOperand(0));
- AddToWorkList(Q.Val);
- }
- // If d < 0 and m > 0, subtract the numerator.
- if (d < 0 && magics.m > 0) {
- Q = DAG.getNode(ISD::SUB, VT, Q, N->getOperand(0));
- AddToWorkList(Q.Val);
- }
- // Shift right algebraic if shift value is nonzero
- if (magics.s > 0) {
- Q = DAG.getNode(ISD::SRA, VT, Q,
- DAG.getConstant(magics.s, TLI.getShiftAmountTy()));
- AddToWorkList(Q.Val);
- }
- // Extract the sign bit and add it to the quotient
- SDOperand T =
- DAG.getNode(ISD::SRL, VT, Q, DAG.getConstant(MVT::getSizeInBits(VT)-1,
- TLI.getShiftAmountTy()));
- AddToWorkList(T.Val);
- return DAG.getNode(ISD::ADD, VT, Q, T);
+ std::list<SDNode*> Built;
+ SDOperand S = TLI.BuildSDIV(N, DAG, &Built);
+
+ for (std::list<SDNode*>::iterator ii = Built.begin(), ee = Built.end();
+ ii != ee; ++ii)
+ AddToWorkList(*ii);
+ return S;
}
/// BuildUDIVSequence - Given an ISD::UDIV node expressing a divide by constant,
/// multiplying by a magic number. See:
/// <http://the.wall.riscom.net/books/proc/ppc/cwg/code2.html>
SDOperand DAGCombiner::BuildUDIV(SDNode *N) {
- MVT::ValueType VT = N->getValueType(0);
-
- // Check to see if we can do this.
- if (!TLI.isTypeLegal(VT) || (VT != MVT::i32 && VT != MVT::i64))
- return SDOperand(); // BuildUDIV only operates on i32 or i64
- if (!TLI.isOperationLegal(ISD::MULHU, VT))
- return SDOperand(); // Make sure the target supports MULHU.
-
- uint64_t d = cast<ConstantSDNode>(N->getOperand(1))->getValue();
- mu magics = (VT == MVT::i32) ? magicu32(d) : magicu64(d);
-
- // Multiply the numerator (operand 0) by the magic value
- SDOperand Q = DAG.getNode(ISD::MULHU, VT, N->getOperand(0),
- DAG.getConstant(magics.m, VT));
- AddToWorkList(Q.Val);
-
- if (magics.a == 0) {
- return DAG.getNode(ISD::SRL, VT, Q,
- DAG.getConstant(magics.s, TLI.getShiftAmountTy()));
- } else {
- SDOperand NPQ = DAG.getNode(ISD::SUB, VT, N->getOperand(0), Q);
- AddToWorkList(NPQ.Val);
- NPQ = DAG.getNode(ISD::SRL, VT, NPQ,
- DAG.getConstant(1, TLI.getShiftAmountTy()));
- AddToWorkList(NPQ.Val);
- NPQ = DAG.getNode(ISD::ADD, VT, NPQ, Q);
- AddToWorkList(NPQ.Val);
- return DAG.getNode(ISD::SRL, VT, NPQ,
- DAG.getConstant(magics.s-1, TLI.getShiftAmountTy()));
- }
+ std::list<SDNode*> Built;
+ SDOperand S = TLI.BuildUDIV(N, DAG, &Built);
+
+ for (std::list<SDNode*>::iterator ii = Built.begin(), ee = Built.end();
+ ii != ee; ++ii)
+ AddToWorkList(*ii);
+ return S;
}
// SelectionDAG::Combine - This is the entry point for the file.
bool TargetLowering::isLegalAddressImmediate(GlobalValue *GV) const {
return false;
}
+
+
+// Magic for divide replacement
+
+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 ms magic32(int32_t d) {
+ int32_t p;
+ uint32_t ad, anc, delta, q1, r1, q2, r2, t;
+ const uint32_t two31 = 0x80000000U;
+ struct ms mag;
+
+ ad = abs(d);
+ t = two31 + ((uint32_t)d >> 31);
+ anc = t - 1 - t%ad; // absolute value of nc
+ p = 31; // initialize p
+ q1 = two31/anc; // initialize q1 = 2p/abs(nc)
+ r1 = two31 - q1*anc; // initialize r1 = rem(2p,abs(nc))
+ q2 = two31/ad; // initialize q2 = 2p/abs(d)
+ r2 = two31 - 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 = (int32_t)(q2 + 1); // make sure to sign extend
+ if (d < 0) mag.m = -mag.m; // resulting magic number
+ mag.s = p - 32; // 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 mu magicu32(uint32_t d) {
+ int32_t p;
+ uint32_t nc, delta, q1, r1, q2, r2;
+ struct mu magu;
+ magu.a = 0; // initialize "add" indicator
+ nc = - 1 - (-d)%d;
+ p = 31; // initialize p
+ q1 = 0x80000000/nc; // initialize q1 = 2p/nc
+ r1 = 0x80000000 - q1*nc; // initialize r1 = rem(2p,nc)
+ q2 = 0x7FFFFFFF/d; // initialize q2 = (2p-1)/d
+ r2 = 0x7FFFFFFF - 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 >= 0x7FFFFFFF) magu.a = 1;
+ q2 = 2*q2 + 1; // update q2
+ r2 = 2*r2 + 1 - d; // update r2
+ }
+ else {
+ if (q2 >= 0x80000000) 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 - 32; // resulting shift
+ return magu;
+}
+
+/// 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 ms magic64(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 = d >= 0 ? d : -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 mu magicu64(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>
+SDOperand TargetLowering::BuildSDIV(SDNode *N, SelectionDAG &DAG,
+ std::list<SDNode*>* Created) const {
+ MVT::ValueType VT = N->getValueType(0);
+
+ // Check to see if we can do this.
+ if (!isTypeLegal(VT) || (VT != MVT::i32 && VT != MVT::i64))
+ return SDOperand(); // BuildSDIV only operates on i32 or i64
+ if (!isOperationLegal(ISD::MULHS, VT))
+ return SDOperand(); // Make sure the target supports MULHS.
+
+ int64_t d = cast<ConstantSDNode>(N->getOperand(1))->getSignExtended();
+ ms magics = (VT == MVT::i32) ? magic32(d) : magic64(d);
+
+ // Multiply the numerator (operand 0) by the magic value
+ SDOperand Q = DAG.getNode(ISD::MULHS, VT, N->getOperand(0),
+ DAG.getConstant(magics.m, VT));
+ // If d > 0 and m < 0, add the numerator
+ if (d > 0 && magics.m < 0) {
+ Q = DAG.getNode(ISD::ADD, VT, Q, N->getOperand(0));
+ if (Created)
+ Created->push_back(Q.Val);
+ }
+ // If d < 0 and m > 0, subtract the numerator.
+ if (d < 0 && magics.m > 0) {
+ Q = DAG.getNode(ISD::SUB, VT, Q, N->getOperand(0));
+ if (Created)
+ Created->push_back(Q.Val);
+ }
+ // Shift right algebraic if shift value is nonzero
+ if (magics.s > 0) {
+ Q = DAG.getNode(ISD::SRA, VT, Q,
+ DAG.getConstant(magics.s, getShiftAmountTy()));
+ if (Created)
+ Created->push_back(Q.Val);
+ }
+ // Extract the sign bit and add it to the quotient
+ SDOperand T =
+ DAG.getNode(ISD::SRL, VT, Q, DAG.getConstant(MVT::getSizeInBits(VT)-1,
+ getShiftAmountTy()));
+ if (Created)
+ Created->push_back(T.Val);
+ return DAG.getNode(ISD::ADD, VT, 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>
+SDOperand TargetLowering::BuildUDIV(SDNode *N, SelectionDAG &DAG,
+ std::list<SDNode*>* Created) const {
+ MVT::ValueType VT = N->getValueType(0);
+
+ // Check to see if we can do this.
+ if (!isTypeLegal(VT) || (VT != MVT::i32 && VT != MVT::i64))
+ return SDOperand(); // BuildUDIV only operates on i32 or i64
+ if (!isOperationLegal(ISD::MULHU, VT))
+ return SDOperand(); // Make sure the target supports MULHU.
+
+ uint64_t d = cast<ConstantSDNode>(N->getOperand(1))->getValue();
+ mu magics = (VT == MVT::i32) ? magicu32(d) : magicu64(d);
+
+ // Multiply the numerator (operand 0) by the magic value
+ SDOperand Q = DAG.getNode(ISD::MULHU, VT, N->getOperand(0),
+ DAG.getConstant(magics.m, VT));
+ if (Created)
+ Created->push_back(Q.Val);
+
+ if (magics.a == 0) {
+ return DAG.getNode(ISD::SRL, VT, Q,
+ DAG.getConstant(magics.s, getShiftAmountTy()));
+ } else {
+ SDOperand NPQ = DAG.getNode(ISD::SUB, VT, N->getOperand(0), Q);
+ if (Created)
+ Created->push_back(NPQ.Val);
+ NPQ = DAG.getNode(ISD::SRL, VT, NPQ,
+ DAG.getConstant(1, getShiftAmountTy()));
+ if (Created)
+ Created->push_back(NPQ.Val);
+ NPQ = DAG.getNode(ISD::ADD, VT, NPQ, Q);
+ if (Created)
+ Created->push_back(NPQ.Val);
+ return DAG.getNode(ISD::SRL, VT, NPQ,
+ DAG.getConstant(magics.s-1, getShiftAmountTy()));
+ }
+}
#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
MVT::ValueType VT = Op.Val->getValueType(0);
unsigned Opc = Op.Val->getOpcode() == ISD::UREM ? ISD::UDIV : ISD::SDIV;
SDOperand Tmp1 = Op.Val->getOpcode() == ISD::UREM ?
- BuildUDIVSequence(Op, &DAG) :
- BuildSDIVSequence(Op, &DAG);
+ BuildUDIV(Op.Val, DAG, NULL) :
+ BuildSDIV(Op.Val, DAG, NULL);
Tmp1 = DAG.getNode(ISD::MUL, VT, Tmp1, Op.getOperand(1));
Tmp1 = DAG.getNode(ISD::SUB, VT, Op.getOperand(0), Tmp1);
return Tmp1;
case ISD::UDIV:
if (MVT::isInteger(Op.getValueType())) {
if (Op.getOperand(1).getOpcode() == ISD::Constant)
- return Op.getOpcode() == ISD::SDIV ? BuildSDIVSequence(Op, &DAG) : BuildUDIVSequence(Op, &DAG);
+ return Op.getOpcode() == ISD::SDIV ? BuildSDIV(Op.Val, DAG, NULL)
+ : BuildUDIV(Op.Val, DAG, NULL);
const char* opstr = 0;
switch(Op.getOpcode()) {
case ISD::UREM: opstr = "__remqu"; break;
/// operation.
bool SelectAddr(SDOperand Addr, SDOperand &Op1, SDOperand &Op2);
- SDOperand BuildSDIVSequence(SDNode *N);
- SDOperand BuildUDIVSequence(SDNode *N);
-
/// InstructionSelectBasicBlock - This callback is invoked by
/// SelectionDAGISel when it has created a SelectionDAG for us to codegen.
virtual void InstructionSelectBasicBlock(SelectionDAG &DAG);
projects / oota-llvm.git / commitdiff