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