X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Fgraphite-ppl.c;h=9762ca46770bbc8b39f7135999d23d64ac89d50d;hb=3b01567f28b62f8d753edb3a490064eeeabb5420;hp=62af5adfc6835fc13ed22ff13a838bf639ff4fb9;hpb=7cf0dbf3e5eee1286c76c26a836622c9c9974736;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/graphite-ppl.c b/gcc/graphite-ppl.c index 62af5adfc68..9762ca46770 100644 --- a/gcc/graphite-ppl.c +++ b/gcc/graphite-ppl.c @@ -22,303 +22,60 @@ along with GCC; see the file COPYING3. If not see #include "config.h" #include "system.h" #include "coretypes.h" -#include "tm.h" -#include "ggc.h" #ifdef HAVE_cloog + #include "ppl_c.h" -#include "cloog/cloog.h" +#include "graphite-cloog-util.h" #include "graphite-ppl.h" -/* Translates row ROW of the CloogMatrix MATRIX to a PPL Constraint. */ - -static ppl_Constraint_t -cloog_matrix_to_ppl_constraint (CloogMatrix *matrix, int row) -{ - int j; - ppl_Constraint_t cstr; - ppl_Coefficient_t coef; - ppl_Linear_Expression_t expr; - ppl_dimension_type dim = matrix->NbColumns - 2; - - ppl_new_Coefficient (&coef); - ppl_new_Linear_Expression_with_dimension (&expr, dim); - - for (j = 1; j < matrix->NbColumns - 1; j++) - { - ppl_assign_Coefficient_from_mpz_t (coef, matrix->p[row][j]); - ppl_Linear_Expression_add_to_coefficient (expr, j - 1, coef); - } - - ppl_assign_Coefficient_from_mpz_t (coef, - matrix->p[row][matrix->NbColumns - 1]); - ppl_Linear_Expression_add_to_inhomogeneous (expr, coef); - ppl_delete_Coefficient (coef); - - if (value_zero_p (matrix->p[row][0])) - ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_EQUAL); - else - ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL); - - ppl_delete_Linear_Expression (expr); - return cstr; -} - -/* Creates a PPL constraint system from MATRIX. */ - -static void -new_Constraint_System_from_Cloog_Matrix (ppl_Constraint_System_t *pcs, - CloogMatrix *matrix) -{ - int i; - - ppl_new_Constraint_System (pcs); - - for (i = 0; i < matrix->NbRows; i++) - { - ppl_Constraint_t c = cloog_matrix_to_ppl_constraint (matrix, i); - ppl_Constraint_System_insert_Constraint (*pcs, c); - ppl_delete_Constraint (c); - } -} - -/* Creates a PPL Polyhedron from MATRIX. */ - -void -new_C_Polyhedron_from_Cloog_Matrix (ppl_Polyhedron_t *ph, - CloogMatrix *matrix) -{ - ppl_Constraint_System_t cs; - new_Constraint_System_from_Cloog_Matrix (&cs, matrix); - ppl_new_C_Polyhedron_recycle_Constraint_System (ph, cs); -} - -/* Counts the number of constraints in PCS. */ - -static int -ppl_Constrain_System_number_of_constraints (ppl_const_Constraint_System_t pcs) -{ - ppl_Constraint_System_const_iterator_t cit, end; - int num = 0; - - ppl_new_Constraint_System_const_iterator (&cit); - ppl_new_Constraint_System_const_iterator (&end); - - for (ppl_Constraint_System_begin (pcs, cit), - ppl_Constraint_System_end (pcs, end); - !ppl_Constraint_System_const_iterator_equal_test (cit, end); - ppl_Constraint_System_const_iterator_increment (cit)) - num++; - - ppl_delete_Constraint_System_const_iterator (cit); - ppl_delete_Constraint_System_const_iterator (end); - return num; -} - -static void -oppose_constraint (CloogMatrix *m, int row) -{ - int k; - - /* Do not oppose the first column: it is the eq/ineq one. */ - for (k = 1; k < m->NbColumns; k++) - value_oppose (m->p[row][k], m->p[row][k]); -} - -/* Inserts constraint CSTR at row ROW of matrix M. */ - -void -insert_constraint_into_matrix (CloogMatrix *m, int row, - ppl_const_Constraint_t cstr) -{ - ppl_Coefficient_t c; - ppl_dimension_type i, dim, nb_cols = m->NbColumns; - - ppl_Constraint_space_dimension (cstr, &dim); - ppl_new_Coefficient (&c); - - for (i = 0; i < dim; i++) - { - ppl_Constraint_coefficient (cstr, i, c); - ppl_Coefficient_to_mpz_t (c, m->p[row][i + 1]); - } - - for (i = dim; i < nb_cols - 1; i++) - value_set_si (m->p[row][i + 1], 0); - - ppl_Constraint_inhomogeneous_term (cstr, c); - ppl_Coefficient_to_mpz_t (c, m->p[row][nb_cols - 1]); - value_set_si (m->p[row][0], 1); - - switch (ppl_Constraint_type (cstr)) - { - case PPL_CONSTRAINT_TYPE_LESS_THAN: - oppose_constraint (m, row); - case PPL_CONSTRAINT_TYPE_GREATER_THAN: - value_sub_int (m->p[row][nb_cols - 1], - m->p[row][nb_cols - 1], 1); - break; - - case PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL: - oppose_constraint (m, row); - case PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL: - break; - - case PPL_CONSTRAINT_TYPE_EQUAL: - value_set_si (m->p[row][0], 0); - break; - - default: - /* Not yet implemented. */ - gcc_unreachable(); - } - - ppl_delete_Coefficient (c); -} - -/* Creates a CloogMatrix from constraint system PCS. */ - -static CloogMatrix * -new_Cloog_Matrix_from_ppl_Constraint_System (ppl_const_Constraint_System_t pcs) -{ - CloogMatrix *matrix; - ppl_Constraint_System_const_iterator_t cit, end; - ppl_dimension_type dim; - int rows; - int row = 0; - - rows = ppl_Constrain_System_number_of_constraints (pcs); - ppl_Constraint_System_space_dimension (pcs, &dim); - matrix = cloog_matrix_alloc (rows, dim + 2); - ppl_new_Constraint_System_const_iterator (&cit); - ppl_new_Constraint_System_const_iterator (&end); - - for (ppl_Constraint_System_begin (pcs, cit), - ppl_Constraint_System_end (pcs, end); - !ppl_Constraint_System_const_iterator_equal_test (cit, end); - ppl_Constraint_System_const_iterator_increment (cit)) - { - ppl_const_Constraint_t c; - ppl_Constraint_System_const_iterator_dereference (cit, &c); - insert_constraint_into_matrix (matrix, row, c); - row++; - } - - ppl_delete_Constraint_System_const_iterator (cit); - ppl_delete_Constraint_System_const_iterator (end); - - return matrix; -} - -/* Creates a CloogMatrix from polyhedron PH. */ - -CloogMatrix * -new_Cloog_Matrix_from_ppl_Polyhedron (ppl_const_Polyhedron_t ph) -{ - ppl_const_Constraint_System_t pcs; - CloogMatrix *res; - - ppl_Polyhedron_get_constraints (ph, &pcs); - res = new_Cloog_Matrix_from_ppl_Constraint_System (pcs); - - return res; -} - -/* Creates a CloogDomain from polyhedron PH. */ - -CloogDomain * -new_Cloog_Domain_from_ppl_Polyhedron (ppl_const_Polyhedron_t ph) -{ - CloogMatrix *mat = new_Cloog_Matrix_from_ppl_Polyhedron (ph); - CloogDomain *res = cloog_domain_matrix2domain (mat); - cloog_matrix_free (mat); - return res; -} - -/* Creates a CloogDomain from a pointset powerset PS. */ - -CloogDomain * -new_Cloog_Domain_from_ppl_Pointset_Powerset ( - ppl_Pointset_Powerset_C_Polyhedron_t ps) -{ - CloogDomain *res = NULL; - ppl_Pointset_Powerset_C_Polyhedron_iterator_t it, end; - - ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&it); - ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&end); - - for (ppl_Pointset_Powerset_C_Polyhedron_iterator_begin (ps, it), - ppl_Pointset_Powerset_C_Polyhedron_iterator_end (ps, end); - !ppl_Pointset_Powerset_C_Polyhedron_iterator_equal_test (it, end); - ppl_Pointset_Powerset_C_Polyhedron_iterator_increment (it)) - { - ppl_const_Polyhedron_t ph; - CloogDomain *tmp; - - ppl_Pointset_Powerset_C_Polyhedron_iterator_dereference (it, &ph); - tmp = new_Cloog_Domain_from_ppl_Polyhedron (ph); - - if (res == NULL) - res = tmp; - else - res = cloog_domain_union (res, tmp); - } - - ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (it); - ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (end); - - gcc_assert (res != NULL); - - return res; -} - /* Set the inhomogeneous term of E to X. */ void -ppl_set_inhomogeneous_gmp (ppl_Linear_Expression_t e, Value x) +ppl_set_inhomogeneous_gmp (ppl_Linear_Expression_t e, mpz_t x) { - Value v0, v1; + mpz_t v0, v1; ppl_Coefficient_t c; - value_init (v0); - value_init (v1); + mpz_init (v0); + mpz_init (v1); ppl_new_Coefficient (&c); ppl_Linear_Expression_inhomogeneous_term (e, c); ppl_Coefficient_to_mpz_t (c, v1); - value_oppose (v1, v1); - value_assign (v0, x); - value_addto (v0, v0, v1); + mpz_neg (v1, v1); + mpz_set (v0, x); + mpz_add (v0, v0, v1); ppl_assign_Coefficient_from_mpz_t (c, v0); ppl_Linear_Expression_add_to_inhomogeneous (e, c); - value_clear (v0); - value_clear (v1); + mpz_clear (v0); + mpz_clear (v1); ppl_delete_Coefficient (c); } /* Set E[I] to X. */ void -ppl_set_coef_gmp (ppl_Linear_Expression_t e, ppl_dimension_type i, Value x) +ppl_set_coef_gmp (ppl_Linear_Expression_t e, ppl_dimension_type i, mpz_t x) { - Value v0, v1; + mpz_t v0, v1; ppl_Coefficient_t c; - value_init (v0); - value_init (v1); + mpz_init (v0); + mpz_init (v1); ppl_new_Coefficient (&c); ppl_Linear_Expression_coefficient (e, i, c); ppl_Coefficient_to_mpz_t (c, v1); - value_oppose (v1, v1); - value_assign (v0, x); - value_addto (v0, v0, v1); + mpz_neg (v1, v1); + mpz_set (v0, x); + mpz_add (v0, v0, v1); ppl_assign_Coefficient_from_mpz_t (c, v0); ppl_Linear_Expression_add_to_coefficient (e, i, c); - value_clear (v0); - value_clear (v1); + mpz_clear (v0); + mpz_clear (v1); ppl_delete_Coefficient (c); } @@ -421,9 +178,9 @@ ppl_strip_loop (ppl_Polyhedron_t ph, ppl_dimension_type loop, int stride) ppl_dimension_type dim; ppl_Polyhedron_t res; ppl_Coefficient_t c; - Value val; + mpz_t val; - value_init (val); + mpz_init (val); ppl_new_Coefficient (&c); ppl_Polyhedron_space_dimension (ph, &dim); @@ -455,7 +212,7 @@ ppl_strip_loop (ppl_Polyhedron_t ph, ppl_dimension_type loop, int stride) ppl_Linear_Expression_coefficient (expr, loop, c); ppl_delete_Linear_Expression (expr); ppl_Coefficient_to_mpz_t (c, val); - v = value_get_si (val); + v = mpz_get_si (val); if (0 < v || v < 0) ppl_Polyhedron_add_constraint (tmp, cstr); @@ -499,7 +256,7 @@ ppl_strip_loop (ppl_Polyhedron_t ph, ppl_dimension_type loop, int stride) ppl_delete_Constraint (new_cstr); } - value_clear (val); + mpz_clear (val); ppl_delete_Coefficient (c); return res; } @@ -515,13 +272,13 @@ ppl_lexico_compare_linear_expressions (ppl_Linear_Expression_t a, ppl_dimension_type i; ppl_Coefficient_t c; int res; - Value va, vb; + mpz_t va, vb; ppl_Linear_Expression_space_dimension (a, &length1); ppl_Linear_Expression_space_dimension (b, &length2); ppl_new_Coefficient (&c); - value_init (va); - value_init (vb); + mpz_init (va); + mpz_init (vb); if (length1 < length2) min_length = length1; @@ -534,19 +291,19 @@ ppl_lexico_compare_linear_expressions (ppl_Linear_Expression_t a, ppl_Coefficient_to_mpz_t (c, va); ppl_Linear_Expression_coefficient (b, i, c); ppl_Coefficient_to_mpz_t (c, vb); - res = value_compare (va, vb); + res = mpz_cmp (va, vb); if (res == 0) continue; - value_clear (va); - value_clear (vb); + mpz_clear (va); + mpz_clear (vb); ppl_delete_Coefficient (c); return res; } - value_clear (va); - value_clear (vb); + mpz_clear (va); + mpz_clear (vb); ppl_delete_Coefficient (c); return length1 - length2; } @@ -579,7 +336,7 @@ ppl_print_linear_expr (FILE *file, ppl_Linear_Expression_t le) /* Print to STDERR the linear expression LE. */ -void +DEBUG_FUNCTION void debug_ppl_linear_expr (ppl_Linear_Expression_t le) { ppl_print_linear_expr (stderr, le); @@ -617,7 +374,7 @@ ppl_print_powerset_matrix (FILE *file, /* Print to STDERR the polyhedron PH under its PolyLib matrix form. */ -void +DEBUG_FUNCTION void debug_ppl_polyhedron_matrix (ppl_Polyhedron_t ph) { ppl_print_polyhedron_matrix (stderr, ph); @@ -625,7 +382,7 @@ debug_ppl_polyhedron_matrix (ppl_Polyhedron_t ph) /* Print to STDERR the powerset PS in its PolyLib matrix form. */ -void +DEBUG_FUNCTION void debug_ppl_powerset_matrix (ppl_Pointset_Powerset_C_Polyhedron_t ps) { ppl_print_powerset_matrix (stderr, ps); @@ -647,14 +404,14 @@ ppl_read_polyhedron_matrix (ppl_Polyhedron_t *ph, FILE *file) void ppl_max_for_le_pointset (ppl_Pointset_Powerset_C_Polyhedron_t ps, - ppl_Linear_Expression_t le, Value res) + ppl_Linear_Expression_t le, mpz_t res) { ppl_Coefficient_t num, denom; - Value dv, nv; + mpz_t dv, nv; int maximum, err; - value_init (nv); - value_init (dv); + mpz_init (nv); + mpz_init (dv); ppl_new_Coefficient (&num); ppl_new_Coefficient (&denom); err = ppl_Pointset_Powerset_C_Polyhedron_maximize (ps, le, num, denom, &maximum); @@ -663,12 +420,12 @@ ppl_max_for_le_pointset (ppl_Pointset_Powerset_C_Polyhedron_t ps, { ppl_Coefficient_to_mpz_t (num, nv); ppl_Coefficient_to_mpz_t (denom, dv); - gcc_assert (value_notzero_p (dv)); - value_division (res, nv, dv); + gcc_assert (mpz_sgn (dv) != 0); + mpz_tdiv_q (res, nv, dv); } - value_clear (nv); - value_clear (dv); + mpz_clear (nv); + mpz_clear (dv); ppl_delete_Coefficient (num); ppl_delete_Coefficient (denom); } @@ -678,14 +435,14 @@ ppl_max_for_le_pointset (ppl_Pointset_Powerset_C_Polyhedron_t ps, void ppl_min_for_le_pointset (ppl_Pointset_Powerset_C_Polyhedron_t ps, - ppl_Linear_Expression_t le, Value res) + ppl_Linear_Expression_t le, mpz_t res) { ppl_Coefficient_t num, denom; - Value dv, nv; + mpz_t dv, nv; int minimum, err; - value_init (nv); - value_init (dv); + mpz_init (nv); + mpz_init (dv); ppl_new_Coefficient (&num); ppl_new_Coefficient (&denom); err = ppl_Pointset_Powerset_C_Polyhedron_minimize (ps, le, num, denom, &minimum); @@ -694,12 +451,12 @@ ppl_min_for_le_pointset (ppl_Pointset_Powerset_C_Polyhedron_t ps, { ppl_Coefficient_to_mpz_t (num, nv); ppl_Coefficient_to_mpz_t (denom, dv); - gcc_assert (value_notzero_p (dv)); - value_division (res, nv, dv); + gcc_assert (mpz_sgn (dv) != 0); + mpz_tdiv_q (res, nv, dv); } - value_clear (nv); - value_clear (dv); + mpz_clear (nv); + mpz_clear (dv); ppl_delete_Coefficient (num); ppl_delete_Coefficient (denom); } @@ -714,15 +471,15 @@ ppl_build_relation (int dim, int pos1, int pos2, int c, ppl_Linear_Expression_t expr; ppl_Constraint_t cstr; ppl_Coefficient_t coef; - Value v, v_op, v_c; + mpz_t v, v_op, v_c; - value_init (v); - value_init (v_op); - value_init (v_c); + mpz_init (v); + mpz_init (v_op); + mpz_init (v_c); - value_set_si (v, 1); - value_set_si (v_op, -1); - value_set_si (v_c, c); + mpz_set_si (v, 1); + mpz_set_si (v_op, -1); + mpz_set_si (v_c, c); ppl_new_Coefficient (&coef); ppl_new_Linear_Expression_with_dimension (&expr, dim); @@ -738,11 +495,72 @@ ppl_build_relation (int dim, int pos1, int pos2, int c, ppl_delete_Linear_Expression (expr); ppl_delete_Coefficient (coef); - value_clear (v); - value_clear (v_op); - value_clear (v_c); + mpz_clear (v); + mpz_clear (v_op); + mpz_clear (v_c); return cstr; } +/* Print to STDERR the GMP value VAL. */ + +DEBUG_FUNCTION void +debug_gmp_value (mpz_t val) +{ + char *str = mpz_get_str (0, 10, val); + void (*gmp_free) (void *, size_t); + + fprintf (stderr, "%s", str); + mp_get_memory_functions (NULL, NULL, &gmp_free); + (*gmp_free) (str, strlen (str) + 1); +} + +/* Checks for integer feasibility: returns true when the powerset + polyhedron PS has no integer solutions. */ + +bool +ppl_powerset_is_empty (ppl_Pointset_Powerset_C_Polyhedron_t ps) +{ + ppl_PIP_Problem_t pip; + ppl_dimension_type d; + ppl_const_Constraint_System_t pcs; + ppl_Constraint_System_const_iterator_t first, last; + ppl_Pointset_Powerset_C_Polyhedron_iterator_t it, end; + bool has_integer_solutions = false; + + if (ppl_Pointset_Powerset_C_Polyhedron_is_empty (ps)) + return true; + + ppl_Pointset_Powerset_C_Polyhedron_space_dimension (ps, &d); + ppl_new_Constraint_System_const_iterator (&first); + ppl_new_Constraint_System_const_iterator (&last); + ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&it); + ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&end); + + for (ppl_Pointset_Powerset_C_Polyhedron_iterator_begin (ps, it), + ppl_Pointset_Powerset_C_Polyhedron_iterator_end (ps, end); + !ppl_Pointset_Powerset_C_Polyhedron_iterator_equal_test (it, end); + ppl_Pointset_Powerset_C_Polyhedron_iterator_increment (it)) + { + ppl_const_Polyhedron_t ph; + ppl_Pointset_Powerset_C_Polyhedron_iterator_dereference (it, &ph); + + ppl_Polyhedron_get_constraints (ph, &pcs); + ppl_Constraint_System_begin (pcs, first); + ppl_Constraint_System_end (pcs, last); + + ppl_new_PIP_Problem_from_constraints (&pip, d, first, last, 0, NULL); + has_integer_solutions |= ppl_PIP_Problem_is_satisfiable (pip); + + ppl_delete_PIP_Problem (pip); + } + + ppl_delete_Constraint_System_const_iterator (first); + ppl_delete_Constraint_System_const_iterator (last); + ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (it); + ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (end); + + return !has_integer_solutions; +} + #endif