This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[patch][graphite] Fix PR38492: segfaulting code when compiled with -fgraphite -fgraphite-identity
- From: "Sebastian Pop" <sebpop at gmail dot com>
- To: "GCC Patches" <gcc-patches at gcc dot gnu dot org>, "Richard Guenther" <rguenther at suse dot de>
- Date: Fri, 12 Dec 2008 15:51:06 -0600
- Subject: [patch][graphite] Fix PR38492: segfaulting code when compiled with -fgraphite -fgraphite-identity
Hi,
I committed the attached patch to the graphite branch: it fixes at
least PR38492 that was reported as generating wrong code from
-fgraphite-identity. I'm still testing this patch so I cannot say yet
whether it also fixes the bootstrap of GCC with -fgraphite-identity in
BOOT_CFLAGS. Okay for trunk once it finishes regstrap?
Thanks,
Sebastian Pop
--
AMD - GNU Tools
2008-12-12 Sebastian Pop <sebastian.pop@amd.com>
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.
Index: graphite.c
===================================================================
--- graphite.c (revision 142693)
+++ graphite.c (working copy)
@@ -1190,6 +1190,169 @@ free_graphite_bb (struct graphite_bb *gb
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
@@ -1210,6 +1373,47 @@ register_bb_in_sese (basic_block entry_b
}
}
+/* 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
@@ -1219,12 +1423,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);
@@ -1237,6 +1436,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);
SCOP_DEP_GRAPH (scop) = NULL;
return scop;
}
@@ -1269,7 +1470,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);
}
@@ -3759,94 +3961,6 @@ graphite_create_new_loop (scop_p scop, e
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
@@ -4037,38 +4151,6 @@ rename_variables (basic_block bb, htab_t
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
@@ -4149,7 +4231,7 @@ build_iv_mapping (loop_iv_stack ivstack,
/* 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;
@@ -4198,11 +4280,32 @@ graphite_copy_stmts_from_block (basic_bl
{
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. */
@@ -4220,15 +4323,153 @@ copy_bb_and_scalar_dependences (basic_bl
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,
@@ -4269,14 +4510,16 @@ translate_clast (scop_p scop, struct loo
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);
@@ -4284,14 +4527,27 @@ translate_clast (scop_p scop, struct loo
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);
graphite_verify ();
+
return translate_clast (scop, context_loop, stmt->next, last_e, ivstack);
}
@@ -4713,72 +4969,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);
@@ -4789,10 +4983,10 @@ sese_add_exit_phis_edge (basic_block exi
}
/* 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;
@@ -4808,39 +5002,82 @@ sese_add_exit_phis_var (basic_block wher
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. */
@@ -4979,22 +5216,31 @@ gloog (scop_p scop, struct clast_stmt *s
}
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);
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);
+
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. */
Index: graphite.h
===================================================================
--- graphite.h (revision 142685)
+++ graphite.h (working copy)
@@ -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. */
@@ -322,6 +345,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
@@ -345,6 +372,7 @@ struct scop
#define SCOP_LOOP2CLOOG_LOOP(S) S->loop2cloog_loop
#define SCOP_LOOPS_MAPPING(S) S->loops_mapping
#define SCOP_DEP_GRAPH(S) S->dep_graph
+#define SCOP_LIVEOUT_RENAMES(S) S->liveout_renames
extern void debug_scop (scop_p, int);
extern void debug_scops (int);