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