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