1 //===-- TargetLowering.cpp - Implement the TargetLowering class -----------===//
3 // The LLVM Compiler Infrastructure
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.
8 //===----------------------------------------------------------------------===//
10 // This implements the TargetLowering class.
12 //===----------------------------------------------------------------------===//
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"
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));
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;
42 TargetLowering::~TargetLowering() {}
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,
49 MVT::ValueType *TransformToType,
50 TargetLowering::ValueTypeActionImpl &ValueTypeActions) {
51 ValueTypeActions.setTypeAction(VT, Action);
52 if (Action == TargetLowering::Promote) {
53 MVT::ValueType PromoteTo;
57 unsigned LargerReg = VT+1;
58 while (!TLI.isTypeLegal((MVT::ValueType)LargerReg)) {
60 assert(MVT::isInteger((MVT::ValueType)LargerReg) &&
61 "Nothing to promote to??");
63 PromoteTo = (MVT::ValueType)LargerReg;
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);
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!");
86 // Everything defaults to one.
87 for (unsigned i = 0; i != MVT::LAST_VALUETYPE; ++i)
88 NumElementsForVT[i] = 1;
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!");
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];
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,
107 else if (!isTypeLegal((MVT::ValueType)IntReg))
108 // Otherwise, if we don't have native support, we must promote to a
110 SetValueTypeAction((MVT::ValueType)IntReg, Promote, *this,
111 TransformToType, ValueTypeActions);
113 TransformToType[(MVT::ValueType)IntReg] = (MVT::ValueType)IntReg;
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);
120 TransformToType[MVT::f32] = MVT::f32;
122 // Set MVT::Vector to always be Expanded
123 SetValueTypeAction(MVT::Vector, Expand, *this, TransformToType,
126 assert(isTypeLegal(MVT::f64) && "Target does not support FP?");
127 TransformToType[MVT::f64] = MVT::f64;
130 const char *TargetLowering::getTargetNodeName(unsigned Opcode) const {
134 //===----------------------------------------------------------------------===//
135 // Optimization Methods
136 //===----------------------------------------------------------------------===//
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
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())
152 switch (Op.getOpcode()) {
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);
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);
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)) {
175 New = Op.getOperand(0);
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)) {
186 New = DAG.getNode(ISD::SRL, Op.getValueType(), Op.getOperand(0),
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 {
202 if (Mask == 0) return true;
204 // If we know the result of a setcc has the top bits zero, use this info.
205 switch (Op.getOpcode()) {
207 return (cast<ConstantSDNode>(Op)->getValue() & Mask) == 0;
209 return ((Mask & 1) == 0) &&
210 getSetCCResultContents() == TargetLowering::ZeroOrOneSetCCResult;
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.
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))
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);
236 return MaskedValueIsZero(Op.getOperand(0), Mask) &&
237 MaskedValueIsZero(Op.getOperand(1), Mask);
239 return MaskedValueIsZero(Op.getOperand(1), Mask) &&
240 MaskedValueIsZero(Op.getOperand(2), Mask);
242 return MaskedValueIsZero(Op.getOperand(2), Mask) &&
243 MaskedValueIsZero(Op.getOperand(3), Mask);
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);
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);
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))
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)
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;
293 // Allow the target to implement this method for its nodes.
294 if (Op.getOpcode() >= ISD::BUILTIN_OP_END)
295 return isMaskedValueZeroForTargetNode(Op, Mask);
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!");
309 //===----------------------------------------------------------------------===//
310 // Inline Assembler Implementation Methods
311 //===----------------------------------------------------------------------===//
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.
329 case 'P': return C_Other;
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.
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?");
351 // Remove the braces from around the name.
352 std::string RegName(Constraint.begin()+1, Constraint.end()-1);
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);
363 return std::vector<unsigned>();