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>.
6 This file is part of GCC.
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)
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.
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/>. */
25 /* Workaround for GMP 5.1.3 bug, see PR56019. */
28 #include <isl/constraint.h>
31 #include <isl/union_map.h>
32 #include <isl/constraint.h>
37 /* Since ISL-0.13, the extern is in val_gmp.h. */
38 #if !defined(HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE) && defined(__cplusplus)
41 #include <isl/val_gmp.h>
42 #if !defined(HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE) && defined(__cplusplus)
47 #include "coretypes.h"
52 #include "gimple-pretty-print.h"
53 #include "diagnostic-core.h"
54 #include "fold-const.h"
55 #include "gimple-iterator.h"
56 #include "tree-ssa-loop.h"
58 #include "tree-data-ref.h"
59 #include "graphite-poly.h"
61 #define OPENSCOP_MAX_STRING 256
64 /* Print to STDERR the GMP value VAL. */
67 debug_gmp_value (mpz_t val
)
69 gmp_fprintf (stderr
, "%Zd", val
);
72 /* Prints to FILE the iteration domain of PBB. */
75 print_iteration_domain (FILE *file
, poly_bb_p pbb
)
77 print_pbb_domain (file
, pbb
);
80 /* Prints to FILE the iteration domains of every PBB of SCOP. */
83 print_iteration_domains (FILE *file
, scop_p scop
)
88 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
89 print_iteration_domain (file
, pbb
);
92 /* Prints to STDERR the iteration domain of PBB. */
95 debug_iteration_domain (poly_bb_p pbb
)
97 print_iteration_domain (stderr
, pbb
);
100 /* Prints to STDERR the iteration domains of every PBB of SCOP. */
103 debug_iteration_domains (scop_p scop
)
105 print_iteration_domains (stderr
, scop
);
108 /* Apply graphite transformations to all the basic blocks of SCOP. */
111 apply_poly_transforms (scop_p scop
)
113 bool transform_done
= false;
115 /* Generate code even if we did not apply any real transformation.
116 This also allows to check the performance for the identity
117 transformation: GIMPLE -> GRAPHITE -> GIMPLE. */
118 if (flag_graphite_identity
)
119 transform_done
= true;
121 if (flag_loop_parallelize_all
)
122 transform_done
= true;
124 if (flag_loop_optimize_isl
)
125 transform_done
|= optimize_isl (scop
);
127 return transform_done
;
130 /* Create a new polyhedral data reference and add it to PBB. It is
131 defined by its ACCESSES, its TYPE, and the number of subscripts
135 new_poly_dr (poly_bb_p pbb
, gimple
*stmt
, enum poly_dr_type type
,
136 isl_map
*acc
, isl_set
*subscript_sizes
)
139 poly_dr_p pdr
= XNEW (struct poly_dr
);
143 PDR_NB_REFS (pdr
) = 1;
146 pdr
->subscript_sizes
= subscript_sizes
;
147 PDR_TYPE (pdr
) = type
;
148 PBB_DRS (pbb
).safe_push (pdr
);
151 /* Free polyhedral data reference PDR. */
154 free_poly_dr (poly_dr_p pdr
)
156 isl_map_free (pdr
->accesses
);
157 isl_set_free (pdr
->subscript_sizes
);
161 /* Create a new polyhedral black box. */
164 new_poly_bb (scop_p scop
, gimple_poly_bb_p black_box
)
166 poly_bb_p pbb
= XNEW (struct poly_bb
);
169 pbb
->schedule
= NULL
;
170 pbb
->transformed
= NULL
;
172 PBB_SCOP (pbb
) = scop
;
173 pbb_set_black_box (pbb
, black_box
);
174 PBB_DRS (pbb
).create (3);
175 PBB_IS_REDUCTION (pbb
) = false;
176 GBB_PBB ((gimple_poly_bb_p
) black_box
) = pbb
;
181 /* Free polyhedral black box. */
184 free_poly_bb (poly_bb_p pbb
)
189 isl_set_free (pbb
->domain
);
190 isl_map_free (pbb
->schedule
);
191 isl_map_free (pbb
->transformed
);
192 isl_map_free (pbb
->saved
);
194 if (PBB_DRS (pbb
).exists ())
195 FOR_EACH_VEC_ELT (PBB_DRS (pbb
), i
, pdr
)
198 PBB_DRS (pbb
).release ();
202 /* Prints to FILE the polyhedral data reference PDR. */
205 print_pdr (FILE *file
, poly_dr_p pdr
)
207 fprintf (file
, "pdr_%d (", PDR_ID (pdr
));
209 switch (PDR_TYPE (pdr
))
212 fprintf (file
, "read \n");
216 fprintf (file
, "write \n");
220 fprintf (file
, "may_write \n");
227 fprintf (file
, "in gimple stmt: ");
228 print_gimple_stmt (file
, pdr
->stmt
, 0, 0);
229 fprintf (file
, "data accesses: ");
230 print_isl_map (file
, pdr
->accesses
);
231 fprintf (file
, "subscript sizes: ");
232 print_isl_set (file
, pdr
->subscript_sizes
);
233 fprintf (file
, ")\n");
236 /* Prints to STDERR the polyhedral data reference PDR. */
239 debug_pdr (poly_dr_p pdr
)
241 print_pdr (stderr
, pdr
);
244 /* Store the GRAPHITE representation of BB. */
247 new_gimple_poly_bb (basic_block bb
, vec
<data_reference_p
> drs
,
248 vec
<scalar_use
> reads
, vec
<tree
> writes
)
250 gimple_poly_bb_p gbb
= XNEW (struct gimple_poly_bb
);
252 GBB_DATA_REFS (gbb
) = drs
;
253 gbb
->read_scalar_refs
= reads
;
254 gbb
->write_scalar_refs
= writes
;
255 GBB_CONDITIONS (gbb
).create (0);
256 GBB_CONDITION_CASES (gbb
).create (0);
264 free_gimple_poly_bb (gimple_poly_bb_p gbb
)
266 free_data_refs (GBB_DATA_REFS (gbb
));
267 GBB_CONDITIONS (gbb
).release ();
268 GBB_CONDITION_CASES (gbb
).release ();
269 gbb
->read_scalar_refs
.release ();
270 gbb
->write_scalar_refs
.release ();
274 /* Deletes all gimple bbs in SCOP. */
277 remove_gbbs_in_scop (scop_p scop
)
282 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
283 free_gimple_poly_bb (PBB_BLACK_BOX (pbb
));
286 /* Creates a new SCOP containing the region (ENTRY, EXIT). */
289 new_scop (edge entry
, edge exit
)
291 sese_info_p region
= new_sese_info (entry
, exit
);
292 scop_p scop
= XNEW (struct scop
);
294 scop
->param_context
= NULL
;
295 scop
->must_raw
= NULL
;
296 scop
->may_raw
= NULL
;
297 scop
->must_raw_no_source
= NULL
;
298 scop
->may_raw_no_source
= NULL
;
299 scop
->must_war
= NULL
;
300 scop
->may_war
= NULL
;
301 scop
->must_war_no_source
= NULL
;
302 scop
->may_war_no_source
= NULL
;
303 scop
->must_waw
= NULL
;
304 scop
->may_waw
= NULL
;
305 scop
->must_waw_no_source
= NULL
;
306 scop
->may_waw_no_source
= NULL
;
307 scop_set_region (scop
, region
);
308 scop
->original_schedule
= NULL
;
309 scop
->pbbs
.create (3);
310 scop
->poly_scop_p
= false;
311 scop
->drs
.create (3);
319 free_scop (scop_p scop
)
324 remove_gbbs_in_scop (scop
);
325 free_sese_info (scop
->scop_info
);
327 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
330 scop
->pbbs
.release ();
331 scop
->drs
.release ();
333 isl_set_free (scop
->param_context
);
334 isl_union_map_free (scop
->must_raw
);
335 isl_union_map_free (scop
->may_raw
);
336 isl_union_map_free (scop
->must_raw_no_source
);
337 isl_union_map_free (scop
->may_raw_no_source
);
338 isl_union_map_free (scop
->must_war
);
339 isl_union_map_free (scop
->may_war
);
340 isl_union_map_free (scop
->must_war_no_source
);
341 isl_union_map_free (scop
->may_war_no_source
);
342 isl_union_map_free (scop
->must_waw
);
343 isl_union_map_free (scop
->may_waw
);
344 isl_union_map_free (scop
->must_waw_no_source
);
345 isl_union_map_free (scop
->may_waw_no_source
);
346 isl_union_map_free (scop
->original_schedule
);
350 /* Print to FILE the domain of PBB. */
353 print_pbb_domain (FILE *file
, poly_bb_p pbb
)
355 print_isl_set (file
, pbb
->domain
);
358 /* Dump the cases of a graphite basic block GBB on FILE. */
361 dump_gbb_cases (FILE *file
, gimple_poly_bb_p gbb
)
370 cases
= GBB_CONDITION_CASES (gbb
);
371 if (cases
.is_empty ())
374 fprintf (file
, "cases bb_%d (\n", GBB_BB (gbb
)->index
);
376 FOR_EACH_VEC_ELT (cases
, i
, stmt
)
377 print_gimple_stmt (file
, stmt
, 0, 0);
379 fprintf (file
, ")\n");
382 /* Dump conditions of a graphite basic block GBB on FILE. */
385 dump_gbb_conditions (FILE *file
, gimple_poly_bb_p gbb
)
389 vec
<gimple
*> conditions
;
394 conditions
= GBB_CONDITIONS (gbb
);
395 if (conditions
.is_empty ())
398 fprintf (file
, "conditions bb_%d (\n", GBB_BB (gbb
)->index
);
400 FOR_EACH_VEC_ELT (conditions
, i
, stmt
)
401 print_gimple_stmt (file
, stmt
, 0, 0);
403 fprintf (file
, ")\n");
406 /* Print to FILE all the data references of PBB. */
409 print_pdrs (FILE *file
, poly_bb_p pbb
)
416 if (PBB_DRS (pbb
).is_empty ())
419 fprintf (file
, "Data references (\n");
421 FOR_EACH_VEC_ELT (PBB_DRS (pbb
), i
, pdr
)
422 if (PDR_TYPE (pdr
) == PDR_READ
)
427 fprintf (file
, "Read data references (\n");
429 FOR_EACH_VEC_ELT (PBB_DRS (pbb
), i
, pdr
)
430 if (PDR_TYPE (pdr
) == PDR_READ
)
431 print_pdr (file
, pdr
);
433 fprintf (file
, ")\n");
434 fprintf (file
, "Write data references (\n");
435 FOR_EACH_VEC_ELT (PBB_DRS (pbb
), i
, pdr
)
436 if (PDR_TYPE (pdr
) != PDR_READ
)
437 print_pdr (file
, pdr
);
438 fprintf (file
, ")\n");
439 fprintf (file
, ")\n");
442 /* Print to STDERR all the data references of PBB. */
445 debug_pdrs (poly_bb_p pbb
)
447 print_pdrs (stderr
, pbb
);
450 /* Print to FILE the body of PBB. */
453 print_pbb_body (FILE *file
, poly_bb_p pbb
)
455 fprintf (file
, "Body (\n");
456 dump_bb (file
, pbb_bb (pbb
), 0, 0);
457 fprintf (file
, ")\n");
460 /* Print to FILE the domain and scattering function of PBB. */
463 print_pbb (FILE *file
, poly_bb_p pbb
)
465 fprintf (file
, "pbb_%d (\n", pbb_index (pbb
));
466 dump_gbb_conditions (file
, PBB_BLACK_BOX (pbb
));
467 dump_gbb_cases (file
, PBB_BLACK_BOX (pbb
));
469 print_pbb_domain (file
, pbb
);
470 print_pdrs (file
, pbb
);
471 print_pbb_body (file
, pbb
);
473 fprintf (file
, ")\n");
476 /* Print to FILE the parameters of SCOP. */
479 print_scop_params (FILE *file
, scop_p scop
)
481 if (scop
->scop_info
->params
.is_empty ())
486 fprintf (file
, "parameters (");
487 FOR_EACH_VEC_ELT (scop
->scop_info
->params
, i
, t
)
489 print_generic_expr (file
, t
, 0);
490 fprintf (file
, ", ");
492 fprintf (file
, ")\n");
495 /* Print to FILE the context of SCoP. */
498 print_scop_context (FILE *file
, scop_p scop
)
500 if (!scop
->param_context
)
503 fprintf (file
, "Context (\n");
504 print_isl_set (file
, scop
->param_context
);
505 fprintf (file
, ")\n");
508 /* Print to FILE the SCOP. */
511 print_scop (FILE *file
, scop_p scop
)
516 fprintf (file
, "SCoP (\n");
517 print_scop_context (file
, scop
);
518 print_scop_params (file
, scop
);
520 fprintf (file
, "Number of statements: ");
521 fprintf (file
, "%d\n", scop
->pbbs
.length ());
523 FOR_EACH_VEC_ELT (scop
->pbbs
, i
, pbb
)
524 print_pbb (file
, pbb
);
526 fprintf (file
, ")\n");
529 /* Print to STDERR the domain of PBB. */
532 debug_pbb_domain (poly_bb_p pbb
)
534 print_pbb_domain (stderr
, pbb
);
537 /* Print to FILE the domain and scattering function of PBB. */
540 debug_pbb (poly_bb_p pbb
)
542 print_pbb (stderr
, pbb
);
545 /* Print to STDERR the context of SCOP. */
548 debug_scop_context (scop_p scop
)
550 print_scop_context (stderr
, scop
);
553 /* Print to STDERR the SCOP. */
556 debug_scop (scop_p scop
)
558 print_scop (stderr
, scop
);
561 /* Print to STDERR the parameters of SCOP. */
564 debug_scop_params (scop_p scop
)
566 print_scop_params (stderr
, scop
);
569 extern isl_ctx
*the_isl_ctx
;
571 print_isl_set (FILE *f
, isl_set
*set
)
573 isl_printer
*p
= isl_printer_to_file (the_isl_ctx
, f
);
574 p
= isl_printer_print_set (p
, set
);
575 p
= isl_printer_print_str (p
, "\n");
576 isl_printer_free (p
);
580 debug_isl_set (isl_set
*set
)
582 print_isl_set (stderr
, set
);
586 print_isl_map (FILE *f
, isl_map
*map
)
588 isl_printer
*p
= isl_printer_to_file (the_isl_ctx
, f
);
589 p
= isl_printer_print_map (p
, map
);
590 p
= isl_printer_print_str (p
, "\n");
591 isl_printer_free (p
);
595 debug_isl_map (isl_map
*map
)
597 print_isl_map (stderr
, map
);
601 print_isl_union_map (FILE *f
, isl_union_map
*map
)
603 isl_printer
*p
= isl_printer_to_file (the_isl_ctx
, f
);
604 p
= isl_printer_print_union_map (p
, map
);
605 p
= isl_printer_print_str (p
, "\n");
606 isl_printer_free (p
);
610 debug_isl_union_map (isl_union_map
*map
)
612 print_isl_union_map (stderr
, map
);
617 print_isl_aff (FILE *f
, isl_aff
*aff
)
619 isl_printer
*p
= isl_printer_to_file (the_isl_ctx
, f
);
620 p
= isl_printer_print_aff (p
, aff
);
621 p
= isl_printer_print_str (p
, "\n");
622 isl_printer_free (p
);
626 debug_isl_aff (isl_aff
*aff
)
628 print_isl_aff (stderr
, aff
);
632 print_isl_constraint (FILE *f
, isl_constraint
*c
)
634 isl_printer
*p
= isl_printer_to_file (the_isl_ctx
, f
);
635 p
= isl_printer_print_constraint (p
, c
);
636 p
= isl_printer_print_str (p
, "\n");
637 isl_printer_free (p
);
641 debug_isl_constraint (isl_constraint
*c
)
643 print_isl_constraint (stderr
, c
);
646 /* Returns the number of iterations RES of the loop around PBB at
647 time(scattering) dimension TIME_DEPTH. */
650 pbb_number_of_iterations_at_time (poly_bb_p pbb
,
651 graphite_dim_t time_depth
,
654 isl_set
*transdomain
;
657 isl_val
*isllb
, *islub
;
659 /* Map the iteration domain through the current scatter, and work
660 on the resulting set. */
661 transdomain
= isl_set_apply (isl_set_copy (pbb
->domain
),
662 isl_map_copy (pbb
->transformed
));
664 /* Select the time_depth' dimension via an affine expression. */
665 dc
= isl_set_get_space (transdomain
);
666 aff
= isl_aff_zero_on_domain (isl_local_space_from_space (dc
));
667 aff
= isl_aff_set_coefficient_si (aff
, isl_dim_in
, time_depth
, 1);
669 /* And find the min/max for that function. */
670 /* XXX isl check results? */
671 isllb
= isl_set_min_val (transdomain
, aff
);
672 islub
= isl_set_max_val (transdomain
, aff
);
674 islub
= isl_val_sub (islub
, isllb
);
675 islub
= isl_val_add_ui (islub
, 1);
676 isl_val_get_num_gmp (islub
, res
);
678 isl_val_free (islub
);
680 isl_set_free (transdomain
);
683 #endif /* HAVE_isl */