gcc/graphite-poly.c

   1 /* Graphite polyhedral representation.
   2    Copyright (C) 2009, 2010 Free Software Foundation, Inc.
   3    Contributed by Sebastian Pop <sebastian.pop@amd.com> and
   4    Tobias Grosser <grosser@fim.uni-passau.de>.
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify
   9 it under the terms of the GNU General Public License as published by
  10 the Free Software Foundation; either version 3, or (at your option)
  11 any later version.
  12
  13 GCC is distributed in the hope that it will be useful,
  14 but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 GNU General Public License for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "ggc.h"
  26 #include "tree.h"
  27 #include "rtl.h"
  28 #include "output.h"
  29 #include "basic-block.h"
  30 #include "diagnostic.h"
  31 #include "tree-pretty-print.h"
  32 #include "gimple-pretty-print.h"
  33 #include "tree-flow.h"
  34 #include "toplev.h"
  35 #include "tree-dump.h"
  36 #include "timevar.h"
  37 #include "cfgloop.h"
  38 #include "tree-chrec.h"
  39 #include "tree-data-ref.h"
  40 #include "tree-scalar-evolution.h"
  41 #include "tree-pass.h"
  42 #include "domwalk.h"
  43 #include "value-prof.h"
  44 #include "pointer-set.h"
  45 #include "gimple.h"
  46 #include "params.h"
  47 #include "graphite-cloog-util.h"
  48
  49 #ifdef HAVE_cloog
  50 #include "ppl_c.h"
  51 #include "sese.h"
  52 #include "graphite-ppl.h"
  53 #include "graphite.h"
  54 #include "graphite-poly.h"
  55 #include "graphite-dependences.h"
  56
  57 /* Return the maximal loop depth in SCOP.  */
  58
  59 int
  60 scop_max_loop_depth (scop_p scop)
  61 {
  62   int i;
  63   poly_bb_p pbb;
  64   int max_nb_loops = 0;
  65
  66   FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
  67     {
  68       int nb_loops = pbb_dim_iter_domain (pbb);
  69       if (max_nb_loops < nb_loops)
  70         max_nb_loops = nb_loops;
  71     }
  72
  73   return max_nb_loops;
  74 }
  75
  76 /* Extend the scattering matrix of PBB to MAX_SCATTERING scattering
  77    dimensions.  */
  78
  79 static void
  80 extend_scattering (poly_bb_p pbb, int max_scattering)
  81 {
  82   ppl_dimension_type nb_old_dims, nb_new_dims;
  83   int nb_added_dims, i;
  84   ppl_Coefficient_t coef;
  85   mpz_t one;
  86
  87   nb_added_dims = max_scattering - pbb_nb_scattering_transform (pbb);
  88   mpz_init (one);
  89   mpz_set_si (one, 1);
  90   ppl_new_Coefficient (&coef);
  91   ppl_assign_Coefficient_from_mpz_t (coef, one);
  92
  93   gcc_assert (nb_added_dims >= 0);
  94
  95   nb_old_dims = pbb_nb_scattering_transform (pbb) + pbb_dim_iter_domain (pbb)
  96     + scop_nb_params (PBB_SCOP (pbb));
  97   nb_new_dims = nb_old_dims + nb_added_dims;
  98
  99   ppl_insert_dimensions (PBB_TRANSFORMED_SCATTERING (pbb),
 100                          pbb_nb_scattering_transform (pbb), nb_added_dims);
 101   PBB_NB_SCATTERING_TRANSFORM (pbb) += nb_added_dims;
 102
 103   /* Add identity matrix for the added dimensions.  */
 104   for (i = max_scattering - nb_added_dims; i < max_scattering; i++)
 105     {
 106       ppl_Constraint_t cstr;
 107       ppl_Linear_Expression_t expr;
 108
 109       ppl_new_Linear_Expression_with_dimension (&expr, nb_new_dims);
 110       ppl_Linear_Expression_add_to_coefficient (expr, i, coef);
 111       ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_EQUAL);
 112       ppl_Polyhedron_add_constraint (PBB_TRANSFORMED_SCATTERING (pbb), cstr);
 113       ppl_delete_Constraint (cstr);
 114       ppl_delete_Linear_Expression (expr);
 115     }
 116
 117   ppl_delete_Coefficient (coef);
 118   mpz_clear (one);
 119 }
 120
 121 /* All scattering matrices in SCOP will have the same number of scattering
 122    dimensions.  */
 123
 124 int
 125 unify_scattering_dimensions (scop_p scop)
 126 {
 127   int i;
 128   poly_bb_p pbb;
 129   graphite_dim_t max_scattering = 0;
 130
 131   FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
 132     max_scattering = MAX (pbb_nb_scattering_transform (pbb), max_scattering);
 133
 134   FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
 135     extend_scattering (pbb, max_scattering);
 136
 137   return max_scattering;
 138 }
 139
 140 /* Print to FILE the pdr PH in OpenScop format.  NB_SUBSCRIPTS is the number
 141    of subscripts in PH, ALIAS_SET_DIM is the dimension of the alias set and
 142    NB_PARAMS is the number of parameters in PH.  */
 143
 144 static void
 145 openscop_print_pdr_polyhedron (FILE *file, ppl_const_Polyhedron_t ph,
 146                                int nb_subscripts, int alias_set_dimension,
 147                                int nb_params)
 148 {
 149   int input, locals, output;
 150   ppl_dimension_type alias_set_dim = (ppl_dimension_type) alias_set_dimension;
 151   ppl_dimension_type sub_dim_last = alias_set_dim + nb_subscripts;
 152   ppl_dimension_type *map, i, ph_space_dim = sub_dim_last + 1;
 153   ppl_Polyhedron_t pph;
 154
 155   ppl_new_C_Polyhedron_from_C_Polyhedron (&pph, ph);
 156
 157   map = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, ph_space_dim);
 158
 159   for (i = 0; i < alias_set_dim - 1; i++)
 160     map[i] = nb_subscripts + 1 + i;
 161
 162   for (i = alias_set_dim - 1; i < sub_dim_last; i++)
 163     map[i] = i - alias_set_dim + 1;
 164
 165   ppl_Polyhedron_map_space_dimensions (pph, map, ph_space_dim - 1);
 166
 167   locals = 0;
 168   input = alias_set_dim - nb_params - 1;
 169
 170   /* According to OpenScop specification, the alias set column is a part of
 171      the output columns.  */
 172   output = nb_subscripts + 1;
 173
 174   openscop_print_polyhedron_matrix (file, pph, output, input, locals, nb_params);
 175 }
 176
 177 /* Print to FILE the powerset PDR.  NB_SUBSCRIPTS is the number of subscripts
 178    in PDR, ALIAS_SET_DIM is the dimension of the alias set in PDR and
 179    NB_PARAMS is the number of parameters in PDR.  */
 180
 181 static void
 182 openscop_print_pdr_powerset (FILE *file,
 183                              ppl_Pointset_Powerset_C_Polyhedron_t ps,
 184                              int nb_subscripts,
 185                              int alias_set_dim,
 186                              int nb_params)
 187 {
 188   size_t nb_disjuncts;
 189   ppl_Pointset_Powerset_C_Polyhedron_iterator_t it, end;
 190
 191   ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&it);
 192   ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&end);
 193
 194   ppl_Pointset_Powerset_C_Polyhedron_size (ps, &nb_disjuncts);
 195   fprintf (file, "%d\n", (int) nb_disjuncts);
 196
 197   for (ppl_Pointset_Powerset_C_Polyhedron_iterator_begin (ps, it),
 198        ppl_Pointset_Powerset_C_Polyhedron_iterator_end (ps, end);
 199        !ppl_Pointset_Powerset_C_Polyhedron_iterator_equal_test (it, end);
 200        ppl_Pointset_Powerset_C_Polyhedron_iterator_increment (it))
 201     {
 202       ppl_const_Polyhedron_t ph;
 203
 204       ppl_Pointset_Powerset_C_Polyhedron_iterator_dereference (it, &ph);
 205       openscop_print_pdr_polyhedron (file, ph, nb_subscripts, alias_set_dim,
 206                                      nb_params);
 207     }
 208
 209   ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (it);
 210   ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (end);
 211 }
 212
 213 /* Print to FILE the powerset PS in its OpenScop matrix form.  */
 214
 215 static void
 216 openscop_print_powerset_matrix (FILE *file,
 217                                 ppl_Pointset_Powerset_C_Polyhedron_t ps,
 218                                 int output, int input, int locals,
 219                                 int params)
 220 {
 221   size_t nb_disjuncts;
 222   ppl_Pointset_Powerset_C_Polyhedron_iterator_t it, end;
 223
 224   ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&it);
 225   ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&end);
 226
 227   ppl_Pointset_Powerset_C_Polyhedron_size (ps, &nb_disjuncts);
 228   fprintf (file, "%d\n", (int) nb_disjuncts);
 229
 230   for (ppl_Pointset_Powerset_C_Polyhedron_iterator_begin (ps, it),
 231        ppl_Pointset_Powerset_C_Polyhedron_iterator_end (ps, end);
 232        !ppl_Pointset_Powerset_C_Polyhedron_iterator_equal_test (it, end);
 233        ppl_Pointset_Powerset_C_Polyhedron_iterator_increment (it))
 234     {
 235       ppl_const_Polyhedron_t ph;
 236
 237       ppl_Pointset_Powerset_C_Polyhedron_iterator_dereference (it, &ph);
 238       openscop_print_polyhedron_matrix (file, ph, output, input, locals,
 239                                         params);
 240     }
 241
 242   ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (it);
 243   ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (end);
 244 }
 245
 246 /* Prints to FILE the scattering function of PBB in OpenScop format, at some
 247    VERBOSITY level.  */
 248
 249 static void
 250 openscop_print_scattering_function_1 (FILE *file, poly_bb_p pbb, int verbosity)
 251 {
 252   graphite_dim_t i;
 253   ppl_const_Polyhedron_t ph;
 254
 255   if (verbosity > 0)
 256     {
 257       fprintf (file, "# scattering bb_%d (\n", pbb_index (pbb));
 258       fprintf (file, "#  eq");
 259
 260       for (i = 0; i < pbb_nb_scattering_transform (pbb); i++)
 261         fprintf (file, "     s%d", (int) i);
 262
 263       for (i = 0; i < pbb_nb_local_vars (pbb); i++)
 264         fprintf (file, "    lv%d", (int) i);
 265
 266       for (i = 0; i < pbb_dim_iter_domain (pbb); i++)
 267         fprintf (file, "     i%d", (int) i);
 268
 269       for (i = 0; i < pbb_nb_params (pbb); i++)
 270         fprintf (file, "     p%d", (int) i);
 271
 272       fprintf (file, "    cst\n");
 273     }
 274
 275   /* Number of disjunct components.  Remove this when
 276      PBB_TRANSFORMED_SCATTERING will be a pointset_powerset.  */
 277   fprintf (file, "1\n");
 278
 279   ph = PBB_TRANSFORMED_SCATTERING (pbb)
 280     ? PBB_TRANSFORMED_SCATTERING (pbb)
 281     : PBB_ORIGINAL_SCATTERING (pbb);
 282
 283   openscop_print_polyhedron_matrix (file, ph,
 284                                     pbb_nb_scattering_transform (pbb),
 285                                     pbb_dim_iter_domain (pbb),
 286                                     pbb_nb_local_vars (pbb),
 287                                     pbb_nb_params (pbb));
 288
 289   if (verbosity > 0)
 290     fprintf (file, "#)\n");
 291 }
 292
 293 /* Prints to FILE the scattering function of PBB, at some VERBOSITY
 294    level.  */
 295
 296 static void
 297 print_scattering_function_1 (FILE *file, poly_bb_p pbb, int verbosity)
 298 {
 299   graphite_dim_t i;
 300
 301   if (verbosity > 0)
 302     {
 303       fprintf (file, "# scattering bb_%d (\n", pbb_index (pbb));
 304       fprintf (file, "#  eq");
 305
 306       for (i = 0; i < pbb_nb_scattering_transform (pbb); i++)
 307         fprintf (file, "     s%d", (int) i);
 308
 309       for (i = 0; i < pbb_nb_local_vars (pbb); i++)
 310         fprintf (file, "    lv%d", (int) i);
 311
 312       for (i = 0; i < pbb_dim_iter_domain (pbb); i++)
 313         fprintf (file, "     i%d", (int) i);
 314
 315       for (i = 0; i < pbb_nb_params (pbb); i++)
 316         fprintf (file, "     p%d", (int) i);
 317
 318       fprintf (file, "    cst\n");
 319     }
 320
 321   /* Number of disjunct components.  Remove this when
 322      PBB_TRANSFORMED_SCATTERING will be a pointset_powerset.  */
 323   fprintf (file, "1\n");
 324   ppl_print_polyhedron_matrix (file, PBB_TRANSFORMED_SCATTERING (pbb)
 325                                ? PBB_TRANSFORMED_SCATTERING (pbb)
 326                                : PBB_ORIGINAL_SCATTERING (pbb));
 327
 328   if (verbosity > 0)
 329     fprintf (file, "#)\n");
 330 }
 331
 332 /* Prints to FILE the scattering function of PBB, at some VERBOSITY
 333    level.  */
 334
 335 void
 336 print_scattering_function (FILE *file, poly_bb_p pbb, int verbosity)
 337 {
 338   if (!PBB_TRANSFORMED (pbb))
 339     return;
 340
 341   if (PBB_TRANSFORMED_SCATTERING (pbb)
 342       || PBB_ORIGINAL_SCATTERING (pbb))
 343     {
 344       if (verbosity > 0)
 345         fprintf (file, "# Scattering function is provided\n");
 346
 347       fprintf (file, "1\n");
 348     }
 349   else
 350     {
 351       if (verbosity > 0)
 352         fprintf (file, "# Scattering function is not provided\n");
 353
 354       fprintf (file, "0\n");
 355       return;
 356     }
 357
 358   openscop_print_scattering_function_1 (file, pbb, verbosity);
 359
 360   if (verbosity > 0)
 361     fprintf (file, "# Scattering names are not provided\n");
 362
 363   fprintf (file, "0\n");
 364
 365 }
 366
 367 /* Prints to FILE the iteration domain of PBB, at some VERBOSITY
 368    level.  */
 369
 370 void
 371 print_iteration_domain (FILE *file, poly_bb_p pbb, int verbosity)
 372 {
 373   print_pbb_domain (file, pbb, verbosity);
 374 }
 375
 376 /* Prints to FILE the scattering functions of every PBB of SCOP.  */
 377
 378 void
 379 print_scattering_functions (FILE *file, scop_p scop, int verbosity)
 380 {
 381   int i;
 382   poly_bb_p pbb;
 383
 384   FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
 385     print_scattering_function (file, pbb, verbosity);
 386 }
 387
 388 /* Prints to FILE the iteration domains of every PBB of SCOP, at some
 389    VERBOSITY level.  */
 390
 391 void
 392 print_iteration_domains (FILE *file, scop_p scop, int verbosity)
 393 {
 394   int i;
 395   poly_bb_p pbb;
 396
 397   FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
 398     print_iteration_domain (file, pbb, verbosity);
 399 }
 400
 401 /* Prints to STDERR the scattering function of PBB, at some VERBOSITY
 402    level.  */
 403
 404 DEBUG_FUNCTION void
 405 debug_scattering_function (poly_bb_p pbb, int verbosity)
 406 {
 407   print_scattering_function (stderr, pbb, verbosity);
 408 }
 409
 410 /* Prints to STDERR the iteration domain of PBB, at some VERBOSITY
 411    level.  */
 412
 413 DEBUG_FUNCTION void
 414 debug_iteration_domain (poly_bb_p pbb, int verbosity)
 415 {
 416   print_iteration_domain (stderr, pbb, verbosity);
 417 }
 418
 419 /* Prints to STDERR the scattering functions of every PBB of SCOP, at
 420    some VERBOSITY level.  */
 421
 422 DEBUG_FUNCTION void
 423 debug_scattering_functions (scop_p scop, int verbosity)
 424 {
 425   print_scattering_functions (stderr, scop, verbosity);
 426 }
 427
 428 /* Prints to STDERR the iteration domains of every PBB of SCOP, at
 429    some VERBOSITY level.  */
 430
 431 DEBUG_FUNCTION void
 432 debug_iteration_domains (scop_p scop, int verbosity)
 433 {
 434   print_iteration_domains (stderr, scop, verbosity);
 435 }
 436
 437
 438 /* Apply graphite transformations to all the basic blocks of SCOP.  */
 439
 440 bool
 441 apply_poly_transforms (scop_p scop)
 442 {
 443   bool transform_done = false;
 444
 445   /* Generate code even if we did not apply any real transformation.
 446      This also allows to check the performance for the identity
 447      transformation: GIMPLE -> GRAPHITE -> GIMPLE
 448      Keep in mind that CLooG optimizes in control, so the loop structure
 449      may change, even if we only use -fgraphite-identity.  */
 450   if (flag_graphite_identity)
 451     transform_done = true;
 452
 453   if (flag_loop_parallelize_all)
 454     transform_done = true;
 455
 456   if (flag_loop_block)
 457     transform_done |= scop_do_block (scop);
 458   else
 459     {
 460       if (flag_loop_strip_mine)
 461         transform_done |= scop_do_strip_mine (scop);
 462
 463       if (flag_loop_interchange)
 464         transform_done |= scop_do_interchange (scop);
 465     }
 466
 467   return transform_done;
 468 }
 469
 470 /* Returns true when it PDR1 is a duplicate of PDR2: same PBB, and
 471    their ACCESSES, TYPE, and NB_SUBSCRIPTS are the same.  */
 472
 473 static inline bool
 474 can_collapse_pdrs (poly_dr_p pdr1, poly_dr_p pdr2)
 475 {
 476   bool res;
 477   ppl_Pointset_Powerset_C_Polyhedron_t af1, af2, diff;
 478
 479   if (PDR_PBB (pdr1) != PDR_PBB (pdr2)
 480       || PDR_NB_SUBSCRIPTS (pdr1) != PDR_NB_SUBSCRIPTS (pdr2)
 481       || PDR_TYPE (pdr1) != PDR_TYPE (pdr2))
 482     return false;
 483
 484   af1 = PDR_ACCESSES (pdr1);
 485   af2 = PDR_ACCESSES (pdr2);
 486   ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
 487     (&diff, af1);
 488   ppl_Pointset_Powerset_C_Polyhedron_difference_assign (diff, af2);
 489
 490   res = ppl_Pointset_Powerset_C_Polyhedron_is_empty (diff);
 491   ppl_delete_Pointset_Powerset_C_Polyhedron (diff);
 492   return res;
 493 }
 494
 495 /* Removes duplicated data references in PBB.  */
 496
 497 void
 498 pbb_remove_duplicate_pdrs (poly_bb_p pbb)
 499 {
 500   int i, j;
 501   poly_dr_p pdr1, pdr2;
 502   unsigned n = VEC_length (poly_dr_p, PBB_DRS (pbb));
 503   VEC (poly_dr_p, heap) *collapsed = VEC_alloc (poly_dr_p, heap, n);
 504
 505   FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb), i, pdr1)
 506     FOR_EACH_VEC_ELT (poly_dr_p, collapsed, j, pdr2)
 507       if (!can_collapse_pdrs (pdr1, pdr2))
 508         VEC_quick_push (poly_dr_p, collapsed, pdr1);
 509
 510   VEC_free (poly_dr_p, heap, collapsed);
 511   PBB_PDR_DUPLICATES_REMOVED (pbb) = true;
 512 }
 513
 514 /* Create a new polyhedral data reference and add it to PBB.  It is
 515    defined by its ACCESSES, its TYPE, and the number of subscripts
 516    NB_SUBSCRIPTS.  */
 517
 518 void
 519 new_poly_dr (poly_bb_p pbb, int dr_base_object_set,
 520              ppl_Pointset_Powerset_C_Polyhedron_t accesses,
 521              enum poly_dr_type type, void *cdr, graphite_dim_t nb_subscripts)
 522 {
 523   static int id = 0;
 524   poly_dr_p pdr = XNEW (struct poly_dr);
 525
 526   PDR_ID (pdr) = id++;
 527   PDR_BASE_OBJECT_SET (pdr) = dr_base_object_set;
 528   PDR_NB_REFS (pdr) = 1;
 529   PDR_PBB (pdr) = pbb;
 530   PDR_ACCESSES (pdr) = accesses;
 531   PDR_TYPE (pdr) = type;
 532   PDR_CDR (pdr) = cdr;
 533   PDR_NB_SUBSCRIPTS (pdr) = nb_subscripts;
 534   VEC_safe_push (poly_dr_p, heap, PBB_DRS (pbb), pdr);
 535 }
 536
 537 /* Free polyhedral data reference PDR.  */
 538
 539 void
 540 free_poly_dr (poly_dr_p pdr)
 541 {
 542   ppl_delete_Pointset_Powerset_C_Polyhedron (PDR_ACCESSES (pdr));
 543   XDELETE (pdr);
 544 }
 545
 546 /* Create a new polyhedral black box.  */
 547
 548 void
 549 new_poly_bb (scop_p scop, void *black_box, bool reduction)
 550 {
 551   poly_bb_p pbb = XNEW (struct poly_bb);
 552
 553   PBB_DOMAIN (pbb) = NULL;
 554   PBB_SCOP (pbb) = scop;
 555   pbb_set_black_box (pbb, black_box);
 556   PBB_TRANSFORMED (pbb) = NULL;
 557   PBB_SAVED (pbb) = NULL;
 558   PBB_ORIGINAL (pbb) = NULL;
 559   PBB_DRS (pbb) = VEC_alloc (poly_dr_p, heap, 3);
 560   PBB_IS_REDUCTION (pbb) = reduction;
 561   PBB_PDR_DUPLICATES_REMOVED (pbb) = false;
 562   VEC_safe_push (poly_bb_p, heap, SCOP_BBS (scop), pbb);
 563 }
 564
 565 /* Free polyhedral black box.  */
 566
 567 void
 568 free_poly_bb (poly_bb_p pbb)
 569 {
 570   int i;
 571   poly_dr_p pdr;
 572
 573   ppl_delete_Pointset_Powerset_C_Polyhedron (PBB_DOMAIN (pbb));
 574
 575   if (PBB_TRANSFORMED (pbb))
 576     poly_scattering_free (PBB_TRANSFORMED (pbb));
 577
 578   if (PBB_SAVED (pbb))
 579     poly_scattering_free (PBB_SAVED (pbb));
 580
 581   if (PBB_ORIGINAL (pbb))
 582     poly_scattering_free (PBB_ORIGINAL (pbb));
 583
 584   if (PBB_DRS (pbb))
 585     FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb), i, pdr)
 586       free_poly_dr (pdr);
 587
 588   VEC_free (poly_dr_p, heap, PBB_DRS (pbb));
 589   XDELETE (pbb);
 590 }
 591
 592 static void
 593 print_pdr_access_layout (FILE *file, poly_bb_p pbb, poly_dr_p pdr)
 594 {
 595   graphite_dim_t i;
 596
 597   fprintf (file, "#  eq");
 598
 599   fprintf (file, "   alias");
 600
 601   for (i = 0; i < PDR_NB_SUBSCRIPTS (pdr); i++)
 602     fprintf (file, "   sub%d", (int) i);
 603
 604   for (i = 0; i < pbb_dim_iter_domain (pbb); i++)
 605     fprintf (file, "     i%d", (int) i);
 606
 607   for (i = 0; i < pbb_nb_params (pbb); i++)
 608     fprintf (file, "     p%d", (int) i);
 609
 610   fprintf (file, "    cst\n");
 611 }
 612
 613 /* Prints to FILE the polyhedral data reference PDR, at some VERBOSITY
 614    level.  */
 615
 616 void
 617 print_pdr (FILE *file, poly_dr_p pdr, int verbosity)
 618 {
 619   int alias_set_dim;
 620
 621   if (verbosity > 1)
 622     {
 623       fprintf (file, "# pdr_%d (", PDR_ID (pdr));
 624
 625       switch (PDR_TYPE (pdr))
 626         {
 627         case PDR_READ:
 628           fprintf (file, "read \n");
 629           break;
 630
 631         case PDR_WRITE:
 632           fprintf (file, "write \n");
 633           break;
 634
 635         case PDR_MAY_WRITE:
 636           fprintf (file, "may_write \n");
 637           break;
 638
 639         default:
 640           gcc_unreachable ();
 641         }
 642
 643       dump_data_reference (file, (data_reference_p) PDR_CDR (pdr));
 644     }
 645
 646   if (verbosity > 0)
 647     {
 648       fprintf (file, "# data accesses (\n");
 649       print_pdr_access_layout (file, PDR_PBB (pdr), pdr);
 650     }
 651
 652   alias_set_dim = pdr_alias_set_dim (pdr) + 1;
 653
 654   openscop_print_pdr_powerset (file,
 655                                PDR_ACCESSES (pdr),
 656                                PDR_NB_SUBSCRIPTS (pdr),
 657                                alias_set_dim,
 658                                pbb_nb_params (PDR_PBB (pdr)));
 659
 660   if (verbosity > 0)
 661     fprintf (file, "#)\n");
 662
 663   if (verbosity > 1)
 664     fprintf (file, "#)\n");
 665 }
 666
 667 /* Prints to STDERR the polyhedral data reference PDR, at some
 668    VERBOSITY level.  */
 669
 670 DEBUG_FUNCTION void
 671 debug_pdr (poly_dr_p pdr, int verbosity)
 672 {
 673   print_pdr (stderr, pdr, verbosity);
 674 }
 675
 676 /* Creates a new SCOP containing REGION.  */
 677
 678 scop_p
 679 new_scop (void *region)
 680 {
 681   scop_p scop = XNEW (struct scop);
 682
 683   SCOP_CONTEXT (scop) = NULL;
 684   scop_set_region (scop, region);
 685   SCOP_BBS (scop) = VEC_alloc (poly_bb_p, heap, 3);
 686   SCOP_ORIGINAL_PDDRS (scop) = htab_create (10, hash_poly_ddr_p,
 687                                             eq_poly_ddr_p, free_poly_ddr);
 688   SCOP_ORIGINAL_SCHEDULE (scop) = NULL;
 689   SCOP_TRANSFORMED_SCHEDULE (scop) = NULL;
 690   SCOP_SAVED_SCHEDULE (scop) = NULL;
 691   POLY_SCOP_P (scop) = false;
 692
 693   return scop;
 694 }
 695
 696 /* Deletes SCOP.  */
 697
 698 void
 699 free_scop (scop_p scop)
 700 {
 701   int i;
 702   poly_bb_p pbb;
 703
 704   FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
 705     free_poly_bb (pbb);
 706
 707   VEC_free (poly_bb_p, heap, SCOP_BBS (scop));
 708
 709   if (SCOP_CONTEXT (scop))
 710     ppl_delete_Pointset_Powerset_C_Polyhedron (SCOP_CONTEXT (scop));
 711
 712   htab_delete (SCOP_ORIGINAL_PDDRS (scop));
 713   free_lst (SCOP_ORIGINAL_SCHEDULE (scop));
 714   free_lst (SCOP_TRANSFORMED_SCHEDULE (scop));
 715   free_lst (SCOP_SAVED_SCHEDULE (scop));
 716   XDELETE (scop);
 717 }
 718
 719 /* Print to FILE the domain of PBB in OpenScop format, at some VERBOSITY
 720    level.  */
 721
 722 static void
 723 openscop_print_pbb_domain (FILE *file, poly_bb_p pbb, int verbosity)
 724 {
 725   graphite_dim_t i;
 726   gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
 727
 728   if (!PBB_DOMAIN (pbb))
 729     return;
 730
 731   if (verbosity > 0)
 732     {
 733       fprintf (file, "\n# Iteration domain of bb_%d (\n", GBB_BB (gbb)->index);
 734       fprintf (file, "#  eq");
 735
 736       for (i = 0; i < pbb_dim_iter_domain (pbb); i++)
 737         fprintf (file, "     i%d", (int) i);
 738
 739       for (i = 0; i < pbb_nb_params (pbb); i++)
 740         fprintf (file, "     p%d", (int) i);
 741
 742       fprintf (file, "    cst\n");
 743     }
 744
 745   if (PBB_DOMAIN (pbb))
 746     openscop_print_powerset_matrix (file, PBB_DOMAIN (pbb),
 747                                     pbb_dim_iter_domain (pbb),
 748                                     0,
 749                                     0,
 750                                     pbb_nb_params (pbb));
 751   else
 752     fprintf (file, "0\n");
 753
 754   if (verbosity > 0)
 755     fprintf (file, "#)\n");
 756 }
 757
 758 /* Print to FILE the domain of PBB, at some VERBOSITY level.  */
 759
 760 void
 761 print_pbb_domain (FILE *file, poly_bb_p pbb, int verbosity)
 762 {
 763   graphite_dim_t i;
 764   gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
 765
 766   if (!PBB_DOMAIN (pbb))
 767     return;
 768
 769   if (verbosity > 0)
 770     {
 771       fprintf (file, "# Iteration domain of bb_%d (\n", GBB_BB (gbb)->index);
 772       fprintf (file, "#  eq");
 773
 774       for (i = 0; i < pbb_dim_iter_domain (pbb); i++)
 775         fprintf (file, "     i%d", (int) i);
 776
 777       for (i = 0; i < pbb_nb_params (pbb); i++)
 778         fprintf (file, "     p%d", (int) i);
 779
 780       fprintf (file, "    cst\n");
 781     }
 782
 783   if (PBB_DOMAIN (pbb))
 784     ppl_print_powerset_matrix (file, PBB_DOMAIN (pbb));
 785   else
 786     fprintf (file, "0\n");
 787
 788   if (verbosity > 0)
 789     fprintf (file, "#)\n");
 790 }
 791
 792 /* Dump the cases of a graphite basic block GBB on FILE.  */
 793
 794 static void
 795 dump_gbb_cases (FILE *file, gimple_bb_p gbb)
 796 {
 797   int i;
 798   gimple stmt;
 799   VEC (gimple, heap) *cases;
 800
 801   if (!gbb)
 802     return;
 803
 804   cases = GBB_CONDITION_CASES (gbb);
 805   if (VEC_empty (gimple, cases))
 806     return;
 807
 808   fprintf (file, "# cases bb_%d (\n", GBB_BB (gbb)->index);
 809
 810   FOR_EACH_VEC_ELT (gimple, cases, i, stmt)
 811     {
 812       fprintf (file, "# ");
 813       print_gimple_stmt (file, stmt, 0, 0);
 814     }
 815
 816   fprintf (file, "#)\n");
 817 }
 818
 819 /* Dump conditions of a graphite basic block GBB on FILE.  */
 820
 821 static void
 822 dump_gbb_conditions (FILE *file, gimple_bb_p gbb)
 823 {
 824   int i;
 825   gimple stmt;
 826   VEC (gimple, heap) *conditions;
 827
 828   if (!gbb)
 829     return;
 830
 831   conditions = GBB_CONDITIONS (gbb);
 832   if (VEC_empty (gimple, conditions))
 833     return;
 834
 835   fprintf (file, "# conditions bb_%d (\n", GBB_BB (gbb)->index);
 836
 837   FOR_EACH_VEC_ELT (gimple, conditions, i, stmt)
 838     {
 839       fprintf (file, "# ");
 840       print_gimple_stmt (file, stmt, 0, 0);
 841     }
 842
 843   fprintf (file, "#)\n");
 844 }
 845
 846 /* Print to FILE all the data references of PBB, at some VERBOSITY
 847    level.  */
 848
 849 void
 850 print_pdrs (FILE *file, poly_bb_p pbb, int verbosity)
 851 {
 852   int i;
 853   poly_dr_p pdr;
 854   int nb_reads = 0;
 855   int nb_writes = 0;
 856
 857   if (VEC_length (poly_dr_p, PBB_DRS (pbb)) == 0)
 858     {
 859       if (verbosity > 0)
 860         fprintf (file, "# Access informations are not provided\n");\
 861       fprintf (file, "0\n");
 862       return;
 863     }
 864
 865   if (verbosity > 1)
 866     fprintf (file, "# Data references (\n");
 867
 868   if (verbosity > 0)
 869     fprintf (file, "# Access informations are provided\n");
 870   fprintf (file, "1\n");
 871
 872   FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb), i, pdr)
 873     if (PDR_TYPE (pdr) == PDR_READ)
 874       nb_reads++;
 875     else
 876       nb_writes++;
 877
 878   if (verbosity > 1)
 879     fprintf (file, "# Read data references (\n");
 880
 881   if (verbosity > 0)
 882     fprintf (file, "# Read access informations\n");
 883   fprintf (file, "%d\n", nb_reads);
 884
 885   FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb), i, pdr)
 886     if (PDR_TYPE (pdr) == PDR_READ)
 887       print_pdr (file, pdr, verbosity);
 888
 889   if (verbosity > 1)
 890     fprintf (file, "#)\n");
 891
 892   if (verbosity > 1)
 893     fprintf (file, "# Write data references (\n");
 894
 895   if (verbosity > 0)
 896     fprintf (file, "# Write access informations\n");
 897   fprintf (file, "%d\n", nb_writes);
 898
 899   FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb), i, pdr)
 900     if (PDR_TYPE (pdr) != PDR_READ)
 901       print_pdr (file, pdr, verbosity);
 902
 903   if (verbosity > 1)
 904     fprintf (file, "#)\n");
 905
 906   if (verbosity > 1)
 907     fprintf (file, "#)\n");
 908 }
 909
 910 /* Print to STDERR all the data references of PBB.  */
 911
 912 DEBUG_FUNCTION void
 913 debug_pdrs (poly_bb_p pbb, int verbosity)
 914 {
 915   print_pdrs (stderr, pbb, verbosity);
 916 }
 917
 918 /* Print to FILE the body of PBB, at some VERBOSITY level.
 919    If statement_body_provided is false statement body is not printed.  */
 920
 921 static void
 922 print_pbb_body (FILE *file, poly_bb_p pbb, int verbosity,
 923                 bool statement_body_provided)
 924 {
 925   if (verbosity > 1)
 926     fprintf (file, "# Body (\n");
 927
 928   if (!statement_body_provided)
 929   {
 930     if (verbosity > 0)
 931       fprintf (file, "# Statement body is not provided\n");
 932
 933    fprintf (file, "0\n");
 934    return;
 935   }
 936
 937   if (verbosity > 0)
 938     fprintf (file, "# Statement body is provided\n");
 939   fprintf (file, "1\n");
 940
 941   if (verbosity > 0)
 942     fprintf (file, "# Original iterator names\n# Iterator names are not provided yet.\n");
 943
 944   if (verbosity > 0)
 945     fprintf (file, "# Statement body\n");
 946
 947   fprintf (file, "{\n");
 948   dump_bb (pbb_bb (pbb), file, 0);
 949   fprintf (file, "}\n");
 950
 951   if (verbosity > 1)
 952     fprintf (file, "#)\n");
 953 }
 954
 955 /* Print to FILE the domain and scattering function of PBB, at some
 956    VERBOSITY level.  */
 957
 958 void
 959 print_pbb (FILE *file, poly_bb_p pbb, int verbosity)
 960 {
 961   if (verbosity > 1)
 962     {
 963       fprintf (file, "# pbb_%d (\n", pbb_index (pbb));
 964       dump_gbb_conditions (file, PBB_BLACK_BOX (pbb));
 965       dump_gbb_cases (file, PBB_BLACK_BOX (pbb));
 966     }
 967
 968   openscop_print_pbb_domain (file, pbb, verbosity);
 969   print_scattering_function (file, pbb, verbosity);
 970   print_pdrs (file, pbb, verbosity);
 971   print_pbb_body (file, pbb, verbosity, false);
 972
 973   if (verbosity > 1)
 974     fprintf (file, "#)\n");
 975 }
 976
 977 /* Print to FILE the parameters of SCOP, at some VERBOSITY level.  */
 978
 979 void
 980 print_scop_params (FILE *file, scop_p scop, int verbosity)
 981 {
 982   int i;
 983   tree t;
 984
 985   if (verbosity > 1)
 986     fprintf (file, "# parameters (\n");
 987
 988   if (VEC_length (tree, SESE_PARAMS (SCOP_REGION (scop))))
 989     {
 990       if (verbosity > 0)
 991         fprintf (file, "# Parameter names are provided\n");
 992
 993       fprintf (file, "1\n");
 994
 995       if (verbosity > 0)
 996         fprintf (file, "# Parameter names\n");
 997     }
 998   else
 999     {
1000       if (verbosity > 0)
1001         fprintf (file, "# Parameter names are not provided\n");
1002       fprintf (file, "0\n");
1003     }
1004
1005   FOR_EACH_VEC_ELT (tree, SESE_PARAMS (SCOP_REGION (scop)), i, t)
1006     {
1007       print_generic_expr (file, t, 0);
1008       fprintf (file, " ");
1009     }
1010
1011   fprintf (file, "\n");
1012
1013   if (verbosity > 1)
1014     fprintf (file, "#)\n");
1015 }
1016
1017 /* Print to FILE the context of SCoP in OpenScop format, at some VERBOSITY
1018    level.  */
1019
1020 static void
1021 openscop_print_scop_context (FILE *file, scop_p scop, int verbosity)
1022 {
1023   graphite_dim_t i;
1024
1025   if (verbosity > 0)
1026     {
1027       fprintf (file, "# Context (\n");
1028       fprintf (file, "#  eq");
1029
1030       for (i = 0; i < scop_nb_params (scop); i++)
1031         fprintf (file, "     p%d", (int) i);
1032
1033       fprintf (file, "    cst\n");
1034     }
1035
1036   if (SCOP_CONTEXT (scop))
1037     openscop_print_powerset_matrix (file, SCOP_CONTEXT (scop), 0, 0, 0,
1038                                     scop_nb_params (scop));
1039   else
1040     fprintf (file, "0 %d 0 0 0 %d\n", (int) scop_nb_params (scop) + 2,
1041              (int) scop_nb_params (scop));
1042
1043   if (verbosity > 0)
1044     fprintf (file, "# )\n");
1045 }
1046
1047 /* Print to FILE the context of SCoP, at some VERBOSITY level.  */
1048
1049 void
1050 print_scop_context (FILE *file, scop_p scop, int verbosity)
1051 {
1052   graphite_dim_t i;
1053
1054   if (verbosity > 0)
1055     {
1056       fprintf (file, "# Context (\n");
1057       fprintf (file, "#  eq");
1058
1059       for (i = 0; i < scop_nb_params (scop); i++)
1060         fprintf (file, "     p%d", (int) i);
1061
1062       fprintf (file, "    cst\n");
1063     }
1064
1065   if (SCOP_CONTEXT (scop))
1066     ppl_print_powerset_matrix (file, SCOP_CONTEXT (scop));
1067   else
1068     fprintf (file, "0 %d\n", (int) scop_nb_params (scop) + 2);
1069
1070   if (verbosity > 0)
1071     fprintf (file, "# )\n");
1072 }
1073
1074 /* Print to FILE the SCOP header: context, parameters, and statements
1075    number.  */
1076
1077 static void
1078 print_scop_header (FILE *file, scop_p scop, int verbosity)
1079 {
1080   fprintf (file, "SCoP 1\n#(\n");
1081   fprintf (file, "# Language\nGimple\n");
1082   openscop_print_scop_context (file, scop, verbosity);
1083   print_scop_params (file, scop, verbosity);
1084
1085   if (verbosity > 0)
1086     fprintf (file, "# Number of statements\n");
1087
1088   fprintf (file, "%d\n",VEC_length (poly_bb_p, SCOP_BBS (scop)));
1089 }
1090
1091 /* Print to FILE the SCOP, at some VERBOSITY level.  */
1092
1093 void
1094 print_scop (FILE *file, scop_p scop, int verbosity)
1095 {
1096   int i;
1097   poly_bb_p pbb;
1098
1099   print_scop_header (file, scop, verbosity);
1100
1101   FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
1102     print_pbb (file, pbb, verbosity);
1103
1104   if (verbosity > 1)
1105     {
1106       fprintf (file, "# original_lst (\n");
1107       print_lst (file, SCOP_ORIGINAL_SCHEDULE (scop), 0);
1108       fprintf (file, "\n#)\n");
1109
1110       fprintf (file, "# transformed_lst (\n");
1111       print_lst (file, SCOP_TRANSFORMED_SCHEDULE (scop), 0);
1112       fprintf (file, "\n#)\n");
1113     }
1114
1115   fprintf (file, "#)\n");
1116 }
1117
1118 /* Print to FILE the input file that CLooG would expect as input, at
1119    some VERBOSITY level.  */
1120
1121 void
1122 print_cloog (FILE *file, scop_p scop, int verbosity)
1123 {
1124   int i;
1125   poly_bb_p pbb;
1126
1127   fprintf (file, "# SCoP (generated by GCC/Graphite\n");
1128   if (verbosity > 0)
1129     fprintf (file, "# CLooG output language\n");
1130   fprintf (file, "c\n");
1131
1132   print_scop_context (file, scop, verbosity);
1133   print_scop_params (file, scop, verbosity);
1134
1135   if (verbosity > 0)
1136     fprintf (file, "# Number of statements\n");
1137
1138   fprintf (file, "%d\n", VEC_length (poly_bb_p, SCOP_BBS (scop)));
1139
1140   FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
1141     {
1142       if (verbosity > 1)
1143         fprintf (file, "# pbb_%d (\n", pbb_index (pbb));
1144
1145       print_pbb_domain (file, pbb, verbosity);
1146       fprintf (file, "0 0 0");
1147
1148       if (verbosity > 0)
1149         fprintf (file, "# For future CLooG options.\n");
1150       else
1151         fprintf (file, "\n");
1152
1153       if (verbosity > 1)
1154         fprintf (file, "#)\n");
1155     }
1156
1157   fprintf (file, "0");
1158   if (verbosity > 0)
1159     fprintf (file, "# Don't set the iterator names.\n");
1160   else
1161     fprintf (file, "\n");
1162
1163   if (verbosity > 0)
1164     fprintf (file, "# Number of scattering functions\n");
1165
1166   fprintf (file, "%d\n", VEC_length (poly_bb_p, SCOP_BBS (scop)));
1167   unify_scattering_dimensions (scop);
1168
1169   FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
1170     {
1171       if (!PBB_TRANSFORMED (pbb)
1172           || !(PBB_TRANSFORMED_SCATTERING (pbb)
1173                || PBB_ORIGINAL_SCATTERING (pbb)))
1174         continue;
1175
1176       if (verbosity > 1)
1177         fprintf (file, "# pbb_%d (\n", pbb_index (pbb));
1178
1179       print_scattering_function_1 (file, pbb, verbosity);
1180
1181       if (verbosity > 1)
1182         fprintf (file, "#)\n");
1183     }
1184
1185   fprintf (file, "0");
1186   if (verbosity > 0)
1187     fprintf (file, "# Don't set the scattering dimension names.\n");
1188   else
1189     fprintf (file, "\n");
1190
1191   fprintf (file, "#)\n");
1192 }
1193
1194 /* Print to STDERR the domain of PBB, at some VERBOSITY level.  */
1195
1196 DEBUG_FUNCTION void
1197 debug_pbb_domain (poly_bb_p pbb, int verbosity)
1198 {
1199   print_pbb_domain (stderr, pbb, verbosity);
1200 }
1201
1202 /* Print to FILE the domain and scattering function of PBB, at some
1203    VERBOSITY level.  */
1204
1205 DEBUG_FUNCTION void
1206 debug_pbb (poly_bb_p pbb, int verbosity)
1207 {
1208   print_pbb (stderr, pbb, verbosity);
1209 }
1210
1211 /* Print to STDERR the context of SCOP, at some VERBOSITY level.  */
1212
1213 DEBUG_FUNCTION void
1214 debug_scop_context (scop_p scop, int verbosity)
1215 {
1216   print_scop_context (stderr, scop, verbosity);
1217 }
1218
1219 /* Print to STDERR the SCOP, at some VERBOSITY level.  */
1220
1221 DEBUG_FUNCTION void
1222 debug_scop (scop_p scop, int verbosity)
1223 {
1224   print_scop (stderr, scop, verbosity);
1225 }
1226
1227 /* Print to STDERR the SCOP under CLooG format, at some VERBOSITY
1228    level.  */
1229
1230 DEBUG_FUNCTION void
1231 debug_cloog (scop_p scop, int verbosity)
1232 {
1233   print_cloog (stderr, scop, verbosity);
1234 }
1235
1236 /* Print to STDERR the parameters of SCOP, at some VERBOSITY
1237    level.  */
1238
1239 DEBUG_FUNCTION void
1240 debug_scop_params (scop_p scop, int verbosity)
1241 {
1242   print_scop_params (stderr, scop, verbosity);
1243 }
1244
1245
1246 /* The dimension in the transformed scattering polyhedron of PBB
1247    containing the scattering iterator for the loop at depth LOOP_DEPTH.  */
1248
1249 ppl_dimension_type
1250 psct_scattering_dim_for_loop_depth (poly_bb_p pbb, graphite_dim_t loop_depth)
1251 {
1252   ppl_const_Constraint_System_t pcs;
1253   ppl_Constraint_System_const_iterator_t cit, cend;
1254   ppl_const_Constraint_t cstr;
1255   ppl_Polyhedron_t ph = PBB_TRANSFORMED_SCATTERING (pbb);
1256   ppl_dimension_type iter = psct_iterator_dim (pbb, loop_depth);
1257   ppl_Linear_Expression_t expr;
1258   ppl_Coefficient_t coef;
1259   mpz_t val;
1260   graphite_dim_t i;
1261
1262   mpz_init (val);
1263   ppl_new_Coefficient (&coef);
1264   ppl_Polyhedron_get_constraints (ph, &pcs);
1265   ppl_new_Constraint_System_const_iterator (&cit);
1266   ppl_new_Constraint_System_const_iterator (&cend);
1267
1268   for (ppl_Constraint_System_begin (pcs, cit),
1269          ppl_Constraint_System_end (pcs, cend);
1270        !ppl_Constraint_System_const_iterator_equal_test (cit, cend);
1271        ppl_Constraint_System_const_iterator_increment (cit))
1272     {
1273       ppl_Constraint_System_const_iterator_dereference (cit, &cstr);
1274       ppl_new_Linear_Expression_from_Constraint (&expr, cstr);
1275       ppl_Linear_Expression_coefficient (expr, iter, coef);
1276       ppl_Coefficient_to_mpz_t (coef, val);
1277
1278       if (mpz_sgn (val) == 0)
1279         {
1280           ppl_delete_Linear_Expression (expr);
1281           continue;
1282         }
1283
1284       for (i = 0; i < pbb_nb_scattering_transform (pbb); i++)
1285         {
1286           ppl_dimension_type scatter = psct_scattering_dim (pbb, i);
1287
1288           ppl_Linear_Expression_coefficient (expr, scatter, coef);
1289           ppl_Coefficient_to_mpz_t (coef, val);
1290
1291           if (mpz_sgn (val) != 0)
1292             {
1293               mpz_clear (val);
1294               ppl_delete_Linear_Expression (expr);
1295               ppl_delete_Coefficient (coef);
1296               ppl_delete_Constraint_System_const_iterator (cit);
1297               ppl_delete_Constraint_System_const_iterator (cend);
1298
1299               return scatter;
1300             }
1301         }
1302     }
1303
1304   gcc_unreachable ();
1305 }
1306
1307 /* Returns the number of iterations NITER of the loop around PBB at
1308    depth LOOP_DEPTH.  */
1309
1310 void
1311 pbb_number_of_iterations (poly_bb_p pbb,
1312                           graphite_dim_t loop_depth,
1313                           mpz_t niter)
1314 {
1315   ppl_Linear_Expression_t le;
1316   ppl_dimension_type dim;
1317
1318   ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PBB_DOMAIN (pbb), &dim);
1319   ppl_new_Linear_Expression_with_dimension (&le, dim);
1320   ppl_set_coef (le, pbb_iterator_dim (pbb, loop_depth), 1);
1321   mpz_set_si (niter, -1);
1322   ppl_max_for_le_pointset (PBB_DOMAIN (pbb), le, niter);
1323   ppl_delete_Linear_Expression (le);
1324 }
1325
1326 /* Returns the number of iterations NITER of the loop around PBB at
1327    time(scattering) dimension TIME_DEPTH.  */
1328
1329 void
1330 pbb_number_of_iterations_at_time (poly_bb_p pbb,
1331                                   graphite_dim_t time_depth,
1332                                   mpz_t niter)
1333 {
1334   ppl_Pointset_Powerset_C_Polyhedron_t ext_domain, sctr;
1335   ppl_Linear_Expression_t le;
1336   ppl_dimension_type dim;
1337
1338   /* Takes together domain and scattering polyhedrons, and composes
1339      them into the bigger polyhedron that has the following format:
1340
1341      t0..t_{n-1} | l0..l_{nlcl-1} | i0..i_{niter-1} | g0..g_{nparm-1}
1342
1343      where
1344      | t0..t_{n-1} are time dimensions (scattering dimensions)
1345      | l0..l_{nclc-1} are local variables in scattering function
1346      | i0..i_{niter-1} are original iteration variables
1347      | g0..g_{nparam-1} are global parameters.  */
1348
1349   ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&sctr,
1350       PBB_TRANSFORMED_SCATTERING (pbb));
1351
1352   /* Extend the iteration domain with the scattering dimensions:
1353      0..0 | 0..0 | i0..i_{niter-1} | g0..g_{nparm-1}.   */
1354   ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1355     (&ext_domain, PBB_DOMAIN (pbb));
1356   ppl_insert_dimensions_pointset (ext_domain, 0,
1357                                   pbb_nb_scattering_transform (pbb)
1358                                   + pbb_nb_local_vars (pbb));
1359
1360   /* Add to sctr the extended domain.  */
1361   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (sctr, ext_domain);
1362
1363   /* Extract the number of iterations.  */
1364   ppl_Pointset_Powerset_C_Polyhedron_space_dimension (sctr, &dim);
1365   ppl_new_Linear_Expression_with_dimension (&le, dim);
1366   ppl_set_coef (le, time_depth, 1);
1367   mpz_set_si (niter, -1);
1368   ppl_max_for_le_pointset (sctr, le, niter);
1369
1370   ppl_delete_Linear_Expression (le);
1371   ppl_delete_Pointset_Powerset_C_Polyhedron (sctr);
1372   ppl_delete_Pointset_Powerset_C_Polyhedron (ext_domain);
1373 }
1374
1375 /* Translates LOOP to LST.  */
1376
1377 static lst_p
1378 loop_to_lst (loop_p loop, VEC (poly_bb_p, heap) *bbs, int *i)
1379 {
1380   poly_bb_p pbb;
1381   VEC (lst_p, heap) *seq = VEC_alloc (lst_p, heap, 5);
1382
1383   for (; VEC_iterate (poly_bb_p, bbs, *i, pbb); (*i)++)
1384     {
1385       lst_p stmt;
1386       basic_block bb = GBB_BB (PBB_BLACK_BOX (pbb));
1387
1388       if (bb->loop_father == loop)
1389         stmt = new_lst_stmt (pbb);
1390       else if (flow_bb_inside_loop_p (loop, bb))
1391         {
1392           loop_p next = loop->inner;
1393
1394           while (next && !flow_bb_inside_loop_p (next, bb))
1395             next = next->next;
1396
1397           stmt = loop_to_lst (next, bbs, i);
1398         }
1399       else
1400         {
1401           (*i)--;
1402           return new_lst_loop (seq);
1403         }
1404
1405       VEC_safe_push (lst_p, heap, seq, stmt);
1406     }
1407
1408   return new_lst_loop (seq);
1409 }
1410
1411 /* Reads the original scattering of the SCOP and returns an LST
1412    representing it.  */
1413
1414 void
1415 scop_to_lst (scop_p scop)
1416 {
1417   lst_p res;
1418   int i, n = VEC_length (poly_bb_p, SCOP_BBS (scop));
1419   VEC (lst_p, heap) *seq = VEC_alloc (lst_p, heap, 5);
1420   sese region = SCOP_REGION (scop);
1421
1422   for (i = 0; i < n; i++)
1423     {
1424       poly_bb_p pbb = VEC_index (poly_bb_p, SCOP_BBS (scop), i);
1425       loop_p loop = outermost_loop_in_sese (region, GBB_BB (PBB_BLACK_BOX (pbb)));
1426
1427       if (loop_in_sese_p (loop, region))
1428         res = loop_to_lst (loop, SCOP_BBS (scop), &i);
1429       else
1430         res = new_lst_stmt (pbb);
1431
1432       VEC_safe_push (lst_p, heap, seq, res);
1433     }
1434
1435   res = new_lst_loop (seq);
1436   SCOP_ORIGINAL_SCHEDULE (scop) = res;
1437   SCOP_TRANSFORMED_SCHEDULE (scop) = copy_lst (res);
1438 }
1439
1440 /* Print to FILE on a new line COLUMN white spaces.  */
1441
1442 static void
1443 lst_indent_to (FILE *file, int column)
1444 {
1445   int i;
1446
1447   if (column > 0)
1448     fprintf (file, "\n#");
1449
1450   for (i = 0; i < column; i++)
1451     fprintf (file, " ");
1452 }
1453
1454 /* Print LST to FILE with INDENT spaces of indentation.  */
1455
1456 void
1457 print_lst (FILE *file, lst_p lst, int indent)
1458 {
1459   if (!lst)
1460     return;
1461
1462   lst_indent_to (file, indent);
1463
1464   if (LST_LOOP_P (lst))
1465     {
1466       int i;
1467       lst_p l;
1468
1469       if (LST_LOOP_FATHER (lst))
1470         fprintf (file, "%d (loop", lst_dewey_number (lst));
1471       else
1472         fprintf (file, "#(root");
1473
1474       FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, l)
1475         print_lst (file, l, indent + 2);
1476
1477       fprintf (file, ")");
1478     }
1479   else
1480     fprintf (file, "%d stmt_%d", lst_dewey_number (lst), pbb_index (LST_PBB (lst)));
1481 }
1482
1483 /* Print LST to STDERR.  */
1484
1485 DEBUG_FUNCTION void
1486 debug_lst (lst_p lst)
1487 {
1488   print_lst (stderr, lst, 0);
1489 }
1490
1491 /* Pretty print to FILE the loop statement tree LST in DOT format.  */
1492
1493 static void
1494 dot_lst_1 (FILE *file, lst_p lst)
1495 {
1496   if (!lst)
1497     return;
1498
1499   if (LST_LOOP_P (lst))
1500     {
1501       int i;
1502       lst_p l;
1503
1504       if (!LST_LOOP_FATHER (lst))
1505         fprintf (file, "L -> L_%d_%d\n",
1506                  lst_depth (lst),
1507                  lst_dewey_number (lst));
1508       else
1509         fprintf (file, "L_%d_%d -> L_%d_%d\n",
1510                  lst_depth (LST_LOOP_FATHER (lst)),
1511                  lst_dewey_number (LST_LOOP_FATHER (lst)),
1512                  lst_depth (lst),
1513                  lst_dewey_number (lst));
1514
1515       FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, l)
1516         dot_lst_1 (file, l);
1517     }
1518
1519   else
1520     fprintf (file, "L_%d_%d -> S_%d\n",
1521              lst_depth (LST_LOOP_FATHER (lst)),
1522              lst_dewey_number (LST_LOOP_FATHER (lst)),
1523              pbb_index (LST_PBB (lst)));
1524
1525 }
1526
1527 /* Display the LST using dotty.  */
1528
1529 DEBUG_FUNCTION void
1530 dot_lst (lst_p lst)
1531 {
1532   /* When debugging, enable the following code.  This cannot be used
1533      in production compilers because it calls "system".  */
1534 #if 0
1535   int x;
1536   FILE *stream = fopen ("/tmp/lst.dot", "w");
1537   gcc_assert (stream);
1538
1539   fputs ("digraph all {\n", stream);
1540   dot_lst_1 (stream, lst);
1541   fputs ("}\n\n", stream);
1542   fclose (stream);
1543
1544   x = system ("dotty /tmp/lst.dot &");
1545 #else
1546   fputs ("digraph all {\n", stderr);
1547   dot_lst_1 (stderr, lst);
1548   fputs ("}\n\n", stderr);
1549
1550 #endif
1551 }
1552
1553 #endif
1554