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