#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 (mpz_sgn (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++)
- mpz_neg (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++)
- mpz_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]);
- mpz_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:
- mpz_sub_ui (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:
- mpz_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_Coefficient_to_mpz_t (num, nv);
ppl_Coefficient_to_mpz_t (denom, dv);
- gcc_assert (value_notzero_p (dv));
+ gcc_assert (mpz_sgn (dv) != 0);
mpz_tdiv_q (res, nv, dv);
}
{
ppl_Coefficient_to_mpz_t (num, nv);
ppl_Coefficient_to_mpz_t (denom, dv);
- gcc_assert (value_notzero_p (dv));
+ gcc_assert (mpz_sgn (dv) != 0);
mpz_tdiv_q (res, nv, dv);
}
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