From 24604110efc862423f7b2724e93a8793eefd44b2 Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Wed, 16 Dec 2009 09:32:05 +0000 Subject: [PATCH] reapply my strstr optimization. I have reproduced the x86-64 bootstrap miscompile (i386.o miscompares) but it happens both with and without this patch. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@91532 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Scalar/SimplifyLibCalls.cpp | 84 +++++++++++++++++++--- test/Transforms/SimplifyLibCalls/StrStr.ll | 48 +++++++++++++ 2 files changed, 123 insertions(+), 9 deletions(-) diff --git a/lib/Transforms/Scalar/SimplifyLibCalls.cpp b/lib/Transforms/Scalar/SimplifyLibCalls.cpp index 6fd884bbd6d..192bcbd6c29 100644 --- a/lib/Transforms/Scalar/SimplifyLibCalls.cpp +++ b/lib/Transforms/Scalar/SimplifyLibCalls.cpp @@ -76,6 +76,11 @@ public: /// return value has 'intptr_t' type. Value *EmitStrLen(Value *Ptr, IRBuilder<> &B); + /// EmitStrChr - Emit a call to the strchr function to the builder, for the + /// specified pointer and character. Ptr is required to be some pointer type, + /// and the return value has 'i8*' type. + Value *EmitStrChr(Value *Ptr, char C, IRBuilder<> &B); + /// EmitMemCpy - Emit a call to the memcpy function to the builder. This /// always expects that the size has type 'intptr_t' and Dst/Src are pointers. Value *EmitMemCpy(Value *Dst, Value *Src, Value *Len, @@ -151,6 +156,26 @@ Value *LibCallOptimization::EmitStrLen(Value *Ptr, IRBuilder<> &B) { return CI; } +/// EmitStrChr - Emit a call to the strchr function to the builder, for the +/// specified pointer and character. Ptr is required to be some pointer type, +/// and the return value has 'i8*' type. +Value *LibCallOptimization::EmitStrChr(Value *Ptr, char C, IRBuilder<> &B) { + Module *M = Caller->getParent(); + AttributeWithIndex AWI = + AttributeWithIndex::get(~0u, Attribute::ReadOnly | Attribute::NoUnwind); + + const Type *I8Ptr = Type::getInt8PtrTy(*Context); + const Type *I32Ty = Type::getInt32Ty(*Context); + Constant *StrChr = M->getOrInsertFunction("strchr", AttrListPtr::get(&AWI, 1), + I8Ptr, I8Ptr, I32Ty, NULL); + CallInst *CI = B.CreateCall2(StrChr, CastToCStr(Ptr, B), + ConstantInt::get(I32Ty, C), "strchr"); + if (const Function *F = dyn_cast(StrChr->stripPointerCasts())) + CI->setCallingConv(F->getCallingConv()); + return CI; +} + + /// EmitMemCpy - Emit a call to the memcpy function to the builder. This always /// expects that the size has type 'intptr_t' and Dst/Src are pointers. Value *LibCallOptimization::EmitMemCpy(Value *Dst, Value *Src, Value *Len, @@ -890,7 +915,7 @@ struct StrLenOpt : public LibCallOptimization { }; //===---------------------------------------===// -// 'strto*' Optimizations +// 'strto*' Optimizations. This handles strtol, strtod, strtof, strtoul, etc. struct StrToOpt : public LibCallOptimization { virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { @@ -910,6 +935,52 @@ struct StrToOpt : public LibCallOptimization { } }; +//===---------------------------------------===// +// 'strstr' Optimizations + +struct StrStrOpt : public LibCallOptimization { + virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) { + const FunctionType *FT = Callee->getFunctionType(); + if (FT->getNumParams() != 2 || + !isa(FT->getParamType(0)) || + !isa(FT->getParamType(1)) || + !isa(FT->getReturnType())) + return 0; + + // fold strstr(x, x) -> x. + if (CI->getOperand(1) == CI->getOperand(2)) + return B.CreateBitCast(CI->getOperand(1), CI->getType()); + + // See if either input string is a constant string. + std::string SearchStr, ToFindStr; + bool HasStr1 = GetConstantStringInfo(CI->getOperand(1), SearchStr); + bool HasStr2 = GetConstantStringInfo(CI->getOperand(2), ToFindStr); + + // fold strstr(x, "") -> x. + if (HasStr2 && ToFindStr.empty()) + return B.CreateBitCast(CI->getOperand(1), CI->getType()); + + // If both strings are known, constant fold it. + if (HasStr1 && HasStr2) { + std::string::size_type Offset = SearchStr.find(ToFindStr); + + if (Offset == std::string::npos) // strstr("foo", "bar") -> null + return Constant::getNullValue(CI->getType()); + + // strstr("abcd", "bc") -> gep((char*)"abcd", 1) + Value *Result = CastToCStr(CI->getOperand(1), B); + Result = B.CreateConstInBoundsGEP1_64(Result, Offset, "strstr"); + return B.CreateBitCast(Result, CI->getType()); + } + + // fold strstr(x, "y") -> strchr(x, 'y'). + if (HasStr2 && ToFindStr.size() == 1) + return B.CreateBitCast(EmitStrChr(CI->getOperand(1), ToFindStr[0], B), + CI->getType()); + return 0; + } +}; + //===---------------------------------------===// // 'memcmp' Optimizations @@ -1675,8 +1746,8 @@ namespace { // String and Memory LibCall Optimizations StrCatOpt StrCat; StrNCatOpt StrNCat; StrChrOpt StrChr; StrCmpOpt StrCmp; StrNCmpOpt StrNCmp; StrCpyOpt StrCpy; StrNCpyOpt StrNCpy; StrLenOpt StrLen; - StrToOpt StrTo; MemCmpOpt MemCmp; MemCpyOpt MemCpy; MemMoveOpt MemMove; - MemSetOpt MemSet; + StrToOpt StrTo; StrStrOpt StrStr; + MemCmpOpt MemCmp; MemCpyOpt MemCpy; MemMoveOpt MemMove; MemSetOpt MemSet; // Math Library Optimizations PowOpt Pow; Exp2Opt Exp2; UnaryDoubleFPOpt UnaryDoubleFP; // Integer Optimizations @@ -1738,6 +1809,7 @@ void SimplifyLibCalls::InitOptimizations() { Optimizations["strtoll"] = &StrTo; Optimizations["strtold"] = &StrTo; Optimizations["strtoull"] = &StrTo; + Optimizations["strstr"] = &StrStr; Optimizations["memcmp"] = &MemCmp; Optimizations["memcpy"] = &MemCpy; Optimizations["memmove"] = &MemMove; @@ -2644,12 +2716,6 @@ bool SimplifyLibCalls::doInitialization(Module &M) { // * strcspn("",a) -> 0 // * strcspn(s,"") -> strlen(a) // -// strstr: (PR5783) -// * strstr(x,x) -> x -// * strstr(x, "") -> x -// * strstr(x, "a") -> strchr(x, 'a') -// * strstr(s1,s2) -> result (if s1 and s2 are constant strings) -// // tan, tanf, tanl: // * tan(atan(x)) -> x // diff --git a/test/Transforms/SimplifyLibCalls/StrStr.ll b/test/Transforms/SimplifyLibCalls/StrStr.ll index e69de29bb2d..2cac2d498ce 100644 --- a/test/Transforms/SimplifyLibCalls/StrStr.ll +++ b/test/Transforms/SimplifyLibCalls/StrStr.ll @@ -0,0 +1,48 @@ +; RUN: opt < %s -simplify-libcalls -S | FileCheck %s +; PR5783 + +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-n8:16:32" +target triple = "i386-apple-darwin9.0" + +@.str = private constant [1 x i8] zeroinitializer ; <[1 x i8]*> [#uses=1] +@.str1 = private constant [2 x i8] c"a\00" ; <[2 x i8]*> [#uses=1] +@.str2 = private constant [6 x i8] c"abcde\00" ; <[6 x i8]*> [#uses=1] +@.str3 = private constant [4 x i8] c"bcd\00" ; <[4 x i8]*> [#uses=1] + +define i8* @test1(i8* %P) nounwind readonly { +entry: + %call = tail call i8* @strstr(i8* %P, i8* getelementptr inbounds ([1 x i8]* @.str, i32 0, i32 0)) nounwind ; [#uses=1] + ret i8* %call +; strstr(P, "") -> P +; CHECK: @test1 +; CHECK: ret i8* %P +} + +declare i8* @strstr(i8*, i8* nocapture) nounwind readonly + +define i8* @test2(i8* %P) nounwind readonly { +entry: + %call = tail call i8* @strstr(i8* %P, i8* getelementptr inbounds ([2 x i8]* @.str1, i32 0, i32 0)) nounwind ; [#uses=1] + ret i8* %call +; strstr(P, "a") -> strchr(P, 'a') +; CHECK: @test2 +; CHECK: @strchr(i8* %P, i32 97) +} + +define i8* @test3(i8* nocapture %P) nounwind readonly { +entry: + %call = tail call i8* @strstr(i8* getelementptr inbounds ([6 x i8]* @.str2, i32 0, i32 0), i8* getelementptr inbounds ([4 x i8]* @.str3, i32 0, i32 0)) nounwind ; [#uses=1] + ret i8* %call +; strstr("abcde", "bcd") -> "abcde"+1 +; CHECK: @test3 +; CHECK: getelementptr inbounds ([6 x i8]* @.str2, i32 0, i64 1) +} + +define i8* @test4(i8* %P) nounwind readonly { +entry: + %call = tail call i8* @strstr(i8* %P, i8* %P) nounwind ; [#uses=1] + ret i8* %call +; strstr(P, P) -> P +; CHECK: @test4 +; CHECK: ret i8* %P +} -- 2.34.1