gcc/graphite-poly.c

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