gcc/graphite-poly.cc

   1 /* Graphite polyhedral representation.
   2    Copyright (C) 2009-2024 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   if (PBB_DRS (pbb).is_empty ())
 345     return;
 346
 347   fprintf (file, "Data references (\n");
 348   fprintf (file, "Read data references (\n");
 349
 350   for (poly_dr_p pdr : PBB_DRS (pbb))
 351     if (PDR_TYPE (pdr) == PDR_READ)
 352       print_pdr (file, pdr);
 353
 354   fprintf (file, ")\n");
 355   fprintf (file, "Write data references (\n");
 356   for (poly_dr_p pdr : PBB_DRS (pbb))
 357     if (PDR_TYPE (pdr) != PDR_READ)
 358       print_pdr (file, pdr);
 359   fprintf (file, ")\n");
 360   fprintf (file, ")\n");
 361 }
 362
 363 /* Print to STDERR all the data references of PBB.  */
 364
 365 DEBUG_FUNCTION void
 366 debug_pdrs (poly_bb_p pbb)
 367 {
 368   print_pdrs (stderr, pbb);
 369 }
 370
 371 /* Print to FILE the body of PBB.  */
 372
 373 static void
 374 print_pbb_body (FILE *file, poly_bb_p pbb)
 375 {
 376   fprintf (file, "Body (\n");
 377   dump_bb (file, pbb_bb (pbb), 0, TDF_NONE);
 378   fprintf (file, ")\n");
 379 }
 380
 381 /* Print to FILE the domain and scattering function of PBB.  */
 382
 383 void
 384 print_pbb (FILE *file, poly_bb_p pbb)
 385 {
 386   fprintf (file, "pbb_%d (\n", pbb_index (pbb));
 387   dump_gbb_conditions (file, PBB_BLACK_BOX (pbb));
 388   dump_gbb_cases (file, PBB_BLACK_BOX (pbb));
 389
 390   print_pbb_domain (file, pbb);
 391   print_pdrs (file, pbb);
 392   print_pbb_body (file, pbb);
 393
 394   fprintf (file, ")\n");
 395 }
 396
 397 /* Print to FILE the parameters of SCOP.  */
 398
 399 void
 400 print_scop_params (FILE *file, scop_p scop)
 401 {
 402   if (scop->scop_info->params.is_empty ())
 403     return;
 404
 405   int i;
 406   tree t;
 407   fprintf (file, "parameters (");
 408   FOR_EACH_VEC_ELT (scop->scop_info->params, i, t)
 409     {
 410       print_generic_expr (file, t);
 411       fprintf (file, ", ");
 412     }
 413   fprintf (file, ")\n");
 414 }
 415
 416 /* Print to FILE the context of SCoP.  */
 417
 418 void
 419 print_scop_context (FILE *file, scop_p scop)
 420 {
 421   if (!scop->param_context)
 422     return;
 423
 424   fprintf (file, "Context (\n");
 425   print_isl_set (file, scop->param_context);
 426   fprintf (file, ")\n");
 427 }
 428
 429 /* Print to FILE the SCOP.  */
 430
 431 void
 432 print_scop (FILE *file, scop_p scop)
 433 {
 434   fprintf (file, "SCoP (\n");
 435   print_scop_context (file, scop);
 436   print_scop_params (file, scop);
 437
 438   fprintf (file, "Number of statements: ");
 439   fprintf (file, "%d\n", scop->pbbs.length ());
 440
 441   for (poly_bb_p pbb : scop->pbbs)
 442     print_pbb (file, pbb);
 443
 444   fprintf (file, ")\n");
 445 }
 446
 447 /* Print to STDERR the domain of PBB.  */
 448
 449 DEBUG_FUNCTION void
 450 debug_pbb_domain (poly_bb_p pbb)
 451 {
 452   print_pbb_domain (stderr, pbb);
 453 }
 454
 455 /* Print to FILE the domain and scattering function of PBB.  */
 456
 457 DEBUG_FUNCTION void
 458 debug_pbb (poly_bb_p pbb)
 459 {
 460   print_pbb (stderr, pbb);
 461 }
 462
 463 /* Print to STDERR the context of SCOP.  */
 464
 465 DEBUG_FUNCTION void
 466 debug_scop_context (scop_p scop)
 467 {
 468   print_scop_context (stderr, scop);
 469 }
 470
 471 /* Print to STDERR the SCOP.  */
 472
 473 DEBUG_FUNCTION void
 474 debug_scop (scop_p scop)
 475 {
 476   print_scop (stderr, scop);
 477 }
 478
 479 /* Print to STDERR the parameters of SCOP.  */
 480
 481 DEBUG_FUNCTION void
 482 debug_scop_params (scop_p scop)
 483 {
 484   print_scop_params (stderr, scop);
 485 }
 486
 487 extern isl_ctx *the_isl_ctx;
 488 void
 489 print_isl_set (FILE *f, __isl_keep isl_set *set)
 490 {
 491   isl_printer *p = isl_printer_to_file (the_isl_ctx, f);
 492   p = isl_printer_set_yaml_style (p, ISL_YAML_STYLE_BLOCK);
 493   p = isl_printer_print_set (p, set);
 494   p = isl_printer_print_str (p, "\n");
 495   isl_printer_free (p);
 496 }
 497
 498 DEBUG_FUNCTION void
 499 debug_isl_set (__isl_keep isl_set *set)
 500 {
 501   print_isl_set (stderr, set);
 502 }
 503
 504 void
 505 print_isl_map (FILE *f, __isl_keep isl_map *map)
 506 {
 507   isl_printer *p = isl_printer_to_file (the_isl_ctx, f);
 508   p = isl_printer_set_yaml_style (p, ISL_YAML_STYLE_BLOCK);
 509   p = isl_printer_print_map (p, map);
 510   p = isl_printer_print_str (p, "\n");
 511   isl_printer_free (p);
 512 }
 513
 514 DEBUG_FUNCTION void
 515 debug_isl_map (__isl_keep isl_map *map)
 516 {
 517   print_isl_map (stderr, map);
 518 }
 519
 520 void
 521 print_isl_union_map (FILE *f, __isl_keep isl_union_map *map)
 522 {
 523   isl_printer *p = isl_printer_to_file (the_isl_ctx, f);
 524   p = isl_printer_set_yaml_style (p, ISL_YAML_STYLE_BLOCK);
 525   p = isl_printer_print_union_map (p, map);
 526   p = isl_printer_print_str (p, "\n");
 527   isl_printer_free (p);
 528 }
 529
 530 DEBUG_FUNCTION void
 531 debug_isl_union_map (__isl_keep isl_union_map *map)
 532 {
 533   print_isl_union_map (stderr, map);
 534 }
 535
 536 void
 537 print_isl_aff (FILE *f, __isl_keep isl_aff *aff)
 538 {
 539   isl_printer *p = isl_printer_to_file (the_isl_ctx, f);
 540   p = isl_printer_print_aff (p, aff);
 541   p = isl_printer_print_str (p, "\n");
 542   isl_printer_free (p);
 543 }
 544
 545 DEBUG_FUNCTION void
 546 debug_isl_aff (__isl_keep isl_aff *aff)
 547 {
 548   print_isl_aff (stderr, aff);
 549 }
 550
 551 void
 552 print_isl_constraint (FILE *f, __isl_keep isl_constraint *c)
 553 {
 554   isl_printer *p = isl_printer_to_file (the_isl_ctx, f);
 555   p = isl_printer_print_constraint (p, c);
 556   p = isl_printer_print_str (p, "\n");
 557   isl_printer_free (p);
 558 }
 559
 560 DEBUG_FUNCTION void
 561 debug_isl_constraint (__isl_keep isl_constraint *c)
 562 {
 563   print_isl_constraint (stderr, c);
 564 }
 565
 566 void
 567 print_isl_schedule (FILE *f, __isl_keep isl_schedule *s)
 568 {
 569   isl_printer *p = isl_printer_to_file (the_isl_ctx, f);
 570   p = isl_printer_set_yaml_style (p, ISL_YAML_STYLE_BLOCK);
 571   p = isl_printer_print_schedule (p, s);
 572   p = isl_printer_print_str (p, "\n");
 573   isl_printer_free (p);
 574 }
 575
 576 DEBUG_FUNCTION void
 577 debug_isl_schedule (__isl_keep isl_schedule *s)
 578 {
 579   print_isl_schedule (stderr, s);
 580 }
 581
 582 void
 583 print_isl_ast (FILE *file, __isl_keep isl_ast_node *n)
 584 {
 585   isl_printer *prn = isl_printer_to_file (the_isl_ctx, file);
 586   prn = isl_printer_set_output_format (prn, ISL_FORMAT_C);
 587   prn = isl_printer_print_ast_node (prn, n);
 588   prn = isl_printer_print_str (prn, "\n");
 589   isl_printer_free (prn);
 590 }
 591
 592 DEBUG_FUNCTION void
 593 debug_isl_ast (isl_ast_node *n)
 594 {
 595   print_isl_ast (stderr, n);
 596 }
 597
 598 DEBUG_FUNCTION void
 599 debug_scop_pbb (scop_p scop, int i)
 600 {
 601   debug_pbb (scop->pbbs[i]);
 602 }
 603
 604 #endif  /* HAVE_isl */
 605