From patchwork Tue May 13 10:04:05 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Zhenqiang Chen X-Patchwork-Id: 30023 Return-Path: X-Original-To: linaro@patches.linaro.org Delivered-To: linaro@patches.linaro.org Received: from mail-pb0-f72.google.com (mail-pb0-f72.google.com [209.85.160.72]) by ip-10-151-82-157.ec2.internal (Postfix) with ESMTPS id 0800C20446 for ; Tue, 13 May 2014 10:04:33 +0000 (UTC) Received: by mail-pb0-f72.google.com with SMTP id ma3sf471481pbc.7 for ; Tue, 13 May 2014 03:04:33 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:delivered-to:mailing-list:precedence:list-id :list-unsubscribe:list-archive:list-post:list-help:sender :delivered-to:mime-version:in-reply-to:references:date:message-id :subject:from:to:cc:x-original-sender :x-original-authentication-results:content-type; bh=qgFiOwd2x4k9y20UTykRnR8bqwBiZS1xNSV+2pFt2d4=; b=Cudgyc4UaZIZ3XymREuoitqXpaSW5aoM6JaLyUy+zrIApP2/j9Re+kPHyqdaKKfDYU C4Z1MFoMZTZPUxbVy2Ozv2I6qHPdEwzHYAFIllxF05BykJgeZLvYYW9WTIczxllcmNw0 S674PmqLDEvhQMQtLJyJIw2/bVz6osN3I44Xhwx/DUo0z4UYO6RBjTi1Pv2EBmzthpfF 8svcOsVIiFr4cTAH+ztrgevkD6CJEm6/KZC9pjhFBQFdVZFHm33poVO7hRMaMR5V0VW8 0iDuMPQtrpJW4/SvQUcvw63hZt04tngOD5r3fwNtYnJ6Zsqqm2fetANLF9Jyxk7Gi99w vUhg== X-Gm-Message-State: ALoCoQktP2CHUl2TXRloBxBo0bDuvfGg4idsRlkJveGh1dSZqEHVB9qQycgLu8IrpyNRAbMm1xCd X-Received: by 10.66.234.39 with SMTP id ub7mr3145711pac.26.1399975473142; Tue, 13 May 2014 03:04:33 -0700 (PDT) X-BeenThere: patchwork-forward@linaro.org Received: by 10.140.102.180 with SMTP id w49ls1770743qge.3.gmail; Tue, 13 May 2014 03:04:33 -0700 (PDT) X-Received: by 10.58.116.1 with SMTP id js1mr6579535veb.29.1399975473029; Tue, 13 May 2014 03:04:33 -0700 (PDT) Received: from mail-vc0-x231.google.com (mail-vc0-x231.google.com [2607:f8b0:400c:c03::231]) by mx.google.com with ESMTPS id f2si1804494vem.171.2014.05.13.03.04.32 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Tue, 13 May 2014 03:04:32 -0700 (PDT) Received-SPF: pass (google.com: domain of patch+caf_=patchwork-forward=linaro.org@linaro.org designates 2607:f8b0:400c:c03::231 as permitted sender) client-ip=2607:f8b0:400c:c03::231; Received: by mail-vc0-f177.google.com with SMTP id if17so122285vcb.22 for ; Tue, 13 May 2014 03:04:32 -0700 (PDT) X-Received: by 10.52.227.138 with SMTP id sa10mr23784388vdc.25.1399975472887; Tue, 13 May 2014 03:04:32 -0700 (PDT) X-Forwarded-To: patchwork-forward@linaro.org X-Forwarded-For: patch@linaro.org patchwork-forward@linaro.org Delivered-To: patch@linaro.org Received: by 10.220.221.72 with SMTP id ib8csp138132vcb; Tue, 13 May 2014 03:04:32 -0700 (PDT) X-Received: by 10.66.163.138 with SMTP id yi10mr62761444pab.95.1399975471897; Tue, 13 May 2014 03:04:31 -0700 (PDT) Received: from sourceware.org (server1.sourceware.org. [209.132.180.131]) by mx.google.com with ESMTPS id iv2si7732227pbd.297.2014.05.13.03.04.31 for (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 13 May 2014 03:04:31 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-return-367342-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) client-ip=209.132.180.131; Received: (qmail 20802 invoked by alias); 13 May 2014 10:04:18 -0000 Mailing-List: list patchwork-forward@linaro.org; contact patchwork-forward+owners@linaro.org Precedence: list 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 20747 invoked by uid 89); 13 May 2014 10:04:12 -0000 X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.5 required=5.0 tests=AWL, BAYES_00, RCVD_IN_DNSWL_LOW, SPF_PASS autolearn=ham version=3.3.2 X-HELO: mail-la0-f50.google.com Received: from mail-la0-f50.google.com (HELO mail-la0-f50.google.com) (209.85.215.50) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-SHA encrypted) ESMTPS; Tue, 13 May 2014 10:04:09 +0000 Received: by mail-la0-f50.google.com with SMTP id b8so87032lan.9 for ; Tue, 13 May 2014 03:04:05 -0700 (PDT) MIME-Version: 1.0 X-Received: by 10.152.4.137 with SMTP id k9mr1241088lak.46.1399975445340; Tue, 13 May 2014 03:04:05 -0700 (PDT) Received: by 10.112.13.36 with HTTP; Tue, 13 May 2014 03:04:05 -0700 (PDT) In-Reply-To: <536C6EF1.6080702@redhat.com> References: <536C6EF1.6080702@redhat.com> Date: Tue, 13 May 2014 18:04:05 +0800 Message-ID: Subject: Re: [PATCH, 1/2] shrink wrap a function with a single loop: copy propagation From: Zhenqiang Chen To: Jeff Law Cc: "gcc-patches@gcc.gnu.org" X-IsSubscribed: yes X-Original-Sender: zhenqiang.chen@linaro.org X-Original-Authentication-Results: mx.google.com; spf=pass (google.com: domain of patch+caf_=patchwork-forward=linaro.org@linaro.org designates 2607:f8b0:400c:c03::231 as permitted sender) smtp.mail=patch+caf_=patchwork-forward=linaro.org@linaro.org; dkim=pass header.i=@gcc.gnu.org X-Google-Group-Id: 836684582541 After reading the code in regcprop.c, I think I should reuse the copyprop_hardreg_forward_1. So rewrite the patch, which is much simple and should handle HAVE_cc0. But not sure we'd handle DEBUG_INSN or not. 2014-05-13 Zhenqiang Chen * regcprop.c (skip_debug_insn_p): New decl. (replace_oldest_value_reg): Check skip_debug_insn_p. (copyprop_hardreg_forward_bb_without_debug_insn.): New function. * shrink-wrap.c (prepare_shrink_wrap): Call copyprop_hardreg_forward_bb_without_debug_insn. * function.h (copyprop_hardreg_forward_bb_without_debug_insn): New prototype. testsuite/ChangeLog: 2014-05-13 Zhenqiang Chen * shrink-wrap-loop.c: New test case. +/* { dg-final { cleanup-rtl-dump "pro_and_epilogue" } } */ On 9 May 2014 14:00, Jeff Law wrote: > On 05/08/14 02:06, Zhenqiang Chen wrote: >> >> Hi, >> >> Similar issue was discussed in thread >> http://gcc.gnu.org/ml/gcc-patches/2013-04/msg01145.html. The patches >> are close to Jeff's suggestion: "sink just the moves out of the >> incoming argument registers". >> >> The patch and following one try to shrink wrap a function with a >> single loop, which can not be handled by >> split_live_ranges_for_shrink_wrap and prepare_shrink_wrap, since the >> induction variable has more than one definitions. Take the test case >> in the patch as example, the pseudo code before shrink-wrap is like: >> >> p = p2 >> if (!p) goto return >> L1: ... >> p = ... >> ... >> goto L1 >> ... >> return: >> >> Function prepare_shrink_wrap does PRE like optimization to sink some >> copies from entry block to the live block. The patches enhance >> prepare_shrink_wrap with: >> (1) Replace the reference of p to p2 in the entry block. (This patch) >> (2) Create a new basic block on the live edge to hold the copy "p = >> p2". (Next patch) >> >> After shrink-wrap, the pseudo code would like: >> >> if (!p2) goto return >> p = p2 >> L1: ... >> p = ... >> ... >> goto L1 >> return: > > Right. Seems like a reasonably useful transformation. Not the totally > general solution, but one that clearly has value. > > > >> 2014-05-08 Zhenqiang Chen >> >> * function.c (last_or_compare_p, try_copy_prop): new functions. >> (move_insn_for_shrink_wrap): try copy propagation. >> (prepare_shrink_wrap): Separate last_uses from uses. >> >> testsuite/ChangeLog: >> 2014-05-08 Zhenqiang Chen >> >> * shrink-wrap-loop.c: New test case. > > So first at a high level, Steven B.'s recommendation to pull the > shrink-wrapping bits out of function.c is a good one. I'd really like to > see that happen as well. > > >> +/* Check whether INSN is the last insn in BB or >> + a COMPARE for the last insn in BB. */ >> + >> +static bool >> +last_or_compare_p (basic_block bb, rtx insn) >> +{ >> + rtx x = single_set (insn); >> + >> + if ((insn == BB_END (bb)) >> + || ((insn == PREV_INSN (BB_END (bb))) >> + && x && REG_P (SET_DEST (x)) >> + && GET_MODE_CLASS (GET_MODE (SET_DEST (x))) == MODE_CC)) >> + return true; >> + >> + return false; > > So you don't actually check if the insn is a compare, just that it's > destination is MODE_CC. That's probably close enough, but please note it in > the comment. Folks are going to read the comment first, not the > implementation. > > Q. Do we have to do anything special for HAVE_cc0 targets here? > > >> +} >> + >> +/* Try to copy propagate INSN with SRC and DEST in BB to the last COMPARE >> + or JUMP insn, which use registers in LAST_USES. */ > > So why restrict this to just cases where we have to propagate into a COMPARE > at the end of a block? So in your example, assume the first block looks > like > > p = p2; > if (!q) return; > [ ... ] > > We ought to be able to turn that into > > if (!q) return > p = p2; > [ ... ] > > > >> + >> +static bool >> +try_copy_prop (basic_block bb, rtx insn, rtx src, rtx dest, >> + HARD_REG_SET *last_uses) > > My first thought here was that we must have some code which does 90% of what > you need. Did you look at any of the existing RTL optimization > infrastructure to see if there was code you could extend to handle this? > > Jeff diff --git a/gcc/regcprop.c b/gcc/regcprop.c index a710cc38..f76a944 100644 --- a/gcc/regcprop.c +++ b/gcc/regcprop.c @@ -77,6 +77,7 @@ struct value_data }; static alloc_pool debug_insn_changes_pool; +static bool skip_debug_insn_p = false; static void kill_value_one_regno (unsigned, struct value_data *); static void kill_value_regno (unsigned, unsigned, struct value_data *); @@ -485,7 +486,7 @@ replace_oldest_value_reg (rtx *loc, enum reg_class cl, rtx insn, struct value_data *vd) { rtx new_rtx = find_oldest_value_reg (cl, *loc, vd); - if (new_rtx) + if (new_rtx && (!DEBUG_INSN_P (insn) || !skip_debug_insn_p)) { if (DEBUG_INSN_P (insn)) { @@ -1112,6 +1113,26 @@ debug_value_data (struct value_data *vd) vd->e[i].next_regno); } +/* Do copyprop_hardreg_forward_1 for a single basic block BB. + DEBUG_INSN is skipped since we do not want to involve DF related + staff as how it is handled in function pass_cprop_hardreg::execute. + + NOTE: Currently it is only used for shrink-wrap. Maybe extend it + to handle DEBUG_INSN for other uses. */ + +void +copyprop_hardreg_forward_bb_without_debug_insn (basic_block bb) +{ + struct value_data *vd; + vd = XNEWVEC (struct value_data, 1); + init_value_data (vd); + + skip_debug_insn_p = true; + copyprop_hardreg_forward_1 (bb, vd); + free (vd); + skip_debug_insn_p = false; +} + #ifdef ENABLE_CHECKING static void validate_value_data (struct value_data *vd) diff --git a/gcc/shrink-wrap.c b/gcc/shrink-wrap.c index f11e920..ce49f16 100644 --- a/gcc/shrink-wrap.c +++ b/gcc/shrink-wrap.c @@ -320,6 +320,15 @@ prepare_shrink_wrap (basic_block entry_block) df_ref *ref; bool split_p = false; + if (JUMP_P (BB_END (entry_block))) + { + /* To have more shrink-wrapping opportunities, prepare_shrink_wrap tries + to sink the copies from parameter to callee saved register out of + entry block. copyprop_hardreg_forward_bb_without_debug_insn is called + to release some dependences. */ + copyprop_hardreg_forward_bb_without_debug_insn (entry_block); + } + CLEAR_HARD_REG_SET (uses); CLEAR_HARD_REG_SET (defs); FOR_BB_INSNS_REVERSE_SAFE (entry_block, insn, curr) diff --git a/gcc/shrink-wrap.h b/gcc/shrink-wrap.h index 22b1d5c..9058d34 100644 --- a/gcc/shrink-wrap.h +++ b/gcc/shrink-wrap.h @@ -45,6 +45,8 @@ extern edge get_unconverted_simple_return (edge, bitmap_head, extern void convert_to_simple_return (edge entry_edge, edge orig_entry_edge, bitmap_head bb_flags, rtx returnjump, vec unconverted_simple_returns); +/* In regcprop.c */ +extern void copyprop_hardreg_forward_bb_without_debug_insn (basic_block bb); #endif #endif /* GCC_SHRINK_WRAP_H */ diff --git a/gcc/testsuite/gcc.dg/shrink-wrap-loop.c b/gcc/testsuite/gcc.dg/shrink-wrap-loop.c new file mode 100644 index 0000000..17dca4e --- /dev/null +++ b/gcc/testsuite/gcc.dg/shrink-wrap-loop.c @@ -0,0 +1,20 @@ +/* { dg-do compile { target { { x86_64-*-* } || { arm_thumb2 } } } } */ +/* { dg-options "-O2 -fdump-rtl-pro_and_epilogue" } */ + +int foo (int *p1, int *p2); + +int +test (int *p1, int *p2) +{ + int *p; + + for (p = p2; p != 0; p++) + { + if (!foo (p, p1)) + return 0; + } + + return 1; +} +/* { dg-final { scan-rtl-dump "Performing shrink-wrapping" "pro_and_epilogue" } } */