From patchwork Mon Sep 2 06:56:28 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Bin Cheng X-Patchwork-Id: 271685 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 4B2E02C009E for ; Mon, 2 Sep 2013 16:56:58 +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:subject:date:message-id:mime-version:content-type; q=dns; s= default; b=DrLh7ScgxnjXM9xkA0zrW/PAU/SitPRAtns8OsCmQTktDWAj4Dujw QjmyTH0S0VSZRyj2qWSsgcgw3X4ID4twHfSTSDZjpSGMcySi1x8Cn9+qzpmjz4wE 2ygSmDuppZyqj0IXmx+9FA/ViAMShkC8NwlbFDLBRoXOWBA1vsFq4s= 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:subject:date:message-id:mime-version:content-type; s= default; bh=PQLzio2c8ZtDI6AqUvAysAmJI50=; b=Rpthzbe19rrkqawoUBtn CrdV2+SKu04J98DgHNGVSVaE1PCfWFubZAvSaaU+1FRR2q0I2cr46zZgZc47XPH1 oa/0YsD8bVP/U+tGk2gkcttSNa5rUEHTsHE8Zh+YOj751M0NSf88uIaevfSAQ9jS bl1aYJSP9BkTia9f1zidKtQ= Received: (qmail 2141 invoked by alias); 2 Sep 2013 06:56:50 -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 2128 invoked by uid 89); 2 Sep 2013 06:56:50 -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; Mon, 02 Sep 2013 06:56:50 +0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-3.5 required=5.0 tests=AWL, BAYES_00, 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; Mon, 02 Sep 2013 07:56:45 +0100 Received: from SHAWIN162 ([10.1.255.212]) by cam-owa2.Emea.Arm.com with Microsoft SMTPSVC(6.0.3790.3959); Mon, 2 Sep 2013 07:56:42 +0100 From: "bin.cheng" To: Subject: [PATCH GCC]Catch more MEM_REFs sharing common addressing part in gimple strength reduction Date: Mon, 2 Sep 2013 14:56:28 +0800 Message-ID: <003f01cea7a9$8e984ae0$abc8e0a0$@arm.com> MIME-Version: 1.0 X-MC-Unique: 113090207564501701 X-IsSubscribed: yes Hi, The gimple-ssa-strength-reduction pass handles CAND_REFs in order to find different MEM_REFs sharing common part in addressing expression. If such MEM_REFs are found, the pass rewrites MEM_REFs, and produces more efficient addressing expression during the RTL passes. The pass analyzes addressing expression in each MEM_REF to see if it can be formalized as follows: base: MEM_REF (T1, C1) offset: MULT_EXPR (PLUS_EXPR (T2, C2), C3) bitpos: C4 * BITS_PER_UNIT Then restructures it into below form: MEM_REF (POINTER_PLUS_EXPR (T1, MULT_EXPR (T2, C3)), C1 + (C2 * C3) + C4) At last, rewrite the MEM_REFs if there are two or more sharing common (non-constant) part. The problem is it doesn't back trace T2. If T2 is recorded as a CAND_ADD in form of "T2' + C5", the MEM_REF should be restructure into: MEM_REF (POINTER_PLUS_EXPR (T1, MULT_EXPR (T2', C3)), C1 + (C2 * C3) + C4 + (C5 * C3)) The patch also includes a test case to illustrate the problem. Bootstrapped and tested on x86/x86_64/arm-a15, is it ok? Thanks. bin 2013-09-02 Bin Cheng * gimple-ssa-strength-reduction.c (backtrace_base_for_ref): New. (restructure_reference): Call backtrace_base_for_ref. gcc/testsuite/ChangeLog 2013-09-02 Bin Cheng * gcc.dg/tree-ssa/slsr-39.c: New test. 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 + CADN_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, loop 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 candiate'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 an 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, - double_int_to_tree (sizetype, c3)); - *pindex = c1 + c2 * c3 + c4; + *poffset = size_binop (MULT_EXPR, fold_convert (sizetype, t2), + double_int_to_tree (sizetype, c3)); + *pindex = c1 + c2 * c3 + c4 + c5 * c3; *ptype = type; return true;