ValueTracking.cpp revision 70d3bebc8bc857fcf3d7fac44bda884d5e2a7040
1//===- ValueTracking.cpp - Walk computations to compute properties --------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file contains routines that help analyze properties that chains of 11// computations have. 12// 13//===----------------------------------------------------------------------===// 14 15#include "llvm/Analysis/ValueTracking.h" 16#include "llvm/ADT/SmallPtrSet.h" 17#include "llvm/Analysis/InstructionSimplify.h" 18#include "llvm/Constants.h" 19#include "llvm/DataLayout.h" 20#include "llvm/GlobalAlias.h" 21#include "llvm/GlobalVariable.h" 22#include "llvm/Instructions.h" 23#include "llvm/IntrinsicInst.h" 24#include "llvm/LLVMContext.h" 25#include "llvm/Metadata.h" 26#include "llvm/Operator.h" 27#include "llvm/Support/ConstantRange.h" 28#include "llvm/Support/GetElementPtrTypeIterator.h" 29#include "llvm/Support/MathExtras.h" 30#include "llvm/Support/PatternMatch.h" 31#include <cstring> 32using namespace llvm; 33using namespace llvm::PatternMatch; 34 35const unsigned MaxDepth = 6; 36 37/// getBitWidth - Returns the bitwidth of the given scalar or pointer type (if 38/// unknown returns 0). For vector types, returns the element type's bitwidth. 39static unsigned getBitWidth(Type *Ty, const DataLayout *TD) { 40 if (unsigned BitWidth = Ty->getScalarSizeInBits()) 41 return BitWidth; 42 assert(isa<PointerType>(Ty) && "Expected a pointer type!"); 43 return TD ? TD->getPointerSizeInBits() : 0; 44} 45 46static void ComputeMaskedBitsAddSub(bool Add, Value *Op0, Value *Op1, bool NSW, 47 APInt &KnownZero, APInt &KnownOne, 48 APInt &KnownZero2, APInt &KnownOne2, 49 const DataLayout *TD, unsigned Depth) { 50 if (!Add) { 51 if (ConstantInt *CLHS = dyn_cast<ConstantInt>(Op0)) { 52 // We know that the top bits of C-X are clear if X contains less bits 53 // than C (i.e. no wrap-around can happen). For example, 20-X is 54 // positive if we can prove that X is >= 0 and < 16. 55 if (!CLHS->getValue().isNegative()) { 56 unsigned BitWidth = KnownZero.getBitWidth(); 57 unsigned NLZ = (CLHS->getValue()+1).countLeadingZeros(); 58 // NLZ can't be BitWidth with no sign bit 59 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1); 60 llvm::ComputeMaskedBits(Op1, KnownZero2, KnownOne2, TD, Depth+1); 61 62 // If all of the MaskV bits are known to be zero, then we know the 63 // output top bits are zero, because we now know that the output is 64 // from [0-C]. 65 if ((KnownZero2 & MaskV) == MaskV) { 66 unsigned NLZ2 = CLHS->getValue().countLeadingZeros(); 67 // Top bits known zero. 68 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2); 69 } 70 } 71 } 72 } 73 74 unsigned BitWidth = KnownZero.getBitWidth(); 75 76 // If one of the operands has trailing zeros, then the bits that the 77 // other operand has in those bit positions will be preserved in the 78 // result. For an add, this works with either operand. For a subtract, 79 // this only works if the known zeros are in the right operand. 80 APInt LHSKnownZero(BitWidth, 0), LHSKnownOne(BitWidth, 0); 81 llvm::ComputeMaskedBits(Op0, LHSKnownZero, LHSKnownOne, TD, Depth+1); 82 assert((LHSKnownZero & LHSKnownOne) == 0 && 83 "Bits known to be one AND zero?"); 84 unsigned LHSKnownZeroOut = LHSKnownZero.countTrailingOnes(); 85 86 llvm::ComputeMaskedBits(Op1, KnownZero2, KnownOne2, TD, Depth+1); 87 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 88 unsigned RHSKnownZeroOut = KnownZero2.countTrailingOnes(); 89 90 // Determine which operand has more trailing zeros, and use that 91 // many bits from the other operand. 92 if (LHSKnownZeroOut > RHSKnownZeroOut) { 93 if (Add) { 94 APInt Mask = APInt::getLowBitsSet(BitWidth, LHSKnownZeroOut); 95 KnownZero |= KnownZero2 & Mask; 96 KnownOne |= KnownOne2 & Mask; 97 } else { 98 // If the known zeros are in the left operand for a subtract, 99 // fall back to the minimum known zeros in both operands. 100 KnownZero |= APInt::getLowBitsSet(BitWidth, 101 std::min(LHSKnownZeroOut, 102 RHSKnownZeroOut)); 103 } 104 } else if (RHSKnownZeroOut >= LHSKnownZeroOut) { 105 APInt Mask = APInt::getLowBitsSet(BitWidth, RHSKnownZeroOut); 106 KnownZero |= LHSKnownZero & Mask; 107 KnownOne |= LHSKnownOne & Mask; 108 } 109 110 // Are we still trying to solve for the sign bit? 111 if (!KnownZero.isNegative() && !KnownOne.isNegative()) { 112 if (NSW) { 113 if (Add) { 114 // Adding two positive numbers can't wrap into negative 115 if (LHSKnownZero.isNegative() && KnownZero2.isNegative()) 116 KnownZero |= APInt::getSignBit(BitWidth); 117 // and adding two negative numbers can't wrap into positive. 118 else if (LHSKnownOne.isNegative() && KnownOne2.isNegative()) 119 KnownOne |= APInt::getSignBit(BitWidth); 120 } else { 121 // Subtracting a negative number from a positive one can't wrap 122 if (LHSKnownZero.isNegative() && KnownOne2.isNegative()) 123 KnownZero |= APInt::getSignBit(BitWidth); 124 // neither can subtracting a positive number from a negative one. 125 else if (LHSKnownOne.isNegative() && KnownZero2.isNegative()) 126 KnownOne |= APInt::getSignBit(BitWidth); 127 } 128 } 129 } 130} 131 132static void ComputeMaskedBitsMul(Value *Op0, Value *Op1, bool NSW, 133 APInt &KnownZero, APInt &KnownOne, 134 APInt &KnownZero2, APInt &KnownOne2, 135 const DataLayout *TD, unsigned Depth) { 136 unsigned BitWidth = KnownZero.getBitWidth(); 137 ComputeMaskedBits(Op1, KnownZero, KnownOne, TD, Depth+1); 138 ComputeMaskedBits(Op0, KnownZero2, KnownOne2, TD, Depth+1); 139 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 140 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 141 142 bool isKnownNegative = false; 143 bool isKnownNonNegative = false; 144 // If the multiplication is known not to overflow, compute the sign bit. 145 if (NSW) { 146 if (Op0 == Op1) { 147 // The product of a number with itself is non-negative. 148 isKnownNonNegative = true; 149 } else { 150 bool isKnownNonNegativeOp1 = KnownZero.isNegative(); 151 bool isKnownNonNegativeOp0 = KnownZero2.isNegative(); 152 bool isKnownNegativeOp1 = KnownOne.isNegative(); 153 bool isKnownNegativeOp0 = KnownOne2.isNegative(); 154 // The product of two numbers with the same sign is non-negative. 155 isKnownNonNegative = (isKnownNegativeOp1 && isKnownNegativeOp0) || 156 (isKnownNonNegativeOp1 && isKnownNonNegativeOp0); 157 // The product of a negative number and a non-negative number is either 158 // negative or zero. 159 if (!isKnownNonNegative) 160 isKnownNegative = (isKnownNegativeOp1 && isKnownNonNegativeOp0 && 161 isKnownNonZero(Op0, TD, Depth)) || 162 (isKnownNegativeOp0 && isKnownNonNegativeOp1 && 163 isKnownNonZero(Op1, TD, Depth)); 164 } 165 } 166 167 // If low bits are zero in either operand, output low known-0 bits. 168 // Also compute a conserative estimate for high known-0 bits. 169 // More trickiness is possible, but this is sufficient for the 170 // interesting case of alignment computation. 171 KnownOne.clearAllBits(); 172 unsigned TrailZ = KnownZero.countTrailingOnes() + 173 KnownZero2.countTrailingOnes(); 174 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() + 175 KnownZero2.countLeadingOnes(), 176 BitWidth) - BitWidth; 177 178 TrailZ = std::min(TrailZ, BitWidth); 179 LeadZ = std::min(LeadZ, BitWidth); 180 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) | 181 APInt::getHighBitsSet(BitWidth, LeadZ); 182 183 // Only make use of no-wrap flags if we failed to compute the sign bit 184 // directly. This matters if the multiplication always overflows, in 185 // which case we prefer to follow the result of the direct computation, 186 // though as the program is invoking undefined behaviour we can choose 187 // whatever we like here. 188 if (isKnownNonNegative && !KnownOne.isNegative()) 189 KnownZero.setBit(BitWidth - 1); 190 else if (isKnownNegative && !KnownZero.isNegative()) 191 KnownOne.setBit(BitWidth - 1); 192} 193 194void llvm::computeMaskedBitsLoad(const MDNode &Ranges, APInt &KnownZero) { 195 unsigned BitWidth = KnownZero.getBitWidth(); 196 unsigned NumRanges = Ranges.getNumOperands() / 2; 197 assert(NumRanges >= 1); 198 199 // Use the high end of the ranges to find leading zeros. 200 unsigned MinLeadingZeros = BitWidth; 201 for (unsigned i = 0; i < NumRanges; ++i) { 202 ConstantInt *Lower = cast<ConstantInt>(Ranges.getOperand(2*i + 0)); 203 ConstantInt *Upper = cast<ConstantInt>(Ranges.getOperand(2*i + 1)); 204 ConstantRange Range(Lower->getValue(), Upper->getValue()); 205 if (Range.isWrappedSet()) 206 MinLeadingZeros = 0; // -1 has no zeros 207 unsigned LeadingZeros = (Upper->getValue() - 1).countLeadingZeros(); 208 MinLeadingZeros = std::min(LeadingZeros, MinLeadingZeros); 209 } 210 211 KnownZero = APInt::getHighBitsSet(BitWidth, MinLeadingZeros); 212} 213/// ComputeMaskedBits - Determine which of the bits are known to be either zero 214/// or one and return them in the KnownZero/KnownOne bit sets. 215/// 216/// NOTE: we cannot consider 'undef' to be "IsZero" here. The problem is that 217/// we cannot optimize based on the assumption that it is zero without changing 218/// it to be an explicit zero. If we don't change it to zero, other code could 219/// optimized based on the contradictory assumption that it is non-zero. 220/// Because instcombine aggressively folds operations with undef args anyway, 221/// this won't lose us code quality. 222/// 223/// This function is defined on values with integer type, values with pointer 224/// type (but only if TD is non-null), and vectors of integers. In the case 225/// where V is a vector, known zero, and known one values are the 226/// same width as the vector element, and the bit is set only if it is true 227/// for all of the elements in the vector. 228void llvm::ComputeMaskedBits(Value *V, APInt &KnownZero, APInt &KnownOne, 229 const DataLayout *TD, unsigned Depth) { 230 assert(V && "No Value?"); 231 assert(Depth <= MaxDepth && "Limit Search Depth"); 232 unsigned BitWidth = KnownZero.getBitWidth(); 233 234 assert((V->getType()->isIntOrIntVectorTy() || 235 V->getType()->getScalarType()->isPointerTy()) && 236 "Not integer or pointer type!"); 237 assert((!TD || 238 TD->getTypeSizeInBits(V->getType()->getScalarType()) == BitWidth) && 239 (!V->getType()->isIntOrIntVectorTy() || 240 V->getType()->getScalarSizeInBits() == BitWidth) && 241 KnownZero.getBitWidth() == BitWidth && 242 KnownOne.getBitWidth() == BitWidth && 243 "V, Mask, KnownOne and KnownZero should have same BitWidth"); 244 245 if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) { 246 // We know all of the bits for a constant! 247 KnownOne = CI->getValue(); 248 KnownZero = ~KnownOne; 249 return; 250 } 251 // Null and aggregate-zero are all-zeros. 252 if (isa<ConstantPointerNull>(V) || 253 isa<ConstantAggregateZero>(V)) { 254 KnownOne.clearAllBits(); 255 KnownZero = APInt::getAllOnesValue(BitWidth); 256 return; 257 } 258 // Handle a constant vector by taking the intersection of the known bits of 259 // each element. There is no real need to handle ConstantVector here, because 260 // we don't handle undef in any particularly useful way. 261 if (ConstantDataSequential *CDS = dyn_cast<ConstantDataSequential>(V)) { 262 // We know that CDS must be a vector of integers. Take the intersection of 263 // each element. 264 KnownZero.setAllBits(); KnownOne.setAllBits(); 265 APInt Elt(KnownZero.getBitWidth(), 0); 266 for (unsigned i = 0, e = CDS->getNumElements(); i != e; ++i) { 267 Elt = CDS->getElementAsInteger(i); 268 KnownZero &= ~Elt; 269 KnownOne &= Elt; 270 } 271 return; 272 } 273 274 // The address of an aligned GlobalValue has trailing zeros. 275 if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) { 276 unsigned Align = GV->getAlignment(); 277 if (Align == 0 && TD) { 278 if (GlobalVariable *GVar = dyn_cast<GlobalVariable>(GV)) { 279 Type *ObjectType = GVar->getType()->getElementType(); 280 if (ObjectType->isSized()) { 281 // If the object is defined in the current Module, we'll be giving 282 // it the preferred alignment. Otherwise, we have to assume that it 283 // may only have the minimum ABI alignment. 284 if (!GVar->isDeclaration() && !GVar->isWeakForLinker()) 285 Align = TD->getPreferredAlignment(GVar); 286 else 287 Align = TD->getABITypeAlignment(ObjectType); 288 } 289 } 290 } 291 if (Align > 0) 292 KnownZero = APInt::getLowBitsSet(BitWidth, 293 CountTrailingZeros_32(Align)); 294 else 295 KnownZero.clearAllBits(); 296 KnownOne.clearAllBits(); 297 return; 298 } 299 // A weak GlobalAlias is totally unknown. A non-weak GlobalAlias has 300 // the bits of its aliasee. 301 if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) { 302 if (GA->mayBeOverridden()) { 303 KnownZero.clearAllBits(); KnownOne.clearAllBits(); 304 } else { 305 ComputeMaskedBits(GA->getAliasee(), KnownZero, KnownOne, TD, Depth+1); 306 } 307 return; 308 } 309 310 if (Argument *A = dyn_cast<Argument>(V)) { 311 unsigned Align = 0; 312 313 if (A->hasByValAttr()) { 314 // Get alignment information off byval arguments if specified in the IR. 315 Align = A->getParamAlignment(); 316 } else if (TD && A->hasStructRetAttr()) { 317 // An sret parameter has at least the ABI alignment of the return type. 318 Type *EltTy = cast<PointerType>(A->getType())->getElementType(); 319 if (EltTy->isSized()) 320 Align = TD->getABITypeAlignment(EltTy); 321 } 322 323 if (Align) 324 KnownZero = APInt::getLowBitsSet(BitWidth, CountTrailingZeros_32(Align)); 325 return; 326 } 327 328 // Start out not knowing anything. 329 KnownZero.clearAllBits(); KnownOne.clearAllBits(); 330 331 if (Depth == MaxDepth) 332 return; // Limit search depth. 333 334 Operator *I = dyn_cast<Operator>(V); 335 if (!I) return; 336 337 APInt KnownZero2(KnownZero), KnownOne2(KnownOne); 338 switch (I->getOpcode()) { 339 default: break; 340 case Instruction::Load: 341 if (MDNode *MD = cast<LoadInst>(I)->getMetadata(LLVMContext::MD_range)) 342 computeMaskedBitsLoad(*MD, KnownZero); 343 return; 344 case Instruction::And: { 345 // If either the LHS or the RHS are Zero, the result is zero. 346 ComputeMaskedBits(I->getOperand(1), KnownZero, KnownOne, TD, Depth+1); 347 ComputeMaskedBits(I->getOperand(0), KnownZero2, KnownOne2, TD, Depth+1); 348 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 349 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 350 351 // Output known-1 bits are only known if set in both the LHS & RHS. 352 KnownOne &= KnownOne2; 353 // Output known-0 are known to be clear if zero in either the LHS | RHS. 354 KnownZero |= KnownZero2; 355 return; 356 } 357 case Instruction::Or: { 358 ComputeMaskedBits(I->getOperand(1), KnownZero, KnownOne, TD, Depth+1); 359 ComputeMaskedBits(I->getOperand(0), KnownZero2, KnownOne2, TD, Depth+1); 360 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 361 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 362 363 // Output known-0 bits are only known if clear in both the LHS & RHS. 364 KnownZero &= KnownZero2; 365 // Output known-1 are known to be set if set in either the LHS | RHS. 366 KnownOne |= KnownOne2; 367 return; 368 } 369 case Instruction::Xor: { 370 ComputeMaskedBits(I->getOperand(1), KnownZero, KnownOne, TD, Depth+1); 371 ComputeMaskedBits(I->getOperand(0), KnownZero2, KnownOne2, TD, Depth+1); 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 // Output known-0 bits are known if clear or set in both the LHS & RHS. 376 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2); 377 // Output known-1 are known to be set if set in only one of the LHS, RHS. 378 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2); 379 KnownZero = KnownZeroOut; 380 return; 381 } 382 case Instruction::Mul: { 383 bool NSW = cast<OverflowingBinaryOperator>(I)->hasNoSignedWrap(); 384 ComputeMaskedBitsMul(I->getOperand(0), I->getOperand(1), NSW, 385 KnownZero, KnownOne, KnownZero2, KnownOne2, TD, Depth); 386 break; 387 } 388 case Instruction::UDiv: { 389 // For the purposes of computing leading zeros we can conservatively 390 // treat a udiv as a logical right shift by the power of 2 known to 391 // be less than the denominator. 392 ComputeMaskedBits(I->getOperand(0), KnownZero2, KnownOne2, TD, Depth+1); 393 unsigned LeadZ = KnownZero2.countLeadingOnes(); 394 395 KnownOne2.clearAllBits(); 396 KnownZero2.clearAllBits(); 397 ComputeMaskedBits(I->getOperand(1), KnownZero2, KnownOne2, TD, Depth+1); 398 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros(); 399 if (RHSUnknownLeadingOnes != BitWidth) 400 LeadZ = std::min(BitWidth, 401 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1); 402 403 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ); 404 return; 405 } 406 case Instruction::Select: 407 ComputeMaskedBits(I->getOperand(2), KnownZero, KnownOne, TD, Depth+1); 408 ComputeMaskedBits(I->getOperand(1), KnownZero2, KnownOne2, TD, 409 Depth+1); 410 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 411 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 412 413 // Only known if known in both the LHS and RHS. 414 KnownOne &= KnownOne2; 415 KnownZero &= KnownZero2; 416 return; 417 case Instruction::FPTrunc: 418 case Instruction::FPExt: 419 case Instruction::FPToUI: 420 case Instruction::FPToSI: 421 case Instruction::SIToFP: 422 case Instruction::UIToFP: 423 return; // Can't work with floating point. 424 case Instruction::PtrToInt: 425 case Instruction::IntToPtr: 426 // We can't handle these if we don't know the pointer size. 427 if (!TD) return; 428 // FALL THROUGH and handle them the same as zext/trunc. 429 case Instruction::ZExt: 430 case Instruction::Trunc: { 431 Type *SrcTy = I->getOperand(0)->getType(); 432 433 unsigned SrcBitWidth; 434 // Note that we handle pointer operands here because of inttoptr/ptrtoint 435 // which fall through here. 436 SrcBitWidth = TD->getTypeSizeInBits(SrcTy->getScalarType()); 437 438 assert(SrcBitWidth && "SrcBitWidth can't be zero"); 439 KnownZero = KnownZero.zextOrTrunc(SrcBitWidth); 440 KnownOne = KnownOne.zextOrTrunc(SrcBitWidth); 441 ComputeMaskedBits(I->getOperand(0), KnownZero, KnownOne, TD, Depth+1); 442 KnownZero = KnownZero.zextOrTrunc(BitWidth); 443 KnownOne = KnownOne.zextOrTrunc(BitWidth); 444 // Any top bits are known to be zero. 445 if (BitWidth > SrcBitWidth) 446 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - SrcBitWidth); 447 return; 448 } 449 case Instruction::BitCast: { 450 Type *SrcTy = I->getOperand(0)->getType(); 451 if ((SrcTy->isIntegerTy() || SrcTy->isPointerTy()) && 452 // TODO: For now, not handling conversions like: 453 // (bitcast i64 %x to <2 x i32>) 454 !I->getType()->isVectorTy()) { 455 ComputeMaskedBits(I->getOperand(0), KnownZero, KnownOne, TD, Depth+1); 456 return; 457 } 458 break; 459 } 460 case Instruction::SExt: { 461 // Compute the bits in the result that are not present in the input. 462 unsigned SrcBitWidth = I->getOperand(0)->getType()->getScalarSizeInBits(); 463 464 KnownZero = KnownZero.trunc(SrcBitWidth); 465 KnownOne = KnownOne.trunc(SrcBitWidth); 466 ComputeMaskedBits(I->getOperand(0), KnownZero, KnownOne, TD, Depth+1); 467 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 468 KnownZero = KnownZero.zext(BitWidth); 469 KnownOne = KnownOne.zext(BitWidth); 470 471 // If the sign bit of the input is known set or clear, then we know the 472 // top bits of the result. 473 if (KnownZero[SrcBitWidth-1]) // Input sign bit known zero 474 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - SrcBitWidth); 475 else if (KnownOne[SrcBitWidth-1]) // Input sign bit known set 476 KnownOne |= APInt::getHighBitsSet(BitWidth, BitWidth - SrcBitWidth); 477 return; 478 } 479 case Instruction::Shl: 480 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0 481 if (ConstantInt *SA = dyn_cast<ConstantInt>(I->getOperand(1))) { 482 uint64_t ShiftAmt = SA->getLimitedValue(BitWidth); 483 ComputeMaskedBits(I->getOperand(0), KnownZero, KnownOne, TD, Depth+1); 484 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 485 KnownZero <<= ShiftAmt; 486 KnownOne <<= ShiftAmt; 487 KnownZero |= APInt::getLowBitsSet(BitWidth, ShiftAmt); // low bits known 0 488 return; 489 } 490 break; 491 case Instruction::LShr: 492 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0 493 if (ConstantInt *SA = dyn_cast<ConstantInt>(I->getOperand(1))) { 494 // Compute the new bits that are at the top now. 495 uint64_t ShiftAmt = SA->getLimitedValue(BitWidth); 496 497 // Unsigned shift right. 498 ComputeMaskedBits(I->getOperand(0), KnownZero,KnownOne, TD, Depth+1); 499 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 500 KnownZero = APIntOps::lshr(KnownZero, ShiftAmt); 501 KnownOne = APIntOps::lshr(KnownOne, ShiftAmt); 502 // high bits known zero. 503 KnownZero |= APInt::getHighBitsSet(BitWidth, ShiftAmt); 504 return; 505 } 506 break; 507 case Instruction::AShr: 508 // (ashr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0 509 if (ConstantInt *SA = dyn_cast<ConstantInt>(I->getOperand(1))) { 510 // Compute the new bits that are at the top now. 511 uint64_t ShiftAmt = SA->getLimitedValue(BitWidth-1); 512 513 // Signed shift right. 514 ComputeMaskedBits(I->getOperand(0), KnownZero, KnownOne, TD, Depth+1); 515 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 516 KnownZero = APIntOps::lshr(KnownZero, ShiftAmt); 517 KnownOne = APIntOps::lshr(KnownOne, ShiftAmt); 518 519 APInt HighBits(APInt::getHighBitsSet(BitWidth, ShiftAmt)); 520 if (KnownZero[BitWidth-ShiftAmt-1]) // New bits are known zero. 521 KnownZero |= HighBits; 522 else if (KnownOne[BitWidth-ShiftAmt-1]) // New bits are known one. 523 KnownOne |= HighBits; 524 return; 525 } 526 break; 527 case Instruction::Sub: { 528 bool NSW = cast<OverflowingBinaryOperator>(I)->hasNoSignedWrap(); 529 ComputeMaskedBitsAddSub(false, I->getOperand(0), I->getOperand(1), NSW, 530 KnownZero, KnownOne, KnownZero2, KnownOne2, TD, 531 Depth); 532 break; 533 } 534 case Instruction::Add: { 535 bool NSW = cast<OverflowingBinaryOperator>(I)->hasNoSignedWrap(); 536 ComputeMaskedBitsAddSub(true, I->getOperand(0), I->getOperand(1), NSW, 537 KnownZero, KnownOne, KnownZero2, KnownOne2, TD, 538 Depth); 539 break; 540 } 541 case Instruction::SRem: 542 if (ConstantInt *Rem = dyn_cast<ConstantInt>(I->getOperand(1))) { 543 APInt RA = Rem->getValue().abs(); 544 if (RA.isPowerOf2()) { 545 APInt LowBits = RA - 1; 546 ComputeMaskedBits(I->getOperand(0), KnownZero2, KnownOne2, TD, Depth+1); 547 548 // The low bits of the first operand are unchanged by the srem. 549 KnownZero = KnownZero2 & LowBits; 550 KnownOne = KnownOne2 & LowBits; 551 552 // If the first operand is non-negative or has all low bits zero, then 553 // the upper bits are all zero. 554 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits)) 555 KnownZero |= ~LowBits; 556 557 // If the first operand is negative and not all low bits are zero, then 558 // the upper bits are all one. 559 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0)) 560 KnownOne |= ~LowBits; 561 562 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 563 } 564 } 565 566 // The sign bit is the LHS's sign bit, except when the result of the 567 // remainder is zero. 568 if (KnownZero.isNonNegative()) { 569 APInt LHSKnownZero(BitWidth, 0), LHSKnownOne(BitWidth, 0); 570 ComputeMaskedBits(I->getOperand(0), LHSKnownZero, LHSKnownOne, TD, 571 Depth+1); 572 // If it's known zero, our sign bit is also zero. 573 if (LHSKnownZero.isNegative()) 574 KnownZero.setBit(BitWidth - 1); 575 } 576 577 break; 578 case Instruction::URem: { 579 if (ConstantInt *Rem = dyn_cast<ConstantInt>(I->getOperand(1))) { 580 APInt RA = Rem->getValue(); 581 if (RA.isPowerOf2()) { 582 APInt LowBits = (RA - 1); 583 ComputeMaskedBits(I->getOperand(0), KnownZero, KnownOne, TD, 584 Depth+1); 585 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 586 KnownZero |= ~LowBits; 587 KnownOne &= LowBits; 588 break; 589 } 590 } 591 592 // Since the result is less than or equal to either operand, any leading 593 // zero bits in either operand must also exist in the result. 594 ComputeMaskedBits(I->getOperand(0), KnownZero, KnownOne, TD, Depth+1); 595 ComputeMaskedBits(I->getOperand(1), KnownZero2, KnownOne2, TD, Depth+1); 596 597 unsigned Leaders = std::max(KnownZero.countLeadingOnes(), 598 KnownZero2.countLeadingOnes()); 599 KnownOne.clearAllBits(); 600 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders); 601 break; 602 } 603 604 case Instruction::Alloca: { 605 AllocaInst *AI = cast<AllocaInst>(V); 606 unsigned Align = AI->getAlignment(); 607 if (Align == 0 && TD) 608 Align = TD->getABITypeAlignment(AI->getType()->getElementType()); 609 610 if (Align > 0) 611 KnownZero = APInt::getLowBitsSet(BitWidth, CountTrailingZeros_32(Align)); 612 break; 613 } 614 case Instruction::GetElementPtr: { 615 // Analyze all of the subscripts of this getelementptr instruction 616 // to determine if we can prove known low zero bits. 617 APInt LocalKnownZero(BitWidth, 0), LocalKnownOne(BitWidth, 0); 618 ComputeMaskedBits(I->getOperand(0), LocalKnownZero, LocalKnownOne, TD, 619 Depth+1); 620 unsigned TrailZ = LocalKnownZero.countTrailingOnes(); 621 622 gep_type_iterator GTI = gep_type_begin(I); 623 for (unsigned i = 1, e = I->getNumOperands(); i != e; ++i, ++GTI) { 624 Value *Index = I->getOperand(i); 625 if (StructType *STy = dyn_cast<StructType>(*GTI)) { 626 // Handle struct member offset arithmetic. 627 if (!TD) return; 628 const StructLayout *SL = TD->getStructLayout(STy); 629 unsigned Idx = cast<ConstantInt>(Index)->getZExtValue(); 630 uint64_t Offset = SL->getElementOffset(Idx); 631 TrailZ = std::min(TrailZ, 632 CountTrailingZeros_64(Offset)); 633 } else { 634 // Handle array index arithmetic. 635 Type *IndexedTy = GTI.getIndexedType(); 636 if (!IndexedTy->isSized()) return; 637 unsigned GEPOpiBits = Index->getType()->getScalarSizeInBits(); 638 uint64_t TypeSize = TD ? TD->getTypeAllocSize(IndexedTy) : 1; 639 LocalKnownZero = LocalKnownOne = APInt(GEPOpiBits, 0); 640 ComputeMaskedBits(Index, LocalKnownZero, LocalKnownOne, TD, Depth+1); 641 TrailZ = std::min(TrailZ, 642 unsigned(CountTrailingZeros_64(TypeSize) + 643 LocalKnownZero.countTrailingOnes())); 644 } 645 } 646 647 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ); 648 break; 649 } 650 case Instruction::PHI: { 651 PHINode *P = cast<PHINode>(I); 652 // Handle the case of a simple two-predecessor recurrence PHI. 653 // There's a lot more that could theoretically be done here, but 654 // this is sufficient to catch some interesting cases. 655 if (P->getNumIncomingValues() == 2) { 656 for (unsigned i = 0; i != 2; ++i) { 657 Value *L = P->getIncomingValue(i); 658 Value *R = P->getIncomingValue(!i); 659 Operator *LU = dyn_cast<Operator>(L); 660 if (!LU) 661 continue; 662 unsigned Opcode = LU->getOpcode(); 663 // Check for operations that have the property that if 664 // both their operands have low zero bits, the result 665 // will have low zero bits. 666 if (Opcode == Instruction::Add || 667 Opcode == Instruction::Sub || 668 Opcode == Instruction::And || 669 Opcode == Instruction::Or || 670 Opcode == Instruction::Mul) { 671 Value *LL = LU->getOperand(0); 672 Value *LR = LU->getOperand(1); 673 // Find a recurrence. 674 if (LL == I) 675 L = LR; 676 else if (LR == I) 677 L = LL; 678 else 679 break; 680 // Ok, we have a PHI of the form L op= R. Check for low 681 // zero bits. 682 ComputeMaskedBits(R, KnownZero2, KnownOne2, TD, Depth+1); 683 684 // We need to take the minimum number of known bits 685 APInt KnownZero3(KnownZero), KnownOne3(KnownOne); 686 ComputeMaskedBits(L, KnownZero3, KnownOne3, TD, Depth+1); 687 688 KnownZero = APInt::getLowBitsSet(BitWidth, 689 std::min(KnownZero2.countTrailingOnes(), 690 KnownZero3.countTrailingOnes())); 691 break; 692 } 693 } 694 } 695 696 // Unreachable blocks may have zero-operand PHI nodes. 697 if (P->getNumIncomingValues() == 0) 698 return; 699 700 // Otherwise take the unions of the known bit sets of the operands, 701 // taking conservative care to avoid excessive recursion. 702 if (Depth < MaxDepth - 1 && !KnownZero && !KnownOne) { 703 // Skip if every incoming value references to ourself. 704 if (dyn_cast_or_null<UndefValue>(P->hasConstantValue())) 705 break; 706 707 KnownZero = APInt::getAllOnesValue(BitWidth); 708 KnownOne = APInt::getAllOnesValue(BitWidth); 709 for (unsigned i = 0, e = P->getNumIncomingValues(); i != e; ++i) { 710 // Skip direct self references. 711 if (P->getIncomingValue(i) == P) continue; 712 713 KnownZero2 = APInt(BitWidth, 0); 714 KnownOne2 = APInt(BitWidth, 0); 715 // Recurse, but cap the recursion to one level, because we don't 716 // want to waste time spinning around in loops. 717 ComputeMaskedBits(P->getIncomingValue(i), KnownZero2, KnownOne2, TD, 718 MaxDepth-1); 719 KnownZero &= KnownZero2; 720 KnownOne &= KnownOne2; 721 // If all bits have been ruled out, there's no need to check 722 // more operands. 723 if (!KnownZero && !KnownOne) 724 break; 725 } 726 } 727 break; 728 } 729 case Instruction::Call: 730 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { 731 switch (II->getIntrinsicID()) { 732 default: break; 733 case Intrinsic::ctlz: 734 case Intrinsic::cttz: { 735 unsigned LowBits = Log2_32(BitWidth)+1; 736 // If this call is undefined for 0, the result will be less than 2^n. 737 if (II->getArgOperand(1) == ConstantInt::getTrue(II->getContext())) 738 LowBits -= 1; 739 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits); 740 break; 741 } 742 case Intrinsic::ctpop: { 743 unsigned LowBits = Log2_32(BitWidth)+1; 744 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits); 745 break; 746 } 747 case Intrinsic::x86_sse42_crc32_64_8: 748 case Intrinsic::x86_sse42_crc32_64_64: 749 KnownZero = APInt::getHighBitsSet(64, 32); 750 break; 751 } 752 } 753 break; 754 case Instruction::ExtractValue: 755 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I->getOperand(0))) { 756 ExtractValueInst *EVI = cast<ExtractValueInst>(I); 757 if (EVI->getNumIndices() != 1) break; 758 if (EVI->getIndices()[0] == 0) { 759 switch (II->getIntrinsicID()) { 760 default: break; 761 case Intrinsic::uadd_with_overflow: 762 case Intrinsic::sadd_with_overflow: 763 ComputeMaskedBitsAddSub(true, II->getArgOperand(0), 764 II->getArgOperand(1), false, KnownZero, 765 KnownOne, KnownZero2, KnownOne2, TD, Depth); 766 break; 767 case Intrinsic::usub_with_overflow: 768 case Intrinsic::ssub_with_overflow: 769 ComputeMaskedBitsAddSub(false, II->getArgOperand(0), 770 II->getArgOperand(1), false, KnownZero, 771 KnownOne, KnownZero2, KnownOne2, TD, Depth); 772 break; 773 case Intrinsic::umul_with_overflow: 774 case Intrinsic::smul_with_overflow: 775 ComputeMaskedBitsMul(II->getArgOperand(0), II->getArgOperand(1), 776 false, KnownZero, KnownOne, 777 KnownZero2, KnownOne2, TD, Depth); 778 break; 779 } 780 } 781 } 782 } 783} 784 785/// ComputeSignBit - Determine whether the sign bit is known to be zero or 786/// one. Convenience wrapper around ComputeMaskedBits. 787void llvm::ComputeSignBit(Value *V, bool &KnownZero, bool &KnownOne, 788 const DataLayout *TD, unsigned Depth) { 789 unsigned BitWidth = getBitWidth(V->getType(), TD); 790 if (!BitWidth) { 791 KnownZero = false; 792 KnownOne = false; 793 return; 794 } 795 APInt ZeroBits(BitWidth, 0); 796 APInt OneBits(BitWidth, 0); 797 ComputeMaskedBits(V, ZeroBits, OneBits, TD, Depth); 798 KnownOne = OneBits[BitWidth - 1]; 799 KnownZero = ZeroBits[BitWidth - 1]; 800} 801 802/// isPowerOfTwo - Return true if the given value is known to have exactly one 803/// bit set when defined. For vectors return true if every element is known to 804/// be a power of two when defined. Supports values with integer or pointer 805/// types and vectors of integers. 806bool llvm::isPowerOfTwo(Value *V, const DataLayout *TD, bool OrZero, 807 unsigned Depth) { 808 if (Constant *C = dyn_cast<Constant>(V)) { 809 if (C->isNullValue()) 810 return OrZero; 811 if (ConstantInt *CI = dyn_cast<ConstantInt>(C)) 812 return CI->getValue().isPowerOf2(); 813 // TODO: Handle vector constants. 814 } 815 816 // 1 << X is clearly a power of two if the one is not shifted off the end. If 817 // it is shifted off the end then the result is undefined. 818 if (match(V, m_Shl(m_One(), m_Value()))) 819 return true; 820 821 // (signbit) >>l X is clearly a power of two if the one is not shifted off the 822 // bottom. If it is shifted off the bottom then the result is undefined. 823 if (match(V, m_LShr(m_SignBit(), m_Value()))) 824 return true; 825 826 // The remaining tests are all recursive, so bail out if we hit the limit. 827 if (Depth++ == MaxDepth) 828 return false; 829 830 Value *X = 0, *Y = 0; 831 // A shift of a power of two is a power of two or zero. 832 if (OrZero && (match(V, m_Shl(m_Value(X), m_Value())) || 833 match(V, m_Shr(m_Value(X), m_Value())))) 834 return isPowerOfTwo(X, TD, /*OrZero*/true, Depth); 835 836 if (ZExtInst *ZI = dyn_cast<ZExtInst>(V)) 837 return isPowerOfTwo(ZI->getOperand(0), TD, OrZero, Depth); 838 839 if (SelectInst *SI = dyn_cast<SelectInst>(V)) 840 return isPowerOfTwo(SI->getTrueValue(), TD, OrZero, Depth) && 841 isPowerOfTwo(SI->getFalseValue(), TD, OrZero, Depth); 842 843 if (OrZero && match(V, m_And(m_Value(X), m_Value(Y)))) { 844 // A power of two and'd with anything is a power of two or zero. 845 if (isPowerOfTwo(X, TD, /*OrZero*/true, Depth) || 846 isPowerOfTwo(Y, TD, /*OrZero*/true, Depth)) 847 return true; 848 // X & (-X) is always a power of two or zero. 849 if (match(X, m_Neg(m_Specific(Y))) || match(Y, m_Neg(m_Specific(X)))) 850 return true; 851 return false; 852 } 853 854 // An exact divide or right shift can only shift off zero bits, so the result 855 // is a power of two only if the first operand is a power of two and not 856 // copying a sign bit (sdiv int_min, 2). 857 if (match(V, m_Exact(m_LShr(m_Value(), m_Value()))) || 858 match(V, m_Exact(m_UDiv(m_Value(), m_Value())))) { 859 return isPowerOfTwo(cast<Operator>(V)->getOperand(0), TD, OrZero, Depth); 860 } 861 862 return false; 863} 864 865/// \brief Test whether a GEP's result is known to be non-null. 866/// 867/// Uses properties inherent in a GEP to try to determine whether it is known 868/// to be non-null. 869/// 870/// Currently this routine does not support vector GEPs. 871static bool isGEPKnownNonNull(GEPOperator *GEP, const DataLayout *DL, 872 unsigned Depth) { 873 if (!GEP->isInBounds() || GEP->getPointerAddressSpace() != 0) 874 return false; 875 876 // FIXME: Support vector-GEPs. 877 assert(GEP->getType()->isPointerTy() && "We only support plain pointer GEP"); 878 879 // If the base pointer is non-null, we cannot walk to a null address with an 880 // inbounds GEP in address space zero. 881 if (isKnownNonZero(GEP->getPointerOperand(), DL, Depth)) 882 return true; 883 884 // Past this, if we don't have DataLayout, we can't do much. 885 if (!DL) 886 return false; 887 888 // Walk the GEP operands and see if any operand introduces a non-zero offset. 889 // If so, then the GEP cannot produce a null pointer, as doing so would 890 // inherently violate the inbounds contract within address space zero. 891 for (gep_type_iterator GTI = gep_type_begin(GEP), GTE = gep_type_end(GEP); 892 GTI != GTE; ++GTI) { 893 // Struct types are easy -- they must always be indexed by a constant. 894 if (StructType *STy = dyn_cast<StructType>(*GTI)) { 895 ConstantInt *OpC = cast<ConstantInt>(GTI.getOperand()); 896 unsigned ElementIdx = OpC->getZExtValue(); 897 const StructLayout *SL = DL->getStructLayout(STy); 898 uint64_t ElementOffset = SL->getElementOffset(ElementIdx); 899 if (ElementOffset > 0) 900 return true; 901 continue; 902 } 903 904 // If we have a zero-sized type, the index doesn't matter. Keep looping. 905 if (DL->getTypeAllocSize(GTI.getIndexedType()) == 0) 906 continue; 907 908 // Fast path the constant operand case both for efficiency and so we don't 909 // increment Depth when just zipping down an all-constant GEP. 910 if (ConstantInt *OpC = dyn_cast<ConstantInt>(GTI.getOperand())) { 911 if (!OpC->isZero()) 912 return true; 913 continue; 914 } 915 916 // We post-increment Depth here because while isKnownNonZero increments it 917 // as well, when we pop back up that increment won't persist. We don't want 918 // to recurse 10k times just because we have 10k GEP operands. We don't 919 // bail completely out because we want to handle constant GEPs regardless 920 // of depth. 921 if (Depth++ >= MaxDepth) 922 continue; 923 924 if (isKnownNonZero(GTI.getOperand(), DL, Depth)) 925 return true; 926 } 927 928 return false; 929} 930 931/// isKnownNonZero - Return true if the given value is known to be non-zero 932/// when defined. For vectors return true if every element is known to be 933/// non-zero when defined. Supports values with integer or pointer type and 934/// vectors of integers. 935bool llvm::isKnownNonZero(Value *V, const DataLayout *TD, unsigned Depth) { 936 if (Constant *C = dyn_cast<Constant>(V)) { 937 if (C->isNullValue()) 938 return false; 939 if (isa<ConstantInt>(C)) 940 // Must be non-zero due to null test above. 941 return true; 942 // TODO: Handle vectors 943 return false; 944 } 945 946 // The remaining tests are all recursive, so bail out if we hit the limit. 947 if (Depth++ >= MaxDepth) 948 return false; 949 950 // Check for pointer simplifications. 951 if (V->getType()->isPointerTy()) { 952 if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) 953 if (isGEPKnownNonNull(GEP, TD, Depth)) 954 return true; 955 } 956 957 unsigned BitWidth = getBitWidth(V->getType(), TD); 958 959 // X | Y != 0 if X != 0 or Y != 0. 960 Value *X = 0, *Y = 0; 961 if (match(V, m_Or(m_Value(X), m_Value(Y)))) 962 return isKnownNonZero(X, TD, Depth) || isKnownNonZero(Y, TD, Depth); 963 964 // ext X != 0 if X != 0. 965 if (isa<SExtInst>(V) || isa<ZExtInst>(V)) 966 return isKnownNonZero(cast<Instruction>(V)->getOperand(0), TD, Depth); 967 968 // shl X, Y != 0 if X is odd. Note that the value of the shift is undefined 969 // if the lowest bit is shifted off the end. 970 if (BitWidth && match(V, m_Shl(m_Value(X), m_Value(Y)))) { 971 // shl nuw can't remove any non-zero bits. 972 OverflowingBinaryOperator *BO = cast<OverflowingBinaryOperator>(V); 973 if (BO->hasNoUnsignedWrap()) 974 return isKnownNonZero(X, TD, Depth); 975 976 APInt KnownZero(BitWidth, 0); 977 APInt KnownOne(BitWidth, 0); 978 ComputeMaskedBits(X, KnownZero, KnownOne, TD, Depth); 979 if (KnownOne[0]) 980 return true; 981 } 982 // shr X, Y != 0 if X is negative. Note that the value of the shift is not 983 // defined if the sign bit is shifted off the end. 984 else if (match(V, m_Shr(m_Value(X), m_Value(Y)))) { 985 // shr exact can only shift out zero bits. 986 PossiblyExactOperator *BO = cast<PossiblyExactOperator>(V); 987 if (BO->isExact()) 988 return isKnownNonZero(X, TD, Depth); 989 990 bool XKnownNonNegative, XKnownNegative; 991 ComputeSignBit(X, XKnownNonNegative, XKnownNegative, TD, Depth); 992 if (XKnownNegative) 993 return true; 994 } 995 // div exact can only produce a zero if the dividend is zero. 996 else if (match(V, m_Exact(m_IDiv(m_Value(X), m_Value())))) { 997 return isKnownNonZero(X, TD, Depth); 998 } 999 // X + Y. 1000 else if (match(V, m_Add(m_Value(X), m_Value(Y)))) { 1001 bool XKnownNonNegative, XKnownNegative; 1002 bool YKnownNonNegative, YKnownNegative; 1003 ComputeSignBit(X, XKnownNonNegative, XKnownNegative, TD, Depth); 1004 ComputeSignBit(Y, YKnownNonNegative, YKnownNegative, TD, Depth); 1005 1006 // If X and Y are both non-negative (as signed values) then their sum is not 1007 // zero unless both X and Y are zero. 1008 if (XKnownNonNegative && YKnownNonNegative) 1009 if (isKnownNonZero(X, TD, Depth) || isKnownNonZero(Y, TD, Depth)) 1010 return true; 1011 1012 // If X and Y are both negative (as signed values) then their sum is not 1013 // zero unless both X and Y equal INT_MIN. 1014 if (BitWidth && XKnownNegative && YKnownNegative) { 1015 APInt KnownZero(BitWidth, 0); 1016 APInt KnownOne(BitWidth, 0); 1017 APInt Mask = APInt::getSignedMaxValue(BitWidth); 1018 // The sign bit of X is set. If some other bit is set then X is not equal 1019 // to INT_MIN. 1020 ComputeMaskedBits(X, KnownZero, KnownOne, TD, Depth); 1021 if ((KnownOne & Mask) != 0) 1022 return true; 1023 // The sign bit of Y is set. If some other bit is set then Y is not equal 1024 // to INT_MIN. 1025 ComputeMaskedBits(Y, KnownZero, KnownOne, TD, Depth); 1026 if ((KnownOne & Mask) != 0) 1027 return true; 1028 } 1029 1030 // The sum of a non-negative number and a power of two is not zero. 1031 if (XKnownNonNegative && isPowerOfTwo(Y, TD, /*OrZero*/false, Depth)) 1032 return true; 1033 if (YKnownNonNegative && isPowerOfTwo(X, TD, /*OrZero*/false, Depth)) 1034 return true; 1035 } 1036 // X * Y. 1037 else if (match(V, m_Mul(m_Value(X), m_Value(Y)))) { 1038 OverflowingBinaryOperator *BO = cast<OverflowingBinaryOperator>(V); 1039 // If X and Y are non-zero then so is X * Y as long as the multiplication 1040 // does not overflow. 1041 if ((BO->hasNoSignedWrap() || BO->hasNoUnsignedWrap()) && 1042 isKnownNonZero(X, TD, Depth) && isKnownNonZero(Y, TD, Depth)) 1043 return true; 1044 } 1045 // (C ? X : Y) != 0 if X != 0 and Y != 0. 1046 else if (SelectInst *SI = dyn_cast<SelectInst>(V)) { 1047 if (isKnownNonZero(SI->getTrueValue(), TD, Depth) && 1048 isKnownNonZero(SI->getFalseValue(), TD, Depth)) 1049 return true; 1050 } 1051 1052 if (!BitWidth) return false; 1053 APInt KnownZero(BitWidth, 0); 1054 APInt KnownOne(BitWidth, 0); 1055 ComputeMaskedBits(V, KnownZero, KnownOne, TD, Depth); 1056 return KnownOne != 0; 1057} 1058 1059/// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use 1060/// this predicate to simplify operations downstream. Mask is known to be zero 1061/// for bits that V cannot have. 1062/// 1063/// This function is defined on values with integer type, values with pointer 1064/// type (but only if TD is non-null), and vectors of integers. In the case 1065/// where V is a vector, the mask, known zero, and known one values are the 1066/// same width as the vector element, and the bit is set only if it is true 1067/// for all of the elements in the vector. 1068bool llvm::MaskedValueIsZero(Value *V, const APInt &Mask, 1069 const DataLayout *TD, unsigned Depth) { 1070 APInt KnownZero(Mask.getBitWidth(), 0), KnownOne(Mask.getBitWidth(), 0); 1071 ComputeMaskedBits(V, KnownZero, KnownOne, TD, Depth); 1072 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 1073 return (KnownZero & Mask) == Mask; 1074} 1075 1076 1077 1078/// ComputeNumSignBits - Return the number of times the sign bit of the 1079/// register is replicated into the other bits. We know that at least 1 bit 1080/// is always equal to the sign bit (itself), but other cases can give us 1081/// information. For example, immediately after an "ashr X, 2", we know that 1082/// the top 3 bits are all equal to each other, so we return 3. 1083/// 1084/// 'Op' must have a scalar integer type. 1085/// 1086unsigned llvm::ComputeNumSignBits(Value *V, const DataLayout *TD, 1087 unsigned Depth) { 1088 assert((TD || V->getType()->isIntOrIntVectorTy()) && 1089 "ComputeNumSignBits requires a DataLayout object to operate " 1090 "on non-integer values!"); 1091 Type *Ty = V->getType(); 1092 unsigned TyBits = TD ? TD->getTypeSizeInBits(V->getType()->getScalarType()) : 1093 Ty->getScalarSizeInBits(); 1094 unsigned Tmp, Tmp2; 1095 unsigned FirstAnswer = 1; 1096 1097 // Note that ConstantInt is handled by the general ComputeMaskedBits case 1098 // below. 1099 1100 if (Depth == 6) 1101 return 1; // Limit search depth. 1102 1103 Operator *U = dyn_cast<Operator>(V); 1104 switch (Operator::getOpcode(V)) { 1105 default: break; 1106 case Instruction::SExt: 1107 Tmp = TyBits - U->getOperand(0)->getType()->getScalarSizeInBits(); 1108 return ComputeNumSignBits(U->getOperand(0), TD, Depth+1) + Tmp; 1109 1110 case Instruction::AShr: { 1111 Tmp = ComputeNumSignBits(U->getOperand(0), TD, Depth+1); 1112 // ashr X, C -> adds C sign bits. Vectors too. 1113 const APInt *ShAmt; 1114 if (match(U->getOperand(1), m_APInt(ShAmt))) { 1115 Tmp += ShAmt->getZExtValue(); 1116 if (Tmp > TyBits) Tmp = TyBits; 1117 } 1118 return Tmp; 1119 } 1120 case Instruction::Shl: { 1121 const APInt *ShAmt; 1122 if (match(U->getOperand(1), m_APInt(ShAmt))) { 1123 // shl destroys sign bits. 1124 Tmp = ComputeNumSignBits(U->getOperand(0), TD, Depth+1); 1125 Tmp2 = ShAmt->getZExtValue(); 1126 if (Tmp2 >= TyBits || // Bad shift. 1127 Tmp2 >= Tmp) break; // Shifted all sign bits out. 1128 return Tmp - Tmp2; 1129 } 1130 break; 1131 } 1132 case Instruction::And: 1133 case Instruction::Or: 1134 case Instruction::Xor: // NOT is handled here. 1135 // Logical binary ops preserve the number of sign bits at the worst. 1136 Tmp = ComputeNumSignBits(U->getOperand(0), TD, Depth+1); 1137 if (Tmp != 1) { 1138 Tmp2 = ComputeNumSignBits(U->getOperand(1), TD, Depth+1); 1139 FirstAnswer = std::min(Tmp, Tmp2); 1140 // We computed what we know about the sign bits as our first 1141 // answer. Now proceed to the generic code that uses 1142 // ComputeMaskedBits, and pick whichever answer is better. 1143 } 1144 break; 1145 1146 case Instruction::Select: 1147 Tmp = ComputeNumSignBits(U->getOperand(1), TD, Depth+1); 1148 if (Tmp == 1) return 1; // Early out. 1149 Tmp2 = ComputeNumSignBits(U->getOperand(2), TD, Depth+1); 1150 return std::min(Tmp, Tmp2); 1151 1152 case Instruction::Add: 1153 // Add can have at most one carry bit. Thus we know that the output 1154 // is, at worst, one more bit than the inputs. 1155 Tmp = ComputeNumSignBits(U->getOperand(0), TD, Depth+1); 1156 if (Tmp == 1) return 1; // Early out. 1157 1158 // Special case decrementing a value (ADD X, -1): 1159 if (ConstantInt *CRHS = dyn_cast<ConstantInt>(U->getOperand(1))) 1160 if (CRHS->isAllOnesValue()) { 1161 APInt KnownZero(TyBits, 0), KnownOne(TyBits, 0); 1162 ComputeMaskedBits(U->getOperand(0), KnownZero, KnownOne, TD, Depth+1); 1163 1164 // If the input is known to be 0 or 1, the output is 0/-1, which is all 1165 // sign bits set. 1166 if ((KnownZero | APInt(TyBits, 1)).isAllOnesValue()) 1167 return TyBits; 1168 1169 // If we are subtracting one from a positive number, there is no carry 1170 // out of the result. 1171 if (KnownZero.isNegative()) 1172 return Tmp; 1173 } 1174 1175 Tmp2 = ComputeNumSignBits(U->getOperand(1), TD, Depth+1); 1176 if (Tmp2 == 1) return 1; 1177 return std::min(Tmp, Tmp2)-1; 1178 1179 case Instruction::Sub: 1180 Tmp2 = ComputeNumSignBits(U->getOperand(1), TD, Depth+1); 1181 if (Tmp2 == 1) return 1; 1182 1183 // Handle NEG. 1184 if (ConstantInt *CLHS = dyn_cast<ConstantInt>(U->getOperand(0))) 1185 if (CLHS->isNullValue()) { 1186 APInt KnownZero(TyBits, 0), KnownOne(TyBits, 0); 1187 ComputeMaskedBits(U->getOperand(1), KnownZero, KnownOne, TD, Depth+1); 1188 // If the input is known to be 0 or 1, the output is 0/-1, which is all 1189 // sign bits set. 1190 if ((KnownZero | APInt(TyBits, 1)).isAllOnesValue()) 1191 return TyBits; 1192 1193 // If the input is known to be positive (the sign bit is known clear), 1194 // the output of the NEG has the same number of sign bits as the input. 1195 if (KnownZero.isNegative()) 1196 return Tmp2; 1197 1198 // Otherwise, we treat this like a SUB. 1199 } 1200 1201 // Sub can have at most one carry bit. Thus we know that the output 1202 // is, at worst, one more bit than the inputs. 1203 Tmp = ComputeNumSignBits(U->getOperand(0), TD, Depth+1); 1204 if (Tmp == 1) return 1; // Early out. 1205 return std::min(Tmp, Tmp2)-1; 1206 1207 case Instruction::PHI: { 1208 PHINode *PN = cast<PHINode>(U); 1209 // Don't analyze large in-degree PHIs. 1210 if (PN->getNumIncomingValues() > 4) break; 1211 1212 // Take the minimum of all incoming values. This can't infinitely loop 1213 // because of our depth threshold. 1214 Tmp = ComputeNumSignBits(PN->getIncomingValue(0), TD, Depth+1); 1215 for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i) { 1216 if (Tmp == 1) return Tmp; 1217 Tmp = std::min(Tmp, 1218 ComputeNumSignBits(PN->getIncomingValue(i), TD, Depth+1)); 1219 } 1220 return Tmp; 1221 } 1222 1223 case Instruction::Trunc: 1224 // FIXME: it's tricky to do anything useful for this, but it is an important 1225 // case for targets like X86. 1226 break; 1227 } 1228 1229 // Finally, if we can prove that the top bits of the result are 0's or 1's, 1230 // use this information. 1231 APInt KnownZero(TyBits, 0), KnownOne(TyBits, 0); 1232 APInt Mask; 1233 ComputeMaskedBits(V, KnownZero, KnownOne, TD, Depth); 1234 1235 if (KnownZero.isNegative()) { // sign bit is 0 1236 Mask = KnownZero; 1237 } else if (KnownOne.isNegative()) { // sign bit is 1; 1238 Mask = KnownOne; 1239 } else { 1240 // Nothing known. 1241 return FirstAnswer; 1242 } 1243 1244 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine 1245 // the number of identical bits in the top of the input value. 1246 Mask = ~Mask; 1247 Mask <<= Mask.getBitWidth()-TyBits; 1248 // Return # leading zeros. We use 'min' here in case Val was zero before 1249 // shifting. We don't want to return '64' as for an i32 "0". 1250 return std::max(FirstAnswer, std::min(TyBits, Mask.countLeadingZeros())); 1251} 1252 1253/// ComputeMultiple - This function computes the integer multiple of Base that 1254/// equals V. If successful, it returns true and returns the multiple in 1255/// Multiple. If unsuccessful, it returns false. It looks 1256/// through SExt instructions only if LookThroughSExt is true. 1257bool llvm::ComputeMultiple(Value *V, unsigned Base, Value *&Multiple, 1258 bool LookThroughSExt, unsigned Depth) { 1259 const unsigned MaxDepth = 6; 1260 1261 assert(V && "No Value?"); 1262 assert(Depth <= MaxDepth && "Limit Search Depth"); 1263 assert(V->getType()->isIntegerTy() && "Not integer or pointer type!"); 1264 1265 Type *T = V->getType(); 1266 1267 ConstantInt *CI = dyn_cast<ConstantInt>(V); 1268 1269 if (Base == 0) 1270 return false; 1271 1272 if (Base == 1) { 1273 Multiple = V; 1274 return true; 1275 } 1276 1277 ConstantExpr *CO = dyn_cast<ConstantExpr>(V); 1278 Constant *BaseVal = ConstantInt::get(T, Base); 1279 if (CO && CO == BaseVal) { 1280 // Multiple is 1. 1281 Multiple = ConstantInt::get(T, 1); 1282 return true; 1283 } 1284 1285 if (CI && CI->getZExtValue() % Base == 0) { 1286 Multiple = ConstantInt::get(T, CI->getZExtValue() / Base); 1287 return true; 1288 } 1289 1290 if (Depth == MaxDepth) return false; // Limit search depth. 1291 1292 Operator *I = dyn_cast<Operator>(V); 1293 if (!I) return false; 1294 1295 switch (I->getOpcode()) { 1296 default: break; 1297 case Instruction::SExt: 1298 if (!LookThroughSExt) return false; 1299 // otherwise fall through to ZExt 1300 case Instruction::ZExt: 1301 return ComputeMultiple(I->getOperand(0), Base, Multiple, 1302 LookThroughSExt, Depth+1); 1303 case Instruction::Shl: 1304 case Instruction::Mul: { 1305 Value *Op0 = I->getOperand(0); 1306 Value *Op1 = I->getOperand(1); 1307 1308 if (I->getOpcode() == Instruction::Shl) { 1309 ConstantInt *Op1CI = dyn_cast<ConstantInt>(Op1); 1310 if (!Op1CI) return false; 1311 // Turn Op0 << Op1 into Op0 * 2^Op1 1312 APInt Op1Int = Op1CI->getValue(); 1313 uint64_t BitToSet = Op1Int.getLimitedValue(Op1Int.getBitWidth() - 1); 1314 APInt API(Op1Int.getBitWidth(), 0); 1315 API.setBit(BitToSet); 1316 Op1 = ConstantInt::get(V->getContext(), API); 1317 } 1318 1319 Value *Mul0 = NULL; 1320 if (ComputeMultiple(Op0, Base, Mul0, LookThroughSExt, Depth+1)) { 1321 if (Constant *Op1C = dyn_cast<Constant>(Op1)) 1322 if (Constant *MulC = dyn_cast<Constant>(Mul0)) { 1323 if (Op1C->getType()->getPrimitiveSizeInBits() < 1324 MulC->getType()->getPrimitiveSizeInBits()) 1325 Op1C = ConstantExpr::getZExt(Op1C, MulC->getType()); 1326 if (Op1C->getType()->getPrimitiveSizeInBits() > 1327 MulC->getType()->getPrimitiveSizeInBits()) 1328 MulC = ConstantExpr::getZExt(MulC, Op1C->getType()); 1329 1330 // V == Base * (Mul0 * Op1), so return (Mul0 * Op1) 1331 Multiple = ConstantExpr::getMul(MulC, Op1C); 1332 return true; 1333 } 1334 1335 if (ConstantInt *Mul0CI = dyn_cast<ConstantInt>(Mul0)) 1336 if (Mul0CI->getValue() == 1) { 1337 // V == Base * Op1, so return Op1 1338 Multiple = Op1; 1339 return true; 1340 } 1341 } 1342 1343 Value *Mul1 = NULL; 1344 if (ComputeMultiple(Op1, Base, Mul1, LookThroughSExt, Depth+1)) { 1345 if (Constant *Op0C = dyn_cast<Constant>(Op0)) 1346 if (Constant *MulC = dyn_cast<Constant>(Mul1)) { 1347 if (Op0C->getType()->getPrimitiveSizeInBits() < 1348 MulC->getType()->getPrimitiveSizeInBits()) 1349 Op0C = ConstantExpr::getZExt(Op0C, MulC->getType()); 1350 if (Op0C->getType()->getPrimitiveSizeInBits() > 1351 MulC->getType()->getPrimitiveSizeInBits()) 1352 MulC = ConstantExpr::getZExt(MulC, Op0C->getType()); 1353 1354 // V == Base * (Mul1 * Op0), so return (Mul1 * Op0) 1355 Multiple = ConstantExpr::getMul(MulC, Op0C); 1356 return true; 1357 } 1358 1359 if (ConstantInt *Mul1CI = dyn_cast<ConstantInt>(Mul1)) 1360 if (Mul1CI->getValue() == 1) { 1361 // V == Base * Op0, so return Op0 1362 Multiple = Op0; 1363 return true; 1364 } 1365 } 1366 } 1367 } 1368 1369 // We could not determine if V is a multiple of Base. 1370 return false; 1371} 1372 1373/// CannotBeNegativeZero - Return true if we can prove that the specified FP 1374/// value is never equal to -0.0. 1375/// 1376/// NOTE: this function will need to be revisited when we support non-default 1377/// rounding modes! 1378/// 1379bool llvm::CannotBeNegativeZero(const Value *V, unsigned Depth) { 1380 if (const ConstantFP *CFP = dyn_cast<ConstantFP>(V)) 1381 return !CFP->getValueAPF().isNegZero(); 1382 1383 if (Depth == 6) 1384 return 1; // Limit search depth. 1385 1386 const Operator *I = dyn_cast<Operator>(V); 1387 if (I == 0) return false; 1388 1389 // Check if the nsz fast-math flag is set 1390 if (const FPMathOperator *FPO = dyn_cast<FPMathOperator>(I)) 1391 if (FPO->hasNoSignedZeros()) 1392 return true; 1393 1394 // (add x, 0.0) is guaranteed to return +0.0, not -0.0. 1395 if (I->getOpcode() == Instruction::FAdd && 1396 isa<ConstantFP>(I->getOperand(1)) && 1397 cast<ConstantFP>(I->getOperand(1))->isNullValue()) 1398 return true; 1399 1400 // sitofp and uitofp turn into +0.0 for zero. 1401 if (isa<SIToFPInst>(I) || isa<UIToFPInst>(I)) 1402 return true; 1403 1404 if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) 1405 // sqrt(-0.0) = -0.0, no other negative results are possible. 1406 if (II->getIntrinsicID() == Intrinsic::sqrt) 1407 return CannotBeNegativeZero(II->getArgOperand(0), Depth+1); 1408 1409 if (const CallInst *CI = dyn_cast<CallInst>(I)) 1410 if (const Function *F = CI->getCalledFunction()) { 1411 if (F->isDeclaration()) { 1412 // abs(x) != -0.0 1413 if (F->getName() == "abs") return true; 1414 // fabs[lf](x) != -0.0 1415 if (F->getName() == "fabs") return true; 1416 if (F->getName() == "fabsf") return true; 1417 if (F->getName() == "fabsl") return true; 1418 if (F->getName() == "sqrt" || F->getName() == "sqrtf" || 1419 F->getName() == "sqrtl") 1420 return CannotBeNegativeZero(CI->getArgOperand(0), Depth+1); 1421 } 1422 } 1423 1424 return false; 1425} 1426 1427/// isBytewiseValue - If the specified value can be set by repeating the same 1428/// byte in memory, return the i8 value that it is represented with. This is 1429/// true for all i8 values obviously, but is also true for i32 0, i32 -1, 1430/// i16 0xF0F0, double 0.0 etc. If the value can't be handled with a repeated 1431/// byte store (e.g. i16 0x1234), return null. 1432Value *llvm::isBytewiseValue(Value *V) { 1433 // All byte-wide stores are splatable, even of arbitrary variables. 1434 if (V->getType()->isIntegerTy(8)) return V; 1435 1436 // Handle 'null' ConstantArrayZero etc. 1437 if (Constant *C = dyn_cast<Constant>(V)) 1438 if (C->isNullValue()) 1439 return Constant::getNullValue(Type::getInt8Ty(V->getContext())); 1440 1441 // Constant float and double values can be handled as integer values if the 1442 // corresponding integer value is "byteable". An important case is 0.0. 1443 if (ConstantFP *CFP = dyn_cast<ConstantFP>(V)) { 1444 if (CFP->getType()->isFloatTy()) 1445 V = ConstantExpr::getBitCast(CFP, Type::getInt32Ty(V->getContext())); 1446 if (CFP->getType()->isDoubleTy()) 1447 V = ConstantExpr::getBitCast(CFP, Type::getInt64Ty(V->getContext())); 1448 // Don't handle long double formats, which have strange constraints. 1449 } 1450 1451 // We can handle constant integers that are power of two in size and a 1452 // multiple of 8 bits. 1453 if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) { 1454 unsigned Width = CI->getBitWidth(); 1455 if (isPowerOf2_32(Width) && Width > 8) { 1456 // We can handle this value if the recursive binary decomposition is the 1457 // same at all levels. 1458 APInt Val = CI->getValue(); 1459 APInt Val2; 1460 while (Val.getBitWidth() != 8) { 1461 unsigned NextWidth = Val.getBitWidth()/2; 1462 Val2 = Val.lshr(NextWidth); 1463 Val2 = Val2.trunc(Val.getBitWidth()/2); 1464 Val = Val.trunc(Val.getBitWidth()/2); 1465 1466 // If the top/bottom halves aren't the same, reject it. 1467 if (Val != Val2) 1468 return 0; 1469 } 1470 return ConstantInt::get(V->getContext(), Val); 1471 } 1472 } 1473 1474 // A ConstantDataArray/Vector is splatable if all its members are equal and 1475 // also splatable. 1476 if (ConstantDataSequential *CA = dyn_cast<ConstantDataSequential>(V)) { 1477 Value *Elt = CA->getElementAsConstant(0); 1478 Value *Val = isBytewiseValue(Elt); 1479 if (!Val) 1480 return 0; 1481 1482 for (unsigned I = 1, E = CA->getNumElements(); I != E; ++I) 1483 if (CA->getElementAsConstant(I) != Elt) 1484 return 0; 1485 1486 return Val; 1487 } 1488 1489 // Conceptually, we could handle things like: 1490 // %a = zext i8 %X to i16 1491 // %b = shl i16 %a, 8 1492 // %c = or i16 %a, %b 1493 // but until there is an example that actually needs this, it doesn't seem 1494 // worth worrying about. 1495 return 0; 1496} 1497 1498 1499// This is the recursive version of BuildSubAggregate. It takes a few different 1500// arguments. Idxs is the index within the nested struct From that we are 1501// looking at now (which is of type IndexedType). IdxSkip is the number of 1502// indices from Idxs that should be left out when inserting into the resulting 1503// struct. To is the result struct built so far, new insertvalue instructions 1504// build on that. 1505static Value *BuildSubAggregate(Value *From, Value* To, Type *IndexedType, 1506 SmallVector<unsigned, 10> &Idxs, 1507 unsigned IdxSkip, 1508 Instruction *InsertBefore) { 1509 llvm::StructType *STy = llvm::dyn_cast<llvm::StructType>(IndexedType); 1510 if (STy) { 1511 // Save the original To argument so we can modify it 1512 Value *OrigTo = To; 1513 // General case, the type indexed by Idxs is a struct 1514 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { 1515 // Process each struct element recursively 1516 Idxs.push_back(i); 1517 Value *PrevTo = To; 1518 To = BuildSubAggregate(From, To, STy->getElementType(i), Idxs, IdxSkip, 1519 InsertBefore); 1520 Idxs.pop_back(); 1521 if (!To) { 1522 // Couldn't find any inserted value for this index? Cleanup 1523 while (PrevTo != OrigTo) { 1524 InsertValueInst* Del = cast<InsertValueInst>(PrevTo); 1525 PrevTo = Del->getAggregateOperand(); 1526 Del->eraseFromParent(); 1527 } 1528 // Stop processing elements 1529 break; 1530 } 1531 } 1532 // If we successfully found a value for each of our subaggregates 1533 if (To) 1534 return To; 1535 } 1536 // Base case, the type indexed by SourceIdxs is not a struct, or not all of 1537 // the struct's elements had a value that was inserted directly. In the latter 1538 // case, perhaps we can't determine each of the subelements individually, but 1539 // we might be able to find the complete struct somewhere. 1540 1541 // Find the value that is at that particular spot 1542 Value *V = FindInsertedValue(From, Idxs); 1543 1544 if (!V) 1545 return NULL; 1546 1547 // Insert the value in the new (sub) aggregrate 1548 return llvm::InsertValueInst::Create(To, V, makeArrayRef(Idxs).slice(IdxSkip), 1549 "tmp", InsertBefore); 1550} 1551 1552// This helper takes a nested struct and extracts a part of it (which is again a 1553// struct) into a new value. For example, given the struct: 1554// { a, { b, { c, d }, e } } 1555// and the indices "1, 1" this returns 1556// { c, d }. 1557// 1558// It does this by inserting an insertvalue for each element in the resulting 1559// struct, as opposed to just inserting a single struct. This will only work if 1560// each of the elements of the substruct are known (ie, inserted into From by an 1561// insertvalue instruction somewhere). 1562// 1563// All inserted insertvalue instructions are inserted before InsertBefore 1564static Value *BuildSubAggregate(Value *From, ArrayRef<unsigned> idx_range, 1565 Instruction *InsertBefore) { 1566 assert(InsertBefore && "Must have someplace to insert!"); 1567 Type *IndexedType = ExtractValueInst::getIndexedType(From->getType(), 1568 idx_range); 1569 Value *To = UndefValue::get(IndexedType); 1570 SmallVector<unsigned, 10> Idxs(idx_range.begin(), idx_range.end()); 1571 unsigned IdxSkip = Idxs.size(); 1572 1573 return BuildSubAggregate(From, To, IndexedType, Idxs, IdxSkip, InsertBefore); 1574} 1575 1576/// FindInsertedValue - Given an aggregrate and an sequence of indices, see if 1577/// the scalar value indexed is already around as a register, for example if it 1578/// were inserted directly into the aggregrate. 1579/// 1580/// If InsertBefore is not null, this function will duplicate (modified) 1581/// insertvalues when a part of a nested struct is extracted. 1582Value *llvm::FindInsertedValue(Value *V, ArrayRef<unsigned> idx_range, 1583 Instruction *InsertBefore) { 1584 // Nothing to index? Just return V then (this is useful at the end of our 1585 // recursion). 1586 if (idx_range.empty()) 1587 return V; 1588 // We have indices, so V should have an indexable type. 1589 assert((V->getType()->isStructTy() || V->getType()->isArrayTy()) && 1590 "Not looking at a struct or array?"); 1591 assert(ExtractValueInst::getIndexedType(V->getType(), idx_range) && 1592 "Invalid indices for type?"); 1593 1594 if (Constant *C = dyn_cast<Constant>(V)) { 1595 C = C->getAggregateElement(idx_range[0]); 1596 if (C == 0) return 0; 1597 return FindInsertedValue(C, idx_range.slice(1), InsertBefore); 1598 } 1599 1600 if (InsertValueInst *I = dyn_cast<InsertValueInst>(V)) { 1601 // Loop the indices for the insertvalue instruction in parallel with the 1602 // requested indices 1603 const unsigned *req_idx = idx_range.begin(); 1604 for (const unsigned *i = I->idx_begin(), *e = I->idx_end(); 1605 i != e; ++i, ++req_idx) { 1606 if (req_idx == idx_range.end()) { 1607 // We can't handle this without inserting insertvalues 1608 if (!InsertBefore) 1609 return 0; 1610 1611 // The requested index identifies a part of a nested aggregate. Handle 1612 // this specially. For example, 1613 // %A = insertvalue { i32, {i32, i32 } } undef, i32 10, 1, 0 1614 // %B = insertvalue { i32, {i32, i32 } } %A, i32 11, 1, 1 1615 // %C = extractvalue {i32, { i32, i32 } } %B, 1 1616 // This can be changed into 1617 // %A = insertvalue {i32, i32 } undef, i32 10, 0 1618 // %C = insertvalue {i32, i32 } %A, i32 11, 1 1619 // which allows the unused 0,0 element from the nested struct to be 1620 // removed. 1621 return BuildSubAggregate(V, makeArrayRef(idx_range.begin(), req_idx), 1622 InsertBefore); 1623 } 1624 1625 // This insert value inserts something else than what we are looking for. 1626 // See if the (aggregrate) value inserted into has the value we are 1627 // looking for, then. 1628 if (*req_idx != *i) 1629 return FindInsertedValue(I->getAggregateOperand(), idx_range, 1630 InsertBefore); 1631 } 1632 // If we end up here, the indices of the insertvalue match with those 1633 // requested (though possibly only partially). Now we recursively look at 1634 // the inserted value, passing any remaining indices. 1635 return FindInsertedValue(I->getInsertedValueOperand(), 1636 makeArrayRef(req_idx, idx_range.end()), 1637 InsertBefore); 1638 } 1639 1640 if (ExtractValueInst *I = dyn_cast<ExtractValueInst>(V)) { 1641 // If we're extracting a value from an aggregrate that was extracted from 1642 // something else, we can extract from that something else directly instead. 1643 // However, we will need to chain I's indices with the requested indices. 1644 1645 // Calculate the number of indices required 1646 unsigned size = I->getNumIndices() + idx_range.size(); 1647 // Allocate some space to put the new indices in 1648 SmallVector<unsigned, 5> Idxs; 1649 Idxs.reserve(size); 1650 // Add indices from the extract value instruction 1651 Idxs.append(I->idx_begin(), I->idx_end()); 1652 1653 // Add requested indices 1654 Idxs.append(idx_range.begin(), idx_range.end()); 1655 1656 assert(Idxs.size() == size 1657 && "Number of indices added not correct?"); 1658 1659 return FindInsertedValue(I->getAggregateOperand(), Idxs, InsertBefore); 1660 } 1661 // Otherwise, we don't know (such as, extracting from a function return value 1662 // or load instruction) 1663 return 0; 1664} 1665 1666/// GetPointerBaseWithConstantOffset - Analyze the specified pointer to see if 1667/// it can be expressed as a base pointer plus a constant offset. Return the 1668/// base and offset to the caller. 1669Value *llvm::GetPointerBaseWithConstantOffset(Value *Ptr, int64_t &Offset, 1670 const DataLayout &TD) { 1671 Operator *PtrOp = dyn_cast<Operator>(Ptr); 1672 if (PtrOp == 0 || Ptr->getType()->isVectorTy()) 1673 return Ptr; 1674 1675 // Just look through bitcasts. 1676 if (PtrOp->getOpcode() == Instruction::BitCast) 1677 return GetPointerBaseWithConstantOffset(PtrOp->getOperand(0), Offset, TD); 1678 1679 // If this is a GEP with constant indices, we can look through it. 1680 GEPOperator *GEP = dyn_cast<GEPOperator>(PtrOp); 1681 if (GEP == 0 || !GEP->hasAllConstantIndices()) return Ptr; 1682 1683 gep_type_iterator GTI = gep_type_begin(GEP); 1684 for (User::op_iterator I = GEP->idx_begin(), E = GEP->idx_end(); I != E; 1685 ++I, ++GTI) { 1686 ConstantInt *OpC = cast<ConstantInt>(*I); 1687 if (OpC->isZero()) continue; 1688 1689 // Handle a struct and array indices which add their offset to the pointer. 1690 if (StructType *STy = dyn_cast<StructType>(*GTI)) { 1691 Offset += TD.getStructLayout(STy)->getElementOffset(OpC->getZExtValue()); 1692 } else { 1693 uint64_t Size = TD.getTypeAllocSize(GTI.getIndexedType()); 1694 Offset += OpC->getSExtValue()*Size; 1695 } 1696 } 1697 1698 // Re-sign extend from the pointer size if needed to get overflow edge cases 1699 // right. 1700 unsigned PtrSize = TD.getPointerSizeInBits(); 1701 if (PtrSize < 64) 1702 Offset = SignExtend64(Offset, PtrSize); 1703 1704 return GetPointerBaseWithConstantOffset(GEP->getPointerOperand(), Offset, TD); 1705} 1706 1707 1708/// getConstantStringInfo - This function computes the length of a 1709/// null-terminated C string pointed to by V. If successful, it returns true 1710/// and returns the string in Str. If unsuccessful, it returns false. 1711bool llvm::getConstantStringInfo(const Value *V, StringRef &Str, 1712 uint64_t Offset, bool TrimAtNul) { 1713 assert(V); 1714 1715 // Look through bitcast instructions and geps. 1716 V = V->stripPointerCasts(); 1717 1718 // If the value is a GEP instructionor constant expression, treat it as an 1719 // offset. 1720 if (const GEPOperator *GEP = dyn_cast<GEPOperator>(V)) { 1721 // Make sure the GEP has exactly three arguments. 1722 if (GEP->getNumOperands() != 3) 1723 return false; 1724 1725 // Make sure the index-ee is a pointer to array of i8. 1726 PointerType *PT = cast<PointerType>(GEP->getOperand(0)->getType()); 1727 ArrayType *AT = dyn_cast<ArrayType>(PT->getElementType()); 1728 if (AT == 0 || !AT->getElementType()->isIntegerTy(8)) 1729 return false; 1730 1731 // Check to make sure that the first operand of the GEP is an integer and 1732 // has value 0 so that we are sure we're indexing into the initializer. 1733 const ConstantInt *FirstIdx = dyn_cast<ConstantInt>(GEP->getOperand(1)); 1734 if (FirstIdx == 0 || !FirstIdx->isZero()) 1735 return false; 1736 1737 // If the second index isn't a ConstantInt, then this is a variable index 1738 // into the array. If this occurs, we can't say anything meaningful about 1739 // the string. 1740 uint64_t StartIdx = 0; 1741 if (const ConstantInt *CI = dyn_cast<ConstantInt>(GEP->getOperand(2))) 1742 StartIdx = CI->getZExtValue(); 1743 else 1744 return false; 1745 return getConstantStringInfo(GEP->getOperand(0), Str, StartIdx+Offset); 1746 } 1747 1748 // The GEP instruction, constant or instruction, must reference a global 1749 // variable that is a constant and is initialized. The referenced constant 1750 // initializer is the array that we'll use for optimization. 1751 const GlobalVariable *GV = dyn_cast<GlobalVariable>(V); 1752 if (!GV || !GV->isConstant() || !GV->hasDefinitiveInitializer()) 1753 return false; 1754 1755 // Handle the all-zeros case 1756 if (GV->getInitializer()->isNullValue()) { 1757 // This is a degenerate case. The initializer is constant zero so the 1758 // length of the string must be zero. 1759 Str = ""; 1760 return true; 1761 } 1762 1763 // Must be a Constant Array 1764 const ConstantDataArray *Array = 1765 dyn_cast<ConstantDataArray>(GV->getInitializer()); 1766 if (Array == 0 || !Array->isString()) 1767 return false; 1768 1769 // Get the number of elements in the array 1770 uint64_t NumElts = Array->getType()->getArrayNumElements(); 1771 1772 // Start out with the entire array in the StringRef. 1773 Str = Array->getAsString(); 1774 1775 if (Offset > NumElts) 1776 return false; 1777 1778 // Skip over 'offset' bytes. 1779 Str = Str.substr(Offset); 1780 1781 if (TrimAtNul) { 1782 // Trim off the \0 and anything after it. If the array is not nul 1783 // terminated, we just return the whole end of string. The client may know 1784 // some other way that the string is length-bound. 1785 Str = Str.substr(0, Str.find('\0')); 1786 } 1787 return true; 1788} 1789 1790// These next two are very similar to the above, but also look through PHI 1791// nodes. 1792// TODO: See if we can integrate these two together. 1793 1794/// GetStringLengthH - If we can compute the length of the string pointed to by 1795/// the specified pointer, return 'len+1'. If we can't, return 0. 1796static uint64_t GetStringLengthH(Value *V, SmallPtrSet<PHINode*, 32> &PHIs) { 1797 // Look through noop bitcast instructions. 1798 V = V->stripPointerCasts(); 1799 1800 // If this is a PHI node, there are two cases: either we have already seen it 1801 // or we haven't. 1802 if (PHINode *PN = dyn_cast<PHINode>(V)) { 1803 if (!PHIs.insert(PN)) 1804 return ~0ULL; // already in the set. 1805 1806 // If it was new, see if all the input strings are the same length. 1807 uint64_t LenSoFar = ~0ULL; 1808 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 1809 uint64_t Len = GetStringLengthH(PN->getIncomingValue(i), PHIs); 1810 if (Len == 0) return 0; // Unknown length -> unknown. 1811 1812 if (Len == ~0ULL) continue; 1813 1814 if (Len != LenSoFar && LenSoFar != ~0ULL) 1815 return 0; // Disagree -> unknown. 1816 LenSoFar = Len; 1817 } 1818 1819 // Success, all agree. 1820 return LenSoFar; 1821 } 1822 1823 // strlen(select(c,x,y)) -> strlen(x) ^ strlen(y) 1824 if (SelectInst *SI = dyn_cast<SelectInst>(V)) { 1825 uint64_t Len1 = GetStringLengthH(SI->getTrueValue(), PHIs); 1826 if (Len1 == 0) return 0; 1827 uint64_t Len2 = GetStringLengthH(SI->getFalseValue(), PHIs); 1828 if (Len2 == 0) return 0; 1829 if (Len1 == ~0ULL) return Len2; 1830 if (Len2 == ~0ULL) return Len1; 1831 if (Len1 != Len2) return 0; 1832 return Len1; 1833 } 1834 1835 // Otherwise, see if we can read the string. 1836 StringRef StrData; 1837 if (!getConstantStringInfo(V, StrData)) 1838 return 0; 1839 1840 return StrData.size()+1; 1841} 1842 1843/// GetStringLength - If we can compute the length of the string pointed to by 1844/// the specified pointer, return 'len+1'. If we can't, return 0. 1845uint64_t llvm::GetStringLength(Value *V) { 1846 if (!V->getType()->isPointerTy()) return 0; 1847 1848 SmallPtrSet<PHINode*, 32> PHIs; 1849 uint64_t Len = GetStringLengthH(V, PHIs); 1850 // If Len is ~0ULL, we had an infinite phi cycle: this is dead code, so return 1851 // an empty string as a length. 1852 return Len == ~0ULL ? 1 : Len; 1853} 1854 1855Value * 1856llvm::GetUnderlyingObject(Value *V, const DataLayout *TD, unsigned MaxLookup) { 1857 if (!V->getType()->isPointerTy()) 1858 return V; 1859 for (unsigned Count = 0; MaxLookup == 0 || Count < MaxLookup; ++Count) { 1860 if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) { 1861 V = GEP->getPointerOperand(); 1862 } else if (Operator::getOpcode(V) == Instruction::BitCast) { 1863 V = cast<Operator>(V)->getOperand(0); 1864 } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) { 1865 if (GA->mayBeOverridden()) 1866 return V; 1867 V = GA->getAliasee(); 1868 } else { 1869 // See if InstructionSimplify knows any relevant tricks. 1870 if (Instruction *I = dyn_cast<Instruction>(V)) 1871 // TODO: Acquire a DominatorTree and use it. 1872 if (Value *Simplified = SimplifyInstruction(I, TD, 0)) { 1873 V = Simplified; 1874 continue; 1875 } 1876 1877 return V; 1878 } 1879 assert(V->getType()->isPointerTy() && "Unexpected operand type!"); 1880 } 1881 return V; 1882} 1883 1884void 1885llvm::GetUnderlyingObjects(Value *V, 1886 SmallVectorImpl<Value *> &Objects, 1887 const DataLayout *TD, 1888 unsigned MaxLookup) { 1889 SmallPtrSet<Value *, 4> Visited; 1890 SmallVector<Value *, 4> Worklist; 1891 Worklist.push_back(V); 1892 do { 1893 Value *P = Worklist.pop_back_val(); 1894 P = GetUnderlyingObject(P, TD, MaxLookup); 1895 1896 if (!Visited.insert(P)) 1897 continue; 1898 1899 if (SelectInst *SI = dyn_cast<SelectInst>(P)) { 1900 Worklist.push_back(SI->getTrueValue()); 1901 Worklist.push_back(SI->getFalseValue()); 1902 continue; 1903 } 1904 1905 if (PHINode *PN = dyn_cast<PHINode>(P)) { 1906 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 1907 Worklist.push_back(PN->getIncomingValue(i)); 1908 continue; 1909 } 1910 1911 Objects.push_back(P); 1912 } while (!Worklist.empty()); 1913} 1914 1915/// onlyUsedByLifetimeMarkers - Return true if the only users of this pointer 1916/// are lifetime markers. 1917/// 1918bool llvm::onlyUsedByLifetimeMarkers(const Value *V) { 1919 for (Value::const_use_iterator UI = V->use_begin(), UE = V->use_end(); 1920 UI != UE; ++UI) { 1921 const IntrinsicInst *II = dyn_cast<IntrinsicInst>(*UI); 1922 if (!II) return false; 1923 1924 if (II->getIntrinsicID() != Intrinsic::lifetime_start && 1925 II->getIntrinsicID() != Intrinsic::lifetime_end) 1926 return false; 1927 } 1928 return true; 1929} 1930 1931bool llvm::isSafeToSpeculativelyExecute(const Value *V, 1932 const DataLayout *TD) { 1933 const Operator *Inst = dyn_cast<Operator>(V); 1934 if (!Inst) 1935 return false; 1936 1937 for (unsigned i = 0, e = Inst->getNumOperands(); i != e; ++i) 1938 if (Constant *C = dyn_cast<Constant>(Inst->getOperand(i))) 1939 if (C->canTrap()) 1940 return false; 1941 1942 switch (Inst->getOpcode()) { 1943 default: 1944 return true; 1945 case Instruction::UDiv: 1946 case Instruction::URem: 1947 // x / y is undefined if y == 0, but calcuations like x / 3 are safe. 1948 return isKnownNonZero(Inst->getOperand(1), TD); 1949 case Instruction::SDiv: 1950 case Instruction::SRem: { 1951 Value *Op = Inst->getOperand(1); 1952 // x / y is undefined if y == 0 1953 if (!isKnownNonZero(Op, TD)) 1954 return false; 1955 // x / y might be undefined if y == -1 1956 unsigned BitWidth = getBitWidth(Op->getType(), TD); 1957 if (BitWidth == 0) 1958 return false; 1959 APInt KnownZero(BitWidth, 0); 1960 APInt KnownOne(BitWidth, 0); 1961 ComputeMaskedBits(Op, KnownZero, KnownOne, TD); 1962 return !!KnownZero; 1963 } 1964 case Instruction::Load: { 1965 const LoadInst *LI = cast<LoadInst>(Inst); 1966 if (!LI->isUnordered()) 1967 return false; 1968 return LI->getPointerOperand()->isDereferenceablePointer(); 1969 } 1970 case Instruction::Call: { 1971 if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) { 1972 switch (II->getIntrinsicID()) { 1973 // These synthetic intrinsics have no side-effects, and just mark 1974 // information about their operands. 1975 // FIXME: There are other no-op synthetic instructions that potentially 1976 // should be considered at least *safe* to speculate... 1977 case Intrinsic::dbg_declare: 1978 case Intrinsic::dbg_value: 1979 return true; 1980 1981 case Intrinsic::bswap: 1982 case Intrinsic::ctlz: 1983 case Intrinsic::ctpop: 1984 case Intrinsic::cttz: 1985 case Intrinsic::objectsize: 1986 case Intrinsic::sadd_with_overflow: 1987 case Intrinsic::smul_with_overflow: 1988 case Intrinsic::ssub_with_overflow: 1989 case Intrinsic::uadd_with_overflow: 1990 case Intrinsic::umul_with_overflow: 1991 case Intrinsic::usub_with_overflow: 1992 return true; 1993 // TODO: some fp intrinsics are marked as having the same error handling 1994 // as libm. They're safe to speculate when they won't error. 1995 // TODO: are convert_{from,to}_fp16 safe? 1996 // TODO: can we list target-specific intrinsics here? 1997 default: break; 1998 } 1999 } 2000 return false; // The called function could have undefined behavior or 2001 // side-effects, even if marked readnone nounwind. 2002 } 2003 case Instruction::VAArg: 2004 case Instruction::Alloca: 2005 case Instruction::Invoke: 2006 case Instruction::PHI: 2007 case Instruction::Store: 2008 case Instruction::Ret: 2009 case Instruction::Br: 2010 case Instruction::IndirectBr: 2011 case Instruction::Switch: 2012 case Instruction::Unreachable: 2013 case Instruction::Fence: 2014 case Instruction::LandingPad: 2015 case Instruction::AtomicRMW: 2016 case Instruction::AtomicCmpXchg: 2017 case Instruction::Resume: 2018 return false; // Misc instructions which have effects 2019 } 2020} 2021