source/ppl/checking.c

   1
   2    /**-------------------------------------------------------------------**
   3     **                               CLooG                               **
   4     **-------------------------------------------------------------------**
   5     **                             checking.c                            **
   6     **-------------------------------------------------------------------**
   7     **                   First version: July 22th 2008                   **
   8     **-------------------------------------------------------------------**/
   9
  10
  11 /******************************************************************************
  12  *               CLooG : the Chunky Loop Generator (experimental)             *
  13  ******************************************************************************
  14  *                                                                            *
  15  * Copyright (C) 2001-2008 Cedric Bastoul                                     *
  16  *                                                                            *
  17  * This is free software; you can redistribute it and/or modify it under the  *
  18  * terms of the GNU General Public License as published by the Free Software  *
  19  * Foundation; either version 2 of the License, or (at your option) any later *
  20  * version.                                                                   *
  21  *                                                                            *
  22  * This software is distributed in the hope that it will be useful, but       *
  23  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY *
  24  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License   *
  25  * for more details.                                                          *
  26  *                                                                            *
  27  * You should have received a copy of the GNU General Public License along    *
  28  * with software; if not, write to the Free Software Foundation, Inc.,        *
  29  * 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA                     *
  30  *                                                                            *
  31  * CLooG, the Chunky Loop Generator                                           *
  32  * Written by Cedric Bastoul, Cedric.Bastoul@inria.fr                         *
  33  *                                                                            *
  34  ******************************************************************************/
  35
  36
  37 static CloogDomain *
  38 cloog_domain_image (CloogDomain * domain, CloogMatrix * mapping)
  39 {
  40   Polyhedron *p = d2p (domain);
  41   CloogDomain *res =
  42     cloog_check_domain (cloog_domain_alloc
  43                         (DomainImage (p, mapping, MAX_RAYS)));
  44   Polyhedron_Free (p);
  45   return print_result ("cloog_domain_image", res);
  46 }
  47
  48 static CloogDomain *
  49 cloog_domain_preimage (CloogDomain * domain, CloogMatrix * mapping)
  50 {
  51   Polyhedron *p = d2p (domain);
  52   CloogDomain *res =
  53     cloog_check_domain (cloog_domain_alloc
  54                         (DomainPreimage (p, mapping, MAX_RAYS)));
  55   Polyhedron_Free (p);
  56   return print_result ("cloog_domain_preimage", res);
  57 }
  58
  59 CloogDomain *
  60 cloog_domain_project_1 (CloogDomain * domain, int level, int nb_par)
  61 {
  62   int row, column, nb_rows, nb_columns, difference;
  63   CloogDomain *projected_domain;
  64   CloogMatrix *matrix;
  65
  66   nb_rows = level + nb_par + 1;
  67   nb_columns = cloog_domain_dim (domain) + 1;
  68   difference = nb_columns - nb_rows;
  69
  70   if (difference == 0)
  71     return print_result ("cloog_domain_project", cloog_domain_copy (domain));
  72
  73   matrix = cloog_matrix_alloc (nb_rows, nb_columns);
  74
  75   for (row = 0; row < level; row++)
  76     for (column = 0; column < nb_columns; column++)
  77       value_set_si (matrix->p[row][column], (row == column ? 1 : 0));
  78
  79   for (; row < nb_rows; row++)
  80     for (column = 0; column < nb_columns; column++)
  81       value_set_si (matrix->p[row][column],
  82                     (row + difference == column ? 1 : 0));
  83
  84   projected_domain = cloog_domain_image (domain, matrix);
  85   cloog_matrix_free (matrix);
  86
  87   return print_result ("cloog_domain_project_1", cloog_check_domain (projected_domain));
  88 }
  89
  90 static CloogDomain *
  91 cloog_domain_addconstraints_1 (domain_source, domain_target)
  92      CloogDomain *domain_source, *domain_target;
  93 {
  94   unsigned nb_constraint;
  95   Value *constraints;
  96   ppl_polyhedra_union *source, *target, *new, *next, *last;
  97
  98   source = cloog_domain_upol (domain_source);
  99   target = cloog_domain_upol (domain_target);
 100
 101   constraints = cloog_upol_polyhedron (source)->p_Init;
 102   nb_constraint = cloog_upol_nbc (source);
 103   last = new = cloog_new_upol (AddConstraints (constraints, nb_constraint,
 104                                                u2p (target), MAX_RAYS));
 105   source = cloog_upol_next (source);
 106   next = cloog_upol_next (target);
 107
 108   while (next)
 109     {                           /* BUG !!! This is actually a bug. I don't know yet how to cleanly avoid
 110                                  * the situation where source and target do not have the same number of
 111                                  * elements. So this 'if' is an awful trick, waiting for better.
 112                                  */
 113       if (source)
 114         {
 115           constraints = cloog_upol_polyhedron (source)->p_Init;
 116           nb_constraint = cloog_upol_nbc (source);
 117           source = cloog_upol_next (source);
 118         }
 119       cloog_upol_set_next
 120         (last, cloog_new_upol (AddConstraints (constraints, nb_constraint,
 121                                                u2p (next), MAX_RAYS)));
 122       last = cloog_upol_next (last);
 123       next = cloog_upol_next (next);
 124     }
 125
 126   return print_result ("cloog_domain_addconstraints", cloog_check_domain (cloog_new_domain (new)));
 127 }
 128
 129 CloogDomain *
 130 cloog_domain_extend_1 (CloogDomain * domain, int dim, int nb_par)
 131 {
 132   int row, column, nb_rows, nb_columns, difference;
 133   CloogDomain *extended_domain;
 134   CloogMatrix *matrix;
 135
 136   nb_rows = 1 + cloog_domain_dim (domain);
 137   nb_columns = dim + nb_par + 1;
 138   difference = nb_columns - nb_rows;
 139
 140   if (difference == 0)
 141     return print_result ("cloog_domain_extend_1", cloog_domain_copy (domain));
 142
 143   matrix = cloog_matrix_alloc (nb_rows, nb_columns);
 144
 145   for (row = 0; row < cloog_domain_dim (domain) - nb_par; row++)
 146     for (column = 0; column < nb_columns; column++)
 147       value_set_si (matrix->p[row][column], (row == column ? 1 : 0));
 148
 149   for (; row <= cloog_domain_dim (domain); row++)
 150     for (column = 0; column < nb_columns; column++)
 151       value_set_si (matrix->p[row][column],
 152                     (row + difference == column ? 1 : 0));
 153
 154   extended_domain = cloog_domain_preimage (domain, matrix);
 155   cloog_matrix_free (matrix);
 156
 157   return print_result ("cloog_domain_extend_1", cloog_check_domain (extended_domain));
 158 }
 159
 160 static CloogDomain *
 161 cloog_domain_convex_1 (CloogDomain * domain)
 162 {
 163   Polyhedron *p = d2p (domain);
 164   CloogDomain *res =
 165     cloog_check_domain (cloog_domain_alloc
 166                         (DomainConvex (p, MAX_RAYS)));
 167   Polyhedron_Free (p);
 168   return print_result ("cloog_domain_convex_1", res);
 169 }
 170
 171 static CloogDomain *
 172 cloog_domain_simplify_1 (CloogDomain * dom1, CloogDomain * dom2)
 173 {
 174   CloogMatrix *M, *M2;
 175   CloogDomain *dom;
 176   Polyhedron *p1 = d2p (dom1);
 177   Polyhedron *p2 = d2p (dom2);
 178   int nbc = cloog_domain_nbconstraints (dom1);
 179
 180   /* DomainSimplify doesn't remove all redundant equalities,
 181    * so we remove them here first in case both dom1 and dom2
 182    * are single polyhedra (i.e., not unions of polyhedra).
 183    */
 184   if (cloog_domain_isconvex (dom1) && cloog_domain_isconvex (dom2)
 185       && cloog_domain_nbeq (dom1) && cloog_domain_nbeq (dom2))
 186     {
 187       int i, row;
 188       int rows = cloog_domain_nbeq (dom1) + cloog_domain_nbeq (dom2);
 189       int cols = cloog_domain_dim (dom1) + 2;
 190       int rank;
 191       M = cloog_matrix_alloc (rows, cols);
 192       M2 = cloog_matrix_alloc (nbc, cols);
 193       Vector_Copy (cloog_domain_polyhedron (dom2)->Constraint[0],
 194                    M->p[0], cloog_domain_nbeq (dom2) * cols);
 195       rank = cloog_domain_nbeq (dom2);
 196       row = 0;
 197       for (i = 0; i < cloog_domain_nbeq (dom1); ++i)
 198         {
 199           Vector_Copy (p1->Constraint[i], M->p[rank], cols);
 200           if (Gauss (M, rank + 1, cols - 1) > rank)
 201             {
 202               Vector_Copy (p1->Constraint[i], M2->p[row++], cols);
 203               rank++;
 204             }
 205         }
 206       if (row < cloog_domain_nbeq (dom1))
 207         {
 208           Vector_Copy (p1->Constraint[cloog_domain_nbeq (dom1)],
 209                        M2->p[row], (nbc - cloog_domain_nbeq (dom1)) * cols);
 210           p1 = Constraints2Polyhedron (M2, MAX_RAYS);
 211         }
 212       cloog_matrix_free (M2);
 213       cloog_matrix_free (M);
 214     }
 215
 216   dom = cloog_domain_alloc (DomainSimplify (p1, p2, MAX_RAYS));
 217   Polyhedron_Free (p1);
 218   Polyhedron_Free (p2);
 219   return print_result ("cloog_domain_simplify", cloog_check_domain (dom));
 220 }
 221