Move the target constant divide optimization up into the dag combiner, so

that the nodes can be folded with other nodes, and we can not duplicate
code in every backend.  Alpha will probably want this too.


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

1 files changed, 0 insertions, 154 deletions

diff --git a/lib/Target/PowerPC/PPCISelPattern.cpp b/lib/Target/PowerPC/PPCISelPattern.cpp
index bf50a64480..1a9d09c64b 100644
--- a/lib/Target/PowerPC/PPCISelPattern.cpp
+++ b/lib/Target/PowerPC/PPCISelPattern.cpp
@@ -274,151 +274,6 @@ static unsigned IndexedOpForOp(unsigned Opcode) {
   }
   return 0;
 }
-
-// Structure used to return the necessary information to codegen an SDIV as
-// a multiply.
-struct ms {
-  int m; // magic number
-  int s; // shift amount
-};
-
-struct mu {
-  unsigned int m; // magic number
-  int a;          // add indicator
-  int 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(int d) {
-  int p;
-  unsigned int ad, anc, delta, q1, r1, q2, r2, t;
-  const unsigned int two31 = 0x80000000U;
-  struct ms mag;
-
-  ad = abs(d);
-  t = two31 + ((unsigned int)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 = q2 + 1;
-  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 struct mu magicu(unsigned d)
-{
-  int p;
-  unsigned int 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;
-}
-}
-
-/// 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 ISel::BuildSDIVSequence(SDOperand N) {
-  int d = (int)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::i32, N.getOperand(0),
-                                 ISelDAG->getConstant(magics.m, MVT::i32));
-  // If d > 0 and m < 0, add the numerator
-  if (d > 0 && magics.m < 0)
-    Q = ISelDAG->getNode(ISD::ADD, MVT::i32, 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::i32, Q, N.getOperand(0));
-  // Shift right algebraic if shift value is nonzero
-  if (magics.s > 0)
-    Q = ISelDAG->getNode(ISD::SRA, MVT::i32, Q,
-                         ISelDAG->getConstant(magics.s, MVT::i32));
-  // Extract the sign bit and add it to the quotient
-  SDOperand T =
-    ISelDAG->getNode(ISD::SRL, MVT::i32, Q, ISelDAG->getConstant(31, MVT::i32));
-  return ISelDAG->getNode(ISD::ADD, MVT::i32, 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 ISel::BuildUDIVSequence(SDOperand N) {
-  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::i32, N.getOperand(0),
-                                 ISelDAG->getConstant(magics.m, MVT::i32));
-  if (magics.a == 0) {
-    Q = ISelDAG->getNode(ISD::SRL, MVT::i32, Q,
-                         ISelDAG->getConstant(magics.s, MVT::i32));
-  } else {
-    SDOperand NPQ = ISelDAG->getNode(ISD::SUB, MVT::i32, N.getOperand(0), Q);
-    NPQ = ISelDAG->getNode(ISD::SRL, MVT::i32, NPQ,
-                           ISelDAG->getConstant(1, MVT::i32));
-    NPQ = ISelDAG->getNode(ISD::ADD, MVT::i32, NPQ, Q);
-    Q = ISelDAG->getNode(ISD::SRL, MVT::i32, NPQ,
-                           ISelDAG->getConstant(magics.s-1, MVT::i32));
-  }
-  return Q;
 }
 
 /// getGlobalBaseReg - Output the instructions required to put the
@@ -1395,19 +1250,10 @@ unsigned ISel::SelectExpr(SDOperand N, bool Recording) {
         BuildMI(BB, PPC::ADDZE, 1, Tmp4).addReg(Tmp1);
         BuildMI(BB, PPC::NEG, 1, Result).addReg(Tmp4);
         return Result;
-      } else if (Tmp3) {
-        ExprMap.erase(N);
-        return SelectExpr(BuildSDIVSequence(N));
       }
     }
     // fall thru
   case ISD::UDIV:
-    // If this is a divide by constant, we can emit code using some magic
-    // constants to implement it as a multiply instead.
-    if (isIntImmediate(N.getOperand(1), Tmp3) && Tmp3) {
-      ExprMap.erase(N);
-      return SelectExpr(BuildUDIVSequence(N));
-    }
     Tmp1 = SelectExpr(N.getOperand(0));
     Tmp2 = SelectExpr(N.getOperand(1));
     Opc = (ISD::UDIV == opcode) ? PPC::DIVWU : PPC::DIVW; break;