#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);
}
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);
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);
ppl_delete_Constraint (new_cstr);
}
- value_clear (val);
+ mpz_clear (val);
ppl_delete_Coefficient (c);
return res;
}
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;
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;
}
/* 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);
/* 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);
/* 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);
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);
{
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);
}
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);
{
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);
}
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);
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
OSDN Git Service
