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