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    return;
1258   }
1259
1260   if (verbosity > 0)
1261     fprintf (file, "# Statement body is provided\n");
1262   fprintf (file, "1\n");
1263
1264   if (verbosity > 0)
1265     fprintf (file, "# Original iterator names\n# Iterator names are not provided yet.\n");
1266
1267   if (verbosity > 0)
1268     fprintf (file, "# Statement body\n");
1269
1270   fprintf (file, "{\n");
1271   dump_bb (pbb_bb (pbb), file, 0);
1272   fprintf (file, "}\n");
1273
1274   if (verbosity > 1)
1275     fprintf (file, "#)\n");
1276 }
1277
1278 /* Print to FILE the domain and scattering function of PBB, at some
1279    VERBOSITY level.  */
1280
1281 void
1282 print_pbb (FILE *file, poly_bb_p pbb, int verbosity)
1283 {
1284   if (verbosity > 1)
1285     {
1286       fprintf (file, "# pbb_%d (\n", pbb_index (pbb));
1287       dump_gbb_conditions (file, PBB_BLACK_BOX (pbb));
1288       dump_gbb_cases (file, PBB_BLACK_BOX (pbb));
1289     }
1290
1291   openscop_print_pbb_domain (file, pbb, verbosity);
1292   print_scattering_function (file, pbb, verbosity);
1293   print_pdrs (file, pbb, verbosity);
1294   print_pbb_body (file, pbb, verbosity, false);
1295
1296   if (verbosity > 1)
1297     fprintf (file, "#)\n");
1298 }
1299
1300 /* Print to FILE the parameters of SCOP, at some VERBOSITY level.  */
1301
1302 void
1303 print_scop_params (FILE *file, scop_p scop, int verbosity)
1304 {
1305   int i;
1306   tree t;
1307
1308   if (verbosity > 1)
1309     fprintf (file, "# parameters (\n");
1310
1311   if (VEC_length (tree, SESE_PARAMS (SCOP_REGION (scop))))
1312     {
1313       if (verbosity > 0)
1314         fprintf (file, "# Parameter names are provided\n");
1315
1316       fprintf (file, "1\n");
1317
1318       if (verbosity > 0)
1319         fprintf (file, "# Parameter names\n");
1320     }
1321   else
1322     {
1323       if (verbosity > 0)
1324         fprintf (file, "# Parameter names are not provided\n");
1325       fprintf (file, "0\n");
1326     }
1327
1328   FOR_EACH_VEC_ELT (tree, SESE_PARAMS (SCOP_REGION (scop)), i, t)
1329     {
1330       print_generic_expr (file, t, 0);
1331       fprintf (file, " ");
1332     }
1333
1334   fprintf (file, "\n");
1335
1336   if (verbosity > 1)
1337     fprintf (file, "#)\n");
1338 }
1339
1340 /* Print to FILE the context of SCoP in OpenScop format, at some VERBOSITY
1341    level.  */
1342
1343 static void
1344 openscop_print_scop_context (FILE *file, scop_p scop, int verbosity)
1345 {
1346   graphite_dim_t i;
1347
1348   if (verbosity > 0)
1349     {
1350       fprintf (file, "# Context (\n");
1351       fprintf (file, "#eq");
1352
1353       for (i = 0; i < scop_nb_params (scop); i++)
1354         fprintf (file, "     p%d", (int) i);
1355
1356       fprintf (file, "    cst\n");
1357     }
1358
1359   if (SCOP_CONTEXT (scop))
1360     openscop_print_powerset_matrix (file, SCOP_CONTEXT (scop), 0, 0, 0,
1361                                     scop_nb_params (scop));
1362   else
1363     fprintf (file, "0 %d 0 0 0 %d\n", (int) scop_nb_params (scop) + 2,
1364              (int) scop_nb_params (scop));
1365
1366   if (verbosity > 0)
1367     fprintf (file, "# )\n");
1368 }
1369
1370 /* Print to FILE the context of SCoP, at some VERBOSITY level.  */
1371
1372 void
1373 print_scop_context (FILE *file, scop_p scop, int verbosity)
1374 {
1375   graphite_dim_t i;
1376
1377   if (verbosity > 0)
1378     {
1379       fprintf (file, "# Context (\n");
1380       fprintf (file, "#eq");
1381
1382       for (i = 0; i < scop_nb_params (scop); i++)
1383         fprintf (file, "     p%d", (int) i);
1384
1385       fprintf (file, "    cst\n");
1386     }
1387
1388   if (SCOP_CONTEXT (scop))
1389     ppl_print_powerset_matrix (file, SCOP_CONTEXT (scop));
1390   else
1391     fprintf (file, "0 %d\n", (int) scop_nb_params (scop) + 2);
1392
1393   if (verbosity > 0)
1394     fprintf (file, "# )\n");
1395 }
1396
1397 /* Print to FILE the SCOP header: context, parameters, and statements
1398    number.  */
1399
1400 static void
1401 print_scop_header (FILE *file, scop_p scop, int verbosity)
1402 {
1403   fprintf (file, "SCoP 1\n#(\n");
1404   fprintf (file, "# Language\nGimple\n");
1405   openscop_print_scop_context (file, scop, verbosity);
1406   print_scop_params (file, scop, verbosity);
1407
1408   if (verbosity > 0)
1409     fprintf (file, "# Number of statements\n");
1410
1411   fprintf (file, "%d\n",VEC_length (poly_bb_p, SCOP_BBS (scop)));
1412 }
1413
1414 /* Print to FILE the SCOP, at some VERBOSITY level.  */
1415
1416 void
1417 print_scop (FILE *file, scop_p scop, int verbosity)
1418 {
1419   int i;
1420   poly_bb_p pbb;
1421
1422   print_scop_header (file, scop, verbosity);
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 NITER of the loop around PBB at
1631    depth LOOP_DEPTH.  */
1632
1633 void
1634 pbb_number_of_iterations (poly_bb_p pbb,
1635                           graphite_dim_t loop_depth,
1636                           mpz_t niter)
1637 {
1638   ppl_Linear_Expression_t le;
1639   ppl_dimension_type dim;
1640
1641   ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PBB_DOMAIN (pbb), &dim);
1642   ppl_new_Linear_Expression_with_dimension (&le, dim);
1643   ppl_set_coef (le, pbb_iterator_dim (pbb, loop_depth), 1);
1644   mpz_set_si (niter, -1);
1645   ppl_max_for_le_pointset (PBB_DOMAIN (pbb), le, niter);
1646   ppl_delete_Linear_Expression (le);
1647 }
1648
1649 /* Returns the number of iterations NITER of the loop around PBB at
1650    time(scattering) dimension TIME_DEPTH.  */
1651
1652 void
1653 pbb_number_of_iterations_at_time (poly_bb_p pbb,
1654                                   graphite_dim_t time_depth,
1655                                   mpz_t niter)
1656 {
1657   ppl_Pointset_Powerset_C_Polyhedron_t ext_domain, sctr;
1658   ppl_Linear_Expression_t le;
1659   ppl_dimension_type dim;
1660
1661   /* Takes together domain and scattering polyhedrons, and composes
1662      them into the bigger polyhedron that has the following format:
1663
1664      t0..t_{n-1} | l0..l_{nlcl-1} | i0..i_{niter-1} | g0..g_{nparm-1}
1665
1666      where
1667      | t0..t_{n-1} are time dimensions (scattering dimensions)
1668      | l0..l_{nclc-1} are local variables in scattering function
1669      | i0..i_{niter-1} are original iteration variables
1670      | g0..g_{nparam-1} are global parameters.  */
1671
1672   ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&sctr,
1673       PBB_TRANSFORMED_SCATTERING (pbb));
1674
1675   /* Extend the iteration domain with the scattering dimensions:
1676      0..0 | 0..0 | i0..i_{niter-1} | g0..g_{nparm-1}.   */
1677   ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1678     (&ext_domain, PBB_DOMAIN (pbb));
1679   ppl_insert_dimensions_pointset (ext_domain, 0,
1680                                   pbb_nb_scattering_transform (pbb)
1681                                   + pbb_nb_local_vars (pbb));
1682
1683   /* Add to sctr the extended domain.  */
1684   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (sctr, ext_domain);
1685
1686   /* Extract the number of iterations.  */
1687   ppl_Pointset_Powerset_C_Polyhedron_space_dimension (sctr, &dim);
1688   ppl_new_Linear_Expression_with_dimension (&le, dim);
1689   ppl_set_coef (le, time_depth, 1);
1690   mpz_set_si (niter, -1);
1691   ppl_max_for_le_pointset (sctr, le, niter);
1692
1693   ppl_delete_Linear_Expression (le);
1694   ppl_delete_Pointset_Powerset_C_Polyhedron (sctr);
1695   ppl_delete_Pointset_Powerset_C_Polyhedron (ext_domain);
1696 }
1697
1698 /* Translates LOOP to LST.  */
1699
1700 static lst_p
1701 loop_to_lst (loop_p loop, VEC (poly_bb_p, heap) *bbs, int *i)
1702 {
1703   poly_bb_p pbb;
1704   VEC (lst_p, heap) *seq = VEC_alloc (lst_p, heap, 5);
1705
1706   for (; VEC_iterate (poly_bb_p, bbs, *i, pbb); (*i)++)
1707     {
1708       lst_p stmt;
1709       basic_block bb = GBB_BB (PBB_BLACK_BOX (pbb));
1710
1711       if (bb->loop_father == loop)
1712         stmt = new_lst_stmt (pbb);
1713       else if (flow_bb_inside_loop_p (loop, bb))
1714         {
1715           loop_p next = loop->inner;
1716
1717           while (next && !flow_bb_inside_loop_p (next, bb))
1718             next = next->next;
1719
1720           stmt = loop_to_lst (next, bbs, i);
1721         }
1722       else
1723         {
1724           (*i)--;
1725           return new_lst_loop (seq);
1726         }
1727
1728       VEC_safe_push (lst_p, heap, seq, stmt);
1729     }
1730
1731   return new_lst_loop (seq);
1732 }
1733
1734 /* Reads the original scattering of the SCOP and returns an LST
1735    representing it.  */
1736
1737 void
1738 scop_to_lst (scop_p scop)
1739 {
1740   lst_p res;
1741   int i, n = VEC_length (poly_bb_p, SCOP_BBS (scop));
1742   VEC (lst_p, heap) *seq = VEC_alloc (lst_p, heap, 5);
1743   sese region = SCOP_REGION (scop);
1744
1745   for (i = 0; i < n; i++)
1746     {
1747       poly_bb_p pbb = VEC_index (poly_bb_p, SCOP_BBS (scop), i);
1748       loop_p loop = outermost_loop_in_sese (region, GBB_BB (PBB_BLACK_BOX (pbb)));
1749
1750       if (loop_in_sese_p (loop, region))
1751         res = loop_to_lst (loop, SCOP_BBS (scop), &i);
1752       else
1753         res = new_lst_stmt (pbb);
1754
1755       VEC_safe_push (lst_p, heap, seq, res);
1756     }
1757
1758   res = new_lst_loop (seq);
1759   SCOP_ORIGINAL_SCHEDULE (scop) = res;
1760   SCOP_TRANSFORMED_SCHEDULE (scop) = copy_lst (res);
1761 }
1762
1763 /* Print to FILE on a new line COLUMN white spaces.  */
1764
1765 static void
1766 lst_indent_to (FILE *file, int column)
1767 {
1768   int i;
1769
1770   if (column > 0)
1771     fprintf (file, "\n#");
1772
1773   for (i = 0; i < column; i++)
1774     fprintf (file, " ");
1775 }
1776
1777 /* Print LST to FILE with INDENT spaces of indentation.  */
1778
1779 void
1780 print_lst (FILE *file, lst_p lst, int indent)
1781 {
1782   if (!lst)
1783     return;
1784
1785   lst_indent_to (file, indent);
1786
1787   if (LST_LOOP_P (lst))
1788     {
1789       int i;
1790       lst_p l;
1791
1792       if (LST_LOOP_FATHER (lst))
1793         fprintf (file, "%d (loop", lst_dewey_number (lst));
1794       else
1795         fprintf (file, "#(root");
1796
1797       FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, l)
1798         print_lst (file, l, indent + 2);
1799
1800       fprintf (file, ")");
1801     }
1802   else
1803     fprintf (file, "%d stmt_%d", lst_dewey_number (lst), pbb_index (LST_PBB (lst)));
1804 }
1805
1806 /* Print LST to STDERR.  */
1807
1808 DEBUG_FUNCTION void
1809 debug_lst (lst_p lst)
1810 {
1811   print_lst (stderr, lst, 0);
1812 }
1813
1814 /* Pretty print to FILE the loop statement tree LST in DOT format.  */
1815
1816 static void
1817 dot_lst_1 (FILE *file, lst_p lst)
1818 {
1819   if (!lst)
1820     return;
1821
1822   if (LST_LOOP_P (lst))
1823     {
1824       int i;
1825       lst_p l;
1826
1827       if (!LST_LOOP_FATHER (lst))
1828         fprintf (file, "L -> L_%d_%d\n",
1829                  lst_depth (lst),
1830                  lst_dewey_number (lst));
1831       else
1832         fprintf (file, "L_%d_%d -> L_%d_%d\n",
1833                  lst_depth (LST_LOOP_FATHER (lst)),
1834                  lst_dewey_number (LST_LOOP_FATHER (lst)),
1835                  lst_depth (lst),
1836                  lst_dewey_number (lst));
1837
1838       FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, l)
1839         dot_lst_1 (file, l);
1840     }
1841
1842   else
1843     fprintf (file, "L_%d_%d -> S_%d\n",
1844              lst_depth (LST_LOOP_FATHER (lst)),
1845              lst_dewey_number (LST_LOOP_FATHER (lst)),
1846              pbb_index (LST_PBB (lst)));
1847
1848 }
1849
1850 /* Display the LST using dotty.  */
1851
1852 DEBUG_FUNCTION void
1853 dot_lst (lst_p lst)
1854 {
1855   /* When debugging, enable the following code.  This cannot be used
1856      in production compilers because it calls "system".  */
1857 #if 0
1858   FILE *stream = fopen ("/tmp/lst.dot", "w");
1859   gcc_assert (stream);
1860
1861   fputs ("digraph all {\n", stream);
1862   dot_lst_1 (stream, lst);
1863   fputs ("}\n\n", stream);
1864   fclose (stream);
1865
1866   system ("dotty /tmp/lst.dot &");
1867 #else
1868   fputs ("digraph all {\n", stderr);
1869   dot_lst_1 (stderr, lst);
1870   fputs ("}\n\n", stderr);
1871
1872 #endif
1873 }
1874
1875 #endif
1876