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 first class types. For example, <8 x float> maps to 2 MVT::v4f32
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 uint64_t LowBits = (1ULL << SA->getValue())-1;
784 Mask >>= SA->getValue();
785 ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero, KnownOne, Depth+1);
786 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
787 KnownZero <<= SA->getValue();
788 KnownOne <<= SA->getValue();
789 KnownZero |= LowBits; // low bits known zero
790 KnownOne &= ~LowBits; // and known not to be one.
794 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
795 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
796 uint64_t HighBits = (1ULL << SA->getValue())-1;
797 HighBits <<= MVT::getSizeInBits(Op.getValueType())-SA->getValue();
798 Mask <<= SA->getValue();
799 ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero, KnownOne, Depth+1);
800 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
801 KnownZero >>= SA->getValue();
802 KnownOne >>= SA->getValue();
803 KnownZero |= HighBits; // high bits known zero
804 KnownOne &= ~HighBits; // and known not to be one.
808 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
809 uint64_t HighBits = (1ULL << SA->getValue())-1;
810 HighBits <<= MVT::getSizeInBits(Op.getValueType())-SA->getValue();
811 Mask <<= SA->getValue();
812 ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero, KnownOne, Depth+1);
813 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
814 KnownZero >>= SA->getValue();
815 KnownOne >>= SA->getValue();
817 // Handle the sign bits.
818 uint64_t SignBit = 1ULL << (MVT::getSizeInBits(Op.getValueType())-1);
819 SignBit >>= SA->getValue(); // Adjust to where it is now in the mask.
821 if (KnownZero & SignBit) {
822 KnownZero |= HighBits; // New bits are known zero
823 KnownOne &= ~HighBits; // and known not to be one.
824 } else if (KnownOne & SignBit) {
825 KnownOne |= HighBits; // New bits are known one
826 KnownZero &= ~HighBits; // and known not to be zero.
830 case ISD::SIGN_EXTEND_INREG: {
831 MVT::ValueType VT = Op.getValueType();
832 MVT::ValueType EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
834 // Sign extension. Compute the demanded bits in the result that are not
835 // present in the input.
836 uint64_t NewBits = ~MVT::getIntVTBitMask(EVT) & Mask;
838 uint64_t InSignBit = MVT::getIntVTSignBit(EVT);
839 int64_t InputDemandedBits = Mask & MVT::getIntVTBitMask(EVT);
841 // If the sign extended bits are demanded, we know that the sign
844 InputDemandedBits |= InSignBit;
846 ComputeMaskedBits(Op.getOperand(0), InputDemandedBits,
847 KnownZero, KnownOne, Depth+1);
848 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
850 // If the sign bit of the input is known set or clear, then we know the
851 // top bits of the result.
852 if (KnownZero & InSignBit) { // Input sign bit known clear
853 KnownZero |= NewBits;
854 KnownOne &= ~NewBits;
855 } else if (KnownOne & InSignBit) { // Input sign bit known set
857 KnownZero &= ~NewBits;
858 } else { // Input sign bit unknown
859 KnownZero &= ~NewBits;
860 KnownOne &= ~NewBits;
867 MVT::ValueType VT = Op.getValueType();
868 unsigned LowBits = Log2_32(MVT::getSizeInBits(VT))+1;
869 KnownZero = ~((1ULL << LowBits)-1) & MVT::getIntVTBitMask(VT);
873 case ISD::ZEXTLOAD: {
874 MVT::ValueType VT = cast<VTSDNode>(Op.getOperand(3))->getVT();
875 KnownZero |= ~MVT::getIntVTBitMask(VT) & Mask;
878 case ISD::ZERO_EXTEND: {
879 uint64_t InMask = MVT::getIntVTBitMask(Op.getOperand(0).getValueType());
880 uint64_t NewBits = (~InMask) & Mask;
881 ComputeMaskedBits(Op.getOperand(0), Mask & InMask, KnownZero,
883 KnownZero |= NewBits & Mask;
884 KnownOne &= ~NewBits;
887 case ISD::SIGN_EXTEND: {
888 MVT::ValueType InVT = Op.getOperand(0).getValueType();
889 unsigned InBits = MVT::getSizeInBits(InVT);
890 uint64_t InMask = MVT::getIntVTBitMask(InVT);
891 uint64_t InSignBit = 1ULL << (InBits-1);
892 uint64_t NewBits = (~InMask) & Mask;
893 uint64_t InDemandedBits = Mask & InMask;
895 // If any of the sign extended bits are demanded, we know that the sign
898 InDemandedBits |= InSignBit;
900 ComputeMaskedBits(Op.getOperand(0), InDemandedBits, KnownZero,
902 // If the sign bit is known zero or one, the top bits match.
903 if (KnownZero & InSignBit) {
904 KnownZero |= NewBits;
905 KnownOne &= ~NewBits;
906 } else if (KnownOne & InSignBit) {
908 KnownZero &= ~NewBits;
909 } else { // Otherwise, top bits aren't known.
910 KnownOne &= ~NewBits;
911 KnownZero &= ~NewBits;
915 case ISD::ANY_EXTEND: {
916 MVT::ValueType VT = Op.getOperand(0).getValueType();
917 ComputeMaskedBits(Op.getOperand(0), Mask & MVT::getIntVTBitMask(VT),
918 KnownZero, KnownOne, Depth+1);
921 case ISD::TRUNCATE: {
922 ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero, KnownOne, Depth+1);
923 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
924 uint64_t OutMask = MVT::getIntVTBitMask(Op.getValueType());
925 KnownZero &= OutMask;
929 case ISD::AssertZext: {
930 MVT::ValueType VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
931 uint64_t InMask = MVT::getIntVTBitMask(VT);
932 ComputeMaskedBits(Op.getOperand(0), Mask & InMask, KnownZero,
934 KnownZero |= (~InMask) & Mask;
938 // If either the LHS or the RHS are Zero, the result is zero.
939 ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1);
940 ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero2, KnownOne2, Depth+1);
941 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
942 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
944 // Output known-0 bits are known if clear or set in both the low clear bits
945 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
947 uint64_t KnownZeroOut = std::min(CountTrailingZeros_64(~KnownZero),
948 CountTrailingZeros_64(~KnownZero2));
950 KnownZero = (1ULL << KnownZeroOut) - 1;
955 ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0));
958 // We know that the top bits of C-X are clear if X contains less bits
959 // than C (i.e. no wrap-around can happen). For example, 20-X is
960 // positive if we can prove that X is >= 0 and < 16.
961 MVT::ValueType VT = CLHS->getValueType(0);
962 if ((CLHS->getValue() & MVT::getIntVTSignBit(VT)) == 0) { // sign bit clear
963 unsigned NLZ = CountLeadingZeros_64(CLHS->getValue()+1);
964 uint64_t MaskV = (1ULL << (63-NLZ))-1; // NLZ can't be 64 with no sign bit
965 MaskV = ~MaskV & MVT::getIntVTBitMask(VT);
966 ComputeMaskedBits(Op.getOperand(1), MaskV, KnownZero, KnownOne, Depth+1);
968 // If all of the MaskV bits are known to be zero, then we know the output
969 // top bits are zero, because we now know that the output is from [0-C].
970 if ((KnownZero & MaskV) == MaskV) {
971 unsigned NLZ2 = CountLeadingZeros_64(CLHS->getValue());
972 KnownZero = ~((1ULL << (64-NLZ2))-1) & Mask; // Top bits known zero.
973 KnownOne = 0; // No one bits known.
975 KnownOne = KnownOne = 0; // Otherwise, nothing known.
981 // Allow the target to implement this method for its nodes.
982 if (Op.getOpcode() >= ISD::BUILTIN_OP_END) {
983 case ISD::INTRINSIC_WO_CHAIN:
984 case ISD::INTRINSIC_W_CHAIN:
985 case ISD::INTRINSIC_VOID:
986 computeMaskedBitsForTargetNode(Op, Mask, KnownZero, KnownOne);
992 /// computeMaskedBitsForTargetNode - Determine which of the bits specified
993 /// in Mask are known to be either zero or one and return them in the
994 /// KnownZero/KnownOne bitsets.
995 void TargetLowering::computeMaskedBitsForTargetNode(const SDOperand Op,
999 unsigned Depth) const {
1000 assert((Op.getOpcode() >= ISD::BUILTIN_OP_END ||
1001 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
1002 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
1003 Op.getOpcode() == ISD::INTRINSIC_VOID) &&
1004 "Should use MaskedValueIsZero if you don't know whether Op"
1005 " is a target node!");
1010 /// ComputeNumSignBits - Return the number of times the sign bit of the
1011 /// register is replicated into the other bits. We know that at least 1 bit
1012 /// is always equal to the sign bit (itself), but other cases can give us
1013 /// information. For example, immediately after an "SRA X, 2", we know that
1014 /// the top 3 bits are all equal to each other, so we return 3.
1015 unsigned TargetLowering::ComputeNumSignBits(SDOperand Op, unsigned Depth) const{
1016 MVT::ValueType VT = Op.getValueType();
1017 assert(MVT::isInteger(VT) && "Invalid VT!");
1018 unsigned VTBits = MVT::getSizeInBits(VT);
1022 return 1; // Limit search depth.
1024 switch (Op.getOpcode()) {
1026 case ISD::AssertSext:
1027 Tmp = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(1))->getVT());
1028 return VTBits-Tmp+1;
1029 case ISD::AssertZext:
1030 Tmp = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(1))->getVT());
1033 case ISD::SEXTLOAD: // '17' bits known
1034 Tmp = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(3))->getVT());
1035 return VTBits-Tmp+1;
1036 case ISD::ZEXTLOAD: // '16' bits known
1037 Tmp = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(3))->getVT());
1040 case ISD::Constant: {
1041 uint64_t Val = cast<ConstantSDNode>(Op)->getValue();
1042 // If negative, invert the bits, then look at it.
1043 if (Val & MVT::getIntVTSignBit(VT))
1046 // Shift the bits so they are the leading bits in the int64_t.
1049 // Return # leading zeros. We use 'min' here in case Val was zero before
1050 // shifting. We don't want to return '64' as for an i32 "0".
1051 return std::min(VTBits, CountLeadingZeros_64(Val));
1054 case ISD::SIGN_EXTEND:
1055 Tmp = VTBits-MVT::getSizeInBits(Op.getOperand(0).getValueType());
1056 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
1058 case ISD::SIGN_EXTEND_INREG:
1059 // Max of the input and what this extends.
1060 Tmp = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(1))->getVT());
1063 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1064 return std::max(Tmp, Tmp2);
1067 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1068 // SRA X, C -> adds C sign bits.
1069 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1070 Tmp += C->getValue();
1071 if (Tmp > VTBits) Tmp = VTBits;
1075 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1076 // shl destroys sign bits.
1077 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1078 if (C->getValue() >= VTBits || // Bad shift.
1079 C->getValue() >= Tmp) break; // Shifted all sign bits out.
1080 return Tmp - C->getValue();
1085 case ISD::XOR: // NOT is handled here.
1086 // Logical binary ops preserve the number of sign bits.
1087 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1088 if (Tmp == 1) return 1; // Early out.
1089 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
1090 return std::min(Tmp, Tmp2);
1093 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1094 if (Tmp == 1) return 1; // Early out.
1095 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
1096 return std::min(Tmp, Tmp2);
1099 // If setcc returns 0/-1, all bits are sign bits.
1100 if (getSetCCResultContents() == ZeroOrNegativeOneSetCCResult)
1105 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1106 unsigned RotAmt = C->getValue() & (VTBits-1);
1108 // Handle rotate right by N like a rotate left by 32-N.
1109 if (Op.getOpcode() == ISD::ROTR)
1110 RotAmt = (VTBits-RotAmt) & (VTBits-1);
1112 // If we aren't rotating out all of the known-in sign bits, return the
1113 // number that are left. This handles rotl(sext(x), 1) for example.
1114 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1115 if (Tmp > RotAmt+1) return Tmp-RotAmt;
1119 // Add can have at most one carry bit. Thus we know that the output
1120 // is, at worst, one more bit than the inputs.
1121 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1122 if (Tmp == 1) return 1; // Early out.
1124 // Special case decrementing a value (ADD X, -1):
1125 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
1126 if (CRHS->isAllOnesValue()) {
1127 uint64_t KnownZero, KnownOne;
1128 uint64_t Mask = MVT::getIntVTBitMask(VT);
1129 ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero, KnownOne, Depth+1);
1131 // If the input is known to be 0 or 1, the output is 0/-1, which is all
1133 if ((KnownZero|1) == Mask)
1136 // If we are subtracting one from a positive number, there is no carry
1137 // out of the result.
1138 if (KnownZero & MVT::getIntVTSignBit(VT))
1142 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
1143 if (Tmp2 == 1) return 1;
1144 return std::min(Tmp, Tmp2)-1;
1148 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
1149 if (Tmp2 == 1) return 1;
1152 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
1153 if (CLHS->getValue() == 0) {
1154 uint64_t KnownZero, KnownOne;
1155 uint64_t Mask = MVT::getIntVTBitMask(VT);
1156 ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1);
1157 // If the input is known to be 0 or 1, the output is 0/-1, which is all
1159 if ((KnownZero|1) == Mask)
1162 // If the input is known to be positive (the sign bit is known clear),
1163 // the output of the NEG has the same number of sign bits as the input.
1164 if (KnownZero & MVT::getIntVTSignBit(VT))
1167 // Otherwise, we treat this like a SUB.
1170 // Sub can have at most one carry bit. Thus we know that the output
1171 // is, at worst, one more bit than the inputs.
1172 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1173 if (Tmp == 1) return 1; // Early out.
1174 return std::min(Tmp, Tmp2)-1;
1177 // FIXME: it's tricky to do anything useful for this, but it is an important
1178 // case for targets like X86.
1182 // Allow the target to implement this method for its nodes.
1183 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
1184 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
1185 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
1186 Op.getOpcode() == ISD::INTRINSIC_VOID) {
1187 unsigned NumBits = ComputeNumSignBitsForTargetNode(Op, Depth);
1188 if (NumBits > 1) return NumBits;
1191 // Finally, if we can prove that the top bits of the result are 0's or 1's,
1192 // use this information.
1193 uint64_t KnownZero, KnownOne;
1194 uint64_t Mask = MVT::getIntVTBitMask(VT);
1195 ComputeMaskedBits(Op, Mask, KnownZero, KnownOne, Depth);
1197 uint64_t SignBit = MVT::getIntVTSignBit(VT);
1198 if (KnownZero & SignBit) { // SignBit is 0
1200 } else if (KnownOne & SignBit) { // SignBit is 1;
1207 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
1208 // the number of identical bits in the top of the input value.
1211 // Return # leading zeros. We use 'min' here in case Val was zero before
1212 // shifting. We don't want to return '64' as for an i32 "0".
1213 return std::min(VTBits, CountLeadingZeros_64(Mask));
1218 /// ComputeNumSignBitsForTargetNode - This method can be implemented by
1219 /// targets that want to expose additional information about sign bits to the
1221 unsigned TargetLowering::ComputeNumSignBitsForTargetNode(SDOperand Op,
1222 unsigned Depth) const {
1223 assert((Op.getOpcode() >= ISD::BUILTIN_OP_END ||
1224 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
1225 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
1226 Op.getOpcode() == ISD::INTRINSIC_VOID) &&
1227 "Should use ComputeNumSignBits if you don't know whether Op"
1228 " is a target node!");
1233 SDOperand TargetLowering::
1234 PerformDAGCombine(SDNode *N, DAGCombinerInfo &DCI) const {
1235 // Default implementation: no optimization.
1239 //===----------------------------------------------------------------------===//
1240 // Inline Assembler Implementation Methods
1241 //===----------------------------------------------------------------------===//
1243 TargetLowering::ConstraintType
1244 TargetLowering::getConstraintType(char ConstraintLetter) const {
1245 // FIXME: lots more standard ones to handle.
1246 switch (ConstraintLetter) {
1247 default: return C_Unknown;
1248 case 'r': return C_RegisterClass;
1250 case 'o': // offsetable
1251 case 'V': // not offsetable
1253 case 'i': // Simple Integer or Relocatable Constant
1254 case 'n': // Simple Integer
1255 case 's': // Relocatable Constant
1256 case 'I': // Target registers.
1268 bool TargetLowering::isOperandValidForConstraint(SDOperand Op,
1269 char ConstraintLetter) {
1270 switch (ConstraintLetter) {
1271 default: return false;
1272 case 'i': // Simple Integer or Relocatable Constant
1273 case 'n': // Simple Integer
1274 case 's': // Relocatable Constant
1275 return true; // FIXME: not right.
1280 std::vector<unsigned> TargetLowering::
1281 getRegClassForInlineAsmConstraint(const std::string &Constraint,
1282 MVT::ValueType VT) const {
1283 return std::vector<unsigned>();
1287 std::pair<unsigned, const TargetRegisterClass*> TargetLowering::
1288 getRegForInlineAsmConstraint(const std::string &Constraint,
1289 MVT::ValueType VT) const {
1290 if (Constraint[0] != '{')
1291 return std::pair<unsigned, const TargetRegisterClass*>(0, 0);
1292 assert(*(Constraint.end()-1) == '}' && "Not a brace enclosed constraint?");
1294 // Remove the braces from around the name.
1295 std::string RegName(Constraint.begin()+1, Constraint.end()-1);
1297 // Figure out which register class contains this reg.
1298 const MRegisterInfo *RI = TM.getRegisterInfo();
1299 for (MRegisterInfo::regclass_iterator RCI = RI->regclass_begin(),
1300 E = RI->regclass_end(); RCI != E; ++RCI) {
1301 const TargetRegisterClass *RC = *RCI;
1303 // If none of the the value types for this register class are valid, we
1304 // can't use it. For example, 64-bit reg classes on 32-bit targets.
1305 bool isLegal = false;
1306 for (TargetRegisterClass::vt_iterator I = RC->vt_begin(), E = RC->vt_end();
1308 if (isTypeLegal(*I)) {
1314 if (!isLegal) continue;
1316 for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end();
1318 if (StringsEqualNoCase(RegName, RI->get(*I).Name))
1319 return std::make_pair(*I, RC);
1323 return std::pair<unsigned, const TargetRegisterClass*>(0, 0);
1326 //===----------------------------------------------------------------------===//
1327 // Loop Strength Reduction hooks
1328 //===----------------------------------------------------------------------===//
1330 /// isLegalAddressImmediate - Return true if the integer value or
1331 /// GlobalValue can be used as the offset of the target addressing mode.
1332 bool TargetLowering::isLegalAddressImmediate(int64_t V) const {
1335 bool TargetLowering::isLegalAddressImmediate(GlobalValue *GV) const {
1340 // Magic for divide replacement
1343 int64_t m; // magic number
1344 int64_t s; // shift amount
1348 uint64_t m; // magic number
1349 int64_t a; // add indicator
1350 int64_t s; // shift amount
1353 /// magic - calculate the magic numbers required to codegen an integer sdiv as
1354 /// a sequence of multiply and shifts. Requires that the divisor not be 0, 1,
1356 static ms magic32(int32_t d) {
1358 uint32_t ad, anc, delta, q1, r1, q2, r2, t;
1359 const uint32_t two31 = 0x80000000U;
1363 t = two31 + ((uint32_t)d >> 31);
1364 anc = t - 1 - t%ad; // absolute value of nc
1365 p = 31; // initialize p
1366 q1 = two31/anc; // initialize q1 = 2p/abs(nc)
1367 r1 = two31 - q1*anc; // initialize r1 = rem(2p,abs(nc))
1368 q2 = two31/ad; // initialize q2 = 2p/abs(d)
1369 r2 = two31 - q2*ad; // initialize r2 = rem(2p,abs(d))
1372 q1 = 2*q1; // update q1 = 2p/abs(nc)
1373 r1 = 2*r1; // update r1 = rem(2p/abs(nc))
1374 if (r1 >= anc) { // must be unsigned comparison
1378 q2 = 2*q2; // update q2 = 2p/abs(d)
1379 r2 = 2*r2; // update r2 = rem(2p/abs(d))
1380 if (r2 >= ad) { // must be unsigned comparison
1385 } while (q1 < delta || (q1 == delta && r1 == 0));
1387 mag.m = (int32_t)(q2 + 1); // make sure to sign extend
1388 if (d < 0) mag.m = -mag.m; // resulting magic number
1389 mag.s = p - 32; // resulting shift
1393 /// magicu - calculate the magic numbers required to codegen an integer udiv as
1394 /// a sequence of multiply, add and shifts. Requires that the divisor not be 0.
1395 static mu magicu32(uint32_t d) {
1397 uint32_t nc, delta, q1, r1, q2, r2;
1399 magu.a = 0; // initialize "add" indicator
1401 p = 31; // initialize p
1402 q1 = 0x80000000/nc; // initialize q1 = 2p/nc
1403 r1 = 0x80000000 - q1*nc; // initialize r1 = rem(2p,nc)
1404 q2 = 0x7FFFFFFF/d; // initialize q2 = (2p-1)/d
1405 r2 = 0x7FFFFFFF - q2*d; // initialize r2 = rem((2p-1),d)
1408 if (r1 >= nc - r1 ) {
1409 q1 = 2*q1 + 1; // update q1
1410 r1 = 2*r1 - nc; // update r1
1413 q1 = 2*q1; // update q1
1414 r1 = 2*r1; // update r1
1416 if (r2 + 1 >= d - r2) {
1417 if (q2 >= 0x7FFFFFFF) magu.a = 1;
1418 q2 = 2*q2 + 1; // update q2
1419 r2 = 2*r2 + 1 - d; // update r2
1422 if (q2 >= 0x80000000) magu.a = 1;
1423 q2 = 2*q2; // update q2
1424 r2 = 2*r2 + 1; // update r2
1427 } while (p < 64 && (q1 < delta || (q1 == delta && r1 == 0)));
1428 magu.m = q2 + 1; // resulting magic number
1429 magu.s = p - 32; // resulting shift
1433 /// magic - calculate the magic numbers required to codegen an integer sdiv as
1434 /// a sequence of multiply and shifts. Requires that the divisor not be 0, 1,
1436 static ms magic64(int64_t d) {
1438 uint64_t ad, anc, delta, q1, r1, q2, r2, t;
1439 const uint64_t two63 = 9223372036854775808ULL; // 2^63
1442 ad = d >= 0 ? d : -d;
1443 t = two63 + ((uint64_t)d >> 63);
1444 anc = t - 1 - t%ad; // absolute value of nc
1445 p = 63; // initialize p
1446 q1 = two63/anc; // initialize q1 = 2p/abs(nc)
1447 r1 = two63 - q1*anc; // initialize r1 = rem(2p,abs(nc))
1448 q2 = two63/ad; // initialize q2 = 2p/abs(d)
1449 r2 = two63 - q2*ad; // initialize r2 = rem(2p,abs(d))
1452 q1 = 2*q1; // update q1 = 2p/abs(nc)
1453 r1 = 2*r1; // update r1 = rem(2p/abs(nc))
1454 if (r1 >= anc) { // must be unsigned comparison
1458 q2 = 2*q2; // update q2 = 2p/abs(d)
1459 r2 = 2*r2; // update r2 = rem(2p/abs(d))
1460 if (r2 >= ad) { // must be unsigned comparison
1465 } while (q1 < delta || (q1 == delta && r1 == 0));
1468 if (d < 0) mag.m = -mag.m; // resulting magic number
1469 mag.s = p - 64; // resulting shift
1473 /// magicu - calculate the magic numbers required to codegen an integer udiv as
1474 /// a sequence of multiply, add and shifts. Requires that the divisor not be 0.
1475 static mu magicu64(uint64_t d)
1478 uint64_t nc, delta, q1, r1, q2, r2;
1480 magu.a = 0; // initialize "add" indicator
1482 p = 63; // initialize p
1483 q1 = 0x8000000000000000ull/nc; // initialize q1 = 2p/nc
1484 r1 = 0x8000000000000000ull - q1*nc; // initialize r1 = rem(2p,nc)
1485 q2 = 0x7FFFFFFFFFFFFFFFull/d; // initialize q2 = (2p-1)/d
1486 r2 = 0x7FFFFFFFFFFFFFFFull - q2*d; // initialize r2 = rem((2p-1),d)
1489 if (r1 >= nc - r1 ) {
1490 q1 = 2*q1 + 1; // update q1
1491 r1 = 2*r1 - nc; // update r1
1494 q1 = 2*q1; // update q1
1495 r1 = 2*r1; // update r1
1497 if (r2 + 1 >= d - r2) {
1498 if (q2 >= 0x7FFFFFFFFFFFFFFFull) magu.a = 1;
1499 q2 = 2*q2 + 1; // update q2
1500 r2 = 2*r2 + 1 - d; // update r2
1503 if (q2 >= 0x8000000000000000ull) magu.a = 1;
1504 q2 = 2*q2; // update q2
1505 r2 = 2*r2 + 1; // update r2
1508 } while (p < 128 && (q1 < delta || (q1 == delta && r1 == 0)));
1509 magu.m = q2 + 1; // resulting magic number
1510 magu.s = p - 64; // resulting shift
1514 /// BuildSDIVSequence - Given an ISD::SDIV node expressing a divide by constant,
1515 /// return a DAG expression to select that will generate the same value by
1516 /// multiplying by a magic number. See:
1517 /// <http://the.wall.riscom.net/books/proc/ppc/cwg/code2.html>
1518 SDOperand TargetLowering::BuildSDIV(SDNode *N, SelectionDAG &DAG,
1519 std::vector<SDNode*>* Created) const {
1520 MVT::ValueType VT = N->getValueType(0);
1522 // Check to see if we can do this.
1523 if (!isTypeLegal(VT) || (VT != MVT::i32 && VT != MVT::i64))
1524 return SDOperand(); // BuildSDIV only operates on i32 or i64
1525 if (!isOperationLegal(ISD::MULHS, VT))
1526 return SDOperand(); // Make sure the target supports MULHS.
1528 int64_t d = cast<ConstantSDNode>(N->getOperand(1))->getSignExtended();
1529 ms magics = (VT == MVT::i32) ? magic32(d) : magic64(d);
1531 // Multiply the numerator (operand 0) by the magic value
1532 SDOperand Q = DAG.getNode(ISD::MULHS, VT, N->getOperand(0),
1533 DAG.getConstant(magics.m, VT));
1534 // If d > 0 and m < 0, add the numerator
1535 if (d > 0 && magics.m < 0) {
1536 Q = DAG.getNode(ISD::ADD, VT, Q, N->getOperand(0));
1538 Created->push_back(Q.Val);
1540 // If d < 0 and m > 0, subtract the numerator.
1541 if (d < 0 && magics.m > 0) {
1542 Q = DAG.getNode(ISD::SUB, VT, Q, N->getOperand(0));
1544 Created->push_back(Q.Val);
1546 // Shift right algebraic if shift value is nonzero
1548 Q = DAG.getNode(ISD::SRA, VT, Q,
1549 DAG.getConstant(magics.s, getShiftAmountTy()));
1551 Created->push_back(Q.Val);
1553 // Extract the sign bit and add it to the quotient
1555 DAG.getNode(ISD::SRL, VT, Q, DAG.getConstant(MVT::getSizeInBits(VT)-1,
1556 getShiftAmountTy()));
1558 Created->push_back(T.Val);
1559 return DAG.getNode(ISD::ADD, VT, Q, T);
1562 /// BuildUDIVSequence - Given an ISD::UDIV node expressing a divide by constant,
1563 /// return a DAG expression to select that will generate the same value by
1564 /// multiplying by a magic number. See:
1565 /// <http://the.wall.riscom.net/books/proc/ppc/cwg/code2.html>
1566 SDOperand TargetLowering::BuildUDIV(SDNode *N, SelectionDAG &DAG,
1567 std::vector<SDNode*>* Created) const {
1568 MVT::ValueType VT = N->getValueType(0);
1570 // Check to see if we can do this.
1571 if (!isTypeLegal(VT) || (VT != MVT::i32 && VT != MVT::i64))
1572 return SDOperand(); // BuildUDIV only operates on i32 or i64
1573 if (!isOperationLegal(ISD::MULHU, VT))
1574 return SDOperand(); // Make sure the target supports MULHU.
1576 uint64_t d = cast<ConstantSDNode>(N->getOperand(1))->getValue();
1577 mu magics = (VT == MVT::i32) ? magicu32(d) : magicu64(d);
1579 // Multiply the numerator (operand 0) by the magic value
1580 SDOperand Q = DAG.getNode(ISD::MULHU, VT, N->getOperand(0),
1581 DAG.getConstant(magics.m, VT));
1583 Created->push_back(Q.Val);
1585 if (magics.a == 0) {
1586 return DAG.getNode(ISD::SRL, VT, Q,
1587 DAG.getConstant(magics.s, getShiftAmountTy()));
1589 SDOperand NPQ = DAG.getNode(ISD::SUB, VT, N->getOperand(0), Q);
1591 Created->push_back(NPQ.Val);
1592 NPQ = DAG.getNode(ISD::SRL, VT, NPQ,
1593 DAG.getConstant(1, getShiftAmountTy()));
1595 Created->push_back(NPQ.Val);
1596 NPQ = DAG.getNode(ISD::ADD, VT, NPQ, Q);
1598 Created->push_back(NPQ.Val);
1599 return DAG.getNode(ISD::SRL, VT, NPQ,
1600 DAG.getConstant(magics.s-1, getShiftAmountTy()));