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