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