1/* Graphite polyhedral representation.
2 Copyright (C) 2009-2025 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <sebastian.pop@amd.com> and
4 Tobias Grosser <grosser@fim.uni-passau.de>.
5
6This file is part of GCC.
7
8GCC is free software; you can redistribute it and/or modify
9it under the terms of the GNU General Public License as published by
10the Free Software Foundation; either version 3, or (at your option)
11any later version.
12
13GCC is distributed in the hope that it will be useful,
14but WITHOUT ANY WARRANTY; without even the implied warranty of
15MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16GNU General Public License for more details.
17
18You should have received a copy of the GNU General Public License
19along 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
47DEBUG_FUNCTION void
48debug_gmp_value (mpz_t val)
49{
50 gmp_fprintf (stderr, "%Zd", val);
51}
52
53/* Prints to FILE the iteration domain of PBB. */
54
55void
56print_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
63void
64print_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
72DEBUG_FUNCTION void
73debug_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
80DEBUG_FUNCTION void
81debug_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
90void
91new_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
120static void
121free_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
130poly_bb_p
131new_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
147static void
148free_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
165void
166print_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
199DEBUG_FUNCTION void
200debug_pdr (poly_dr_p pdr)
201{
202 print_pdr (stderr, pdr);
203}
204
205/* Store the GRAPHITE representation of BB. */
206
207gimple_poly_bb_p
208new_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
224static void
225free_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
237static void
238remove_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
246scop_p
247new_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
264void
265free_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
289void
290print_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
297static void
298dump_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
319static void
320dump_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
341void
342print_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
365DEBUG_FUNCTION void
366debug_pdrs (poly_bb_p pbb)
367{
368 print_pdrs (stderr, pbb);
369}
370
371/* Print to FILE the body of PBB. */
372
373static void
374print_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
383void
384print_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
399void
400print_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
418void
419print_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
431void
432print_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
449DEBUG_FUNCTION void
450debug_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
457DEBUG_FUNCTION void
458debug_pbb (poly_bb_p pbb)
459{
460 print_pbb (stderr, pbb);
461}
462
463/* Print to STDERR the context of SCOP. */
464
465DEBUG_FUNCTION void
466debug_scop_context (scop_p scop)
467{
468 print_scop_context (stderr, scop);
469}
470
471/* Print to STDERR the SCOP. */
472
473DEBUG_FUNCTION void
474debug_scop (scop_p scop)
475{
476 print_scop (stderr, scop);
477}
478
479/* Print to STDERR the parameters of SCOP. */
480
481DEBUG_FUNCTION void
482debug_scop_params (scop_p scop)
483{
484 print_scop_params (stderr, scop);
485}
486
487extern isl_ctx *the_isl_ctx;
488void
489print_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
498DEBUG_FUNCTION void
499debug_isl_set (__isl_keep isl_set *set)
500{
501 print_isl_set (stderr, set);
502}
503
504void
505print_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
514DEBUG_FUNCTION void
515debug_isl_map (__isl_keep isl_map *map)
516{
517 print_isl_map (stderr, map);
518}
519
520void
521print_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
530DEBUG_FUNCTION void
531debug_isl_union_map (__isl_keep isl_union_map *map)
532{
533 print_isl_union_map (stderr, map);
534}
535
536void
537print_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
545DEBUG_FUNCTION void
546debug_isl_aff (__isl_keep isl_aff *aff)
547{
548 print_isl_aff (stderr, aff);
549}
550
551void
552print_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
560DEBUG_FUNCTION void
561debug_isl_constraint (__isl_keep isl_constraint *c)
562{
563 print_isl_constraint (stderr, c);
564}
565
566void
567print_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
576DEBUG_FUNCTION void
577debug_isl_schedule (__isl_keep isl_schedule *s)
578{
579 print_isl_schedule (stderr, s);
580}
581
582void
583print_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
592DEBUG_FUNCTION void
593debug_isl_ast (isl_ast_node *n)
594{
595 print_isl_ast (stderr, n);
596}
597
598DEBUG_FUNCTION void
599debug_scop_pbb (scop_p scop, int i)
600{
601 debug_pbb (scop->pbbs[i]);
602}
603
604#endif /* HAVE_isl */
605
606

source code of gcc/graphite-poly.cc