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   /* This feature is only enabled in the Graphite branch.  */
 787   if (0)
 788     {
 789       graphite_file = init_graphite_out_file (file_scop_number);
 790       print_scop (graphite_file, scop, 1);
 791       file_scop_number++;
 792     }
 793
 794   return transform_done;
 795 }
 796
 797 /* Returns true when it PDR1 is a duplicate of PDR2: same PBB, and
 798    their ACCESSES, TYPE, and NB_SUBSCRIPTS are the same.  */
 799
 800 static inline bool
 801 can_collapse_pdrs (poly_dr_p pdr1, poly_dr_p pdr2)
 802 {
 803   bool res;
 804   ppl_Pointset_Powerset_C_Polyhedron_t af1, af2, diff;
 805
 806   if (PDR_PBB (pdr1) != PDR_PBB (pdr2)
 807       || PDR_NB_SUBSCRIPTS (pdr1) != PDR_NB_SUBSCRIPTS (pdr2)
 808       || PDR_TYPE (pdr1) != PDR_TYPE (pdr2))
 809     return false;
 810
 811   af1 = PDR_ACCESSES (pdr1);
 812   af2 = PDR_ACCESSES (pdr2);
 813   ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
 814     (&diff, af1);
 815   ppl_Pointset_Powerset_C_Polyhedron_difference_assign (diff, af2);
 816
 817   res = ppl_Pointset_Powerset_C_Polyhedron_is_empty (diff);
 818   ppl_delete_Pointset_Powerset_C_Polyhedron (diff);
 819   return res;
 820 }
 821
 822 /* Removes duplicated data references in PBB.  */
 823
 824 void
 825 pbb_remove_duplicate_pdrs (poly_bb_p pbb)
 826 {
 827   int i, j;
 828   poly_dr_p pdr1, pdr2;
 829   unsigned n = VEC_length (poly_dr_p, PBB_DRS (pbb));
 830   VEC (poly_dr_p, heap) *collapsed = VEC_alloc (poly_dr_p, heap, n);
 831
 832   FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb), i, pdr1)
 833     FOR_EACH_VEC_ELT (poly_dr_p, collapsed, j, pdr2)
 834       if (!can_collapse_pdrs (pdr1, pdr2))
 835         VEC_quick_push (poly_dr_p, collapsed, pdr1);
 836
 837   VEC_free (poly_dr_p, heap, collapsed);
 838   PBB_PDR_DUPLICATES_REMOVED (pbb) = true;
 839 }
 840
 841 /* Create a new polyhedral data reference and add it to PBB.  It is
 842    defined by its ACCESSES, its TYPE, and the number of subscripts
 843    NB_SUBSCRIPTS.  */
 844
 845 void
 846 new_poly_dr (poly_bb_p pbb, int dr_base_object_set,
 847              ppl_Pointset_Powerset_C_Polyhedron_t accesses,
 848              enum poly_dr_type type, void *cdr, graphite_dim_t nb_subscripts)
 849 {
 850   static int id = 0;
 851   poly_dr_p pdr = XNEW (struct poly_dr);
 852
 853   PDR_ID (pdr) = id++;
 854   PDR_BASE_OBJECT_SET (pdr) = dr_base_object_set;
 855   PDR_NB_REFS (pdr) = 1;
 856   PDR_PBB (pdr) = pbb;
 857   PDR_ACCESSES (pdr) = accesses;
 858   PDR_TYPE (pdr) = type;
 859   PDR_CDR (pdr) = cdr;
 860   PDR_NB_SUBSCRIPTS (pdr) = nb_subscripts;
 861   VEC_safe_push (poly_dr_p, heap, PBB_DRS (pbb), pdr);
 862 }
 863
 864 /* Free polyhedral data reference PDR.  */
 865
 866 void
 867 free_poly_dr (poly_dr_p pdr)
 868 {
 869   ppl_delete_Pointset_Powerset_C_Polyhedron (PDR_ACCESSES (pdr));
 870   XDELETE (pdr);
 871 }
 872
 873 /* Create a new polyhedral black box.  */
 874
 875 void
 876 new_poly_bb (scop_p scop, void *black_box, bool reduction)
 877 {
 878   poly_bb_p pbb = XNEW (struct poly_bb);
 879
 880   PBB_DOMAIN (pbb) = NULL;
 881   PBB_SCOP (pbb) = scop;
 882   pbb_set_black_box (pbb, black_box);
 883   PBB_TRANSFORMED (pbb) = NULL;
 884   PBB_SAVED (pbb) = NULL;
 885   PBB_ORIGINAL (pbb) = NULL;
 886   PBB_DRS (pbb) = VEC_alloc (poly_dr_p, heap, 3);
 887   PBB_IS_REDUCTION (pbb) = reduction;
 888   PBB_PDR_DUPLICATES_REMOVED (pbb) = false;
 889   VEC_safe_push (poly_bb_p, heap, SCOP_BBS (scop), pbb);
 890 }
 891
 892 /* Free polyhedral black box.  */
 893
 894 void
 895 free_poly_bb (poly_bb_p pbb)
 896 {
 897   int i;
 898   poly_dr_p pdr;
 899
 900   ppl_delete_Pointset_Powerset_C_Polyhedron (PBB_DOMAIN (pbb));
 901
 902   if (PBB_TRANSFORMED (pbb))
 903     poly_scattering_free (PBB_TRANSFORMED (pbb));
 904
 905   if (PBB_SAVED (pbb))
 906     poly_scattering_free (PBB_SAVED (pbb));
 907
 908   if (PBB_ORIGINAL (pbb))
 909     poly_scattering_free (PBB_ORIGINAL (pbb));
 910
 911   if (PBB_DRS (pbb))
 912     FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb), i, pdr)
 913       free_poly_dr (pdr);
 914
 915   VEC_free (poly_dr_p, heap, PBB_DRS (pbb));
 916   XDELETE (pbb);
 917 }
 918
 919 static void
 920 print_pdr_access_layout (FILE *file, poly_bb_p pbb, poly_dr_p pdr)
 921 {
 922   graphite_dim_t i;
 923
 924   fprintf (file, "#  eq");
 925
 926   fprintf (file, "   alias");
 927
 928   for (i = 0; i < PDR_NB_SUBSCRIPTS (pdr); i++)
 929     fprintf (file, "   sub%d", (int) i);
 930
 931   for (i = 0; i < pbb_dim_iter_domain (pbb); i++)
 932     fprintf (file, "     i%d", (int) i);
 933
 934   for (i = 0; i < pbb_nb_params (pbb); i++)
 935     fprintf (file, "     p%d", (int) i);
 936
 937   fprintf (file, "    cst\n");
 938 }
 939
 940 /* Prints to FILE the polyhedral data reference PDR, at some VERBOSITY
 941    level.  */
 942
 943 void
 944 print_pdr (FILE *file, poly_dr_p pdr, int verbosity)
 945 {
 946   int alias_set_dim;
 947
 948   if (verbosity > 1)
 949     {
 950       fprintf (file, "# pdr_%d (", PDR_ID (pdr));
 951
 952       switch (PDR_TYPE (pdr))
 953         {
 954         case PDR_READ:
 955           fprintf (file, "read \n");
 956           break;
 957
 958         case PDR_WRITE:
 959           fprintf (file, "write \n");
 960           break;
 961
 962         case PDR_MAY_WRITE:
 963           fprintf (file, "may_write \n");
 964           break;
 965
 966         default:
 967           gcc_unreachable ();
 968         }
 969
 970       dump_data_reference (file, (data_reference_p) PDR_CDR (pdr));
 971     }
 972
 973   if (verbosity > 0)
 974     {
 975       fprintf (file, "# data accesses (\n");
 976       print_pdr_access_layout (file, PDR_PBB (pdr), pdr);
 977     }
 978
 979   alias_set_dim = pdr_alias_set_dim (pdr) + 1;
 980
 981   openscop_print_pdr_powerset (file,
 982                                PDR_ACCESSES (pdr),
 983                                PDR_NB_SUBSCRIPTS (pdr),
 984                                alias_set_dim,
 985                                pbb_nb_params (PDR_PBB (pdr)));
 986
 987   if (verbosity > 0)
 988     fprintf (file, "#)\n");
 989
 990   if (verbosity > 1)
 991     fprintf (file, "#)\n");
 992 }
 993
 994 /* Prints to STDERR the polyhedral data reference PDR, at some
 995    VERBOSITY level.  */
 996
 997 DEBUG_FUNCTION void
 998 debug_pdr (poly_dr_p pdr, int verbosity)
 999 {
1000   print_pdr (stderr, pdr, verbosity);
1001 }
1002
1003 /* Creates a new SCOP containing REGION.  */
1004
1005 scop_p
1006 new_scop (void *region)
1007 {
1008   scop_p scop = XNEW (struct scop);
1009
1010   SCOP_CONTEXT (scop) = NULL;
1011   scop_set_region (scop, region);
1012   SCOP_BBS (scop) = VEC_alloc (poly_bb_p, heap, 3);
1013   SCOP_ORIGINAL_PDDRS (scop) = htab_create (10, hash_poly_ddr_p,
1014                                             eq_poly_ddr_p, free_poly_ddr);
1015   SCOP_ORIGINAL_SCHEDULE (scop) = NULL;
1016   SCOP_TRANSFORMED_SCHEDULE (scop) = NULL;
1017   SCOP_SAVED_SCHEDULE (scop) = NULL;
1018   POLY_SCOP_P (scop) = false;
1019
1020   return scop;
1021 }
1022
1023 /* Deletes SCOP.  */
1024
1025 void
1026 free_scop (scop_p scop)
1027 {
1028   int i;
1029   poly_bb_p pbb;
1030
1031   FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
1032     free_poly_bb (pbb);
1033
1034   VEC_free (poly_bb_p, heap, SCOP_BBS (scop));
1035
1036   if (SCOP_CONTEXT (scop))
1037     ppl_delete_Pointset_Powerset_C_Polyhedron (SCOP_CONTEXT (scop));
1038
1039   htab_delete (SCOP_ORIGINAL_PDDRS (scop));
1040   free_lst (SCOP_ORIGINAL_SCHEDULE (scop));
1041   free_lst (SCOP_TRANSFORMED_SCHEDULE (scop));
1042   free_lst (SCOP_SAVED_SCHEDULE (scop));
1043   XDELETE (scop);
1044 }
1045
1046 /* Print to FILE the domain of PBB in OpenScop format, at some VERBOSITY
1047    level.  */
1048
1049 static void
1050 openscop_print_pbb_domain (FILE *file, poly_bb_p pbb, int verbosity)
1051 {
1052   graphite_dim_t i;
1053   gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
1054
1055   if (!PBB_DOMAIN (pbb))
1056     return;
1057
1058   if (verbosity > 0)
1059     {
1060       fprintf (file, "\n# Iteration domain of bb_%d (\n", GBB_BB (gbb)->index);
1061       fprintf (file, "#eq");
1062
1063       for (i = 0; i < pbb_dim_iter_domain (pbb); i++)
1064         fprintf (file, "     i%d", (int) i);
1065
1066       for (i = 0; i < pbb_nb_params (pbb); i++)
1067         fprintf (file, "     p%d", (int) i);
1068
1069       fprintf (file, "    cst\n");
1070     }
1071
1072   if (PBB_DOMAIN (pbb))
1073     openscop_print_powerset_matrix (file, PBB_DOMAIN (pbb),
1074                                     pbb_dim_iter_domain (pbb),
1075                                     0,
1076                                     0,
1077                                     pbb_nb_params (pbb));
1078   else
1079     fprintf (file, "0\n");
1080
1081   if (verbosity > 0)
1082     fprintf (file, "#)\n");
1083 }
1084
1085 /* Print to FILE the domain of PBB, at some VERBOSITY level.  */
1086
1087 void
1088 print_pbb_domain (FILE *file, poly_bb_p pbb, int verbosity)
1089 {
1090   graphite_dim_t i;
1091   gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
1092
1093   if (!PBB_DOMAIN (pbb))
1094     return;
1095
1096   if (verbosity > 0)
1097     {
1098       fprintf (file, "# Iteration domain of bb_%d (\n", GBB_BB (gbb)->index);
1099       fprintf (file, "#  eq");
1100
1101       for (i = 0; i < pbb_dim_iter_domain (pbb); i++)
1102         fprintf (file, "     i%d", (int) i);
1103
1104       for (i = 0; i < pbb_nb_params (pbb); i++)
1105         fprintf (file, "     p%d", (int) i);
1106
1107       fprintf (file, "    cst\n");
1108     }
1109
1110   if (PBB_DOMAIN (pbb))
1111     ppl_print_powerset_matrix (file, PBB_DOMAIN (pbb));
1112   else
1113     fprintf (file, "0\n");
1114
1115   if (verbosity > 0)
1116     fprintf (file, "#)\n");
1117 }
1118
1119 /* Dump the cases of a graphite basic block GBB on FILE.  */
1120
1121 static void
1122 dump_gbb_cases (FILE *file, gimple_bb_p gbb)
1123 {
1124   int i;
1125   gimple stmt;
1126   VEC (gimple, heap) *cases;
1127
1128   if (!gbb)
1129     return;
1130
1131   cases = GBB_CONDITION_CASES (gbb);
1132   if (VEC_empty (gimple, cases))
1133     return;
1134
1135   fprintf (file, "# cases bb_%d (\n", GBB_BB (gbb)->index);
1136
1137   FOR_EACH_VEC_ELT (gimple, cases, i, stmt)
1138     {
1139       fprintf (file, "# ");
1140       print_gimple_stmt (file, stmt, 0, 0);
1141     }
1142
1143   fprintf (file, "#)\n");
1144 }
1145
1146 /* Dump conditions of a graphite basic block GBB on FILE.  */
1147
1148 static void
1149 dump_gbb_conditions (FILE *file, gimple_bb_p gbb)
1150 {
1151   int i;
1152   gimple stmt;
1153   VEC (gimple, heap) *conditions;
1154
1155   if (!gbb)
1156     return;
1157
1158   conditions = GBB_CONDITIONS (gbb);
1159   if (VEC_empty (gimple, conditions))
1160     return;
1161
1162   fprintf (file, "# conditions bb_%d (\n", GBB_BB (gbb)->index);
1163
1164   FOR_EACH_VEC_ELT (gimple, conditions, i, stmt)
1165     {
1166       fprintf (file, "# ");
1167       print_gimple_stmt (file, stmt, 0, 0);
1168     }
1169
1170   fprintf (file, "#)\n");
1171 }
1172
1173 /* Print to FILE all the data references of PBB, at some VERBOSITY
1174    level.  */
1175
1176 void
1177 print_pdrs (FILE *file, poly_bb_p pbb, int verbosity)
1178 {
1179   int i;
1180   poly_dr_p pdr;
1181   int nb_reads = 0;
1182   int nb_writes = 0;
1183
1184   if (VEC_length (poly_dr_p, PBB_DRS (pbb)) == 0)
1185     {
1186       if (verbosity > 0)
1187         fprintf (file, "# Access informations are not provided\n");\
1188       fprintf (file, "0\n");
1189       return;
1190     }
1191
1192   if (verbosity > 1)
1193     fprintf (file, "# Data references (\n");
1194
1195   if (verbosity > 0)
1196     fprintf (file, "# Access informations are provided\n");
1197   fprintf (file, "1\n");
1198
1199   FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb), i, pdr)
1200     if (PDR_TYPE (pdr) == PDR_READ)
1201       nb_reads++;
1202     else
1203       nb_writes++;
1204
1205   if (verbosity > 1)
1206     fprintf (file, "# Read data references (\n");
1207
1208   if (verbosity > 0)
1209     fprintf (file, "# Read access informations\n");
1210   fprintf (file, "%d\n", nb_reads);
1211
1212   FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb), i, pdr)
1213     if (PDR_TYPE (pdr) == PDR_READ)
1214       print_pdr (file, pdr, verbosity);
1215
1216   if (verbosity > 1)
1217     fprintf (file, "#)\n");
1218
1219   if (verbosity > 1)
1220     fprintf (file, "# Write data references (\n");
1221
1222   if (verbosity > 0)
1223     fprintf (file, "# Write access informations\n");
1224   fprintf (file, "%d\n", nb_writes);
1225
1226   FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb), i, pdr)
1227     if (PDR_TYPE (pdr) != PDR_READ)
1228       print_pdr (file, pdr, verbosity);
1229
1230   if (verbosity > 1)
1231     fprintf (file, "#)\n");
1232
1233   if (verbosity > 1)
1234     fprintf (file, "#)\n");
1235 }
1236
1237 /* Print to STDERR all the data references of PBB.  */
1238
1239 DEBUG_FUNCTION void
1240 debug_pdrs (poly_bb_p pbb, int verbosity)
1241 {
1242   print_pdrs (stderr, pbb, verbosity);
1243 }
1244
1245 /* Print to FILE the body of PBB, at some VERBOSITY level.
1246    If statement_body_provided is false statement body is not printed.  */
1247
1248 static void
1249 print_pbb_body (FILE *file, poly_bb_p pbb, int verbosity,
1250                 bool statement_body_provided)
1251 {
1252   if (verbosity > 1)
1253     fprintf (file, "# Body (\n");
1254
1255   if (!statement_body_provided)
1256     {
1257       if (verbosity > 0)
1258         fprintf (file, "# Statement body is not provided\n");
1259
1260       fprintf (file, "0\n");
1261
1262       if (verbosity > 1)
1263         fprintf (file, "#)\n");
1264       return;
1265     }
1266
1267   if (verbosity > 0)
1268     fprintf (file, "# Statement body is provided\n");
1269   fprintf (file, "1\n");
1270
1271   if (verbosity > 0)
1272     fprintf (file, "# Original iterator names\n# Iterator names are not provided yet.\n");
1273
1274   if (verbosity > 0)
1275     fprintf (file, "# Statement body\n");
1276
1277   fprintf (file, "{\n");
1278   dump_bb (pbb_bb (pbb), file, 0);
1279   fprintf (file, "}\n");
1280
1281   if (verbosity > 1)
1282     fprintf (file, "#)\n");
1283 }
1284
1285 /* Print to FILE the domain and scattering function of PBB, at some
1286    VERBOSITY level.  */
1287
1288 void
1289 print_pbb (FILE *file, poly_bb_p pbb, int verbosity)
1290 {
1291   if (verbosity > 1)
1292     {
1293       fprintf (file, "# pbb_%d (\n", pbb_index (pbb));
1294       dump_gbb_conditions (file, PBB_BLACK_BOX (pbb));
1295       dump_gbb_cases (file, PBB_BLACK_BOX (pbb));
1296     }
1297
1298   openscop_print_pbb_domain (file, pbb, verbosity);
1299   print_scattering_function (file, pbb, verbosity);
1300   print_pdrs (file, pbb, verbosity);
1301   print_pbb_body (file, pbb, verbosity, false);
1302
1303   if (verbosity > 1)
1304     fprintf (file, "#)\n");
1305 }
1306
1307 /* Print to FILE the parameters of SCOP, at some VERBOSITY level.  */
1308
1309 void
1310 print_scop_params (FILE *file, scop_p scop, int verbosity)
1311 {
1312   int i;
1313   tree t;
1314
1315   if (verbosity > 1)
1316     fprintf (file, "# parameters (\n");
1317
1318   if (VEC_length (tree, SESE_PARAMS (SCOP_REGION (scop))))
1319     {
1320       if (verbosity > 0)
1321         fprintf (file, "# Parameter names are provided\n");
1322
1323       fprintf (file, "1\n");
1324
1325       if (verbosity > 0)
1326         fprintf (file, "# Parameter names\n");
1327     }
1328   else
1329     {
1330       if (verbosity > 0)
1331         fprintf (file, "# Parameter names are not provided\n");
1332       fprintf (file, "0\n");
1333     }
1334
1335   FOR_EACH_VEC_ELT (tree, SESE_PARAMS (SCOP_REGION (scop)), i, t)
1336     {
1337       print_generic_expr (file, t, 0);
1338       fprintf (file, " ");
1339     }
1340
1341   fprintf (file, "\n");
1342
1343   if (verbosity > 1)
1344     fprintf (file, "#)\n");
1345 }
1346
1347 /* Print to FILE the context of SCoP in OpenScop format, at some VERBOSITY
1348    level.  */
1349
1350 static void
1351 openscop_print_scop_context (FILE *file, scop_p scop, int verbosity)
1352 {
1353   graphite_dim_t i;
1354
1355   if (verbosity > 0)
1356     {
1357       fprintf (file, "# Context (\n");
1358       fprintf (file, "#eq");
1359
1360       for (i = 0; i < scop_nb_params (scop); i++)
1361         fprintf (file, "     p%d", (int) i);
1362
1363       fprintf (file, "    cst\n");
1364     }
1365
1366   if (SCOP_CONTEXT (scop))
1367     openscop_print_powerset_matrix (file, SCOP_CONTEXT (scop), 0, 0, 0,
1368                                     scop_nb_params (scop));
1369   else
1370     fprintf (file, "0 %d 0 0 0 %d\n", (int) scop_nb_params (scop) + 2,
1371              (int) scop_nb_params (scop));
1372
1373   if (verbosity > 0)
1374     fprintf (file, "# )\n");
1375 }
1376
1377 /* Print to FILE the context of SCoP, at some VERBOSITY level.  */
1378
1379 void
1380 print_scop_context (FILE *file, scop_p scop, int verbosity)
1381 {
1382   graphite_dim_t i;
1383
1384   if (verbosity > 0)
1385     {
1386       fprintf (file, "# Context (\n");
1387       fprintf (file, "#eq");
1388
1389       for (i = 0; i < scop_nb_params (scop); i++)
1390         fprintf (file, "     p%d", (int) i);
1391
1392       fprintf (file, "    cst\n");
1393     }
1394
1395   if (SCOP_CONTEXT (scop))
1396     ppl_print_powerset_matrix (file, SCOP_CONTEXT (scop));
1397   else
1398     fprintf (file, "0 %d\n", (int) scop_nb_params (scop) + 2);
1399
1400   if (verbosity > 0)
1401     fprintf (file, "# )\n");
1402 }
1403
1404 /* Print to FILE the SCOP, at some VERBOSITY level.  */
1405
1406 void
1407 print_scop (FILE *file, scop_p scop, int verbosity)
1408 {
1409   int i;
1410   poly_bb_p pbb;
1411
1412   fprintf (file, "SCoP 1\n#(\n");
1413   fprintf (file, "# Language\nGimple\n");
1414   openscop_print_scop_context (file, scop, verbosity);
1415   print_scop_params (file, scop, verbosity);
1416
1417   if (verbosity > 0)
1418     fprintf (file, "# Number of statements\n");
1419
1420   fprintf (file, "%d\n",VEC_length (poly_bb_p, SCOP_BBS (scop)));
1421
1422   FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
1423     print_pbb (file, pbb, verbosity);
1424
1425   if (verbosity > 1)
1426     {
1427       fprintf (file, "# original_lst (\n");
1428       print_lst (file, SCOP_ORIGINAL_SCHEDULE (scop), 0);
1429       fprintf (file, "\n#)\n");
1430
1431       fprintf (file, "# transformed_lst (\n");
1432       print_lst (file, SCOP_TRANSFORMED_SCHEDULE (scop), 0);
1433       fprintf (file, "\n#)\n");
1434     }
1435
1436   fprintf (file, "#)\n");
1437 }
1438
1439 /* Print to FILE the input file that CLooG would expect as input, at
1440    some VERBOSITY level.  */
1441
1442 void
1443 print_cloog (FILE *file, scop_p scop, int verbosity)
1444 {
1445   int i;
1446   poly_bb_p pbb;
1447
1448   fprintf (file, "# SCoP (generated by GCC/Graphite\n");
1449   if (verbosity > 0)
1450     fprintf (file, "# CLooG output language\n");
1451   fprintf (file, "c\n");
1452
1453   print_scop_context (file, scop, verbosity);
1454   print_scop_params (file, scop, verbosity);
1455
1456   if (verbosity > 0)
1457     fprintf (file, "# Number of statements\n");
1458
1459   fprintf (file, "%d\n", VEC_length (poly_bb_p, SCOP_BBS (scop)));
1460
1461   FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
1462     {
1463       if (verbosity > 1)
1464         fprintf (file, "# pbb_%d (\n", pbb_index (pbb));
1465
1466       print_pbb_domain (file, pbb, verbosity);
1467       fprintf (file, "0 0 0");
1468
1469       if (verbosity > 0)
1470         fprintf (file, "# For future CLooG options.\n");
1471       else
1472         fprintf (file, "\n");
1473
1474       if (verbosity > 1)
1475         fprintf (file, "#)\n");
1476     }
1477
1478   fprintf (file, "0");
1479   if (verbosity > 0)
1480     fprintf (file, "# Don't set the iterator names.\n");
1481   else
1482     fprintf (file, "\n");
1483
1484   if (verbosity > 0)
1485     fprintf (file, "# Number of scattering functions\n");
1486
1487   fprintf (file, "%d\n", VEC_length (poly_bb_p, SCOP_BBS (scop)));
1488   unify_scattering_dimensions (scop);
1489
1490   FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
1491     {
1492       if (!PBB_TRANSFORMED (pbb)
1493           || !(PBB_TRANSFORMED_SCATTERING (pbb)
1494                || PBB_ORIGINAL_SCATTERING (pbb)))
1495         continue;
1496
1497       if (verbosity > 1)
1498         fprintf (file, "# pbb_%d (\n", pbb_index (pbb));
1499
1500       print_scattering_function_1 (file, pbb, verbosity);
1501
1502       if (verbosity > 1)
1503         fprintf (file, "#)\n");
1504     }
1505
1506   fprintf (file, "0");
1507   if (verbosity > 0)
1508     fprintf (file, "# Don't set the scattering dimension names.\n");
1509   else
1510     fprintf (file, "\n");
1511
1512   fprintf (file, "#)\n");
1513 }
1514
1515 /* Print to STDERR the domain of PBB, at some VERBOSITY level.  */
1516
1517 DEBUG_FUNCTION void
1518 debug_pbb_domain (poly_bb_p pbb, int verbosity)
1519 {
1520   print_pbb_domain (stderr, pbb, verbosity);
1521 }
1522
1523 /* Print to FILE the domain and scattering function of PBB, at some
1524    VERBOSITY level.  */
1525
1526 DEBUG_FUNCTION void
1527 debug_pbb (poly_bb_p pbb, int verbosity)
1528 {
1529   print_pbb (stderr, pbb, verbosity);
1530 }
1531
1532 /* Print to STDERR the context of SCOP, at some VERBOSITY level.  */
1533
1534 DEBUG_FUNCTION void
1535 debug_scop_context (scop_p scop, int verbosity)
1536 {
1537   print_scop_context (stderr, scop, verbosity);
1538 }
1539
1540 /* Print to STDERR the SCOP, at some VERBOSITY level.  */
1541
1542 DEBUG_FUNCTION void
1543 debug_scop (scop_p scop, int verbosity)
1544 {
1545   print_scop (stderr, scop, verbosity);
1546 }
1547
1548 /* Print to STDERR the SCOP under CLooG format, at some VERBOSITY
1549    level.  */
1550
1551 DEBUG_FUNCTION void
1552 debug_cloog (scop_p scop, int verbosity)
1553 {
1554   print_cloog (stderr, scop, verbosity);
1555 }
1556
1557 /* Print to STDERR the parameters of SCOP, at some VERBOSITY
1558    level.  */
1559
1560 DEBUG_FUNCTION void
1561 debug_scop_params (scop_p scop, int verbosity)
1562 {
1563   print_scop_params (stderr, scop, verbosity);
1564 }
1565
1566
1567 /* The dimension in the transformed scattering polyhedron of PBB
1568    containing the scattering iterator for the loop at depth LOOP_DEPTH.  */
1569
1570 ppl_dimension_type
1571 psct_scattering_dim_for_loop_depth (poly_bb_p pbb, graphite_dim_t loop_depth)
1572 {
1573   ppl_const_Constraint_System_t pcs;
1574   ppl_Constraint_System_const_iterator_t cit, cend;
1575   ppl_const_Constraint_t cstr;
1576   ppl_Polyhedron_t ph = PBB_TRANSFORMED_SCATTERING (pbb);
1577   ppl_dimension_type iter = psct_iterator_dim (pbb, loop_depth);
1578   ppl_Linear_Expression_t expr;
1579   ppl_Coefficient_t coef;
1580   mpz_t val;
1581   graphite_dim_t i;
1582
1583   mpz_init (val);
1584   ppl_new_Coefficient (&coef);
1585   ppl_Polyhedron_get_constraints (ph, &pcs);
1586   ppl_new_Constraint_System_const_iterator (&cit);
1587   ppl_new_Constraint_System_const_iterator (&cend);
1588
1589   for (ppl_Constraint_System_begin (pcs, cit),
1590          ppl_Constraint_System_end (pcs, cend);
1591        !ppl_Constraint_System_const_iterator_equal_test (cit, cend);
1592        ppl_Constraint_System_const_iterator_increment (cit))
1593     {
1594       ppl_Constraint_System_const_iterator_dereference (cit, &cstr);
1595       ppl_new_Linear_Expression_from_Constraint (&expr, cstr);
1596       ppl_Linear_Expression_coefficient (expr, iter, coef);
1597       ppl_Coefficient_to_mpz_t (coef, val);
1598
1599       if (mpz_sgn (val) == 0)
1600         {
1601           ppl_delete_Linear_Expression (expr);
1602           continue;
1603         }
1604
1605       for (i = 0; i < pbb_nb_scattering_transform (pbb); i++)
1606         {
1607           ppl_dimension_type scatter = psct_scattering_dim (pbb, i);
1608
1609           ppl_Linear_Expression_coefficient (expr, scatter, coef);
1610           ppl_Coefficient_to_mpz_t (coef, val);
1611
1612           if (mpz_sgn (val) != 0)
1613             {
1614               mpz_clear (val);
1615               ppl_delete_Linear_Expression (expr);
1616               ppl_delete_Coefficient (coef);
1617               ppl_delete_Constraint_System_const_iterator (cit);
1618               ppl_delete_Constraint_System_const_iterator (cend);
1619
1620               return scatter;
1621             }
1622         }
1623     }
1624
1625   gcc_unreachable ();
1626 }
1627
1628 /* Returns the number of iterations RES of the loop around PBB at
1629    time(scattering) dimension TIME_DEPTH.  */
1630
1631 void
1632 pbb_number_of_iterations_at_time (poly_bb_p pbb,
1633                                   graphite_dim_t time_depth,
1634                                   mpz_t res)
1635 {
1636   ppl_Pointset_Powerset_C_Polyhedron_t domain, sctr_lb, sctr_ub;
1637   ppl_dimension_type domain_dim, sctr_dim;
1638   ppl_Linear_Expression_t le;
1639   mpz_t lb, ub, diff, one;
1640   int i;
1641
1642   ppl_Polyhedron_space_dimension (PBB_TRANSFORMED_SCATTERING (pbb), &sctr_dim);
1643
1644   ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1645     (&domain, PBB_DOMAIN (pbb));
1646
1647   ppl_Pointset_Powerset_C_Polyhedron_space_dimension (domain, &domain_dim);
1648   mpz_init (diff);
1649   mpz_init (lb);
1650   mpz_init (ub);
1651   mpz_init (one);
1652   mpz_set_si (one, 1);
1653
1654   /* Compute the upper bound on the original iteration domain and add
1655      that upper bound to the scattering.  */
1656   ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1657     (&sctr_ub, PBB_TRANSFORMED_SCATTERING (pbb));
1658   for (i = 0; i < (int) domain_dim; i++)
1659     {
1660       ppl_Linear_Expression_t eq;
1661       ppl_Constraint_t pc;
1662       ppl_Constraint_System_t cs;
1663       ppl_Polyhedron_t ph;
1664       ppl_Pointset_Powerset_C_Polyhedron_t pph;
1665
1666       ppl_new_Linear_Expression_with_dimension (&le, domain_dim);
1667       ppl_set_coef (le, i, 1);
1668       ppl_min_for_le_pointset (domain, le, lb);
1669       ppl_max_for_le_pointset (domain, le, ub);
1670       mpz_sub (diff, ub, lb);
1671       mpz_add (diff, diff, one);
1672
1673       ppl_new_Linear_Expression_with_dimension (&eq, sctr_dim);
1674       ppl_set_coef (eq, psct_iterator_dim (pbb, i), -1);
1675       ppl_set_inhomogeneous_gmp (eq, diff);
1676
1677       ppl_new_Constraint (&pc, eq, PPL_CONSTRAINT_TYPE_EQUAL);
1678       ppl_new_Constraint_System_from_Constraint (&cs, pc);
1679       ppl_new_C_Polyhedron_from_Constraint_System (&ph, cs);
1680       ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&pph, ph);
1681       ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (sctr_ub, pph);
1682
1683       ppl_delete_Linear_Expression (le);
1684       ppl_delete_Linear_Expression (eq);
1685       ppl_delete_Polyhedron (ph);
1686       ppl_delete_Pointset_Powerset_C_Polyhedron (pph);
1687       ppl_delete_Constraint (pc);
1688       ppl_delete_Constraint_System (cs);
1689     }
1690
1691   /* Compute the lower bound on the original iteration domain.  */
1692   ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1693     (&sctr_lb, PBB_TRANSFORMED_SCATTERING (pbb));
1694   for (i = 0; i < (int) domain_dim; i++)
1695     {
1696       ppl_Linear_Expression_t eq;
1697       ppl_Constraint_t pc;
1698       ppl_Constraint_System_t cs;
1699       ppl_Polyhedron_t ph;
1700       ppl_Pointset_Powerset_C_Polyhedron_t pph;
1701
1702       ppl_new_Linear_Expression_with_dimension (&le, domain_dim);
1703       ppl_set_coef (le, i, 1);
1704       ppl_min_for_le_pointset (domain, le, lb);
1705
1706       ppl_new_Linear_Expression_with_dimension (&eq, sctr_dim);
1707       ppl_set_coef (eq, psct_iterator_dim (pbb, i), -1);
1708       ppl_set_inhomogeneous_gmp (eq, lb);
1709
1710       ppl_new_Constraint (&pc, eq, PPL_CONSTRAINT_TYPE_EQUAL);
1711       ppl_new_Constraint_System_from_Constraint (&cs, pc);
1712       ppl_new_C_Polyhedron_from_Constraint_System (&ph, cs);
1713       ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&pph, ph);
1714       ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (sctr_lb, pph);
1715
1716       ppl_delete_Linear_Expression (le);
1717       ppl_delete_Linear_Expression (eq);
1718       ppl_delete_Polyhedron (ph);
1719       ppl_delete_Pointset_Powerset_C_Polyhedron (pph);
1720       ppl_delete_Constraint (pc);
1721       ppl_delete_Constraint_System (cs);
1722     }
1723
1724   /* Extract the number of iterations.  */
1725   ppl_new_Linear_Expression_with_dimension (&le, sctr_dim);
1726   ppl_set_coef (le, time_depth, 1);
1727   ppl_min_for_le_pointset (sctr_lb, le, lb);
1728   ppl_max_for_le_pointset (sctr_ub, le, ub);
1729   mpz_sub (res, ub, lb);
1730
1731   mpz_clear (one);
1732   mpz_clear (diff);
1733   mpz_clear (lb);
1734   mpz_clear (ub);
1735   ppl_delete_Pointset_Powerset_C_Polyhedron (sctr_ub);
1736   ppl_delete_Pointset_Powerset_C_Polyhedron (sctr_lb);
1737 }
1738
1739 /* Translates LOOP to LST.  */
1740
1741 static lst_p
1742 loop_to_lst (loop_p loop, VEC (poly_bb_p, heap) *bbs, int *i)
1743 {
1744   poly_bb_p pbb;
1745   VEC (lst_p, heap) *seq = VEC_alloc (lst_p, heap, 5);
1746
1747   for (; VEC_iterate (poly_bb_p, bbs, *i, pbb); (*i)++)
1748     {
1749       lst_p stmt;
1750       basic_block bb = GBB_BB (PBB_BLACK_BOX (pbb));
1751
1752       if (bb->loop_father == loop)
1753         stmt = new_lst_stmt (pbb);
1754       else if (flow_bb_inside_loop_p (loop, bb))
1755         {
1756           loop_p next = loop->inner;
1757
1758           while (next && !flow_bb_inside_loop_p (next, bb))
1759             next = next->next;
1760
1761           stmt = loop_to_lst (next, bbs, i);
1762         }
1763       else
1764         {
1765           (*i)--;
1766           return new_lst_loop (seq);
1767         }
1768
1769       VEC_safe_push (lst_p, heap, seq, stmt);
1770     }
1771
1772   return new_lst_loop (seq);
1773 }
1774
1775 /* Reads the original scattering of the SCOP and returns an LST
1776    representing it.  */
1777
1778 void
1779 scop_to_lst (scop_p scop)
1780 {
1781   lst_p res;
1782   int i, n = VEC_length (poly_bb_p, SCOP_BBS (scop));
1783   VEC (lst_p, heap) *seq = VEC_alloc (lst_p, heap, 5);
1784   sese region = SCOP_REGION (scop);
1785
1786   for (i = 0; i < n; i++)
1787     {
1788       poly_bb_p pbb = VEC_index (poly_bb_p, SCOP_BBS (scop), i);
1789       loop_p loop = outermost_loop_in_sese (region, GBB_BB (PBB_BLACK_BOX (pbb)));
1790
1791       if (loop_in_sese_p (loop, region))
1792         res = loop_to_lst (loop, SCOP_BBS (scop), &i);
1793       else
1794         res = new_lst_stmt (pbb);
1795
1796       VEC_safe_push (lst_p, heap, seq, res);
1797     }
1798
1799   res = new_lst_loop (seq);
1800   SCOP_ORIGINAL_SCHEDULE (scop) = res;
1801   SCOP_TRANSFORMED_SCHEDULE (scop) = copy_lst (res);
1802 }
1803
1804 /* Print to FILE on a new line COLUMN white spaces.  */
1805
1806 static void
1807 lst_indent_to (FILE *file, int column)
1808 {
1809   int i;
1810
1811   if (column > 0)
1812     fprintf (file, "\n#");
1813
1814   for (i = 0; i < column; i++)
1815     fprintf (file, " ");
1816 }
1817
1818 /* Print LST to FILE with INDENT spaces of indentation.  */
1819
1820 void
1821 print_lst (FILE *file, lst_p lst, int indent)
1822 {
1823   if (!lst)
1824     return;
1825
1826   lst_indent_to (file, indent);
1827
1828   if (LST_LOOP_P (lst))
1829     {
1830       int i;
1831       lst_p l;
1832
1833       if (LST_LOOP_FATHER (lst))
1834         fprintf (file, "%d (loop", lst_dewey_number (lst));
1835       else
1836         fprintf (file, "#(root");
1837
1838       FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, l)
1839         print_lst (file, l, indent + 2);
1840
1841       fprintf (file, ")");
1842     }
1843   else
1844     fprintf (file, "%d stmt_%d", lst_dewey_number (lst), pbb_index (LST_PBB (lst)));
1845 }
1846
1847 /* Print LST to STDERR.  */
1848
1849 DEBUG_FUNCTION void
1850 debug_lst (lst_p lst)
1851 {
1852   print_lst (stderr, lst, 0);
1853 }
1854
1855 /* Pretty print to FILE the loop statement tree LST in DOT format.  */
1856
1857 static void
1858 dot_lst_1 (FILE *file, lst_p lst)
1859 {
1860   if (!lst)
1861     return;
1862
1863   if (LST_LOOP_P (lst))
1864     {
1865       int i;
1866       lst_p l;
1867
1868       if (!LST_LOOP_FATHER (lst))
1869         fprintf (file, "L -> L_%d_%d\n",
1870                  lst_depth (lst),
1871                  lst_dewey_number (lst));
1872       else
1873         fprintf (file, "L_%d_%d -> L_%d_%d\n",
1874                  lst_depth (LST_LOOP_FATHER (lst)),
1875                  lst_dewey_number (LST_LOOP_FATHER (lst)),
1876                  lst_depth (lst),
1877                  lst_dewey_number (lst));
1878
1879       FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, l)
1880         dot_lst_1 (file, l);
1881     }
1882
1883   else
1884     fprintf (file, "L_%d_%d -> S_%d\n",
1885              lst_depth (LST_LOOP_FATHER (lst)),
1886              lst_dewey_number (LST_LOOP_FATHER (lst)),
1887              pbb_index (LST_PBB (lst)));
1888
1889 }
1890
1891 /* Display the LST using dotty.  */
1892
1893 DEBUG_FUNCTION void
1894 dot_lst (lst_p lst)
1895 {
1896   /* When debugging, enable the following code.  This cannot be used
1897      in production compilers because it calls "system".  */
1898 #if 0
1899   FILE *stream = fopen ("/tmp/lst.dot", "w");
1900   gcc_assert (stream);
1901
1902   fputs ("digraph all {\n", stream);
1903   dot_lst_1 (stream, lst);
1904   fputs ("}\n\n", stream);
1905   fclose (stream);
1906
1907   system ("dotty /tmp/lst.dot &");
1908 #else
1909   fputs ("digraph all {\n", stderr);
1910   dot_lst_1 (stderr, lst);
1911   fputs ("}\n\n", stderr);
1912
1913 #endif
1914 }
1915
1916 #endif
1917