From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 6253 invoked by alias); 9 Dec 2015 14:32:58 -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 6222 invoked by uid 89); 9 Dec 2015 14:32:56 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.8 required=5.0 tests=AWL,BAYES_00,SPF_HELO_PASS,T_RP_MATCHES_RCVD autolearn=ham version=3.3.2 X-HELO: mx1.redhat.com Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES256-GCM-SHA384 encrypted) ESMTPS; Wed, 09 Dec 2015 14:32:50 +0000 Received: from int-mx13.intmail.prod.int.phx2.redhat.com (int-mx13.intmail.prod.int.phx2.redhat.com [10.5.11.26]) by mx1.redhat.com (Postfix) with ESMTPS id 76BFE71; Wed, 9 Dec 2015 14:32:49 +0000 (UTC) Received: from [10.3.236.204] (vpn-236-204.phx2.redhat.com [10.3.236.204]) by int-mx13.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id tB9EWmcr031399; Wed, 9 Dec 2015 09:32:48 -0500 Message-ID: <1449671567.1916.10.camel@surprise> Subject: Re: [Patch,rtl Optimization]: Better register pressure estimate for Loop Invariant Code Motion. From: David Malcolm To: Richard Biener Cc: Ajit Kumar Agarwal , Jeff Law , GCC Patches , Vinod Kathail , Shail Aditya Gupta , Vidhumouli Hunsigida , Nagaraju Mekala Date: Wed, 09 Dec 2015 14:32:00 -0000 In-Reply-To: References: <37378DC5BCD0EE48BA4B082E0B55DFAA429D3942@XAP-PVEXMBX02.xlnx.xilinx.com> Content-Type: text/plain; charset="UTF-8" Mime-Version: 1.0 Content-Transfer-Encoding: 7bit X-IsSubscribed: yes X-SW-Source: 2015-12/txt/msg01005.txt.bz2 On Wed, 2015-12-09 at 11:35 +0100, Richard Biener wrote: > On Tue, Dec 8, 2015 at 11:24 PM, Ajit Kumar Agarwal > wrote: > > Based on the comments on RFC patch this patch incorporates all the comments from Jeff. Thanks Jeff for the valuable feedback. > > > > This patch enables the better register pressure estimate for Loop Invariant code motion. This patch Calculate the Loop Liveness used for regs_used > > used to calculate the register pressure used in the cost estimation. > > > > Loop Liveness is based on the following properties. we only require to calculate the set of objects that are live at the birth or the header of the loop. We > > don't need to calculate the live through the Loop considering Live in and Live out of all the basic blocks of the Loop. This is because the set of objects. That > > are live-in at the birth or header of the loop will be live-in at every node in the Loop. > > > > If a v live out at the header of the loop then the variable is live-in at every node in the Loop. To prove this, Consider a Loop L with header h such that The > > variable v defined at d is live-in at h. Since v is live at h, d is not part of L. This follows from the dominance property, i.e. h is strictly dominated by d. > > Furthermore, there exists a path from h to a use of v which does not go through d. For every node of the loop, p, since the loop is strongly connected > > Component of the CFG, there exists a path, consisting only of nodes of L from p to h. Concatenating those two paths prove that v is live-in and live-out Of p. > > > > Also Calculate the Live-Out and Live-In for the exit edge of the loop. This considers liveness for not only the Loop latch but also the liveness outside the Loops. > > > > Bootstrapped and Regtested for x86_64 and microblaze target. > > > > There is an extra failure for the testcase gcc.dg/loop-invariant.c with the change that looks correct to me. > > > > This is because the available_regs = 6 and the regs_needed = 1 and new_regs = 0 and the regs_used = 10. As the reg_used that are based on the Liveness > > given above is greater than the available_regs, then it's candidate of spill and the estimate_register_pressure calculates the spill cost. This spill cost is greater > > than inv_cost and gain comes to be negative. The disables the loop invariant for the above testcase. > > > > Disabling of the Loop invariant for the testcase loop-invariant.c with this patch looks correct to me considering the calculation of available_regs in cfgloopanal.c > > is correct. > > You keep a lot of data (bitmaps) live just to use the number of bits > set in the end. > > I'll note that this also increases the complexity of the pass which is > enabled at -O1+ where > -O1 should limit itself to O(n*log n) algorithms but live is quadratic. > > So I don't think doing this unconditionally is a good idea (and we > have -fira-loop-pressure > after all). > > Please watch not making -O1 worse again after we spent so much time > making it suitable > for all the weird autogenerated code. > > Richard. > > > ChangeLog: > > 2015-12-09 Ajit Agarwal > > > > * loop-invariant.c > > (calculate_loop_liveness): New. > > (move_loop_invariants): Use of calculate_loop_liveness. > > > > Signed-off-by:Ajit Agarwal ajitkum@xilinx.com > > > > --- > > gcc/loop-invariant.c | 77 ++++++++++++++++++++++++++++++++++++++++++-------- > > 1 files changed, 65 insertions(+), 12 deletions(-) > > > > diff --git a/gcc/loop-invariant.c b/gcc/loop-invariant.c > > index 53d1377..ac08594 100644 > > --- a/gcc/loop-invariant.c > > +++ b/gcc/loop-invariant.c [...snip...] > > @@ -1966,7 +1955,63 @@ mark_ref_regs (rtx x) > > } > > } > > > > +/* Calculate the Loop Liveness used for regs_used used in > > + heuristics to calculate the register pressure. */ > > + > > +static void > > +calculate_loop_liveness (void) > > +{ > > + struct loop *loop; > > + > > + FOR_EACH_LOOP (loop, 0) > > + if (loop->aux == NULL) > > + { > > + loop->aux = xcalloc (1, sizeof (struct loop_data)); > > + bitmap_initialize (&LOOP_DATA (loop)->regs_live, ®_obstack); > > + } > > + > > + FOR_EACH_LOOP (loop, LI_FROM_INNERMOST) > > + { > > + int i; > > + edge e; > > + vec edges; > > + edges = get_loop_exit_edges (loop); Doesn't this leak "edges"? (Could/should it be an auto_vec?) > > + > > + /* Loop Liveness is based on the following proprties. > > + we only require to calculate the set of objects that are live at > > + the birth or the header of the loop. > > + We don't need to calculate the live through the Loop considering > > + Live in and Live out of all the basic blocks of the Loop. This is > > + because the set of objects. That are live-in at the birth or header > > + of the loop will be live-in at every node in the Loop. > > + > > + If a v live out at the header of the loop then the variable is live-in > > + at every node in the Loop. To prove this, Consider a Loop L with header > > + h such that The variable v defined at d is live-in at h. Since v is live > > + at h, d is not part of L. This follows from the dominance property, i.e. > > + h is strictly dominated by d. Furthermore, there exists a path from h to > > + a use of v which does not go through d. For every node of the loop, p, > > + since the loop is strongly connected Component of the CFG, there exists > > + a path, consisting only of nodes of L from p to h. Concatenating those > > + two paths prove that v is live-in and live-out Of p. */ > > + > > + bitmap_ior_into (&LOOP_DATA (loop)->regs_live, DF_LR_IN (loop->header)); > > + bitmap_ior_into (&LOOP_DATA (loop)->regs_live, DF_LR_OUT (loop->header)); > > + > > + /* Calculate the Live-Out and Live-In for the exit edge of the loop. > > + This considers liveness for not only the Loop latch but also the > > + liveness outside the Loops. */ > > + > > + FOR_EACH_VEC_ELT (edges, i, e) > > + { > > + bitmap_ior_into (&LOOP_DATA (loop)->regs_live, DF_LR_OUT (e->src)); > > + bitmap_ior_into (&LOOP_DATA (loop)->regs_live, DF_LR_IN (e->dest)); > > + } > > + } > > +} [...snip...]