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