1193323Sed//===- ValueTracking.cpp - Walk computations to compute properties --------===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file contains routines that help analyze properties that chains of 11193323Sed// computations have. 12193323Sed// 13193323Sed//===----------------------------------------------------------------------===// 14193323Sed 15193323Sed#include "llvm/Analysis/ValueTracking.h" 16252723Sdim#include "llvm/ADT/SmallPtrSet.h" 17218893Sdim#include "llvm/Analysis/InstructionSimplify.h" 18263509Sdim#include "llvm/Analysis/MemoryBuiltins.h" 19252723Sdim#include "llvm/IR/Constants.h" 20252723Sdim#include "llvm/IR/DataLayout.h" 21252723Sdim#include "llvm/IR/GlobalAlias.h" 22252723Sdim#include "llvm/IR/GlobalVariable.h" 23252723Sdim#include "llvm/IR/Instructions.h" 24252723Sdim#include "llvm/IR/IntrinsicInst.h" 25252723Sdim#include "llvm/IR/LLVMContext.h" 26252723Sdim#include "llvm/IR/Metadata.h" 27252723Sdim#include "llvm/IR/Operator.h" 28235633Sdim#include "llvm/Support/ConstantRange.h" 29193323Sed#include "llvm/Support/GetElementPtrTypeIterator.h" 30193323Sed#include "llvm/Support/MathExtras.h" 31218893Sdim#include "llvm/Support/PatternMatch.h" 32193323Sed#include <cstring> 33193323Sedusing namespace llvm; 34218893Sdimusing namespace llvm::PatternMatch; 35193323Sed 36218893Sdimconst unsigned MaxDepth = 6; 37218893Sdim 38218893Sdim/// getBitWidth - Returns the bitwidth of the given scalar or pointer type (if 39218893Sdim/// unknown returns 0). For vector types, returns the element type's bitwidth. 40245431Sdimstatic unsigned getBitWidth(Type *Ty, const DataLayout *TD) { 41218893Sdim if (unsigned BitWidth = Ty->getScalarSizeInBits()) 42218893Sdim return BitWidth; 43263509Sdim 44263509Sdim return TD ? TD->getPointerTypeSizeInBits(Ty) : 0; 45218893Sdim} 46218893Sdim 47235633Sdimstatic void ComputeMaskedBitsAddSub(bool Add, Value *Op0, Value *Op1, bool NSW, 48235633Sdim APInt &KnownZero, APInt &KnownOne, 49235633Sdim APInt &KnownZero2, APInt &KnownOne2, 50245431Sdim const DataLayout *TD, unsigned Depth) { 51235633Sdim if (!Add) { 52235633Sdim if (ConstantInt *CLHS = dyn_cast<ConstantInt>(Op0)) { 53235633Sdim // We know that the top bits of C-X are clear if X contains less bits 54235633Sdim // than C (i.e. no wrap-around can happen). For example, 20-X is 55235633Sdim // positive if we can prove that X is >= 0 and < 16. 56235633Sdim if (!CLHS->getValue().isNegative()) { 57235633Sdim unsigned BitWidth = KnownZero.getBitWidth(); 58235633Sdim unsigned NLZ = (CLHS->getValue()+1).countLeadingZeros(); 59235633Sdim // NLZ can't be BitWidth with no sign bit 60235633Sdim APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1); 61235633Sdim llvm::ComputeMaskedBits(Op1, KnownZero2, KnownOne2, TD, Depth+1); 62252723Sdim 63235633Sdim // If all of the MaskV bits are known to be zero, then we know the 64235633Sdim // output top bits are zero, because we now know that the output is 65235633Sdim // from [0-C]. 66235633Sdim if ((KnownZero2 & MaskV) == MaskV) { 67235633Sdim unsigned NLZ2 = CLHS->getValue().countLeadingZeros(); 68235633Sdim // Top bits known zero. 69235633Sdim KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2); 70235633Sdim } 71235633Sdim } 72235633Sdim } 73235633Sdim } 74235633Sdim 75235633Sdim unsigned BitWidth = KnownZero.getBitWidth(); 76235633Sdim 77235633Sdim // If one of the operands has trailing zeros, then the bits that the 78235633Sdim // other operand has in those bit positions will be preserved in the 79235633Sdim // result. For an add, this works with either operand. For a subtract, 80235633Sdim // this only works if the known zeros are in the right operand. 81235633Sdim APInt LHSKnownZero(BitWidth, 0), LHSKnownOne(BitWidth, 0); 82235633Sdim llvm::ComputeMaskedBits(Op0, LHSKnownZero, LHSKnownOne, TD, Depth+1); 83235633Sdim assert((LHSKnownZero & LHSKnownOne) == 0 && 84235633Sdim "Bits known to be one AND zero?"); 85235633Sdim unsigned LHSKnownZeroOut = LHSKnownZero.countTrailingOnes(); 86235633Sdim 87235633Sdim llvm::ComputeMaskedBits(Op1, KnownZero2, KnownOne2, TD, Depth+1); 88252723Sdim assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 89235633Sdim unsigned RHSKnownZeroOut = KnownZero2.countTrailingOnes(); 90235633Sdim 91235633Sdim // Determine which operand has more trailing zeros, and use that 92235633Sdim // many bits from the other operand. 93235633Sdim if (LHSKnownZeroOut > RHSKnownZeroOut) { 94235633Sdim if (Add) { 95235633Sdim APInt Mask = APInt::getLowBitsSet(BitWidth, LHSKnownZeroOut); 96235633Sdim KnownZero |= KnownZero2 & Mask; 97235633Sdim KnownOne |= KnownOne2 & Mask; 98235633Sdim } else { 99235633Sdim // If the known zeros are in the left operand for a subtract, 100235633Sdim // fall back to the minimum known zeros in both operands. 101235633Sdim KnownZero |= APInt::getLowBitsSet(BitWidth, 102235633Sdim std::min(LHSKnownZeroOut, 103235633Sdim RHSKnownZeroOut)); 104235633Sdim } 105235633Sdim } else if (RHSKnownZeroOut >= LHSKnownZeroOut) { 106235633Sdim APInt Mask = APInt::getLowBitsSet(BitWidth, RHSKnownZeroOut); 107235633Sdim KnownZero |= LHSKnownZero & Mask; 108235633Sdim KnownOne |= LHSKnownOne & Mask; 109235633Sdim } 110235633Sdim 111235633Sdim // Are we still trying to solve for the sign bit? 112235633Sdim if (!KnownZero.isNegative() && !KnownOne.isNegative()) { 113235633Sdim if (NSW) { 114235633Sdim if (Add) { 115235633Sdim // Adding two positive numbers can't wrap into negative 116235633Sdim if (LHSKnownZero.isNegative() && KnownZero2.isNegative()) 117235633Sdim KnownZero |= APInt::getSignBit(BitWidth); 118235633Sdim // and adding two negative numbers can't wrap into positive. 119235633Sdim else if (LHSKnownOne.isNegative() && KnownOne2.isNegative()) 120235633Sdim KnownOne |= APInt::getSignBit(BitWidth); 121235633Sdim } else { 122235633Sdim // Subtracting a negative number from a positive one can't wrap 123235633Sdim if (LHSKnownZero.isNegative() && KnownOne2.isNegative()) 124235633Sdim KnownZero |= APInt::getSignBit(BitWidth); 125235633Sdim // neither can subtracting a positive number from a negative one. 126235633Sdim else if (LHSKnownOne.isNegative() && KnownZero2.isNegative()) 127235633Sdim KnownOne |= APInt::getSignBit(BitWidth); 128235633Sdim } 129235633Sdim } 130235633Sdim } 131235633Sdim} 132235633Sdim 133235633Sdimstatic void ComputeMaskedBitsMul(Value *Op0, Value *Op1, bool NSW, 134235633Sdim APInt &KnownZero, APInt &KnownOne, 135235633Sdim APInt &KnownZero2, APInt &KnownOne2, 136245431Sdim const DataLayout *TD, unsigned Depth) { 137235633Sdim unsigned BitWidth = KnownZero.getBitWidth(); 138235633Sdim ComputeMaskedBits(Op1, KnownZero, KnownOne, TD, Depth+1); 139235633Sdim ComputeMaskedBits(Op0, KnownZero2, KnownOne2, TD, Depth+1); 140235633Sdim assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 141235633Sdim assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 142235633Sdim 143235633Sdim bool isKnownNegative = false; 144235633Sdim bool isKnownNonNegative = false; 145235633Sdim // If the multiplication is known not to overflow, compute the sign bit. 146235633Sdim if (NSW) { 147235633Sdim if (Op0 == Op1) { 148235633Sdim // The product of a number with itself is non-negative. 149235633Sdim isKnownNonNegative = true; 150235633Sdim } else { 151235633Sdim bool isKnownNonNegativeOp1 = KnownZero.isNegative(); 152235633Sdim bool isKnownNonNegativeOp0 = KnownZero2.isNegative(); 153235633Sdim bool isKnownNegativeOp1 = KnownOne.isNegative(); 154235633Sdim bool isKnownNegativeOp0 = KnownOne2.isNegative(); 155235633Sdim // The product of two numbers with the same sign is non-negative. 156235633Sdim isKnownNonNegative = (isKnownNegativeOp1 && isKnownNegativeOp0) || 157235633Sdim (isKnownNonNegativeOp1 && isKnownNonNegativeOp0); 158235633Sdim // The product of a negative number and a non-negative number is either 159235633Sdim // negative or zero. 160235633Sdim if (!isKnownNonNegative) 161235633Sdim isKnownNegative = (isKnownNegativeOp1 && isKnownNonNegativeOp0 && 162235633Sdim isKnownNonZero(Op0, TD, Depth)) || 163235633Sdim (isKnownNegativeOp0 && isKnownNonNegativeOp1 && 164235633Sdim isKnownNonZero(Op1, TD, Depth)); 165235633Sdim } 166235633Sdim } 167235633Sdim 168235633Sdim // If low bits are zero in either operand, output low known-0 bits. 169235633Sdim // Also compute a conserative estimate for high known-0 bits. 170235633Sdim // More trickiness is possible, but this is sufficient for the 171235633Sdim // interesting case of alignment computation. 172235633Sdim KnownOne.clearAllBits(); 173235633Sdim unsigned TrailZ = KnownZero.countTrailingOnes() + 174235633Sdim KnownZero2.countTrailingOnes(); 175235633Sdim unsigned LeadZ = std::max(KnownZero.countLeadingOnes() + 176235633Sdim KnownZero2.countLeadingOnes(), 177235633Sdim BitWidth) - BitWidth; 178235633Sdim 179235633Sdim TrailZ = std::min(TrailZ, BitWidth); 180235633Sdim LeadZ = std::min(LeadZ, BitWidth); 181235633Sdim KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) | 182235633Sdim APInt::getHighBitsSet(BitWidth, LeadZ); 183235633Sdim 184235633Sdim // Only make use of no-wrap flags if we failed to compute the sign bit 185235633Sdim // directly. This matters if the multiplication always overflows, in 186235633Sdim // which case we prefer to follow the result of the direct computation, 187235633Sdim // though as the program is invoking undefined behaviour we can choose 188235633Sdim // whatever we like here. 189235633Sdim if (isKnownNonNegative && !KnownOne.isNegative()) 190235633Sdim KnownZero.setBit(BitWidth - 1); 191235633Sdim else if (isKnownNegative && !KnownZero.isNegative()) 192235633Sdim KnownOne.setBit(BitWidth - 1); 193235633Sdim} 194235633Sdim 195235633Sdimvoid llvm::computeMaskedBitsLoad(const MDNode &Ranges, APInt &KnownZero) { 196235633Sdim unsigned BitWidth = KnownZero.getBitWidth(); 197235633Sdim unsigned NumRanges = Ranges.getNumOperands() / 2; 198235633Sdim assert(NumRanges >= 1); 199235633Sdim 200235633Sdim // Use the high end of the ranges to find leading zeros. 201235633Sdim unsigned MinLeadingZeros = BitWidth; 202235633Sdim for (unsigned i = 0; i < NumRanges; ++i) { 203235633Sdim ConstantInt *Lower = cast<ConstantInt>(Ranges.getOperand(2*i + 0)); 204235633Sdim ConstantInt *Upper = cast<ConstantInt>(Ranges.getOperand(2*i + 1)); 205235633Sdim ConstantRange Range(Lower->getValue(), Upper->getValue()); 206235633Sdim if (Range.isWrappedSet()) 207235633Sdim MinLeadingZeros = 0; // -1 has no zeros 208235633Sdim unsigned LeadingZeros = (Upper->getValue() - 1).countLeadingZeros(); 209235633Sdim MinLeadingZeros = std::min(LeadingZeros, MinLeadingZeros); 210235633Sdim } 211235633Sdim 212235633Sdim KnownZero = APInt::getHighBitsSet(BitWidth, MinLeadingZeros); 213235633Sdim} 214235633Sdim/// ComputeMaskedBits - Determine which of the bits are known to be either zero 215235633Sdim/// or one and return them in the KnownZero/KnownOne bit sets. 216235633Sdim/// 217193323Sed/// NOTE: we cannot consider 'undef' to be "IsZero" here. The problem is that 218193323Sed/// we cannot optimize based on the assumption that it is zero without changing 219193323Sed/// it to be an explicit zero. If we don't change it to zero, other code could 220193323Sed/// optimized based on the contradictory assumption that it is non-zero. 221193323Sed/// Because instcombine aggressively folds operations with undef args anyway, 222193323Sed/// this won't lose us code quality. 223198090Srdivacky/// 224198090Srdivacky/// This function is defined on values with integer type, values with pointer 225198090Srdivacky/// type (but only if TD is non-null), and vectors of integers. In the case 226235633Sdim/// where V is a vector, known zero, and known one values are the 227198090Srdivacky/// same width as the vector element, and the bit is set only if it is true 228198090Srdivacky/// for all of the elements in the vector. 229235633Sdimvoid llvm::ComputeMaskedBits(Value *V, APInt &KnownZero, APInt &KnownOne, 230245431Sdim const DataLayout *TD, unsigned Depth) { 231193323Sed assert(V && "No Value?"); 232193323Sed assert(Depth <= MaxDepth && "Limit Search Depth"); 233235633Sdim unsigned BitWidth = KnownZero.getBitWidth(); 234235633Sdim 235235633Sdim assert((V->getType()->isIntOrIntVectorTy() || 236235633Sdim V->getType()->getScalarType()->isPointerTy()) && 237235633Sdim "Not integer or pointer type!"); 238194612Sed assert((!TD || 239194612Sed TD->getTypeSizeInBits(V->getType()->getScalarType()) == BitWidth) && 240203954Srdivacky (!V->getType()->isIntOrIntVectorTy() || 241194612Sed V->getType()->getScalarSizeInBits() == BitWidth) && 242235633Sdim KnownZero.getBitWidth() == BitWidth && 243193323Sed KnownOne.getBitWidth() == BitWidth && 244193323Sed "V, Mask, KnownOne and KnownZero should have same BitWidth"); 245193323Sed 246193323Sed if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) { 247193323Sed // We know all of the bits for a constant! 248235633Sdim KnownOne = CI->getValue(); 249235633Sdim KnownZero = ~KnownOne; 250193323Sed return; 251193323Sed } 252194612Sed // Null and aggregate-zero are all-zeros. 253194612Sed if (isa<ConstantPointerNull>(V) || 254194612Sed isa<ConstantAggregateZero>(V)) { 255218893Sdim KnownOne.clearAllBits(); 256235633Sdim KnownZero = APInt::getAllOnesValue(BitWidth); 257193323Sed return; 258193323Sed } 259194612Sed // Handle a constant vector by taking the intersection of the known bits of 260235633Sdim // each element. There is no real need to handle ConstantVector here, because 261235633Sdim // we don't handle undef in any particularly useful way. 262235633Sdim if (ConstantDataSequential *CDS = dyn_cast<ConstantDataSequential>(V)) { 263235633Sdim // We know that CDS must be a vector of integers. Take the intersection of 264235633Sdim // each element. 265218893Sdim KnownZero.setAllBits(); KnownOne.setAllBits(); 266235633Sdim APInt Elt(KnownZero.getBitWidth(), 0); 267235633Sdim for (unsigned i = 0, e = CDS->getNumElements(); i != e; ++i) { 268235633Sdim Elt = CDS->getElementAsInteger(i); 269235633Sdim KnownZero &= ~Elt; 270252723Sdim KnownOne &= Elt; 271194612Sed } 272194612Sed return; 273194612Sed } 274252723Sdim 275193323Sed // The address of an aligned GlobalValue has trailing zeros. 276193323Sed if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) { 277193323Sed unsigned Align = GV->getAlignment(); 278235633Sdim if (Align == 0 && TD) { 279235633Sdim if (GlobalVariable *GVar = dyn_cast<GlobalVariable>(GV)) { 280235633Sdim Type *ObjectType = GVar->getType()->getElementType(); 281235633Sdim if (ObjectType->isSized()) { 282235633Sdim // If the object is defined in the current Module, we'll be giving 283235633Sdim // it the preferred alignment. Otherwise, we have to assume that it 284235633Sdim // may only have the minimum ABI alignment. 285235633Sdim if (!GVar->isDeclaration() && !GVar->isWeakForLinker()) 286235633Sdim Align = TD->getPreferredAlignment(GVar); 287235633Sdim else 288235633Sdim Align = TD->getABITypeAlignment(ObjectType); 289235633Sdim } 290235633Sdim } 291198090Srdivacky } 292193323Sed if (Align > 0) 293235633Sdim KnownZero = APInt::getLowBitsSet(BitWidth, 294263509Sdim countTrailingZeros(Align)); 295193323Sed else 296218893Sdim KnownZero.clearAllBits(); 297218893Sdim KnownOne.clearAllBits(); 298193323Sed return; 299193323Sed } 300198090Srdivacky // A weak GlobalAlias is totally unknown. A non-weak GlobalAlias has 301198090Srdivacky // the bits of its aliasee. 302198090Srdivacky if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) { 303198090Srdivacky if (GA->mayBeOverridden()) { 304218893Sdim KnownZero.clearAllBits(); KnownOne.clearAllBits(); 305198090Srdivacky } else { 306235633Sdim ComputeMaskedBits(GA->getAliasee(), KnownZero, KnownOne, TD, Depth+1); 307198090Srdivacky } 308198090Srdivacky return; 309198090Srdivacky } 310252723Sdim 311223017Sdim if (Argument *A = dyn_cast<Argument>(V)) { 312245431Sdim unsigned Align = 0; 313245431Sdim 314245431Sdim if (A->hasByValAttr()) { 315245431Sdim // Get alignment information off byval arguments if specified in the IR. 316245431Sdim Align = A->getParamAlignment(); 317245431Sdim } else if (TD && A->hasStructRetAttr()) { 318245431Sdim // An sret parameter has at least the ABI alignment of the return type. 319245431Sdim Type *EltTy = cast<PointerType>(A->getType())->getElementType(); 320245431Sdim if (EltTy->isSized()) 321245431Sdim Align = TD->getABITypeAlignment(EltTy); 322245431Sdim } 323245431Sdim 324245431Sdim if (Align) 325263509Sdim KnownZero = APInt::getLowBitsSet(BitWidth, countTrailingZeros(Align)); 326223017Sdim return; 327223017Sdim } 328193323Sed 329223017Sdim // Start out not knowing anything. 330223017Sdim KnownZero.clearAllBits(); KnownOne.clearAllBits(); 331193323Sed 332235633Sdim if (Depth == MaxDepth) 333193323Sed return; // Limit search depth. 334193323Sed 335198090Srdivacky Operator *I = dyn_cast<Operator>(V); 336193323Sed if (!I) return; 337193323Sed 338193323Sed APInt KnownZero2(KnownZero), KnownOne2(KnownOne); 339198090Srdivacky switch (I->getOpcode()) { 340193323Sed default: break; 341235633Sdim case Instruction::Load: 342235633Sdim if (MDNode *MD = cast<LoadInst>(I)->getMetadata(LLVMContext::MD_range)) 343235633Sdim computeMaskedBitsLoad(*MD, KnownZero); 344235633Sdim return; 345193323Sed case Instruction::And: { 346193323Sed // If either the LHS or the RHS are Zero, the result is zero. 347235633Sdim ComputeMaskedBits(I->getOperand(1), KnownZero, KnownOne, TD, Depth+1); 348235633Sdim ComputeMaskedBits(I->getOperand(0), KnownZero2, KnownOne2, TD, Depth+1); 349252723Sdim assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 350252723Sdim assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 351252723Sdim 352193323Sed // Output known-1 bits are only known if set in both the LHS & RHS. 353193323Sed KnownOne &= KnownOne2; 354193323Sed // Output known-0 are known to be clear if zero in either the LHS | RHS. 355193323Sed KnownZero |= KnownZero2; 356193323Sed return; 357193323Sed } 358193323Sed case Instruction::Or: { 359235633Sdim ComputeMaskedBits(I->getOperand(1), KnownZero, KnownOne, TD, Depth+1); 360235633Sdim ComputeMaskedBits(I->getOperand(0), KnownZero2, KnownOne2, TD, Depth+1); 361252723Sdim assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 362252723Sdim assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 363252723Sdim 364193323Sed // Output known-0 bits are only known if clear in both the LHS & RHS. 365193323Sed KnownZero &= KnownZero2; 366193323Sed // Output known-1 are known to be set if set in either the LHS | RHS. 367193323Sed KnownOne |= KnownOne2; 368193323Sed return; 369193323Sed } 370193323Sed case Instruction::Xor: { 371235633Sdim ComputeMaskedBits(I->getOperand(1), KnownZero, KnownOne, TD, Depth+1); 372235633Sdim ComputeMaskedBits(I->getOperand(0), KnownZero2, KnownOne2, TD, Depth+1); 373252723Sdim assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 374252723Sdim assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 375252723Sdim 376193323Sed // Output known-0 bits are known if clear or set in both the LHS & RHS. 377193323Sed APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2); 378193323Sed // Output known-1 are known to be set if set in only one of the LHS, RHS. 379193323Sed KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2); 380193323Sed KnownZero = KnownZeroOut; 381193323Sed return; 382193323Sed } 383193323Sed case Instruction::Mul: { 384235633Sdim bool NSW = cast<OverflowingBinaryOperator>(I)->hasNoSignedWrap(); 385235633Sdim ComputeMaskedBitsMul(I->getOperand(0), I->getOperand(1), NSW, 386235633Sdim KnownZero, KnownOne, KnownZero2, KnownOne2, TD, Depth); 387235633Sdim break; 388193323Sed } 389193323Sed case Instruction::UDiv: { 390193323Sed // For the purposes of computing leading zeros we can conservatively 391193323Sed // treat a udiv as a logical right shift by the power of 2 known to 392193323Sed // be less than the denominator. 393235633Sdim ComputeMaskedBits(I->getOperand(0), KnownZero2, KnownOne2, TD, Depth+1); 394193323Sed unsigned LeadZ = KnownZero2.countLeadingOnes(); 395193323Sed 396218893Sdim KnownOne2.clearAllBits(); 397218893Sdim KnownZero2.clearAllBits(); 398235633Sdim ComputeMaskedBits(I->getOperand(1), KnownZero2, KnownOne2, TD, Depth+1); 399193323Sed unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros(); 400193323Sed if (RHSUnknownLeadingOnes != BitWidth) 401193323Sed LeadZ = std::min(BitWidth, 402193323Sed LeadZ + BitWidth - RHSUnknownLeadingOnes - 1); 403193323Sed 404235633Sdim KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ); 405193323Sed return; 406193323Sed } 407193323Sed case Instruction::Select: 408235633Sdim ComputeMaskedBits(I->getOperand(2), KnownZero, KnownOne, TD, Depth+1); 409235633Sdim ComputeMaskedBits(I->getOperand(1), KnownZero2, KnownOne2, TD, 410193323Sed Depth+1); 411252723Sdim assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 412252723Sdim assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 413193323Sed 414193323Sed // Only known if known in both the LHS and RHS. 415193323Sed KnownOne &= KnownOne2; 416193323Sed KnownZero &= KnownZero2; 417193323Sed return; 418193323Sed case Instruction::FPTrunc: 419193323Sed case Instruction::FPExt: 420193323Sed case Instruction::FPToUI: 421193323Sed case Instruction::FPToSI: 422193323Sed case Instruction::SIToFP: 423193323Sed case Instruction::UIToFP: 424193323Sed return; // Can't work with floating point. 425193323Sed case Instruction::PtrToInt: 426193323Sed case Instruction::IntToPtr: 427193323Sed // We can't handle these if we don't know the pointer size. 428193323Sed if (!TD) return; 429193323Sed // FALL THROUGH and handle them the same as zext/trunc. 430193323Sed case Instruction::ZExt: 431193323Sed case Instruction::Trunc: { 432226890Sdim Type *SrcTy = I->getOperand(0)->getType(); 433245431Sdim 434198090Srdivacky unsigned SrcBitWidth; 435193323Sed // Note that we handle pointer operands here because of inttoptr/ptrtoint 436193323Sed // which fall through here. 437252723Sdim if(TD) { 438252723Sdim SrcBitWidth = TD->getTypeSizeInBits(SrcTy->getScalarType()); 439252723Sdim } else { 440252723Sdim SrcBitWidth = SrcTy->getScalarSizeInBits(); 441252723Sdim if (!SrcBitWidth) return; 442252723Sdim } 443245431Sdim 444245431Sdim assert(SrcBitWidth && "SrcBitWidth can't be zero"); 445218893Sdim KnownZero = KnownZero.zextOrTrunc(SrcBitWidth); 446218893Sdim KnownOne = KnownOne.zextOrTrunc(SrcBitWidth); 447235633Sdim ComputeMaskedBits(I->getOperand(0), KnownZero, KnownOne, TD, Depth+1); 448218893Sdim KnownZero = KnownZero.zextOrTrunc(BitWidth); 449218893Sdim KnownOne = KnownOne.zextOrTrunc(BitWidth); 450193323Sed // Any top bits are known to be zero. 451193323Sed if (BitWidth > SrcBitWidth) 452193323Sed KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - SrcBitWidth); 453193323Sed return; 454193323Sed } 455193323Sed case Instruction::BitCast: { 456226890Sdim Type *SrcTy = I->getOperand(0)->getType(); 457204642Srdivacky if ((SrcTy->isIntegerTy() || SrcTy->isPointerTy()) && 458195340Sed // TODO: For now, not handling conversions like: 459195340Sed // (bitcast i64 %x to <2 x i32>) 460204642Srdivacky !I->getType()->isVectorTy()) { 461235633Sdim ComputeMaskedBits(I->getOperand(0), KnownZero, KnownOne, TD, Depth+1); 462193323Sed return; 463193323Sed } 464193323Sed break; 465193323Sed } 466193323Sed case Instruction::SExt: { 467193323Sed // Compute the bits in the result that are not present in the input. 468198090Srdivacky unsigned SrcBitWidth = I->getOperand(0)->getType()->getScalarSizeInBits(); 469252723Sdim 470218893Sdim KnownZero = KnownZero.trunc(SrcBitWidth); 471218893Sdim KnownOne = KnownOne.trunc(SrcBitWidth); 472235633Sdim ComputeMaskedBits(I->getOperand(0), KnownZero, KnownOne, TD, Depth+1); 473252723Sdim assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 474218893Sdim KnownZero = KnownZero.zext(BitWidth); 475218893Sdim KnownOne = KnownOne.zext(BitWidth); 476193323Sed 477193323Sed // If the sign bit of the input is known set or clear, then we know the 478193323Sed // top bits of the result. 479193323Sed if (KnownZero[SrcBitWidth-1]) // Input sign bit known zero 480193323Sed KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - SrcBitWidth); 481193323Sed else if (KnownOne[SrcBitWidth-1]) // Input sign bit known set 482193323Sed KnownOne |= APInt::getHighBitsSet(BitWidth, BitWidth - SrcBitWidth); 483193323Sed return; 484193323Sed } 485193323Sed case Instruction::Shl: 486193323Sed // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0 487193323Sed if (ConstantInt *SA = dyn_cast<ConstantInt>(I->getOperand(1))) { 488193323Sed uint64_t ShiftAmt = SA->getLimitedValue(BitWidth); 489235633Sdim ComputeMaskedBits(I->getOperand(0), KnownZero, KnownOne, TD, Depth+1); 490252723Sdim assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 491193323Sed KnownZero <<= ShiftAmt; 492193323Sed KnownOne <<= ShiftAmt; 493193323Sed KnownZero |= APInt::getLowBitsSet(BitWidth, ShiftAmt); // low bits known 0 494193323Sed return; 495193323Sed } 496193323Sed break; 497193323Sed case Instruction::LShr: 498193323Sed // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0 499193323Sed if (ConstantInt *SA = dyn_cast<ConstantInt>(I->getOperand(1))) { 500193323Sed // Compute the new bits that are at the top now. 501193323Sed uint64_t ShiftAmt = SA->getLimitedValue(BitWidth); 502252723Sdim 503193323Sed // Unsigned shift right. 504235633Sdim ComputeMaskedBits(I->getOperand(0), KnownZero,KnownOne, TD, Depth+1); 505252723Sdim assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 506193323Sed KnownZero = APIntOps::lshr(KnownZero, ShiftAmt); 507193323Sed KnownOne = APIntOps::lshr(KnownOne, ShiftAmt); 508193323Sed // high bits known zero. 509193323Sed KnownZero |= APInt::getHighBitsSet(BitWidth, ShiftAmt); 510193323Sed return; 511193323Sed } 512193323Sed break; 513193323Sed case Instruction::AShr: 514193323Sed // (ashr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0 515193323Sed if (ConstantInt *SA = dyn_cast<ConstantInt>(I->getOperand(1))) { 516193323Sed // Compute the new bits that are at the top now. 517218893Sdim uint64_t ShiftAmt = SA->getLimitedValue(BitWidth-1); 518252723Sdim 519193323Sed // Signed shift right. 520235633Sdim ComputeMaskedBits(I->getOperand(0), KnownZero, KnownOne, TD, Depth+1); 521252723Sdim assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 522193323Sed KnownZero = APIntOps::lshr(KnownZero, ShiftAmt); 523193323Sed KnownOne = APIntOps::lshr(KnownOne, ShiftAmt); 524252723Sdim 525193323Sed APInt HighBits(APInt::getHighBitsSet(BitWidth, ShiftAmt)); 526193323Sed if (KnownZero[BitWidth-ShiftAmt-1]) // New bits are known zero. 527193323Sed KnownZero |= HighBits; 528193323Sed else if (KnownOne[BitWidth-ShiftAmt-1]) // New bits are known one. 529193323Sed KnownOne |= HighBits; 530193323Sed return; 531193323Sed } 532193323Sed break; 533193323Sed case Instruction::Sub: { 534235633Sdim bool NSW = cast<OverflowingBinaryOperator>(I)->hasNoSignedWrap(); 535235633Sdim ComputeMaskedBitsAddSub(false, I->getOperand(0), I->getOperand(1), NSW, 536235633Sdim KnownZero, KnownOne, KnownZero2, KnownOne2, TD, 537235633Sdim Depth); 538235633Sdim break; 539193323Sed } 540193323Sed case Instruction::Add: { 541235633Sdim bool NSW = cast<OverflowingBinaryOperator>(I)->hasNoSignedWrap(); 542235633Sdim ComputeMaskedBitsAddSub(true, I->getOperand(0), I->getOperand(1), NSW, 543235633Sdim KnownZero, KnownOne, KnownZero2, KnownOne2, TD, 544235633Sdim Depth); 545235633Sdim break; 546193323Sed } 547193323Sed case Instruction::SRem: 548193323Sed if (ConstantInt *Rem = dyn_cast<ConstantInt>(I->getOperand(1))) { 549203954Srdivacky APInt RA = Rem->getValue().abs(); 550203954Srdivacky if (RA.isPowerOf2()) { 551203954Srdivacky APInt LowBits = RA - 1; 552235633Sdim ComputeMaskedBits(I->getOperand(0), KnownZero2, KnownOne2, TD, Depth+1); 553193323Sed 554203954Srdivacky // The low bits of the first operand are unchanged by the srem. 555203954Srdivacky KnownZero = KnownZero2 & LowBits; 556203954Srdivacky KnownOne = KnownOne2 & LowBits; 557203954Srdivacky 558203954Srdivacky // If the first operand is non-negative or has all low bits zero, then 559203954Srdivacky // the upper bits are all zero. 560193323Sed if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits)) 561203954Srdivacky KnownZero |= ~LowBits; 562193323Sed 563203954Srdivacky // If the first operand is negative and not all low bits are zero, then 564203954Srdivacky // the upper bits are all one. 565203954Srdivacky if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0)) 566203954Srdivacky KnownOne |= ~LowBits; 567193323Sed 568252723Sdim assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 569193323Sed } 570193323Sed } 571221345Sdim 572221345Sdim // The sign bit is the LHS's sign bit, except when the result of the 573221345Sdim // remainder is zero. 574235633Sdim if (KnownZero.isNonNegative()) { 575221345Sdim APInt LHSKnownZero(BitWidth, 0), LHSKnownOne(BitWidth, 0); 576235633Sdim ComputeMaskedBits(I->getOperand(0), LHSKnownZero, LHSKnownOne, TD, 577221345Sdim Depth+1); 578221345Sdim // If it's known zero, our sign bit is also zero. 579221345Sdim if (LHSKnownZero.isNegative()) 580235633Sdim KnownZero.setBit(BitWidth - 1); 581221345Sdim } 582221345Sdim 583193323Sed break; 584193323Sed case Instruction::URem: { 585193323Sed if (ConstantInt *Rem = dyn_cast<ConstantInt>(I->getOperand(1))) { 586193323Sed APInt RA = Rem->getValue(); 587193323Sed if (RA.isPowerOf2()) { 588193323Sed APInt LowBits = (RA - 1); 589235633Sdim ComputeMaskedBits(I->getOperand(0), KnownZero, KnownOne, TD, 590193323Sed Depth+1); 591199989Srdivacky assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 592235633Sdim KnownZero |= ~LowBits; 593235633Sdim KnownOne &= LowBits; 594193323Sed break; 595193323Sed } 596193323Sed } 597193323Sed 598193323Sed // Since the result is less than or equal to either operand, any leading 599193323Sed // zero bits in either operand must also exist in the result. 600235633Sdim ComputeMaskedBits(I->getOperand(0), KnownZero, KnownOne, TD, Depth+1); 601235633Sdim ComputeMaskedBits(I->getOperand(1), KnownZero2, KnownOne2, TD, Depth+1); 602193323Sed 603193323Sed unsigned Leaders = std::max(KnownZero.countLeadingOnes(), 604193323Sed KnownZero2.countLeadingOnes()); 605218893Sdim KnownOne.clearAllBits(); 606235633Sdim KnownZero = APInt::getHighBitsSet(BitWidth, Leaders); 607193323Sed break; 608193323Sed } 609193323Sed 610198396Srdivacky case Instruction::Alloca: { 611198892Srdivacky AllocaInst *AI = cast<AllocaInst>(V); 612193323Sed unsigned Align = AI->getAlignment(); 613198396Srdivacky if (Align == 0 && TD) 614198396Srdivacky Align = TD->getABITypeAlignment(AI->getType()->getElementType()); 615252723Sdim 616193323Sed if (Align > 0) 617263509Sdim KnownZero = APInt::getLowBitsSet(BitWidth, countTrailingZeros(Align)); 618193323Sed break; 619193323Sed } 620193323Sed case Instruction::GetElementPtr: { 621193323Sed // Analyze all of the subscripts of this getelementptr instruction 622193323Sed // to determine if we can prove known low zero bits. 623193323Sed APInt LocalKnownZero(BitWidth, 0), LocalKnownOne(BitWidth, 0); 624235633Sdim ComputeMaskedBits(I->getOperand(0), LocalKnownZero, LocalKnownOne, TD, 625235633Sdim Depth+1); 626193323Sed unsigned TrailZ = LocalKnownZero.countTrailingOnes(); 627193323Sed 628193323Sed gep_type_iterator GTI = gep_type_begin(I); 629193323Sed for (unsigned i = 1, e = I->getNumOperands(); i != e; ++i, ++GTI) { 630193323Sed Value *Index = I->getOperand(i); 631226890Sdim if (StructType *STy = dyn_cast<StructType>(*GTI)) { 632193323Sed // Handle struct member offset arithmetic. 633263509Sdim if (!TD) 634263509Sdim return; 635263509Sdim 636263509Sdim // Handle case when index is vector zeroinitializer 637263509Sdim Constant *CIndex = cast<Constant>(Index); 638263509Sdim if (CIndex->isZeroValue()) 639263509Sdim continue; 640263509Sdim 641263509Sdim if (CIndex->getType()->isVectorTy()) 642263509Sdim Index = CIndex->getSplatValue(); 643263509Sdim 644263509Sdim unsigned Idx = cast<ConstantInt>(Index)->getZExtValue(); 645193323Sed const StructLayout *SL = TD->getStructLayout(STy); 646193323Sed uint64_t Offset = SL->getElementOffset(Idx); 647263509Sdim TrailZ = std::min<unsigned>(TrailZ, 648263509Sdim countTrailingZeros(Offset)); 649193323Sed } else { 650193323Sed // Handle array index arithmetic. 651226890Sdim Type *IndexedTy = GTI.getIndexedType(); 652193323Sed if (!IndexedTy->isSized()) return; 653194612Sed unsigned GEPOpiBits = Index->getType()->getScalarSizeInBits(); 654193323Sed uint64_t TypeSize = TD ? TD->getTypeAllocSize(IndexedTy) : 1; 655193323Sed LocalKnownZero = LocalKnownOne = APInt(GEPOpiBits, 0); 656235633Sdim ComputeMaskedBits(Index, LocalKnownZero, LocalKnownOne, TD, Depth+1); 657193323Sed TrailZ = std::min(TrailZ, 658263509Sdim unsigned(countTrailingZeros(TypeSize) + 659193323Sed LocalKnownZero.countTrailingOnes())); 660193323Sed } 661193323Sed } 662252723Sdim 663235633Sdim KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ); 664193323Sed break; 665193323Sed } 666193323Sed case Instruction::PHI: { 667193323Sed PHINode *P = cast<PHINode>(I); 668193323Sed // Handle the case of a simple two-predecessor recurrence PHI. 669193323Sed // There's a lot more that could theoretically be done here, but 670193323Sed // this is sufficient to catch some interesting cases. 671193323Sed if (P->getNumIncomingValues() == 2) { 672193323Sed for (unsigned i = 0; i != 2; ++i) { 673193323Sed Value *L = P->getIncomingValue(i); 674193323Sed Value *R = P->getIncomingValue(!i); 675198090Srdivacky Operator *LU = dyn_cast<Operator>(L); 676193323Sed if (!LU) 677193323Sed continue; 678198090Srdivacky unsigned Opcode = LU->getOpcode(); 679193323Sed // Check for operations that have the property that if 680193323Sed // both their operands have low zero bits, the result 681193323Sed // will have low zero bits. 682193323Sed if (Opcode == Instruction::Add || 683193323Sed Opcode == Instruction::Sub || 684193323Sed Opcode == Instruction::And || 685193323Sed Opcode == Instruction::Or || 686193323Sed Opcode == Instruction::Mul) { 687193323Sed Value *LL = LU->getOperand(0); 688193323Sed Value *LR = LU->getOperand(1); 689193323Sed // Find a recurrence. 690193323Sed if (LL == I) 691193323Sed L = LR; 692193323Sed else if (LR == I) 693193323Sed L = LL; 694193323Sed else 695193323Sed break; 696193323Sed // Ok, we have a PHI of the form L op= R. Check for low 697193323Sed // zero bits. 698235633Sdim ComputeMaskedBits(R, KnownZero2, KnownOne2, TD, Depth+1); 699193323Sed 700193323Sed // We need to take the minimum number of known bits 701193323Sed APInt KnownZero3(KnownZero), KnownOne3(KnownOne); 702235633Sdim ComputeMaskedBits(L, KnownZero3, KnownOne3, TD, Depth+1); 703193323Sed 704235633Sdim KnownZero = APInt::getLowBitsSet(BitWidth, 705193323Sed std::min(KnownZero2.countTrailingOnes(), 706193323Sed KnownZero3.countTrailingOnes())); 707193323Sed break; 708193323Sed } 709193323Sed } 710193323Sed } 711193323Sed 712218893Sdim // Unreachable blocks may have zero-operand PHI nodes. 713218893Sdim if (P->getNumIncomingValues() == 0) 714218893Sdim return; 715218893Sdim 716193323Sed // Otherwise take the unions of the known bit sets of the operands, 717193323Sed // taking conservative care to avoid excessive recursion. 718193323Sed if (Depth < MaxDepth - 1 && !KnownZero && !KnownOne) { 719221345Sdim // Skip if every incoming value references to ourself. 720245431Sdim if (dyn_cast_or_null<UndefValue>(P->hasConstantValue())) 721221345Sdim break; 722221345Sdim 723193323Sed KnownZero = APInt::getAllOnesValue(BitWidth); 724193323Sed KnownOne = APInt::getAllOnesValue(BitWidth); 725193323Sed for (unsigned i = 0, e = P->getNumIncomingValues(); i != e; ++i) { 726193323Sed // Skip direct self references. 727193323Sed if (P->getIncomingValue(i) == P) continue; 728193323Sed 729193323Sed KnownZero2 = APInt(BitWidth, 0); 730193323Sed KnownOne2 = APInt(BitWidth, 0); 731193323Sed // Recurse, but cap the recursion to one level, because we don't 732193323Sed // want to waste time spinning around in loops. 733235633Sdim ComputeMaskedBits(P->getIncomingValue(i), KnownZero2, KnownOne2, TD, 734235633Sdim MaxDepth-1); 735193323Sed KnownZero &= KnownZero2; 736193323Sed KnownOne &= KnownOne2; 737193323Sed // If all bits have been ruled out, there's no need to check 738193323Sed // more operands. 739193323Sed if (!KnownZero && !KnownOne) 740193323Sed break; 741193323Sed } 742193323Sed } 743193323Sed break; 744193323Sed } 745193323Sed case Instruction::Call: 746193323Sed if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { 747193323Sed switch (II->getIntrinsicID()) { 748193323Sed default: break; 749193323Sed case Intrinsic::ctlz: 750193323Sed case Intrinsic::cttz: { 751193323Sed unsigned LowBits = Log2_32(BitWidth)+1; 752235633Sdim // If this call is undefined for 0, the result will be less than 2^n. 753235633Sdim if (II->getArgOperand(1) == ConstantInt::getTrue(II->getContext())) 754235633Sdim LowBits -= 1; 755193323Sed KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits); 756193323Sed break; 757193323Sed } 758235633Sdim case Intrinsic::ctpop: { 759235633Sdim unsigned LowBits = Log2_32(BitWidth)+1; 760235633Sdim KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits); 761235633Sdim break; 762235633Sdim } 763223017Sdim case Intrinsic::x86_sse42_crc32_64_64: 764223017Sdim KnownZero = APInt::getHighBitsSet(64, 32); 765223017Sdim break; 766193323Sed } 767193323Sed } 768193323Sed break; 769235633Sdim case Instruction::ExtractValue: 770235633Sdim if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I->getOperand(0))) { 771235633Sdim ExtractValueInst *EVI = cast<ExtractValueInst>(I); 772235633Sdim if (EVI->getNumIndices() != 1) break; 773235633Sdim if (EVI->getIndices()[0] == 0) { 774235633Sdim switch (II->getIntrinsicID()) { 775235633Sdim default: break; 776235633Sdim case Intrinsic::uadd_with_overflow: 777235633Sdim case Intrinsic::sadd_with_overflow: 778235633Sdim ComputeMaskedBitsAddSub(true, II->getArgOperand(0), 779235633Sdim II->getArgOperand(1), false, KnownZero, 780235633Sdim KnownOne, KnownZero2, KnownOne2, TD, Depth); 781235633Sdim break; 782235633Sdim case Intrinsic::usub_with_overflow: 783235633Sdim case Intrinsic::ssub_with_overflow: 784235633Sdim ComputeMaskedBitsAddSub(false, II->getArgOperand(0), 785235633Sdim II->getArgOperand(1), false, KnownZero, 786235633Sdim KnownOne, KnownZero2, KnownOne2, TD, Depth); 787235633Sdim break; 788235633Sdim case Intrinsic::umul_with_overflow: 789235633Sdim case Intrinsic::smul_with_overflow: 790235633Sdim ComputeMaskedBitsMul(II->getArgOperand(0), II->getArgOperand(1), 791235633Sdim false, KnownZero, KnownOne, 792235633Sdim KnownZero2, KnownOne2, TD, Depth); 793235633Sdim break; 794235633Sdim } 795235633Sdim } 796235633Sdim } 797193323Sed } 798193323Sed} 799193323Sed 800218893Sdim/// ComputeSignBit - Determine whether the sign bit is known to be zero or 801218893Sdim/// one. Convenience wrapper around ComputeMaskedBits. 802218893Sdimvoid llvm::ComputeSignBit(Value *V, bool &KnownZero, bool &KnownOne, 803245431Sdim const DataLayout *TD, unsigned Depth) { 804218893Sdim unsigned BitWidth = getBitWidth(V->getType(), TD); 805218893Sdim if (!BitWidth) { 806218893Sdim KnownZero = false; 807218893Sdim KnownOne = false; 808218893Sdim return; 809218893Sdim } 810218893Sdim APInt ZeroBits(BitWidth, 0); 811218893Sdim APInt OneBits(BitWidth, 0); 812235633Sdim ComputeMaskedBits(V, ZeroBits, OneBits, TD, Depth); 813218893Sdim KnownOne = OneBits[BitWidth - 1]; 814218893Sdim KnownZero = ZeroBits[BitWidth - 1]; 815218893Sdim} 816218893Sdim 817252723Sdim/// isKnownToBeAPowerOfTwo - Return true if the given value is known to have exactly one 818218893Sdim/// bit set when defined. For vectors return true if every element is known to 819218893Sdim/// be a power of two when defined. Supports values with integer or pointer 820218893Sdim/// types and vectors of integers. 821252723Sdimbool llvm::isKnownToBeAPowerOfTwo(Value *V, bool OrZero, unsigned Depth) { 822235633Sdim if (Constant *C = dyn_cast<Constant>(V)) { 823235633Sdim if (C->isNullValue()) 824235633Sdim return OrZero; 825235633Sdim if (ConstantInt *CI = dyn_cast<ConstantInt>(C)) 826235633Sdim return CI->getValue().isPowerOf2(); 827235633Sdim // TODO: Handle vector constants. 828235633Sdim } 829218893Sdim 830218893Sdim // 1 << X is clearly a power of two if the one is not shifted off the end. If 831218893Sdim // it is shifted off the end then the result is undefined. 832218893Sdim if (match(V, m_Shl(m_One(), m_Value()))) 833218893Sdim return true; 834218893Sdim 835218893Sdim // (signbit) >>l X is clearly a power of two if the one is not shifted off the 836218893Sdim // bottom. If it is shifted off the bottom then the result is undefined. 837218893Sdim if (match(V, m_LShr(m_SignBit(), m_Value()))) 838218893Sdim return true; 839218893Sdim 840218893Sdim // The remaining tests are all recursive, so bail out if we hit the limit. 841218893Sdim if (Depth++ == MaxDepth) 842218893Sdim return false; 843218893Sdim 844235633Sdim Value *X = 0, *Y = 0; 845235633Sdim // A shift of a power of two is a power of two or zero. 846235633Sdim if (OrZero && (match(V, m_Shl(m_Value(X), m_Value())) || 847235633Sdim match(V, m_Shr(m_Value(X), m_Value())))) 848252723Sdim return isKnownToBeAPowerOfTwo(X, /*OrZero*/true, Depth); 849235633Sdim 850218893Sdim if (ZExtInst *ZI = dyn_cast<ZExtInst>(V)) 851252723Sdim return isKnownToBeAPowerOfTwo(ZI->getOperand(0), OrZero, Depth); 852218893Sdim 853218893Sdim if (SelectInst *SI = dyn_cast<SelectInst>(V)) 854252723Sdim return isKnownToBeAPowerOfTwo(SI->getTrueValue(), OrZero, Depth) && 855252723Sdim isKnownToBeAPowerOfTwo(SI->getFalseValue(), OrZero, Depth); 856218893Sdim 857235633Sdim if (OrZero && match(V, m_And(m_Value(X), m_Value(Y)))) { 858235633Sdim // A power of two and'd with anything is a power of two or zero. 859252723Sdim if (isKnownToBeAPowerOfTwo(X, /*OrZero*/true, Depth) || 860252723Sdim isKnownToBeAPowerOfTwo(Y, /*OrZero*/true, Depth)) 861235633Sdim return true; 862235633Sdim // X & (-X) is always a power of two or zero. 863235633Sdim if (match(X, m_Neg(m_Specific(Y))) || match(Y, m_Neg(m_Specific(X)))) 864235633Sdim return true; 865235633Sdim return false; 866235633Sdim } 867235633Sdim 868263509Sdim // Adding a power-of-two or zero to the same power-of-two or zero yields 869263509Sdim // either the original power-of-two, a larger power-of-two or zero. 870263509Sdim if (match(V, m_Add(m_Value(X), m_Value(Y)))) { 871263509Sdim OverflowingBinaryOperator *VOBO = cast<OverflowingBinaryOperator>(V); 872263509Sdim if (OrZero || VOBO->hasNoUnsignedWrap() || VOBO->hasNoSignedWrap()) { 873263509Sdim if (match(X, m_And(m_Specific(Y), m_Value())) || 874263509Sdim match(X, m_And(m_Value(), m_Specific(Y)))) 875263509Sdim if (isKnownToBeAPowerOfTwo(Y, OrZero, Depth)) 876263509Sdim return true; 877263509Sdim if (match(Y, m_And(m_Specific(X), m_Value())) || 878263509Sdim match(Y, m_And(m_Value(), m_Specific(X)))) 879263509Sdim if (isKnownToBeAPowerOfTwo(X, OrZero, Depth)) 880263509Sdim return true; 881263509Sdim 882263509Sdim unsigned BitWidth = V->getType()->getScalarSizeInBits(); 883263509Sdim APInt LHSZeroBits(BitWidth, 0), LHSOneBits(BitWidth, 0); 884263509Sdim ComputeMaskedBits(X, LHSZeroBits, LHSOneBits, 0, Depth); 885263509Sdim 886263509Sdim APInt RHSZeroBits(BitWidth, 0), RHSOneBits(BitWidth, 0); 887263509Sdim ComputeMaskedBits(Y, RHSZeroBits, RHSOneBits, 0, Depth); 888263509Sdim // If i8 V is a power of two or zero: 889263509Sdim // ZeroBits: 1 1 1 0 1 1 1 1 890263509Sdim // ~ZeroBits: 0 0 0 1 0 0 0 0 891263509Sdim if ((~(LHSZeroBits & RHSZeroBits)).isPowerOf2()) 892263509Sdim // If OrZero isn't set, we cannot give back a zero result. 893263509Sdim // Make sure either the LHS or RHS has a bit set. 894263509Sdim if (OrZero || RHSOneBits.getBoolValue() || LHSOneBits.getBoolValue()) 895263509Sdim return true; 896263509Sdim } 897263509Sdim } 898263509Sdim 899221345Sdim // An exact divide or right shift can only shift off zero bits, so the result 900221345Sdim // is a power of two only if the first operand is a power of two and not 901221345Sdim // copying a sign bit (sdiv int_min, 2). 902235633Sdim if (match(V, m_Exact(m_LShr(m_Value(), m_Value()))) || 903235633Sdim match(V, m_Exact(m_UDiv(m_Value(), m_Value())))) { 904252723Sdim return isKnownToBeAPowerOfTwo(cast<Operator>(V)->getOperand(0), OrZero, Depth); 905221345Sdim } 906221345Sdim 907218893Sdim return false; 908218893Sdim} 909218893Sdim 910252723Sdim/// \brief Test whether a GEP's result is known to be non-null. 911252723Sdim/// 912252723Sdim/// Uses properties inherent in a GEP to try to determine whether it is known 913252723Sdim/// to be non-null. 914252723Sdim/// 915252723Sdim/// Currently this routine does not support vector GEPs. 916252723Sdimstatic bool isGEPKnownNonNull(GEPOperator *GEP, const DataLayout *DL, 917252723Sdim unsigned Depth) { 918252723Sdim if (!GEP->isInBounds() || GEP->getPointerAddressSpace() != 0) 919252723Sdim return false; 920252723Sdim 921252723Sdim // FIXME: Support vector-GEPs. 922252723Sdim assert(GEP->getType()->isPointerTy() && "We only support plain pointer GEP"); 923252723Sdim 924252723Sdim // If the base pointer is non-null, we cannot walk to a null address with an 925252723Sdim // inbounds GEP in address space zero. 926252723Sdim if (isKnownNonZero(GEP->getPointerOperand(), DL, Depth)) 927252723Sdim return true; 928252723Sdim 929252723Sdim // Past this, if we don't have DataLayout, we can't do much. 930252723Sdim if (!DL) 931252723Sdim return false; 932252723Sdim 933252723Sdim // Walk the GEP operands and see if any operand introduces a non-zero offset. 934252723Sdim // If so, then the GEP cannot produce a null pointer, as doing so would 935252723Sdim // inherently violate the inbounds contract within address space zero. 936252723Sdim for (gep_type_iterator GTI = gep_type_begin(GEP), GTE = gep_type_end(GEP); 937252723Sdim GTI != GTE; ++GTI) { 938252723Sdim // Struct types are easy -- they must always be indexed by a constant. 939252723Sdim if (StructType *STy = dyn_cast<StructType>(*GTI)) { 940252723Sdim ConstantInt *OpC = cast<ConstantInt>(GTI.getOperand()); 941252723Sdim unsigned ElementIdx = OpC->getZExtValue(); 942252723Sdim const StructLayout *SL = DL->getStructLayout(STy); 943252723Sdim uint64_t ElementOffset = SL->getElementOffset(ElementIdx); 944252723Sdim if (ElementOffset > 0) 945252723Sdim return true; 946252723Sdim continue; 947252723Sdim } 948252723Sdim 949252723Sdim // If we have a zero-sized type, the index doesn't matter. Keep looping. 950252723Sdim if (DL->getTypeAllocSize(GTI.getIndexedType()) == 0) 951252723Sdim continue; 952252723Sdim 953252723Sdim // Fast path the constant operand case both for efficiency and so we don't 954252723Sdim // increment Depth when just zipping down an all-constant GEP. 955252723Sdim if (ConstantInt *OpC = dyn_cast<ConstantInt>(GTI.getOperand())) { 956252723Sdim if (!OpC->isZero()) 957252723Sdim return true; 958252723Sdim continue; 959252723Sdim } 960252723Sdim 961252723Sdim // We post-increment Depth here because while isKnownNonZero increments it 962252723Sdim // as well, when we pop back up that increment won't persist. We don't want 963252723Sdim // to recurse 10k times just because we have 10k GEP operands. We don't 964252723Sdim // bail completely out because we want to handle constant GEPs regardless 965252723Sdim // of depth. 966252723Sdim if (Depth++ >= MaxDepth) 967252723Sdim continue; 968252723Sdim 969252723Sdim if (isKnownNonZero(GTI.getOperand(), DL, Depth)) 970252723Sdim return true; 971252723Sdim } 972252723Sdim 973252723Sdim return false; 974252723Sdim} 975252723Sdim 976218893Sdim/// isKnownNonZero - Return true if the given value is known to be non-zero 977218893Sdim/// when defined. For vectors return true if every element is known to be 978218893Sdim/// non-zero when defined. Supports values with integer or pointer type and 979218893Sdim/// vectors of integers. 980245431Sdimbool llvm::isKnownNonZero(Value *V, const DataLayout *TD, unsigned Depth) { 981218893Sdim if (Constant *C = dyn_cast<Constant>(V)) { 982218893Sdim if (C->isNullValue()) 983218893Sdim return false; 984218893Sdim if (isa<ConstantInt>(C)) 985218893Sdim // Must be non-zero due to null test above. 986218893Sdim return true; 987218893Sdim // TODO: Handle vectors 988218893Sdim return false; 989218893Sdim } 990218893Sdim 991218893Sdim // The remaining tests are all recursive, so bail out if we hit the limit. 992235633Sdim if (Depth++ >= MaxDepth) 993218893Sdim return false; 994218893Sdim 995252723Sdim // Check for pointer simplifications. 996252723Sdim if (V->getType()->isPointerTy()) { 997252723Sdim if (isKnownNonNull(V)) 998252723Sdim return true; 999252723Sdim if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) 1000252723Sdim if (isGEPKnownNonNull(GEP, TD, Depth)) 1001252723Sdim return true; 1002252723Sdim } 1003218893Sdim 1004252723Sdim unsigned BitWidth = getBitWidth(V->getType()->getScalarType(), TD); 1005252723Sdim 1006218893Sdim // X | Y != 0 if X != 0 or Y != 0. 1007218893Sdim Value *X = 0, *Y = 0; 1008218893Sdim if (match(V, m_Or(m_Value(X), m_Value(Y)))) 1009218893Sdim return isKnownNonZero(X, TD, Depth) || isKnownNonZero(Y, TD, Depth); 1010218893Sdim 1011218893Sdim // ext X != 0 if X != 0. 1012218893Sdim if (isa<SExtInst>(V) || isa<ZExtInst>(V)) 1013218893Sdim return isKnownNonZero(cast<Instruction>(V)->getOperand(0), TD, Depth); 1014218893Sdim 1015218893Sdim // shl X, Y != 0 if X is odd. Note that the value of the shift is undefined 1016218893Sdim // if the lowest bit is shifted off the end. 1017218893Sdim if (BitWidth && match(V, m_Shl(m_Value(X), m_Value(Y)))) { 1018221345Sdim // shl nuw can't remove any non-zero bits. 1019235633Sdim OverflowingBinaryOperator *BO = cast<OverflowingBinaryOperator>(V); 1020221345Sdim if (BO->hasNoUnsignedWrap()) 1021221345Sdim return isKnownNonZero(X, TD, Depth); 1022221345Sdim 1023218893Sdim APInt KnownZero(BitWidth, 0); 1024218893Sdim APInt KnownOne(BitWidth, 0); 1025235633Sdim ComputeMaskedBits(X, KnownZero, KnownOne, TD, Depth); 1026218893Sdim if (KnownOne[0]) 1027218893Sdim return true; 1028218893Sdim } 1029218893Sdim // shr X, Y != 0 if X is negative. Note that the value of the shift is not 1030218893Sdim // defined if the sign bit is shifted off the end. 1031218893Sdim else if (match(V, m_Shr(m_Value(X), m_Value(Y)))) { 1032221345Sdim // shr exact can only shift out zero bits. 1033235633Sdim PossiblyExactOperator *BO = cast<PossiblyExactOperator>(V); 1034221345Sdim if (BO->isExact()) 1035221345Sdim return isKnownNonZero(X, TD, Depth); 1036221345Sdim 1037218893Sdim bool XKnownNonNegative, XKnownNegative; 1038218893Sdim ComputeSignBit(X, XKnownNonNegative, XKnownNegative, TD, Depth); 1039218893Sdim if (XKnownNegative) 1040218893Sdim return true; 1041218893Sdim } 1042221345Sdim // div exact can only produce a zero if the dividend is zero. 1043235633Sdim else if (match(V, m_Exact(m_IDiv(m_Value(X), m_Value())))) { 1044235633Sdim return isKnownNonZero(X, TD, Depth); 1045221345Sdim } 1046218893Sdim // X + Y. 1047218893Sdim else if (match(V, m_Add(m_Value(X), m_Value(Y)))) { 1048218893Sdim bool XKnownNonNegative, XKnownNegative; 1049218893Sdim bool YKnownNonNegative, YKnownNegative; 1050218893Sdim ComputeSignBit(X, XKnownNonNegative, XKnownNegative, TD, Depth); 1051218893Sdim ComputeSignBit(Y, YKnownNonNegative, YKnownNegative, TD, Depth); 1052218893Sdim 1053218893Sdim // If X and Y are both non-negative (as signed values) then their sum is not 1054218893Sdim // zero unless both X and Y are zero. 1055218893Sdim if (XKnownNonNegative && YKnownNonNegative) 1056218893Sdim if (isKnownNonZero(X, TD, Depth) || isKnownNonZero(Y, TD, Depth)) 1057218893Sdim return true; 1058218893Sdim 1059218893Sdim // If X and Y are both negative (as signed values) then their sum is not 1060218893Sdim // zero unless both X and Y equal INT_MIN. 1061218893Sdim if (BitWidth && XKnownNegative && YKnownNegative) { 1062218893Sdim APInt KnownZero(BitWidth, 0); 1063218893Sdim APInt KnownOne(BitWidth, 0); 1064218893Sdim APInt Mask = APInt::getSignedMaxValue(BitWidth); 1065218893Sdim // The sign bit of X is set. If some other bit is set then X is not equal 1066218893Sdim // to INT_MIN. 1067235633Sdim ComputeMaskedBits(X, KnownZero, KnownOne, TD, Depth); 1068218893Sdim if ((KnownOne & Mask) != 0) 1069218893Sdim return true; 1070218893Sdim // The sign bit of Y is set. If some other bit is set then Y is not equal 1071218893Sdim // to INT_MIN. 1072235633Sdim ComputeMaskedBits(Y, KnownZero, KnownOne, TD, Depth); 1073218893Sdim if ((KnownOne & Mask) != 0) 1074218893Sdim return true; 1075218893Sdim } 1076218893Sdim 1077218893Sdim // The sum of a non-negative number and a power of two is not zero. 1078252723Sdim if (XKnownNonNegative && isKnownToBeAPowerOfTwo(Y, /*OrZero*/false, Depth)) 1079218893Sdim return true; 1080252723Sdim if (YKnownNonNegative && isKnownToBeAPowerOfTwo(X, /*OrZero*/false, Depth)) 1081218893Sdim return true; 1082218893Sdim } 1083235633Sdim // X * Y. 1084235633Sdim else if (match(V, m_Mul(m_Value(X), m_Value(Y)))) { 1085235633Sdim OverflowingBinaryOperator *BO = cast<OverflowingBinaryOperator>(V); 1086235633Sdim // If X and Y are non-zero then so is X * Y as long as the multiplication 1087235633Sdim // does not overflow. 1088235633Sdim if ((BO->hasNoSignedWrap() || BO->hasNoUnsignedWrap()) && 1089235633Sdim isKnownNonZero(X, TD, Depth) && isKnownNonZero(Y, TD, Depth)) 1090235633Sdim return true; 1091235633Sdim } 1092218893Sdim // (C ? X : Y) != 0 if X != 0 and Y != 0. 1093218893Sdim else if (SelectInst *SI = dyn_cast<SelectInst>(V)) { 1094218893Sdim if (isKnownNonZero(SI->getTrueValue(), TD, Depth) && 1095218893Sdim isKnownNonZero(SI->getFalseValue(), TD, Depth)) 1096218893Sdim return true; 1097218893Sdim } 1098218893Sdim 1099218893Sdim if (!BitWidth) return false; 1100218893Sdim APInt KnownZero(BitWidth, 0); 1101218893Sdim APInt KnownOne(BitWidth, 0); 1102235633Sdim ComputeMaskedBits(V, KnownZero, KnownOne, TD, Depth); 1103218893Sdim return KnownOne != 0; 1104218893Sdim} 1105218893Sdim 1106193323Sed/// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use 1107193323Sed/// this predicate to simplify operations downstream. Mask is known to be zero 1108193323Sed/// for bits that V cannot have. 1109198090Srdivacky/// 1110198090Srdivacky/// This function is defined on values with integer type, values with pointer 1111198090Srdivacky/// type (but only if TD is non-null), and vectors of integers. In the case 1112198090Srdivacky/// where V is a vector, the mask, known zero, and known one values are the 1113198090Srdivacky/// same width as the vector element, and the bit is set only if it is true 1114198090Srdivacky/// for all of the elements in the vector. 1115193323Sedbool llvm::MaskedValueIsZero(Value *V, const APInt &Mask, 1116245431Sdim const DataLayout *TD, unsigned Depth) { 1117193323Sed APInt KnownZero(Mask.getBitWidth(), 0), KnownOne(Mask.getBitWidth(), 0); 1118235633Sdim ComputeMaskedBits(V, KnownZero, KnownOne, TD, Depth); 1119252723Sdim assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 1120193323Sed return (KnownZero & Mask) == Mask; 1121193323Sed} 1122193323Sed 1123193323Sed 1124193323Sed 1125193323Sed/// ComputeNumSignBits - Return the number of times the sign bit of the 1126193323Sed/// register is replicated into the other bits. We know that at least 1 bit 1127193323Sed/// is always equal to the sign bit (itself), but other cases can give us 1128193323Sed/// information. For example, immediately after an "ashr X, 2", we know that 1129193323Sed/// the top 3 bits are all equal to each other, so we return 3. 1130193323Sed/// 1131193323Sed/// 'Op' must have a scalar integer type. 1132193323Sed/// 1133245431Sdimunsigned llvm::ComputeNumSignBits(Value *V, const DataLayout *TD, 1134198090Srdivacky unsigned Depth) { 1135203954Srdivacky assert((TD || V->getType()->isIntOrIntVectorTy()) && 1136245431Sdim "ComputeNumSignBits requires a DataLayout object to operate " 1137194710Sed "on non-integer values!"); 1138226890Sdim Type *Ty = V->getType(); 1139194710Sed unsigned TyBits = TD ? TD->getTypeSizeInBits(V->getType()->getScalarType()) : 1140194710Sed Ty->getScalarSizeInBits(); 1141193323Sed unsigned Tmp, Tmp2; 1142193323Sed unsigned FirstAnswer = 1; 1143193323Sed 1144193323Sed // Note that ConstantInt is handled by the general ComputeMaskedBits case 1145193323Sed // below. 1146193323Sed 1147193323Sed if (Depth == 6) 1148193323Sed return 1; // Limit search depth. 1149252723Sdim 1150198090Srdivacky Operator *U = dyn_cast<Operator>(V); 1151198090Srdivacky switch (Operator::getOpcode(V)) { 1152193323Sed default: break; 1153193323Sed case Instruction::SExt: 1154200581Srdivacky Tmp = TyBits - U->getOperand(0)->getType()->getScalarSizeInBits(); 1155193323Sed return ComputeNumSignBits(U->getOperand(0), TD, Depth+1) + Tmp; 1156252723Sdim 1157235633Sdim case Instruction::AShr: { 1158193323Sed Tmp = ComputeNumSignBits(U->getOperand(0), TD, Depth+1); 1159235633Sdim // ashr X, C -> adds C sign bits. Vectors too. 1160235633Sdim const APInt *ShAmt; 1161235633Sdim if (match(U->getOperand(1), m_APInt(ShAmt))) { 1162235633Sdim Tmp += ShAmt->getZExtValue(); 1163193323Sed if (Tmp > TyBits) Tmp = TyBits; 1164193323Sed } 1165193323Sed return Tmp; 1166235633Sdim } 1167235633Sdim case Instruction::Shl: { 1168235633Sdim const APInt *ShAmt; 1169235633Sdim if (match(U->getOperand(1), m_APInt(ShAmt))) { 1170193323Sed // shl destroys sign bits. 1171193323Sed Tmp = ComputeNumSignBits(U->getOperand(0), TD, Depth+1); 1172235633Sdim Tmp2 = ShAmt->getZExtValue(); 1173235633Sdim if (Tmp2 >= TyBits || // Bad shift. 1174235633Sdim Tmp2 >= Tmp) break; // Shifted all sign bits out. 1175235633Sdim return Tmp - Tmp2; 1176193323Sed } 1177193323Sed break; 1178235633Sdim } 1179193323Sed case Instruction::And: 1180193323Sed case Instruction::Or: 1181193323Sed case Instruction::Xor: // NOT is handled here. 1182193323Sed // Logical binary ops preserve the number of sign bits at the worst. 1183193323Sed Tmp = ComputeNumSignBits(U->getOperand(0), TD, Depth+1); 1184193323Sed if (Tmp != 1) { 1185193323Sed Tmp2 = ComputeNumSignBits(U->getOperand(1), TD, Depth+1); 1186193323Sed FirstAnswer = std::min(Tmp, Tmp2); 1187193323Sed // We computed what we know about the sign bits as our first 1188193323Sed // answer. Now proceed to the generic code that uses 1189193323Sed // ComputeMaskedBits, and pick whichever answer is better. 1190193323Sed } 1191193323Sed break; 1192193323Sed 1193193323Sed case Instruction::Select: 1194193323Sed Tmp = ComputeNumSignBits(U->getOperand(1), TD, Depth+1); 1195193323Sed if (Tmp == 1) return 1; // Early out. 1196193323Sed Tmp2 = ComputeNumSignBits(U->getOperand(2), TD, Depth+1); 1197193323Sed return std::min(Tmp, Tmp2); 1198252723Sdim 1199193323Sed case Instruction::Add: 1200193323Sed // Add can have at most one carry bit. Thus we know that the output 1201193323Sed // is, at worst, one more bit than the inputs. 1202193323Sed Tmp = ComputeNumSignBits(U->getOperand(0), TD, Depth+1); 1203193323Sed if (Tmp == 1) return 1; // Early out. 1204252723Sdim 1205193323Sed // Special case decrementing a value (ADD X, -1): 1206193323Sed if (ConstantInt *CRHS = dyn_cast<ConstantInt>(U->getOperand(1))) 1207193323Sed if (CRHS->isAllOnesValue()) { 1208193323Sed APInt KnownZero(TyBits, 0), KnownOne(TyBits, 0); 1209235633Sdim ComputeMaskedBits(U->getOperand(0), KnownZero, KnownOne, TD, Depth+1); 1210252723Sdim 1211193323Sed // If the input is known to be 0 or 1, the output is 0/-1, which is all 1212193323Sed // sign bits set. 1213235633Sdim if ((KnownZero | APInt(TyBits, 1)).isAllOnesValue()) 1214193323Sed return TyBits; 1215252723Sdim 1216193323Sed // If we are subtracting one from a positive number, there is no carry 1217193323Sed // out of the result. 1218193323Sed if (KnownZero.isNegative()) 1219193323Sed return Tmp; 1220193323Sed } 1221252723Sdim 1222193323Sed Tmp2 = ComputeNumSignBits(U->getOperand(1), TD, Depth+1); 1223193323Sed if (Tmp2 == 1) return 1; 1224202375Srdivacky return std::min(Tmp, Tmp2)-1; 1225252723Sdim 1226193323Sed case Instruction::Sub: 1227193323Sed Tmp2 = ComputeNumSignBits(U->getOperand(1), TD, Depth+1); 1228193323Sed if (Tmp2 == 1) return 1; 1229252723Sdim 1230193323Sed // Handle NEG. 1231193323Sed if (ConstantInt *CLHS = dyn_cast<ConstantInt>(U->getOperand(0))) 1232193323Sed if (CLHS->isNullValue()) { 1233193323Sed APInt KnownZero(TyBits, 0), KnownOne(TyBits, 0); 1234235633Sdim ComputeMaskedBits(U->getOperand(1), KnownZero, KnownOne, TD, Depth+1); 1235193323Sed // If the input is known to be 0 or 1, the output is 0/-1, which is all 1236193323Sed // sign bits set. 1237235633Sdim if ((KnownZero | APInt(TyBits, 1)).isAllOnesValue()) 1238193323Sed return TyBits; 1239252723Sdim 1240193323Sed // If the input is known to be positive (the sign bit is known clear), 1241193323Sed // the output of the NEG has the same number of sign bits as the input. 1242193323Sed if (KnownZero.isNegative()) 1243193323Sed return Tmp2; 1244252723Sdim 1245193323Sed // Otherwise, we treat this like a SUB. 1246193323Sed } 1247252723Sdim 1248193323Sed // Sub can have at most one carry bit. Thus we know that the output 1249193323Sed // is, at worst, one more bit than the inputs. 1250193323Sed Tmp = ComputeNumSignBits(U->getOperand(0), TD, Depth+1); 1251193323Sed if (Tmp == 1) return 1; // Early out. 1252202375Srdivacky return std::min(Tmp, Tmp2)-1; 1253252723Sdim 1254202375Srdivacky case Instruction::PHI: { 1255202375Srdivacky PHINode *PN = cast<PHINode>(U); 1256202375Srdivacky // Don't analyze large in-degree PHIs. 1257202375Srdivacky if (PN->getNumIncomingValues() > 4) break; 1258252723Sdim 1259202375Srdivacky // Take the minimum of all incoming values. This can't infinitely loop 1260202375Srdivacky // because of our depth threshold. 1261202375Srdivacky Tmp = ComputeNumSignBits(PN->getIncomingValue(0), TD, Depth+1); 1262202375Srdivacky for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i) { 1263202375Srdivacky if (Tmp == 1) return Tmp; 1264202375Srdivacky Tmp = std::min(Tmp, 1265205218Srdivacky ComputeNumSignBits(PN->getIncomingValue(i), TD, Depth+1)); 1266202375Srdivacky } 1267202375Srdivacky return Tmp; 1268202375Srdivacky } 1269202375Srdivacky 1270193323Sed case Instruction::Trunc: 1271193323Sed // FIXME: it's tricky to do anything useful for this, but it is an important 1272193323Sed // case for targets like X86. 1273193323Sed break; 1274193323Sed } 1275252723Sdim 1276193323Sed // Finally, if we can prove that the top bits of the result are 0's or 1's, 1277193323Sed // use this information. 1278193323Sed APInt KnownZero(TyBits, 0), KnownOne(TyBits, 0); 1279235633Sdim APInt Mask; 1280235633Sdim ComputeMaskedBits(V, KnownZero, KnownOne, TD, Depth); 1281252723Sdim 1282193323Sed if (KnownZero.isNegative()) { // sign bit is 0 1283193323Sed Mask = KnownZero; 1284193323Sed } else if (KnownOne.isNegative()) { // sign bit is 1; 1285193323Sed Mask = KnownOne; 1286193323Sed } else { 1287193323Sed // Nothing known. 1288193323Sed return FirstAnswer; 1289193323Sed } 1290252723Sdim 1291193323Sed // Okay, we know that the sign bit in Mask is set. Use CLZ to determine 1292193323Sed // the number of identical bits in the top of the input value. 1293193323Sed Mask = ~Mask; 1294193323Sed Mask <<= Mask.getBitWidth()-TyBits; 1295193323Sed // Return # leading zeros. We use 'min' here in case Val was zero before 1296193323Sed // shifting. We don't want to return '64' as for an i32 "0". 1297193323Sed return std::max(FirstAnswer, std::min(TyBits, Mask.countLeadingZeros())); 1298193323Sed} 1299193323Sed 1300199481Srdivacky/// ComputeMultiple - This function computes the integer multiple of Base that 1301199481Srdivacky/// equals V. If successful, it returns true and returns the multiple in 1302199481Srdivacky/// Multiple. If unsuccessful, it returns false. It looks 1303199481Srdivacky/// through SExt instructions only if LookThroughSExt is true. 1304199481Srdivackybool llvm::ComputeMultiple(Value *V, unsigned Base, Value *&Multiple, 1305199481Srdivacky bool LookThroughSExt, unsigned Depth) { 1306199481Srdivacky const unsigned MaxDepth = 6; 1307199481Srdivacky 1308199481Srdivacky assert(V && "No Value?"); 1309199481Srdivacky assert(Depth <= MaxDepth && "Limit Search Depth"); 1310203954Srdivacky assert(V->getType()->isIntegerTy() && "Not integer or pointer type!"); 1311199481Srdivacky 1312226890Sdim Type *T = V->getType(); 1313199481Srdivacky 1314199481Srdivacky ConstantInt *CI = dyn_cast<ConstantInt>(V); 1315199481Srdivacky 1316199481Srdivacky if (Base == 0) 1317199481Srdivacky return false; 1318252723Sdim 1319199481Srdivacky if (Base == 1) { 1320199481Srdivacky Multiple = V; 1321199481Srdivacky return true; 1322199481Srdivacky } 1323199481Srdivacky 1324199481Srdivacky ConstantExpr *CO = dyn_cast<ConstantExpr>(V); 1325199481Srdivacky Constant *BaseVal = ConstantInt::get(T, Base); 1326199481Srdivacky if (CO && CO == BaseVal) { 1327199481Srdivacky // Multiple is 1. 1328199481Srdivacky Multiple = ConstantInt::get(T, 1); 1329199481Srdivacky return true; 1330199481Srdivacky } 1331199481Srdivacky 1332199481Srdivacky if (CI && CI->getZExtValue() % Base == 0) { 1333199481Srdivacky Multiple = ConstantInt::get(T, CI->getZExtValue() / Base); 1334252723Sdim return true; 1335199481Srdivacky } 1336252723Sdim 1337199481Srdivacky if (Depth == MaxDepth) return false; // Limit search depth. 1338252723Sdim 1339199481Srdivacky Operator *I = dyn_cast<Operator>(V); 1340199481Srdivacky if (!I) return false; 1341199481Srdivacky 1342199481Srdivacky switch (I->getOpcode()) { 1343199481Srdivacky default: break; 1344199989Srdivacky case Instruction::SExt: 1345199481Srdivacky if (!LookThroughSExt) return false; 1346199481Srdivacky // otherwise fall through to ZExt 1347199989Srdivacky case Instruction::ZExt: 1348199481Srdivacky return ComputeMultiple(I->getOperand(0), Base, Multiple, 1349199481Srdivacky LookThroughSExt, Depth+1); 1350199481Srdivacky case Instruction::Shl: 1351199481Srdivacky case Instruction::Mul: { 1352199481Srdivacky Value *Op0 = I->getOperand(0); 1353199481Srdivacky Value *Op1 = I->getOperand(1); 1354199481Srdivacky 1355199481Srdivacky if (I->getOpcode() == Instruction::Shl) { 1356199481Srdivacky ConstantInt *Op1CI = dyn_cast<ConstantInt>(Op1); 1357199481Srdivacky if (!Op1CI) return false; 1358199481Srdivacky // Turn Op0 << Op1 into Op0 * 2^Op1 1359199481Srdivacky APInt Op1Int = Op1CI->getValue(); 1360199481Srdivacky uint64_t BitToSet = Op1Int.getLimitedValue(Op1Int.getBitWidth() - 1); 1361218893Sdim APInt API(Op1Int.getBitWidth(), 0); 1362218893Sdim API.setBit(BitToSet); 1363218893Sdim Op1 = ConstantInt::get(V->getContext(), API); 1364199481Srdivacky } 1365199481Srdivacky 1366199481Srdivacky Value *Mul0 = NULL; 1367212904Sdim if (ComputeMultiple(Op0, Base, Mul0, LookThroughSExt, Depth+1)) { 1368212904Sdim if (Constant *Op1C = dyn_cast<Constant>(Op1)) 1369212904Sdim if (Constant *MulC = dyn_cast<Constant>(Mul0)) { 1370252723Sdim if (Op1C->getType()->getPrimitiveSizeInBits() < 1371212904Sdim MulC->getType()->getPrimitiveSizeInBits()) 1372212904Sdim Op1C = ConstantExpr::getZExt(Op1C, MulC->getType()); 1373252723Sdim if (Op1C->getType()->getPrimitiveSizeInBits() > 1374212904Sdim MulC->getType()->getPrimitiveSizeInBits()) 1375212904Sdim MulC = ConstantExpr::getZExt(MulC, Op1C->getType()); 1376252723Sdim 1377212904Sdim // V == Base * (Mul0 * Op1), so return (Mul0 * Op1) 1378212904Sdim Multiple = ConstantExpr::getMul(MulC, Op1C); 1379212904Sdim return true; 1380212904Sdim } 1381199481Srdivacky 1382199481Srdivacky if (ConstantInt *Mul0CI = dyn_cast<ConstantInt>(Mul0)) 1383199481Srdivacky if (Mul0CI->getValue() == 1) { 1384199481Srdivacky // V == Base * Op1, so return Op1 1385199481Srdivacky Multiple = Op1; 1386199481Srdivacky return true; 1387199481Srdivacky } 1388199481Srdivacky } 1389199481Srdivacky 1390212904Sdim Value *Mul1 = NULL; 1391212904Sdim if (ComputeMultiple(Op1, Base, Mul1, LookThroughSExt, Depth+1)) { 1392212904Sdim if (Constant *Op0C = dyn_cast<Constant>(Op0)) 1393212904Sdim if (Constant *MulC = dyn_cast<Constant>(Mul1)) { 1394252723Sdim if (Op0C->getType()->getPrimitiveSizeInBits() < 1395212904Sdim MulC->getType()->getPrimitiveSizeInBits()) 1396212904Sdim Op0C = ConstantExpr::getZExt(Op0C, MulC->getType()); 1397252723Sdim if (Op0C->getType()->getPrimitiveSizeInBits() > 1398212904Sdim MulC->getType()->getPrimitiveSizeInBits()) 1399212904Sdim MulC = ConstantExpr::getZExt(MulC, Op0C->getType()); 1400252723Sdim 1401212904Sdim // V == Base * (Mul1 * Op0), so return (Mul1 * Op0) 1402212904Sdim Multiple = ConstantExpr::getMul(MulC, Op0C); 1403212904Sdim return true; 1404212904Sdim } 1405199481Srdivacky 1406199481Srdivacky if (ConstantInt *Mul1CI = dyn_cast<ConstantInt>(Mul1)) 1407199481Srdivacky if (Mul1CI->getValue() == 1) { 1408199481Srdivacky // V == Base * Op0, so return Op0 1409199481Srdivacky Multiple = Op0; 1410199481Srdivacky return true; 1411199481Srdivacky } 1412199481Srdivacky } 1413199481Srdivacky } 1414199481Srdivacky } 1415199481Srdivacky 1416199481Srdivacky // We could not determine if V is a multiple of Base. 1417199481Srdivacky return false; 1418199481Srdivacky} 1419199481Srdivacky 1420252723Sdim/// CannotBeNegativeZero - Return true if we can prove that the specified FP 1421193323Sed/// value is never equal to -0.0. 1422193323Sed/// 1423193323Sed/// NOTE: this function will need to be revisited when we support non-default 1424193323Sed/// rounding modes! 1425193323Sed/// 1426193323Sedbool llvm::CannotBeNegativeZero(const Value *V, unsigned Depth) { 1427193323Sed if (const ConstantFP *CFP = dyn_cast<ConstantFP>(V)) 1428193323Sed return !CFP->getValueAPF().isNegZero(); 1429252723Sdim 1430193323Sed if (Depth == 6) 1431193323Sed return 1; // Limit search depth. 1432193323Sed 1433198090Srdivacky const Operator *I = dyn_cast<Operator>(V); 1434193323Sed if (I == 0) return false; 1435252723Sdim 1436252723Sdim // Check if the nsz fast-math flag is set 1437252723Sdim if (const FPMathOperator *FPO = dyn_cast<FPMathOperator>(I)) 1438252723Sdim if (FPO->hasNoSignedZeros()) 1439252723Sdim return true; 1440252723Sdim 1441193323Sed // (add x, 0.0) is guaranteed to return +0.0, not -0.0. 1442252723Sdim if (I->getOpcode() == Instruction::FAdd) 1443252723Sdim if (ConstantFP *CFP = dyn_cast<ConstantFP>(I->getOperand(1))) 1444252723Sdim if (CFP->isNullValue()) 1445252723Sdim return true; 1446252723Sdim 1447193323Sed // sitofp and uitofp turn into +0.0 for zero. 1448193323Sed if (isa<SIToFPInst>(I) || isa<UIToFPInst>(I)) 1449193323Sed return true; 1450252723Sdim 1451193323Sed if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) 1452193323Sed // sqrt(-0.0) = -0.0, no other negative results are possible. 1453193323Sed if (II->getIntrinsicID() == Intrinsic::sqrt) 1454210299Sed return CannotBeNegativeZero(II->getArgOperand(0), Depth+1); 1455252723Sdim 1456193323Sed if (const CallInst *CI = dyn_cast<CallInst>(I)) 1457193323Sed if (const Function *F = CI->getCalledFunction()) { 1458193323Sed if (F->isDeclaration()) { 1459198090Srdivacky // abs(x) != -0.0 1460198090Srdivacky if (F->getName() == "abs") return true; 1461198090Srdivacky // fabs[lf](x) != -0.0 1462198090Srdivacky if (F->getName() == "fabs") return true; 1463198090Srdivacky if (F->getName() == "fabsf") return true; 1464198090Srdivacky if (F->getName() == "fabsl") return true; 1465198090Srdivacky if (F->getName() == "sqrt" || F->getName() == "sqrtf" || 1466198090Srdivacky F->getName() == "sqrtl") 1467210299Sed return CannotBeNegativeZero(CI->getArgOperand(0), Depth+1); 1468193323Sed } 1469193323Sed } 1470252723Sdim 1471193323Sed return false; 1472193323Sed} 1473193323Sed 1474218893Sdim/// isBytewiseValue - If the specified value can be set by repeating the same 1475218893Sdim/// byte in memory, return the i8 value that it is represented with. This is 1476218893Sdim/// true for all i8 values obviously, but is also true for i32 0, i32 -1, 1477218893Sdim/// i16 0xF0F0, double 0.0 etc. If the value can't be handled with a repeated 1478218893Sdim/// byte store (e.g. i16 0x1234), return null. 1479218893SdimValue *llvm::isBytewiseValue(Value *V) { 1480218893Sdim // All byte-wide stores are splatable, even of arbitrary variables. 1481218893Sdim if (V->getType()->isIntegerTy(8)) return V; 1482218893Sdim 1483218893Sdim // Handle 'null' ConstantArrayZero etc. 1484218893Sdim if (Constant *C = dyn_cast<Constant>(V)) 1485218893Sdim if (C->isNullValue()) 1486218893Sdim return Constant::getNullValue(Type::getInt8Ty(V->getContext())); 1487252723Sdim 1488218893Sdim // Constant float and double values can be handled as integer values if the 1489252723Sdim // corresponding integer value is "byteable". An important case is 0.0. 1490218893Sdim if (ConstantFP *CFP = dyn_cast<ConstantFP>(V)) { 1491218893Sdim if (CFP->getType()->isFloatTy()) 1492218893Sdim V = ConstantExpr::getBitCast(CFP, Type::getInt32Ty(V->getContext())); 1493218893Sdim if (CFP->getType()->isDoubleTy()) 1494218893Sdim V = ConstantExpr::getBitCast(CFP, Type::getInt64Ty(V->getContext())); 1495218893Sdim // Don't handle long double formats, which have strange constraints. 1496218893Sdim } 1497252723Sdim 1498252723Sdim // We can handle constant integers that are power of two in size and a 1499218893Sdim // multiple of 8 bits. 1500218893Sdim if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) { 1501218893Sdim unsigned Width = CI->getBitWidth(); 1502218893Sdim if (isPowerOf2_32(Width) && Width > 8) { 1503218893Sdim // We can handle this value if the recursive binary decomposition is the 1504218893Sdim // same at all levels. 1505218893Sdim APInt Val = CI->getValue(); 1506218893Sdim APInt Val2; 1507218893Sdim while (Val.getBitWidth() != 8) { 1508218893Sdim unsigned NextWidth = Val.getBitWidth()/2; 1509218893Sdim Val2 = Val.lshr(NextWidth); 1510218893Sdim Val2 = Val2.trunc(Val.getBitWidth()/2); 1511218893Sdim Val = Val.trunc(Val.getBitWidth()/2); 1512252723Sdim 1513218893Sdim // If the top/bottom halves aren't the same, reject it. 1514218893Sdim if (Val != Val2) 1515218893Sdim return 0; 1516218893Sdim } 1517218893Sdim return ConstantInt::get(V->getContext(), Val); 1518218893Sdim } 1519218893Sdim } 1520252723Sdim 1521235633Sdim // A ConstantDataArray/Vector is splatable if all its members are equal and 1522235633Sdim // also splatable. 1523235633Sdim if (ConstantDataSequential *CA = dyn_cast<ConstantDataSequential>(V)) { 1524235633Sdim Value *Elt = CA->getElementAsConstant(0); 1525235633Sdim Value *Val = isBytewiseValue(Elt); 1526218893Sdim if (!Val) 1527218893Sdim return 0; 1528252723Sdim 1529235633Sdim for (unsigned I = 1, E = CA->getNumElements(); I != E; ++I) 1530235633Sdim if (CA->getElementAsConstant(I) != Elt) 1531218893Sdim return 0; 1532252723Sdim 1533218893Sdim return Val; 1534218893Sdim } 1535235633Sdim 1536218893Sdim // Conceptually, we could handle things like: 1537218893Sdim // %a = zext i8 %X to i16 1538218893Sdim // %b = shl i16 %a, 8 1539218893Sdim // %c = or i16 %a, %b 1540218893Sdim // but until there is an example that actually needs this, it doesn't seem 1541218893Sdim // worth worrying about. 1542218893Sdim return 0; 1543218893Sdim} 1544218893Sdim 1545218893Sdim 1546193323Sed// This is the recursive version of BuildSubAggregate. It takes a few different 1547193323Sed// arguments. Idxs is the index within the nested struct From that we are 1548193323Sed// looking at now (which is of type IndexedType). IdxSkip is the number of 1549193323Sed// indices from Idxs that should be left out when inserting into the resulting 1550193323Sed// struct. To is the result struct built so far, new insertvalue instructions 1551193323Sed// build on that. 1552226890Sdimstatic Value *BuildSubAggregate(Value *From, Value* To, Type *IndexedType, 1553263509Sdim SmallVectorImpl<unsigned> &Idxs, 1554198090Srdivacky unsigned IdxSkip, 1555198090Srdivacky Instruction *InsertBefore) { 1556252723Sdim llvm::StructType *STy = dyn_cast<llvm::StructType>(IndexedType); 1557193323Sed if (STy) { 1558193323Sed // Save the original To argument so we can modify it 1559193323Sed Value *OrigTo = To; 1560193323Sed // General case, the type indexed by Idxs is a struct 1561193323Sed for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { 1562193323Sed // Process each struct element recursively 1563193323Sed Idxs.push_back(i); 1564193323Sed Value *PrevTo = To; 1565193323Sed To = BuildSubAggregate(From, To, STy->getElementType(i), Idxs, IdxSkip, 1566199989Srdivacky InsertBefore); 1567193323Sed Idxs.pop_back(); 1568193323Sed if (!To) { 1569193323Sed // Couldn't find any inserted value for this index? Cleanup 1570193323Sed while (PrevTo != OrigTo) { 1571193323Sed InsertValueInst* Del = cast<InsertValueInst>(PrevTo); 1572193323Sed PrevTo = Del->getAggregateOperand(); 1573193323Sed Del->eraseFromParent(); 1574193323Sed } 1575193323Sed // Stop processing elements 1576193323Sed break; 1577193323Sed } 1578193323Sed } 1579221345Sdim // If we successfully found a value for each of our subaggregates 1580193323Sed if (To) 1581193323Sed return To; 1582193323Sed } 1583193323Sed // Base case, the type indexed by SourceIdxs is not a struct, or not all of 1584193323Sed // the struct's elements had a value that was inserted directly. In the latter 1585193323Sed // case, perhaps we can't determine each of the subelements individually, but 1586193323Sed // we might be able to find the complete struct somewhere. 1587252723Sdim 1588193323Sed // Find the value that is at that particular spot 1589224145Sdim Value *V = FindInsertedValue(From, Idxs); 1590193323Sed 1591193323Sed if (!V) 1592193323Sed return NULL; 1593193323Sed 1594193323Sed // Insert the value in the new (sub) aggregrate 1595226890Sdim return llvm::InsertValueInst::Create(To, V, makeArrayRef(Idxs).slice(IdxSkip), 1596224145Sdim "tmp", InsertBefore); 1597193323Sed} 1598193323Sed 1599193323Sed// This helper takes a nested struct and extracts a part of it (which is again a 1600193323Sed// struct) into a new value. For example, given the struct: 1601193323Sed// { a, { b, { c, d }, e } } 1602193323Sed// and the indices "1, 1" this returns 1603193323Sed// { c, d }. 1604193323Sed// 1605193323Sed// It does this by inserting an insertvalue for each element in the resulting 1606193323Sed// struct, as opposed to just inserting a single struct. This will only work if 1607193323Sed// each of the elements of the substruct are known (ie, inserted into From by an 1608193323Sed// insertvalue instruction somewhere). 1609193323Sed// 1610193323Sed// All inserted insertvalue instructions are inserted before InsertBefore 1611224145Sdimstatic Value *BuildSubAggregate(Value *From, ArrayRef<unsigned> idx_range, 1612198090Srdivacky Instruction *InsertBefore) { 1613193323Sed assert(InsertBefore && "Must have someplace to insert!"); 1614226890Sdim Type *IndexedType = ExtractValueInst::getIndexedType(From->getType(), 1615224145Sdim idx_range); 1616193323Sed Value *To = UndefValue::get(IndexedType); 1617224145Sdim SmallVector<unsigned, 10> Idxs(idx_range.begin(), idx_range.end()); 1618193323Sed unsigned IdxSkip = Idxs.size(); 1619193323Sed 1620199989Srdivacky return BuildSubAggregate(From, To, IndexedType, Idxs, IdxSkip, InsertBefore); 1621193323Sed} 1622193323Sed 1623193323Sed/// FindInsertedValue - Given an aggregrate and an sequence of indices, see if 1624193323Sed/// the scalar value indexed is already around as a register, for example if it 1625193323Sed/// were inserted directly into the aggregrate. 1626193323Sed/// 1627193323Sed/// If InsertBefore is not null, this function will duplicate (modified) 1628193323Sed/// insertvalues when a part of a nested struct is extracted. 1629224145SdimValue *llvm::FindInsertedValue(Value *V, ArrayRef<unsigned> idx_range, 1630224145Sdim Instruction *InsertBefore) { 1631193323Sed // Nothing to index? Just return V then (this is useful at the end of our 1632235633Sdim // recursion). 1633224145Sdim if (idx_range.empty()) 1634193323Sed return V; 1635235633Sdim // We have indices, so V should have an indexable type. 1636235633Sdim assert((V->getType()->isStructTy() || V->getType()->isArrayTy()) && 1637235633Sdim "Not looking at a struct or array?"); 1638235633Sdim assert(ExtractValueInst::getIndexedType(V->getType(), idx_range) && 1639235633Sdim "Invalid indices for type?"); 1640198090Srdivacky 1641235633Sdim if (Constant *C = dyn_cast<Constant>(V)) { 1642235633Sdim C = C->getAggregateElement(idx_range[0]); 1643235633Sdim if (C == 0) return 0; 1644235633Sdim return FindInsertedValue(C, idx_range.slice(1), InsertBefore); 1645235633Sdim } 1646252723Sdim 1647235633Sdim if (InsertValueInst *I = dyn_cast<InsertValueInst>(V)) { 1648193323Sed // Loop the indices for the insertvalue instruction in parallel with the 1649193323Sed // requested indices 1650224145Sdim const unsigned *req_idx = idx_range.begin(); 1651193323Sed for (const unsigned *i = I->idx_begin(), *e = I->idx_end(); 1652193323Sed i != e; ++i, ++req_idx) { 1653224145Sdim if (req_idx == idx_range.end()) { 1654235633Sdim // We can't handle this without inserting insertvalues 1655235633Sdim if (!InsertBefore) 1656193323Sed return 0; 1657235633Sdim 1658235633Sdim // The requested index identifies a part of a nested aggregate. Handle 1659235633Sdim // this specially. For example, 1660235633Sdim // %A = insertvalue { i32, {i32, i32 } } undef, i32 10, 1, 0 1661235633Sdim // %B = insertvalue { i32, {i32, i32 } } %A, i32 11, 1, 1 1662235633Sdim // %C = extractvalue {i32, { i32, i32 } } %B, 1 1663235633Sdim // This can be changed into 1664235633Sdim // %A = insertvalue {i32, i32 } undef, i32 10, 0 1665235633Sdim // %C = insertvalue {i32, i32 } %A, i32 11, 1 1666235633Sdim // which allows the unused 0,0 element from the nested struct to be 1667235633Sdim // removed. 1668235633Sdim return BuildSubAggregate(V, makeArrayRef(idx_range.begin(), req_idx), 1669235633Sdim InsertBefore); 1670193323Sed } 1671252723Sdim 1672193323Sed // This insert value inserts something else than what we are looking for. 1673193323Sed // See if the (aggregrate) value inserted into has the value we are 1674193323Sed // looking for, then. 1675193323Sed if (*req_idx != *i) 1676224145Sdim return FindInsertedValue(I->getAggregateOperand(), idx_range, 1677199989Srdivacky InsertBefore); 1678193323Sed } 1679193323Sed // If we end up here, the indices of the insertvalue match with those 1680193323Sed // requested (though possibly only partially). Now we recursively look at 1681193323Sed // the inserted value, passing any remaining indices. 1682224145Sdim return FindInsertedValue(I->getInsertedValueOperand(), 1683226890Sdim makeArrayRef(req_idx, idx_range.end()), 1684199989Srdivacky InsertBefore); 1685235633Sdim } 1686252723Sdim 1687235633Sdim if (ExtractValueInst *I = dyn_cast<ExtractValueInst>(V)) { 1688193323Sed // If we're extracting a value from an aggregrate that was extracted from 1689193323Sed // something else, we can extract from that something else directly instead. 1690193323Sed // However, we will need to chain I's indices with the requested indices. 1691252723Sdim 1692252723Sdim // Calculate the number of indices required 1693224145Sdim unsigned size = I->getNumIndices() + idx_range.size(); 1694193323Sed // Allocate some space to put the new indices in 1695193323Sed SmallVector<unsigned, 5> Idxs; 1696193323Sed Idxs.reserve(size); 1697193323Sed // Add indices from the extract value instruction 1698224145Sdim Idxs.append(I->idx_begin(), I->idx_end()); 1699252723Sdim 1700193323Sed // Add requested indices 1701224145Sdim Idxs.append(idx_range.begin(), idx_range.end()); 1702193323Sed 1703252723Sdim assert(Idxs.size() == size 1704193323Sed && "Number of indices added not correct?"); 1705252723Sdim 1706224145Sdim return FindInsertedValue(I->getAggregateOperand(), Idxs, InsertBefore); 1707193323Sed } 1708193323Sed // Otherwise, we don't know (such as, extracting from a function return value 1709193323Sed // or load instruction) 1710193323Sed return 0; 1711193323Sed} 1712193323Sed 1713218893Sdim/// GetPointerBaseWithConstantOffset - Analyze the specified pointer to see if 1714218893Sdim/// it can be expressed as a base pointer plus a constant offset. Return the 1715218893Sdim/// base and offset to the caller. 1716218893SdimValue *llvm::GetPointerBaseWithConstantOffset(Value *Ptr, int64_t &Offset, 1717263509Sdim const DataLayout *DL) { 1718252723Sdim // Without DataLayout, conservatively assume 64-bit offsets, which is 1719252723Sdim // the widest we support. 1720263509Sdim unsigned BitWidth = DL ? DL->getPointerTypeSizeInBits(Ptr->getType()) : 64; 1721252723Sdim APInt ByteOffset(BitWidth, 0); 1722252723Sdim while (1) { 1723252723Sdim if (Ptr->getType()->isVectorTy()) 1724252723Sdim break; 1725252723Sdim 1726252723Sdim if (GEPOperator *GEP = dyn_cast<GEPOperator>(Ptr)) { 1727263509Sdim if (DL) { 1728263509Sdim APInt GEPOffset(BitWidth, 0); 1729263509Sdim if (!GEP->accumulateConstantOffset(*DL, GEPOffset)) 1730263509Sdim break; 1731263509Sdim 1732263509Sdim ByteOffset += GEPOffset; 1733263509Sdim } 1734263509Sdim 1735252723Sdim Ptr = GEP->getPointerOperand(); 1736252723Sdim } else if (Operator::getOpcode(Ptr) == Instruction::BitCast) { 1737252723Sdim Ptr = cast<Operator>(Ptr)->getOperand(0); 1738252723Sdim } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(Ptr)) { 1739252723Sdim if (GA->mayBeOverridden()) 1740252723Sdim break; 1741252723Sdim Ptr = GA->getAliasee(); 1742218893Sdim } else { 1743252723Sdim break; 1744218893Sdim } 1745218893Sdim } 1746252723Sdim Offset = ByteOffset.getSExtValue(); 1747252723Sdim return Ptr; 1748218893Sdim} 1749218893Sdim 1750218893Sdim 1751235633Sdim/// getConstantStringInfo - This function computes the length of a 1752193323Sed/// null-terminated C string pointed to by V. If successful, it returns true 1753193323Sed/// and returns the string in Str. If unsuccessful, it returns false. 1754235633Sdimbool llvm::getConstantStringInfo(const Value *V, StringRef &Str, 1755235633Sdim uint64_t Offset, bool TrimAtNul) { 1756235633Sdim assert(V); 1757193323Sed 1758235633Sdim // Look through bitcast instructions and geps. 1759235633Sdim V = V->stripPointerCasts(); 1760252723Sdim 1761235633Sdim // If the value is a GEP instructionor constant expression, treat it as an 1762235633Sdim // offset. 1763235633Sdim if (const GEPOperator *GEP = dyn_cast<GEPOperator>(V)) { 1764193323Sed // Make sure the GEP has exactly three arguments. 1765193323Sed if (GEP->getNumOperands() != 3) 1766193323Sed return false; 1767252723Sdim 1768193323Sed // Make sure the index-ee is a pointer to array of i8. 1769226890Sdim PointerType *PT = cast<PointerType>(GEP->getOperand(0)->getType()); 1770226890Sdim ArrayType *AT = dyn_cast<ArrayType>(PT->getElementType()); 1771203954Srdivacky if (AT == 0 || !AT->getElementType()->isIntegerTy(8)) 1772193323Sed return false; 1773252723Sdim 1774193323Sed // Check to make sure that the first operand of the GEP is an integer and 1775193323Sed // has value 0 so that we are sure we're indexing into the initializer. 1776207618Srdivacky const ConstantInt *FirstIdx = dyn_cast<ConstantInt>(GEP->getOperand(1)); 1777193323Sed if (FirstIdx == 0 || !FirstIdx->isZero()) 1778193323Sed return false; 1779252723Sdim 1780193323Sed // If the second index isn't a ConstantInt, then this is a variable index 1781193323Sed // into the array. If this occurs, we can't say anything meaningful about 1782193323Sed // the string. 1783193323Sed uint64_t StartIdx = 0; 1784207618Srdivacky if (const ConstantInt *CI = dyn_cast<ConstantInt>(GEP->getOperand(2))) 1785193323Sed StartIdx = CI->getZExtValue(); 1786193323Sed else 1787193323Sed return false; 1788235633Sdim return getConstantStringInfo(GEP->getOperand(0), Str, StartIdx+Offset); 1789193323Sed } 1790235633Sdim 1791193323Sed // The GEP instruction, constant or instruction, must reference a global 1792193323Sed // variable that is a constant and is initialized. The referenced constant 1793193323Sed // initializer is the array that we'll use for optimization. 1794235633Sdim const GlobalVariable *GV = dyn_cast<GlobalVariable>(V); 1795198090Srdivacky if (!GV || !GV->isConstant() || !GV->hasDefinitiveInitializer()) 1796193323Sed return false; 1797235633Sdim 1798235633Sdim // Handle the all-zeros case 1799235633Sdim if (GV->getInitializer()->isNullValue()) { 1800193323Sed // This is a degenerate case. The initializer is constant zero so the 1801193323Sed // length of the string must be zero. 1802235633Sdim Str = ""; 1803193323Sed return true; 1804193323Sed } 1805252723Sdim 1806193323Sed // Must be a Constant Array 1807235633Sdim const ConstantDataArray *Array = 1808235633Sdim dyn_cast<ConstantDataArray>(GV->getInitializer()); 1809235633Sdim if (Array == 0 || !Array->isString()) 1810193323Sed return false; 1811252723Sdim 1812193323Sed // Get the number of elements in the array 1813235633Sdim uint64_t NumElts = Array->getType()->getArrayNumElements(); 1814235633Sdim 1815235633Sdim // Start out with the entire array in the StringRef. 1816235633Sdim Str = Array->getAsString(); 1817235633Sdim 1818193323Sed if (Offset > NumElts) 1819193323Sed return false; 1820252723Sdim 1821235633Sdim // Skip over 'offset' bytes. 1822235633Sdim Str = Str.substr(Offset); 1823252723Sdim 1824235633Sdim if (TrimAtNul) { 1825235633Sdim // Trim off the \0 and anything after it. If the array is not nul 1826235633Sdim // terminated, we just return the whole end of string. The client may know 1827235633Sdim // some other way that the string is length-bound. 1828235633Sdim Str = Str.substr(0, Str.find('\0')); 1829193323Sed } 1830193323Sed return true; 1831193323Sed} 1832204792Srdivacky 1833204792Srdivacky// These next two are very similar to the above, but also look through PHI 1834204792Srdivacky// nodes. 1835204792Srdivacky// TODO: See if we can integrate these two together. 1836204792Srdivacky 1837204792Srdivacky/// GetStringLengthH - If we can compute the length of the string pointed to by 1838204792Srdivacky/// the specified pointer, return 'len+1'. If we can't, return 0. 1839204792Srdivackystatic uint64_t GetStringLengthH(Value *V, SmallPtrSet<PHINode*, 32> &PHIs) { 1840204792Srdivacky // Look through noop bitcast instructions. 1841235633Sdim V = V->stripPointerCasts(); 1842204792Srdivacky 1843204792Srdivacky // If this is a PHI node, there are two cases: either we have already seen it 1844204792Srdivacky // or we haven't. 1845204792Srdivacky if (PHINode *PN = dyn_cast<PHINode>(V)) { 1846204792Srdivacky if (!PHIs.insert(PN)) 1847204792Srdivacky return ~0ULL; // already in the set. 1848204792Srdivacky 1849204792Srdivacky // If it was new, see if all the input strings are the same length. 1850204792Srdivacky uint64_t LenSoFar = ~0ULL; 1851204792Srdivacky for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 1852204792Srdivacky uint64_t Len = GetStringLengthH(PN->getIncomingValue(i), PHIs); 1853204792Srdivacky if (Len == 0) return 0; // Unknown length -> unknown. 1854204792Srdivacky 1855204792Srdivacky if (Len == ~0ULL) continue; 1856204792Srdivacky 1857204792Srdivacky if (Len != LenSoFar && LenSoFar != ~0ULL) 1858204792Srdivacky return 0; // Disagree -> unknown. 1859204792Srdivacky LenSoFar = Len; 1860204792Srdivacky } 1861204792Srdivacky 1862204792Srdivacky // Success, all agree. 1863204792Srdivacky return LenSoFar; 1864204792Srdivacky } 1865204792Srdivacky 1866204792Srdivacky // strlen(select(c,x,y)) -> strlen(x) ^ strlen(y) 1867204792Srdivacky if (SelectInst *SI = dyn_cast<SelectInst>(V)) { 1868204792Srdivacky uint64_t Len1 = GetStringLengthH(SI->getTrueValue(), PHIs); 1869204792Srdivacky if (Len1 == 0) return 0; 1870204792Srdivacky uint64_t Len2 = GetStringLengthH(SI->getFalseValue(), PHIs); 1871204792Srdivacky if (Len2 == 0) return 0; 1872204792Srdivacky if (Len1 == ~0ULL) return Len2; 1873204792Srdivacky if (Len2 == ~0ULL) return Len1; 1874204792Srdivacky if (Len1 != Len2) return 0; 1875204792Srdivacky return Len1; 1876204792Srdivacky } 1877252723Sdim 1878235633Sdim // Otherwise, see if we can read the string. 1879235633Sdim StringRef StrData; 1880235633Sdim if (!getConstantStringInfo(V, StrData)) 1881204792Srdivacky return 0; 1882204792Srdivacky 1883235633Sdim return StrData.size()+1; 1884204792Srdivacky} 1885204792Srdivacky 1886204792Srdivacky/// GetStringLength - If we can compute the length of the string pointed to by 1887204792Srdivacky/// the specified pointer, return 'len+1'. If we can't, return 0. 1888204792Srdivackyuint64_t llvm::GetStringLength(Value *V) { 1889204792Srdivacky if (!V->getType()->isPointerTy()) return 0; 1890204792Srdivacky 1891204792Srdivacky SmallPtrSet<PHINode*, 32> PHIs; 1892204792Srdivacky uint64_t Len = GetStringLengthH(V, PHIs); 1893204792Srdivacky // If Len is ~0ULL, we had an infinite phi cycle: this is dead code, so return 1894204792Srdivacky // an empty string as a length. 1895204792Srdivacky return Len == ~0ULL ? 1 : Len; 1896204792Srdivacky} 1897218893Sdim 1898218893SdimValue * 1899245431Sdimllvm::GetUnderlyingObject(Value *V, const DataLayout *TD, unsigned MaxLookup) { 1900218893Sdim if (!V->getType()->isPointerTy()) 1901218893Sdim return V; 1902218893Sdim for (unsigned Count = 0; MaxLookup == 0 || Count < MaxLookup; ++Count) { 1903218893Sdim if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) { 1904218893Sdim V = GEP->getPointerOperand(); 1905218893Sdim } else if (Operator::getOpcode(V) == Instruction::BitCast) { 1906218893Sdim V = cast<Operator>(V)->getOperand(0); 1907218893Sdim } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) { 1908218893Sdim if (GA->mayBeOverridden()) 1909218893Sdim return V; 1910218893Sdim V = GA->getAliasee(); 1911218893Sdim } else { 1912218893Sdim // See if InstructionSimplify knows any relevant tricks. 1913218893Sdim if (Instruction *I = dyn_cast<Instruction>(V)) 1914221345Sdim // TODO: Acquire a DominatorTree and use it. 1915218893Sdim if (Value *Simplified = SimplifyInstruction(I, TD, 0)) { 1916218893Sdim V = Simplified; 1917218893Sdim continue; 1918218893Sdim } 1919218893Sdim 1920218893Sdim return V; 1921218893Sdim } 1922218893Sdim assert(V->getType()->isPointerTy() && "Unexpected operand type!"); 1923218893Sdim } 1924218893Sdim return V; 1925218893Sdim} 1926224145Sdim 1927245431Sdimvoid 1928245431Sdimllvm::GetUnderlyingObjects(Value *V, 1929245431Sdim SmallVectorImpl<Value *> &Objects, 1930245431Sdim const DataLayout *TD, 1931245431Sdim unsigned MaxLookup) { 1932245431Sdim SmallPtrSet<Value *, 4> Visited; 1933245431Sdim SmallVector<Value *, 4> Worklist; 1934245431Sdim Worklist.push_back(V); 1935245431Sdim do { 1936245431Sdim Value *P = Worklist.pop_back_val(); 1937245431Sdim P = GetUnderlyingObject(P, TD, MaxLookup); 1938245431Sdim 1939245431Sdim if (!Visited.insert(P)) 1940245431Sdim continue; 1941245431Sdim 1942245431Sdim if (SelectInst *SI = dyn_cast<SelectInst>(P)) { 1943245431Sdim Worklist.push_back(SI->getTrueValue()); 1944245431Sdim Worklist.push_back(SI->getFalseValue()); 1945245431Sdim continue; 1946245431Sdim } 1947245431Sdim 1948245431Sdim if (PHINode *PN = dyn_cast<PHINode>(P)) { 1949245431Sdim for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 1950245431Sdim Worklist.push_back(PN->getIncomingValue(i)); 1951245431Sdim continue; 1952245431Sdim } 1953245431Sdim 1954245431Sdim Objects.push_back(P); 1955245431Sdim } while (!Worklist.empty()); 1956245431Sdim} 1957245431Sdim 1958224145Sdim/// onlyUsedByLifetimeMarkers - Return true if the only users of this pointer 1959224145Sdim/// are lifetime markers. 1960224145Sdim/// 1961224145Sdimbool llvm::onlyUsedByLifetimeMarkers(const Value *V) { 1962224145Sdim for (Value::const_use_iterator UI = V->use_begin(), UE = V->use_end(); 1963224145Sdim UI != UE; ++UI) { 1964224145Sdim const IntrinsicInst *II = dyn_cast<IntrinsicInst>(*UI); 1965224145Sdim if (!II) return false; 1966224145Sdim 1967224145Sdim if (II->getIntrinsicID() != Intrinsic::lifetime_start && 1968224145Sdim II->getIntrinsicID() != Intrinsic::lifetime_end) 1969224145Sdim return false; 1970224145Sdim } 1971224145Sdim return true; 1972224145Sdim} 1973235633Sdim 1974235633Sdimbool llvm::isSafeToSpeculativelyExecute(const Value *V, 1975245431Sdim const DataLayout *TD) { 1976235633Sdim const Operator *Inst = dyn_cast<Operator>(V); 1977235633Sdim if (!Inst) 1978235633Sdim return false; 1979235633Sdim 1980235633Sdim for (unsigned i = 0, e = Inst->getNumOperands(); i != e; ++i) 1981235633Sdim if (Constant *C = dyn_cast<Constant>(Inst->getOperand(i))) 1982235633Sdim if (C->canTrap()) 1983235633Sdim return false; 1984235633Sdim 1985235633Sdim switch (Inst->getOpcode()) { 1986235633Sdim default: 1987235633Sdim return true; 1988235633Sdim case Instruction::UDiv: 1989235633Sdim case Instruction::URem: 1990235633Sdim // x / y is undefined if y == 0, but calcuations like x / 3 are safe. 1991235633Sdim return isKnownNonZero(Inst->getOperand(1), TD); 1992235633Sdim case Instruction::SDiv: 1993235633Sdim case Instruction::SRem: { 1994235633Sdim Value *Op = Inst->getOperand(1); 1995235633Sdim // x / y is undefined if y == 0 1996235633Sdim if (!isKnownNonZero(Op, TD)) 1997235633Sdim return false; 1998235633Sdim // x / y might be undefined if y == -1 1999235633Sdim unsigned BitWidth = getBitWidth(Op->getType(), TD); 2000235633Sdim if (BitWidth == 0) 2001235633Sdim return false; 2002235633Sdim APInt KnownZero(BitWidth, 0); 2003235633Sdim APInt KnownOne(BitWidth, 0); 2004235633Sdim ComputeMaskedBits(Op, KnownZero, KnownOne, TD); 2005235633Sdim return !!KnownZero; 2006235633Sdim } 2007235633Sdim case Instruction::Load: { 2008235633Sdim const LoadInst *LI = cast<LoadInst>(Inst); 2009235633Sdim if (!LI->isUnordered()) 2010235633Sdim return false; 2011235633Sdim return LI->getPointerOperand()->isDereferenceablePointer(); 2012235633Sdim } 2013235633Sdim case Instruction::Call: { 2014235633Sdim if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) { 2015235633Sdim switch (II->getIntrinsicID()) { 2016235633Sdim // These synthetic intrinsics have no side-effects, and just mark 2017235633Sdim // information about their operands. 2018235633Sdim // FIXME: There are other no-op synthetic instructions that potentially 2019235633Sdim // should be considered at least *safe* to speculate... 2020235633Sdim case Intrinsic::dbg_declare: 2021235633Sdim case Intrinsic::dbg_value: 2022235633Sdim return true; 2023235633Sdim 2024235633Sdim case Intrinsic::bswap: 2025235633Sdim case Intrinsic::ctlz: 2026235633Sdim case Intrinsic::ctpop: 2027235633Sdim case Intrinsic::cttz: 2028235633Sdim case Intrinsic::objectsize: 2029235633Sdim case Intrinsic::sadd_with_overflow: 2030235633Sdim case Intrinsic::smul_with_overflow: 2031235633Sdim case Intrinsic::ssub_with_overflow: 2032235633Sdim case Intrinsic::uadd_with_overflow: 2033235633Sdim case Intrinsic::umul_with_overflow: 2034235633Sdim case Intrinsic::usub_with_overflow: 2035235633Sdim return true; 2036235633Sdim // TODO: some fp intrinsics are marked as having the same error handling 2037235633Sdim // as libm. They're safe to speculate when they won't error. 2038235633Sdim // TODO: are convert_{from,to}_fp16 safe? 2039235633Sdim // TODO: can we list target-specific intrinsics here? 2040235633Sdim default: break; 2041235633Sdim } 2042235633Sdim } 2043235633Sdim return false; // The called function could have undefined behavior or 2044235633Sdim // side-effects, even if marked readnone nounwind. 2045235633Sdim } 2046235633Sdim case Instruction::VAArg: 2047235633Sdim case Instruction::Alloca: 2048235633Sdim case Instruction::Invoke: 2049235633Sdim case Instruction::PHI: 2050235633Sdim case Instruction::Store: 2051235633Sdim case Instruction::Ret: 2052235633Sdim case Instruction::Br: 2053235633Sdim case Instruction::IndirectBr: 2054235633Sdim case Instruction::Switch: 2055235633Sdim case Instruction::Unreachable: 2056235633Sdim case Instruction::Fence: 2057235633Sdim case Instruction::LandingPad: 2058235633Sdim case Instruction::AtomicRMW: 2059235633Sdim case Instruction::AtomicCmpXchg: 2060235633Sdim case Instruction::Resume: 2061235633Sdim return false; // Misc instructions which have effects 2062235633Sdim } 2063235633Sdim} 2064252723Sdim 2065252723Sdim/// isKnownNonNull - Return true if we know that the specified value is never 2066252723Sdim/// null. 2067263509Sdimbool llvm::isKnownNonNull(const Value *V, const TargetLibraryInfo *TLI) { 2068252723Sdim // Alloca never returns null, malloc might. 2069252723Sdim if (isa<AllocaInst>(V)) return true; 2070252723Sdim 2071252723Sdim // A byval argument is never null. 2072252723Sdim if (const Argument *A = dyn_cast<Argument>(V)) 2073252723Sdim return A->hasByValAttr(); 2074252723Sdim 2075252723Sdim // Global values are not null unless extern weak. 2076252723Sdim if (const GlobalValue *GV = dyn_cast<GlobalValue>(V)) 2077252723Sdim return !GV->hasExternalWeakLinkage(); 2078263509Sdim 2079263509Sdim // operator new never returns null. 2080263509Sdim if (isOperatorNewLikeFn(V, TLI, /*LookThroughBitCast=*/true)) 2081263509Sdim return true; 2082263509Sdim 2083252723Sdim return false; 2084252723Sdim} 2085