From 7b10257fdddb77e1854f223fc38c7d695fb8ebb4 Mon Sep 17 00:00:00 2001 From: Sebastian Pop Date: Mon, 5 Jan 2009 21:21:16 +0000 Subject: [PATCH] re PR middle-end/38492 ([graphite] segfaulting code when compiled with -fgraphite -fgraphite-identity) 2009-01-05 Sebastian Pop PR tree-optimization/38492 * graphite.c (rename_map_elt, debug_rename_elt, debug_rename_map_1, debug_rename_map, new_rename_map_elt, rename_map_elt_info, eq_rename_map_elts, get_new_name_from_old_name, bb_in_sese_p): Moved around. (sese_find_uses_to_rename_use): Renamed sese_build_livein_liveouts_use. (sese_find_uses_to_rename_bb): Renamed sese_build_livein_liveouts_bb. (sese_build_livein_liveouts): New. (new_sese, free_sese): New. (new_scop): Call new_sese. (free_scop): Call free_sese. (rename_variables_from_edge, rename_phis_end_scop): Removed. (register_old_new_names): Renamed register_old_and_new_names. (register_scop_liveout_renames, add_loop_exit_phis, insert_loop_close_phis, struct igp, default_liveout_before_guard, add_guard_exit_phis, insert_guard_phis, copy_renames): New. (translate_clast): Call insert_loop_close_phis and insert_guard_phis. (sese_add_exit_phis_edge): Renamed scop_add_exit_phis_edge. (rewrite_into_sese_closed_ssa): Renamed scop_insert_phis_for_liveouts. (scop_adjust_phis_for_liveouts): New. (gloog): Call scop_adjust_phis_for_liveouts. * graphite.h (struct sese): Documented. Added fields liveout, num_ver and livein. (SESE_LIVEOUT, SESE_LIVEIN, SESE_LIVEIN_VER, SESE_NUM_VER): New. (new_sese, free_sese, sese_build_livein_liveouts): Declared. (struct scop): Added field liveout_renames. (SCOP_LIVEOUT_RENAMES): New. From-SVN: r143097 --- gcc/ChangeLog | 32 +++ gcc/graphite.c | 700 ++++++++++++++++++++++++++++++++++++++------------------- gcc/graphite.h | 28 +++ 3 files changed, 533 insertions(+), 227 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 8e4b274..0cccf3b 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,35 @@ +2009-01-05 Sebastian Pop + + PR tree-optimization/38492 + * graphite.c (rename_map_elt, debug_rename_elt, + debug_rename_map_1, debug_rename_map, new_rename_map_elt, + rename_map_elt_info, eq_rename_map_elts, + get_new_name_from_old_name, bb_in_sese_p): Moved around. + (sese_find_uses_to_rename_use): Renamed sese_build_livein_liveouts_use. + (sese_find_uses_to_rename_bb): Renamed sese_build_livein_liveouts_bb. + (sese_build_livein_liveouts): New. + (new_sese, free_sese): New. + (new_scop): Call new_sese. + (free_scop): Call free_sese. + (rename_variables_from_edge, rename_phis_end_scop): Removed. + (register_old_new_names): Renamed register_old_and_new_names. + (register_scop_liveout_renames, add_loop_exit_phis, + insert_loop_close_phis, struct igp, + default_liveout_before_guard, add_guard_exit_phis, + insert_guard_phis, copy_renames): New. + (translate_clast): Call insert_loop_close_phis and insert_guard_phis. + (sese_add_exit_phis_edge): Renamed scop_add_exit_phis_edge. + (rewrite_into_sese_closed_ssa): Renamed scop_insert_phis_for_liveouts. + (scop_adjust_phis_for_liveouts): New. + (gloog): Call scop_adjust_phis_for_liveouts. + + * graphite.h (struct sese): Documented. Added fields liveout, + num_ver and livein. + (SESE_LIVEOUT, SESE_LIVEIN, SESE_LIVEIN_VER, SESE_NUM_VER): New. + (new_sese, free_sese, sese_build_livein_liveouts): Declared. + (struct scop): Added field liveout_renames. + (SCOP_LIVEOUT_RENAMES): New. + 2009-01-05 Harsha Jagasia PR tree-optimization/38510 diff --git a/gcc/graphite.c b/gcc/graphite.c index b051b5b..b03e0619 100644 --- a/gcc/graphite.c +++ b/gcc/graphite.c @@ -1183,6 +1183,169 @@ free_graphite_bb (struct graphite_bb *gbb) XDELETE (gbb); } + + +/* Structure containing the mapping between the old names and the new + names used after block copy in the new loop context. */ +typedef struct rename_map_elt +{ + tree old_name, new_name; +} *rename_map_elt; + + +/* Print to stderr the element ELT. */ + +static void +debug_rename_elt (rename_map_elt elt) +{ + fprintf (stderr, "("); + print_generic_expr (stderr, elt->old_name, 0); + fprintf (stderr, ", "); + print_generic_expr (stderr, elt->new_name, 0); + fprintf (stderr, ")\n"); +} + +/* Helper function for debug_rename_map. */ + +static int +debug_rename_map_1 (void **slot, void *s ATTRIBUTE_UNUSED) +{ + struct rename_map_elt *entry = (struct rename_map_elt *) *slot; + debug_rename_elt (entry); + return 1; +} + +/* Print to stderr all the elements of MAP. */ + +void +debug_rename_map (htab_t map) +{ + htab_traverse (map, debug_rename_map_1, NULL); +} + +/* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */ + +static inline rename_map_elt +new_rename_map_elt (tree old_name, tree new_name) +{ + rename_map_elt res; + + res = XNEW (struct rename_map_elt); + res->old_name = old_name; + res->new_name = new_name; + + return res; +} + +/* Computes a hash function for database element ELT. */ + +static hashval_t +rename_map_elt_info (const void *elt) +{ + return htab_hash_pointer (((const struct rename_map_elt *) elt)->old_name); +} + +/* Compares database elements E1 and E2. */ + +static int +eq_rename_map_elts (const void *e1, const void *e2) +{ + const struct rename_map_elt *elt1 = (const struct rename_map_elt *) e1; + const struct rename_map_elt *elt2 = (const struct rename_map_elt *) e2; + + return (elt1->old_name == elt2->old_name); +} + +/* Returns the new name associated to OLD_NAME in MAP. */ + +static tree +get_new_name_from_old_name (htab_t map, tree old_name) +{ + struct rename_map_elt tmp; + PTR *slot; + + tmp.old_name = old_name; + slot = htab_find_slot (map, &tmp, NO_INSERT); + + if (slot && *slot) + return ((rename_map_elt) *slot)->new_name; + + return old_name; +} + + + +/* Returns true when BB is in REGION. */ + +static bool +bb_in_sese_p (basic_block bb, sese region) +{ + return pointer_set_contains (SESE_REGION_BBS (region), bb); +} + +/* For a USE in BB, if BB is outside REGION, mark the USE in the + SESE_LIVEIN and SESE_LIVEOUT sets. */ + +static void +sese_build_livein_liveouts_use (sese region, basic_block bb, tree use) +{ + unsigned ver; + basic_block def_bb; + + if (TREE_CODE (use) != SSA_NAME) + return; + + ver = SSA_NAME_VERSION (use); + def_bb = gimple_bb (SSA_NAME_DEF_STMT (use)); + if (!def_bb + || !bb_in_sese_p (def_bb, region) + || bb_in_sese_p (bb, region)) + return; + + if (!SESE_LIVEIN_VER (region, ver)) + SESE_LIVEIN_VER (region, ver) = BITMAP_ALLOC (NULL); + + bitmap_set_bit (SESE_LIVEIN_VER (region, ver), bb->index); + bitmap_set_bit (SESE_LIVEOUT (region), ver); +} + +/* Marks for rewrite all the SSA_NAMES defined in REGION and that are + used in BB that is outside of the REGION. */ + +static void +sese_build_livein_liveouts_bb (sese region, basic_block bb) +{ + gimple_stmt_iterator bsi; + edge e; + edge_iterator ei; + ssa_op_iter iter; + tree var; + + FOR_EACH_EDGE (e, ei, bb->succs) + for (bsi = gsi_start_phis (e->dest); !gsi_end_p (bsi); gsi_next (&bsi)) + sese_build_livein_liveouts_use (region, bb, + PHI_ARG_DEF_FROM_EDGE (gsi_stmt (bsi), e)); + + for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi)) + FOR_EACH_SSA_TREE_OPERAND (var, gsi_stmt (bsi), iter, SSA_OP_ALL_USES) + sese_build_livein_liveouts_use (region, bb, var); +} + +/* Build the SESE_LIVEIN and SESE_LIVEOUT for REGION. */ + +void +sese_build_livein_liveouts (sese region) +{ + basic_block bb; + + SESE_LIVEOUT (region) = BITMAP_ALLOC (NULL); + SESE_NUM_VER (region) = num_ssa_names; + SESE_LIVEIN (region) = XCNEWVEC (bitmap, SESE_NUM_VER (region)); + + FOR_EACH_BB (bb) + sese_build_livein_liveouts_bb (region, bb); +} + /* Register basic blocks belonging to a region in a pointer set. */ static void @@ -1203,6 +1366,47 @@ register_bb_in_sese (basic_block entry_bb, basic_block exit_bb, sese region) } } +/* Builds a new SESE region from edges ENTRY and EXIT. */ + +sese +new_sese (edge entry, edge exit) +{ + sese res = XNEW (struct sese); + + SESE_ENTRY (res) = entry; + SESE_EXIT (res) = exit; + SESE_REGION_BBS (res) = pointer_set_create (); + register_bb_in_sese (entry->dest, exit->dest, res); + + SESE_LIVEOUT (res) = NULL; + SESE_NUM_VER (res) = 0; + SESE_LIVEIN (res) = NULL; + + return res; +} + +/* Deletes REGION. */ + +void +free_sese (sese region) +{ + int i; + + for (i = 0; i < SESE_NUM_VER (region); i++) + BITMAP_FREE (SESE_LIVEIN_VER (region, i)); + + if (SESE_LIVEIN (region)) + free (SESE_LIVEIN (region)); + + if (SESE_LIVEOUT (region)) + BITMAP_FREE (SESE_LIVEOUT (region)); + + pointer_set_destroy (SESE_REGION_BBS (region)); + XDELETE (region); +} + + + /* Creates a new scop starting with ENTRY. */ static scop_p @@ -1212,12 +1416,7 @@ new_scop (edge entry, edge exit) gcc_assert (entry && exit); - SCOP_REGION (scop) = XNEW (struct sese); - SESE_ENTRY (SCOP_REGION (scop)) = entry; - SESE_EXIT (SCOP_REGION (scop)) = exit; - SESE_REGION_BBS (SCOP_REGION (scop)) = pointer_set_create (); - register_bb_in_sese (SCOP_ENTRY (scop), SCOP_EXIT (scop), - SCOP_REGION (scop)); + SCOP_REGION (scop) = new_sese (entry, exit); SCOP_BBS (scop) = VEC_alloc (graphite_bb_p, heap, 3); SCOP_OLDIVS (scop) = VEC_alloc (name_tree, heap, 3); SCOP_BBS_B (scop) = BITMAP_ALLOC (NULL); @@ -1230,6 +1429,8 @@ new_scop (edge entry, edge exit) SCOP_LOOP2CLOOG_LOOP (scop) = htab_create (10, hash_loop_to_cloog_loop, eq_loop_to_cloog_loop, free); + SCOP_LIVEOUT_RENAMES (scop) = htab_create (10, rename_map_elt_info, + eq_rename_map_elts, free); return scop; } @@ -1261,7 +1462,8 @@ free_scop (scop_p scop) VEC_free (name_tree, heap, SCOP_PARAMS (scop)); cloog_program_free (SCOP_PROG (scop)); htab_delete (SCOP_LOOP2CLOOG_LOOP (scop)); - XDELETE (SCOP_REGION (scop)); + htab_delete (SCOP_LIVEOUT_RENAMES (scop)); + free_sese (SCOP_REGION (scop)); XDELETE (scop); } @@ -3754,94 +3956,6 @@ graphite_create_new_loop (scop_p scop, edge entry_edge, return loop; } -/* Structure containing the mapping between the old names and the new - names used after block copy in the new loop context. */ -typedef struct rename_map_elt -{ - tree old_name, new_name; -} *rename_map_elt; - - -/* Print to stderr the element ELT. */ - -static void -debug_rename_elt (rename_map_elt elt) -{ - fprintf (stderr, "("); - print_generic_expr (stderr, elt->old_name, 0); - fprintf (stderr, ", "); - print_generic_expr (stderr, elt->new_name, 0); - fprintf (stderr, ")\n"); -} - -/* Helper function for debug_rename_map. */ - -static int -debug_rename_map_1 (void **slot, void *s ATTRIBUTE_UNUSED) -{ - struct rename_map_elt *entry = (struct rename_map_elt *) *slot; - debug_rename_elt (entry); - return 1; -} - -/* Print to stderr all the elements of MAP. */ - -void -debug_rename_map (htab_t map) -{ - htab_traverse (map, debug_rename_map_1, NULL); -} - -/* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */ - -static inline rename_map_elt -new_rename_map_elt (tree old_name, tree new_name) -{ - rename_map_elt res; - - res = XNEW (struct rename_map_elt); - res->old_name = old_name; - res->new_name = new_name; - - return res; -} - -/* Computes a hash function for database element ELT. */ - -static hashval_t -rename_map_elt_info (const void *elt) -{ - return htab_hash_pointer (((const struct rename_map_elt *) elt)->old_name); -} - -/* Compares database elements E1 and E2. */ - -static int -eq_rename_map_elts (const void *e1, const void *e2) -{ - const struct rename_map_elt *elt1 = (const struct rename_map_elt *) e1; - const struct rename_map_elt *elt2 = (const struct rename_map_elt *) e2; - - return (elt1->old_name == elt2->old_name); -} - -/* Returns the new name associated to OLD_NAME in MAP. */ - -static tree -get_new_name_from_old_name (htab_t map, tree old_name) -{ - struct rename_map_elt tmp; - PTR *slot; - - tmp.old_name = old_name; - slot = htab_find_slot (map, &tmp, NO_INSERT); - - if (slot && *slot) - return ((rename_map_elt) *slot)->new_name; - - return old_name; -} - /* Rename the SSA_NAMEs used in STMT and that appear in IVSTACK. */ static void @@ -4032,38 +4146,6 @@ rename_variables (basic_block bb, htab_t map) rename_variables_in_stmt (gsi_stmt (gsi), map); } -/* Rename following the information from MAP the PHI node argument - corresponding to the edge E. In order to allow several renames of - that argument, we match the original SSA_NAME on the argument - coming from the edge different than E. */ - -static void -rename_variables_from_edge (edge e, gimple phi, htab_t map) -{ - int n = e->dest_idx == 0 ? 1 : 0; - tree old_name = gimple_phi_arg_def (phi, n); - tree new_name = get_new_name_from_old_name (map, old_name); - - gcc_assert (gimple_phi_num_args (phi) == 2 - && gimple_phi_arg_edge (phi, e->dest_idx) == e); - - SET_PHI_ARG_DEF (phi, n, new_name); -} - -/* Rename all the phi arguments for the edges comming from the scop - according to the MAP. */ - -static void -rename_phis_end_scop (scop_p scop, htab_t map) -{ - basic_block after_scop = SCOP_EXIT (scop); - edge e = SESE_EXIT (SCOP_REGION (scop)); - gimple_stmt_iterator gsi; - - for (gsi = gsi_start_phis (after_scop); !gsi_end_p (gsi); gsi_next (&gsi)) - rename_variables_from_edge (e, gsi_stmt (gsi), map); -} - /* Remove condition from BB. */ static void @@ -4144,7 +4226,7 @@ build_iv_mapping (loop_iv_stack ivstack, htab_t map, gbb_p gbb, scop_p scop) /* Register in MAP the tuple (old_name, new_name). */ static void -register_old_new_names (htab_t map, tree old_name, tree new_name) +register_old_and_new_names (htab_t map, tree old_name, tree new_name) { struct rename_map_elt tmp; PTR *slot; @@ -4193,11 +4275,32 @@ graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb, htab_t map) { tree old_name = DEF_FROM_PTR (def_p); tree new_name = create_new_def_for (old_name, copy, def_p); - register_old_new_names (map, old_name, new_name); + register_old_and_new_names (map, old_name, new_name); } } } +/* Records in SCOP_LIVEOUT_RENAMES the names that are live out of + the SCOP and that appear in the RENAME_MAP. */ + +static void +register_scop_liveout_renames (scop_p scop, htab_t rename_map) +{ + int i; + sese region = SCOP_REGION (scop); + + for (i = 0; i < SESE_NUM_VER (region); i++) + if (bitmap_bit_p (SESE_LIVEOUT (region), i) + && is_gimple_reg (ssa_name (i))) + { + tree old_name = ssa_name (i); + tree new_name = get_new_name_from_old_name (rename_map, old_name); + + register_old_and_new_names (SCOP_LIVEOUT_RENAMES (scop), + old_name, new_name); + } +} + /* Copies BB and includes in the copied BB all the statements that can be reached following the use-def chains from the memory accesses, and returns the next edge following this new block. */ @@ -4215,15 +4318,153 @@ copy_bb_and_scalar_dependences (basic_block bb, scop_p scop, rename_variables (new_bb, map); remove_phi_nodes (new_bb); expand_scalar_variables (new_bb, scop, context_loop, map); - rename_phis_end_scop (scop, map); + register_scop_liveout_renames (scop, map); return next_e; } -/* Translates a CLAST statement STMT to GCC representation. NEXT_E is - the edge where new generated code should be attached. BB_EXIT is the last - basic block that defines the scope of code generation. CONTEXT_LOOP is the - loop in which the generated code will be placed (might be NULL). */ +/* Helper function for htab_traverse in insert_loop_close_phis. */ + +static int +add_loop_exit_phis (void **slot, void *s) +{ + struct rename_map_elt *entry = (struct rename_map_elt *) *slot; + tree new_name = entry->new_name; + basic_block bb = (basic_block) s; + gimple phi = create_phi_node (new_name, bb); + tree res = create_new_def_for (gimple_phi_result (phi), phi, + gimple_phi_result_ptr (phi)); + + add_phi_arg (phi, new_name, single_pred_edge (bb)); + + entry->new_name = res; + *slot = entry; + return 1; +} + +/* Iterate over the SCOP_LIVEOUT_RENAMES (SCOP) and get tuples of the + form (OLD_NAME, NEW_NAME). Insert in BB "RES = phi (NEW_NAME)", + and finally register in SCOP_LIVEOUT_RENAMES (scop) the tuple + (OLD_NAME, RES). */ + +static void +insert_loop_close_phis (scop_p scop, basic_block bb) +{ + update_ssa (TODO_update_ssa); + htab_traverse (SCOP_LIVEOUT_RENAMES (scop), add_loop_exit_phis, bb); + update_ssa (TODO_update_ssa); +} + +/* Helper structure for htab_traverse in insert_guard_phis. */ + +struct igp { + basic_block bb; + edge true_edge, false_edge; + htab_t liveout_before_guard; +}; + +/* Return the default name that is before the guard. */ + +static tree +default_liveout_before_guard (htab_t liveout_before_guard, tree old_name) +{ + tree res = get_new_name_from_old_name (liveout_before_guard, old_name); + + if (res == old_name) + { + if (is_gimple_reg (res)) + return fold_convert (TREE_TYPE (res), integer_zero_node); + return gimple_default_def (cfun, res); + } + + return res; +} + +/* Helper function for htab_traverse in insert_guard_phis. */ + +static int +add_guard_exit_phis (void **slot, void *s) +{ + struct rename_map_elt *entry = (struct rename_map_elt *) *slot; + struct igp *i = (struct igp *) s; + basic_block bb = i->bb; + edge true_edge = i->true_edge; + edge false_edge = i->false_edge; + tree name1 = entry->new_name; + tree name2 = default_liveout_before_guard (i->liveout_before_guard, + entry->old_name); + gimple phi = create_phi_node (name1, bb); + tree res = create_new_def_for (gimple_phi_result (phi), phi, + gimple_phi_result_ptr (phi)); + + add_phi_arg (phi, name1, true_edge); + add_phi_arg (phi, name2, false_edge); + + entry->new_name = res; + *slot = entry; + return 1; +} + +/* Iterate over the SCOP_LIVEOUT_RENAMES (SCOP) and get tuples of the + form (OLD_NAME, NAME1). If there is a correspondent tuple of + OLD_NAME in LIVEOUT_BEFORE_GUARD, i.e. (OLD_NAME, NAME2) then + insert in BB + + | RES = phi (NAME1 (on TRUE_EDGE), NAME2 (on FALSE_EDGE))" + + if there is no tuple for OLD_NAME in LIVEOUT_BEFORE_GUARD, insert + + | RES = phi (NAME1 (on TRUE_EDGE), + | DEFAULT_DEFINITION of NAME1 (on FALSE_EDGE))". + + Finally register in SCOP_LIVEOUT_RENAMES (scop) the tuple + (OLD_NAME, RES). */ + +static void +insert_guard_phis (scop_p scop, basic_block bb, edge true_edge, + edge false_edge, htab_t liveout_before_guard) +{ + struct igp i; + i.bb = bb; + i.true_edge = true_edge; + i.false_edge = false_edge; + i.liveout_before_guard = liveout_before_guard; + + update_ssa (TODO_update_ssa); + htab_traverse (SCOP_LIVEOUT_RENAMES (scop), add_guard_exit_phis, &i); + update_ssa (TODO_update_ssa); +} + +/* Helper function for htab_traverse. */ + +static int +copy_renames (void **slot, void *s) +{ + struct rename_map_elt *entry = (struct rename_map_elt *) *slot; + htab_t res = (htab_t) s; + tree old_name = entry->old_name; + tree new_name = entry->new_name; + struct rename_map_elt tmp; + PTR *x; + + tmp.old_name = old_name; + x = htab_find_slot (res, &tmp, INSERT); + + if (!*x) + *x = new_rename_map_elt (old_name, new_name); + + return 1; +} + +/* Translates a CLAST statement STMT to GCC representation in the + context of a SCOP. + + - NEXT_E is the edge where new generated code should be attached. + - CONTEXT_LOOP is the loop in which the generated code will be placed + (might be NULL). + - IVSTACK contains the surrounding loops around the statement to be + translated. +*/ static edge translate_clast (scop_p scop, struct loop *context_loop, @@ -4264,14 +4505,16 @@ translate_clast (scop_p scop, struct loop *context_loop, ivstack, context_loop ? context_loop : get_loop (0)); edge last_e = single_exit (loop); - + next_e = translate_clast (scop, loop, ((struct clast_for *) stmt)->body, single_pred_edge (loop->latch), ivstack); redirect_edge_succ_nodup (next_e, loop->latch); - + set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src); loop_iv_stack_pop (ivstack); last_e = single_succ_edge (split_edge (last_e)); + insert_loop_close_phis (scop, last_e->src); + recompute_all_dominators (); graphite_verify (); return translate_clast (scop, context_loop, stmt->next, last_e, ivstack); @@ -4279,15 +4522,28 @@ translate_clast (scop_p scop, struct loop *context_loop, if (CLAST_STMT_IS_A (stmt, stmt_guard)) { + htab_t liveout_before_guard = htab_create (10, rename_map_elt_info, + eq_rename_map_elts, free); edge last_e = graphite_create_new_guard (scop, next_e, ((struct clast_guard *) stmt), ivstack); edge true_e = get_true_edge_from_guard_bb (next_e->dest); + edge false_e = get_false_edge_from_guard_bb (next_e->dest); + edge exit_true_e = single_succ_edge (true_e->dest); + edge exit_false_e = single_succ_edge (false_e->dest); + + htab_traverse (SCOP_LIVEOUT_RENAMES (scop), copy_renames, + liveout_before_guard); + next_e = translate_clast (scop, context_loop, ((struct clast_guard *) stmt)->then, true_e, ivstack); + insert_guard_phis (scop, last_e->src, exit_true_e, exit_false_e, + liveout_before_guard); + htab_delete (liveout_before_guard); recompute_all_dominators (); graphite_verify (); + return translate_clast (scop, context_loop, stmt->next, last_e, ivstack); } @@ -4710,72 +4966,10 @@ move_sese_in_condition (sese region) return if_region; } -/* Returns true when BB is in REGION. */ - -static bool -bb_in_sese_p (basic_block bb, sese region) -{ - return pointer_set_contains (SESE_REGION_BBS (region), bb); -} - -/* For USE in BB, if it is used outside of the REGION it is defined in, - mark it for rewrite. Record basic block BB where it is used - to USE_BLOCKS. Record the ssa name index to NEED_PHIS bitmap. */ - -static void -sese_find_uses_to_rename_use (sese region, basic_block bb, tree use, - bitmap *use_blocks, bitmap need_phis) -{ - unsigned ver; - basic_block def_bb; - - if (TREE_CODE (use) != SSA_NAME) - return; - - ver = SSA_NAME_VERSION (use); - def_bb = gimple_bb (SSA_NAME_DEF_STMT (use)); - if (!def_bb - || !bb_in_sese_p (def_bb, region) - || bb_in_sese_p (bb, region)) - return; - - if (!use_blocks[ver]) - use_blocks[ver] = BITMAP_ALLOC (NULL); - bitmap_set_bit (use_blocks[ver], bb->index); - - bitmap_set_bit (need_phis, ver); -} - -/* Marks names that are used in BB and outside of the loop they are - defined in for rewrite. Records the set of blocks in that the ssa - names are defined to USE_BLOCKS. Record the SSA names that will - need exit PHIs in NEED_PHIS. */ - -static void -sese_find_uses_to_rename_bb (sese region, basic_block bb, - bitmap *use_blocks, bitmap need_phis) -{ - gimple_stmt_iterator bsi; - edge e; - edge_iterator ei; - ssa_op_iter iter; - tree var; - - FOR_EACH_EDGE (e, ei, bb->succs) - for (bsi = gsi_start_phis (e->dest); !gsi_end_p (bsi); gsi_next (&bsi)) - sese_find_uses_to_rename_use (region, bb, - PHI_ARG_DEF_FROM_EDGE (gsi_stmt (bsi), e), - use_blocks, need_phis); - - for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi)) - FOR_EACH_SSA_TREE_OPERAND (var, gsi_stmt (bsi), iter, SSA_OP_ALL_USES) - sese_find_uses_to_rename_use (region, bb, var, use_blocks, need_phis); -} - /* Add exit phis for USE on EXIT. */ static void -sese_add_exit_phis_edge (basic_block exit, tree use, edge false_e, edge true_e) +scop_add_exit_phis_edge (basic_block exit, tree use, edge false_e, edge true_e) { gimple phi = create_phi_node (use, exit); @@ -4786,10 +4980,10 @@ sese_add_exit_phis_edge (basic_block exit, tree use, edge false_e, edge true_e) } /* Add phi nodes for VAR that is used in LIVEIN. Phi nodes are - inserted in block WHERE. */ + inserted in block BB. */ static void -sese_add_exit_phis_var (basic_block where, tree var, bitmap livein, +scop_add_exit_phis_var (basic_block bb, tree var, bitmap livein, edge false_e, edge true_e) { bitmap def; @@ -4805,39 +4999,82 @@ sese_add_exit_phis_var (basic_block where, tree var, bitmap livein, compute_global_livein (livein, def); BITMAP_FREE (def); - sese_add_exit_phis_edge (where, var, false_e, true_e); + scop_add_exit_phis_edge (bb, var, false_e, true_e); } -/* Insert in the block WHERE phi nodes for variables defined in REGION - and used outside the REGION. */ +/* Insert in the block BB phi nodes for variables defined in REGION + and used outside the REGION. The code generation moves REGION in + the else clause of an "if (1)" and generates code in the then + clause that is at this point empty: + + | if (1) + | empty; + | else + | REGION; +*/ static void -rewrite_into_sese_closed_ssa (sese region, basic_block where, - edge false_e, edge true_e) +scop_insert_phis_for_liveouts (sese region, basic_block bb, + edge false_e, edge true_e) { unsigned i; - basic_block bb; bitmap_iterator bi; - bitmap names_to_rename = BITMAP_ALLOC (NULL); - unsigned old_num_ssa_names = num_ssa_names; - bitmap *use_blocks = XCNEWVEC (bitmap, old_num_ssa_names); update_ssa (TODO_update_ssa); - FOR_EACH_BB (bb) - sese_find_uses_to_rename_bb (region, bb, use_blocks, names_to_rename); - - EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i, bi) - sese_add_exit_phis_var (where, ssa_name (i), use_blocks[i], + EXECUTE_IF_SET_IN_BITMAP (SESE_LIVEOUT (region), 0, i, bi) + scop_add_exit_phis_var (bb, ssa_name (i), SESE_LIVEIN_VER (region, i), false_e, true_e); update_ssa (TODO_update_ssa); +} - for (i = 0; i < old_num_ssa_names; i++) - BITMAP_FREE (use_blocks[i]); +/* Adjusts the phi nodes in the block BB for variables defined in + SCOP_REGION and used outside the SCOP_REGION. The code generation + moves SCOP_REGION in the else clause of an "if (1)" and generates + code in the then clause: - free (use_blocks); - BITMAP_FREE (names_to_rename); + | if (1) + | generated code from REGION; + | else + | REGION; + + To adjust the phi nodes after the condition, SCOP_LIVEOUT_RENAMES + hash table is used: this stores for a name that is part of the + LIVEOUT of SCOP_REGION its new name in the generated code. */ + +static void +scop_adjust_phis_for_liveouts (scop_p scop, basic_block bb, edge false_e, + edge true_e) +{ + gimple_stmt_iterator si; + + for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si)) + { + unsigned i, false_i; + gimple phi = gsi_stmt (si); + + if (!is_gimple_reg (PHI_RESULT (phi))) + continue; + + for (i = 0; i < gimple_phi_num_args (phi); i++) + if (gimple_phi_arg_edge (phi, i) == false_e) + { + false_i = i; + break; + } + + for (i = 0; i < gimple_phi_num_args (phi); i++) + if (gimple_phi_arg_edge (phi, i) == true_e) + { + tree old_name = gimple_phi_arg_def (phi, false_i); + tree new_name = get_new_name_from_old_name + (SCOP_LIVEOUT_RENAMES (scop), old_name); + + gcc_assert (old_name != new_name); + SET_PHI_ARG_DEF (phi, i, new_name); + } + } } /* Returns the first cloog name used in EXPR. */ @@ -4976,24 +5213,33 @@ gloog (scop_p scop, struct clast_stmt *stmt) } if_region = move_sese_in_condition (SCOP_REGION (scop)); - rewrite_into_sese_closed_ssa (SCOP_REGION (scop), - if_region->region->exit->src, - if_region->false_region->exit, - if_region->true_region->exit); + sese_build_livein_liveouts (SCOP_REGION (scop)); + scop_insert_phis_for_liveouts (SCOP_REGION (scop), + if_region->region->exit->src, + if_region->false_region->exit, + if_region->true_region->exit); recompute_all_dominators (); graphite_verify (); context_loop = SESE_ENTRY (SCOP_REGION (scop))->src->loop_father; compute_cloog_iv_types (stmt); - new_scop_exit_edge = translate_clast (scop, context_loop, - stmt, if_region->true_region->entry, + + new_scop_exit_edge = translate_clast (scop, context_loop, stmt, + if_region->true_region->entry, &ivstack); + free_loop_iv_stack (&ivstack); + cloog_clast_free (stmt); + + graphite_verify (); + scop_adjust_phis_for_liveouts (scop, + if_region->region->exit->src, + if_region->false_region->exit, + if_region->true_region->exit); + recompute_all_dominators (); graphite_verify (); cleanup_tree_cfg (); recompute_all_dominators (); graphite_verify (); - free_loop_iv_stack (&ivstack); - cloog_clast_free (stmt); } /* Returns the number of data references in SCOP. */ diff --git a/gcc/graphite.h b/gcc/graphite.h index 92a6816..76f26c8 100644 --- a/gcc/graphite.h +++ b/gcc/graphite.h @@ -275,13 +275,36 @@ DEF_VEC_ALLOC_P (name_tree, heap); by two edges. */ typedef struct sese { + /* Single ENTRY and single EXIT from the SESE region. */ edge entry, exit; + + /* REGION_BASIC_BLOCKS contains the set of all the basic blocks + belonging to the SESE region. */ struct pointer_set_t *region_basic_blocks; + + /* An SSA_NAME version is flagged in the LIVEOUT bitmap if the + SSA_NAME is defined inside and used outside the SESE region. */ + bitmap liveout; + + /* The overall number of SSA_NAME versions used to index LIVEIN. */ + int num_ver; + + /* For each SSA_NAME version VER in LIVEOUT, LIVEIN[VER] contains + the set of basic blocks indices that contain a use of VER. */ + bitmap *livein; } *sese; #define SESE_ENTRY(S) (S->entry) #define SESE_EXIT(S) (S->exit) #define SESE_REGION_BBS(S) (S->region_basic_blocks) +#define SESE_LIVEOUT(S) (S->liveout) +#define SESE_LIVEIN(S) (S->livein) +#define SESE_LIVEIN_VER(S, I) (S->livein[I]) +#define SESE_NUM_VER(S) (S->num_ver) + +extern sese new_sese (edge, edge); +extern void free_sese (sese); +extern void sese_build_livein_liveouts (sese); /* A SCOP is a Static Control Part of the program, simple enough to be represented in polyhedral form. */ @@ -319,6 +342,10 @@ struct scop can only add new params before generating the bb domains, otherwise they become invalid. */ bool add_params; + + /* LIVEOUT_RENAMES registers the rename mapping that has to be + applied after code generation. */ + htab_t liveout_renames; }; #define SCOP_BBS(S) S->bbs @@ -341,6 +368,7 @@ struct scop #define SCOP_PROG(S) S->program #define SCOP_LOOP2CLOOG_LOOP(S) S->loop2cloog_loop #define SCOP_LOOPS_MAPPING(S) S->loops_mapping +#define SCOP_LIVEOUT_RENAMES(S) S->liveout_renames extern void debug_scop (scop_p, int); extern void debug_scops (int); -- 2.7.4