From: David Malcolm <dmalcolm@redhat.com>
To: Richard Biener <richard.guenther@gmail.com>
Cc: Ajit Kumar Agarwal <ajit.kumar.agarwal@xilinx.com>,
Jeff Law <law@redhat.com>,
GCC Patches <gcc-patches@gcc.gnu.org>,
Vinod Kathail <vinodk@xilinx.com>,
Shail Aditya Gupta <shailadi@xilinx.com>,
Vidhumouli Hunsigida <vidhum@xilinx.com>,
Nagaraju Mekala <nmekala@xilinx.com>
Subject: Re: [Patch,rtl Optimization]: Better register pressure estimate for Loop Invariant Code Motion.
Date: Wed, 09 Dec 2015 14:32:00 -0000 [thread overview]
Message-ID: <1449671567.1916.10.camel@surprise> (raw)
In-Reply-To: <CAFiYyc2JmYakX1z-e9jJGvbi2o7hRDDoUweG2AwWELWm4n9wZw@mail.gmail.com>
On Wed, 2015-12-09 at 11:35 +0100, Richard Biener wrote:
> On Tue, Dec 8, 2015 at 11:24 PM, Ajit Kumar Agarwal
> <ajit.kumar.agarwal@xilinx.com> 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 <ajitkum@xilinx.com>
> >
> > * 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<edge> 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...]
prev parent reply other threads:[~2015-12-09 14:32 UTC|newest]
Thread overview: 7+ messages / expand[flat|nested] mbox.gz Atom feed top
2015-12-08 22:24 Ajit Kumar Agarwal
2015-12-09 10:36 ` Richard Biener
2015-12-09 11:23 ` Ajit Kumar Agarwal
2015-12-09 14:04 ` Bernd Schmidt
2015-12-09 14:53 ` Ajit Kumar Agarwal
2015-12-15 8:15 ` Ajit Kumar Agarwal
2015-12-09 14:32 ` David Malcolm [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=1449671567.1916.10.camel@surprise \
--to=dmalcolm@redhat.com \
--cc=ajit.kumar.agarwal@xilinx.com \
--cc=gcc-patches@gcc.gnu.org \
--cc=law@redhat.com \
--cc=nmekala@xilinx.com \
--cc=richard.guenther@gmail.com \
--cc=shailadi@xilinx.com \
--cc=vidhum@xilinx.com \
--cc=vinodk@xilinx.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).