source/piplib-wrapper.c

   1
   2 /**------ ( ----------------------------------------------------------**
   3  **       )\                      CAnDL                               **
   4  **----- /  ) --------------------------------------------------------**
   5  **     ( * (               piplib-wrapper.c                          **
   6  **----  \#/  --------------------------------------------------------**
   7  **    .-"#'-.        First version: January 31st 2012                **
   8  **--- |"-.-"| -------------------------------------------------------**
   9  |     |
  10  |     |
  11  ******** |     | *************************************************************
  12  * CAnDL  '-._,-' the Chunky Analyzer for Dependences in Loops (experimental) *
  13  ******************************************************************************
  14  *                                                                            *
  15  * Copyright (C) 2003-2008 Cedric Bastoul                                     *
  16  *                                                                            *
  17  * This is free software; you can redistribute it and/or modify it under the  *
  18  * terms of the GNU Lesser General Public License as published by the Free    *
  19  * Software Foundation; either version 3 of the License, or (at your option)  *
  20  * any later 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 Lesser General Public License   *
  28  * along with software; if not, write to the Free Software Foundation, Inc.,  *
  29  * 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA                     *
  30  *                                                                            *
  31  * CAnDL, the Chunky Dependence Analyzer                                      *
  32  * Written by Cedric Bastoul, Cedric.Bastoul@inria.fr                         *
  33  *                                                                            *
  34  ******************************************************************************/
  35 /**
  36  * \file piplib-wrapper.c
  37  * \author Louis-Noel Pouchet
  38  */
  39
  40
  41 #include <stdlib.h>
  42 #include <stdio.h>
  43 #include <string.h>
  44 #include <candl/candl.h>
  45 #include <osl/relation.h>
  46 #include <osl/macros.h> /* Need OSL_PRECISION for compatibility with piplib */
  47 #include <candl/matrix.h>
  48 #include <candl/piplib-wrapper.h>
  49
  50
  51 /**
  52  * pip_relation2matrix function :
  53  * This function is used to keep the compatibility with Piplib
  54  */
  55 PipMatrix* pip_relation2matrix(osl_relation_p in) {
  56   int i, j, precision;
  57   PipMatrix *out;
  58
  59   if (in == NULL)
  60     return NULL;
  61
  62   #ifdef LINEAR_VALUE_IS_INT
  63     precision = OSL_PRECISION_SP;
  64   #elif defined(LINEAR_VALUE_IS_LONGLONG)
  65     precision = OSL_PRECISION_DP;
  66   #elif defined(LINEAR_VALUE_IS_MP)
  67     precision = OSL_PRECISION_MP;
  68   #endif
  69
  70   if (precision != in->precision)
  71     CANDL_error("Precision not compatible with piplib ! (pip_relation2matrix)");
  72
  73   out = pip_matrix_alloc(in->nb_rows, in->nb_columns);
  74
  75   for (i = 0 ; i < in->nb_rows ; i++) {
  76     for (j = 0 ; j < in->nb_columns ; j++) {
  77       #if defined(LINEAR_VALUE_IS_INT)
  78         CANDL_assign(out->p[i][j], in->m[i][j].sp);
  79       #elif defined(LINEAR_VALUE_IS_LONGLONG)
  80         CANDL_assign(out->p[i][j], in->m[i][j].dp);
  81       #elif defined(LINEAR_VALUE_IS_MP)
  82         CANDL_assign(out->p[i][j], *((mpz_t*)in->m[i][j].mp));
  83       #endif
  84     }
  85   }
  86
  87   return out;
  88 }
  89
  90
  91 /**
  92  * pip_matrix2relation function :
  93  * This function is used to keep the compatibility with Piplib
  94  */
  95 osl_relation_p pip_matrix2relation(PipMatrix* in) {
  96   int i, j, precision;
  97   osl_relation_p out;
  98   osl_int_t temp;
  99
 100   if (in == NULL)
 101     return NULL;
 102
 103   #if defined(LINEAR_VALUE_IS_INT)
 104     precision = OSL_PRECISION_SP;
 105   #elif defined(LINEAR_VALUE_IS_LONGLONG)
 106     precision = OSL_PRECISION_DP;
 107   #elif defined(LINEAR_VALUE_IS_MP)
 108     precision = OSL_PRECISION_MP;
 109   #endif
 110
 111   out = osl_relation_pmalloc(precision, in->NbRows, in->NbColumns);
 112   osl_int_init(precision, &temp);
 113
 114   for (i = 0 ; i < in->NbRows ; i++) {
 115     for (j = 0 ; j < in->NbColumns ; j++) {
 116       #ifdef LINEAR_VALUE_IS_INT
 117         temp.sp = in->p[i][j];
 118       #elif defined(LINEAR_VALUE_IS_LONGLONG)
 119         temp.dp = in->p[i][j];
 120       #elif defined(LINEAR_VALUE_IS_MP)
 121         mpz_set(*((mpz_t*)temp.mp), in->p[i][j]);
 122       #endif
 123       osl_int_assign(precision, &out->m[i][j], temp);
 124     }
 125   }
 126
 127   osl_int_clear(precision, &temp);
 128   return out;
 129 }
 130
 131 int pip_has_rational_point(osl_relation_p system,
 132                        osl_relation_p context,
 133                        int conservative) {
 134 // FIXME : compatibility with osl
 135 //#ifdef CANDL_HAS_PIPLIB_HYBRID
 136 //  return piplib_hybrid_has_rational_point(system, context, conservative);
 137 //#else
 138   PipOptions* options;
 139   int ret = 0;
 140   options = pip_options_init ();
 141   options->Simplify = 1;
 142   options->Urs_parms = -1;
 143   options->Urs_unknowns = -1;
 144   options->Nq = 0;
 145   PipQuast* solution = pip_solve_osl(system, context, -1, options);
 146   if ((solution != NULL) &&
 147       ((solution->list != NULL) || (solution->condition != NULL)))
 148     ret = 1;
 149   pip_options_free(options);
 150   pip_quast_free(solution);
 151   return ret;
 152 //#endif
 153 }
 154
 155
 156 /**
 157  * pip_solve_osl function :
 158  * A pip_solve with osl_relation_p instead of PipMatrix
 159  */
 160 PipQuast* pip_solve_osl(osl_relation_p inequnk, osl_relation_p ineqpar,
 161                         int Bg, PipOptions *options) {
 162   PipMatrix *pip_unk  = pip_relation2matrix(inequnk);
 163   PipMatrix *pip_par  = pip_relation2matrix(ineqpar);
 164   PipQuast  *solution = pip_solve(pip_unk, pip_par, Bg, options);
 165   if (pip_unk) pip_matrix_free(pip_unk);
 166   if (pip_par) pip_matrix_free(pip_par);
 167   return solution;
 168 }
 169
 170
 171 /**
 172  * Return true if the 'size' first elements of 'l1' and 'l2' are equal.
 173  */
 174 int piplist_are_equal(PipList* l1, PipList* l2, int size) {
 175   if (l1 == NULL && l2 == NULL)
 176     return 1;
 177   if (l1 == NULL || l2 == NULL)
 178     return 0;
 179   if (l1->vector == NULL && l2->vector == NULL)
 180     return 1;
 181   if (l1->vector == NULL || l2->vector == NULL)
 182     return 0;
 183
 184   int count = 0;
 185   for (; l1 && l2 && count < size; l1 = l1->next, l2 = l2->next, ++count) {
 186     if (l1->vector == NULL && l2->vector == NULL)
 187       return 1;
 188     if (l1->vector == NULL || l2->vector == NULL)
 189       return 0;
 190     if (l1->vector->nb_elements != l2->vector->nb_elements)
 191       return 0;
 192     int j;
 193     for (j = 0; j < l1->vector->nb_elements; ++j)
 194       if (! CANDL_eq(l1->vector->the_vector[j],
 195                      l2->vector->the_vector[j]) ||
 196           ! CANDL_eq(l1->vector->the_deno[j],
 197                      l2->vector->the_deno[j]))
 198         return 0;
 199   }
 200
 201   return 1;
 202 }
 203
 204
 205 /*
 206  * Converts all conditions where the path does not lead to a solution
 207  * The return is a upip_quast_to_polyhedranion of polyhedra
 208  * extracted from pip_quast_to_polyhedra
 209  */
 210 osl_relation_p pip_quast_no_solution_to_polyhedra(PipQuast *quast, int nvar,
 211                                                   int npar) {
 212   osl_relation_p ep;
 213   osl_relation_p tp;
 214   osl_relation_p qp;
 215   osl_relation_p iter;
 216   int precision;
 217   int j;
 218   if (quast == NULL)
 219     return NULL;
 220
 221   #if defined(LINEAR_VALUE_IS_INT)
 222     precision = OSL_PRECISION_SP;
 223   #elif defined(LINEAR_VALUE_IS_LONGLONG)
 224     precision = OSL_PRECISION_DP;
 225   #elif defined(LINEAR_VALUE_IS_MP)
 226     precision = OSL_PRECISION_MP;
 227   #endif
 228
 229   if (quast->condition != NULL) {
 230     tp = pip_quast_no_solution_to_polyhedra(quast->next_then, nvar, npar);
 231     ep = pip_quast_no_solution_to_polyhedra(quast->next_else, nvar, npar);
 232
 233     /* Each of the matrices in the then tree needs to be augmented with
 234      * the condition */
 235     for (iter = tp ; iter != NULL ; iter = iter->next) {
 236       int nrows = iter->nb_rows;
 237       osl_int_set_si(precision, &iter->m[nrows][0], 1);
 238       for (j = 1; j < 1 + nvar; j++)
 239         osl_int_set_si(precision, &iter->m[nrows][j], 0);
 240       for (j = 0; j < npar + 1; j++)
 241         osl_int_set_si(precision, &iter->m[nrows][1 + nvar + j],
 242                         CANDL_get_si(quast->condition->the_vector[j]));
 243       (iter->nb_rows)++;
 244     }
 245
 246     for (iter = ep; iter != NULL ; iter = iter->next) {
 247       int nrows = iter->nb_rows;
 248       /* Inequality */
 249       osl_int_set_si(precision, &iter->m[nrows][0], 1);
 250       for (j = 1; j < 1 + nvar; j++)
 251         osl_int_set_si(precision, &iter->m[nrows][j], 0);
 252       for (j = 0; j < npar + 1; j++)
 253         osl_int_set_si(precision, &iter->m[nrows][1 + nvar + j],
 254                      -CANDL_get_si(quast->condition->the_vector[j]));
 255       osl_int_decrement(precision,
 256                         &iter->m[nrows][iter->nb_columns - 1],
 257                         iter->m[nrows][iter->nb_columns - 1]);
 258       (iter->nb_rows)++;
 259     }
 260
 261     /* union of tp and ep */
 262     if (tp) {
 263       qp = tp;
 264       for (iter = tp ; iter->next != NULL ; iter = iter->next)
 265         ;
 266       iter->next = ep;
 267     } else {
 268       qp = ep;
 269     }
 270
 271     return qp;
 272
 273   }
 274
 275   if (quast->list != NULL)
 276     return NULL;
 277
 278   /* quast condition is NULL */
 279   osl_relation_p lwmatrix = osl_relation_pmalloc(precision, nvar+npar+1,
 280                                                 nvar+npar+2);
 281   lwmatrix->nb_rows = 0;
 282   lwmatrix->nb_parameters = npar;
 283
 284   return lwmatrix;
 285 }
 286
 287
 288 /*
 289  * Converts a PIP quast to a union of polyhedra
 290  */
 291 osl_relation_p pip_quast_to_polyhedra(PipQuast *quast, int nvar, int npar) {
 292   // originaly used for lastwriter
 293   // july 5th 2012 : extracted from dependence.c
 294
 295   osl_relation_p ep;
 296   osl_relation_p tp;
 297   osl_relation_p qp;
 298   osl_relation_p iter;
 299   int precision;
 300   int j;
 301   if (quast == NULL)
 302     return NULL;
 303
 304   #if defined(LINEAR_VALUE_IS_INT)
 305     precision = OSL_PRECISION_SP;
 306   #elif defined(LINEAR_VALUE_IS_LONGLONG)
 307     precision = OSL_PRECISION_DP;
 308   #elif defined(LINEAR_VALUE_IS_MP)
 309     precision = OSL_PRECISION_MP;
 310   #endif
 311
 312   if (quast->condition != NULL) {
 313     tp = pip_quast_to_polyhedra(quast->next_then, nvar, npar);
 314     ep = pip_quast_to_polyhedra(quast->next_else, nvar, npar);
 315
 316     /* Each of the matrices in the then tree needs to be augmented with
 317      * the condition */
 318     for (iter = tp ; iter != NULL ; iter = iter->next) {
 319       int nrows = iter->nb_rows;
 320       osl_int_set_si(precision, &iter->m[nrows][0], 1);
 321       for (j = 1; j < 1 + nvar; j++)
 322         osl_int_set_si(precision, &iter->m[nrows][j], 0);
 323       for (j = 0; j < npar + 1; j++)
 324         osl_int_set_si(precision, &iter->m[nrows][1 + nvar + j],
 325                         CANDL_get_si(quast->condition->the_vector[j]));
 326       (iter->nb_rows)++;
 327     }
 328
 329     /* JP : july 5th 2012:
 330      * Fix negation of a constraint in adding -1 to the constant
 331      */
 332
 333     for (iter = ep; iter != NULL ; iter = iter->next) {
 334       int nrows = iter->nb_rows;
 335       /* Inequality */
 336       osl_int_set_si(precision, &iter->m[nrows][0], 5);
 337       for (j = 1; j < 1 + nvar; j++)
 338         osl_int_set_si(precision, &iter->m[nrows][j], 0);
 339       for (j = 0; j < npar + 1; j++)
 340         osl_int_set_si(precision, &iter->m[nrows][1 + nvar + j],
 341                      -CANDL_get_si(quast->condition->the_vector[j]));
 342       osl_int_decrement(precision,
 343                         &iter->m[nrows][iter->nb_columns - 1],
 344                         iter->m[nrows][iter->nb_columns - 1]);
 345       (iter->nb_rows)++;
 346     }
 347
 348     /* union of tp and ep */
 349     if (tp) {
 350       qp = tp;
 351       for (iter = tp ; iter->next != NULL ; iter = iter->next)
 352         ;
 353       iter->next = ep;
 354     } else {
 355       qp = ep;
 356     }
 357
 358     return qp;
 359
 360   } else {
 361     /* quast condition is NULL */
 362     osl_relation_p lwmatrix = osl_relation_pmalloc(precision, nvar+npar+1,
 363                                                   nvar+npar+2);
 364     PipList *vecList = quast->list;
 365
 366     int count=0;
 367     while (vecList != NULL) {
 368       /* Equality */
 369       osl_int_set_si(precision, &lwmatrix->m[count][0], 0);
 370       for (j=0; j < nvar; j++)
 371         if (j == count)
 372           osl_int_set_si(precision, &lwmatrix->m[count][j + 1], 1);
 373         else
 374           osl_int_set_si(precision, &lwmatrix->m[count][j + 1], 0);
 375
 376       for (j=0; j < npar; j++)
 377         osl_int_set_si(precision, &lwmatrix->m[count][j + 1 + nvar],
 378                        -CANDL_get_si(vecList->vector->the_vector[j]));
 379       /* Constant portion */
 380       if (quast->newparm != NULL)
 381         /* Don't handle newparm for now */
 382         osl_int_set_si(precision, &lwmatrix->m[count][npar + 1 + nvar],
 383                        -CANDL_get_si(vecList->vector->the_vector[npar+1]));
 384       else
 385         osl_int_set_si(precision, &lwmatrix->m[count][npar + 1 + nvar],
 386                        -CANDL_get_si(vecList->vector->the_vector[npar]));
 387
 388       count++;
 389
 390       vecList = vecList->next;
 391     }
 392     lwmatrix->nb_rows = count;
 393     lwmatrix->nb_parameters = npar;
 394
 395     return lwmatrix;
 396   }
 397 }
 398
 399