TargetLowering.cpp revision e60351bb72938117a0a0dd6fe2844381e9ec4ca9
1//===-- TargetLowering.cpp - Implement the TargetLowering class -----------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by the LLVM research group and is distributed under 6// the University of Illinois Open Source License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This implements the TargetLowering class. 11// 12//===----------------------------------------------------------------------===// 13 14#include "llvm/Target/TargetLowering.h" 15#include "llvm/Target/TargetMachine.h" 16#include "llvm/Target/MRegisterInfo.h" 17#include "llvm/DerivedTypes.h" 18#include "llvm/CodeGen/SelectionDAG.h" 19#include "llvm/ADT/StringExtras.h" 20#include "llvm/Support/MathExtras.h" 21using namespace llvm; 22 23TargetLowering::TargetLowering(TargetMachine &tm) 24 : TM(tm), TD(TM.getTargetData()) { 25 assert(ISD::BUILTIN_OP_END <= 156 && 26 "Fixed size array in TargetLowering is not large enough!"); 27 // All operations default to being supported. 28 memset(OpActions, 0, sizeof(OpActions)); 29 30 IsLittleEndian = TD->isLittleEndian(); 31 ShiftAmountTy = SetCCResultTy = PointerTy = getValueType(TD->getIntPtrType()); 32 ShiftAmtHandling = Undefined; 33 memset(RegClassForVT, 0,MVT::LAST_VALUETYPE*sizeof(TargetRegisterClass*)); 34 memset(TargetDAGCombineArray, 0, 35 sizeof(TargetDAGCombineArray)/sizeof(TargetDAGCombineArray[0])); 36 maxStoresPerMemset = maxStoresPerMemcpy = maxStoresPerMemmove = 8; 37 allowUnalignedMemoryAccesses = false; 38 UseUnderscoreSetJmpLongJmp = false; 39 IntDivIsCheap = false; 40 Pow2DivIsCheap = false; 41 StackPointerRegisterToSaveRestore = 0; 42 SchedPreferenceInfo = SchedulingForLatency; 43} 44 45TargetLowering::~TargetLowering() {} 46 47/// setValueTypeAction - Set the action for a particular value type. This 48/// assumes an action has not already been set for this value type. 49static void SetValueTypeAction(MVT::ValueType VT, 50 TargetLowering::LegalizeAction Action, 51 TargetLowering &TLI, 52 MVT::ValueType *TransformToType, 53 TargetLowering::ValueTypeActionImpl &ValueTypeActions) { 54 ValueTypeActions.setTypeAction(VT, Action); 55 if (Action == TargetLowering::Promote) { 56 MVT::ValueType PromoteTo; 57 if (VT == MVT::f32) 58 PromoteTo = MVT::f64; 59 else { 60 unsigned LargerReg = VT+1; 61 while (!TLI.isTypeLegal((MVT::ValueType)LargerReg)) { 62 ++LargerReg; 63 assert(MVT::isInteger((MVT::ValueType)LargerReg) && 64 "Nothing to promote to??"); 65 } 66 PromoteTo = (MVT::ValueType)LargerReg; 67 } 68 69 assert(MVT::isInteger(VT) == MVT::isInteger(PromoteTo) && 70 MVT::isFloatingPoint(VT) == MVT::isFloatingPoint(PromoteTo) && 71 "Can only promote from int->int or fp->fp!"); 72 assert(VT < PromoteTo && "Must promote to a larger type!"); 73 TransformToType[VT] = PromoteTo; 74 } else if (Action == TargetLowering::Expand) { 75 assert((VT == MVT::Vector || MVT::isInteger(VT)) && VT > MVT::i8 && 76 "Cannot expand this type: target must support SOME integer reg!"); 77 // Expand to the next smaller integer type! 78 TransformToType[VT] = (MVT::ValueType)(VT-1); 79 } 80} 81 82 83/// computeRegisterProperties - Once all of the register classes are added, 84/// this allows us to compute derived properties we expose. 85void TargetLowering::computeRegisterProperties() { 86 assert(MVT::LAST_VALUETYPE <= 32 && 87 "Too many value types for ValueTypeActions to hold!"); 88 89 // Everything defaults to one. 90 for (unsigned i = 0; i != MVT::LAST_VALUETYPE; ++i) 91 NumElementsForVT[i] = 1; 92 93 // Find the largest integer register class. 94 unsigned LargestIntReg = MVT::i128; 95 for (; RegClassForVT[LargestIntReg] == 0; --LargestIntReg) 96 assert(LargestIntReg != MVT::i1 && "No integer registers defined!"); 97 98 // Every integer value type larger than this largest register takes twice as 99 // many registers to represent as the previous ValueType. 100 unsigned ExpandedReg = LargestIntReg; ++LargestIntReg; 101 for (++ExpandedReg; MVT::isInteger((MVT::ValueType)ExpandedReg);++ExpandedReg) 102 NumElementsForVT[ExpandedReg] = 2*NumElementsForVT[ExpandedReg-1]; 103 104 // Inspect all of the ValueType's possible, deciding how to process them. 105 for (unsigned IntReg = MVT::i1; IntReg <= MVT::i128; ++IntReg) 106 // If we are expanding this type, expand it! 107 if (getNumElements((MVT::ValueType)IntReg) != 1) 108 SetValueTypeAction((MVT::ValueType)IntReg, Expand, *this, TransformToType, 109 ValueTypeActions); 110 else if (!isTypeLegal((MVT::ValueType)IntReg)) 111 // Otherwise, if we don't have native support, we must promote to a 112 // larger type. 113 SetValueTypeAction((MVT::ValueType)IntReg, Promote, *this, 114 TransformToType, ValueTypeActions); 115 else 116 TransformToType[(MVT::ValueType)IntReg] = (MVT::ValueType)IntReg; 117 118 // If the target does not have native support for F32, promote it to F64. 119 if (!isTypeLegal(MVT::f32)) 120 SetValueTypeAction(MVT::f32, Promote, *this, 121 TransformToType, ValueTypeActions); 122 else 123 TransformToType[MVT::f32] = MVT::f32; 124 125 // Set MVT::Vector to always be Expanded 126 SetValueTypeAction(MVT::Vector, Expand, *this, TransformToType, 127 ValueTypeActions); 128 129 // Loop over all of the legal vector value types, specifying an identity type 130 // transformation. 131 for (unsigned i = MVT::FIRST_VECTOR_VALUETYPE; 132 i <= MVT::LAST_VECTOR_VALUETYPE; ++i) { 133 if (isTypeLegal((MVT::ValueType)i)) 134 TransformToType[i] = (MVT::ValueType)i; 135 } 136 137 assert(isTypeLegal(MVT::f64) && "Target does not support FP?"); 138 TransformToType[MVT::f64] = MVT::f64; 139} 140 141const char *TargetLowering::getTargetNodeName(unsigned Opcode) const { 142 return NULL; 143} 144 145/// getPackedTypeBreakdown - Packed types are broken down into some number of 146/// legal scalar types. For example, <8 x float> maps to 2 MVT::v2f32 values 147/// with Altivec or SSE1, or 8 promoted MVT::f64 values with the X86 FP stack. 148/// 149/// This method returns the number and type of the resultant breakdown. 150/// 151unsigned TargetLowering::getPackedTypeBreakdown(const PackedType *PTy, 152 MVT::ValueType &PTyElementVT, 153 MVT::ValueType &PTyLegalElementVT) const { 154 // Figure out the right, legal destination reg to copy into. 155 unsigned NumElts = PTy->getNumElements(); 156 MVT::ValueType EltTy = getValueType(PTy->getElementType()); 157 158 unsigned NumVectorRegs = 1; 159 160 // Divide the input until we get to a supported size. This will always 161 // end with a scalar if the target doesn't support vectors. 162 while (NumElts > 1 && !isTypeLegal(getVectorType(EltTy, NumElts))) { 163 NumElts >>= 1; 164 NumVectorRegs <<= 1; 165 } 166 167 MVT::ValueType VT; 168 if (NumElts == 1) { 169 VT = EltTy; 170 } else { 171 VT = getVectorType(EltTy, NumElts); 172 } 173 PTyElementVT = VT; 174 175 MVT::ValueType DestVT = getTypeToTransformTo(VT); 176 PTyLegalElementVT = DestVT; 177 if (DestVT < VT) { 178 // Value is expanded, e.g. i64 -> i16. 179 return NumVectorRegs*(MVT::getSizeInBits(VT)/MVT::getSizeInBits(DestVT)); 180 } else { 181 // Otherwise, promotion or legal types use the same number of registers as 182 // the vector decimated to the appropriate level. 183 return NumVectorRegs; 184 } 185 186 return DestVT; 187} 188 189//===----------------------------------------------------------------------===// 190// Optimization Methods 191//===----------------------------------------------------------------------===// 192 193/// ShrinkDemandedConstant - Check to see if the specified operand of the 194/// specified instruction is a constant integer. If so, check to see if there 195/// are any bits set in the constant that are not demanded. If so, shrink the 196/// constant and return true. 197bool TargetLowering::TargetLoweringOpt::ShrinkDemandedConstant(SDOperand Op, 198 uint64_t Demanded) { 199 // FIXME: ISD::SELECT, ISD::SELECT_CC 200 switch(Op.getOpcode()) { 201 default: break; 202 case ISD::AND: 203 case ISD::OR: 204 case ISD::XOR: 205 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) 206 if ((~Demanded & C->getValue()) != 0) { 207 MVT::ValueType VT = Op.getValueType(); 208 SDOperand New = DAG.getNode(Op.getOpcode(), VT, Op.getOperand(0), 209 DAG.getConstant(Demanded & C->getValue(), 210 VT)); 211 return CombineTo(Op, New); 212 } 213 break; 214 } 215 return false; 216} 217 218/// SimplifyDemandedBits - Look at Op. At this point, we know that only the 219/// DemandedMask bits of the result of Op are ever used downstream. If we can 220/// use this information to simplify Op, create a new simplified DAG node and 221/// return true, returning the original and new nodes in Old and New. Otherwise, 222/// analyze the expression and return a mask of KnownOne and KnownZero bits for 223/// the expression (used to simplify the caller). The KnownZero/One bits may 224/// only be accurate for those bits in the DemandedMask. 225bool TargetLowering::SimplifyDemandedBits(SDOperand Op, uint64_t DemandedMask, 226 uint64_t &KnownZero, 227 uint64_t &KnownOne, 228 TargetLoweringOpt &TLO, 229 unsigned Depth) const { 230 KnownZero = KnownOne = 0; // Don't know anything. 231 // Other users may use these bits. 232 if (!Op.Val->hasOneUse()) { 233 if (Depth != 0) { 234 // If not at the root, Just compute the KnownZero/KnownOne bits to 235 // simplify things downstream. 236 ComputeMaskedBits(Op, DemandedMask, KnownZero, KnownOne, Depth); 237 return false; 238 } 239 // If this is the root being simplified, allow it to have multiple uses, 240 // just set the DemandedMask to all bits. 241 DemandedMask = MVT::getIntVTBitMask(Op.getValueType()); 242 } else if (DemandedMask == 0) { 243 // Not demanding any bits from Op. 244 if (Op.getOpcode() != ISD::UNDEF) 245 return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::UNDEF, Op.getValueType())); 246 return false; 247 } else if (Depth == 6) { // Limit search depth. 248 return false; 249 } 250 251 uint64_t KnownZero2, KnownOne2, KnownZeroOut, KnownOneOut; 252 switch (Op.getOpcode()) { 253 case ISD::Constant: 254 // We know all of the bits for a constant! 255 KnownOne = cast<ConstantSDNode>(Op)->getValue() & DemandedMask; 256 KnownZero = ~KnownOne & DemandedMask; 257 return false; // Don't fall through, will infinitely loop. 258 case ISD::AND: 259 // If the RHS is a constant, check to see if the LHS would be zero without 260 // using the bits from the RHS. Below, we use knowledge about the RHS to 261 // simplify the LHS, here we're using information from the LHS to simplify 262 // the RHS. 263 if (ConstantSDNode *RHSC = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 264 uint64_t LHSZero, LHSOne; 265 ComputeMaskedBits(Op.getOperand(0), DemandedMask, 266 LHSZero, LHSOne, Depth+1); 267 // If the LHS already has zeros where RHSC does, this and is dead. 268 if ((LHSZero & DemandedMask) == (~RHSC->getValue() & DemandedMask)) 269 return TLO.CombineTo(Op, Op.getOperand(0)); 270 // If any of the set bits in the RHS are known zero on the LHS, shrink 271 // the constant. 272 if (TLO.ShrinkDemandedConstant(Op, ~LHSZero & DemandedMask)) 273 return true; 274 } 275 276 if (SimplifyDemandedBits(Op.getOperand(1), DemandedMask, KnownZero, 277 KnownOne, TLO, Depth+1)) 278 return true; 279 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 280 if (SimplifyDemandedBits(Op.getOperand(0), DemandedMask & ~KnownZero, 281 KnownZero2, KnownOne2, TLO, Depth+1)) 282 return true; 283 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 284 285 // If all of the demanded bits are known one on one side, return the other. 286 // These bits cannot contribute to the result of the 'and'. 287 if ((DemandedMask & ~KnownZero2 & KnownOne)==(DemandedMask & ~KnownZero2)) 288 return TLO.CombineTo(Op, Op.getOperand(0)); 289 if ((DemandedMask & ~KnownZero & KnownOne2)==(DemandedMask & ~KnownZero)) 290 return TLO.CombineTo(Op, Op.getOperand(1)); 291 // If all of the demanded bits in the inputs are known zeros, return zero. 292 if ((DemandedMask & (KnownZero|KnownZero2)) == DemandedMask) 293 return TLO.CombineTo(Op, TLO.DAG.getConstant(0, Op.getValueType())); 294 // If the RHS is a constant, see if we can simplify it. 295 if (TLO.ShrinkDemandedConstant(Op, DemandedMask & ~KnownZero2)) 296 return true; 297 298 // Output known-1 bits are only known if set in both the LHS & RHS. 299 KnownOne &= KnownOne2; 300 // Output known-0 are known to be clear if zero in either the LHS | RHS. 301 KnownZero |= KnownZero2; 302 break; 303 case ISD::OR: 304 if (SimplifyDemandedBits(Op.getOperand(1), DemandedMask, KnownZero, 305 KnownOne, TLO, Depth+1)) 306 return true; 307 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 308 if (SimplifyDemandedBits(Op.getOperand(0), DemandedMask & ~KnownOne, 309 KnownZero2, KnownOne2, TLO, Depth+1)) 310 return true; 311 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 312 313 // If all of the demanded bits are known zero on one side, return the other. 314 // These bits cannot contribute to the result of the 'or'. 315 if ((DemandedMask & ~KnownOne2 & KnownZero) == (DemandedMask & ~KnownOne2)) 316 return TLO.CombineTo(Op, Op.getOperand(0)); 317 if ((DemandedMask & ~KnownOne & KnownZero2) == (DemandedMask & ~KnownOne)) 318 return TLO.CombineTo(Op, Op.getOperand(1)); 319 // If all of the potentially set bits on one side are known to be set on 320 // the other side, just use the 'other' side. 321 if ((DemandedMask & (~KnownZero) & KnownOne2) == 322 (DemandedMask & (~KnownZero))) 323 return TLO.CombineTo(Op, Op.getOperand(0)); 324 if ((DemandedMask & (~KnownZero2) & KnownOne) == 325 (DemandedMask & (~KnownZero2))) 326 return TLO.CombineTo(Op, Op.getOperand(1)); 327 // If the RHS is a constant, see if we can simplify it. 328 if (TLO.ShrinkDemandedConstant(Op, DemandedMask)) 329 return true; 330 331 // Output known-0 bits are only known if clear in both the LHS & RHS. 332 KnownZero &= KnownZero2; 333 // Output known-1 are known to be set if set in either the LHS | RHS. 334 KnownOne |= KnownOne2; 335 break; 336 case ISD::XOR: 337 if (SimplifyDemandedBits(Op.getOperand(1), DemandedMask, KnownZero, 338 KnownOne, TLO, Depth+1)) 339 return true; 340 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 341 if (SimplifyDemandedBits(Op.getOperand(0), DemandedMask, KnownZero2, 342 KnownOne2, TLO, Depth+1)) 343 return true; 344 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 345 346 // If all of the demanded bits are known zero on one side, return the other. 347 // These bits cannot contribute to the result of the 'xor'. 348 if ((DemandedMask & KnownZero) == DemandedMask) 349 return TLO.CombineTo(Op, Op.getOperand(0)); 350 if ((DemandedMask & KnownZero2) == DemandedMask) 351 return TLO.CombineTo(Op, Op.getOperand(1)); 352 353 // Output known-0 bits are known if clear or set in both the LHS & RHS. 354 KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2); 355 // Output known-1 are known to be set if set in only one of the LHS, RHS. 356 KnownOneOut = (KnownZero & KnownOne2) | (KnownOne & KnownZero2); 357 358 // If all of the unknown bits are known to be zero on one side or the other 359 // (but not both) turn this into an *inclusive* or. 360 // e.g. (A & C1)^(B & C2) -> (A & C1)|(B & C2) iff C1&C2 == 0 361 if (uint64_t UnknownBits = DemandedMask & ~(KnownZeroOut|KnownOneOut)) 362 if ((UnknownBits & (KnownZero|KnownZero2)) == UnknownBits) 363 return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::OR, Op.getValueType(), 364 Op.getOperand(0), 365 Op.getOperand(1))); 366 // If all of the demanded bits on one side are known, and all of the set 367 // bits on that side are also known to be set on the other side, turn this 368 // into an AND, as we know the bits will be cleared. 369 // e.g. (X | C1) ^ C2 --> (X | C1) & ~C2 iff (C1&C2) == C2 370 if ((DemandedMask & (KnownZero|KnownOne)) == DemandedMask) { // all known 371 if ((KnownOne & KnownOne2) == KnownOne) { 372 MVT::ValueType VT = Op.getValueType(); 373 SDOperand ANDC = TLO.DAG.getConstant(~KnownOne & DemandedMask, VT); 374 return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::AND, VT, Op.getOperand(0), 375 ANDC)); 376 } 377 } 378 379 // If the RHS is a constant, see if we can simplify it. 380 // FIXME: for XOR, we prefer to force bits to 1 if they will make a -1. 381 if (TLO.ShrinkDemandedConstant(Op, DemandedMask)) 382 return true; 383 384 KnownZero = KnownZeroOut; 385 KnownOne = KnownOneOut; 386 break; 387 case ISD::SETCC: 388 // If we know the result of a setcc has the top bits zero, use this info. 389 if (getSetCCResultContents() == TargetLowering::ZeroOrOneSetCCResult) 390 KnownZero |= (MVT::getIntVTBitMask(Op.getValueType()) ^ 1ULL); 391 break; 392 case ISD::SELECT: 393 if (SimplifyDemandedBits(Op.getOperand(2), DemandedMask, KnownZero, 394 KnownOne, TLO, Depth+1)) 395 return true; 396 if (SimplifyDemandedBits(Op.getOperand(1), DemandedMask, KnownZero2, 397 KnownOne2, TLO, Depth+1)) 398 return true; 399 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 400 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 401 402 // If the operands are constants, see if we can simplify them. 403 if (TLO.ShrinkDemandedConstant(Op, DemandedMask)) 404 return true; 405 406 // Only known if known in both the LHS and RHS. 407 KnownOne &= KnownOne2; 408 KnownZero &= KnownZero2; 409 break; 410 case ISD::SELECT_CC: 411 if (SimplifyDemandedBits(Op.getOperand(3), DemandedMask, KnownZero, 412 KnownOne, TLO, Depth+1)) 413 return true; 414 if (SimplifyDemandedBits(Op.getOperand(2), DemandedMask, KnownZero2, 415 KnownOne2, TLO, Depth+1)) 416 return true; 417 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 418 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 419 420 // If the operands are constants, see if we can simplify them. 421 if (TLO.ShrinkDemandedConstant(Op, DemandedMask)) 422 return true; 423 424 // Only known if known in both the LHS and RHS. 425 KnownOne &= KnownOne2; 426 KnownZero &= KnownZero2; 427 break; 428 case ISD::SHL: 429 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 430 if (SimplifyDemandedBits(Op.getOperand(0), DemandedMask >> SA->getValue(), 431 KnownZero, KnownOne, TLO, Depth+1)) 432 return true; 433 KnownZero <<= SA->getValue(); 434 KnownOne <<= SA->getValue(); 435 KnownZero |= (1ULL << SA->getValue())-1; // low bits known zero. 436 } 437 break; 438 case ISD::SRL: 439 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 440 MVT::ValueType VT = Op.getValueType(); 441 unsigned ShAmt = SA->getValue(); 442 443 // Compute the new bits that are at the top now. 444 uint64_t HighBits = (1ULL << ShAmt)-1; 445 HighBits <<= MVT::getSizeInBits(VT) - ShAmt; 446 uint64_t TypeMask = MVT::getIntVTBitMask(VT); 447 448 if (SimplifyDemandedBits(Op.getOperand(0), 449 (DemandedMask << ShAmt) & TypeMask, 450 KnownZero, KnownOne, TLO, Depth+1)) 451 return true; 452 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 453 KnownZero &= TypeMask; 454 KnownOne &= TypeMask; 455 KnownZero >>= ShAmt; 456 KnownOne >>= ShAmt; 457 KnownZero |= HighBits; // high bits known zero. 458 } 459 break; 460 case ISD::SRA: 461 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 462 MVT::ValueType VT = Op.getValueType(); 463 unsigned ShAmt = SA->getValue(); 464 465 // Compute the new bits that are at the top now. 466 uint64_t HighBits = (1ULL << ShAmt)-1; 467 HighBits <<= MVT::getSizeInBits(VT) - ShAmt; 468 uint64_t TypeMask = MVT::getIntVTBitMask(VT); 469 470 if (SimplifyDemandedBits(Op.getOperand(0), 471 (DemandedMask << ShAmt) & TypeMask, 472 KnownZero, KnownOne, TLO, Depth+1)) 473 return true; 474 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 475 KnownZero &= TypeMask; 476 KnownOne &= TypeMask; 477 KnownZero >>= SA->getValue(); 478 KnownOne >>= SA->getValue(); 479 480 // Handle the sign bits. 481 uint64_t SignBit = MVT::getIntVTSignBit(VT); 482 SignBit >>= SA->getValue(); // Adjust to where it is now in the mask. 483 484 // If the input sign bit is known to be zero, or if none of the top bits 485 // are demanded, turn this into an unsigned shift right. 486 if ((KnownZero & SignBit) || (HighBits & ~DemandedMask) == HighBits) { 487 return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::SRL, VT, Op.getOperand(0), 488 Op.getOperand(1))); 489 } else if (KnownOne & SignBit) { // New bits are known one. 490 KnownOne |= HighBits; 491 } 492 } 493 break; 494 case ISD::SIGN_EXTEND_INREG: { 495 MVT::ValueType VT = Op.getValueType(); 496 MVT::ValueType EVT = cast<VTSDNode>(Op.getOperand(1))->getVT(); 497 498 // Sign extension. Compute the demanded bits in the result that are not 499 // present in the input. 500 uint64_t NewBits = ~MVT::getIntVTBitMask(EVT) & DemandedMask; 501 502 // If none of the extended bits are demanded, eliminate the sextinreg. 503 if (NewBits == 0) 504 return TLO.CombineTo(Op, Op.getOperand(0)); 505 506 uint64_t InSignBit = MVT::getIntVTSignBit(EVT); 507 int64_t InputDemandedBits = DemandedMask & MVT::getIntVTBitMask(EVT); 508 509 // Since the sign extended bits are demanded, we know that the sign 510 // bit is demanded. 511 InputDemandedBits |= InSignBit; 512 513 if (SimplifyDemandedBits(Op.getOperand(0), InputDemandedBits, 514 KnownZero, KnownOne, TLO, Depth+1)) 515 return true; 516 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 517 518 // If the sign bit of the input is known set or clear, then we know the 519 // top bits of the result. 520 521 // If the input sign bit is known zero, convert this into a zero extension. 522 if (KnownZero & InSignBit) 523 return TLO.CombineTo(Op, 524 TLO.DAG.getZeroExtendInReg(Op.getOperand(0), EVT)); 525 526 if (KnownOne & InSignBit) { // Input sign bit known set 527 KnownOne |= NewBits; 528 KnownZero &= ~NewBits; 529 } else { // Input sign bit unknown 530 KnownZero &= ~NewBits; 531 KnownOne &= ~NewBits; 532 } 533 break; 534 } 535 case ISD::CTTZ: 536 case ISD::CTLZ: 537 case ISD::CTPOP: { 538 MVT::ValueType VT = Op.getValueType(); 539 unsigned LowBits = Log2_32(MVT::getSizeInBits(VT))+1; 540 KnownZero = ~((1ULL << LowBits)-1) & MVT::getIntVTBitMask(VT); 541 KnownOne = 0; 542 break; 543 } 544 case ISD::ZEXTLOAD: { 545 MVT::ValueType VT = cast<VTSDNode>(Op.getOperand(3))->getVT(); 546 KnownZero |= ~MVT::getIntVTBitMask(VT) & DemandedMask; 547 break; 548 } 549 case ISD::ZERO_EXTEND: { 550 uint64_t InMask = MVT::getIntVTBitMask(Op.getOperand(0).getValueType()); 551 552 // If none of the top bits are demanded, convert this into an any_extend. 553 uint64_t NewBits = (~InMask) & DemandedMask; 554 if (NewBits == 0) 555 return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::ANY_EXTEND, 556 Op.getValueType(), 557 Op.getOperand(0))); 558 559 if (SimplifyDemandedBits(Op.getOperand(0), DemandedMask & InMask, 560 KnownZero, KnownOne, TLO, Depth+1)) 561 return true; 562 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 563 KnownZero |= NewBits; 564 break; 565 } 566 case ISD::SIGN_EXTEND: { 567 MVT::ValueType InVT = Op.getOperand(0).getValueType(); 568 uint64_t InMask = MVT::getIntVTBitMask(InVT); 569 uint64_t InSignBit = MVT::getIntVTSignBit(InVT); 570 uint64_t NewBits = (~InMask) & DemandedMask; 571 572 // If none of the top bits are demanded, convert this into an any_extend. 573 if (NewBits == 0) 574 return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::ANY_EXTEND,Op.getValueType(), 575 Op.getOperand(0))); 576 577 // Since some of the sign extended bits are demanded, we know that the sign 578 // bit is demanded. 579 uint64_t InDemandedBits = DemandedMask & InMask; 580 InDemandedBits |= InSignBit; 581 582 if (SimplifyDemandedBits(Op.getOperand(0), InDemandedBits, KnownZero, 583 KnownOne, TLO, Depth+1)) 584 return true; 585 586 // If the sign bit is known zero, convert this to a zero extend. 587 if (KnownZero & InSignBit) 588 return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::ZERO_EXTEND, 589 Op.getValueType(), 590 Op.getOperand(0))); 591 592 // If the sign bit is known one, the top bits match. 593 if (KnownOne & InSignBit) { 594 KnownOne |= NewBits; 595 KnownZero &= ~NewBits; 596 } else { // Otherwise, top bits aren't known. 597 KnownOne &= ~NewBits; 598 KnownZero &= ~NewBits; 599 } 600 break; 601 } 602 case ISD::ANY_EXTEND: { 603 uint64_t InMask = MVT::getIntVTBitMask(Op.getOperand(0).getValueType()); 604 if (SimplifyDemandedBits(Op.getOperand(0), DemandedMask & InMask, 605 KnownZero, KnownOne, TLO, Depth+1)) 606 return true; 607 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 608 break; 609 } 610 case ISD::TRUNCATE: { 611 // Simplify the input, using demanded bit information, and compute the known 612 // zero/one bits live out. 613 if (SimplifyDemandedBits(Op.getOperand(0), DemandedMask, 614 KnownZero, KnownOne, TLO, Depth+1)) 615 return true; 616 617 // If the input is only used by this truncate, see if we can shrink it based 618 // on the known demanded bits. 619 if (Op.getOperand(0).Val->hasOneUse()) { 620 SDOperand In = Op.getOperand(0); 621 switch (In.getOpcode()) { 622 default: break; 623 case ISD::SRL: 624 // Shrink SRL by a constant if none of the high bits shifted in are 625 // demanded. 626 if (ConstantSDNode *ShAmt = dyn_cast<ConstantSDNode>(In.getOperand(1))){ 627 uint64_t HighBits = MVT::getIntVTBitMask(In.getValueType()); 628 HighBits &= ~MVT::getIntVTBitMask(Op.getValueType()); 629 HighBits >>= ShAmt->getValue(); 630 631 if (ShAmt->getValue() < MVT::getSizeInBits(Op.getValueType()) && 632 (DemandedMask & HighBits) == 0) { 633 // None of the shifted in bits are needed. Add a truncate of the 634 // shift input, then shift it. 635 SDOperand NewTrunc = TLO.DAG.getNode(ISD::TRUNCATE, 636 Op.getValueType(), 637 In.getOperand(0)); 638 return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::SRL,Op.getValueType(), 639 NewTrunc, In.getOperand(1))); 640 } 641 } 642 break; 643 } 644 } 645 646 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 647 uint64_t OutMask = MVT::getIntVTBitMask(Op.getValueType()); 648 KnownZero &= OutMask; 649 KnownOne &= OutMask; 650 break; 651 } 652 case ISD::AssertZext: { 653 MVT::ValueType VT = cast<VTSDNode>(Op.getOperand(1))->getVT(); 654 uint64_t InMask = MVT::getIntVTBitMask(VT); 655 if (SimplifyDemandedBits(Op.getOperand(0), DemandedMask & InMask, 656 KnownZero, KnownOne, TLO, Depth+1)) 657 return true; 658 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 659 KnownZero |= ~InMask & DemandedMask; 660 break; 661 } 662 case ISD::ADD: 663 case ISD::SUB: 664 case ISD::INTRINSIC_WO_CHAIN: 665 case ISD::INTRINSIC_W_CHAIN: 666 case ISD::INTRINSIC_VOID: 667 // Just use ComputeMaskedBits to compute output bits. 668 ComputeMaskedBits(Op, DemandedMask, KnownZero, KnownOne, Depth); 669 break; 670 } 671 672 // If we know the value of all of the demanded bits, return this as a 673 // constant. 674 if ((DemandedMask & (KnownZero|KnownOne)) == DemandedMask) 675 return TLO.CombineTo(Op, TLO.DAG.getConstant(KnownOne, Op.getValueType())); 676 677 return false; 678} 679 680/// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use 681/// this predicate to simplify operations downstream. Mask is known to be zero 682/// for bits that V cannot have. 683bool TargetLowering::MaskedValueIsZero(SDOperand Op, uint64_t Mask, 684 unsigned Depth) const { 685 uint64_t KnownZero, KnownOne; 686 ComputeMaskedBits(Op, Mask, KnownZero, KnownOne, Depth); 687 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 688 return (KnownZero & Mask) == Mask; 689} 690 691/// ComputeMaskedBits - Determine which of the bits specified in Mask are 692/// known to be either zero or one and return them in the KnownZero/KnownOne 693/// bitsets. This code only analyzes bits in Mask, in order to short-circuit 694/// processing. 695void TargetLowering::ComputeMaskedBits(SDOperand Op, uint64_t Mask, 696 uint64_t &KnownZero, uint64_t &KnownOne, 697 unsigned Depth) const { 698 KnownZero = KnownOne = 0; // Don't know anything. 699 if (Depth == 6 || Mask == 0) 700 return; // Limit search depth. 701 702 uint64_t KnownZero2, KnownOne2; 703 704 switch (Op.getOpcode()) { 705 case ISD::Constant: 706 // We know all of the bits for a constant! 707 KnownOne = cast<ConstantSDNode>(Op)->getValue() & Mask; 708 KnownZero = ~KnownOne & Mask; 709 return; 710 case ISD::AND: 711 // If either the LHS or the RHS are Zero, the result is zero. 712 ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1); 713 Mask &= ~KnownZero; 714 ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero2, KnownOne2, Depth+1); 715 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 716 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 717 718 // Output known-1 bits are only known if set in both the LHS & RHS. 719 KnownOne &= KnownOne2; 720 // Output known-0 are known to be clear if zero in either the LHS | RHS. 721 KnownZero |= KnownZero2; 722 return; 723 case ISD::OR: 724 ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1); 725 Mask &= ~KnownOne; 726 ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero2, KnownOne2, Depth+1); 727 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 728 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 729 730 // Output known-0 bits are only known if clear in both the LHS & RHS. 731 KnownZero &= KnownZero2; 732 // Output known-1 are known to be set if set in either the LHS | RHS. 733 KnownOne |= KnownOne2; 734 return; 735 case ISD::XOR: { 736 ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1); 737 ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero2, KnownOne2, Depth+1); 738 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 739 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 740 741 // Output known-0 bits are known if clear or set in both the LHS & RHS. 742 uint64_t KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2); 743 // Output known-1 are known to be set if set in only one of the LHS, RHS. 744 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2); 745 KnownZero = KnownZeroOut; 746 return; 747 } 748 case ISD::SELECT: 749 ComputeMaskedBits(Op.getOperand(2), Mask, KnownZero, KnownOne, Depth+1); 750 ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero2, KnownOne2, Depth+1); 751 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 752 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 753 754 // Only known if known in both the LHS and RHS. 755 KnownOne &= KnownOne2; 756 KnownZero &= KnownZero2; 757 return; 758 case ISD::SELECT_CC: 759 ComputeMaskedBits(Op.getOperand(3), Mask, KnownZero, KnownOne, Depth+1); 760 ComputeMaskedBits(Op.getOperand(2), Mask, KnownZero2, KnownOne2, Depth+1); 761 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 762 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 763 764 // Only known if known in both the LHS and RHS. 765 KnownOne &= KnownOne2; 766 KnownZero &= KnownZero2; 767 return; 768 case ISD::SETCC: 769 // If we know the result of a setcc has the top bits zero, use this info. 770 if (getSetCCResultContents() == TargetLowering::ZeroOrOneSetCCResult) 771 KnownZero |= (MVT::getIntVTBitMask(Op.getValueType()) ^ 1ULL); 772 return; 773 case ISD::SHL: 774 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0 775 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 776 Mask >>= SA->getValue(); 777 ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero, KnownOne, Depth+1); 778 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 779 KnownZero <<= SA->getValue(); 780 KnownOne <<= SA->getValue(); 781 KnownZero |= (1ULL << SA->getValue())-1; // low bits known zero. 782 } 783 return; 784 case ISD::SRL: 785 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0 786 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 787 uint64_t HighBits = (1ULL << SA->getValue())-1; 788 HighBits <<= MVT::getSizeInBits(Op.getValueType())-SA->getValue(); 789 Mask <<= SA->getValue(); 790 ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero, KnownOne, Depth+1); 791 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 792 KnownZero >>= SA->getValue(); 793 KnownOne >>= SA->getValue(); 794 KnownZero |= HighBits; // high bits known zero. 795 } 796 return; 797 case ISD::SRA: 798 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 799 uint64_t HighBits = (1ULL << SA->getValue())-1; 800 HighBits <<= MVT::getSizeInBits(Op.getValueType())-SA->getValue(); 801 Mask <<= SA->getValue(); 802 ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero, KnownOne, Depth+1); 803 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?"); 804 KnownZero >>= SA->getValue(); 805 KnownOne >>= SA->getValue(); 806 807 // Handle the sign bits. 808 uint64_t SignBit = 1ULL << (MVT::getSizeInBits(Op.getValueType())-1); 809 SignBit >>= SA->getValue(); // Adjust to where it is now in the mask. 810 811 if (KnownZero & SignBit) { // New bits are known zero. 812 KnownZero |= HighBits; 813 } else if (KnownOne & SignBit) { // New bits are known one. 814 KnownOne |= HighBits; 815 } 816 } 817 return; 818 case ISD::SIGN_EXTEND_INREG: { 819 MVT::ValueType VT = Op.getValueType(); 820 MVT::ValueType EVT = cast<VTSDNode>(Op.getOperand(1))->getVT(); 821 822 // Sign extension. Compute the demanded bits in the result that are not 823 // present in the input. 824 uint64_t NewBits = ~MVT::getIntVTBitMask(EVT) & Mask; 825 826 uint64_t InSignBit = MVT::getIntVTSignBit(EVT); 827 int64_t InputDemandedBits = Mask & MVT::getIntVTBitMask(EVT); 828 829 // If the sign extended bits are demanded, we know that the sign 830 // bit is demanded. 831 if (NewBits) 832 InputDemandedBits |= InSignBit; 833 834 ComputeMaskedBits(Op.getOperand(0), InputDemandedBits, 835 KnownZero, KnownOne, Depth+1); 836 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 837 838 // If the sign bit of the input is known set or clear, then we know the 839 // top bits of the result. 840 if (KnownZero & InSignBit) { // Input sign bit known clear 841 KnownZero |= NewBits; 842 KnownOne &= ~NewBits; 843 } else if (KnownOne & InSignBit) { // Input sign bit known set 844 KnownOne |= NewBits; 845 KnownZero &= ~NewBits; 846 } else { // Input sign bit unknown 847 KnownZero &= ~NewBits; 848 KnownOne &= ~NewBits; 849 } 850 return; 851 } 852 case ISD::CTTZ: 853 case ISD::CTLZ: 854 case ISD::CTPOP: { 855 MVT::ValueType VT = Op.getValueType(); 856 unsigned LowBits = Log2_32(MVT::getSizeInBits(VT))+1; 857 KnownZero = ~((1ULL << LowBits)-1) & MVT::getIntVTBitMask(VT); 858 KnownOne = 0; 859 return; 860 } 861 case ISD::ZEXTLOAD: { 862 MVT::ValueType VT = cast<VTSDNode>(Op.getOperand(3))->getVT(); 863 KnownZero |= ~MVT::getIntVTBitMask(VT) & Mask; 864 return; 865 } 866 case ISD::ZERO_EXTEND: { 867 uint64_t InMask = MVT::getIntVTBitMask(Op.getOperand(0).getValueType()); 868 uint64_t NewBits = (~InMask) & Mask; 869 ComputeMaskedBits(Op.getOperand(0), Mask & InMask, KnownZero, 870 KnownOne, Depth+1); 871 KnownZero |= NewBits & Mask; 872 KnownOne &= ~NewBits; 873 return; 874 } 875 case ISD::SIGN_EXTEND: { 876 MVT::ValueType InVT = Op.getOperand(0).getValueType(); 877 unsigned InBits = MVT::getSizeInBits(InVT); 878 uint64_t InMask = MVT::getIntVTBitMask(InVT); 879 uint64_t InSignBit = 1ULL << (InBits-1); 880 uint64_t NewBits = (~InMask) & Mask; 881 uint64_t InDemandedBits = Mask & InMask; 882 883 // If any of the sign extended bits are demanded, we know that the sign 884 // bit is demanded. 885 if (NewBits & Mask) 886 InDemandedBits |= InSignBit; 887 888 ComputeMaskedBits(Op.getOperand(0), InDemandedBits, KnownZero, 889 KnownOne, Depth+1); 890 // If the sign bit is known zero or one, the top bits match. 891 if (KnownZero & InSignBit) { 892 KnownZero |= NewBits; 893 KnownOne &= ~NewBits; 894 } else if (KnownOne & InSignBit) { 895 KnownOne |= NewBits; 896 KnownZero &= ~NewBits; 897 } else { // Otherwise, top bits aren't known. 898 KnownOne &= ~NewBits; 899 KnownZero &= ~NewBits; 900 } 901 return; 902 } 903 case ISD::ANY_EXTEND: { 904 MVT::ValueType VT = Op.getOperand(0).getValueType(); 905 ComputeMaskedBits(Op.getOperand(0), Mask & MVT::getIntVTBitMask(VT), 906 KnownZero, KnownOne, Depth+1); 907 return; 908 } 909 case ISD::TRUNCATE: { 910 ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero, KnownOne, Depth+1); 911 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 912 uint64_t OutMask = MVT::getIntVTBitMask(Op.getValueType()); 913 KnownZero &= OutMask; 914 KnownOne &= OutMask; 915 break; 916 } 917 case ISD::AssertZext: { 918 MVT::ValueType VT = cast<VTSDNode>(Op.getOperand(1))->getVT(); 919 uint64_t InMask = MVT::getIntVTBitMask(VT); 920 ComputeMaskedBits(Op.getOperand(0), Mask & InMask, KnownZero, 921 KnownOne, Depth+1); 922 KnownZero |= (~InMask) & Mask; 923 return; 924 } 925 case ISD::ADD: { 926 // If either the LHS or the RHS are Zero, the result is zero. 927 ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1); 928 ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero2, KnownOne2, Depth+1); 929 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 930 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 931 932 // Output known-0 bits are known if clear or set in both the low clear bits 933 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the 934 // low 3 bits clear. 935 uint64_t KnownZeroOut = std::min(CountTrailingZeros_64(~KnownZero), 936 CountTrailingZeros_64(~KnownZero2)); 937 938 KnownZero = (1ULL << KnownZeroOut) - 1; 939 KnownOne = 0; 940 return; 941 } 942 case ISD::SUB: { 943 ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)); 944 if (!CLHS) return; 945 946 // We know that the top bits of C-X are clear if X contains less bits 947 // than C (i.e. no wrap-around can happen). For example, 20-X is 948 // positive if we can prove that X is >= 0 and < 16. 949 MVT::ValueType VT = CLHS->getValueType(0); 950 if ((CLHS->getValue() & MVT::getIntVTSignBit(VT)) == 0) { // sign bit clear 951 unsigned NLZ = CountLeadingZeros_64(CLHS->getValue()+1); 952 uint64_t MaskV = (1ULL << (63-NLZ))-1; // NLZ can't be 64 with no sign bit 953 MaskV = ~MaskV & MVT::getIntVTBitMask(VT); 954 ComputeMaskedBits(Op.getOperand(1), MaskV, KnownZero, KnownOne, Depth+1); 955 956 // If all of the MaskV bits are known to be zero, then we know the output 957 // top bits are zero, because we now know that the output is from [0-C]. 958 if ((KnownZero & MaskV) == MaskV) { 959 unsigned NLZ2 = CountLeadingZeros_64(CLHS->getValue()); 960 KnownZero = ~((1ULL << (64-NLZ2))-1) & Mask; // Top bits known zero. 961 KnownOne = 0; // No one bits known. 962 } else { 963 KnownOne = KnownOne = 0; // Otherwise, nothing known. 964 } 965 } 966 return; 967 } 968 default: 969 // Allow the target to implement this method for its nodes. 970 if (Op.getOpcode() >= ISD::BUILTIN_OP_END) { 971 case ISD::INTRINSIC_WO_CHAIN: 972 case ISD::INTRINSIC_W_CHAIN: 973 case ISD::INTRINSIC_VOID: 974 computeMaskedBitsForTargetNode(Op, Mask, KnownZero, KnownOne); 975 } 976 return; 977 } 978} 979 980/// computeMaskedBitsForTargetNode - Determine which of the bits specified 981/// in Mask are known to be either zero or one and return them in the 982/// KnownZero/KnownOne bitsets. 983void TargetLowering::computeMaskedBitsForTargetNode(const SDOperand Op, 984 uint64_t Mask, 985 uint64_t &KnownZero, 986 uint64_t &KnownOne, 987 unsigned Depth) const { 988 assert((Op.getOpcode() >= ISD::BUILTIN_OP_END || 989 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN || 990 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN || 991 Op.getOpcode() == ISD::INTRINSIC_VOID) && 992 "Should use MaskedValueIsZero if you don't know whether Op" 993 " is a target node!"); 994 KnownZero = 0; 995 KnownOne = 0; 996} 997 998/// ComputeNumSignBits - Return the number of times the sign bit of the 999/// register is replicated into the other bits. We know that at least 1 bit 1000/// is always equal to the sign bit (itself), but other cases can give us 1001/// information. For example, immediately after an "SRA X, 2", we know that 1002/// the top 3 bits are all equal to each other, so we return 3. 1003unsigned TargetLowering::ComputeNumSignBits(SDOperand Op, unsigned Depth) const{ 1004 MVT::ValueType VT = Op.getValueType(); 1005 assert(MVT::isInteger(VT) && "Invalid VT!"); 1006 unsigned VTBits = MVT::getSizeInBits(VT); 1007 unsigned Tmp, Tmp2; 1008 1009 if (Depth == 6) 1010 return 1; // Limit search depth. 1011 1012 switch (Op.getOpcode()) { 1013 default: break; 1014 case ISD::AssertSext: 1015 Tmp = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(1))->getVT()); 1016 return VTBits-Tmp+1; 1017 case ISD::AssertZext: 1018 Tmp = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(1))->getVT()); 1019 return VTBits-Tmp; 1020 1021 case ISD::SEXTLOAD: // '17' bits known 1022 Tmp = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(3))->getVT()); 1023 return VTBits-Tmp+1; 1024 case ISD::ZEXTLOAD: // '16' bits known 1025 Tmp = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(3))->getVT()); 1026 return VTBits-Tmp; 1027 1028 case ISD::Constant: { 1029 uint64_t Val = cast<ConstantSDNode>(Op)->getValue(); 1030 // If negative, invert the bits, then look at it. 1031 if (Val & MVT::getIntVTSignBit(VT)) 1032 Val = ~Val; 1033 1034 // Shift the bits so they are the leading bits in the int64_t. 1035 Val <<= 64-VTBits; 1036 1037 // Return # leading zeros. We use 'min' here in case Val was zero before 1038 // shifting. We don't want to return '64' as for an i32 "0". 1039 return std::min(VTBits, CountLeadingZeros_64(Val)); 1040 } 1041 1042 case ISD::SIGN_EXTEND: 1043 Tmp = VTBits-MVT::getSizeInBits(Op.getOperand(0).getValueType()); 1044 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp; 1045 1046 case ISD::SIGN_EXTEND_INREG: 1047 // Max of the input and what this extends. 1048 Tmp = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(1))->getVT()); 1049 Tmp = VTBits-Tmp+1; 1050 1051 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1); 1052 return std::max(Tmp, Tmp2); 1053 1054 case ISD::SRA: 1055 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1); 1056 // SRA X, C -> adds C sign bits. 1057 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 1058 Tmp += C->getValue(); 1059 if (Tmp > VTBits) Tmp = VTBits; 1060 } 1061 return Tmp; 1062 case ISD::SHL: 1063 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 1064 // shl destroys sign bits. 1065 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1); 1066 if (C->getValue() >= VTBits || // Bad shift. 1067 C->getValue() >= Tmp) break; // Shifted all sign bits out. 1068 return Tmp - C->getValue(); 1069 } 1070 break; 1071 case ISD::AND: 1072 case ISD::OR: 1073 case ISD::XOR: // NOT is handled here. 1074 // Logical binary ops preserve the number of sign bits. 1075 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1); 1076 if (Tmp == 1) return 1; // Early out. 1077 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1); 1078 return std::min(Tmp, Tmp2); 1079 1080 case ISD::SELECT: 1081 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1); 1082 if (Tmp == 1) return 1; // Early out. 1083 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1); 1084 return std::min(Tmp, Tmp2); 1085 1086 case ISD::SETCC: 1087 // If setcc returns 0/-1, all bits are sign bits. 1088 if (getSetCCResultContents() == ZeroOrNegativeOneSetCCResult) 1089 return VTBits; 1090 break; 1091 case ISD::ROTL: 1092 case ISD::ROTR: 1093 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 1094 unsigned RotAmt = C->getValue() & (VTBits-1); 1095 1096 // Handle rotate right by N like a rotate left by 32-N. 1097 if (Op.getOpcode() == ISD::ROTR) 1098 RotAmt = (VTBits-RotAmt) & (VTBits-1); 1099 1100 // If we aren't rotating out all of the known-in sign bits, return the 1101 // number that are left. This handles rotl(sext(x), 1) for example. 1102 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1); 1103 if (Tmp > RotAmt+1) return Tmp-RotAmt; 1104 } 1105 break; 1106 case ISD::ADD: 1107 // Add can have at most one carry bit. Thus we know that the output 1108 // is, at worst, one more bit than the inputs. 1109 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1); 1110 if (Tmp == 1) return 1; // Early out. 1111 1112 // Special case decrementing a value (ADD X, -1): 1113 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) 1114 if (CRHS->isAllOnesValue()) { 1115 uint64_t KnownZero, KnownOne; 1116 uint64_t Mask = MVT::getIntVTBitMask(VT); 1117 ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero, KnownOne, Depth+1); 1118 1119 // If the input is known to be 0 or 1, the output is 0/-1, which is all 1120 // sign bits set. 1121 if ((KnownZero|1) == Mask) 1122 return VTBits; 1123 1124 // If we are subtracting one from a positive number, there is no carry 1125 // out of the result. 1126 if (KnownZero & MVT::getIntVTSignBit(VT)) 1127 return Tmp; 1128 } 1129 1130 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1); 1131 if (Tmp2 == 1) return 1; 1132 return std::min(Tmp, Tmp2)-1; 1133 break; 1134 1135 case ISD::SUB: 1136 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1); 1137 if (Tmp2 == 1) return 1; 1138 1139 // Handle NEG. 1140 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) 1141 if (CLHS->getValue() == 0) { 1142 uint64_t KnownZero, KnownOne; 1143 uint64_t Mask = MVT::getIntVTBitMask(VT); 1144 ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1); 1145 // If the input is known to be 0 or 1, the output is 0/-1, which is all 1146 // sign bits set. 1147 if ((KnownZero|1) == Mask) 1148 return VTBits; 1149 1150 // If the input is known to be positive (the sign bit is known clear), 1151 // the output of the NEG has the same number of sign bits as the input. 1152 if (KnownZero & MVT::getIntVTSignBit(VT)) 1153 return Tmp2; 1154 1155 // Otherwise, we treat this like a SUB. 1156 } 1157 1158 // Sub can have at most one carry bit. Thus we know that the output 1159 // is, at worst, one more bit than the inputs. 1160 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1); 1161 if (Tmp == 1) return 1; // Early out. 1162 return std::min(Tmp, Tmp2)-1; 1163 break; 1164 case ISD::TRUNCATE: 1165 // FIXME: it's tricky to do anything useful for this, but it is an important 1166 // case for targets like X86. 1167 break; 1168 } 1169 1170 // Allow the target to implement this method for its nodes. 1171 if (Op.getOpcode() >= ISD::BUILTIN_OP_END || 1172 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN || 1173 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN || 1174 Op.getOpcode() == ISD::INTRINSIC_VOID) { 1175 unsigned NumBits = ComputeNumSignBitsForTargetNode(Op, Depth); 1176 if (NumBits > 1) return NumBits; 1177 } 1178 1179 // FIXME: Should use computemaskedbits to look at the top bits. 1180 return 1; 1181} 1182 1183 1184 1185/// ComputeNumSignBitsForTargetNode - This method can be implemented by 1186/// targets that want to expose additional information about sign bits to the 1187/// DAG Combiner. 1188unsigned TargetLowering::ComputeNumSignBitsForTargetNode(SDOperand Op, 1189 unsigned Depth) const { 1190 assert((Op.getOpcode() >= ISD::BUILTIN_OP_END || 1191 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN || 1192 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN || 1193 Op.getOpcode() == ISD::INTRINSIC_VOID) && 1194 "Should use ComputeNumSignBits if you don't know whether Op" 1195 " is a target node!"); 1196 return 1; 1197} 1198 1199 1200SDOperand TargetLowering:: 1201PerformDAGCombine(SDNode *N, DAGCombinerInfo &DCI) const { 1202 // Default implementation: no optimization. 1203 return SDOperand(); 1204} 1205 1206//===----------------------------------------------------------------------===// 1207// Inline Assembler Implementation Methods 1208//===----------------------------------------------------------------------===// 1209 1210TargetLowering::ConstraintType 1211TargetLowering::getConstraintType(char ConstraintLetter) const { 1212 // FIXME: lots more standard ones to handle. 1213 switch (ConstraintLetter) { 1214 default: return C_Unknown; 1215 case 'r': return C_RegisterClass; 1216 case 'm': // memory 1217 case 'o': // offsetable 1218 case 'V': // not offsetable 1219 return C_Memory; 1220 case 'i': // Simple Integer or Relocatable Constant 1221 case 'n': // Simple Integer 1222 case 's': // Relocatable Constant 1223 case 'I': // Target registers. 1224 case 'J': 1225 case 'K': 1226 case 'L': 1227 case 'M': 1228 case 'N': 1229 case 'O': 1230 case 'P': 1231 return C_Other; 1232 } 1233} 1234 1235bool TargetLowering::isOperandValidForConstraint(SDOperand Op, 1236 char ConstraintLetter) { 1237 switch (ConstraintLetter) { 1238 default: return false; 1239 case 'i': // Simple Integer or Relocatable Constant 1240 case 'n': // Simple Integer 1241 case 's': // Relocatable Constant 1242 return true; // FIXME: not right. 1243 } 1244} 1245 1246 1247std::vector<unsigned> TargetLowering:: 1248getRegClassForInlineAsmConstraint(const std::string &Constraint, 1249 MVT::ValueType VT) const { 1250 return std::vector<unsigned>(); 1251} 1252 1253 1254std::pair<unsigned, const TargetRegisterClass*> TargetLowering:: 1255getRegForInlineAsmConstraint(const std::string &Constraint, 1256 MVT::ValueType VT) const { 1257 if (Constraint[0] != '{') 1258 return std::pair<unsigned, const TargetRegisterClass*>(0, 0); 1259 assert(*(Constraint.end()-1) == '}' && "Not a brace enclosed constraint?"); 1260 1261 // Remove the braces from around the name. 1262 std::string RegName(Constraint.begin()+1, Constraint.end()-1); 1263 1264 // Figure out which register class contains this reg. 1265 const MRegisterInfo *RI = TM.getRegisterInfo(); 1266 for (MRegisterInfo::regclass_iterator RCI = RI->regclass_begin(), 1267 E = RI->regclass_end(); RCI != E; ++RCI) { 1268 const TargetRegisterClass *RC = *RCI; 1269 1270 // If none of the the value types for this register class are valid, we 1271 // can't use it. For example, 64-bit reg classes on 32-bit targets. 1272 bool isLegal = false; 1273 for (TargetRegisterClass::vt_iterator I = RC->vt_begin(), E = RC->vt_end(); 1274 I != E; ++I) { 1275 if (isTypeLegal(*I)) { 1276 isLegal = true; 1277 break; 1278 } 1279 } 1280 1281 if (!isLegal) continue; 1282 1283 for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); 1284 I != E; ++I) { 1285 if (StringsEqualNoCase(RegName, RI->get(*I).Name)) 1286 return std::make_pair(*I, RC); 1287 } 1288 } 1289 1290 return std::pair<unsigned, const TargetRegisterClass*>(0, 0); 1291} 1292 1293//===----------------------------------------------------------------------===// 1294// Loop Strength Reduction hooks 1295//===----------------------------------------------------------------------===// 1296 1297/// isLegalAddressImmediate - Return true if the integer value or 1298/// GlobalValue can be used as the offset of the target addressing mode. 1299bool TargetLowering::isLegalAddressImmediate(int64_t V) const { 1300 return false; 1301} 1302bool TargetLowering::isLegalAddressImmediate(GlobalValue *GV) const { 1303 return false; 1304} 1305