gcc/graphite-poly.c

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