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/TargetMachine.h"
  16 #include "llvm/Target/MRegisterInfo.h"
  17 #include "llvm/CodeGen/SelectionDAG.h"
  18 #include "llvm/ADT/StringExtras.h"
  19 #include "llvm/Support/MathExtras.h"
  20 using namespace llvm;
  21
  22 TargetLowering::TargetLowering(TargetMachine &tm)
  23   : TM(tm), TD(TM.getTargetData()) {
  24   assert(ISD::BUILTIN_OP_END <= 156 &&
  25          "Fixed size array in TargetLowering is not large enough!");
  26   // All operations default to being supported.
  27   memset(OpActions, 0, sizeof(OpActions));
  28
  29   IsLittleEndian = TD.isLittleEndian();
  30   ShiftAmountTy = SetCCResultTy = PointerTy = getValueType(TD.getIntPtrType());
  31   ShiftAmtHandling = Undefined;
  32   memset(RegClassForVT, 0,MVT::LAST_VALUETYPE*sizeof(TargetRegisterClass*));
  33   memset(TargetDAGCombineArray, 0,
  34          sizeof(TargetDAGCombineArray)/sizeof(TargetDAGCombineArray[0]));
  35   maxStoresPerMemset = maxStoresPerMemcpy = maxStoresPerMemmove = 8;
  36   allowUnalignedMemoryAccesses = false;
  37   UseUnderscoreSetJmpLongJmp = false;
  38   IntDivIsCheap = false;
  39   Pow2DivIsCheap = false;
  40   StackPointerRegisterToSaveRestore = 0;
  41   SchedPreferenceInfo = SchedulingForLatency;
  42 }
  43
  44 TargetLowering::~TargetLowering() {}
  45
  46 /// setValueTypeAction - Set the action for a particular value type.  This
  47 /// assumes an action has not already been set for this value type.
  48 static void SetValueTypeAction(MVT::ValueType VT,
  49                                TargetLowering::LegalizeAction Action,
  50                                TargetLowering &TLI,
  51                                MVT::ValueType *TransformToType,
  52                         TargetLowering::ValueTypeActionImpl &ValueTypeActions) {
  53   ValueTypeActions.setTypeAction(VT, Action);
  54   if (Action == TargetLowering::Promote) {
  55     MVT::ValueType PromoteTo;
  56     if (VT == MVT::f32)
  57       PromoteTo = MVT::f64;
  58     else {
  59       unsigned LargerReg = VT+1;
  60       while (!TLI.isTypeLegal((MVT::ValueType)LargerReg)) {
  61         ++LargerReg;
  62         assert(MVT::isInteger((MVT::ValueType)LargerReg) &&
  63                "Nothing to promote to??");
  64       }
  65       PromoteTo = (MVT::ValueType)LargerReg;
  66     }
  67
  68     assert(MVT::isInteger(VT) == MVT::isInteger(PromoteTo) &&
  69            MVT::isFloatingPoint(VT) == MVT::isFloatingPoint(PromoteTo) &&
  70            "Can only promote from int->int or fp->fp!");
  71     assert(VT < PromoteTo && "Must promote to a larger type!");
  72     TransformToType[VT] = PromoteTo;
  73   } else if (Action == TargetLowering::Expand) {
  74     assert((VT == MVT::Vector || MVT::isInteger(VT)) && VT > MVT::i8 &&
  75            "Cannot expand this type: target must support SOME integer reg!");
  76     // Expand to the next smaller integer type!
  77     TransformToType[VT] = (MVT::ValueType)(VT-1);
  78   }
  79 }
  80
  81
  82 /// computeRegisterProperties - Once all of the register classes are added,
  83 /// this allows us to compute derived properties we expose.
  84 void TargetLowering::computeRegisterProperties() {
  85   assert(MVT::LAST_VALUETYPE <= 32 &&
  86          "Too many value types for ValueTypeActions to hold!");
  87
  88   // Everything defaults to one.
  89   for (unsigned i = 0; i != MVT::LAST_VALUETYPE; ++i)
  90     NumElementsForVT[i] = 1;
  91
  92   // Find the largest integer register class.
  93   unsigned LargestIntReg = MVT::i128;
  94   for (; RegClassForVT[LargestIntReg] == 0; --LargestIntReg)
  95     assert(LargestIntReg != MVT::i1 && "No integer registers defined!");
  96
  97   // Every integer value type larger than this largest register takes twice as
  98   // many registers to represent as the previous ValueType.
  99   unsigned ExpandedReg = LargestIntReg; ++LargestIntReg;
 100   for (++ExpandedReg; MVT::isInteger((MVT::ValueType)ExpandedReg);++ExpandedReg)
 101     NumElementsForVT[ExpandedReg] = 2*NumElementsForVT[ExpandedReg-1];
 102
 103   // Inspect all of the ValueType's possible, deciding how to process them.
 104   for (unsigned IntReg = MVT::i1; IntReg <= MVT::i128; ++IntReg)
 105     // If we are expanding this type, expand it!
 106     if (getNumElements((MVT::ValueType)IntReg) != 1)
 107       SetValueTypeAction((MVT::ValueType)IntReg, Expand, *this, TransformToType,
 108                          ValueTypeActions);
 109     else if (!isTypeLegal((MVT::ValueType)IntReg))
 110       // Otherwise, if we don't have native support, we must promote to a
 111       // larger type.
 112       SetValueTypeAction((MVT::ValueType)IntReg, Promote, *this,
 113                          TransformToType, ValueTypeActions);
 114     else
 115       TransformToType[(MVT::ValueType)IntReg] = (MVT::ValueType)IntReg;
 116
 117   // If the target does not have native support for F32, promote it to F64.
 118   if (!isTypeLegal(MVT::f32))
 119     SetValueTypeAction(MVT::f32, Promote, *this,
 120                        TransformToType, ValueTypeActions);
 121   else
 122     TransformToType[MVT::f32] = MVT::f32;
 123
 124   // Set MVT::Vector to always be Expanded
 125   SetValueTypeAction(MVT::Vector, Expand, *this, TransformToType,
 126                      ValueTypeActions);
 127
 128   // Loop over all of the legal vector value types, specifying an identity type
 129   // transformation.
 130   for (unsigned i = MVT::FIRST_VECTOR_VALUETYPE;
 131        i != MVT::LAST_VECTOR_VALUETYPE; ++i) {
 132     if (isTypeLegal((MVT::ValueType)i))
 133       TransformToType[i] = (MVT::ValueType)i;
 134   }
 135
 136   assert(isTypeLegal(MVT::f64) && "Target does not support FP?");
 137   TransformToType[MVT::f64] = MVT::f64;
 138 }
 139
 140 const char *TargetLowering::getTargetNodeName(unsigned Opcode) const {
 141   return NULL;
 142 }
 143
 144 //===----------------------------------------------------------------------===//
 145 //  Optimization Methods
 146 //===----------------------------------------------------------------------===//
 147
 148 /// ShrinkDemandedConstant - Check to see if the specified operand of the
 149 /// specified instruction is a constant integer.  If so, check to see if there
 150 /// are any bits set in the constant that are not demanded.  If so, shrink the
 151 /// constant and return true.
 152 bool TargetLowering::TargetLoweringOpt::ShrinkDemandedConstant(SDOperand Op,
 153                                                             uint64_t Demanded) {
 154   // FIXME: ISD::SELECT, ISD::SELECT_CC
 155   switch(Op.getOpcode()) {
 156   default: break;
 157   case ISD::AND:
 158   case ISD::OR:
 159   case ISD::XOR:
 160     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
 161       if ((~Demanded & C->getValue()) != 0) {
 162         MVT::ValueType VT = Op.getValueType();
 163         SDOperand New = DAG.getNode(Op.getOpcode(), VT, Op.getOperand(0),
 164                                     DAG.getConstant(Demanded & C->getValue(),
 165                                                     VT));
 166         return CombineTo(Op, New);
 167       }
 168     break;
 169   }
 170   return false;
 171 }
 172
 173 /// SimplifyDemandedBits - Look at Op.  At this point, we know that only the
 174 /// DemandedMask bits of the result of Op are ever used downstream.  If we can
 175 /// use this information to simplify Op, create a new simplified DAG node and
 176 /// return true, returning the original and new nodes in Old and New. Otherwise,
 177 /// analyze the expression and return a mask of KnownOne and KnownZero bits for
 178 /// the expression (used to simplify the caller).  The KnownZero/One bits may
 179 /// only be accurate for those bits in the DemandedMask.
 180 bool TargetLowering::SimplifyDemandedBits(SDOperand Op, uint64_t DemandedMask,
 181                                           uint64_t &KnownZero,
 182                                           uint64_t &KnownOne,
 183                                           TargetLoweringOpt &TLO,
 184                                           unsigned Depth) const {
 185   KnownZero = KnownOne = 0;   // Don't know anything.
 186   // Other users may use these bits.
 187   if (!Op.Val->hasOneUse()) {
 188     if (Depth != 0) {
 189       // If not at the root, Just compute the KnownZero/KnownOne bits to
 190       // simplify things downstream.
 191       ComputeMaskedBits(Op, DemandedMask, KnownZero, KnownOne, Depth);
 192       return false;
 193     }
 194     // If this is the root being simplified, allow it to have multiple uses,
 195     // just set the DemandedMask to all bits.
 196     DemandedMask = MVT::getIntVTBitMask(Op.getValueType());
 197   } else if (DemandedMask == 0) {
 198     // Not demanding any bits from Op.
 199     if (Op.getOpcode() != ISD::UNDEF)
 200       return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::UNDEF, Op.getValueType()));
 201     return false;
 202   } else if (Depth == 6) {        // Limit search depth.
 203     return false;
 204   }
 205
 206   uint64_t KnownZero2, KnownOne2, KnownZeroOut, KnownOneOut;
 207   switch (Op.getOpcode()) {
 208   case ISD::Constant:
 209     // We know all of the bits for a constant!
 210     KnownOne = cast<ConstantSDNode>(Op)->getValue() & DemandedMask;
 211     KnownZero = ~KnownOne & DemandedMask;
 212     return false;   // Don't fall through, will infinitely loop.
 213   case ISD::AND:
 214     // If the RHS is a constant, check to see if the LHS would be zero without
 215     // using the bits from the RHS.  Below, we use knowledge about the RHS to
 216     // simplify the LHS, here we're using information from the LHS to simplify
 217     // the RHS.
 218     if (ConstantSDNode *RHSC = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
 219       uint64_t LHSZero, LHSOne;
 220       ComputeMaskedBits(Op.getOperand(0), DemandedMask,
 221                         LHSZero, LHSOne, Depth+1);
 222       // If the LHS already has zeros where RHSC does, this and is dead.
 223       if ((LHSZero & DemandedMask) == (~RHSC->getValue() & DemandedMask))
 224         return TLO.CombineTo(Op, Op.getOperand(0));
 225       // If any of the set bits in the RHS are known zero on the LHS, shrink
 226       // the constant.
 227       if (TLO.ShrinkDemandedConstant(Op, ~LHSZero & DemandedMask))
 228         return true;
 229     }
 230
 231     if (SimplifyDemandedBits(Op.getOperand(1), DemandedMask, KnownZero,
 232                              KnownOne, TLO, Depth+1))
 233       return true;
 234     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 235     if (SimplifyDemandedBits(Op.getOperand(0), DemandedMask & ~KnownZero,
 236                              KnownZero2, KnownOne2, TLO, Depth+1))
 237       return true;
 238     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
 239
 240     // If all of the demanded bits are known one on one side, return the other.
 241     // These bits cannot contribute to the result of the 'and'.
 242     if ((DemandedMask & ~KnownZero2 & KnownOne)==(DemandedMask & ~KnownZero2))
 243       return TLO.CombineTo(Op, Op.getOperand(0));
 244     if ((DemandedMask & ~KnownZero & KnownOne2)==(DemandedMask & ~KnownZero))
 245       return TLO.CombineTo(Op, Op.getOperand(1));
 246     // If all of the demanded bits in the inputs are known zeros, return zero.
 247     if ((DemandedMask & (KnownZero|KnownZero2)) == DemandedMask)
 248       return TLO.CombineTo(Op, TLO.DAG.getConstant(0, Op.getValueType()));
 249     // If the RHS is a constant, see if we can simplify it.
 250     if (TLO.ShrinkDemandedConstant(Op, DemandedMask & ~KnownZero2))
 251       return true;
 252
 253     // Output known-1 bits are only known if set in both the LHS & RHS.
 254     KnownOne &= KnownOne2;
 255     // Output known-0 are known to be clear if zero in either the LHS | RHS.
 256     KnownZero |= KnownZero2;
 257     break;
 258   case ISD::OR:
 259     if (SimplifyDemandedBits(Op.getOperand(1), DemandedMask, KnownZero,
 260                              KnownOne, TLO, Depth+1))
 261       return true;
 262     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 263     if (SimplifyDemandedBits(Op.getOperand(0), DemandedMask & ~KnownOne,
 264                              KnownZero2, KnownOne2, TLO, Depth+1))
 265       return true;
 266     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
 267
 268     // If all of the demanded bits are known zero on one side, return the other.
 269     // These bits cannot contribute to the result of the 'or'.
 270     if ((DemandedMask & ~KnownOne2 & KnownZero) == (DemandedMask & ~KnownOne2))
 271       return TLO.CombineTo(Op, Op.getOperand(0));
 272     if ((DemandedMask & ~KnownOne & KnownZero2) == (DemandedMask & ~KnownOne))
 273       return TLO.CombineTo(Op, Op.getOperand(1));
 274     // If all of the potentially set bits on one side are known to be set on
 275     // the other side, just use the 'other' side.
 276     if ((DemandedMask & (~KnownZero) & KnownOne2) ==
 277         (DemandedMask & (~KnownZero)))
 278       return TLO.CombineTo(Op, Op.getOperand(0));
 279     if ((DemandedMask & (~KnownZero2) & KnownOne) ==
 280         (DemandedMask & (~KnownZero2)))
 281       return TLO.CombineTo(Op, Op.getOperand(1));
 282     // If the RHS is a constant, see if we can simplify it.
 283     if (TLO.ShrinkDemandedConstant(Op, DemandedMask))
 284       return true;
 285
 286     // Output known-0 bits are only known if clear in both the LHS & RHS.
 287     KnownZero &= KnownZero2;
 288     // Output known-1 are known to be set if set in either the LHS | RHS.
 289     KnownOne |= KnownOne2;
 290     break;
 291   case ISD::XOR:
 292     if (SimplifyDemandedBits(Op.getOperand(1), DemandedMask, KnownZero,
 293                              KnownOne, TLO, Depth+1))
 294       return true;
 295     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 296     if (SimplifyDemandedBits(Op.getOperand(0), DemandedMask, KnownZero2,
 297                              KnownOne2, TLO, Depth+1))
 298       return true;
 299     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
 300
 301     // If all of the demanded bits are known zero on one side, return the other.
 302     // These bits cannot contribute to the result of the 'xor'.
 303     if ((DemandedMask & KnownZero) == DemandedMask)
 304       return TLO.CombineTo(Op, Op.getOperand(0));
 305     if ((DemandedMask & KnownZero2) == DemandedMask)
 306       return TLO.CombineTo(Op, Op.getOperand(1));
 307
 308     // Output known-0 bits are known if clear or set in both the LHS & RHS.
 309     KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
 310     // Output known-1 are known to be set if set in only one of the LHS, RHS.
 311     KnownOneOut = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
 312
 313     // If all of the unknown bits are known to be zero on one side or the other
 314     // (but not both) turn this into an *inclusive* or.
 315     //    e.g. (A & C1)^(B & C2) -> (A & C1)|(B & C2) iff C1&C2 == 0
 316     if (uint64_t UnknownBits = DemandedMask & ~(KnownZeroOut|KnownOneOut))
 317       if ((UnknownBits & (KnownZero|KnownZero2)) == UnknownBits)
 318         return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::OR, Op.getValueType(),
 319                                                  Op.getOperand(0),
 320                                                  Op.getOperand(1)));
 321     // If all of the demanded bits on one side are known, and all of the set
 322     // bits on that side are also known to be set on the other side, turn this
 323     // into an AND, as we know the bits will be cleared.
 324     //    e.g. (X | C1) ^ C2 --> (X | C1) & ~C2 iff (C1&C2) == C2
 325     if ((DemandedMask & (KnownZero|KnownOne)) == DemandedMask) { // all known
 326       if ((KnownOne & KnownOne2) == KnownOne) {
 327         MVT::ValueType VT = Op.getValueType();
 328         SDOperand ANDC = TLO.DAG.getConstant(~KnownOne & DemandedMask, VT);
 329         return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::AND, VT, Op.getOperand(0),
 330                                                  ANDC));
 331       }
 332     }
 333
 334     // If the RHS is a constant, see if we can simplify it.
 335     // FIXME: for XOR, we prefer to force bits to 1 if they will make a -1.
 336     if (TLO.ShrinkDemandedConstant(Op, DemandedMask))
 337       return true;
 338
 339     KnownZero = KnownZeroOut;
 340     KnownOne  = KnownOneOut;
 341     break;
 342   case ISD::SETCC:
 343     // If we know the result of a setcc has the top bits zero, use this info.
 344     if (getSetCCResultContents() == TargetLowering::ZeroOrOneSetCCResult)
 345       KnownZero |= (MVT::getIntVTBitMask(Op.getValueType()) ^ 1ULL);
 346     break;
 347   case ISD::SELECT:
 348     if (SimplifyDemandedBits(Op.getOperand(2), DemandedMask, KnownZero,
 349                              KnownOne, TLO, Depth+1))
 350       return true;
 351     if (SimplifyDemandedBits(Op.getOperand(1), DemandedMask, KnownZero2,
 352                              KnownOne2, TLO, Depth+1))
 353       return true;
 354     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 355     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
 356
 357     // If the operands are constants, see if we can simplify them.
 358     if (TLO.ShrinkDemandedConstant(Op, DemandedMask))
 359       return true;
 360
 361     // Only known if known in both the LHS and RHS.
 362     KnownOne &= KnownOne2;
 363     KnownZero &= KnownZero2;
 364     break;
 365   case ISD::SELECT_CC:
 366     if (SimplifyDemandedBits(Op.getOperand(3), DemandedMask, KnownZero,
 367                              KnownOne, TLO, Depth+1))
 368       return true;
 369     if (SimplifyDemandedBits(Op.getOperand(2), DemandedMask, KnownZero2,
 370                              KnownOne2, TLO, Depth+1))
 371       return true;
 372     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 373     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
 374
 375     // If the operands are constants, see if we can simplify them.
 376     if (TLO.ShrinkDemandedConstant(Op, DemandedMask))
 377       return true;
 378
 379     // Only known if known in both the LHS and RHS.
 380     KnownOne &= KnownOne2;
 381     KnownZero &= KnownZero2;
 382     break;
 383   case ISD::SHL:
 384     if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
 385       if (SimplifyDemandedBits(Op.getOperand(0), DemandedMask >> SA->getValue(),
 386                                KnownZero, KnownOne, TLO, Depth+1))
 387         return true;
 388       KnownZero <<= SA->getValue();
 389       KnownOne  <<= SA->getValue();
 390       KnownZero |= (1ULL << SA->getValue())-1;  // low bits known zero.
 391     }
 392     break;
 393   case ISD::SRL:
 394     if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
 395       MVT::ValueType VT = Op.getValueType();
 396       unsigned ShAmt = SA->getValue();
 397
 398       // Compute the new bits that are at the top now.
 399       uint64_t HighBits = (1ULL << ShAmt)-1;
 400       HighBits <<= MVT::getSizeInBits(VT) - ShAmt;
 401       uint64_t TypeMask = MVT::getIntVTBitMask(VT);
 402
 403       if (SimplifyDemandedBits(Op.getOperand(0),
 404                                (DemandedMask << ShAmt) & TypeMask,
 405                                KnownZero, KnownOne, TLO, Depth+1))
 406         return true;
 407       assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 408       KnownZero &= TypeMask;
 409       KnownOne  &= TypeMask;
 410       KnownZero >>= ShAmt;
 411       KnownOne  >>= ShAmt;
 412       KnownZero |= HighBits;  // high bits known zero.
 413     }
 414     break;
 415   case ISD::SRA:
 416     if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
 417       MVT::ValueType VT = Op.getValueType();
 418       unsigned ShAmt = SA->getValue();
 419
 420       // Compute the new bits that are at the top now.
 421       uint64_t HighBits = (1ULL << ShAmt)-1;
 422       HighBits <<= MVT::getSizeInBits(VT) - ShAmt;
 423       uint64_t TypeMask = MVT::getIntVTBitMask(VT);
 424
 425       if (SimplifyDemandedBits(Op.getOperand(0),
 426                                (DemandedMask << ShAmt) & TypeMask,
 427                                KnownZero, KnownOne, TLO, Depth+1))
 428         return true;
 429       assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 430       KnownZero &= TypeMask;
 431       KnownOne  &= TypeMask;
 432       KnownZero >>= SA->getValue();
 433       KnownOne  >>= SA->getValue();
 434
 435       // Handle the sign bits.
 436       uint64_t SignBit = MVT::getIntVTSignBit(VT);
 437       SignBit >>= SA->getValue();  // Adjust to where it is now in the mask.
 438
 439       // If the input sign bit is known to be zero, or if none of the top bits
 440       // are demanded, turn this into an unsigned shift right.
 441       if ((KnownZero & SignBit) || (HighBits & ~DemandedMask) == HighBits) {
 442         return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::SRL, VT, Op.getOperand(0),
 443                                                  Op.getOperand(1)));
 444       } else if (KnownOne & SignBit) { // New bits are known one.
 445         KnownOne |= HighBits;
 446       }
 447     }
 448     break;
 449   case ISD::SIGN_EXTEND_INREG: {
 450     MVT::ValueType  VT = Op.getValueType();
 451     MVT::ValueType EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
 452
 453     // Sign extension.  Compute the demanded bits in the result that are not
 454     // present in the input.
 455     uint64_t NewBits = ~MVT::getIntVTBitMask(EVT) & DemandedMask;
 456
 457     // If none of the extended bits are demanded, eliminate the sextinreg.
 458     if (NewBits == 0)
 459       return TLO.CombineTo(Op, Op.getOperand(0));
 460
 461     uint64_t InSignBit = MVT::getIntVTSignBit(EVT);
 462     int64_t InputDemandedBits = DemandedMask & MVT::getIntVTBitMask(EVT);
 463
 464     // Since the sign extended bits are demanded, we know that the sign
 465     // bit is demanded.
 466     InputDemandedBits |= InSignBit;
 467
 468     if (SimplifyDemandedBits(Op.getOperand(0), InputDemandedBits,
 469                              KnownZero, KnownOne, TLO, Depth+1))
 470       return true;
 471     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 472
 473     // If the sign bit of the input is known set or clear, then we know the
 474     // top bits of the result.
 475
 476     // If the input sign bit is known zero, convert this into a zero extension.
 477     if (KnownZero & InSignBit)
 478       return TLO.CombineTo(Op,
 479                            TLO.DAG.getZeroExtendInReg(Op.getOperand(0), EVT));
 480
 481     if (KnownOne & InSignBit) {    // Input sign bit known set
 482       KnownOne |= NewBits;
 483       KnownZero &= ~NewBits;
 484     } else {                       // Input sign bit unknown
 485       KnownZero &= ~NewBits;
 486       KnownOne &= ~NewBits;
 487     }
 488     break;
 489   }
 490   case ISD::CTTZ:
 491   case ISD::CTLZ:
 492   case ISD::CTPOP: {
 493     MVT::ValueType VT = Op.getValueType();
 494     unsigned LowBits = Log2_32(MVT::getSizeInBits(VT))+1;
 495     KnownZero = ~((1ULL << LowBits)-1) & MVT::getIntVTBitMask(VT);
 496     KnownOne  = 0;
 497     break;
 498   }
 499   case ISD::ZEXTLOAD: {
 500     MVT::ValueType VT = cast<VTSDNode>(Op.getOperand(3))->getVT();
 501     KnownZero |= ~MVT::getIntVTBitMask(VT) & DemandedMask;
 502     break;
 503   }
 504   case ISD::ZERO_EXTEND: {
 505     uint64_t InMask = MVT::getIntVTBitMask(Op.getOperand(0).getValueType());
 506
 507     // If none of the top bits are demanded, convert this into an any_extend.
 508     uint64_t NewBits = (~InMask) & DemandedMask;
 509     if (NewBits == 0)
 510       return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::ANY_EXTEND,
 511                                                Op.getValueType(),
 512                                                Op.getOperand(0)));
 513
 514     if (SimplifyDemandedBits(Op.getOperand(0), DemandedMask & InMask,
 515                              KnownZero, KnownOne, TLO, Depth+1))
 516       return true;
 517     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 518     KnownZero |= NewBits;
 519     break;
 520   }
 521   case ISD::SIGN_EXTEND: {
 522     MVT::ValueType InVT = Op.getOperand(0).getValueType();
 523     uint64_t InMask    = MVT::getIntVTBitMask(InVT);
 524     uint64_t InSignBit = MVT::getIntVTSignBit(InVT);
 525     uint64_t NewBits   = (~InMask) & DemandedMask;
 526
 527     // If none of the top bits are demanded, convert this into an any_extend.
 528     if (NewBits == 0)
 529       return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::ANY_EXTEND,Op.getValueType(),
 530                                            Op.getOperand(0)));
 531
 532     // Since some of the sign extended bits are demanded, we know that the sign
 533     // bit is demanded.
 534     uint64_t InDemandedBits = DemandedMask & InMask;
 535     InDemandedBits |= InSignBit;
 536
 537     if (SimplifyDemandedBits(Op.getOperand(0), InDemandedBits, KnownZero,
 538                              KnownOne, TLO, Depth+1))
 539       return true;
 540
 541     // If the sign bit is known zero, convert this to a zero extend.
 542     if (KnownZero & InSignBit)
 543       return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::ZERO_EXTEND,
 544                                                Op.getValueType(),
 545                                                Op.getOperand(0)));
 546
 547     // If the sign bit is known one, the top bits match.
 548     if (KnownOne & InSignBit) {
 549       KnownOne  |= NewBits;
 550       KnownZero &= ~NewBits;
 551     } else {   // Otherwise, top bits aren't known.
 552       KnownOne  &= ~NewBits;
 553       KnownZero &= ~NewBits;
 554     }
 555     break;
 556   }
 557   case ISD::ANY_EXTEND: {
 558     uint64_t InMask = MVT::getIntVTBitMask(Op.getOperand(0).getValueType());
 559     if (SimplifyDemandedBits(Op.getOperand(0), DemandedMask & InMask,
 560                              KnownZero, KnownOne, TLO, Depth+1))
 561       return true;
 562     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 563     break;
 564   }
 565   case ISD::AssertZext: {
 566     MVT::ValueType VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
 567     uint64_t InMask = MVT::getIntVTBitMask(VT);
 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 |= ~InMask & DemandedMask;
 573     break;
 574   }
 575   case ISD::ADD:
 576   case ISD::SUB:
 577     // Just use ComputeMaskedBits to compute output bits, there are no
 578     // simplifications that can be done here, and sub always demands all input
 579     // bits.
 580     ComputeMaskedBits(Op, DemandedMask, KnownZero, KnownOne, Depth);
 581     break;
 582   }
 583
 584   // If we know the value of all of the demanded bits, return this as a
 585   // constant.
 586   if ((DemandedMask & (KnownZero|KnownOne)) == DemandedMask)
 587     return TLO.CombineTo(Op, TLO.DAG.getConstant(KnownOne, Op.getValueType()));
 588
 589   return false;
 590 }
 591
 592 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero.  We use
 593 /// this predicate to simplify operations downstream.  Mask is known to be zero
 594 /// for bits that V cannot have.
 595 bool TargetLowering::MaskedValueIsZero(SDOperand Op, uint64_t Mask,
 596                                        unsigned Depth) const {
 597   uint64_t KnownZero, KnownOne;
 598   ComputeMaskedBits(Op, Mask, KnownZero, KnownOne, Depth);
 599   assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 600   return (KnownZero & Mask) == Mask;
 601 }
 602
 603 /// ComputeMaskedBits - Determine which of the bits specified in Mask are
 604 /// known to be either zero or one and return them in the KnownZero/KnownOne
 605 /// bitsets.  This code only analyzes bits in Mask, in order to short-circuit
 606 /// processing.
 607 void TargetLowering::ComputeMaskedBits(SDOperand Op, uint64_t Mask,
 608                                        uint64_t &KnownZero, uint64_t &KnownOne,
 609                                        unsigned Depth) const {
 610   KnownZero = KnownOne = 0;   // Don't know anything.
 611   if (Depth == 6 || Mask == 0)
 612     return;  // Limit search depth.
 613
 614   uint64_t KnownZero2, KnownOne2;
 615
 616   switch (Op.getOpcode()) {
 617   case ISD::Constant:
 618     // We know all of the bits for a constant!
 619     KnownOne = cast<ConstantSDNode>(Op)->getValue() & Mask;
 620     KnownZero = ~KnownOne & Mask;
 621     return;
 622   case ISD::AND:
 623     // If either the LHS or the RHS are Zero, the result is zero.
 624     ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1);
 625     Mask &= ~KnownZero;
 626     ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero2, KnownOne2, Depth+1);
 627     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 628     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
 629
 630     // Output known-1 bits are only known if set in both the LHS & RHS.
 631     KnownOne &= KnownOne2;
 632     // Output known-0 are known to be clear if zero in either the LHS | RHS.
 633     KnownZero |= KnownZero2;
 634     return;
 635   case ISD::OR:
 636     ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1);
 637     Mask &= ~KnownOne;
 638     ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero2, KnownOne2, Depth+1);
 639     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 640     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
 641
 642     // Output known-0 bits are only known if clear in both the LHS & RHS.
 643     KnownZero &= KnownZero2;
 644     // Output known-1 are known to be set if set in either the LHS | RHS.
 645     KnownOne |= KnownOne2;
 646     return;
 647   case ISD::XOR: {
 648     ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1);
 649     ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero2, KnownOne2, Depth+1);
 650     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 651     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
 652
 653     // Output known-0 bits are known if clear or set in both the LHS & RHS.
 654     uint64_t KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
 655     // Output known-1 are known to be set if set in only one of the LHS, RHS.
 656     KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
 657     KnownZero = KnownZeroOut;
 658     return;
 659   }
 660   case ISD::SELECT:
 661     ComputeMaskedBits(Op.getOperand(2), Mask, KnownZero, KnownOne, Depth+1);
 662     ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero2, KnownOne2, Depth+1);
 663     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 664     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
 665
 666     // Only known if known in both the LHS and RHS.
 667     KnownOne &= KnownOne2;
 668     KnownZero &= KnownZero2;
 669     return;
 670   case ISD::SELECT_CC:
 671     ComputeMaskedBits(Op.getOperand(3), Mask, KnownZero, KnownOne, Depth+1);
 672     ComputeMaskedBits(Op.getOperand(2), Mask, KnownZero2, KnownOne2, Depth+1);
 673     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 674     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
 675
 676     // Only known if known in both the LHS and RHS.
 677     KnownOne &= KnownOne2;
 678     KnownZero &= KnownZero2;
 679     return;
 680   case ISD::SETCC:
 681     // If we know the result of a setcc has the top bits zero, use this info.
 682     if (getSetCCResultContents() == TargetLowering::ZeroOrOneSetCCResult)
 683       KnownZero |= (MVT::getIntVTBitMask(Op.getValueType()) ^ 1ULL);
 684     return;
 685   case ISD::SHL:
 686     // (shl X, C1) & C2 == 0   iff   (X & C2 >>u C1) == 0
 687     if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
 688       Mask >>= SA->getValue();
 689       ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero, KnownOne, Depth+1);
 690       assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 691       KnownZero <<= SA->getValue();
 692       KnownOne  <<= SA->getValue();
 693       KnownZero |= (1ULL << SA->getValue())-1;  // low bits known zero.
 694     }
 695     return;
 696   case ISD::SRL:
 697     // (ushr X, C1) & C2 == 0   iff  (-1 >> C1) & C2 == 0
 698     if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
 699       uint64_t HighBits = (1ULL << SA->getValue())-1;
 700       HighBits <<= MVT::getSizeInBits(Op.getValueType())-SA->getValue();
 701       Mask <<= SA->getValue();
 702       ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero, KnownOne, Depth+1);
 703       assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 704       KnownZero >>= SA->getValue();
 705       KnownOne  >>= SA->getValue();
 706       KnownZero |= HighBits;  // high bits known zero.
 707     }
 708     return;
 709   case ISD::SRA:
 710     if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
 711       uint64_t HighBits = (1ULL << SA->getValue())-1;
 712       HighBits <<= MVT::getSizeInBits(Op.getValueType())-SA->getValue();
 713       Mask <<= SA->getValue();
 714       ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero, KnownOne, Depth+1);
 715       assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
 716       KnownZero >>= SA->getValue();
 717       KnownOne  >>= SA->getValue();
 718
 719       // Handle the sign bits.
 720       uint64_t SignBit = 1ULL << (MVT::getSizeInBits(Op.getValueType())-1);
 721       SignBit >>= SA->getValue();  // Adjust to where it is now in the mask.
 722
 723       if (KnownZero & SignBit) {       // New bits are known zero.
 724         KnownZero |= HighBits;
 725       } else if (KnownOne & SignBit) { // New bits are known one.
 726         KnownOne |= HighBits;
 727       }
 728     }
 729     return;
 730   case ISD::SIGN_EXTEND_INREG: {
 731     MVT::ValueType  VT = Op.getValueType();
 732     MVT::ValueType EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
 733
 734     // Sign extension.  Compute the demanded bits in the result that are not
 735     // present in the input.
 736     uint64_t NewBits = ~MVT::getIntVTBitMask(EVT) & Mask;
 737
 738     uint64_t InSignBit = MVT::getIntVTSignBit(EVT);
 739     int64_t InputDemandedBits = Mask & MVT::getIntVTBitMask(EVT);
 740
 741     // If the sign extended bits are demanded, we know that the sign
 742     // bit is demanded.
 743     if (NewBits)
 744       InputDemandedBits |= InSignBit;
 745
 746     ComputeMaskedBits(Op.getOperand(0), InputDemandedBits,
 747                       KnownZero, KnownOne, Depth+1);
 748     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 749
 750     // If the sign bit of the input is known set or clear, then we know the
 751     // top bits of the result.
 752     if (KnownZero & InSignBit) {          // Input sign bit known clear
 753       KnownZero |= NewBits;
 754       KnownOne  &= ~NewBits;
 755     } else if (KnownOne & InSignBit) {    // Input sign bit known set
 756       KnownOne  |= NewBits;
 757       KnownZero &= ~NewBits;
 758     } else {                              // Input sign bit unknown
 759       KnownZero &= ~NewBits;
 760       KnownOne  &= ~NewBits;
 761     }
 762     return;
 763   }
 764   case ISD::CTTZ:
 765   case ISD::CTLZ:
 766   case ISD::CTPOP: {
 767     MVT::ValueType VT = Op.getValueType();
 768     unsigned LowBits = Log2_32(MVT::getSizeInBits(VT))+1;
 769     KnownZero = ~((1ULL << LowBits)-1) & MVT::getIntVTBitMask(VT);
 770     KnownOne  = 0;
 771     return;
 772   }
 773   case ISD::ZEXTLOAD: {
 774     MVT::ValueType VT = cast<VTSDNode>(Op.getOperand(3))->getVT();
 775     KnownZero |= ~MVT::getIntVTBitMask(VT) & Mask;
 776     return;
 777   }
 778   case ISD::ZERO_EXTEND: {
 779     uint64_t InMask  = MVT::getIntVTBitMask(Op.getOperand(0).getValueType());
 780     uint64_t NewBits = (~InMask) & Mask;
 781     ComputeMaskedBits(Op.getOperand(0), Mask & InMask, KnownZero,
 782                       KnownOne, Depth+1);
 783     KnownZero |= NewBits & Mask;
 784     KnownOne  &= ~NewBits;
 785     return;
 786   }
 787   case ISD::SIGN_EXTEND: {
 788     MVT::ValueType InVT = Op.getOperand(0).getValueType();
 789     unsigned InBits    = MVT::getSizeInBits(InVT);
 790     uint64_t InMask    = MVT::getIntVTBitMask(InVT);
 791     uint64_t InSignBit = 1ULL << (InBits-1);
 792     uint64_t NewBits   = (~InMask) & Mask;
 793     uint64_t InDemandedBits = Mask & InMask;
 794
 795     // If any of the sign extended bits are demanded, we know that the sign
 796     // bit is demanded.
 797     if (NewBits & Mask)
 798       InDemandedBits |= InSignBit;
 799
 800     ComputeMaskedBits(Op.getOperand(0), InDemandedBits, KnownZero,
 801                       KnownOne, Depth+1);
 802     // If the sign bit is known zero or one, the  top bits match.
 803     if (KnownZero & InSignBit) {
 804       KnownZero |= NewBits;
 805       KnownOne  &= ~NewBits;
 806     } else if (KnownOne & InSignBit) {
 807       KnownOne  |= NewBits;
 808       KnownZero &= ~NewBits;
 809     } else {   // Otherwise, top bits aren't known.
 810       KnownOne  &= ~NewBits;
 811       KnownZero &= ~NewBits;
 812     }
 813     return;
 814   }
 815   case ISD::ANY_EXTEND: {
 816     MVT::ValueType VT = Op.getOperand(0).getValueType();
 817     ComputeMaskedBits(Op.getOperand(0), Mask & MVT::getIntVTBitMask(VT),
 818                       KnownZero, KnownOne, Depth+1);
 819     return;
 820   }
 821   case ISD::AssertZext: {
 822     MVT::ValueType VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
 823     uint64_t InMask = MVT::getIntVTBitMask(VT);
 824     ComputeMaskedBits(Op.getOperand(0), Mask & InMask, KnownZero,
 825                       KnownOne, Depth+1);
 826     KnownZero |= (~InMask) & Mask;
 827     return;
 828   }
 829   case ISD::ADD: {
 830     // If either the LHS or the RHS are Zero, the result is zero.
 831     ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1);
 832     ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero2, KnownOne2, Depth+1);
 833     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 834     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
 835
 836     // Output known-0 bits are known if clear or set in both the low clear bits
 837     // common to both LHS & RHS.  For example, 8+(X<<3) is known to have the
 838     // low 3 bits clear.
 839     uint64_t KnownZeroOut = std::min(CountTrailingZeros_64(~KnownZero),
 840                                      CountTrailingZeros_64(~KnownZero2));
 841
 842     KnownZero = (1ULL << KnownZeroOut) - 1;
 843     KnownOne = 0;
 844     return;
 845   }
 846   case ISD::SUB: {
 847     ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0));
 848     if (!CLHS) return;
 849
 850     // We know that the top bits of C-X are clear if X contains less bits
 851     // than C (i.e. no wrap-around can happen).  For example, 20-X is
 852     // positive if we can prove that X is >= 0 and < 16.
 853     MVT::ValueType VT = CLHS->getValueType(0);
 854     if ((CLHS->getValue() & MVT::getIntVTSignBit(VT)) == 0) {  // sign bit clear
 855       unsigned NLZ = CountLeadingZeros_64(CLHS->getValue()+1);
 856       uint64_t MaskV = (1ULL << (63-NLZ))-1; // NLZ can't be 64 with no sign bit
 857       MaskV = ~MaskV & MVT::getIntVTBitMask(VT);
 858       ComputeMaskedBits(Op.getOperand(1), MaskV, KnownZero, KnownOne, Depth+1);
 859
 860       // If all of the MaskV bits are known to be zero, then we know the output
 861       // top bits are zero, because we now know that the output is from [0-C].
 862       if ((KnownZero & MaskV) == MaskV) {
 863         unsigned NLZ2 = CountLeadingZeros_64(CLHS->getValue());
 864         KnownZero = ~((1ULL << (64-NLZ2))-1) & Mask;  // Top bits known zero.
 865         KnownOne = 0;   // No one bits known.
 866       } else {
 867         KnownOne = KnownOne = 0;  // Otherwise, nothing known.
 868       }
 869     }
 870     return;
 871   }
 872   default:
 873     // Allow the target to implement this method for its nodes.
 874     if (Op.getOpcode() >= ISD::BUILTIN_OP_END)
 875       computeMaskedBitsForTargetNode(Op, Mask, KnownZero, KnownOne);
 876     return;
 877   }
 878 }
 879
 880 /// computeMaskedBitsForTargetNode - Determine which of the bits specified
 881 /// in Mask are known to be either zero or one and return them in the
 882 /// KnownZero/KnownOne bitsets.
 883 void TargetLowering::computeMaskedBitsForTargetNode(const SDOperand Op,
 884                                                     uint64_t Mask,
 885                                                     uint64_t &KnownZero,
 886                                                     uint64_t &KnownOne,
 887                                                     unsigned Depth) const {
 888   assert(Op.getOpcode() >= ISD::BUILTIN_OP_END &&
 889          "Should use MaskedValueIsZero if you don't know whether Op"
 890          " is a target node!");
 891   KnownZero = 0;
 892   KnownOne = 0;
 893 }
 894
 895 SDOperand TargetLowering::
 896 PerformDAGCombine(SDNode *N, DAGCombinerInfo &DCI) const {
 897   // Default implementation: no optimization.
 898   return SDOperand();
 899 }
 900
 901 //===----------------------------------------------------------------------===//
 902 //  Inline Assembler Implementation Methods
 903 //===----------------------------------------------------------------------===//
 904
 905 TargetLowering::ConstraintType
 906 TargetLowering::getConstraintType(char ConstraintLetter) const {
 907   // FIXME: lots more standard ones to handle.
 908   switch (ConstraintLetter) {
 909   default: return C_Unknown;
 910   case 'r': return C_RegisterClass;
 911   case 'm':    // memory
 912   case 'o':    // offsetable
 913   case 'V':    // not offsetable
 914     return C_Memory;
 915   case 'i':    // Simple Integer or Relocatable Constant
 916   case 'n':    // Simple Integer
 917   case 's':    // Relocatable Constant
 918   case 'I':    // Target registers.
 919   case 'J':
 920   case 'K':
 921   case 'L':
 922   case 'M':
 923   case 'N':
 924   case 'O':
 925   case 'P':
 926     return C_Other;
 927   }
 928 }
 929
 930 bool TargetLowering::isOperandValidForConstraint(SDOperand Op,
 931                                                  char ConstraintLetter) {
 932   switch (ConstraintLetter) {
 933   default: return false;
 934   case 'i':    // Simple Integer or Relocatable Constant
 935   case 'n':    // Simple Integer
 936   case 's':    // Relocatable Constant
 937     return true;   // FIXME: not right.
 938   }
 939 }
 940
 941
 942 std::vector<unsigned> TargetLowering::
 943 getRegClassForInlineAsmConstraint(const std::string &Constraint,
 944                                   MVT::ValueType VT) const {
 945   return std::vector<unsigned>();
 946 }
 947
 948
 949 std::pair<unsigned, const TargetRegisterClass*> TargetLowering::
 950 getRegForInlineAsmConstraint(const std::string &Constraint,
 951                              MVT::ValueType VT) const {
 952   if (Constraint[0] != '{')
 953     return std::pair<unsigned, const TargetRegisterClass*>(0, 0);
 954   assert(*(Constraint.end()-1) == '}' && "Not a brace enclosed constraint?");
 955
 956   // Remove the braces from around the name.
 957   std::string RegName(Constraint.begin()+1, Constraint.end()-1);
 958
 959   // Figure out which register class contains this reg.
 960   const MRegisterInfo *RI = TM.getRegisterInfo();
 961   for (MRegisterInfo::regclass_iterator RCI = RI->regclass_begin(),
 962        E = RI->regclass_end(); RCI != E; ++RCI) {
 963     const TargetRegisterClass *RC = *RCI;
 964
 965     // If none of the the value types for this register class are valid, we
 966     // can't use it.  For example, 64-bit reg classes on 32-bit targets.
 967     bool isLegal = false;
 968     for (TargetRegisterClass::vt_iterator I = RC->vt_begin(), E = RC->vt_end();
 969          I != E; ++I) {
 970       if (isTypeLegal(*I)) {
 971         isLegal = true;
 972         break;
 973       }
 974     }
 975
 976     if (!isLegal) continue;
 977
 978     for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end();
 979          I != E; ++I) {
 980       if (StringsEqualNoCase(RegName, RI->get(*I).Name))
 981         return std::make_pair(*I, RC);
 982     }
 983   }
 984
 985   return std::pair<unsigned, const TargetRegisterClass*>(0, 0);
 986 }
 987
 988 //===----------------------------------------------------------------------===//
 989 //  Loop Strength Reduction hooks
 990 //===----------------------------------------------------------------------===//
 991
 992 /// isLegalAddressImmediate - Return true if the integer value or
 993 /// GlobalValue can be used as the offset of the target addressing mode.
 994 bool TargetLowering::isLegalAddressImmediate(int64_t V) const {
 995   return false;
 996 }
 997 bool TargetLowering::isLegalAddressImmediate(GlobalValue *GV) const {
 998   return false;
 999 }