TargetLowering.cpp revision 3a59358499f527ad9a8d1d4ed7d80b6bf0f1c12d
1//===-- TargetLowering.cpp - Implement the TargetLowering class -----------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by the LLVM research group and is distributed under 6// the University of Illinois Open Source License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This implements the TargetLowering class. 11// 12//===----------------------------------------------------------------------===// 13 14#include "llvm/Target/TargetLowering.h" 15#include "llvm/Target/TargetMachine.h" 16#include "llvm/Target/MRegisterInfo.h" 17#include "llvm/CodeGen/SelectionDAG.h" 18#include "llvm/ADT/StringExtras.h" 19#include "llvm/Support/MathExtras.h" 20using namespace llvm; 21 22TargetLowering::TargetLowering(TargetMachine &tm) 23 : TM(tm), TD(TM.getTargetData()) { 24 assert(ISD::BUILTIN_OP_END <= 156 && 25 "Fixed size array in TargetLowering is not large enough!"); 26 // All operations default to being supported. 27 memset(OpActions, 0, sizeof(OpActions)); 28 29 IsLittleEndian = TD.isLittleEndian(); 30 ShiftAmountTy = SetCCResultTy = PointerTy = getValueType(TD.getIntPtrType()); 31 ShiftAmtHandling = Undefined; 32 memset(RegClassForVT, 0,MVT::LAST_VALUETYPE*sizeof(TargetRegisterClass*)); 33 memset(TargetDAGCombineArray, 0, 34 sizeof(TargetDAGCombineArray)/sizeof(TargetDAGCombineArray[0])); 35 maxStoresPerMemset = maxStoresPerMemcpy = maxStoresPerMemmove = 8; 36 allowUnalignedMemoryAccesses = false; 37 UseUnderscoreSetJmpLongJmp = false; 38 IntDivIsCheap = false; 39 Pow2DivIsCheap = false; 40 StackPointerRegisterToSaveRestore = 0; 41 SchedPreferenceInfo = SchedulingForLatency; 42} 43 44TargetLowering::~TargetLowering() {} 45 46/// setValueTypeAction - Set the action for a particular value type. This 47/// assumes an action has not already been set for this value type. 48static void SetValueTypeAction(MVT::ValueType VT, 49 TargetLowering::LegalizeAction Action, 50 TargetLowering &TLI, 51 MVT::ValueType *TransformToType, 52 TargetLowering::ValueTypeActionImpl &ValueTypeActions) { 53 ValueTypeActions.setTypeAction(VT, Action); 54 if (Action == TargetLowering::Promote) { 55 MVT::ValueType PromoteTo; 56 if (VT == MVT::f32) 57 PromoteTo = MVT::f64; 58 else { 59 unsigned LargerReg = VT+1; 60 while (!TLI.isTypeLegal((MVT::ValueType)LargerReg)) { 61 ++LargerReg; 62 assert(MVT::isInteger((MVT::ValueType)LargerReg) && 63 "Nothing to promote to??"); 64 } 65 PromoteTo = (MVT::ValueType)LargerReg; 66 } 67 68 assert(MVT::isInteger(VT) == MVT::isInteger(PromoteTo) && 69 MVT::isFloatingPoint(VT) == MVT::isFloatingPoint(PromoteTo) && 70 "Can only promote from int->int or fp->fp!"); 71 assert(VT < PromoteTo && "Must promote to a larger type!"); 72 TransformToType[VT] = PromoteTo; 73 } else if (Action == TargetLowering::Expand) { 74 assert((VT == MVT::Vector || MVT::isInteger(VT)) && VT > MVT::i8 && 75 "Cannot expand this type: target must support SOME integer reg!"); 76 // Expand to the next smaller integer type! 77 TransformToType[VT] = (MVT::ValueType)(VT-1); 78 } 79} 80 81 82/// computeRegisterProperties - Once all of the register classes are added, 83/// this allows us to compute derived properties we expose. 84void TargetLowering::computeRegisterProperties() { 85 assert(MVT::LAST_VALUETYPE <= 32 && 86 "Too many value types for ValueTypeActions to hold!"); 87 88 // Everything defaults to one. 89 for (unsigned i = 0; i != MVT::LAST_VALUETYPE; ++i) 90 NumElementsForVT[i] = 1; 91 92 // Find the largest integer register class. 93 unsigned LargestIntReg = MVT::i128; 94 for (; RegClassForVT[LargestIntReg] == 0; --LargestIntReg) 95 assert(LargestIntReg != MVT::i1 && "No integer registers defined!"); 96 97 // Every integer value type larger than this largest register takes twice as 98 // many registers to represent as the previous ValueType. 99 unsigned ExpandedReg = LargestIntReg; ++LargestIntReg; 100 for (++ExpandedReg; MVT::isInteger((MVT::ValueType)ExpandedReg);++ExpandedReg) 101 NumElementsForVT[ExpandedReg] = 2*NumElementsForVT[ExpandedReg-1]; 102 103 // Inspect all of the ValueType's possible, deciding how to process them. 104 for (unsigned IntReg = MVT::i1; IntReg <= MVT::i128; ++IntReg) 105 // If we are expanding this type, expand it! 106 if (getNumElements((MVT::ValueType)IntReg) != 1) 107 SetValueTypeAction((MVT::ValueType)IntReg, Expand, *this, TransformToType, 108 ValueTypeActions); 109 else if (!isTypeLegal((MVT::ValueType)IntReg)) 110 // Otherwise, if we don't have native support, we must promote to a 111 // larger type. 112 SetValueTypeAction((MVT::ValueType)IntReg, Promote, *this, 113 TransformToType, ValueTypeActions); 114 else 115 TransformToType[(MVT::ValueType)IntReg] = (MVT::ValueType)IntReg; 116 117 // If the target does not have native support for F32, promote it to F64. 118 if (!isTypeLegal(MVT::f32)) 119 SetValueTypeAction(MVT::f32, Promote, *this, 120 TransformToType, ValueTypeActions); 121 else 122 TransformToType[MVT::f32] = MVT::f32; 123 124 // Set MVT::Vector to always be Expanded 125 SetValueTypeAction(MVT::Vector, Expand, *this, TransformToType, 126 ValueTypeActions); 127 128 // Loop over all of the legal vector value types, specifying an identity type 129 // transformation. 130 for (unsigned i = MVT::FIRST_VECTOR_VALUETYPE; 131 i != MVT::LAST_VECTOR_VALUETYPE; ++i) { 132 if (isTypeLegal((MVT::ValueType)i)) 133 TransformToType[i] = (MVT::ValueType)i; 134 } 135 136 assert(isTypeLegal(MVT::f64) && "Target does not support FP?"); 137 TransformToType[MVT::f64] = MVT::f64; 138} 139 140const char *TargetLowering::getTargetNodeName(unsigned Opcode) const { 141 return NULL; 142} 143 144//===----------------------------------------------------------------------===// 145// Optimization Methods 146//===----------------------------------------------------------------------===// 147 148/// ShrinkDemandedConstant - Check to see if the specified operand of the 149/// specified instruction is a constant integer. If so, check to see if there 150/// are any bits set in the constant that are not demanded. If so, shrink the 151/// constant and return true. 152bool TargetLowering::TargetLoweringOpt::ShrinkDemandedConstant(SDOperand Op, 153 uint64_t Demanded) { 154 // FIXME: ISD::SELECT, ISD::SELECT_CC 155 switch(Op.getOpcode()) { 156 default: break; 157 case ISD::AND: 158 case ISD::OR: 159 case ISD::XOR: 160 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) 161 if ((~Demanded & C->getValue()) != 0) { 162 MVT::ValueType VT = Op.getValueType(); 163 SDOperand New = DAG.getNode(Op.getOpcode(), VT, Op.getOperand(0), 164 DAG.getConstant(Demanded & C->getValue(), 165 VT)); 166 return CombineTo(Op, New); 167 } 168 break; 169 } 170 return false; 171} 172 173/// SimplifyDemandedBits - Look at Op. At this point, we know that only the 174/// DemandedMask bits of the result of Op are ever used downstream. If we can 175/// use this information to simplify Op, create a new simplified DAG node and 176/// return true, returning the original and new nodes in Old and New. Otherwise, 177/// analyze the expression and return a mask of KnownOne and KnownZero bits for 178/// the expression (used to simplify the caller). The KnownZero/One bits may 179/// only be accurate for those bits in the DemandedMask. 180bool TargetLowering::SimplifyDemandedBits(SDOperand Op, uint64_t DemandedMask, 181 uint64_t &KnownZero, 182 uint64_t &KnownOne, 183 TargetLoweringOpt &TLO, 184 unsigned Depth) const { 185 KnownZero = KnownOne = 0; // Don't know anything. 186 // Other users may use these bits. 187 if (!Op.Val->hasOneUse()) { 188 if (Depth != 0) { 189 // If not at the root, Just compute the KnownZero/KnownOne bits to 190 // simplify things downstream. 191 ComputeMaskedBits(Op, DemandedMask, KnownZero, KnownOne, Depth); 192 return false; 193 } 194 // If this is the root being simplified, allow it to have multiple uses, 195 // just set the DemandedMask to all bits. 196 DemandedMask = MVT::getIntVTBitMask(Op.getValueType()); 197 } else if (DemandedMask == 0) { 198 // Not demanding any bits from Op. 199 if (Op.getOpcode() != ISD::UNDEF) 200 return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::UNDEF, Op.getValueType())); 201 return false; 202 } else if (Depth == 6) { // Limit search depth. 203 return false; 204 } 205 206 uint64_t KnownZero2, KnownOne2, KnownZeroOut, KnownOneOut; 207 switch (Op.getOpcode()) { 208 case ISD::Constant: 209 // We know all of the bits for a constant! 210 KnownOne = cast<ConstantSDNode>(Op)->getValue() & DemandedMask; 211 KnownZero = ~KnownOne & DemandedMask; 212 return false; // Don't fall through, will infinitely loop. 213 case ISD::AND: 214 // If the RHS is a constant, check to see if the LHS would be zero without 215 // using the bits from the RHS. Below, we use knowledge about the RHS to 216 // simplify the LHS, here we're using information from the LHS to simplify 217 // the RHS. 218 if (ConstantSDNode *RHSC = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 219 uint64_t LHSZero, LHSOne; 220 ComputeMaskedBits(Op.getOperand(0), DemandedMask, 221 LHSZero, LHSOne, Depth+1); 222 // If the LHS already has zeros where RHSC does, this and is dead. 223 if ((LHSZero & DemandedMask) == (~RHSC->getValue() & DemandedMask)) 224 return TLO.CombineTo(Op, Op.getOperand(0)); 225 // If any of the set bits in the RHS are known zero on the LHS, shrink 226 // the constant. 227 if (TLO.ShrinkDemandedConstant(Op, ~LHSZero & DemandedMask)) 228 return true; 229 } 230 231 if (SimplifyDemandedBits(Op.getOperand(1), DemandedMask, KnownZero, 232 KnownOne, TLO, Depth+1)) 233 return true; 234 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 235 if (SimplifyDemandedBits(Op.getOperand(0), DemandedMask & ~KnownZero, 236 KnownZero2, KnownOne2, TLO, Depth+1)) 237 return true; 238 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 239 240 // If all of the demanded bits are known one on one side, return the other. 241 // These bits cannot contribute to the result of the 'and'. 242 if ((DemandedMask & ~KnownZero2 & KnownOne)==(DemandedMask & ~KnownZero2)) 243 return TLO.CombineTo(Op, Op.getOperand(0)); 244 if ((DemandedMask & ~KnownZero & KnownOne2)==(DemandedMask & ~KnownZero)) 245 return TLO.CombineTo(Op, Op.getOperand(1)); 246 // If all of the demanded bits in the inputs are known zeros, return zero. 247 if ((DemandedMask & (KnownZero|KnownZero2)) == DemandedMask) 248 return TLO.CombineTo(Op, TLO.DAG.getConstant(0, Op.getValueType())); 249 // If the RHS is a constant, see if we can simplify it. 250 if (TLO.ShrinkDemandedConstant(Op, DemandedMask & ~KnownZero2)) 251 return true; 252 253 // Output known-1 bits are only known if set in both the LHS & RHS. 254 KnownOne &= KnownOne2; 255 // Output known-0 are known to be clear if zero in either the LHS | RHS. 256 KnownZero |= KnownZero2; 257 break; 258 case ISD::OR: 259 if (SimplifyDemandedBits(Op.getOperand(1), DemandedMask, KnownZero, 260 KnownOne, TLO, Depth+1)) 261 return true; 262 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 263 if (SimplifyDemandedBits(Op.getOperand(0), DemandedMask & ~KnownOne, 264 KnownZero2, KnownOne2, TLO, Depth+1)) 265 return true; 266 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 267 268 // If all of the demanded bits are known zero on one side, return the other. 269 // These bits cannot contribute to the result of the 'or'. 270 if ((DemandedMask & ~KnownOne2 & KnownZero) == (DemandedMask & ~KnownOne2)) 271 return TLO.CombineTo(Op, Op.getOperand(0)); 272 if ((DemandedMask & ~KnownOne & KnownZero2) == (DemandedMask & ~KnownOne)) 273 return TLO.CombineTo(Op, Op.getOperand(1)); 274 // If all of the potentially set bits on one side are known to be set on 275 // the other side, just use the 'other' side. 276 if ((DemandedMask & (~KnownZero) & KnownOne2) == 277 (DemandedMask & (~KnownZero))) 278 return TLO.CombineTo(Op, Op.getOperand(0)); 279 if ((DemandedMask & (~KnownZero2) & KnownOne) == 280 (DemandedMask & (~KnownZero2))) 281 return TLO.CombineTo(Op, Op.getOperand(1)); 282 // If the RHS is a constant, see if we can simplify it. 283 if (TLO.ShrinkDemandedConstant(Op, DemandedMask)) 284 return true; 285 286 // Output known-0 bits are only known if clear in both the LHS & RHS. 287 KnownZero &= KnownZero2; 288 // Output known-1 are known to be set if set in either the LHS | RHS. 289 KnownOne |= KnownOne2; 290 break; 291 case ISD::XOR: 292 if (SimplifyDemandedBits(Op.getOperand(1), DemandedMask, KnownZero, 293 KnownOne, TLO, Depth+1)) 294 return true; 295 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 296 if (SimplifyDemandedBits(Op.getOperand(0), DemandedMask, KnownZero2, 297 KnownOne2, TLO, Depth+1)) 298 return true; 299 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 300 301 // If all of the demanded bits are known zero on one side, return the other. 302 // These bits cannot contribute to the result of the 'xor'. 303 if ((DemandedMask & KnownZero) == DemandedMask) 304 return TLO.CombineTo(Op, Op.getOperand(0)); 305 if ((DemandedMask & KnownZero2) == DemandedMask) 306 return TLO.CombineTo(Op, Op.getOperand(1)); 307 308 // Output known-0 bits are known if clear or set in both the LHS & RHS. 309 KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2); 310 // Output known-1 are known to be set if set in only one of the LHS, RHS. 311 KnownOneOut = (KnownZero & KnownOne2) | (KnownOne & KnownZero2); 312 313 // If all of the unknown bits are known to be zero on one side or the other 314 // (but not both) turn this into an *inclusive* or. 315 // e.g. (A & C1)^(B & C2) -> (A & C1)|(B & C2) iff C1&C2 == 0 316 if (uint64_t UnknownBits = DemandedMask & ~(KnownZeroOut|KnownOneOut)) 317 if ((UnknownBits & (KnownZero|KnownZero2)) == UnknownBits) 318 return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::OR, Op.getValueType(), 319 Op.getOperand(0), 320 Op.getOperand(1))); 321 // If all of the demanded bits on one side are known, and all of the set 322 // bits on that side are also known to be set on the other side, turn this 323 // into an AND, as we know the bits will be cleared. 324 // e.g. (X | C1) ^ C2 --> (X | C1) & ~C2 iff (C1&C2) == C2 325 if ((DemandedMask & (KnownZero|KnownOne)) == DemandedMask) { // all known 326 if ((KnownOne & KnownOne2) == KnownOne) { 327 MVT::ValueType VT = Op.getValueType(); 328 SDOperand ANDC = TLO.DAG.getConstant(~KnownOne & DemandedMask, VT); 329 return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::AND, VT, Op.getOperand(0), 330 ANDC)); 331 } 332 } 333 334 // If the RHS is a constant, see if we can simplify it. 335 // FIXME: for XOR, we prefer to force bits to 1 if they will make a -1. 336 if (TLO.ShrinkDemandedConstant(Op, DemandedMask)) 337 return true; 338 339 KnownZero = KnownZeroOut; 340 KnownOne = KnownOneOut; 341 break; 342 case ISD::SETCC: 343 // If we know the result of a setcc has the top bits zero, use this info. 344 if (getSetCCResultContents() == TargetLowering::ZeroOrOneSetCCResult) 345 KnownZero |= (MVT::getIntVTBitMask(Op.getValueType()) ^ 1ULL); 346 break; 347 case ISD::SELECT: 348 if (SimplifyDemandedBits(Op.getOperand(2), DemandedMask, KnownZero, 349 KnownOne, TLO, Depth+1)) 350 return true; 351 if (SimplifyDemandedBits(Op.getOperand(1), DemandedMask, KnownZero2, 352 KnownOne2, TLO, Depth+1)) 353 return true; 354 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 355 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 356 357 // If the operands are constants, see if we can simplify them. 358 if (TLO.ShrinkDemandedConstant(Op, DemandedMask)) 359 return true; 360 361 // Only known if known in both the LHS and RHS. 362 KnownOne &= KnownOne2; 363 KnownZero &= KnownZero2; 364 break; 365 case ISD::SELECT_CC: 366 if (SimplifyDemandedBits(Op.getOperand(3), DemandedMask, KnownZero, 367 KnownOne, TLO, Depth+1)) 368 return true; 369 if (SimplifyDemandedBits(Op.getOperand(2), DemandedMask, KnownZero2, 370 KnownOne2, TLO, Depth+1)) 371 return true; 372 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 373 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 374 375 // If the operands are constants, see if we can simplify them. 376 if (TLO.ShrinkDemandedConstant(Op, DemandedMask)) 377 return true; 378 379 // Only known if known in both the LHS and RHS. 380 KnownOne &= KnownOne2; 381 KnownZero &= KnownZero2; 382 break; 383 case ISD::SHL: 384 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 385 if (SimplifyDemandedBits(Op.getOperand(0), DemandedMask >> SA->getValue(), 386 KnownZero, KnownOne, TLO, Depth+1)) 387 return true; 388 KnownZero <<= SA->getValue(); 389 KnownOne <<= SA->getValue(); 390 KnownZero |= (1ULL << SA->getValue())-1; // low bits known zero. 391 } 392 break; 393 case ISD::SRL: 394 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 395 MVT::ValueType VT = Op.getValueType(); 396 unsigned ShAmt = SA->getValue(); 397 398 // Compute the new bits that are at the top now. 399 uint64_t HighBits = (1ULL << ShAmt)-1; 400 HighBits <<= MVT::getSizeInBits(VT) - ShAmt; 401 uint64_t TypeMask = MVT::getIntVTBitMask(VT); 402 403 if (SimplifyDemandedBits(Op.getOperand(0), 404 (DemandedMask << ShAmt) & TypeMask, 405 KnownZero, KnownOne, TLO, Depth+1)) 406 return true; 407 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 408 KnownZero &= TypeMask; 409 KnownOne &= TypeMask; 410 KnownZero >>= ShAmt; 411 KnownOne >>= ShAmt; 412 KnownZero |= HighBits; // high bits known zero. 413 } 414 break; 415 case ISD::SRA: 416 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 417 MVT::ValueType VT = Op.getValueType(); 418 unsigned ShAmt = SA->getValue(); 419 420 // Compute the new bits that are at the top now. 421 uint64_t HighBits = (1ULL << ShAmt)-1; 422 HighBits <<= MVT::getSizeInBits(VT) - ShAmt; 423 uint64_t TypeMask = MVT::getIntVTBitMask(VT); 424 425 if (SimplifyDemandedBits(Op.getOperand(0), 426 (DemandedMask << ShAmt) & TypeMask, 427 KnownZero, KnownOne, TLO, Depth+1)) 428 return true; 429 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 430 KnownZero &= TypeMask; 431 KnownOne &= TypeMask; 432 KnownZero >>= SA->getValue(); 433 KnownOne >>= SA->getValue(); 434 435 // Handle the sign bits. 436 uint64_t SignBit = MVT::getIntVTSignBit(VT); 437 SignBit >>= SA->getValue(); // Adjust to where it is now in the mask. 438 439 // If the input sign bit is known to be zero, or if none of the top bits 440 // are demanded, turn this into an unsigned shift right. 441 if ((KnownZero & SignBit) || (HighBits & ~DemandedMask) == HighBits) { 442 return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::SRL, VT, Op.getOperand(0), 443 Op.getOperand(1))); 444 } else if (KnownOne & SignBit) { // New bits are known one. 445 KnownOne |= HighBits; 446 } 447 } 448 break; 449 case ISD::SIGN_EXTEND_INREG: { 450 MVT::ValueType VT = Op.getValueType(); 451 MVT::ValueType EVT = cast<VTSDNode>(Op.getOperand(1))->getVT(); 452 453 // Sign extension. Compute the demanded bits in the result that are not 454 // present in the input. 455 uint64_t NewBits = ~MVT::getIntVTBitMask(EVT) & DemandedMask; 456 457 // If none of the extended bits are demanded, eliminate the sextinreg. 458 if (NewBits == 0) 459 return TLO.CombineTo(Op, Op.getOperand(0)); 460 461 uint64_t InSignBit = MVT::getIntVTSignBit(EVT); 462 int64_t InputDemandedBits = DemandedMask & MVT::getIntVTBitMask(EVT); 463 464 // Since the sign extended bits are demanded, we know that the sign 465 // bit is demanded. 466 InputDemandedBits |= InSignBit; 467 468 if (SimplifyDemandedBits(Op.getOperand(0), InputDemandedBits, 469 KnownZero, KnownOne, TLO, Depth+1)) 470 return true; 471 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 472 473 // If the sign bit of the input is known set or clear, then we know the 474 // top bits of the result. 475 476 // If the input sign bit is known zero, convert this into a zero extension. 477 if (KnownZero & InSignBit) 478 return TLO.CombineTo(Op, 479 TLO.DAG.getZeroExtendInReg(Op.getOperand(0), EVT)); 480 481 if (KnownOne & InSignBit) { // Input sign bit known set 482 KnownOne |= NewBits; 483 KnownZero &= ~NewBits; 484 } else { // Input sign bit unknown 485 KnownZero &= ~NewBits; 486 KnownOne &= ~NewBits; 487 } 488 break; 489 } 490 case ISD::CTTZ: 491 case ISD::CTLZ: 492 case ISD::CTPOP: { 493 MVT::ValueType VT = Op.getValueType(); 494 unsigned LowBits = Log2_32(MVT::getSizeInBits(VT))+1; 495 KnownZero = ~((1ULL << LowBits)-1) & MVT::getIntVTBitMask(VT); 496 KnownOne = 0; 497 break; 498 } 499 case ISD::ZEXTLOAD: { 500 MVT::ValueType VT = cast<VTSDNode>(Op.getOperand(3))->getVT(); 501 KnownZero |= ~MVT::getIntVTBitMask(VT) & DemandedMask; 502 break; 503 } 504 case ISD::ZERO_EXTEND: { 505 uint64_t InMask = MVT::getIntVTBitMask(Op.getOperand(0).getValueType()); 506 507 // If none of the top bits are demanded, convert this into an any_extend. 508 uint64_t NewBits = (~InMask) & DemandedMask; 509 if (NewBits == 0) 510 return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::ANY_EXTEND, 511 Op.getValueType(), 512 Op.getOperand(0))); 513 514 if (SimplifyDemandedBits(Op.getOperand(0), DemandedMask & InMask, 515 KnownZero, KnownOne, TLO, Depth+1)) 516 return true; 517 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 518 KnownZero |= NewBits; 519 break; 520 } 521 case ISD::SIGN_EXTEND: { 522 MVT::ValueType InVT = Op.getOperand(0).getValueType(); 523 uint64_t InMask = MVT::getIntVTBitMask(InVT); 524 uint64_t InSignBit = MVT::getIntVTSignBit(InVT); 525 uint64_t NewBits = (~InMask) & DemandedMask; 526 527 // If none of the top bits are demanded, convert this into an any_extend. 528 if (NewBits == 0) 529 return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::ANY_EXTEND,Op.getValueType(), 530 Op.getOperand(0))); 531 532 // Since some of the sign extended bits are demanded, we know that the sign 533 // bit is demanded. 534 uint64_t InDemandedBits = DemandedMask & InMask; 535 InDemandedBits |= InSignBit; 536 537 if (SimplifyDemandedBits(Op.getOperand(0), InDemandedBits, KnownZero, 538 KnownOne, TLO, Depth+1)) 539 return true; 540 541 // If the sign bit is known zero, convert this to a zero extend. 542 if (KnownZero & InSignBit) 543 return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::ZERO_EXTEND, 544 Op.getValueType(), 545 Op.getOperand(0))); 546 547 // If the sign bit is known one, the top bits match. 548 if (KnownOne & InSignBit) { 549 KnownOne |= NewBits; 550 KnownZero &= ~NewBits; 551 } else { // Otherwise, top bits aren't known. 552 KnownOne &= ~NewBits; 553 KnownZero &= ~NewBits; 554 } 555 break; 556 } 557 case ISD::ANY_EXTEND: { 558 uint64_t InMask = MVT::getIntVTBitMask(Op.getOperand(0).getValueType()); 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 break; 564 } 565 case ISD::AssertZext: { 566 MVT::ValueType VT = cast<VTSDNode>(Op.getOperand(1))->getVT(); 567 uint64_t InMask = MVT::getIntVTBitMask(VT); 568 if (SimplifyDemandedBits(Op.getOperand(0), DemandedMask & InMask, 569 KnownZero, KnownOne, TLO, Depth+1)) 570 return true; 571 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 572 KnownZero |= ~InMask & DemandedMask; 573 break; 574 } 575 case ISD::ADD: 576 case ISD::SUB: 577 // Just use ComputeMaskedBits to compute output bits, there are no 578 // simplifications that can be done here, and sub always demands all input 579 // bits. 580 ComputeMaskedBits(Op, DemandedMask, KnownZero, KnownOne, Depth); 581 break; 582 } 583 584 // If we know the value of all of the demanded bits, return this as a 585 // constant. 586 if ((DemandedMask & (KnownZero|KnownOne)) == DemandedMask) 587 return TLO.CombineTo(Op, TLO.DAG.getConstant(KnownOne, Op.getValueType())); 588 589 return false; 590} 591 592/// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use 593/// this predicate to simplify operations downstream. Mask is known to be zero 594/// for bits that V cannot have. 595bool TargetLowering::MaskedValueIsZero(SDOperand Op, uint64_t Mask, 596 unsigned Depth) const { 597 uint64_t KnownZero, KnownOne; 598 ComputeMaskedBits(Op, Mask, KnownZero, KnownOne, Depth); 599 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 600 return (KnownZero & Mask) == Mask; 601} 602 603/// ComputeMaskedBits - Determine which of the bits specified in Mask are 604/// known to be either zero or one and return them in the KnownZero/KnownOne 605/// bitsets. This code only analyzes bits in Mask, in order to short-circuit 606/// processing. 607void TargetLowering::ComputeMaskedBits(SDOperand Op, uint64_t Mask, 608 uint64_t &KnownZero, uint64_t &KnownOne, 609 unsigned Depth) const { 610 KnownZero = KnownOne = 0; // Don't know anything. 611 if (Depth == 6 || Mask == 0) 612 return; // Limit search depth. 613 614 uint64_t KnownZero2, KnownOne2; 615 616 switch (Op.getOpcode()) { 617 case ISD::Constant: 618 // We know all of the bits for a constant! 619 KnownOne = cast<ConstantSDNode>(Op)->getValue() & Mask; 620 KnownZero = ~KnownOne & Mask; 621 return; 622 case ISD::AND: 623 // If either the LHS or the RHS are Zero, the result is zero. 624 ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1); 625 Mask &= ~KnownZero; 626 ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero2, KnownOne2, Depth+1); 627 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 628 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 629 630 // Output known-1 bits are only known if set in both the LHS & RHS. 631 KnownOne &= KnownOne2; 632 // Output known-0 are known to be clear if zero in either the LHS | RHS. 633 KnownZero |= KnownZero2; 634 return; 635 case ISD::OR: 636 ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1); 637 Mask &= ~KnownOne; 638 ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero2, KnownOne2, Depth+1); 639 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 640 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 641 642 // Output known-0 bits are only known if clear in both the LHS & RHS. 643 KnownZero &= KnownZero2; 644 // Output known-1 are known to be set if set in either the LHS | RHS. 645 KnownOne |= KnownOne2; 646 return; 647 case ISD::XOR: { 648 ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1); 649 ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero2, KnownOne2, Depth+1); 650 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 651 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 652 653 // Output known-0 bits are known if clear or set in both the LHS & RHS. 654 uint64_t KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2); 655 // Output known-1 are known to be set if set in only one of the LHS, RHS. 656 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2); 657 KnownZero = KnownZeroOut; 658 return; 659 } 660 case ISD::SELECT: 661 ComputeMaskedBits(Op.getOperand(2), Mask, KnownZero, KnownOne, Depth+1); 662 ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero2, KnownOne2, Depth+1); 663 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 664 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 665 666 // Only known if known in both the LHS and RHS. 667 KnownOne &= KnownOne2; 668 KnownZero &= KnownZero2; 669 return; 670 case ISD::SELECT_CC: 671 ComputeMaskedBits(Op.getOperand(3), Mask, KnownZero, KnownOne, Depth+1); 672 ComputeMaskedBits(Op.getOperand(2), Mask, KnownZero2, KnownOne2, Depth+1); 673 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 674 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 675 676 // Only known if known in both the LHS and RHS. 677 KnownOne &= KnownOne2; 678 KnownZero &= KnownZero2; 679 return; 680 case ISD::SETCC: 681 // If we know the result of a setcc has the top bits zero, use this info. 682 if (getSetCCResultContents() == TargetLowering::ZeroOrOneSetCCResult) 683 KnownZero |= (MVT::getIntVTBitMask(Op.getValueType()) ^ 1ULL); 684 return; 685 case ISD::SHL: 686 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0 687 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 688 Mask >>= SA->getValue(); 689 ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero, KnownOne, Depth+1); 690 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 691 KnownZero <<= SA->getValue(); 692 KnownOne <<= SA->getValue(); 693 KnownZero |= (1ULL << SA->getValue())-1; // low bits known zero. 694 } 695 return; 696 case ISD::SRL: 697 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0 698 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 699 uint64_t HighBits = (1ULL << SA->getValue())-1; 700 HighBits <<= MVT::getSizeInBits(Op.getValueType())-SA->getValue(); 701 Mask <<= SA->getValue(); 702 ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero, KnownOne, Depth+1); 703 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 704 KnownZero >>= SA->getValue(); 705 KnownOne >>= SA->getValue(); 706 KnownZero |= HighBits; // high bits known zero. 707 } 708 return; 709 case ISD::SRA: 710 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 711 uint64_t HighBits = (1ULL << SA->getValue())-1; 712 HighBits <<= MVT::getSizeInBits(Op.getValueType())-SA->getValue(); 713 Mask <<= SA->getValue(); 714 ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero, KnownOne, Depth+1); 715 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?"); 716 KnownZero >>= SA->getValue(); 717 KnownOne >>= SA->getValue(); 718 719 // Handle the sign bits. 720 uint64_t SignBit = 1ULL << (MVT::getSizeInBits(Op.getValueType())-1); 721 SignBit >>= SA->getValue(); // Adjust to where it is now in the mask. 722 723 if (KnownZero & SignBit) { // New bits are known zero. 724 KnownZero |= HighBits; 725 } else if (KnownOne & SignBit) { // New bits are known one. 726 KnownOne |= HighBits; 727 } 728 } 729 return; 730 case ISD::SIGN_EXTEND_INREG: { 731 MVT::ValueType VT = Op.getValueType(); 732 MVT::ValueType EVT = cast<VTSDNode>(Op.getOperand(1))->getVT(); 733 734 // Sign extension. Compute the demanded bits in the result that are not 735 // present in the input. 736 uint64_t NewBits = ~MVT::getIntVTBitMask(EVT) & Mask; 737 738 uint64_t InSignBit = MVT::getIntVTSignBit(EVT); 739 int64_t InputDemandedBits = Mask & MVT::getIntVTBitMask(EVT); 740 741 // If the sign extended bits are demanded, we know that the sign 742 // bit is demanded. 743 if (NewBits) 744 InputDemandedBits |= InSignBit; 745 746 ComputeMaskedBits(Op.getOperand(0), InputDemandedBits, 747 KnownZero, KnownOne, Depth+1); 748 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 749 750 // If the sign bit of the input is known set or clear, then we know the 751 // top bits of the result. 752 if (KnownZero & InSignBit) { // Input sign bit known clear 753 KnownZero |= NewBits; 754 KnownOne &= ~NewBits; 755 } else if (KnownOne & InSignBit) { // Input sign bit known set 756 KnownOne |= NewBits; 757 KnownZero &= ~NewBits; 758 } else { // Input sign bit unknown 759 KnownZero &= ~NewBits; 760 KnownOne &= ~NewBits; 761 } 762 return; 763 } 764 case ISD::CTTZ: 765 case ISD::CTLZ: 766 case ISD::CTPOP: { 767 MVT::ValueType VT = Op.getValueType(); 768 unsigned LowBits = Log2_32(MVT::getSizeInBits(VT))+1; 769 KnownZero = ~((1ULL << LowBits)-1) & MVT::getIntVTBitMask(VT); 770 KnownOne = 0; 771 return; 772 } 773 case ISD::ZEXTLOAD: { 774 MVT::ValueType VT = cast<VTSDNode>(Op.getOperand(3))->getVT(); 775 KnownZero |= ~MVT::getIntVTBitMask(VT) & Mask; 776 return; 777 } 778 case ISD::ZERO_EXTEND: { 779 uint64_t InMask = MVT::getIntVTBitMask(Op.getOperand(0).getValueType()); 780 uint64_t NewBits = (~InMask) & Mask; 781 ComputeMaskedBits(Op.getOperand(0), Mask & InMask, KnownZero, 782 KnownOne, Depth+1); 783 KnownZero |= NewBits & Mask; 784 KnownOne &= ~NewBits; 785 return; 786 } 787 case ISD::SIGN_EXTEND: { 788 MVT::ValueType InVT = Op.getOperand(0).getValueType(); 789 unsigned InBits = MVT::getSizeInBits(InVT); 790 uint64_t InMask = MVT::getIntVTBitMask(InVT); 791 uint64_t InSignBit = 1ULL << (InBits-1); 792 uint64_t NewBits = (~InMask) & Mask; 793 uint64_t InDemandedBits = Mask & InMask; 794 795 // If any of the sign extended bits are demanded, we know that the sign 796 // bit is demanded. 797 if (NewBits & Mask) 798 InDemandedBits |= InSignBit; 799 800 ComputeMaskedBits(Op.getOperand(0), InDemandedBits, KnownZero, 801 KnownOne, Depth+1); 802 // If the sign bit is known zero or one, the top bits match. 803 if (KnownZero & InSignBit) { 804 KnownZero |= NewBits; 805 KnownOne &= ~NewBits; 806 } else if (KnownOne & InSignBit) { 807 KnownOne |= NewBits; 808 KnownZero &= ~NewBits; 809 } else { // Otherwise, top bits aren't known. 810 KnownOne &= ~NewBits; 811 KnownZero &= ~NewBits; 812 } 813 return; 814 } 815 case ISD::ANY_EXTEND: { 816 MVT::ValueType VT = Op.getOperand(0).getValueType(); 817 ComputeMaskedBits(Op.getOperand(0), Mask & MVT::getIntVTBitMask(VT), 818 KnownZero, KnownOne, Depth+1); 819 return; 820 } 821 case ISD::AssertZext: { 822 MVT::ValueType VT = cast<VTSDNode>(Op.getOperand(1))->getVT(); 823 uint64_t InMask = MVT::getIntVTBitMask(VT); 824 ComputeMaskedBits(Op.getOperand(0), Mask & InMask, KnownZero, 825 KnownOne, Depth+1); 826 KnownZero |= (~InMask) & Mask; 827 return; 828 } 829 case ISD::ADD: { 830 // If either the LHS or the RHS are Zero, the result is zero. 831 ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1); 832 ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero2, KnownOne2, Depth+1); 833 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 834 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 835 836 // Output known-0 bits are known if clear or set in both the low clear bits 837 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the 838 // low 3 bits clear. 839 uint64_t KnownZeroOut = std::min(CountTrailingZeros_64(~KnownZero), 840 CountTrailingZeros_64(~KnownZero2)); 841 842 KnownZero = (1ULL << KnownZeroOut) - 1; 843 KnownOne = 0; 844 return; 845 } 846 case ISD::SUB: { 847 ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)); 848 if (!CLHS) return; 849 850 // We know that the top bits of C-X are clear if X contains less bits 851 // than C (i.e. no wrap-around can happen). For example, 20-X is 852 // positive if we can prove that X is >= 0 and < 16. 853 MVT::ValueType VT = CLHS->getValueType(0); 854 if ((CLHS->getValue() & MVT::getIntVTSignBit(VT)) == 0) { // sign bit clear 855 unsigned NLZ = CountLeadingZeros_64(CLHS->getValue()+1); 856 uint64_t MaskV = (1ULL << (63-NLZ))-1; // NLZ can't be 64 with no sign bit 857 MaskV = ~MaskV & MVT::getIntVTBitMask(VT); 858 ComputeMaskedBits(Op.getOperand(1), MaskV, KnownZero, KnownOne, Depth+1); 859 860 // If all of the MaskV bits are known to be zero, then we know the output 861 // top bits are zero, because we now know that the output is from [0-C]. 862 if ((KnownZero & MaskV) == MaskV) { 863 unsigned NLZ2 = CountLeadingZeros_64(CLHS->getValue()); 864 KnownZero = ~((1ULL << (64-NLZ2))-1) & Mask; // Top bits known zero. 865 KnownOne = 0; // No one bits known. 866 } else { 867 KnownOne = KnownOne = 0; // Otherwise, nothing known. 868 } 869 } 870 return; 871 } 872 default: 873 // Allow the target to implement this method for its nodes. 874 if (Op.getOpcode() >= ISD::BUILTIN_OP_END) 875 computeMaskedBitsForTargetNode(Op, Mask, KnownZero, KnownOne); 876 return; 877 } 878} 879 880/// computeMaskedBitsForTargetNode - Determine which of the bits specified 881/// in Mask are known to be either zero or one and return them in the 882/// KnownZero/KnownOne bitsets. 883void TargetLowering::computeMaskedBitsForTargetNode(const SDOperand Op, 884 uint64_t Mask, 885 uint64_t &KnownZero, 886 uint64_t &KnownOne, 887 unsigned Depth) const { 888 assert(Op.getOpcode() >= ISD::BUILTIN_OP_END && 889 "Should use MaskedValueIsZero if you don't know whether Op" 890 " is a target node!"); 891 KnownZero = 0; 892 KnownOne = 0; 893} 894 895SDOperand TargetLowering:: 896PerformDAGCombine(SDNode *N, DAGCombinerInfo &DCI) const { 897 // Default implementation: no optimization. 898 return SDOperand(); 899} 900 901//===----------------------------------------------------------------------===// 902// Inline Assembler Implementation Methods 903//===----------------------------------------------------------------------===// 904 905TargetLowering::ConstraintType 906TargetLowering::getConstraintType(char ConstraintLetter) const { 907 // FIXME: lots more standard ones to handle. 908 switch (ConstraintLetter) { 909 default: return C_Unknown; 910 case 'r': return C_RegisterClass; 911 case 'm': // memory 912 case 'o': // offsetable 913 case 'V': // not offsetable 914 return C_Memory; 915 case 'i': // Simple Integer or Relocatable Constant 916 case 'n': // Simple Integer 917 case 's': // Relocatable Constant 918 case 'I': // Target registers. 919 case 'J': 920 case 'K': 921 case 'L': 922 case 'M': 923 case 'N': 924 case 'O': 925 case 'P': 926 return C_Other; 927 } 928} 929 930bool TargetLowering::isOperandValidForConstraint(SDOperand Op, 931 char ConstraintLetter) { 932 switch (ConstraintLetter) { 933 default: return false; 934 case 'i': // Simple Integer or Relocatable Constant 935 case 'n': // Simple Integer 936 case 's': // Relocatable Constant 937 return true; // FIXME: not right. 938 } 939} 940 941 942std::vector<unsigned> TargetLowering:: 943getRegClassForInlineAsmConstraint(const std::string &Constraint, 944 MVT::ValueType VT) const { 945 return std::vector<unsigned>(); 946} 947 948 949std::pair<unsigned, const TargetRegisterClass*> TargetLowering:: 950getRegForInlineAsmConstraint(const std::string &Constraint, 951 MVT::ValueType VT) const { 952 if (Constraint[0] != '{') 953 return std::pair<unsigned, const TargetRegisterClass*>(0, 0); 954 assert(*(Constraint.end()-1) == '}' && "Not a brace enclosed constraint?"); 955 956 // Remove the braces from around the name. 957 std::string RegName(Constraint.begin()+1, Constraint.end()-1); 958 959 // Figure out which register class contains this reg. 960 const MRegisterInfo *RI = TM.getRegisterInfo(); 961 for (MRegisterInfo::regclass_iterator RCI = RI->regclass_begin(), 962 E = RI->regclass_end(); RCI != E; ++RCI) { 963 const TargetRegisterClass *RC = *RCI; 964 965 // If none of the the value types for this register class are valid, we 966 // can't use it. For example, 64-bit reg classes on 32-bit targets. 967 bool isLegal = false; 968 for (TargetRegisterClass::vt_iterator I = RC->vt_begin(), E = RC->vt_end(); 969 I != E; ++I) { 970 if (isTypeLegal(*I)) { 971 isLegal = true; 972 break; 973 } 974 } 975 976 if (!isLegal) continue; 977 978 for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); 979 I != E; ++I) { 980 if (StringsEqualNoCase(RegName, RI->get(*I).Name)) 981 return std::make_pair(*I, RC); 982 } 983 } 984 985 return std::pair<unsigned, const TargetRegisterClass*>(0, 0); 986} 987 988//===----------------------------------------------------------------------===// 989// Loop Strength Reduction hooks 990//===----------------------------------------------------------------------===// 991 992/// isLegalAddressImmediate - Return true if the integer value or 993/// GlobalValue can be used as the offset of the target addressing mode. 994bool TargetLowering::isLegalAddressImmediate(int64_t V) const { 995 return false; 996} 997bool TargetLowering::isLegalAddressImmediate(GlobalValue *GV) const { 998 return false; 999} 1000