SimplifyLibCalls: Add basic optimization of memchr calls.

This is just memchr(x, y, 0) -> nullptr and constant folding.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@232896 91177308-0d34-0410-b5e6-96231b3b80d8

diff --git a/include/llvm/ADT/StringRef.h b/include/llvm/ADT/StringRef.h
index 6111c42da9dced36ed905fb0e715865b0f4cdd91..4d491e8606ac5d834902edbb9cec219d64759266 100644 (file)
--- a/include/llvm/ADT/StringRef.h
+++ b/include/llvm/ADT/StringRef.h
@@ -238,9 +238,12 @@ namespace llvm {
     /// \returns The index of the first occurrence of \p C, or npos if not
     /// found.
     size_t find(char C, size_t From = 0) const {
-      for (size_t i = std::min(From, Length), e = Length; i != e; ++i)
-        if (Data[i] == C)
-          return i;
+      if (Length != 0) {
+        size_t FindBegin = std::min(From, Length);
+        if (const void *Found =
+                std::memchr(Data + FindBegin, C, Length - FindBegin))
+          return static_cast<const char *>(Found) - Data;
+      }
       return npos;
     }
 

diff --git a/include/llvm/Transforms/Utils/SimplifyLibCalls.h b/include/llvm/Transforms/Utils/SimplifyLibCalls.h
index 4f2ca9de4fa67e4b1034b1a23a68afb51cfc710c..41159603aae5ead751143e7bf2ba666435d4aef6 100644 (file)
--- a/include/llvm/Transforms/Utils/SimplifyLibCalls.h
+++ b/include/llvm/Transforms/Utils/SimplifyLibCalls.h
@@ -116,6 +116,7 @@ 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);

diff --git a/lib/Transforms/Utils/SimplifyLibCalls.cpp b/lib/Transforms/Utils/SimplifyLibCalls.cpp
index a30514e4d9e860b5533db45b6dbc67f036a0abaf..0d0b77a6a3e599ce96f4ed6e453ad6000bebcefe 100644 (file)
--- a/lib/Transforms/Utils/SimplifyLibCalls.cpp
+++ b/lib/Transforms/Utils/SimplifyLibCalls.cpp
@@ -745,6 +745,44 @@ Value *LibCallSimplifier::optimizeStrStr(CallInst *CI, IRBuilder<> &B) {
   return nullptr;
 }
 
+Value *LibCallSimplifier::optimizeMemChr(CallInst *CI, IRBuilder<> &B) {
+  Function *Callee = CI->getCalledFunction();
+  FunctionType *FT = Callee->getFunctionType();
+  if (FT->getNumParams() != 3 || !FT->getParamType(0)->isPointerTy() ||
+      !FT->getParamType(1)->isIntegerTy(32) ||
+      !FT->getParamType(2)->isIntegerTy() ||
+      !FT->getReturnType()->isPointerTy())
+    return nullptr;
+
+  Value *SrcStr = CI->getArgOperand(0);
+  ConstantInt *CharC = dyn_cast<ConstantInt>(CI->getArgOperand(1));
+  ConstantInt *LenC = dyn_cast<ConstantInt>(CI->getArgOperand(2));
+
+  // memchr(x, y, 0) -> null
+  if (LenC && LenC->isNullValue())
+    return Constant::getNullValue(CI->getType());
+
+  // Check if all arguments are constants.  If so, we can constant fold.
+  StringRef Str;
+  if (!CharC || !LenC ||
+      !getConstantStringInfo(SrcStr, Str, /*Offset=*/0,
+                             /*TrimAtNul=*/false))
+    return nullptr;
+
+  // Truncate the string to LenC. If Str is smaller than LenC we will still only
+  // scan the string, as reading past the end of it is undefined and we can just
+  // return null if we don't find the char.
+  Str = Str.substr(0, LenC->getZExtValue());
+
+  // Compute the offset.
+  size_t I = Str.find(CharC->getSExtValue() & 0xFF);
+  if (I == StringRef::npos) // Didn't find the char.  memchr returns null.
+    return Constant::getNullValue(CI->getType());
+
+  // memchr(s+n,c,l) -> gep(s+n+i,c)
+  return B.CreateGEP(SrcStr, B.getInt64(I), "memchr");
+}
+
 Value *LibCallSimplifier::optimizeMemCmp(CallInst *CI, IRBuilder<> &B) {
   Function *Callee = CI->getCalledFunction();
   FunctionType *FT = Callee->getFunctionType();
@@ -1852,6 +1890,8 @@ Value *LibCallSimplifier::optimizeStringMemoryLibCall(CallInst *CI,
       return optimizeStrCSpn(CI, Builder);
     case LibFunc::strstr:
       return optimizeStrStr(CI, Builder);
+    case LibFunc::memchr:
+      return optimizeMemChr(CI, Builder);
     case LibFunc::memcmp:
       return optimizeMemCmp(CI, Builder);
     case LibFunc::memcpy:

diff --git a/test/Transforms/InstCombine/memchr.ll b/test/Transforms/InstCombine/memchr.ll
new file mode 100644 (file)
index 0000000..4cadbfa
--- /dev/null
+++ b/test/Transforms/InstCombine/memchr.ll
@@ -0,0 +1,121 @@
+; Test that the memchr library call simplifier works correctly.
+; RUN: opt < %s -instcombine -S | FileCheck %s
+
+target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:128:128"
+
+@hello = constant [14 x i8] c"hello world\5Cn\00"
+@hellonull = constant [14 x i8] c"hello\00world\5Cn\00"
+@null = constant [1 x i8] zeroinitializer
+@chp = global i8* zeroinitializer
+
+declare i8* @memchr(i8*, i32, i32)
+
+define void @test1() {
+; CHECK-LABEL: @test1
+; CHECK: store i8* getelementptr inbounds ([14 x i8], [14 x i8]* @hello, i32 0, i32 6)
+; CHECK-NOT: call i8* @memchr
+; CHECK: ret void
+
+  %str = getelementptr [14 x i8], [14 x i8]* @hello, i32 0, i32 0
+  %dst = call i8* @memchr(i8* %str, i32 119, i32 14)
+  store i8* %dst, i8** @chp
+  ret void
+}
+
+define void @test2() {
+; CHECK-LABEL: @test2
+; CHECK: store i8* null, i8** @chp, align 4
+; CHECK-NOT: call i8* @memchr
+; CHECK: ret void
+
+  %str = getelementptr [1 x i8], [1 x i8]* @null, i32 0, i32 0
+  %dst = call i8* @memchr(i8* %str, i32 119, i32 1)
+  store i8* %dst, i8** @chp
+  ret void
+}
+
+define void @test3() {
+; CHECK-LABEL: @test3
+; CHECK: store i8* getelementptr inbounds ([14 x i8], [14 x i8]* @hello, i32 0, i32 13)
+; CHECK-NOT: call i8* @memchr
+; CHECK: ret void
+
+  %src = getelementptr [14 x i8], [14 x i8]* @hello, i32 0, i32 0
+  %dst = call i8* @memchr(i8* %src, i32 0, i32 14)
+  store i8* %dst, i8** @chp
+  ret void
+}
+
+define void @test4(i32 %chr) {
+; CHECK-LABEL: @test4
+; CHECK: call i8* @memchr
+; CHECK-NOT: call i8* @memchr
+; CHECK: ret void
+
+  %src = getelementptr [14 x i8], [14 x i8]* @hello, i32 0, i32 0
+  %dst = call i8* @memchr(i8* %src, i32 %chr, i32 14)
+  store i8* %dst, i8** @chp
+  ret void
+}
+
+define void @test5() {
+; CHECK-LABEL: @test5
+; CHECK: store i8* getelementptr inbounds ([14 x i8], [14 x i8]* @hello, i32 0, i32 13)
+; CHECK-NOT: call i8* @memchr
+; CHECK: ret void
+
+  %src = getelementptr [14 x i8], [14 x i8]* @hello, i32 0, i32 0
+  %dst = call i8* @memchr(i8* %src, i32 65280, i32 14)
+  store i8* %dst, i8** @chp
+  ret void
+}
+
+define void @test6() {
+; CHECK-LABEL: @test6
+; CHECK: store i8* getelementptr inbounds ([14 x i8], [14 x i8]* @hello, i32 0, i32 6)
+; CHECK-NOT: call i8* @memchr
+; CHECK: ret void
+
+  %src = getelementptr [14 x i8], [14 x i8]* @hello, i32 0, i32 0
+; Overflow, but we still find the right thing.
+  %dst = call i8* @memchr(i8* %src, i32 119, i32 100)
+  store i8* %dst, i8** @chp
+  ret void
+}
+
+define void @test7() {
+; CHECK-LABEL: @test7
+; CHECK: store i8* null, i8** @chp, align 4
+; CHECK-NOT: call i8* @memchr
+; CHECK: ret void
+
+  %src = getelementptr [14 x i8], [14 x i8]* @hello, i32 0, i32 0
+; Overflow
+  %dst = call i8* @memchr(i8* %src, i32 120, i32 100)
+  store i8* %dst, i8** @chp
+  ret void
+}
+
+define void @test8() {
+; CHECK-LABEL: @test8
+; CHECK: store i8* getelementptr inbounds ([14 x i8], [14 x i8]* @hellonull, i32 0, i32 6)
+; CHECK-NOT: call i8* @memchr
+; CHECK: ret void
+
+  %str = getelementptr [14 x i8], [14 x i8]* @hellonull, i32 0, i32 0
+  %dst = call i8* @memchr(i8* %str, i32 119, i32 14)
+  store i8* %dst, i8** @chp
+  ret void
+}
+
+define void @test9() {
+; CHECK-LABEL: @test9
+; CHECK: store i8* getelementptr inbounds ([14 x i8], [14 x i8]* @hellonull, i32 0, i32 6)
+; CHECK-NOT: call i8* @memchr
+; CHECK: ret void
+
+  %str = getelementptr [14 x i8], [14 x i8]* @hellonull, i32 0, i32 2
+  %dst = call i8* @memchr(i8* %str, i32 119, i32 12)
+  store i8* %dst, i8** @chp
+  ret void
+}