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