This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Fix bug in graphite
- From: Tobias Grosser <grosser at fim dot uni-passau dot de>
- To: GCC Patches <gcc-patches at gcc dot gnu dot org>
- Date: Tue, 03 Feb 2009 19:56:56 -0600
- Subject: Fix bug in graphite
Hi,
I would like to commit this patch to gcc trunk.
It fixes a bug in graphite scop detection, that was found during libjava
compilation. I also included the reduced test case.
The patch was bootstrapped without problems.
See you
Tobias
* graphite.c (bb_in_sese_p, sese_build_livein_liveouts_use,
sese_build_livein_liveouts_bb, sese_build_livein_liveouts,
register_bb_in_sese, new_sese, free_sese): Moved.
(dot_scop_1, build_scop_loop_nests, build_loop_iteration_domains,
outermost_loop_in_scop, build_scop_iteration_domain,
expand_scalar_variables_ssa_name, get_vdef_before_scop,
limit_scops): Use bb_in_sese_p instead of bb_in_scop_p.
Use loop_in_sese_p instead of loop_in_scop_p.
(new_graphite_bb, new_scop, gloog): Do not initialize SCOP_BBS_B.
(free_scop): Do not free SCOP_BBS_B.
(nb_loops_around_loop_in_scop, nb_loops_around_gb,
ref_nb_loops): Moved here...
* graphite.h (ref_nb_loops): ... from here.
(struct scop): Remove bbs_b bitmap.
(SCOP_BBS_B, bb_in_scop_p, loop_in_scop_p): Removed.
* testsuite/gcc.dg/graphite/scop-19.c: New
* graphite.c (scopdet_basic_block_info): Fix bug in scop
detection.
* graphite.c (new_loop_to_cloog_loop_str, hash_loop_to_cloog_loop,
eq_loop_to_cloog_loop): Remove.
(new_scop, free_scop): Remove SCOP_LOOP2CLOOG_LOOP.
* graphite.h (struct scop): Remove loop2cloog_loop.
(loop_domain_dim, loop_iteration_vector_dim): Remove.
Index: gcc/graphite.c
===================================================================
--- gcc/graphite.c (revision 143917)
+++ gcc/graphite.c (working copy)
@@ -69,6 +69,147 @@
return build_int_cst (type, value_get_si (v));
}
+/* 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);
+}
+
+/* Returns true when LOOP is in the SESE region R. */
+
+static inline bool
+loop_in_sese_p (struct loop *loop, sese r)
+{
+ return (bb_in_sese_p (loop->header, r)
+ && bb_in_sese_p (loop->latch, r));
+}
+
+/* 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
+register_bb_in_sese (basic_block entry_bb, basic_block exit_bb, sese region)
+{
+ edge_iterator ei;
+ edge e;
+ basic_block bb = entry_bb;
+
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ {
+ if (!pointer_set_contains (SESE_REGION_BBS (region), e->dest) &&
+ e->dest->index != exit_bb->index)
+ {
+ pointer_set_insert (SESE_REGION_BBS (region), e->dest);
+ register_bb_in_sese (e->dest, exit_bb, 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);
+}
+
+
+
/* Debug the list of old induction variables for this SCOP. */
void
@@ -701,7 +842,7 @@
if (bb == exit)
fprintf (file, "%d [shape=box];\n", bb->index);
- if (bb_in_scop_p (bb, scop))
+ if (bb_in_sese_p (bb, SCOP_REGION (scop)))
fprintf (file, "%d [color=red];\n", bb->index);
FOR_EACH_EDGE (e, ei, bb->succs)
@@ -755,7 +896,7 @@
/* Select color for SCoP. */
for (i = 0; VEC_iterate (scop_p, current_scops, i, scop); i++)
- if (bb_in_scop_p (bb, scop)
+ if (bb_in_sese_p (bb, SCOP_REGION (scop))
|| (SCOP_EXIT (scop) == bb)
|| (SCOP_ENTRY (scop) == bb))
{
@@ -818,7 +959,7 @@
fprintf (file, " <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">", color);
- if (!bb_in_scop_p (bb, scop))
+ if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
fprintf (file, " (");
if (bb == SCOP_ENTRY (scop)
@@ -831,7 +972,7 @@
else
fprintf (file, " %d ", bb->index);
- if (!bb_in_scop_p (bb, scop))
+ if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
fprintf (file, ")");
fprintf (file, "</TD></TR>\n");
@@ -887,7 +1028,8 @@
struct loop *nest;
nest = bb->loop_father;
- while (loop_outer (nest) && loop_in_scop_p (loop_outer (nest), scop))
+ while (loop_outer (nest)
+ && loop_in_sese_p (loop_outer (nest), SCOP_REGION (scop)))
nest = loop_outer (nest);
return nest;
@@ -1133,8 +1275,6 @@
struct loop *nest = outermost_loop_in_scop (scop, bb);
gimple_stmt_iterator gsi;
- bitmap_set_bit (SCOP_BBS_B (scop), bb->index);
-
for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
find_data_references_in_stmt (nest, gsi_stmt (gsi), &drs);
@@ -1273,138 +1413,6 @@
-/* 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
-register_bb_in_sese (basic_block entry_bb, basic_block exit_bb, sese region)
-{
- edge_iterator ei;
- edge e;
- basic_block bb = entry_bb;
-
- FOR_EACH_EDGE (e, ei, bb->succs)
- {
- if (!pointer_set_contains (SESE_REGION_BBS (region), e->dest) &&
- e->dest->index != exit_bb->index)
- {
- pointer_set_insert (SESE_REGION_BBS (region), e->dest);
- register_bb_in_sese (e->dest, exit_bb, 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
@@ -1417,7 +1425,6 @@
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);
SCOP_LOOPS (scop) = BITMAP_ALLOC (NULL);
SCOP_LOOP_NEST (scop) = VEC_alloc (loop_p, heap, 3);
SCOP_ADD_PARAMS (scop) = true;
@@ -1446,7 +1453,6 @@
free_graphite_bb (gb);
VEC_free (graphite_bb_p, heap, SCOP_BBS (scop));
- BITMAP_FREE (SCOP_BBS_B (scop));
BITMAP_FREE (SCOP_LOOPS (scop));
VEC_free (loop_p, heap, SCOP_LOOP_NEST (scop));
@@ -1632,6 +1638,12 @@
result.next = NULL;
result.exits = false;
result.last = bb;
+
+ /* Mark bbs terminating a SESE region difficult, if they start
+ a condition. */
+ if (VEC_length (edge, bb->succs) > 1)
+ result.difficult = true;
+
break;
case GBB_SIMPLE:
@@ -2410,13 +2422,13 @@
struct loop *loop0, *loop1;
FOR_EACH_BB (bb)
- if (bb_in_scop_p (bb, scop))
+ if (bb_in_sese_p (bb, SCOP_REGION (scop)))
{
struct loop *loop = bb->loop_father;
/* Only add loops if they are completely contained in the SCoP. */
if (loop->header == bb
- && bb_in_scop_p (loop->latch, scop))
+ && bb_in_sese_p (loop->latch, SCOP_REGION (scop)))
{
if (!scop_record_loop (scop, loop))
return false;
@@ -2442,6 +2454,40 @@
return true;
}
+/* Calculate the number of loops around LOOP in the SCOP. */
+
+static inline int
+nb_loops_around_loop_in_scop (struct loop *l, scop_p scop)
+{
+ int d = 0;
+
+ for (; loop_in_sese_p (l, SCOP_REGION (scop)); d++, l = loop_outer (l));
+
+ return d;
+}
+
+/* Calculate the number of loops around GB in the current SCOP. */
+
+int
+nb_loops_around_gb (graphite_bb_p gb)
+{
+ return nb_loops_around_loop_in_scop (gbb_loop (gb), GBB_SCOP (gb));
+}
+
+/* Returns the dimensionality of an enclosing loop iteration domain
+ with respect to enclosing SCoP for a given data reference REF. The
+ returned dimensionality is homogeneous (depth of loop nest + number
+ of SCoP parameters + const). */
+
+int
+ref_nb_loops (data_reference_p ref)
+{
+ loop_p loop = loop_containing_stmt (DR_STMT (ref));
+ scop_p scop = DR_SCOP (ref);
+
+ return nb_loops_around_loop_in_scop (loop, scop) + scop_nb_params (scop) + 2;
+}
+
/* Build dynamic schedules for all the BBs. */
static void
@@ -3086,13 +3132,14 @@
else
gcc_unreachable ();
- if (loop->inner && loop_in_scop_p (loop->inner, scop))
+ if (loop->inner && loop_in_sese_p (loop->inner, SCOP_REGION (scop)))
build_loop_iteration_domains (scop, loop->inner, cstr, nb_outer_loops + 1);
/* Only go to the next loops, if we are not at the outermost layer. These
have to be handled seperately, as we can be sure, that the chain at this
layer will be connected. */
- if (nb_outer_loops != 0 && loop->next && loop_in_scop_p (loop->next, scop))
+ if (nb_outer_loops != 0 && loop->next && loop_in_sese_p (loop->next,
+ SCOP_REGION (scop)))
build_loop_iteration_domains (scop, loop->next, outer_cstr, nb_outer_loops);
for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
@@ -3368,7 +3415,7 @@
VEC (basic_block, heap) *dom;
/* Make sure we are in the SCoP. */
- if (!bb_in_scop_p (bb, scop))
+ if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
return true;
if (bb_contains_non_iv_scalar_phi_nodes (bb))
@@ -3562,7 +3609,7 @@
/* Build cloog loop for all loops, that are in the uppermost loop layer of
this SCoP. */
for (i = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), i, loop); i++)
- if (!loop_in_scop_p (loop_outer (loop), scop))
+ if (!loop_in_sese_p (loop_outer (loop), SCOP_REGION (scop)))
{
/* The outermost constraints is a matrix that has:
-first column: eq/ineq boolean
@@ -4138,7 +4185,7 @@
else
{
if (gimple_code (def_stmt) != GIMPLE_ASSIGN
- || !bb_in_scop_p (gimple_bb (def_stmt), scop))
+ || !bb_in_sese_p (gimple_bb (def_stmt), SCOP_REGION (scop)))
return get_new_name_from_old_name (map, op0);
var0 = gimple_assign_rhs1 (def_stmt);
@@ -5142,7 +5189,7 @@
basic_block def_bb = gimple_bb (def_stmt);
if (!def_bb
- || !bb_in_scop_p (def_bb, scop))
+ || !bb_in_sese_p (def_bb, SCOP_REGION (scop)))
return name;
if (TEST_BIT (visited, def_bb->index))
@@ -5396,7 +5443,6 @@
{
basic_block bb = SESE_EXIT (SCOP_REGION (scop))->dest;
SESE_EXIT (SCOP_REGION (scop)) = split_block_after_labels (bb);
- bitmap_set_bit (SCOP_BBS_B (scop), bb->index);
pointer_set_insert (SESE_REGION_BBS (SCOP_REGION (scop)), bb);
}
@@ -6031,7 +6077,7 @@
continue;
for (j = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), j, loop); j++)
- if (!loop_in_scop_p (loop_outer (loop), scop))
+ if (!loop_in_sese_p (loop_outer (loop), SCOP_REGION (scop)))
{
sd_region open_scop;
open_scop.entry = loop->header;
Index: gcc/graphite.h
===================================================================
--- gcc/graphite.h (revision 143917)
+++ gcc/graphite.h (working copy)
@@ -23,6 +23,8 @@
#include "tree-data-ref.h"
+int ref_nb_loops (data_reference_p);
+
typedef struct graphite_bb *graphite_bb_p;
DEF_VEC_P(graphite_bb_p);
DEF_VEC_ALLOC_P (graphite_bb_p, heap);
@@ -216,6 +218,8 @@
return GBB_BB (gbb)->loop_father;
}
+int nb_loops_around_gb (graphite_bb_p);
+
/* Calculate the number of loops around GB in the current SCOP. Only
works if GBB_DOMAIN is built. */
@@ -313,13 +317,11 @@
/* A SCOP is defined as a SESE region. */
sese region;
- /* All the basic blocks in this scop. They have extra information
- attached to them, in the graphite_bb structure. */
+ /* All the basic blocks in this scop that contain memory references
+ and that will be represented as statements in the polyhedral
+ representation. */
VEC (graphite_bb_p, heap) *bbs;
- /* Set for a basic block index when it belongs to this SCOP. */
- bitmap bbs_b;
-
lambda_vector static_schedule;
/* Parameters used within the SCOP. */
@@ -349,7 +351,6 @@
};
#define SCOP_BBS(S) S->bbs
-#define SCOP_BBS_B(S) S->bbs_b
#define SCOP_REGION(S) S->region
/* SCOP_ENTRY bb dominates all the bbs of the scop. SCOP_EXIT bb
post-dominates all the bbs of the scop. SCOP_EXIT potentially
@@ -572,59 +573,4 @@
return depth;
}
-/* Static inline function prototypes. */
-
-static inline unsigned scop_nb_params (scop_p scop);
-
-/* Returns true when BB is in SCOP. */
-
-static inline bool
-bb_in_scop_p (basic_block bb, scop_p scop)
-{
- return bitmap_bit_p (SCOP_BBS_B (scop), bb->index);
-}
-
-/* Returns true when LOOP is in SCOP. */
-
-static inline bool
-loop_in_scop_p (struct loop *loop, scop_p scop)
-{
- return (bb_in_scop_p (loop->header, scop)
- && bb_in_scop_p (loop->latch, scop));
-}
-
-/* Calculate the number of loops around LOOP in the SCOP. */
-
-static inline int
-nb_loops_around_loop_in_scop (struct loop *l, scop_p scop)
-{
- int d = 0;
-
- for (; loop_in_scop_p (l, scop); d++, l = loop_outer (l));
-
- return d;
-}
-
-/* Calculate the number of loops around GB in the current SCOP. */
-
-static inline int
-nb_loops_around_gb (graphite_bb_p gb)
-{
- return nb_loops_around_loop_in_scop (gbb_loop (gb), GBB_SCOP (gb));
-}
-
-/* Returns the dimensionality of an enclosing loop iteration domain
- with respect to enclosing SCoP for a given data reference REF. The
- returned dimensionality is homogeneous (depth of loop nest + number
- of SCoP parameters + const). */
-
-static inline int
-ref_nb_loops (data_reference_p ref)
-{
- loop_p loop = loop_containing_stmt (DR_STMT (ref));
- scop_p scop = DR_SCOP (ref);
-
- return nb_loops_around_loop_in_scop (loop, scop) + scop_nb_params (scop) + 2;
-}
-
#endif /* GCC_GRAPHITE_H */