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