lib/CodeGen/SelectionDAG/TargetLowering.cpp

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