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. 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 @@ -1464,18 +1464,7 @@ find_invariants_to_move (bool speed, bool call_p) registers used; we put some initial bound here to stand for induction variables etc. that we do not detect. */ { - unsigned int n_regs = DF_REG_SIZE (df); - - regs_used = 2; - - for (i = 0; i < n_regs; i++) - { - if (!DF_REGNO_FIRST_DEF (i) && DF_REGNO_LAST_USE (i)) - { - /* This is a value that is used but not changed inside loop. */ - regs_used++; - } - } + regs_used = bitmap_count_bits (&LOOP_DATA (curr_loop)->regs_live) + 2; } if (! flag_ira_loop_pressure) @@ -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); + + /* 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)); + } + } +} + /* Calculate register pressure in the loops. */ + static void calculate_loop_reg_pressure (void) { @@ -2103,6 +2148,14 @@ move_loop_invariants (void) calculate_loop_reg_pressure (); regstat_free_n_sets_and_refs (); } + else + { + df_analyze(); + regstat_init_n_sets_and_refs (); + calculate_loop_liveness(); + regstat_free_n_sets_and_refs (); + } + df_set_flags (DF_EQ_NOTES + DF_DEFER_INSN_RESCAN); /* Process the loops, innermost first. */ FOR_EACH_LOOP (loop, LI_FROM_INNERMOST) -- 1.7.1 Thanks & Regards Ajit