From patchwork Tue Sep 10 07:41:00 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Bin Cheng X-Patchwork-Id: 273772 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (Client CN "www.sourceware.org", Issuer "StartCom Class 1 Primary Intermediate Server CA" (not verified)) by ozlabs.org (Postfix) with ESMTPS id 3B77F2C0115 for ; Tue, 10 Sep 2013 17:41:35 +1000 (EST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:cc:references:in-reply-to:subject:date:message-id :mime-version:content-type; q=dns; s=default; b=pIQovY6N5SmhvvxX oQNrr9jNBL0r7vMdadDmxmRVhy1JokH+JkGZIN8MUPQlZA2yycwP3KU0tyuGxwNH soV6LuEX6cjbB+Tfaj8/jS/Her4jippEbPhmFyZOJ/8Jprutyv1sXJzNeq4vw3E3 6Re+tTzRndRhLZOtiN43U2e4mMc= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:cc:references:in-reply-to:subject:date:message-id :mime-version:content-type; s=default; bh=01xj2sq9x3TuSMxT1q1PTJ W0RT4=; b=ion28us+Gvfwq97K/PTc8ZR/7Sj3VsukDVImypIhGvw7FXzuYdoImP rWmHiu3QS4kLvpsK/J5wWbx7pTPuuwp2QG8VcH06wMj7QvLxa61lUxmaGa7L343q Ok8MPpUWFLAxv1SXw9Mimd8WZL2X+NyAMViQOUYWlSrl31krsEzGg= Received: (qmail 16592 invoked by alias); 10 Sep 2013 07:41:28 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 16578 invoked by uid 89); 10 Sep 2013 07:41:28 -0000 Received: from service87.mimecast.com (HELO service87.mimecast.com) (91.220.42.44) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Tue, 10 Sep 2013 07:41:28 +0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-3.4 required=5.0 tests=AWL, BAYES_00, KHOP_THREADED, RCVD_IN_DNSWL_LOW, RCVD_IN_HOSTKARMA_NO, RP_MATCHES_RCVD, SPF_PASS autolearn=ham version=3.3.2 X-HELO: service87.mimecast.com Received: from cam-owa2.Emea.Arm.com (fw-tnat.cambridge.arm.com [217.140.96.21]) by service87.mimecast.com; Tue, 10 Sep 2013 08:41:23 +0100 Received: from SHAWIN162 ([10.1.255.212]) by cam-owa2.Emea.Arm.com with Microsoft SMTPSVC(6.0.3790.3959); Tue, 10 Sep 2013 08:41:20 +0100 From: "bin.cheng" To: "'Bill Schmidt'" Cc: "Richard Biener" , "GCC Patches" References: <003f01cea7a9$8e984ae0$abc8e0a0$@arm.com> <1378685738.3730.16.camel@gnopaine> <004801cead25$724765c0$56d63140$@arm.com> <1378740018.3730.21.camel@gnopaine> <1378740932.3730.23.camel@gnopaine> In-Reply-To: <1378740932.3730.23.camel@gnopaine> Subject: RE: [PATCH GCC]Catch more MEM_REFs sharing common addressing part in gimple strength reduction Date: Tue, 10 Sep 2013 15:41:00 +0800 Message-ID: <004901ceadf9$195f9700$4c1ec500$@arm.com> MIME-Version: 1.0 X-MC-Unique: 113091008412305001 X-IsSubscribed: yes On Mon, Sep 9, 2013 at 11:35 PM, Bill Schmidt wrote: > >> > I rely on size_binop to convert T2 into sizetype, because T2' may be in other kind of type. Otherwise there will be ssa_verify error later. >> >> OK, I see now. I had thought this was handled by fold_build2, but >> apparently not. I guess all T2's formerly handled were already sizetype >> as expected. Thanks for the explanation! > > So, wouldn't it suffice to change t2 to fold_convert (sizetype, t2) in > the argument list to fold_build2? It's picking nits, but that would be > slightly more efficient. Hi Bill, This is the 2nd version of patch with your comments incorporated. Bootstrap and re-test on x86. Re-test on ARM ongoing. Is it ok if tests pass? Thanks. bin Index: gcc/testsuite/gcc.dg/tree-ssa/slsr-39.c =================================================================== --- gcc/testsuite/gcc.dg/tree-ssa/slsr-39.c (revision 0) +++ gcc/testsuite/gcc.dg/tree-ssa/slsr-39.c (revision 0) @@ -0,0 +1,26 @@ +/* Verify straight-line strength reduction for back-tracing + CAND_ADD for T2 in: + + *PBASE: T1 + *POFFSET: MULT_EXPR (T2, C3) + *PINDEX: C1 + (C2 * C3) + C4 */ + +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-slsr" } */ + +typedef int arr_2[50][50]; + +void foo (arr_2 a2, int v1) +{ + int i, j; + + i = v1 + 5; + j = i; + a2 [i] [j++] = i; + a2 [i] [j++] = i; + a2 [i] [i-1] += 1; + return; +} + +/* { dg-final { scan-tree-dump-times "MEM" 4 "slsr" } } */ +/* { dg-final { cleanup-tree-dump "slsr" } } */ Index: gcc/gimple-ssa-strength-reduction.c =================================================================== --- gcc/gimple-ssa-strength-reduction.c (revision 202067) +++ gcc/gimple-ssa-strength-reduction.c (working copy) @@ -750,6 +750,57 @@ slsr_process_phi (gimple phi, bool speed) add_cand_for_stmt (phi, c); } +/* Given PBASE which is a pointer to tree, look up the defining + statement for it and check whether the candidate is in the + form of: + + X = B + (1 * S), S is integer constant + X = B + (i * S), S is integer one + + If so, set PBASE to the candidate's base_expr and return double + int (i * S). + Otherwise, just return double int zero. */ + +static double_int +backtrace_base_for_ref (tree *pbase) +{ + tree base_in = *pbase; + slsr_cand_t base_cand; + + STRIP_NOPS (base_in); + if (TREE_CODE (base_in) != SSA_NAME) + return tree_to_double_int (integer_zero_node); + + base_cand = base_cand_from_table (base_in); + + while (base_cand && base_cand->kind != CAND_PHI) + { + if (base_cand->kind == CAND_ADD + && base_cand->index.is_one () + && TREE_CODE (base_cand->stride) == INTEGER_CST) + { + /* X = B + (1 * S), S is integer constant. */ + *pbase = base_cand->base_expr; + return tree_to_double_int (base_cand->stride); + } + else if (base_cand->kind == CAND_ADD + && TREE_CODE (base_cand->stride) == INTEGER_CST + && integer_onep (base_cand->stride)) + { + /* X = B + (i * S), S is integer one. */ + *pbase = base_cand->base_expr; + return base_cand->index; + } + + if (base_cand->next_interp) + base_cand = lookup_cand (base_cand->next_interp); + else + base_cand = NULL; + } + + return tree_to_double_int (integer_zero_node); +} + /* Look for the following pattern: *PBASE: MEM_REF (T1, C1) @@ -767,8 +818,15 @@ slsr_process_phi (gimple phi, bool speed) *PBASE: T1 *POFFSET: MULT_EXPR (T2, C3) - *PINDEX: C1 + (C2 * C3) + C4 */ + *PINDEX: C1 + (C2 * C3) + C4 + When T2 is recorded by a CAND_ADD in the form of (T2' + C5), it + will be further restructured to: + + *PBASE: T1 + *POFFSET: MULT_EXPR (T2', C3) + *PINDEX: C1 + (C2 * C3) + C4 + (C5 * C3) */ + static bool restructure_reference (tree *pbase, tree *poffset, double_int *pindex, tree *ptype) @@ -777,7 +835,7 @@ restructure_reference (tree *pbase, tree *poffset, double_int index = *pindex; double_int bpu = double_int::from_uhwi (BITS_PER_UNIT); tree mult_op0, mult_op1, t1, t2, type; - double_int c1, c2, c3, c4; + double_int c1, c2, c3, c4, c5; if (!base || !offset @@ -823,11 +881,12 @@ restructure_reference (tree *pbase, tree *poffset, } c4 = index.udiv (bpu, FLOOR_DIV_EXPR); + c5 = backtrace_base_for_ref (&t2); *pbase = t1; - *poffset = fold_build2 (MULT_EXPR, sizetype, t2, + *poffset = fold_build2 (MULT_EXPR, sizetype, fold_convert (sizetype, t2), double_int_to_tree (sizetype, c3)); - *pindex = c1 + c2 * c3 + c4; + *pindex = c1 + c2 * c3 + c4 + c5 * c3; *ptype = type; return true;