lib/CodeGen/SelectionDAG/TargetLowering.cpp

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