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