This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [graphite] instancewise dependence analysis functions and structures
- From: Jack Howarth <howarth at bromo dot msbb dot uc dot edu>
- To: Konrad Trifunovic <konrad dot trifunovic at gmail dot com>
- Cc: gcc-patches at gcc dot gnu dot org, Sebastian Pop <sebpop at gmail dot com>, Sebastian Pop <sebastian dot pop at amd dot com>, Razya Ladelsky <RAZYA at il dot ibm dot com>, Dorit Nuzman <DORIT at il dot ibm dot com>
- Date: Wed, 20 Aug 2008 22:15:27 -0400
- Subject: Re: [graphite] instancewise dependence analysis functions and structures
- References: <bd2d0a90808191136g738656dn7d5d302bb53c2c52@mail.gmail.com>
On Tue, Aug 19, 2008 at 09:36:21PM +0300, Konrad Trifunovic wrote:
> Hi,
>
> this is a patch that brings back data dependence analysis code into Graphite.
> The code is factored into new files: graphite-data-ref.h and
> graphite-data-ref.c.
> Also some minor changes in graphite.c and graphite.h.
> In Makefile.in added a target for graphite-data-ref.o.
>
> PS
>
> Sebastian, can You check if I still have a commit access to graphite
> branch using my trifunovic@gcc.gnu.org account?
> regards,
> Konrad
> 2008-08-19 Konrad Trifunovic <konrad.trifunovic@inria.fr>
>
> * graphite-data-ref.c: New.
> * graphite-data-ref.h: New.
> * graphite.c (print_scop): Dump also a dependence graph.
> (bb_in_scop_p): Moved to header file.
> (loop_in_scop_p): Moved to header file.
> (nb_loops_around_gb): Moved to header file.
> (new_scop): Initialize SCOP_DEP_GRAPH with NULL.
> (build_scop_dynamic_schedules): call nb_loops_around_gb instead
> of loop_iteration_vector_dim.
> (build_access_matrix_with_af): Fixed column numbering.
> (graphite_transform_loops): Enable calling of
> build_scop_dynamic_schedules.
> * graphite.h: Added ifndef/define guards against multiple inclusion.
> (struct scop): Added dep_graph field.
> (SCOP_DEP_GRAPH): Defined.
> (ref_nb_loops): Fixed and moved to other position.
> (bb_in_scop_p): Moved to header file.
> (loop_in_scop_p): Moved to header file.
> (nb_loops_around_gb): Moved to header file.
> (nb_loops_around_loop_in_scop): New.
> * Makefile.in (graphite-data-ref.o): New target.
>
> Index: graphite-data-ref.c
> ===================================================================
> --- graphite-data-ref.c (revision 0)
> +++ graphite-data-ref.c (revision 0)
> @@ -0,0 +1,438 @@
> +/* Gimple Represented as Polyhedra. Dependence analysis.
> + Copyright (C) 2006, 2007, 2008 Free Software Foundation, Inc.
> + Contributed by Sebastian Pop <sebastian.pop@inria.fr>.
> + Contributed by Konrad Trifunovic <konrad.trifunovic@inria.fr>.
> +
> +This file is part of GCC.
> +
> +GCC is free software; you can redistribute it and/or modify
> +it under the terms of the GNU General Public License as published by
> +the Free Software Foundation; either version 3, or (at your option)
> +any later version.
> +
> +GCC is distributed in the hope that it will be useful,
> +but WITHOUT ANY WARRANTY; without even the implied warranty of
> +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
> +GNU General Public License for more details.
> +
> +You should have received a copy of the GNU General Public License
> +along with GCC; see the file COPYING3. If not see
> +<http://www.gnu.org/licenses/>. */
> +
> +/* This pass converts GIMPLE to GRAPHITE, performs some loop
> + transformations and then converts the resulting representation back
> + to GIMPLE. */
> +
> +
> +#include "config.h"
> +#include "system.h"
> +#include "coretypes.h"
> +#include "tm.h"
> +#include "ggc.h"
> +#include "tree.h"
> +#include "rtl.h"
> +#include "basic-block.h"
> +#include "diagnostic.h"
> +#include "tree-flow.h"
> +#include "toplev.h"
> +#include "tree-dump.h"
> +#include "timevar.h"
> +#include "cfgloop.h"
> +#include "tree-chrec.h"
> +#include "tree-data-ref.h"
> +#include "tree-scalar-evolution.h"
> +#include "tree-pass.h"
> +#include "domwalk.h"
> +#include "pointer-set.h"
> +#include "gimple.h"
> +
> +
> +#ifdef HAVE_cloog
> +#include "cloog/cloog.h"
> +#include "graphite.h"
> +#include "graphite-data-ref.h"
> +
> +/*
> + * Add a row of zeros at the end of the matrix 'M' and return the new matrix
> + */
> +
> +static CloogMatrix *
> +graphite_add_a_null_row (CloogMatrix *M)
> +{
> + int i,j;
> + CloogMatrix *Result;
> +
> + Result = cloog_matrix_alloc (M->NbRows+1, M->NbColumns);
> + for (i = 0; i < M->NbRows; i++)
> + for (j = 0; j < M->NbColumns; j++)
> + value_assign (Result->p[i][j], M->p[i][j]);
> + for (j = 0; j < M->NbColumns; j++)
> + value_set_si (Result->p[i][j],0);
> + return Result;
> +}
> +
> +/* Returns a matrix representing the data dependence between memory
> + accesses A and B in the context of SCOP. */
> +
> +static CloogMatrix *
> +graphite_initialize_dependence_polyhedron (scop_p scop,
> + graphite_bb_p gb1, graphite_bb_p gb2,
> + struct data_reference *a,
> + struct data_reference *b)
> +{
> + int nb_cols, nb_rows, nb_params, nb_iter1, nb_iter2;
> + int row, col, offset;
> + CloogMatrix *domain1, *domain2;
> + CloogMatrix *dep_constraints;
> + lambda_vector access_row_vector;
> + Value value;
> +
> + domain1 = (GBB_DOMAIN (gb1));
> + domain2 = (GBB_DOMAIN (gb2));
> + /* Adding 2 columns: one for the eq/neq column, one for constant
> + term. */
> +
> + nb_params = scop_nb_params (scop);
> + nb_iter1 = domain1->NbColumns - 2 - nb_params;
> + nb_iter2 = domain2->NbColumns - 2 - nb_params;
> +
> + nb_cols = nb_iter1 + nb_iter2 + scop_nb_params (scop) + 2;
> + nb_rows = domain1->NbRows + domain2->NbRows + DR_NUM_DIMENSIONS (a)
> + + 2 * MIN (nb_iter1, nb_iter2);
> + dep_constraints = cloog_matrix_alloc (nb_rows, nb_cols);
> +
> + /* Initialize dependence polyhedron. TODO: 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_iter1; 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 + nb_iter1 + nb_iter2],
> + domain1->p[row][col + nb_iter1]);
> + }
> +
> + /* 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_iter2; col++)
> + value_assign (dep_constraints->p[row + domain1->NbRows][col + nb_iter2],
> + 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], domain2->p[row][0]);
> +
> + /* Copy the parametric and constant part of Dt. */
> + 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 + nb_iter1 + nb_iter2],
> + domain2->p[row][col + nb_iter2]);
> + }
> +
> + /* Copy Ds access matrix. */
> + for (row = 0; VEC_iterate (lambda_vector, AM_MATRIX (DR_ACCESS_MATRIX (a)),
> + row, access_row_vector); row++)
> + {
> + for (col = 1; col <= nb_iter1; col++)
> + value_set_si (dep_constraints->p[row + domain1->NbRows + domain2->NbRows][col],
> + access_row_vector[col]);
> +
> + for (col = 1; col <= nb_params; col++)
> + value_set_si (dep_constraints->p[row + domain1->NbRows + domain2->NbRows]
> + [col + nb_iter1 + nb_iter2],
> + access_row_vector[col + nb_iter1]);
> +
> + value_set_si (dep_constraints->p[row + domain1->NbRows + domain2->NbRows][nb_cols-1],
> + access_row_vector[ref_nb_loops (a) - 1]);
> + /* TODO: do not forget about parametric part. */
> + }
> + value_init (value);
> + /* Copy -Dt access matrix. */
> + offset = domain1->NbRows + domain2->NbRows;
> + for (row = 0; VEC_iterate (lambda_vector, AM_MATRIX (DR_ACCESS_MATRIX (b)),
> + row, access_row_vector); row++)
> + {
> + for (col = 1; col <= nb_iter2; col++)
> + value_set_si (dep_constraints->p[row + domain1->NbRows + domain2->NbRows][nb_iter1 + col],
> + -access_row_vector[col]);
> +
> + for (col = 1; col <= nb_params; col++)
> + {
> + value_set_si (value, access_row_vector[col + nb_iter2]);
> +
> + value_subtract (dep_constraints->p[row + offset][col + nb_iter1 + nb_iter2],
> + dep_constraints->p[row + offset][col + nb_iter1 + nb_iter2],
> + value);
> + }
> +
> + value_set_si (value, access_row_vector[ref_nb_loops (b) - 1]);
> + value_subtract (dep_constraints->p[row + domain1->NbRows + domain2->NbRows][nb_cols-1],
> + dep_constraints->p[row + domain1->NbRows + domain2->NbRows][nb_cols-1],
> + value);
> + }
> + value_clear (value);
> + return dep_constraints;
> +}
> +
> +/* Returns true when the last row of DOMAIN polyhedron is zero. */
> +
> +static bool
> +is_empty_polyhedron (CloogDomain *domain)
> +{
> + return cloog_domain_isempty (domain);
> +}
> +
> +/* Returns a new dependence polyhedron for data references A and B. */
> +
> +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;
> +}
> +
> +/* Returns true if statement A, contained in basic block GB_A,
> + precedes statement B, contained in basic block GB_B. The decision
> + is based on static schedule of basic blocks and relative position
> + of statements. */
> +
> +static bool
> +statement_precedes_p (graphite_bb_p gb_a,
> + gimple a,
> + graphite_bb_p gb_b,
> + gimple b,
> + unsigned p)
> +{
> + gimple_stmt_iterator gsi;
> + bool statm_a_found, statm_b_found;
> +
> + if (GBB_STATIC_SCHEDULE (gb_a)[p] < GBB_STATIC_SCHEDULE (gb_b)[p])
> + return true;
> + else if (GBB_STATIC_SCHEDULE (gb_a)[p] == GBB_STATIC_SCHEDULE (gb_b)[p])
> + {
> + statm_a_found = false;
> + statm_b_found = false;
> + for (gsi = gsi_start_bb (GBB_BB (gb_a)); !gsi_end_p (gsi); gsi_next (&gsi))
> + {
> + if (gsi_stmt (gsi) == a)
> + {
> + statm_a_found = true;
> + continue;
> + }
> +
> + if (statm_a_found && gsi_stmt (gsi) == b)
> + return true;
> + }
> + }
> +
> + return false;
> +}
> +
> +struct data_dependence_polyhedron *
> +graphite_test_dependence (scop_p scop, graphite_bb_p gb1, graphite_bb_p gb2,
> + struct data_reference *a, struct data_reference *b)
> +{
> + unsigned i, j, row, iter_vector_dim;
> + unsigned loop_a, loop_b;
> + signed p;
> + CloogMatrix *dep_constraints = NULL, *temp_matrix = NULL;
> + CloogDomain *simplified;
> +
> + loop_a = loop_containing_stmt (DR_STMT (a)) -> num;
> + loop_b = loop_containing_stmt (DR_STMT (b)) -> num;
> +
> +/* iter_vector_dim = MIN (loop_iteration_vector_dim (loop_a, scop),
> + loop_iteration_vector_dim (loop_b, scop));*/
> +
> + iter_vector_dim = MIN (nb_loops_around_gb (gb1),
> + nb_loops_around_gb (gb2));
> +
> + for (i = 1; i <= 2 * iter_vector_dim + 1; i++)
> + {
> + /* S - gb1 */
> + /* T - gb2 */
> + /* S -> T, T - S >=1 */
> + /* p is alternating sequence 0,1,-1,2,-2,... */
> + p = (i / 2) * (1 - (i % 2)*2);
> + if (p == 0)
> + dep_constraints = graphite_initialize_dependence_polyhedron (scop, gb1, gb2, a, b);
> + else if (p > 0)
> + {
> + /* assert B0, B1, ..., Bp-1 satisfy the equality */
> +
> + for (j = 0; j < iter_vector_dim; j++)
> + {
> + temp_matrix = graphite_add_a_null_row (dep_constraints);
> +
> + row = j + dep_constraints->NbRows - iter_vector_dim;
> + value_set_si (temp_matrix->p[row][0], 1); /* >= */
> + value_oppose (temp_matrix->p[row][p],
> + GBB_DYNAMIC_SCHEDULE (gb1)->p[j][p - 1]);
> + value_assign (temp_matrix->p[row]
> + [nb_loops_around_gb (gb1) + p],
> + GBB_DYNAMIC_SCHEDULE (gb2)->p[j][p - 1]);
> + value_set_si (temp_matrix->p[row][temp_matrix->NbColumns - 1], -1);
> +
> + simplified = cloog_domain_matrix2domain (temp_matrix);
> + if (is_empty_polyhedron (simplified))
> + {
> + value_assign (dep_constraints->p[j + dep_constraints->NbRows
> + - 2*iter_vector_dim][p],
> + GBB_DYNAMIC_SCHEDULE (gb1)->p[j][p - 1]);
> +
> + value_oppose (dep_constraints->p[j + dep_constraints->NbRows
> + - 2*iter_vector_dim]
> + [nb_loops_around_gb (gb1) + p],
> + GBB_DYNAMIC_SCHEDULE (gb2)->p[j][p - 1]);
> + }
> + else
> + return initialize_data_dependence_polyhedron (true, simplified,
> + p, a, b);
> + cloog_matrix_free (temp_matrix);
> + }
> + }
> + else if (p < 0)
> + {
> + temp_matrix = graphite_add_a_null_row (dep_constraints);
> + simplified = cloog_domain_matrix2domain (temp_matrix);
> +
> + if (!is_empty_polyhedron (simplified))
> + if (statement_precedes_p (gb1, DR_STMT (a), gb2, DR_STMT (b), -p))
> + {
> + return initialize_data_dependence_polyhedron (false, simplified, -p,
> + a, b);
> + /* VEC_safe_push (ddp_p, heap, ddps, ddp); */
> + break;
> + }
> +
> + cloog_matrix_free (temp_matrix);
> + }
> + }
> + cloog_matrix_free (dep_constraints);
> + return NULL;
> +}
> +
> +/* Returns the polyhedral data dependence graph for SCOP. */
> +
> +struct graph *
> +graphite_build_rdg_all_levels (scop_p scop)
> +{
> + unsigned i, j, i1, j1;
> + int va, vb;
> + graphite_bb_p gb1, gb2;
> + struct graph * rdg = NULL;
> + struct data_reference *a, *b;
> + gimple_stmt_iterator gsi;
> + struct graph_edge *e;
> +
> + /* All the statements that are involved in dependences are stored in
> + this vector. */
> + VEC (gimple, heap) *stmts = VEC_alloc (gimple, heap, 10);
> + VEC (ddp_p, heap) *dependences = VEC_alloc (ddp_p, heap, 10);
> + ddp_p dependence_polyhedron;
> + /* datarefs = VEC_alloc (data_reference_p, heap, 2);*/
> + for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb1); i++)
> + {
> + for (gsi = gsi_start_bb (GBB_BB (gb1)); !gsi_end_p (gsi); gsi_next (&gsi))
> + VEC_safe_push (gimple, heap, stmts, gsi_stmt (gsi));
> +
> + 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))
> + {
> + dependence_polyhedron = graphite_test_dependence (scop, gb1, gb2, a, b);
> + if (dependence_polyhedron != NULL)
> + VEC_safe_push (ddp_p, heap, dependences, dependence_polyhedron);
> + }
> + /* The previous check might be too restrictive. */
> + }
> +
> +
> + rdg = build_empty_rdg (VEC_length (gimple, stmts));
> + create_rdg_vertices (rdg, stmts);
> +
> + for (i = 0; VEC_iterate (ddp_p, dependences, i, dependence_polyhedron); i++)
> + {
> + va = rdg_vertex_for_stmt (rdg, DR_STMT (dependence_polyhedron->a));
> + vb = rdg_vertex_for_stmt (rdg, DR_STMT (dependence_polyhedron->b));
> + e = add_edge (rdg, va, vb);
> + e->data = dependence_polyhedron;
> + }
> +
> + VEC_free (gimple, heap, stmts);
> + return rdg;
> +}
> +
> +
> +/* Dumps the dependence graph G to file F. */
> +
> +void
> +graphite_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 \nStatement: ", i);
> + print_gimple_stmt (f, RDGV_STMT (&(g->vertices[i])), 0, 0);
> + fprintf (f, "\n-----------------\n");
> +
> + for (e = g->vertices[i].succ; e; e = e->succ_next)
> + {
> + struct data_dependence_polyhedron *ddp = RDGE_DDP (e);
> + fprintf (f, "edge %d -> %d\n", i, e->dest);
> + if (ddp->polyhedron != NULL)
> + {
> + cloog_domain_print (f, ddp->polyhedron);
> + }
> + else if (!ddp->loop_carried)
> + fprintf (f, "loop independent dependence at level %d\n", ddp->level);
> + fprintf (f, "--------\n");
> + }
> + fprintf (f, "\n");
> + }
> +}
> +
> +#else /* If Cloog is not available: #ifndef HAVE_cloog. */
> +
> +#endif
> Index: graphite-data-ref.h
> ===================================================================
> --- graphite-data-ref.h (revision 0)
> +++ graphite-data-ref.h (revision 0)
> @@ -0,0 +1,34 @@
> +/* Gimple Represented as Polyhedra. Dependence analysis.
> + Copyright (C) 2006, 2007, 2008 Free Software Foundation, Inc.
> + Contributed by Sebastian Pop <sebastian.pop@inria.fr>.
> + Contributed by Konrad Trifunovic <konrad.trifunovic@inria.fr>.
> +
> +This file is part of GCC.
> +
> +GCC is free software; you can redistribute it and/or modify
> +it under the terms of the GNU General Public License as published by
> +the Free Software Foundation; either version 3, or (at your option)
> +any later version.
> +
> +GCC is distributed in the hope that it will be useful,
> +but WITHOUT ANY WARRANTY; without even the implied warranty of
> +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
> +GNU General Public License for more details.
> +
> +You should have received a copy of the GNU General Public License
> +along with GCC; see the file COPYING3. If not see
> +<http://www.gnu.org/licenses/>. */
> +
> +/* This pass converts GIMPLE to GRAPHITE, performs some loop
> + transformations and then converts the resulting representation back
> + to GIMPLE. */
> +
> +#ifndef GCC_GRAPHITE_DATA_REF_H
> +#define GCC_GRAPHITE_DATA_REF_H
> +
> +/* Dumps the dependence graph G to file F. */
> +extern void graphite_dump_dependence_graph (FILE *f, struct graph *g);
> +
> +/* Returns the polyhedral data dependence graph for SCOP. */
> +extern struct graph *graphite_build_rdg_all_levels (scop_p scop);
> +#endif
> Index: graphite.c
> ===================================================================
> --- graphite.c (revision 139240)
> +++ graphite.c (working copy)
> @@ -47,6 +47,7 @@ along with GCC; see the file COPYING3.
> #ifdef HAVE_cloog
> #include "cloog/cloog.h"
> #include "graphite.h"
> +#include "graphite-data-ref.h"
>
> static VEC (scop_p, heap) *current_scops;
>
> @@ -688,6 +689,11 @@ print_scop (FILE *file, scop_p scop, int
> print_graphite_bb (file, gb, 0, verbosity);
> }
>
> + fprintf (file, " (data dependences: \n");
> + if (SCOP_DEP_GRAPH (scop))
> + graphite_dump_dependence_graph (dump_file, SCOP_DEP_GRAPH (scop));
> + fprintf (file, " )\n");
> +
> fprintf (file, ")\n");
> }
>
> @@ -719,13 +725,6 @@ debug_scops (int verbosity)
> print_scops (stderr, verbosity);
> }
>
> -/* Return true when BB is contained 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);
> -}
>
> /* Pretty print a scop in DOT format. */
>
> @@ -913,15 +912,6 @@ dot_all_scops (void)
> dot_all_scops_1 (stderr);
> }
>
> -/* 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));
> -}
> -
> /* Returns the outermost loop in SCOP that contains BB. */
>
> static struct loop *
> @@ -1113,6 +1103,7 @@ new_scop (basic_block entry)
> SCOP_LOOP2CLOOG_LOOP (scop) = htab_create (10, hash_loop_to_cloog_loop,
> eq_loop_to_cloog_loop,
> free);
> + SCOP_DEP_GRAPH (scop) = NULL;
> SCOP_LOOPS_MAPPING (scop) = create_loops_mapping ();
> return scop;
> }
> @@ -1792,7 +1783,7 @@ build_scop_dynamic_schedules (scop_p sco
> loop_num = GBB_BB (gb) -> loop_father -> num;
> if (loop_num != 0)
> {
> - dim = loop_iteration_vector_dim (loop_num, scop);
> + dim = nb_loops_around_gb (gb);
> GBB_DYNAMIC_SCHEDULE (gb) = cloog_matrix_alloc (dim, dim);
> for (row = 0; row < GBB_DYNAMIC_SCHEDULE (gb)->NbRows; row++)
> for (col = 0; col < GBB_DYNAMIC_SCHEDULE (gb)->NbColumns; col++)
> @@ -2298,20 +2289,6 @@ build_scop_context (scop_p scop)
> cloog_matrix_free (matrix);
> }
>
> -/* Calculate the number of loops around GB in the current SCOP. */
> -
> -static inline int
> -nb_loops_around_gb (graphite_bb_p gb)
> -{
> - scop_p scop = GBB_SCOP (gb);
> - struct loop *l = gbb_loop (gb);
> - int d = 0;
> -
> - for (; loop_in_scop_p (l, scop); d++, l = loop_outer (l));
> -
> - return d;
> -}
> -
> /* Returns a graphite_bb from BB. */
>
> static graphite_bb_p
> @@ -2903,6 +2880,7 @@ static bool
> build_access_matrix_with_af (tree access_fun, lambda_vector cy,
> scop_p scop, int ndim)
> {
> + int param_col;
> switch (TREE_CODE (access_fun))
> {
> case POLYNOMIAL_CHREC:
> @@ -2914,7 +2892,9 @@ build_access_matrix_with_af (tree access
> if (TREE_CODE (right) != INTEGER_CST)
> return false;
>
> - var = loop_iteration_vector_dim (CHREC_VARIABLE (access_fun), scop);
> + struct loop *outer_loop;
> + outer_loop = get_loop (CHREC_VARIABLE (access_fun));
> + var = nb_loops_around_loop_in_scop (outer_loop, scop);
> cy[var] = int_cst_value (right);
>
> switch (TREE_CODE (left))
> @@ -2929,14 +2909,30 @@ build_access_matrix_with_af (tree access
>
> default:
> /* TODO: also consider that access_fn can have parameters. */
> - return false;
> + return build_access_matrix_with_af (left, cy, scop, ndim);
> }
> }
> +
> + case PLUS_EXPR:
> + build_access_matrix_with_af (TREE_OPERAND (access_fun, 0), cy, scop, ndim);
> + build_access_matrix_with_af (TREE_OPERAND (access_fun, 1), cy, scop, ndim);
> + return true;
> +
> + case MINUS_EXPR:
> + build_access_matrix_with_af (TREE_OPERAND (access_fun, 0), cy, scop, ndim);
> + build_access_matrix_with_af (TREE_OPERAND (access_fun, 1), cy, scop, ndim);
> + return true;
> +
> case INTEGER_CST:
> /* Constant part. */
> cy[ndim - 1] = int_cst_value (access_fun);
> return true;
>
> + case SSA_NAME:
> + param_col = param_index (access_fun, scop);
> + cy [ndim - scop_nb_params (scop) + param_col - 1] = 1;
> + return true;
> +
> default:
> return false;
> }
> @@ -4775,9 +4771,7 @@ graphite_transform_loops (void)
> build_scop_conditions (scop);
> build_scop_data_accesses (scop);
>
> - /* XXX: Disabled, it does not work at the moment. */
> - if (0)
> - build_scop_dynamic_schedules (scop);
> + build_scop_dynamic_schedules (scop);
>
> if (dump_file && (dump_flags & TDF_DETAILS))
> {
> @@ -4785,6 +4779,8 @@ graphite_transform_loops (void)
> fprintf (dump_file, "\nnumber of data refs: %d\n", nbrefs);
> }
>
> + if (0)
> + SCOP_DEP_GRAPH (scop) = graphite_build_rdg_all_levels (scop);
> /* We only build new graphite code, if we applied a transformation. But
> call find_transform always to get more test coverage during
> developement. */
> Index: graphite.h
> ===================================================================
> --- graphite.h (revision 139240)
> +++ graphite.h (working copy)
> @@ -18,6 +18,9 @@ You should have received a copy of the G
> along with GCC; see the file COPYING3. If not see
> <http://www.gnu.org/licenses/>. */
>
> +#ifndef GCC_GRAPHITE_H
> +#define GCC_GRAPHITE_H
> +
> #include "tree-data-ref.h"
>
> typedef struct graphite_loop_node *graphite_loops_mapping;
> @@ -328,6 +331,9 @@ struct scop
> /* ??? It looks like a global mapping loop_id -> cloog_loop would work. */
> htab_t loop2cloog_loop;
>
> + /* Data dependence graph for this SCoP. */
> + struct graph *dep_graph;
> +
> /* Cloog representation of this scop. */
> CloogProgram *program;
> };
> @@ -344,6 +350,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_DEP_GRAPH(S) S->dep_graph
>
> extern void debug_scop (scop_p, int);
> extern void debug_scops (int);
> @@ -424,15 +431,6 @@ loop_domain_dim (unsigned int loop_num,
> return cloog_domain_dim (cloog_loop_domain (slot->cloog_loop)) + 2;
> }
>
> -/* Returns the dimensionality of an enclosing loop iteration domain
> - with respect to enclosing SCoP for a given data reference REF. */
> -
> -static inline int
> -ref_nb_loops (data_reference_p ref)
> -{
> - return loop_domain_dim (loop_containing_stmt (DR_STMT (ref))->num, DR_SCOP (ref));
> -}
> -
> /* Returns the dimensionality of a loop iteration vector in a loop
> iteration domain for a given loop (identified by LOOP_NUM) with
> respect to SCOP. */
> @@ -523,6 +521,66 @@ scop_gimple_loop_depth (scop_p scop, loo
> return depth;
> }
>
> +/* Static inline function prototypes. */
> +
> +static inline unsigned scop_nb_params (scop_p scop);
> +
> +/* Static inline function definitions. Graphite BB
> + manipulation functions. */
> +
> +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 GB in the current SCOP. */
> +
> +static inline int
> +nb_loops_around_gb (graphite_bb_p gb)
> +{
> + scop_p scop = GBB_SCOP (gb);
> + struct loop *l = gbb_loop (gb);
> + int d = 0;
> +
> + for (; loop_in_scop_p (l, scop); d++, l = loop_outer (l));
> +
> + return d;
> +}
> +
> +/* 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;
> +}
> +
> +/* 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)
> +{
> + return nb_loops_around_loop_in_scop (loop_containing_stmt (DR_STMT (ref)), DR_SCOP (ref))
> + + scop_nb_params (DR_SCOP (ref)) + 2;
> +}
> +
> /* Associate a POLYHEDRON dependence description to two data
> references A and B. */
> struct data_dependence_polyhedron
> @@ -530,7 +588,7 @@ 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 */
> + bool loop_carried;
> signed level;
> CloogDomain *polyhedron;
> };
> @@ -542,3 +600,4 @@ typedef struct data_dependence_polyhedro
> DEF_VEC_P(ddp_p);
> DEF_VEC_ALLOC_P(ddp_p,heap);
>
> +#endif /* GCC_GRAPHITE_H */
> Index: Makefile.in
> ===================================================================
> --- Makefile.in (revision 139240)
> +++ Makefile.in (working copy)
> @@ -1113,6 +1113,7 @@ OBJS-common = \
> graph.o \
> graphds.o \
> graphite.o \
> + graphite-data-ref.o \
> gtype-desc.o \
> haifa-sched.o \
> hooks.o \
> @@ -2350,6 +2351,10 @@ graphite.o: graphite.c $(CONFIG_H) $(SYS
> $(GGC_H) $(TREE_H) $(RTL_H) $(BASIC_BLOCK_H) $(DIAGNOSTIC_H) $(TOPLEV_H) \
> $(TREE_FLOW_H) $(TREE_DUMP_H) $(TIMEVAR_H) $(CFGLOOP_H) $(GIMPLE_H) domwalk.h \
> $(TREE_DATA_REF_H) $(SCEV_H) tree-pass.h tree-chrec.h graphite.h
> +graphite-data-ref.o: graphite-data-ref.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
> + $(GGC_H) $(TREE_H) $(RTL_H) $(BASIC_BLOCK_H) $(DIAGNOSTIC_H) $(TOPLEV_H) \
> + $(TREE_FLOW_H) $(TREE_DUMP_H) $(TIMEVAR_H) $(CFGLOOP_H) $(GIMPLE_H) domwalk.h \
> + $(TREE_DATA_REF_H) $(SCEV_H) tree-pass.h tree-chrec.h graphite.h graphite-data-ref.h
>
> tree-vect-analyze.o: tree-vect-analyze.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \
> $(TM_H) $(GGC_H) $(OPTABS_H) $(TREE_H) $(RECOG_H) $(BASIC_BLOCK_H) \
> $(DIAGNOSTIC_H) $(TREE_FLOW_H) $(TREE_DUMP_H) $(TIMEVAR_H) $(CFGLOOP_H) \
Does this patch build against the current graphite branch? When I try to apply it
to current gcc trunk with the graphite branch patches backported, I am getting a compilation
failure...
/sw/src/fink.build/gcc44-4.3.999-20080820/darwin_objdir/./prev-gcc/xgcc -B/sw/src/fink.build/gcc44-4.3.999-20080820/darwin_objdir/./prev-gcc/ -B/sw/lib/gcc4.4/i686-apple-darwin9/bin/ -c -g -O2 -fomit-frame-pointer -DIN_GCC -W -Wall -Wwrite-strings -Wstrict-prototypes -Wmissing-prototypes -Wcast-qual -Wold-style-definition -Wc++-compat -Wmissing-format-attribute -pedantic -Wno-long-long -Wno-variadic-macros -Wno-overlength-strings -Werror -fno-common -DHAVE_CONFIG_H -I. -I. -I../../gcc-4.4-20080820/gcc -I../../gcc-4.4-20080820/gcc/. -I../../gcc-4.4-20080820/gcc/../include -I../../gcc-4.4-20080820/gcc/../libcpp/include -I/sw/include -I../../gcc-4.4-20080820/gcc/../libdecnumber -I../../gcc-4.4-20080820/gcc/../libdecnumber/dpd -I../libdecnumber -I/sw/include -I/sw/include -DCLOOG_PPL_BACKEND -I/sw/include ../../gcc-4.4-20080820/gcc/graphite-data-ref.c -o graphite-data-ref.o
cc1: warnings being treated as errors
../../gcc-4.4-20080820/gcc/graphite-data-ref.c:261: error: no previous prototype for 'graphite_test_dependence'
FYI.
Jack