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