X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FValueTracking.cpp;h=58adc26a1d7543589b770c52bd251744bb47e06b;hb=618c1dbd293d15ee19f61b1156ab8086ad28311a;hp=5320fa0768db86f1387c2c7eb5f5f32c956ad4c7;hpb=227fba11ca168225d913d1cea94a05b883092e76;p=oota-llvm.git diff --git a/lib/Analysis/ValueTracking.cpp b/lib/Analysis/ValueTracking.cpp index 5320fa0768d..58adc26a1d7 100644 --- a/lib/Analysis/ValueTracking.cpp +++ b/lib/Analysis/ValueTracking.cpp @@ -34,7 +34,7 @@ const unsigned MaxDepth = 6; /// getBitWidth - Returns the bitwidth of the given scalar or pointer type (if /// unknown returns 0). For vector types, returns the element type's bitwidth. -static unsigned getBitWidth(const Type *Ty, const TargetData *TD) { +static unsigned getBitWidth(Type *Ty, const TargetData *TD) { if (unsigned BitWidth = Ty->getScalarSizeInBits()) return BitWidth; assert(isa(Ty) && "Expected a pointer type!"); @@ -103,14 +103,16 @@ void llvm::ComputeMaskedBits(Value *V, const APInt &Mask, if (GlobalValue *GV = dyn_cast(V)) { unsigned Align = GV->getAlignment(); if (Align == 0 && TD && GV->getType()->getElementType()->isSized()) { - const Type *ObjectType = GV->getType()->getElementType(); - // If the object is defined in the current Module, we'll be giving - // it the preferred alignment. Otherwise, we have to assume that it - // may only have the minimum ABI alignment. - if (!GV->isDeclaration() && !GV->mayBeOverridden()) - Align = TD->getPrefTypeAlignment(ObjectType); - else - Align = TD->getABITypeAlignment(ObjectType); + if (GlobalVariable *GVar = dyn_cast(GV)) { + Type *ObjectType = GVar->getType()->getElementType(); + // If the object is defined in the current Module, we'll be giving + // it the preferred alignment. Otherwise, we have to assume that it + // may only have the minimum ABI alignment. + if (!GVar->isDeclaration() && !GVar->isWeakForLinker()) + Align = TD->getPreferredAlignment(GVar); + else + Align = TD->getABITypeAlignment(ObjectType); + } } if (Align > 0) KnownZero = Mask & APInt::getLowBitsSet(BitWidth, @@ -131,8 +133,18 @@ void llvm::ComputeMaskedBits(Value *V, const APInt &Mask, } return; } + + if (Argument *A = dyn_cast(V)) { + // Get alignment information off byval arguments if specified in the IR. + if (A->hasByValAttr()) + if (unsigned Align = A->getParamAlignment()) + KnownZero = Mask & APInt::getLowBitsSet(BitWidth, + CountTrailingZeros_32(Align)); + return; + } - KnownZero.clearAllBits(); KnownOne.clearAllBits(); // Start out not knowing anything. + // Start out not knowing anything. + KnownZero.clearAllBits(); KnownOne.clearAllBits(); if (Depth == MaxDepth || Mask == 0) return; // Limit search depth. @@ -191,9 +203,36 @@ void llvm::ComputeMaskedBits(Value *V, const APInt &Mask, ComputeMaskedBits(I->getOperand(1), Mask2, KnownZero, KnownOne, TD,Depth+1); ComputeMaskedBits(I->getOperand(0), Mask2, KnownZero2, KnownOne2, TD, Depth+1); - assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); - assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); - + assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); + assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); + + bool isKnownNegative = false; + bool isKnownNonNegative = false; + // If the multiplication is known not to overflow, compute the sign bit. + if (Mask.isNegative() && + cast(I)->hasNoSignedWrap()) { + Value *Op1 = I->getOperand(1), *Op2 = I->getOperand(0); + if (Op1 == Op2) { + // The product of a number with itself is non-negative. + isKnownNonNegative = true; + } else { + bool isKnownNonNegative1 = KnownZero.isNegative(); + bool isKnownNonNegative2 = KnownZero2.isNegative(); + bool isKnownNegative1 = KnownOne.isNegative(); + bool isKnownNegative2 = KnownOne2.isNegative(); + // The product of two numbers with the same sign is non-negative. + isKnownNonNegative = (isKnownNegative1 && isKnownNegative2) || + (isKnownNonNegative1 && isKnownNonNegative2); + // The product of a negative number and a non-negative number is either + // negative or zero. + if (!isKnownNonNegative) + isKnownNegative = (isKnownNegative1 && isKnownNonNegative2 && + isKnownNonZero(Op2, TD, Depth)) || + (isKnownNegative2 && isKnownNonNegative1 && + isKnownNonZero(Op1, TD, Depth)); + } + } + // If low bits are zero in either operand, output low known-0 bits. // Also compute a conserative estimate for high known-0 bits. // More trickiness is possible, but this is sufficient for the @@ -210,6 +249,17 @@ void llvm::ComputeMaskedBits(Value *V, const APInt &Mask, KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) | APInt::getHighBitsSet(BitWidth, LeadZ); KnownZero &= Mask; + + // Only make use of no-wrap flags if we failed to compute the sign bit + // directly. This matters if the multiplication always overflows, in + // which case we prefer to follow the result of the direct computation, + // though as the program is invoking undefined behaviour we can choose + // whatever we like here. + if (isKnownNonNegative && !KnownOne.isNegative()) + KnownZero.setBit(BitWidth - 1); + else if (isKnownNegative && !KnownZero.isNegative()) + KnownOne.setBit(BitWidth - 1); + return; } case Instruction::UDiv: { @@ -258,7 +308,7 @@ void llvm::ComputeMaskedBits(Value *V, const APInt &Mask, // FALL THROUGH and handle them the same as zext/trunc. case Instruction::ZExt: case Instruction::Trunc: { - const Type *SrcTy = I->getOperand(0)->getType(); + Type *SrcTy = I->getOperand(0)->getType(); unsigned SrcBitWidth; // Note that we handle pointer operands here because of inttoptr/ptrtoint @@ -281,7 +331,7 @@ void llvm::ComputeMaskedBits(Value *V, const APInt &Mask, return; } case Instruction::BitCast: { - const Type *SrcTy = I->getOperand(0)->getType(); + Type *SrcTy = I->getOperand(0)->getType(); if ((SrcTy->isIntegerTy() || SrcTy->isPointerTy()) && // TODO: For now, not handling conversions like: // (bitcast i64 %x to <2 x i32>) @@ -429,6 +479,29 @@ void llvm::ComputeMaskedBits(Value *V, const APInt &Mask, KnownZero |= LHSKnownZero & Mask; KnownOne |= LHSKnownOne & Mask; } + + // Are we still trying to solve for the sign bit? + if (Mask.isNegative() && !KnownZero.isNegative() && !KnownOne.isNegative()){ + OverflowingBinaryOperator *OBO = cast(I); + if (OBO->hasNoSignedWrap()) { + if (I->getOpcode() == Instruction::Add) { + // Adding two positive numbers can't wrap into negative + if (LHSKnownZero.isNegative() && KnownZero2.isNegative()) + KnownZero |= APInt::getSignBit(BitWidth); + // and adding two negative numbers can't wrap into positive. + else if (LHSKnownOne.isNegative() && KnownOne2.isNegative()) + KnownOne |= APInt::getSignBit(BitWidth); + } else { + // Subtracting a negative number from a positive one can't wrap + if (LHSKnownZero.isNegative() && KnownOne2.isNegative()) + KnownZero |= APInt::getSignBit(BitWidth); + // neither can subtracting a positive number from a negative one. + else if (LHSKnownOne.isNegative() && KnownZero2.isNegative()) + KnownOne |= APInt::getSignBit(BitWidth); + } + } + } + return; } case Instruction::SRem: @@ -460,6 +533,19 @@ void llvm::ComputeMaskedBits(Value *V, const APInt &Mask, assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); } } + + // The sign bit is the LHS's sign bit, except when the result of the + // remainder is zero. + if (Mask.isNegative() && KnownZero.isNonNegative()) { + APInt Mask2 = APInt::getSignBit(BitWidth); + APInt LHSKnownZero(BitWidth, 0), LHSKnownOne(BitWidth, 0); + ComputeMaskedBits(I->getOperand(0), Mask2, LHSKnownZero, LHSKnownOne, TD, + Depth+1); + // If it's known zero, our sign bit is also zero. + if (LHSKnownZero.isNegative()) + KnownZero |= LHSKnownZero; + } + break; case Instruction::URem: { if (ConstantInt *Rem = dyn_cast(I->getOperand(1))) { @@ -513,7 +599,7 @@ void llvm::ComputeMaskedBits(Value *V, const APInt &Mask, gep_type_iterator GTI = gep_type_begin(I); for (unsigned i = 1, e = I->getNumOperands(); i != e; ++i, ++GTI) { Value *Index = I->getOperand(i); - if (const StructType *STy = dyn_cast(*GTI)) { + if (StructType *STy = dyn_cast(*GTI)) { // Handle struct member offset arithmetic. if (!TD) return; const StructLayout *SL = TD->getStructLayout(STy); @@ -523,7 +609,7 @@ void llvm::ComputeMaskedBits(Value *V, const APInt &Mask, CountTrailingZeros_64(Offset)); } else { // Handle array index arithmetic. - const Type *IndexedTy = GTI.getIndexedType(); + Type *IndexedTy = GTI.getIndexedType(); if (!IndexedTy->isSized()) return; unsigned GEPOpiBits = Index->getType()->getScalarSizeInBits(); uint64_t TypeSize = TD ? TD->getTypeAllocSize(IndexedTy) : 1; @@ -590,9 +676,17 @@ void llvm::ComputeMaskedBits(Value *V, const APInt &Mask, } } + // Unreachable blocks may have zero-operand PHI nodes. + if (P->getNumIncomingValues() == 0) + return; + // Otherwise take the unions of the known bit sets of the operands, // taking conservative care to avoid excessive recursion. if (Depth < MaxDepth - 1 && !KnownZero && !KnownOne) { + // Skip if every incoming value references to ourself. + if (P->hasConstantValue() == P) + break; + KnownZero = APInt::getAllOnesValue(BitWidth); KnownOne = APInt::getAllOnesValue(BitWidth); for (unsigned i = 0, e = P->getNumIncomingValues(); i != e; ++i) { @@ -626,6 +720,10 @@ void llvm::ComputeMaskedBits(Value *V, const APInt &Mask, KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits); break; } + case Intrinsic::x86_sse42_crc32_64_8: + case Intrinsic::x86_sse42_crc32_64_64: + KnownZero = APInt::getHighBitsSet(64, 32); + break; } } break; @@ -654,10 +752,15 @@ void llvm::ComputeSignBit(Value *V, bool &KnownZero, bool &KnownOne, /// bit set when defined. For vectors return true if every element is known to /// be a power of two when defined. Supports values with integer or pointer /// types and vectors of integers. -bool llvm::isPowerOfTwo(Value *V, const TargetData *TD, unsigned Depth) { - if (ConstantInt *CI = dyn_cast(V)) - return CI->getValue().countPopulation() == 1; - // TODO: Handle vector constants. +bool llvm::isPowerOfTwo(Value *V, const TargetData *TD, bool OrZero, + unsigned Depth) { + if (Constant *C = dyn_cast(V)) { + if (C->isNullValue()) + return OrZero; + if (ConstantInt *CI = dyn_cast(C)) + return CI->getValue().isPowerOf2(); + // TODO: Handle vector constants. + } // 1 << X is clearly a power of two if the one is not shifted off the end. If // it is shifted off the end then the result is undefined. @@ -666,21 +769,46 @@ bool llvm::isPowerOfTwo(Value *V, const TargetData *TD, unsigned Depth) { // (signbit) >>l X is clearly a power of two if the one is not shifted off the // bottom. If it is shifted off the bottom then the result is undefined. - ConstantInt *CI; - if (match(V, m_LShr(m_ConstantInt(CI), m_Value())) && - CI->getValue().isSignBit()) + if (match(V, m_LShr(m_SignBit(), m_Value()))) return true; // The remaining tests are all recursive, so bail out if we hit the limit. if (Depth++ == MaxDepth) return false; + Value *X = 0, *Y = 0; + // A shift of a power of two is a power of two or zero. + if (OrZero && (match(V, m_Shl(m_Value(X), m_Value())) || + match(V, m_Shr(m_Value(X), m_Value())))) + return isPowerOfTwo(X, TD, /*OrZero*/true, Depth); + if (ZExtInst *ZI = dyn_cast(V)) - return isPowerOfTwo(ZI->getOperand(0), TD, Depth); + return isPowerOfTwo(ZI->getOperand(0), TD, OrZero, Depth); if (SelectInst *SI = dyn_cast(V)) - return isPowerOfTwo(SI->getTrueValue(), TD, Depth) && - isPowerOfTwo(SI->getFalseValue(), TD, Depth); + return isPowerOfTwo(SI->getTrueValue(), TD, OrZero, Depth) && + isPowerOfTwo(SI->getFalseValue(), TD, OrZero, Depth); + + if (OrZero && match(V, m_And(m_Value(X), m_Value(Y)))) { + // A power of two and'd with anything is a power of two or zero. + if (isPowerOfTwo(X, TD, /*OrZero*/true, Depth) || + isPowerOfTwo(Y, TD, /*OrZero*/true, Depth)) + return true; + // X & (-X) is always a power of two or zero. + if (match(X, m_Neg(m_Specific(Y))) || match(Y, m_Neg(m_Specific(X)))) + return true; + return false; + } + + // An exact divide or right shift can only shift off zero bits, so the result + // is a power of two only if the first operand is a power of two and not + // copying a sign bit (sdiv int_min, 2). + if (match(V, m_LShr(m_Value(), m_Value())) || + match(V, m_UDiv(m_Value(), m_Value()))) { + PossiblyExactOperator *PEO = cast(V); + if (PEO->isExact()) + return isPowerOfTwo(PEO->getOperand(0), TD, OrZero, Depth); + } return false; } @@ -701,7 +829,7 @@ bool llvm::isKnownNonZero(Value *V, const TargetData *TD, unsigned Depth) { } // The remaining tests are all recursive, so bail out if we hit the limit. - if (Depth++ == MaxDepth) + if (Depth++ >= MaxDepth) return false; unsigned BitWidth = getBitWidth(V->getType(), TD); @@ -715,23 +843,39 @@ bool llvm::isKnownNonZero(Value *V, const TargetData *TD, unsigned Depth) { if (isa(V) || isa(V)) return isKnownNonZero(cast(V)->getOperand(0), TD, Depth); - // shl X, A != 0 if X is odd. Note that the value of the shift is undefined + // shl X, Y != 0 if X is odd. Note that the value of the shift is undefined // if the lowest bit is shifted off the end. if (BitWidth && match(V, m_Shl(m_Value(X), m_Value(Y)))) { + // shl nuw can't remove any non-zero bits. + OverflowingBinaryOperator *BO = cast(V); + if (BO->hasNoUnsignedWrap()) + return isKnownNonZero(X, TD, Depth); + APInt KnownZero(BitWidth, 0); APInt KnownOne(BitWidth, 0); - ComputeMaskedBits(V, APInt(BitWidth, 1), KnownZero, KnownOne, TD, Depth); + ComputeMaskedBits(X, APInt(BitWidth, 1), KnownZero, KnownOne, TD, Depth); if (KnownOne[0]) return true; } - // shr X, A != 0 if X is negative. Note that the value of the shift is not + // shr X, Y != 0 if X is negative. Note that the value of the shift is not // defined if the sign bit is shifted off the end. else if (match(V, m_Shr(m_Value(X), m_Value(Y)))) { + // shr exact can only shift out zero bits. + PossiblyExactOperator *BO = cast(V); + if (BO->isExact()) + return isKnownNonZero(X, TD, Depth); + bool XKnownNonNegative, XKnownNegative; ComputeSignBit(X, XKnownNonNegative, XKnownNegative, TD, Depth); if (XKnownNegative) return true; } + // div exact can only produce a zero if the dividend is zero. + else if (match(V, m_IDiv(m_Value(X), m_Value()))) { + PossiblyExactOperator *BO = cast(V); + if (BO->isExact()) + return isKnownNonZero(X, TD, Depth); + } // X + Y. else if (match(V, m_Add(m_Value(X), m_Value(Y)))) { bool XKnownNonNegative, XKnownNegative; @@ -764,9 +908,18 @@ bool llvm::isKnownNonZero(Value *V, const TargetData *TD, unsigned Depth) { } // The sum of a non-negative number and a power of two is not zero. - if (XKnownNonNegative && isPowerOfTwo(Y, TD, Depth)) + if (XKnownNonNegative && isPowerOfTwo(Y, TD, /*OrZero*/false, Depth)) + return true; + if (YKnownNonNegative && isPowerOfTwo(X, TD, /*OrZero*/false, Depth)) return true; - if (YKnownNonNegative && isPowerOfTwo(X, TD, Depth)) + } + // X * Y. + else if (match(V, m_Mul(m_Value(X), m_Value(Y)))) { + OverflowingBinaryOperator *BO = cast(V); + // If X and Y are non-zero then so is X * Y as long as the multiplication + // does not overflow. + if ((BO->hasNoSignedWrap() || BO->hasNoUnsignedWrap()) && + isKnownNonZero(X, TD, Depth) && isKnownNonZero(Y, TD, Depth)) return true; } // (C ? X : Y) != 0 if X != 0 and Y != 0. @@ -816,7 +969,7 @@ unsigned llvm::ComputeNumSignBits(Value *V, const TargetData *TD, assert((TD || V->getType()->isIntOrIntVectorTy()) && "ComputeNumSignBits requires a TargetData object to operate " "on non-integer values!"); - const Type *Ty = V->getType(); + Type *Ty = V->getType(); unsigned TyBits = TD ? TD->getTypeSizeInBits(V->getType()->getScalarType()) : Ty->getScalarSizeInBits(); unsigned Tmp, Tmp2; @@ -996,7 +1149,7 @@ bool llvm::ComputeMultiple(Value *V, unsigned Base, Value *&Multiple, assert(Depth <= MaxDepth && "Limit Search Depth"); assert(V->getType()->isIntegerTy() && "Not integer or pointer type!"); - const Type *T = V->getType(); + Type *T = V->getType(); ConstantInt *CI = dyn_cast(V); @@ -1161,6 +1314,11 @@ bool llvm::CannotBeNegativeZero(const Value *V, unsigned Depth) { Value *llvm::isBytewiseValue(Value *V) { // All byte-wide stores are splatable, even of arbitrary variables. if (V->getType()->isIntegerTy(8)) return V; + + // Handle 'null' ConstantArrayZero etc. + if (Constant *C = dyn_cast(V)) + if (C->isNullValue()) + return Constant::getNullValue(Type::getInt8Ty(V->getContext())); // Constant float and double values can be handled as integer values if the // corresponding integer value is "byteable". An important case is 0.0. @@ -1228,11 +1386,11 @@ Value *llvm::isBytewiseValue(Value *V) { // indices from Idxs that should be left out when inserting into the resulting // struct. To is the result struct built so far, new insertvalue instructions // build on that. -static Value *BuildSubAggregate(Value *From, Value* To, const Type *IndexedType, +static Value *BuildSubAggregate(Value *From, Value* To, Type *IndexedType, SmallVector &Idxs, unsigned IdxSkip, Instruction *InsertBefore) { - const llvm::StructType *STy = llvm::dyn_cast(IndexedType); + llvm::StructType *STy = llvm::dyn_cast(IndexedType); if (STy) { // Save the original To argument so we can modify it Value *OrigTo = To; @@ -1255,7 +1413,7 @@ static Value *BuildSubAggregate(Value *From, Value* To, const Type *IndexedType, break; } } - // If we succesfully found a value for each of our subaggregates + // If we successfully found a value for each of our subaggregates if (To) return To; } @@ -1265,14 +1423,14 @@ static Value *BuildSubAggregate(Value *From, Value* To, const Type *IndexedType, // we might be able to find the complete struct somewhere. // Find the value that is at that particular spot - Value *V = FindInsertedValue(From, Idxs.begin(), Idxs.end()); + Value *V = FindInsertedValue(From, Idxs); if (!V) return NULL; // Insert the value in the new (sub) aggregrate - return llvm::InsertValueInst::Create(To, V, Idxs.begin() + IdxSkip, - Idxs.end(), "tmp", InsertBefore); + return llvm::InsertValueInst::Create(To, V, makeArrayRef(Idxs).slice(IdxSkip), + "tmp", InsertBefore); } // This helper takes a nested struct and extracts a part of it (which is again a @@ -1287,15 +1445,13 @@ static Value *BuildSubAggregate(Value *From, Value* To, const Type *IndexedType, // insertvalue instruction somewhere). // // All inserted insertvalue instructions are inserted before InsertBefore -static Value *BuildSubAggregate(Value *From, const unsigned *idx_begin, - const unsigned *idx_end, +static Value *BuildSubAggregate(Value *From, ArrayRef idx_range, Instruction *InsertBefore) { assert(InsertBefore && "Must have someplace to insert!"); - const Type *IndexedType = ExtractValueInst::getIndexedType(From->getType(), - idx_begin, - idx_end); + Type *IndexedType = ExtractValueInst::getIndexedType(From->getType(), + idx_range); Value *To = UndefValue::get(IndexedType); - SmallVector Idxs(idx_begin, idx_end); + SmallVector Idxs(idx_range.begin(), idx_range.end()); unsigned IdxSkip = Idxs.size(); return BuildSubAggregate(From, To, IndexedType, Idxs, IdxSkip, InsertBefore); @@ -1307,39 +1463,37 @@ static Value *BuildSubAggregate(Value *From, const unsigned *idx_begin, /// /// If InsertBefore is not null, this function will duplicate (modified) /// insertvalues when a part of a nested struct is extracted. -Value *llvm::FindInsertedValue(Value *V, const unsigned *idx_begin, - const unsigned *idx_end, Instruction *InsertBefore) { +Value *llvm::FindInsertedValue(Value *V, ArrayRef idx_range, + Instruction *InsertBefore) { // Nothing to index? Just return V then (this is useful at the end of our // recursion) - if (idx_begin == idx_end) + if (idx_range.empty()) return V; // We have indices, so V should have an indexable type assert((V->getType()->isStructTy() || V->getType()->isArrayTy()) && "Not looking at a struct or array?"); - assert(ExtractValueInst::getIndexedType(V->getType(), idx_begin, idx_end) + assert(ExtractValueInst::getIndexedType(V->getType(), idx_range) && "Invalid indices for type?"); - const CompositeType *PTy = cast(V->getType()); + CompositeType *PTy = cast(V->getType()); if (isa(V)) return UndefValue::get(ExtractValueInst::getIndexedType(PTy, - idx_begin, - idx_end)); + idx_range)); else if (isa(V)) return Constant::getNullValue(ExtractValueInst::getIndexedType(PTy, - idx_begin, - idx_end)); + idx_range)); else if (Constant *C = dyn_cast(V)) { if (isa(C) || isa(C)) // Recursively process this constant - return FindInsertedValue(C->getOperand(*idx_begin), idx_begin + 1, - idx_end, InsertBefore); + return FindInsertedValue(C->getOperand(idx_range[0]), idx_range.slice(1), + InsertBefore); } else if (InsertValueInst *I = dyn_cast(V)) { // Loop the indices for the insertvalue instruction in parallel with the // requested indices - const unsigned *req_idx = idx_begin; + const unsigned *req_idx = idx_range.begin(); for (const unsigned *i = I->idx_begin(), *e = I->idx_end(); i != e; ++i, ++req_idx) { - if (req_idx == idx_end) { + if (req_idx == idx_range.end()) { if (InsertBefore) // The requested index identifies a part of a nested aggregate. Handle // this specially. For example, @@ -1351,7 +1505,8 @@ Value *llvm::FindInsertedValue(Value *V, const unsigned *idx_begin, // %C = insertvalue {i32, i32 } %A, i32 11, 1 // which allows the unused 0,0 element from the nested struct to be // removed. - return BuildSubAggregate(V, idx_begin, req_idx, InsertBefore); + return BuildSubAggregate(V, makeArrayRef(idx_range.begin(), req_idx), + InsertBefore); else // We can't handle this without inserting insertvalues return 0; @@ -1361,13 +1516,14 @@ Value *llvm::FindInsertedValue(Value *V, const unsigned *idx_begin, // See if the (aggregrate) value inserted into has the value we are // looking for, then. if (*req_idx != *i) - return FindInsertedValue(I->getAggregateOperand(), idx_begin, idx_end, + return FindInsertedValue(I->getAggregateOperand(), idx_range, InsertBefore); } // If we end up here, the indices of the insertvalue match with those // requested (though possibly only partially). Now we recursively look at // the inserted value, passing any remaining indices. - return FindInsertedValue(I->getInsertedValueOperand(), req_idx, idx_end, + return FindInsertedValue(I->getInsertedValueOperand(), + makeArrayRef(req_idx, idx_range.end()), InsertBefore); } else if (ExtractValueInst *I = dyn_cast(V)) { // If we're extracting a value from an aggregrate that was extracted from @@ -1375,24 +1531,20 @@ Value *llvm::FindInsertedValue(Value *V, const unsigned *idx_begin, // However, we will need to chain I's indices with the requested indices. // Calculate the number of indices required - unsigned size = I->getNumIndices() + (idx_end - idx_begin); + unsigned size = I->getNumIndices() + idx_range.size(); // Allocate some space to put the new indices in SmallVector Idxs; Idxs.reserve(size); // Add indices from the extract value instruction - for (const unsigned *i = I->idx_begin(), *e = I->idx_end(); - i != e; ++i) - Idxs.push_back(*i); + Idxs.append(I->idx_begin(), I->idx_end()); // Add requested indices - for (const unsigned *i = idx_begin, *e = idx_end; i != e; ++i) - Idxs.push_back(*i); + Idxs.append(idx_range.begin(), idx_range.end()); assert(Idxs.size() == size && "Number of indices added not correct?"); - return FindInsertedValue(I->getAggregateOperand(), Idxs.begin(), Idxs.end(), - InsertBefore); + return FindInsertedValue(I->getAggregateOperand(), Idxs, InsertBefore); } // Otherwise, we don't know (such as, extracting from a function return value // or load instruction) @@ -1422,7 +1574,7 @@ Value *llvm::GetPointerBaseWithConstantOffset(Value *Ptr, int64_t &Offset, if (OpC->isZero()) continue; // Handle a struct and array indices which add their offset to the pointer. - if (const StructType *STy = dyn_cast(*GTI)) { + if (StructType *STy = dyn_cast(*GTI)) { Offset += TD.getStructLayout(STy)->getElementOffset(OpC->getZExtValue()); } else { uint64_t Size = TD.getTypeAllocSize(GTI.getIndexedType()); @@ -1444,8 +1596,7 @@ Value *llvm::GetPointerBaseWithConstantOffset(Value *Ptr, int64_t &Offset, /// null-terminated C string pointed to by V. If successful, it returns true /// and returns the string in Str. If unsuccessful, it returns false. bool llvm::GetConstantStringInfo(const Value *V, std::string &Str, - uint64_t Offset, - bool StopAtNul) { + uint64_t Offset, bool StopAtNul) { // If V is NULL then return false; if (V == NULL) return false; @@ -1455,7 +1606,7 @@ bool llvm::GetConstantStringInfo(const Value *V, std::string &Str, // If the value is not a GEP instruction nor a constant expression with a // GEP instruction, then return false because ConstantArray can't occur - // any other way + // any other way. const User *GEP = 0; if (const GetElementPtrInst *GEPI = dyn_cast(V)) { GEP = GEPI; @@ -1473,8 +1624,8 @@ bool llvm::GetConstantStringInfo(const Value *V, std::string &Str, return false; // Make sure the index-ee is a pointer to array of i8. - const PointerType *PT = cast(GEP->getOperand(0)->getType()); - const ArrayType *AT = dyn_cast(PT->getElementType()); + PointerType *PT = cast(GEP->getOperand(0)->getType()); + ArrayType *AT = dyn_cast(PT->getElementType()); if (AT == 0 || !AT->getElementType()->isIntegerTy(8)) return false; @@ -1495,7 +1646,7 @@ bool llvm::GetConstantStringInfo(const Value *V, std::string &Str, return GetConstantStringInfo(GEP->getOperand(0), Str, StartIdx+Offset, StopAtNul); } - + // The GEP instruction, constant or instruction, must reference a global // variable that is a constant and is initialized. The referenced constant // initializer is the array that we'll use for optimization. @@ -1504,8 +1655,8 @@ bool llvm::GetConstantStringInfo(const Value *V, std::string &Str, return false; const Constant *GlobalInit = GV->getInitializer(); - // Handle the ConstantAggregateZero case - if (isa(GlobalInit)) { + // Handle the all-zeros case + if (GlobalInit->isNullValue()) { // This is a degenerate case. The initializer is constant zero so the // length of the string must be zero. Str.clear(); @@ -1586,6 +1737,14 @@ static uint64_t GetStringLengthH(Value *V, SmallPtrSet &PHIs) { return Len1; } + // As a special-case, "@string = constant i8 0" is also a string with zero + // length, not wrapped in a bitcast or GEP. + if (GlobalVariable *GV = dyn_cast(V)) { + if (GV->isConstant() && GV->hasDefinitiveInitializer()) + if (GV->getInitializer()->isNullValue()) return 1; + return 0; + } + // If the value is not a GEP instruction nor a constant expression with a // GEP instruction, then return unknown. User *GEP = 0; @@ -1684,7 +1843,7 @@ llvm::GetUnderlyingObject(Value *V, const TargetData *TD, unsigned MaxLookup) { } else { // See if InstructionSimplify knows any relevant tricks. if (Instruction *I = dyn_cast(V)) - // TODO: Aquire a DominatorTree and use it. + // TODO: Acquire a DominatorTree and use it. if (Value *Simplified = SimplifyInstruction(I, TD, 0)) { V = Simplified; continue; @@ -1696,3 +1855,19 @@ llvm::GetUnderlyingObject(Value *V, const TargetData *TD, unsigned MaxLookup) { } return V; } + +/// onlyUsedByLifetimeMarkers - Return true if the only users of this pointer +/// are lifetime markers. +/// +bool llvm::onlyUsedByLifetimeMarkers(const Value *V) { + for (Value::const_use_iterator UI = V->use_begin(), UE = V->use_end(); + UI != UE; ++UI) { + const IntrinsicInst *II = dyn_cast(*UI); + if (!II) return false; + + if (II->getIntrinsicID() != Intrinsic::lifetime_start && + II->getIntrinsicID() != Intrinsic::lifetime_end) + return false; + } + return true; +}