• Graphite
• Data_deps_todo

Tasks related to the data dependence analysis for Graphite:

• Cleanups
  • Remove all references to lambda_vector: replace with ppl_Linear_Expression_t.
  • Remove calls to struct access_matrix: replace with a static array of ppl_Linear_Expression_t.

• Represent the gcc data-refs in polyhedral representation

  • Add a structure poly_data_ref to keep track of the polyhedral representation of data accesses:

/* This will be in the first time before conversion to PCP.  */
typedef graphite_array data_reference_p;

/* This will be the new definition in PCP.  */
typedef graphite_array pcp_array;

struct poly_data_ref {
  int nb_subscripts;
  ppl_Linear_Expression_t *access_fn;
  graphite_array *array;
};

bool drs_may_not_conflict (graphite_array *a, graphite_array *b);

• Split out from data_reference_p the polyhedral representation
• Implement drs_may_not_conflict

• Build the data dependence relations in polyhedral form independent of GCC internal structures

  • Build the data dependence polyhedron "dp" for two poly_data_ref's "a" and "b":

if (drs_may_not_conflict (a, b))
  no dependence;

for (i = 0; i < a->nb_subscripts; i++)
  add_constraint_to_poly (dp, constraint (a.access_fn[i] == b.access_fn[i]));

add_iteration_domains (dp, a, b)

• Use polyhedral data dependence relations to determine the legality of a transform (instead of calling the LAMBDA data dependence legality)

• Represent scalar variables used in computations as zero dimensional arrays
• Implement data privatization: removes dependences for auto-parallelization
• Embed full scattering function into dependence check polyhedron, so that we do not make any special assumptions about the form of the scattering function eligible for data dependence/transformation legality check (Konrad will do that)