gcc/graphite-poly.c

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