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