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