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