gcc/graphite-poly.c

   1 /* Graphite polyhedral representation.
   2    Copyright (C) 2009, 2010 Free Software Foundation, Inc.
   3    Contributed by Sebastian Pop <sebastian.pop@amd.com> and
   4    Tobias Grosser <grosser@fim.uni-passau.de>.
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify
   9 it under the terms of the GNU General Public License as published by
  10 the Free Software Foundation; either version 3, or (at your option)
  11 any later version.
  12
  13 GCC is distributed in the hope that it will be useful,
  14 but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 GNU General Public License for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "diagnostic-core.h"
  25 #include "tree-flow.h"
  26 #include "tree-dump.h"
  27 #include "gimple-pretty-print.h"
  28 #include "cfgloop.h"
  29 #include "tree-chrec.h"
  30 #include "tree-data-ref.h"
  31 #include "tree-scalar-evolution.h"
  32 #include "sese.h"
  33
  34 #ifdef HAVE_cloog
  35 #include "ppl_c.h"
  36 #include "graphite-ppl.h"
  37 #include "graphite-poly.h"
  38 #include "graphite-dependences.h"
  39 #include "graphite-cloog-util.h"
  40
  41 #define OPENSCOP_MAX_STRING 256
  42
  43 /* Return the maximal loop depth in SCOP.  */
  44
  45 int
  46 scop_max_loop_depth (scop_p scop)
  47 {
  48   int i;
  49   poly_bb_p pbb;
  50   int max_nb_loops = 0;
  51
  52   FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
  53     {
  54       int nb_loops = pbb_dim_iter_domain (pbb);
  55       if (max_nb_loops < nb_loops)
  56         max_nb_loops = nb_loops;
  57     }
  58
  59   return max_nb_loops;
  60 }
  61
  62 /* Extend the scattering matrix of PBB to MAX_SCATTERING scattering
  63    dimensions.  */
  64
  65 static void
  66 extend_scattering (poly_bb_p pbb, int max_scattering)
  67 {
  68   ppl_dimension_type nb_old_dims, nb_new_dims;
  69   int nb_added_dims, i;
  70   ppl_Coefficient_t coef;
  71   mpz_t one;
  72
  73   nb_added_dims = max_scattering - pbb_nb_scattering_transform (pbb);
  74   mpz_init (one);
  75   mpz_set_si (one, 1);
  76   ppl_new_Coefficient (&coef);
  77   ppl_assign_Coefficient_from_mpz_t (coef, one);
  78
  79   gcc_assert (nb_added_dims >= 0);
  80
  81   nb_old_dims = pbb_nb_scattering_transform (pbb) + pbb_dim_iter_domain (pbb)
  82     + scop_nb_params (PBB_SCOP (pbb));
  83   nb_new_dims = nb_old_dims + nb_added_dims;
  84
  85   ppl_insert_dimensions (PBB_TRANSFORMED_SCATTERING (pbb),
  86                          pbb_nb_scattering_transform (pbb), nb_added_dims);
  87   PBB_NB_SCATTERING_TRANSFORM (pbb) += nb_added_dims;
  88
  89   /* Add identity matrix for the added dimensions.  */
  90   for (i = max_scattering - nb_added_dims; i < max_scattering; i++)
  91     {
  92       ppl_Constraint_t cstr;
  93       ppl_Linear_Expression_t expr;
  94
  95       ppl_new_Linear_Expression_with_dimension (&expr, nb_new_dims);
  96       ppl_Linear_Expression_add_to_coefficient (expr, i, coef);
  97       ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_EQUAL);
  98       ppl_Polyhedron_add_constraint (PBB_TRANSFORMED_SCATTERING (pbb), cstr);
  99       ppl_delete_Constraint (cstr);
 100       ppl_delete_Linear_Expression (expr);
 101     }
 102
 103   ppl_delete_Coefficient (coef);
 104   mpz_clear (one);
 105 }
 106
 107 /* All scattering matrices in SCOP will have the same number of scattering
 108    dimensions.  */
 109
 110 int
 111 unify_scattering_dimensions (scop_p scop)
 112 {
 113   int i;
 114   poly_bb_p pbb;
 115   graphite_dim_t max_scattering = 0;
 116
 117   FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
 118     max_scattering = MAX (pbb_nb_scattering_transform (pbb), max_scattering);
 119
 120   FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
 121     extend_scattering (pbb, max_scattering);
 122
 123   return max_scattering;
 124 }
 125
 126 /* Print to FILE the pdr PH in OpenScop format.  NB_SUBSCRIPTS is the number
 127    of subscripts in PH, ALIAS_SET_DIM is the dimension of the alias set and
 128    NB_PARAMS is the number of parameters in PH.  */
 129
 130 static void
 131 openscop_print_pdr_polyhedron (FILE *file, ppl_const_Polyhedron_t ph,
 132                                int nb_subscripts, int alias_set_dimension,
 133                                int nb_params)
 134 {
 135   int input, locals, output;
 136   ppl_dimension_type alias_set_dim = (ppl_dimension_type) alias_set_dimension;
 137   ppl_dimension_type sub_dim_last = alias_set_dim + nb_subscripts;
 138   ppl_dimension_type *map, i, ph_space_dim = sub_dim_last + 1;
 139   ppl_Polyhedron_t pph;
 140
 141   ppl_new_C_Polyhedron_from_C_Polyhedron (&pph, ph);
 142
 143   map = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, ph_space_dim);
 144
 145   for (i = 0; i < alias_set_dim - 1; i++)
 146     map[i] = nb_subscripts + 1 + i;
 147
 148   for (i = alias_set_dim - 1; i < sub_dim_last; i++)
 149     map[i] = i - alias_set_dim + 1;
 150
 151   ppl_Polyhedron_map_space_dimensions (pph, map, ph_space_dim - 1);
 152
 153   locals = 0;
 154   input = alias_set_dim - nb_params - 1;
 155
 156   /* According to OpenScop specification, the alias set column is a part of
 157      the output columns.  */
 158   output = nb_subscripts + 1;
 159
 160   openscop_print_polyhedron_matrix (file, pph, output, input, locals, nb_params);
 161 }
 162
 163 /* Print to FILE the powerset PDR.  NB_SUBSCRIPTS is the number of subscripts
 164    in PDR, ALIAS_SET_DIM is the dimension of the alias set in PDR and
 165    NB_PARAMS is the number of parameters in PDR.  */
 166
 167 static void
 168 openscop_print_pdr_powerset (FILE *file,
 169                              ppl_Pointset_Powerset_C_Polyhedron_t ps,
 170                              int nb_subscripts,
 171                              int alias_set_dim,
 172                              int nb_params)
 173 {
 174   size_t nb_disjuncts;
 175   ppl_Pointset_Powerset_C_Polyhedron_iterator_t it, end;
 176
 177   ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&it);
 178   ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&end);
 179
 180   ppl_Pointset_Powerset_C_Polyhedron_size (ps, &nb_disjuncts);
 181   fprintf (file, "%d\n", (int) nb_disjuncts);
 182
 183   for (ppl_Pointset_Powerset_C_Polyhedron_iterator_begin (ps, it),
 184        ppl_Pointset_Powerset_C_Polyhedron_iterator_end (ps, end);
 185        !ppl_Pointset_Powerset_C_Polyhedron_iterator_equal_test (it, end);
 186        ppl_Pointset_Powerset_C_Polyhedron_iterator_increment (it))
 187     {
 188       ppl_const_Polyhedron_t ph;
 189
 190       ppl_Pointset_Powerset_C_Polyhedron_iterator_dereference (it, &ph);
 191       openscop_print_pdr_polyhedron (file, ph, nb_subscripts, alias_set_dim,
 192                                      nb_params);
 193     }
 194
 195   ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (it);
 196   ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (end);
 197 }
 198
 199 /* Print to FILE the powerset PS in its OpenScop matrix form.  */
 200
 201 static void
 202 openscop_print_powerset_matrix (FILE *file,
 203                                 ppl_Pointset_Powerset_C_Polyhedron_t ps,
 204                                 int output, int input, int locals,
 205                                 int params)
 206 {
 207   size_t nb_disjuncts;
 208   ppl_Pointset_Powerset_C_Polyhedron_iterator_t it, end;
 209
 210   ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&it);
 211   ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&end);
 212
 213   ppl_Pointset_Powerset_C_Polyhedron_size (ps, &nb_disjuncts);
 214   fprintf (file, "%d\n", (int) nb_disjuncts);
 215
 216   for (ppl_Pointset_Powerset_C_Polyhedron_iterator_begin (ps, it),
 217        ppl_Pointset_Powerset_C_Polyhedron_iterator_end (ps, end);
 218        !ppl_Pointset_Powerset_C_Polyhedron_iterator_equal_test (it, end);
 219        ppl_Pointset_Powerset_C_Polyhedron_iterator_increment (it))
 220     {
 221       ppl_const_Polyhedron_t ph;
 222
 223       ppl_Pointset_Powerset_C_Polyhedron_iterator_dereference (it, &ph);
 224       openscop_print_polyhedron_matrix (file, ph, output, input, locals,
 225                                         params);
 226     }
 227
 228   ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (it);
 229   ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (end);
 230 }
 231
 232 /* Prints to FILE the scattering function of PBB in OpenScop format, at some
 233    VERBOSITY level.  */
 234
 235 static void
 236 openscop_print_scattering_function_1 (FILE *file, poly_bb_p pbb, int verbosity)
 237 {
 238   graphite_dim_t i;
 239   ppl_const_Polyhedron_t ph;
 240
 241   if (verbosity > 0)
 242     {
 243       fprintf (file, "# scattering bb_%d (\n", pbb_index (pbb));
 244       fprintf (file, "#eq");
 245
 246       for (i = 0; i < pbb_nb_scattering_transform (pbb); i++)
 247         fprintf (file, "     s%d", (int) i);
 248
 249       for (i = 0; i < pbb_nb_local_vars (pbb); i++)
 250         fprintf (file, "    lv%d", (int) i);
 251
 252       for (i = 0; i < pbb_dim_iter_domain (pbb); i++)
 253         fprintf (file, "     i%d", (int) i);
 254
 255       for (i = 0; i < pbb_nb_params (pbb); i++)
 256         fprintf (file, "     p%d", (int) i);
 257
 258       fprintf (file, "    cst\n");
 259     }
 260
 261   /* Number of disjunct components.  Remove this when
 262      PBB_TRANSFORMED_SCATTERING will be a pointset_powerset.  */
 263   fprintf (file, "1\n");
 264
 265   ph = PBB_TRANSFORMED_SCATTERING (pbb)
 266     ? PBB_TRANSFORMED_SCATTERING (pbb)
 267     : PBB_ORIGINAL_SCATTERING (pbb);
 268
 269   openscop_print_polyhedron_matrix (file, ph,
 270                                     pbb_nb_scattering_transform (pbb),
 271                                     pbb_dim_iter_domain (pbb),
 272                                     pbb_nb_local_vars (pbb),
 273                                     pbb_nb_params (pbb));
 274
 275   if (verbosity > 0)
 276     fprintf (file, "#)\n");
 277 }
 278
 279 /* Prints to FILE the scattering function of PBB, at some VERBOSITY
 280    level.  */
 281
 282 static void
 283 print_scattering_function_1 (FILE *file, poly_bb_p pbb, int verbosity)
 284 {
 285   graphite_dim_t i;
 286
 287   if (verbosity > 0)
 288     {
 289       fprintf (file, "# scattering bb_%d (\n", pbb_index (pbb));
 290       fprintf (file, "#eq");
 291
 292       for (i = 0; i < pbb_nb_scattering_transform (pbb); i++)
 293         fprintf (file, "     s%d", (int) i);
 294
 295       for (i = 0; i < pbb_nb_local_vars (pbb); i++)
 296         fprintf (file, "    lv%d", (int) i);
 297
 298       for (i = 0; i < pbb_dim_iter_domain (pbb); i++)
 299         fprintf (file, "     i%d", (int) i);
 300
 301       for (i = 0; i < pbb_nb_params (pbb); i++)
 302         fprintf (file, "     p%d", (int) i);
 303
 304       fprintf (file, "    cst\n");
 305     }
 306
 307   /* Number of disjunct components.  Remove this when
 308      PBB_TRANSFORMED_SCATTERING will be a pointset_powerset.  */
 309   fprintf (file, "1\n");
 310   ppl_print_polyhedron_matrix (file, PBB_TRANSFORMED_SCATTERING (pbb)
 311                                ? PBB_TRANSFORMED_SCATTERING (pbb)
 312                                : PBB_ORIGINAL_SCATTERING (pbb));
 313
 314   if (verbosity > 0)
 315     fprintf (file, "#)\n");
 316 }
 317
 318 /* Prints to FILE the scattering function of PBB, at some VERBOSITY
 319    level.  */
 320
 321 void
 322 print_scattering_function (FILE *file, poly_bb_p pbb, int verbosity)
 323 {
 324   if (!PBB_TRANSFORMED (pbb))
 325     return;
 326
 327   if (PBB_TRANSFORMED_SCATTERING (pbb)
 328       || PBB_ORIGINAL_SCATTERING (pbb))
 329     {
 330       if (verbosity > 0)
 331         fprintf (file, "# Scattering function is provided\n");
 332
 333       fprintf (file, "1\n");
 334     }
 335   else
 336     {
 337       if (verbosity > 0)
 338         fprintf (file, "# Scattering function is not provided\n");
 339
 340       fprintf (file, "0\n");
 341       return;
 342     }
 343
 344   openscop_print_scattering_function_1 (file, pbb, verbosity);
 345
 346   if (verbosity > 0)
 347     fprintf (file, "# Scattering names are not provided\n");
 348
 349   fprintf (file, "0\n");
 350
 351 }
 352
 353 /* Prints to FILE the iteration domain of PBB, at some VERBOSITY
 354    level.  */
 355
 356 void
 357 print_iteration_domain (FILE *file, poly_bb_p pbb, int verbosity)
 358 {
 359   print_pbb_domain (file, pbb, verbosity);
 360 }
 361
 362 /* Prints to FILE the scattering functions of every PBB of SCOP.  */
 363
 364 void
 365 print_scattering_functions (FILE *file, scop_p scop, int verbosity)
 366 {
 367   int i;
 368   poly_bb_p pbb;
 369
 370   FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
 371     print_scattering_function (file, pbb, verbosity);
 372 }
 373
 374 /* Prints to FILE the iteration domains of every PBB of SCOP, at some
 375    VERBOSITY level.  */
 376
 377 void
 378 print_iteration_domains (FILE *file, scop_p scop, int verbosity)
 379 {
 380   int i;
 381   poly_bb_p pbb;
 382
 383   FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
 384     print_iteration_domain (file, pbb, verbosity);
 385 }
 386
 387 /* Prints to STDERR the scattering function of PBB, at some VERBOSITY
 388    level.  */
 389
 390 DEBUG_FUNCTION void
 391 debug_scattering_function (poly_bb_p pbb, int verbosity)
 392 {
 393   print_scattering_function (stderr, pbb, verbosity);
 394 }
 395
 396 /* Prints to STDERR the iteration domain of PBB, at some VERBOSITY
 397    level.  */
 398
 399 DEBUG_FUNCTION void
 400 debug_iteration_domain (poly_bb_p pbb, int verbosity)
 401 {
 402   print_iteration_domain (stderr, pbb, verbosity);
 403 }
 404
 405 /* Prints to STDERR the scattering functions of every PBB of SCOP, at
 406    some VERBOSITY level.  */
 407
 408 DEBUG_FUNCTION void
 409 debug_scattering_functions (scop_p scop, int verbosity)
 410 {
 411   print_scattering_functions (stderr, scop, verbosity);
 412 }
 413
 414 /* Prints to STDERR the iteration domains of every PBB of SCOP, at
 415    some VERBOSITY level.  */
 416
 417 DEBUG_FUNCTION void
 418 debug_iteration_domains (scop_p scop, int verbosity)
 419 {
 420   print_iteration_domains (stderr, scop, verbosity);
 421 }
 422
 423 /* Read N integer from FILE.  */
 424
 425 int *
 426 openscop_read_N_int (FILE *file, int N)
 427 {
 428   char s[OPENSCOP_MAX_STRING];
 429   char *str;
 430   int i, *res = (int *) xmalloc (OPENSCOP_MAX_STRING * sizeof (int));
 431
 432   /* Skip blank and commented lines.  */
 433   while (fgets (s, sizeof s, file) == (char *) 0
 434          || s[0] == '#'
 435          || ISSPACE (s[0]))
 436     ;
 437
 438   str = s;
 439
 440   for (i = 0; i < N; i++)
 441     {
 442       sscanf (str, "%d", &res[i]);
 443
 444       /* Jump the integer that was read.  */
 445       while ((*str) && !ISSPACE (*str) && (*str != '#'))
 446         str++;
 447
 448       /* Jump spaces.  */
 449       while ((*str) && ISSPACE (*str) && (*str != '#'))
 450         str++;
 451     }
 452
 453   return res;
 454 }
 455
 456 /* Read one integer from FILE.  */
 457
 458 static int
 459 openscop_read_one_int (FILE *file)
 460 {
 461   int *x = openscop_read_N_int (file, 1);
 462   int res = *x;
 463
 464   free (x);
 465   return res;
 466 }
 467
 468 /* Read N string from FILE.  */
 469
 470 static char *
 471 openscop_read_N_string (FILE *file, int N)
 472 {
 473   int count, i;
 474   char str[OPENSCOP_MAX_STRING];
 475   char *tmp = (char *) xmalloc (sizeof (char) * OPENSCOP_MAX_STRING);
 476   char *s = NULL;
 477
 478   /* Skip blank and commented lines.  */
 479   while (fgets (str, sizeof str, file) == (char *) 0
 480          || str[0] == '#'
 481          || ISSPACE (str[0]))
 482     ;
 483
 484   s = str;
 485   count = 0;
 486
 487   for (i = 0; i < N; i++)
 488     {
 489       /* Read the first word.  */
 490       for (; (*s) && (!ISSPACE (*s)) && (*s != '#'); ++count)
 491         tmp[count] = *(s++);
 492
 493       tmp[count] = ' ';
 494       count++;
 495
 496       /* Jump spaces.  */
 497       while ((*s) && ISSPACE (*s) && (*s != '#'))
 498         s++;
 499     }
 500
 501   tmp[count-1] = '\0';
 502
 503   return tmp;
 504 }
 505
 506 /* Read one string from FILE.  */
 507
 508 static char *
 509 openscop_read_one_string (FILE *file)
 510 {
 511   return openscop_read_N_string (file, 1);
 512 }
 513
 514 /* Read from FILE the powerset PS in its OpenScop matrix form.  OUTPUT is the
 515    number of output dimensions, INPUT is the number of input dimensions,
 516    LOCALS is the number of existentially quantified variables and PARAMS is
 517    the number of parameters.  */
 518
 519 static void
 520 openscop_read_powerset_matrix (FILE *file,
 521                                ppl_Pointset_Powerset_C_Polyhedron_t *ps,
 522                                int *output, int *input, int *locals,
 523                                int *params)
 524 {
 525   int nb_disjuncts, i;
 526
 527   nb_disjuncts = openscop_read_one_int (file);
 528
 529   for (i = 0; i < nb_disjuncts; i++)
 530     {
 531       ppl_Polyhedron_t ph;
 532
 533       openscop_read_polyhedron_matrix (file, &ph, output, input, locals,
 534                                        params);
 535       if (!ph)
 536         *ps = NULL;
 537       else if (i == 0)
 538         ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (ps, ph);
 539       else
 540         ppl_Pointset_Powerset_C_Polyhedron_add_disjunct (*ps, ph);
 541     }
 542 }
 543
 544 /* Read a scattering function from FILE and save it to PBB.  Return whether
 545    the scattering function was provided or not.  */
 546
 547 static bool
 548 graphite_read_scatt (FILE *file, poly_bb_p pbb)
 549 {
 550   bool scattering_provided = false;
 551   int output, input, locals, params;
 552   ppl_Polyhedron_t newp;
 553
 554   if (openscop_read_one_int (file) > 0)
 555     {
 556       /* Read number of disjunct components.  */
 557       openscop_read_one_int (file);
 558
 559       /* Read scattering function.  */
 560       openscop_read_polyhedron_matrix (file, &newp, &output, &input,
 561                                        &locals, &params);
 562       store_scattering (PBB_SCOP (pbb));
 563       PBB_TRANSFORMED (pbb) = poly_scattering_new ();
 564       PBB_TRANSFORMED_SCATTERING (pbb) = newp;
 565       PBB_NB_LOCAL_VARIABLES (pbb) = locals;
 566
 567       /* New scattering dimension.  */
 568       PBB_NB_SCATTERING_TRANSFORM (pbb) = output;
 569
 570       scattering_provided = true;
 571     }
 572
 573   return scattering_provided;
 574 }
 575
 576 /* Read a scop file.  Return true if the scop is transformed.  */
 577
 578 static bool
 579 graphite_read_scop_file (FILE *file, scop_p scop)
 580 {
 581   char *tmp, *language;
 582   size_t i, j, nb_statements, nbr, nbw;
 583   int input, output, locals, params;
 584   ppl_Pointset_Powerset_C_Polyhedron_t ps;
 585   poly_bb_p pbb;
 586   bool transform_done = false;
 587
 588   /* Ensure that the file is in OpenScop format.  */
 589   tmp = openscop_read_N_string (file, 2);
 590
 591   if (strcmp (tmp, "SCoP 1"))
 592     {
 593       error ("the file is not in OpenScop format");
 594       return false;
 595     }
 596
 597   free (tmp);
 598
 599   /* Read the language.  */
 600   language = openscop_read_one_string (file);
 601
 602   if (strcmp (language, "Gimple"))
 603     {
 604       error ("the language is not recognized");
 605       return false;
 606     }
 607
 608   free (language);
 609
 610   /* Read the context but do not use it.  */
 611   openscop_read_powerset_matrix (file, &ps, &input, &output, &locals, &params);
 612
 613   if ((size_t) params != scop->nb_params)
 614     {
 615       error ("parameters number in the scop file is different from the"
 616              " internal scop parameter number");
 617       return false;
 618     }
 619
 620   /* Read parameter names if provided.  */
 621   if (openscop_read_one_int (file))
 622     openscop_read_N_string (file, scop->nb_params);
 623
 624   nb_statements = openscop_read_one_int (file);
 625
 626   if (nb_statements != VEC_length (poly_bb_p, SCOP_BBS (scop)))
 627     {
 628       error ("number of statements in the OpenScop file does not match"
 629              " the graphite internal statements number");
 630       return false;
 631     }
 632
 633   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
 634     {
 635       /* Read iteration domain.  */
 636       openscop_read_powerset_matrix (file, &ps, &input, &output, &locals,
 637                                      &params);
 638
 639       /* Read scattering.  */
 640       transform_done = graphite_read_scatt (file, pbb);
 641
 642       /* Scattering names.  */
 643       openscop_read_one_int (file);
 644
 645       /* Read access functions.  */
 646       if (openscop_read_one_int (file) > 0)
 647         {
 648           nbr = openscop_read_one_int (file);
 649
 650           /* Read access functions.  */
 651           for (j = 0; j < nbr; j++)
 652             openscop_read_powerset_matrix (file, &ps, &input, &output, &locals,
 653                                            &params);
 654
 655           nbw = openscop_read_one_int (file);
 656
 657           /* Write access functions.  */
 658           for (j = 0; j < nbw; j++)
 659             openscop_read_powerset_matrix (file, &ps, &input, &output, &locals,
 660                                            &params);
 661         }
 662
 663       /* Statement body.  */
 664       openscop_read_one_int (file);
 665     }
 666
 667   return transform_done;
 668 }
 669
 670 /* Initialize and return a file that will be used to write a scop.  SCOP_NUMBER
 671    is a sequential number (identifier) used to differentiate scop files.
 672    Examples of the generated file names: dump_base_name.0.graphite,
 673    dump_base_name.1.graphite, dump_base_name.2.graphite, etc.  */
 674
 675 static FILE *
 676 init_graphite_out_file (int scop_number)
 677 {
 678   FILE *graphite_out_file;
 679   int len = strlen (dump_base_name);
 680   char *dumpname = XNEWVEC (char, len + 25);
 681   char *s_scop_number = XNEWVEC (char, 15);
 682
 683   memcpy (dumpname, dump_base_name, len + 1);
 684   strip_off_ending (dumpname, len);
 685   sprintf (s_scop_number, ".%d", scop_number);
 686   strcat (dumpname, s_scop_number);
 687   strcat (dumpname, ".graphite");
 688   graphite_out_file = fopen (dumpname, "w+b");
 689
 690   if (graphite_out_file == 0)
 691     fatal_error ("can%'t open %s for writing: %m", dumpname);
 692
 693   free (dumpname);
 694
 695   return graphite_out_file;
 696 }
 697
 698 /* Open and return a file used for scop reading.  SCOP_NUMBER is a sequential
 699    number (identifier) used to differentiate scop files.  Examples of the
 700    generated file names: dump_base_name.0.graphite, dump_base_name.1.graphite,
 701    dump_base_name.2.graphite, etc.  */
 702
 703 static FILE *
 704 init_graphite_in_file (int scop_number)
 705 {
 706   FILE *graphite_in_file;
 707   int len = strlen (dump_base_name);
 708   char *dumpname = XNEWVEC (char, len + 25);
 709   char *s_scop_number = XNEWVEC (char, 15);
 710
 711   memcpy (dumpname, dump_base_name, len + 1);
 712   strip_off_ending (dumpname, len);
 713   sprintf (s_scop_number, ".%d", scop_number);
 714   strcat (dumpname, s_scop_number);
 715   strcat (dumpname, ".graphite");
 716   graphite_in_file = fopen (dumpname, "r+b");
 717
 718   if (graphite_in_file == 0)
 719     fatal_error ("can%'t open %s for reading: %m", dumpname);
 720
 721   free (dumpname);
 722
 723   return graphite_in_file;
 724 }
 725
 726 /* Apply graphite transformations to all the basic blocks of SCOP.  */
 727
 728 bool
 729 apply_poly_transforms (scop_p scop)
 730 {
 731   bool transform_done = false;
 732   FILE *graphite_file;
 733   static size_t file_scop_number = 0;
 734
 735   /* This feature is only enabled in the Graphite branch.  */
 736   if (0)
 737     {
 738       graphite_file = init_graphite_in_file (file_scop_number);
 739       transform_done |= graphite_read_scop_file (graphite_file, scop);
 740
 741       /* We cannot check for the legality of the transform here: there
 742          are cases where graphite_legal_transform cannot determine the
 743          dependence at compile time.  For an example, see the
 744          explanation of why http://gcc.gnu.org/PR45450 is invalid.  */
 745       if (0 && !graphite_legal_transform (scop))
 746         fatal_error ("the graphite file read for scop %d does not contain a legal transform",
 747                      (int) file_scop_number);
 748
 749       file_scop_number++;
 750     }
 751
 752   /* Generate code even if we did not apply any real transformation.
 753      This also allows to check the performance for the identity
 754      transformation: GIMPLE -> GRAPHITE -> GIMPLE
 755      Keep in mind that CLooG optimizes in control, so the loop structure
 756      may change, even if we only use -fgraphite-identity.  */
 757   if (flag_graphite_identity)
 758     transform_done = true;
 759
 760   if (flag_loop_parallelize_all)
 761     transform_done = true;
 762
 763   if (flag_loop_block)
 764     transform_done |= scop_do_block (scop);
 765   else
 766     {
 767       if (flag_loop_strip_mine)
 768         transform_done |= scop_do_strip_mine (scop, 0);
 769
 770       if (flag_loop_interchange)
 771         transform_done |= scop_do_interchange (scop);
 772     }
 773
 774   if (flag_loop_flatten)
 775     transform_done |= flatten_all_loops (scop);
 776
 777   /* This feature is only enabled in the Graphite branch.  */
 778   if (0)
 779     {
 780       graphite_file = init_graphite_out_file (file_scop_number);
 781       print_scop (graphite_file, scop, 1);
 782       file_scop_number++;
 783     }
 784
 785   return transform_done;
 786 }
 787
 788 /* Returns true when it PDR1 is a duplicate of PDR2: same PBB, and
 789    their ACCESSES, TYPE, and NB_SUBSCRIPTS are the same.  */
 790
 791 static inline bool
 792 can_collapse_pdrs (poly_dr_p pdr1, poly_dr_p pdr2)
 793 {
 794   bool res;
 795   ppl_Pointset_Powerset_C_Polyhedron_t af1, af2, diff;
 796
 797   if (PDR_PBB (pdr1) != PDR_PBB (pdr2)
 798       || PDR_NB_SUBSCRIPTS (pdr1) != PDR_NB_SUBSCRIPTS (pdr2)
 799       || PDR_TYPE (pdr1) != PDR_TYPE (pdr2))
 800     return false;
 801
 802   af1 = PDR_ACCESSES (pdr1);
 803   af2 = PDR_ACCESSES (pdr2);
 804   ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
 805     (&diff, af1);
 806   ppl_Pointset_Powerset_C_Polyhedron_difference_assign (diff, af2);
 807
 808   res = ppl_Pointset_Powerset_C_Polyhedron_is_empty (diff);
 809   ppl_delete_Pointset_Powerset_C_Polyhedron (diff);
 810   return res;
 811 }
 812
 813 /* Removes duplicated data references in PBB.  */
 814
 815 void
 816 pbb_remove_duplicate_pdrs (poly_bb_p pbb)
 817 {
 818   int i, j;
 819   poly_dr_p pdr1, pdr2;
 820
 821   FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb), i, pdr1)
 822     for (j = i + 1; VEC_iterate (poly_dr_p, PBB_DRS (pbb), j, pdr2); j++)
 823       if (can_collapse_pdrs (pdr1, pdr2))
 824         {
 825           PDR_NB_REFS (pdr1) += PDR_NB_REFS (pdr2);
 826           free_poly_dr (pdr2);
 827           VEC_ordered_remove (poly_dr_p, PBB_DRS (pbb), j);
 828         }
 829
 830   PBB_PDR_DUPLICATES_REMOVED (pbb) = true;
 831 }
 832
 833 /* Create a new polyhedral data reference and add it to PBB.  It is
 834    defined by its ACCESSES, its TYPE, and the number of subscripts
 835    NB_SUBSCRIPTS.  */
 836
 837 void
 838 new_poly_dr (poly_bb_p pbb, int dr_base_object_set,
 839              ppl_Pointset_Powerset_C_Polyhedron_t accesses,
 840              enum poly_dr_type type, void *cdr, graphite_dim_t nb_subscripts)
 841 {
 842   static int id = 0;
 843   poly_dr_p pdr = XNEW (struct poly_dr);
 844
 845   PDR_ID (pdr) = id++;
 846   PDR_BASE_OBJECT_SET (pdr) = dr_base_object_set;
 847   PDR_NB_REFS (pdr) = 1;
 848   PDR_PBB (pdr) = pbb;
 849   PDR_ACCESSES (pdr) = accesses;
 850   PDR_TYPE (pdr) = type;
 851   PDR_CDR (pdr) = cdr;
 852   PDR_NB_SUBSCRIPTS (pdr) = nb_subscripts;
 853   VEC_safe_push (poly_dr_p, heap, PBB_DRS (pbb), pdr);
 854 }
 855
 856 /* Free polyhedral data reference PDR.  */
 857
 858 void
 859 free_poly_dr (poly_dr_p pdr)
 860 {
 861   ppl_delete_Pointset_Powerset_C_Polyhedron (PDR_ACCESSES (pdr));
 862   XDELETE (pdr);
 863 }
 864
 865 /* Create a new polyhedral black box.  */
 866
 867 poly_bb_p
 868 new_poly_bb (scop_p scop, void *black_box)
 869 {
 870   poly_bb_p pbb = XNEW (struct poly_bb);
 871
 872   PBB_DOMAIN (pbb) = NULL;
 873   PBB_SCOP (pbb) = scop;
 874   pbb_set_black_box (pbb, black_box);
 875   PBB_TRANSFORMED (pbb) = NULL;
 876   PBB_SAVED (pbb) = NULL;
 877   PBB_ORIGINAL (pbb) = NULL;
 878   PBB_DRS (pbb) = VEC_alloc (poly_dr_p, heap, 3);
 879   PBB_IS_REDUCTION (pbb) = false;
 880   PBB_PDR_DUPLICATES_REMOVED (pbb) = false;
 881   GBB_PBB ((gimple_bb_p) black_box) = pbb;
 882
 883   return pbb;
 884 }
 885
 886 /* Free polyhedral black box.  */
 887
 888 void
 889 free_poly_bb (poly_bb_p pbb)
 890 {
 891   int i;
 892   poly_dr_p pdr;
 893
 894   ppl_delete_Pointset_Powerset_C_Polyhedron (PBB_DOMAIN (pbb));
 895
 896   if (PBB_TRANSFORMED (pbb))
 897     poly_scattering_free (PBB_TRANSFORMED (pbb));
 898
 899   if (PBB_SAVED (pbb))
 900     poly_scattering_free (PBB_SAVED (pbb));
 901
 902   if (PBB_ORIGINAL (pbb))
 903     poly_scattering_free (PBB_ORIGINAL (pbb));
 904
 905   if (PBB_DRS (pbb))
 906     FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb), i, pdr)
 907       free_poly_dr (pdr);
 908
 909   VEC_free (poly_dr_p, heap, PBB_DRS (pbb));
 910   XDELETE (pbb);
 911 }
 912
 913 static void
 914 print_pdr_access_layout (FILE *file, poly_bb_p pbb, poly_dr_p pdr)
 915 {
 916   graphite_dim_t i;
 917
 918   fprintf (file, "#  eq");
 919
 920   fprintf (file, "   alias");
 921
 922   for (i = 0; i < PDR_NB_SUBSCRIPTS (pdr); i++)
 923     fprintf (file, "   sub%d", (int) i);
 924
 925   for (i = 0; i < pbb_dim_iter_domain (pbb); i++)
 926     fprintf (file, "     i%d", (int) i);
 927
 928   for (i = 0; i < pbb_nb_params (pbb); i++)
 929     fprintf (file, "     p%d", (int) i);
 930
 931   fprintf (file, "    cst\n");
 932 }
 933
 934 /* Prints to FILE the polyhedral data reference PDR, at some VERBOSITY
 935    level.  */
 936
 937 void
 938 print_pdr (FILE *file, poly_dr_p pdr, int verbosity)
 939 {
 940   int alias_set_dim;
 941
 942   if (verbosity > 1)
 943     {
 944       fprintf (file, "# pdr_%d (", PDR_ID (pdr));
 945
 946       switch (PDR_TYPE (pdr))
 947         {
 948         case PDR_READ:
 949           fprintf (file, "read \n");
 950           break;
 951
 952         case PDR_WRITE:
 953           fprintf (file, "write \n");
 954           break;
 955
 956         case PDR_MAY_WRITE:
 957           fprintf (file, "may_write \n");
 958           break;
 959
 960         default:
 961           gcc_unreachable ();
 962         }
 963
 964       dump_data_reference (file, (data_reference_p) PDR_CDR (pdr));
 965     }
 966
 967   if (verbosity > 0)
 968     {
 969       fprintf (file, "# data accesses (\n");
 970       print_pdr_access_layout (file, PDR_PBB (pdr), pdr);
 971     }
 972
 973   alias_set_dim = pdr_alias_set_dim (pdr) + 1;
 974
 975   openscop_print_pdr_powerset (file,
 976                                PDR_ACCESSES (pdr),
 977                                PDR_NB_SUBSCRIPTS (pdr),
 978                                alias_set_dim,
 979                                pbb_nb_params (PDR_PBB (pdr)));
 980
 981   if (verbosity > 0)
 982     fprintf (file, "#)\n");
 983
 984   if (verbosity > 1)
 985     fprintf (file, "#)\n");
 986 }
 987
 988 /* Prints to STDERR the polyhedral data reference PDR, at some
 989    VERBOSITY level.  */
 990
 991 DEBUG_FUNCTION void
 992 debug_pdr (poly_dr_p pdr, int verbosity)
 993 {
 994   print_pdr (stderr, pdr, verbosity);
 995 }
 996
 997 /* Creates a new SCOP containing REGION.  */
 998
 999 scop_p
1000 new_scop (void *region)
1001 {
1002   scop_p scop = XNEW (struct scop);
1003
1004   SCOP_CONTEXT (scop) = NULL;
1005   scop_set_region (scop, region);
1006   SCOP_BBS (scop) = VEC_alloc (poly_bb_p, heap, 3);
1007   SCOP_ORIGINAL_PDDRS (scop) = htab_create (10, hash_poly_ddr_p,
1008                                             eq_poly_ddr_p, free_poly_ddr);
1009   SCOP_ORIGINAL_SCHEDULE (scop) = NULL;
1010   SCOP_TRANSFORMED_SCHEDULE (scop) = NULL;
1011   SCOP_SAVED_SCHEDULE (scop) = NULL;
1012   POLY_SCOP_P (scop) = false;
1013
1014   return scop;
1015 }
1016
1017 /* Deletes SCOP.  */
1018
1019 void
1020 free_scop (scop_p scop)
1021 {
1022   int i;
1023   poly_bb_p pbb;
1024
1025   FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
1026     free_poly_bb (pbb);
1027
1028   VEC_free (poly_bb_p, heap, SCOP_BBS (scop));
1029
1030   if (SCOP_CONTEXT (scop))
1031     ppl_delete_Pointset_Powerset_C_Polyhedron (SCOP_CONTEXT (scop));
1032
1033   htab_delete (SCOP_ORIGINAL_PDDRS (scop));
1034   free_lst (SCOP_ORIGINAL_SCHEDULE (scop));
1035   free_lst (SCOP_TRANSFORMED_SCHEDULE (scop));
1036   free_lst (SCOP_SAVED_SCHEDULE (scop));
1037   XDELETE (scop);
1038 }
1039
1040 /* Print to FILE the domain of PBB in OpenScop format, at some VERBOSITY
1041    level.  */
1042
1043 static void
1044 openscop_print_pbb_domain (FILE *file, poly_bb_p pbb, int verbosity)
1045 {
1046   graphite_dim_t i;
1047   gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
1048
1049   if (!PBB_DOMAIN (pbb))
1050     return;
1051
1052   if (verbosity > 0)
1053     {
1054       fprintf (file, "\n# Iteration domain of bb_%d (\n", GBB_BB (gbb)->index);
1055       fprintf (file, "#eq");
1056
1057       for (i = 0; i < pbb_dim_iter_domain (pbb); i++)
1058         fprintf (file, "     i%d", (int) i);
1059
1060       for (i = 0; i < pbb_nb_params (pbb); i++)
1061         fprintf (file, "     p%d", (int) i);
1062
1063       fprintf (file, "    cst\n");
1064     }
1065
1066   if (PBB_DOMAIN (pbb))
1067     openscop_print_powerset_matrix (file, PBB_DOMAIN (pbb),
1068                                     pbb_dim_iter_domain (pbb),
1069                                     0,
1070                                     0,
1071                                     pbb_nb_params (pbb));
1072   else
1073     fprintf (file, "0\n");
1074
1075   if (verbosity > 0)
1076     fprintf (file, "#)\n");
1077 }
1078
1079 /* Print to FILE the domain of PBB, at some VERBOSITY level.  */
1080
1081 void
1082 print_pbb_domain (FILE *file, poly_bb_p pbb, int verbosity)
1083 {
1084   graphite_dim_t i;
1085   gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
1086
1087   if (!PBB_DOMAIN (pbb))
1088     return;
1089
1090   if (verbosity > 0)
1091     {
1092       fprintf (file, "# Iteration domain of bb_%d (\n", GBB_BB (gbb)->index);
1093       fprintf (file, "#  eq");
1094
1095       for (i = 0; i < pbb_dim_iter_domain (pbb); i++)
1096         fprintf (file, "     i%d", (int) i);
1097
1098       for (i = 0; i < pbb_nb_params (pbb); i++)
1099         fprintf (file, "     p%d", (int) i);
1100
1101       fprintf (file, "    cst\n");
1102     }
1103
1104   if (PBB_DOMAIN (pbb))
1105     ppl_print_powerset_matrix (file, PBB_DOMAIN (pbb));
1106   else
1107     fprintf (file, "0\n");
1108
1109   if (verbosity > 0)
1110     fprintf (file, "#)\n");
1111 }
1112
1113 /* Dump the cases of a graphite basic block GBB on FILE.  */
1114
1115 static void
1116 dump_gbb_cases (FILE *file, gimple_bb_p gbb)
1117 {
1118   int i;
1119   gimple stmt;
1120   VEC (gimple, heap) *cases;
1121
1122   if (!gbb)
1123     return;
1124
1125   cases = GBB_CONDITION_CASES (gbb);
1126   if (VEC_empty (gimple, cases))
1127     return;
1128
1129   fprintf (file, "# cases bb_%d (\n", GBB_BB (gbb)->index);
1130
1131   FOR_EACH_VEC_ELT (gimple, cases, i, stmt)
1132     {
1133       fprintf (file, "# ");
1134       print_gimple_stmt (file, stmt, 0, 0);
1135     }
1136
1137   fprintf (file, "#)\n");
1138 }
1139
1140 /* Dump conditions of a graphite basic block GBB on FILE.  */
1141
1142 static void
1143 dump_gbb_conditions (FILE *file, gimple_bb_p gbb)
1144 {
1145   int i;
1146   gimple stmt;
1147   VEC (gimple, heap) *conditions;
1148
1149   if (!gbb)
1150     return;
1151
1152   conditions = GBB_CONDITIONS (gbb);
1153   if (VEC_empty (gimple, conditions))
1154     return;
1155
1156   fprintf (file, "# conditions bb_%d (\n", GBB_BB (gbb)->index);
1157
1158   FOR_EACH_VEC_ELT (gimple, conditions, i, stmt)
1159     {
1160       fprintf (file, "# ");
1161       print_gimple_stmt (file, stmt, 0, 0);
1162     }
1163
1164   fprintf (file, "#)\n");
1165 }
1166
1167 /* Print to FILE all the data references of PBB, at some VERBOSITY
1168    level.  */
1169
1170 void
1171 print_pdrs (FILE *file, poly_bb_p pbb, int verbosity)
1172 {
1173   int i;
1174   poly_dr_p pdr;
1175   int nb_reads = 0;
1176   int nb_writes = 0;
1177
1178   if (VEC_length (poly_dr_p, PBB_DRS (pbb)) == 0)
1179     {
1180       if (verbosity > 0)
1181         fprintf (file, "# Access informations are not provided\n");\
1182       fprintf (file, "0\n");
1183       return;
1184     }
1185
1186   if (verbosity > 1)
1187     fprintf (file, "# Data references (\n");
1188
1189   if (verbosity > 0)
1190     fprintf (file, "# Access informations are provided\n");
1191   fprintf (file, "1\n");
1192
1193   FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb), i, pdr)
1194     if (PDR_TYPE (pdr) == PDR_READ)
1195       nb_reads++;
1196     else
1197       nb_writes++;
1198
1199   if (verbosity > 1)
1200     fprintf (file, "# Read data references (\n");
1201
1202   if (verbosity > 0)
1203     fprintf (file, "# Read access informations\n");
1204   fprintf (file, "%d\n", nb_reads);
1205
1206   FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb), i, pdr)
1207     if (PDR_TYPE (pdr) == PDR_READ)
1208       print_pdr (file, pdr, verbosity);
1209
1210   if (verbosity > 1)
1211     fprintf (file, "#)\n");
1212
1213   if (verbosity > 1)
1214     fprintf (file, "# Write data references (\n");
1215
1216   if (verbosity > 0)
1217     fprintf (file, "# Write access informations\n");
1218   fprintf (file, "%d\n", nb_writes);
1219
1220   FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb), i, pdr)
1221     if (PDR_TYPE (pdr) != PDR_READ)
1222       print_pdr (file, pdr, verbosity);
1223
1224   if (verbosity > 1)
1225     fprintf (file, "#)\n");
1226
1227   if (verbosity > 1)
1228     fprintf (file, "#)\n");
1229 }
1230
1231 /* Print to STDERR all the data references of PBB.  */
1232
1233 DEBUG_FUNCTION void
1234 debug_pdrs (poly_bb_p pbb, int verbosity)
1235 {
1236   print_pdrs (stderr, pbb, verbosity);
1237 }
1238
1239 /* Print to FILE the body of PBB, at some VERBOSITY level.
1240    If statement_body_provided is false statement body is not printed.  */
1241
1242 static void
1243 print_pbb_body (FILE *file, poly_bb_p pbb, int verbosity,
1244                 bool statement_body_provided)
1245 {
1246   if (verbosity > 1)
1247     fprintf (file, "# Body (\n");
1248
1249   if (!statement_body_provided)
1250     {
1251       if (verbosity > 0)
1252         fprintf (file, "# Statement body is not provided\n");
1253
1254       fprintf (file, "0\n");
1255
1256       if (verbosity > 1)
1257         fprintf (file, "#)\n");
1258       return;
1259     }
1260
1261   if (verbosity > 0)
1262     fprintf (file, "# Statement body is provided\n");
1263   fprintf (file, "1\n");
1264
1265   if (verbosity > 0)
1266     fprintf (file, "# Original iterator names\n# Iterator names are not provided yet.\n");
1267
1268   if (verbosity > 0)
1269     fprintf (file, "# Statement body\n");
1270
1271   fprintf (file, "{\n");
1272   dump_bb (pbb_bb (pbb), file, 0);
1273   fprintf (file, "}\n");
1274
1275   if (verbosity > 1)
1276     fprintf (file, "#)\n");
1277 }
1278
1279 /* Print to FILE the domain and scattering function of PBB, at some
1280    VERBOSITY level.  */
1281
1282 void
1283 print_pbb (FILE *file, poly_bb_p pbb, int verbosity)
1284 {
1285   if (verbosity > 1)
1286     {
1287       fprintf (file, "# pbb_%d (\n", pbb_index (pbb));
1288       dump_gbb_conditions (file, PBB_BLACK_BOX (pbb));
1289       dump_gbb_cases (file, PBB_BLACK_BOX (pbb));
1290     }
1291
1292   openscop_print_pbb_domain (file, pbb, verbosity);
1293   print_scattering_function (file, pbb, verbosity);
1294   print_pdrs (file, pbb, verbosity);
1295   print_pbb_body (file, pbb, verbosity, false);
1296
1297   if (verbosity > 1)
1298     fprintf (file, "#)\n");
1299 }
1300
1301 /* Print to FILE the parameters of SCOP, at some VERBOSITY level.  */
1302
1303 void
1304 print_scop_params (FILE *file, scop_p scop, int verbosity)
1305 {
1306   int i;
1307   tree t;
1308
1309   if (verbosity > 1)
1310     fprintf (file, "# parameters (\n");
1311
1312   if (VEC_length (tree, SESE_PARAMS (SCOP_REGION (scop))))
1313     {
1314       if (verbosity > 0)
1315         fprintf (file, "# Parameter names are provided\n");
1316
1317       fprintf (file, "1\n");
1318
1319       if (verbosity > 0)
1320         fprintf (file, "# Parameter names\n");
1321     }
1322   else
1323     {
1324       if (verbosity > 0)
1325         fprintf (file, "# Parameter names are not provided\n");
1326       fprintf (file, "0\n");
1327     }
1328
1329   FOR_EACH_VEC_ELT (tree, SESE_PARAMS (SCOP_REGION (scop)), i, t)
1330     {
1331       print_generic_expr (file, t, 0);
1332       fprintf (file, " ");
1333     }
1334
1335   fprintf (file, "\n");
1336
1337   if (verbosity > 1)
1338     fprintf (file, "#)\n");
1339 }
1340
1341 /* Print to FILE the context of SCoP in OpenScop format, at some VERBOSITY
1342    level.  */
1343
1344 static void
1345 openscop_print_scop_context (FILE *file, scop_p scop, int verbosity)
1346 {
1347   graphite_dim_t i;
1348
1349   if (verbosity > 0)
1350     {
1351       fprintf (file, "# Context (\n");
1352       fprintf (file, "#eq");
1353
1354       for (i = 0; i < scop_nb_params (scop); i++)
1355         fprintf (file, "     p%d", (int) i);
1356
1357       fprintf (file, "    cst\n");
1358     }
1359
1360   if (SCOP_CONTEXT (scop))
1361     openscop_print_powerset_matrix (file, SCOP_CONTEXT (scop), 0, 0, 0,
1362                                     scop_nb_params (scop));
1363   else
1364     fprintf (file, "0 %d 0 0 0 %d\n", (int) scop_nb_params (scop) + 2,
1365              (int) scop_nb_params (scop));
1366
1367   if (verbosity > 0)
1368     fprintf (file, "# )\n");
1369 }
1370
1371 /* Print to FILE the context of SCoP, at some VERBOSITY level.  */
1372
1373 void
1374 print_scop_context (FILE *file, scop_p scop, int verbosity)
1375 {
1376   graphite_dim_t i;
1377
1378   if (verbosity > 0)
1379     {
1380       fprintf (file, "# Context (\n");
1381       fprintf (file, "#eq");
1382
1383       for (i = 0; i < scop_nb_params (scop); i++)
1384         fprintf (file, "     p%d", (int) i);
1385
1386       fprintf (file, "    cst\n");
1387     }
1388
1389   if (SCOP_CONTEXT (scop))
1390     ppl_print_powerset_matrix (file, SCOP_CONTEXT (scop));
1391   else
1392     fprintf (file, "0 %d\n", (int) scop_nb_params (scop) + 2);
1393
1394   if (verbosity > 0)
1395     fprintf (file, "# )\n");
1396 }
1397
1398 /* Print to FILE the SCOP, at some VERBOSITY level.  */
1399
1400 void
1401 print_scop (FILE *file, scop_p scop, int verbosity)
1402 {
1403   int i;
1404   poly_bb_p pbb;
1405
1406   fprintf (file, "SCoP 1\n#(\n");
1407   fprintf (file, "# Language\nGimple\n");
1408   openscop_print_scop_context (file, scop, verbosity);
1409   print_scop_params (file, scop, verbosity);
1410
1411   if (verbosity > 0)
1412     fprintf (file, "# Number of statements\n");
1413
1414   fprintf (file, "%d\n",VEC_length (poly_bb_p, SCOP_BBS (scop)));
1415
1416   FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
1417     print_pbb (file, pbb, verbosity);
1418
1419   if (verbosity > 1)
1420     {
1421       fprintf (file, "# original_lst (\n");
1422       print_lst (file, SCOP_ORIGINAL_SCHEDULE (scop), 0);
1423       fprintf (file, "\n#)\n");
1424
1425       fprintf (file, "# transformed_lst (\n");
1426       print_lst (file, SCOP_TRANSFORMED_SCHEDULE (scop), 0);
1427       fprintf (file, "\n#)\n");
1428     }
1429
1430   fprintf (file, "#)\n");
1431 }
1432
1433 /* Print to FILE the input file that CLooG would expect as input, at
1434    some VERBOSITY level.  */
1435
1436 void
1437 print_cloog (FILE *file, scop_p scop, int verbosity)
1438 {
1439   int i;
1440   poly_bb_p pbb;
1441
1442   fprintf (file, "# SCoP (generated by GCC/Graphite\n");
1443   if (verbosity > 0)
1444     fprintf (file, "# CLooG output language\n");
1445   fprintf (file, "c\n");
1446
1447   print_scop_context (file, scop, verbosity);
1448   print_scop_params (file, scop, verbosity);
1449
1450   if (verbosity > 0)
1451     fprintf (file, "# Number of statements\n");
1452
1453   fprintf (file, "%d\n", VEC_length (poly_bb_p, SCOP_BBS (scop)));
1454
1455   FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
1456     {
1457       if (verbosity > 1)
1458         fprintf (file, "# pbb_%d (\n", pbb_index (pbb));
1459
1460       print_pbb_domain (file, pbb, verbosity);
1461       fprintf (file, "0 0 0");
1462
1463       if (verbosity > 0)
1464         fprintf (file, "# For future CLooG options.\n");
1465       else
1466         fprintf (file, "\n");
1467
1468       if (verbosity > 1)
1469         fprintf (file, "#)\n");
1470     }
1471
1472   fprintf (file, "0");
1473   if (verbosity > 0)
1474     fprintf (file, "# Don't set the iterator names.\n");
1475   else
1476     fprintf (file, "\n");
1477
1478   if (verbosity > 0)
1479     fprintf (file, "# Number of scattering functions\n");
1480
1481   fprintf (file, "%d\n", VEC_length (poly_bb_p, SCOP_BBS (scop)));
1482   unify_scattering_dimensions (scop);
1483
1484   FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
1485     {
1486       if (!PBB_TRANSFORMED (pbb)
1487           || !(PBB_TRANSFORMED_SCATTERING (pbb)
1488                || PBB_ORIGINAL_SCATTERING (pbb)))
1489         continue;
1490
1491       if (verbosity > 1)
1492         fprintf (file, "# pbb_%d (\n", pbb_index (pbb));
1493
1494       print_scattering_function_1 (file, pbb, verbosity);
1495
1496       if (verbosity > 1)
1497         fprintf (file, "#)\n");
1498     }
1499
1500   fprintf (file, "0");
1501   if (verbosity > 0)
1502     fprintf (file, "# Don't set the scattering dimension names.\n");
1503   else
1504     fprintf (file, "\n");
1505
1506   fprintf (file, "#)\n");
1507 }
1508
1509 /* Print to STDERR the domain of PBB, at some VERBOSITY level.  */
1510
1511 DEBUG_FUNCTION void
1512 debug_pbb_domain (poly_bb_p pbb, int verbosity)
1513 {
1514   print_pbb_domain (stderr, pbb, verbosity);
1515 }
1516
1517 /* Print to FILE the domain and scattering function of PBB, at some
1518    VERBOSITY level.  */
1519
1520 DEBUG_FUNCTION void
1521 debug_pbb (poly_bb_p pbb, int verbosity)
1522 {
1523   print_pbb (stderr, pbb, verbosity);
1524 }
1525
1526 /* Print to STDERR the context of SCOP, at some VERBOSITY level.  */
1527
1528 DEBUG_FUNCTION void
1529 debug_scop_context (scop_p scop, int verbosity)
1530 {
1531   print_scop_context (stderr, scop, verbosity);
1532 }
1533
1534 /* Print to STDERR the SCOP, at some VERBOSITY level.  */
1535
1536 DEBUG_FUNCTION void
1537 debug_scop (scop_p scop, int verbosity)
1538 {
1539   print_scop (stderr, scop, verbosity);
1540 }
1541
1542 /* Print to STDERR the SCOP under CLooG format, at some VERBOSITY
1543    level.  */
1544
1545 DEBUG_FUNCTION void
1546 debug_cloog (scop_p scop, int verbosity)
1547 {
1548   print_cloog (stderr, scop, verbosity);
1549 }
1550
1551 /* Print to STDERR the parameters of SCOP, at some VERBOSITY
1552    level.  */
1553
1554 DEBUG_FUNCTION void
1555 debug_scop_params (scop_p scop, int verbosity)
1556 {
1557   print_scop_params (stderr, scop, verbosity);
1558 }
1559
1560
1561 /* The dimension in the transformed scattering polyhedron of PBB
1562    containing the scattering iterator for the loop at depth LOOP_DEPTH.  */
1563
1564 ppl_dimension_type
1565 psct_scattering_dim_for_loop_depth (poly_bb_p pbb, graphite_dim_t loop_depth)
1566 {
1567   ppl_const_Constraint_System_t pcs;
1568   ppl_Constraint_System_const_iterator_t cit, cend;
1569   ppl_const_Constraint_t cstr;
1570   ppl_Polyhedron_t ph = PBB_TRANSFORMED_SCATTERING (pbb);
1571   ppl_dimension_type iter = psct_iterator_dim (pbb, loop_depth);
1572   ppl_Linear_Expression_t expr;
1573   ppl_Coefficient_t coef;
1574   mpz_t val;
1575   graphite_dim_t i;
1576
1577   mpz_init (val);
1578   ppl_new_Coefficient (&coef);
1579   ppl_Polyhedron_get_constraints (ph, &pcs);
1580   ppl_new_Constraint_System_const_iterator (&cit);
1581   ppl_new_Constraint_System_const_iterator (&cend);
1582
1583   for (ppl_Constraint_System_begin (pcs, cit),
1584          ppl_Constraint_System_end (pcs, cend);
1585        !ppl_Constraint_System_const_iterator_equal_test (cit, cend);
1586        ppl_Constraint_System_const_iterator_increment (cit))
1587     {
1588       ppl_Constraint_System_const_iterator_dereference (cit, &cstr);
1589       ppl_new_Linear_Expression_from_Constraint (&expr, cstr);
1590       ppl_Linear_Expression_coefficient (expr, iter, coef);
1591       ppl_Coefficient_to_mpz_t (coef, val);
1592
1593       if (mpz_sgn (val) == 0)
1594         {
1595           ppl_delete_Linear_Expression (expr);
1596           continue;
1597         }
1598
1599       for (i = 0; i < pbb_nb_scattering_transform (pbb); i++)
1600         {
1601           ppl_dimension_type scatter = psct_scattering_dim (pbb, i);
1602
1603           ppl_Linear_Expression_coefficient (expr, scatter, coef);
1604           ppl_Coefficient_to_mpz_t (coef, val);
1605
1606           if (mpz_sgn (val) != 0)
1607             {
1608               mpz_clear (val);
1609               ppl_delete_Linear_Expression (expr);
1610               ppl_delete_Coefficient (coef);
1611               ppl_delete_Constraint_System_const_iterator (cit);
1612               ppl_delete_Constraint_System_const_iterator (cend);
1613
1614               return scatter;
1615             }
1616         }
1617     }
1618
1619   gcc_unreachable ();
1620 }
1621
1622 /* Returns the number of iterations RES of the loop around PBB at
1623    time(scattering) dimension TIME_DEPTH.  */
1624
1625 void
1626 pbb_number_of_iterations_at_time (poly_bb_p pbb,
1627                                   graphite_dim_t time_depth,
1628                                   mpz_t res)
1629 {
1630   ppl_Pointset_Powerset_C_Polyhedron_t domain, sctr_lb, sctr_ub;
1631   ppl_dimension_type domain_dim, sctr_dim;
1632   graphite_dim_t dim_iter_domain = pbb_dim_iter_domain (pbb);
1633   ppl_Linear_Expression_t le;
1634   mpz_t lb, ub, diff, one;
1635   int i;
1636
1637   ppl_Polyhedron_space_dimension (PBB_TRANSFORMED_SCATTERING (pbb), &sctr_dim);
1638
1639   ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1640     (&domain, PBB_DOMAIN (pbb));
1641
1642   ppl_Pointset_Powerset_C_Polyhedron_space_dimension (domain, &domain_dim);
1643
1644   mpz_init (diff);
1645   mpz_init (lb);
1646   mpz_init (ub);
1647   mpz_init (one);
1648   mpz_set_si (one, 1);
1649
1650   /* Compute the upper bound on the original iteration domain and add
1651      that upper bound to the scattering.  */
1652   ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1653     (&sctr_ub, PBB_TRANSFORMED_SCATTERING (pbb));
1654   for (i = 0; i < (int) dim_iter_domain; i++)
1655     {
1656       ppl_Linear_Expression_t eq;
1657       ppl_Constraint_t pc;
1658       ppl_Constraint_System_t cs;
1659       ppl_Polyhedron_t ph;
1660       ppl_Pointset_Powerset_C_Polyhedron_t pph;
1661
1662       ppl_new_Linear_Expression_with_dimension (&le, domain_dim);
1663       ppl_set_coef (le, i, 1);
1664       ppl_min_for_le_pointset (domain, le, lb);
1665       ppl_max_for_le_pointset (domain, le, ub);
1666       mpz_sub (diff, ub, lb);
1667       mpz_add (diff, diff, one);
1668
1669       ppl_new_Linear_Expression_with_dimension (&eq, sctr_dim);
1670       ppl_set_coef (eq, psct_iterator_dim (pbb, i), -1);
1671       ppl_set_inhomogeneous_gmp (eq, diff);
1672
1673       ppl_new_Constraint (&pc, eq, PPL_CONSTRAINT_TYPE_EQUAL);
1674       ppl_new_Constraint_System_from_Constraint (&cs, pc);
1675       ppl_new_C_Polyhedron_from_Constraint_System (&ph, cs);
1676       ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&pph, ph);
1677       ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (sctr_ub, pph);
1678
1679       ppl_delete_Linear_Expression (le);
1680       ppl_delete_Linear_Expression (eq);
1681       ppl_delete_Polyhedron (ph);
1682       ppl_delete_Pointset_Powerset_C_Polyhedron (pph);
1683       ppl_delete_Constraint (pc);
1684       ppl_delete_Constraint_System (cs);
1685     }
1686
1687   /* Compute the lower bound on the original iteration domain and add
1688      it to the scattering.  */
1689   ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1690     (&sctr_lb, PBB_TRANSFORMED_SCATTERING (pbb));
1691   for (i = 0; i < (int) dim_iter_domain; i++)
1692     {
1693       ppl_Linear_Expression_t eq;
1694       ppl_Constraint_t pc;
1695       ppl_Constraint_System_t cs;
1696       ppl_Polyhedron_t ph;
1697       ppl_Pointset_Powerset_C_Polyhedron_t pph;
1698
1699       ppl_new_Linear_Expression_with_dimension (&le, domain_dim);
1700       ppl_set_coef (le, i, 1);
1701       ppl_min_for_le_pointset (domain, le, lb);
1702
1703       ppl_new_Linear_Expression_with_dimension (&eq, sctr_dim);
1704       ppl_set_coef (eq, psct_iterator_dim (pbb, i), -1);
1705       ppl_set_inhomogeneous_gmp (eq, lb);
1706
1707       ppl_new_Constraint (&pc, eq, PPL_CONSTRAINT_TYPE_EQUAL);
1708       ppl_new_Constraint_System_from_Constraint (&cs, pc);
1709       ppl_new_C_Polyhedron_from_Constraint_System (&ph, cs);
1710       ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&pph, ph);
1711       ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (sctr_lb, pph);
1712
1713       ppl_delete_Linear_Expression (le);
1714       ppl_delete_Linear_Expression (eq);
1715       ppl_delete_Polyhedron (ph);
1716       ppl_delete_Pointset_Powerset_C_Polyhedron (pph);
1717       ppl_delete_Constraint (pc);
1718       ppl_delete_Constraint_System (cs);
1719     }
1720
1721   /* Extract the number of iterations.  */
1722   ppl_new_Linear_Expression_with_dimension (&le, sctr_dim);
1723   ppl_set_coef (le, time_depth, 1);
1724   ppl_min_for_le_pointset (sctr_lb, le, lb);
1725   ppl_max_for_le_pointset (sctr_ub, le, ub);
1726   mpz_sub (res, ub, lb);
1727
1728   mpz_clear (one);
1729   mpz_clear (diff);
1730   mpz_clear (lb);
1731   mpz_clear (ub);
1732   ppl_delete_Linear_Expression (le);
1733   ppl_delete_Pointset_Powerset_C_Polyhedron (sctr_ub);
1734   ppl_delete_Pointset_Powerset_C_Polyhedron (sctr_lb);
1735   ppl_delete_Pointset_Powerset_C_Polyhedron (domain);
1736 }
1737
1738 /* Translates LOOP to LST.  */
1739
1740 static lst_p
1741 loop_to_lst (loop_p loop, VEC (poly_bb_p, heap) *bbs, int *i)
1742 {
1743   poly_bb_p pbb;
1744   VEC (lst_p, heap) *seq = VEC_alloc (lst_p, heap, 5);
1745
1746   for (; VEC_iterate (poly_bb_p, bbs, *i, pbb); (*i)++)
1747     {
1748       lst_p stmt;
1749       basic_block bb = GBB_BB (PBB_BLACK_BOX (pbb));
1750
1751       if (bb->loop_father == loop)
1752         stmt = new_lst_stmt (pbb);
1753       else if (flow_bb_inside_loop_p (loop, bb))
1754         {
1755           loop_p next = loop->inner;
1756
1757           while (next && !flow_bb_inside_loop_p (next, bb))
1758             next = next->next;
1759
1760           stmt = loop_to_lst (next, bbs, i);
1761         }
1762       else
1763         {
1764           (*i)--;
1765           return new_lst_loop (seq);
1766         }
1767
1768       VEC_safe_push (lst_p, heap, seq, stmt);
1769     }
1770
1771   return new_lst_loop (seq);
1772 }
1773
1774 /* Reads the original scattering of the SCOP and returns an LST
1775    representing it.  */
1776
1777 void
1778 scop_to_lst (scop_p scop)
1779 {
1780   lst_p res;
1781   int i, n = VEC_length (poly_bb_p, SCOP_BBS (scop));
1782   VEC (lst_p, heap) *seq = VEC_alloc (lst_p, heap, 5);
1783   sese region = SCOP_REGION (scop);
1784
1785   for (i = 0; i < n; i++)
1786     {
1787       poly_bb_p pbb = VEC_index (poly_bb_p, SCOP_BBS (scop), i);
1788       loop_p loop = outermost_loop_in_sese (region, GBB_BB (PBB_BLACK_BOX (pbb)));
1789
1790       if (loop_in_sese_p (loop, region))
1791         res = loop_to_lst (loop, SCOP_BBS (scop), &i);
1792       else
1793         res = new_lst_stmt (pbb);
1794
1795       VEC_safe_push (lst_p, heap, seq, res);
1796     }
1797
1798   res = new_lst_loop (seq);
1799   SCOP_ORIGINAL_SCHEDULE (scop) = res;
1800   SCOP_TRANSFORMED_SCHEDULE (scop) = copy_lst (res);
1801 }
1802
1803 /* Print to FILE on a new line COLUMN white spaces.  */
1804
1805 static void
1806 lst_indent_to (FILE *file, int column)
1807 {
1808   int i;
1809
1810   if (column > 0)
1811     fprintf (file, "\n#");
1812
1813   for (i = 0; i < column; i++)
1814     fprintf (file, " ");
1815 }
1816
1817 /* Print LST to FILE with INDENT spaces of indentation.  */
1818
1819 void
1820 print_lst (FILE *file, lst_p lst, int indent)
1821 {
1822   if (!lst)
1823     return;
1824
1825   lst_indent_to (file, indent);
1826
1827   if (LST_LOOP_P (lst))
1828     {
1829       int i;
1830       lst_p l;
1831
1832       if (LST_LOOP_FATHER (lst))
1833         fprintf (file, "%d (loop", lst_dewey_number (lst));
1834       else
1835         fprintf (file, "#(root");
1836
1837       FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, l)
1838         print_lst (file, l, indent + 2);
1839
1840       fprintf (file, ")");
1841     }
1842   else
1843     fprintf (file, "%d stmt_%d", lst_dewey_number (lst), pbb_index (LST_PBB (lst)));
1844 }
1845
1846 /* Print LST to STDERR.  */
1847
1848 DEBUG_FUNCTION void
1849 debug_lst (lst_p lst)
1850 {
1851   print_lst (stderr, lst, 0);
1852 }
1853
1854 /* Pretty print to FILE the loop statement tree LST in DOT format.  */
1855
1856 static void
1857 dot_lst_1 (FILE *file, lst_p lst)
1858 {
1859   if (!lst)
1860     return;
1861
1862   if (LST_LOOP_P (lst))
1863     {
1864       int i;
1865       lst_p l;
1866
1867       if (!LST_LOOP_FATHER (lst))
1868         fprintf (file, "L -> L_%d_%d\n",
1869                  lst_depth (lst),
1870                  lst_dewey_number (lst));
1871       else
1872         fprintf (file, "L_%d_%d -> L_%d_%d\n",
1873                  lst_depth (LST_LOOP_FATHER (lst)),
1874                  lst_dewey_number (LST_LOOP_FATHER (lst)),
1875                  lst_depth (lst),
1876                  lst_dewey_number (lst));
1877
1878       FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, l)
1879         dot_lst_1 (file, l);
1880     }
1881
1882   else
1883     fprintf (file, "L_%d_%d -> S_%d\n",
1884              lst_depth (LST_LOOP_FATHER (lst)),
1885              lst_dewey_number (LST_LOOP_FATHER (lst)),
1886              pbb_index (LST_PBB (lst)));
1887
1888 }
1889
1890 /* Display the LST using dotty.  */
1891
1892 DEBUG_FUNCTION void
1893 dot_lst (lst_p lst)
1894 {
1895   /* When debugging, enable the following code.  This cannot be used
1896      in production compilers because it calls "system".  */
1897 #if 0
1898   FILE *stream = fopen ("/tmp/lst.dot", "w");
1899   gcc_assert (stream);
1900
1901   fputs ("digraph all {\n", stream);
1902   dot_lst_1 (stream, lst);
1903   fputs ("}\n\n", stream);
1904   fclose (stream);
1905
1906   system ("dotty /tmp/lst.dot &");
1907 #else
1908   fputs ("digraph all {\n", stderr);
1909   dot_lst_1 (stderr, lst);
1910   fputs ("}\n\n", stderr);
1911
1912 #endif
1913 }
1914
1915 /* Computes a checksum for the code generated by CLooG for SCOP.  */
1916
1917 DEBUG_FUNCTION void
1918 cloog_checksum (scop_p scop ATTRIBUTE_UNUSED)
1919 {
1920   /* When debugging, enable the following code.  This cannot be used
1921      in production compilers because it calls "system".  */
1922 #if 0
1923   FILE *stream = fopen ("/tmp/scop.cloog", "w");
1924   gcc_assert (stream);
1925   print_cloog (stream, scop, 0);
1926   fclose (stream);
1927
1928   fputs ("\n", stdout);
1929   system ("cloog -compilable 1 /tmp/scop.cloog > /tmp/scop.c ; gcc -O0 -g /tmp/scop.c -lm -o /tmp/scop; /tmp/scop | md5sum ");
1930 #endif
1931 }
1932
1933 #endif
1934