From 338392ed0fd9ca466905860e931b7a480179bce4 Mon Sep 17 00:00:00 2001 From: Tom de Vries Date: Tue, 7 Jul 2015 16:25:12 +0000 Subject: [PATCH] Add rewrite_virtuals_into_loop_closed_ssa 2015-07-07 Tom de Vries * tree-cfg.c (get_virtual_phi): New function. * tree-cfg.h (get_virtual_phi): Declare. * tree-ssa-loop-manip.c (replace_uses_in_dominated_bbs) (rewrite_virtuals_into_loop_closed_ssa): New function. * tree-ssa-loop-manip.h (rewrite_virtuals_into_loop_closed_ssa): Declare. * tree-parloops.c (replace_uses_in_bbs_by): Remove. (transform_to_exit_first_loop_alt): Use rewrite_virtuals_into_loop_closed_ssa. From-SVN: r225520 --- gcc/ChangeLog | 12 +++++++++ gcc/tree-cfg.c | 17 +++++++++++++ gcc/tree-cfg.h | 1 + gcc/tree-parloops.c | 43 ++++++--------------------------- gcc/tree-ssa-loop-manip.c | 51 +++++++++++++++++++++++++++++++++++++++ gcc/tree-ssa-loop-manip.h | 1 + 6 files changed, 90 insertions(+), 35 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index b1b3f7f9589..7dee74d5d3b 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,15 @@ +2015-07-07 Tom de Vries + + * tree-cfg.c (get_virtual_phi): New function. + * tree-cfg.h (get_virtual_phi): Declare. + * tree-ssa-loop-manip.c (replace_uses_in_dominated_bbs) + (rewrite_virtuals_into_loop_closed_ssa): New function. + * tree-ssa-loop-manip.h (rewrite_virtuals_into_loop_closed_ssa): + Declare. + * tree-parloops.c (replace_uses_in_bbs_by): Remove. + (transform_to_exit_first_loop_alt): Use + rewrite_virtuals_into_loop_closed_ssa. + 2015-07-07 Richard Biener * fold-const.c (fold_binary_loc): Move diff --git a/gcc/tree-cfg.c b/gcc/tree-cfg.c index f47795a3cf2..b7c4026b684 100644 --- a/gcc/tree-cfg.c +++ b/gcc/tree-cfg.c @@ -2623,6 +2623,23 @@ delete_tree_cfg_annotations (void) vec_free (label_to_block_map_for_fn (cfun)); } +/* Return the virtual phi in BB. */ + +gphi * +get_virtual_phi (basic_block bb) +{ + for (gphi_iterator gsi = gsi_start_phis (bb); + !gsi_end_p (gsi); + gsi_next (&gsi)) + { + gphi *phi = gsi.phi (); + + if (virtual_operand_p (PHI_RESULT (phi))) + return phi; + } + + return NULL; +} /* Return the first statement in basic block BB. */ diff --git a/gcc/tree-cfg.h b/gcc/tree-cfg.h index 2fc1e886ff0..af58c80559d 100644 --- a/gcc/tree-cfg.h +++ b/gcc/tree-cfg.h @@ -59,6 +59,7 @@ extern bool simple_goto_p (gimple); extern bool stmt_ends_bb_p (gimple); extern bool assert_unreachable_fallthru_edge_p (edge); extern void delete_tree_cfg_annotations (void); +extern gphi *get_virtual_phi (basic_block); extern gimple first_stmt (basic_block); extern gimple last_stmt (basic_block); extern gimple last_and_only_stmt (basic_block); diff --git a/gcc/tree-parloops.c b/gcc/tree-parloops.c index 21ed17b4caf..4a2757dc71b 100644 --- a/gcc/tree-parloops.c +++ b/gcc/tree-parloops.c @@ -1492,25 +1492,6 @@ replace_uses_in_bb_by (tree name, tree val, basic_block bb) } } -/* Replace uses of NAME by VAL in blocks BBS. */ - -static void -replace_uses_in_bbs_by (tree name, tree val, bitmap bbs) -{ - gimple use_stmt; - imm_use_iterator imm_iter; - - FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, name) - { - if (!bitmap_bit_p (bbs, gimple_bb (use_stmt)->index)) - continue; - - use_operand_p use_p; - FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter) - SET_USE (use_p, val); - } -} - /* Do transformation from: : @@ -1631,18 +1612,11 @@ transform_to_exit_first_loop_alt (struct loop *loop, tree control = gimple_cond_lhs (cond_stmt); edge e; - /* Gather the bbs dominated by the exit block. */ - bitmap exit_dominated = BITMAP_ALLOC (NULL); - bitmap_set_bit (exit_dominated, exit_block->index); - vec exit_dominated_vec - = get_dominated_by (CDI_DOMINATORS, exit_block); - - int i; - basic_block dom_bb; - FOR_EACH_VEC_ELT (exit_dominated_vec, i, dom_bb) - bitmap_set_bit (exit_dominated, dom_bb->index); - - exit_dominated_vec.release (); + /* Rewriting virtuals into loop-closed ssa normal form makes this + transformation simpler. It also ensures that the virtuals are in + loop-closed ssa normal from after the transformation, which is required by + create_parallel_loop. */ + rewrite_virtuals_into_loop_closed_ssa (loop); /* Create the new_header block. */ basic_block new_header = split_block_before_cond_jump (exit->src); @@ -1675,6 +1649,7 @@ transform_to_exit_first_loop_alt (struct loop *loop, vec *v = redirect_edge_var_map_vector (post_inc_edge); edge_var_map *vm; gphi_iterator gsi; + int i; for (gsi = gsi_start_phis (header), i = 0; !gsi_end_p (gsi) && v->iterate (i, &vm); gsi_next (&gsi), i++) @@ -1692,10 +1667,9 @@ transform_to_exit_first_loop_alt (struct loop *loop, /* Replace ivtmp/sum_b with ivtmp/sum_c in header phi. */ add_phi_arg (phi, res_c, post_cond_edge, UNKNOWN_LOCATION); - /* Replace sum_b with sum_c in exit phi. Loop-closed ssa does not hold - for virtuals, so we cannot get away with exit_block only. */ + /* Replace sum_b with sum_c in exit phi. */ tree res_b = redirect_edge_var_map_def (vm); - replace_uses_in_bbs_by (res_b, res_c, exit_dominated); + replace_uses_in_bb_by (res_b, res_c, exit_block); struct reduction_info *red = reduction_phi (reduction_list, phi); gcc_assert (virtual_operand_p (res_a) @@ -1710,7 +1684,6 @@ transform_to_exit_first_loop_alt (struct loop *loop, } } gcc_assert (gsi_end_p (gsi) && !v->iterate (i, &vm)); - BITMAP_FREE (exit_dominated); /* Set the preheader argument of the new phis to ivtmp/sum_init. */ flush_pending_stmts (entry); diff --git a/gcc/tree-ssa-loop-manip.c b/gcc/tree-ssa-loop-manip.c index a72b779ef9d..3fbb4563670 100644 --- a/gcc/tree-ssa-loop-manip.c +++ b/gcc/tree-ssa-loop-manip.c @@ -560,6 +560,57 @@ rewrite_into_loop_closed_ssa (bitmap changed_bbs, unsigned update_flag) free (use_blocks); } +/* Replace uses of OLD_VAL with NEW_VAL in bbs dominated by BB. */ + +static void +replace_uses_in_dominated_bbs (tree old_val, tree new_val, basic_block bb) +{ + gimple use_stmt; + imm_use_iterator imm_iter; + + FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, old_val) + { + if (!dominated_by_p (CDI_DOMINATORS, gimple_bb (use_stmt), bb)) + continue; + + use_operand_p use_p; + FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter) + SET_USE (use_p, new_val); + } +} + +/* Ensure a virtual phi is present in the exit block, if LOOP contains a vdef. + In other words, ensure loop-closed ssa normal form for virtuals. Handles + only loops with a single exit that dominates the latch. */ + +void +rewrite_virtuals_into_loop_closed_ssa (struct loop *loop) +{ + gphi *phi; + /* TODO: Handle !single_dom_exit loops. */ + edge exit = single_dom_exit (loop); + gcc_assert (exit != NULL); + + phi = get_virtual_phi (loop->header); + if (phi == NULL) + return; + + tree final_loop = PHI_ARG_DEF_FROM_EDGE (phi, single_succ_edge (loop->latch)); + + phi = get_virtual_phi (exit->dest); + if (phi != NULL) + { + tree final_exit = PHI_ARG_DEF_FROM_EDGE (phi, exit); + gcc_assert (operand_equal_p (final_loop, final_exit, 0)); + return; + } + + tree res_new = copy_ssa_name (final_loop, NULL); + gphi *nphi = create_phi_node (res_new, exit->dest); + replace_uses_in_dominated_bbs (final_loop, res_new, exit->dest); + add_phi_arg (nphi, final_loop, exit, UNKNOWN_LOCATION); +} + /* Check invariants of the loop closed ssa form for the USE in BB. */ static void diff --git a/gcc/tree-ssa-loop-manip.h b/gcc/tree-ssa-loop-manip.h index ad0c3815d4f..9285718eaba 100644 --- a/gcc/tree-ssa-loop-manip.h +++ b/gcc/tree-ssa-loop-manip.h @@ -25,6 +25,7 @@ typedef void (*transform_callback)(struct loop *, void *); extern void create_iv (tree, tree, tree, struct loop *, gimple_stmt_iterator *, bool, tree *, tree *); extern void rewrite_into_loop_closed_ssa (bitmap, unsigned); +extern void rewrite_virtuals_into_loop_closed_ssa (struct loop *); extern void verify_loop_closed_ssa (bool); extern basic_block split_loop_exit_edge (edge); extern basic_block ip_end_pos (struct loop *); -- 2.30.2