gcc/graphite-poly.c

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