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