This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[graphite] instancewise dependence analysis functions and structures
- From: "Konrad Trifunovic" <konrad dot trifunovic at gmail dot com>
- To: gcc-patches at gcc dot gnu dot org
- Cc: sebpop at gmail dot com
- Date: Mon, 11 Feb 2008 18:42:52 +0100
- Subject: [graphite] instancewise dependence analysis functions and structures
Hi all,
I send a patch that contains functions and data structures used for
instancewise dependence analysis. Now the is inactive (functions are
not called).
My goal is just to synchronize with graphite branch, I will carry on
with further development.
Best regards,
Konrad
2008-02-10 Konrad Trifunovic <konrad.trifunovic@inria.fr>
* tree-data-ref.c : make dr_may_alias_p and create_rdg_vertices
function external, so they are visible in other places (graphite.c)
* graphite.c, graphite.h : add function and data structures for
instancewise (polyhedral) data dependence analysis
Index: tree-data-ref.c
===================================================================
--- tree-data-ref.c (revision 132238)
+++ tree-data-ref.c (working copy)
@@ -1207,7 +1207,7 @@ disjoint_objects_p (tree a, tree b)
/* Returns false if we can prove that data references A and B do not alias,
true otherwise. */
-static bool
+bool
dr_may_alias_p (const struct data_reference *a, const struct data_reference *b)
{
const_tree addr_a = DR_BASE_ADDRESS (a);
@@ -4611,7 +4611,7 @@ create_rdg_edges (struct graph *rdg, VEC
/* Build the vertices of the reduced dependence graph RDG. */
-static void
+void
create_rdg_vertices (struct graph *rdg, VEC (tree, heap) *stmts)
{
int i, j;
Index: tree-data-ref.h
===================================================================
--- tree-data-ref.h (revision 132238)
+++ tree-data-ref.h (working copy)
@@ -370,6 +370,13 @@ bool find_loop_nest (struct loop *, VEC
void compute_all_dependences (VEC (data_reference_p, heap) *,
VEC (ddr_p, heap) **, VEC (loop_p, heap) *, bool);
+extern bool find_data_references_in_stmt (struct loop *nest, tree stmt,
+ VEC (data_reference_p, heap) **datarefs);
+extern void create_rdg_vertices (struct graph *rdg, VEC (tree, heap) *stmts);
+
+extern bool dr_may_alias_p (const struct data_reference *a, const struct data_reference *b);
+
+
/* Return true when the DDR contains two data references that have the
same access functions. */
Index: graphite.c
===================================================================
--- graphite.c (revision 132238)
+++ graphite.c (working copy)
@@ -51,6 +51,41 @@ VEC (scop_p, heap) *current_scops;
static bool basic_block_simple_for_scop_p (basic_block);
static CloogMatrix *schedule_to_scattering (graphite_bb_p);
+static inline struct loop_to_cloog_loop_str *
+new_loop_to_cloog_loop_str (unsigned int loop_num,
+ unsigned int loop_position,
+ CloogLoop *cloog_loop)
+{
+ struct loop_to_cloog_loop_str *result;
+ result = xcalloc (1, sizeof (struct loop_to_cloog_loop_str));
+ result->loop_num = loop_num;
+ result->cloog_loop = cloog_loop;
+ result->loop_position = loop_position;
+
+ return result;
+}
+
+static hashval_t
+hash_loop_to_cloog_loop (const void *elt)
+{
+ return ((const struct loop_to_cloog_loop_str *) elt)->loop_num;
+}
+
+static int
+eq_loop_to_cloog_loop (const void *el1, const void *el2)
+{
+ const struct loop_to_cloog_loop_str *elt1 = (const struct loop_to_cloog_loop_str *) el1;
+ const struct loop_to_cloog_loop_str *elt2 = (const struct loop_to_cloog_loop_str *) el2;
+
+ return elt1->loop_num == elt2->loop_num;
+}
+
+static void
+del_loop_to_cloog_loop (void *e)
+{
+ free (e);
+}
+
/* Print the schedules from SCHED. */
void
@@ -514,7 +549,7 @@ new_scop (basic_block bb)
SCOP_PARAMS (scop) = VEC_alloc (tree, heap, 3);
SCOP_PROG (scop) = cloog_program_malloc ();
SCOP_PROG (scop)->names = cloog_names_malloc ();
-
+ SCOP_LOOP2CLOOG_LOOP (scop) = htab_create (10, hash_loop_to_cloog_loop, eq_loop_to_cloog_loop, del_loop_to_cloog_loop);
return scop;
}
@@ -1085,6 +1120,8 @@ setup_cloog_loop (scop_p scop, struct lo
unsigned i, j, row;
CloogStatement *statement;
CloogMatrix *cstr;
+ struct loop_to_cloog_loop_str tmp;
+ PTR *slot;
CloogLoop *res = cloog_loop_malloc ();
unsigned nb_rows = outer_cstr->NbRows + 1;
@@ -1174,6 +1211,11 @@ setup_cloog_loop (scop_p scop, struct lo
res->domain = cloog_domain_matrix2domain (cstr);
+ tmp.loop_num = loop->num;
+ slot = htab_find_slot (SCOP_LOOP2CLOOG_LOOP(scop), &tmp, INSERT);
+ if (!*slot)
+ *slot = new_loop_to_cloog_loop_str (loop->num, loop_col - 1, res);
+
/* Now set up the other loop constructs. CLooG is expecting to see
a list of loops chained with the res->next pointer. Don't use
res->inner for representing inner loops: this information is
@@ -1463,6 +1505,420 @@ gloog (scop_p scop ATTRIBUTE_UNUSED, str
/* Perform a set of linear transforms on LOOPS. */
+
+
+static CloogMatrix *
+initialize_dependence_polyhedron (scop_p scop,
+ struct data_reference *a,
+ struct data_reference *b)
+{
+ unsigned nb_cols, nb_rows, nb_loops, nb_params;
+ struct loop_to_cloog_loop_str tmp, *slot1, *slot2;
+ unsigned row, col;
+ CloogMatrix *domain1, *domain2;
+ CloogMatrix *dep_constraints;
+ lambda_vector access_row_vector;
+ struct loop *containing_loop;
+ containing_loop = loop_containing_stmt (DR_STMT (a));
+ tmp.loop_num = containing_loop->num;
+ slot1 = (struct loop_to_cloog_loop_str *) htab_find (SCOP_LOOP2CLOOG_LOOP(scop), &tmp);
+
+ containing_loop = loop_containing_stmt (DR_STMT (b));
+ tmp.loop_num = containing_loop->num;
+ slot2 = (struct loop_to_cloog_loop_str *) htab_find (SCOP_LOOP2CLOOG_LOOP(scop), &tmp);
+ /*TODO:konrad insert checking for possible null values of slot1 and
+ * slot2 */
+
+ domain1 = cloog_domain_domain2matrix (slot1->cloog_loop->domain);
+ domain2 = cloog_domain_domain2matrix (slot2->cloog_loop->domain);
+
+ /* 2 = one for eq/neq column, one for constant term */
+ nb_cols = scop_nb_loops (scop) * 2 + scop_nb_params (scop) + 2;
+ nb_rows = domain1->NbRows + domain2->NbRows + DR_NUM_DIMENSIONS (a);
+ nb_loops = scop_nb_loops (scop);
+ nb_params = scop_nb_params (scop);
+ dep_constraints = cloog_matrix_alloc (nb_rows, nb_cols);
+
+ /* initialize dependence polyhedron. TODO:konrad do we need it */
+ for (row = 0; row < dep_constraints->NbRows ; row++)
+ {
+ for (col = 0; col < dep_constraints->NbColumns; col++)
+ {
+ value_init (dep_constraints->p[row][col]);
+ }
+ }
+
+ /*copy the iterator part of Ds (domain of S statement), with eq/neq column */
+ for (row = 0; row < domain1->NbRows; row++)
+ {
+ for (col = 0; col <= nb_loops; col++)
+ {
+ value_assign (dep_constraints->p[row][col], domain1->p[row][col]);
+ }
+ }
+
+ /* copy the parametric and constant part of Ds */
+
+ for (row = 0; row < domain1->NbRows; row++)
+ {
+ value_assign (dep_constraints->p[row][nb_cols-1], domain1->p[row][domain1->NbColumns - 1]);
+ for (col = 1; col <= nb_params; col++)
+ {
+ value_assign (dep_constraints->p[row][col + 2 * scop_nb_loops (scop)],
+ domain1->p[row][col + scop_nb_loops (scop)]);
+ }
+ }
+
+ /*copy the iterator part of Dt (domain of T statement), without eq/neq column */
+ for (row = 0; row < domain2->NbRows; row++)
+ {
+ for (col = 1; col <= nb_loops; col++)
+ {
+ value_assign (dep_constraints->p[row + domain1->NbRows][col + scop_nb_loops (scop)],
+ domain2->p[row][col]);
+ }
+ }
+
+
+ /*copy the eq/neq column of Dt to dependence polyhedron*/
+
+ for (row = 0; row < domain2->NbRows; row++)
+ {
+ value_assign (dep_constraints->p[row + domain1->NbRows][0], domain1->p[row][0]);
+ }
+
+ for (row = 0; row < domain2->NbRows; row++)
+ {
+ value_assign (dep_constraints->p[row + domain1->NbRows][nb_cols-1], domain1->p[row][domain2->NbColumns - 1]);
+ for (col = 1; col <= nb_params; col++)
+ {
+ value_assign (dep_constraints->p[row + domain1->NbRows][col + 2 * scop_nb_loops (scop)],
+ domain2->p[row][col + scop_nb_loops (scop)]);
+ }
+ }
+
+ /* copy Ds access matrix */
+
+ for (row = 0; VEC_iterate (lambda_vector, DR_ACCESS_MATRIX (a), row, access_row_vector); row++)
+ {
+ for (col = 0; col < nb_loops; col++)
+ {
+ value_set_si (dep_constraints->p[row + domain1->NbRows + domain2->NbRows][col + 1], access_row_vector[col]);
+ }
+
+ value_set_si (dep_constraints->p[row + domain1->NbRows + domain2->NbRows][nb_cols-1],
+ access_row_vector[scop_dim_domain (scop) - 1]);
+ //TODO:konrad do not forget about parametric part
+ }
+
+ /* copy -Dt access matrix */
+
+ for (row = 0; VEC_iterate (lambda_vector, DR_ACCESS_MATRIX (b), row, access_row_vector); row++)
+ {
+ for (col = 0; col < nb_loops; col++)
+ {
+ value_set_si (dep_constraints->p[row + domain1->NbRows + domain2->NbRows][scop_nb_loops (scop) + col + 1],
+ -access_row_vector[col]);
+ }
+
+ value_sub_int (dep_constraints->p[row + domain1->NbRows + domain2->NbRows][nb_cols-1],
+ dep_constraints->p[row + domain1->NbRows + domain2->NbRows][nb_cols-1],
+ access_row_vector[scop_dim_domain (scop) - 1]);
+ }
+
+ return dep_constraints;
+}
+
+static int
+find_vertex_for_stmt (const struct graph *rdg, const_tree stmt)
+{
+ int i;
+
+ for (i = 0; i < rdg->n_vertices; i++)
+ if (RDGV_STMT (&(rdg->vertices[i])) == stmt)
+ return i;
+
+ gcc_unreachable ();
+ return 0;
+}
+
+static struct data_dependence_polyhedron *
+initialize_data_dependence_polyhedron (bool loop_carried,
+ CloogDomain *domain,
+ unsigned level,
+ struct data_reference *a,
+ struct data_reference *b)
+{
+ struct data_dependence_polyhedron *res;
+ res = XNEW (struct data_dependence_polyhedron);
+ res -> a = a;
+ res -> b = b;
+ res -> loop_carried = loop_carried;
+ res -> level = level;
+ if (loop_carried)
+ {
+ res -> polyhedron = domain;
+ }
+ else
+ {
+ res -> polyhedron = NULL;
+ }
+ return res;
+}
+
+static bool
+is_empty_polyhedron (CloogDomain *domain)
+{
+ Polyhedron *polyhedron;
+ unsigned i, last_column, last_row;
+ polyhedron = domain->polyhedron;
+ last_column = polyhedron->Dimension + 2;
+ last_row = polyhedron->NbConstraints - 1;
+
+ for (i = 1; i < last_column - 1; i++)
+ {
+ if (!value_zero_p (polyhedron->Constraint[last_row][i]))
+ {
+ return false;
+ }
+ }
+
+ return !value_zero_p (polyhedron->Constraint[last_row][last_column - 1]);
+}
+
+/* return true if statement a (contained in bb gb_a)
+ precedes statement b (contained in bb gb_b). The decision
+ is based on static schedule of bb's and(or) relative position
+ of statements.
+*/
+static bool
+statement_precedes_p (scop_p scop,
+ graphite_bb_p gb_a,
+ tree a,
+ graphite_bb_p gb_b,
+ tree b,
+ unsigned p)
+{
+ block_stmt_iterator bsi;
+ bool statm_a_found, statm_b_found;
+ struct loop_to_cloog_loop_str tmp, *slot;
+
+ if (GBB_STATIC_SCHEDULE (gb_a)[p - 1] < GBB_STATIC_SCHEDULE (gb_b)[p - 1])
+ {
+ return true;
+ }
+ else if (GBB_STATIC_SCHEDULE (gb_a)[p - 1] == GBB_STATIC_SCHEDULE (gb_b)[p - 1])
+ {
+ statm_a_found = false;
+ statm_b_found = false;
+ /* TODO:konrad You can use stmt_ann->uid for a slight speedup */
+ /* if static schedules are the same -> gb1 = gb2 */
+/* GBB_BB (gb_a)->loop_father;*/
+ tmp.loop_num = GBB_BB (gb_a)->loop_father->num;
+ slot = (struct loop_to_cloog_loop_str *) htab_find (SCOP_LOOP2CLOOG_LOOP(scop), &tmp);
+ if (slot->loop_position == p - 1)
+ {
+ for (bsi = bsi_start (GBB_BB (gb_a)); !bsi_end_p (bsi); bsi_next (&bsi))
+ {
+ if (bsi_stmt (bsi) == a)
+ statm_a_found = true;
+
+ if (statm_a_found && bsi_stmt (bsi) == b)
+ return true;
+ }
+ }
+ }
+ return false;
+}
+
+static struct graph *
+build_rdg_all_levels (scop_p scop)
+{
+ unsigned i, j, row, nb_loops;
+ unsigned i1, j1;
+ int va, vb;
+ signed p;
+ graphite_bb_p gb1, gb2;
+ struct graph * rdg = NULL;
+ struct data_reference *a, *b;
+ CloogMatrix *dep_constraints, *temp_matrix;
+ CloogDomain *simplified;
+ block_stmt_iterator bsi;
+ struct graph_edge *e;
+
+ /* VEC (data_reference_p, heap) *datarefs;*/
+ /* all the statements that are involved in dependences are stored in this
+ vector */
+ VEC (tree, heap) *stmts = VEC_alloc (tree, heap, 10);
+ VEC (ddp_p, heap) *ddps = VEC_alloc (ddp_p, heap, 10);
+ ddp_p ddp;
+/* datarefs = VEC_alloc (data_reference_p, heap, 2);*/
+ nb_loops = scop_nb_loops (scop);
+ for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb1); i++)
+ {
+
+ for (bsi = bsi_start (GBB_BB (gb1)); !bsi_end_p (bsi); bsi_next (&bsi))
+ {
+ VEC_safe_push (tree, heap, stmts, bsi_stmt (bsi));
+ }
+
+ for (i1 = 0; VEC_iterate (data_reference_p, GBB_DATA_REFS (gb1), i1, a); i1++)
+ {
+ for (j = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), j, gb2); j++)
+ {
+ for (j1 = 0; VEC_iterate (data_reference_p, GBB_DATA_REFS (gb2), j1, b); j1++)
+ {
+ if ((!DR_IS_READ (a) || !DR_IS_READ (b)) && dr_may_alias_p (a,b)
+ && operand_equal_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b), 0))
+ {
+ /* TODO:konrad the previous check might be too restrictive*/
+ for (i = 1; i <= 2 * nb_loops + 1; i++)
+ {
+ /* S - gb1 */
+ /* T - gb2 */
+ /* S -> T, T - S >=1 */
+ p = (i / 2) * (1 - (i % 2)*2); /* p is alternating sequence 0,1,-1,2,-2,... */
+ if (p == 0)
+ {
+ dep_constraints = initialize_dependence_polyhedron (scop, a, b);
+ temp_matrix = AddANullRow (dep_constraints);
+ }
+ else if (p > 0)
+ {
+ /* assert B0, B1, ..., Bp-1 satisfy the equality */
+
+ temp_matrix = AddANullRow (temp_matrix);
+
+ row = temp_matrix->NbRows - 1;
+
+ value_set_si (temp_matrix->p[row][0], 1);
+ value_set_si (temp_matrix->p[row][p], -GBB_ALPHA (gb1)[p - 1]);
+ value_set_si (temp_matrix->p[row][p + scop_nb_loops (scop)], GBB_ALPHA (gb2)[p - 1]);
+ value_set_si (temp_matrix->p[row][temp_matrix->NbColumns - 1], -1);
+
+ simplified = cloog_domain_matrix2domain (temp_matrix);
+ temp_matrix = RemoveRow (temp_matrix, temp_matrix->NbRows - 1);
+
+ if (!is_empty_polyhedron (simplified))
+ {
+ ddp = initialize_data_dependence_polyhedron (true, simplified, p, a, b);
+ VEC_safe_push (ddp_p, heap, ddps, ddp);
+ break;
+ }
+ }
+ else if (p < 0)
+ {
+
+ /*TODO:konrad do not forget about memory leaks, temp_matrix is
+ new matrix ! */
+ temp_matrix = AddANullRow (temp_matrix);
+
+ row = temp_matrix->NbRows - 1;
+ value_set_si (temp_matrix->p[row][-p], -GBB_ALPHA (gb1)[-p - 1]);
+ value_set_si (temp_matrix->p[row][-p + scop_nb_loops (scop)], GBB_ALPHA (gb2)[-p - 1]);
+
+ simplified = cloog_domain_matrix2domain (temp_matrix);
+
+ if (statement_precedes_p (scop, gb1, DR_STMT (a), gb2, DR_STMT (b), -p))
+ {
+ ddp = initialize_data_dependence_polyhedron (false, simplified, -p, a, b);
+ VEC_safe_push (ddp_p, heap, ddps, ddp);
+ break;
+ }
+ }
+ }
+ }
+ }
+ }
+ }
+ }
+ rdg = new_graph (VEC_length (tree, stmts));
+ create_rdg_vertices (rdg, stmts);
+
+ for (i = 0; VEC_iterate (ddp_p, ddps, i, ddp); i++)
+ {
+ va = find_vertex_for_stmt (rdg, DR_STMT (ddp->a));
+ vb = find_vertex_for_stmt (rdg, DR_STMT (ddp->b));
+ e = add_edge (rdg, va, vb);
+ e->data = ddp;
+ }
+
+ VEC_free (tree, heap, stmts);
+ return rdg;
+}
+
+static void
+build_scop_alpha (scop_p scop)
+{
+ unsigned i, j;
+ graphite_bb_p gb;
+ unsigned nb = scop_nb_loops (scop);
+ struct loop *ploop, *loop;
+ struct loop_to_cloog_loop_str tmp, *slot;
+
+ for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
+ {
+ GBB_ALPHA (gb) = lambda_vector_new (nb);
+ loop = GBB_BB (gb) -> loop_father;
+ for (j = 0; VEC_iterate (loop_p, loop->superloops, j, ploop); j++)
+ {
+ if (loop_in_scop_p (ploop, scop))
+ {
+ tmp.loop_num = ploop->num;
+ slot = (struct loop_to_cloog_loop_str *) htab_find (SCOP_LOOP2CLOOG_LOOP(scop), &tmp);
+ GBB_ALPHA (gb) [slot->loop_position] = 1;
+ }
+ }
+ if (loop_in_scop_p (loop, scop))
+ {
+ tmp.loop_num = loop->num;
+ slot = (struct loop_to_cloog_loop_str *) htab_find (SCOP_LOOP2CLOOG_LOOP(scop), &tmp);
+ GBB_ALPHA (gb) [slot->loop_position] = 1;
+ }
+ }
+}
+
+static void
+dump_dependence_graph (FILE *f, struct graph *g)
+{
+ int i;
+ struct graph_edge *e;
+
+ for (i = 0; i < g->n_vertices; i++)
+ {
+ if (!g->vertices[i].pred
+ && !g->vertices[i].succ)
+ continue;
+
+ fprintf (f, "vertex: %d (%d)\nStatement: ", i, g->vertices[i].component);
+ print_generic_expr (f, RDGV_STMT (&(g->vertices[i])), 0);
+ fprintf (f, "\n-----------------\n");
+
+ for (e = g->vertices[i].pred; e; e = e->pred_next)
+ {
+ fprintf (f, "edge %d -> %d\n", e->src, i);
+ struct data_dependence_polyhedron *ddp = RDGE_DDP (e);
+ if (ddp->polyhedron != NULL)
+ {
+ cloog_domain_print (f, ddp->polyhedron);
+ }
+ fprintf (f, "-----------------\n");
+ }
+
+ for (e = g->vertices[i].succ; e; e = e->succ_next)
+ {
+ fprintf (f, "edge %d -> %d\n", i, e->dest);
+ struct data_dependence_polyhedron *ddp = RDGE_DDP (e);
+ if (ddp->polyhedron != NULL)
+ {
+ cloog_domain_print (f, ddp->polyhedron);
+ }
+ fprintf (f, "-----------------\n");
+ }
+ fprintf (f, "\n");
+ }
+}
+
void
graphite_transform_loops (void)
{
Index: graphite.h
===================================================================
--- graphite.h (revision 132238)
+++ graphite.h (working copy)
@@ -34,6 +34,7 @@ struct graphite_bb
scop_p scop;
lambda_vector static_schedule;
+ lambda_vector compressed_alpha_matrix;
VEC (data_reference_p, heap) *data_refs;
};
@@ -41,6 +42,7 @@ struct graphite_bb
#define GBB_SCOP(GBB) GBB->scop
#define GBB_STATIC_SCHEDULE(GBB) GBB->static_schedule
#define GBB_DATA_REFS(GBB) GBB->data_refs
+#define GBB_ALPHA(GBB) GBB->compressed_alpha_matrix
/* Return the loop that contains the basic block GBB. */
@@ -76,6 +78,8 @@ struct scop
/* Loops contained in the scop. */
VEC (loop_p, heap) *loop_nest;
+ htab_t loop2cloog_loop;
+
/* Cloog representation of this scop. */
CloogProgram *program;
};
@@ -88,6 +92,7 @@ struct scop
#define SCOP_LOOP_NEST(S) S->loop_nest
#define SCOP_PARAMS(S) S->params
#define SCOP_PROG(S) S->program
+#define SCOP_LOOP2CLOOG_LOOP(S) S->loop2cloog_loop
extern void debug_scop (scop_p, int);
extern void debug_scops (int);
@@ -143,3 +148,28 @@ scop_loop_index (scop_p scop, struct loo
return -1;
}
+
+struct data_dependence_polyhedron
+{
+ struct data_reference *a;
+ struct data_reference *b;
+ bool reversed_p;
+ bool loop_carried; /*TODO:konrad get rid of this, make level signed */
+ signed level;
+ CloogDomain *polyhedron;
+};
+
+#define RDGE_DDP(E) ((struct data_dependence_polyhedron*) ((E)->data))
+
+typedef struct data_dependence_polyhedron *ddp_p;
+
+DEF_VEC_P(ddp_p);
+DEF_VEC_ALLOC_P(ddp_p,heap);
+
+struct loop_to_cloog_loop_str
+{
+ unsigned int loop_num;
+ unsigned int loop_position; /* the column that represents this loop */
+ CloogLoop *cloog_loop;
+};
+