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/ADT/STLExtras.h"
  22 #include "llvm/Support/MathExtras.h"
  23 using namespace llvm;
  24
  25 /// InitLibcallNames - Set default libcall names.
  26 ///
  27 static void InitLibcallNames(const char **Names) {
  28   Names[RTLIB::SHL_I32] = "__ashlsi3";
  29   Names[RTLIB::SHL_I64] = "__ashldi3";
  30   Names[RTLIB::SRL_I32] = "__lshrsi3";
  31   Names[RTLIB::SRL_I64] = "__lshrdi3";
  32   Names[RTLIB::SRA_I32] = "__ashrsi3";
  33   Names[RTLIB::SRA_I64] = "__ashrdi3";
  34   Names[RTLIB::MUL_I32] = "__mulsi3";
  35   Names[RTLIB::MUL_I64] = "__muldi3";
  36   Names[RTLIB::SDIV_I32] = "__divsi3";
  37   Names[RTLIB::SDIV_I64] = "__divdi3";
  38   Names[RTLIB::UDIV_I32] = "__udivsi3";
  39   Names[RTLIB::UDIV_I64] = "__udivdi3";
  40   Names[RTLIB::SREM_I32] = "__modsi3";
  41   Names[RTLIB::SREM_I64] = "__moddi3";
  42   Names[RTLIB::UREM_I32] = "__umodsi3";
  43   Names[RTLIB::UREM_I64] = "__umoddi3";
  44   Names[RTLIB::NEG_I32] = "__negsi2";
  45   Names[RTLIB::NEG_I64] = "__negdi2";
  46   Names[RTLIB::ADD_F32] = "__addsf3";
  47   Names[RTLIB::ADD_F64] = "__adddf3";
  48   Names[RTLIB::SUB_F32] = "__subsf3";
  49   Names[RTLIB::SUB_F64] = "__subdf3";
  50   Names[RTLIB::MUL_F32] = "__mulsf3";
  51   Names[RTLIB::MUL_F64] = "__muldf3";
  52   Names[RTLIB::DIV_F32] = "__divsf3";
  53   Names[RTLIB::DIV_F64] = "__divdf3";
  54   Names[RTLIB::REM_F32] = "fmodf";
  55   Names[RTLIB::REM_F64] = "fmod";
  56   Names[RTLIB::NEG_F32] = "__negsf2";
  57   Names[RTLIB::NEG_F64] = "__negdf2";
  58   Names[RTLIB::POWI_F32] = "__powisf2";
  59   Names[RTLIB::POWI_F64] = "__powidf2";
  60   Names[RTLIB::SQRT_F32] = "sqrtf";
  61   Names[RTLIB::SQRT_F64] = "sqrt";
  62   Names[RTLIB::SIN_F32] = "sinf";
  63   Names[RTLIB::SIN_F64] = "sin";
  64   Names[RTLIB::COS_F32] = "cosf";
  65   Names[RTLIB::COS_F64] = "cos";
  66   Names[RTLIB::FPEXT_F32_F64] = "__extendsfdf2";
  67   Names[RTLIB::FPROUND_F64_F32] = "__truncdfsf2";
  68   Names[RTLIB::FPTOSINT_F32_I32] = "__fixsfsi";
  69   Names[RTLIB::FPTOSINT_F32_I64] = "__fixsfdi";
  70   Names[RTLIB::FPTOSINT_F64_I32] = "__fixdfsi";
  71   Names[RTLIB::FPTOSINT_F64_I64] = "__fixdfdi";
  72   Names[RTLIB::FPTOUINT_F32_I32] = "__fixunssfsi";
  73   Names[RTLIB::FPTOUINT_F32_I64] = "__fixunssfdi";
  74   Names[RTLIB::FPTOUINT_F64_I32] = "__fixunsdfsi";
  75   Names[RTLIB::FPTOUINT_F64_I64] = "__fixunsdfdi";
  76   Names[RTLIB::SINTTOFP_I32_F32] = "__floatsisf";
  77   Names[RTLIB::SINTTOFP_I32_F64] = "__floatsidf";
  78   Names[RTLIB::SINTTOFP_I64_F32] = "__floatdisf";
  79   Names[RTLIB::SINTTOFP_I64_F64] = "__floatdidf";
  80   Names[RTLIB::UINTTOFP_I32_F32] = "__floatunsisf";
  81   Names[RTLIB::UINTTOFP_I32_F64] = "__floatunsidf";
  82   Names[RTLIB::UINTTOFP_I64_F32] = "__floatundisf";
  83   Names[RTLIB::UINTTOFP_I64_F64] = "__floatundidf";
  84   Names[RTLIB::OEQ_F32] = "__eqsf2";
  85   Names[RTLIB::OEQ_F64] = "__eqdf2";
  86   Names[RTLIB::UNE_F32] = "__nesf2";
  87   Names[RTLIB::UNE_F64] = "__nedf2";
  88   Names[RTLIB::OGE_F32] = "__gesf2";
  89   Names[RTLIB::OGE_F64] = "__gedf2";
  90   Names[RTLIB::OLT_F32] = "__ltsf2";
  91   Names[RTLIB::OLT_F64] = "__ltdf2";
  92   Names[RTLIB::OLE_F32] = "__lesf2";
  93   Names[RTLIB::OLE_F64] = "__ledf2";
  94   Names[RTLIB::OGT_F32] = "__gtsf2";
  95   Names[RTLIB::OGT_F64] = "__gtdf2";
  96   Names[RTLIB::UO_F32] = "__unordsf2";
  97   Names[RTLIB::UO_F64] = "__unorddf2";
  98   Names[RTLIB::O_F32] = "__unordsf2";
  99   Names[RTLIB::O_F64] = "__unorddf2";
 100 }
 101
 102 /// InitCmpLibcallCCs - Set default comparison libcall CC.
 103 ///
 104 static void InitCmpLibcallCCs(ISD::CondCode *CCs) {
 105   memset(CCs, ISD::SETCC_INVALID, sizeof(ISD::CondCode)*RTLIB::UNKNOWN_LIBCALL);
 106   CCs[RTLIB::OEQ_F32] = ISD::SETEQ;
 107   CCs[RTLIB::OEQ_F64] = ISD::SETEQ;
 108   CCs[RTLIB::UNE_F32] = ISD::SETNE;
 109   CCs[RTLIB::UNE_F64] = ISD::SETNE;
 110   CCs[RTLIB::OGE_F32] = ISD::SETGE;
 111   CCs[RTLIB::OGE_F64] = ISD::SETGE;
 112   CCs[RTLIB::OLT_F32] = ISD::SETLT;
 113   CCs[RTLIB::OLT_F64] = ISD::SETLT;
 114   CCs[RTLIB::OLE_F32] = ISD::SETLE;
 115   CCs[RTLIB::OLE_F64] = ISD::SETLE;
 116   CCs[RTLIB::OGT_F32] = ISD::SETGT;
 117   CCs[RTLIB::OGT_F64] = ISD::SETGT;
 118   CCs[RTLIB::UO_F32] = ISD::SETNE;
 119   CCs[RTLIB::UO_F64] = ISD::SETNE;
 120   CCs[RTLIB::O_F32] = ISD::SETEQ;
 121   CCs[RTLIB::O_F64] = ISD::SETEQ;
 122 }
 123
 124 TargetLowering::TargetLowering(TargetMachine &tm)
 125   : TM(tm), TD(TM.getTargetData()) {
 126   assert(ISD::BUILTIN_OP_END <= 156 &&
 127          "Fixed size array in TargetLowering is not large enough!");
 128   // All operations default to being supported.
 129   memset(OpActions, 0, sizeof(OpActions));
 130   memset(LoadXActions, 0, sizeof(LoadXActions));
 131   memset(&StoreXActions, 0, sizeof(StoreXActions));
 132   memset(&IndexedModeActions, 0, sizeof(IndexedModeActions));
 133   memset(&ConvertActions, 0, sizeof(ConvertActions));
 134
 135   // Set all indexed load / store to expand.
 136   for (unsigned VT = 0; VT != (unsigned)MVT::LAST_VALUETYPE; ++VT) {
 137     for (unsigned IM = (unsigned)ISD::PRE_INC;
 138          IM != (unsigned)ISD::LAST_INDEXED_MODE; ++IM) {
 139       setIndexedLoadAction(IM, (MVT::ValueType)VT, Expand);
 140       setIndexedStoreAction(IM, (MVT::ValueType)VT, Expand);
 141     }
 142   }
 143
 144   IsLittleEndian = TD->isLittleEndian();
 145   UsesGlobalOffsetTable = false;
 146   ShiftAmountTy = SetCCResultTy = PointerTy = getValueType(TD->getIntPtrType());
 147   ShiftAmtHandling = Undefined;
 148   memset(RegClassForVT, 0,MVT::LAST_VALUETYPE*sizeof(TargetRegisterClass*));
 149   memset(TargetDAGCombineArray, 0, array_lengthof(TargetDAGCombineArray));
 150   maxStoresPerMemset = maxStoresPerMemcpy = maxStoresPerMemmove = 8;
 151   allowUnalignedMemoryAccesses = false;
 152   UseUnderscoreSetJmp = false;
 153   UseUnderscoreLongJmp = false;
 154   SelectIsExpensive = false;
 155   IntDivIsCheap = false;
 156   Pow2DivIsCheap = false;
 157   StackPointerRegisterToSaveRestore = 0;
 158   ExceptionPointerRegister = 0;
 159   ExceptionSelectorRegister = 0;
 160   SchedPreferenceInfo = SchedulingForLatency;
 161   JumpBufSize = 0;
 162   JumpBufAlignment = 0;
 163   IfCvtBlockSizeLimit = 2;
 164
 165   InitLibcallNames(LibcallRoutineNames);
 166   InitCmpLibcallCCs(CmpLibcallCCs);
 167 }
 168
 169 TargetLowering::~TargetLowering() {}
 170
 171 /// computeRegisterProperties - Once all of the register classes are added,
 172 /// this allows us to compute derived properties we expose.
 173 void TargetLowering::computeRegisterProperties() {
 174   assert(MVT::LAST_VALUETYPE <= 32 &&
 175          "Too many value types for ValueTypeActions to hold!");
 176
 177   // Everything defaults to needing one register.
 178   for (unsigned i = 0; i != MVT::LAST_VALUETYPE; ++i) {
 179     NumRegistersForVT[i] = 1;
 180     RegisterTypeForVT[i] = TransformToType[i] = i;
 181   }
 182   // ...except isVoid, which doesn't need any registers.
 183   NumRegistersForVT[MVT::isVoid] = 0;
 184
 185   // Find the largest integer register class.
 186   unsigned LargestIntReg = MVT::i128;
 187   for (; RegClassForVT[LargestIntReg] == 0; --LargestIntReg)
 188     assert(LargestIntReg != MVT::i1 && "No integer registers defined!");
 189
 190   // Every integer value type larger than this largest register takes twice as
 191   // many registers to represent as the previous ValueType.
 192   for (MVT::ValueType ExpandedReg = LargestIntReg + 1;
 193        MVT::isInteger(ExpandedReg); ++ExpandedReg) {
 194     NumRegistersForVT[ExpandedReg] = 2*NumRegistersForVT[ExpandedReg-1];
 195     RegisterTypeForVT[ExpandedReg] = LargestIntReg;
 196     TransformToType[ExpandedReg] = ExpandedReg - 1;
 197     ValueTypeActions.setTypeAction(ExpandedReg, Expand);
 198   }
 199
 200   // Inspect all of the ValueType's smaller than the largest integer
 201   // register to see which ones need promotion.
 202   MVT::ValueType LegalIntReg = LargestIntReg;
 203   for (MVT::ValueType IntReg = LargestIntReg - 1;
 204        IntReg >= MVT::i1; --IntReg) {
 205     if (isTypeLegal(IntReg)) {
 206       LegalIntReg = IntReg;
 207     } else {
 208       RegisterTypeForVT[IntReg] = TransformToType[IntReg] = LegalIntReg;
 209       ValueTypeActions.setTypeAction(IntReg, Promote);
 210     }
 211   }
 212
 213   // Decide how to handle f64. If the target does not have native f64 support,
 214   // expand it to i64 and we will be generating soft float library calls.
 215   if (!isTypeLegal(MVT::f64)) {
 216     NumRegistersForVT[MVT::f64] = NumRegistersForVT[MVT::i64];
 217     RegisterTypeForVT[MVT::f64] = RegisterTypeForVT[MVT::i64];
 218     TransformToType[MVT::f64] = MVT::i64;
 219     ValueTypeActions.setTypeAction(MVT::f64, Expand);
 220   }
 221
 222   // Decide how to handle f32. If the target does not have native support for
 223   // f32, promote it to f64 if it is legal. Otherwise, expand it to i32.
 224   if (!isTypeLegal(MVT::f32)) {
 225     if (isTypeLegal(MVT::f64)) {
 226       NumRegistersForVT[MVT::f32] = NumRegistersForVT[MVT::f64];
 227       RegisterTypeForVT[MVT::f32] = RegisterTypeForVT[MVT::f64];
 228       TransformToType[MVT::f32] = MVT::f64;
 229       ValueTypeActions.setTypeAction(MVT::f32, Promote);
 230     } else {
 231       NumRegistersForVT[MVT::f32] = NumRegistersForVT[MVT::i32];
 232       RegisterTypeForVT[MVT::f32] = RegisterTypeForVT[MVT::i32];
 233       TransformToType[MVT::f32] = MVT::i32;
 234       ValueTypeActions.setTypeAction(MVT::f32, Expand);
 235     }
 236   }
 237
 238   // Loop over all of the vector value types to see which need transformations.
 239   for (MVT::ValueType i = MVT::FIRST_VECTOR_VALUETYPE;
 240        i <= MVT::LAST_VECTOR_VALUETYPE; ++i) {
 241     if (!isTypeLegal(i)) {
 242       MVT::ValueType IntermediateVT, RegisterVT;
 243       unsigned NumIntermediates;
 244       NumRegistersForVT[i] =
 245         getVectorTypeBreakdown(i,
 246                                IntermediateVT, NumIntermediates,
 247                                RegisterVT);
 248       RegisterTypeForVT[i] = RegisterVT;
 249       TransformToType[i] = MVT::Other; // this isn't actually used
 250       ValueTypeActions.setTypeAction(i, Expand);
 251     }
 252   }
 253 }
 254
 255 const char *TargetLowering::getTargetNodeName(unsigned Opcode) const {
 256   return NULL;
 257 }
 258
 259 /// getVectorTypeBreakdown - Vector types are broken down into some number of
 260 /// legal first class types.  For example, MVT::v8f32 maps to 2 MVT::v4f32
 261 /// with Altivec or SSE1, or 8 promoted MVT::f64 values with the X86 FP stack.
 262 /// Similarly, MVT::v2i64 turns into 4 MVT::i32 values with both PPC and X86.
 263 ///
 264 /// This method returns the number of registers needed, and the VT for each
 265 /// register.  It also returns the VT and quantity of the intermediate values
 266 /// before they are promoted/expanded.
 267 ///
 268 unsigned TargetLowering::getVectorTypeBreakdown(MVT::ValueType VT,
 269                                                 MVT::ValueType &IntermediateVT,
 270                                                 unsigned &NumIntermediates,
 271                                       MVT::ValueType &RegisterVT) const {
 272   // Figure out the right, legal destination reg to copy into.
 273   unsigned NumElts = MVT::getVectorNumElements(VT);
 274   MVT::ValueType EltTy = MVT::getVectorElementType(VT);
 275
 276   unsigned NumVectorRegs = 1;
 277
 278   // Divide the input until we get to a supported size.  This will always
 279   // end with a scalar if the target doesn't support vectors.
 280   while (NumElts > 1 &&
 281          !isTypeLegal(MVT::getVectorType(EltTy, NumElts))) {
 282     NumElts >>= 1;
 283     NumVectorRegs <<= 1;
 284   }
 285
 286   NumIntermediates = NumVectorRegs;
 287
 288   MVT::ValueType NewVT = MVT::getVectorType(EltTy, NumElts);
 289   if (!isTypeLegal(NewVT))
 290     NewVT = EltTy;
 291   IntermediateVT = NewVT;
 292
 293   MVT::ValueType DestVT = getTypeToTransformTo(NewVT);
 294   RegisterVT = DestVT;
 295   if (DestVT < NewVT) {
 296     // Value is expanded, e.g. i64 -> i16.
 297     return NumVectorRegs*(MVT::getSizeInBits(NewVT)/MVT::getSizeInBits(DestVT));
 298   } else {
 299     // Otherwise, promotion or legal types use the same number of registers as
 300     // the vector decimated to the appropriate level.
 301     return NumVectorRegs;
 302   }
 303
 304   return 1;
 305 }
 306
 307 //===----------------------------------------------------------------------===//
 308 //  Optimization Methods
 309 //===----------------------------------------------------------------------===//
 310
 311 /// ShrinkDemandedConstant - Check to see if the specified operand of the
 312 /// specified instruction is a constant integer.  If so, check to see if there
 313 /// are any bits set in the constant that are not demanded.  If so, shrink the
 314 /// constant and return true.
 315 bool TargetLowering::TargetLoweringOpt::ShrinkDemandedConstant(SDOperand Op,
 316                                                             uint64_t Demanded) {
 317   // FIXME: ISD::SELECT, ISD::SELECT_CC
 318   switch(Op.getOpcode()) {
 319   default: break;
 320   case ISD::AND:
 321   case ISD::OR:
 322   case ISD::XOR:
 323     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
 324       if ((~Demanded & C->getValue()) != 0) {
 325         MVT::ValueType VT = Op.getValueType();
 326         SDOperand New = DAG.getNode(Op.getOpcode(), VT, Op.getOperand(0),
 327                                     DAG.getConstant(Demanded & C->getValue(),
 328                                                     VT));
 329         return CombineTo(Op, New);
 330       }
 331     break;
 332   }
 333   return false;
 334 }
 335
 336 /// SimplifyDemandedBits - Look at Op.  At this point, we know that only the
 337 /// DemandedMask bits of the result of Op are ever used downstream.  If we can
 338 /// use this information to simplify Op, create a new simplified DAG node and
 339 /// return true, returning the original and new nodes in Old and New. Otherwise,
 340 /// analyze the expression and return a mask of KnownOne and KnownZero bits for
 341 /// the expression (used to simplify the caller).  The KnownZero/One bits may
 342 /// only be accurate for those bits in the DemandedMask.
 343 bool TargetLowering::SimplifyDemandedBits(SDOperand Op, uint64_t DemandedMask,
 344                                           uint64_t &KnownZero,
 345                                           uint64_t &KnownOne,
 346                                           TargetLoweringOpt &TLO,
 347                                           unsigned Depth) const {
 348   KnownZero = KnownOne = 0;   // Don't know anything.
 349
 350   // The masks are not wide enough to represent this type!  Should use APInt.
 351   if (Op.getValueType() == MVT::i128)
 352     return false;
 353
 354   // Other users may use these bits.
 355   if (!Op.Val->hasOneUse()) {
 356     if (Depth != 0) {
 357       // If not at the root, Just compute the KnownZero/KnownOne bits to
 358       // simplify things downstream.
 359       TLO.DAG.ComputeMaskedBits(Op, DemandedMask, KnownZero, KnownOne, Depth);
 360       return false;
 361     }
 362     // If this is the root being simplified, allow it to have multiple uses,
 363     // just set the DemandedMask to all bits.
 364     DemandedMask = MVT::getIntVTBitMask(Op.getValueType());
 365   } else if (DemandedMask == 0) {
 366     // Not demanding any bits from Op.
 367     if (Op.getOpcode() != ISD::UNDEF)
 368       return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::UNDEF, Op.getValueType()));
 369     return false;
 370   } else if (Depth == 6) {        // Limit search depth.
 371     return false;
 372   }
 373
 374   uint64_t KnownZero2, KnownOne2, KnownZeroOut, KnownOneOut;
 375   switch (Op.getOpcode()) {
 376   case ISD::Constant:
 377     // We know all of the bits for a constant!
 378     KnownOne = cast<ConstantSDNode>(Op)->getValue() & DemandedMask;
 379     KnownZero = ~KnownOne & DemandedMask;
 380     return false;   // Don't fall through, will infinitely loop.
 381   case ISD::AND:
 382     // If the RHS is a constant, check to see if the LHS would be zero without
 383     // using the bits from the RHS.  Below, we use knowledge about the RHS to
 384     // simplify the LHS, here we're using information from the LHS to simplify
 385     // the RHS.
 386     if (ConstantSDNode *RHSC = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
 387       uint64_t LHSZero, LHSOne;
 388       TLO.DAG.ComputeMaskedBits(Op.getOperand(0), DemandedMask,
 389                                 LHSZero, LHSOne, Depth+1);
 390       // If the LHS already has zeros where RHSC does, this and is dead.
 391       if ((LHSZero & DemandedMask) == (~RHSC->getValue() & DemandedMask))
 392         return TLO.CombineTo(Op, Op.getOperand(0));
 393       // If any of the set bits in the RHS are known zero on the LHS, shrink
 394       // the constant.
 395       if (TLO.ShrinkDemandedConstant(Op, ~LHSZero & DemandedMask))
 396         return true;
 397     }
 398
 399     if (SimplifyDemandedBits(Op.getOperand(1), DemandedMask, KnownZero,
 400                              KnownOne, TLO, Depth+1))
 401       return true;
 402     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 403     if (SimplifyDemandedBits(Op.getOperand(0), DemandedMask & ~KnownZero,
 404                              KnownZero2, KnownOne2, TLO, Depth+1))
 405       return true;
 406     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
 407
 408     // If all of the demanded bits are known one on one side, return the other.
 409     // These bits cannot contribute to the result of the 'and'.
 410     if ((DemandedMask & ~KnownZero2 & KnownOne)==(DemandedMask & ~KnownZero2))
 411       return TLO.CombineTo(Op, Op.getOperand(0));
 412     if ((DemandedMask & ~KnownZero & KnownOne2)==(DemandedMask & ~KnownZero))
 413       return TLO.CombineTo(Op, Op.getOperand(1));
 414     // If all of the demanded bits in the inputs are known zeros, return zero.
 415     if ((DemandedMask & (KnownZero|KnownZero2)) == DemandedMask)
 416       return TLO.CombineTo(Op, TLO.DAG.getConstant(0, Op.getValueType()));
 417     // If the RHS is a constant, see if we can simplify it.
 418     if (TLO.ShrinkDemandedConstant(Op, DemandedMask & ~KnownZero2))
 419       return true;
 420
 421     // Output known-1 bits are only known if set in both the LHS & RHS.
 422     KnownOne &= KnownOne2;
 423     // Output known-0 are known to be clear if zero in either the LHS | RHS.
 424     KnownZero |= KnownZero2;
 425     break;
 426   case ISD::OR:
 427     if (SimplifyDemandedBits(Op.getOperand(1), DemandedMask, KnownZero,
 428                              KnownOne, TLO, Depth+1))
 429       return true;
 430     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 431     if (SimplifyDemandedBits(Op.getOperand(0), DemandedMask & ~KnownOne,
 432                              KnownZero2, KnownOne2, TLO, Depth+1))
 433       return true;
 434     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
 435
 436     // If all of the demanded bits are known zero on one side, return the other.
 437     // These bits cannot contribute to the result of the 'or'.
 438     if ((DemandedMask & ~KnownOne2 & KnownZero) == (DemandedMask & ~KnownOne2))
 439       return TLO.CombineTo(Op, Op.getOperand(0));
 440     if ((DemandedMask & ~KnownOne & KnownZero2) == (DemandedMask & ~KnownOne))
 441       return TLO.CombineTo(Op, Op.getOperand(1));
 442     // If all of the potentially set bits on one side are known to be set on
 443     // the other side, just use the 'other' side.
 444     if ((DemandedMask & (~KnownZero) & KnownOne2) ==
 445         (DemandedMask & (~KnownZero)))
 446       return TLO.CombineTo(Op, Op.getOperand(0));
 447     if ((DemandedMask & (~KnownZero2) & KnownOne) ==
 448         (DemandedMask & (~KnownZero2)))
 449       return TLO.CombineTo(Op, Op.getOperand(1));
 450     // If the RHS is a constant, see if we can simplify it.
 451     if (TLO.ShrinkDemandedConstant(Op, DemandedMask))
 452       return true;
 453
 454     // Output known-0 bits are only known if clear in both the LHS & RHS.
 455     KnownZero &= KnownZero2;
 456     // Output known-1 are known to be set if set in either the LHS | RHS.
 457     KnownOne |= KnownOne2;
 458     break;
 459   case ISD::XOR:
 460     if (SimplifyDemandedBits(Op.getOperand(1), DemandedMask, KnownZero,
 461                              KnownOne, TLO, Depth+1))
 462       return true;
 463     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 464     if (SimplifyDemandedBits(Op.getOperand(0), DemandedMask, KnownZero2,
 465                              KnownOne2, TLO, Depth+1))
 466       return true;
 467     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
 468
 469     // If all of the demanded bits are known zero on one side, return the other.
 470     // These bits cannot contribute to the result of the 'xor'.
 471     if ((DemandedMask & KnownZero) == DemandedMask)
 472       return TLO.CombineTo(Op, Op.getOperand(0));
 473     if ((DemandedMask & KnownZero2) == DemandedMask)
 474       return TLO.CombineTo(Op, Op.getOperand(1));
 475
 476     // If all of the unknown bits are known to be zero on one side or the other
 477     // (but not both) turn this into an *inclusive* or.
 478     //    e.g. (A & C1)^(B & C2) -> (A & C1)|(B & C2) iff C1&C2 == 0
 479     if ((DemandedMask & ~KnownZero & ~KnownZero2) == 0)
 480       return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::OR, Op.getValueType(),
 481                                                Op.getOperand(0),
 482                                                Op.getOperand(1)));
 483
 484     // Output known-0 bits are known if clear or set in both the LHS & RHS.
 485     KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
 486     // Output known-1 are known to be set if set in only one of the LHS, RHS.
 487     KnownOneOut = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
 488
 489     // If all of the demanded bits on one side are known, and all of the set
 490     // bits on that side are also known to be set on the other side, turn this
 491     // into an AND, as we know the bits will be cleared.
 492     //    e.g. (X | C1) ^ C2 --> (X | C1) & ~C2 iff (C1&C2) == C2
 493     if ((DemandedMask & (KnownZero|KnownOne)) == DemandedMask) { // all known
 494       if ((KnownOne & KnownOne2) == KnownOne) {
 495         MVT::ValueType VT = Op.getValueType();
 496         SDOperand ANDC = TLO.DAG.getConstant(~KnownOne & DemandedMask, VT);
 497         return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::AND, VT, Op.getOperand(0),
 498                                                  ANDC));
 499       }
 500     }
 501
 502     // If the RHS is a constant, see if we can simplify it.
 503     // FIXME: for XOR, we prefer to force bits to 1 if they will make a -1.
 504     if (TLO.ShrinkDemandedConstant(Op, DemandedMask))
 505       return true;
 506
 507     KnownZero = KnownZeroOut;
 508     KnownOne  = KnownOneOut;
 509     break;
 510   case ISD::SETCC:
 511     // If we know the result of a setcc has the top bits zero, use this info.
 512     if (getSetCCResultContents() == TargetLowering::ZeroOrOneSetCCResult)
 513       KnownZero |= (MVT::getIntVTBitMask(Op.getValueType()) ^ 1ULL);
 514     break;
 515   case ISD::SELECT:
 516     if (SimplifyDemandedBits(Op.getOperand(2), DemandedMask, KnownZero,
 517                              KnownOne, TLO, Depth+1))
 518       return true;
 519     if (SimplifyDemandedBits(Op.getOperand(1), DemandedMask, KnownZero2,
 520                              KnownOne2, TLO, Depth+1))
 521       return true;
 522     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 523     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
 524
 525     // If the operands are constants, see if we can simplify them.
 526     if (TLO.ShrinkDemandedConstant(Op, DemandedMask))
 527       return true;
 528
 529     // Only known if known in both the LHS and RHS.
 530     KnownOne &= KnownOne2;
 531     KnownZero &= KnownZero2;
 532     break;
 533   case ISD::SELECT_CC:
 534     if (SimplifyDemandedBits(Op.getOperand(3), DemandedMask, KnownZero,
 535                              KnownOne, TLO, Depth+1))
 536       return true;
 537     if (SimplifyDemandedBits(Op.getOperand(2), DemandedMask, KnownZero2,
 538                              KnownOne2, TLO, Depth+1))
 539       return true;
 540     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 541     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
 542
 543     // If the operands are constants, see if we can simplify them.
 544     if (TLO.ShrinkDemandedConstant(Op, DemandedMask))
 545       return true;
 546
 547     // Only known if known in both the LHS and RHS.
 548     KnownOne &= KnownOne2;
 549     KnownZero &= KnownZero2;
 550     break;
 551   case ISD::SHL:
 552     if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
 553       unsigned ShAmt = SA->getValue();
 554       SDOperand InOp = Op.getOperand(0);
 555
 556       // If this is ((X >>u C1) << ShAmt), see if we can simplify this into a
 557       // single shift.  We can do this if the bottom bits (which are shifted
 558       // out) are never demanded.
 559       if (InOp.getOpcode() == ISD::SRL &&
 560           isa<ConstantSDNode>(InOp.getOperand(1))) {
 561         if (ShAmt && (DemandedMask & ((1ULL << ShAmt)-1)) == 0) {
 562           unsigned C1 = cast<ConstantSDNode>(InOp.getOperand(1))->getValue();
 563           unsigned Opc = ISD::SHL;
 564           int Diff = ShAmt-C1;
 565           if (Diff < 0) {
 566             Diff = -Diff;
 567             Opc = ISD::SRL;
 568           }
 569
 570           SDOperand NewSA =
 571             TLO.DAG.getConstant(Diff, Op.getOperand(1).getValueType());
 572           MVT::ValueType VT = Op.getValueType();
 573           return TLO.CombineTo(Op, TLO.DAG.getNode(Opc, VT,
 574                                                    InOp.getOperand(0), NewSA));
 575         }
 576       }
 577
 578       if (SimplifyDemandedBits(Op.getOperand(0), DemandedMask >> ShAmt,
 579                                KnownZero, KnownOne, TLO, Depth+1))
 580         return true;
 581       KnownZero <<= SA->getValue();
 582       KnownOne  <<= SA->getValue();
 583       KnownZero |= (1ULL << SA->getValue())-1;  // low bits known zero.
 584     }
 585     break;
 586   case ISD::SRL:
 587     if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
 588       MVT::ValueType VT = Op.getValueType();
 589       unsigned ShAmt = SA->getValue();
 590       uint64_t TypeMask = MVT::getIntVTBitMask(VT);
 591       unsigned VTSize = MVT::getSizeInBits(VT);
 592       SDOperand InOp = Op.getOperand(0);
 593
 594       // If this is ((X << C1) >>u ShAmt), see if we can simplify this into a
 595       // single shift.  We can do this if the top bits (which are shifted out)
 596       // are never demanded.
 597       if (InOp.getOpcode() == ISD::SHL &&
 598           isa<ConstantSDNode>(InOp.getOperand(1))) {
 599         if (ShAmt && (DemandedMask & (~0ULL << (VTSize-ShAmt))) == 0) {
 600           unsigned C1 = cast<ConstantSDNode>(InOp.getOperand(1))->getValue();
 601           unsigned Opc = ISD::SRL;
 602           int Diff = ShAmt-C1;
 603           if (Diff < 0) {
 604             Diff = -Diff;
 605             Opc = ISD::SHL;
 606           }
 607
 608           SDOperand NewSA =
 609             TLO.DAG.getConstant(Diff, Op.getOperand(1).getValueType());
 610           return TLO.CombineTo(Op, TLO.DAG.getNode(Opc, VT,
 611                                                    InOp.getOperand(0), NewSA));
 612         }
 613       }
 614
 615       // Compute the new bits that are at the top now.
 616       if (SimplifyDemandedBits(InOp, (DemandedMask << ShAmt) & TypeMask,
 617                                KnownZero, KnownOne, TLO, Depth+1))
 618         return true;
 619       assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 620       KnownZero &= TypeMask;
 621       KnownOne  &= TypeMask;
 622       KnownZero >>= ShAmt;
 623       KnownOne  >>= ShAmt;
 624
 625       uint64_t HighBits = (1ULL << ShAmt)-1;
 626       HighBits <<= VTSize - ShAmt;
 627       KnownZero |= HighBits;  // High bits known zero.
 628     }
 629     break;
 630   case ISD::SRA:
 631     if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
 632       MVT::ValueType VT = Op.getValueType();
 633       unsigned ShAmt = SA->getValue();
 634
 635       // Compute the new bits that are at the top now.
 636       uint64_t TypeMask = MVT::getIntVTBitMask(VT);
 637
 638       uint64_t InDemandedMask = (DemandedMask << ShAmt) & TypeMask;
 639
 640       // If any of the demanded bits are produced by the sign extension, we also
 641       // demand the input sign bit.
 642       uint64_t HighBits = (1ULL << ShAmt)-1;
 643       HighBits <<= MVT::getSizeInBits(VT) - ShAmt;
 644       if (HighBits & DemandedMask)
 645         InDemandedMask |= MVT::getIntVTSignBit(VT);
 646
 647       if (SimplifyDemandedBits(Op.getOperand(0), InDemandedMask,
 648                                KnownZero, KnownOne, TLO, Depth+1))
 649         return true;
 650       assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 651       KnownZero &= TypeMask;
 652       KnownOne  &= TypeMask;
 653       KnownZero >>= ShAmt;
 654       KnownOne  >>= ShAmt;
 655
 656       // Handle the sign bits.
 657       uint64_t SignBit = MVT::getIntVTSignBit(VT);
 658       SignBit >>= ShAmt;  // Adjust to where it is now in the mask.
 659
 660       // If the input sign bit is known to be zero, or if none of the top bits
 661       // are demanded, turn this into an unsigned shift right.
 662       if ((KnownZero & SignBit) || (HighBits & ~DemandedMask) == HighBits) {
 663         return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::SRL, VT, Op.getOperand(0),
 664                                                  Op.getOperand(1)));
 665       } else if (KnownOne & SignBit) { // New bits are known one.
 666         KnownOne |= HighBits;
 667       }
 668     }
 669     break;
 670   case ISD::SIGN_EXTEND_INREG: {
 671     MVT::ValueType EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
 672
 673     // Sign extension.  Compute the demanded bits in the result that are not
 674     // present in the input.
 675     uint64_t NewBits = ~MVT::getIntVTBitMask(EVT) & DemandedMask;
 676
 677     // If none of the extended bits are demanded, eliminate the sextinreg.
 678     if (NewBits == 0)
 679       return TLO.CombineTo(Op, Op.getOperand(0));
 680
 681     uint64_t InSignBit = MVT::getIntVTSignBit(EVT);
 682     int64_t InputDemandedBits = DemandedMask & MVT::getIntVTBitMask(EVT);
 683
 684     // Since the sign extended bits are demanded, we know that the sign
 685     // bit is demanded.
 686     InputDemandedBits |= InSignBit;
 687
 688     if (SimplifyDemandedBits(Op.getOperand(0), InputDemandedBits,
 689                              KnownZero, KnownOne, TLO, Depth+1))
 690       return true;
 691     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 692
 693     // If the sign bit of the input is known set or clear, then we know the
 694     // top bits of the result.
 695
 696     // If the input sign bit is known zero, convert this into a zero extension.
 697     if (KnownZero & InSignBit)
 698       return TLO.CombineTo(Op,
 699                            TLO.DAG.getZeroExtendInReg(Op.getOperand(0), EVT));
 700
 701     if (KnownOne & InSignBit) {    // Input sign bit known set
 702       KnownOne |= NewBits;
 703       KnownZero &= ~NewBits;
 704     } else {                       // Input sign bit unknown
 705       KnownZero &= ~NewBits;
 706       KnownOne &= ~NewBits;
 707     }
 708     break;
 709   }
 710   case ISD::CTTZ:
 711   case ISD::CTLZ:
 712   case ISD::CTPOP: {
 713     MVT::ValueType VT = Op.getValueType();
 714     unsigned LowBits = Log2_32(MVT::getSizeInBits(VT))+1;
 715     KnownZero = ~((1ULL << LowBits)-1) & MVT::getIntVTBitMask(VT);
 716     KnownOne  = 0;
 717     break;
 718   }
 719   case ISD::LOAD: {
 720     if (ISD::isZEXTLoad(Op.Val)) {
 721       LoadSDNode *LD = cast<LoadSDNode>(Op);
 722       MVT::ValueType VT = LD->getLoadedVT();
 723       KnownZero |= ~MVT::getIntVTBitMask(VT) & DemandedMask;
 724     }
 725     break;
 726   }
 727   case ISD::ZERO_EXTEND: {
 728     uint64_t InMask = MVT::getIntVTBitMask(Op.getOperand(0).getValueType());
 729
 730     // If none of the top bits are demanded, convert this into an any_extend.
 731     uint64_t NewBits = (~InMask) & DemandedMask;
 732     if (NewBits == 0)
 733       return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::ANY_EXTEND,
 734                                                Op.getValueType(),
 735                                                Op.getOperand(0)));
 736
 737     if (SimplifyDemandedBits(Op.getOperand(0), DemandedMask & InMask,
 738                              KnownZero, KnownOne, TLO, Depth+1))
 739       return true;
 740     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 741     KnownZero |= NewBits;
 742     break;
 743   }
 744   case ISD::SIGN_EXTEND: {
 745     MVT::ValueType InVT = Op.getOperand(0).getValueType();
 746     uint64_t InMask    = MVT::getIntVTBitMask(InVT);
 747     uint64_t InSignBit = MVT::getIntVTSignBit(InVT);
 748     uint64_t NewBits   = (~InMask) & DemandedMask;
 749
 750     // If none of the top bits are demanded, convert this into an any_extend.
 751     if (NewBits == 0)
 752       return TLO.CombineTo(Op,TLO.DAG.getNode(ISD::ANY_EXTEND,Op.getValueType(),
 753                                            Op.getOperand(0)));
 754
 755     // Since some of the sign extended bits are demanded, we know that the sign
 756     // bit is demanded.
 757     uint64_t InDemandedBits = DemandedMask & InMask;
 758     InDemandedBits |= InSignBit;
 759
 760     if (SimplifyDemandedBits(Op.getOperand(0), InDemandedBits, KnownZero,
 761                              KnownOne, TLO, Depth+1))
 762       return true;
 763
 764     // If the sign bit is known zero, convert this to a zero extend.
 765     if (KnownZero & InSignBit)
 766       return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::ZERO_EXTEND,
 767                                                Op.getValueType(),
 768                                                Op.getOperand(0)));
 769
 770     // If the sign bit is known one, the top bits match.
 771     if (KnownOne & InSignBit) {
 772       KnownOne  |= NewBits;
 773       KnownZero &= ~NewBits;
 774     } else {   // Otherwise, top bits aren't known.
 775       KnownOne  &= ~NewBits;
 776       KnownZero &= ~NewBits;
 777     }
 778     break;
 779   }
 780   case ISD::ANY_EXTEND: {
 781     uint64_t InMask = MVT::getIntVTBitMask(Op.getOperand(0).getValueType());
 782     if (SimplifyDemandedBits(Op.getOperand(0), DemandedMask & InMask,
 783                              KnownZero, KnownOne, TLO, Depth+1))
 784       return true;
 785     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 786     break;
 787   }
 788   case ISD::TRUNCATE: {
 789     // Simplify the input, using demanded bit information, and compute the known
 790     // zero/one bits live out.
 791     if (SimplifyDemandedBits(Op.getOperand(0), DemandedMask,
 792                              KnownZero, KnownOne, TLO, Depth+1))
 793       return true;
 794
 795     // If the input is only used by this truncate, see if we can shrink it based
 796     // on the known demanded bits.
 797     if (Op.getOperand(0).Val->hasOneUse()) {
 798       SDOperand In = Op.getOperand(0);
 799       switch (In.getOpcode()) {
 800       default: break;
 801       case ISD::SRL:
 802         // Shrink SRL by a constant if none of the high bits shifted in are
 803         // demanded.
 804         if (ConstantSDNode *ShAmt = dyn_cast<ConstantSDNode>(In.getOperand(1))){
 805           uint64_t HighBits = MVT::getIntVTBitMask(In.getValueType());
 806           HighBits &= ~MVT::getIntVTBitMask(Op.getValueType());
 807           HighBits >>= ShAmt->getValue();
 808
 809           if (ShAmt->getValue() < MVT::getSizeInBits(Op.getValueType()) &&
 810               (DemandedMask & HighBits) == 0) {
 811             // None of the shifted in bits are needed.  Add a truncate of the
 812             // shift input, then shift it.
 813             SDOperand NewTrunc = TLO.DAG.getNode(ISD::TRUNCATE,
 814                                                  Op.getValueType(),
 815                                                  In.getOperand(0));
 816             return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::SRL,Op.getValueType(),
 817                                                    NewTrunc, In.getOperand(1)));
 818           }
 819         }
 820         break;
 821       }
 822     }
 823
 824     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 825     uint64_t OutMask = MVT::getIntVTBitMask(Op.getValueType());
 826     KnownZero &= OutMask;
 827     KnownOne &= OutMask;
 828     break;
 829   }
 830   case ISD::AssertZext: {
 831     MVT::ValueType VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
 832     uint64_t InMask = MVT::getIntVTBitMask(VT);
 833     if (SimplifyDemandedBits(Op.getOperand(0), DemandedMask & InMask,
 834                              KnownZero, KnownOne, TLO, Depth+1))
 835       return true;
 836     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 837     KnownZero |= ~InMask & DemandedMask;
 838     break;
 839   }
 840   case ISD::ADD:
 841   case ISD::SUB:
 842   case ISD::INTRINSIC_WO_CHAIN:
 843   case ISD::INTRINSIC_W_CHAIN:
 844   case ISD::INTRINSIC_VOID:
 845     // Just use ComputeMaskedBits to compute output bits.
 846     TLO.DAG.ComputeMaskedBits(Op, DemandedMask, KnownZero, KnownOne, Depth);
 847     break;
 848   }
 849
 850   // If we know the value of all of the demanded bits, return this as a
 851   // constant.
 852   if ((DemandedMask & (KnownZero|KnownOne)) == DemandedMask)
 853     return TLO.CombineTo(Op, TLO.DAG.getConstant(KnownOne, Op.getValueType()));
 854
 855   return false;
 856 }
 857
 858 /// computeMaskedBitsForTargetNode - Determine which of the bits specified
 859 /// in Mask are known to be either zero or one and return them in the
 860 /// KnownZero/KnownOne bitsets.
 861 void TargetLowering::computeMaskedBitsForTargetNode(const SDOperand Op,
 862                                                     uint64_t Mask,
 863                                                     uint64_t &KnownZero,
 864                                                     uint64_t &KnownOne,
 865                                                     const SelectionDAG &DAG,
 866                                                     unsigned Depth) const {
 867   assert((Op.getOpcode() >= ISD::BUILTIN_OP_END ||
 868           Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
 869           Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
 870           Op.getOpcode() == ISD::INTRINSIC_VOID) &&
 871          "Should use MaskedValueIsZero if you don't know whether Op"
 872          " is a target node!");
 873   KnownZero = 0;
 874   KnownOne = 0;
 875 }
 876
 877 /// ComputeNumSignBitsForTargetNode - This method can be implemented by
 878 /// targets that want to expose additional information about sign bits to the
 879 /// DAG Combiner.
 880 unsigned TargetLowering::ComputeNumSignBitsForTargetNode(SDOperand Op,
 881                                                          unsigned Depth) const {
 882   assert((Op.getOpcode() >= ISD::BUILTIN_OP_END ||
 883           Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
 884           Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
 885           Op.getOpcode() == ISD::INTRINSIC_VOID) &&
 886          "Should use ComputeNumSignBits if you don't know whether Op"
 887          " is a target node!");
 888   return 1;
 889 }
 890
 891
 892 /// SimplifySetCC - Try to simplify a setcc built with the specified operands
 893 /// and cc. If it is unable to simplify it, return a null SDOperand.
 894 SDOperand
 895 TargetLowering::SimplifySetCC(MVT::ValueType VT, SDOperand N0, SDOperand N1,
 896                               ISD::CondCode Cond, bool foldBooleans,
 897                               DAGCombinerInfo &DCI) const {
 898   SelectionDAG &DAG = DCI.DAG;
 899
 900   // These setcc operations always fold.
 901   switch (Cond) {
 902   default: break;
 903   case ISD::SETFALSE:
 904   case ISD::SETFALSE2: return DAG.getConstant(0, VT);
 905   case ISD::SETTRUE:
 906   case ISD::SETTRUE2:  return DAG.getConstant(1, VT);
 907   }
 908
 909   if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val)) {
 910     uint64_t C1 = N1C->getValue();
 911     if (isa<ConstantSDNode>(N0.Val)) {
 912       return DAG.FoldSetCC(VT, N0, N1, Cond);
 913     } else {
 914       // If the LHS is '(srl (ctlz x), 5)', the RHS is 0/1, and this is an
 915       // equality comparison, then we're just comparing whether X itself is
 916       // zero.
 917       if (N0.getOpcode() == ISD::SRL && (C1 == 0 || C1 == 1) &&
 918           N0.getOperand(0).getOpcode() == ISD::CTLZ &&
 919           N0.getOperand(1).getOpcode() == ISD::Constant) {
 920         unsigned ShAmt = cast<ConstantSDNode>(N0.getOperand(1))->getValue();
 921         if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
 922             ShAmt == Log2_32(MVT::getSizeInBits(N0.getValueType()))) {
 923           if ((C1 == 0) == (Cond == ISD::SETEQ)) {
 924             // (srl (ctlz x), 5) == 0  -> X != 0
 925             // (srl (ctlz x), 5) != 1  -> X != 0
 926             Cond = ISD::SETNE;
 927           } else {
 928             // (srl (ctlz x), 5) != 0  -> X == 0
 929             // (srl (ctlz x), 5) == 1  -> X == 0
 930             Cond = ISD::SETEQ;
 931           }
 932           SDOperand Zero = DAG.getConstant(0, N0.getValueType());
 933           return DAG.getSetCC(VT, N0.getOperand(0).getOperand(0),
 934                               Zero, Cond);
 935         }
 936       }
 937
 938       // If the LHS is a ZERO_EXTEND, perform the comparison on the input.
 939       if (N0.getOpcode() == ISD::ZERO_EXTEND) {
 940         unsigned InSize = MVT::getSizeInBits(N0.getOperand(0).getValueType());
 941
 942         // If the comparison constant has bits in the upper part, the
 943         // zero-extended value could never match.
 944         if (C1 & (~0ULL << InSize)) {
 945           unsigned VSize = MVT::getSizeInBits(N0.getValueType());
 946           switch (Cond) {
 947           case ISD::SETUGT:
 948           case ISD::SETUGE:
 949           case ISD::SETEQ: return DAG.getConstant(0, VT);
 950           case ISD::SETULT:
 951           case ISD::SETULE:
 952           case ISD::SETNE: return DAG.getConstant(1, VT);
 953           case ISD::SETGT:
 954           case ISD::SETGE:
 955             // True if the sign bit of C1 is set.
 956             return DAG.getConstant((C1 & (1ULL << (VSize-1))) != 0, VT);
 957           case ISD::SETLT:
 958           case ISD::SETLE:
 959             // True if the sign bit of C1 isn't set.
 960             return DAG.getConstant((C1 & (1ULL << (VSize-1))) == 0, VT);
 961           default:
 962             break;
 963           }
 964         }
 965
 966         // Otherwise, we can perform the comparison with the low bits.
 967         switch (Cond) {
 968         case ISD::SETEQ:
 969         case ISD::SETNE:
 970         case ISD::SETUGT:
 971         case ISD::SETUGE:
 972         case ISD::SETULT:
 973         case ISD::SETULE:
 974           return DAG.getSetCC(VT, N0.getOperand(0),
 975                           DAG.getConstant(C1, N0.getOperand(0).getValueType()),
 976                           Cond);
 977         default:
 978           break;   // todo, be more careful with signed comparisons
 979         }
 980       } else if (N0.getOpcode() == ISD::SIGN_EXTEND_INREG &&
 981                  (Cond == ISD::SETEQ || Cond == ISD::SETNE)) {
 982         MVT::ValueType ExtSrcTy = cast<VTSDNode>(N0.getOperand(1))->getVT();
 983         unsigned ExtSrcTyBits = MVT::getSizeInBits(ExtSrcTy);
 984         MVT::ValueType ExtDstTy = N0.getValueType();
 985         unsigned ExtDstTyBits = MVT::getSizeInBits(ExtDstTy);
 986
 987         // If the extended part has any inconsistent bits, it cannot ever
 988         // compare equal.  In other words, they have to be all ones or all
 989         // zeros.
 990         uint64_t ExtBits =
 991           (~0ULL >> (64-ExtSrcTyBits)) & (~0ULL << (ExtDstTyBits-1));
 992         if ((C1 & ExtBits) != 0 && (C1 & ExtBits) != ExtBits)
 993           return DAG.getConstant(Cond == ISD::SETNE, VT);
 994
 995         SDOperand ZextOp;
 996         MVT::ValueType Op0Ty = N0.getOperand(0).getValueType();
 997         if (Op0Ty == ExtSrcTy) {
 998           ZextOp = N0.getOperand(0);
 999         } else {
1000           int64_t Imm = ~0ULL >> (64-ExtSrcTyBits);
1001           ZextOp = DAG.getNode(ISD::AND, Op0Ty, N0.getOperand(0),
1002                                DAG.getConstant(Imm, Op0Ty));
1003         }
1004         if (!DCI.isCalledByLegalizer())
1005           DCI.AddToWorklist(ZextOp.Val);
1006         // Otherwise, make this a use of a zext.
1007         return DAG.getSetCC(VT, ZextOp,
1008                             DAG.getConstant(C1 & (~0ULL>>(64-ExtSrcTyBits)),
1009                                             ExtDstTy),
1010                             Cond);
1011       } else if ((N1C->getValue() == 0 || N1C->getValue() == 1) &&
1012                  (Cond == ISD::SETEQ || Cond == ISD::SETNE)) {
1013
1014         // SETCC (SETCC), [0|1], [EQ|NE]  -> SETCC
1015         if (N0.getOpcode() == ISD::SETCC) {
1016           bool TrueWhenTrue = (Cond == ISD::SETEQ) ^ (N1C->getValue() != 1);
1017           if (TrueWhenTrue)
1018             return N0;
1019
1020           // Invert the condition.
1021           ISD::CondCode CC = cast<CondCodeSDNode>(N0.getOperand(2))->get();
1022           CC = ISD::getSetCCInverse(CC,
1023                                MVT::isInteger(N0.getOperand(0).getValueType()));
1024           return DAG.getSetCC(VT, N0.getOperand(0), N0.getOperand(1), CC);
1025         }
1026
1027         if ((N0.getOpcode() == ISD::XOR ||
1028              (N0.getOpcode() == ISD::AND &&
1029               N0.getOperand(0).getOpcode() == ISD::XOR &&
1030               N0.getOperand(1) == N0.getOperand(0).getOperand(1))) &&
1031             isa<ConstantSDNode>(N0.getOperand(1)) &&
1032             cast<ConstantSDNode>(N0.getOperand(1))->getValue() == 1) {
1033           // If this is (X^1) == 0/1, swap the RHS and eliminate the xor.  We
1034           // can only do this if the top bits are known zero.
1035           if (DAG.MaskedValueIsZero(N0,
1036                                     MVT::getIntVTBitMask(N0.getValueType())-1)){
1037             // Okay, get the un-inverted input value.
1038             SDOperand Val;
1039             if (N0.getOpcode() == ISD::XOR)
1040               Val = N0.getOperand(0);
1041             else {
1042               assert(N0.getOpcode() == ISD::AND &&
1043                      N0.getOperand(0).getOpcode() == ISD::XOR);
1044               // ((X^1)&1)^1 -> X & 1
1045               Val = DAG.getNode(ISD::AND, N0.getValueType(),
1046                                 N0.getOperand(0).getOperand(0),
1047                                 N0.getOperand(1));
1048             }
1049             return DAG.getSetCC(VT, Val, N1,
1050                                 Cond == ISD::SETEQ ? ISD::SETNE : ISD::SETEQ);
1051           }
1052         }
1053       }
1054
1055       uint64_t MinVal, MaxVal;
1056       unsigned OperandBitSize = MVT::getSizeInBits(N1C->getValueType(0));
1057       if (ISD::isSignedIntSetCC(Cond)) {
1058         MinVal = 1ULL << (OperandBitSize-1);
1059         if (OperandBitSize != 1)   // Avoid X >> 64, which is undefined.
1060           MaxVal = ~0ULL >> (65-OperandBitSize);
1061         else
1062           MaxVal = 0;
1063       } else {
1064         MinVal = 0;
1065         MaxVal = ~0ULL >> (64-OperandBitSize);
1066       }
1067
1068       // Canonicalize GE/LE comparisons to use GT/LT comparisons.
1069       if (Cond == ISD::SETGE || Cond == ISD::SETUGE) {
1070         if (C1 == MinVal) return DAG.getConstant(1, VT);   // X >= MIN --> true
1071         --C1;                                          // X >= C0 --> X > (C0-1)
1072         return DAG.getSetCC(VT, N0, DAG.getConstant(C1, N1.getValueType()),
1073                         (Cond == ISD::SETGE) ? ISD::SETGT : ISD::SETUGT);
1074       }
1075
1076       if (Cond == ISD::SETLE || Cond == ISD::SETULE) {
1077         if (C1 == MaxVal) return DAG.getConstant(1, VT);   // X <= MAX --> true
1078         ++C1;                                          // X <= C0 --> X < (C0+1)
1079         return DAG.getSetCC(VT, N0, DAG.getConstant(C1, N1.getValueType()),
1080                         (Cond == ISD::SETLE) ? ISD::SETLT : ISD::SETULT);
1081       }
1082
1083       if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C1 == MinVal)
1084         return DAG.getConstant(0, VT);      // X < MIN --> false
1085       if ((Cond == ISD::SETGE || Cond == ISD::SETUGE) && C1 == MinVal)
1086         return DAG.getConstant(1, VT);      // X >= MIN --> true
1087       if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C1 == MaxVal)
1088         return DAG.getConstant(0, VT);      // X > MAX --> false
1089       if ((Cond == ISD::SETLE || Cond == ISD::SETULE) && C1 == MaxVal)
1090         return DAG.getConstant(1, VT);      // X <= MAX --> true
1091
1092       // Canonicalize setgt X, Min --> setne X, Min
1093       if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C1 == MinVal)
1094         return DAG.getSetCC(VT, N0, N1, ISD::SETNE);
1095       // Canonicalize setlt X, Max --> setne X, Max
1096       if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C1 == MaxVal)
1097         return DAG.getSetCC(VT, N0, N1, ISD::SETNE);
1098
1099       // If we have setult X, 1, turn it into seteq X, 0
1100       if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C1 == MinVal+1)
1101         return DAG.getSetCC(VT, N0, DAG.getConstant(MinVal, N0.getValueType()),
1102                         ISD::SETEQ);
1103       // If we have setugt X, Max-1, turn it into seteq X, Max
1104       else if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C1 == MaxVal-1)
1105         return DAG.getSetCC(VT, N0, DAG.getConstant(MaxVal, N0.getValueType()),
1106                         ISD::SETEQ);
1107
1108       // If we have "setcc X, C0", check to see if we can shrink the immediate
1109       // by changing cc.
1110
1111       // SETUGT X, SINTMAX  -> SETLT X, 0
1112       if (Cond == ISD::SETUGT && OperandBitSize != 1 &&
1113           C1 == (~0ULL >> (65-OperandBitSize)))
1114         return DAG.getSetCC(VT, N0, DAG.getConstant(0, N1.getValueType()),
1115                             ISD::SETLT);
1116
1117       // FIXME: Implement the rest of these.
1118
1119       // Fold bit comparisons when we can.
1120       if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
1121           VT == N0.getValueType() && N0.getOpcode() == ISD::AND)
1122         if (ConstantSDNode *AndRHS =
1123                     dyn_cast<ConstantSDNode>(N0.getOperand(1))) {
1124           if (Cond == ISD::SETNE && C1 == 0) {// (X & 8) != 0  -->  (X & 8) >> 3
1125             // Perform the xform if the AND RHS is a single bit.
1126             if (isPowerOf2_64(AndRHS->getValue())) {
1127               return DAG.getNode(ISD::SRL, VT, N0,
1128                              DAG.getConstant(Log2_64(AndRHS->getValue()),
1129                                              getShiftAmountTy()));
1130             }
1131           } else if (Cond == ISD::SETEQ && C1 == AndRHS->getValue()) {
1132             // (X & 8) == 8  -->  (X & 8) >> 3
1133             // Perform the xform if C1 is a single bit.
1134             if (isPowerOf2_64(C1)) {
1135               return DAG.getNode(ISD::SRL, VT, N0,
1136                           DAG.getConstant(Log2_64(C1), getShiftAmountTy()));
1137             }
1138           }
1139         }
1140     }
1141   } else if (isa<ConstantSDNode>(N0.Val)) {
1142       // Ensure that the constant occurs on the RHS.
1143     return DAG.getSetCC(VT, N1, N0, ISD::getSetCCSwappedOperands(Cond));
1144   }
1145
1146   if (isa<ConstantFPSDNode>(N0.Val)) {
1147     // Constant fold or commute setcc.
1148     SDOperand O = DAG.FoldSetCC(VT, N0, N1, Cond);
1149     if (O.Val) return O;
1150   }
1151
1152   if (N0 == N1) {
1153     // We can always fold X == X for integer setcc's.
1154     if (MVT::isInteger(N0.getValueType()))
1155       return DAG.getConstant(ISD::isTrueWhenEqual(Cond), VT);
1156     unsigned UOF = ISD::getUnorderedFlavor(Cond);
1157     if (UOF == 2)   // FP operators that are undefined on NaNs.
1158       return DAG.getConstant(ISD::isTrueWhenEqual(Cond), VT);
1159     if (UOF == unsigned(ISD::isTrueWhenEqual(Cond)))
1160       return DAG.getConstant(UOF, VT);
1161     // Otherwise, we can't fold it.  However, we can simplify it to SETUO/SETO
1162     // if it is not already.
1163     ISD::CondCode NewCond = UOF == 0 ? ISD::SETO : ISD::SETUO;
1164     if (NewCond != Cond)
1165       return DAG.getSetCC(VT, N0, N1, NewCond);
1166   }
1167
1168   if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
1169       MVT::isInteger(N0.getValueType())) {
1170     if (N0.getOpcode() == ISD::ADD || N0.getOpcode() == ISD::SUB ||
1171         N0.getOpcode() == ISD::XOR) {
1172       // Simplify (X+Y) == (X+Z) -->  Y == Z
1173       if (N0.getOpcode() == N1.getOpcode()) {
1174         if (N0.getOperand(0) == N1.getOperand(0))
1175           return DAG.getSetCC(VT, N0.getOperand(1), N1.getOperand(1), Cond);
1176         if (N0.getOperand(1) == N1.getOperand(1))
1177           return DAG.getSetCC(VT, N0.getOperand(0), N1.getOperand(0), Cond);
1178         if (DAG.isCommutativeBinOp(N0.getOpcode())) {
1179           // If X op Y == Y op X, try other combinations.
1180           if (N0.getOperand(0) == N1.getOperand(1))
1181             return DAG.getSetCC(VT, N0.getOperand(1), N1.getOperand(0), Cond);
1182           if (N0.getOperand(1) == N1.getOperand(0))
1183             return DAG.getSetCC(VT, N0.getOperand(0), N1.getOperand(1), Cond);
1184         }
1185       }
1186
1187       if (ConstantSDNode *RHSC = dyn_cast<ConstantSDNode>(N1)) {
1188         if (ConstantSDNode *LHSR = dyn_cast<ConstantSDNode>(N0.getOperand(1))) {
1189           // Turn (X+C1) == C2 --> X == C2-C1
1190           if (N0.getOpcode() == ISD::ADD && N0.Val->hasOneUse()) {
1191             return DAG.getSetCC(VT, N0.getOperand(0),
1192                               DAG.getConstant(RHSC->getValue()-LHSR->getValue(),
1193                                 N0.getValueType()), Cond);
1194           }
1195
1196           // Turn (X^C1) == C2 into X == C1^C2 iff X&~C1 = 0.
1197           if (N0.getOpcode() == ISD::XOR)
1198             // If we know that all of the inverted bits are zero, don't bother
1199             // performing the inversion.
1200             if (DAG.MaskedValueIsZero(N0.getOperand(0), ~LHSR->getValue()))
1201               return DAG.getSetCC(VT, N0.getOperand(0),
1202                               DAG.getConstant(LHSR->getValue()^RHSC->getValue(),
1203                                               N0.getValueType()), Cond);
1204         }
1205
1206         // Turn (C1-X) == C2 --> X == C1-C2
1207         if (ConstantSDNode *SUBC = dyn_cast<ConstantSDNode>(N0.getOperand(0))) {
1208           if (N0.getOpcode() == ISD::SUB && N0.Val->hasOneUse()) {
1209             return DAG.getSetCC(VT, N0.getOperand(1),
1210                              DAG.getConstant(SUBC->getValue()-RHSC->getValue(),
1211                                              N0.getValueType()), Cond);
1212           }
1213         }
1214       }
1215
1216       // Simplify (X+Z) == X -->  Z == 0
1217       if (N0.getOperand(0) == N1)
1218         return DAG.getSetCC(VT, N0.getOperand(1),
1219                         DAG.getConstant(0, N0.getValueType()), Cond);
1220       if (N0.getOperand(1) == N1) {
1221         if (DAG.isCommutativeBinOp(N0.getOpcode()))
1222           return DAG.getSetCC(VT, N0.getOperand(0),
1223                           DAG.getConstant(0, N0.getValueType()), Cond);
1224         else if (N0.Val->hasOneUse()) {
1225           assert(N0.getOpcode() == ISD::SUB && "Unexpected operation!");
1226           // (Z-X) == X  --> Z == X<<1
1227           SDOperand SH = DAG.getNode(ISD::SHL, N1.getValueType(),
1228                                      N1,
1229                                      DAG.getConstant(1, getShiftAmountTy()));
1230           if (!DCI.isCalledByLegalizer())
1231             DCI.AddToWorklist(SH.Val);
1232           return DAG.getSetCC(VT, N0.getOperand(0), SH, Cond);
1233         }
1234       }
1235     }
1236
1237     if (N1.getOpcode() == ISD::ADD || N1.getOpcode() == ISD::SUB ||
1238         N1.getOpcode() == ISD::XOR) {
1239       // Simplify  X == (X+Z) -->  Z == 0
1240       if (N1.getOperand(0) == N0) {
1241         return DAG.getSetCC(VT, N1.getOperand(1),
1242                         DAG.getConstant(0, N1.getValueType()), Cond);
1243       } else if (N1.getOperand(1) == N0) {
1244         if (DAG.isCommutativeBinOp(N1.getOpcode())) {
1245           return DAG.getSetCC(VT, N1.getOperand(0),
1246                           DAG.getConstant(0, N1.getValueType()), Cond);
1247         } else if (N1.Val->hasOneUse()) {
1248           assert(N1.getOpcode() == ISD::SUB && "Unexpected operation!");
1249           // X == (Z-X)  --> X<<1 == Z
1250           SDOperand SH = DAG.getNode(ISD::SHL, N1.getValueType(), N0,
1251                                      DAG.getConstant(1, getShiftAmountTy()));
1252           if (!DCI.isCalledByLegalizer())
1253             DCI.AddToWorklist(SH.Val);
1254           return DAG.getSetCC(VT, SH, N1.getOperand(0), Cond);
1255         }
1256       }
1257     }
1258   }
1259
1260   // Fold away ALL boolean setcc's.
1261   SDOperand Temp;
1262   if (N0.getValueType() == MVT::i1 && foldBooleans) {
1263     switch (Cond) {
1264     default: assert(0 && "Unknown integer setcc!");
1265     case ISD::SETEQ:  // X == Y  -> (X^Y)^1
1266       Temp = DAG.getNode(ISD::XOR, MVT::i1, N0, N1);
1267       N0 = DAG.getNode(ISD::XOR, MVT::i1, Temp, DAG.getConstant(1, MVT::i1));
1268       if (!DCI.isCalledByLegalizer())
1269         DCI.AddToWorklist(Temp.Val);
1270       break;
1271     case ISD::SETNE:  // X != Y   -->  (X^Y)
1272       N0 = DAG.getNode(ISD::XOR, MVT::i1, N0, N1);
1273       break;
1274     case ISD::SETGT:  // X >s Y   -->  X == 0 & Y == 1  -->  X^1 & Y
1275     case ISD::SETULT: // X <u Y   -->  X == 0 & Y == 1  -->  X^1 & Y
1276       Temp = DAG.getNode(ISD::XOR, MVT::i1, N0, DAG.getConstant(1, MVT::i1));
1277       N0 = DAG.getNode(ISD::AND, MVT::i1, N1, Temp);
1278       if (!DCI.isCalledByLegalizer())
1279         DCI.AddToWorklist(Temp.Val);
1280       break;
1281     case ISD::SETLT:  // X <s Y   --> X == 1 & Y == 0  -->  Y^1 & X
1282     case ISD::SETUGT: // X >u Y   --> X == 1 & Y == 0  -->  Y^1 & X
1283       Temp = DAG.getNode(ISD::XOR, MVT::i1, N1, DAG.getConstant(1, MVT::i1));
1284       N0 = DAG.getNode(ISD::AND, MVT::i1, N0, Temp);
1285       if (!DCI.isCalledByLegalizer())
1286         DCI.AddToWorklist(Temp.Val);
1287       break;
1288     case ISD::SETULE: // X <=u Y  --> X == 0 | Y == 1  -->  X^1 | Y
1289     case ISD::SETGE:  // X >=s Y  --> X == 0 | Y == 1  -->  X^1 | Y
1290       Temp = DAG.getNode(ISD::XOR, MVT::i1, N0, DAG.getConstant(1, MVT::i1));
1291       N0 = DAG.getNode(ISD::OR, MVT::i1, N1, Temp);
1292       if (!DCI.isCalledByLegalizer())
1293         DCI.AddToWorklist(Temp.Val);
1294       break;
1295     case ISD::SETUGE: // X >=u Y  --> X == 1 | Y == 0  -->  Y^1 | X
1296     case ISD::SETLE:  // X <=s Y  --> X == 1 | Y == 0  -->  Y^1 | X
1297       Temp = DAG.getNode(ISD::XOR, MVT::i1, N1, DAG.getConstant(1, MVT::i1));
1298       N0 = DAG.getNode(ISD::OR, MVT::i1, N0, Temp);
1299       break;
1300     }
1301     if (VT != MVT::i1) {
1302       if (!DCI.isCalledByLegalizer())
1303         DCI.AddToWorklist(N0.Val);
1304       // FIXME: If running after legalize, we probably can't do this.
1305       N0 = DAG.getNode(ISD::ZERO_EXTEND, VT, N0);
1306     }
1307     return N0;
1308   }
1309
1310   // Could not fold it.
1311   return SDOperand();
1312 }
1313
1314 SDOperand TargetLowering::
1315 PerformDAGCombine(SDNode *N, DAGCombinerInfo &DCI) const {
1316   // Default implementation: no optimization.
1317   return SDOperand();
1318 }
1319
1320 //===----------------------------------------------------------------------===//
1321 //  Inline Assembler Implementation Methods
1322 //===----------------------------------------------------------------------===//
1323
1324 TargetLowering::ConstraintType
1325 TargetLowering::getConstraintType(const std::string &Constraint) const {
1326   // FIXME: lots more standard ones to handle.
1327   if (Constraint.size() == 1) {
1328     switch (Constraint[0]) {
1329     default: break;
1330     case 'r': return C_RegisterClass;
1331     case 'm':    // memory
1332     case 'o':    // offsetable
1333     case 'V':    // not offsetable
1334       return C_Memory;
1335     case 'i':    // Simple Integer or Relocatable Constant
1336     case 'n':    // Simple Integer
1337     case 's':    // Relocatable Constant
1338     case 'X':    // Allow ANY value.
1339     case 'I':    // Target registers.
1340     case 'J':
1341     case 'K':
1342     case 'L':
1343     case 'M':
1344     case 'N':
1345     case 'O':
1346     case 'P':
1347       return C_Other;
1348     }
1349   }
1350
1351   if (Constraint.size() > 1 && Constraint[0] == '{' &&
1352       Constraint[Constraint.size()-1] == '}')
1353     return C_Register;
1354   return C_Unknown;
1355 }
1356
1357 /// LowerAsmOperandForConstraint - Lower the specified operand into the Ops
1358 /// vector.  If it is invalid, don't add anything to Ops.
1359 void TargetLowering::LowerAsmOperandForConstraint(SDOperand Op,
1360                                                   char ConstraintLetter,
1361                                                   std::vector<SDOperand> &Ops,
1362                                                   SelectionDAG &DAG) {
1363   switch (ConstraintLetter) {
1364   default: break;
1365   case 'i':    // Simple Integer or Relocatable Constant
1366   case 'n':    // Simple Integer
1367   case 's':    // Relocatable Constant
1368   case 'X': {  // Allows any operand.
1369     // These operands are interested in values of the form (GV+C), where C may
1370     // be folded in as an offset of GV, or it may be explicitly added.  Also, it
1371     // is possible and fine if either GV or C are missing.
1372     ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op);
1373     GlobalAddressSDNode *GA = dyn_cast<GlobalAddressSDNode>(Op);
1374
1375     // If we have "(add GV, C)", pull out GV/C
1376     if (Op.getOpcode() == ISD::ADD) {
1377       C = dyn_cast<ConstantSDNode>(Op.getOperand(1));
1378       GA = dyn_cast<GlobalAddressSDNode>(Op.getOperand(0));
1379       if (C == 0 || GA == 0) {
1380         C = dyn_cast<ConstantSDNode>(Op.getOperand(0));
1381         GA = dyn_cast<GlobalAddressSDNode>(Op.getOperand(1));
1382       }
1383       if (C == 0 || GA == 0)
1384         C = 0, GA = 0;
1385     }
1386
1387     // If we find a valid operand, map to the TargetXXX version so that the
1388     // value itself doesn't get selected.
1389     if (GA) {   // Either &GV   or   &GV+C
1390       if (ConstraintLetter != 'n') {
1391         int64_t Offs = GA->getOffset();
1392         if (C) Offs += C->getValue();
1393         Ops.push_back(DAG.getTargetGlobalAddress(GA->getGlobal(),
1394                                                  Op.getValueType(), Offs));
1395         return;
1396       }
1397     }
1398     if (C) {   // just C, no GV.
1399       // Simple constants are not allowed for 's'.
1400       if (ConstraintLetter != 's') {
1401         Ops.push_back(DAG.getTargetConstant(C->getValue(), Op.getValueType()));
1402         return;
1403       }
1404     }
1405     break;
1406   }
1407   }
1408 }
1409
1410 std::vector<unsigned> TargetLowering::
1411 getRegClassForInlineAsmConstraint(const std::string &Constraint,
1412                                   MVT::ValueType VT) const {
1413   return std::vector<unsigned>();
1414 }
1415
1416
1417 std::pair<unsigned, const TargetRegisterClass*> TargetLowering::
1418 getRegForInlineAsmConstraint(const std::string &Constraint,
1419                              MVT::ValueType VT) const {
1420   if (Constraint[0] != '{')
1421     return std::pair<unsigned, const TargetRegisterClass*>(0, 0);
1422   assert(*(Constraint.end()-1) == '}' && "Not a brace enclosed constraint?");
1423
1424   // Remove the braces from around the name.
1425   std::string RegName(Constraint.begin()+1, Constraint.end()-1);
1426
1427   // Figure out which register class contains this reg.
1428   const MRegisterInfo *RI = TM.getRegisterInfo();
1429   for (MRegisterInfo::regclass_iterator RCI = RI->regclass_begin(),
1430        E = RI->regclass_end(); RCI != E; ++RCI) {
1431     const TargetRegisterClass *RC = *RCI;
1432
1433     // If none of the the value types for this register class are valid, we
1434     // can't use it.  For example, 64-bit reg classes on 32-bit targets.
1435     bool isLegal = false;
1436     for (TargetRegisterClass::vt_iterator I = RC->vt_begin(), E = RC->vt_end();
1437          I != E; ++I) {
1438       if (isTypeLegal(*I)) {
1439         isLegal = true;
1440         break;
1441       }
1442     }
1443
1444     if (!isLegal) continue;
1445
1446     for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end();
1447          I != E; ++I) {
1448       if (StringsEqualNoCase(RegName, RI->get(*I).Name))
1449         return std::make_pair(*I, RC);
1450     }
1451   }
1452
1453   return std::pair<unsigned, const TargetRegisterClass*>(0, 0);
1454 }
1455
1456 //===----------------------------------------------------------------------===//
1457 //  Loop Strength Reduction hooks
1458 //===----------------------------------------------------------------------===//
1459
1460 /// isLegalAddressingMode - Return true if the addressing mode represented
1461 /// by AM is legal for this target, for a load/store of the specified type.
1462 bool TargetLowering::isLegalAddressingMode(const AddrMode &AM,
1463                                            const Type *Ty) const {
1464   // The default implementation of this implements a conservative RISCy, r+r and
1465   // r+i addr mode.
1466
1467   // Allows a sign-extended 16-bit immediate field.
1468   if (AM.BaseOffs <= -(1LL << 16) || AM.BaseOffs >= (1LL << 16)-1)
1469     return false;
1470
1471   // No global is ever allowed as a base.
1472   if (AM.BaseGV)
1473     return false;
1474
1475   // Only support r+r,
1476   switch (AM.Scale) {
1477   case 0:  // "r+i" or just "i", depending on HasBaseReg.
1478     break;
1479   case 1:
1480     if (AM.HasBaseReg && AM.BaseOffs)  // "r+r+i" is not allowed.
1481       return false;
1482     // Otherwise we have r+r or r+i.
1483     break;
1484   case 2:
1485     if (AM.HasBaseReg || AM.BaseOffs)  // 2*r+r  or  2*r+i is not allowed.
1486       return false;
1487     // Allow 2*r as r+r.
1488     break;
1489   }
1490
1491   return true;
1492 }
1493
1494 // Magic for divide replacement
1495
1496 struct ms {
1497   int64_t m;  // magic number
1498   int64_t s;  // shift amount
1499 };
1500
1501 struct mu {
1502   uint64_t m; // magic number
1503   int64_t a;  // add indicator
1504   int64_t s;  // shift amount
1505 };
1506
1507 /// magic - calculate the magic numbers required to codegen an integer sdiv as
1508 /// a sequence of multiply and shifts.  Requires that the divisor not be 0, 1,
1509 /// or -1.
1510 static ms magic32(int32_t d) {
1511   int32_t p;
1512   uint32_t ad, anc, delta, q1, r1, q2, r2, t;
1513   const uint32_t two31 = 0x80000000U;
1514   struct ms mag;
1515
1516   ad = abs(d);
1517   t = two31 + ((uint32_t)d >> 31);
1518   anc = t - 1 - t%ad;   // absolute value of nc
1519   p = 31;               // initialize p
1520   q1 = two31/anc;       // initialize q1 = 2p/abs(nc)
1521   r1 = two31 - q1*anc;  // initialize r1 = rem(2p,abs(nc))
1522   q2 = two31/ad;        // initialize q2 = 2p/abs(d)
1523   r2 = two31 - q2*ad;   // initialize r2 = rem(2p,abs(d))
1524   do {
1525     p = p + 1;
1526     q1 = 2*q1;        // update q1 = 2p/abs(nc)
1527     r1 = 2*r1;        // update r1 = rem(2p/abs(nc))
1528     if (r1 >= anc) {  // must be unsigned comparison
1529       q1 = q1 + 1;
1530       r1 = r1 - anc;
1531     }
1532     q2 = 2*q2;        // update q2 = 2p/abs(d)
1533     r2 = 2*r2;        // update r2 = rem(2p/abs(d))
1534     if (r2 >= ad) {   // must be unsigned comparison
1535       q2 = q2 + 1;
1536       r2 = r2 - ad;
1537     }
1538     delta = ad - r2;
1539   } while (q1 < delta || (q1 == delta && r1 == 0));
1540
1541   mag.m = (int32_t)(q2 + 1); // make sure to sign extend
1542   if (d < 0) mag.m = -mag.m; // resulting magic number
1543   mag.s = p - 32;            // resulting shift
1544   return mag;
1545 }
1546
1547 /// magicu - calculate the magic numbers required to codegen an integer udiv as
1548 /// a sequence of multiply, add and shifts.  Requires that the divisor not be 0.
1549 static mu magicu32(uint32_t d) {
1550   int32_t p;
1551   uint32_t nc, delta, q1, r1, q2, r2;
1552   struct mu magu;
1553   magu.a = 0;               // initialize "add" indicator
1554   nc = - 1 - (-d)%d;
1555   p = 31;                   // initialize p
1556   q1 = 0x80000000/nc;       // initialize q1 = 2p/nc
1557   r1 = 0x80000000 - q1*nc;  // initialize r1 = rem(2p,nc)
1558   q2 = 0x7FFFFFFF/d;        // initialize q2 = (2p-1)/d
1559   r2 = 0x7FFFFFFF - q2*d;   // initialize r2 = rem((2p-1),d)
1560   do {
1561     p = p + 1;
1562     if (r1 >= nc - r1 ) {
1563       q1 = 2*q1 + 1;  // update q1
1564       r1 = 2*r1 - nc; // update r1
1565     }
1566     else {
1567       q1 = 2*q1; // update q1
1568       r1 = 2*r1; // update r1
1569     }
1570     if (r2 + 1 >= d - r2) {
1571       if (q2 >= 0x7FFFFFFF) magu.a = 1;
1572       q2 = 2*q2 + 1;     // update q2
1573       r2 = 2*r2 + 1 - d; // update r2
1574     }
1575     else {
1576       if (q2 >= 0x80000000) magu.a = 1;
1577       q2 = 2*q2;     // update q2
1578       r2 = 2*r2 + 1; // update r2
1579     }
1580     delta = d - 1 - r2;
1581   } while (p < 64 && (q1 < delta || (q1 == delta && r1 == 0)));
1582   magu.m = q2 + 1; // resulting magic number
1583   magu.s = p - 32;  // resulting shift
1584   return magu;
1585 }
1586
1587 /// magic - calculate the magic numbers required to codegen an integer sdiv as
1588 /// a sequence of multiply and shifts.  Requires that the divisor not be 0, 1,
1589 /// or -1.
1590 static ms magic64(int64_t d) {
1591   int64_t p;
1592   uint64_t ad, anc, delta, q1, r1, q2, r2, t;
1593   const uint64_t two63 = 9223372036854775808ULL; // 2^63
1594   struct ms mag;
1595
1596   ad = d >= 0 ? d : -d;
1597   t = two63 + ((uint64_t)d >> 63);
1598   anc = t - 1 - t%ad;   // absolute value of nc
1599   p = 63;               // initialize p
1600   q1 = two63/anc;       // initialize q1 = 2p/abs(nc)
1601   r1 = two63 - q1*anc;  // initialize r1 = rem(2p,abs(nc))
1602   q2 = two63/ad;        // initialize q2 = 2p/abs(d)
1603   r2 = two63 - q2*ad;   // initialize r2 = rem(2p,abs(d))
1604   do {
1605     p = p + 1;
1606     q1 = 2*q1;        // update q1 = 2p/abs(nc)
1607     r1 = 2*r1;        // update r1 = rem(2p/abs(nc))
1608     if (r1 >= anc) {  // must be unsigned comparison
1609       q1 = q1 + 1;
1610       r1 = r1 - anc;
1611     }
1612     q2 = 2*q2;        // update q2 = 2p/abs(d)
1613     r2 = 2*r2;        // update r2 = rem(2p/abs(d))
1614     if (r2 >= ad) {   // must be unsigned comparison
1615       q2 = q2 + 1;
1616       r2 = r2 - ad;
1617     }
1618     delta = ad - r2;
1619   } while (q1 < delta || (q1 == delta && r1 == 0));
1620
1621   mag.m = q2 + 1;
1622   if (d < 0) mag.m = -mag.m; // resulting magic number
1623   mag.s = p - 64;            // resulting shift
1624   return mag;
1625 }
1626
1627 /// magicu - calculate the magic numbers required to codegen an integer udiv as
1628 /// a sequence of multiply, add and shifts.  Requires that the divisor not be 0.
1629 static mu magicu64(uint64_t d)
1630 {
1631   int64_t p;
1632   uint64_t nc, delta, q1, r1, q2, r2;
1633   struct mu magu;
1634   magu.a = 0;               // initialize "add" indicator
1635   nc = - 1 - (-d)%d;
1636   p = 63;                   // initialize p
1637   q1 = 0x8000000000000000ull/nc;       // initialize q1 = 2p/nc
1638   r1 = 0x8000000000000000ull - q1*nc;  // initialize r1 = rem(2p,nc)
1639   q2 = 0x7FFFFFFFFFFFFFFFull/d;        // initialize q2 = (2p-1)/d
1640   r2 = 0x7FFFFFFFFFFFFFFFull - q2*d;   // initialize r2 = rem((2p-1),d)
1641   do {
1642     p = p + 1;
1643     if (r1 >= nc - r1 ) {
1644       q1 = 2*q1 + 1;  // update q1
1645       r1 = 2*r1 - nc; // update r1
1646     }
1647     else {
1648       q1 = 2*q1; // update q1
1649       r1 = 2*r1; // update r1
1650     }
1651     if (r2 + 1 >= d - r2) {
1652       if (q2 >= 0x7FFFFFFFFFFFFFFFull) magu.a = 1;
1653       q2 = 2*q2 + 1;     // update q2
1654       r2 = 2*r2 + 1 - d; // update r2
1655     }
1656     else {
1657       if (q2 >= 0x8000000000000000ull) magu.a = 1;
1658       q2 = 2*q2;     // update q2
1659       r2 = 2*r2 + 1; // update r2
1660     }
1661     delta = d - 1 - r2;
1662   } while (p < 128 && (q1 < delta || (q1 == delta && r1 == 0)));
1663   magu.m = q2 + 1; // resulting magic number
1664   magu.s = p - 64;  // resulting shift
1665   return magu;
1666 }
1667
1668 /// BuildSDIVSequence - Given an ISD::SDIV node expressing a divide by constant,
1669 /// return a DAG expression to select that will generate the same value by
1670 /// multiplying by a magic number.  See:
1671 /// <http://the.wall.riscom.net/books/proc/ppc/cwg/code2.html>
1672 SDOperand TargetLowering::BuildSDIV(SDNode *N, SelectionDAG &DAG,
1673                                     std::vector<SDNode*>* Created) const {
1674   MVT::ValueType VT = N->getValueType(0);
1675
1676   // Check to see if we can do this.
1677   if (!isTypeLegal(VT) || (VT != MVT::i32 && VT != MVT::i64))
1678     return SDOperand();       // BuildSDIV only operates on i32 or i64
1679   if (!isOperationLegal(ISD::MULHS, VT))
1680     return SDOperand();       // Make sure the target supports MULHS.
1681
1682   int64_t d = cast<ConstantSDNode>(N->getOperand(1))->getSignExtended();
1683   ms magics = (VT == MVT::i32) ? magic32(d) : magic64(d);
1684
1685   // Multiply the numerator (operand 0) by the magic value
1686   SDOperand Q = DAG.getNode(ISD::MULHS, VT, N->getOperand(0),
1687                             DAG.getConstant(magics.m, VT));
1688   // If d > 0 and m < 0, add the numerator
1689   if (d > 0 && magics.m < 0) {
1690     Q = DAG.getNode(ISD::ADD, VT, Q, N->getOperand(0));
1691     if (Created)
1692       Created->push_back(Q.Val);
1693   }
1694   // If d < 0 and m > 0, subtract the numerator.
1695   if (d < 0 && magics.m > 0) {
1696     Q = DAG.getNode(ISD::SUB, VT, Q, N->getOperand(0));
1697     if (Created)
1698       Created->push_back(Q.Val);
1699   }
1700   // Shift right algebraic if shift value is nonzero
1701   if (magics.s > 0) {
1702     Q = DAG.getNode(ISD::SRA, VT, Q,
1703                     DAG.getConstant(magics.s, getShiftAmountTy()));
1704     if (Created)
1705       Created->push_back(Q.Val);
1706   }
1707   // Extract the sign bit and add it to the quotient
1708   SDOperand T =
1709     DAG.getNode(ISD::SRL, VT, Q, DAG.getConstant(MVT::getSizeInBits(VT)-1,
1710                                                  getShiftAmountTy()));
1711   if (Created)
1712     Created->push_back(T.Val);
1713   return DAG.getNode(ISD::ADD, VT, Q, T);
1714 }
1715
1716 /// BuildUDIVSequence - Given an ISD::UDIV node expressing a divide by constant,
1717 /// return a DAG expression to select that will generate the same value by
1718 /// multiplying by a magic number.  See:
1719 /// <http://the.wall.riscom.net/books/proc/ppc/cwg/code2.html>
1720 SDOperand TargetLowering::BuildUDIV(SDNode *N, SelectionDAG &DAG,
1721                                     std::vector<SDNode*>* Created) const {
1722   MVT::ValueType VT = N->getValueType(0);
1723
1724   // Check to see if we can do this.
1725   if (!isTypeLegal(VT) || (VT != MVT::i32 && VT != MVT::i64))
1726     return SDOperand();       // BuildUDIV only operates on i32 or i64
1727   if (!isOperationLegal(ISD::MULHU, VT))
1728     return SDOperand();       // Make sure the target supports MULHU.
1729
1730   uint64_t d = cast<ConstantSDNode>(N->getOperand(1))->getValue();
1731   mu magics = (VT == MVT::i32) ? magicu32(d) : magicu64(d);
1732
1733   // Multiply the numerator (operand 0) by the magic value
1734   SDOperand Q = DAG.getNode(ISD::MULHU, VT, N->getOperand(0),
1735                             DAG.getConstant(magics.m, VT));
1736   if (Created)
1737     Created->push_back(Q.Val);
1738
1739   if (magics.a == 0) {
1740     return DAG.getNode(ISD::SRL, VT, Q,
1741                        DAG.getConstant(magics.s, getShiftAmountTy()));
1742   } else {
1743     SDOperand NPQ = DAG.getNode(ISD::SUB, VT, N->getOperand(0), Q);
1744     if (Created)
1745       Created->push_back(NPQ.Val);
1746     NPQ = DAG.getNode(ISD::SRL, VT, NPQ,
1747                       DAG.getConstant(1, getShiftAmountTy()));
1748     if (Created)
1749       Created->push_back(NPQ.Val);
1750     NPQ = DAG.getNode(ISD::ADD, VT, NPQ, Q);
1751     if (Created)
1752       Created->push_back(NPQ.Val);
1753     return DAG.getNode(ISD::SRL, VT, NPQ,
1754                        DAG.getConstant(magics.s-1, getShiftAmountTy()));
1755   }
1756 }