gcc/graphite-poly.c

   1 /* Graphite polyhedral representation.
   2    Copyright (C) 2009-2017 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   pbb->iterators = NULL;
 140   PBB_SCOP (pbb) = scop;
 141   pbb_set_black_box (pbb, black_box);
 142   PBB_DRS (pbb).create (3);
 143   GBB_PBB ((gimple_poly_bb_p) black_box) = pbb;
 144
 145   return pbb;
 146 }
 147
 148 /* Free polyhedral black box.  */
 149
 150 static void
 151 free_poly_bb (poly_bb_p pbb)
 152 {
 153   int i;
 154   poly_dr_p pdr;
 155
 156   isl_set_free (pbb->domain);
 157   pbb->domain = NULL;
 158   isl_set_free (pbb->iterators);
 159   pbb->iterators = NULL;
 160
 161   if (PBB_DRS (pbb).exists ())
 162     FOR_EACH_VEC_ELT (PBB_DRS (pbb), i, pdr)
 163       free_poly_dr (pdr);
 164
 165   PBB_DRS (pbb).release ();
 166   XDELETE (pbb);
 167 }
 168
 169 /* Prints to FILE the polyhedral data reference PDR.  */
 170
 171 void
 172 print_pdr (FILE *file, poly_dr_p pdr)
 173 {
 174   fprintf (file, "pdr_%d (", PDR_ID (pdr));
 175
 176   switch (PDR_TYPE (pdr))
 177     {
 178     case PDR_READ:
 179       fprintf (file, "read \n");
 180       break;
 181
 182     case PDR_WRITE:
 183       fprintf (file, "write \n");
 184       break;
 185
 186     case PDR_MAY_WRITE:
 187       fprintf (file, "may_write \n");
 188       break;
 189
 190     default:
 191       gcc_unreachable ();
 192     }
 193
 194   fprintf (file, "in gimple stmt: ");
 195   print_gimple_stmt (file, pdr->stmt, 0, 0);
 196   fprintf (file, "data accesses: ");
 197   print_isl_map (file, pdr->accesses);
 198   fprintf (file, "subscript sizes: ");
 199   print_isl_set (file, pdr->subscript_sizes);
 200   fprintf (file, ")\n");
 201 }
 202
 203 /* Prints to STDERR the polyhedral data reference PDR.  */
 204
 205 DEBUG_FUNCTION void
 206 debug_pdr (poly_dr_p pdr)
 207 {
 208   print_pdr (stderr, pdr);
 209 }
 210
 211 /* Store the GRAPHITE representation of BB.  */
 212
 213 gimple_poly_bb_p
 214 new_gimple_poly_bb (basic_block bb, vec<data_reference_p> drs,
 215                     vec<scalar_use> reads, vec<tree> writes)
 216 {
 217   gimple_poly_bb_p gbb = XNEW (struct gimple_poly_bb);
 218   GBB_BB (gbb) = bb;
 219   GBB_DATA_REFS (gbb) = drs;
 220   gbb->read_scalar_refs = reads;
 221   gbb->write_scalar_refs = writes;
 222   GBB_CONDITIONS (gbb).create (0);
 223   GBB_CONDITION_CASES (gbb).create (0);
 224
 225   return gbb;
 226 }
 227
 228 /* Frees GBB.  */
 229
 230 static void
 231 free_gimple_poly_bb (gimple_poly_bb_p gbb)
 232 {
 233   free_data_refs (GBB_DATA_REFS (gbb));
 234   GBB_CONDITIONS (gbb).release ();
 235   GBB_CONDITION_CASES (gbb).release ();
 236   gbb->read_scalar_refs.release ();
 237   gbb->write_scalar_refs.release ();
 238   XDELETE (gbb);
 239 }
 240
 241 /* Deletes all gimple bbs in SCOP.  */
 242
 243 static void
 244 remove_gbbs_in_scop (scop_p scop)
 245 {
 246   int i;
 247   poly_bb_p pbb;
 248
 249   FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
 250     free_gimple_poly_bb (PBB_BLACK_BOX (pbb));
 251 }
 252
 253 /* Creates a new SCOP containing the region (ENTRY, EXIT).  */
 254
 255 scop_p
 256 new_scop (edge entry, edge exit)
 257 {
 258   sese_info_p region = new_sese_info (entry, exit);
 259   scop_p s = XNEW (struct scop);
 260
 261   s->original_schedule = NULL;
 262   s->transformed_schedule = NULL;
 263   s->param_context = NULL;
 264   scop_set_region (s, region);
 265   s->pbbs.create (3);
 266   s->drs.create (3);
 267   s->dependence = NULL;
 268   return s;
 269 }
 270
 271 /* Deletes SCOP.  */
 272
 273 void
 274 free_scop (scop_p scop)
 275 {
 276   int i;
 277   poly_bb_p pbb;
 278
 279   remove_gbbs_in_scop (scop);
 280   free_sese_info (scop->scop_info);
 281
 282   FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
 283     free_poly_bb (pbb);
 284
 285   scop->pbbs.release ();
 286   scop->drs.release ();
 287
 288   isl_set_free (scop->param_context);
 289   scop->param_context = NULL;
 290   isl_union_map_free (scop->dependence);
 291   scop->dependence = NULL;
 292   isl_schedule_free (scop->original_schedule);
 293   scop->original_schedule = NULL;
 294   isl_schedule_free (scop->transformed_schedule);
 295   scop->transformed_schedule = NULL;
 296   XDELETE (scop);
 297 }
 298
 299 /* Print to FILE the domain of PBB.  */
 300
 301 void
 302 print_pbb_domain (FILE *file, poly_bb_p pbb)
 303 {
 304   print_isl_set (file, pbb->domain);
 305 }
 306
 307 /* Dump the cases of a graphite basic block GBB on FILE.  */
 308
 309 static void
 310 dump_gbb_cases (FILE *file, gimple_poly_bb_p gbb)
 311 {
 312   int i;
 313   gimple *stmt;
 314   vec<gimple *> cases;
 315
 316   if (!gbb)
 317     return;
 318
 319   cases = GBB_CONDITION_CASES (gbb);
 320   if (cases.is_empty ())
 321     return;
 322
 323   fprintf (file, "cases bb_%d (\n", GBB_BB (gbb)->index);
 324
 325   FOR_EACH_VEC_ELT (cases, i, stmt)
 326     print_gimple_stmt (file, stmt, 0, 0);
 327
 328   fprintf (file, ")\n");
 329 }
 330
 331 /* Dump conditions of a graphite basic block GBB on FILE.  */
 332
 333 static void
 334 dump_gbb_conditions (FILE *file, gimple_poly_bb_p gbb)
 335 {
 336   int i;
 337   gimple *stmt;
 338   vec<gimple *> conditions;
 339
 340   if (!gbb)
 341     return;
 342
 343   conditions = GBB_CONDITIONS (gbb);
 344   if (conditions.is_empty ())
 345     return;
 346
 347   fprintf (file, "conditions bb_%d (\n", GBB_BB (gbb)->index);
 348
 349   FOR_EACH_VEC_ELT (conditions, i, stmt)
 350     print_gimple_stmt (file, stmt, 0, 0);
 351
 352   fprintf (file, ")\n");
 353 }
 354
 355 /* Print to FILE all the data references of PBB.  */
 356
 357 void
 358 print_pdrs (FILE *file, poly_bb_p pbb)
 359 {
 360   int i;
 361   poly_dr_p pdr;
 362   int nb_reads = 0;
 363   int nb_writes = 0;
 364
 365   if (PBB_DRS (pbb).is_empty ())
 366     return;
 367
 368   fprintf (file, "Data references (\n");
 369
 370   FOR_EACH_VEC_ELT (PBB_DRS (pbb), i, pdr)
 371     if (PDR_TYPE (pdr) == PDR_READ)
 372       nb_reads++;
 373     else
 374       nb_writes++;
 375
 376   fprintf (file, "Read data references (\n");
 377
 378   FOR_EACH_VEC_ELT (PBB_DRS (pbb), i, pdr)
 379     if (PDR_TYPE (pdr) == PDR_READ)
 380       print_pdr (file, pdr);
 381
 382   fprintf (file, ")\n");
 383   fprintf (file, "Write data references (\n");
 384   FOR_EACH_VEC_ELT (PBB_DRS (pbb), i, pdr)
 385     if (PDR_TYPE (pdr) != PDR_READ)
 386       print_pdr (file, pdr);
 387   fprintf (file, ")\n");
 388   fprintf (file, ")\n");
 389 }
 390
 391 /* Print to STDERR all the data references of PBB.  */
 392
 393 DEBUG_FUNCTION void
 394 debug_pdrs (poly_bb_p pbb)
 395 {
 396   print_pdrs (stderr, pbb);
 397 }
 398
 399 /* Print to FILE the body of PBB.  */
 400
 401 static void
 402 print_pbb_body (FILE *file, poly_bb_p pbb)
 403 {
 404   fprintf (file, "Body (\n");
 405   dump_bb (file, pbb_bb (pbb), 0, 0);
 406   fprintf (file, ")\n");
 407 }
 408
 409 /* Print to FILE the domain and scattering function of PBB.  */
 410
 411 void
 412 print_pbb (FILE *file, poly_bb_p pbb)
 413 {
 414   fprintf (file, "pbb_%d (\n", pbb_index (pbb));
 415   dump_gbb_conditions (file, PBB_BLACK_BOX (pbb));
 416   dump_gbb_cases (file, PBB_BLACK_BOX (pbb));
 417
 418   print_pbb_domain (file, pbb);
 419   print_pdrs (file, pbb);
 420   print_pbb_body (file, pbb);
 421
 422   fprintf (file, ")\n");
 423 }
 424
 425 /* Print to FILE the parameters of SCOP.  */
 426
 427 void
 428 print_scop_params (FILE *file, scop_p scop)
 429 {
 430   if (scop->scop_info->params.is_empty ())
 431     return;
 432
 433   int i;
 434   tree t;
 435   fprintf (file, "parameters (");
 436   FOR_EACH_VEC_ELT (scop->scop_info->params, i, t)
 437     {
 438       print_generic_expr (file, t, 0);
 439       fprintf (file, ", ");
 440     }
 441   fprintf (file, ")\n");
 442 }
 443
 444 /* Print to FILE the context of SCoP.  */
 445
 446 void
 447 print_scop_context (FILE *file, scop_p scop)
 448 {
 449   if (!scop->param_context)
 450     return;
 451
 452   fprintf (file, "Context (\n");
 453   print_isl_set (file, scop->param_context);
 454   fprintf (file, ")\n");
 455 }
 456
 457 /* Print to FILE the SCOP.  */
 458
 459 void
 460 print_scop (FILE *file, scop_p scop)
 461 {
 462   int i;
 463   poly_bb_p pbb;
 464
 465   fprintf (file, "SCoP (\n");
 466   print_scop_context (file, scop);
 467   print_scop_params (file, scop);
 468
 469   fprintf (file, "Number of statements: ");
 470   fprintf (file, "%d\n", scop->pbbs.length ());
 471
 472   FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
 473     print_pbb (file, pbb);
 474
 475   fprintf (file, ")\n");
 476 }
 477
 478 /* Print to STDERR the domain of PBB.  */
 479
 480 DEBUG_FUNCTION void
 481 debug_pbb_domain (poly_bb_p pbb)
 482 {
 483   print_pbb_domain (stderr, pbb);
 484 }
 485
 486 /* Print to FILE the domain and scattering function of PBB.  */
 487
 488 DEBUG_FUNCTION void
 489 debug_pbb (poly_bb_p pbb)
 490 {
 491   print_pbb (stderr, pbb);
 492 }
 493
 494 /* Print to STDERR the context of SCOP.  */
 495
 496 DEBUG_FUNCTION void
 497 debug_scop_context (scop_p scop)
 498 {
 499   print_scop_context (stderr, scop);
 500 }
 501
 502 /* Print to STDERR the SCOP.  */
 503
 504 DEBUG_FUNCTION void
 505 debug_scop (scop_p scop)
 506 {
 507   print_scop (stderr, scop);
 508 }
 509
 510 /* Print to STDERR the parameters of SCOP.  */
 511
 512 DEBUG_FUNCTION void
 513 debug_scop_params (scop_p scop)
 514 {
 515   print_scop_params (stderr, scop);
 516 }
 517
 518 extern isl_ctx *the_isl_ctx;
 519 void
 520 print_isl_set (FILE *f, __isl_keep isl_set *set)
 521 {
 522   isl_printer *p = isl_printer_to_file (the_isl_ctx, f);
 523   p = isl_printer_set_yaml_style (p, ISL_YAML_STYLE_BLOCK);
 524   p = isl_printer_print_set (p, set);
 525   p = isl_printer_print_str (p, "\n");
 526   isl_printer_free (p);
 527 }
 528
 529 DEBUG_FUNCTION void
 530 debug_isl_set (__isl_keep isl_set *set)
 531 {
 532   print_isl_set (stderr, set);
 533 }
 534
 535 void
 536 print_isl_map (FILE *f, __isl_keep isl_map *map)
 537 {
 538   isl_printer *p = isl_printer_to_file (the_isl_ctx, f);
 539   p = isl_printer_set_yaml_style (p, ISL_YAML_STYLE_BLOCK);
 540   p = isl_printer_print_map (p, map);
 541   p = isl_printer_print_str (p, "\n");
 542   isl_printer_free (p);
 543 }
 544
 545 DEBUG_FUNCTION void
 546 debug_isl_map (__isl_keep isl_map *map)
 547 {
 548   print_isl_map (stderr, map);
 549 }
 550
 551 void
 552 print_isl_union_map (FILE *f, __isl_keep isl_union_map *map)
 553 {
 554   isl_printer *p = isl_printer_to_file (the_isl_ctx, f);
 555   p = isl_printer_set_yaml_style (p, ISL_YAML_STYLE_BLOCK);
 556   p = isl_printer_print_union_map (p, map);
 557   p = isl_printer_print_str (p, "\n");
 558   isl_printer_free (p);
 559 }
 560
 561 DEBUG_FUNCTION void
 562 debug_isl_union_map (__isl_keep isl_union_map *map)
 563 {
 564   print_isl_union_map (stderr, map);
 565 }
 566
 567 void
 568 print_isl_aff (FILE *f, __isl_keep isl_aff *aff)
 569 {
 570   isl_printer *p = isl_printer_to_file (the_isl_ctx, f);
 571   p = isl_printer_print_aff (p, aff);
 572   p = isl_printer_print_str (p, "\n");
 573   isl_printer_free (p);
 574 }
 575
 576 DEBUG_FUNCTION void
 577 debug_isl_aff (__isl_keep isl_aff *aff)
 578 {
 579   print_isl_aff (stderr, aff);
 580 }
 581
 582 void
 583 print_isl_constraint (FILE *f, __isl_keep isl_constraint *c)
 584 {
 585   isl_printer *p = isl_printer_to_file (the_isl_ctx, f);
 586   p = isl_printer_print_constraint (p, c);
 587   p = isl_printer_print_str (p, "\n");
 588   isl_printer_free (p);
 589 }
 590
 591 DEBUG_FUNCTION void
 592 debug_isl_constraint (__isl_keep isl_constraint *c)
 593 {
 594   print_isl_constraint (stderr, c);
 595 }
 596
 597 void
 598 print_isl_schedule (FILE *f, __isl_keep isl_schedule *s)
 599 {
 600   isl_printer *p = isl_printer_to_file (the_isl_ctx, f);
 601   p = isl_printer_set_yaml_style (p, ISL_YAML_STYLE_BLOCK);
 602   p = isl_printer_print_schedule (p, s);
 603   p = isl_printer_print_str (p, "\n");
 604   isl_printer_free (p);
 605 }
 606
 607 DEBUG_FUNCTION void
 608 debug_isl_schedule (__isl_keep isl_schedule *s)
 609 {
 610   print_isl_schedule (stderr, s);
 611 }
 612
 613 void
 614 print_isl_ast (FILE *file, __isl_keep isl_ast_node *n)
 615 {
 616   isl_printer *prn = isl_printer_to_file (the_isl_ctx, file);
 617   prn = isl_printer_set_output_format (prn, ISL_FORMAT_C);
 618   prn = isl_printer_print_ast_node (prn, n);
 619   prn = isl_printer_print_str (prn, "\n");
 620   isl_printer_free (prn);
 621 }
 622
 623 DEBUG_FUNCTION void
 624 debug_isl_ast (isl_ast_node *n)
 625 {
 626   print_isl_ast (stderr, n);
 627 }
 628
 629 DEBUG_FUNCTION void
 630 debug_scop_pbb (scop_p scop, int i)
 631 {
 632   debug_pbb (scop->pbbs[i]);
 633 }
 634
 635 #endif  /* HAVE_isl */
 636