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