gcc/graphite-poly.c

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