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