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