diff options
Diffstat (limited to 'llvm/lib')
-rw-r--r-- | llvm/lib/Analysis/TargetLibraryInfo.cpp | 12 | ||||
-rw-r--r-- | llvm/lib/Analysis/ValueTracking.cpp | 122 | ||||
-rw-r--r-- | llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp | 49 | ||||
-rw-r--r-- | llvm/lib/IR/Constants.cpp | 4 | ||||
-rw-r--r-- | llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp | 82 |
5 files changed, 186 insertions, 83 deletions
diff --git a/llvm/lib/Analysis/TargetLibraryInfo.cpp b/llvm/lib/Analysis/TargetLibraryInfo.cpp index 3cf1bbc5daa..7a07ab75264 100644 --- a/llvm/lib/Analysis/TargetLibraryInfo.cpp +++ b/llvm/lib/Analysis/TargetLibraryInfo.cpp @@ -13,6 +13,7 @@ #include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/ADT/Triple.h" +#include "llvm/IR/Constants.h" #include "llvm/Support/CommandLine.h" using namespace llvm; @@ -1518,6 +1519,17 @@ TargetLibraryInfoImpl &TargetLibraryAnalysis::lookupInfoImpl(const Triple &T) { return *Impl; } +unsigned TargetLibraryInfoImpl::getTargetWCharSize(const Triple &T) { + // See also clang/lib/Basic/Targets.cpp. + return T.isPS4() || T.isOSWindows() || T.getArch() == Triple::xcore ? 2 : 4; +} + +unsigned TargetLibraryInfoImpl::getWCharSize(const Module &M) const { + if (auto *ShortWChar = cast_or_null<ConstantAsMetadata>( + M.getModuleFlag("wchar_size"))) + return cast<ConstantInt>(ShortWChar->getValue())->getZExtValue(); + return getTargetWCharSize(Triple(M.getTargetTriple())); +} TargetLibraryInfoWrapperPass::TargetLibraryInfoWrapperPass() : ImmutablePass(ID), TLIImpl(), TLI(TLIImpl) { diff --git a/llvm/lib/Analysis/ValueTracking.cpp b/llvm/lib/Analysis/ValueTracking.cpp index cba7363a0af..8e6c1096eec 100644 --- a/llvm/lib/Analysis/ValueTracking.cpp +++ b/llvm/lib/Analysis/ValueTracking.cpp @@ -26,6 +26,7 @@ #include "llvm/IR/ConstantRange.h" #include "llvm/IR/Constants.h" #include "llvm/IR/DataLayout.h" +#include "llvm/IR/DerivedTypes.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/GetElementPtrTypeIterator.h" #include "llvm/IR/GlobalAlias.h" @@ -2953,14 +2954,16 @@ Value *llvm::GetPointerBaseWithConstantOffset(Value *Ptr, int64_t &Offset, return Ptr; } -bool llvm::isGEPBasedOnPointerToString(const GEPOperator *GEP) { +bool llvm::isGEPBasedOnPointerToString(const GEPOperator *GEP, + unsigned CharSize) { // Make sure the GEP has exactly three arguments. if (GEP->getNumOperands() != 3) return false; - // Make sure the index-ee is a pointer to array of i8. + // Make sure the index-ee is a pointer to array of \p CharSize integers. + // CharSize. ArrayType *AT = dyn_cast<ArrayType>(GEP->getSourceElementType()); - if (!AT || !AT->getElementType()->isIntegerTy(8)) + if (!AT || !AT->getElementType()->isIntegerTy(CharSize)) return false; // Check to make sure that the first operand of the GEP is an integer and @@ -2972,11 +2975,9 @@ bool llvm::isGEPBasedOnPointerToString(const GEPOperator *GEP) { return true; } -/// This function computes the length of a 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, StringRef &Str, - uint64_t Offset, bool TrimAtNul) { +bool llvm::getConstantDataArrayInfo(const Value *V, + ConstantDataArraySlice &Slice, + unsigned ElementSize, uint64_t Offset) { assert(V); // Look through bitcast instructions and geps. @@ -2987,7 +2988,7 @@ bool llvm::getConstantStringInfo(const Value *V, StringRef &Str, if (const GEPOperator *GEP = dyn_cast<GEPOperator>(V)) { // The GEP operator should be based on a pointer to string constant, and is // indexing into the string constant. - if (!isGEPBasedOnPointerToString(GEP)) + if (!isGEPBasedOnPointerToString(GEP, ElementSize)) return false; // If the second index isn't a ConstantInt, then this is a variable index @@ -2998,8 +2999,8 @@ bool llvm::getConstantStringInfo(const Value *V, StringRef &Str, StartIdx = CI->getZExtValue(); else return false; - return getConstantStringInfo(GEP->getOperand(0), Str, StartIdx + Offset, - TrimAtNul); + return getConstantDataArrayInfo(GEP->getOperand(0), Slice, ElementSize, + StartIdx + Offset); } // The GEP instruction, constant or instruction, must reference a global @@ -3009,30 +3010,72 @@ bool llvm::getConstantStringInfo(const Value *V, StringRef &Str, if (!GV || !GV->isConstant() || !GV->hasDefinitiveInitializer()) return false; - // Handle the all-zeros case. + const ConstantDataArray *Array; + ArrayType *ArrayTy; if (GV->getInitializer()->isNullValue()) { - // This is a degenerate case. The initializer is constant zero so the - // length of the string must be zero. - Str = ""; - return true; + Type *GVTy = GV->getValueType(); + if ( (ArrayTy = dyn_cast<ArrayType>(GVTy)) ) { + // A zeroinitializer for the array; There is no ConstantDataArray. + Array = nullptr; + } else { + const DataLayout &DL = GV->getParent()->getDataLayout(); + uint64_t SizeInBytes = DL.getTypeStoreSize(GVTy); + uint64_t Length = SizeInBytes / (ElementSize / 8); + if (Length <= Offset) + return false; + + Slice.Array = nullptr; + Slice.Offset = 0; + Slice.Length = Length - Offset; + return true; + } + } else { + // This must be a ConstantDataArray. + Array = dyn_cast<ConstantDataArray>(GV->getInitializer()); + if (!Array) + return false; + ArrayTy = Array->getType(); } + if (!ArrayTy->getElementType()->isIntegerTy(ElementSize)) + return false; - // This must be a ConstantDataArray. - const auto *Array = dyn_cast<ConstantDataArray>(GV->getInitializer()); - if (!Array || !Array->isString()) + uint64_t NumElts = ArrayTy->getArrayNumElements(); + if (Offset > NumElts) return false; - // Get the number of elements in the array. - uint64_t NumElts = Array->getType()->getArrayNumElements(); + Slice.Array = Array; + Slice.Offset = Offset; + Slice.Length = NumElts - Offset; + return true; +} - // Start out with the entire array in the StringRef. - Str = Array->getAsString(); +/// This function computes the length of a 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, StringRef &Str, + uint64_t Offset, bool TrimAtNul) { + ConstantDataArraySlice Slice; + if (!getConstantDataArrayInfo(V, Slice, 8, Offset)) + return false; - if (Offset > NumElts) + if (Slice.Array == nullptr) { + if (TrimAtNul) { + Str = StringRef(); + return true; + } + if (Slice.Length == 1) { + Str = StringRef("", 1); + return true; + } + // We cannot instantiate a StringRef as we do not have an apropriate string + // of 0s at hand. return false; + } + // Start out with the entire array in the StringRef. + Str = Slice.Array->getAsString(); // Skip over 'offset' bytes. - Str = Str.substr(Offset); + Str = Str.substr(Slice.Offset); if (TrimAtNul) { // Trim off the \0 and anything after it. If the array is not nul @@ -3050,7 +3093,8 @@ bool llvm::getConstantStringInfo(const Value *V, StringRef &Str, /// If we can compute the length of the string pointed to by /// the specified pointer, return 'len+1'. If we can't, return 0. static uint64_t GetStringLengthH(const Value *V, - SmallPtrSetImpl<const PHINode*> &PHIs) { + SmallPtrSetImpl<const PHINode*> &PHIs, + unsigned CharSize) { // Look through noop bitcast instructions. V = V->stripPointerCasts(); @@ -3063,7 +3107,7 @@ static uint64_t GetStringLengthH(const Value *V, // If it was new, see if all the input strings are the same length. uint64_t LenSoFar = ~0ULL; for (Value *IncValue : PN->incoming_values()) { - uint64_t Len = GetStringLengthH(IncValue, PHIs); + uint64_t Len = GetStringLengthH(IncValue, PHIs, CharSize); if (Len == 0) return 0; // Unknown length -> unknown. if (Len == ~0ULL) continue; @@ -3079,9 +3123,9 @@ static uint64_t GetStringLengthH(const Value *V, // strlen(select(c,x,y)) -> strlen(x) ^ strlen(y) if (const SelectInst *SI = dyn_cast<SelectInst>(V)) { - uint64_t Len1 = GetStringLengthH(SI->getTrueValue(), PHIs); + uint64_t Len1 = GetStringLengthH(SI->getTrueValue(), PHIs, CharSize); if (Len1 == 0) return 0; - uint64_t Len2 = GetStringLengthH(SI->getFalseValue(), PHIs); + uint64_t Len2 = GetStringLengthH(SI->getFalseValue(), PHIs, CharSize); if (Len2 == 0) return 0; if (Len1 == ~0ULL) return Len2; if (Len2 == ~0ULL) return Len1; @@ -3090,20 +3134,30 @@ static uint64_t GetStringLengthH(const Value *V, } // Otherwise, see if we can read the string. - StringRef StrData; - if (!getConstantStringInfo(V, StrData)) + ConstantDataArraySlice Slice; + if (!getConstantDataArrayInfo(V, Slice, CharSize)) return 0; - return StrData.size()+1; + if (Slice.Array == nullptr) + return 1; + + // Search for nul characters + unsigned NullIndex = 0; + for (unsigned E = Slice.Length; NullIndex < E; ++NullIndex) { + if (Slice.Array->getElementAsInteger(Slice.Offset + NullIndex) == 0) + break; + } + + return NullIndex + 1; } /// If we can compute the length of the string pointed to by /// the specified pointer, return 'len+1'. If we can't, return 0. -uint64_t llvm::GetStringLength(const Value *V) { +uint64_t llvm::GetStringLength(const Value *V, unsigned CharSize) { if (!V->getType()->isPointerTy()) return 0; SmallPtrSet<const PHINode*, 32> PHIs; - uint64_t Len = GetStringLengthH(V, PHIs); + uint64_t Len = GetStringLengthH(V, PHIs, CharSize); // If Len is ~0ULL, we had an infinite phi cycle: this is dead code, so return // an empty string as a length. return Len == ~0ULL ? 1 : Len; diff --git a/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp b/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp index 057badcd6b7..16c1f78f1b3 100644 --- a/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp +++ b/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp @@ -4685,9 +4685,10 @@ static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG, /// used when a memcpy is turned into a memset when the source is a constant /// string ptr. static SDValue getMemsetStringVal(EVT VT, const SDLoc &dl, SelectionDAG &DAG, - const TargetLowering &TLI, StringRef Str) { + const TargetLowering &TLI, + const ConstantDataArraySlice &Slice) { // Handle vector with all elements zero. - if (Str.empty()) { + if (Slice.Array == nullptr) { if (VT.isInteger()) return DAG.getConstant(0, dl, VT); else if (VT == MVT::f32 || VT == MVT::f64 || VT == MVT::f128) @@ -4706,15 +4707,15 @@ static SDValue getMemsetStringVal(EVT VT, const SDLoc &dl, SelectionDAG &DAG, assert(!VT.isVector() && "Can't handle vector type here!"); unsigned NumVTBits = VT.getSizeInBits(); unsigned NumVTBytes = NumVTBits / 8; - unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size())); + unsigned NumBytes = std::min(NumVTBytes, unsigned(Slice.Length)); APInt Val(NumVTBits, 0); if (DAG.getDataLayout().isLittleEndian()) { for (unsigned i = 0; i != NumBytes; ++i) - Val |= (uint64_t)(unsigned char)Str[i] << i*8; + Val |= (uint64_t)(unsigned char)Slice[i] << i*8; } else { for (unsigned i = 0; i != NumBytes; ++i) - Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8; + Val |= (uint64_t)(unsigned char)Slice[i] << (NumVTBytes-i-1)*8; } // If the "cost" of materializing the integer immediate is less than the cost @@ -4731,9 +4732,8 @@ SDValue SelectionDAG::getMemBasePlusOffset(SDValue Base, unsigned Offset, return getNode(ISD::ADD, DL, VT, Base, getConstant(Offset, DL, VT)); } -/// isMemSrcFromString - Returns true if memcpy source is a string constant. -/// -static bool isMemSrcFromString(SDValue Src, StringRef &Str) { +/// Returns true if memcpy source is constant data. +static bool isMemSrcFromConstant(SDValue Src, ConstantDataArraySlice &Slice) { uint64_t SrcDelta = 0; GlobalAddressSDNode *G = nullptr; if (Src.getOpcode() == ISD::GlobalAddress) @@ -4747,8 +4747,8 @@ static bool isMemSrcFromString(SDValue Src, StringRef &Str) { if (!G) return false; - return getConstantStringInfo(G->getGlobal(), Str, - SrcDelta + G->getOffset(), false); + return getConstantDataArrayInfo(G->getGlobal(), Slice, 8, + SrcDelta + G->getOffset()); } /// Determines the optimal series of memory ops to replace the memset / memcpy. @@ -4891,15 +4891,15 @@ static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, const SDLoc &dl, unsigned SrcAlign = DAG.InferPtrAlignment(Src); if (Align > SrcAlign) SrcAlign = Align; - StringRef Str; - bool CopyFromStr = isMemSrcFromString(Src, Str); - bool isZeroStr = CopyFromStr && Str.empty(); + ConstantDataArraySlice Slice; + bool CopyFromConstant = isMemSrcFromConstant(Src, Slice); + bool isZeroConstant = CopyFromConstant && Slice.Array == nullptr; unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize); if (!FindOptimalMemOpLowering(MemOps, Limit, Size, (DstAlignCanChange ? 0 : Align), - (isZeroStr ? 0 : SrcAlign), - false, false, CopyFromStr, true, + (isZeroConstant ? 0 : SrcAlign), + false, false, CopyFromConstant, true, DstPtrInfo.getAddrSpace(), SrcPtrInfo.getAddrSpace(), DAG, TLI)) @@ -4943,18 +4943,29 @@ static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, const SDLoc &dl, DstOff -= VTSize - Size; } - if (CopyFromStr && - (isZeroStr || (VT.isInteger() && !VT.isVector()))) { + if (CopyFromConstant && + (isZeroConstant || (VT.isInteger() && !VT.isVector()))) { // It's unlikely a store of a vector immediate can be done in a single // instruction. It would require a load from a constantpool first. // We only handle zero vectors here. // FIXME: Handle other cases where store of vector immediate is done in // a single instruction. - Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff)); + ConstantDataArraySlice SubSlice; + if (SrcOff < Slice.Length) { + SubSlice = Slice; + SubSlice.move(SrcOff); + } else { + // This is an out-of-bounds access and hence UB. Pretend we read zero. + SubSlice.Array = nullptr; + SubSlice.Offset = 0; + SubSlice.Length = VTSize; + } + Value = getMemsetStringVal(VT, dl, DAG, TLI, SubSlice); if (Value.getNode()) Store = DAG.getStore(Chain, dl, Value, DAG.getMemBasePlusOffset(Dst, DstOff, dl), - DstPtrInfo.getWithOffset(DstOff), Align, MMOFlags); + DstPtrInfo.getWithOffset(DstOff), Align, + MMOFlags); } if (!Store.getNode()) { diff --git a/llvm/lib/IR/Constants.cpp b/llvm/lib/IR/Constants.cpp index f0b9dfb2d62..8b0ff66334a 100644 --- a/llvm/lib/IR/Constants.cpp +++ b/llvm/lib/IR/Constants.cpp @@ -2616,8 +2616,8 @@ Constant *ConstantDataSequential::getElementAsConstant(unsigned Elt) const { return ConstantInt::get(getElementType(), getElementAsInteger(Elt)); } -bool ConstantDataSequential::isString() const { - return isa<ArrayType>(getType()) && getElementType()->isIntegerTy(8); +bool ConstantDataSequential::isString(unsigned CharSize) const { + return isa<ArrayType>(getType()) && getElementType()->isIntegerTy(CharSize); } bool ConstantDataSequential::isCString() const { diff --git a/llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp b/llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp index 1de579ed41b..85c9464b556 100644 --- a/llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp +++ b/llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp @@ -426,57 +426,70 @@ Value *LibCallSimplifier::optimizeStrNCpy(CallInst *CI, IRBuilder<> &B) { return Dst; } -Value *LibCallSimplifier::optimizeStrLen(CallInst *CI, IRBuilder<> &B) { +Value *LibCallSimplifier::optimizeStringLength(CallInst *CI, IRBuilder<> &B, + unsigned CharSize) { Value *Src = CI->getArgOperand(0); // Constant folding: strlen("xyz") -> 3 - if (uint64_t Len = GetStringLength(Src)) + if (uint64_t Len = GetStringLength(Src, CharSize)) return ConstantInt::get(CI->getType(), Len - 1); // If s is a constant pointer pointing to a string literal, we can fold - // strlen(s + x) to strlen(s) - x, when x is known to be in the range + // strlen(s + x) to strlen(s) - x, when x is known to be in the range // [0, strlen(s)] or the string has a single null terminator '\0' at the end. - // We only try to simplify strlen when the pointer s points to an array + // We only try to simplify strlen when the pointer s points to an array // of i8. Otherwise, we would need to scale the offset x before doing the - // subtraction. This will make the optimization more complex, and it's not - // very useful because calling strlen for a pointer of other types is + // subtraction. This will make the optimization more complex, and it's not + // very useful because calling strlen for a pointer of other types is // very uncommon. if (GEPOperator *GEP = dyn_cast<GEPOperator>(Src)) { - if (!isGEPBasedOnPointerToString(GEP)) + if (!isGEPBasedOnPointerToString(GEP, CharSize)) return nullptr; - StringRef Str; - if (getConstantStringInfo(GEP->getOperand(0), Str, 0, false)) { - size_t NullTermIdx = Str.find('\0'); - - // If the string does not have '\0', leave it to strlen to compute - // its length. - if (NullTermIdx == StringRef::npos) - return nullptr; - + ConstantDataArraySlice Slice; + if (getConstantDataArrayInfo(GEP->getOperand(0), Slice, CharSize)) { + uint64_t NullTermIdx; + if (Slice.Array == nullptr) { + NullTermIdx = 0; + } else { + NullTermIdx = ~((uint64_t)0); + for (uint64_t I = 0, E = Slice.Length; I < E; ++I) { + if (Slice.Array->getElementAsInteger(I + Slice.Offset) == 0) { + NullTermIdx = I; + break; + } + } + // If the string does not have '\0', leave it to strlen to compute + // its length. + if (NullTermIdx == ~((uint64_t)0)) + return nullptr; + } + Value *Offset = GEP->getOperand(2); unsigned BitWidth = Offset->getType()->getIntegerBitWidth(); KnownBits Known(BitWidth); computeKnownBits(Offset, Known, DL, 0, nullptr, CI, nullptr); Known.Zero.flipAllBits(); - size_t ArrSize = + uint64_t ArrSize = cast<ArrayType>(GEP->getSourceElementType())->getNumElements(); - // KnownZero's bits are flipped, so zeros in KnownZero now represent - // bits known to be zeros in Offset, and ones in KnowZero represent + // KnownZero's bits are flipped, so zeros in KnownZero now represent + // bits known to be zeros in Offset, and ones in KnowZero represent // bits unknown in Offset. Therefore, Offset is known to be in range - // [0, NullTermIdx] when the flipped KnownZero is non-negative and + // [0, NullTermIdx] when the flipped KnownZero is non-negative and // unsigned-less-than NullTermIdx. // - // If Offset is not provably in the range [0, NullTermIdx], we can still - // optimize if we can prove that the program has undefined behavior when - // Offset is outside that range. That is the case when GEP->getOperand(0) + // If Offset is not provably in the range [0, NullTermIdx], we can still + // optimize if we can prove that the program has undefined behavior when + // Offset is outside that range. That is the case when GEP->getOperand(0) // is a pointer to an object whose memory extent is NullTermIdx+1. - if ((Known.Zero.isNonNegative() && Known.Zero.ule(NullTermIdx)) || + if ((Known.Zero.isNonNegative() && Known.Zero.ule(NullTermIdx)) || (GEP->isInBounds() && isa<GlobalVariable>(GEP->getOperand(0)) && - NullTermIdx == ArrSize - 1)) - return B.CreateSub(ConstantInt::get(CI->getType(), NullTermIdx), + NullTermIdx == ArrSize - 1)) { + Offset = B.CreateSExtOrTrunc(Offset, CI->getType()); + return B.CreateSub(ConstantInt::get(CI->getType(), NullTermIdx), Offset); + } } return nullptr; @@ -484,8 +497,8 @@ Value *LibCallSimplifier::optimizeStrLen(CallInst *CI, IRBuilder<> &B) { // strlen(x?"foo":"bars") --> x ? 3 : 4 if (SelectInst *SI = dyn_cast<SelectInst>(Src)) { - uint64_t LenTrue = GetStringLength(SI->getTrueValue()); - uint64_t LenFalse = GetStringLength(SI->getFalseValue()); + uint64_t LenTrue = GetStringLength(SI->getTrueValue(), CharSize); + uint64_t LenFalse = GetStringLength(SI->getFalseValue(), CharSize); if (LenTrue && LenFalse) { Function *Caller = CI->getParent()->getParent(); emitOptimizationRemark(CI->getContext(), "simplify-libcalls", *Caller, @@ -505,6 +518,17 @@ Value *LibCallSimplifier::optimizeStrLen(CallInst *CI, IRBuilder<> &B) { return nullptr; } +Value *LibCallSimplifier::optimizeStrLen(CallInst *CI, IRBuilder<> &B) { + return optimizeStringLength(CI, B, 8); +} + +Value *LibCallSimplifier::optimizeWcslen(CallInst *CI, IRBuilder<> &B) { + Module &M = *CI->getParent()->getParent()->getParent(); + unsigned WCharSize = TLI->getWCharSize(M) * 8; + + return optimizeStringLength(CI, B, WCharSize); +} + Value *LibCallSimplifier::optimizeStrPBrk(CallInst *CI, IRBuilder<> &B) { StringRef S1, S2; bool HasS1 = getConstantStringInfo(CI->getArgOperand(0), S1); @@ -2026,6 +2050,8 @@ Value *LibCallSimplifier::optimizeStringMemoryLibCall(CallInst *CI, return optimizeMemMove(CI, Builder); case LibFunc_memset: return optimizeMemSet(CI, Builder); + case LibFunc_wcslen: + return optimizeWcslen(CI, Builder); default: break; } |