gcc/graphite-poly.c

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