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/TargetData.h"
16 #include "llvm/Target/TargetMachine.h"
17 #include "llvm/Target/MRegisterInfo.h"
18 #include "llvm/DerivedTypes.h"
19 #include "llvm/CodeGen/SelectionDAG.h"
20 #include "llvm/ADT/StringExtras.h"
21 #include "llvm/Support/MathExtras.h"
24 TargetLowering::TargetLowering(TargetMachine &tm)
25 : TM(tm), TD(TM.getTargetData()) {
26 assert(ISD::BUILTIN_OP_END <= 156 &&
27 "Fixed size array in TargetLowering is not large enough!");
28 // All operations default to being supported.
29 memset(OpActions, 0, sizeof(OpActions));
31 IsLittleEndian = TD->isLittleEndian();
32 ShiftAmountTy = SetCCResultTy = PointerTy = getValueType(TD->getIntPtrType());
33 ShiftAmtHandling = Undefined;
34 memset(RegClassForVT, 0,MVT::LAST_VALUETYPE*sizeof(TargetRegisterClass*));
35 memset(TargetDAGCombineArray, 0,
36 sizeof(TargetDAGCombineArray)/sizeof(TargetDAGCombineArray[0]));
37 maxStoresPerMemset = maxStoresPerMemcpy = maxStoresPerMemmove = 8;
38 allowUnalignedMemoryAccesses = false;
39 UseUnderscoreSetJmpLongJmp = false;
40 IntDivIsCheap = false;
41 Pow2DivIsCheap = false;
42 StackPointerRegisterToSaveRestore = 0;
43 SchedPreferenceInfo = SchedulingForLatency;
46 TargetLowering::~TargetLowering() {}
48 /// setValueTypeAction - Set the action for a particular value type. This
49 /// assumes an action has not already been set for this value type.
50 static void SetValueTypeAction(MVT::ValueType VT,
51 TargetLowering::LegalizeAction Action,
53 MVT::ValueType *TransformToType,
54 TargetLowering::ValueTypeActionImpl &ValueTypeActions) {
55 ValueTypeActions.setTypeAction(VT, Action);
56 if (Action == TargetLowering::Promote) {
57 MVT::ValueType PromoteTo;
61 unsigned LargerReg = VT+1;
62 while (!TLI.isTypeLegal((MVT::ValueType)LargerReg)) {
64 assert(MVT::isInteger((MVT::ValueType)LargerReg) &&
65 "Nothing to promote to??");
67 PromoteTo = (MVT::ValueType)LargerReg;
70 assert(MVT::isInteger(VT) == MVT::isInteger(PromoteTo) &&
71 MVT::isFloatingPoint(VT) == MVT::isFloatingPoint(PromoteTo) &&
72 "Can only promote from int->int or fp->fp!");
73 assert(VT < PromoteTo && "Must promote to a larger type!");
74 TransformToType[VT] = PromoteTo;
75 } else if (Action == TargetLowering::Expand) {
76 assert((VT == MVT::Vector || MVT::isInteger(VT)) && VT > MVT::i8 &&
77 "Cannot expand this type: target must support SOME integer reg!");
78 // Expand to the next smaller integer type!
79 TransformToType[VT] = (MVT::ValueType)(VT-1);
84 /// computeRegisterProperties - Once all of the register classes are added,
85 /// this allows us to compute derived properties we expose.
86 void TargetLowering::computeRegisterProperties() {
87 assert(MVT::LAST_VALUETYPE <= 32 &&
88 "Too many value types for ValueTypeActions to hold!");
90 // Everything defaults to one.
91 for (unsigned i = 0; i != MVT::LAST_VALUETYPE; ++i)
92 NumElementsForVT[i] = 1;
94 // Find the largest integer register class.
95 unsigned LargestIntReg = MVT::i128;
96 for (; RegClassForVT[LargestIntReg] == 0; --LargestIntReg)
97 assert(LargestIntReg != MVT::i1 && "No integer registers defined!");
99 // Every integer value type larger than this largest register takes twice as
100 // many registers to represent as the previous ValueType.
101 unsigned ExpandedReg = LargestIntReg; ++LargestIntReg;
102 for (++ExpandedReg; MVT::isInteger((MVT::ValueType)ExpandedReg);++ExpandedReg)
103 NumElementsForVT[ExpandedReg] = 2*NumElementsForVT[ExpandedReg-1];
105 // Inspect all of the ValueType's possible, deciding how to process them.
106 for (unsigned IntReg = MVT::i1; IntReg <= MVT::i128; ++IntReg)
107 // If we are expanding this type, expand it!
108 if (getNumElements((MVT::ValueType)IntReg) != 1)
109 SetValueTypeAction((MVT::ValueType)IntReg, Expand, *this, TransformToType,
111 else if (!isTypeLegal((MVT::ValueType)IntReg))
112 // Otherwise, if we don't have native support, we must promote to a
114 SetValueTypeAction((MVT::ValueType)IntReg, Promote, *this,
115 TransformToType, ValueTypeActions);
117 TransformToType[(MVT::ValueType)IntReg] = (MVT::ValueType)IntReg;
119 // If the target does not have native support for F32, promote it to F64.
120 if (!isTypeLegal(MVT::f32))
121 SetValueTypeAction(MVT::f32, Promote, *this,
122 TransformToType, ValueTypeActions);
124 TransformToType[MVT::f32] = MVT::f32;
126 // Set MVT::Vector to always be Expanded
127 SetValueTypeAction(MVT::Vector, Expand, *this, TransformToType,
130 // Loop over all of the legal vector value types, specifying an identity type
132 for (unsigned i = MVT::FIRST_VECTOR_VALUETYPE;
133 i <= MVT::LAST_VECTOR_VALUETYPE; ++i) {
134 if (isTypeLegal((MVT::ValueType)i))
135 TransformToType[i] = (MVT::ValueType)i;
138 assert(isTypeLegal(MVT::f64) && "Target does not support FP?");
139 TransformToType[MVT::f64] = MVT::f64;
142 const char *TargetLowering::getTargetNodeName(unsigned Opcode) const {
146 /// getPackedTypeBreakdown - Packed types are broken down into some number of
147 /// legal scalar types. For example, <8 x float> maps to 2 MVT::v2f32 values
148 /// with Altivec or SSE1, or 8 promoted MVT::f64 values with the X86 FP stack.
150 /// This method returns the number and type of the resultant breakdown.
152 unsigned TargetLowering::getPackedTypeBreakdown(const PackedType *PTy,
153 MVT::ValueType &PTyElementVT,
154 MVT::ValueType &PTyLegalElementVT) const {
155 // Figure out the right, legal destination reg to copy into.
156 unsigned NumElts = PTy->getNumElements();
157 MVT::ValueType EltTy = getValueType(PTy->getElementType());
159 unsigned NumVectorRegs = 1;
161 // Divide the input until we get to a supported size. This will always
162 // end with a scalar if the target doesn't support vectors.
163 while (NumElts > 1 && !isTypeLegal(getVectorType(EltTy, NumElts))) {
172 VT = getVectorType(EltTy, NumElts);
176 MVT::ValueType DestVT = getTypeToTransformTo(VT);
177 PTyLegalElementVT = DestVT;
179 // Value is expanded, e.g. i64 -> i16.
180 return NumVectorRegs*(MVT::getSizeInBits(VT)/MVT::getSizeInBits(DestVT));
182 // Otherwise, promotion or legal types use the same number of registers as
183 // the vector decimated to the appropriate level.
184 return NumVectorRegs;
190 //===----------------------------------------------------------------------===//
191 // Optimization Methods
192 //===----------------------------------------------------------------------===//
194 /// ShrinkDemandedConstant - Check to see if the specified operand of the
195 /// specified instruction is a constant integer. If so, check to see if there
196 /// are any bits set in the constant that are not demanded. If so, shrink the
197 /// constant and return true.
198 bool TargetLowering::TargetLoweringOpt::ShrinkDemandedConstant(SDOperand Op,
200 // FIXME: ISD::SELECT, ISD::SELECT_CC
201 switch(Op.getOpcode()) {
206 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
207 if ((~Demanded & C->getValue()) != 0) {
208 MVT::ValueType VT = Op.getValueType();
209 SDOperand New = DAG.getNode(Op.getOpcode(), VT, Op.getOperand(0),
210 DAG.getConstant(Demanded & C->getValue(),
212 return CombineTo(Op, New);
219 /// SimplifyDemandedBits - Look at Op. At this point, we know that only the
220 /// DemandedMask bits of the result of Op are ever used downstream. If we can
221 /// use this information to simplify Op, create a new simplified DAG node and
222 /// return true, returning the original and new nodes in Old and New. Otherwise,
223 /// analyze the expression and return a mask of KnownOne and KnownZero bits for
224 /// the expression (used to simplify the caller). The KnownZero/One bits may
225 /// only be accurate for those bits in the DemandedMask.
226 bool TargetLowering::SimplifyDemandedBits(SDOperand Op, uint64_t DemandedMask,
229 TargetLoweringOpt &TLO,
230 unsigned Depth) const {
231 KnownZero = KnownOne = 0; // Don't know anything.
232 // Other users may use these bits.
233 if (!Op.Val->hasOneUse()) {
235 // If not at the root, Just compute the KnownZero/KnownOne bits to
236 // simplify things downstream.
237 ComputeMaskedBits(Op, DemandedMask, KnownZero, KnownOne, Depth);
240 // If this is the root being simplified, allow it to have multiple uses,
241 // just set the DemandedMask to all bits.
242 DemandedMask = MVT::getIntVTBitMask(Op.getValueType());
243 } else if (DemandedMask == 0) {
244 // Not demanding any bits from Op.
245 if (Op.getOpcode() != ISD::UNDEF)
246 return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::UNDEF, Op.getValueType()));
248 } else if (Depth == 6) { // Limit search depth.
252 uint64_t KnownZero2, KnownOne2, KnownZeroOut, KnownOneOut;
253 switch (Op.getOpcode()) {
255 // We know all of the bits for a constant!
256 KnownOne = cast<ConstantSDNode>(Op)->getValue() & DemandedMask;
257 KnownZero = ~KnownOne & DemandedMask;
258 return false; // Don't fall through, will infinitely loop.
260 // If the RHS is a constant, check to see if the LHS would be zero without
261 // using the bits from the RHS. Below, we use knowledge about the RHS to
262 // simplify the LHS, here we're using information from the LHS to simplify
264 if (ConstantSDNode *RHSC = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
265 uint64_t LHSZero, LHSOne;
266 ComputeMaskedBits(Op.getOperand(0), DemandedMask,
267 LHSZero, LHSOne, Depth+1);
268 // If the LHS already has zeros where RHSC does, this and is dead.
269 if ((LHSZero & DemandedMask) == (~RHSC->getValue() & DemandedMask))
270 return TLO.CombineTo(Op, Op.getOperand(0));
271 // If any of the set bits in the RHS are known zero on the LHS, shrink
273 if (TLO.ShrinkDemandedConstant(Op, ~LHSZero & DemandedMask))
277 if (SimplifyDemandedBits(Op.getOperand(1), DemandedMask, KnownZero,
278 KnownOne, TLO, Depth+1))
280 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
281 if (SimplifyDemandedBits(Op.getOperand(0), DemandedMask & ~KnownZero,
282 KnownZero2, KnownOne2, TLO, Depth+1))
284 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
286 // If all of the demanded bits are known one on one side, return the other.
287 // These bits cannot contribute to the result of the 'and'.
288 if ((DemandedMask & ~KnownZero2 & KnownOne)==(DemandedMask & ~KnownZero2))
289 return TLO.CombineTo(Op, Op.getOperand(0));
290 if ((DemandedMask & ~KnownZero & KnownOne2)==(DemandedMask & ~KnownZero))
291 return TLO.CombineTo(Op, Op.getOperand(1));
292 // If all of the demanded bits in the inputs are known zeros, return zero.
293 if ((DemandedMask & (KnownZero|KnownZero2)) == DemandedMask)
294 return TLO.CombineTo(Op, TLO.DAG.getConstant(0, Op.getValueType()));
295 // If the RHS is a constant, see if we can simplify it.
296 if (TLO.ShrinkDemandedConstant(Op, DemandedMask & ~KnownZero2))
299 // Output known-1 bits are only known if set in both the LHS & RHS.
300 KnownOne &= KnownOne2;
301 // Output known-0 are known to be clear if zero in either the LHS | RHS.
302 KnownZero |= KnownZero2;
305 if (SimplifyDemandedBits(Op.getOperand(1), DemandedMask, KnownZero,
306 KnownOne, TLO, Depth+1))
308 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
309 if (SimplifyDemandedBits(Op.getOperand(0), DemandedMask & ~KnownOne,
310 KnownZero2, KnownOne2, TLO, Depth+1))
312 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
314 // If all of the demanded bits are known zero on one side, return the other.
315 // These bits cannot contribute to the result of the 'or'.
316 if ((DemandedMask & ~KnownOne2 & KnownZero) == (DemandedMask & ~KnownOne2))
317 return TLO.CombineTo(Op, Op.getOperand(0));
318 if ((DemandedMask & ~KnownOne & KnownZero2) == (DemandedMask & ~KnownOne))
319 return TLO.CombineTo(Op, Op.getOperand(1));
320 // If all of the potentially set bits on one side are known to be set on
321 // the other side, just use the 'other' side.
322 if ((DemandedMask & (~KnownZero) & KnownOne2) ==
323 (DemandedMask & (~KnownZero)))
324 return TLO.CombineTo(Op, Op.getOperand(0));
325 if ((DemandedMask & (~KnownZero2) & KnownOne) ==
326 (DemandedMask & (~KnownZero2)))
327 return TLO.CombineTo(Op, Op.getOperand(1));
328 // If the RHS is a constant, see if we can simplify it.
329 if (TLO.ShrinkDemandedConstant(Op, DemandedMask))
332 // Output known-0 bits are only known if clear in both the LHS & RHS.
333 KnownZero &= KnownZero2;
334 // Output known-1 are known to be set if set in either the LHS | RHS.
335 KnownOne |= KnownOne2;
338 if (SimplifyDemandedBits(Op.getOperand(1), DemandedMask, KnownZero,
339 KnownOne, TLO, Depth+1))
341 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
342 if (SimplifyDemandedBits(Op.getOperand(0), DemandedMask, KnownZero2,
343 KnownOne2, TLO, Depth+1))
345 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
347 // If all of the demanded bits are known zero on one side, return the other.
348 // These bits cannot contribute to the result of the 'xor'.
349 if ((DemandedMask & KnownZero) == DemandedMask)
350 return TLO.CombineTo(Op, Op.getOperand(0));
351 if ((DemandedMask & KnownZero2) == DemandedMask)
352 return TLO.CombineTo(Op, Op.getOperand(1));
354 // Output known-0 bits are known if clear or set in both the LHS & RHS.
355 KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
356 // Output known-1 are known to be set if set in only one of the LHS, RHS.
357 KnownOneOut = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
359 // If all of the unknown bits are known to be zero on one side or the other
360 // (but not both) turn this into an *inclusive* or.
361 // e.g. (A & C1)^(B & C2) -> (A & C1)|(B & C2) iff C1&C2 == 0
362 if (uint64_t UnknownBits = DemandedMask & ~(KnownZeroOut|KnownOneOut))
363 if ((UnknownBits & (KnownZero|KnownZero2)) == UnknownBits)
364 return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::OR, Op.getValueType(),
367 // If all of the demanded bits on one side are known, and all of the set
368 // bits on that side are also known to be set on the other side, turn this
369 // into an AND, as we know the bits will be cleared.
370 // e.g. (X | C1) ^ C2 --> (X | C1) & ~C2 iff (C1&C2) == C2
371 if ((DemandedMask & (KnownZero|KnownOne)) == DemandedMask) { // all known
372 if ((KnownOne & KnownOne2) == KnownOne) {
373 MVT::ValueType VT = Op.getValueType();
374 SDOperand ANDC = TLO.DAG.getConstant(~KnownOne & DemandedMask, VT);
375 return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::AND, VT, Op.getOperand(0),
380 // If the RHS is a constant, see if we can simplify it.
381 // FIXME: for XOR, we prefer to force bits to 1 if they will make a -1.
382 if (TLO.ShrinkDemandedConstant(Op, DemandedMask))
385 KnownZero = KnownZeroOut;
386 KnownOne = KnownOneOut;
389 // If we know the result of a setcc has the top bits zero, use this info.
390 if (getSetCCResultContents() == TargetLowering::ZeroOrOneSetCCResult)
391 KnownZero |= (MVT::getIntVTBitMask(Op.getValueType()) ^ 1ULL);
394 if (SimplifyDemandedBits(Op.getOperand(2), DemandedMask, KnownZero,
395 KnownOne, TLO, Depth+1))
397 if (SimplifyDemandedBits(Op.getOperand(1), DemandedMask, KnownZero2,
398 KnownOne2, TLO, Depth+1))
400 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
401 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
403 // If the operands are constants, see if we can simplify them.
404 if (TLO.ShrinkDemandedConstant(Op, DemandedMask))
407 // Only known if known in both the LHS and RHS.
408 KnownOne &= KnownOne2;
409 KnownZero &= KnownZero2;
412 if (SimplifyDemandedBits(Op.getOperand(3), DemandedMask, KnownZero,
413 KnownOne, TLO, Depth+1))
415 if (SimplifyDemandedBits(Op.getOperand(2), DemandedMask, KnownZero2,
416 KnownOne2, TLO, Depth+1))
418 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
419 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
421 // If the operands are constants, see if we can simplify them.
422 if (TLO.ShrinkDemandedConstant(Op, DemandedMask))
425 // Only known if known in both the LHS and RHS.
426 KnownOne &= KnownOne2;
427 KnownZero &= KnownZero2;
430 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
431 if (SimplifyDemandedBits(Op.getOperand(0), DemandedMask >> SA->getValue(),
432 KnownZero, KnownOne, TLO, Depth+1))
434 KnownZero <<= SA->getValue();
435 KnownOne <<= SA->getValue();
436 KnownZero |= (1ULL << SA->getValue())-1; // low bits known zero.
440 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
441 MVT::ValueType VT = Op.getValueType();
442 unsigned ShAmt = SA->getValue();
444 // Compute the new bits that are at the top now.
445 uint64_t HighBits = (1ULL << ShAmt)-1;
446 HighBits <<= MVT::getSizeInBits(VT) - ShAmt;
447 uint64_t TypeMask = MVT::getIntVTBitMask(VT);
449 if (SimplifyDemandedBits(Op.getOperand(0),
450 (DemandedMask << ShAmt) & TypeMask,
451 KnownZero, KnownOne, TLO, Depth+1))
453 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
454 KnownZero &= TypeMask;
455 KnownOne &= TypeMask;
458 KnownZero |= HighBits; // high bits known zero.
462 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
463 MVT::ValueType VT = Op.getValueType();
464 unsigned ShAmt = SA->getValue();
466 // Compute the new bits that are at the top now.
467 uint64_t HighBits = (1ULL << ShAmt)-1;
468 HighBits <<= MVT::getSizeInBits(VT) - ShAmt;
469 uint64_t TypeMask = MVT::getIntVTBitMask(VT);
471 uint64_t InDemandedMask = (DemandedMask << ShAmt) & TypeMask;
473 // If any of the demanded bits are produced by the sign extension, we also
474 // demand the input sign bit.
475 if (HighBits & DemandedMask)
476 InDemandedMask |= MVT::getIntVTSignBit(VT);
478 if (SimplifyDemandedBits(Op.getOperand(0), InDemandedMask,
479 KnownZero, KnownOne, TLO, Depth+1))
481 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
482 KnownZero &= TypeMask;
483 KnownOne &= TypeMask;
484 KnownZero >>= SA->getValue();
485 KnownOne >>= SA->getValue();
487 // Handle the sign bits.
488 uint64_t SignBit = MVT::getIntVTSignBit(VT);
489 SignBit >>= SA->getValue(); // Adjust to where it is now in the mask.
491 // If the input sign bit is known to be zero, or if none of the top bits
492 // are demanded, turn this into an unsigned shift right.
493 if ((KnownZero & SignBit) || (HighBits & ~DemandedMask) == HighBits) {
494 return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::SRL, VT, Op.getOperand(0),
496 } else if (KnownOne & SignBit) { // New bits are known one.
497 KnownOne |= HighBits;
501 case ISD::SIGN_EXTEND_INREG: {
502 MVT::ValueType VT = Op.getValueType();
503 MVT::ValueType EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
505 // Sign extension. Compute the demanded bits in the result that are not
506 // present in the input.
507 uint64_t NewBits = ~MVT::getIntVTBitMask(EVT) & DemandedMask;
509 // If none of the extended bits are demanded, eliminate the sextinreg.
511 return TLO.CombineTo(Op, Op.getOperand(0));
513 uint64_t InSignBit = MVT::getIntVTSignBit(EVT);
514 int64_t InputDemandedBits = DemandedMask & MVT::getIntVTBitMask(EVT);
516 // Since the sign extended bits are demanded, we know that the sign
518 InputDemandedBits |= InSignBit;
520 if (SimplifyDemandedBits(Op.getOperand(0), InputDemandedBits,
521 KnownZero, KnownOne, TLO, Depth+1))
523 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
525 // If the sign bit of the input is known set or clear, then we know the
526 // top bits of the result.
528 // If the input sign bit is known zero, convert this into a zero extension.
529 if (KnownZero & InSignBit)
530 return TLO.CombineTo(Op,
531 TLO.DAG.getZeroExtendInReg(Op.getOperand(0), EVT));
533 if (KnownOne & InSignBit) { // Input sign bit known set
535 KnownZero &= ~NewBits;
536 } else { // Input sign bit unknown
537 KnownZero &= ~NewBits;
538 KnownOne &= ~NewBits;
545 MVT::ValueType VT = Op.getValueType();
546 unsigned LowBits = Log2_32(MVT::getSizeInBits(VT))+1;
547 KnownZero = ~((1ULL << LowBits)-1) & MVT::getIntVTBitMask(VT);
551 case ISD::ZEXTLOAD: {
552 MVT::ValueType VT = cast<VTSDNode>(Op.getOperand(3))->getVT();
553 KnownZero |= ~MVT::getIntVTBitMask(VT) & DemandedMask;
556 case ISD::ZERO_EXTEND: {
557 uint64_t InMask = MVT::getIntVTBitMask(Op.getOperand(0).getValueType());
559 // If none of the top bits are demanded, convert this into an any_extend.
560 uint64_t NewBits = (~InMask) & DemandedMask;
562 return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::ANY_EXTEND,
566 if (SimplifyDemandedBits(Op.getOperand(0), DemandedMask & InMask,
567 KnownZero, KnownOne, TLO, Depth+1))
569 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
570 KnownZero |= NewBits;
573 case ISD::SIGN_EXTEND: {
574 MVT::ValueType InVT = Op.getOperand(0).getValueType();
575 uint64_t InMask = MVT::getIntVTBitMask(InVT);
576 uint64_t InSignBit = MVT::getIntVTSignBit(InVT);
577 uint64_t NewBits = (~InMask) & DemandedMask;
579 // If none of the top bits are demanded, convert this into an any_extend.
581 return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::ANY_EXTEND,Op.getValueType(),
584 // Since some of the sign extended bits are demanded, we know that the sign
586 uint64_t InDemandedBits = DemandedMask & InMask;
587 InDemandedBits |= InSignBit;
589 if (SimplifyDemandedBits(Op.getOperand(0), InDemandedBits, KnownZero,
590 KnownOne, TLO, Depth+1))
593 // If the sign bit is known zero, convert this to a zero extend.
594 if (KnownZero & InSignBit)
595 return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::ZERO_EXTEND,
599 // If the sign bit is known one, the top bits match.
600 if (KnownOne & InSignBit) {
602 KnownZero &= ~NewBits;
603 } else { // Otherwise, top bits aren't known.
604 KnownOne &= ~NewBits;
605 KnownZero &= ~NewBits;
609 case ISD::ANY_EXTEND: {
610 uint64_t InMask = MVT::getIntVTBitMask(Op.getOperand(0).getValueType());
611 if (SimplifyDemandedBits(Op.getOperand(0), DemandedMask & InMask,
612 KnownZero, KnownOne, TLO, Depth+1))
614 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
617 case ISD::TRUNCATE: {
618 // Simplify the input, using demanded bit information, and compute the known
619 // zero/one bits live out.
620 if (SimplifyDemandedBits(Op.getOperand(0), DemandedMask,
621 KnownZero, KnownOne, TLO, Depth+1))
624 // If the input is only used by this truncate, see if we can shrink it based
625 // on the known demanded bits.
626 if (Op.getOperand(0).Val->hasOneUse()) {
627 SDOperand In = Op.getOperand(0);
628 switch (In.getOpcode()) {
631 // Shrink SRL by a constant if none of the high bits shifted in are
633 if (ConstantSDNode *ShAmt = dyn_cast<ConstantSDNode>(In.getOperand(1))){
634 uint64_t HighBits = MVT::getIntVTBitMask(In.getValueType());
635 HighBits &= ~MVT::getIntVTBitMask(Op.getValueType());
636 HighBits >>= ShAmt->getValue();
638 if (ShAmt->getValue() < MVT::getSizeInBits(Op.getValueType()) &&
639 (DemandedMask & HighBits) == 0) {
640 // None of the shifted in bits are needed. Add a truncate of the
641 // shift input, then shift it.
642 SDOperand NewTrunc = TLO.DAG.getNode(ISD::TRUNCATE,
645 return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::SRL,Op.getValueType(),
646 NewTrunc, In.getOperand(1)));
653 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
654 uint64_t OutMask = MVT::getIntVTBitMask(Op.getValueType());
655 KnownZero &= OutMask;
659 case ISD::AssertZext: {
660 MVT::ValueType VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
661 uint64_t InMask = MVT::getIntVTBitMask(VT);
662 if (SimplifyDemandedBits(Op.getOperand(0), DemandedMask & InMask,
663 KnownZero, KnownOne, TLO, Depth+1))
665 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
666 KnownZero |= ~InMask & DemandedMask;
671 case ISD::INTRINSIC_WO_CHAIN:
672 case ISD::INTRINSIC_W_CHAIN:
673 case ISD::INTRINSIC_VOID:
674 // Just use ComputeMaskedBits to compute output bits.
675 ComputeMaskedBits(Op, DemandedMask, KnownZero, KnownOne, Depth);
679 // If we know the value of all of the demanded bits, return this as a
681 if ((DemandedMask & (KnownZero|KnownOne)) == DemandedMask)
682 return TLO.CombineTo(Op, TLO.DAG.getConstant(KnownOne, Op.getValueType()));
687 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
688 /// this predicate to simplify operations downstream. Mask is known to be zero
689 /// for bits that V cannot have.
690 bool TargetLowering::MaskedValueIsZero(SDOperand Op, uint64_t Mask,
691 unsigned Depth) const {
692 uint64_t KnownZero, KnownOne;
693 ComputeMaskedBits(Op, Mask, KnownZero, KnownOne, Depth);
694 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
695 return (KnownZero & Mask) == Mask;
698 /// ComputeMaskedBits - Determine which of the bits specified in Mask are
699 /// known to be either zero or one and return them in the KnownZero/KnownOne
700 /// bitsets. This code only analyzes bits in Mask, in order to short-circuit
702 void TargetLowering::ComputeMaskedBits(SDOperand Op, uint64_t Mask,
703 uint64_t &KnownZero, uint64_t &KnownOne,
704 unsigned Depth) const {
705 KnownZero = KnownOne = 0; // Don't know anything.
706 if (Depth == 6 || Mask == 0)
707 return; // Limit search depth.
709 uint64_t KnownZero2, KnownOne2;
711 switch (Op.getOpcode()) {
713 // We know all of the bits for a constant!
714 KnownOne = cast<ConstantSDNode>(Op)->getValue() & Mask;
715 KnownZero = ~KnownOne & Mask;
718 // If either the LHS or the RHS are Zero, the result is zero.
719 ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1);
721 ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero2, KnownOne2, Depth+1);
722 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
723 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
725 // Output known-1 bits are only known if set in both the LHS & RHS.
726 KnownOne &= KnownOne2;
727 // Output known-0 are known to be clear if zero in either the LHS | RHS.
728 KnownZero |= KnownZero2;
731 ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1);
733 ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero2, KnownOne2, Depth+1);
734 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
735 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
737 // Output known-0 bits are only known if clear in both the LHS & RHS.
738 KnownZero &= KnownZero2;
739 // Output known-1 are known to be set if set in either the LHS | RHS.
740 KnownOne |= KnownOne2;
743 ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1);
744 ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero2, KnownOne2, Depth+1);
745 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
746 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
748 // Output known-0 bits are known if clear or set in both the LHS & RHS.
749 uint64_t KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
750 // Output known-1 are known to be set if set in only one of the LHS, RHS.
751 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
752 KnownZero = KnownZeroOut;
756 ComputeMaskedBits(Op.getOperand(2), Mask, KnownZero, KnownOne, Depth+1);
757 ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero2, KnownOne2, Depth+1);
758 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
759 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
761 // Only known if known in both the LHS and RHS.
762 KnownOne &= KnownOne2;
763 KnownZero &= KnownZero2;
766 ComputeMaskedBits(Op.getOperand(3), Mask, KnownZero, KnownOne, Depth+1);
767 ComputeMaskedBits(Op.getOperand(2), Mask, KnownZero2, KnownOne2, Depth+1);
768 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
769 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
771 // Only known if known in both the LHS and RHS.
772 KnownOne &= KnownOne2;
773 KnownZero &= KnownZero2;
776 // If we know the result of a setcc has the top bits zero, use this info.
777 if (getSetCCResultContents() == TargetLowering::ZeroOrOneSetCCResult)
778 KnownZero |= (MVT::getIntVTBitMask(Op.getValueType()) ^ 1ULL);
781 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
782 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
783 Mask >>= SA->getValue();
784 ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero, KnownOne, Depth+1);
785 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
786 KnownZero <<= SA->getValue();
787 KnownOne <<= SA->getValue();
788 KnownZero |= (1ULL << SA->getValue())-1; // low bits known zero.
792 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
793 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
794 uint64_t HighBits = (1ULL << SA->getValue())-1;
795 HighBits <<= MVT::getSizeInBits(Op.getValueType())-SA->getValue();
796 Mask <<= SA->getValue();
797 ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero, KnownOne, Depth+1);
798 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
799 KnownZero >>= SA->getValue();
800 KnownOne >>= SA->getValue();
801 KnownZero |= HighBits; // high bits known zero.
805 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
806 uint64_t HighBits = (1ULL << SA->getValue())-1;
807 HighBits <<= MVT::getSizeInBits(Op.getValueType())-SA->getValue();
808 Mask <<= SA->getValue();
809 ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero, KnownOne, Depth+1);
810 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
811 KnownZero >>= SA->getValue();
812 KnownOne >>= SA->getValue();
814 // Handle the sign bits.
815 uint64_t SignBit = 1ULL << (MVT::getSizeInBits(Op.getValueType())-1);
816 SignBit >>= SA->getValue(); // Adjust to where it is now in the mask.
818 if (KnownZero & SignBit) { // New bits are known zero.
819 KnownZero |= HighBits;
820 } else if (KnownOne & SignBit) { // New bits are known one.
821 KnownOne |= HighBits;
825 case ISD::SIGN_EXTEND_INREG: {
826 MVT::ValueType VT = Op.getValueType();
827 MVT::ValueType EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
829 // Sign extension. Compute the demanded bits in the result that are not
830 // present in the input.
831 uint64_t NewBits = ~MVT::getIntVTBitMask(EVT) & Mask;
833 uint64_t InSignBit = MVT::getIntVTSignBit(EVT);
834 int64_t InputDemandedBits = Mask & MVT::getIntVTBitMask(EVT);
836 // If the sign extended bits are demanded, we know that the sign
839 InputDemandedBits |= InSignBit;
841 ComputeMaskedBits(Op.getOperand(0), InputDemandedBits,
842 KnownZero, KnownOne, Depth+1);
843 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
845 // If the sign bit of the input is known set or clear, then we know the
846 // top bits of the result.
847 if (KnownZero & InSignBit) { // Input sign bit known clear
848 KnownZero |= NewBits;
849 KnownOne &= ~NewBits;
850 } else if (KnownOne & InSignBit) { // Input sign bit known set
852 KnownZero &= ~NewBits;
853 } else { // Input sign bit unknown
854 KnownZero &= ~NewBits;
855 KnownOne &= ~NewBits;
862 MVT::ValueType VT = Op.getValueType();
863 unsigned LowBits = Log2_32(MVT::getSizeInBits(VT))+1;
864 KnownZero = ~((1ULL << LowBits)-1) & MVT::getIntVTBitMask(VT);
868 case ISD::ZEXTLOAD: {
869 MVT::ValueType VT = cast<VTSDNode>(Op.getOperand(3))->getVT();
870 KnownZero |= ~MVT::getIntVTBitMask(VT) & Mask;
873 case ISD::ZERO_EXTEND: {
874 uint64_t InMask = MVT::getIntVTBitMask(Op.getOperand(0).getValueType());
875 uint64_t NewBits = (~InMask) & Mask;
876 ComputeMaskedBits(Op.getOperand(0), Mask & InMask, KnownZero,
878 KnownZero |= NewBits & Mask;
879 KnownOne &= ~NewBits;
882 case ISD::SIGN_EXTEND: {
883 MVT::ValueType InVT = Op.getOperand(0).getValueType();
884 unsigned InBits = MVT::getSizeInBits(InVT);
885 uint64_t InMask = MVT::getIntVTBitMask(InVT);
886 uint64_t InSignBit = 1ULL << (InBits-1);
887 uint64_t NewBits = (~InMask) & Mask;
888 uint64_t InDemandedBits = Mask & InMask;
890 // If any of the sign extended bits are demanded, we know that the sign
893 InDemandedBits |= InSignBit;
895 ComputeMaskedBits(Op.getOperand(0), InDemandedBits, KnownZero,
897 // If the sign bit is known zero or one, the top bits match.
898 if (KnownZero & InSignBit) {
899 KnownZero |= NewBits;
900 KnownOne &= ~NewBits;
901 } else if (KnownOne & InSignBit) {
903 KnownZero &= ~NewBits;
904 } else { // Otherwise, top bits aren't known.
905 KnownOne &= ~NewBits;
906 KnownZero &= ~NewBits;
910 case ISD::ANY_EXTEND: {
911 MVT::ValueType VT = Op.getOperand(0).getValueType();
912 ComputeMaskedBits(Op.getOperand(0), Mask & MVT::getIntVTBitMask(VT),
913 KnownZero, KnownOne, Depth+1);
916 case ISD::TRUNCATE: {
917 ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero, KnownOne, Depth+1);
918 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
919 uint64_t OutMask = MVT::getIntVTBitMask(Op.getValueType());
920 KnownZero &= OutMask;
924 case ISD::AssertZext: {
925 MVT::ValueType VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
926 uint64_t InMask = MVT::getIntVTBitMask(VT);
927 ComputeMaskedBits(Op.getOperand(0), Mask & InMask, KnownZero,
929 KnownZero |= (~InMask) & Mask;
933 // If either the LHS or the RHS are Zero, the result is zero.
934 ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1);
935 ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero2, KnownOne2, Depth+1);
936 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
937 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
939 // Output known-0 bits are known if clear or set in both the low clear bits
940 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
942 uint64_t KnownZeroOut = std::min(CountTrailingZeros_64(~KnownZero),
943 CountTrailingZeros_64(~KnownZero2));
945 KnownZero = (1ULL << KnownZeroOut) - 1;
950 ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0));
953 // We know that the top bits of C-X are clear if X contains less bits
954 // than C (i.e. no wrap-around can happen). For example, 20-X is
955 // positive if we can prove that X is >= 0 and < 16.
956 MVT::ValueType VT = CLHS->getValueType(0);
957 if ((CLHS->getValue() & MVT::getIntVTSignBit(VT)) == 0) { // sign bit clear
958 unsigned NLZ = CountLeadingZeros_64(CLHS->getValue()+1);
959 uint64_t MaskV = (1ULL << (63-NLZ))-1; // NLZ can't be 64 with no sign bit
960 MaskV = ~MaskV & MVT::getIntVTBitMask(VT);
961 ComputeMaskedBits(Op.getOperand(1), MaskV, KnownZero, KnownOne, Depth+1);
963 // If all of the MaskV bits are known to be zero, then we know the output
964 // top bits are zero, because we now know that the output is from [0-C].
965 if ((KnownZero & MaskV) == MaskV) {
966 unsigned NLZ2 = CountLeadingZeros_64(CLHS->getValue());
967 KnownZero = ~((1ULL << (64-NLZ2))-1) & Mask; // Top bits known zero.
968 KnownOne = 0; // No one bits known.
970 KnownOne = KnownOne = 0; // Otherwise, nothing known.
976 // Allow the target to implement this method for its nodes.
977 if (Op.getOpcode() >= ISD::BUILTIN_OP_END) {
978 case ISD::INTRINSIC_WO_CHAIN:
979 case ISD::INTRINSIC_W_CHAIN:
980 case ISD::INTRINSIC_VOID:
981 computeMaskedBitsForTargetNode(Op, Mask, KnownZero, KnownOne);
987 /// computeMaskedBitsForTargetNode - Determine which of the bits specified
988 /// in Mask are known to be either zero or one and return them in the
989 /// KnownZero/KnownOne bitsets.
990 void TargetLowering::computeMaskedBitsForTargetNode(const SDOperand Op,
994 unsigned Depth) const {
995 assert((Op.getOpcode() >= ISD::BUILTIN_OP_END ||
996 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
997 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
998 Op.getOpcode() == ISD::INTRINSIC_VOID) &&
999 "Should use MaskedValueIsZero if you don't know whether Op"
1000 " is a target node!");
1005 /// ComputeNumSignBits - Return the number of times the sign bit of the
1006 /// register is replicated into the other bits. We know that at least 1 bit
1007 /// is always equal to the sign bit (itself), but other cases can give us
1008 /// information. For example, immediately after an "SRA X, 2", we know that
1009 /// the top 3 bits are all equal to each other, so we return 3.
1010 unsigned TargetLowering::ComputeNumSignBits(SDOperand Op, unsigned Depth) const{
1011 MVT::ValueType VT = Op.getValueType();
1012 assert(MVT::isInteger(VT) && "Invalid VT!");
1013 unsigned VTBits = MVT::getSizeInBits(VT);
1017 return 1; // Limit search depth.
1019 switch (Op.getOpcode()) {
1021 case ISD::AssertSext:
1022 Tmp = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(1))->getVT());
1023 return VTBits-Tmp+1;
1024 case ISD::AssertZext:
1025 Tmp = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(1))->getVT());
1028 case ISD::SEXTLOAD: // '17' bits known
1029 Tmp = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(3))->getVT());
1030 return VTBits-Tmp+1;
1031 case ISD::ZEXTLOAD: // '16' bits known
1032 Tmp = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(3))->getVT());
1035 case ISD::Constant: {
1036 uint64_t Val = cast<ConstantSDNode>(Op)->getValue();
1037 // If negative, invert the bits, then look at it.
1038 if (Val & MVT::getIntVTSignBit(VT))
1041 // Shift the bits so they are the leading bits in the int64_t.
1044 // Return # leading zeros. We use 'min' here in case Val was zero before
1045 // shifting. We don't want to return '64' as for an i32 "0".
1046 return std::min(VTBits, CountLeadingZeros_64(Val));
1049 case ISD::SIGN_EXTEND:
1050 Tmp = VTBits-MVT::getSizeInBits(Op.getOperand(0).getValueType());
1051 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
1053 case ISD::SIGN_EXTEND_INREG:
1054 // Max of the input and what this extends.
1055 Tmp = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(1))->getVT());
1058 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1059 return std::max(Tmp, Tmp2);
1062 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1063 // SRA X, C -> adds C sign bits.
1064 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1065 Tmp += C->getValue();
1066 if (Tmp > VTBits) Tmp = VTBits;
1070 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1071 // shl destroys sign bits.
1072 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1073 if (C->getValue() >= VTBits || // Bad shift.
1074 C->getValue() >= Tmp) break; // Shifted all sign bits out.
1075 return Tmp - C->getValue();
1080 case ISD::XOR: // NOT is handled here.
1081 // Logical binary ops preserve the number of sign bits.
1082 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1083 if (Tmp == 1) return 1; // Early out.
1084 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
1085 return std::min(Tmp, Tmp2);
1088 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1089 if (Tmp == 1) return 1; // Early out.
1090 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
1091 return std::min(Tmp, Tmp2);
1094 // If setcc returns 0/-1, all bits are sign bits.
1095 if (getSetCCResultContents() == ZeroOrNegativeOneSetCCResult)
1100 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1101 unsigned RotAmt = C->getValue() & (VTBits-1);
1103 // Handle rotate right by N like a rotate left by 32-N.
1104 if (Op.getOpcode() == ISD::ROTR)
1105 RotAmt = (VTBits-RotAmt) & (VTBits-1);
1107 // If we aren't rotating out all of the known-in sign bits, return the
1108 // number that are left. This handles rotl(sext(x), 1) for example.
1109 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1110 if (Tmp > RotAmt+1) return Tmp-RotAmt;
1114 // Add can have at most one carry bit. Thus we know that the output
1115 // is, at worst, one more bit than the inputs.
1116 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1117 if (Tmp == 1) return 1; // Early out.
1119 // Special case decrementing a value (ADD X, -1):
1120 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
1121 if (CRHS->isAllOnesValue()) {
1122 uint64_t KnownZero, KnownOne;
1123 uint64_t Mask = MVT::getIntVTBitMask(VT);
1124 ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero, KnownOne, Depth+1);
1126 // If the input is known to be 0 or 1, the output is 0/-1, which is all
1128 if ((KnownZero|1) == Mask)
1131 // If we are subtracting one from a positive number, there is no carry
1132 // out of the result.
1133 if (KnownZero & MVT::getIntVTSignBit(VT))
1137 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
1138 if (Tmp2 == 1) return 1;
1139 return std::min(Tmp, Tmp2)-1;
1143 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
1144 if (Tmp2 == 1) return 1;
1147 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
1148 if (CLHS->getValue() == 0) {
1149 uint64_t KnownZero, KnownOne;
1150 uint64_t Mask = MVT::getIntVTBitMask(VT);
1151 ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1);
1152 // If the input is known to be 0 or 1, the output is 0/-1, which is all
1154 if ((KnownZero|1) == Mask)
1157 // If the input is known to be positive (the sign bit is known clear),
1158 // the output of the NEG has the same number of sign bits as the input.
1159 if (KnownZero & MVT::getIntVTSignBit(VT))
1162 // Otherwise, we treat this like a SUB.
1165 // Sub can have at most one carry bit. Thus we know that the output
1166 // is, at worst, one more bit than the inputs.
1167 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1168 if (Tmp == 1) return 1; // Early out.
1169 return std::min(Tmp, Tmp2)-1;
1172 // FIXME: it's tricky to do anything useful for this, but it is an important
1173 // case for targets like X86.
1177 // Allow the target to implement this method for its nodes.
1178 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
1179 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
1180 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
1181 Op.getOpcode() == ISD::INTRINSIC_VOID) {
1182 unsigned NumBits = ComputeNumSignBitsForTargetNode(Op, Depth);
1183 if (NumBits > 1) return NumBits;
1186 // Finally, if we can prove that the top bits of the result are 0's or 1's,
1187 // use this information.
1188 uint64_t KnownZero, KnownOne;
1189 uint64_t Mask = MVT::getIntVTBitMask(VT);
1190 ComputeMaskedBits(Op, Mask, KnownZero, KnownOne, Depth);
1192 uint64_t SignBit = MVT::getIntVTSignBit(VT);
1193 if (KnownZero & SignBit) { // SignBit is 0
1195 } else if (KnownOne & SignBit) { // SignBit is 1;
1202 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
1203 // the number of identical bits in the top of the input value.
1206 // Return # leading zeros. We use 'min' here in case Val was zero before
1207 // shifting. We don't want to return '64' as for an i32 "0".
1208 return std::min(VTBits, CountLeadingZeros_64(Mask));
1213 /// ComputeNumSignBitsForTargetNode - This method can be implemented by
1214 /// targets that want to expose additional information about sign bits to the
1216 unsigned TargetLowering::ComputeNumSignBitsForTargetNode(SDOperand Op,
1217 unsigned Depth) const {
1218 assert((Op.getOpcode() >= ISD::BUILTIN_OP_END ||
1219 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
1220 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
1221 Op.getOpcode() == ISD::INTRINSIC_VOID) &&
1222 "Should use ComputeNumSignBits if you don't know whether Op"
1223 " is a target node!");
1228 SDOperand TargetLowering::
1229 PerformDAGCombine(SDNode *N, DAGCombinerInfo &DCI) const {
1230 // Default implementation: no optimization.
1234 //===----------------------------------------------------------------------===//
1235 // Inline Assembler Implementation Methods
1236 //===----------------------------------------------------------------------===//
1238 TargetLowering::ConstraintType
1239 TargetLowering::getConstraintType(char ConstraintLetter) const {
1240 // FIXME: lots more standard ones to handle.
1241 switch (ConstraintLetter) {
1242 default: return C_Unknown;
1243 case 'r': return C_RegisterClass;
1245 case 'o': // offsetable
1246 case 'V': // not offsetable
1248 case 'i': // Simple Integer or Relocatable Constant
1249 case 'n': // Simple Integer
1250 case 's': // Relocatable Constant
1251 case 'I': // Target registers.
1263 bool TargetLowering::isOperandValidForConstraint(SDOperand Op,
1264 char ConstraintLetter) {
1265 switch (ConstraintLetter) {
1266 default: return false;
1267 case 'i': // Simple Integer or Relocatable Constant
1268 case 'n': // Simple Integer
1269 case 's': // Relocatable Constant
1270 return true; // FIXME: not right.
1275 std::vector<unsigned> TargetLowering::
1276 getRegClassForInlineAsmConstraint(const std::string &Constraint,
1277 MVT::ValueType VT) const {
1278 return std::vector<unsigned>();
1282 std::pair<unsigned, const TargetRegisterClass*> TargetLowering::
1283 getRegForInlineAsmConstraint(const std::string &Constraint,
1284 MVT::ValueType VT) const {
1285 if (Constraint[0] != '{')
1286 return std::pair<unsigned, const TargetRegisterClass*>(0, 0);
1287 assert(*(Constraint.end()-1) == '}' && "Not a brace enclosed constraint?");
1289 // Remove the braces from around the name.
1290 std::string RegName(Constraint.begin()+1, Constraint.end()-1);
1292 // Figure out which register class contains this reg.
1293 const MRegisterInfo *RI = TM.getRegisterInfo();
1294 for (MRegisterInfo::regclass_iterator RCI = RI->regclass_begin(),
1295 E = RI->regclass_end(); RCI != E; ++RCI) {
1296 const TargetRegisterClass *RC = *RCI;
1298 // If none of the the value types for this register class are valid, we
1299 // can't use it. For example, 64-bit reg classes on 32-bit targets.
1300 bool isLegal = false;
1301 for (TargetRegisterClass::vt_iterator I = RC->vt_begin(), E = RC->vt_end();
1303 if (isTypeLegal(*I)) {
1309 if (!isLegal) continue;
1311 for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end();
1313 if (StringsEqualNoCase(RegName, RI->get(*I).Name))
1314 return std::make_pair(*I, RC);
1318 return std::pair<unsigned, const TargetRegisterClass*>(0, 0);
1321 //===----------------------------------------------------------------------===//
1322 // Loop Strength Reduction hooks
1323 //===----------------------------------------------------------------------===//
1325 /// isLegalAddressImmediate - Return true if the integer value or
1326 /// GlobalValue can be used as the offset of the target addressing mode.
1327 bool TargetLowering::isLegalAddressImmediate(int64_t V) const {
1330 bool TargetLowering::isLegalAddressImmediate(GlobalValue *GV) const {