From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 59461 invoked by alias); 23 Sep 2016 14:07:39 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 59449 invoked by uid 89); 23 Sep 2016 14:07:38 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.7 required=5.0 tests=AWL,BAYES_00,KAM_LOTSOFHASH,SPF_PASS autolearn=no version=3.3.2 spammy=869, 48,9, SRC, strcat X-HELO: eu-smtp-delivery-143.mimecast.com Received: from eu-smtp-delivery-143.mimecast.com (HELO eu-smtp-delivery-143.mimecast.com) (146.101.78.143) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Fri, 23 Sep 2016 14:07:28 +0000 Received: from EUR03-DB5-obe.outbound.protection.outlook.com (mail-db5eur03lp0083.outbound.protection.outlook.com [94.245.120.83]) (Using TLS) by eu-smtp-1.mimecast.com with ESMTP id uk-mta-9-fIH0Ue-EP1GOLw04KeWtTA-1; Fri, 23 Sep 2016 15:07:23 +0100 Received: from AM5PR0802MB2610.eurprd08.prod.outlook.com (10.175.46.18) by AM5PR0802MB2609.eurprd08.prod.outlook.com (10.175.46.17) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384_P384) id 15.1.629.8; Fri, 23 Sep 2016 14:07:21 +0000 Received: from AM5PR0802MB2610.eurprd08.prod.outlook.com ([10.175.46.18]) by AM5PR0802MB2610.eurprd08.prod.outlook.com ([10.175.46.18]) with mapi id 15.01.0639.008; Fri, 23 Sep 2016 14:07:21 +0000 From: Wilco Dijkstra To: GCC Patches CC: nd , Richard Biener , "Jakub Jelinek" Subject: [PATCH v3] Optimize strchr to strlen Date: Fri, 23 Sep 2016 14:18:00 -0000 Message-ID: x-ms-office365-filtering-correlation-id: 9d2b1fd1-d438-4137-87a4-08d3e3baefa6 x-microsoft-exchange-diagnostics: 1;AM5PR0802MB2609;20:yPJy84jmvPZaAg7YKe8u36hAJE5LjEHeVCRqxgYLBU56K/+DBnqjxZHYxjoGmd0yImXA9LHk+fWQKjHeEOyujYxZDN0B3/IxczeGdcf0jxg6IjyNZwFtP2GVJjWad56TDOhkKp9eMq34AwuXltCJFACG7eTWQVjL9jGcEVpu47I= x-microsoft-antispam: UriScan:;BCL:0;PCL:0;RULEID:;SRVR:AM5PR0802MB2609; nodisclaimer: True x-microsoft-antispam-prvs: x-exchange-antispam-report-test: UriScan:(180628864354917)(22074186197030)(183786458502308); x-exchange-antispam-report-cfa-test: BCL:0;PCL:0;RULEID:(6040176)(601004)(2401047)(8121501046)(5005006)(3002001)(10201501046)(6055026);SRVR:AM5PR0802MB2609;BCL:0;PCL:0;RULEID:;SRVR:AM5PR0802MB2609; x-forefront-prvs: 0074BBE012 x-forefront-antispam-report: SFV:NSPM;SFS:(10009020)(6009001)(7916002)(189002)(377424004)(199003)(54534003)(7696004)(11100500001)(76576001)(110136003)(8936002)(2900100001)(3280700002)(122556002)(66066001)(19580395003)(15975445007)(87936001)(4326007)(77096005)(81166006)(97736004)(2906002)(6916009)(7846002)(81156014)(8676002)(5660300001)(3660700001)(9686002)(305945005)(74316002)(7736002)(19580405001)(86362001)(575784001)(5002640100001)(33656002)(229853001)(92566002)(586003)(102836003)(68736007)(3846002)(106116001)(105586002)(50986999)(10400500002)(101416001)(54356999)(189998001)(6116002)(106356001)(40753002);DIR:OUT;SFP:1101;SCL:1;SRVR:AM5PR0802MB2609;H:AM5PR0802MB2610.eurprd08.prod.outlook.com;FPR:;SPF:None;PTR:InfoNoRecords;MX:1;A:1;LANG:en; spamdiagnosticoutput: 1:99 spamdiagnosticmetadata: NSPM MIME-Version: 1.0 X-OriginatorOrg: arm.com X-MS-Exchange-CrossTenant-originalarrivaltime: 23 Sep 2016 14:07:21.0800 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: f34e5979-57d9-4aaa-ad4d-b122a662184d X-MS-Exchange-Transport-CrossTenantHeadersStamped: AM5PR0802MB2609 X-MC-Unique: fIH0Ue-EP1GOLw04KeWtTA-1 Content-Type: text/plain; charset=WINDOWS-1252 Content-Transfer-Encoding: quoted-printable X-SW-Source: 2016-09/txt/msg01688.txt.bz2 After discussion (https://gcc.gnu.org/ml/gcc-patches/2016-09/msg00718.html) here is the latest version of the strchr patch. This uses a gimple stateme= nt for the pointer addition so the gsi_prev always points at the strlen call. Optimize strchr (s, 0) to s + strlen (s). strchr (s, 0) appears a common idiom for finding the end of a string, however it is not a very efficient way of doing so. Strlen is a much simpler operation which is significantly faster (eg. on x86 strlen is 50% faster for strings of 8 bytes and about twice as fast as strchr on strings of 1KB). OK for commit? ChangeLog: 2016-09-23 Wilco Dijkstra gcc/ * gcc/gimple-fold.c (gimple_fold_builtin_strchr): New function to optimize strchr (s, 0) to strlen. (gimple_fold_builtin): Add BUILT_IN_STRCHR case. testsuite/ * gcc/testsuite/gcc.dg/strlenopt-20.c: Update test. * gcc/testsuite/gcc.dg/strlenopt-21.c: Likewise. * gcc/testsuite/gcc.dg/strlenopt-22.c: Likewise. * gcc/testsuite/gcc.dg/strlenopt-22g.c: Likewise. * gcc/testsuite/gcc.dg/strlenopt-26.c: Likewise. * gcc/testsuite/gcc.dg/strlenopt-5.c: Likewise. * gcc/testsuite/gcc.dg/strlenopt-7.c: Likewise. * gcc/testsuite/gcc.dg/strlenopt-9.c: Likewise. -- diff --git a/gcc/gimple-fold.c b/gcc/gimple-fold.c index addabb745efc73465f313d1d591aea383f7f4a13..ddf4cf0ae68ef6708377fdb1a2b= 45575d90da799 100644 --- a/gcc/gimple-fold.c +++ b/gcc/gimple-fold.c @@ -1457,6 +1457,55 @@ gimple_fold_builtin_strncpy (gimple_stmt_iterator *g= si, return true; } =20 +/* Simplify strchr (str, 0) into str + strlen (str). + In general strlen is significantly faster than strchr + due to being a simpler operation. */ +static bool +gimple_fold_builtin_strchr (gimple_stmt_iterator *gsi) +{ + gimple *stmt =3D gsi_stmt (*gsi); + tree str =3D gimple_call_arg (stmt, 0); + tree c =3D gimple_call_arg (stmt, 1); + location_t loc =3D gimple_location (stmt); + + if (optimize_function_for_size_p (cfun)) + return false; + + if (!integer_zerop (c) || !gimple_call_lhs (stmt)) + return false; + + tree len; + tree strlen_fn =3D builtin_decl_implicit (BUILT_IN_STRLEN); + + if (!strlen_fn) + return false; + + /* Create newstr =3D strlen (str). */ + gimple_seq stmts =3D NULL; + gimple *new_stmt =3D gimple_build_call (strlen_fn, 1, str); + gimple_set_location (new_stmt, loc); + if (gimple_in_ssa_p (cfun)) + len =3D make_ssa_name (size_type_node); + else + len =3D create_tmp_reg (size_type_node); + gimple_call_set_lhs (new_stmt, len); + gimple_seq_add_stmt_without_update (&stmts, new_stmt); + + /* Create (str p+ strlen (str)). */ + new_stmt =3D gimple_build_assign (gimple_call_lhs (stmt), + POINTER_PLUS_EXPR, str, len); + gimple_seq_add_stmt_without_update (&stmts, new_stmt); + gsi_replace_with_seq_vops (gsi, stmts); + /* gsi now points at the assignment to the lhs, get a + stmt iterator to the strlen. + ??? We can't use gsi_for_stmt as that doesn't work when the + CFG isn't built yet. */ + gimple_stmt_iterator gsi2 =3D *gsi; + gsi_prev (&gsi2); + fold_stmt (&gsi2); + return true; +} + /* Simplify a call to the strcat builtin. DST and SRC are the arguments to the call. =20 @@ -2898,6 +2947,8 @@ gimple_fold_builtin (gimple_stmt_iterator *gsi) gimple_call_arg (stmt, 1)); case BUILT_IN_STRNCAT: return gimple_fold_builtin_strncat (gsi); + case BUILT_IN_STRCHR: + return gimple_fold_builtin_strchr (gsi); case BUILT_IN_FPUTS: return gimple_fold_builtin_fputs (gsi, gimple_call_arg (stmt, 0), gimple_call_arg (stmt, 1), false); diff --git a/gcc/testsuite/gcc.dg/strlenopt-20.c b/gcc/testsuite/gcc.dg/str= lenopt-20.c index a83e845c26d88e5acdcabf142f7b319136663488..7b483eaeac1aa47278111a92148= a16f00b2aaa2d 100644 --- a/gcc/testsuite/gcc.dg/strlenopt-20.c +++ b/gcc/testsuite/gcc.dg/strlenopt-20.c @@ -86,9 +86,9 @@ main () return 0; } =20 -/* { dg-final { scan-tree-dump-times "strlen \\(" 1 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strlen \\(" 2 "strlen" } } */ /* { dg-final { scan-tree-dump-times "memcpy \\(" 4 "strlen" } } */ /* { dg-final { scan-tree-dump-times "strcpy \\(" 0 "strlen" } } */ /* { dg-final { scan-tree-dump-times "strcat \\(" 0 "strlen" } } */ -/* { dg-final { scan-tree-dump-times "strchr \\(" 1 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strchr \\(" 0 "strlen" } } */ /* { dg-final { scan-tree-dump-times "stpcpy \\(" 0 "strlen" } } */ diff --git a/gcc/testsuite/gcc.dg/strlenopt-21.c b/gcc/testsuite/gcc.dg/str= lenopt-21.c index e22fa9fca9ba14354db2cd5f602283b64bd8dcac..05b85a49dde0a7f5d269174fd42= 69e40be910dbd 100644 --- a/gcc/testsuite/gcc.dg/strlenopt-21.c +++ b/gcc/testsuite/gcc.dg/strlenopt-21.c @@ -57,9 +57,9 @@ main () return 0; } =20 -/* { dg-final { scan-tree-dump-times "strlen \\(" 1 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strlen \\(" 2 "strlen" } } */ /* { dg-final { scan-tree-dump-times "memcpy \\(" 3 "strlen" } } */ /* { dg-final { scan-tree-dump-times "strcpy \\(" 0 "strlen" } } */ /* { dg-final { scan-tree-dump-times "strcat \\(" 0 "strlen" } } */ -/* { dg-final { scan-tree-dump-times "strchr \\(" 1 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strchr \\(" 0 "strlen" } } */ /* { dg-final { scan-tree-dump-times "stpcpy \\(" 0 "strlen" } } */ diff --git a/gcc/testsuite/gcc.dg/strlenopt-22.c b/gcc/testsuite/gcc.dg/str= lenopt-22.c index aa55f5ebd6a2d4803ee9a7fd60fc538d86f47124..b4ef772f0e59252f10a5419ede6= 837b3c8ca8265 100644 --- a/gcc/testsuite/gcc.dg/strlenopt-22.c +++ b/gcc/testsuite/gcc.dg/strlenopt-22.c @@ -31,9 +31,9 @@ main () return 0; } =20 -/* { dg-final { scan-tree-dump-times "strlen \\(" 3 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strlen \\(" 4 "strlen" } } */ /* { dg-final { scan-tree-dump-times "memcpy \\(" 1 "strlen" } } */ /* { dg-final { scan-tree-dump-times "strcpy \\(" 1 "strlen" } } */ /* { dg-final { scan-tree-dump-times "strcat \\(" 0 "strlen" } } */ -/* { dg-final { scan-tree-dump-times "strchr \\(" 1 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strchr \\(" 0 "strlen" } } */ /* { dg-final { scan-tree-dump-times "stpcpy \\(" 0 "strlen" } } */ diff --git a/gcc/testsuite/gcc.dg/strlenopt-22g.c b/gcc/testsuite/gcc.dg/st= rlenopt-22g.c index 3e2f8c4633939a0b5ff667fb3671e11cde8fe6ed..9c5d020588f3f338a9acf51d36f= acfea55810760 100644 --- a/gcc/testsuite/gcc.dg/strlenopt-22g.c +++ b/gcc/testsuite/gcc.dg/strlenopt-22g.c @@ -5,9 +5,9 @@ #define USE_GNU #include "strlenopt-22.c" =20 -/* { dg-final { scan-tree-dump-times "strlen \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strlen \\(" 1 "strlen" } } */ /* { dg-final { scan-tree-dump-times "memcpy \\(" 1 "strlen" } } */ /* { dg-final { scan-tree-dump-times "strcpy \\(" 0 "strlen" } } */ /* { dg-final { scan-tree-dump-times "strcat \\(" 0 "strlen" } } */ -/* { dg-final { scan-tree-dump-times "strchr \\(" 1 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strchr \\(" 0 "strlen" } } */ /* { dg-final { scan-tree-dump-times "stpcpy \\(" 1 "strlen" } } */ diff --git a/gcc/testsuite/gcc.dg/strlenopt-26.c b/gcc/testsuite/gcc.dg/str= lenopt-26.c index 4bd54bef540806ca90d2b9bcfc33eb531991c967..da2f465a5b5003fa5dca05f3a6e= e00e97b98b5dd 100644 --- a/gcc/testsuite/gcc.dg/strlenopt-26.c +++ b/gcc/testsuite/gcc.dg/strlenopt-26.c @@ -21,4 +21,5 @@ main (void) return 0; } =20 -/* { dg-final { scan-tree-dump-times "strlen \\(" 1 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strlen \\(" 2 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strchr \\(" 0 "strlen" } } */ diff --git a/gcc/testsuite/gcc.dg/strlenopt-5.c b/gcc/testsuite/gcc.dg/strl= enopt-5.c index 1b006a93045599a75bdb10a39e86ffa59b475c83..a24aea44e8b00ff7b35a907aaa9= 41b4c509642c4 100644 --- a/gcc/testsuite/gcc.dg/strlenopt-5.c +++ b/gcc/testsuite/gcc.dg/strlenopt-5.c @@ -48,9 +48,9 @@ main () return 0; } =20 -/* { dg-final { scan-tree-dump-times "strlen \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strlen \\(" 2 "strlen" } } */ /* { dg-final { scan-tree-dump-times "memcpy \\(" 2 "strlen" } } */ /* { dg-final { scan-tree-dump-times "strcpy \\(" 1 "strlen" } } */ /* { dg-final { scan-tree-dump-times "strcat \\(" 0 "strlen" } } */ -/* { dg-final { scan-tree-dump-times "strchr \\(" 2 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strchr \\(" 0 "strlen" } } */ /* { dg-final { scan-tree-dump-times "stpcpy \\(" 0 "strlen" } } */ diff --git a/gcc/testsuite/gcc.dg/strlenopt-7.c b/gcc/testsuite/gcc.dg/strl= enopt-7.c index 3ae1e2cb3f0d08c8b05107c4e65b67bdb39cf7ab..aa53d7e75254dfe56c93172afc4= 9f95e5b7901e6 100644 --- a/gcc/testsuite/gcc.dg/strlenopt-7.c +++ b/gcc/testsuite/gcc.dg/strlenopt-7.c @@ -40,11 +40,11 @@ main () return 0; } =20 -/* { dg-final { scan-tree-dump-times "strlen \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strlen \\(" 1 "strlen" } } */ /* { dg-final { scan-tree-dump-times "memcpy \\(" 2 "strlen" } } */ /* { dg-final { scan-tree-dump-times "strcpy \\(" 0 "strlen" } } */ /* { dg-final { scan-tree-dump-times "strcat \\(" 0 "strlen" } } */ -/* { dg-final { scan-tree-dump-times "strchr \\(" 1 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strchr \\(" 0 "strlen" } } */ /* { dg-final { scan-tree-dump-times "stpcpy \\(" 0 "strlen" } } */ /* { dg-final { scan-tree-dump-times "\\*r_\[0-9\]* =3D 0;" 1 "strlen" } }= */ /* { dg-final { scan-tree-dump-times "return 3;" 1 "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/strlenopt-9.c b/gcc/testsuite/gcc.dg/strl= enopt-9.c index f78defe6287cee9e9ed4779c70675e91c6541d40..e8ff1023d71268e2067993189d5= f62eab37a16e5 100644 --- a/gcc/testsuite/gcc.dg/strlenopt-9.c +++ b/gcc/testsuite/gcc.dg/strlenopt-9.c @@ -98,10 +98,10 @@ main () return 0; } =20 -/* { dg-final { scan-tree-dump-times "strlen \\(" 3 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strlen \\(" 5 "strlen" } } */ /* { dg-final { scan-tree-dump-times "memcpy \\(" 6 "strlen" } } */ /* { dg-final { scan-tree-dump-times "strcpy \\(" 1 "strlen" } } */ /* { dg-final { scan-tree-dump-times "strcat \\(" 0 "strlen" } } */ -/* { dg-final { scan-tree-dump-times "strchr \\(" 3 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strchr \\(" 0 "strlen" } } */ /* { dg-final { scan-tree-dump-times "stpcpy \\(" 0 "strlen" } } */ /* { dg-final { scan-tree-dump-times "return 4;" 1 "optimized" } } */