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