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"
49 #include "diagnostic-core.h"
53 #include "fold-const.h"
54 #include "gimple-iterator.h"
55 #include "tree-ssa-loop.h"
56 #include "gimple-pretty-print.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, at some VERBOSITY
76 print_iteration_domain (FILE *file
, poly_bb_p pbb
, int verbosity
)
78 print_pbb_domain (file
, pbb
, verbosity
);
81 /* Prints to FILE the iteration domains of every PBB of SCOP, at some
85 print_iteration_domains (FILE *file
, scop_p scop
, int verbosity
)
90 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
91 print_iteration_domain (file
, pbb
, verbosity
);
94 /* Prints to STDERR the iteration domain of PBB, at some VERBOSITY
98 debug_iteration_domain (poly_bb_p pbb
, int verbosity
)
100 print_iteration_domain (stderr
, pbb
, verbosity
);
103 /* Prints to STDERR the iteration domains of every PBB of SCOP, at
104 some VERBOSITY level. */
107 debug_iteration_domains (scop_p scop
, int verbosity
)
109 print_iteration_domains (stderr
, scop
, verbosity
);
112 /* Apply graphite transformations to all the basic blocks of SCOP. */
115 apply_poly_transforms (scop_p scop
)
117 bool transform_done
= false;
119 /* Generate code even if we did not apply any real transformation.
120 This also allows to check the performance for the identity
121 transformation: GIMPLE -> GRAPHITE -> GIMPLE. */
122 if (flag_graphite_identity
)
123 transform_done
= true;
125 if (flag_loop_parallelize_all
)
126 transform_done
= true;
128 if (flag_loop_optimize_isl
)
129 transform_done
|= optimize_isl (scop
);
131 return transform_done
;
134 /* Create a new polyhedral data reference and add it to PBB. It is
135 defined by its ACCESSES, its TYPE, and the number of subscripts
139 new_poly_dr (poly_bb_p pbb
, int dr_base_object_set
,
140 enum poly_dr_type type
, void *cdr
, graphite_dim_t nb_subscripts
,
141 isl_map
*acc
, isl_set
*subscript_sizes
)
144 poly_dr_p pdr
= XNEW (struct poly_dr
);
147 PDR_BASE_OBJECT_SET (pdr
) = dr_base_object_set
;
148 PDR_NB_REFS (pdr
) = 1;
151 pdr
->subscript_sizes
= subscript_sizes
;
152 PDR_TYPE (pdr
) = type
;
154 PDR_NB_SUBSCRIPTS (pdr
) = nb_subscripts
;
155 PBB_DRS (pbb
).safe_push (pdr
);
158 /* Free polyhedral data reference PDR. */
161 free_poly_dr (poly_dr_p pdr
)
163 isl_map_free (pdr
->accesses
);
164 isl_set_free (pdr
->subscript_sizes
);
168 /* Create a new polyhedral black box. */
171 new_poly_bb (scop_p scop
, void *black_box
)
173 poly_bb_p pbb
= XNEW (struct poly_bb
);
176 pbb
->schedule
= NULL
;
177 pbb
->transformed
= NULL
;
179 PBB_SCOP (pbb
) = scop
;
180 pbb_set_black_box (pbb
, black_box
);
181 PBB_DRS (pbb
).create (3);
182 PBB_IS_REDUCTION (pbb
) = false;
183 GBB_PBB ((gimple_poly_bb_p
) black_box
) = pbb
;
188 /* Free polyhedral black box. */
191 free_poly_bb (poly_bb_p pbb
)
196 isl_set_free (pbb
->domain
);
197 isl_map_free (pbb
->schedule
);
198 isl_map_free (pbb
->transformed
);
199 isl_map_free (pbb
->saved
);
201 if (PBB_DRS (pbb
).exists ())
202 FOR_EACH_VEC_ELT (PBB_DRS (pbb
), i
, pdr
)
205 PBB_DRS (pbb
).release ();
209 /* Prints to FILE the polyhedral data reference PDR, at some VERBOSITY
213 print_pdr (FILE *file
, poly_dr_p pdr
, int verbosity
)
217 fprintf (file
, "# pdr_%d (", PDR_ID (pdr
));
219 switch (PDR_TYPE (pdr
))
222 fprintf (file
, "read \n");
226 fprintf (file
, "write \n");
230 fprintf (file
, "may_write \n");
237 dump_data_reference (file
, (data_reference_p
) PDR_CDR (pdr
));
242 fprintf (file
, "# data accesses (\n");
243 print_isl_map (file
, pdr
->accesses
);
244 print_isl_set (file
, pdr
->subscript_sizes
);
245 fprintf (file
, "#)\n");
248 fprintf (file
, "#)\n");
251 /* Prints to STDERR the polyhedral data reference PDR, at some
255 debug_pdr (poly_dr_p pdr
, int verbosity
)
257 print_pdr (stderr
, pdr
, verbosity
);
260 /* Creates a new SCOP containing REGION. */
263 new_scop (sese region
)
265 scop_p scop
= XNEW (struct scop
);
267 scop
->context
= NULL
;
268 scop
->must_raw
= NULL
;
269 scop
->may_raw
= NULL
;
270 scop
->must_raw_no_source
= NULL
;
271 scop
->may_raw_no_source
= NULL
;
272 scop
->must_war
= NULL
;
273 scop
->may_war
= NULL
;
274 scop
->must_war_no_source
= NULL
;
275 scop
->may_war_no_source
= NULL
;
276 scop
->must_waw
= NULL
;
277 scop
->may_waw
= NULL
;
278 scop
->must_waw_no_source
= NULL
;
279 scop
->may_waw_no_source
= NULL
;
280 scop_set_region (scop
, region
);
281 SCOP_BBS (scop
).create (3);
282 POLY_SCOP_P (scop
) = false;
290 free_scop (scop_p scop
)
295 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
298 SCOP_BBS (scop
).release ();
300 isl_set_free (scop
->context
);
301 isl_union_map_free (scop
->must_raw
);
302 isl_union_map_free (scop
->may_raw
);
303 isl_union_map_free (scop
->must_raw_no_source
);
304 isl_union_map_free (scop
->may_raw_no_source
);
305 isl_union_map_free (scop
->must_war
);
306 isl_union_map_free (scop
->may_war
);
307 isl_union_map_free (scop
->must_war_no_source
);
308 isl_union_map_free (scop
->may_war_no_source
);
309 isl_union_map_free (scop
->must_waw
);
310 isl_union_map_free (scop
->may_waw
);
311 isl_union_map_free (scop
->must_waw_no_source
);
312 isl_union_map_free (scop
->may_waw_no_source
);
316 /* Print to FILE the domain of PBB, at some VERBOSITY level. */
319 print_pbb_domain (FILE *file
, poly_bb_p pbb
, int verbosity ATTRIBUTE_UNUSED
)
321 print_isl_set (file
, pbb
->domain
);
324 /* Dump the cases of a graphite basic block GBB on FILE. */
327 dump_gbb_cases (FILE *file
, gimple_poly_bb_p gbb
)
336 cases
= GBB_CONDITION_CASES (gbb
);
337 if (cases
.is_empty ())
340 fprintf (file
, "# cases bb_%d (\n", GBB_BB (gbb
)->index
);
342 FOR_EACH_VEC_ELT (cases
, i
, stmt
)
344 fprintf (file
, "# ");
345 print_gimple_stmt (file
, stmt
, 0, 0);
348 fprintf (file
, "#)\n");
351 /* Dump conditions of a graphite basic block GBB on FILE. */
354 dump_gbb_conditions (FILE *file
, gimple_poly_bb_p gbb
)
358 vec
<gimple
*> conditions
;
363 conditions
= GBB_CONDITIONS (gbb
);
364 if (conditions
.is_empty ())
367 fprintf (file
, "# conditions bb_%d (\n", GBB_BB (gbb
)->index
);
369 FOR_EACH_VEC_ELT (conditions
, i
, stmt
)
371 fprintf (file
, "# ");
372 print_gimple_stmt (file
, stmt
, 0, 0);
375 fprintf (file
, "#)\n");
378 /* Print to FILE all the data references of PBB, at some VERBOSITY
382 print_pdrs (FILE *file
, poly_bb_p pbb
, int verbosity
)
389 if (PBB_DRS (pbb
).length () == 0)
392 fprintf (file
, "# Access informations are not provided\n");\
393 fprintf (file
, "0\n");
398 fprintf (file
, "# Data references (\n");
401 fprintf (file
, "# Access informations are provided\n");
402 fprintf (file
, "1\n");
404 FOR_EACH_VEC_ELT (PBB_DRS (pbb
), i
, pdr
)
405 if (PDR_TYPE (pdr
) == PDR_READ
)
411 fprintf (file
, "# Read data references (\n");
414 fprintf (file
, "# Read access informations\n");
415 fprintf (file
, "%d\n", nb_reads
);
417 FOR_EACH_VEC_ELT (PBB_DRS (pbb
), i
, pdr
)
418 if (PDR_TYPE (pdr
) == PDR_READ
)
419 print_pdr (file
, pdr
, verbosity
);
422 fprintf (file
, "#)\n");
425 fprintf (file
, "# Write data references (\n");
428 fprintf (file
, "# Write access informations\n");
429 fprintf (file
, "%d\n", nb_writes
);
431 FOR_EACH_VEC_ELT (PBB_DRS (pbb
), i
, pdr
)
432 if (PDR_TYPE (pdr
) != PDR_READ
)
433 print_pdr (file
, pdr
, verbosity
);
436 fprintf (file
, "#)\n");
439 fprintf (file
, "#)\n");
442 /* Print to STDERR all the data references of PBB. */
445 debug_pdrs (poly_bb_p pbb
, int verbosity
)
447 print_pdrs (stderr
, pbb
, verbosity
);
450 /* Print to FILE the body of PBB, at some VERBOSITY level.
451 If statement_body_provided is false statement body is not printed. */
454 print_pbb_body (FILE *file
, poly_bb_p pbb
, int verbosity
,
455 bool statement_body_provided
)
458 fprintf (file
, "# Body (\n");
460 if (!statement_body_provided
)
463 fprintf (file
, "# Statement body is not provided\n");
465 fprintf (file
, "0\n");
468 fprintf (file
, "#)\n");
473 fprintf (file
, "# Statement body is provided\n");
474 fprintf (file
, "1\n");
477 fprintf (file
, "# Original iterator names\n# Iterator names are not provided yet.\n");
480 fprintf (file
, "# Statement body\n");
482 fprintf (file
, "{\n");
483 dump_bb (file
, pbb_bb (pbb
), 0, 0);
484 fprintf (file
, "}\n");
487 fprintf (file
, "#)\n");
490 /* Print to FILE the domain and scattering function of PBB, at some
494 print_pbb (FILE *file
, poly_bb_p pbb
, int verbosity
)
498 fprintf (file
, "# pbb_%d (\n", pbb_index (pbb
));
499 dump_gbb_conditions (file
, PBB_BLACK_BOX (pbb
));
500 dump_gbb_cases (file
, PBB_BLACK_BOX (pbb
));
503 print_pbb_domain (file
, pbb
, verbosity
);
504 print_pdrs (file
, pbb
, verbosity
);
505 print_pbb_body (file
, pbb
, verbosity
, false);
508 fprintf (file
, "#)\n");
511 /* Print to FILE the parameters of SCOP, at some VERBOSITY level. */
514 print_scop_params (FILE *file
, scop_p scop
, int verbosity
)
520 fprintf (file
, "# parameters (\n");
522 if (SESE_PARAMS (SCOP_REGION (scop
)).length ())
525 fprintf (file
, "# Parameter names are provided\n");
527 fprintf (file
, "1\n");
530 fprintf (file
, "# Parameter names\n");
535 fprintf (file
, "# Parameter names are not provided\n");
536 fprintf (file
, "0\n");
539 FOR_EACH_VEC_ELT (SESE_PARAMS (SCOP_REGION (scop
)), i
, t
)
541 print_generic_expr (file
, t
, 0);
545 fprintf (file
, "\n");
548 fprintf (file
, "#)\n");
551 /* Print to FILE the context of SCoP, at some VERBOSITY level. */
554 print_scop_context (FILE *file
, scop_p scop
, int verbosity
)
557 fprintf (file
, "# Context (\n");
560 print_isl_set (file
, scop
->context
);
563 fprintf (file
, "# )\n");
566 /* Print to FILE the SCOP, at some VERBOSITY level. */
569 print_scop (FILE *file
, scop_p scop
, int verbosity
)
574 fprintf (file
, "SCoP 1\n#(\n");
575 fprintf (file
, "# Language\nGimple\n");
576 print_scop_context (file
, scop
, verbosity
);
577 print_scop_params (file
, scop
, verbosity
);
580 fprintf (file
, "# Number of statements\n");
582 fprintf (file
, "%d\n", SCOP_BBS (scop
).length ());
584 FOR_EACH_VEC_ELT (SCOP_BBS (scop
), i
, pbb
)
585 print_pbb (file
, pbb
, verbosity
);
587 fprintf (file
, "#)\n");
590 /* Print to STDERR the domain of PBB, at some VERBOSITY level. */
593 debug_pbb_domain (poly_bb_p pbb
, int verbosity
)
595 print_pbb_domain (stderr
, pbb
, verbosity
);
598 /* Print to FILE the domain and scattering function of PBB, at some
602 debug_pbb (poly_bb_p pbb
, int verbosity
)
604 print_pbb (stderr
, pbb
, verbosity
);
607 /* Print to STDERR the context of SCOP, at some VERBOSITY level. */
610 debug_scop_context (scop_p scop
, int verbosity
)
612 print_scop_context (stderr
, scop
, verbosity
);
615 /* Print to STDERR the SCOP, at some VERBOSITY level. */
618 debug_scop (scop_p scop
, int verbosity
)
620 print_scop (stderr
, scop
, verbosity
);
623 /* Print to STDERR the parameters of SCOP, at some VERBOSITY
627 debug_scop_params (scop_p scop
, int verbosity
)
629 print_scop_params (stderr
, scop
, verbosity
);
632 extern isl_ctx
*the_isl_ctx
;
634 print_isl_set (FILE *f
, isl_set
*set
)
636 isl_printer
*p
= isl_printer_to_file (the_isl_ctx
, f
);
637 p
= isl_printer_print_set (p
, set
);
638 p
= isl_printer_print_str (p
, "\n");
639 isl_printer_free (p
);
643 debug_isl_set (isl_set
*set
)
645 print_isl_set (stderr
, set
);
649 print_isl_map (FILE *f
, isl_map
*map
)
651 isl_printer
*p
= isl_printer_to_file (the_isl_ctx
, f
);
652 p
= isl_printer_print_map (p
, map
);
653 p
= isl_printer_print_str (p
, "\n");
654 isl_printer_free (p
);
658 debug_isl_map (isl_map
*map
)
660 print_isl_map (stderr
, map
);
664 print_isl_aff (FILE *f
, isl_aff
*aff
)
666 isl_printer
*p
= isl_printer_to_file (the_isl_ctx
, f
);
667 p
= isl_printer_print_aff (p
, aff
);
668 p
= isl_printer_print_str (p
, "\n");
669 isl_printer_free (p
);
673 debug_isl_aff (isl_aff
*aff
)
675 print_isl_aff (stderr
, aff
);
679 print_isl_constraint (FILE *f
, isl_constraint
*c
)
681 isl_printer
*p
= isl_printer_to_file (the_isl_ctx
, f
);
682 p
= isl_printer_print_constraint (p
, c
);
683 p
= isl_printer_print_str (p
, "\n");
684 isl_printer_free (p
);
688 debug_isl_constraint (isl_constraint
*c
)
690 print_isl_constraint (stderr
, c
);
693 /* Returns the number of iterations RES of the loop around PBB at
694 time(scattering) dimension TIME_DEPTH. */
697 pbb_number_of_iterations_at_time (poly_bb_p pbb
,
698 graphite_dim_t time_depth
,
701 isl_set
*transdomain
;
704 isl_val
*isllb
, *islub
;
706 /* Map the iteration domain through the current scatter, and work
707 on the resulting set. */
708 transdomain
= isl_set_apply (isl_set_copy (pbb
->domain
),
709 isl_map_copy (pbb
->transformed
));
711 /* Select the time_depth' dimension via an affine expression. */
712 dc
= isl_set_get_space (transdomain
);
713 aff
= isl_aff_zero_on_domain (isl_local_space_from_space (dc
));
714 aff
= isl_aff_set_coefficient_si (aff
, isl_dim_in
, time_depth
, 1);
716 /* And find the min/max for that function. */
717 /* XXX isl check results? */
718 isllb
= isl_set_min_val (transdomain
, aff
);
719 islub
= isl_set_max_val (transdomain
, aff
);
721 islub
= isl_val_sub (islub
, isllb
);
722 islub
= isl_val_add_ui (islub
, 1);
723 isl_val_get_num_gmp (islub
, res
);
725 isl_val_free (islub
);
727 isl_set_free (transdomain
);
730 #endif /* HAVE_isl */