Move this code to a common place

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@28329 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 4 insertions, 148 deletions

diff --git a/lib/Target/Alpha/AlphaISelLowering.cpp b/lib/Target/Alpha/AlphaISelLowering.cpp
index eecb21a491..b47a51891a 100644
--- a/lib/Target/Alpha/AlphaISelLowering.cpp
+++ b/lib/Target/Alpha/AlphaISelLowering.cpp
@@ -25,151 +25,6 @@
 #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
@@ -593,8 +448,8 @@ SDOperand AlphaTargetLowering::LowerOperation(SDOperand Op, SelectionDAG &DAG) {
       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;
@@ -604,7 +459,8 @@ SDOperand AlphaTargetLowering::LowerOperation(SDOperand Op, SelectionDAG &DAG) {
   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;