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 /* Apply graphite transformations to all the basic blocks of SCOP.  */
  90
  91 bool
  92 apply_poly_transforms (scop_p scop)
  93 {
  94   bool transform_done = false;
  95
  96   /* Generate code even if we did not apply any real transformation.
  97      This also allows to check the performance for the identity
  98      transformation: GIMPLE -> GRAPHITE -> GIMPLE.  */
  99   if (flag_graphite_identity)
 100     transform_done = true;
 101
 102   if (flag_loop_parallelize_all)
 103     transform_done = true;
 104
 105   if (flag_loop_nest_optimize)
 106     transform_done |= optimize_isl (scop);
 107
 108   return transform_done;
 109 }
 110
 111 /* Create a new polyhedral data reference and add it to PBB.  It is
 112    defined by its ACCESSES, its TYPE, and the number of subscripts
 113    NB_SUBSCRIPTS.  */
 114
 115 void
 116 new_poly_dr (poly_bb_p pbb, gimple *stmt, enum poly_dr_type type,
 117              isl_map *acc, isl_set *subscript_sizes)
 118 {
 119   static int id = 0;
 120   poly_dr_p pdr = XNEW (struct poly_dr);
 121
 122   pdr->stmt = stmt;
 123   PDR_ID (pdr) = id++;
 124   PDR_NB_REFS (pdr) = 1;
 125   PDR_PBB (pdr) = pbb;
 126   pdr->accesses = acc;
 127   pdr->subscript_sizes = subscript_sizes;
 128   PDR_TYPE (pdr) = type;
 129   PBB_DRS (pbb).safe_push (pdr);
 130
 131   if (dump_file)
 132     {
 133       fprintf (dump_file, "Converting dr: ");
 134       print_pdr (dump_file, pdr);
 135       fprintf (dump_file, "To polyhedral representation:\n");
 136       fprintf (dump_file, "  - access functions: ");
 137       print_isl_map (dump_file, acc);
 138       fprintf (dump_file, "  - subscripts: ");
 139       print_isl_set (dump_file, subscript_sizes);
 140     }
 141 }
 142
 143 /* Free polyhedral data reference PDR.  */
 144
 145 void
 146 free_poly_dr (poly_dr_p pdr)
 147 {
 148   isl_map_free (pdr->accesses);
 149   isl_set_free (pdr->subscript_sizes);
 150   XDELETE (pdr);
 151 }
 152
 153 /* Create a new polyhedral black box.  */
 154
 155 poly_bb_p
 156 new_poly_bb (scop_p scop, gimple_poly_bb_p black_box)
 157 {
 158   poly_bb_p pbb = XNEW (struct poly_bb);
 159
 160   pbb->domain = NULL;
 161   pbb->schedule = NULL;
 162   pbb->transformed = NULL;
 163   pbb->saved = NULL;
 164   PBB_SCOP (pbb) = scop;
 165   pbb_set_black_box (pbb, black_box);
 166   PBB_DRS (pbb).create (3);
 167   PBB_IS_REDUCTION (pbb) = false;
 168   GBB_PBB ((gimple_poly_bb_p) black_box) = pbb;
 169
 170   return pbb;
 171 }
 172
 173 /* Free polyhedral black box.  */
 174
 175 void
 176 free_poly_bb (poly_bb_p pbb)
 177 {
 178   int i;
 179   poly_dr_p pdr;
 180
 181   isl_set_free (pbb->domain);
 182   isl_map_free (pbb->schedule);
 183   isl_map_free (pbb->transformed);
 184   isl_map_free (pbb->saved);
 185
 186   if (PBB_DRS (pbb).exists ())
 187     FOR_EACH_VEC_ELT (PBB_DRS (pbb), i, pdr)
 188       free_poly_dr (pdr);
 189
 190   PBB_DRS (pbb).release ();
 191   XDELETE (pbb);
 192 }
 193
 194 /* Prints to FILE the polyhedral data reference PDR.  */
 195
 196 void
 197 print_pdr (FILE *file, poly_dr_p pdr)
 198 {
 199   fprintf (file, "pdr_%d (", PDR_ID (pdr));
 200
 201   switch (PDR_TYPE (pdr))
 202     {
 203     case PDR_READ:
 204       fprintf (file, "read \n");
 205       break;
 206
 207     case PDR_WRITE:
 208       fprintf (file, "write \n");
 209       break;
 210
 211     case PDR_MAY_WRITE:
 212       fprintf (file, "may_write \n");
 213       break;
 214
 215     default:
 216       gcc_unreachable ();
 217     }
 218
 219   fprintf (file, "in gimple stmt: ");
 220   print_gimple_stmt (file, pdr->stmt, 0, 0);
 221   fprintf (file, "data accesses: ");
 222   print_isl_map (file, pdr->accesses);
 223   fprintf (file, "subscript sizes: ");
 224   print_isl_set (file, pdr->subscript_sizes);
 225   fprintf (file, ")\n");
 226 }
 227
 228 /* Prints to STDERR the polyhedral data reference PDR.  */
 229
 230 DEBUG_FUNCTION void
 231 debug_pdr (poly_dr_p pdr)
 232 {
 233   print_pdr (stderr, pdr);
 234 }
 235
 236 /* Store the GRAPHITE representation of BB.  */
 237
 238 gimple_poly_bb_p
 239 new_gimple_poly_bb (basic_block bb, vec<data_reference_p> drs,
 240                     vec<scalar_use> reads, vec<tree> writes)
 241 {
 242   gimple_poly_bb_p gbb = XNEW (struct gimple_poly_bb);
 243   GBB_BB (gbb) = bb;
 244   GBB_DATA_REFS (gbb) = drs;
 245   gbb->read_scalar_refs = reads;
 246   gbb->write_scalar_refs = writes;
 247   GBB_CONDITIONS (gbb).create (0);
 248   GBB_CONDITION_CASES (gbb).create (0);
 249
 250   return gbb;
 251 }
 252
 253 /* Frees GBB.  */
 254
 255 void
 256 free_gimple_poly_bb (gimple_poly_bb_p gbb)
 257 {
 258   free_data_refs (GBB_DATA_REFS (gbb));
 259   GBB_CONDITIONS (gbb).release ();
 260   GBB_CONDITION_CASES (gbb).release ();
 261   gbb->read_scalar_refs.release ();
 262   gbb->write_scalar_refs.release ();
 263   XDELETE (gbb);
 264 }
 265
 266 /* Deletes all gimple bbs in SCOP.  */
 267
 268 static void
 269 remove_gbbs_in_scop (scop_p scop)
 270 {
 271   int i;
 272   poly_bb_p pbb;
 273
 274   FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
 275     free_gimple_poly_bb (PBB_BLACK_BOX (pbb));
 276 }
 277
 278 /* Creates a new SCOP containing the region (ENTRY, EXIT).  */
 279
 280 scop_p
 281 new_scop (edge entry, edge exit)
 282 {
 283   sese_info_p region = new_sese_info (entry, exit);
 284   scop_p s = XNEW (struct scop);
 285
 286   s->schedule = NULL;
 287   s->param_context = NULL;
 288   scop_set_region (s, region);
 289   s->pbbs.create (3);
 290   s->drs.create (3);
 291   s->dependence = NULL;
 292   return s;
 293 }
 294
 295 /* Deletes SCOP.  */
 296
 297 void
 298 free_scop (scop_p scop)
 299 {
 300   int i;
 301   poly_bb_p pbb;
 302
 303   remove_gbbs_in_scop (scop);
 304   free_sese_info (scop->scop_info);
 305
 306   FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
 307     free_poly_bb (pbb);
 308
 309   scop->pbbs.release ();
 310   scop->drs.release ();
 311
 312   isl_set_free (scop->param_context);
 313   isl_union_map_free (scop->dependence);
 314   scop->dependence = NULL;
 315   XDELETE (scop);
 316 }
 317
 318 /* Print to FILE the domain of PBB.  */
 319
 320 void
 321 print_pbb_domain (FILE *file, poly_bb_p pbb)
 322 {
 323   print_isl_set (file, pbb->domain);
 324 }
 325
 326 /* Dump the cases of a graphite basic block GBB on FILE.  */
 327
 328 static void
 329 dump_gbb_cases (FILE *file, gimple_poly_bb_p gbb)
 330 {
 331   int i;
 332   gimple *stmt;
 333   vec<gimple *> cases;
 334
 335   if (!gbb)
 336     return;
 337
 338   cases = GBB_CONDITION_CASES (gbb);
 339   if (cases.is_empty ())
 340     return;
 341
 342   fprintf (file, "cases bb_%d (\n", GBB_BB (gbb)->index);
 343
 344   FOR_EACH_VEC_ELT (cases, i, stmt)
 345     print_gimple_stmt (file, stmt, 0, 0);
 346
 347   fprintf (file, ")\n");
 348 }
 349
 350 /* Dump conditions of a graphite basic block GBB on FILE.  */
 351
 352 static void
 353 dump_gbb_conditions (FILE *file, gimple_poly_bb_p gbb)
 354 {
 355   int i;
 356   gimple *stmt;
 357   vec<gimple *> conditions;
 358
 359   if (!gbb)
 360     return;
 361
 362   conditions = GBB_CONDITIONS (gbb);
 363   if (conditions.is_empty ())
 364     return;
 365
 366   fprintf (file, "conditions bb_%d (\n", GBB_BB (gbb)->index);
 367
 368   FOR_EACH_VEC_ELT (conditions, i, stmt)
 369     print_gimple_stmt (file, stmt, 0, 0);
 370
 371   fprintf (file, ")\n");
 372 }
 373
 374 /* Print to FILE all the data references of PBB.  */
 375
 376 void
 377 print_pdrs (FILE *file, poly_bb_p pbb)
 378 {
 379   int i;
 380   poly_dr_p pdr;
 381   int nb_reads = 0;
 382   int nb_writes = 0;
 383
 384   if (PBB_DRS (pbb).is_empty ())
 385     return;
 386
 387   fprintf (file, "Data references (\n");
 388
 389   FOR_EACH_VEC_ELT (PBB_DRS (pbb), i, pdr)
 390     if (PDR_TYPE (pdr) == PDR_READ)
 391       nb_reads++;
 392     else
 393       nb_writes++;
 394
 395   fprintf (file, "Read data references (\n");
 396
 397   FOR_EACH_VEC_ELT (PBB_DRS (pbb), i, pdr)
 398     if (PDR_TYPE (pdr) == PDR_READ)
 399       print_pdr (file, pdr);
 400
 401   fprintf (file, ")\n");
 402   fprintf (file, "Write data references (\n");
 403   FOR_EACH_VEC_ELT (PBB_DRS (pbb), i, pdr)
 404     if (PDR_TYPE (pdr) != PDR_READ)
 405       print_pdr (file, pdr);
 406   fprintf (file, ")\n");
 407   fprintf (file, ")\n");
 408 }
 409
 410 /* Print to STDERR all the data references of PBB.  */
 411
 412 DEBUG_FUNCTION void
 413 debug_pdrs (poly_bb_p pbb)
 414 {
 415   print_pdrs (stderr, pbb);
 416 }
 417
 418 /* Print to FILE the body of PBB.  */
 419
 420 static void
 421 print_pbb_body (FILE *file, poly_bb_p pbb)
 422 {
 423   fprintf (file, "Body (\n");
 424   dump_bb (file, pbb_bb (pbb), 0, 0);
 425   fprintf (file, ")\n");
 426 }
 427
 428 /* Print to FILE the domain and scattering function of PBB.  */
 429
 430 void
 431 print_pbb (FILE *file, poly_bb_p pbb)
 432 {
 433   fprintf (file, "pbb_%d (\n", pbb_index (pbb));
 434   dump_gbb_conditions (file, PBB_BLACK_BOX (pbb));
 435   dump_gbb_cases (file, PBB_BLACK_BOX (pbb));
 436
 437   print_pbb_domain (file, pbb);
 438   print_pdrs (file, pbb);
 439   print_pbb_body (file, pbb);
 440
 441   fprintf (file, ")\n");
 442 }
 443
 444 /* Print to FILE the parameters of SCOP.  */
 445
 446 void
 447 print_scop_params (FILE *file, scop_p scop)
 448 {
 449   if (scop->scop_info->params.is_empty ())
 450     return;
 451
 452   int i;
 453   tree t;
 454   fprintf (file, "parameters (");
 455   FOR_EACH_VEC_ELT (scop->scop_info->params, i, t)
 456     {
 457       print_generic_expr (file, t, 0);
 458       fprintf (file, ", ");
 459     }
 460   fprintf (file, ")\n");
 461 }
 462
 463 /* Print to FILE the context of SCoP.  */
 464
 465 void
 466 print_scop_context (FILE *file, scop_p scop)
 467 {
 468   if (!scop->param_context)
 469     return;
 470
 471   fprintf (file, "Context (\n");
 472   print_isl_set (file, scop->param_context);
 473   fprintf (file, ")\n");
 474 }
 475
 476 /* Print to FILE the SCOP.  */
 477
 478 void
 479 print_scop (FILE *file, scop_p scop)
 480 {
 481   int i;
 482   poly_bb_p pbb;
 483
 484   fprintf (file, "SCoP (\n");
 485   print_scop_context (file, scop);
 486   print_scop_params (file, scop);
 487
 488   fprintf (file, "Number of statements: ");
 489   fprintf (file, "%d\n", scop->pbbs.length ());
 490
 491   FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
 492     print_pbb (file, pbb);
 493
 494   fprintf (file, ")\n");
 495 }
 496
 497 /* Print to STDERR the domain of PBB.  */
 498
 499 DEBUG_FUNCTION void
 500 debug_pbb_domain (poly_bb_p pbb)
 501 {
 502   print_pbb_domain (stderr, pbb);
 503 }
 504
 505 /* Print to FILE the domain and scattering function of PBB.  */
 506
 507 DEBUG_FUNCTION void
 508 debug_pbb (poly_bb_p pbb)
 509 {
 510   print_pbb (stderr, pbb);
 511 }
 512
 513 /* Print to STDERR the context of SCOP.  */
 514
 515 DEBUG_FUNCTION void
 516 debug_scop_context (scop_p scop)
 517 {
 518   print_scop_context (stderr, scop);
 519 }
 520
 521 /* Print to STDERR the SCOP.  */
 522
 523 DEBUG_FUNCTION void
 524 debug_scop (scop_p scop)
 525 {
 526   print_scop (stderr, scop);
 527 }
 528
 529 /* Print to STDERR the parameters of SCOP.  */
 530
 531 DEBUG_FUNCTION void
 532 debug_scop_params (scop_p scop)
 533 {
 534   print_scop_params (stderr, scop);
 535 }
 536
 537 extern isl_ctx *the_isl_ctx;
 538 void
 539 print_isl_set (FILE *f, isl_set *set)
 540 {
 541   isl_printer *p = isl_printer_to_file (the_isl_ctx, f);
 542   p = isl_printer_print_set (p, set);
 543   p = isl_printer_print_str (p, "\n");
 544   isl_printer_free (p);
 545 }
 546
 547 DEBUG_FUNCTION void
 548 debug_isl_set (isl_set *set)
 549 {
 550   print_isl_set (stderr, set);
 551 }
 552
 553 void
 554 print_isl_map (FILE *f, isl_map *map)
 555 {
 556   isl_printer *p = isl_printer_to_file (the_isl_ctx, f);
 557   p = isl_printer_print_map (p, map);
 558   p = isl_printer_print_str (p, "\n");
 559   isl_printer_free (p);
 560 }
 561
 562 DEBUG_FUNCTION void
 563 debug_isl_map (isl_map *map)
 564 {
 565   print_isl_map (stderr, map);
 566 }
 567
 568 void
 569 print_isl_union_map (FILE *f, isl_union_map *map)
 570 {
 571   isl_printer *p = isl_printer_to_file (the_isl_ctx, f);
 572   p = isl_printer_print_union_map (p, map);
 573   p = isl_printer_print_str (p, "\n");
 574   isl_printer_free (p);
 575 }
 576
 577 DEBUG_FUNCTION void
 578 debug_isl_union_map (isl_union_map *map)
 579 {
 580   print_isl_union_map (stderr, map);
 581 }
 582
 583
 584 void
 585 print_isl_aff (FILE *f, isl_aff *aff)
 586 {
 587   isl_printer *p = isl_printer_to_file (the_isl_ctx, f);
 588   p = isl_printer_print_aff (p, aff);
 589   p = isl_printer_print_str (p, "\n");
 590   isl_printer_free (p);
 591 }
 592
 593 DEBUG_FUNCTION void
 594 debug_isl_aff (isl_aff *aff)
 595 {
 596   print_isl_aff (stderr, aff);
 597 }
 598
 599 void
 600 print_isl_constraint (FILE *f, isl_constraint *c)
 601 {
 602   isl_printer *p = isl_printer_to_file (the_isl_ctx, f);
 603   p = isl_printer_print_constraint (p, c);
 604   p = isl_printer_print_str (p, "\n");
 605   isl_printer_free (p);
 606 }
 607
 608 DEBUG_FUNCTION void
 609 debug_isl_constraint (isl_constraint *c)
 610 {
 611   print_isl_constraint (stderr, c);
 612 }
 613
 614 /* Returns the number of iterations RES of the loop around PBB at
 615    time(scattering) dimension TIME_DEPTH.  */
 616
 617 void
 618 pbb_number_of_iterations_at_time (poly_bb_p pbb,
 619                                   graphite_dim_t time_depth,
 620                                   mpz_t res)
 621 {
 622   isl_set *transdomain;
 623   isl_space *dc;
 624   isl_aff *aff;
 625   isl_val *isllb, *islub;
 626
 627   /* Map the iteration domain through the current scatter, and work
 628      on the resulting set.  */
 629   transdomain = isl_set_apply (isl_set_copy (pbb->domain),
 630                                isl_map_copy (pbb->transformed));
 631
 632   /* Select the time_depth' dimension via an affine expression.  */
 633   dc = isl_set_get_space (transdomain);
 634   aff = isl_aff_zero_on_domain (isl_local_space_from_space (dc));
 635   aff = isl_aff_set_coefficient_si (aff, isl_dim_in, time_depth, 1);
 636
 637   /* And find the min/max for that function.  */
 638   /* XXX isl check results?  */
 639   isllb = isl_set_min_val (transdomain, aff);
 640   islub = isl_set_max_val (transdomain, aff);
 641
 642   islub = isl_val_sub (islub, isllb);
 643   islub = isl_val_add_ui (islub, 1);
 644   isl_val_get_num_gmp (islub, res);
 645
 646   isl_val_free (islub);
 647   isl_aff_free (aff);
 648   isl_set_free (transdomain);
 649 }
 650
 651 #endif  /* HAVE_isl */
 652