gcc/graphite-poly.c

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