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