TargetLowering.cpp revision eb8146b5ee4b9b66d6294f62a5ed556e332018ab
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" 20using namespace llvm; 21 22TargetLowering::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 42TargetLowering::~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. 46static 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. 82void 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 130const 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. 144bool 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. 199bool 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 301bool 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 313TargetLowering::ConstraintType 314TargetLowering::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 333bool 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 345std::vector<unsigned> TargetLowering:: 346getRegForInlineAsmConstraint(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 366