TargetLowering.cpp revision c6fd6cd65c88ef1f11da43c11be0152cb69013a7
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 136/// MaskedValueIsZero - Return true if 'Op & Mask' is known to be zero. We use 137/// this predicate to simplify operations downstream. Op and Mask are known to 138/// be the same type. 139bool TargetLowering::MaskedValueIsZero(const SDOperand &Op, 140 uint64_t Mask) const { 141 unsigned SrcBits; 142 if (Mask == 0) return true; 143 144 // If we know the result of a setcc has the top bits zero, use this info. 145 switch (Op.getOpcode()) { 146 case ISD::Constant: 147 return (cast<ConstantSDNode>(Op)->getValue() & Mask) == 0; 148 case ISD::SETCC: 149 return ((Mask & 1) == 0) && 150 getSetCCResultContents() == TargetLowering::ZeroOrOneSetCCResult; 151 case ISD::ZEXTLOAD: 152 SrcBits = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(3))->getVT()); 153 return (Mask & ((1ULL << SrcBits)-1)) == 0; // Returning only the zext bits. 154 case ISD::ZERO_EXTEND: 155 SrcBits = MVT::getSizeInBits(Op.getOperand(0).getValueType()); 156 return MaskedValueIsZero(Op.getOperand(0),Mask & (~0ULL >> (64-SrcBits))); 157 case ISD::AssertZext: 158 SrcBits = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(1))->getVT()); 159 return (Mask & ((1ULL << SrcBits)-1)) == 0; // Returning only the zext bits. 160 case ISD::AND: 161 // If either of the operands has zero bits, the result will too. 162 if (MaskedValueIsZero(Op.getOperand(1), Mask) || 163 MaskedValueIsZero(Op.getOperand(0), Mask)) 164 return true; 165 // (X & C1) & C2 == 0 iff C1 & C2 == 0. 166 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1))) 167 return MaskedValueIsZero(Op.getOperand(0),AndRHS->getValue() & Mask); 168 return false; 169 case ISD::OR: 170 case ISD::XOR: 171 return MaskedValueIsZero(Op.getOperand(0), Mask) && 172 MaskedValueIsZero(Op.getOperand(1), Mask); 173 case ISD::SELECT: 174 return MaskedValueIsZero(Op.getOperand(1), Mask) && 175 MaskedValueIsZero(Op.getOperand(2), Mask); 176 case ISD::SELECT_CC: 177 return MaskedValueIsZero(Op.getOperand(2), Mask) && 178 MaskedValueIsZero(Op.getOperand(3), Mask); 179 case ISD::SRL: 180 // (ushr X, C1) & C2 == 0 iff X & (C2 << C1) == 0 181 if (ConstantSDNode *ShAmt = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 182 uint64_t NewVal = Mask << ShAmt->getValue(); 183 SrcBits = MVT::getSizeInBits(Op.getValueType()); 184 if (SrcBits != 64) NewVal &= (1ULL << SrcBits)-1; 185 return MaskedValueIsZero(Op.getOperand(0), NewVal); 186 } 187 return false; 188 case ISD::SHL: 189 // (ushl X, C1) & C2 == 0 iff X & (C2 >> C1) == 0 190 if (ConstantSDNode *ShAmt = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 191 uint64_t NewVal = Mask >> ShAmt->getValue(); 192 return MaskedValueIsZero(Op.getOperand(0), NewVal); 193 } 194 return false; 195 case ISD::ADD: 196 // (add X, Y) & C == 0 iff (X&C)|(Y&C) == 0 and all bits are low bits. 197 if ((Mask&(Mask+1)) == 0) { // All low bits 198 if (MaskedValueIsZero(Op.getOperand(0), Mask) && 199 MaskedValueIsZero(Op.getOperand(1), Mask)) 200 return true; 201 } 202 break; 203 case ISD::SUB: 204 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) { 205 // We know that the top bits of C-X are clear if X contains less bits 206 // than C (i.e. no wrap-around can happen). For example, 20-X is 207 // positive if we can prove that X is >= 0 and < 16. 208 unsigned Bits = MVT::getSizeInBits(CLHS->getValueType(0)); 209 if ((CLHS->getValue() & (1 << (Bits-1))) == 0) { // sign bit clear 210 unsigned NLZ = CountLeadingZeros_64(CLHS->getValue()+1); 211 uint64_t MaskV = (1ULL << (63-NLZ))-1; 212 if (MaskedValueIsZero(Op.getOperand(1), ~MaskV)) { 213 // High bits are clear this value is known to be >= C. 214 unsigned NLZ2 = CountLeadingZeros_64(CLHS->getValue()); 215 if ((Mask & ((1ULL << (64-NLZ2))-1)) == 0) 216 return true; 217 } 218 } 219 } 220 break; 221 case ISD::CTTZ: 222 case ISD::CTLZ: 223 case ISD::CTPOP: 224 // Bit counting instructions can not set the high bits of the result 225 // register. The max number of bits sets depends on the input. 226 return (Mask & (MVT::getSizeInBits(Op.getValueType())*2-1)) == 0; 227 default: 228 // Allow the target to implement this method for its nodes. 229 if (Op.getOpcode() >= ISD::BUILTIN_OP_END) 230 return isMaskedValueZeroForTargetNode(Op, Mask); 231 break; 232 } 233 return false; 234} 235 236bool TargetLowering::isMaskedValueZeroForTargetNode(const SDOperand &Op, 237 uint64_t Mask) const { 238 assert(Op.getOpcode() >= ISD::BUILTIN_OP_END && 239 "Should use MaskedValueIsZero if you don't know whether Op" 240 " is a target node!"); 241 return false; 242} 243 244std::vector<unsigned> TargetLowering:: 245getRegForInlineAsmConstraint(const std::string &Constraint) const { 246 // Scan to see if this constraint is a register name. 247 const MRegisterInfo *RI = TM.getRegisterInfo(); 248 for (unsigned i = 1, e = RI->getNumRegs(); i != e; ++i) { 249 if (const char *Name = RI->get(i).Name) 250 if (StringsEqualNoCase(Constraint, Name)) 251 return std::vector<unsigned>(1, i); 252 } 253 254 // Not a physreg, must not be a register reference or something. 255 return std::vector<unsigned>(); 256} 257 258