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 HighBits = (1ULL << ShAmt)-1;
 446       HighBits <<= MVT::getSizeInBits(VT) - ShAmt;
 447       uint64_t TypeMask = MVT::getIntVTBitMask(VT);
 448
 449       if (SimplifyDemandedBits(Op.getOperand(0),
 450                                (DemandedMask << ShAmt) & TypeMask,
 451                                KnownZero, KnownOne, TLO, Depth+1))
 452         return true;
 453       assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 454       KnownZero &= TypeMask;
 455       KnownOne  &= TypeMask;
 456       KnownZero >>= ShAmt;
 457       KnownOne  >>= 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 HighBits = (1ULL << ShAmt)-1;
 468       HighBits <<= MVT::getSizeInBits(VT) - ShAmt;
 469       uint64_t TypeMask = MVT::getIntVTBitMask(VT);
 470
 471       uint64_t InDemandedMask = (DemandedMask << ShAmt) & TypeMask;
 472
 473       // If any of the demanded bits are produced by the sign extension, we also
 474       // demand the input sign bit.
 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 >>= SA->getValue();
 485       KnownOne  >>= SA->getValue();
 486
 487       // Handle the sign bits.
 488       uint64_t SignBit = MVT::getIntVTSignBit(VT);
 489       SignBit >>= SA->getValue();  // 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       uint64_t LowBits = (1ULL << SA->getValue())-1;
 784       Mask >>= SA->getValue();
 785       ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero, KnownOne, Depth+1);
 786       assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 787       KnownZero <<= SA->getValue();
 788       KnownOne  <<= SA->getValue();
 789       KnownZero |= LowBits;  // low bits known zero
 790       KnownOne &= ~LowBits;  // and known not to be one.
 791     }
 792     return;
 793   case ISD::SRL:
 794     // (ushr X, C1) & C2 == 0   iff  (-1 >> C1) & C2 == 0
 795     if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
 796       uint64_t HighBits = (1ULL << SA->getValue())-1;
 797       HighBits <<= MVT::getSizeInBits(Op.getValueType())-SA->getValue();
 798       Mask <<= SA->getValue();
 799       ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero, KnownOne, Depth+1);
 800       assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 801       KnownZero >>= SA->getValue();
 802       KnownOne  >>= SA->getValue();
 803       KnownZero |= HighBits;  // high bits known zero
 804       KnownOne  &= ~HighBits; // and known not to be one.
 805     }
 806     return;
 807   case ISD::SRA:
 808     if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
 809       uint64_t HighBits = (1ULL << SA->getValue())-1;
 810       HighBits <<= MVT::getSizeInBits(Op.getValueType())-SA->getValue();
 811       Mask <<= SA->getValue();
 812       ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero, KnownOne, Depth+1);
 813       assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
 814       KnownZero >>= SA->getValue();
 815       KnownOne  >>= SA->getValue();
 816
 817       // Handle the sign bits.
 818       uint64_t SignBit = 1ULL << (MVT::getSizeInBits(Op.getValueType())-1);
 819       SignBit >>= SA->getValue();  // Adjust to where it is now in the mask.
 820
 821       if (KnownZero & SignBit) {
 822         KnownZero |= HighBits;  // New bits are known zero
 823         KnownOne  &= ~HighBits; // and known not to be one.
 824       } else if (KnownOne & SignBit) {
 825         KnownOne  |= HighBits;  // New bits are known one
 826         KnownZero &= ~HighBits; // and known not to be zero.
 827       }
 828     }
 829     return;
 830   case ISD::SIGN_EXTEND_INREG: {
 831     MVT::ValueType  VT = Op.getValueType();
 832     MVT::ValueType EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
 833
 834     // Sign extension.  Compute the demanded bits in the result that are not
 835     // present in the input.
 836     uint64_t NewBits = ~MVT::getIntVTBitMask(EVT) & Mask;
 837
 838     uint64_t InSignBit = MVT::getIntVTSignBit(EVT);
 839     int64_t InputDemandedBits = Mask & MVT::getIntVTBitMask(EVT);
 840
 841     // If the sign extended bits are demanded, we know that the sign
 842     // bit is demanded.
 843     if (NewBits)
 844       InputDemandedBits |= InSignBit;
 845
 846     ComputeMaskedBits(Op.getOperand(0), InputDemandedBits,
 847                       KnownZero, KnownOne, Depth+1);
 848     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 849
 850     // If the sign bit of the input is known set or clear, then we know the
 851     // top bits of the result.
 852     if (KnownZero & InSignBit) {          // Input sign bit known clear
 853       KnownZero |= NewBits;
 854       KnownOne  &= ~NewBits;
 855     } else if (KnownOne & InSignBit) {    // Input sign bit known set
 856       KnownOne  |= NewBits;
 857       KnownZero &= ~NewBits;
 858     } else {                              // Input sign bit unknown
 859       KnownZero &= ~NewBits;
 860       KnownOne  &= ~NewBits;
 861     }
 862     return;
 863   }
 864   case ISD::CTTZ:
 865   case ISD::CTLZ:
 866   case ISD::CTPOP: {
 867     MVT::ValueType VT = Op.getValueType();
 868     unsigned LowBits = Log2_32(MVT::getSizeInBits(VT))+1;
 869     KnownZero = ~((1ULL << LowBits)-1) & MVT::getIntVTBitMask(VT);
 870     KnownOne  = 0;
 871     return;
 872   }
 873   case ISD::ZEXTLOAD: {
 874     MVT::ValueType VT = cast<VTSDNode>(Op.getOperand(3))->getVT();
 875     KnownZero |= ~MVT::getIntVTBitMask(VT) & Mask;
 876     return;
 877   }
 878   case ISD::ZERO_EXTEND: {
 879     uint64_t InMask  = MVT::getIntVTBitMask(Op.getOperand(0).getValueType());
 880     uint64_t NewBits = (~InMask) & Mask;
 881     ComputeMaskedBits(Op.getOperand(0), Mask & InMask, KnownZero,
 882                       KnownOne, Depth+1);
 883     KnownZero |= NewBits & Mask;
 884     KnownOne  &= ~NewBits;
 885     return;
 886   }
 887   case ISD::SIGN_EXTEND: {
 888     MVT::ValueType InVT = Op.getOperand(0).getValueType();
 889     unsigned InBits    = MVT::getSizeInBits(InVT);
 890     uint64_t InMask    = MVT::getIntVTBitMask(InVT);
 891     uint64_t InSignBit = 1ULL << (InBits-1);
 892     uint64_t NewBits   = (~InMask) & Mask;
 893     uint64_t InDemandedBits = Mask & InMask;
 894
 895     // If any of the sign extended bits are demanded, we know that the sign
 896     // bit is demanded.
 897     if (NewBits & Mask)
 898       InDemandedBits |= InSignBit;
 899
 900     ComputeMaskedBits(Op.getOperand(0), InDemandedBits, KnownZero,
 901                       KnownOne, Depth+1);
 902     // If the sign bit is known zero or one, the  top bits match.
 903     if (KnownZero & InSignBit) {
 904       KnownZero |= NewBits;
 905       KnownOne  &= ~NewBits;
 906     } else if (KnownOne & InSignBit) {
 907       KnownOne  |= NewBits;
 908       KnownZero &= ~NewBits;
 909     } else {   // Otherwise, top bits aren't known.
 910       KnownOne  &= ~NewBits;
 911       KnownZero &= ~NewBits;
 912     }
 913     return;
 914   }
 915   case ISD::ANY_EXTEND: {
 916     MVT::ValueType VT = Op.getOperand(0).getValueType();
 917     ComputeMaskedBits(Op.getOperand(0), Mask & MVT::getIntVTBitMask(VT),
 918                       KnownZero, KnownOne, Depth+1);
 919     return;
 920   }
 921   case ISD::TRUNCATE: {
 922     ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero, KnownOne, Depth+1);
 923     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 924     uint64_t OutMask = MVT::getIntVTBitMask(Op.getValueType());
 925     KnownZero &= OutMask;
 926     KnownOne &= OutMask;
 927     break;
 928   }
 929   case ISD::AssertZext: {
 930     MVT::ValueType VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
 931     uint64_t InMask = MVT::getIntVTBitMask(VT);
 932     ComputeMaskedBits(Op.getOperand(0), Mask & InMask, KnownZero,
 933                       KnownOne, Depth+1);
 934     KnownZero |= (~InMask) & Mask;
 935     return;
 936   }
 937   case ISD::ADD: {
 938     // If either the LHS or the RHS are Zero, the result is zero.
 939     ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1);
 940     ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero2, KnownOne2, Depth+1);
 941     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 942     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
 943
 944     // Output known-0 bits are known if clear or set in both the low clear bits
 945     // common to both LHS & RHS.  For example, 8+(X<<3) is known to have the
 946     // low 3 bits clear.
 947     uint64_t KnownZeroOut = std::min(CountTrailingZeros_64(~KnownZero),
 948                                      CountTrailingZeros_64(~KnownZero2));
 949
 950     KnownZero = (1ULL << KnownZeroOut) - 1;
 951     KnownOne = 0;
 952     return;
 953   }
 954   case ISD::SUB: {
 955     ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0));
 956     if (!CLHS) return;
 957
 958     // We know that the top bits of C-X are clear if X contains less bits
 959     // than C (i.e. no wrap-around can happen).  For example, 20-X is
 960     // positive if we can prove that X is >= 0 and < 16.
 961     MVT::ValueType VT = CLHS->getValueType(0);
 962     if ((CLHS->getValue() & MVT::getIntVTSignBit(VT)) == 0) {  // sign bit clear
 963       unsigned NLZ = CountLeadingZeros_64(CLHS->getValue()+1);
 964       uint64_t MaskV = (1ULL << (63-NLZ))-1; // NLZ can't be 64 with no sign bit
 965       MaskV = ~MaskV & MVT::getIntVTBitMask(VT);
 966       ComputeMaskedBits(Op.getOperand(1), MaskV, KnownZero, KnownOne, Depth+1);
 967
 968       // If all of the MaskV bits are known to be zero, then we know the output
 969       // top bits are zero, because we now know that the output is from [0-C].
 970       if ((KnownZero & MaskV) == MaskV) {
 971         unsigned NLZ2 = CountLeadingZeros_64(CLHS->getValue());
 972         KnownZero = ~((1ULL << (64-NLZ2))-1) & Mask;  // Top bits known zero.
 973         KnownOne = 0;   // No one bits known.
 974       } else {
 975         KnownOne = KnownOne = 0;  // Otherwise, nothing known.
 976       }
 977     }
 978     return;
 979   }
 980   default:
 981     // Allow the target to implement this method for its nodes.
 982     if (Op.getOpcode() >= ISD::BUILTIN_OP_END) {
 983   case ISD::INTRINSIC_WO_CHAIN:
 984   case ISD::INTRINSIC_W_CHAIN:
 985   case ISD::INTRINSIC_VOID:
 986       computeMaskedBitsForTargetNode(Op, Mask, KnownZero, KnownOne);
 987     }
 988     return;
 989   }
 990 }
 991
 992 /// computeMaskedBitsForTargetNode - Determine which of the bits specified
 993 /// in Mask are known to be either zero or one and return them in the
 994 /// KnownZero/KnownOne bitsets.
 995 void TargetLowering::computeMaskedBitsForTargetNode(const SDOperand Op,
 996                                                     uint64_t Mask,
 997                                                     uint64_t &KnownZero,
 998                                                     uint64_t &KnownOne,
 999                                                     unsigned Depth) const {
1000   assert((Op.getOpcode() >= ISD::BUILTIN_OP_END ||
1001           Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
1002           Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
1003           Op.getOpcode() == ISD::INTRINSIC_VOID) &&
1004          "Should use MaskedValueIsZero if you don't know whether Op"
1005          " is a target node!");
1006   KnownZero = 0;
1007   KnownOne = 0;
1008 }
1009
1010 /// ComputeNumSignBits - Return the number of times the sign bit of the
1011 /// register is replicated into the other bits.  We know that at least 1 bit
1012 /// is always equal to the sign bit (itself), but other cases can give us
1013 /// information.  For example, immediately after an "SRA X, 2", we know that
1014 /// the top 3 bits are all equal to each other, so we return 3.
1015 unsigned TargetLowering::ComputeNumSignBits(SDOperand Op, unsigned Depth) const{
1016   MVT::ValueType VT = Op.getValueType();
1017   assert(MVT::isInteger(VT) && "Invalid VT!");
1018   unsigned VTBits = MVT::getSizeInBits(VT);
1019   unsigned Tmp, Tmp2;
1020
1021   if (Depth == 6)
1022     return 1;  // Limit search depth.
1023
1024   switch (Op.getOpcode()) {
1025   default: break;
1026   case ISD::AssertSext:
1027     Tmp = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(1))->getVT());
1028     return VTBits-Tmp+1;
1029   case ISD::AssertZext:
1030     Tmp = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(1))->getVT());
1031     return VTBits-Tmp;
1032
1033   case ISD::SEXTLOAD:    // '17' bits known
1034     Tmp = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(3))->getVT());
1035     return VTBits-Tmp+1;
1036   case ISD::ZEXTLOAD:    // '16' bits known
1037     Tmp = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(3))->getVT());
1038     return VTBits-Tmp;
1039
1040   case ISD::Constant: {
1041     uint64_t Val = cast<ConstantSDNode>(Op)->getValue();
1042     // If negative, invert the bits, then look at it.
1043     if (Val & MVT::getIntVTSignBit(VT))
1044       Val = ~Val;
1045
1046     // Shift the bits so they are the leading bits in the int64_t.
1047     Val <<= 64-VTBits;
1048
1049     // Return # leading zeros.  We use 'min' here in case Val was zero before
1050     // shifting.  We don't want to return '64' as for an i32 "0".
1051     return std::min(VTBits, CountLeadingZeros_64(Val));
1052   }
1053
1054   case ISD::SIGN_EXTEND:
1055     Tmp = VTBits-MVT::getSizeInBits(Op.getOperand(0).getValueType());
1056     return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
1057
1058   case ISD::SIGN_EXTEND_INREG:
1059     // Max of the input and what this extends.
1060     Tmp = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(1))->getVT());
1061     Tmp = VTBits-Tmp+1;
1062
1063     Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1064     return std::max(Tmp, Tmp2);
1065
1066   case ISD::SRA:
1067     Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1068     // SRA X, C   -> adds C sign bits.
1069     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1070       Tmp += C->getValue();
1071       if (Tmp > VTBits) Tmp = VTBits;
1072     }
1073     return Tmp;
1074   case ISD::SHL:
1075     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1076       // shl destroys sign bits.
1077       Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1078       if (C->getValue() >= VTBits ||      // Bad shift.
1079           C->getValue() >= Tmp) break;    // Shifted all sign bits out.
1080       return Tmp - C->getValue();
1081     }
1082     break;
1083   case ISD::AND:
1084   case ISD::OR:
1085   case ISD::XOR:    // NOT is handled here.
1086     // Logical binary ops preserve the number of sign bits.
1087     Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1088     if (Tmp == 1) return 1;  // Early out.
1089     Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
1090     return std::min(Tmp, Tmp2);
1091
1092   case ISD::SELECT:
1093     Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1094     if (Tmp == 1) return 1;  // Early out.
1095     Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
1096     return std::min(Tmp, Tmp2);
1097
1098   case ISD::SETCC:
1099     // If setcc returns 0/-1, all bits are sign bits.
1100     if (getSetCCResultContents() == ZeroOrNegativeOneSetCCResult)
1101       return VTBits;
1102     break;
1103   case ISD::ROTL:
1104   case ISD::ROTR:
1105     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1106       unsigned RotAmt = C->getValue() & (VTBits-1);
1107
1108       // Handle rotate right by N like a rotate left by 32-N.
1109       if (Op.getOpcode() == ISD::ROTR)
1110         RotAmt = (VTBits-RotAmt) & (VTBits-1);
1111
1112       // If we aren't rotating out all of the known-in sign bits, return the
1113       // number that are left.  This handles rotl(sext(x), 1) for example.
1114       Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1115       if (Tmp > RotAmt+1) return Tmp-RotAmt;
1116     }
1117     break;
1118   case ISD::ADD:
1119     // Add can have at most one carry bit.  Thus we know that the output
1120     // is, at worst, one more bit than the inputs.
1121     Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1122     if (Tmp == 1) return 1;  // Early out.
1123
1124     // Special case decrementing a value (ADD X, -1):
1125     if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
1126       if (CRHS->isAllOnesValue()) {
1127         uint64_t KnownZero, KnownOne;
1128         uint64_t Mask = MVT::getIntVTBitMask(VT);
1129         ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero, KnownOne, Depth+1);
1130
1131         // If the input is known to be 0 or 1, the output is 0/-1, which is all
1132         // sign bits set.
1133         if ((KnownZero|1) == Mask)
1134           return VTBits;
1135
1136         // If we are subtracting one from a positive number, there is no carry
1137         // out of the result.
1138         if (KnownZero & MVT::getIntVTSignBit(VT))
1139           return Tmp;
1140       }
1141
1142     Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
1143     if (Tmp2 == 1) return 1;
1144       return std::min(Tmp, Tmp2)-1;
1145     break;
1146
1147   case ISD::SUB:
1148     Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
1149     if (Tmp2 == 1) return 1;
1150
1151     // Handle NEG.
1152     if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
1153       if (CLHS->getValue() == 0) {
1154         uint64_t KnownZero, KnownOne;
1155         uint64_t Mask = MVT::getIntVTBitMask(VT);
1156         ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1);
1157         // If the input is known to be 0 or 1, the output is 0/-1, which is all
1158         // sign bits set.
1159         if ((KnownZero|1) == Mask)
1160           return VTBits;
1161
1162         // If the input is known to be positive (the sign bit is known clear),
1163         // the output of the NEG has the same number of sign bits as the input.
1164         if (KnownZero & MVT::getIntVTSignBit(VT))
1165           return Tmp2;
1166
1167         // Otherwise, we treat this like a SUB.
1168       }
1169
1170     // Sub can have at most one carry bit.  Thus we know that the output
1171     // is, at worst, one more bit than the inputs.
1172     Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1173     if (Tmp == 1) return 1;  // Early out.
1174       return std::min(Tmp, Tmp2)-1;
1175     break;
1176   case ISD::TRUNCATE:
1177     // FIXME: it's tricky to do anything useful for this, but it is an important
1178     // case for targets like X86.
1179     break;
1180   }
1181
1182   // Allow the target to implement this method for its nodes.
1183   if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
1184       Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
1185       Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
1186       Op.getOpcode() == ISD::INTRINSIC_VOID) {
1187     unsigned NumBits = ComputeNumSignBitsForTargetNode(Op, Depth);
1188     if (NumBits > 1) return NumBits;
1189   }
1190
1191   // Finally, if we can prove that the top bits of the result are 0's or 1's,
1192   // use this information.
1193   uint64_t KnownZero, KnownOne;
1194   uint64_t Mask = MVT::getIntVTBitMask(VT);
1195   ComputeMaskedBits(Op, Mask, KnownZero, KnownOne, Depth);
1196
1197   uint64_t SignBit = MVT::getIntVTSignBit(VT);
1198   if (KnownZero & SignBit) {        // SignBit is 0
1199     Mask = KnownZero;
1200   } else if (KnownOne & SignBit) {  // SignBit is 1;
1201     Mask = KnownOne;
1202   } else {
1203     // Nothing known.
1204     return 1;
1205   }
1206
1207   // Okay, we know that the sign bit in Mask is set.  Use CLZ to determine
1208   // the number of identical bits in the top of the input value.
1209   Mask ^= ~0ULL;
1210   Mask <<= 64-VTBits;
1211   // Return # leading zeros.  We use 'min' here in case Val was zero before
1212   // shifting.  We don't want to return '64' as for an i32 "0".
1213   return std::min(VTBits, CountLeadingZeros_64(Mask));
1214 }
1215
1216
1217
1218 /// ComputeNumSignBitsForTargetNode - This method can be implemented by
1219 /// targets that want to expose additional information about sign bits to the
1220 /// DAG Combiner.
1221 unsigned TargetLowering::ComputeNumSignBitsForTargetNode(SDOperand Op,
1222                                                          unsigned Depth) const {
1223   assert((Op.getOpcode() >= ISD::BUILTIN_OP_END ||
1224           Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
1225           Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
1226           Op.getOpcode() == ISD::INTRINSIC_VOID) &&
1227          "Should use ComputeNumSignBits if you don't know whether Op"
1228          " is a target node!");
1229   return 1;
1230 }
1231
1232
1233 SDOperand TargetLowering::
1234 PerformDAGCombine(SDNode *N, DAGCombinerInfo &DCI) const {
1235   // Default implementation: no optimization.
1236   return SDOperand();
1237 }
1238
1239 //===----------------------------------------------------------------------===//
1240 //  Inline Assembler Implementation Methods
1241 //===----------------------------------------------------------------------===//
1242
1243 TargetLowering::ConstraintType
1244 TargetLowering::getConstraintType(char ConstraintLetter) const {
1245   // FIXME: lots more standard ones to handle.
1246   switch (ConstraintLetter) {
1247   default: return C_Unknown;
1248   case 'r': return C_RegisterClass;
1249   case 'm':    // memory
1250   case 'o':    // offsetable
1251   case 'V':    // not offsetable
1252     return C_Memory;
1253   case 'i':    // Simple Integer or Relocatable Constant
1254   case 'n':    // Simple Integer
1255   case 's':    // Relocatable Constant
1256   case 'I':    // Target registers.
1257   case 'J':
1258   case 'K':
1259   case 'L':
1260   case 'M':
1261   case 'N':
1262   case 'O':
1263   case 'P':
1264     return C_Other;
1265   }
1266 }
1267
1268 bool TargetLowering::isOperandValidForConstraint(SDOperand Op,
1269                                                  char ConstraintLetter) {
1270   switch (ConstraintLetter) {
1271   default: return false;
1272   case 'i':    // Simple Integer or Relocatable Constant
1273   case 'n':    // Simple Integer
1274   case 's':    // Relocatable Constant
1275     return true;   // FIXME: not right.
1276   }
1277 }
1278
1279
1280 std::vector<unsigned> TargetLowering::
1281 getRegClassForInlineAsmConstraint(const std::string &Constraint,
1282                                   MVT::ValueType VT) const {
1283   return std::vector<unsigned>();
1284 }
1285
1286
1287 std::pair<unsigned, const TargetRegisterClass*> TargetLowering::
1288 getRegForInlineAsmConstraint(const std::string &Constraint,
1289                              MVT::ValueType VT) const {
1290   if (Constraint[0] != '{')
1291     return std::pair<unsigned, const TargetRegisterClass*>(0, 0);
1292   assert(*(Constraint.end()-1) == '}' && "Not a brace enclosed constraint?");
1293
1294   // Remove the braces from around the name.
1295   std::string RegName(Constraint.begin()+1, Constraint.end()-1);
1296
1297   // Figure out which register class contains this reg.
1298   const MRegisterInfo *RI = TM.getRegisterInfo();
1299   for (MRegisterInfo::regclass_iterator RCI = RI->regclass_begin(),
1300        E = RI->regclass_end(); RCI != E; ++RCI) {
1301     const TargetRegisterClass *RC = *RCI;
1302
1303     // If none of the the value types for this register class are valid, we
1304     // can't use it.  For example, 64-bit reg classes on 32-bit targets.
1305     bool isLegal = false;
1306     for (TargetRegisterClass::vt_iterator I = RC->vt_begin(), E = RC->vt_end();
1307          I != E; ++I) {
1308       if (isTypeLegal(*I)) {
1309         isLegal = true;
1310         break;
1311       }
1312     }
1313
1314     if (!isLegal) continue;
1315
1316     for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end();
1317          I != E; ++I) {
1318       if (StringsEqualNoCase(RegName, RI->get(*I).Name))
1319         return std::make_pair(*I, RC);
1320     }
1321   }
1322
1323   return std::pair<unsigned, const TargetRegisterClass*>(0, 0);
1324 }
1325
1326 //===----------------------------------------------------------------------===//
1327 //  Loop Strength Reduction hooks
1328 //===----------------------------------------------------------------------===//
1329
1330 /// isLegalAddressImmediate - Return true if the integer value or
1331 /// GlobalValue can be used as the offset of the target addressing mode.
1332 bool TargetLowering::isLegalAddressImmediate(int64_t V) const {
1333   return false;
1334 }
1335 bool TargetLowering::isLegalAddressImmediate(GlobalValue *GV) const {
1336   return false;
1337 }
1338
1339
1340 // Magic for divide replacement
1341
1342 struct ms {
1343   int64_t m;  // magic number
1344   int64_t s;  // shift amount
1345 };
1346
1347 struct mu {
1348   uint64_t m; // magic number
1349   int64_t a;  // add indicator
1350   int64_t s;  // shift amount
1351 };
1352
1353 /// magic - calculate the magic numbers required to codegen an integer sdiv as
1354 /// a sequence of multiply and shifts.  Requires that the divisor not be 0, 1,
1355 /// or -1.
1356 static ms magic32(int32_t d) {
1357   int32_t p;
1358   uint32_t ad, anc, delta, q1, r1, q2, r2, t;
1359   const uint32_t two31 = 0x80000000U;
1360   struct ms mag;
1361
1362   ad = abs(d);
1363   t = two31 + ((uint32_t)d >> 31);
1364   anc = t - 1 - t%ad;   // absolute value of nc
1365   p = 31;               // initialize p
1366   q1 = two31/anc;       // initialize q1 = 2p/abs(nc)
1367   r1 = two31 - q1*anc;  // initialize r1 = rem(2p,abs(nc))
1368   q2 = two31/ad;        // initialize q2 = 2p/abs(d)
1369   r2 = two31 - q2*ad;   // initialize r2 = rem(2p,abs(d))
1370   do {
1371     p = p + 1;
1372     q1 = 2*q1;        // update q1 = 2p/abs(nc)
1373     r1 = 2*r1;        // update r1 = rem(2p/abs(nc))
1374     if (r1 >= anc) {  // must be unsigned comparison
1375       q1 = q1 + 1;
1376       r1 = r1 - anc;
1377     }
1378     q2 = 2*q2;        // update q2 = 2p/abs(d)
1379     r2 = 2*r2;        // update r2 = rem(2p/abs(d))
1380     if (r2 >= ad) {   // must be unsigned comparison
1381       q2 = q2 + 1;
1382       r2 = r2 - ad;
1383     }
1384     delta = ad - r2;
1385   } while (q1 < delta || (q1 == delta && r1 == 0));
1386
1387   mag.m = (int32_t)(q2 + 1); // make sure to sign extend
1388   if (d < 0) mag.m = -mag.m; // resulting magic number
1389   mag.s = p - 32;            // resulting shift
1390   return mag;
1391 }
1392
1393 /// magicu - calculate the magic numbers required to codegen an integer udiv as
1394 /// a sequence of multiply, add and shifts.  Requires that the divisor not be 0.
1395 static mu magicu32(uint32_t d) {
1396   int32_t p;
1397   uint32_t nc, delta, q1, r1, q2, r2;
1398   struct mu magu;
1399   magu.a = 0;               // initialize "add" indicator
1400   nc = - 1 - (-d)%d;
1401   p = 31;                   // initialize p
1402   q1 = 0x80000000/nc;       // initialize q1 = 2p/nc
1403   r1 = 0x80000000 - q1*nc;  // initialize r1 = rem(2p,nc)
1404   q2 = 0x7FFFFFFF/d;        // initialize q2 = (2p-1)/d
1405   r2 = 0x7FFFFFFF - q2*d;   // initialize r2 = rem((2p-1),d)
1406   do {
1407     p = p + 1;
1408     if (r1 >= nc - r1 ) {
1409       q1 = 2*q1 + 1;  // update q1
1410       r1 = 2*r1 - nc; // update r1
1411     }
1412     else {
1413       q1 = 2*q1; // update q1
1414       r1 = 2*r1; // update r1
1415     }
1416     if (r2 + 1 >= d - r2) {
1417       if (q2 >= 0x7FFFFFFF) magu.a = 1;
1418       q2 = 2*q2 + 1;     // update q2
1419       r2 = 2*r2 + 1 - d; // update r2
1420     }
1421     else {
1422       if (q2 >= 0x80000000) magu.a = 1;
1423       q2 = 2*q2;     // update q2
1424       r2 = 2*r2 + 1; // update r2
1425     }
1426     delta = d - 1 - r2;
1427   } while (p < 64 && (q1 < delta || (q1 == delta && r1 == 0)));
1428   magu.m = q2 + 1; // resulting magic number
1429   magu.s = p - 32;  // resulting shift
1430   return magu;
1431 }
1432
1433 /// magic - calculate the magic numbers required to codegen an integer sdiv as
1434 /// a sequence of multiply and shifts.  Requires that the divisor not be 0, 1,
1435 /// or -1.
1436 static ms magic64(int64_t d) {
1437   int64_t p;
1438   uint64_t ad, anc, delta, q1, r1, q2, r2, t;
1439   const uint64_t two63 = 9223372036854775808ULL; // 2^63
1440   struct ms mag;
1441
1442   ad = d >= 0 ? d : -d;
1443   t = two63 + ((uint64_t)d >> 63);
1444   anc = t - 1 - t%ad;   // absolute value of nc
1445   p = 63;               // initialize p
1446   q1 = two63/anc;       // initialize q1 = 2p/abs(nc)
1447   r1 = two63 - q1*anc;  // initialize r1 = rem(2p,abs(nc))
1448   q2 = two63/ad;        // initialize q2 = 2p/abs(d)
1449   r2 = two63 - q2*ad;   // initialize r2 = rem(2p,abs(d))
1450   do {
1451     p = p + 1;
1452     q1 = 2*q1;        // update q1 = 2p/abs(nc)
1453     r1 = 2*r1;        // update r1 = rem(2p/abs(nc))
1454     if (r1 >= anc) {  // must be unsigned comparison
1455       q1 = q1 + 1;
1456       r1 = r1 - anc;
1457     }
1458     q2 = 2*q2;        // update q2 = 2p/abs(d)
1459     r2 = 2*r2;        // update r2 = rem(2p/abs(d))
1460     if (r2 >= ad) {   // must be unsigned comparison
1461       q2 = q2 + 1;
1462       r2 = r2 - ad;
1463     }
1464     delta = ad - r2;
1465   } while (q1 < delta || (q1 == delta && r1 == 0));
1466
1467   mag.m = q2 + 1;
1468   if (d < 0) mag.m = -mag.m; // resulting magic number
1469   mag.s = p - 64;            // resulting shift
1470   return mag;
1471 }
1472
1473 /// magicu - calculate the magic numbers required to codegen an integer udiv as
1474 /// a sequence of multiply, add and shifts.  Requires that the divisor not be 0.
1475 static mu magicu64(uint64_t d)
1476 {
1477   int64_t p;
1478   uint64_t nc, delta, q1, r1, q2, r2;
1479   struct mu magu;
1480   magu.a = 0;               // initialize "add" indicator
1481   nc = - 1 - (-d)%d;
1482   p = 63;                   // initialize p
1483   q1 = 0x8000000000000000ull/nc;       // initialize q1 = 2p/nc
1484   r1 = 0x8000000000000000ull - q1*nc;  // initialize r1 = rem(2p,nc)
1485   q2 = 0x7FFFFFFFFFFFFFFFull/d;        // initialize q2 = (2p-1)/d
1486   r2 = 0x7FFFFFFFFFFFFFFFull - q2*d;   // initialize r2 = rem((2p-1),d)
1487   do {
1488     p = p + 1;
1489     if (r1 >= nc - r1 ) {
1490       q1 = 2*q1 + 1;  // update q1
1491       r1 = 2*r1 - nc; // update r1
1492     }
1493     else {
1494       q1 = 2*q1; // update q1
1495       r1 = 2*r1; // update r1
1496     }
1497     if (r2 + 1 >= d - r2) {
1498       if (q2 >= 0x7FFFFFFFFFFFFFFFull) magu.a = 1;
1499       q2 = 2*q2 + 1;     // update q2
1500       r2 = 2*r2 + 1 - d; // update r2
1501     }
1502     else {
1503       if (q2 >= 0x8000000000000000ull) magu.a = 1;
1504       q2 = 2*q2;     // update q2
1505       r2 = 2*r2 + 1; // update r2
1506     }
1507     delta = d - 1 - r2;
1508   } while (p < 128 && (q1 < delta || (q1 == delta && r1 == 0)));
1509   magu.m = q2 + 1; // resulting magic number
1510   magu.s = p - 64;  // resulting shift
1511   return magu;
1512 }
1513
1514 /// BuildSDIVSequence - Given an ISD::SDIV node expressing a divide by constant,
1515 /// return a DAG expression to select that will generate the same value by
1516 /// multiplying by a magic number.  See:
1517 /// <http://the.wall.riscom.net/books/proc/ppc/cwg/code2.html>
1518 SDOperand TargetLowering::BuildSDIV(SDNode *N, SelectionDAG &DAG,
1519                                     std::vector<SDNode*>* Created) const {
1520   MVT::ValueType VT = N->getValueType(0);
1521
1522   // Check to see if we can do this.
1523   if (!isTypeLegal(VT) || (VT != MVT::i32 && VT != MVT::i64))
1524     return SDOperand();       // BuildSDIV only operates on i32 or i64
1525   if (!isOperationLegal(ISD::MULHS, VT))
1526     return SDOperand();       // Make sure the target supports MULHS.
1527
1528   int64_t d = cast<ConstantSDNode>(N->getOperand(1))->getSignExtended();
1529   ms magics = (VT == MVT::i32) ? magic32(d) : magic64(d);
1530
1531   // Multiply the numerator (operand 0) by the magic value
1532   SDOperand Q = DAG.getNode(ISD::MULHS, VT, N->getOperand(0),
1533                             DAG.getConstant(magics.m, VT));
1534   // If d > 0 and m < 0, add the numerator
1535   if (d > 0 && magics.m < 0) {
1536     Q = DAG.getNode(ISD::ADD, VT, Q, N->getOperand(0));
1537     if (Created)
1538       Created->push_back(Q.Val);
1539   }
1540   // If d < 0 and m > 0, subtract the numerator.
1541   if (d < 0 && magics.m > 0) {
1542     Q = DAG.getNode(ISD::SUB, VT, Q, N->getOperand(0));
1543     if (Created)
1544       Created->push_back(Q.Val);
1545   }
1546   // Shift right algebraic if shift value is nonzero
1547   if (magics.s > 0) {
1548     Q = DAG.getNode(ISD::SRA, VT, Q,
1549                     DAG.getConstant(magics.s, getShiftAmountTy()));
1550     if (Created)
1551       Created->push_back(Q.Val);
1552   }
1553   // Extract the sign bit and add it to the quotient
1554   SDOperand T =
1555     DAG.getNode(ISD::SRL, VT, Q, DAG.getConstant(MVT::getSizeInBits(VT)-1,
1556                                                  getShiftAmountTy()));
1557   if (Created)
1558     Created->push_back(T.Val);
1559   return DAG.getNode(ISD::ADD, VT, Q, T);
1560 }
1561
1562 /// BuildUDIVSequence - Given an ISD::UDIV node expressing a divide by constant,
1563 /// return a DAG expression to select that will generate the same value by
1564 /// multiplying by a magic number.  See:
1565 /// <http://the.wall.riscom.net/books/proc/ppc/cwg/code2.html>
1566 SDOperand TargetLowering::BuildUDIV(SDNode *N, SelectionDAG &DAG,
1567                                     std::vector<SDNode*>* Created) const {
1568   MVT::ValueType VT = N->getValueType(0);
1569
1570   // Check to see if we can do this.
1571   if (!isTypeLegal(VT) || (VT != MVT::i32 && VT != MVT::i64))
1572     return SDOperand();       // BuildUDIV only operates on i32 or i64
1573   if (!isOperationLegal(ISD::MULHU, VT))
1574     return SDOperand();       // Make sure the target supports MULHU.
1575
1576   uint64_t d = cast<ConstantSDNode>(N->getOperand(1))->getValue();
1577   mu magics = (VT == MVT::i32) ? magicu32(d) : magicu64(d);
1578
1579   // Multiply the numerator (operand 0) by the magic value
1580   SDOperand Q = DAG.getNode(ISD::MULHU, VT, N->getOperand(0),
1581                             DAG.getConstant(magics.m, VT));
1582   if (Created)
1583     Created->push_back(Q.Val);
1584
1585   if (magics.a == 0) {
1586     return DAG.getNode(ISD::SRL, VT, Q,
1587                        DAG.getConstant(magics.s, getShiftAmountTy()));
1588   } else {
1589     SDOperand NPQ = DAG.getNode(ISD::SUB, VT, N->getOperand(0), Q);
1590     if (Created)
1591       Created->push_back(NPQ.Val);
1592     NPQ = DAG.getNode(ISD::SRL, VT, NPQ,
1593                       DAG.getConstant(1, getShiftAmountTy()));
1594     if (Created)
1595       Created->push_back(NPQ.Val);
1596     NPQ = DAG.getNode(ISD::ADD, VT, NPQ, Q);
1597     if (Created)
1598       Created->push_back(NPQ.Val);
1599     return DAG.getNode(ISD::SRL, VT, NPQ,
1600                        DAG.getConstant(magics.s-1, getShiftAmountTy()));
1601   }
1602 }