Re: [Patch,rtl Optimization]: Better register pressure estimate for Loop Invariant Code Motion.

[David Malcolm <dmalcolm at redhat dot 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, &reg_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...]