gcc/graphite-poly.c

   1 /* Graphite polyhedral representation.
   2    Copyright (C) 2009-2016 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 #define USES_ISL
  23
  24 #include "config.h"
  25
  26 #ifdef HAVE_isl
  27
  28 #include "system.h"
  29 #include "coretypes.h"
  30 #include "backend.h"
  31 #include "tree.h"
  32 #include "gimple.h"
  33 #include "cfghooks.h"
  34 #include "diagnostic-core.h"
  35 #include "fold-const.h"
  36 #include "gimple-iterator.h"
  37 #include "tree-ssa-loop.h"
  38 #include "cfgloop.h"
  39 #include "tree-data-ref.h"
  40 #include "pretty-print.h"
  41 #include "gimple-pretty-print.h"
  42 #include "tree-dump.h"
  43 #include "graphite.h"
  44
  45 /* Print to STDERR the GMP value VAL.  */
  46
  47 DEBUG_FUNCTION void
  48 debug_gmp_value (mpz_t val)
  49 {
  50   gmp_fprintf (stderr, "%Zd", val);
  51 }
  52
  53 /* Prints to FILE the iteration domain of PBB.  */
  54
  55 void
  56 print_iteration_domain (FILE *file, poly_bb_p pbb)
  57 {
  58   print_pbb_domain (file, pbb);
  59 }
  60
  61 /* Prints to FILE the iteration domains of every PBB of SCOP.  */
  62
  63 void
  64 print_iteration_domains (FILE *file, scop_p scop)
  65 {
  66   int i;
  67   poly_bb_p pbb;
  68
  69   FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
  70     print_iteration_domain (file, pbb);
  71 }
  72
  73 /* Prints to STDERR the iteration domain of PBB.  */
  74
  75 DEBUG_FUNCTION void
  76 debug_iteration_domain (poly_bb_p pbb)
  77 {
  78   print_iteration_domain (stderr, pbb);
  79 }
  80
  81 /* Prints to STDERR the iteration domains of every PBB of SCOP.  */
  82
  83 DEBUG_FUNCTION void
  84 debug_iteration_domains (scop_p scop)
  85 {
  86   print_iteration_domains (stderr, scop);
  87 }
  88
  89 /* Create a new polyhedral data reference and add it to PBB.  It is
  90    defined by its ACCESSES, its TYPE, and the number of subscripts
  91    NB_SUBSCRIPTS.  */
  92
  93 void
  94 new_poly_dr (poly_bb_p pbb, gimple *stmt, enum poly_dr_type type,
  95              isl_map *acc, isl_set *subscript_sizes)
  96 {
  97   static int id = 0;
  98   poly_dr_p pdr = XNEW (struct poly_dr);
  99
 100   pdr->stmt = stmt;
 101   PDR_ID (pdr) = id++;
 102   PDR_NB_REFS (pdr) = 1;
 103   PDR_PBB (pdr) = pbb;
 104   pdr->accesses = acc;
 105   pdr->subscript_sizes = subscript_sizes;
 106   PDR_TYPE (pdr) = type;
 107   PBB_DRS (pbb).safe_push (pdr);
 108
 109   if (dump_file)
 110     {
 111       fprintf (dump_file, "Converting dr: ");
 112       print_pdr (dump_file, pdr);
 113       fprintf (dump_file, "To polyhedral representation:\n");
 114       fprintf (dump_file, "  - access functions: ");
 115       print_isl_map (dump_file, acc);
 116       fprintf (dump_file, "  - subscripts: ");
 117       print_isl_set (dump_file, subscript_sizes);
 118     }
 119 }
 120
 121 /* Free polyhedral data reference PDR.  */
 122
 123 static void
 124 free_poly_dr (poly_dr_p pdr)
 125 {
 126   isl_map_free (pdr->accesses);
 127   isl_set_free (pdr->subscript_sizes);
 128   XDELETE (pdr);
 129 }
 130
 131 /* Create a new polyhedral black box.  */
 132
 133 poly_bb_p
 134 new_poly_bb (scop_p scop, gimple_poly_bb_p black_box)
 135 {
 136   poly_bb_p pbb = XNEW (struct poly_bb);
 137
 138   pbb->domain = NULL;
 139 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
 140   pbb->iterators = NULL;
 141 #else
 142   pbb->schedule = NULL;
 143   pbb->transformed = NULL;
 144   pbb->saved = NULL;
 145 #endif
 146   PBB_SCOP (pbb) = scop;
 147   pbb_set_black_box (pbb, black_box);
 148   PBB_DRS (pbb).create (3);
 149   GBB_PBB ((gimple_poly_bb_p) black_box) = pbb;
 150
 151   return pbb;
 152 }
 153
 154 /* Free polyhedral black box.  */
 155
 156 static void
 157 free_poly_bb (poly_bb_p pbb)
 158 {
 159   int i;
 160   poly_dr_p pdr;
 161
 162   isl_set_free (pbb->domain);
 163   pbb->domain = NULL;
 164 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
 165   isl_set_free (pbb->iterators);
 166   pbb->iterators = NULL;
 167 #else
 168   isl_map_free (pbb->schedule);
 169   pbb->schedule = NULL;
 170   isl_map_free (pbb->transformed);
 171   pbb->transformed = NULL;
 172   isl_map_free (pbb->saved);
 173   pbb->saved = NULL;
 174 #endif
 175
 176   if (PBB_DRS (pbb).exists ())
 177     FOR_EACH_VEC_ELT (PBB_DRS (pbb), i, pdr)
 178       free_poly_dr (pdr);
 179
 180   PBB_DRS (pbb).release ();
 181   XDELETE (pbb);
 182 }
 183
 184 /* Prints to FILE the polyhedral data reference PDR.  */
 185
 186 void
 187 print_pdr (FILE *file, poly_dr_p pdr)
 188 {
 189   fprintf (file, "pdr_%d (", PDR_ID (pdr));
 190
 191   switch (PDR_TYPE (pdr))
 192     {
 193     case PDR_READ:
 194       fprintf (file, "read \n");
 195       break;
 196
 197     case PDR_WRITE:
 198       fprintf (file, "write \n");
 199       break;
 200
 201     case PDR_MAY_WRITE:
 202       fprintf (file, "may_write \n");
 203       break;
 204
 205     default:
 206       gcc_unreachable ();
 207     }
 208
 209   fprintf (file, "in gimple stmt: ");
 210   print_gimple_stmt (file, pdr->stmt, 0, 0);
 211   fprintf (file, "data accesses: ");
 212   print_isl_map (file, pdr->accesses);
 213   fprintf (file, "subscript sizes: ");
 214   print_isl_set (file, pdr->subscript_sizes);
 215   fprintf (file, ")\n");
 216 }
 217
 218 /* Prints to STDERR the polyhedral data reference PDR.  */
 219
 220 DEBUG_FUNCTION void
 221 debug_pdr (poly_dr_p pdr)
 222 {
 223   print_pdr (stderr, pdr);
 224 }
 225
 226 /* Store the GRAPHITE representation of BB.  */
 227
 228 gimple_poly_bb_p
 229 new_gimple_poly_bb (basic_block bb, vec<data_reference_p> drs,
 230                     vec<scalar_use> reads, vec<tree> writes)
 231 {
 232   gimple_poly_bb_p gbb = XNEW (struct gimple_poly_bb);
 233   GBB_BB (gbb) = bb;
 234   GBB_DATA_REFS (gbb) = drs;
 235   gbb->read_scalar_refs = reads;
 236   gbb->write_scalar_refs = writes;
 237   GBB_CONDITIONS (gbb).create (0);
 238   GBB_CONDITION_CASES (gbb).create (0);
 239
 240   return gbb;
 241 }
 242
 243 /* Frees GBB.  */
 244
 245 static void
 246 free_gimple_poly_bb (gimple_poly_bb_p gbb)
 247 {
 248   free_data_refs (GBB_DATA_REFS (gbb));
 249   GBB_CONDITIONS (gbb).release ();
 250   GBB_CONDITION_CASES (gbb).release ();
 251   gbb->read_scalar_refs.release ();
 252   gbb->write_scalar_refs.release ();
 253   XDELETE (gbb);
 254 }
 255
 256 /* Deletes all gimple bbs in SCOP.  */
 257
 258 static void
 259 remove_gbbs_in_scop (scop_p scop)
 260 {
 261   int i;
 262   poly_bb_p pbb;
 263
 264   FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
 265     free_gimple_poly_bb (PBB_BLACK_BOX (pbb));
 266 }
 267
 268 /* Creates a new SCOP containing the region (ENTRY, EXIT).  */
 269
 270 scop_p
 271 new_scop (edge entry, edge exit)
 272 {
 273   sese_info_p region = new_sese_info (entry, exit);
 274   scop_p s = XNEW (struct scop);
 275
 276 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
 277   s->original_schedule = NULL;
 278   s->transformed_schedule = NULL;
 279 #else
 280   s->schedule = NULL;
 281 #endif
 282   s->param_context = NULL;
 283   scop_set_region (s, region);
 284   s->pbbs.create (3);
 285   s->drs.create (3);
 286   s->dependence = NULL;
 287   return s;
 288 }
 289
 290 /* Deletes SCOP.  */
 291
 292 void
 293 free_scop (scop_p scop)
 294 {
 295   int i;
 296   poly_bb_p pbb;
 297
 298   remove_gbbs_in_scop (scop);
 299   free_sese_info (scop->scop_info);
 300
 301   FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
 302     free_poly_bb (pbb);
 303
 304   scop->pbbs.release ();
 305   scop->drs.release ();
 306
 307   isl_set_free (scop->param_context);
 308   scop->param_context = NULL;
 309   isl_union_map_free (scop->dependence);
 310   scop->dependence = NULL;
 311 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
 312   isl_schedule_free (scop->original_schedule);
 313   scop->original_schedule = NULL;
 314   isl_schedule_free (scop->transformed_schedule);
 315   scop->transformed_schedule = NULL;
 316 #else
 317
 318 #endif
 319   XDELETE (scop);
 320 }
 321
 322 /* Print to FILE the domain of PBB.  */
 323
 324 void
 325 print_pbb_domain (FILE *file, poly_bb_p pbb)
 326 {
 327   print_isl_set (file, pbb->domain);
 328 }
 329
 330 /* Dump the cases of a graphite basic block GBB on FILE.  */
 331
 332 static void
 333 dump_gbb_cases (FILE *file, gimple_poly_bb_p gbb)
 334 {
 335   int i;
 336   gimple *stmt;
 337   vec<gimple *> cases;
 338
 339   if (!gbb)
 340     return;
 341
 342   cases = GBB_CONDITION_CASES (gbb);
 343   if (cases.is_empty ())
 344     return;
 345
 346   fprintf (file, "cases bb_%d (\n", GBB_BB (gbb)->index);
 347
 348   FOR_EACH_VEC_ELT (cases, i, stmt)
 349     print_gimple_stmt (file, stmt, 0, 0);
 350
 351   fprintf (file, ")\n");
 352 }
 353
 354 /* Dump conditions of a graphite basic block GBB on FILE.  */
 355
 356 static void
 357 dump_gbb_conditions (FILE *file, gimple_poly_bb_p gbb)
 358 {
 359   int i;
 360   gimple *stmt;
 361   vec<gimple *> conditions;
 362
 363   if (!gbb)
 364     return;
 365
 366   conditions = GBB_CONDITIONS (gbb);
 367   if (conditions.is_empty ())
 368     return;
 369
 370   fprintf (file, "conditions bb_%d (\n", GBB_BB (gbb)->index);
 371
 372   FOR_EACH_VEC_ELT (conditions, i, stmt)
 373     print_gimple_stmt (file, stmt, 0, 0);
 374
 375   fprintf (file, ")\n");
 376 }
 377
 378 /* Print to FILE all the data references of PBB.  */
 379
 380 void
 381 print_pdrs (FILE *file, poly_bb_p pbb)
 382 {
 383   int i;
 384   poly_dr_p pdr;
 385   int nb_reads = 0;
 386   int nb_writes = 0;
 387
 388   if (PBB_DRS (pbb).is_empty ())
 389     return;
 390
 391   fprintf (file, "Data references (\n");
 392
 393   FOR_EACH_VEC_ELT (PBB_DRS (pbb), i, pdr)
 394     if (PDR_TYPE (pdr) == PDR_READ)
 395       nb_reads++;
 396     else
 397       nb_writes++;
 398
 399   fprintf (file, "Read data references (\n");
 400
 401   FOR_EACH_VEC_ELT (PBB_DRS (pbb), i, pdr)
 402     if (PDR_TYPE (pdr) == PDR_READ)
 403       print_pdr (file, pdr);
 404
 405   fprintf (file, ")\n");
 406   fprintf (file, "Write data references (\n");
 407   FOR_EACH_VEC_ELT (PBB_DRS (pbb), i, pdr)
 408     if (PDR_TYPE (pdr) != PDR_READ)
 409       print_pdr (file, pdr);
 410   fprintf (file, ")\n");
 411   fprintf (file, ")\n");
 412 }
 413
 414 /* Print to STDERR all the data references of PBB.  */
 415
 416 DEBUG_FUNCTION void
 417 debug_pdrs (poly_bb_p pbb)
 418 {
 419   print_pdrs (stderr, pbb);
 420 }
 421
 422 /* Print to FILE the body of PBB.  */
 423
 424 static void
 425 print_pbb_body (FILE *file, poly_bb_p pbb)
 426 {
 427   fprintf (file, "Body (\n");
 428   dump_bb (file, pbb_bb (pbb), 0, 0);
 429   fprintf (file, ")\n");
 430 }
 431
 432 /* Print to FILE the domain and scattering function of PBB.  */
 433
 434 void
 435 print_pbb (FILE *file, poly_bb_p pbb)
 436 {
 437   fprintf (file, "pbb_%d (\n", pbb_index (pbb));
 438   dump_gbb_conditions (file, PBB_BLACK_BOX (pbb));
 439   dump_gbb_cases (file, PBB_BLACK_BOX (pbb));
 440
 441   print_pbb_domain (file, pbb);
 442   print_pdrs (file, pbb);
 443   print_pbb_body (file, pbb);
 444
 445   fprintf (file, ")\n");
 446 }
 447
 448 /* Print to FILE the parameters of SCOP.  */
 449
 450 void
 451 print_scop_params (FILE *file, scop_p scop)
 452 {
 453   if (scop->scop_info->params.is_empty ())
 454     return;
 455
 456   int i;
 457   tree t;
 458   fprintf (file, "parameters (");
 459   FOR_EACH_VEC_ELT (scop->scop_info->params, i, t)
 460     {
 461       print_generic_expr (file, t, 0);
 462       fprintf (file, ", ");
 463     }
 464   fprintf (file, ")\n");
 465 }
 466
 467 /* Print to FILE the context of SCoP.  */
 468
 469 void
 470 print_scop_context (FILE *file, scop_p scop)
 471 {
 472   if (!scop->param_context)
 473     return;
 474
 475   fprintf (file, "Context (\n");
 476   print_isl_set (file, scop->param_context);
 477   fprintf (file, ")\n");
 478 }
 479
 480 /* Print to FILE the SCOP.  */
 481
 482 void
 483 print_scop (FILE *file, scop_p scop)
 484 {
 485   int i;
 486   poly_bb_p pbb;
 487
 488   fprintf (file, "SCoP (\n");
 489   print_scop_context (file, scop);
 490   print_scop_params (file, scop);
 491
 492   fprintf (file, "Number of statements: ");
 493   fprintf (file, "%d\n", scop->pbbs.length ());
 494
 495   FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
 496     print_pbb (file, pbb);
 497
 498   fprintf (file, ")\n");
 499 }
 500
 501 /* Print to STDERR the domain of PBB.  */
 502
 503 DEBUG_FUNCTION void
 504 debug_pbb_domain (poly_bb_p pbb)
 505 {
 506   print_pbb_domain (stderr, pbb);
 507 }
 508
 509 /* Print to FILE the domain and scattering function of PBB.  */
 510
 511 DEBUG_FUNCTION void
 512 debug_pbb (poly_bb_p pbb)
 513 {
 514   print_pbb (stderr, pbb);
 515 }
 516
 517 /* Print to STDERR the context of SCOP.  */
 518
 519 DEBUG_FUNCTION void
 520 debug_scop_context (scop_p scop)
 521 {
 522   print_scop_context (stderr, scop);
 523 }
 524
 525 /* Print to STDERR the SCOP.  */
 526
 527 DEBUG_FUNCTION void
 528 debug_scop (scop_p scop)
 529 {
 530   print_scop (stderr, scop);
 531 }
 532
 533 /* Print to STDERR the parameters of SCOP.  */
 534
 535 DEBUG_FUNCTION void
 536 debug_scop_params (scop_p scop)
 537 {
 538   print_scop_params (stderr, scop);
 539 }
 540
 541 extern isl_ctx *the_isl_ctx;
 542 void
 543 print_isl_set (FILE *f, __isl_keep isl_set *set)
 544 {
 545   isl_printer *p = isl_printer_to_file (the_isl_ctx, f);
 546 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
 547   p = isl_printer_set_yaml_style (p, ISL_YAML_STYLE_BLOCK);
 548 #endif
 549   p = isl_printer_print_set (p, set);
 550   p = isl_printer_print_str (p, "\n");
 551   isl_printer_free (p);
 552 }
 553
 554 DEBUG_FUNCTION void
 555 debug_isl_set (__isl_keep isl_set *set)
 556 {
 557   print_isl_set (stderr, set);
 558 }
 559
 560 void
 561 print_isl_map (FILE *f, __isl_keep isl_map *map)
 562 {
 563   isl_printer *p = isl_printer_to_file (the_isl_ctx, f);
 564 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
 565   p = isl_printer_set_yaml_style (p, ISL_YAML_STYLE_BLOCK);
 566 #endif
 567   p = isl_printer_print_map (p, map);
 568   p = isl_printer_print_str (p, "\n");
 569   isl_printer_free (p);
 570 }
 571
 572 DEBUG_FUNCTION void
 573 debug_isl_map (__isl_keep isl_map *map)
 574 {
 575   print_isl_map (stderr, map);
 576 }
 577
 578 void
 579 print_isl_union_map (FILE *f, __isl_keep isl_union_map *map)
 580 {
 581   isl_printer *p = isl_printer_to_file (the_isl_ctx, f);
 582 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
 583   p = isl_printer_set_yaml_style (p, ISL_YAML_STYLE_BLOCK);
 584 #endif
 585   p = isl_printer_print_union_map (p, map);
 586   p = isl_printer_print_str (p, "\n");
 587   isl_printer_free (p);
 588 }
 589
 590 DEBUG_FUNCTION void
 591 debug_isl_union_map (__isl_keep isl_union_map *map)
 592 {
 593   print_isl_union_map (stderr, map);
 594 }
 595
 596 void
 597 print_isl_aff (FILE *f, __isl_keep isl_aff *aff)
 598 {
 599   isl_printer *p = isl_printer_to_file (the_isl_ctx, f);
 600   p = isl_printer_print_aff (p, aff);
 601   p = isl_printer_print_str (p, "\n");
 602   isl_printer_free (p);
 603 }
 604
 605 DEBUG_FUNCTION void
 606 debug_isl_aff (__isl_keep isl_aff *aff)
 607 {
 608   print_isl_aff (stderr, aff);
 609 }
 610
 611 void
 612 print_isl_constraint (FILE *f, __isl_keep isl_constraint *c)
 613 {
 614   isl_printer *p = isl_printer_to_file (the_isl_ctx, f);
 615   p = isl_printer_print_constraint (p, c);
 616   p = isl_printer_print_str (p, "\n");
 617   isl_printer_free (p);
 618 }
 619
 620 DEBUG_FUNCTION void
 621 debug_isl_constraint (__isl_keep isl_constraint *c)
 622 {
 623   print_isl_constraint (stderr, c);
 624 }
 625
 626 void
 627 print_isl_schedule (FILE *f, __isl_keep isl_schedule *s)
 628 {
 629   isl_printer *p = isl_printer_to_file (the_isl_ctx, f);
 630 #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
 631   p = isl_printer_set_yaml_style (p, ISL_YAML_STYLE_BLOCK);
 632 #endif
 633   p = isl_printer_print_schedule (p, s);
 634   p = isl_printer_print_str (p, "\n");
 635   isl_printer_free (p);
 636 }
 637
 638 DEBUG_FUNCTION void
 639 debug_isl_schedule (__isl_keep isl_schedule *s)
 640 {
 641   print_isl_schedule (stderr, s);
 642 }
 643
 644 void
 645 print_isl_ast (FILE *file, __isl_keep isl_ast_node *n)
 646 {
 647   isl_printer *prn = isl_printer_to_file (the_isl_ctx, file);
 648   prn = isl_printer_set_output_format (prn, ISL_FORMAT_C);
 649   prn = isl_printer_print_ast_node (prn, n);
 650   prn = isl_printer_print_str (prn, "\n");
 651   isl_printer_free (prn);
 652 }
 653
 654 DEBUG_FUNCTION void
 655 debug_isl_ast (isl_ast_node *n)
 656 {
 657   print_isl_ast (stderr, n);
 658 }
 659
 660 DEBUG_FUNCTION void
 661 debug_scop_pbb (scop_p scop, int i)
 662 {
 663   debug_pbb (scop->pbbs[i]);
 664 }
 665
 666 #endif  /* HAVE_isl */
 667