lib/CodeGen/SelectionDAG/TargetLowering.cpp

   1 //===-- TargetLowering.cpp - Implement the TargetLowering class -----------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This implements the TargetLowering class.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/Target/TargetLowering.h"
  15 #include "llvm/Target/TargetMachine.h"
  16 #include "llvm/Target/MRegisterInfo.h"
  17 #include "llvm/CodeGen/SelectionDAG.h"
  18 #include "llvm/ADT/StringExtras.h"
  19 #include "llvm/Support/MathExtras.h"
  20 using namespace llvm;
  21
  22 TargetLowering::TargetLowering(TargetMachine &tm)
  23   : TM(tm), TD(TM.getTargetData()) {
  24   assert(ISD::BUILTIN_OP_END <= 128 &&
  25          "Fixed size array in TargetLowering is not large enough!");
  26   // All operations default to being supported.
  27   memset(OpActions, 0, sizeof(OpActions));
  28
  29   IsLittleEndian = TD.isLittleEndian();
  30   ShiftAmountTy = SetCCResultTy = PointerTy = getValueType(TD.getIntPtrType());
  31   ShiftAmtHandling = Undefined;
  32   memset(RegClassForVT, 0,MVT::LAST_VALUETYPE*sizeof(TargetRegisterClass*));
  33   maxStoresPerMemset = maxStoresPerMemcpy = maxStoresPerMemmove = 8;
  34   allowUnalignedMemoryAccesses = false;
  35   UseUnderscoreSetJmpLongJmp = false;
  36   IntDivIsCheap = false;
  37   Pow2DivIsCheap = false;
  38   StackPointerRegisterToSaveRestore = 0;
  39   SchedPreferenceInfo = SchedulingForLatency;
  40 }
  41
  42 TargetLowering::~TargetLowering() {}
  43
  44 /// setValueTypeAction - Set the action for a particular value type.  This
  45 /// assumes an action has not already been set for this value type.
  46 static void SetValueTypeAction(MVT::ValueType VT,
  47                                TargetLowering::LegalizeAction Action,
  48                                TargetLowering &TLI,
  49                                MVT::ValueType *TransformToType,
  50                         TargetLowering::ValueTypeActionImpl &ValueTypeActions) {
  51   ValueTypeActions.setTypeAction(VT, Action);
  52   if (Action == TargetLowering::Promote) {
  53     MVT::ValueType PromoteTo;
  54     if (VT == MVT::f32)
  55       PromoteTo = MVT::f64;
  56     else {
  57       unsigned LargerReg = VT+1;
  58       while (!TLI.isTypeLegal((MVT::ValueType)LargerReg)) {
  59         ++LargerReg;
  60         assert(MVT::isInteger((MVT::ValueType)LargerReg) &&
  61                "Nothing to promote to??");
  62       }
  63       PromoteTo = (MVT::ValueType)LargerReg;
  64     }
  65
  66     assert(MVT::isInteger(VT) == MVT::isInteger(PromoteTo) &&
  67            MVT::isFloatingPoint(VT) == MVT::isFloatingPoint(PromoteTo) &&
  68            "Can only promote from int->int or fp->fp!");
  69     assert(VT < PromoteTo && "Must promote to a larger type!");
  70     TransformToType[VT] = PromoteTo;
  71   } else if (Action == TargetLowering::Expand) {
  72     assert((VT == MVT::Vector || MVT::isInteger(VT)) && VT > MVT::i8 &&
  73            "Cannot expand this type: target must support SOME integer reg!");
  74     // Expand to the next smaller integer type!
  75     TransformToType[VT] = (MVT::ValueType)(VT-1);
  76   }
  77 }
  78
  79
  80 /// computeRegisterProperties - Once all of the register classes are added,
  81 /// this allows us to compute derived properties we expose.
  82 void TargetLowering::computeRegisterProperties() {
  83   assert(MVT::LAST_VALUETYPE <= 32 &&
  84          "Too many value types for ValueTypeActions to hold!");
  85
  86   // Everything defaults to one.
  87   for (unsigned i = 0; i != MVT::LAST_VALUETYPE; ++i)
  88     NumElementsForVT[i] = 1;
  89
  90   // Find the largest integer register class.
  91   unsigned LargestIntReg = MVT::i128;
  92   for (; RegClassForVT[LargestIntReg] == 0; --LargestIntReg)
  93     assert(LargestIntReg != MVT::i1 && "No integer registers defined!");
  94
  95   // Every integer value type larger than this largest register takes twice as
  96   // many registers to represent as the previous ValueType.
  97   unsigned ExpandedReg = LargestIntReg; ++LargestIntReg;
  98   for (++ExpandedReg; MVT::isInteger((MVT::ValueType)ExpandedReg);++ExpandedReg)
  99     NumElementsForVT[ExpandedReg] = 2*NumElementsForVT[ExpandedReg-1];
 100
 101   // Inspect all of the ValueType's possible, deciding how to process them.
 102   for (unsigned IntReg = MVT::i1; IntReg <= MVT::i128; ++IntReg)
 103     // If we are expanding this type, expand it!
 104     if (getNumElements((MVT::ValueType)IntReg) != 1)
 105       SetValueTypeAction((MVT::ValueType)IntReg, Expand, *this, TransformToType,
 106                          ValueTypeActions);
 107     else if (!isTypeLegal((MVT::ValueType)IntReg))
 108       // Otherwise, if we don't have native support, we must promote to a
 109       // larger type.
 110       SetValueTypeAction((MVT::ValueType)IntReg, Promote, *this,
 111                          TransformToType, ValueTypeActions);
 112     else
 113       TransformToType[(MVT::ValueType)IntReg] = (MVT::ValueType)IntReg;
 114
 115   // If the target does not have native support for F32, promote it to F64.
 116   if (!isTypeLegal(MVT::f32))
 117     SetValueTypeAction(MVT::f32, Promote, *this,
 118                        TransformToType, ValueTypeActions);
 119   else
 120     TransformToType[MVT::f32] = MVT::f32;
 121
 122   // Set MVT::Vector to always be Expanded
 123   SetValueTypeAction(MVT::Vector, Expand, *this, TransformToType,
 124                      ValueTypeActions);
 125
 126   assert(isTypeLegal(MVT::f64) && "Target does not support FP?");
 127   TransformToType[MVT::f64] = MVT::f64;
 128 }
 129
 130 const char *TargetLowering::getTargetNodeName(unsigned Opcode) const {
 131   return NULL;
 132 }
 133
 134 //===----------------------------------------------------------------------===//
 135 //  Optimization Methods
 136 //===----------------------------------------------------------------------===//
 137
 138 /// DemandedBitsAreZero - Return true if 'Op & Mask' demands no bits from a bit
 139 /// set operation such as a sign extend or or/xor with constant whose only
 140 /// use is Op.  If it returns true, the old node that sets bits which are
 141 /// not demanded is returned in Old, and its replacement node is returned in
 142 /// New, such that callers of DemandedBitsAreZero may call CombineTo on them if
 143 /// desired.
 144 bool TargetLowering::DemandedBitsAreZero(const SDOperand &Op, uint64_t Mask,
 145                                          SDOperand &Old, SDOperand &New,
 146                                          SelectionDAG &DAG) const {
 147   // If the operation has more than one use, we're not interested in it.
 148   // Tracking down and checking all uses would be problematic and slow.
 149   if (!Op.Val->hasOneUse())
 150     return false;
 151
 152   switch (Op.getOpcode()) {
 153   case ISD::AND:
 154     // (X & C1) & C2 == 0   iff   C1 & C2 == 0.
 155     if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
 156       uint64_t NewVal = Mask & AndRHS->getValue();
 157       return DemandedBitsAreZero(Op.getOperand(0), NewVal, Old, New, DAG);
 158     }
 159     break;
 160   case ISD::SHL:
 161     // (ushl X, C1) & C2 == 0   iff  X & (C2 >> C1) == 0
 162     if (ConstantSDNode *ShAmt = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
 163       uint64_t NewVal = Mask >> ShAmt->getValue();
 164       return DemandedBitsAreZero(Op.getOperand(0), NewVal, Old, New, DAG);
 165     }
 166     break;
 167   case ISD::SIGN_EXTEND_INREG: {
 168     MVT::ValueType EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
 169     unsigned ExtendBits = MVT::getSizeInBits(EVT);
 170     // If we're extending from something smaller than MVT::i64 and all of the
 171     // sign extension bits are masked, return true and set New to be the
 172     // first operand, since we no longer care what the high bits are.
 173     if (ExtendBits < 64 && ((Mask & (~0ULL << ExtendBits)) == 0)) {
 174       Old = Op;
 175       New = Op.getOperand(0);
 176       return true;
 177     }
 178     break;
 179   }
 180   case ISD::SRA:
 181     if (ConstantSDNode *ShAmt = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
 182       unsigned OpBits = MVT::getSizeInBits(Op.getValueType());
 183       unsigned SH = ShAmt->getValue();
 184       if (SH && ((Mask & (~0ULL << (OpBits-SH))) == 0)) {
 185         Old = Op;
 186         New = DAG.getNode(ISD::SRL, Op.getValueType(), Op.getOperand(0),
 187                           Op.getOperand(1));
 188         return true;
 189       }
 190     }
 191     break;
 192   }
 193   return false;
 194 }
 195
 196 /// MaskedValueIsZero - Return true if 'Op & Mask' is known to be zero.  We use
 197 /// this predicate to simplify operations downstream.  Op and Mask are known to
 198 /// be the same type.
 199 bool TargetLowering::MaskedValueIsZero(const SDOperand &Op,
 200                                        uint64_t Mask) const {
 201   unsigned SrcBits;
 202   if (Mask == 0) return true;
 203
 204   // If we know the result of a setcc has the top bits zero, use this info.
 205   switch (Op.getOpcode()) {
 206   case ISD::Constant:
 207     return (cast<ConstantSDNode>(Op)->getValue() & Mask) == 0;
 208   case ISD::SETCC:
 209     return ((Mask & 1) == 0) &&
 210       getSetCCResultContents() == TargetLowering::ZeroOrOneSetCCResult;
 211   case ISD::ZEXTLOAD:
 212     SrcBits = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(3))->getVT());
 213     return (Mask & ((1ULL << SrcBits)-1)) == 0; // Returning only the zext bits.
 214   case ISD::ZERO_EXTEND:
 215     SrcBits = MVT::getSizeInBits(Op.getOperand(0).getValueType());
 216     return MaskedValueIsZero(Op.getOperand(0),Mask & (~0ULL >> (64-SrcBits)));
 217   case ISD::ANY_EXTEND:
 218     // If the mask only includes bits in the low part, recurse.
 219     SrcBits = MVT::getSizeInBits(Op.getOperand(0).getValueType());
 220     if (Mask >> SrcBits) return false;  // Use of unknown top bits.
 221     return MaskedValueIsZero(Op.getOperand(0), Mask);
 222   case ISD::AssertZext:
 223     SrcBits = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(1))->getVT());
 224     return (Mask & ((1ULL << SrcBits)-1)) == 0; // Returning only the zext bits.
 225   case ISD::AND:
 226     // If either of the operands has zero bits, the result will too.
 227     if (MaskedValueIsZero(Op.getOperand(1), Mask) ||
 228         MaskedValueIsZero(Op.getOperand(0), Mask))
 229       return true;
 230     // (X & C1) & C2 == 0   iff   C1 & C2 == 0.
 231     if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
 232       return MaskedValueIsZero(Op.getOperand(0),AndRHS->getValue() & Mask);
 233     return false;
 234   case ISD::OR:
 235   case ISD::XOR:
 236     return MaskedValueIsZero(Op.getOperand(0), Mask) &&
 237            MaskedValueIsZero(Op.getOperand(1), Mask);
 238   case ISD::SELECT:
 239     return MaskedValueIsZero(Op.getOperand(1), Mask) &&
 240            MaskedValueIsZero(Op.getOperand(2), Mask);
 241   case ISD::SELECT_CC:
 242     return MaskedValueIsZero(Op.getOperand(2), Mask) &&
 243            MaskedValueIsZero(Op.getOperand(3), Mask);
 244   case ISD::SRL:
 245     // (ushr X, C1) & C2 == 0   iff  X & (C2 << C1) == 0
 246     if (ConstantSDNode *ShAmt = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
 247       uint64_t NewVal = Mask << ShAmt->getValue();
 248       SrcBits = MVT::getSizeInBits(Op.getValueType());
 249       if (SrcBits != 64) NewVal &= (1ULL << SrcBits)-1;
 250       return MaskedValueIsZero(Op.getOperand(0), NewVal);
 251     }
 252     return false;
 253   case ISD::SHL:
 254     // (ushl X, C1) & C2 == 0   iff  X & (C2 >> C1) == 0
 255     if (ConstantSDNode *ShAmt = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
 256       uint64_t NewVal = Mask >> ShAmt->getValue();
 257       return MaskedValueIsZero(Op.getOperand(0), NewVal);
 258     }
 259     return false;
 260   case ISD::ADD:
 261     // (add X, Y) & C == 0 iff (X&C)|(Y&C) == 0 and all bits are low bits.
 262     if ((Mask&(Mask+1)) == 0) {  // All low bits
 263       if (MaskedValueIsZero(Op.getOperand(0), Mask) &&
 264           MaskedValueIsZero(Op.getOperand(1), Mask))
 265         return true;
 266     }
 267     break;
 268   case ISD::SUB:
 269     if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
 270       // We know that the top bits of C-X are clear if X contains less bits
 271       // than C (i.e. no wrap-around can happen).  For example, 20-X is
 272       // positive if we can prove that X is >= 0 and < 16.
 273       unsigned Bits = MVT::getSizeInBits(CLHS->getValueType(0));
 274       if ((CLHS->getValue() & (1 << (Bits-1))) == 0) {  // sign bit clear
 275         unsigned NLZ = CountLeadingZeros_64(CLHS->getValue()+1);
 276         uint64_t MaskV = (1ULL << (63-NLZ))-1;
 277         if (MaskedValueIsZero(Op.getOperand(1), ~MaskV)) {
 278           // High bits are clear this value is known to be >= C.
 279           unsigned NLZ2 = CountLeadingZeros_64(CLHS->getValue());
 280           if ((Mask & ((1ULL << (64-NLZ2))-1)) == 0)
 281             return true;
 282         }
 283       }
 284     }
 285     break;
 286   case ISD::CTTZ:
 287   case ISD::CTLZ:
 288   case ISD::CTPOP:
 289     // Bit counting instructions can not set the high bits of the result
 290     // register.  The max number of bits sets depends on the input.
 291     return (Mask & (MVT::getSizeInBits(Op.getValueType())*2-1)) == 0;
 292   default:
 293     // Allow the target to implement this method for its nodes.
 294     if (Op.getOpcode() >= ISD::BUILTIN_OP_END)
 295       return isMaskedValueZeroForTargetNode(Op, Mask);
 296     break;
 297   }
 298   return false;
 299 }
 300
 301 bool TargetLowering::isMaskedValueZeroForTargetNode(const SDOperand &Op,
 302                                                     uint64_t Mask) const {
 303   assert(Op.getOpcode() >= ISD::BUILTIN_OP_END &&
 304          "Should use MaskedValueIsZero if you don't know whether Op"
 305          " is a target node!");
 306   return false;
 307 }
 308
 309 //===----------------------------------------------------------------------===//
 310 //  Inline Assembler Implementation Methods
 311 //===----------------------------------------------------------------------===//
 312
 313 TargetLowering::ConstraintType
 314 TargetLowering::getConstraintType(char ConstraintLetter) const {
 315   // FIXME: lots more standard ones to handle.
 316   switch (ConstraintLetter) {
 317   default: return C_Unknown;
 318   case 'r': return C_RegisterClass;
 319   case 'i':    // Simple Integer or Relocatable Constant
 320   case 'n':    // Simple Integer
 321   case 's':    // Relocatable Constant
 322   case 'I':    // Target registers.
 323   case 'J':
 324   case 'K':
 325   case 'L':
 326   case 'M':
 327   case 'N':
 328   case 'O':
 329   case 'P':  return C_Other;
 330   }
 331 }
 332
 333 bool TargetLowering::isOperandValidForConstraint(SDOperand Op,
 334                                                  char ConstraintLetter) {
 335   switch (ConstraintLetter) {
 336   default: return false;
 337   case 'i':    // Simple Integer or Relocatable Constant
 338   case 'n':    // Simple Integer
 339   case 's':    // Relocatable Constant
 340     return true;   // FIXME: not right.
 341   }
 342 }
 343
 344
 345 std::vector<unsigned> TargetLowering::
 346 getRegForInlineAsmConstraint(const std::string &Constraint) const {
 347   // Not a physreg, must not be a register reference or something.
 348   if (Constraint[0] != '{') return std::vector<unsigned>();
 349   assert(*(Constraint.end()-1) == '}' && "Not a brace enclosed constraint?");
 350
 351   // Remove the braces from around the name.
 352   std::string RegName(Constraint.begin()+1, Constraint.end()-1);
 353
 354   // Scan to see if this constraint is a register name.
 355   const MRegisterInfo *RI = TM.getRegisterInfo();
 356   for (unsigned i = 1, e = RI->getNumRegs(); i != e; ++i) {
 357     if (const char *Name = RI->get(i).Name)
 358       if (StringsEqualNoCase(RegName, Name))
 359         return std::vector<unsigned>(1, i);
 360   }
 361
 362   // Unknown physreg.
 363   return std::vector<unsigned>();
 364 }
 365