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.agar...@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 <ajit...@xilinx.com> > > > > * loop-invariant.c > > (calculate_loop_liveness): New. > > (move_loop_invariants): Use of calculate_loop_liveness. > > > > Signed-off-by:Ajit Agarwal ajit...@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...]