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 "alias.h"
  47 #include "symtab.h"
  48 #include "options.h"
  49 #include "tree.h"
  50 #include "fold-const.h"
  51 #include "predict.h"
  52 #include "tm.h"
  53 #include "hard-reg-set.h"
  54 #include "function.h"
  55 #include "dominance.h"
  56 #include "cfg.h"
  57 #include "basic-block.h"
  58 #include "tree-ssa-alias.h"
  59 #include "internal-fn.h"
  60 #include "gimple-expr.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 || flag_loop_unroll_jam)
 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->map_sepclass = NULL;
 327   PBB_SCOP (pbb) = scop;
 328   pbb_set_black_box (pbb, black_box);
 329   PBB_TRANSFORMED (pbb) = NULL;
 330   PBB_SAVED (pbb) = NULL;
 331   PBB_ORIGINAL (pbb) = NULL;
 332   PBB_DRS (pbb).create (3);
 333   PBB_IS_REDUCTION (pbb) = false;
 334   GBB_PBB ((gimple_bb_p) black_box) = pbb;
 335
 336   return pbb;
 337 }
 338
 339 /* Free polyhedral black box.  */
 340
 341 void
 342 free_poly_bb (poly_bb_p pbb)
 343 {
 344   int i;
 345   poly_dr_p pdr;
 346
 347   isl_set_free (pbb->domain);
 348   isl_map_free (pbb->schedule);
 349   isl_map_free (pbb->transformed);
 350   isl_map_free (pbb->saved);
 351
 352   if (PBB_DRS (pbb).exists ())
 353     FOR_EACH_VEC_ELT (PBB_DRS (pbb), i, pdr)
 354       free_poly_dr (pdr);
 355
 356   PBB_DRS (pbb).release ();
 357   XDELETE (pbb);
 358 }
 359
 360 static void
 361 print_pdr_access_layout (FILE *file, poly_bb_p pbb, poly_dr_p pdr)
 362 {
 363   graphite_dim_t i;
 364
 365   fprintf (file, "#  eq");
 366
 367   fprintf (file, "   alias");
 368
 369   for (i = 0; i < PDR_NB_SUBSCRIPTS (pdr); i++)
 370     fprintf (file, "   sub%d", (int) i);
 371
 372   for (i = 0; i < pbb_dim_iter_domain (pbb); i++)
 373     fprintf (file, "     i%d", (int) i);
 374
 375   for (i = 0; i < pbb_nb_params (pbb); i++)
 376     fprintf (file, "     p%d", (int) i);
 377
 378   fprintf (file, "    cst\n");
 379 }
 380
 381 /* Prints to FILE the polyhedral data reference PDR, at some VERBOSITY
 382    level.  */
 383
 384 void
 385 print_pdr (FILE *file, poly_dr_p pdr, int verbosity)
 386 {
 387   if (verbosity > 1)
 388     {
 389       fprintf (file, "# pdr_%d (", PDR_ID (pdr));
 390
 391       switch (PDR_TYPE (pdr))
 392         {
 393         case PDR_READ:
 394           fprintf (file, "read \n");
 395           break;
 396
 397         case PDR_WRITE:
 398           fprintf (file, "write \n");
 399           break;
 400
 401         case PDR_MAY_WRITE:
 402           fprintf (file, "may_write \n");
 403           break;
 404
 405         default:
 406           gcc_unreachable ();
 407         }
 408
 409       dump_data_reference (file, (data_reference_p) PDR_CDR (pdr));
 410     }
 411
 412   if (verbosity > 0)
 413     {
 414       fprintf (file, "# data accesses (\n");
 415       print_pdr_access_layout (file, PDR_PBB (pdr), pdr);
 416     }
 417
 418   /* XXX isl dump accesses/subscripts */
 419
 420   if (verbosity > 0)
 421     fprintf (file, "#)\n");
 422
 423   if (verbosity > 1)
 424     fprintf (file, "#)\n");
 425 }
 426
 427 /* Prints to STDERR the polyhedral data reference PDR, at some
 428    VERBOSITY level.  */
 429
 430 DEBUG_FUNCTION void
 431 debug_pdr (poly_dr_p pdr, int verbosity)
 432 {
 433   print_pdr (stderr, pdr, verbosity);
 434 }
 435
 436 /* Creates a new SCOP containing REGION.  */
 437
 438 scop_p
 439 new_scop (void *region)
 440 {
 441   scop_p scop = XNEW (struct scop);
 442
 443   scop->context = NULL;
 444   scop->must_raw = NULL;
 445   scop->may_raw = NULL;
 446   scop->must_raw_no_source = NULL;
 447   scop->may_raw_no_source = NULL;
 448   scop->must_war = NULL;
 449   scop->may_war = NULL;
 450   scop->must_war_no_source = NULL;
 451   scop->may_war_no_source = NULL;
 452   scop->must_waw = NULL;
 453   scop->may_waw = NULL;
 454   scop->must_waw_no_source = NULL;
 455   scop->may_waw_no_source = NULL;
 456   scop_set_region (scop, region);
 457   SCOP_BBS (scop).create (3);
 458   SCOP_ORIGINAL_SCHEDULE (scop) = NULL;
 459   SCOP_TRANSFORMED_SCHEDULE (scop) = NULL;
 460   SCOP_SAVED_SCHEDULE (scop) = NULL;
 461   POLY_SCOP_P (scop) = false;
 462
 463   return scop;
 464 }
 465
 466 /* Deletes SCOP.  */
 467
 468 void
 469 free_scop (scop_p scop)
 470 {
 471   int i;
 472   poly_bb_p pbb;
 473
 474   FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb)
 475     free_poly_bb (pbb);
 476
 477   SCOP_BBS (scop).release ();
 478
 479   isl_set_free (scop->context);
 480   isl_union_map_free (scop->must_raw);
 481   isl_union_map_free (scop->may_raw);
 482   isl_union_map_free (scop->must_raw_no_source);
 483   isl_union_map_free (scop->may_raw_no_source);
 484   isl_union_map_free (scop->must_war);
 485   isl_union_map_free (scop->may_war);
 486   isl_union_map_free (scop->must_war_no_source);
 487   isl_union_map_free (scop->may_war_no_source);
 488   isl_union_map_free (scop->must_waw);
 489   isl_union_map_free (scop->may_waw);
 490   isl_union_map_free (scop->must_waw_no_source);
 491   isl_union_map_free (scop->may_waw_no_source);
 492   free_lst (SCOP_ORIGINAL_SCHEDULE (scop));
 493   free_lst (SCOP_TRANSFORMED_SCHEDULE (scop));
 494   free_lst (SCOP_SAVED_SCHEDULE (scop));
 495   XDELETE (scop);
 496 }
 497
 498 /* Print to FILE the domain of PBB in OpenScop format, at some VERBOSITY
 499    level.  */
 500
 501 static void
 502 openscop_print_pbb_domain (FILE *file, poly_bb_p pbb, int verbosity)
 503 {
 504   graphite_dim_t i;
 505   gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
 506
 507   if (!pbb->domain)
 508     return;
 509
 510   if (verbosity > 0)
 511     {
 512       fprintf (file, "\n# Iteration domain of bb_%d (\n", GBB_BB (gbb)->index);
 513       fprintf (file, "#eq");
 514
 515       for (i = 0; i < pbb_dim_iter_domain (pbb); i++)
 516         fprintf (file, "     i%d", (int) i);
 517
 518       for (i = 0; i < pbb_nb_params (pbb); i++)
 519         fprintf (file, "     p%d", (int) i);
 520
 521       fprintf (file, "    cst\n");
 522     }
 523
 524   fprintf (file, "XXX isl\n");
 525
 526   if (verbosity > 0)
 527     fprintf (file, "#)\n");
 528 }
 529
 530 /* Print to FILE the domain of PBB, at some VERBOSITY level.  */
 531
 532 void
 533 print_pbb_domain (FILE *file, poly_bb_p pbb, int verbosity ATTRIBUTE_UNUSED)
 534 {
 535   print_isl_set (file, pbb->domain);
 536 }
 537
 538 /* Dump the cases of a graphite basic block GBB on FILE.  */
 539
 540 static void
 541 dump_gbb_cases (FILE *file, gimple_bb_p gbb)
 542 {
 543   int i;
 544   gimple stmt;
 545   vec<gimple> cases;
 546
 547   if (!gbb)
 548     return;
 549
 550   cases = GBB_CONDITION_CASES (gbb);
 551   if (cases.is_empty ())
 552     return;
 553
 554   fprintf (file, "# cases bb_%d (\n", GBB_BB (gbb)->index);
 555
 556   FOR_EACH_VEC_ELT (cases, i, stmt)
 557     {
 558       fprintf (file, "# ");
 559       print_gimple_stmt (file, stmt, 0, 0);
 560     }
 561
 562   fprintf (file, "#)\n");
 563 }
 564
 565 /* Dump conditions of a graphite basic block GBB on FILE.  */
 566
 567 static void
 568 dump_gbb_conditions (FILE *file, gimple_bb_p gbb)
 569 {
 570   int i;
 571   gimple stmt;
 572   vec<gimple> conditions;
 573
 574   if (!gbb)
 575     return;
 576
 577   conditions = GBB_CONDITIONS (gbb);
 578   if (conditions.is_empty ())
 579     return;
 580
 581   fprintf (file, "# conditions bb_%d (\n", GBB_BB (gbb)->index);
 582
 583   FOR_EACH_VEC_ELT (conditions, i, stmt)
 584     {
 585       fprintf (file, "# ");
 586       print_gimple_stmt (file, stmt, 0, 0);
 587     }
 588
 589   fprintf (file, "#)\n");
 590 }
 591
 592 /* Print to FILE all the data references of PBB, at some VERBOSITY
 593    level.  */
 594
 595 void
 596 print_pdrs (FILE *file, poly_bb_p pbb, int verbosity)
 597 {
 598   int i;
 599   poly_dr_p pdr;
 600   int nb_reads = 0;
 601   int nb_writes = 0;
 602
 603   if (PBB_DRS (pbb).length () == 0)
 604     {
 605       if (verbosity > 0)
 606         fprintf (file, "# Access informations are not provided\n");\
 607       fprintf (file, "0\n");
 608       return;
 609     }
 610
 611   if (verbosity > 1)
 612     fprintf (file, "# Data references (\n");
 613
 614   if (verbosity > 0)
 615     fprintf (file, "# Access informations are provided\n");
 616   fprintf (file, "1\n");
 617
 618   FOR_EACH_VEC_ELT (PBB_DRS (pbb), i, pdr)
 619     if (PDR_TYPE (pdr) == PDR_READ)
 620       nb_reads++;
 621     else
 622       nb_writes++;
 623
 624   if (verbosity > 1)
 625     fprintf (file, "# Read data references (\n");
 626
 627   if (verbosity > 0)
 628     fprintf (file, "# Read access informations\n");
 629   fprintf (file, "%d\n", nb_reads);
 630
 631   FOR_EACH_VEC_ELT (PBB_DRS (pbb), i, pdr)
 632     if (PDR_TYPE (pdr) == PDR_READ)
 633       print_pdr (file, pdr, verbosity);
 634
 635   if (verbosity > 1)
 636     fprintf (file, "#)\n");
 637
 638   if (verbosity > 1)
 639     fprintf (file, "# Write data references (\n");
 640
 641   if (verbosity > 0)
 642     fprintf (file, "# Write access informations\n");
 643   fprintf (file, "%d\n", nb_writes);
 644
 645   FOR_EACH_VEC_ELT (PBB_DRS (pbb), i, pdr)
 646     if (PDR_TYPE (pdr) != PDR_READ)
 647       print_pdr (file, pdr, verbosity);
 648
 649   if (verbosity > 1)
 650     fprintf (file, "#)\n");
 651
 652   if (verbosity > 1)
 653     fprintf (file, "#)\n");
 654 }
 655
 656 /* Print to STDERR all the data references of PBB.  */
 657
 658 DEBUG_FUNCTION void
 659 debug_pdrs (poly_bb_p pbb, int verbosity)
 660 {
 661   print_pdrs (stderr, pbb, verbosity);
 662 }
 663
 664 /* Print to FILE the body of PBB, at some VERBOSITY level.
 665    If statement_body_provided is false statement body is not printed.  */
 666
 667 static void
 668 print_pbb_body (FILE *file, poly_bb_p pbb, int verbosity,
 669                 bool statement_body_provided)
 670 {
 671   if (verbosity > 1)
 672     fprintf (file, "# Body (\n");
 673
 674   if (!statement_body_provided)
 675     {
 676       if (verbosity > 0)
 677         fprintf (file, "# Statement body is not provided\n");
 678
 679       fprintf (file, "0\n");
 680
 681       if (verbosity > 1)
 682         fprintf (file, "#)\n");
 683       return;
 684     }
 685
 686   if (verbosity > 0)
 687     fprintf (file, "# Statement body is provided\n");
 688   fprintf (file, "1\n");
 689
 690   if (verbosity > 0)
 691     fprintf (file, "# Original iterator names\n# Iterator names are not provided yet.\n");
 692
 693   if (verbosity > 0)
 694     fprintf (file, "# Statement body\n");
 695
 696   fprintf (file, "{\n");
 697   dump_bb (file, pbb_bb (pbb), 0, 0);
 698   fprintf (file, "}\n");
 699
 700   if (verbosity > 1)
 701     fprintf (file, "#)\n");
 702 }
 703
 704 /* Print to FILE the domain and scattering function of PBB, at some
 705    VERBOSITY level.  */
 706
 707 void
 708 print_pbb (FILE *file, poly_bb_p pbb, int verbosity)
 709 {
 710   if (verbosity > 1)
 711     {
 712       fprintf (file, "# pbb_%d (\n", pbb_index (pbb));
 713       dump_gbb_conditions (file, PBB_BLACK_BOX (pbb));
 714       dump_gbb_cases (file, PBB_BLACK_BOX (pbb));
 715     }
 716
 717   openscop_print_pbb_domain (file, pbb, verbosity);
 718   print_scattering_function (file, pbb, verbosity);
 719   print_pdrs (file, pbb, verbosity);
 720   print_pbb_body (file, pbb, verbosity, false);
 721
 722   if (verbosity > 1)
 723     fprintf (file, "#)\n");
 724 }
 725
 726 /* Print to FILE the parameters of SCOP, at some VERBOSITY level.  */
 727
 728 void
 729 print_scop_params (FILE *file, scop_p scop, int verbosity)
 730 {
 731   int i;
 732   tree t;
 733
 734   if (verbosity > 1)
 735     fprintf (file, "# parameters (\n");
 736
 737   if (SESE_PARAMS (SCOP_REGION (scop)).length ())
 738     {
 739       if (verbosity > 0)
 740         fprintf (file, "# Parameter names are provided\n");
 741
 742       fprintf (file, "1\n");
 743
 744       if (verbosity > 0)
 745         fprintf (file, "# Parameter names\n");
 746     }
 747   else
 748     {
 749       if (verbosity > 0)
 750         fprintf (file, "# Parameter names are not provided\n");
 751       fprintf (file, "0\n");
 752     }
 753
 754   FOR_EACH_VEC_ELT (SESE_PARAMS (SCOP_REGION (scop)), i, t)
 755     {
 756       print_generic_expr (file, t, 0);
 757       fprintf (file, " ");
 758     }
 759
 760   fprintf (file, "\n");
 761
 762   if (verbosity > 1)
 763     fprintf (file, "#)\n");
 764 }
 765
 766 /* Print to FILE the context of SCoP in OpenScop format, at some VERBOSITY
 767    level.  */
 768
 769 static void
 770 openscop_print_scop_context (FILE *file, scop_p scop, int verbosity)
 771 {
 772   graphite_dim_t i;
 773
 774   if (verbosity > 0)
 775     {
 776       fprintf (file, "# Context (\n");
 777       fprintf (file, "#eq");
 778
 779       for (i = 0; i < scop_nb_params (scop); i++)
 780         fprintf (file, "     p%d", (int) i);
 781
 782       fprintf (file, "    cst\n");
 783     }
 784
 785   if (scop->context)
 786     /* XXX isl print context */
 787     fprintf (file, "XXX isl\n");
 788   else
 789     fprintf (file, "0 %d 0 0 0 %d\n", (int) scop_nb_params (scop) + 2,
 790              (int) scop_nb_params (scop));
 791
 792   if (verbosity > 0)
 793     fprintf (file, "# )\n");
 794 }
 795
 796 /* Print to FILE the context of SCoP, at some VERBOSITY level.  */
 797
 798 void
 799 print_scop_context (FILE *file, scop_p scop, int verbosity)
 800 {
 801   graphite_dim_t i;
 802
 803   if (verbosity > 0)
 804     {
 805       fprintf (file, "# Context (\n");
 806       fprintf (file, "#eq");
 807
 808       for (i = 0; i < scop_nb_params (scop); i++)
 809         fprintf (file, "     p%d", (int) i);
 810
 811       fprintf (file, "    cst\n");
 812     }
 813
 814   if (scop->context)
 815     print_isl_set (file, scop->context);
 816   else
 817     fprintf (file, "no isl context %d\n", (int) scop_nb_params (scop) + 2);
 818
 819   if (verbosity > 0)
 820     fprintf (file, "# )\n");
 821 }
 822
 823 /* Print to FILE the SCOP, at some VERBOSITY level.  */
 824
 825 void
 826 print_scop (FILE *file, scop_p scop, int verbosity)
 827 {
 828   int i;
 829   poly_bb_p pbb;
 830
 831   fprintf (file, "SCoP 1\n#(\n");
 832   fprintf (file, "# Language\nGimple\n");
 833   openscop_print_scop_context (file, scop, verbosity);
 834   print_scop_params (file, scop, verbosity);
 835
 836   if (verbosity > 0)
 837     fprintf (file, "# Number of statements\n");
 838
 839   fprintf (file, "%d\n", SCOP_BBS (scop).length ());
 840
 841   FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb)
 842     print_pbb (file, pbb, verbosity);
 843
 844   if (verbosity > 1)
 845     {
 846       fprintf (file, "# original_lst (\n");
 847       print_lst (file, SCOP_ORIGINAL_SCHEDULE (scop), 0);
 848       fprintf (file, "\n#)\n");
 849
 850       fprintf (file, "# transformed_lst (\n");
 851       print_lst (file, SCOP_TRANSFORMED_SCHEDULE (scop), 0);
 852       fprintf (file, "\n#)\n");
 853     }
 854
 855   fprintf (file, "#)\n");
 856 }
 857
 858 /* Print to STDERR the domain of PBB, at some VERBOSITY level.  */
 859
 860 DEBUG_FUNCTION void
 861 debug_pbb_domain (poly_bb_p pbb, int verbosity)
 862 {
 863   print_pbb_domain (stderr, pbb, verbosity);
 864 }
 865
 866 /* Print to FILE the domain and scattering function of PBB, at some
 867    VERBOSITY level.  */
 868
 869 DEBUG_FUNCTION void
 870 debug_pbb (poly_bb_p pbb, int verbosity)
 871 {
 872   print_pbb (stderr, pbb, verbosity);
 873 }
 874
 875 /* Print to STDERR the context of SCOP, at some VERBOSITY level.  */
 876
 877 DEBUG_FUNCTION void
 878 debug_scop_context (scop_p scop, int verbosity)
 879 {
 880   print_scop_context (stderr, scop, verbosity);
 881 }
 882
 883 /* Print to STDERR the SCOP, at some VERBOSITY level.  */
 884
 885 DEBUG_FUNCTION void
 886 debug_scop (scop_p scop, int verbosity)
 887 {
 888   print_scop (stderr, scop, verbosity);
 889 }
 890
 891 /* Print to STDERR the parameters of SCOP, at some VERBOSITY
 892    level.  */
 893
 894 DEBUG_FUNCTION void
 895 debug_scop_params (scop_p scop, int verbosity)
 896 {
 897   print_scop_params (stderr, scop, verbosity);
 898 }
 899
 900 extern isl_ctx *the_isl_ctx;
 901 void
 902 print_isl_set (FILE *f, isl_set *set)
 903 {
 904   isl_printer *p = isl_printer_to_file (the_isl_ctx, f);
 905   p = isl_printer_print_set (p, set);
 906   isl_printer_free (p);
 907 }
 908
 909 DEBUG_FUNCTION void
 910 debug_isl_set (isl_set *set)
 911 {
 912   print_isl_set (stderr, set);
 913 }
 914
 915 void
 916 print_isl_map (FILE *f, isl_map *map)
 917 {
 918   isl_printer *p = isl_printer_to_file (the_isl_ctx, f);
 919   p = isl_printer_print_map (p, map);
 920   isl_printer_free (p);
 921 }
 922
 923 DEBUG_FUNCTION void
 924 debug_isl_map (isl_map *map)
 925 {
 926   print_isl_map (stderr, map);
 927 }
 928
 929 void
 930 print_isl_aff (FILE *f, isl_aff *aff)
 931 {
 932   isl_printer *p = isl_printer_to_file (the_isl_ctx, f);
 933   p = isl_printer_print_aff (p, aff);
 934   isl_printer_free (p);
 935 }
 936
 937 DEBUG_FUNCTION void
 938 debug_isl_aff (isl_aff *aff)
 939 {
 940   print_isl_aff (stderr, aff);
 941 }
 942
 943 void
 944 print_isl_constraint (FILE *f, isl_constraint *c)
 945 {
 946   isl_printer *p = isl_printer_to_file (the_isl_ctx, f);
 947   p = isl_printer_print_constraint (p, c);
 948   isl_printer_free (p);
 949 }
 950
 951 DEBUG_FUNCTION void
 952 debug_isl_constraint (isl_constraint *c)
 953 {
 954   print_isl_constraint (stderr, c);
 955 }
 956
 957 /* Returns the number of iterations RES of the loop around PBB at
 958    time(scattering) dimension TIME_DEPTH.  */
 959
 960 void
 961 pbb_number_of_iterations_at_time (poly_bb_p pbb,
 962                                   graphite_dim_t time_depth,
 963                                   mpz_t res)
 964 {
 965   isl_set *transdomain;
 966   isl_space *dc;
 967   isl_aff *aff;
 968   isl_val *isllb, *islub;
 969
 970   /* Map the iteration domain through the current scatter, and work
 971      on the resulting set.  */
 972   transdomain = isl_set_apply (isl_set_copy (pbb->domain),
 973                                isl_map_copy (pbb->transformed));
 974
 975   /* Select the time_depth' dimension via an affine expression.  */
 976   dc = isl_set_get_space (transdomain);
 977   aff = isl_aff_zero_on_domain (isl_local_space_from_space (dc));
 978   aff = isl_aff_set_coefficient_si (aff, isl_dim_in, time_depth, 1);
 979
 980   /* And find the min/max for that function.  */
 981   /* XXX isl check results?  */
 982   isllb = isl_set_min_val (transdomain, aff);
 983   islub = isl_set_max_val (transdomain, aff);
 984
 985   islub = isl_val_sub (islub, isllb);
 986   islub = isl_val_add_ui (islub, 1);
 987   isl_val_get_num_gmp (islub, res);
 988
 989   isl_val_free (islub);
 990   isl_aff_free (aff);
 991   isl_set_free (transdomain);
 992 }
 993
 994 /* Translates LOOP to LST.  */
 995
 996 static lst_p
 997 loop_to_lst (loop_p loop, vec<poly_bb_p> bbs, int *i)
 998 {
 999   poly_bb_p pbb;
1000   vec<lst_p> seq;
1001   seq.create (5);
1002
1003   for (; bbs.iterate (*i, &pbb); (*i)++)
1004     {
1005       lst_p stmt;
1006       basic_block bb = GBB_BB (PBB_BLACK_BOX (pbb));
1007
1008       if (bb->loop_father == loop)
1009         stmt = new_lst_stmt (pbb);
1010       else if (flow_bb_inside_loop_p (loop, bb))
1011         {
1012           loop_p next = loop->inner;
1013
1014           while (next && !flow_bb_inside_loop_p (next, bb))
1015             next = next->next;
1016
1017           stmt = loop_to_lst (next, bbs, i);
1018         }
1019       else
1020         {
1021           (*i)--;
1022           return new_lst_loop (seq);
1023         }
1024
1025       seq.safe_push (stmt);
1026     }
1027
1028   return new_lst_loop (seq);
1029 }
1030
1031 /* Reads the original scattering of the SCOP and returns an LST
1032    representing it.  */
1033
1034 void
1035 scop_to_lst (scop_p scop)
1036 {
1037   lst_p res;
1038   int i, n = SCOP_BBS (scop).length ();
1039   vec<lst_p> seq;
1040   seq.create (5);
1041   sese region = SCOP_REGION (scop);
1042
1043   for (i = 0; i < n; i++)
1044     {
1045       poly_bb_p pbb = SCOP_BBS (scop)[i];
1046       loop_p loop = outermost_loop_in_sese (region, GBB_BB (PBB_BLACK_BOX (pbb)));
1047
1048       if (loop_in_sese_p (loop, region))
1049         res = loop_to_lst (loop, SCOP_BBS (scop), &i);
1050       else
1051         res = new_lst_stmt (pbb);
1052
1053       seq.safe_push (res);
1054     }
1055
1056   res = new_lst_loop (seq);
1057   SCOP_ORIGINAL_SCHEDULE (scop) = res;
1058   SCOP_TRANSFORMED_SCHEDULE (scop) = copy_lst (res);
1059 }
1060
1061 /* Print to FILE on a new line COLUMN white spaces.  */
1062
1063 static void
1064 lst_indent_to (FILE *file, int column)
1065 {
1066   int i;
1067
1068   if (column > 0)
1069     fprintf (file, "\n#");
1070
1071   for (i = 0; i < column; i++)
1072     fprintf (file, " ");
1073 }
1074
1075 /* Print LST to FILE with INDENT spaces of indentation.  */
1076
1077 void
1078 print_lst (FILE *file, lst_p lst, int indent)
1079 {
1080   if (!lst)
1081     return;
1082
1083   lst_indent_to (file, indent);
1084
1085   if (LST_LOOP_P (lst))
1086     {
1087       int i;
1088       lst_p l;
1089
1090       if (LST_LOOP_FATHER (lst))
1091         fprintf (file, "%d (loop", lst_dewey_number (lst));
1092       else
1093         fprintf (file, "#(root");
1094
1095       FOR_EACH_VEC_ELT (LST_SEQ (lst), i, l)
1096         print_lst (file, l, indent + 2);
1097
1098       fprintf (file, ")");
1099     }
1100   else
1101     fprintf (file, "%d stmt_%d", lst_dewey_number (lst), pbb_index (LST_PBB (lst)));
1102 }
1103
1104 /* Print LST to STDERR.  */
1105
1106 DEBUG_FUNCTION void
1107 debug_lst (lst_p lst)
1108 {
1109   print_lst (stderr, lst, 0);
1110 }
1111
1112 /* Pretty print to FILE the loop statement tree LST in DOT format.  */
1113
1114 static void
1115 dot_lst_1 (FILE *file, lst_p lst)
1116 {
1117   if (!lst)
1118     return;
1119
1120   if (LST_LOOP_P (lst))
1121     {
1122       int i;
1123       lst_p l;
1124
1125       if (!LST_LOOP_FATHER (lst))
1126         fprintf (file, "L -> L_%d_%d\n",
1127                  lst_depth (lst),
1128                  lst_dewey_number (lst));
1129       else
1130         fprintf (file, "L_%d_%d -> L_%d_%d\n",
1131                  lst_depth (LST_LOOP_FATHER (lst)),
1132                  lst_dewey_number (LST_LOOP_FATHER (lst)),
1133                  lst_depth (lst),
1134                  lst_dewey_number (lst));
1135
1136       FOR_EACH_VEC_ELT (LST_SEQ (lst), i, l)
1137         dot_lst_1 (file, l);
1138     }
1139
1140   else
1141     fprintf (file, "L_%d_%d -> S_%d\n",
1142              lst_depth (LST_LOOP_FATHER (lst)),
1143              lst_dewey_number (LST_LOOP_FATHER (lst)),
1144              pbb_index (LST_PBB (lst)));
1145
1146 }
1147
1148 /* Display the LST using dotty.  */
1149
1150 DEBUG_FUNCTION void
1151 dot_lst (lst_p lst)
1152 {
1153   /* When debugging, enable the following code.  This cannot be used
1154      in production compilers because it calls "system".  */
1155 #if 0
1156   FILE *stream = fopen ("/tmp/lst.dot", "w");
1157   gcc_assert (stream);
1158
1159   fputs ("digraph all {\n", stream);
1160   dot_lst_1 (stream, lst);
1161   fputs ("}\n\n", stream);
1162   fclose (stream);
1163
1164   system ("dotty /tmp/lst.dot &");
1165 #else
1166   fputs ("digraph all {\n", stderr);
1167   dot_lst_1 (stderr, lst);
1168   fputs ("}\n\n", stderr);
1169
1170 #endif
1171 }
1172
1173 /* Reverse the loop around PBB at level DEPTH.  */
1174
1175 isl_map *
1176 reverse_loop_at_level (poly_bb_p pbb, int depth)
1177 {
1178   unsigned i, depth_dim = psct_dynamic_dim (pbb, depth);
1179   isl_space *d = isl_map_get_space (pbb->transformed);
1180   isl_space *d1 = isl_space_range (d);
1181   unsigned n = isl_space_dim (d1, isl_dim_out);
1182   isl_space *d2 = isl_space_add_dims (d1, isl_dim_in, n);
1183   isl_map *x = isl_map_universe (isl_space_copy (d2));
1184   isl_constraint *c = isl_equality_alloc (isl_local_space_from_space (d2));
1185
1186   for (i = 0; i < n; i++)
1187     if (i != depth_dim)
1188       x = isl_map_equate (x, isl_dim_in, i, isl_dim_out, i);
1189
1190   c = isl_constraint_set_coefficient_si (c, isl_dim_in, depth_dim, 1);
1191   c = isl_constraint_set_coefficient_si (c, isl_dim_out, depth_dim, 1);
1192   x = isl_map_add_constraint (x, c);
1193   return x;
1194 }
1195
1196 /* Reverse the loop at level DEPTH for all the PBBS.  */
1197
1198 isl_union_map *
1199 reverse_loop_for_pbbs (scop_p scop, vec<poly_bb_p> pbbs, int depth)
1200 {
1201   poly_bb_p pbb;
1202   int i;
1203   isl_space *space = isl_space_from_domain (isl_set_get_space (scop->context));
1204   isl_union_map *res = isl_union_map_empty (space);
1205
1206   for (i = 0; pbbs.iterate (i, &pbb); i++)
1207     res = isl_union_map_add_map (res, reverse_loop_at_level (pbb, depth));
1208
1209   return res;
1210 }
1211
1212
1213 #endif
1214