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