gcc/graphite-poly.c

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