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