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