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