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" 16249423Sdim#include "llvm/ADT/SmallPtrSet.h" 17218893Sdim#include "llvm/Analysis/InstructionSimplify.h" 18263508Sdim#include "llvm/Analysis/MemoryBuiltins.h" 19249423Sdim#include "llvm/IR/Constants.h" 20249423Sdim#include "llvm/IR/DataLayout.h" 21249423Sdim#include "llvm/IR/GlobalAlias.h" 22249423Sdim#include "llvm/IR/GlobalVariable.h" 23249423Sdim#include "llvm/IR/Instructions.h" 24249423Sdim#include "llvm/IR/IntrinsicInst.h" 25249423Sdim#include "llvm/IR/LLVMContext.h" 26249423Sdim#include "llvm/IR/Metadata.h" 27249423Sdim#include "llvm/IR/Operator.h" 28234353Sdim#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. 40243830Sdimstatic unsigned getBitWidth(Type *Ty, const DataLayout *TD) { 41218893Sdim if (unsigned BitWidth = Ty->getScalarSizeInBits()) 42218893Sdim return BitWidth; 43263508Sdim 44263508Sdim return TD ? TD->getPointerTypeSizeInBits(Ty) : 0; 45218893Sdim} 46218893Sdim 47234353Sdimstatic void ComputeMaskedBitsAddSub(bool Add, Value *Op0, Value *Op1, bool NSW, 48234353Sdim APInt &KnownZero, APInt &KnownOne, 49234353Sdim APInt &KnownZero2, APInt &KnownOne2, 50243830Sdim const DataLayout *TD, unsigned Depth) { 51234353Sdim if (!Add) { 52234353Sdim if (ConstantInt *CLHS = dyn_cast<ConstantInt>(Op0)) { 53234353Sdim // We know that the top bits of C-X are clear if X contains less bits 54234353Sdim // than C (i.e. no wrap-around can happen). For example, 20-X is 55234353Sdim // positive if we can prove that X is >= 0 and < 16. 56234353Sdim if (!CLHS->getValue().isNegative()) { 57234353Sdim unsigned BitWidth = KnownZero.getBitWidth(); 58234353Sdim unsigned NLZ = (CLHS->getValue()+1).countLeadingZeros(); 59234353Sdim // NLZ can't be BitWidth with no sign bit 60234353Sdim APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1); 61234353Sdim llvm::ComputeMaskedBits(Op1, KnownZero2, KnownOne2, TD, Depth+1); 62249423Sdim 63234353Sdim // If all of the MaskV bits are known to be zero, then we know the 64234353Sdim // output top bits are zero, because we now know that the output is 65234353Sdim // from [0-C]. 66234353Sdim if ((KnownZero2 & MaskV) == MaskV) { 67234353Sdim unsigned NLZ2 = CLHS->getValue().countLeadingZeros(); 68234353Sdim // Top bits known zero. 69234353Sdim KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2); 70234353Sdim } 71234353Sdim } 72234353Sdim } 73234353Sdim } 74234353Sdim 75234353Sdim unsigned BitWidth = KnownZero.getBitWidth(); 76234353Sdim 77234353Sdim // If one of the operands has trailing zeros, then the bits that the 78234353Sdim // other operand has in those bit positions will be preserved in the 79234353Sdim // result. For an add, this works with either operand. For a subtract, 80234353Sdim // this only works if the known zeros are in the right operand. 81234353Sdim APInt LHSKnownZero(BitWidth, 0), LHSKnownOne(BitWidth, 0); 82234353Sdim llvm::ComputeMaskedBits(Op0, LHSKnownZero, LHSKnownOne, TD, Depth+1); 83234353Sdim assert((LHSKnownZero & LHSKnownOne) == 0 && 84234353Sdim "Bits known to be one AND zero?"); 85234353Sdim unsigned LHSKnownZeroOut = LHSKnownZero.countTrailingOnes(); 86234353Sdim 87234353Sdim llvm::ComputeMaskedBits(Op1, KnownZero2, KnownOne2, TD, Depth+1); 88249423Sdim assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 89234353Sdim unsigned RHSKnownZeroOut = KnownZero2.countTrailingOnes(); 90234353Sdim 91234353Sdim // Determine which operand has more trailing zeros, and use that 92234353Sdim // many bits from the other operand. 93234353Sdim if (LHSKnownZeroOut > RHSKnownZeroOut) { 94234353Sdim if (Add) { 95234353Sdim APInt Mask = APInt::getLowBitsSet(BitWidth, LHSKnownZeroOut); 96234353Sdim KnownZero |= KnownZero2 & Mask; 97234353Sdim KnownOne |= KnownOne2 & Mask; 98234353Sdim } else { 99234353Sdim // If the known zeros are in the left operand for a subtract, 100234353Sdim // fall back to the minimum known zeros in both operands. 101234353Sdim KnownZero |= APInt::getLowBitsSet(BitWidth, 102234353Sdim std::min(LHSKnownZeroOut, 103234353Sdim RHSKnownZeroOut)); 104234353Sdim } 105234353Sdim } else if (RHSKnownZeroOut >= LHSKnownZeroOut) { 106234353Sdim APInt Mask = APInt::getLowBitsSet(BitWidth, RHSKnownZeroOut); 107234353Sdim KnownZero |= LHSKnownZero & Mask; 108234353Sdim KnownOne |= LHSKnownOne & Mask; 109234353Sdim } 110234353Sdim 111234353Sdim // Are we still trying to solve for the sign bit? 112234353Sdim if (!KnownZero.isNegative() && !KnownOne.isNegative()) { 113234353Sdim if (NSW) { 114234353Sdim if (Add) { 115234353Sdim // Adding two positive numbers can't wrap into negative 116234353Sdim if (LHSKnownZero.isNegative() && KnownZero2.isNegative()) 117234353Sdim KnownZero |= APInt::getSignBit(BitWidth); 118234353Sdim // and adding two negative numbers can't wrap into positive. 119234353Sdim else if (LHSKnownOne.isNegative() && KnownOne2.isNegative()) 120234353Sdim KnownOne |= APInt::getSignBit(BitWidth); 121234353Sdim } else { 122234353Sdim // Subtracting a negative number from a positive one can't wrap 123234353Sdim if (LHSKnownZero.isNegative() && KnownOne2.isNegative()) 124234353Sdim KnownZero |= APInt::getSignBit(BitWidth); 125234353Sdim // neither can subtracting a positive number from a negative one. 126234353Sdim else if (LHSKnownOne.isNegative() && KnownZero2.isNegative()) 127234353Sdim KnownOne |= APInt::getSignBit(BitWidth); 128234353Sdim } 129234353Sdim } 130234353Sdim } 131234353Sdim} 132234353Sdim 133234353Sdimstatic void ComputeMaskedBitsMul(Value *Op0, Value *Op1, bool NSW, 134234353Sdim APInt &KnownZero, APInt &KnownOne, 135234353Sdim APInt &KnownZero2, APInt &KnownOne2, 136243830Sdim const DataLayout *TD, unsigned Depth) { 137234353Sdim unsigned BitWidth = KnownZero.getBitWidth(); 138234353Sdim ComputeMaskedBits(Op1, KnownZero, KnownOne, TD, Depth+1); 139234353Sdim ComputeMaskedBits(Op0, KnownZero2, KnownOne2, TD, Depth+1); 140234353Sdim assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 141234353Sdim assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 142234353Sdim 143234353Sdim bool isKnownNegative = false; 144234353Sdim bool isKnownNonNegative = false; 145234353Sdim // If the multiplication is known not to overflow, compute the sign bit. 146234353Sdim if (NSW) { 147234353Sdim if (Op0 == Op1) { 148234353Sdim // The product of a number with itself is non-negative. 149234353Sdim isKnownNonNegative = true; 150234353Sdim } else { 151234353Sdim bool isKnownNonNegativeOp1 = KnownZero.isNegative(); 152234353Sdim bool isKnownNonNegativeOp0 = KnownZero2.isNegative(); 153234353Sdim bool isKnownNegativeOp1 = KnownOne.isNegative(); 154234353Sdim bool isKnownNegativeOp0 = KnownOne2.isNegative(); 155234353Sdim // The product of two numbers with the same sign is non-negative. 156234353Sdim isKnownNonNegative = (isKnownNegativeOp1 && isKnownNegativeOp0) || 157234353Sdim (isKnownNonNegativeOp1 && isKnownNonNegativeOp0); 158234353Sdim // The product of a negative number and a non-negative number is either 159234353Sdim // negative or zero. 160234353Sdim if (!isKnownNonNegative) 161234353Sdim isKnownNegative = (isKnownNegativeOp1 && isKnownNonNegativeOp0 && 162234353Sdim isKnownNonZero(Op0, TD, Depth)) || 163234353Sdim (isKnownNegativeOp0 && isKnownNonNegativeOp1 && 164234353Sdim isKnownNonZero(Op1, TD, Depth)); 165234353Sdim } 166234353Sdim } 167234353Sdim 168234353Sdim // If low bits are zero in either operand, output low known-0 bits. 169234353Sdim // Also compute a conserative estimate for high known-0 bits. 170234353Sdim // More trickiness is possible, but this is sufficient for the 171234353Sdim // interesting case of alignment computation. 172234353Sdim KnownOne.clearAllBits(); 173234353Sdim unsigned TrailZ = KnownZero.countTrailingOnes() + 174234353Sdim KnownZero2.countTrailingOnes(); 175234353Sdim unsigned LeadZ = std::max(KnownZero.countLeadingOnes() + 176234353Sdim KnownZero2.countLeadingOnes(), 177234353Sdim BitWidth) - BitWidth; 178234353Sdim 179234353Sdim TrailZ = std::min(TrailZ, BitWidth); 180234353Sdim LeadZ = std::min(LeadZ, BitWidth); 181234353Sdim KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) | 182234353Sdim APInt::getHighBitsSet(BitWidth, LeadZ); 183234353Sdim 184234353Sdim // Only make use of no-wrap flags if we failed to compute the sign bit 185234353Sdim // directly. This matters if the multiplication always overflows, in 186234353Sdim // which case we prefer to follow the result of the direct computation, 187234353Sdim // though as the program is invoking undefined behaviour we can choose 188234353Sdim // whatever we like here. 189234353Sdim if (isKnownNonNegative && !KnownOne.isNegative()) 190234353Sdim KnownZero.setBit(BitWidth - 1); 191234353Sdim else if (isKnownNegative && !KnownZero.isNegative()) 192234353Sdim KnownOne.setBit(BitWidth - 1); 193234353Sdim} 194234353Sdim 195234353Sdimvoid llvm::computeMaskedBitsLoad(const MDNode &Ranges, APInt &KnownZero) { 196234353Sdim unsigned BitWidth = KnownZero.getBitWidth(); 197234353Sdim unsigned NumRanges = Ranges.getNumOperands() / 2; 198234353Sdim assert(NumRanges >= 1); 199234353Sdim 200234353Sdim // Use the high end of the ranges to find leading zeros. 201234353Sdim unsigned MinLeadingZeros = BitWidth; 202234353Sdim for (unsigned i = 0; i < NumRanges; ++i) { 203234353Sdim ConstantInt *Lower = cast<ConstantInt>(Ranges.getOperand(2*i + 0)); 204234353Sdim ConstantInt *Upper = cast<ConstantInt>(Ranges.getOperand(2*i + 1)); 205234353Sdim ConstantRange Range(Lower->getValue(), Upper->getValue()); 206234353Sdim if (Range.isWrappedSet()) 207234353Sdim MinLeadingZeros = 0; // -1 has no zeros 208234353Sdim unsigned LeadingZeros = (Upper->getValue() - 1).countLeadingZeros(); 209234353Sdim MinLeadingZeros = std::min(LeadingZeros, MinLeadingZeros); 210234353Sdim } 211234353Sdim 212234353Sdim KnownZero = APInt::getHighBitsSet(BitWidth, MinLeadingZeros); 213234353Sdim} 214234353Sdim/// ComputeMaskedBits - Determine which of the bits are known to be either zero 215234353Sdim/// or one and return them in the KnownZero/KnownOne bit sets. 216234353Sdim/// 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 226234353Sdim/// 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. 229234353Sdimvoid llvm::ComputeMaskedBits(Value *V, APInt &KnownZero, APInt &KnownOne, 230243830Sdim const DataLayout *TD, unsigned Depth) { 231193323Sed assert(V && "No Value?"); 232193323Sed assert(Depth <= MaxDepth && "Limit Search Depth"); 233234353Sdim unsigned BitWidth = KnownZero.getBitWidth(); 234234353Sdim 235234353Sdim assert((V->getType()->isIntOrIntVectorTy() || 236234353Sdim V->getType()->getScalarType()->isPointerTy()) && 237234353Sdim "Not integer or pointer type!"); 238194612Sed assert((!TD || 239194612Sed TD->getTypeSizeInBits(V->getType()->getScalarType()) == BitWidth) && 240203954Srdivacky (!V->getType()->isIntOrIntVectorTy() || 241194612Sed V->getType()->getScalarSizeInBits() == BitWidth) && 242234353Sdim 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! 248234353Sdim KnownOne = CI->getValue(); 249234353Sdim 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(); 256234353Sdim KnownZero = APInt::getAllOnesValue(BitWidth); 257193323Sed return; 258193323Sed } 259194612Sed // Handle a constant vector by taking the intersection of the known bits of 260234353Sdim // each element. There is no real need to handle ConstantVector here, because 261234353Sdim // we don't handle undef in any particularly useful way. 262234353Sdim if (ConstantDataSequential *CDS = dyn_cast<ConstantDataSequential>(V)) { 263234353Sdim // We know that CDS must be a vector of integers. Take the intersection of 264234353Sdim // each element. 265218893Sdim KnownZero.setAllBits(); KnownOne.setAllBits(); 266234353Sdim APInt Elt(KnownZero.getBitWidth(), 0); 267234353Sdim for (unsigned i = 0, e = CDS->getNumElements(); i != e; ++i) { 268234353Sdim Elt = CDS->getElementAsInteger(i); 269234353Sdim KnownZero &= ~Elt; 270249423Sdim KnownOne &= Elt; 271194612Sed } 272194612Sed return; 273194612Sed } 274249423Sdim 275193323Sed // The address of an aligned GlobalValue has trailing zeros. 276193323Sed if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) { 277193323Sed unsigned Align = GV->getAlignment(); 278234353Sdim if (Align == 0 && TD) { 279234353Sdim if (GlobalVariable *GVar = dyn_cast<GlobalVariable>(GV)) { 280234353Sdim Type *ObjectType = GVar->getType()->getElementType(); 281234353Sdim if (ObjectType->isSized()) { 282234353Sdim // If the object is defined in the current Module, we'll be giving 283234353Sdim // it the preferred alignment. Otherwise, we have to assume that it 284234353Sdim // may only have the minimum ABI alignment. 285234353Sdim if (!GVar->isDeclaration() && !GVar->isWeakForLinker()) 286234353Sdim Align = TD->getPreferredAlignment(GVar); 287234353Sdim else 288234353Sdim Align = TD->getABITypeAlignment(ObjectType); 289234353Sdim } 290234353Sdim } 291198090Srdivacky } 292193323Sed if (Align > 0) 293234353Sdim KnownZero = APInt::getLowBitsSet(BitWidth, 294263508Sdim 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 { 306234353Sdim ComputeMaskedBits(GA->getAliasee(), KnownZero, KnownOne, TD, Depth+1); 307198090Srdivacky } 308198090Srdivacky return; 309198090Srdivacky } 310249423Sdim 311223017Sdim if (Argument *A = dyn_cast<Argument>(V)) { 312243830Sdim unsigned Align = 0; 313243830Sdim 314243830Sdim if (A->hasByValAttr()) { 315243830Sdim // Get alignment information off byval arguments if specified in the IR. 316243830Sdim Align = A->getParamAlignment(); 317243830Sdim } else if (TD && A->hasStructRetAttr()) { 318243830Sdim // An sret parameter has at least the ABI alignment of the return type. 319243830Sdim Type *EltTy = cast<PointerType>(A->getType())->getElementType(); 320243830Sdim if (EltTy->isSized()) 321243830Sdim Align = TD->getABITypeAlignment(EltTy); 322243830Sdim } 323243830Sdim 324243830Sdim if (Align) 325263508Sdim KnownZero = APInt::getLowBitsSet(BitWidth, countTrailingZeros(Align)); 326223017Sdim return; 327223017Sdim } 328193323Sed 329223017Sdim // Start out not knowing anything. 330223017Sdim KnownZero.clearAllBits(); KnownOne.clearAllBits(); 331193323Sed 332234353Sdim 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; 341234353Sdim case Instruction::Load: 342234353Sdim if (MDNode *MD = cast<LoadInst>(I)->getMetadata(LLVMContext::MD_range)) 343234353Sdim computeMaskedBitsLoad(*MD, KnownZero); 344234353Sdim return; 345193323Sed case Instruction::And: { 346193323Sed // If either the LHS or the RHS are Zero, the result is zero. 347234353Sdim ComputeMaskedBits(I->getOperand(1), KnownZero, KnownOne, TD, Depth+1); 348234353Sdim ComputeMaskedBits(I->getOperand(0), KnownZero2, KnownOne2, TD, Depth+1); 349249423Sdim assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 350249423Sdim assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 351249423Sdim 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: { 359234353Sdim ComputeMaskedBits(I->getOperand(1), KnownZero, KnownOne, TD, Depth+1); 360234353Sdim ComputeMaskedBits(I->getOperand(0), KnownZero2, KnownOne2, TD, Depth+1); 361249423Sdim assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 362249423Sdim assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 363249423Sdim 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: { 371234353Sdim ComputeMaskedBits(I->getOperand(1), KnownZero, KnownOne, TD, Depth+1); 372234353Sdim ComputeMaskedBits(I->getOperand(0), KnownZero2, KnownOne2, TD, Depth+1); 373249423Sdim assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 374249423Sdim assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 375249423Sdim 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: { 384234353Sdim bool NSW = cast<OverflowingBinaryOperator>(I)->hasNoSignedWrap(); 385234353Sdim ComputeMaskedBitsMul(I->getOperand(0), I->getOperand(1), NSW, 386234353Sdim KnownZero, KnownOne, KnownZero2, KnownOne2, TD, Depth); 387234353Sdim 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. 393234353Sdim ComputeMaskedBits(I->getOperand(0), KnownZero2, KnownOne2, TD, Depth+1); 394193323Sed unsigned LeadZ = KnownZero2.countLeadingOnes(); 395193323Sed 396218893Sdim KnownOne2.clearAllBits(); 397218893Sdim KnownZero2.clearAllBits(); 398234353Sdim 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 404234353Sdim KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ); 405193323Sed return; 406193323Sed } 407193323Sed case Instruction::Select: 408234353Sdim ComputeMaskedBits(I->getOperand(2), KnownZero, KnownOne, TD, Depth+1); 409234353Sdim ComputeMaskedBits(I->getOperand(1), KnownZero2, KnownOne2, TD, 410193323Sed Depth+1); 411249423Sdim assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 412249423Sdim 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: { 432226633Sdim Type *SrcTy = I->getOperand(0)->getType(); 433243830Sdim 434198090Srdivacky unsigned SrcBitWidth; 435193323Sed // Note that we handle pointer operands here because of inttoptr/ptrtoint 436193323Sed // which fall through here. 437249423Sdim if(TD) { 438249423Sdim SrcBitWidth = TD->getTypeSizeInBits(SrcTy->getScalarType()); 439249423Sdim } else { 440249423Sdim SrcBitWidth = SrcTy->getScalarSizeInBits(); 441249423Sdim if (!SrcBitWidth) return; 442249423Sdim } 443243830Sdim 444243830Sdim assert(SrcBitWidth && "SrcBitWidth can't be zero"); 445218893Sdim KnownZero = KnownZero.zextOrTrunc(SrcBitWidth); 446218893Sdim KnownOne = KnownOne.zextOrTrunc(SrcBitWidth); 447234353Sdim 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: { 456226633Sdim 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()) { 461234353Sdim 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(); 469249423Sdim 470218893Sdim KnownZero = KnownZero.trunc(SrcBitWidth); 471218893Sdim KnownOne = KnownOne.trunc(SrcBitWidth); 472234353Sdim ComputeMaskedBits(I->getOperand(0), KnownZero, KnownOne, TD, Depth+1); 473249423Sdim 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); 489234353Sdim ComputeMaskedBits(I->getOperand(0), KnownZero, KnownOne, TD, Depth+1); 490249423Sdim 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); 502249423Sdim 503193323Sed // Unsigned shift right. 504234353Sdim ComputeMaskedBits(I->getOperand(0), KnownZero,KnownOne, TD, Depth+1); 505249423Sdim 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); 518249423Sdim 519193323Sed // Signed shift right. 520234353Sdim ComputeMaskedBits(I->getOperand(0), KnownZero, KnownOne, TD, Depth+1); 521249423Sdim assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 522193323Sed KnownZero = APIntOps::lshr(KnownZero, ShiftAmt); 523193323Sed KnownOne = APIntOps::lshr(KnownOne, ShiftAmt); 524249423Sdim 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: { 534234353Sdim bool NSW = cast<OverflowingBinaryOperator>(I)->hasNoSignedWrap(); 535234353Sdim ComputeMaskedBitsAddSub(false, I->getOperand(0), I->getOperand(1), NSW, 536234353Sdim KnownZero, KnownOne, KnownZero2, KnownOne2, TD, 537234353Sdim Depth); 538234353Sdim break; 539193323Sed } 540193323Sed case Instruction::Add: { 541234353Sdim bool NSW = cast<OverflowingBinaryOperator>(I)->hasNoSignedWrap(); 542234353Sdim ComputeMaskedBitsAddSub(true, I->getOperand(0), I->getOperand(1), NSW, 543234353Sdim KnownZero, KnownOne, KnownZero2, KnownOne2, TD, 544234353Sdim Depth); 545234353Sdim 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; 552234353Sdim 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 568249423Sdim 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. 574234353Sdim if (KnownZero.isNonNegative()) { 575221345Sdim APInt LHSKnownZero(BitWidth, 0), LHSKnownOne(BitWidth, 0); 576234353Sdim 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()) 580234982Sdim 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); 589234353Sdim ComputeMaskedBits(I->getOperand(0), KnownZero, KnownOne, TD, 590193323Sed Depth+1); 591199989Srdivacky assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 592234353Sdim KnownZero |= ~LowBits; 593234353Sdim 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. 600234353Sdim ComputeMaskedBits(I->getOperand(0), KnownZero, KnownOne, TD, Depth+1); 601234353Sdim ComputeMaskedBits(I->getOperand(1), KnownZero2, KnownOne2, TD, Depth+1); 602193323Sed 603193323Sed unsigned Leaders = std::max(KnownZero.countLeadingOnes(), 604193323Sed KnownZero2.countLeadingOnes()); 605218893Sdim KnownOne.clearAllBits(); 606234353Sdim 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()); 615249423Sdim 616193323Sed if (Align > 0) 617263508Sdim 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); 624234353Sdim ComputeMaskedBits(I->getOperand(0), LocalKnownZero, LocalKnownOne, TD, 625234353Sdim 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); 631226633Sdim if (StructType *STy = dyn_cast<StructType>(*GTI)) { 632193323Sed // Handle struct member offset arithmetic. 633263508Sdim if (!TD) 634263508Sdim return; 635263508Sdim 636263508Sdim // Handle case when index is vector zeroinitializer 637263508Sdim Constant *CIndex = cast<Constant>(Index); 638263508Sdim if (CIndex->isZeroValue()) 639263508Sdim continue; 640263508Sdim 641263508Sdim if (CIndex->getType()->isVectorTy()) 642263508Sdim Index = CIndex->getSplatValue(); 643263508Sdim 644263508Sdim unsigned Idx = cast<ConstantInt>(Index)->getZExtValue(); 645193323Sed const StructLayout *SL = TD->getStructLayout(STy); 646193323Sed uint64_t Offset = SL->getElementOffset(Idx); 647263508Sdim TrailZ = std::min<unsigned>(TrailZ, 648263508Sdim countTrailingZeros(Offset)); 649193323Sed } else { 650193323Sed // Handle array index arithmetic. 651226633Sdim 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); 656234353Sdim ComputeMaskedBits(Index, LocalKnownZero, LocalKnownOne, TD, Depth+1); 657193323Sed TrailZ = std::min(TrailZ, 658263508Sdim unsigned(countTrailingZeros(TypeSize) + 659193323Sed LocalKnownZero.countTrailingOnes())); 660193323Sed } 661193323Sed } 662249423Sdim 663234353Sdim 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. 698234353Sdim 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); 702234353Sdim ComputeMaskedBits(L, KnownZero3, KnownOne3, TD, Depth+1); 703193323Sed 704234353Sdim 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. 720239462Sdim 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. 733234353Sdim ComputeMaskedBits(P->getIncomingValue(i), KnownZero2, KnownOne2, TD, 734234353Sdim 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; 752234353Sdim // If this call is undefined for 0, the result will be less than 2^n. 753234353Sdim if (II->getArgOperand(1) == ConstantInt::getTrue(II->getContext())) 754234353Sdim LowBits -= 1; 755193323Sed KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits); 756193323Sed break; 757193323Sed } 758234353Sdim case Intrinsic::ctpop: { 759234353Sdim unsigned LowBits = Log2_32(BitWidth)+1; 760234353Sdim KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits); 761234353Sdim break; 762234353Sdim } 763223017Sdim case Intrinsic::x86_sse42_crc32_64_64: 764223017Sdim KnownZero = APInt::getHighBitsSet(64, 32); 765223017Sdim break; 766193323Sed } 767193323Sed } 768193323Sed break; 769234353Sdim case Instruction::ExtractValue: 770234353Sdim if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I->getOperand(0))) { 771234353Sdim ExtractValueInst *EVI = cast<ExtractValueInst>(I); 772234353Sdim if (EVI->getNumIndices() != 1) break; 773234353Sdim if (EVI->getIndices()[0] == 0) { 774234353Sdim switch (II->getIntrinsicID()) { 775234353Sdim default: break; 776234353Sdim case Intrinsic::uadd_with_overflow: 777234353Sdim case Intrinsic::sadd_with_overflow: 778234353Sdim ComputeMaskedBitsAddSub(true, II->getArgOperand(0), 779234353Sdim II->getArgOperand(1), false, KnownZero, 780234353Sdim KnownOne, KnownZero2, KnownOne2, TD, Depth); 781234353Sdim break; 782234353Sdim case Intrinsic::usub_with_overflow: 783234353Sdim case Intrinsic::ssub_with_overflow: 784234353Sdim ComputeMaskedBitsAddSub(false, II->getArgOperand(0), 785234353Sdim II->getArgOperand(1), false, KnownZero, 786234353Sdim KnownOne, KnownZero2, KnownOne2, TD, Depth); 787234353Sdim break; 788234353Sdim case Intrinsic::umul_with_overflow: 789234353Sdim case Intrinsic::smul_with_overflow: 790234353Sdim ComputeMaskedBitsMul(II->getArgOperand(0), II->getArgOperand(1), 791234353Sdim false, KnownZero, KnownOne, 792234353Sdim KnownZero2, KnownOne2, TD, Depth); 793234353Sdim break; 794234353Sdim } 795234353Sdim } 796234353Sdim } 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, 803243830Sdim 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); 812234353Sdim ComputeMaskedBits(V, ZeroBits, OneBits, TD, Depth); 813218893Sdim KnownOne = OneBits[BitWidth - 1]; 814218893Sdim KnownZero = ZeroBits[BitWidth - 1]; 815218893Sdim} 816218893Sdim 817249423Sdim/// 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. 821249423Sdimbool llvm::isKnownToBeAPowerOfTwo(Value *V, bool OrZero, unsigned Depth) { 822234353Sdim if (Constant *C = dyn_cast<Constant>(V)) { 823234353Sdim if (C->isNullValue()) 824234353Sdim return OrZero; 825234353Sdim if (ConstantInt *CI = dyn_cast<ConstantInt>(C)) 826234353Sdim return CI->getValue().isPowerOf2(); 827234353Sdim // TODO: Handle vector constants. 828234353Sdim } 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 844234353Sdim Value *X = 0, *Y = 0; 845234353Sdim // A shift of a power of two is a power of two or zero. 846234353Sdim if (OrZero && (match(V, m_Shl(m_Value(X), m_Value())) || 847234353Sdim match(V, m_Shr(m_Value(X), m_Value())))) 848249423Sdim return isKnownToBeAPowerOfTwo(X, /*OrZero*/true, Depth); 849234353Sdim 850218893Sdim if (ZExtInst *ZI = dyn_cast<ZExtInst>(V)) 851249423Sdim return isKnownToBeAPowerOfTwo(ZI->getOperand(0), OrZero, Depth); 852218893Sdim 853218893Sdim if (SelectInst *SI = dyn_cast<SelectInst>(V)) 854249423Sdim return isKnownToBeAPowerOfTwo(SI->getTrueValue(), OrZero, Depth) && 855249423Sdim isKnownToBeAPowerOfTwo(SI->getFalseValue(), OrZero, Depth); 856218893Sdim 857234353Sdim if (OrZero && match(V, m_And(m_Value(X), m_Value(Y)))) { 858234353Sdim // A power of two and'd with anything is a power of two or zero. 859249423Sdim if (isKnownToBeAPowerOfTwo(X, /*OrZero*/true, Depth) || 860249423Sdim isKnownToBeAPowerOfTwo(Y, /*OrZero*/true, Depth)) 861234353Sdim return true; 862234353Sdim // X & (-X) is always a power of two or zero. 863234353Sdim if (match(X, m_Neg(m_Specific(Y))) || match(Y, m_Neg(m_Specific(X)))) 864234353Sdim return true; 865234353Sdim return false; 866234353Sdim } 867234353Sdim 868263508Sdim // Adding a power-of-two or zero to the same power-of-two or zero yields 869263508Sdim // either the original power-of-two, a larger power-of-two or zero. 870263508Sdim if (match(V, m_Add(m_Value(X), m_Value(Y)))) { 871263508Sdim OverflowingBinaryOperator *VOBO = cast<OverflowingBinaryOperator>(V); 872263508Sdim if (OrZero || VOBO->hasNoUnsignedWrap() || VOBO->hasNoSignedWrap()) { 873263508Sdim if (match(X, m_And(m_Specific(Y), m_Value())) || 874263508Sdim match(X, m_And(m_Value(), m_Specific(Y)))) 875263508Sdim if (isKnownToBeAPowerOfTwo(Y, OrZero, Depth)) 876263508Sdim return true; 877263508Sdim if (match(Y, m_And(m_Specific(X), m_Value())) || 878263508Sdim match(Y, m_And(m_Value(), m_Specific(X)))) 879263508Sdim if (isKnownToBeAPowerOfTwo(X, OrZero, Depth)) 880263508Sdim return true; 881263508Sdim 882263508Sdim unsigned BitWidth = V->getType()->getScalarSizeInBits(); 883263508Sdim APInt LHSZeroBits(BitWidth, 0), LHSOneBits(BitWidth, 0); 884263508Sdim ComputeMaskedBits(X, LHSZeroBits, LHSOneBits, 0, Depth); 885263508Sdim 886263508Sdim APInt RHSZeroBits(BitWidth, 0), RHSOneBits(BitWidth, 0); 887263508Sdim ComputeMaskedBits(Y, RHSZeroBits, RHSOneBits, 0, Depth); 888263508Sdim // If i8 V is a power of two or zero: 889263508Sdim // ZeroBits: 1 1 1 0 1 1 1 1 890263508Sdim // ~ZeroBits: 0 0 0 1 0 0 0 0 891263508Sdim if ((~(LHSZeroBits & RHSZeroBits)).isPowerOf2()) 892263508Sdim // If OrZero isn't set, we cannot give back a zero result. 893263508Sdim // Make sure either the LHS or RHS has a bit set. 894263508Sdim if (OrZero || RHSOneBits.getBoolValue() || LHSOneBits.getBoolValue()) 895263508Sdim return true; 896263508Sdim } 897263508Sdim } 898263508Sdim 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). 902234353Sdim if (match(V, m_Exact(m_LShr(m_Value(), m_Value()))) || 903234353Sdim match(V, m_Exact(m_UDiv(m_Value(), m_Value())))) { 904249423Sdim return isKnownToBeAPowerOfTwo(cast<Operator>(V)->getOperand(0), OrZero, Depth); 905221345Sdim } 906221345Sdim 907218893Sdim return false; 908218893Sdim} 909218893Sdim 910249423Sdim/// \brief Test whether a GEP's result is known to be non-null. 911249423Sdim/// 912249423Sdim/// Uses properties inherent in a GEP to try to determine whether it is known 913249423Sdim/// to be non-null. 914249423Sdim/// 915249423Sdim/// Currently this routine does not support vector GEPs. 916249423Sdimstatic bool isGEPKnownNonNull(GEPOperator *GEP, const DataLayout *DL, 917249423Sdim unsigned Depth) { 918249423Sdim if (!GEP->isInBounds() || GEP->getPointerAddressSpace() != 0) 919249423Sdim return false; 920249423Sdim 921249423Sdim // FIXME: Support vector-GEPs. 922249423Sdim assert(GEP->getType()->isPointerTy() && "We only support plain pointer GEP"); 923249423Sdim 924249423Sdim // If the base pointer is non-null, we cannot walk to a null address with an 925249423Sdim // inbounds GEP in address space zero. 926249423Sdim if (isKnownNonZero(GEP->getPointerOperand(), DL, Depth)) 927249423Sdim return true; 928249423Sdim 929249423Sdim // Past this, if we don't have DataLayout, we can't do much. 930249423Sdim if (!DL) 931249423Sdim return false; 932249423Sdim 933249423Sdim // Walk the GEP operands and see if any operand introduces a non-zero offset. 934249423Sdim // If so, then the GEP cannot produce a null pointer, as doing so would 935249423Sdim // inherently violate the inbounds contract within address space zero. 936249423Sdim for (gep_type_iterator GTI = gep_type_begin(GEP), GTE = gep_type_end(GEP); 937249423Sdim GTI != GTE; ++GTI) { 938249423Sdim // Struct types are easy -- they must always be indexed by a constant. 939249423Sdim if (StructType *STy = dyn_cast<StructType>(*GTI)) { 940249423Sdim ConstantInt *OpC = cast<ConstantInt>(GTI.getOperand()); 941249423Sdim unsigned ElementIdx = OpC->getZExtValue(); 942249423Sdim const StructLayout *SL = DL->getStructLayout(STy); 943249423Sdim uint64_t ElementOffset = SL->getElementOffset(ElementIdx); 944249423Sdim if (ElementOffset > 0) 945249423Sdim return true; 946249423Sdim continue; 947249423Sdim } 948249423Sdim 949249423Sdim // If we have a zero-sized type, the index doesn't matter. Keep looping. 950249423Sdim if (DL->getTypeAllocSize(GTI.getIndexedType()) == 0) 951249423Sdim continue; 952249423Sdim 953249423Sdim // Fast path the constant operand case both for efficiency and so we don't 954249423Sdim // increment Depth when just zipping down an all-constant GEP. 955249423Sdim if (ConstantInt *OpC = dyn_cast<ConstantInt>(GTI.getOperand())) { 956249423Sdim if (!OpC->isZero()) 957249423Sdim return true; 958249423Sdim continue; 959249423Sdim } 960249423Sdim 961249423Sdim // We post-increment Depth here because while isKnownNonZero increments it 962249423Sdim // as well, when we pop back up that increment won't persist. We don't want 963249423Sdim // to recurse 10k times just because we have 10k GEP operands. We don't 964249423Sdim // bail completely out because we want to handle constant GEPs regardless 965249423Sdim // of depth. 966249423Sdim if (Depth++ >= MaxDepth) 967249423Sdim continue; 968249423Sdim 969249423Sdim if (isKnownNonZero(GTI.getOperand(), DL, Depth)) 970249423Sdim return true; 971249423Sdim } 972249423Sdim 973249423Sdim return false; 974249423Sdim} 975249423Sdim 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. 980243830Sdimbool 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. 992234353Sdim if (Depth++ >= MaxDepth) 993218893Sdim return false; 994218893Sdim 995249423Sdim // Check for pointer simplifications. 996249423Sdim if (V->getType()->isPointerTy()) { 997249423Sdim if (isKnownNonNull(V)) 998249423Sdim return true; 999249423Sdim if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) 1000249423Sdim if (isGEPKnownNonNull(GEP, TD, Depth)) 1001249423Sdim return true; 1002249423Sdim } 1003218893Sdim 1004249423Sdim unsigned BitWidth = getBitWidth(V->getType()->getScalarType(), TD); 1005249423Sdim 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. 1019234353Sdim 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); 1025234353Sdim 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. 1033234353Sdim 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. 1043234353Sdim else if (match(V, m_Exact(m_IDiv(m_Value(X), m_Value())))) { 1044234353Sdim 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. 1067234353Sdim 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. 1072234353Sdim 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. 1078249423Sdim if (XKnownNonNegative && isKnownToBeAPowerOfTwo(Y, /*OrZero*/false, Depth)) 1079218893Sdim return true; 1080249423Sdim if (YKnownNonNegative && isKnownToBeAPowerOfTwo(X, /*OrZero*/false, Depth)) 1081218893Sdim return true; 1082218893Sdim } 1083234353Sdim // X * Y. 1084234353Sdim else if (match(V, m_Mul(m_Value(X), m_Value(Y)))) { 1085234353Sdim OverflowingBinaryOperator *BO = cast<OverflowingBinaryOperator>(V); 1086234353Sdim // If X and Y are non-zero then so is X * Y as long as the multiplication 1087234353Sdim // does not overflow. 1088234353Sdim if ((BO->hasNoSignedWrap() || BO->hasNoUnsignedWrap()) && 1089234353Sdim isKnownNonZero(X, TD, Depth) && isKnownNonZero(Y, TD, Depth)) 1090234353Sdim return true; 1091234353Sdim } 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); 1102234353Sdim 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, 1116243830Sdim const DataLayout *TD, unsigned Depth) { 1117193323Sed APInt KnownZero(Mask.getBitWidth(), 0), KnownOne(Mask.getBitWidth(), 0); 1118234353Sdim ComputeMaskedBits(V, KnownZero, KnownOne, TD, Depth); 1119249423Sdim 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/// 1133243830Sdimunsigned llvm::ComputeNumSignBits(Value *V, const DataLayout *TD, 1134198090Srdivacky unsigned Depth) { 1135203954Srdivacky assert((TD || V->getType()->isIntOrIntVectorTy()) && 1136243830Sdim "ComputeNumSignBits requires a DataLayout object to operate " 1137194710Sed "on non-integer values!"); 1138226633Sdim 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. 1149249423Sdim 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; 1156249423Sdim 1157234353Sdim case Instruction::AShr: { 1158193323Sed Tmp = ComputeNumSignBits(U->getOperand(0), TD, Depth+1); 1159234353Sdim // ashr X, C -> adds C sign bits. Vectors too. 1160234353Sdim const APInt *ShAmt; 1161234353Sdim if (match(U->getOperand(1), m_APInt(ShAmt))) { 1162234353Sdim Tmp += ShAmt->getZExtValue(); 1163193323Sed if (Tmp > TyBits) Tmp = TyBits; 1164193323Sed } 1165193323Sed return Tmp; 1166234353Sdim } 1167234353Sdim case Instruction::Shl: { 1168234353Sdim const APInt *ShAmt; 1169234353Sdim if (match(U->getOperand(1), m_APInt(ShAmt))) { 1170193323Sed // shl destroys sign bits. 1171193323Sed Tmp = ComputeNumSignBits(U->getOperand(0), TD, Depth+1); 1172234353Sdim Tmp2 = ShAmt->getZExtValue(); 1173234353Sdim if (Tmp2 >= TyBits || // Bad shift. 1174234353Sdim Tmp2 >= Tmp) break; // Shifted all sign bits out. 1175234353Sdim return Tmp - Tmp2; 1176193323Sed } 1177193323Sed break; 1178234353Sdim } 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); 1198249423Sdim 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. 1204249423Sdim 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); 1209234353Sdim ComputeMaskedBits(U->getOperand(0), KnownZero, KnownOne, TD, Depth+1); 1210249423Sdim 1211193323Sed // If the input is known to be 0 or 1, the output is 0/-1, which is all 1212193323Sed // sign bits set. 1213234353Sdim if ((KnownZero | APInt(TyBits, 1)).isAllOnesValue()) 1214193323Sed return TyBits; 1215249423Sdim 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 } 1221249423Sdim 1222193323Sed Tmp2 = ComputeNumSignBits(U->getOperand(1), TD, Depth+1); 1223193323Sed if (Tmp2 == 1) return 1; 1224202375Srdivacky return std::min(Tmp, Tmp2)-1; 1225249423Sdim 1226193323Sed case Instruction::Sub: 1227193323Sed Tmp2 = ComputeNumSignBits(U->getOperand(1), TD, Depth+1); 1228193323Sed if (Tmp2 == 1) return 1; 1229249423Sdim 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); 1234234353Sdim 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. 1237234353Sdim if ((KnownZero | APInt(TyBits, 1)).isAllOnesValue()) 1238193323Sed return TyBits; 1239249423Sdim 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; 1244249423Sdim 1245193323Sed // Otherwise, we treat this like a SUB. 1246193323Sed } 1247249423Sdim 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; 1253249423Sdim 1254202375Srdivacky case Instruction::PHI: { 1255202375Srdivacky PHINode *PN = cast<PHINode>(U); 1256202375Srdivacky // Don't analyze large in-degree PHIs. 1257202375Srdivacky if (PN->getNumIncomingValues() > 4) break; 1258249423Sdim 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 } 1275249423Sdim 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); 1279234353Sdim APInt Mask; 1280234353Sdim ComputeMaskedBits(V, KnownZero, KnownOne, TD, Depth); 1281249423Sdim 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 } 1290249423Sdim 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 1312226633Sdim Type *T = V->getType(); 1313199481Srdivacky 1314199481Srdivacky ConstantInt *CI = dyn_cast<ConstantInt>(V); 1315199481Srdivacky 1316199481Srdivacky if (Base == 0) 1317199481Srdivacky return false; 1318249423Sdim 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); 1334249423Sdim return true; 1335199481Srdivacky } 1336249423Sdim 1337199481Srdivacky if (Depth == MaxDepth) return false; // Limit search depth. 1338249423Sdim 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)) { 1370249423Sdim if (Op1C->getType()->getPrimitiveSizeInBits() < 1371212904Sdim MulC->getType()->getPrimitiveSizeInBits()) 1372212904Sdim Op1C = ConstantExpr::getZExt(Op1C, MulC->getType()); 1373249423Sdim if (Op1C->getType()->getPrimitiveSizeInBits() > 1374212904Sdim MulC->getType()->getPrimitiveSizeInBits()) 1375212904Sdim MulC = ConstantExpr::getZExt(MulC, Op1C->getType()); 1376249423Sdim 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)) { 1394249423Sdim if (Op0C->getType()->getPrimitiveSizeInBits() < 1395212904Sdim MulC->getType()->getPrimitiveSizeInBits()) 1396212904Sdim Op0C = ConstantExpr::getZExt(Op0C, MulC->getType()); 1397249423Sdim if (Op0C->getType()->getPrimitiveSizeInBits() > 1398212904Sdim MulC->getType()->getPrimitiveSizeInBits()) 1399212904Sdim MulC = ConstantExpr::getZExt(MulC, Op0C->getType()); 1400249423Sdim 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 1420249423Sdim/// 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(); 1429249423Sdim 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; 1435249423Sdim 1436249423Sdim // Check if the nsz fast-math flag is set 1437249423Sdim if (const FPMathOperator *FPO = dyn_cast<FPMathOperator>(I)) 1438249423Sdim if (FPO->hasNoSignedZeros()) 1439249423Sdim return true; 1440249423Sdim 1441193323Sed // (add x, 0.0) is guaranteed to return +0.0, not -0.0. 1442249423Sdim if (I->getOpcode() == Instruction::FAdd) 1443249423Sdim if (ConstantFP *CFP = dyn_cast<ConstantFP>(I->getOperand(1))) 1444249423Sdim if (CFP->isNullValue()) 1445249423Sdim return true; 1446249423Sdim 1447193323Sed // sitofp and uitofp turn into +0.0 for zero. 1448193323Sed if (isa<SIToFPInst>(I) || isa<UIToFPInst>(I)) 1449193323Sed return true; 1450249423Sdim 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); 1455249423Sdim 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 } 1470249423Sdim 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())); 1487249423Sdim 1488218893Sdim // Constant float and double values can be handled as integer values if the 1489249423Sdim // 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 } 1497249423Sdim 1498249423Sdim // 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); 1512249423Sdim 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 } 1520249423Sdim 1521234353Sdim // A ConstantDataArray/Vector is splatable if all its members are equal and 1522234353Sdim // also splatable. 1523234353Sdim if (ConstantDataSequential *CA = dyn_cast<ConstantDataSequential>(V)) { 1524234353Sdim Value *Elt = CA->getElementAsConstant(0); 1525234353Sdim Value *Val = isBytewiseValue(Elt); 1526218893Sdim if (!Val) 1527218893Sdim return 0; 1528249423Sdim 1529234353Sdim for (unsigned I = 1, E = CA->getNumElements(); I != E; ++I) 1530234353Sdim if (CA->getElementAsConstant(I) != Elt) 1531218893Sdim return 0; 1532249423Sdim 1533218893Sdim return Val; 1534218893Sdim } 1535234353Sdim 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. 1552226633Sdimstatic Value *BuildSubAggregate(Value *From, Value* To, Type *IndexedType, 1553263508Sdim SmallVectorImpl<unsigned> &Idxs, 1554198090Srdivacky unsigned IdxSkip, 1555198090Srdivacky Instruction *InsertBefore) { 1556249423Sdim 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. 1587249423Sdim 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 1595226633Sdim 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!"); 1614226633Sdim 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 1632234353Sdim // recursion). 1633224145Sdim if (idx_range.empty()) 1634193323Sed return V; 1635234353Sdim // We have indices, so V should have an indexable type. 1636234353Sdim assert((V->getType()->isStructTy() || V->getType()->isArrayTy()) && 1637234353Sdim "Not looking at a struct or array?"); 1638234353Sdim assert(ExtractValueInst::getIndexedType(V->getType(), idx_range) && 1639234353Sdim "Invalid indices for type?"); 1640198090Srdivacky 1641234353Sdim if (Constant *C = dyn_cast<Constant>(V)) { 1642234353Sdim C = C->getAggregateElement(idx_range[0]); 1643234353Sdim if (C == 0) return 0; 1644234353Sdim return FindInsertedValue(C, idx_range.slice(1), InsertBefore); 1645234353Sdim } 1646249423Sdim 1647234353Sdim 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()) { 1654234353Sdim // We can't handle this without inserting insertvalues 1655234353Sdim if (!InsertBefore) 1656193323Sed return 0; 1657234353Sdim 1658234353Sdim // The requested index identifies a part of a nested aggregate. Handle 1659234353Sdim // this specially. For example, 1660234353Sdim // %A = insertvalue { i32, {i32, i32 } } undef, i32 10, 1, 0 1661234353Sdim // %B = insertvalue { i32, {i32, i32 } } %A, i32 11, 1, 1 1662234353Sdim // %C = extractvalue {i32, { i32, i32 } } %B, 1 1663234353Sdim // This can be changed into 1664234353Sdim // %A = insertvalue {i32, i32 } undef, i32 10, 0 1665234353Sdim // %C = insertvalue {i32, i32 } %A, i32 11, 1 1666234353Sdim // which allows the unused 0,0 element from the nested struct to be 1667234353Sdim // removed. 1668234353Sdim return BuildSubAggregate(V, makeArrayRef(idx_range.begin(), req_idx), 1669234353Sdim InsertBefore); 1670193323Sed } 1671249423Sdim 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(), 1683226633Sdim makeArrayRef(req_idx, idx_range.end()), 1684199989Srdivacky InsertBefore); 1685234353Sdim } 1686249423Sdim 1687234353Sdim 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. 1691249423Sdim 1692249423Sdim // 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()); 1699249423Sdim 1700193323Sed // Add requested indices 1701224145Sdim Idxs.append(idx_range.begin(), idx_range.end()); 1702193323Sed 1703249423Sdim assert(Idxs.size() == size 1704193323Sed && "Number of indices added not correct?"); 1705249423Sdim 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, 1717263508Sdim const DataLayout *DL) { 1718249423Sdim // Without DataLayout, conservatively assume 64-bit offsets, which is 1719249423Sdim // the widest we support. 1720263508Sdim unsigned BitWidth = DL ? DL->getPointerTypeSizeInBits(Ptr->getType()) : 64; 1721249423Sdim APInt ByteOffset(BitWidth, 0); 1722249423Sdim while (1) { 1723249423Sdim if (Ptr->getType()->isVectorTy()) 1724249423Sdim break; 1725249423Sdim 1726249423Sdim if (GEPOperator *GEP = dyn_cast<GEPOperator>(Ptr)) { 1727263508Sdim if (DL) { 1728263508Sdim APInt GEPOffset(BitWidth, 0); 1729263508Sdim if (!GEP->accumulateConstantOffset(*DL, GEPOffset)) 1730263508Sdim break; 1731263508Sdim 1732263508Sdim ByteOffset += GEPOffset; 1733263508Sdim } 1734263508Sdim 1735249423Sdim Ptr = GEP->getPointerOperand(); 1736249423Sdim } else if (Operator::getOpcode(Ptr) == Instruction::BitCast) { 1737249423Sdim Ptr = cast<Operator>(Ptr)->getOperand(0); 1738249423Sdim } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(Ptr)) { 1739249423Sdim if (GA->mayBeOverridden()) 1740249423Sdim break; 1741249423Sdim Ptr = GA->getAliasee(); 1742218893Sdim } else { 1743249423Sdim break; 1744218893Sdim } 1745218893Sdim } 1746249423Sdim Offset = ByteOffset.getSExtValue(); 1747249423Sdim return Ptr; 1748218893Sdim} 1749218893Sdim 1750218893Sdim 1751234353Sdim/// 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. 1754234353Sdimbool llvm::getConstantStringInfo(const Value *V, StringRef &Str, 1755234353Sdim uint64_t Offset, bool TrimAtNul) { 1756234353Sdim assert(V); 1757193323Sed 1758234353Sdim // Look through bitcast instructions and geps. 1759234353Sdim V = V->stripPointerCasts(); 1760249423Sdim 1761234353Sdim // If the value is a GEP instructionor constant expression, treat it as an 1762234353Sdim // offset. 1763234353Sdim 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; 1767249423Sdim 1768193323Sed // Make sure the index-ee is a pointer to array of i8. 1769226633Sdim PointerType *PT = cast<PointerType>(GEP->getOperand(0)->getType()); 1770226633Sdim ArrayType *AT = dyn_cast<ArrayType>(PT->getElementType()); 1771203954Srdivacky if (AT == 0 || !AT->getElementType()->isIntegerTy(8)) 1772193323Sed return false; 1773249423Sdim 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; 1779249423Sdim 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; 1788234353Sdim return getConstantStringInfo(GEP->getOperand(0), Str, StartIdx+Offset); 1789193323Sed } 1790234353Sdim 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. 1794234353Sdim const GlobalVariable *GV = dyn_cast<GlobalVariable>(V); 1795198090Srdivacky if (!GV || !GV->isConstant() || !GV->hasDefinitiveInitializer()) 1796193323Sed return false; 1797234353Sdim 1798234353Sdim // Handle the all-zeros case 1799234353Sdim 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. 1802234353Sdim Str = ""; 1803193323Sed return true; 1804193323Sed } 1805249423Sdim 1806193323Sed // Must be a Constant Array 1807234353Sdim const ConstantDataArray *Array = 1808234353Sdim dyn_cast<ConstantDataArray>(GV->getInitializer()); 1809234353Sdim if (Array == 0 || !Array->isString()) 1810193323Sed return false; 1811249423Sdim 1812193323Sed // Get the number of elements in the array 1813234353Sdim uint64_t NumElts = Array->getType()->getArrayNumElements(); 1814234353Sdim 1815234353Sdim // Start out with the entire array in the StringRef. 1816234353Sdim Str = Array->getAsString(); 1817234353Sdim 1818193323Sed if (Offset > NumElts) 1819193323Sed return false; 1820249423Sdim 1821234353Sdim // Skip over 'offset' bytes. 1822234353Sdim Str = Str.substr(Offset); 1823249423Sdim 1824234353Sdim if (TrimAtNul) { 1825234353Sdim // Trim off the \0 and anything after it. If the array is not nul 1826234353Sdim // terminated, we just return the whole end of string. The client may know 1827234353Sdim // some other way that the string is length-bound. 1828234353Sdim 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. 1841234353Sdim 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 } 1877249423Sdim 1878234353Sdim // Otherwise, see if we can read the string. 1879234353Sdim StringRef StrData; 1880234353Sdim if (!getConstantStringInfo(V, StrData)) 1881204792Srdivacky return 0; 1882204792Srdivacky 1883234353Sdim 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 * 1899243830Sdimllvm::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 1927239462Sdimvoid 1928239462Sdimllvm::GetUnderlyingObjects(Value *V, 1929239462Sdim SmallVectorImpl<Value *> &Objects, 1930243830Sdim const DataLayout *TD, 1931239462Sdim unsigned MaxLookup) { 1932239462Sdim SmallPtrSet<Value *, 4> Visited; 1933239462Sdim SmallVector<Value *, 4> Worklist; 1934239462Sdim Worklist.push_back(V); 1935239462Sdim do { 1936239462Sdim Value *P = Worklist.pop_back_val(); 1937239462Sdim P = GetUnderlyingObject(P, TD, MaxLookup); 1938239462Sdim 1939239462Sdim if (!Visited.insert(P)) 1940239462Sdim continue; 1941239462Sdim 1942239462Sdim if (SelectInst *SI = dyn_cast<SelectInst>(P)) { 1943239462Sdim Worklist.push_back(SI->getTrueValue()); 1944239462Sdim Worklist.push_back(SI->getFalseValue()); 1945239462Sdim continue; 1946239462Sdim } 1947239462Sdim 1948239462Sdim if (PHINode *PN = dyn_cast<PHINode>(P)) { 1949239462Sdim for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 1950239462Sdim Worklist.push_back(PN->getIncomingValue(i)); 1951239462Sdim continue; 1952239462Sdim } 1953239462Sdim 1954239462Sdim Objects.push_back(P); 1955239462Sdim } while (!Worklist.empty()); 1956239462Sdim} 1957239462Sdim 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} 1973234353Sdim 1974234353Sdimbool llvm::isSafeToSpeculativelyExecute(const Value *V, 1975243830Sdim const DataLayout *TD) { 1976234353Sdim const Operator *Inst = dyn_cast<Operator>(V); 1977234353Sdim if (!Inst) 1978234353Sdim return false; 1979234353Sdim 1980234353Sdim for (unsigned i = 0, e = Inst->getNumOperands(); i != e; ++i) 1981234353Sdim if (Constant *C = dyn_cast<Constant>(Inst->getOperand(i))) 1982234353Sdim if (C->canTrap()) 1983234353Sdim return false; 1984234353Sdim 1985234353Sdim switch (Inst->getOpcode()) { 1986234353Sdim default: 1987234353Sdim return true; 1988234353Sdim case Instruction::UDiv: 1989234353Sdim case Instruction::URem: 1990234353Sdim // x / y is undefined if y == 0, but calcuations like x / 3 are safe. 1991234353Sdim return isKnownNonZero(Inst->getOperand(1), TD); 1992234353Sdim case Instruction::SDiv: 1993234353Sdim case Instruction::SRem: { 1994234353Sdim Value *Op = Inst->getOperand(1); 1995234353Sdim // x / y is undefined if y == 0 1996234353Sdim if (!isKnownNonZero(Op, TD)) 1997234353Sdim return false; 1998234353Sdim // x / y might be undefined if y == -1 1999234353Sdim unsigned BitWidth = getBitWidth(Op->getType(), TD); 2000234353Sdim if (BitWidth == 0) 2001234353Sdim return false; 2002234353Sdim APInt KnownZero(BitWidth, 0); 2003234353Sdim APInt KnownOne(BitWidth, 0); 2004234353Sdim ComputeMaskedBits(Op, KnownZero, KnownOne, TD); 2005234353Sdim return !!KnownZero; 2006234353Sdim } 2007234353Sdim case Instruction::Load: { 2008234353Sdim const LoadInst *LI = cast<LoadInst>(Inst); 2009234353Sdim if (!LI->isUnordered()) 2010234353Sdim return false; 2011234353Sdim return LI->getPointerOperand()->isDereferenceablePointer(); 2012234353Sdim } 2013234353Sdim case Instruction::Call: { 2014234353Sdim if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) { 2015234353Sdim switch (II->getIntrinsicID()) { 2016234353Sdim // These synthetic intrinsics have no side-effects, and just mark 2017234353Sdim // information about their operands. 2018234353Sdim // FIXME: There are other no-op synthetic instructions that potentially 2019234353Sdim // should be considered at least *safe* to speculate... 2020234353Sdim case Intrinsic::dbg_declare: 2021234353Sdim case Intrinsic::dbg_value: 2022234353Sdim return true; 2023234353Sdim 2024234353Sdim case Intrinsic::bswap: 2025234353Sdim case Intrinsic::ctlz: 2026234353Sdim case Intrinsic::ctpop: 2027234353Sdim case Intrinsic::cttz: 2028234353Sdim case Intrinsic::objectsize: 2029234353Sdim case Intrinsic::sadd_with_overflow: 2030234353Sdim case Intrinsic::smul_with_overflow: 2031234353Sdim case Intrinsic::ssub_with_overflow: 2032234353Sdim case Intrinsic::uadd_with_overflow: 2033234353Sdim case Intrinsic::umul_with_overflow: 2034234353Sdim case Intrinsic::usub_with_overflow: 2035234353Sdim return true; 2036234353Sdim // TODO: some fp intrinsics are marked as having the same error handling 2037234353Sdim // as libm. They're safe to speculate when they won't error. 2038234353Sdim // TODO: are convert_{from,to}_fp16 safe? 2039234353Sdim // TODO: can we list target-specific intrinsics here? 2040234353Sdim default: break; 2041234353Sdim } 2042234353Sdim } 2043234353Sdim return false; // The called function could have undefined behavior or 2044234353Sdim // side-effects, even if marked readnone nounwind. 2045234353Sdim } 2046234353Sdim case Instruction::VAArg: 2047234353Sdim case Instruction::Alloca: 2048234353Sdim case Instruction::Invoke: 2049234353Sdim case Instruction::PHI: 2050234353Sdim case Instruction::Store: 2051234353Sdim case Instruction::Ret: 2052234353Sdim case Instruction::Br: 2053234353Sdim case Instruction::IndirectBr: 2054234353Sdim case Instruction::Switch: 2055234353Sdim case Instruction::Unreachable: 2056234353Sdim case Instruction::Fence: 2057234353Sdim case Instruction::LandingPad: 2058234353Sdim case Instruction::AtomicRMW: 2059234353Sdim case Instruction::AtomicCmpXchg: 2060234353Sdim case Instruction::Resume: 2061234353Sdim return false; // Misc instructions which have effects 2062234353Sdim } 2063234353Sdim} 2064249423Sdim 2065249423Sdim/// isKnownNonNull - Return true if we know that the specified value is never 2066249423Sdim/// null. 2067263508Sdimbool llvm::isKnownNonNull(const Value *V, const TargetLibraryInfo *TLI) { 2068249423Sdim // Alloca never returns null, malloc might. 2069249423Sdim if (isa<AllocaInst>(V)) return true; 2070249423Sdim 2071249423Sdim // A byval argument is never null. 2072249423Sdim if (const Argument *A = dyn_cast<Argument>(V)) 2073249423Sdim return A->hasByValAttr(); 2074249423Sdim 2075249423Sdim // Global values are not null unless extern weak. 2076249423Sdim if (const GlobalValue *GV = dyn_cast<GlobalValue>(V)) 2077249423Sdim return !GV->hasExternalWeakLinkage(); 2078263508Sdim 2079263508Sdim // operator new never returns null. 2080263508Sdim if (isOperatorNewLikeFn(V, TLI, /*LookThroughBitCast=*/true)) 2081263508Sdim return true; 2082263508Sdim 2083249423Sdim return false; 2084249423Sdim} 2085