gcc/graphite-poly.c

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