gcc/graphite-poly.c

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