SimplifyLibCalls: Optimize wcslen

[MatzeB]

Summary

Refactor the strlen optimization code to work for both strlen and wcslen.

This especially helps with programs in the wild where people pass L"string"s to const std::wstring& function parameters and the wstring constructor gets inlined.

[MatzeB]

Add some tests that I missed to include in the last revision.

[efriedma]

lib/Transforms/Utils/SimplifyLibCalls.cpp

531

Making assumptions about the implementation of wcslen() based on the type of the pointer is bad idea. It probably works most of the time for code generated by clang, but pointee types don't have any semantics in IR, so it's likely to mess up at some point. (Also, pointee types in IR are likely to go away at some point in the future.)

I think the right approach is to add a function to TargetLibraryInfo to compute the size of wchar_t based on the triple.

[MatzeB]

lib/Transforms/Utils/SimplifyLibCalls.cpp

531

I assume the argument must match the declaration of wcslen which I assumed to be correct. I could grab the information directly from the declaration to avoid problems when the IR pointers don't have pointee-types anymore.

I'm not convinced the Triple/DataLayout has enough information to give you the type of wchar_t. There are for example the -fshort-wchar and -fno-short-wchar clang flags that do not affect the triple or datalayout.

[efriedma]

lib/Transforms/Utils/SimplifyLibCalls.cpp

531

If we want to support compiling against a C library built with "-fshort-wchar" on a platform where wchar_t is 32 bits by default, the triple isn't sufficient, yes. We can emit that information from clang; see http://llvm.org/docs/LangRef.html#c-type-width-module-flags-metadata . (We currently only emit it on ARM, but we could emit it on other architectures.)

[MatzeB]

• Determine wchar_t size based on the wcslen declaration
• Improve/fix tests

[MatzeB]

lib/Transforms/Utils/SimplifyLibCalls.cpp

531

The updated version gets wchar_t by looking at the wcslen declaration. I think that is in line with other code here (the length of size_t is also determined by looking at the call result types / function declarations if you look around).

(I don't think adding support for determining the sizes of C/C++ types into TargetLibraryInfo is a worthwhile goal at this point.)

[dblaikie]

lib/Transforms/Utils/SimplifyLibCalls.cpp

531

Any call to "getPointerElementType" won't be valid post-typeless-pointer work. Pointers will be opaque blobs (think of it as if your C code was "all void* all the time"). Please avoid adding uses of a pointer's element type where practical (using it to determine if bitcasts need to be added, etc is unavoidable for now - and would go away once typeless pointers are done and pointer bitcasts are no longer meaningful/needed).

So, yes, I'm not sure how this could be done correctly in that case without some kind of target hint/info about the size of a wchar?

[efriedma]

lib/Analysis/ValueTracking.cpp

3038–3039

Do we care about the size of the array in this case?

3092

See https://bugs.llvm.org//show_bug.cgi?id=32124 .

lib/Transforms/Utils/SimplifyLibCalls.cpp

458

Could you use an iterator which returns the elements of the ConstantDataArray, instead of using explicit indexing everywhere?

[MatzeB]

• Add functionality to TargetLibraryInfo to determine the size of wchar_t for a target triple (an upcoming clang patch will introduce an assert() on the clang side to catch when they become out of sync).
• getConstantDataArrayInfo() now returns Offset+Length into the ConstantDataArray and corrects handling of zeroinitializers

[MatzeB]

lib/Analysis/ValueTracking.cpp

3038–3039

Looks like you answered your own question by digging out that PR in the next comment :)
That testcase is fixed as well in my latest revision.

lib/Transforms/Utils/SimplifyLibCalls.cpp

458

There are no iterators defined for ConstantDataArray, did I miss something? (Defining them seems tricky to get right to support various datatypes and target/host data conversions).

[efriedma]

lib/Analysis/TargetLibraryInfo.cpp

1420

We should probably have a verifier check to make sure these casts will succeed.

lib/Analysis/ValueTracking.cpp

3043

Do you need to check the type against ElementSize here?

lib/Transforms/Utils/SimplifyLibCalls.cpp

458

No, there aren't any existing iterators.

It doesn't seem that tricky to write, though. It could just be a wrapper around getElementAsInteger; or if you want to get fancy, you could represent it as a pointer+width pair, I guess. (The data is just an array of integers in host byte order.)

[MatzeB]

• Check type in !Array zeroinitializer case. (Technically this shouldn't be necessary as it would be UB otherwise, but optimizing based on this will hardly buy us anything).

lib/Analysis/TargetLibraryInfo.cpp

1420

https://reviews.llvm.org/D32974

lib/Transforms/Utils/SimplifyLibCalls.cpp

458

I tried this and it looks like this: https://reviews.llvm.org/P7994
39 extra lines added for the iterator foo and none of the actual uses gets simpler.
(If you now want to argue that I didn't use llvm::enumerate(), then I'd kindly ask you to present me an example of how the heck I can implement an interator compliant the forward iterator concept where operator* returns a reference! to the underlying object).
I worked on this stuff for >2 hours now and it is definitely "tricky to write" and not really necessary here.

[efriedma]

clang only emits wchar_size on ARM at the moment; that might need to change before this gets merged.

Missing tests for 16-bit wchar_t.

lib/Transforms/Utils/SimplifyLibCalls.cpp

458

Mmm... okay, maybe not as simple as I'd hoped; fine.

[MatzeB]

• Add a test passing a pointer to an array with the wrong size to wcslen.
• Add variants of tests in wcslen-1.ll in wcslen-3.ll that test with sizeof(wchar_t)==2.
• (The clang patch to always emit wchar_size is approved.)

[efriedma]

LGTM.

[MatzeB]

Fixing getConstantStringInfo() here caused some changes in behavior in SelectionDAG memcpy lowering. I'll put in some more fixes before committing...

include/llvm/Analysis/TargetLibraryInfo.h

void setShouldExtI32Return(bool Val) {
     ShouldExtI32Return = Val;
   }
 
   /// Set to true iff i32 parameters to library functions should have signext
   /// attribute if they correspond to C-level int or unsigned int.
   void setShouldSignExtI32Param(bool Val) {
     ShouldSignExtI32Param = Val;
   }
+
+  /// Returns the size of the wchar_t type in bytes.
+  unsigned getWCharSize(const Module &M) const;
+
+  /// Returns size of the default wchar_t type on target \p T. This is mostly
+  /// intended to verify that the size in the frontend matches LLVM. All other
+  /// queries should use getWCharSize() instead.
+  static unsigned getTargetWCharSize(const Triple &T);
 };
 
 /// Provides information about what library functions are available for
 /// the current target.
 ///
 /// This both allows optimizations to handle them specially and frontends to
 /// disable such optimizations through -fno-builtin etc.
 class TargetLibraryInfo {
public:
   /// corresponding to C-level int or unsigned int.  May be zeroext, signext,
   /// or none.
   Attribute::AttrKind getExtAttrForI32Return(bool Signed = true) const {
     if (Impl->ShouldExtI32Return)
       return Signed ? Attribute::SExt : Attribute::ZExt;
     return Attribute::None;
   }
 
+  /// \copydoc TargetLibraryInfoImpl::getWCharSize()
+  unsigned getWCharSize(const Module &M) const {
+    return Impl->getWCharSize(M);
+  }
+
   /// Handle invalidation from the pass manager.
   ///
   /// If we try to invalidate this info, just return false. It cannot become
   /// invalid even if the module or function changes.
   bool invalidate(Module &, const PreservedAnalyses &,
                   ModuleAnalysisManager::Invalidator &) {
     return false;
   }

include/llvm/Analysis/ValueTracking.h

Value *GetPointerBaseWithConstantOffset(Value *Ptr, int64_t &Offset,
                                           const DataLayout &DL);
   static inline const Value *
   GetPointerBaseWithConstantOffset(const Value *Ptr, int64_t &Offset,
                                    const DataLayout &DL) {
     return GetPointerBaseWithConstantOffset(const_cast<Value *>(Ptr), Offset,
                                             DL);
   }
 
-  /// Returns true if the GEP is based on a pointer to a string (array of i8), 
-  /// and is indexing into this string.
-  bool isGEPBasedOnPointerToString(const GEPOperator *GEP);
+  /// Returns true if the GEP is based on a pointer to a string (array of
+  // \p CharSize integers) and is indexing into this string.
+  bool isGEPBasedOnPointerToString(const GEPOperator *GEP,
+                                   unsigned CharSize = 8);
+
+  /// Represents offset+length into a ConstantDataArray.
+  struct ConstantDataArraySlice {
+    /// ConstantDataArray pointer. nullptr indicates a zeroinitializer (a valid
+    /// initializer, it just doesn't fit the ConstantDataArray interface).
+    const ConstantDataArray *Array;
+    /// Slice starts at this Offset.
+    uint64_t Offset;
+    /// Length of the slice.
+    uint64_t Length;
+  };
+
+  /// Returns true if the value \p V is a pointer into a ContantDataArray.
+  /// If successfull \p Index will point to a ConstantDataArray info object
+  /// with an apropriate offset.
+  bool getConstantDataArrayInfo(const Value *V, ConstantDataArraySlice &Slice,
+                                unsigned ElementSize, uint64_t Offset = 0);
 
   /// 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. This does not include the trailing null
   /// character by default. If TrimAtNul is set to false, then this returns any
   /// trailing null characters as well as any other characters that come after
   /// it.
   bool getConstantStringInfo(const Value *V, StringRef &Str,
                              uint64_t Offset = 0, bool TrimAtNul = true);
 
   /// 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 GetStringLength(const Value *V);
+  uint64_t GetStringLength(const Value *V, unsigned CharSize = 8);
 
   /// This method strips off any GEP address adjustments and pointer casts from
   /// the specified value, returning the original object being addressed. Note
   /// that the returned value has pointer type if the specified value does. If
   /// the MaxLookup value is non-zero, it limits the number of instructions to
   /// be stripped off.
   Value *GetUnderlyingObject(Value *V, const DataLayout &DL,
                              unsigned MaxLookup = 6);

include/llvm/IR/Constants.h

public:
 
   /// Return the number of elements in the array or vector.
   unsigned getNumElements() const;
 
   /// Return the size (in bytes) of each element in the array/vector.
   /// The size of the elements is known to be a multiple of one byte.
   uint64_t getElementByteSize() const;
 
-  /// This method returns true if this is an array of i8.
-  bool isString() const;
+  /// This method returns true if this is an array of \p CharSize integers.
+  bool isString(unsigned CharSize = 8) const;
 
   /// This method returns true if the array "isString", ends with a null byte,
   /// and does not contains any other null bytes.
   bool isCString() const;
 
   /// If this array is isString(), then this method returns the array as a
   /// StringRef. Otherwise, it asserts out.
   StringRef getAsString() const {

include/llvm/Transforms/Utils/SimplifyLibCalls.h

private:
   Value *optimizeStrSpn(CallInst *CI, IRBuilder<> &B);
   Value *optimizeStrCSpn(CallInst *CI, IRBuilder<> &B);
   Value *optimizeStrStr(CallInst *CI, IRBuilder<> &B);
   Value *optimizeMemChr(CallInst *CI, IRBuilder<> &B);
   Value *optimizeMemCmp(CallInst *CI, IRBuilder<> &B);
   Value *optimizeMemCpy(CallInst *CI, IRBuilder<> &B);
   Value *optimizeMemMove(CallInst *CI, IRBuilder<> &B);
   Value *optimizeMemSet(CallInst *CI, IRBuilder<> &B);
+  Value *optimizeWcslen(CallInst *CI, IRBuilder<> &B);
   // Wrapper for all String/Memory Library Call Optimizations
   Value *optimizeStringMemoryLibCall(CallInst *CI, IRBuilder<> &B);
 
   // Math Library Optimizations
   Value *optimizeCos(CallInst *CI, IRBuilder<> &B);
   Value *optimizePow(CallInst *CI, IRBuilder<> &B);
   Value *optimizeExp2(CallInst *CI, IRBuilder<> &B);
   Value *optimizeFMinFMax(CallInst *CI, IRBuilder<> &B);
void classifyArgUse(Value *Val, Function *F, bool IsFloat,
                       SmallVectorImpl<CallInst *> &SinCosCalls);
   Value *optimizePrintFString(CallInst *CI, IRBuilder<> &B);
   Value *optimizeSPrintFString(CallInst *CI, IRBuilder<> &B);
   Value *optimizeFPrintFString(CallInst *CI, IRBuilder<> &B);
 
   /// hasFloatVersion - Checks if there is a float version of the specified
   /// function by checking for an existing function with name FuncName + f
   bool hasFloatVersion(StringRef FuncName);
+
+  /// Shared code to optimize strlen+wcslen.
+  Value *optimizeStringLength(CallInst *CI, IRBuilder<> &B, unsigned CharSize);
 };
 } // End llvm namespace
 
 #endif

lib/Analysis/TargetLibraryInfo.cpp

 //===-- TargetLibraryInfo.cpp - Runtime library information ----------------==//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the TargetLibraryInfo class.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/ADT/Triple.h"
+#include "llvm/IR/Constants.h"
 #include "llvm/Support/CommandLine.h"
 using namespace llvm;
 
 static cl::opt<TargetLibraryInfoImpl::VectorLibrary> ClVectorLibrary(
     "vector-library", cl::Hidden, cl::desc("Vector functions library"),
     cl::init(TargetLibraryInfoImpl::NoLibrary),
     cl::values(clEnumValN(TargetLibraryInfoImpl::NoLibrary, "none",
                           "No vector functions library"),
TargetLibraryInfoImpl &TargetLibraryAnalysis::lookupInfoImpl(const Triple &T) {
   std::unique_ptr<TargetLibraryInfoImpl> &Impl =
       Impls[T.normalize()];
   if (!Impl)
     Impl.reset(new TargetLibraryInfoImpl(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) {
   initializeTargetLibraryInfoWrapperPassPass(*PassRegistry::getPassRegistry());
 }
 
 TargetLibraryInfoWrapperPass::TargetLibraryInfoWrapperPass(const Triple &T)
     : ImmutablePass(ID), TLIImpl(T), TLI(TLIImpl) {

lib/Analysis/ValueTracking.cpp

 #include "llvm/Analysis/Loads.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/OptimizationDiagnosticInfo.h"
 #include "llvm/Analysis/VectorUtils.h"
 #include "llvm/IR/CallSite.h"
 #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"
 #include "llvm/IR/GlobalVariable.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Metadata.h"
while (Visited.insert(Ptr).second) {
     } else {
       break;
     }
   }
   Offset = ByteOffset.getSExtValue();
   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
   // has value 0 so that we are sure we're indexing into the initializer.
   const ConstantInt *FirstIdx = dyn_cast<ConstantInt>(GEP->getOperand(1));
   if (!FirstIdx || !FirstIdx->isZero())
     return false;
 
   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.
   V = V->stripPointerCasts();
 
   // If the value is a GEP instruction or constant expression, treat it as an
   // offset.
   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
     // into the array.  If this occurs, we can't say anything meaningful about
     // the string.
     uint64_t StartIdx = 0;
     if (const ConstantInt *CI = dyn_cast<ConstantInt>(GEP->getOperand(2)))
       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
   // variable that is a constant and is initialized. The referenced constant
   // initializer is the array that we'll use for optimization.
   const GlobalVariable *GV = dyn_cast<GlobalVariable>(V);
   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 = "";
+    ArrayTy = dyn_cast<ArrayType>(GV->getValueType());
+    if (!ArrayTy) {
+      Slice.Array = nullptr;
+      Slice.Offset = 0;
+      Slice.Length = 1;
       return true;
     }
-
+    Array = nullptr;
+  } else {
     // This must be a ConstantDataArray.
-  const auto *Array = dyn_cast<ConstantDataArray>(GV->getInitializer());
-  if (!Array || !Array->isString())
+    Array = dyn_cast<ConstantDataArray>(GV->getInitializer());
+    if (!Array)
+      return false;
+    ArrayTy = Array->getType();
+  }
+  if (!ArrayTy->getElementType()->isIntegerTy(ElementSize))
     return false;
 
-  // Get the number of elements in the array.
-  uint64_t NumElts = Array->getType()->getArrayNumElements();
+  uint64_t NumElts = ArrayTy->getArrayNumElements();
+  if (Offset > NumElts)
+    return false;
 
-  // Start out with the entire array in the StringRef.
-  Str = Array->getAsString();
+  Slice.Array = Array;
+  Slice.Offset = Offset;
+  Slice.Length = NumElts - Offset;
+  return true;
+}
 
-  if (Offset > NumElts)
+/// 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 (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
     // terminated, we just return the whole end of string.  The client may know
     // some other way that the string is length-bound.
     Str = Str.substr(0, Str.find('\0'));
   }
   return true;
 }
 
 // These next two are very similar to the above, but also look through PHI
 // nodes.
 // TODO: See if we can integrate these two together.
 
 /// 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();
 
   // If this is a PHI node, there are two cases: either we have already seen it
   // or we haven't.
   if (const PHINode *PN = dyn_cast<PHINode>(V)) {
     if (!PHIs.insert(PN).second)
       return ~0ULL;  // already in the set.
 
     // 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;
 
       if (Len != LenSoFar && LenSoFar != ~0ULL)
         return 0;    // Disagree -> unknown.
       LenSoFar = Len;
     }
 
     // Success, all agree.
     return LenSoFar;
   }
 
   // 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;
     if (Len1 != Len2) return 0;
     return Len1;
   }
 
   // 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;
 }
 
 /// \brief \p PN defines a loop-variant pointer to an object.  Check if the
 /// previous iteration of the loop was referring to the same object as \p PN.
 static bool isSameUnderlyingObjectInLoop(const PHINode *PN,

lib/IR/Constants.cpp

 Constant *ConstantDataSequential::getElementAsConstant(unsigned Elt) const {
   if (getElementType()->isHalfTy() || getElementType()->isFloatTy() ||
       getElementType()->isDoubleTy())
     return ConstantFP::get(getContext(), getElementAsAPFloat(Elt));
 
   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 {
   if (!isString())
     return false;
 
   StringRef Str = getAsString();
 

lib/Transforms/Utils/SimplifyLibCalls.cpp

Value *LibCallSimplifier::optimizeStrNCpy(CallInst *CI, IRBuilder<> &B) {
 
   Type *PT = Callee->getFunctionType()->getParamType(0);
   // strncpy(x, s, c) -> memcpy(x, s, c, 1) [s and c are constant]
   B.CreateMemCpy(Dst, Src, ConstantInt::get(DL.getIntPtrType(PT), Len), 1);
 
   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');
-      
+    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 == StringRef::npos)
+        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;
   }
 
   // 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,
                              SI->getDebugLoc(),
                              "folded strlen(select) to select of constants");
       return B.CreateSelect(SI->getCondition(),
                             ConstantInt::get(CI->getType(), LenTrue - 1),
                             ConstantInt::get(CI->getType(), LenFalse - 1));
     }
   }
 
   // strlen(x) != 0 --> *x != 0
   // strlen(x) == 0 --> *x == 0
   if (isOnlyUsedInZeroEqualityComparison(CI))
     return B.CreateZExt(B.CreateLoad(Src, "strlenfirst"), CI->getType());
 
   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);
   bool HasS2 = getConstantStringInfo(CI->getArgOperand(1), S2);
 
   // strpbrk(s, "") -> nullptr
   // strpbrk("", s) -> nullptr
   if ((HasS1 && S1.empty()) || (HasS2 && S2.empty()))
if (TLI->getLibFunc(*Callee, Func) && TLI->has(Func)) {
     case LibFunc_memcmp:
       return optimizeMemCmp(CI, Builder);
     case LibFunc_memcpy:
       return optimizeMemCpy(CI, Builder);
     case LibFunc_memmove:
       return optimizeMemMove(CI, Builder);
     case LibFunc_memset:
       return optimizeMemSet(CI, Builder);
+    case LibFunc_wcslen:
+      return optimizeWcslen(CI, Builder);
     default:
       break;
     }
   }
   return nullptr;
 }
 
 Value *LibCallSimplifier::optimizeCall(CallInst *CI) {

test/Transforms/InstCombine/wcslen-1.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; Test that the wcslen library call simplifier works correctly.
+;
+; RUN: opt < %s -instcombine -S | FileCheck %s
+
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+
+declare i64 @wcslen(i32*)
+
+@hello = constant [6 x i32] [i32 104, i32 101, i32 108, i32 108, i32 111, i32 0]
+@longer = constant [7 x i32] [i32 108, i32 111, i32 110, i32 103, i32 101, i32 114, i32 0]
+@null = constant [1 x i32] zeroinitializer
+@null_hello = constant [7 x i32] [i32 0, i32 104, i32 101, i32 108, i32 108, i32 111, i32 0]
+@nullstring = constant i32 0
+@a = common global [32 x i32] zeroinitializer, align 1
+@null_hello_mid = constant [13 x i32] [i32 104, i32 101, i32 108, i32 108, i32 111, i32 32, i32 119, i32 111, i32 114, i32 0, i32 108, i32 100, i32 0]
+
+define i64 @test_simplify1() {
+; CHECK-LABEL: @test_simplify1(
+; CHECK-NEXT:    ret i64 5
+;
+  %hello_p = getelementptr [6 x i32], [6 x i32]* @hello, i64 0, i64 0
+  %hello_l = call i64 @wcslen(i32* %hello_p)
+  ret i64 %hello_l
+}
+
+define i64 @test_simplify2() {
+; CHECK-LABEL: @test_simplify2(
+; CHECK-NEXT:    ret i64 0
+;
+  %null_p = getelementptr [1 x i32], [1 x i32]* @null, i64 0, i64 0
+  %null_l = call i64 @wcslen(i32* %null_p)
+  ret i64 %null_l
+}
+
+define i64 @test_simplify3() {
+; CHECK-LABEL: @test_simplify3(
+; CHECK-NEXT:    ret i64 0
+;
+  %null_hello_p = getelementptr [7 x i32], [7 x i32]* @null_hello, i64 0, i64 0
+  %null_hello_l = call i64 @wcslen(i32* %null_hello_p)
+  ret i64 %null_hello_l
+}
+
+define i64 @test_simplify4() {
+; CHECK-LABEL: @test_simplify4(
+; CHECK-NEXT:    ret i64 0
+;
+  %len = tail call i64 @wcslen(i32* @nullstring) nounwind
+  ret i64 %len
+}
+
+; Check wcslen(x) == 0 --> *x == 0.
+
+define i1 @test_simplify5() {
+; CHECK-LABEL: @test_simplify5(
+; CHECK-NEXT:    ret i1 false
+;
+  %hello_p = getelementptr [6 x i32], [6 x i32]* @hello, i64 0, i64 0
+  %hello_l = call i64 @wcslen(i32* %hello_p)
+  %eq_hello = icmp eq i64 %hello_l, 0
+  ret i1 %eq_hello
+}
+
+define i1 @test_simplify6(i32* %str_p) {
+; CHECK-LABEL: @test_simplify6(
+; CHECK-NEXT:    [[STRLENFIRST:%.*]] = load i32, i32* [[STR_P:%.*]], align 4
+; CHECK-NEXT:    [[EQ_NULL:%.*]] = icmp eq i32 [[STRLENFIRST]], 0
+; CHECK-NEXT:    ret i1 [[EQ_NULL]]
+;
+  %str_l = call i64 @wcslen(i32* %str_p)
+  %eq_null = icmp eq i64 %str_l, 0
+  ret i1 %eq_null
+}
+
+; Check wcslen(x) != 0 --> *x != 0.
+
+define i1 @test_simplify7() {
+; CHECK-LABEL: @test_simplify7(
+; CHECK-NEXT:    ret i1 true
+;
+  %hello_p = getelementptr [6 x i32], [6 x i32]* @hello, i64 0, i64 0
+  %hello_l = call i64 @wcslen(i32* %hello_p)
+  %ne_hello = icmp ne i64 %hello_l, 0
+  ret i1 %ne_hello
+}
+
+define i1 @test_simplify8(i32* %str_p) {
+; CHECK-LABEL: @test_simplify8(
+; CHECK-NEXT:    [[STRLENFIRST:%.*]] = load i32, i32* [[STR_P:%.*]], align 4
+; CHECK-NEXT:    [[NE_NULL:%.*]] = icmp ne i32 [[STRLENFIRST]], 0
+; CHECK-NEXT:    ret i1 [[NE_NULL]]
+;
+  %str_l = call i64 @wcslen(i32* %str_p)
+  %ne_null = icmp ne i64 %str_l, 0
+  ret i1 %ne_null
+}
+
+define i64 @test_simplify9(i1 %x) {
+; CHECK-LABEL: @test_simplify9(
+; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[X:%.*]], i64 5, i64 6
+; CHECK-NEXT:    ret i64 [[TMP1]]
+;
+  %hello = getelementptr [6 x i32], [6 x i32]* @hello, i64 0, i64 0
+  %longer = getelementptr [7 x i32], [7 x i32]* @longer, i64 0, i64 0
+  %s = select i1 %x, i32* %hello, i32* %longer
+  %l = call i64 @wcslen(i32* %s)
+  ret i64 %l
+}
+
+; Check the case that should be simplified to a sub instruction.
+; wcslen(@hello + x) --> 5 - x
+
+define i64 @test_simplify10(i32 %x) {
+; CHECK-LABEL: @test_simplify10(
+; CHECK-NEXT:    [[TMP1:%.*]] = sext i32 [[X:%.*]] to i64
+; CHECK-NEXT:    [[TMP2:%.*]] = sub nsw i64 5, [[TMP1]]
+; CHECK-NEXT:    ret i64 [[TMP2]]
+;
+  %hello_p = getelementptr inbounds [6 x i32], [6 x i32]* @hello, i32 0, i32 %x
+  %hello_l = call i64 @wcslen(i32* %hello_p)
+  ret i64 %hello_l
+}
+
+; wcslen(@null_hello_mid + (x & 7)) --> 9 - (x & 7)
+
+define i64 @test_simplify11(i32 %x) {
+; CHECK-LABEL: @test_simplify11(
+; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], 7
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i32 [[AND]] to i64
+; CHECK-NEXT:    [[TMP2:%.*]] = sub nsw i64 9, [[TMP1]]
+; CHECK-NEXT:    ret i64 [[TMP2]]
+;
+  %and = and i32 %x, 7
+  %hello_p = getelementptr inbounds [13 x i32], [13 x i32]* @null_hello_mid, i32 0, i32 %and
+  %hello_l = call i64 @wcslen(i32* %hello_p)
+  ret i64 %hello_l
+}
+
+; Check cases that shouldn't be simplified.
+
+define i64 @test_no_simplify1() {
+; CHECK-LABEL: @test_no_simplify1(
+; CHECK-NEXT:    [[A_L:%.*]] = call i64 @wcslen(i32* getelementptr inbounds ([32 x i32], [32 x i32]* @a, i64 0, i64 0))
+; CHECK-NEXT:    ret i64 [[A_L]]
+;
+  %a_p = getelementptr [32 x i32], [32 x i32]* @a, i64 0, i64 0
+  %a_l = call i64 @wcslen(i32* %a_p)
+  ret i64 %a_l
+}
+
+; wcslen(@null_hello + x) should not be simplified to a sub instruction.
+
+define i64 @test_no_simplify2(i32 %x) {
+; CHECK-LABEL: @test_no_simplify2(
+; CHECK-NEXT:    [[TMP1:%.*]] = sext i32 [[X:%.*]] to i64
+; CHECK-NEXT:    [[HELLO_P:%.*]] = getelementptr inbounds [7 x i32], [7 x i32]* @null_hello, i64 0, i64 [[TMP1]]
+; CHECK-NEXT:    [[HELLO_L:%.*]] = call i64 @wcslen(i32* [[HELLO_P]])
+; CHECK-NEXT:    ret i64 [[HELLO_L]]
+;
+  %hello_p = getelementptr inbounds [7 x i32], [7 x i32]* @null_hello, i32 0, i32 %x
+  %hello_l = call i64 @wcslen(i32* %hello_p)
+  ret i64 %hello_l
+}
+
+; wcslen(@null_hello_mid + (x & 15)) should not be simplified to a sub instruction.
+
+define i64 @test_no_simplify3(i32 %x) {
+; CHECK-LABEL: @test_no_simplify3(
+; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], 15
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i32 [[AND]] to i64
+; CHECK-NEXT:    [[HELLO_P:%.*]] = getelementptr inbounds [13 x i32], [13 x i32]* @null_hello_mid, i64 0, i64 [[TMP1]]
+; CHECK-NEXT:    [[HELLO_L:%.*]] = call i64 @wcslen(i32* [[HELLO_P]])
+; CHECK-NEXT:    ret i64 [[HELLO_L]]
+;
+  %and = and i32 %x, 15
+  %hello_p = getelementptr inbounds [13 x i32], [13 x i32]* @null_hello_mid, i32 0, i32 %and
+  %hello_l = call i64 @wcslen(i32* %hello_p)
+  ret i64 %hello_l
+}

test/Transforms/InstCombine/wcslen-2.ll

+; Test that the wcslen library call simplifier works correctly.
+;
+; RUN: opt < %s -instcombine -S | FileCheck %s
+
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+
+@hello = constant [6 x i32] [i32 104, i32 101, i32 108, i32 108, i32 111, i32 0]
+
+declare i64 @wcslen(i32*, i32)
+
+define i64 @test_no_simplify1() {
+; CHECK-LABEL: @test_no_simplify1(
+  %hello_p = getelementptr [6 x i32], [6 x i32]* @hello, i64 0, i64 0
+  %hello_l = call i64 @wcslen(i32* %hello_p, i32 187)
+; CHECK-NEXT: %hello_l = call i64 @wcslen
+  ret i64 %hello_l
+; CHECK-NEXT: ret i64 %hello_l
+}