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