gcc/graphite-poly.c

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