lib/CodeGen/SelectionDAG/TargetLowering.cpp

   1 //===-- TargetLowering.cpp - Implement the TargetLowering class -----------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This implements the TargetLowering class.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/Target/TargetLowering.h"
  15 #include "llvm/Target/TargetData.h"
  16 #include "llvm/Target/TargetMachine.h"
  17 #include "llvm/Target/MRegisterInfo.h"
  18 #include "llvm/DerivedTypes.h"
  19 #include "llvm/CodeGen/SelectionDAG.h"
  20 #include "llvm/ADT/StringExtras.h"
  21 #include "llvm/Support/MathExtras.h"
  22 using namespace llvm;
  23
  24 TargetLowering::TargetLowering(TargetMachine &tm)
  25   : TM(tm), TD(TM.getTargetData()) {
  26   assert(ISD::BUILTIN_OP_END <= 156 &&
  27          "Fixed size array in TargetLowering is not large enough!");
  28   // All operations default to being supported.
  29   memset(OpActions, 0, sizeof(OpActions));
  30
  31   IsLittleEndian = TD->isLittleEndian();
  32   ShiftAmountTy = SetCCResultTy = PointerTy = getValueType(TD->getIntPtrType());
  33   ShiftAmtHandling = Undefined;
  34   memset(RegClassForVT, 0,MVT::LAST_VALUETYPE*sizeof(TargetRegisterClass*));
  35   memset(TargetDAGCombineArray, 0,
  36          sizeof(TargetDAGCombineArray)/sizeof(TargetDAGCombineArray[0]));
  37   maxStoresPerMemset = maxStoresPerMemcpy = maxStoresPerMemmove = 8;
  38   allowUnalignedMemoryAccesses = false;
  39   UseUnderscoreSetJmpLongJmp = false;
  40   IntDivIsCheap = false;
  41   Pow2DivIsCheap = false;
  42   StackPointerRegisterToSaveRestore = 0;
  43   SchedPreferenceInfo = SchedulingForLatency;
  44 }
  45
  46 TargetLowering::~TargetLowering() {}
  47
  48 /// setValueTypeAction - Set the action for a particular value type.  This
  49 /// assumes an action has not already been set for this value type.
  50 static void SetValueTypeAction(MVT::ValueType VT,
  51                                TargetLowering::LegalizeAction Action,
  52                                TargetLowering &TLI,
  53                                MVT::ValueType *TransformToType,
  54                         TargetLowering::ValueTypeActionImpl &ValueTypeActions) {
  55   ValueTypeActions.setTypeAction(VT, Action);
  56   if (Action == TargetLowering::Promote) {
  57     MVT::ValueType PromoteTo;
  58     if (VT == MVT::f32)
  59       PromoteTo = MVT::f64;
  60     else {
  61       unsigned LargerReg = VT+1;
  62       while (!TLI.isTypeLegal((MVT::ValueType)LargerReg)) {
  63         ++LargerReg;
  64         assert(MVT::isInteger((MVT::ValueType)LargerReg) &&
  65                "Nothing to promote to??");
  66       }
  67       PromoteTo = (MVT::ValueType)LargerReg;
  68     }
  69
  70     assert(MVT::isInteger(VT) == MVT::isInteger(PromoteTo) &&
  71            MVT::isFloatingPoint(VT) == MVT::isFloatingPoint(PromoteTo) &&
  72            "Can only promote from int->int or fp->fp!");
  73     assert(VT < PromoteTo && "Must promote to a larger type!");
  74     TransformToType[VT] = PromoteTo;
  75   } else if (Action == TargetLowering::Expand) {
  76     assert((VT == MVT::Vector || MVT::isInteger(VT)) && VT > MVT::i8 &&
  77            "Cannot expand this type: target must support SOME integer reg!");
  78     // Expand to the next smaller integer type!
  79     TransformToType[VT] = (MVT::ValueType)(VT-1);
  80   }
  81 }
  82
  83
  84 /// computeRegisterProperties - Once all of the register classes are added,
  85 /// this allows us to compute derived properties we expose.
  86 void TargetLowering::computeRegisterProperties() {
  87   assert(MVT::LAST_VALUETYPE <= 32 &&
  88          "Too many value types for ValueTypeActions to hold!");
  89
  90   // Everything defaults to one.
  91   for (unsigned i = 0; i != MVT::LAST_VALUETYPE; ++i)
  92     NumElementsForVT[i] = 1;
  93
  94   // Find the largest integer register class.
  95   unsigned LargestIntReg = MVT::i128;
  96   for (; RegClassForVT[LargestIntReg] == 0; --LargestIntReg)
  97     assert(LargestIntReg != MVT::i1 && "No integer registers defined!");
  98
  99   // Every integer value type larger than this largest register takes twice as
 100   // many registers to represent as the previous ValueType.
 101   unsigned ExpandedReg = LargestIntReg; ++LargestIntReg;
 102   for (++ExpandedReg; MVT::isInteger((MVT::ValueType)ExpandedReg);++ExpandedReg)
 103     NumElementsForVT[ExpandedReg] = 2*NumElementsForVT[ExpandedReg-1];
 104
 105   // Inspect all of the ValueType's possible, deciding how to process them.
 106   for (unsigned IntReg = MVT::i1; IntReg <= MVT::i128; ++IntReg)
 107     // If we are expanding this type, expand it!
 108     if (getNumElements((MVT::ValueType)IntReg) != 1)
 109       SetValueTypeAction((MVT::ValueType)IntReg, Expand, *this, TransformToType,
 110                          ValueTypeActions);
 111     else if (!isTypeLegal((MVT::ValueType)IntReg))
 112       // Otherwise, if we don't have native support, we must promote to a
 113       // larger type.
 114       SetValueTypeAction((MVT::ValueType)IntReg, Promote, *this,
 115                          TransformToType, ValueTypeActions);
 116     else
 117       TransformToType[(MVT::ValueType)IntReg] = (MVT::ValueType)IntReg;
 118
 119   // If the target does not have native support for F32, promote it to F64.
 120   if (!isTypeLegal(MVT::f32))
 121     SetValueTypeAction(MVT::f32, Promote, *this,
 122                        TransformToType, ValueTypeActions);
 123   else
 124     TransformToType[MVT::f32] = MVT::f32;
 125
 126   // Set MVT::Vector to always be Expanded
 127   SetValueTypeAction(MVT::Vector, Expand, *this, TransformToType,
 128                      ValueTypeActions);
 129
 130   // Loop over all of the legal vector value types, specifying an identity type
 131   // transformation.
 132   for (unsigned i = MVT::FIRST_VECTOR_VALUETYPE;
 133        i <= MVT::LAST_VECTOR_VALUETYPE; ++i) {
 134     if (isTypeLegal((MVT::ValueType)i))
 135       TransformToType[i] = (MVT::ValueType)i;
 136   }
 137
 138   assert(isTypeLegal(MVT::f64) && "Target does not support FP?");
 139   TransformToType[MVT::f64] = MVT::f64;
 140 }
 141
 142 const char *TargetLowering::getTargetNodeName(unsigned Opcode) const {
 143   return NULL;
 144 }
 145
 146 /// getPackedTypeBreakdown - Packed types are broken down into some number of
 147 /// legal first class types. For example, <8 x float> maps to 2 MVT::v4f32
 148 /// with Altivec or SSE1, or 8 promoted MVT::f64 values with the X86 FP stack.
 149 ///
 150 /// This method returns the number and type of the resultant breakdown.
 151 ///
 152 unsigned TargetLowering::getPackedTypeBreakdown(const PackedType *PTy,
 153                                                 MVT::ValueType &PTyElementVT,
 154                                       MVT::ValueType &PTyLegalElementVT) const {
 155   // Figure out the right, legal destination reg to copy into.
 156   unsigned NumElts = PTy->getNumElements();
 157   MVT::ValueType EltTy = getValueType(PTy->getElementType());
 158
 159   unsigned NumVectorRegs = 1;
 160
 161   // Divide the input until we get to a supported size.  This will always
 162   // end with a scalar if the target doesn't support vectors.
 163   while (NumElts > 1 && !isTypeLegal(getVectorType(EltTy, NumElts))) {
 164     NumElts >>= 1;
 165     NumVectorRegs <<= 1;
 166   }
 167
 168   MVT::ValueType VT;
 169   if (NumElts == 1) {
 170     VT = EltTy;
 171   } else {
 172     VT = getVectorType(EltTy, NumElts);
 173   }
 174   PTyElementVT = VT;
 175
 176   MVT::ValueType DestVT = getTypeToTransformTo(VT);
 177   PTyLegalElementVT = DestVT;
 178   if (DestVT < VT) {
 179     // Value is expanded, e.g. i64 -> i16.
 180     return NumVectorRegs*(MVT::getSizeInBits(VT)/MVT::getSizeInBits(DestVT));
 181   } else {
 182     // Otherwise, promotion or legal types use the same number of registers as
 183     // the vector decimated to the appropriate level.
 184     return NumVectorRegs;
 185   }
 186
 187   return 1;
 188 }
 189
 190 //===----------------------------------------------------------------------===//
 191 //  Optimization Methods
 192 //===----------------------------------------------------------------------===//
 193
 194 /// ShrinkDemandedConstant - Check to see if the specified operand of the
 195 /// specified instruction is a constant integer.  If so, check to see if there
 196 /// are any bits set in the constant that are not demanded.  If so, shrink the
 197 /// constant and return true.
 198 bool TargetLowering::TargetLoweringOpt::ShrinkDemandedConstant(SDOperand Op,
 199                                                             uint64_t Demanded) {
 200   // FIXME: ISD::SELECT, ISD::SELECT_CC
 201   switch(Op.getOpcode()) {
 202   default: break;
 203   case ISD::AND:
 204   case ISD::OR:
 205   case ISD::XOR:
 206     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
 207       if ((~Demanded & C->getValue()) != 0) {
 208         MVT::ValueType VT = Op.getValueType();
 209         SDOperand New = DAG.getNode(Op.getOpcode(), VT, Op.getOperand(0),
 210                                     DAG.getConstant(Demanded & C->getValue(),
 211                                                     VT));
 212         return CombineTo(Op, New);
 213       }
 214     break;
 215   }
 216   return false;
 217 }
 218
 219 /// SimplifyDemandedBits - Look at Op.  At this point, we know that only the
 220 /// DemandedMask bits of the result of Op are ever used downstream.  If we can
 221 /// use this information to simplify Op, create a new simplified DAG node and
 222 /// return true, returning the original and new nodes in Old and New. Otherwise,
 223 /// analyze the expression and return a mask of KnownOne and KnownZero bits for
 224 /// the expression (used to simplify the caller).  The KnownZero/One bits may
 225 /// only be accurate for those bits in the DemandedMask.
 226 bool TargetLowering::SimplifyDemandedBits(SDOperand Op, uint64_t DemandedMask,
 227                                           uint64_t &KnownZero,
 228                                           uint64_t &KnownOne,
 229                                           TargetLoweringOpt &TLO,
 230                                           unsigned Depth) const {
 231   KnownZero = KnownOne = 0;   // Don't know anything.
 232   // Other users may use these bits.
 233   if (!Op.Val->hasOneUse()) {
 234     if (Depth != 0) {
 235       // If not at the root, Just compute the KnownZero/KnownOne bits to
 236       // simplify things downstream.
 237       ComputeMaskedBits(Op, DemandedMask, KnownZero, KnownOne, Depth);
 238       return false;
 239     }
 240     // If this is the root being simplified, allow it to have multiple uses,
 241     // just set the DemandedMask to all bits.
 242     DemandedMask = MVT::getIntVTBitMask(Op.getValueType());
 243   } else if (DemandedMask == 0) {
 244     // Not demanding any bits from Op.
 245     if (Op.getOpcode() != ISD::UNDEF)
 246       return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::UNDEF, Op.getValueType()));
 247     return false;
 248   } else if (Depth == 6) {        // Limit search depth.
 249     return false;
 250   }
 251
 252   uint64_t KnownZero2, KnownOne2, KnownZeroOut, KnownOneOut;
 253   switch (Op.getOpcode()) {
 254   case ISD::Constant:
 255     // We know all of the bits for a constant!
 256     KnownOne = cast<ConstantSDNode>(Op)->getValue() & DemandedMask;
 257     KnownZero = ~KnownOne & DemandedMask;
 258     return false;   // Don't fall through, will infinitely loop.
 259   case ISD::AND:
 260     // If the RHS is a constant, check to see if the LHS would be zero without
 261     // using the bits from the RHS.  Below, we use knowledge about the RHS to
 262     // simplify the LHS, here we're using information from the LHS to simplify
 263     // the RHS.
 264     if (ConstantSDNode *RHSC = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
 265       uint64_t LHSZero, LHSOne;
 266       ComputeMaskedBits(Op.getOperand(0), DemandedMask,
 267                         LHSZero, LHSOne, Depth+1);
 268       // If the LHS already has zeros where RHSC does, this and is dead.
 269       if ((LHSZero & DemandedMask) == (~RHSC->getValue() & DemandedMask))
 270         return TLO.CombineTo(Op, Op.getOperand(0));
 271       // If any of the set bits in the RHS are known zero on the LHS, shrink
 272       // the constant.
 273       if (TLO.ShrinkDemandedConstant(Op, ~LHSZero & DemandedMask))
 274         return true;
 275     }
 276
 277     if (SimplifyDemandedBits(Op.getOperand(1), DemandedMask, KnownZero,
 278                              KnownOne, TLO, Depth+1))
 279       return true;
 280     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 281     if (SimplifyDemandedBits(Op.getOperand(0), DemandedMask & ~KnownZero,
 282                              KnownZero2, KnownOne2, TLO, Depth+1))
 283       return true;
 284     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
 285
 286     // If all of the demanded bits are known one on one side, return the other.
 287     // These bits cannot contribute to the result of the 'and'.
 288     if ((DemandedMask & ~KnownZero2 & KnownOne)==(DemandedMask & ~KnownZero2))
 289       return TLO.CombineTo(Op, Op.getOperand(0));
 290     if ((DemandedMask & ~KnownZero & KnownOne2)==(DemandedMask & ~KnownZero))
 291       return TLO.CombineTo(Op, Op.getOperand(1));
 292     // If all of the demanded bits in the inputs are known zeros, return zero.
 293     if ((DemandedMask & (KnownZero|KnownZero2)) == DemandedMask)
 294       return TLO.CombineTo(Op, TLO.DAG.getConstant(0, Op.getValueType()));
 295     // If the RHS is a constant, see if we can simplify it.
 296     if (TLO.ShrinkDemandedConstant(Op, DemandedMask & ~KnownZero2))
 297       return true;
 298
 299     // Output known-1 bits are only known if set in both the LHS & RHS.
 300     KnownOne &= KnownOne2;
 301     // Output known-0 are known to be clear if zero in either the LHS | RHS.
 302     KnownZero |= KnownZero2;
 303     break;
 304   case ISD::OR:
 305     if (SimplifyDemandedBits(Op.getOperand(1), DemandedMask, KnownZero,
 306                              KnownOne, TLO, Depth+1))
 307       return true;
 308     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 309     if (SimplifyDemandedBits(Op.getOperand(0), DemandedMask & ~KnownOne,
 310                              KnownZero2, KnownOne2, TLO, Depth+1))
 311       return true;
 312     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
 313
 314     // If all of the demanded bits are known zero on one side, return the other.
 315     // These bits cannot contribute to the result of the 'or'.
 316     if ((DemandedMask & ~KnownOne2 & KnownZero) == (DemandedMask & ~KnownOne2))
 317       return TLO.CombineTo(Op, Op.getOperand(0));
 318     if ((DemandedMask & ~KnownOne & KnownZero2) == (DemandedMask & ~KnownOne))
 319       return TLO.CombineTo(Op, Op.getOperand(1));
 320     // If all of the potentially set bits on one side are known to be set on
 321     // the other side, just use the 'other' side.
 322     if ((DemandedMask & (~KnownZero) & KnownOne2) ==
 323         (DemandedMask & (~KnownZero)))
 324       return TLO.CombineTo(Op, Op.getOperand(0));
 325     if ((DemandedMask & (~KnownZero2) & KnownOne) ==
 326         (DemandedMask & (~KnownZero2)))
 327       return TLO.CombineTo(Op, Op.getOperand(1));
 328     // If the RHS is a constant, see if we can simplify it.
 329     if (TLO.ShrinkDemandedConstant(Op, DemandedMask))
 330       return true;
 331
 332     // Output known-0 bits are only known if clear in both the LHS & RHS.
 333     KnownZero &= KnownZero2;
 334     // Output known-1 are known to be set if set in either the LHS | RHS.
 335     KnownOne |= KnownOne2;
 336     break;
 337   case ISD::XOR:
 338     if (SimplifyDemandedBits(Op.getOperand(1), DemandedMask, KnownZero,
 339                              KnownOne, TLO, Depth+1))
 340       return true;
 341     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 342     if (SimplifyDemandedBits(Op.getOperand(0), DemandedMask, KnownZero2,
 343                              KnownOne2, TLO, Depth+1))
 344       return true;
 345     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
 346
 347     // If all of the demanded bits are known zero on one side, return the other.
 348     // These bits cannot contribute to the result of the 'xor'.
 349     if ((DemandedMask & KnownZero) == DemandedMask)
 350       return TLO.CombineTo(Op, Op.getOperand(0));
 351     if ((DemandedMask & KnownZero2) == DemandedMask)
 352       return TLO.CombineTo(Op, Op.getOperand(1));
 353
 354     // Output known-0 bits are known if clear or set in both the LHS & RHS.
 355     KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
 356     // Output known-1 are known to be set if set in only one of the LHS, RHS.
 357     KnownOneOut = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
 358
 359     // If all of the unknown bits are known to be zero on one side or the other
 360     // (but not both) turn this into an *inclusive* or.
 361     //    e.g. (A & C1)^(B & C2) -> (A & C1)|(B & C2) iff C1&C2 == 0
 362     if (uint64_t UnknownBits = DemandedMask & ~(KnownZeroOut|KnownOneOut))
 363       if ((UnknownBits & (KnownZero|KnownZero2)) == UnknownBits)
 364         return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::OR, Op.getValueType(),
 365                                                  Op.getOperand(0),
 366                                                  Op.getOperand(1)));
 367     // If all of the demanded bits on one side are known, and all of the set
 368     // bits on that side are also known to be set on the other side, turn this
 369     // into an AND, as we know the bits will be cleared.
 370     //    e.g. (X | C1) ^ C2 --> (X | C1) & ~C2 iff (C1&C2) == C2
 371     if ((DemandedMask & (KnownZero|KnownOne)) == DemandedMask) { // all known
 372       if ((KnownOne & KnownOne2) == KnownOne) {
 373         MVT::ValueType VT = Op.getValueType();
 374         SDOperand ANDC = TLO.DAG.getConstant(~KnownOne & DemandedMask, VT);
 375         return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::AND, VT, Op.getOperand(0),
 376                                                  ANDC));
 377       }
 378     }
 379
 380     // If the RHS is a constant, see if we can simplify it.
 381     // FIXME: for XOR, we prefer to force bits to 1 if they will make a -1.
 382     if (TLO.ShrinkDemandedConstant(Op, DemandedMask))
 383       return true;
 384
 385     KnownZero = KnownZeroOut;
 386     KnownOne  = KnownOneOut;
 387     break;
 388   case ISD::SETCC:
 389     // If we know the result of a setcc has the top bits zero, use this info.
 390     if (getSetCCResultContents() == TargetLowering::ZeroOrOneSetCCResult)
 391       KnownZero |= (MVT::getIntVTBitMask(Op.getValueType()) ^ 1ULL);
 392     break;
 393   case ISD::SELECT:
 394     if (SimplifyDemandedBits(Op.getOperand(2), DemandedMask, KnownZero,
 395                              KnownOne, TLO, Depth+1))
 396       return true;
 397     if (SimplifyDemandedBits(Op.getOperand(1), DemandedMask, KnownZero2,
 398                              KnownOne2, TLO, Depth+1))
 399       return true;
 400     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 401     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
 402
 403     // If the operands are constants, see if we can simplify them.
 404     if (TLO.ShrinkDemandedConstant(Op, DemandedMask))
 405       return true;
 406
 407     // Only known if known in both the LHS and RHS.
 408     KnownOne &= KnownOne2;
 409     KnownZero &= KnownZero2;
 410     break;
 411   case ISD::SELECT_CC:
 412     if (SimplifyDemandedBits(Op.getOperand(3), DemandedMask, KnownZero,
 413                              KnownOne, TLO, Depth+1))
 414       return true;
 415     if (SimplifyDemandedBits(Op.getOperand(2), DemandedMask, KnownZero2,
 416                              KnownOne2, TLO, Depth+1))
 417       return true;
 418     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 419     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
 420
 421     // If the operands are constants, see if we can simplify them.
 422     if (TLO.ShrinkDemandedConstant(Op, DemandedMask))
 423       return true;
 424
 425     // Only known if known in both the LHS and RHS.
 426     KnownOne &= KnownOne2;
 427     KnownZero &= KnownZero2;
 428     break;
 429   case ISD::SHL:
 430     if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
 431       if (SimplifyDemandedBits(Op.getOperand(0), DemandedMask >> SA->getValue(),
 432                                KnownZero, KnownOne, TLO, Depth+1))
 433         return true;
 434       KnownZero <<= SA->getValue();
 435       KnownOne  <<= SA->getValue();
 436       KnownZero |= (1ULL << SA->getValue())-1;  // low bits known zero.
 437     }
 438     break;
 439   case ISD::SRL:
 440     if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
 441       MVT::ValueType VT = Op.getValueType();
 442       unsigned ShAmt = SA->getValue();
 443
 444       // Compute the new bits that are at the top now.
 445       uint64_t HighBits = (1ULL << ShAmt)-1;
 446       HighBits <<= MVT::getSizeInBits(VT) - ShAmt;
 447       uint64_t TypeMask = MVT::getIntVTBitMask(VT);
 448
 449       if (SimplifyDemandedBits(Op.getOperand(0),
 450                                (DemandedMask << ShAmt) & TypeMask,
 451                                KnownZero, KnownOne, TLO, Depth+1))
 452         return true;
 453       assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 454       KnownZero &= TypeMask;
 455       KnownOne  &= TypeMask;
 456       KnownZero >>= ShAmt;
 457       KnownOne  >>= ShAmt;
 458       KnownZero |= HighBits;  // high bits known zero.
 459     }
 460     break;
 461   case ISD::SRA:
 462     if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
 463       MVT::ValueType VT = Op.getValueType();
 464       unsigned ShAmt = SA->getValue();
 465
 466       // Compute the new bits that are at the top now.
 467       uint64_t HighBits = (1ULL << ShAmt)-1;
 468       HighBits <<= MVT::getSizeInBits(VT) - ShAmt;
 469       uint64_t TypeMask = MVT::getIntVTBitMask(VT);
 470
 471       uint64_t InDemandedMask = (DemandedMask << ShAmt) & TypeMask;
 472
 473       // If any of the demanded bits are produced by the sign extension, we also
 474       // demand the input sign bit.
 475       if (HighBits & DemandedMask)
 476         InDemandedMask |= MVT::getIntVTSignBit(VT);
 477
 478       if (SimplifyDemandedBits(Op.getOperand(0), InDemandedMask,
 479                                KnownZero, KnownOne, TLO, Depth+1))
 480         return true;
 481       assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 482       KnownZero &= TypeMask;
 483       KnownOne  &= TypeMask;
 484       KnownZero >>= SA->getValue();
 485       KnownOne  >>= SA->getValue();
 486
 487       // Handle the sign bits.
 488       uint64_t SignBit = MVT::getIntVTSignBit(VT);
 489       SignBit >>= SA->getValue();  // Adjust to where it is now in the mask.
 490
 491       // If the input sign bit is known to be zero, or if none of the top bits
 492       // are demanded, turn this into an unsigned shift right.
 493       if ((KnownZero & SignBit) || (HighBits & ~DemandedMask) == HighBits) {
 494         return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::SRL, VT, Op.getOperand(0),
 495                                                  Op.getOperand(1)));
 496       } else if (KnownOne & SignBit) { // New bits are known one.
 497         KnownOne |= HighBits;
 498       }
 499     }
 500     break;
 501   case ISD::SIGN_EXTEND_INREG: {
 502     MVT::ValueType  VT = Op.getValueType();
 503     MVT::ValueType EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
 504
 505     // Sign extension.  Compute the demanded bits in the result that are not
 506     // present in the input.
 507     uint64_t NewBits = ~MVT::getIntVTBitMask(EVT) & DemandedMask;
 508
 509     // If none of the extended bits are demanded, eliminate the sextinreg.
 510     if (NewBits == 0)
 511       return TLO.CombineTo(Op, Op.getOperand(0));
 512
 513     uint64_t InSignBit = MVT::getIntVTSignBit(EVT);
 514     int64_t InputDemandedBits = DemandedMask & MVT::getIntVTBitMask(EVT);
 515
 516     // Since the sign extended bits are demanded, we know that the sign
 517     // bit is demanded.
 518     InputDemandedBits |= InSignBit;
 519
 520     if (SimplifyDemandedBits(Op.getOperand(0), InputDemandedBits,
 521                              KnownZero, KnownOne, TLO, Depth+1))
 522       return true;
 523     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 524
 525     // If the sign bit of the input is known set or clear, then we know the
 526     // top bits of the result.
 527
 528     // If the input sign bit is known zero, convert this into a zero extension.
 529     if (KnownZero & InSignBit)
 530       return TLO.CombineTo(Op,
 531                            TLO.DAG.getZeroExtendInReg(Op.getOperand(0), EVT));
 532
 533     if (KnownOne & InSignBit) {    // Input sign bit known set
 534       KnownOne |= NewBits;
 535       KnownZero &= ~NewBits;
 536     } else {                       // Input sign bit unknown
 537       KnownZero &= ~NewBits;
 538       KnownOne &= ~NewBits;
 539     }
 540     break;
 541   }
 542   case ISD::CTTZ:
 543   case ISD::CTLZ:
 544   case ISD::CTPOP: {
 545     MVT::ValueType VT = Op.getValueType();
 546     unsigned LowBits = Log2_32(MVT::getSizeInBits(VT))+1;
 547     KnownZero = ~((1ULL << LowBits)-1) & MVT::getIntVTBitMask(VT);
 548     KnownOne  = 0;
 549     break;
 550   }
 551   case ISD::ZEXTLOAD: {
 552     MVT::ValueType VT = cast<VTSDNode>(Op.getOperand(3))->getVT();
 553     KnownZero |= ~MVT::getIntVTBitMask(VT) & DemandedMask;
 554     break;
 555   }
 556   case ISD::ZERO_EXTEND: {
 557     uint64_t InMask = MVT::getIntVTBitMask(Op.getOperand(0).getValueType());
 558
 559     // If none of the top bits are demanded, convert this into an any_extend.
 560     uint64_t NewBits = (~InMask) & DemandedMask;
 561     if (NewBits == 0)
 562       return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::ANY_EXTEND,
 563                                                Op.getValueType(),
 564                                                Op.getOperand(0)));
 565
 566     if (SimplifyDemandedBits(Op.getOperand(0), DemandedMask & InMask,
 567                              KnownZero, KnownOne, TLO, Depth+1))
 568       return true;
 569     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 570     KnownZero |= NewBits;
 571     break;
 572   }
 573   case ISD::SIGN_EXTEND: {
 574     MVT::ValueType InVT = Op.getOperand(0).getValueType();
 575     uint64_t InMask    = MVT::getIntVTBitMask(InVT);
 576     uint64_t InSignBit = MVT::getIntVTSignBit(InVT);
 577     uint64_t NewBits   = (~InMask) & DemandedMask;
 578
 579     // If none of the top bits are demanded, convert this into an any_extend.
 580     if (NewBits == 0)
 581       return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::ANY_EXTEND,Op.getValueType(),
 582                                            Op.getOperand(0)));
 583
 584     // Since some of the sign extended bits are demanded, we know that the sign
 585     // bit is demanded.
 586     uint64_t InDemandedBits = DemandedMask & InMask;
 587     InDemandedBits |= InSignBit;
 588
 589     if (SimplifyDemandedBits(Op.getOperand(0), InDemandedBits, KnownZero,
 590                              KnownOne, TLO, Depth+1))
 591       return true;
 592
 593     // If the sign bit is known zero, convert this to a zero extend.
 594     if (KnownZero & InSignBit)
 595       return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::ZERO_EXTEND,
 596                                                Op.getValueType(),
 597                                                Op.getOperand(0)));
 598
 599     // If the sign bit is known one, the top bits match.
 600     if (KnownOne & InSignBit) {
 601       KnownOne  |= NewBits;
 602       KnownZero &= ~NewBits;
 603     } else {   // Otherwise, top bits aren't known.
 604       KnownOne  &= ~NewBits;
 605       KnownZero &= ~NewBits;
 606     }
 607     break;
 608   }
 609   case ISD::ANY_EXTEND: {
 610     uint64_t InMask = MVT::getIntVTBitMask(Op.getOperand(0).getValueType());
 611     if (SimplifyDemandedBits(Op.getOperand(0), DemandedMask & InMask,
 612                              KnownZero, KnownOne, TLO, Depth+1))
 613       return true;
 614     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 615     break;
 616   }
 617   case ISD::TRUNCATE: {
 618     // Simplify the input, using demanded bit information, and compute the known
 619     // zero/one bits live out.
 620     if (SimplifyDemandedBits(Op.getOperand(0), DemandedMask,
 621                              KnownZero, KnownOne, TLO, Depth+1))
 622       return true;
 623
 624     // If the input is only used by this truncate, see if we can shrink it based
 625     // on the known demanded bits.
 626     if (Op.getOperand(0).Val->hasOneUse()) {
 627       SDOperand In = Op.getOperand(0);
 628       switch (In.getOpcode()) {
 629       default: break;
 630       case ISD::SRL:
 631         // Shrink SRL by a constant if none of the high bits shifted in are
 632         // demanded.
 633         if (ConstantSDNode *ShAmt = dyn_cast<ConstantSDNode>(In.getOperand(1))){
 634           uint64_t HighBits = MVT::getIntVTBitMask(In.getValueType());
 635           HighBits &= ~MVT::getIntVTBitMask(Op.getValueType());
 636           HighBits >>= ShAmt->getValue();
 637
 638           if (ShAmt->getValue() < MVT::getSizeInBits(Op.getValueType()) &&
 639               (DemandedMask & HighBits) == 0) {
 640             // None of the shifted in bits are needed.  Add a truncate of the
 641             // shift input, then shift it.
 642             SDOperand NewTrunc = TLO.DAG.getNode(ISD::TRUNCATE,
 643                                                  Op.getValueType(),
 644                                                  In.getOperand(0));
 645             return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::SRL,Op.getValueType(),
 646                                                    NewTrunc, In.getOperand(1)));
 647           }
 648         }
 649         break;
 650       }
 651     }
 652
 653     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 654     uint64_t OutMask = MVT::getIntVTBitMask(Op.getValueType());
 655     KnownZero &= OutMask;
 656     KnownOne &= OutMask;
 657     break;
 658   }
 659   case ISD::AssertZext: {
 660     MVT::ValueType VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
 661     uint64_t InMask = MVT::getIntVTBitMask(VT);
 662     if (SimplifyDemandedBits(Op.getOperand(0), DemandedMask & InMask,
 663                              KnownZero, KnownOne, TLO, Depth+1))
 664       return true;
 665     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 666     KnownZero |= ~InMask & DemandedMask;
 667     break;
 668   }
 669   case ISD::ADD:
 670   case ISD::SUB:
 671   case ISD::INTRINSIC_WO_CHAIN:
 672   case ISD::INTRINSIC_W_CHAIN:
 673   case ISD::INTRINSIC_VOID:
 674     // Just use ComputeMaskedBits to compute output bits.
 675     ComputeMaskedBits(Op, DemandedMask, KnownZero, KnownOne, Depth);
 676     break;
 677   }
 678
 679   // If we know the value of all of the demanded bits, return this as a
 680   // constant.
 681   if ((DemandedMask & (KnownZero|KnownOne)) == DemandedMask)
 682     return TLO.CombineTo(Op, TLO.DAG.getConstant(KnownOne, Op.getValueType()));
 683
 684   return false;
 685 }
 686
 687 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero.  We use
 688 /// this predicate to simplify operations downstream.  Mask is known to be zero
 689 /// for bits that V cannot have.
 690 bool TargetLowering::MaskedValueIsZero(SDOperand Op, uint64_t Mask,
 691                                        unsigned Depth) const {
 692   uint64_t KnownZero, KnownOne;
 693   ComputeMaskedBits(Op, Mask, KnownZero, KnownOne, Depth);
 694   assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 695   return (KnownZero & Mask) == Mask;
 696 }
 697
 698 /// ComputeMaskedBits - Determine which of the bits specified in Mask are
 699 /// known to be either zero or one and return them in the KnownZero/KnownOne
 700 /// bitsets.  This code only analyzes bits in Mask, in order to short-circuit
 701 /// processing.
 702 void TargetLowering::ComputeMaskedBits(SDOperand Op, uint64_t Mask,
 703                                        uint64_t &KnownZero, uint64_t &KnownOne,
 704                                        unsigned Depth) const {
 705   KnownZero = KnownOne = 0;   // Don't know anything.
 706   if (Depth == 6 || Mask == 0)
 707     return;  // Limit search depth.
 708
 709   uint64_t KnownZero2, KnownOne2;
 710
 711   switch (Op.getOpcode()) {
 712   case ISD::Constant:
 713     // We know all of the bits for a constant!
 714     KnownOne = cast<ConstantSDNode>(Op)->getValue() & Mask;
 715     KnownZero = ~KnownOne & Mask;
 716     return;
 717   case ISD::AND:
 718     // If either the LHS or the RHS are Zero, the result is zero.
 719     ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1);
 720     Mask &= ~KnownZero;
 721     ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero2, KnownOne2, Depth+1);
 722     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 723     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
 724
 725     // Output known-1 bits are only known if set in both the LHS & RHS.
 726     KnownOne &= KnownOne2;
 727     // Output known-0 are known to be clear if zero in either the LHS | RHS.
 728     KnownZero |= KnownZero2;
 729     return;
 730   case ISD::OR:
 731     ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1);
 732     Mask &= ~KnownOne;
 733     ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero2, KnownOne2, Depth+1);
 734     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 735     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
 736
 737     // Output known-0 bits are only known if clear in both the LHS & RHS.
 738     KnownZero &= KnownZero2;
 739     // Output known-1 are known to be set if set in either the LHS | RHS.
 740     KnownOne |= KnownOne2;
 741     return;
 742   case ISD::XOR: {
 743     ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1);
 744     ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero2, KnownOne2, Depth+1);
 745     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 746     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
 747
 748     // Output known-0 bits are known if clear or set in both the LHS & RHS.
 749     uint64_t KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
 750     // Output known-1 are known to be set if set in only one of the LHS, RHS.
 751     KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
 752     KnownZero = KnownZeroOut;
 753     return;
 754   }
 755   case ISD::SELECT:
 756     ComputeMaskedBits(Op.getOperand(2), Mask, KnownZero, KnownOne, Depth+1);
 757     ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero2, KnownOne2, Depth+1);
 758     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 759     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
 760
 761     // Only known if known in both the LHS and RHS.
 762     KnownOne &= KnownOne2;
 763     KnownZero &= KnownZero2;
 764     return;
 765   case ISD::SELECT_CC:
 766     ComputeMaskedBits(Op.getOperand(3), Mask, KnownZero, KnownOne, Depth+1);
 767     ComputeMaskedBits(Op.getOperand(2), Mask, KnownZero2, KnownOne2, Depth+1);
 768     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 769     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
 770
 771     // Only known if known in both the LHS and RHS.
 772     KnownOne &= KnownOne2;
 773     KnownZero &= KnownZero2;
 774     return;
 775   case ISD::SETCC:
 776     // If we know the result of a setcc has the top bits zero, use this info.
 777     if (getSetCCResultContents() == TargetLowering::ZeroOrOneSetCCResult)
 778       KnownZero |= (MVT::getIntVTBitMask(Op.getValueType()) ^ 1ULL);
 779     return;
 780   case ISD::SHL:
 781     // (shl X, C1) & C2 == 0   iff   (X & C2 >>u C1) == 0
 782     if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
 783       Mask >>= SA->getValue();
 784       ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero, KnownOne, Depth+1);
 785       assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 786       KnownZero <<= SA->getValue();
 787       KnownOne  <<= SA->getValue();
 788       KnownZero |= (1ULL << SA->getValue())-1;  // low bits known zero.
 789     }
 790     return;
 791   case ISD::SRL:
 792     // (ushr X, C1) & C2 == 0   iff  (-1 >> C1) & C2 == 0
 793     if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
 794       uint64_t HighBits = (1ULL << SA->getValue())-1;
 795       HighBits <<= MVT::getSizeInBits(Op.getValueType())-SA->getValue();
 796       Mask <<= SA->getValue();
 797       ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero, KnownOne, Depth+1);
 798       assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 799       KnownZero >>= SA->getValue();
 800       KnownOne  >>= SA->getValue();
 801       KnownZero |= HighBits;  // high bits known zero.
 802     }
 803     return;
 804   case ISD::SRA:
 805     if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
 806       uint64_t HighBits = (1ULL << SA->getValue())-1;
 807       HighBits <<= MVT::getSizeInBits(Op.getValueType())-SA->getValue();
 808       Mask <<= SA->getValue();
 809       ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero, KnownOne, Depth+1);
 810       assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
 811       KnownZero >>= SA->getValue();
 812       KnownOne  >>= SA->getValue();
 813
 814       // Handle the sign bits.
 815       uint64_t SignBit = 1ULL << (MVT::getSizeInBits(Op.getValueType())-1);
 816       SignBit >>= SA->getValue();  // Adjust to where it is now in the mask.
 817
 818       if (KnownZero & SignBit) {       // New bits are known zero.
 819         KnownZero |= HighBits;
 820       } else if (KnownOne & SignBit) { // New bits are known one.
 821         KnownOne |= HighBits;
 822       }
 823     }
 824     return;
 825   case ISD::SIGN_EXTEND_INREG: {
 826     MVT::ValueType  VT = Op.getValueType();
 827     MVT::ValueType EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
 828
 829     // Sign extension.  Compute the demanded bits in the result that are not
 830     // present in the input.
 831     uint64_t NewBits = ~MVT::getIntVTBitMask(EVT) & Mask;
 832
 833     uint64_t InSignBit = MVT::getIntVTSignBit(EVT);
 834     int64_t InputDemandedBits = Mask & MVT::getIntVTBitMask(EVT);
 835
 836     // If the sign extended bits are demanded, we know that the sign
 837     // bit is demanded.
 838     if (NewBits)
 839       InputDemandedBits |= InSignBit;
 840
 841     ComputeMaskedBits(Op.getOperand(0), InputDemandedBits,
 842                       KnownZero, KnownOne, Depth+1);
 843     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 844
 845     // If the sign bit of the input is known set or clear, then we know the
 846     // top bits of the result.
 847     if (KnownZero & InSignBit) {          // Input sign bit known clear
 848       KnownZero |= NewBits;
 849       KnownOne  &= ~NewBits;
 850     } else if (KnownOne & InSignBit) {    // Input sign bit known set
 851       KnownOne  |= NewBits;
 852       KnownZero &= ~NewBits;
 853     } else {                              // Input sign bit unknown
 854       KnownZero &= ~NewBits;
 855       KnownOne  &= ~NewBits;
 856     }
 857     return;
 858   }
 859   case ISD::CTTZ:
 860   case ISD::CTLZ:
 861   case ISD::CTPOP: {
 862     MVT::ValueType VT = Op.getValueType();
 863     unsigned LowBits = Log2_32(MVT::getSizeInBits(VT))+1;
 864     KnownZero = ~((1ULL << LowBits)-1) & MVT::getIntVTBitMask(VT);
 865     KnownOne  = 0;
 866     return;
 867   }
 868   case ISD::ZEXTLOAD: {
 869     MVT::ValueType VT = cast<VTSDNode>(Op.getOperand(3))->getVT();
 870     KnownZero |= ~MVT::getIntVTBitMask(VT) & Mask;
 871     return;
 872   }
 873   case ISD::ZERO_EXTEND: {
 874     uint64_t InMask  = MVT::getIntVTBitMask(Op.getOperand(0).getValueType());
 875     uint64_t NewBits = (~InMask) & Mask;
 876     ComputeMaskedBits(Op.getOperand(0), Mask & InMask, KnownZero,
 877                       KnownOne, Depth+1);
 878     KnownZero |= NewBits & Mask;
 879     KnownOne  &= ~NewBits;
 880     return;
 881   }
 882   case ISD::SIGN_EXTEND: {
 883     MVT::ValueType InVT = Op.getOperand(0).getValueType();
 884     unsigned InBits    = MVT::getSizeInBits(InVT);
 885     uint64_t InMask    = MVT::getIntVTBitMask(InVT);
 886     uint64_t InSignBit = 1ULL << (InBits-1);
 887     uint64_t NewBits   = (~InMask) & Mask;
 888     uint64_t InDemandedBits = Mask & InMask;
 889
 890     // If any of the sign extended bits are demanded, we know that the sign
 891     // bit is demanded.
 892     if (NewBits & Mask)
 893       InDemandedBits |= InSignBit;
 894
 895     ComputeMaskedBits(Op.getOperand(0), InDemandedBits, KnownZero,
 896                       KnownOne, Depth+1);
 897     // If the sign bit is known zero or one, the  top bits match.
 898     if (KnownZero & InSignBit) {
 899       KnownZero |= NewBits;
 900       KnownOne  &= ~NewBits;
 901     } else if (KnownOne & InSignBit) {
 902       KnownOne  |= NewBits;
 903       KnownZero &= ~NewBits;
 904     } else {   // Otherwise, top bits aren't known.
 905       KnownOne  &= ~NewBits;
 906       KnownZero &= ~NewBits;
 907     }
 908     return;
 909   }
 910   case ISD::ANY_EXTEND: {
 911     MVT::ValueType VT = Op.getOperand(0).getValueType();
 912     ComputeMaskedBits(Op.getOperand(0), Mask & MVT::getIntVTBitMask(VT),
 913                       KnownZero, KnownOne, Depth+1);
 914     return;
 915   }
 916   case ISD::TRUNCATE: {
 917     ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero, KnownOne, Depth+1);
 918     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 919     uint64_t OutMask = MVT::getIntVTBitMask(Op.getValueType());
 920     KnownZero &= OutMask;
 921     KnownOne &= OutMask;
 922     break;
 923   }
 924   case ISD::AssertZext: {
 925     MVT::ValueType VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
 926     uint64_t InMask = MVT::getIntVTBitMask(VT);
 927     ComputeMaskedBits(Op.getOperand(0), Mask & InMask, KnownZero,
 928                       KnownOne, Depth+1);
 929     KnownZero |= (~InMask) & Mask;
 930     return;
 931   }
 932   case ISD::ADD: {
 933     // If either the LHS or the RHS are Zero, the result is zero.
 934     ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1);
 935     ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero2, KnownOne2, Depth+1);
 936     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 937     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
 938
 939     // Output known-0 bits are known if clear or set in both the low clear bits
 940     // common to both LHS & RHS.  For example, 8+(X<<3) is known to have the
 941     // low 3 bits clear.
 942     uint64_t KnownZeroOut = std::min(CountTrailingZeros_64(~KnownZero),
 943                                      CountTrailingZeros_64(~KnownZero2));
 944
 945     KnownZero = (1ULL << KnownZeroOut) - 1;
 946     KnownOne = 0;
 947     return;
 948   }
 949   case ISD::SUB: {
 950     ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0));
 951     if (!CLHS) return;
 952
 953     // We know that the top bits of C-X are clear if X contains less bits
 954     // than C (i.e. no wrap-around can happen).  For example, 20-X is
 955     // positive if we can prove that X is >= 0 and < 16.
 956     MVT::ValueType VT = CLHS->getValueType(0);
 957     if ((CLHS->getValue() & MVT::getIntVTSignBit(VT)) == 0) {  // sign bit clear
 958       unsigned NLZ = CountLeadingZeros_64(CLHS->getValue()+1);
 959       uint64_t MaskV = (1ULL << (63-NLZ))-1; // NLZ can't be 64 with no sign bit
 960       MaskV = ~MaskV & MVT::getIntVTBitMask(VT);
 961       ComputeMaskedBits(Op.getOperand(1), MaskV, KnownZero, KnownOne, Depth+1);
 962
 963       // If all of the MaskV bits are known to be zero, then we know the output
 964       // top bits are zero, because we now know that the output is from [0-C].
 965       if ((KnownZero & MaskV) == MaskV) {
 966         unsigned NLZ2 = CountLeadingZeros_64(CLHS->getValue());
 967         KnownZero = ~((1ULL << (64-NLZ2))-1) & Mask;  // Top bits known zero.
 968         KnownOne = 0;   // No one bits known.
 969       } else {
 970         KnownOne = KnownOne = 0;  // Otherwise, nothing known.
 971       }
 972     }
 973     return;
 974   }
 975   default:
 976     // Allow the target to implement this method for its nodes.
 977     if (Op.getOpcode() >= ISD::BUILTIN_OP_END) {
 978   case ISD::INTRINSIC_WO_CHAIN:
 979   case ISD::INTRINSIC_W_CHAIN:
 980   case ISD::INTRINSIC_VOID:
 981       computeMaskedBitsForTargetNode(Op, Mask, KnownZero, KnownOne);
 982     }
 983     return;
 984   }
 985 }
 986
 987 /// computeMaskedBitsForTargetNode - Determine which of the bits specified
 988 /// in Mask are known to be either zero or one and return them in the
 989 /// KnownZero/KnownOne bitsets.
 990 void TargetLowering::computeMaskedBitsForTargetNode(const SDOperand Op,
 991                                                     uint64_t Mask,
 992                                                     uint64_t &KnownZero,
 993                                                     uint64_t &KnownOne,
 994                                                     unsigned Depth) const {
 995   assert((Op.getOpcode() >= ISD::BUILTIN_OP_END ||
 996           Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
 997           Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
 998           Op.getOpcode() == ISD::INTRINSIC_VOID) &&
 999          "Should use MaskedValueIsZero if you don't know whether Op"
1000          " is a target node!");
1001   KnownZero = 0;
1002   KnownOne = 0;
1003 }
1004
1005 /// ComputeNumSignBits - Return the number of times the sign bit of the
1006 /// register is replicated into the other bits.  We know that at least 1 bit
1007 /// is always equal to the sign bit (itself), but other cases can give us
1008 /// information.  For example, immediately after an "SRA X, 2", we know that
1009 /// the top 3 bits are all equal to each other, so we return 3.
1010 unsigned TargetLowering::ComputeNumSignBits(SDOperand Op, unsigned Depth) const{
1011   MVT::ValueType VT = Op.getValueType();
1012   assert(MVT::isInteger(VT) && "Invalid VT!");
1013   unsigned VTBits = MVT::getSizeInBits(VT);
1014   unsigned Tmp, Tmp2;
1015
1016   if (Depth == 6)
1017     return 1;  // Limit search depth.
1018
1019   switch (Op.getOpcode()) {
1020   default: break;
1021   case ISD::AssertSext:
1022     Tmp = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(1))->getVT());
1023     return VTBits-Tmp+1;
1024   case ISD::AssertZext:
1025     Tmp = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(1))->getVT());
1026     return VTBits-Tmp;
1027
1028   case ISD::SEXTLOAD:    // '17' bits known
1029     Tmp = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(3))->getVT());
1030     return VTBits-Tmp+1;
1031   case ISD::ZEXTLOAD:    // '16' bits known
1032     Tmp = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(3))->getVT());
1033     return VTBits-Tmp;
1034
1035   case ISD::Constant: {
1036     uint64_t Val = cast<ConstantSDNode>(Op)->getValue();
1037     // If negative, invert the bits, then look at it.
1038     if (Val & MVT::getIntVTSignBit(VT))
1039       Val = ~Val;
1040
1041     // Shift the bits so they are the leading bits in the int64_t.
1042     Val <<= 64-VTBits;
1043
1044     // Return # leading zeros.  We use 'min' here in case Val was zero before
1045     // shifting.  We don't want to return '64' as for an i32 "0".
1046     return std::min(VTBits, CountLeadingZeros_64(Val));
1047   }
1048
1049   case ISD::SIGN_EXTEND:
1050     Tmp = VTBits-MVT::getSizeInBits(Op.getOperand(0).getValueType());
1051     return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
1052
1053   case ISD::SIGN_EXTEND_INREG:
1054     // Max of the input and what this extends.
1055     Tmp = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(1))->getVT());
1056     Tmp = VTBits-Tmp+1;
1057
1058     Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1059     return std::max(Tmp, Tmp2);
1060
1061   case ISD::SRA:
1062     Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1063     // SRA X, C   -> adds C sign bits.
1064     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1065       Tmp += C->getValue();
1066       if (Tmp > VTBits) Tmp = VTBits;
1067     }
1068     return Tmp;
1069   case ISD::SHL:
1070     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1071       // shl destroys sign bits.
1072       Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1073       if (C->getValue() >= VTBits ||      // Bad shift.
1074           C->getValue() >= Tmp) break;    // Shifted all sign bits out.
1075       return Tmp - C->getValue();
1076     }
1077     break;
1078   case ISD::AND:
1079   case ISD::OR:
1080   case ISD::XOR:    // NOT is handled here.
1081     // Logical binary ops preserve the number of sign bits.
1082     Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1083     if (Tmp == 1) return 1;  // Early out.
1084     Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
1085     return std::min(Tmp, Tmp2);
1086
1087   case ISD::SELECT:
1088     Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1089     if (Tmp == 1) return 1;  // Early out.
1090     Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
1091     return std::min(Tmp, Tmp2);
1092
1093   case ISD::SETCC:
1094     // If setcc returns 0/-1, all bits are sign bits.
1095     if (getSetCCResultContents() == ZeroOrNegativeOneSetCCResult)
1096       return VTBits;
1097     break;
1098   case ISD::ROTL:
1099   case ISD::ROTR:
1100     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1101       unsigned RotAmt = C->getValue() & (VTBits-1);
1102
1103       // Handle rotate right by N like a rotate left by 32-N.
1104       if (Op.getOpcode() == ISD::ROTR)
1105         RotAmt = (VTBits-RotAmt) & (VTBits-1);
1106
1107       // If we aren't rotating out all of the known-in sign bits, return the
1108       // number that are left.  This handles rotl(sext(x), 1) for example.
1109       Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1110       if (Tmp > RotAmt+1) return Tmp-RotAmt;
1111     }
1112     break;
1113   case ISD::ADD:
1114     // Add can have at most one carry bit.  Thus we know that the output
1115     // is, at worst, one more bit than the inputs.
1116     Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1117     if (Tmp == 1) return 1;  // Early out.
1118
1119     // Special case decrementing a value (ADD X, -1):
1120     if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
1121       if (CRHS->isAllOnesValue()) {
1122         uint64_t KnownZero, KnownOne;
1123         uint64_t Mask = MVT::getIntVTBitMask(VT);
1124         ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero, KnownOne, Depth+1);
1125
1126         // If the input is known to be 0 or 1, the output is 0/-1, which is all
1127         // sign bits set.
1128         if ((KnownZero|1) == Mask)
1129           return VTBits;
1130
1131         // If we are subtracting one from a positive number, there is no carry
1132         // out of the result.
1133         if (KnownZero & MVT::getIntVTSignBit(VT))
1134           return Tmp;
1135       }
1136
1137     Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
1138     if (Tmp2 == 1) return 1;
1139       return std::min(Tmp, Tmp2)-1;
1140     break;
1141
1142   case ISD::SUB:
1143     Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
1144     if (Tmp2 == 1) return 1;
1145
1146     // Handle NEG.
1147     if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
1148       if (CLHS->getValue() == 0) {
1149         uint64_t KnownZero, KnownOne;
1150         uint64_t Mask = MVT::getIntVTBitMask(VT);
1151         ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1);
1152         // If the input is known to be 0 or 1, the output is 0/-1, which is all
1153         // sign bits set.
1154         if ((KnownZero|1) == Mask)
1155           return VTBits;
1156
1157         // If the input is known to be positive (the sign bit is known clear),
1158         // the output of the NEG has the same number of sign bits as the input.
1159         if (KnownZero & MVT::getIntVTSignBit(VT))
1160           return Tmp2;
1161
1162         // Otherwise, we treat this like a SUB.
1163       }
1164
1165     // Sub can have at most one carry bit.  Thus we know that the output
1166     // is, at worst, one more bit than the inputs.
1167     Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1168     if (Tmp == 1) return 1;  // Early out.
1169       return std::min(Tmp, Tmp2)-1;
1170     break;
1171   case ISD::TRUNCATE:
1172     // FIXME: it's tricky to do anything useful for this, but it is an important
1173     // case for targets like X86.
1174     break;
1175   }
1176
1177   // Allow the target to implement this method for its nodes.
1178   if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
1179       Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
1180       Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
1181       Op.getOpcode() == ISD::INTRINSIC_VOID) {
1182     unsigned NumBits = ComputeNumSignBitsForTargetNode(Op, Depth);
1183     if (NumBits > 1) return NumBits;
1184   }
1185
1186   // Finally, if we can prove that the top bits of the result are 0's or 1's,
1187   // use this information.
1188   uint64_t KnownZero, KnownOne;
1189   uint64_t Mask = MVT::getIntVTBitMask(VT);
1190   ComputeMaskedBits(Op, Mask, KnownZero, KnownOne, Depth);
1191
1192   uint64_t SignBit = MVT::getIntVTSignBit(VT);
1193   if (KnownZero & SignBit) {        // SignBit is 0
1194     Mask = KnownZero;
1195   } else if (KnownOne & SignBit) {  // SignBit is 1;
1196     Mask = KnownOne;
1197   } else {
1198     // Nothing known.
1199     return 1;
1200   }
1201
1202   // Okay, we know that the sign bit in Mask is set.  Use CLZ to determine
1203   // the number of identical bits in the top of the input value.
1204   Mask ^= ~0ULL;
1205   Mask <<= 64-VTBits;
1206   // Return # leading zeros.  We use 'min' here in case Val was zero before
1207   // shifting.  We don't want to return '64' as for an i32 "0".
1208   return std::min(VTBits, CountLeadingZeros_64(Mask));
1209 }
1210
1211
1212
1213 /// ComputeNumSignBitsForTargetNode - This method can be implemented by
1214 /// targets that want to expose additional information about sign bits to the
1215 /// DAG Combiner.
1216 unsigned TargetLowering::ComputeNumSignBitsForTargetNode(SDOperand Op,
1217                                                          unsigned Depth) const {
1218   assert((Op.getOpcode() >= ISD::BUILTIN_OP_END ||
1219           Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
1220           Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
1221           Op.getOpcode() == ISD::INTRINSIC_VOID) &&
1222          "Should use ComputeNumSignBits if you don't know whether Op"
1223          " is a target node!");
1224   return 1;
1225 }
1226
1227
1228 SDOperand TargetLowering::
1229 PerformDAGCombine(SDNode *N, DAGCombinerInfo &DCI) const {
1230   // Default implementation: no optimization.
1231   return SDOperand();
1232 }
1233
1234 //===----------------------------------------------------------------------===//
1235 //  Inline Assembler Implementation Methods
1236 //===----------------------------------------------------------------------===//
1237
1238 TargetLowering::ConstraintType
1239 TargetLowering::getConstraintType(char ConstraintLetter) const {
1240   // FIXME: lots more standard ones to handle.
1241   switch (ConstraintLetter) {
1242   default: return C_Unknown;
1243   case 'r': return C_RegisterClass;
1244   case 'm':    // memory
1245   case 'o':    // offsetable
1246   case 'V':    // not offsetable
1247     return C_Memory;
1248   case 'i':    // Simple Integer or Relocatable Constant
1249   case 'n':    // Simple Integer
1250   case 's':    // Relocatable Constant
1251   case 'I':    // Target registers.
1252   case 'J':
1253   case 'K':
1254   case 'L':
1255   case 'M':
1256   case 'N':
1257   case 'O':
1258   case 'P':
1259     return C_Other;
1260   }
1261 }
1262
1263 bool TargetLowering::isOperandValidForConstraint(SDOperand Op,
1264                                                  char ConstraintLetter) {
1265   switch (ConstraintLetter) {
1266   default: return false;
1267   case 'i':    // Simple Integer or Relocatable Constant
1268   case 'n':    // Simple Integer
1269   case 's':    // Relocatable Constant
1270     return true;   // FIXME: not right.
1271   }
1272 }
1273
1274
1275 std::vector<unsigned> TargetLowering::
1276 getRegClassForInlineAsmConstraint(const std::string &Constraint,
1277                                   MVT::ValueType VT) const {
1278   return std::vector<unsigned>();
1279 }
1280
1281
1282 std::pair<unsigned, const TargetRegisterClass*> TargetLowering::
1283 getRegForInlineAsmConstraint(const std::string &Constraint,
1284                              MVT::ValueType VT) const {
1285   if (Constraint[0] != '{')
1286     return std::pair<unsigned, const TargetRegisterClass*>(0, 0);
1287   assert(*(Constraint.end()-1) == '}' && "Not a brace enclosed constraint?");
1288
1289   // Remove the braces from around the name.
1290   std::string RegName(Constraint.begin()+1, Constraint.end()-1);
1291
1292   // Figure out which register class contains this reg.
1293   const MRegisterInfo *RI = TM.getRegisterInfo();
1294   for (MRegisterInfo::regclass_iterator RCI = RI->regclass_begin(),
1295        E = RI->regclass_end(); RCI != E; ++RCI) {
1296     const TargetRegisterClass *RC = *RCI;
1297
1298     // If none of the the value types for this register class are valid, we
1299     // can't use it.  For example, 64-bit reg classes on 32-bit targets.
1300     bool isLegal = false;
1301     for (TargetRegisterClass::vt_iterator I = RC->vt_begin(), E = RC->vt_end();
1302          I != E; ++I) {
1303       if (isTypeLegal(*I)) {
1304         isLegal = true;
1305         break;
1306       }
1307     }
1308
1309     if (!isLegal) continue;
1310
1311     for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end();
1312          I != E; ++I) {
1313       if (StringsEqualNoCase(RegName, RI->get(*I).Name))
1314         return std::make_pair(*I, RC);
1315     }
1316   }
1317
1318   return std::pair<unsigned, const TargetRegisterClass*>(0, 0);
1319 }
1320
1321 //===----------------------------------------------------------------------===//
1322 //  Loop Strength Reduction hooks
1323 //===----------------------------------------------------------------------===//
1324
1325 /// isLegalAddressImmediate - Return true if the integer value or
1326 /// GlobalValue can be used as the offset of the target addressing mode.
1327 bool TargetLowering::isLegalAddressImmediate(int64_t V) const {
1328   return false;
1329 }
1330 bool TargetLowering::isLegalAddressImmediate(GlobalValue *GV) const {
1331   return false;
1332 }
1333
1334
1335 // Magic for divide replacement
1336
1337 struct ms {
1338   int64_t m;  // magic number
1339   int64_t s;  // shift amount
1340 };
1341
1342 struct mu {
1343   uint64_t m; // magic number
1344   int64_t a;  // add indicator
1345   int64_t s;  // shift amount
1346 };
1347
1348 /// magic - calculate the magic numbers required to codegen an integer sdiv as
1349 /// a sequence of multiply and shifts.  Requires that the divisor not be 0, 1,
1350 /// or -1.
1351 static ms magic32(int32_t d) {
1352   int32_t p;
1353   uint32_t ad, anc, delta, q1, r1, q2, r2, t;
1354   const uint32_t two31 = 0x80000000U;
1355   struct ms mag;
1356
1357   ad = abs(d);
1358   t = two31 + ((uint32_t)d >> 31);
1359   anc = t - 1 - t%ad;   // absolute value of nc
1360   p = 31;               // initialize p
1361   q1 = two31/anc;       // initialize q1 = 2p/abs(nc)
1362   r1 = two31 - q1*anc;  // initialize r1 = rem(2p,abs(nc))
1363   q2 = two31/ad;        // initialize q2 = 2p/abs(d)
1364   r2 = two31 - q2*ad;   // initialize r2 = rem(2p,abs(d))
1365   do {
1366     p = p + 1;
1367     q1 = 2*q1;        // update q1 = 2p/abs(nc)
1368     r1 = 2*r1;        // update r1 = rem(2p/abs(nc))
1369     if (r1 >= anc) {  // must be unsigned comparison
1370       q1 = q1 + 1;
1371       r1 = r1 - anc;
1372     }
1373     q2 = 2*q2;        // update q2 = 2p/abs(d)
1374     r2 = 2*r2;        // update r2 = rem(2p/abs(d))
1375     if (r2 >= ad) {   // must be unsigned comparison
1376       q2 = q2 + 1;
1377       r2 = r2 - ad;
1378     }
1379     delta = ad - r2;
1380   } while (q1 < delta || (q1 == delta && r1 == 0));
1381
1382   mag.m = (int32_t)(q2 + 1); // make sure to sign extend
1383   if (d < 0) mag.m = -mag.m; // resulting magic number
1384   mag.s = p - 32;            // resulting shift
1385   return mag;
1386 }
1387
1388 /// magicu - calculate the magic numbers required to codegen an integer udiv as
1389 /// a sequence of multiply, add and shifts.  Requires that the divisor not be 0.
1390 static mu magicu32(uint32_t d) {
1391   int32_t p;
1392   uint32_t nc, delta, q1, r1, q2, r2;
1393   struct mu magu;
1394   magu.a = 0;               // initialize "add" indicator
1395   nc = - 1 - (-d)%d;
1396   p = 31;                   // initialize p
1397   q1 = 0x80000000/nc;       // initialize q1 = 2p/nc
1398   r1 = 0x80000000 - q1*nc;  // initialize r1 = rem(2p,nc)
1399   q2 = 0x7FFFFFFF/d;        // initialize q2 = (2p-1)/d
1400   r2 = 0x7FFFFFFF - q2*d;   // initialize r2 = rem((2p-1),d)
1401   do {
1402     p = p + 1;
1403     if (r1 >= nc - r1 ) {
1404       q1 = 2*q1 + 1;  // update q1
1405       r1 = 2*r1 - nc; // update r1
1406     }
1407     else {
1408       q1 = 2*q1; // update q1
1409       r1 = 2*r1; // update r1
1410     }
1411     if (r2 + 1 >= d - r2) {
1412       if (q2 >= 0x7FFFFFFF) magu.a = 1;
1413       q2 = 2*q2 + 1;     // update q2
1414       r2 = 2*r2 + 1 - d; // update r2
1415     }
1416     else {
1417       if (q2 >= 0x80000000) magu.a = 1;
1418       q2 = 2*q2;     // update q2
1419       r2 = 2*r2 + 1; // update r2
1420     }
1421     delta = d - 1 - r2;
1422   } while (p < 64 && (q1 < delta || (q1 == delta && r1 == 0)));
1423   magu.m = q2 + 1; // resulting magic number
1424   magu.s = p - 32;  // resulting shift
1425   return magu;
1426 }
1427
1428 /// magic - calculate the magic numbers required to codegen an integer sdiv as
1429 /// a sequence of multiply and shifts.  Requires that the divisor not be 0, 1,
1430 /// or -1.
1431 static ms magic64(int64_t d) {
1432   int64_t p;
1433   uint64_t ad, anc, delta, q1, r1, q2, r2, t;
1434   const uint64_t two63 = 9223372036854775808ULL; // 2^63
1435   struct ms mag;
1436
1437   ad = d >= 0 ? d : -d;
1438   t = two63 + ((uint64_t)d >> 63);
1439   anc = t - 1 - t%ad;   // absolute value of nc
1440   p = 63;               // initialize p
1441   q1 = two63/anc;       // initialize q1 = 2p/abs(nc)
1442   r1 = two63 - q1*anc;  // initialize r1 = rem(2p,abs(nc))
1443   q2 = two63/ad;        // initialize q2 = 2p/abs(d)
1444   r2 = two63 - q2*ad;   // initialize r2 = rem(2p,abs(d))
1445   do {
1446     p = p + 1;
1447     q1 = 2*q1;        // update q1 = 2p/abs(nc)
1448     r1 = 2*r1;        // update r1 = rem(2p/abs(nc))
1449     if (r1 >= anc) {  // must be unsigned comparison
1450       q1 = q1 + 1;
1451       r1 = r1 - anc;
1452     }
1453     q2 = 2*q2;        // update q2 = 2p/abs(d)
1454     r2 = 2*r2;        // update r2 = rem(2p/abs(d))
1455     if (r2 >= ad) {   // must be unsigned comparison
1456       q2 = q2 + 1;
1457       r2 = r2 - ad;
1458     }
1459     delta = ad - r2;
1460   } while (q1 < delta || (q1 == delta && r1 == 0));
1461
1462   mag.m = q2 + 1;
1463   if (d < 0) mag.m = -mag.m; // resulting magic number
1464   mag.s = p - 64;            // resulting shift
1465   return mag;
1466 }
1467
1468 /// magicu - calculate the magic numbers required to codegen an integer udiv as
1469 /// a sequence of multiply, add and shifts.  Requires that the divisor not be 0.
1470 static mu magicu64(uint64_t d)
1471 {
1472   int64_t p;
1473   uint64_t nc, delta, q1, r1, q2, r2;
1474   struct mu magu;
1475   magu.a = 0;               // initialize "add" indicator
1476   nc = - 1 - (-d)%d;
1477   p = 63;                   // initialize p
1478   q1 = 0x8000000000000000ull/nc;       // initialize q1 = 2p/nc
1479   r1 = 0x8000000000000000ull - q1*nc;  // initialize r1 = rem(2p,nc)
1480   q2 = 0x7FFFFFFFFFFFFFFFull/d;        // initialize q2 = (2p-1)/d
1481   r2 = 0x7FFFFFFFFFFFFFFFull - q2*d;   // initialize r2 = rem((2p-1),d)
1482   do {
1483     p = p + 1;
1484     if (r1 >= nc - r1 ) {
1485       q1 = 2*q1 + 1;  // update q1
1486       r1 = 2*r1 - nc; // update r1
1487     }
1488     else {
1489       q1 = 2*q1; // update q1
1490       r1 = 2*r1; // update r1
1491     }
1492     if (r2 + 1 >= d - r2) {
1493       if (q2 >= 0x7FFFFFFFFFFFFFFFull) magu.a = 1;
1494       q2 = 2*q2 + 1;     // update q2
1495       r2 = 2*r2 + 1 - d; // update r2
1496     }
1497     else {
1498       if (q2 >= 0x8000000000000000ull) magu.a = 1;
1499       q2 = 2*q2;     // update q2
1500       r2 = 2*r2 + 1; // update r2
1501     }
1502     delta = d - 1 - r2;
1503   } while (p < 128 && (q1 < delta || (q1 == delta && r1 == 0)));
1504   magu.m = q2 + 1; // resulting magic number
1505   magu.s = p - 64;  // resulting shift
1506   return magu;
1507 }
1508
1509 /// BuildSDIVSequence - Given an ISD::SDIV node expressing a divide by constant,
1510 /// return a DAG expression to select that will generate the same value by
1511 /// multiplying by a magic number.  See:
1512 /// <http://the.wall.riscom.net/books/proc/ppc/cwg/code2.html>
1513 SDOperand TargetLowering::BuildSDIV(SDNode *N, SelectionDAG &DAG,
1514                                     std::list<SDNode*>* Created) const {
1515   MVT::ValueType VT = N->getValueType(0);
1516
1517   // Check to see if we can do this.
1518   if (!isTypeLegal(VT) || (VT != MVT::i32 && VT != MVT::i64))
1519     return SDOperand();       // BuildSDIV only operates on i32 or i64
1520   if (!isOperationLegal(ISD::MULHS, VT))
1521     return SDOperand();       // Make sure the target supports MULHS.
1522
1523   int64_t d = cast<ConstantSDNode>(N->getOperand(1))->getSignExtended();
1524   ms magics = (VT == MVT::i32) ? magic32(d) : magic64(d);
1525
1526   // Multiply the numerator (operand 0) by the magic value
1527   SDOperand Q = DAG.getNode(ISD::MULHS, VT, N->getOperand(0),
1528                             DAG.getConstant(magics.m, VT));
1529   // If d > 0 and m < 0, add the numerator
1530   if (d > 0 && magics.m < 0) {
1531     Q = DAG.getNode(ISD::ADD, VT, Q, N->getOperand(0));
1532     if (Created)
1533       Created->push_back(Q.Val);
1534   }
1535   // If d < 0 and m > 0, subtract the numerator.
1536   if (d < 0 && magics.m > 0) {
1537     Q = DAG.getNode(ISD::SUB, VT, Q, N->getOperand(0));
1538     if (Created)
1539       Created->push_back(Q.Val);
1540   }
1541   // Shift right algebraic if shift value is nonzero
1542   if (magics.s > 0) {
1543     Q = DAG.getNode(ISD::SRA, VT, Q,
1544                     DAG.getConstant(magics.s, getShiftAmountTy()));
1545     if (Created)
1546       Created->push_back(Q.Val);
1547   }
1548   // Extract the sign bit and add it to the quotient
1549   SDOperand T =
1550     DAG.getNode(ISD::SRL, VT, Q, DAG.getConstant(MVT::getSizeInBits(VT)-1,
1551                                                  getShiftAmountTy()));
1552   if (Created)
1553     Created->push_back(T.Val);
1554   return DAG.getNode(ISD::ADD, VT, Q, T);
1555 }
1556
1557 /// BuildUDIVSequence - Given an ISD::UDIV node expressing a divide by constant,
1558 /// return a DAG expression to select that will generate the same value by
1559 /// multiplying by a magic number.  See:
1560 /// <http://the.wall.riscom.net/books/proc/ppc/cwg/code2.html>
1561 SDOperand TargetLowering::BuildUDIV(SDNode *N, SelectionDAG &DAG,
1562                                     std::list<SDNode*>* Created) const {
1563   MVT::ValueType VT = N->getValueType(0);
1564
1565   // Check to see if we can do this.
1566   if (!isTypeLegal(VT) || (VT != MVT::i32 && VT != MVT::i64))
1567     return SDOperand();       // BuildUDIV only operates on i32 or i64
1568   if (!isOperationLegal(ISD::MULHU, VT))
1569     return SDOperand();       // Make sure the target supports MULHU.
1570
1571   uint64_t d = cast<ConstantSDNode>(N->getOperand(1))->getValue();
1572   mu magics = (VT == MVT::i32) ? magicu32(d) : magicu64(d);
1573
1574   // Multiply the numerator (operand 0) by the magic value
1575   SDOperand Q = DAG.getNode(ISD::MULHU, VT, N->getOperand(0),
1576                             DAG.getConstant(magics.m, VT));
1577   if (Created)
1578     Created->push_back(Q.Val);
1579
1580   if (magics.a == 0) {
1581     return DAG.getNode(ISD::SRL, VT, Q,
1582                        DAG.getConstant(magics.s, getShiftAmountTy()));
1583   } else {
1584     SDOperand NPQ = DAG.getNode(ISD::SUB, VT, N->getOperand(0), Q);
1585     if (Created)
1586       Created->push_back(NPQ.Val);
1587     NPQ = DAG.getNode(ISD::SRL, VT, NPQ,
1588                       DAG.getConstant(1, getShiftAmountTy()));
1589     if (Created)
1590       Created->push_back(NPQ.Val);
1591     NPQ = DAG.getNode(ISD::ADD, VT, NPQ, Q);
1592     if (Created)
1593       Created->push_back(NPQ.Val);
1594     return DAG.getNode(ISD::SRL, VT, NPQ,
1595                        DAG.getConstant(magics.s-1, getShiftAmountTy()));
1596   }
1597 }