Expand small memmovs using inline code. Set the X86 threshold for expanding
[oota-llvm.git] / lib / CodeGen / SelectionDAG / TargetLowering.cpp
index ff5289e088291ca21fb6a3d8d4473174d2d92929..408a5b23b4fed0590634797df5eabf0d95249681 100644 (file)
@@ -17,8 +17,9 @@
 #include "llvm/Target/TargetData.h"
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Target/TargetRegisterInfo.h"
-#include "llvm/CallingConv.h"
+#include "llvm/GlobalVariable.h"
 #include "llvm/DerivedTypes.h"
+#include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/SelectionDAG.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/STLExtras.h"
@@ -90,23 +91,35 @@ static void InitLibcallNames(const char **Names) {
   Names[RTLIB::FPROUND_F64_F32] = "__truncdfsf2";
   Names[RTLIB::FPTOSINT_F32_I32] = "__fixsfsi";
   Names[RTLIB::FPTOSINT_F32_I64] = "__fixsfdi";
+  Names[RTLIB::FPTOSINT_F32_I128] = "__fixsfti";
   Names[RTLIB::FPTOSINT_F64_I32] = "__fixdfsi";
   Names[RTLIB::FPTOSINT_F64_I64] = "__fixdfdi";
+  Names[RTLIB::FPTOSINT_F64_I128] = "__fixdfti";
   Names[RTLIB::FPTOSINT_F80_I64] = "__fixxfdi";
+  Names[RTLIB::FPTOSINT_F80_I128] = "__fixxfti";
   Names[RTLIB::FPTOSINT_PPCF128_I64] = "__fixtfdi";
+  Names[RTLIB::FPTOSINT_PPCF128_I128] = "__fixtfti";
   Names[RTLIB::FPTOUINT_F32_I32] = "__fixunssfsi";
   Names[RTLIB::FPTOUINT_F32_I64] = "__fixunssfdi";
+  Names[RTLIB::FPTOUINT_F32_I128] = "__fixunssfti";
   Names[RTLIB::FPTOUINT_F64_I32] = "__fixunsdfsi";
   Names[RTLIB::FPTOUINT_F64_I64] = "__fixunsdfdi";
+  Names[RTLIB::FPTOUINT_F64_I128] = "__fixunsdfti";
   Names[RTLIB::FPTOUINT_F80_I32] = "__fixunsxfsi";
   Names[RTLIB::FPTOUINT_F80_I64] = "__fixunsxfdi";
+  Names[RTLIB::FPTOUINT_F80_I128] = "__fixunsxfti";
   Names[RTLIB::FPTOUINT_PPCF128_I64] = "__fixunstfdi";
+  Names[RTLIB::FPTOUINT_PPCF128_I128] = "__fixunstfti";
   Names[RTLIB::SINTTOFP_I32_F32] = "__floatsisf";
   Names[RTLIB::SINTTOFP_I32_F64] = "__floatsidf";
   Names[RTLIB::SINTTOFP_I64_F32] = "__floatdisf";
   Names[RTLIB::SINTTOFP_I64_F64] = "__floatdidf";
   Names[RTLIB::SINTTOFP_I64_F80] = "__floatdixf";
   Names[RTLIB::SINTTOFP_I64_PPCF128] = "__floatditf";
+  Names[RTLIB::SINTTOFP_I128_F32] = "__floattisf";
+  Names[RTLIB::SINTTOFP_I128_F64] = "__floattidf";
+  Names[RTLIB::SINTTOFP_I128_F80] = "__floattixf";
+  Names[RTLIB::SINTTOFP_I128_PPCF128] = "__floattitf";
   Names[RTLIB::UINTTOFP_I32_F32] = "__floatunsisf";
   Names[RTLIB::UINTTOFP_I32_F64] = "__floatunsidf";
   Names[RTLIB::UINTTOFP_I64_F32] = "__floatundisf";
@@ -153,7 +166,7 @@ static void InitCmpLibcallCCs(ISD::CondCode *CCs) {
 
 TargetLowering::TargetLowering(TargetMachine &tm)
   : TM(tm), TD(TM.getTargetData()) {
-  assert(ISD::BUILTIN_OP_END <= 156 &&
+  assert(ISD::BUILTIN_OP_END <= OpActionsCapacity &&
          "Fixed size array in TargetLowering is not large enough!");
   // All operations default to being supported.
   memset(OpActions, 0, sizeof(OpActions));
@@ -174,6 +187,9 @@ TargetLowering::TargetLowering(TargetMachine &tm)
     // These operations default to expand.
     setOperationAction(ISD::FGETSIGN, (MVT::ValueType)VT, Expand);
   }
+
+  // Most targets ignore the @llvm.prefetch intrinsic.
+  setOperationAction(ISD::PREFETCH, MVT::Other, Expand);
   
   // ConstantFP nodes default to expand.  Targets can either change this to 
   // Legal, in which case all fp constants are legal, or use addLegalFPImmediate
@@ -187,7 +203,7 @@ TargetLowering::TargetLowering(TargetMachine &tm)
     
   IsLittleEndian = TD->isLittleEndian();
   UsesGlobalOffsetTable = false;
-  ShiftAmountTy = SetCCResultTy = PointerTy = getValueType(TD->getIntPtrType());
+  ShiftAmountTy = PointerTy = getValueType(TD->getIntPtrType());
   ShiftAmtHandling = Undefined;
   memset(RegClassForVT, 0,MVT::LAST_VALUETYPE*sizeof(TargetRegisterClass*));
   memset(TargetDAGCombineArray, 0, array_lengthof(TargetDAGCombineArray));
@@ -219,59 +235,6 @@ TargetLowering::TargetLowering(TargetMachine &tm)
 
 TargetLowering::~TargetLowering() {}
 
-
-SDOperand TargetLowering::LowerMEMCPY(SDOperand Op, SelectionDAG &DAG) {
-  assert(getSubtarget() && "Subtarget not defined");
-  SDOperand ChainOp = Op.getOperand(0);
-  SDOperand DestOp = Op.getOperand(1);
-  SDOperand SourceOp = Op.getOperand(2);
-  SDOperand CountOp = Op.getOperand(3);
-  SDOperand AlignOp = Op.getOperand(4);
-  SDOperand AlwaysInlineOp = Op.getOperand(5);
-
-  bool AlwaysInline = (bool)cast<ConstantSDNode>(AlwaysInlineOp)->getValue();
-  unsigned Align = (unsigned)cast<ConstantSDNode>(AlignOp)->getValue();
-  if (Align == 0) Align = 1;
-
-  // If size is unknown, call memcpy.
-  ConstantSDNode *I = dyn_cast<ConstantSDNode>(CountOp);
-  if (!I) {
-    assert(!AlwaysInline && "Cannot inline copy of unknown size");
-    return LowerMEMCPYCall(ChainOp, DestOp, SourceOp, CountOp, DAG);
-  }
-
-  // If not DWORD aligned or if size is more than threshold, then call memcpy.
-  // The libc version is likely to be faster for the following cases. It can
-  // use the address value and run time information about the CPU.
-  // With glibc 2.6.1 on a core 2, coping an array of 100M longs was 30% faster
-  unsigned Size = I->getValue();
-  if (AlwaysInline ||
-      (Size <= getSubtarget()->getMaxInlineSizeThreshold() &&
-       (Align & 3) == 0))
-    return LowerMEMCPYInline(ChainOp, DestOp, SourceOp, Size, Align, DAG);
-  return LowerMEMCPYCall(ChainOp, DestOp, SourceOp, CountOp, DAG);
-}
-
-
-SDOperand TargetLowering::LowerMEMCPYCall(SDOperand Chain,
-                                          SDOperand Dest,
-                                          SDOperand Source,
-                                          SDOperand Count,
-                                          SelectionDAG &DAG) {
-  MVT::ValueType IntPtr = getPointerTy();
-  TargetLowering::ArgListTy Args;
-  TargetLowering::ArgListEntry Entry;
-  Entry.Ty = getTargetData()->getIntPtrType();
-  Entry.Node = Dest; Args.push_back(Entry);
-  Entry.Node = Source; Args.push_back(Entry);
-  Entry.Node = Count; Args.push_back(Entry);
-  std::pair<SDOperand,SDOperand> CallResult =
-      LowerCallTo(Chain, Type::VoidTy, false, false, false, CallingConv::C,
-                  false, DAG.getExternalSymbol("memcpy", IntPtr), Args, DAG);
-  return CallResult.second;
-}
-
-
 /// computeRegisterProperties - Once all of the register classes are added,
 /// this allows us to compute derived properties we expose.
 void TargetLowering::computeRegisterProperties() {
@@ -368,6 +331,13 @@ const char *TargetLowering::getTargetNodeName(unsigned Opcode) const {
   return NULL;
 }
 
+
+MVT::ValueType
+TargetLowering::getSetCCResultType(const SDOperand &) const {
+  return getValueType(TD->getIntPtrType());
+}
+
+
 /// getVectorTypeBreakdown - Vector types are broken down into some number of
 /// legal first class types.  For example, MVT::v8f32 maps to 2 MVT::v4f32
 /// with Altivec or SSE1, or 8 promoted MVT::f64 values with the X86 FP stack.
@@ -424,9 +394,10 @@ unsigned TargetLowering::getVectorTypeBreakdown(MVT::ValueType VT,
 }
 
 /// getByValTypeAlignment - Return the desired alignment for ByVal aggregate
-/// function arguments in the caller parameter area.
+/// function arguments in the caller parameter area.  This is the actual
+/// alignment, not its logarithm.
 unsigned TargetLowering::getByValTypeAlignment(const Type *Ty) const {
-  return Log2_32(TD->getCallFrameTypeAlignment(Ty));
+  return TD->getCallFrameTypeAlignment(Ty);
 }
 
 SDOperand TargetLowering::getPICJumpTableRelocBase(SDOperand Table,
@@ -634,10 +605,25 @@ bool TargetLowering::SimplifyDemandedBits(SDOperand Op,
     }
     
     // If the RHS is a constant, see if we can simplify it.
-    // FIXME: for XOR, we prefer to force bits to 1 if they will make a -1.
-    if (TLO.ShrinkDemandedConstant(Op, NewMask))
-      return true;
-    
+    // for XOR, we prefer to force bits to 1 if they will make a -1.
+    // if we can't force bits, try to shrink constant
+    if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
+      APInt Expanded = C->getAPIntValue() | (~NewMask);
+      // if we can expand it to have all bits set, do it
+      if (Expanded.isAllOnesValue()) {
+        if (Expanded != C->getAPIntValue()) {
+          MVT::ValueType VT = Op.getValueType();
+          SDOperand New = TLO.DAG.getNode(Op.getOpcode(), VT, Op.getOperand(0),
+                                          TLO.DAG.getConstant(Expanded, VT));
+          return TLO.CombineTo(Op, New);
+        }
+        // if it already has all the bits set, nothing to change
+        // but don't shrink either!
+      } else if (TLO.ShrinkDemandedConstant(Op, NewMask)) {
+        return true;
+      }
+    }
+
     KnownZero = KnownZeroOut;
     KnownOne  = KnownOneOut;
     break;
@@ -869,7 +855,7 @@ bool TargetLowering::SimplifyDemandedBits(SDOperand Op,
     MVT::ValueType InVT = Op.getOperand(0).getValueType();
     unsigned InBits = MVT::getSizeInBits(InVT);
     APInt InMask    = APInt::getLowBitsSet(BitWidth, InBits);
-    APInt InSignBit = APInt::getLowBitsSet(BitWidth, InBits);
+    APInt InSignBit = APInt::getBitsSet(BitWidth, InBits - 1, InBits);
     APInt NewBits   = ~InMask & NewMask;
     
     // If none of the top bits are demanded, convert this into an any_extend.
@@ -994,17 +980,7 @@ bool TargetLowering::SimplifyDemandedBits(SDOperand Op,
     }
 #endif
     break;
-  case ISD::ADD:
-  case ISD::SUB:
-  case ISD::INTRINSIC_WO_CHAIN:
-  case ISD::INTRINSIC_W_CHAIN:
-  case ISD::INTRINSIC_VOID:
-  case ISD::CTTZ:
-  case ISD::CTLZ:
-  case ISD::CTPOP:
-  case ISD::LOAD:
-  case ISD::SETCC:
-  case ISD::FGETSIGN:
+  default:
     // Just use ComputeMaskedBits to compute output bits.
     TLO.DAG.ComputeMaskedBits(Op, NewMask, KnownZero, KnownOne, Depth);
     break;
@@ -1069,7 +1045,7 @@ TargetLowering::SimplifySetCC(MVT::ValueType VT, SDOperand N0, SDOperand N1,
   }
 
   if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val)) {
-    uint64_t C1 = N1C->getValue();
+    const APInt &C1 = N1C->getAPIntValue();
     if (isa<ConstantSDNode>(N0.Val)) {
       return DAG.FoldSetCC(VT, N0, N1, Cond);
     } else {
@@ -1103,8 +1079,8 @@ TargetLowering::SimplifySetCC(MVT::ValueType VT, SDOperand N0, SDOperand N1,
 
         // If the comparison constant has bits in the upper part, the
         // zero-extended value could never match.
-        if (C1 & (~0ULL << InSize)) {
-          unsigned VSize = MVT::getSizeInBits(N0.getValueType());
+        if (C1.intersects(APInt::getHighBitsSet(C1.getBitWidth(),
+                                                C1.getBitWidth() - InSize))) {
           switch (Cond) {
           case ISD::SETUGT:
           case ISD::SETUGE:
@@ -1115,11 +1091,11 @@ TargetLowering::SimplifySetCC(MVT::ValueType VT, SDOperand N0, SDOperand N1,
           case ISD::SETGT:
           case ISD::SETGE:
             // True if the sign bit of C1 is set.
-            return DAG.getConstant((C1 & (1ULL << (VSize-1))) != 0, VT);
+            return DAG.getConstant(C1.isNegative(), VT);
           case ISD::SETLT:
           case ISD::SETLE:
             // True if the sign bit of C1 isn't set.
-            return DAG.getConstant((C1 & (1ULL << (VSize-1))) == 0, VT);
+            return DAG.getConstant(C1.isNonNegative(), VT);
           default:
             break;
           }
@@ -1134,7 +1110,8 @@ TargetLowering::SimplifySetCC(MVT::ValueType VT, SDOperand N0, SDOperand N1,
         case ISD::SETULT:
         case ISD::SETULE:
           return DAG.getSetCC(VT, N0.getOperand(0),
-                          DAG.getConstant(C1, N0.getOperand(0).getValueType()),
+                          DAG.getConstant(APInt(C1).trunc(InSize),
+                                          N0.getOperand(0).getValueType()),
                           Cond);
         default:
           break;   // todo, be more careful with signed comparisons
@@ -1149,8 +1126,8 @@ TargetLowering::SimplifySetCC(MVT::ValueType VT, SDOperand N0, SDOperand N1,
         // If the extended part has any inconsistent bits, it cannot ever
         // compare equal.  In other words, they have to be all ones or all
         // zeros.
-        uint64_t ExtBits =
-          (~0ULL >> (64-ExtSrcTyBits)) & (~0ULL << (ExtDstTyBits-1));
+        APInt ExtBits =
+          APInt::getHighBitsSet(ExtDstTyBits, ExtDstTyBits - ExtSrcTyBits);
         if ((C1 & ExtBits) != 0 && (C1 & ExtBits) != ExtBits)
           return DAG.getConstant(Cond == ISD::SETNE, VT);
         
@@ -1159,7 +1136,7 @@ TargetLowering::SimplifySetCC(MVT::ValueType VT, SDOperand N0, SDOperand N1,
         if (Op0Ty == ExtSrcTy) {
           ZextOp = N0.getOperand(0);
         } else {
-          int64_t Imm = ~0ULL >> (64-ExtSrcTyBits);
+          APInt Imm = APInt::getLowBitsSet(ExtDstTyBits, ExtSrcTyBits);
           ZextOp = DAG.getNode(ISD::AND, Op0Ty, N0.getOperand(0),
                                DAG.getConstant(Imm, Op0Ty));
         }
@@ -1167,10 +1144,12 @@ TargetLowering::SimplifySetCC(MVT::ValueType VT, SDOperand N0, SDOperand N1,
           DCI.AddToWorklist(ZextOp.Val);
         // Otherwise, make this a use of a zext.
         return DAG.getSetCC(VT, ZextOp, 
-                            DAG.getConstant(C1 & (~0ULL>>(64-ExtSrcTyBits)), 
+                            DAG.getConstant(C1 & APInt::getLowBitsSet(
+                                                               ExtDstTyBits,
+                                                               ExtSrcTyBits), 
                                             ExtDstTy),
                             Cond);
-      } else if ((N1C->getValue() == 0 || N1C->getValue() == 1) &&
+      } else if ((N1C->isNullValue() || N1C->getAPIntValue() == 1) &&
                  (Cond == ISD::SETEQ || Cond == ISD::SETNE)) {
         
         // SETCC (SETCC), [0|1], [EQ|NE]  -> SETCC
@@ -1191,7 +1170,7 @@ TargetLowering::SimplifySetCC(MVT::ValueType VT, SDOperand N0, SDOperand N1,
               N0.getOperand(0).getOpcode() == ISD::XOR &&
               N0.getOperand(1) == N0.getOperand(0).getOperand(1))) &&
             isa<ConstantSDNode>(N0.getOperand(1)) &&
-            cast<ConstantSDNode>(N0.getOperand(1))->getValue() == 1) {
+            cast<ConstantSDNode>(N0.getOperand(1))->getAPIntValue() == 1) {
           // If this is (X^1) == 0/1, swap the RHS and eliminate the xor.  We
           // can only do this if the top bits are known zero.
           unsigned BitWidth = N0.getValueSizeInBits();
@@ -1216,31 +1195,28 @@ TargetLowering::SimplifySetCC(MVT::ValueType VT, SDOperand N0, SDOperand N1,
         }
       }
       
-      uint64_t MinVal, MaxVal;
+      APInt MinVal, MaxVal;
       unsigned OperandBitSize = MVT::getSizeInBits(N1C->getValueType(0));
       if (ISD::isSignedIntSetCC(Cond)) {
-        MinVal = 1ULL << (OperandBitSize-1);
-        if (OperandBitSize != 1)   // Avoid X >> 64, which is undefined.
-          MaxVal = ~0ULL >> (65-OperandBitSize);
-        else
-          MaxVal = 0;
+        MinVal = APInt::getSignedMinValue(OperandBitSize);
+        MaxVal = APInt::getSignedMaxValue(OperandBitSize);
       } else {
-        MinVal = 0;
-        MaxVal = ~0ULL >> (64-OperandBitSize);
+        MinVal = APInt::getMinValue(OperandBitSize);
+        MaxVal = APInt::getMaxValue(OperandBitSize);
       }
 
       // Canonicalize GE/LE comparisons to use GT/LT comparisons.
       if (Cond == ISD::SETGE || Cond == ISD::SETUGE) {
         if (C1 == MinVal) return DAG.getConstant(1, VT);   // X >= MIN --> true
-        --C1;                                          // X >= C0 --> X > (C0-1)
-        return DAG.getSetCC(VT, N0, DAG.getConstant(C1, N1.getValueType()),
+        // X >= C0 --> X > (C0-1)
+        return DAG.getSetCC(VT, N0, DAG.getConstant(C1-1, N1.getValueType()),
                         (Cond == ISD::SETGE) ? ISD::SETGT : ISD::SETUGT);
       }
 
       if (Cond == ISD::SETLE || Cond == ISD::SETULE) {
         if (C1 == MaxVal) return DAG.getConstant(1, VT);   // X <= MAX --> true
-        ++C1;                                          // X <= C0 --> X < (C0+1)
-        return DAG.getSetCC(VT, N0, DAG.getConstant(C1, N1.getValueType()),
+        // X <= C0 --> X < (C0+1)
+        return DAG.getSetCC(VT, N0, DAG.getConstant(C1+1, N1.getValueType()),
                         (Cond == ISD::SETLE) ? ISD::SETLT : ISD::SETULT);
       }
 
@@ -1295,9 +1271,9 @@ TargetLowering::SimplifySetCC(MVT::ValueType VT, SDOperand N0, SDOperand N1,
           } else if (Cond == ISD::SETEQ && C1 == AndRHS->getValue()) {
             // (X & 8) == 8  -->  (X & 8) >> 3
             // Perform the xform if C1 is a single bit.
-            if (isPowerOf2_64(C1)) {
+            if (C1.isPowerOf2()) {
               return DAG.getNode(ISD::SRL, VT, N0,
-                          DAG.getConstant(Log2_64(C1), getShiftAmountTy()));
+                          DAG.getConstant(C1.logBase2(), getShiftAmountTy()));
             }
           }
         }
@@ -1503,6 +1479,73 @@ TargetLowering::SimplifySetCC(MVT::ValueType VT, SDOperand N0, SDOperand N1,
   return SDOperand();
 }
 
+/// isGAPlusOffset - Returns true (and the GlobalValue and the offset) if the
+/// node is a GlobalAddress + offset.
+bool TargetLowering::isGAPlusOffset(SDNode *N, GlobalValue* &GA,
+                                    int64_t &Offset) const {
+  if (isa<GlobalAddressSDNode>(N)) {
+    GA = cast<GlobalAddressSDNode>(N)->getGlobal();
+    return true;
+  }
+
+  if (N->getOpcode() == ISD::ADD) {
+    SDOperand N1 = N->getOperand(0);
+    SDOperand N2 = N->getOperand(1);
+    if (isGAPlusOffset(N1.Val, GA, Offset)) {
+      ConstantSDNode *V = dyn_cast<ConstantSDNode>(N2);
+      if (V) {
+        Offset += V->getSignExtended();
+        return true;
+      }
+    } else if (isGAPlusOffset(N2.Val, GA, Offset)) {
+      ConstantSDNode *V = dyn_cast<ConstantSDNode>(N1);
+      if (V) {
+        Offset += V->getSignExtended();
+        return true;
+      }
+    }
+  }
+  return false;
+}
+
+
+/// isConsecutiveLoad - Return true if LD (which must be a LoadSDNode) is
+/// loading 'Bytes' bytes from a location that is 'Dist' units away from the
+/// location that the 'Base' load is loading from.
+bool TargetLowering::isConsecutiveLoad(SDNode *LD, SDNode *Base,
+                                       unsigned Bytes, int Dist,
+                                       const MachineFrameInfo *MFI) const {
+  if (LD->getOperand(0).Val != Base->getOperand(0).Val)
+    return false;
+  MVT::ValueType VT = LD->getValueType(0);
+  if (MVT::getSizeInBits(VT) / 8 != Bytes)
+    return false;
+
+  SDOperand Loc = LD->getOperand(1);
+  SDOperand BaseLoc = Base->getOperand(1);
+  if (Loc.getOpcode() == ISD::FrameIndex) {
+    if (BaseLoc.getOpcode() != ISD::FrameIndex)
+      return false;
+    int FI  = cast<FrameIndexSDNode>(Loc)->getIndex();
+    int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
+    int FS  = MFI->getObjectSize(FI);
+    int BFS = MFI->getObjectSize(BFI);
+    if (FS != BFS || FS != (int)Bytes) return false;
+    return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
+  }
+
+  GlobalValue *GV1 = NULL;
+  GlobalValue *GV2 = NULL;
+  int64_t Offset1 = 0;
+  int64_t Offset2 = 0;
+  bool isGA1 = isGAPlusOffset(Loc.Val, GV1, Offset1);
+  bool isGA2 = isGAPlusOffset(BaseLoc.Val, GV2, Offset2);
+  if (isGA1 && isGA2 && GV1 == GV2)
+    return Offset1 == (Offset2 + Dist*Bytes);
+  return false;
+}
+
+
 SDOperand TargetLowering::
 PerformDAGCombine(SDNode *N, DAGCombinerInfo &DCI) const {
   // Default implementation: no optimization.
@@ -1513,6 +1556,7 @@ PerformDAGCombine(SDNode *N, DAGCombinerInfo &DCI) const {
 //  Inline Assembler Implementation Methods
 //===----------------------------------------------------------------------===//
 
+
 TargetLowering::ConstraintType
 TargetLowering::getConstraintType(const std::string &Constraint) const {
   // FIXME: lots more standard ones to handle.
@@ -1549,14 +1593,12 @@ TargetLowering::getConstraintType(const std::string &Constraint) const {
 /// LowerXConstraint - try to replace an X constraint, which matches anything,
 /// with another that has more specific requirements based on the type of the
 /// corresponding operand.
-void TargetLowering::lowerXConstraint(MVT::ValueType ConstraintVT, 
-                                      std::string& s) const {
+const char *TargetLowering::LowerXConstraint(MVT::ValueType ConstraintVT) const{
   if (MVT::isInteger(ConstraintVT))
-    s = "r";
-  else if (MVT::isFloatingPoint(ConstraintVT))
-    s = "f";      // works for many targets
-  else 
-    s = "";
+    return "r";
+  if (MVT::isFloatingPoint(ConstraintVT))
+    return "f";      // works for many targets
+  return 0;
 }
 
 /// LowerAsmOperandForConstraint - Lower the specified operand into the Ops
@@ -1564,7 +1606,7 @@ void TargetLowering::lowerXConstraint(MVT::ValueType ConstraintVT,
 void TargetLowering::LowerAsmOperandForConstraint(SDOperand Op,
                                                   char ConstraintLetter,
                                                   std::vector<SDOperand> &Ops,
-                                                  SelectionDAG &DAG) {
+                                                  SelectionDAG &DAG) const {
   switch (ConstraintLetter) {
   default: break;
   case 'X':     // Allows any operand; labels (basic block) use this.
@@ -1663,6 +1705,122 @@ getRegForInlineAsmConstraint(const std::string &Constraint,
   return std::pair<unsigned, const TargetRegisterClass*>(0, 0);
 }
 
+//===----------------------------------------------------------------------===//
+// Constraint Selection.
+
+/// getConstraintGenerality - Return an integer indicating how general CT
+/// is.
+static unsigned getConstraintGenerality(TargetLowering::ConstraintType CT) {
+  switch (CT) {
+  default: assert(0 && "Unknown constraint type!");
+  case TargetLowering::C_Other:
+  case TargetLowering::C_Unknown:
+    return 0;
+  case TargetLowering::C_Register:
+    return 1;
+  case TargetLowering::C_RegisterClass:
+    return 2;
+  case TargetLowering::C_Memory:
+    return 3;
+  }
+}
+
+/// ChooseConstraint - If there are multiple different constraints that we
+/// could pick for this operand (e.g. "imr") try to pick the 'best' one.
+/// This is somewhat tricky: constraints fall into four classes:
+///    Other         -> immediates and magic values
+///    Register      -> one specific register
+///    RegisterClass -> a group of regs
+///    Memory        -> memory
+/// Ideally, we would pick the most specific constraint possible: if we have
+/// something that fits into a register, we would pick it.  The problem here
+/// is that if we have something that could either be in a register or in
+/// memory that use of the register could cause selection of *other*
+/// operands to fail: they might only succeed if we pick memory.  Because of
+/// this the heuristic we use is:
+///
+///  1) If there is an 'other' constraint, and if the operand is valid for
+///     that constraint, use it.  This makes us take advantage of 'i'
+///     constraints when available.
+///  2) Otherwise, pick the most general constraint present.  This prefers
+///     'm' over 'r', for example.
+///
+static void ChooseConstraint(TargetLowering::AsmOperandInfo &OpInfo,
+                             const TargetLowering &TLI,
+                             SDOperand Op, SelectionDAG *DAG) {
+  assert(OpInfo.Codes.size() > 1 && "Doesn't have multiple constraint options");
+  unsigned BestIdx = 0;
+  TargetLowering::ConstraintType BestType = TargetLowering::C_Unknown;
+  int BestGenerality = -1;
+  
+  // Loop over the options, keeping track of the most general one.
+  for (unsigned i = 0, e = OpInfo.Codes.size(); i != e; ++i) {
+    TargetLowering::ConstraintType CType =
+      TLI.getConstraintType(OpInfo.Codes[i]);
+    
+    // If this is an 'other' constraint, see if the operand is valid for it.
+    // For example, on X86 we might have an 'rI' constraint.  If the operand
+    // is an integer in the range [0..31] we want to use I (saving a load
+    // of a register), otherwise we must use 'r'.
+    if (CType == TargetLowering::C_Other && Op.Val) {
+      assert(OpInfo.Codes[i].size() == 1 &&
+             "Unhandled multi-letter 'other' constraint");
+      std::vector<SDOperand> ResultOps;
+      TLI.LowerAsmOperandForConstraint(Op, OpInfo.Codes[i][0],
+                                       ResultOps, *DAG);
+      if (!ResultOps.empty()) {
+        BestType = CType;
+        BestIdx = i;
+        break;
+      }
+    }
+    
+    // This constraint letter is more general than the previous one, use it.
+    int Generality = getConstraintGenerality(CType);
+    if (Generality > BestGenerality) {
+      BestType = CType;
+      BestIdx = i;
+      BestGenerality = Generality;
+    }
+  }
+  
+  OpInfo.ConstraintCode = OpInfo.Codes[BestIdx];
+  OpInfo.ConstraintType = BestType;
+}
+
+/// ComputeConstraintToUse - Determines the constraint code and constraint
+/// type to use for the specific AsmOperandInfo, setting
+/// OpInfo.ConstraintCode and OpInfo.ConstraintType.
+void TargetLowering::ComputeConstraintToUse(AsmOperandInfo &OpInfo,
+                                            SDOperand Op, 
+                                            SelectionDAG *DAG) const {
+  assert(!OpInfo.Codes.empty() && "Must have at least one constraint");
+  
+  // Single-letter constraints ('r') are very common.
+  if (OpInfo.Codes.size() == 1) {
+    OpInfo.ConstraintCode = OpInfo.Codes[0];
+    OpInfo.ConstraintType = getConstraintType(OpInfo.ConstraintCode);
+  } else {
+    ChooseConstraint(OpInfo, *this, Op, DAG);
+  }
+  
+  // 'X' matches anything.
+  if (OpInfo.ConstraintCode == "X" && OpInfo.CallOperandVal) {
+    // Labels and constants are handled elsewhere ('X' is the only thing
+    // that matches labels).
+    if (isa<BasicBlock>(OpInfo.CallOperandVal) ||
+        isa<ConstantInt>(OpInfo.CallOperandVal))
+      return;
+    
+    // Otherwise, try to resolve it to something we know about by looking at
+    // the actual operand type.
+    if (const char *Repl = LowerXConstraint(OpInfo.ConstraintVT)) {
+      OpInfo.ConstraintCode = Repl;
+      OpInfo.ConstraintType = getConstraintType(OpInfo.ConstraintCode);
+    }
+  }
+}
+
 //===----------------------------------------------------------------------===//
 //  Loop Strength Reduction hooks
 //===----------------------------------------------------------------------===//