gcc/graphite-poly.c

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