TargetLowering.cpp revision 7acf5f39fea463df5ad196affbef0176f3b25e0f
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/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" 22using namespace llvm; 23 24TargetLowering::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)); 30 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; 44 JumpBufSize = 0; 45 JumpBufAlignment = 0; 46} 47 48TargetLowering::~TargetLowering() {} 49 50/// setValueTypeAction - Set the action for a particular value type. This 51/// assumes an action has not already been set for this value type. 52static void SetValueTypeAction(MVT::ValueType VT, 53 TargetLowering::LegalizeAction Action, 54 TargetLowering &TLI, 55 MVT::ValueType *TransformToType, 56 TargetLowering::ValueTypeActionImpl &ValueTypeActions) { 57 ValueTypeActions.setTypeAction(VT, Action); 58 if (Action == TargetLowering::Promote) { 59 MVT::ValueType PromoteTo; 60 if (VT == MVT::f32) 61 PromoteTo = MVT::f64; 62 else { 63 unsigned LargerReg = VT+1; 64 while (!TLI.isTypeLegal((MVT::ValueType)LargerReg)) { 65 ++LargerReg; 66 assert(MVT::isInteger((MVT::ValueType)LargerReg) && 67 "Nothing to promote to??"); 68 } 69 PromoteTo = (MVT::ValueType)LargerReg; 70 } 71 72 assert(MVT::isInteger(VT) == MVT::isInteger(PromoteTo) && 73 MVT::isFloatingPoint(VT) == MVT::isFloatingPoint(PromoteTo) && 74 "Can only promote from int->int or fp->fp!"); 75 assert(VT < PromoteTo && "Must promote to a larger type!"); 76 TransformToType[VT] = PromoteTo; 77 } else if (Action == TargetLowering::Expand) { 78 assert((VT == MVT::Vector || MVT::isInteger(VT)) && VT > MVT::i8 && 79 "Cannot expand this type: target must support SOME integer reg!"); 80 // Expand to the next smaller integer type! 81 TransformToType[VT] = (MVT::ValueType)(VT-1); 82 } 83} 84 85 86/// computeRegisterProperties - Once all of the register classes are added, 87/// this allows us to compute derived properties we expose. 88void TargetLowering::computeRegisterProperties() { 89 assert(MVT::LAST_VALUETYPE <= 32 && 90 "Too many value types for ValueTypeActions to hold!"); 91 92 // Everything defaults to one. 93 for (unsigned i = 0; i != MVT::LAST_VALUETYPE; ++i) 94 NumElementsForVT[i] = 1; 95 96 // Find the largest integer register class. 97 unsigned LargestIntReg = MVT::i128; 98 for (; RegClassForVT[LargestIntReg] == 0; --LargestIntReg) 99 assert(LargestIntReg != MVT::i1 && "No integer registers defined!"); 100 101 // Every integer value type larger than this largest register takes twice as 102 // many registers to represent as the previous ValueType. 103 unsigned ExpandedReg = LargestIntReg; ++LargestIntReg; 104 for (++ExpandedReg; MVT::isInteger((MVT::ValueType)ExpandedReg);++ExpandedReg) 105 NumElementsForVT[ExpandedReg] = 2*NumElementsForVT[ExpandedReg-1]; 106 107 // Inspect all of the ValueType's possible, deciding how to process them. 108 for (unsigned IntReg = MVT::i1; IntReg <= MVT::i128; ++IntReg) 109 // If we are expanding this type, expand it! 110 if (getNumElements((MVT::ValueType)IntReg) != 1) 111 SetValueTypeAction((MVT::ValueType)IntReg, Expand, *this, TransformToType, 112 ValueTypeActions); 113 else if (!isTypeLegal((MVT::ValueType)IntReg)) 114 // Otherwise, if we don't have native support, we must promote to a 115 // larger type. 116 SetValueTypeAction((MVT::ValueType)IntReg, Promote, *this, 117 TransformToType, ValueTypeActions); 118 else 119 TransformToType[(MVT::ValueType)IntReg] = (MVT::ValueType)IntReg; 120 121 // If the target does not have native support for F32, promote it to F64. 122 if (!isTypeLegal(MVT::f32)) 123 SetValueTypeAction(MVT::f32, Promote, *this, 124 TransformToType, ValueTypeActions); 125 else 126 TransformToType[MVT::f32] = MVT::f32; 127 128 // Set MVT::Vector to always be Expanded 129 SetValueTypeAction(MVT::Vector, Expand, *this, TransformToType, 130 ValueTypeActions); 131 132 // Loop over all of the legal vector value types, specifying an identity type 133 // transformation. 134 for (unsigned i = MVT::FIRST_VECTOR_VALUETYPE; 135 i <= MVT::LAST_VECTOR_VALUETYPE; ++i) { 136 if (isTypeLegal((MVT::ValueType)i)) 137 TransformToType[i] = (MVT::ValueType)i; 138 } 139 140 assert(isTypeLegal(MVT::f64) && "Target does not support FP?"); 141 TransformToType[MVT::f64] = MVT::f64; 142} 143 144const char *TargetLowering::getTargetNodeName(unsigned Opcode) const { 145 return NULL; 146} 147 148/// getPackedTypeBreakdown - Packed types are broken down into some number of 149/// legal first class types. For example, <8 x float> maps to 2 MVT::v4f32 150/// with Altivec or SSE1, or 8 promoted MVT::f64 values with the X86 FP stack. 151/// 152/// This method returns the number and type of the resultant breakdown. 153/// 154unsigned TargetLowering::getPackedTypeBreakdown(const PackedType *PTy, 155 MVT::ValueType &PTyElementVT, 156 MVT::ValueType &PTyLegalElementVT) const { 157 // Figure out the right, legal destination reg to copy into. 158 unsigned NumElts = PTy->getNumElements(); 159 MVT::ValueType EltTy = getValueType(PTy->getElementType()); 160 161 unsigned NumVectorRegs = 1; 162 163 // Divide the input until we get to a supported size. This will always 164 // end with a scalar if the target doesn't support vectors. 165 while (NumElts > 1 && !isTypeLegal(getVectorType(EltTy, NumElts))) { 166 NumElts >>= 1; 167 NumVectorRegs <<= 1; 168 } 169 170 MVT::ValueType VT; 171 if (NumElts == 1) { 172 VT = EltTy; 173 } else { 174 VT = getVectorType(EltTy, NumElts); 175 } 176 PTyElementVT = VT; 177 178 MVT::ValueType DestVT = getTypeToTransformTo(VT); 179 PTyLegalElementVT = DestVT; 180 if (DestVT < VT) { 181 // Value is expanded, e.g. i64 -> i16. 182 return NumVectorRegs*(MVT::getSizeInBits(VT)/MVT::getSizeInBits(DestVT)); 183 } else { 184 // Otherwise, promotion or legal types use the same number of registers as 185 // the vector decimated to the appropriate level. 186 return NumVectorRegs; 187 } 188 189 return 1; 190} 191 192//===----------------------------------------------------------------------===// 193// Optimization Methods 194//===----------------------------------------------------------------------===// 195 196/// ShrinkDemandedConstant - Check to see if the specified operand of the 197/// specified instruction is a constant integer. If so, check to see if there 198/// are any bits set in the constant that are not demanded. If so, shrink the 199/// constant and return true. 200bool TargetLowering::TargetLoweringOpt::ShrinkDemandedConstant(SDOperand Op, 201 uint64_t Demanded) { 202 // FIXME: ISD::SELECT, ISD::SELECT_CC 203 switch(Op.getOpcode()) { 204 default: break; 205 case ISD::AND: 206 case ISD::OR: 207 case ISD::XOR: 208 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) 209 if ((~Demanded & C->getValue()) != 0) { 210 MVT::ValueType VT = Op.getValueType(); 211 SDOperand New = DAG.getNode(Op.getOpcode(), VT, Op.getOperand(0), 212 DAG.getConstant(Demanded & C->getValue(), 213 VT)); 214 return CombineTo(Op, New); 215 } 216 break; 217 } 218 return false; 219} 220 221/// SimplifyDemandedBits - Look at Op. At this point, we know that only the 222/// DemandedMask bits of the result of Op are ever used downstream. If we can 223/// use this information to simplify Op, create a new simplified DAG node and 224/// return true, returning the original and new nodes in Old and New. Otherwise, 225/// analyze the expression and return a mask of KnownOne and KnownZero bits for 226/// the expression (used to simplify the caller). The KnownZero/One bits may 227/// only be accurate for those bits in the DemandedMask. 228bool TargetLowering::SimplifyDemandedBits(SDOperand Op, uint64_t DemandedMask, 229 uint64_t &KnownZero, 230 uint64_t &KnownOne, 231 TargetLoweringOpt &TLO, 232 unsigned Depth) const { 233 KnownZero = KnownOne = 0; // Don't know anything. 234 // Other users may use these bits. 235 if (!Op.Val->hasOneUse()) { 236 if (Depth != 0) { 237 // If not at the root, Just compute the KnownZero/KnownOne bits to 238 // simplify things downstream. 239 ComputeMaskedBits(Op, DemandedMask, KnownZero, KnownOne, Depth); 240 return false; 241 } 242 // If this is the root being simplified, allow it to have multiple uses, 243 // just set the DemandedMask to all bits. 244 DemandedMask = MVT::getIntVTBitMask(Op.getValueType()); 245 } else if (DemandedMask == 0) { 246 // Not demanding any bits from Op. 247 if (Op.getOpcode() != ISD::UNDEF) 248 return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::UNDEF, Op.getValueType())); 249 return false; 250 } else if (Depth == 6) { // Limit search depth. 251 return false; 252 } 253 254 uint64_t KnownZero2, KnownOne2, KnownZeroOut, KnownOneOut; 255 switch (Op.getOpcode()) { 256 case ISD::Constant: 257 // We know all of the bits for a constant! 258 KnownOne = cast<ConstantSDNode>(Op)->getValue() & DemandedMask; 259 KnownZero = ~KnownOne & DemandedMask; 260 return false; // Don't fall through, will infinitely loop. 261 case ISD::AND: 262 // If the RHS is a constant, check to see if the LHS would be zero without 263 // using the bits from the RHS. Below, we use knowledge about the RHS to 264 // simplify the LHS, here we're using information from the LHS to simplify 265 // the RHS. 266 if (ConstantSDNode *RHSC = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 267 uint64_t LHSZero, LHSOne; 268 ComputeMaskedBits(Op.getOperand(0), DemandedMask, 269 LHSZero, LHSOne, Depth+1); 270 // If the LHS already has zeros where RHSC does, this and is dead. 271 if ((LHSZero & DemandedMask) == (~RHSC->getValue() & DemandedMask)) 272 return TLO.CombineTo(Op, Op.getOperand(0)); 273 // If any of the set bits in the RHS are known zero on the LHS, shrink 274 // the constant. 275 if (TLO.ShrinkDemandedConstant(Op, ~LHSZero & DemandedMask)) 276 return true; 277 } 278 279 if (SimplifyDemandedBits(Op.getOperand(1), DemandedMask, KnownZero, 280 KnownOne, TLO, Depth+1)) 281 return true; 282 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 283 if (SimplifyDemandedBits(Op.getOperand(0), DemandedMask & ~KnownZero, 284 KnownZero2, KnownOne2, TLO, Depth+1)) 285 return true; 286 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 287 288 // If all of the demanded bits are known one on one side, return the other. 289 // These bits cannot contribute to the result of the 'and'. 290 if ((DemandedMask & ~KnownZero2 & KnownOne)==(DemandedMask & ~KnownZero2)) 291 return TLO.CombineTo(Op, Op.getOperand(0)); 292 if ((DemandedMask & ~KnownZero & KnownOne2)==(DemandedMask & ~KnownZero)) 293 return TLO.CombineTo(Op, Op.getOperand(1)); 294 // If all of the demanded bits in the inputs are known zeros, return zero. 295 if ((DemandedMask & (KnownZero|KnownZero2)) == DemandedMask) 296 return TLO.CombineTo(Op, TLO.DAG.getConstant(0, Op.getValueType())); 297 // If the RHS is a constant, see if we can simplify it. 298 if (TLO.ShrinkDemandedConstant(Op, DemandedMask & ~KnownZero2)) 299 return true; 300 301 // Output known-1 bits are only known if set in both the LHS & RHS. 302 KnownOne &= KnownOne2; 303 // Output known-0 are known to be clear if zero in either the LHS | RHS. 304 KnownZero |= KnownZero2; 305 break; 306 case ISD::OR: 307 if (SimplifyDemandedBits(Op.getOperand(1), DemandedMask, KnownZero, 308 KnownOne, TLO, Depth+1)) 309 return true; 310 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 311 if (SimplifyDemandedBits(Op.getOperand(0), DemandedMask & ~KnownOne, 312 KnownZero2, KnownOne2, TLO, Depth+1)) 313 return true; 314 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 315 316 // If all of the demanded bits are known zero on one side, return the other. 317 // These bits cannot contribute to the result of the 'or'. 318 if ((DemandedMask & ~KnownOne2 & KnownZero) == (DemandedMask & ~KnownOne2)) 319 return TLO.CombineTo(Op, Op.getOperand(0)); 320 if ((DemandedMask & ~KnownOne & KnownZero2) == (DemandedMask & ~KnownOne)) 321 return TLO.CombineTo(Op, Op.getOperand(1)); 322 // If all of the potentially set bits on one side are known to be set on 323 // the other side, just use the 'other' side. 324 if ((DemandedMask & (~KnownZero) & KnownOne2) == 325 (DemandedMask & (~KnownZero))) 326 return TLO.CombineTo(Op, Op.getOperand(0)); 327 if ((DemandedMask & (~KnownZero2) & KnownOne) == 328 (DemandedMask & (~KnownZero2))) 329 return TLO.CombineTo(Op, Op.getOperand(1)); 330 // If the RHS is a constant, see if we can simplify it. 331 if (TLO.ShrinkDemandedConstant(Op, DemandedMask)) 332 return true; 333 334 // Output known-0 bits are only known if clear in both the LHS & RHS. 335 KnownZero &= KnownZero2; 336 // Output known-1 are known to be set if set in either the LHS | RHS. 337 KnownOne |= KnownOne2; 338 break; 339 case ISD::XOR: 340 if (SimplifyDemandedBits(Op.getOperand(1), DemandedMask, KnownZero, 341 KnownOne, TLO, Depth+1)) 342 return true; 343 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 344 if (SimplifyDemandedBits(Op.getOperand(0), DemandedMask, KnownZero2, 345 KnownOne2, TLO, Depth+1)) 346 return true; 347 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 348 349 // If all of the demanded bits are known zero on one side, return the other. 350 // These bits cannot contribute to the result of the 'xor'. 351 if ((DemandedMask & KnownZero) == DemandedMask) 352 return TLO.CombineTo(Op, Op.getOperand(0)); 353 if ((DemandedMask & KnownZero2) == DemandedMask) 354 return TLO.CombineTo(Op, Op.getOperand(1)); 355 356 // Output known-0 bits are known if clear or set in both the LHS & RHS. 357 KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2); 358 // Output known-1 are known to be set if set in only one of the LHS, RHS. 359 KnownOneOut = (KnownZero & KnownOne2) | (KnownOne & KnownZero2); 360 361 // If all of the unknown bits are known to be zero on one side or the other 362 // (but not both) turn this into an *inclusive* or. 363 // e.g. (A & C1)^(B & C2) -> (A & C1)|(B & C2) iff C1&C2 == 0 364 if (uint64_t UnknownBits = DemandedMask & ~(KnownZeroOut|KnownOneOut)) 365 if ((UnknownBits & (KnownZero|KnownZero2)) == UnknownBits) 366 return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::OR, Op.getValueType(), 367 Op.getOperand(0), 368 Op.getOperand(1))); 369 // If all of the demanded bits on one side are known, and all of the set 370 // bits on that side are also known to be set on the other side, turn this 371 // into an AND, as we know the bits will be cleared. 372 // e.g. (X | C1) ^ C2 --> (X | C1) & ~C2 iff (C1&C2) == C2 373 if ((DemandedMask & (KnownZero|KnownOne)) == DemandedMask) { // all known 374 if ((KnownOne & KnownOne2) == KnownOne) { 375 MVT::ValueType VT = Op.getValueType(); 376 SDOperand ANDC = TLO.DAG.getConstant(~KnownOne & DemandedMask, VT); 377 return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::AND, VT, Op.getOperand(0), 378 ANDC)); 379 } 380 } 381 382 // If the RHS is a constant, see if we can simplify it. 383 // FIXME: for XOR, we prefer to force bits to 1 if they will make a -1. 384 if (TLO.ShrinkDemandedConstant(Op, DemandedMask)) 385 return true; 386 387 KnownZero = KnownZeroOut; 388 KnownOne = KnownOneOut; 389 break; 390 case ISD::SETCC: 391 // If we know the result of a setcc has the top bits zero, use this info. 392 if (getSetCCResultContents() == TargetLowering::ZeroOrOneSetCCResult) 393 KnownZero |= (MVT::getIntVTBitMask(Op.getValueType()) ^ 1ULL); 394 break; 395 case ISD::SELECT: 396 if (SimplifyDemandedBits(Op.getOperand(2), DemandedMask, KnownZero, 397 KnownOne, TLO, Depth+1)) 398 return true; 399 if (SimplifyDemandedBits(Op.getOperand(1), DemandedMask, KnownZero2, 400 KnownOne2, TLO, Depth+1)) 401 return true; 402 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 403 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 404 405 // If the operands are constants, see if we can simplify them. 406 if (TLO.ShrinkDemandedConstant(Op, DemandedMask)) 407 return true; 408 409 // Only known if known in both the LHS and RHS. 410 KnownOne &= KnownOne2; 411 KnownZero &= KnownZero2; 412 break; 413 case ISD::SELECT_CC: 414 if (SimplifyDemandedBits(Op.getOperand(3), DemandedMask, KnownZero, 415 KnownOne, TLO, Depth+1)) 416 return true; 417 if (SimplifyDemandedBits(Op.getOperand(2), DemandedMask, KnownZero2, 418 KnownOne2, TLO, Depth+1)) 419 return true; 420 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 421 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 422 423 // If the operands are constants, see if we can simplify them. 424 if (TLO.ShrinkDemandedConstant(Op, DemandedMask)) 425 return true; 426 427 // Only known if known in both the LHS and RHS. 428 KnownOne &= KnownOne2; 429 KnownZero &= KnownZero2; 430 break; 431 case ISD::SHL: 432 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 433 if (SimplifyDemandedBits(Op.getOperand(0), DemandedMask >> SA->getValue(), 434 KnownZero, KnownOne, TLO, Depth+1)) 435 return true; 436 KnownZero <<= SA->getValue(); 437 KnownOne <<= SA->getValue(); 438 KnownZero |= (1ULL << SA->getValue())-1; // low bits known zero. 439 } 440 break; 441 case ISD::SRL: 442 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 443 MVT::ValueType VT = Op.getValueType(); 444 unsigned ShAmt = SA->getValue(); 445 446 // Compute the new bits that are at the top now. 447 uint64_t TypeMask = MVT::getIntVTBitMask(VT); 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 458 uint64_t HighBits = (1ULL << ShAmt)-1; 459 HighBits <<= MVT::getSizeInBits(VT) - ShAmt; 460 KnownZero |= HighBits; // High bits known zero. 461 } 462 break; 463 case ISD::SRA: 464 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 465 MVT::ValueType VT = Op.getValueType(); 466 unsigned ShAmt = SA->getValue(); 467 468 // Compute the new bits that are at the top now. 469 uint64_t TypeMask = MVT::getIntVTBitMask(VT); 470 471 uint64_t InDemandedMask = (DemandedMask << ShAmt) & TypeMask; 472 473 // If any of the demanded bits are produced by the sign extension, we also 474 // demand the input sign bit. 475 uint64_t HighBits = (1ULL << ShAmt)-1; 476 HighBits <<= MVT::getSizeInBits(VT) - ShAmt; 477 if (HighBits & DemandedMask) 478 InDemandedMask |= MVT::getIntVTSignBit(VT); 479 480 if (SimplifyDemandedBits(Op.getOperand(0), InDemandedMask, 481 KnownZero, KnownOne, TLO, Depth+1)) 482 return true; 483 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 484 KnownZero &= TypeMask; 485 KnownOne &= TypeMask; 486 KnownZero >>= ShAmt; 487 KnownOne >>= ShAmt; 488 489 // Handle the sign bits. 490 uint64_t SignBit = MVT::getIntVTSignBit(VT); 491 SignBit >>= ShAmt; // Adjust to where it is now in the mask. 492 493 // If the input sign bit is known to be zero, or if none of the top bits 494 // are demanded, turn this into an unsigned shift right. 495 if ((KnownZero & SignBit) || (HighBits & ~DemandedMask) == HighBits) { 496 return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::SRL, VT, Op.getOperand(0), 497 Op.getOperand(1))); 498 } else if (KnownOne & SignBit) { // New bits are known one. 499 KnownOne |= HighBits; 500 } 501 } 502 break; 503 case ISD::SIGN_EXTEND_INREG: { 504 MVT::ValueType VT = Op.getValueType(); 505 MVT::ValueType EVT = cast<VTSDNode>(Op.getOperand(1))->getVT(); 506 507 // Sign extension. Compute the demanded bits in the result that are not 508 // present in the input. 509 uint64_t NewBits = ~MVT::getIntVTBitMask(EVT) & DemandedMask; 510 511 // If none of the extended bits are demanded, eliminate the sextinreg. 512 if (NewBits == 0) 513 return TLO.CombineTo(Op, Op.getOperand(0)); 514 515 uint64_t InSignBit = MVT::getIntVTSignBit(EVT); 516 int64_t InputDemandedBits = DemandedMask & MVT::getIntVTBitMask(EVT); 517 518 // Since the sign extended bits are demanded, we know that the sign 519 // bit is demanded. 520 InputDemandedBits |= InSignBit; 521 522 if (SimplifyDemandedBits(Op.getOperand(0), InputDemandedBits, 523 KnownZero, KnownOne, TLO, Depth+1)) 524 return true; 525 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 526 527 // If the sign bit of the input is known set or clear, then we know the 528 // top bits of the result. 529 530 // If the input sign bit is known zero, convert this into a zero extension. 531 if (KnownZero & InSignBit) 532 return TLO.CombineTo(Op, 533 TLO.DAG.getZeroExtendInReg(Op.getOperand(0), EVT)); 534 535 if (KnownOne & InSignBit) { // Input sign bit known set 536 KnownOne |= NewBits; 537 KnownZero &= ~NewBits; 538 } else { // Input sign bit unknown 539 KnownZero &= ~NewBits; 540 KnownOne &= ~NewBits; 541 } 542 break; 543 } 544 case ISD::CTTZ: 545 case ISD::CTLZ: 546 case ISD::CTPOP: { 547 MVT::ValueType VT = Op.getValueType(); 548 unsigned LowBits = Log2_32(MVT::getSizeInBits(VT))+1; 549 KnownZero = ~((1ULL << LowBits)-1) & MVT::getIntVTBitMask(VT); 550 KnownOne = 0; 551 break; 552 } 553 case ISD::ZEXTLOAD: { 554 MVT::ValueType VT = cast<VTSDNode>(Op.getOperand(3))->getVT(); 555 KnownZero |= ~MVT::getIntVTBitMask(VT) & DemandedMask; 556 break; 557 } 558 case ISD::ZERO_EXTEND: { 559 uint64_t InMask = MVT::getIntVTBitMask(Op.getOperand(0).getValueType()); 560 561 // If none of the top bits are demanded, convert this into an any_extend. 562 uint64_t NewBits = (~InMask) & DemandedMask; 563 if (NewBits == 0) 564 return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::ANY_EXTEND, 565 Op.getValueType(), 566 Op.getOperand(0))); 567 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 |= NewBits; 573 break; 574 } 575 case ISD::SIGN_EXTEND: { 576 MVT::ValueType InVT = Op.getOperand(0).getValueType(); 577 uint64_t InMask = MVT::getIntVTBitMask(InVT); 578 uint64_t InSignBit = MVT::getIntVTSignBit(InVT); 579 uint64_t NewBits = (~InMask) & DemandedMask; 580 581 // If none of the top bits are demanded, convert this into an any_extend. 582 if (NewBits == 0) 583 return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::ANY_EXTEND,Op.getValueType(), 584 Op.getOperand(0))); 585 586 // Since some of the sign extended bits are demanded, we know that the sign 587 // bit is demanded. 588 uint64_t InDemandedBits = DemandedMask & InMask; 589 InDemandedBits |= InSignBit; 590 591 if (SimplifyDemandedBits(Op.getOperand(0), InDemandedBits, KnownZero, 592 KnownOne, TLO, Depth+1)) 593 return true; 594 595 // If the sign bit is known zero, convert this to a zero extend. 596 if (KnownZero & InSignBit) 597 return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::ZERO_EXTEND, 598 Op.getValueType(), 599 Op.getOperand(0))); 600 601 // If the sign bit is known one, the top bits match. 602 if (KnownOne & InSignBit) { 603 KnownOne |= NewBits; 604 KnownZero &= ~NewBits; 605 } else { // Otherwise, top bits aren't known. 606 KnownOne &= ~NewBits; 607 KnownZero &= ~NewBits; 608 } 609 break; 610 } 611 case ISD::ANY_EXTEND: { 612 uint64_t InMask = MVT::getIntVTBitMask(Op.getOperand(0).getValueType()); 613 if (SimplifyDemandedBits(Op.getOperand(0), DemandedMask & InMask, 614 KnownZero, KnownOne, TLO, Depth+1)) 615 return true; 616 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 617 break; 618 } 619 case ISD::TRUNCATE: { 620 // Simplify the input, using demanded bit information, and compute the known 621 // zero/one bits live out. 622 if (SimplifyDemandedBits(Op.getOperand(0), DemandedMask, 623 KnownZero, KnownOne, TLO, Depth+1)) 624 return true; 625 626 // If the input is only used by this truncate, see if we can shrink it based 627 // on the known demanded bits. 628 if (Op.getOperand(0).Val->hasOneUse()) { 629 SDOperand In = Op.getOperand(0); 630 switch (In.getOpcode()) { 631 default: break; 632 case ISD::SRL: 633 // Shrink SRL by a constant if none of the high bits shifted in are 634 // demanded. 635 if (ConstantSDNode *ShAmt = dyn_cast<ConstantSDNode>(In.getOperand(1))){ 636 uint64_t HighBits = MVT::getIntVTBitMask(In.getValueType()); 637 HighBits &= ~MVT::getIntVTBitMask(Op.getValueType()); 638 HighBits >>= ShAmt->getValue(); 639 640 if (ShAmt->getValue() < MVT::getSizeInBits(Op.getValueType()) && 641 (DemandedMask & HighBits) == 0) { 642 // None of the shifted in bits are needed. Add a truncate of the 643 // shift input, then shift it. 644 SDOperand NewTrunc = TLO.DAG.getNode(ISD::TRUNCATE, 645 Op.getValueType(), 646 In.getOperand(0)); 647 return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::SRL,Op.getValueType(), 648 NewTrunc, In.getOperand(1))); 649 } 650 } 651 break; 652 } 653 } 654 655 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 656 uint64_t OutMask = MVT::getIntVTBitMask(Op.getValueType()); 657 KnownZero &= OutMask; 658 KnownOne &= OutMask; 659 break; 660 } 661 case ISD::AssertZext: { 662 MVT::ValueType VT = cast<VTSDNode>(Op.getOperand(1))->getVT(); 663 uint64_t InMask = MVT::getIntVTBitMask(VT); 664 if (SimplifyDemandedBits(Op.getOperand(0), DemandedMask & InMask, 665 KnownZero, KnownOne, TLO, Depth+1)) 666 return true; 667 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 668 KnownZero |= ~InMask & DemandedMask; 669 break; 670 } 671 case ISD::ADD: 672 case ISD::SUB: 673 case ISD::INTRINSIC_WO_CHAIN: 674 case ISD::INTRINSIC_W_CHAIN: 675 case ISD::INTRINSIC_VOID: 676 // Just use ComputeMaskedBits to compute output bits. 677 ComputeMaskedBits(Op, DemandedMask, KnownZero, KnownOne, Depth); 678 break; 679 } 680 681 // If we know the value of all of the demanded bits, return this as a 682 // constant. 683 if ((DemandedMask & (KnownZero|KnownOne)) == DemandedMask) 684 return TLO.CombineTo(Op, TLO.DAG.getConstant(KnownOne, Op.getValueType())); 685 686 return false; 687} 688 689/// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use 690/// this predicate to simplify operations downstream. Mask is known to be zero 691/// for bits that V cannot have. 692bool TargetLowering::MaskedValueIsZero(SDOperand Op, uint64_t Mask, 693 unsigned Depth) const { 694 uint64_t KnownZero, KnownOne; 695 ComputeMaskedBits(Op, Mask, KnownZero, KnownOne, Depth); 696 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 697 return (KnownZero & Mask) == Mask; 698} 699 700/// ComputeMaskedBits - Determine which of the bits specified in Mask are 701/// known to be either zero or one and return them in the KnownZero/KnownOne 702/// bitsets. This code only analyzes bits in Mask, in order to short-circuit 703/// processing. 704void TargetLowering::ComputeMaskedBits(SDOperand Op, uint64_t Mask, 705 uint64_t &KnownZero, uint64_t &KnownOne, 706 unsigned Depth) const { 707 KnownZero = KnownOne = 0; // Don't know anything. 708 if (Depth == 6 || Mask == 0) 709 return; // Limit search depth. 710 711 uint64_t KnownZero2, KnownOne2; 712 713 switch (Op.getOpcode()) { 714 case ISD::Constant: 715 // We know all of the bits for a constant! 716 KnownOne = cast<ConstantSDNode>(Op)->getValue() & Mask; 717 KnownZero = ~KnownOne & Mask; 718 return; 719 case ISD::AND: 720 // If either the LHS or the RHS are Zero, the result is zero. 721 ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1); 722 Mask &= ~KnownZero; 723 ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero2, KnownOne2, Depth+1); 724 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 725 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 726 727 // Output known-1 bits are only known if set in both the LHS & RHS. 728 KnownOne &= KnownOne2; 729 // Output known-0 are known to be clear if zero in either the LHS | RHS. 730 KnownZero |= KnownZero2; 731 return; 732 case ISD::OR: 733 ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1); 734 Mask &= ~KnownOne; 735 ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero2, KnownOne2, Depth+1); 736 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 737 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 738 739 // Output known-0 bits are only known if clear in both the LHS & RHS. 740 KnownZero &= KnownZero2; 741 // Output known-1 are known to be set if set in either the LHS | RHS. 742 KnownOne |= KnownOne2; 743 return; 744 case ISD::XOR: { 745 ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1); 746 ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero2, KnownOne2, Depth+1); 747 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 748 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 749 750 // Output known-0 bits are known if clear or set in both the LHS & RHS. 751 uint64_t KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2); 752 // Output known-1 are known to be set if set in only one of the LHS, RHS. 753 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2); 754 KnownZero = KnownZeroOut; 755 return; 756 } 757 case ISD::SELECT: 758 ComputeMaskedBits(Op.getOperand(2), Mask, KnownZero, KnownOne, Depth+1); 759 ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero2, KnownOne2, Depth+1); 760 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 761 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 762 763 // Only known if known in both the LHS and RHS. 764 KnownOne &= KnownOne2; 765 KnownZero &= KnownZero2; 766 return; 767 case ISD::SELECT_CC: 768 ComputeMaskedBits(Op.getOperand(3), Mask, KnownZero, KnownOne, Depth+1); 769 ComputeMaskedBits(Op.getOperand(2), Mask, KnownZero2, KnownOne2, Depth+1); 770 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 771 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 772 773 // Only known if known in both the LHS and RHS. 774 KnownOne &= KnownOne2; 775 KnownZero &= KnownZero2; 776 return; 777 case ISD::SETCC: 778 // If we know the result of a setcc has the top bits zero, use this info. 779 if (getSetCCResultContents() == TargetLowering::ZeroOrOneSetCCResult) 780 KnownZero |= (MVT::getIntVTBitMask(Op.getValueType()) ^ 1ULL); 781 return; 782 case ISD::SHL: 783 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0 784 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 785 ComputeMaskedBits(Op.getOperand(0), Mask >> SA->getValue(), 786 KnownZero, KnownOne, Depth+1); 787 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 788 KnownZero <<= SA->getValue(); 789 KnownOne <<= SA->getValue(); 790 KnownZero |= (1ULL << SA->getValue())-1; // low bits known zero. 791 } 792 return; 793 case ISD::SRL: 794 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0 795 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 796 MVT::ValueType VT = Op.getValueType(); 797 unsigned ShAmt = SA->getValue(); 798 799 uint64_t TypeMask = MVT::getIntVTBitMask(VT); 800 ComputeMaskedBits(Op.getOperand(0), (Mask << ShAmt) & TypeMask, 801 KnownZero, KnownOne, Depth+1); 802 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 803 KnownZero &= TypeMask; 804 KnownOne &= TypeMask; 805 KnownZero >>= ShAmt; 806 KnownOne >>= ShAmt; 807 808 uint64_t HighBits = (1ULL << ShAmt)-1; 809 HighBits <<= MVT::getSizeInBits(VT)-ShAmt; 810 KnownZero |= HighBits; // High bits known zero. 811 } 812 return; 813 case ISD::SRA: 814 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 815 MVT::ValueType VT = Op.getValueType(); 816 unsigned ShAmt = SA->getValue(); 817 818 // Compute the new bits that are at the top now. 819 uint64_t TypeMask = MVT::getIntVTBitMask(VT); 820 821 uint64_t InDemandedMask = (Mask << ShAmt) & TypeMask; 822 // If any of the demanded bits are produced by the sign extension, we also 823 // demand the input sign bit. 824 uint64_t HighBits = (1ULL << ShAmt)-1; 825 HighBits <<= MVT::getSizeInBits(VT) - ShAmt; 826 if (HighBits & Mask) 827 InDemandedMask |= MVT::getIntVTSignBit(VT); 828 829 ComputeMaskedBits(Op.getOperand(0), InDemandedMask, KnownZero, KnownOne, 830 Depth+1); 831 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 832 KnownZero &= TypeMask; 833 KnownOne &= TypeMask; 834 KnownZero >>= ShAmt; 835 KnownOne >>= ShAmt; 836 837 // Handle the sign bits. 838 uint64_t SignBit = MVT::getIntVTSignBit(VT); 839 SignBit >>= ShAmt; // Adjust to where it is now in the mask. 840 841 if (KnownZero & SignBit) { 842 KnownZero |= HighBits; // New bits are known zero. 843 } else if (KnownOne & SignBit) { 844 KnownOne |= HighBits; // New bits are known one. 845 } 846 } 847 return; 848 case ISD::SIGN_EXTEND_INREG: { 849 MVT::ValueType VT = Op.getValueType(); 850 MVT::ValueType EVT = cast<VTSDNode>(Op.getOperand(1))->getVT(); 851 852 // Sign extension. Compute the demanded bits in the result that are not 853 // present in the input. 854 uint64_t NewBits = ~MVT::getIntVTBitMask(EVT) & Mask; 855 856 uint64_t InSignBit = MVT::getIntVTSignBit(EVT); 857 int64_t InputDemandedBits = Mask & MVT::getIntVTBitMask(EVT); 858 859 // If the sign extended bits are demanded, we know that the sign 860 // bit is demanded. 861 if (NewBits) 862 InputDemandedBits |= InSignBit; 863 864 ComputeMaskedBits(Op.getOperand(0), InputDemandedBits, 865 KnownZero, KnownOne, Depth+1); 866 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 867 868 // If the sign bit of the input is known set or clear, then we know the 869 // top bits of the result. 870 if (KnownZero & InSignBit) { // Input sign bit known clear 871 KnownZero |= NewBits; 872 KnownOne &= ~NewBits; 873 } else if (KnownOne & InSignBit) { // Input sign bit known set 874 KnownOne |= NewBits; 875 KnownZero &= ~NewBits; 876 } else { // Input sign bit unknown 877 KnownZero &= ~NewBits; 878 KnownOne &= ~NewBits; 879 } 880 return; 881 } 882 case ISD::CTTZ: 883 case ISD::CTLZ: 884 case ISD::CTPOP: { 885 MVT::ValueType VT = Op.getValueType(); 886 unsigned LowBits = Log2_32(MVT::getSizeInBits(VT))+1; 887 KnownZero = ~((1ULL << LowBits)-1) & MVT::getIntVTBitMask(VT); 888 KnownOne = 0; 889 return; 890 } 891 case ISD::ZEXTLOAD: { 892 MVT::ValueType VT = cast<VTSDNode>(Op.getOperand(3))->getVT(); 893 KnownZero |= ~MVT::getIntVTBitMask(VT) & Mask; 894 return; 895 } 896 case ISD::ZERO_EXTEND: { 897 uint64_t InMask = MVT::getIntVTBitMask(Op.getOperand(0).getValueType()); 898 uint64_t NewBits = (~InMask) & Mask; 899 ComputeMaskedBits(Op.getOperand(0), Mask & InMask, KnownZero, 900 KnownOne, Depth+1); 901 KnownZero |= NewBits & Mask; 902 KnownOne &= ~NewBits; 903 return; 904 } 905 case ISD::SIGN_EXTEND: { 906 MVT::ValueType InVT = Op.getOperand(0).getValueType(); 907 unsigned InBits = MVT::getSizeInBits(InVT); 908 uint64_t InMask = MVT::getIntVTBitMask(InVT); 909 uint64_t InSignBit = 1ULL << (InBits-1); 910 uint64_t NewBits = (~InMask) & Mask; 911 uint64_t InDemandedBits = Mask & InMask; 912 913 // If any of the sign extended bits are demanded, we know that the sign 914 // bit is demanded. 915 if (NewBits & Mask) 916 InDemandedBits |= InSignBit; 917 918 ComputeMaskedBits(Op.getOperand(0), InDemandedBits, KnownZero, 919 KnownOne, Depth+1); 920 // If the sign bit is known zero or one, the top bits match. 921 if (KnownZero & InSignBit) { 922 KnownZero |= NewBits; 923 KnownOne &= ~NewBits; 924 } else if (KnownOne & InSignBit) { 925 KnownOne |= NewBits; 926 KnownZero &= ~NewBits; 927 } else { // Otherwise, top bits aren't known. 928 KnownOne &= ~NewBits; 929 KnownZero &= ~NewBits; 930 } 931 return; 932 } 933 case ISD::ANY_EXTEND: { 934 MVT::ValueType VT = Op.getOperand(0).getValueType(); 935 ComputeMaskedBits(Op.getOperand(0), Mask & MVT::getIntVTBitMask(VT), 936 KnownZero, KnownOne, Depth+1); 937 return; 938 } 939 case ISD::TRUNCATE: { 940 ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero, KnownOne, Depth+1); 941 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 942 uint64_t OutMask = MVT::getIntVTBitMask(Op.getValueType()); 943 KnownZero &= OutMask; 944 KnownOne &= OutMask; 945 break; 946 } 947 case ISD::AssertZext: { 948 MVT::ValueType VT = cast<VTSDNode>(Op.getOperand(1))->getVT(); 949 uint64_t InMask = MVT::getIntVTBitMask(VT); 950 ComputeMaskedBits(Op.getOperand(0), Mask & InMask, KnownZero, 951 KnownOne, Depth+1); 952 KnownZero |= (~InMask) & Mask; 953 return; 954 } 955 case ISD::ADD: { 956 // If either the LHS or the RHS are Zero, the result is zero. 957 ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1); 958 ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero2, KnownOne2, Depth+1); 959 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 960 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 961 962 // Output known-0 bits are known if clear or set in both the low clear bits 963 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the 964 // low 3 bits clear. 965 uint64_t KnownZeroOut = std::min(CountTrailingZeros_64(~KnownZero), 966 CountTrailingZeros_64(~KnownZero2)); 967 968 KnownZero = (1ULL << KnownZeroOut) - 1; 969 KnownOne = 0; 970 return; 971 } 972 case ISD::SUB: { 973 ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)); 974 if (!CLHS) return; 975 976 // We know that the top bits of C-X are clear if X contains less bits 977 // than C (i.e. no wrap-around can happen). For example, 20-X is 978 // positive if we can prove that X is >= 0 and < 16. 979 MVT::ValueType VT = CLHS->getValueType(0); 980 if ((CLHS->getValue() & MVT::getIntVTSignBit(VT)) == 0) { // sign bit clear 981 unsigned NLZ = CountLeadingZeros_64(CLHS->getValue()+1); 982 uint64_t MaskV = (1ULL << (63-NLZ))-1; // NLZ can't be 64 with no sign bit 983 MaskV = ~MaskV & MVT::getIntVTBitMask(VT); 984 ComputeMaskedBits(Op.getOperand(1), MaskV, KnownZero, KnownOne, Depth+1); 985 986 // If all of the MaskV bits are known to be zero, then we know the output 987 // top bits are zero, because we now know that the output is from [0-C]. 988 if ((KnownZero & MaskV) == MaskV) { 989 unsigned NLZ2 = CountLeadingZeros_64(CLHS->getValue()); 990 KnownZero = ~((1ULL << (64-NLZ2))-1) & Mask; // Top bits known zero. 991 KnownOne = 0; // No one bits known. 992 } else { 993 KnownZero = KnownOne = 0; // Otherwise, nothing known. 994 } 995 } 996 return; 997 } 998 default: 999 // Allow the target to implement this method for its nodes. 1000 if (Op.getOpcode() >= ISD::BUILTIN_OP_END) { 1001 case ISD::INTRINSIC_WO_CHAIN: 1002 case ISD::INTRINSIC_W_CHAIN: 1003 case ISD::INTRINSIC_VOID: 1004 computeMaskedBitsForTargetNode(Op, Mask, KnownZero, KnownOne); 1005 } 1006 return; 1007 } 1008} 1009 1010/// computeMaskedBitsForTargetNode - Determine which of the bits specified 1011/// in Mask are known to be either zero or one and return them in the 1012/// KnownZero/KnownOne bitsets. 1013void TargetLowering::computeMaskedBitsForTargetNode(const SDOperand Op, 1014 uint64_t Mask, 1015 uint64_t &KnownZero, 1016 uint64_t &KnownOne, 1017 unsigned Depth) const { 1018 assert((Op.getOpcode() >= ISD::BUILTIN_OP_END || 1019 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN || 1020 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN || 1021 Op.getOpcode() == ISD::INTRINSIC_VOID) && 1022 "Should use MaskedValueIsZero if you don't know whether Op" 1023 " is a target node!"); 1024 KnownZero = 0; 1025 KnownOne = 0; 1026} 1027 1028/// ComputeNumSignBits - Return the number of times the sign bit of the 1029/// register is replicated into the other bits. We know that at least 1 bit 1030/// is always equal to the sign bit (itself), but other cases can give us 1031/// information. For example, immediately after an "SRA X, 2", we know that 1032/// the top 3 bits are all equal to each other, so we return 3. 1033unsigned TargetLowering::ComputeNumSignBits(SDOperand Op, unsigned Depth) const{ 1034 MVT::ValueType VT = Op.getValueType(); 1035 assert(MVT::isInteger(VT) && "Invalid VT!"); 1036 unsigned VTBits = MVT::getSizeInBits(VT); 1037 unsigned Tmp, Tmp2; 1038 1039 if (Depth == 6) 1040 return 1; // Limit search depth. 1041 1042 switch (Op.getOpcode()) { 1043 default: break; 1044 case ISD::AssertSext: 1045 Tmp = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(1))->getVT()); 1046 return VTBits-Tmp+1; 1047 case ISD::AssertZext: 1048 Tmp = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(1))->getVT()); 1049 return VTBits-Tmp; 1050 1051 case ISD::SEXTLOAD: // '17' bits known 1052 Tmp = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(3))->getVT()); 1053 return VTBits-Tmp+1; 1054 case ISD::ZEXTLOAD: // '16' bits known 1055 Tmp = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(3))->getVT()); 1056 return VTBits-Tmp; 1057 1058 case ISD::Constant: { 1059 uint64_t Val = cast<ConstantSDNode>(Op)->getValue(); 1060 // If negative, invert the bits, then look at it. 1061 if (Val & MVT::getIntVTSignBit(VT)) 1062 Val = ~Val; 1063 1064 // Shift the bits so they are the leading bits in the int64_t. 1065 Val <<= 64-VTBits; 1066 1067 // Return # leading zeros. We use 'min' here in case Val was zero before 1068 // shifting. We don't want to return '64' as for an i32 "0". 1069 return std::min(VTBits, CountLeadingZeros_64(Val)); 1070 } 1071 1072 case ISD::SIGN_EXTEND: 1073 Tmp = VTBits-MVT::getSizeInBits(Op.getOperand(0).getValueType()); 1074 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp; 1075 1076 case ISD::SIGN_EXTEND_INREG: 1077 // Max of the input and what this extends. 1078 Tmp = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(1))->getVT()); 1079 Tmp = VTBits-Tmp+1; 1080 1081 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1); 1082 return std::max(Tmp, Tmp2); 1083 1084 case ISD::SRA: 1085 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1); 1086 // SRA X, C -> adds C sign bits. 1087 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 1088 Tmp += C->getValue(); 1089 if (Tmp > VTBits) Tmp = VTBits; 1090 } 1091 return Tmp; 1092 case ISD::SHL: 1093 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 1094 // shl destroys sign bits. 1095 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1); 1096 if (C->getValue() >= VTBits || // Bad shift. 1097 C->getValue() >= Tmp) break; // Shifted all sign bits out. 1098 return Tmp - C->getValue(); 1099 } 1100 break; 1101 case ISD::AND: 1102 case ISD::OR: 1103 case ISD::XOR: // NOT is handled here. 1104 // Logical binary ops preserve the number of sign bits. 1105 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1); 1106 if (Tmp == 1) return 1; // Early out. 1107 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1); 1108 return std::min(Tmp, Tmp2); 1109 1110 case ISD::SELECT: 1111 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1); 1112 if (Tmp == 1) return 1; // Early out. 1113 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1); 1114 return std::min(Tmp, Tmp2); 1115 1116 case ISD::SETCC: 1117 // If setcc returns 0/-1, all bits are sign bits. 1118 if (getSetCCResultContents() == ZeroOrNegativeOneSetCCResult) 1119 return VTBits; 1120 break; 1121 case ISD::ROTL: 1122 case ISD::ROTR: 1123 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 1124 unsigned RotAmt = C->getValue() & (VTBits-1); 1125 1126 // Handle rotate right by N like a rotate left by 32-N. 1127 if (Op.getOpcode() == ISD::ROTR) 1128 RotAmt = (VTBits-RotAmt) & (VTBits-1); 1129 1130 // If we aren't rotating out all of the known-in sign bits, return the 1131 // number that are left. This handles rotl(sext(x), 1) for example. 1132 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1); 1133 if (Tmp > RotAmt+1) return Tmp-RotAmt; 1134 } 1135 break; 1136 case ISD::ADD: 1137 // Add can have at most one carry bit. Thus we know that the output 1138 // is, at worst, one more bit than the inputs. 1139 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1); 1140 if (Tmp == 1) return 1; // Early out. 1141 1142 // Special case decrementing a value (ADD X, -1): 1143 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) 1144 if (CRHS->isAllOnesValue()) { 1145 uint64_t KnownZero, KnownOne; 1146 uint64_t Mask = MVT::getIntVTBitMask(VT); 1147 ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero, KnownOne, Depth+1); 1148 1149 // If the input is known to be 0 or 1, the output is 0/-1, which is all 1150 // sign bits set. 1151 if ((KnownZero|1) == Mask) 1152 return VTBits; 1153 1154 // If we are subtracting one from a positive number, there is no carry 1155 // out of the result. 1156 if (KnownZero & MVT::getIntVTSignBit(VT)) 1157 return Tmp; 1158 } 1159 1160 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1); 1161 if (Tmp2 == 1) return 1; 1162 return std::min(Tmp, Tmp2)-1; 1163 break; 1164 1165 case ISD::SUB: 1166 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1); 1167 if (Tmp2 == 1) return 1; 1168 1169 // Handle NEG. 1170 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) 1171 if (CLHS->getValue() == 0) { 1172 uint64_t KnownZero, KnownOne; 1173 uint64_t Mask = MVT::getIntVTBitMask(VT); 1174 ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1); 1175 // If the input is known to be 0 or 1, the output is 0/-1, which is all 1176 // sign bits set. 1177 if ((KnownZero|1) == Mask) 1178 return VTBits; 1179 1180 // If the input is known to be positive (the sign bit is known clear), 1181 // the output of the NEG has the same number of sign bits as the input. 1182 if (KnownZero & MVT::getIntVTSignBit(VT)) 1183 return Tmp2; 1184 1185 // Otherwise, we treat this like a SUB. 1186 } 1187 1188 // Sub can have at most one carry bit. Thus we know that the output 1189 // is, at worst, one more bit than the inputs. 1190 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1); 1191 if (Tmp == 1) return 1; // Early out. 1192 return std::min(Tmp, Tmp2)-1; 1193 break; 1194 case ISD::TRUNCATE: 1195 // FIXME: it's tricky to do anything useful for this, but it is an important 1196 // case for targets like X86. 1197 break; 1198 } 1199 1200 // Allow the target to implement this method for its nodes. 1201 if (Op.getOpcode() >= ISD::BUILTIN_OP_END || 1202 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN || 1203 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN || 1204 Op.getOpcode() == ISD::INTRINSIC_VOID) { 1205 unsigned NumBits = ComputeNumSignBitsForTargetNode(Op, Depth); 1206 if (NumBits > 1) return NumBits; 1207 } 1208 1209 // Finally, if we can prove that the top bits of the result are 0's or 1's, 1210 // use this information. 1211 uint64_t KnownZero, KnownOne; 1212 uint64_t Mask = MVT::getIntVTBitMask(VT); 1213 ComputeMaskedBits(Op, Mask, KnownZero, KnownOne, Depth); 1214 1215 uint64_t SignBit = MVT::getIntVTSignBit(VT); 1216 if (KnownZero & SignBit) { // SignBit is 0 1217 Mask = KnownZero; 1218 } else if (KnownOne & SignBit) { // SignBit is 1; 1219 Mask = KnownOne; 1220 } else { 1221 // Nothing known. 1222 return 1; 1223 } 1224 1225 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine 1226 // the number of identical bits in the top of the input value. 1227 Mask ^= ~0ULL; 1228 Mask <<= 64-VTBits; 1229 // Return # leading zeros. We use 'min' here in case Val was zero before 1230 // shifting. We don't want to return '64' as for an i32 "0". 1231 return std::min(VTBits, CountLeadingZeros_64(Mask)); 1232} 1233 1234 1235 1236/// ComputeNumSignBitsForTargetNode - This method can be implemented by 1237/// targets that want to expose additional information about sign bits to the 1238/// DAG Combiner. 1239unsigned TargetLowering::ComputeNumSignBitsForTargetNode(SDOperand Op, 1240 unsigned Depth) const { 1241 assert((Op.getOpcode() >= ISD::BUILTIN_OP_END || 1242 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN || 1243 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN || 1244 Op.getOpcode() == ISD::INTRINSIC_VOID) && 1245 "Should use ComputeNumSignBits if you don't know whether Op" 1246 " is a target node!"); 1247 return 1; 1248} 1249 1250 1251SDOperand TargetLowering:: 1252PerformDAGCombine(SDNode *N, DAGCombinerInfo &DCI) const { 1253 // Default implementation: no optimization. 1254 return SDOperand(); 1255} 1256 1257//===----------------------------------------------------------------------===// 1258// Inline Assembler Implementation Methods 1259//===----------------------------------------------------------------------===// 1260 1261TargetLowering::ConstraintType 1262TargetLowering::getConstraintType(char ConstraintLetter) const { 1263 // FIXME: lots more standard ones to handle. 1264 switch (ConstraintLetter) { 1265 default: return C_Unknown; 1266 case 'r': return C_RegisterClass; 1267 case 'm': // memory 1268 case 'o': // offsetable 1269 case 'V': // not offsetable 1270 return C_Memory; 1271 case 'i': // Simple Integer or Relocatable Constant 1272 case 'n': // Simple Integer 1273 case 's': // Relocatable Constant 1274 case 'I': // Target registers. 1275 case 'J': 1276 case 'K': 1277 case 'L': 1278 case 'M': 1279 case 'N': 1280 case 'O': 1281 case 'P': 1282 return C_Other; 1283 } 1284} 1285 1286bool TargetLowering::isOperandValidForConstraint(SDOperand Op, 1287 char ConstraintLetter) { 1288 switch (ConstraintLetter) { 1289 default: return false; 1290 case 'i': // Simple Integer or Relocatable Constant 1291 case 'n': // Simple Integer 1292 case 's': // Relocatable Constant 1293 return true; // FIXME: not right. 1294 } 1295} 1296 1297 1298std::vector<unsigned> TargetLowering:: 1299getRegClassForInlineAsmConstraint(const std::string &Constraint, 1300 MVT::ValueType VT) const { 1301 return std::vector<unsigned>(); 1302} 1303 1304 1305std::pair<unsigned, const TargetRegisterClass*> TargetLowering:: 1306getRegForInlineAsmConstraint(const std::string &Constraint, 1307 MVT::ValueType VT) const { 1308 if (Constraint[0] != '{') 1309 return std::pair<unsigned, const TargetRegisterClass*>(0, 0); 1310 assert(*(Constraint.end()-1) == '}' && "Not a brace enclosed constraint?"); 1311 1312 // Remove the braces from around the name. 1313 std::string RegName(Constraint.begin()+1, Constraint.end()-1); 1314 1315 // Figure out which register class contains this reg. 1316 const MRegisterInfo *RI = TM.getRegisterInfo(); 1317 for (MRegisterInfo::regclass_iterator RCI = RI->regclass_begin(), 1318 E = RI->regclass_end(); RCI != E; ++RCI) { 1319 const TargetRegisterClass *RC = *RCI; 1320 1321 // If none of the the value types for this register class are valid, we 1322 // can't use it. For example, 64-bit reg classes on 32-bit targets. 1323 bool isLegal = false; 1324 for (TargetRegisterClass::vt_iterator I = RC->vt_begin(), E = RC->vt_end(); 1325 I != E; ++I) { 1326 if (isTypeLegal(*I)) { 1327 isLegal = true; 1328 break; 1329 } 1330 } 1331 1332 if (!isLegal) continue; 1333 1334 for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); 1335 I != E; ++I) { 1336 if (StringsEqualNoCase(RegName, RI->get(*I).Name)) 1337 return std::make_pair(*I, RC); 1338 } 1339 } 1340 1341 return std::pair<unsigned, const TargetRegisterClass*>(0, 0); 1342} 1343 1344//===----------------------------------------------------------------------===// 1345// Loop Strength Reduction hooks 1346//===----------------------------------------------------------------------===// 1347 1348/// isLegalAddressImmediate - Return true if the integer value or 1349/// GlobalValue can be used as the offset of the target addressing mode. 1350bool TargetLowering::isLegalAddressImmediate(int64_t V) const { 1351 return false; 1352} 1353bool TargetLowering::isLegalAddressImmediate(GlobalValue *GV) const { 1354 return false; 1355} 1356 1357 1358// Magic for divide replacement 1359 1360struct ms { 1361 int64_t m; // magic number 1362 int64_t s; // shift amount 1363}; 1364 1365struct mu { 1366 uint64_t m; // magic number 1367 int64_t a; // add indicator 1368 int64_t s; // shift amount 1369}; 1370 1371/// magic - calculate the magic numbers required to codegen an integer sdiv as 1372/// a sequence of multiply and shifts. Requires that the divisor not be 0, 1, 1373/// or -1. 1374static ms magic32(int32_t d) { 1375 int32_t p; 1376 uint32_t ad, anc, delta, q1, r1, q2, r2, t; 1377 const uint32_t two31 = 0x80000000U; 1378 struct ms mag; 1379 1380 ad = abs(d); 1381 t = two31 + ((uint32_t)d >> 31); 1382 anc = t - 1 - t%ad; // absolute value of nc 1383 p = 31; // initialize p 1384 q1 = two31/anc; // initialize q1 = 2p/abs(nc) 1385 r1 = two31 - q1*anc; // initialize r1 = rem(2p,abs(nc)) 1386 q2 = two31/ad; // initialize q2 = 2p/abs(d) 1387 r2 = two31 - q2*ad; // initialize r2 = rem(2p,abs(d)) 1388 do { 1389 p = p + 1; 1390 q1 = 2*q1; // update q1 = 2p/abs(nc) 1391 r1 = 2*r1; // update r1 = rem(2p/abs(nc)) 1392 if (r1 >= anc) { // must be unsigned comparison 1393 q1 = q1 + 1; 1394 r1 = r1 - anc; 1395 } 1396 q2 = 2*q2; // update q2 = 2p/abs(d) 1397 r2 = 2*r2; // update r2 = rem(2p/abs(d)) 1398 if (r2 >= ad) { // must be unsigned comparison 1399 q2 = q2 + 1; 1400 r2 = r2 - ad; 1401 } 1402 delta = ad - r2; 1403 } while (q1 < delta || (q1 == delta && r1 == 0)); 1404 1405 mag.m = (int32_t)(q2 + 1); // make sure to sign extend 1406 if (d < 0) mag.m = -mag.m; // resulting magic number 1407 mag.s = p - 32; // resulting shift 1408 return mag; 1409} 1410 1411/// magicu - calculate the magic numbers required to codegen an integer udiv as 1412/// a sequence of multiply, add and shifts. Requires that the divisor not be 0. 1413static mu magicu32(uint32_t d) { 1414 int32_t p; 1415 uint32_t nc, delta, q1, r1, q2, r2; 1416 struct mu magu; 1417 magu.a = 0; // initialize "add" indicator 1418 nc = - 1 - (-d)%d; 1419 p = 31; // initialize p 1420 q1 = 0x80000000/nc; // initialize q1 = 2p/nc 1421 r1 = 0x80000000 - q1*nc; // initialize r1 = rem(2p,nc) 1422 q2 = 0x7FFFFFFF/d; // initialize q2 = (2p-1)/d 1423 r2 = 0x7FFFFFFF - q2*d; // initialize r2 = rem((2p-1),d) 1424 do { 1425 p = p + 1; 1426 if (r1 >= nc - r1 ) { 1427 q1 = 2*q1 + 1; // update q1 1428 r1 = 2*r1 - nc; // update r1 1429 } 1430 else { 1431 q1 = 2*q1; // update q1 1432 r1 = 2*r1; // update r1 1433 } 1434 if (r2 + 1 >= d - r2) { 1435 if (q2 >= 0x7FFFFFFF) magu.a = 1; 1436 q2 = 2*q2 + 1; // update q2 1437 r2 = 2*r2 + 1 - d; // update r2 1438 } 1439 else { 1440 if (q2 >= 0x80000000) magu.a = 1; 1441 q2 = 2*q2; // update q2 1442 r2 = 2*r2 + 1; // update r2 1443 } 1444 delta = d - 1 - r2; 1445 } while (p < 64 && (q1 < delta || (q1 == delta && r1 == 0))); 1446 magu.m = q2 + 1; // resulting magic number 1447 magu.s = p - 32; // resulting shift 1448 return magu; 1449} 1450 1451/// magic - calculate the magic numbers required to codegen an integer sdiv as 1452/// a sequence of multiply and shifts. Requires that the divisor not be 0, 1, 1453/// or -1. 1454static ms magic64(int64_t d) { 1455 int64_t p; 1456 uint64_t ad, anc, delta, q1, r1, q2, r2, t; 1457 const uint64_t two63 = 9223372036854775808ULL; // 2^63 1458 struct ms mag; 1459 1460 ad = d >= 0 ? d : -d; 1461 t = two63 + ((uint64_t)d >> 63); 1462 anc = t - 1 - t%ad; // absolute value of nc 1463 p = 63; // initialize p 1464 q1 = two63/anc; // initialize q1 = 2p/abs(nc) 1465 r1 = two63 - q1*anc; // initialize r1 = rem(2p,abs(nc)) 1466 q2 = two63/ad; // initialize q2 = 2p/abs(d) 1467 r2 = two63 - q2*ad; // initialize r2 = rem(2p,abs(d)) 1468 do { 1469 p = p + 1; 1470 q1 = 2*q1; // update q1 = 2p/abs(nc) 1471 r1 = 2*r1; // update r1 = rem(2p/abs(nc)) 1472 if (r1 >= anc) { // must be unsigned comparison 1473 q1 = q1 + 1; 1474 r1 = r1 - anc; 1475 } 1476 q2 = 2*q2; // update q2 = 2p/abs(d) 1477 r2 = 2*r2; // update r2 = rem(2p/abs(d)) 1478 if (r2 >= ad) { // must be unsigned comparison 1479 q2 = q2 + 1; 1480 r2 = r2 - ad; 1481 } 1482 delta = ad - r2; 1483 } while (q1 < delta || (q1 == delta && r1 == 0)); 1484 1485 mag.m = q2 + 1; 1486 if (d < 0) mag.m = -mag.m; // resulting magic number 1487 mag.s = p - 64; // resulting shift 1488 return mag; 1489} 1490 1491/// magicu - calculate the magic numbers required to codegen an integer udiv as 1492/// a sequence of multiply, add and shifts. Requires that the divisor not be 0. 1493static mu magicu64(uint64_t d) 1494{ 1495 int64_t p; 1496 uint64_t nc, delta, q1, r1, q2, r2; 1497 struct mu magu; 1498 magu.a = 0; // initialize "add" indicator 1499 nc = - 1 - (-d)%d; 1500 p = 63; // initialize p 1501 q1 = 0x8000000000000000ull/nc; // initialize q1 = 2p/nc 1502 r1 = 0x8000000000000000ull - q1*nc; // initialize r1 = rem(2p,nc) 1503 q2 = 0x7FFFFFFFFFFFFFFFull/d; // initialize q2 = (2p-1)/d 1504 r2 = 0x7FFFFFFFFFFFFFFFull - q2*d; // initialize r2 = rem((2p-1),d) 1505 do { 1506 p = p + 1; 1507 if (r1 >= nc - r1 ) { 1508 q1 = 2*q1 + 1; // update q1 1509 r1 = 2*r1 - nc; // update r1 1510 } 1511 else { 1512 q1 = 2*q1; // update q1 1513 r1 = 2*r1; // update r1 1514 } 1515 if (r2 + 1 >= d - r2) { 1516 if (q2 >= 0x7FFFFFFFFFFFFFFFull) magu.a = 1; 1517 q2 = 2*q2 + 1; // update q2 1518 r2 = 2*r2 + 1 - d; // update r2 1519 } 1520 else { 1521 if (q2 >= 0x8000000000000000ull) magu.a = 1; 1522 q2 = 2*q2; // update q2 1523 r2 = 2*r2 + 1; // update r2 1524 } 1525 delta = d - 1 - r2; 1526 } while (p < 128 && (q1 < delta || (q1 == delta && r1 == 0))); 1527 magu.m = q2 + 1; // resulting magic number 1528 magu.s = p - 64; // resulting shift 1529 return magu; 1530} 1531 1532/// BuildSDIVSequence - Given an ISD::SDIV node expressing a divide by constant, 1533/// return a DAG expression to select that will generate the same value by 1534/// multiplying by a magic number. See: 1535/// <http://the.wall.riscom.net/books/proc/ppc/cwg/code2.html> 1536SDOperand TargetLowering::BuildSDIV(SDNode *N, SelectionDAG &DAG, 1537 std::vector<SDNode*>* Created) const { 1538 MVT::ValueType VT = N->getValueType(0); 1539 1540 // Check to see if we can do this. 1541 if (!isTypeLegal(VT) || (VT != MVT::i32 && VT != MVT::i64)) 1542 return SDOperand(); // BuildSDIV only operates on i32 or i64 1543 if (!isOperationLegal(ISD::MULHS, VT)) 1544 return SDOperand(); // Make sure the target supports MULHS. 1545 1546 int64_t d = cast<ConstantSDNode>(N->getOperand(1))->getSignExtended(); 1547 ms magics = (VT == MVT::i32) ? magic32(d) : magic64(d); 1548 1549 // Multiply the numerator (operand 0) by the magic value 1550 SDOperand Q = DAG.getNode(ISD::MULHS, VT, N->getOperand(0), 1551 DAG.getConstant(magics.m, VT)); 1552 // If d > 0 and m < 0, add the numerator 1553 if (d > 0 && magics.m < 0) { 1554 Q = DAG.getNode(ISD::ADD, VT, Q, N->getOperand(0)); 1555 if (Created) 1556 Created->push_back(Q.Val); 1557 } 1558 // If d < 0 and m > 0, subtract the numerator. 1559 if (d < 0 && magics.m > 0) { 1560 Q = DAG.getNode(ISD::SUB, VT, Q, N->getOperand(0)); 1561 if (Created) 1562 Created->push_back(Q.Val); 1563 } 1564 // Shift right algebraic if shift value is nonzero 1565 if (magics.s > 0) { 1566 Q = DAG.getNode(ISD::SRA, VT, Q, 1567 DAG.getConstant(magics.s, getShiftAmountTy())); 1568 if (Created) 1569 Created->push_back(Q.Val); 1570 } 1571 // Extract the sign bit and add it to the quotient 1572 SDOperand T = 1573 DAG.getNode(ISD::SRL, VT, Q, DAG.getConstant(MVT::getSizeInBits(VT)-1, 1574 getShiftAmountTy())); 1575 if (Created) 1576 Created->push_back(T.Val); 1577 return DAG.getNode(ISD::ADD, VT, Q, T); 1578} 1579 1580/// BuildUDIVSequence - Given an ISD::UDIV node expressing a divide by constant, 1581/// return a DAG expression to select that will generate the same value by 1582/// multiplying by a magic number. See: 1583/// <http://the.wall.riscom.net/books/proc/ppc/cwg/code2.html> 1584SDOperand TargetLowering::BuildUDIV(SDNode *N, SelectionDAG &DAG, 1585 std::vector<SDNode*>* Created) const { 1586 MVT::ValueType VT = N->getValueType(0); 1587 1588 // Check to see if we can do this. 1589 if (!isTypeLegal(VT) || (VT != MVT::i32 && VT != MVT::i64)) 1590 return SDOperand(); // BuildUDIV only operates on i32 or i64 1591 if (!isOperationLegal(ISD::MULHU, VT)) 1592 return SDOperand(); // Make sure the target supports MULHU. 1593 1594 uint64_t d = cast<ConstantSDNode>(N->getOperand(1))->getValue(); 1595 mu magics = (VT == MVT::i32) ? magicu32(d) : magicu64(d); 1596 1597 // Multiply the numerator (operand 0) by the magic value 1598 SDOperand Q = DAG.getNode(ISD::MULHU, VT, N->getOperand(0), 1599 DAG.getConstant(magics.m, VT)); 1600 if (Created) 1601 Created->push_back(Q.Val); 1602 1603 if (magics.a == 0) { 1604 return DAG.getNode(ISD::SRL, VT, Q, 1605 DAG.getConstant(magics.s, getShiftAmountTy())); 1606 } else { 1607 SDOperand NPQ = DAG.getNode(ISD::SUB, VT, N->getOperand(0), Q); 1608 if (Created) 1609 Created->push_back(NPQ.Val); 1610 NPQ = DAG.getNode(ISD::SRL, VT, NPQ, 1611 DAG.getConstant(1, getShiftAmountTy())); 1612 if (Created) 1613 Created->push_back(NPQ.Val); 1614 NPQ = DAG.getNode(ISD::ADD, VT, NPQ, Q); 1615 if (Created) 1616 Created->push_back(NPQ.Val); 1617 return DAG.getNode(ISD::SRL, VT, NPQ, 1618 DAG.getConstant(magics.s-1, getShiftAmountTy())); 1619 } 1620} 1621