* g++.dg/cpp/ucn-1.C: Fix typo.
[official-gcc.git] / gcc / graphite-poly.c
blob809670ab3308901a141d20ccbb5695acdcf53f8d
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)
11 any later version.
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/>. */
22 #include "config.h"
24 #ifdef HAVE_isl
25 /* Workaround for GMP 5.1.3 bug, see PR56019. */
26 #include <stddef.h>
28 #include <isl/constraint.h>
29 #include <isl/set.h>
30 #include <isl/map.h>
31 #include <isl/union_map.h>
32 #include <isl/constraint.h>
33 #include <isl/ilp.h>
34 #include <isl/aff.h>
35 #include <isl/val.h>
37 /* Since ISL-0.13, the extern is in val_gmp.h. */
38 #if !defined(HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE) && defined(__cplusplus)
39 extern "C" {
40 #endif
41 #include <isl/val_gmp.h>
42 #if !defined(HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE) && defined(__cplusplus)
44 #endif
46 #include "system.h"
47 #include "coretypes.h"
48 #include "backend.h"
49 #include "tree.h"
50 #include "gimple.h"
51 #include "cfghooks.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"
57 #include "cfgloop.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. */
66 DEBUG_FUNCTION void
67 debug_gmp_value (mpz_t val)
69 gmp_fprintf (stderr, "%Zd", val);
72 /* Prints to FILE the iteration domain of PBB. */
74 void
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. */
82 void
83 print_iteration_domains (FILE *file, scop_p scop)
85 int i;
86 poly_bb_p pbb;
88 FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
89 print_iteration_domain (file, pbb);
92 /* Prints to STDERR the iteration domain of PBB. */
94 DEBUG_FUNCTION void
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. */
102 DEBUG_FUNCTION void
103 debug_iteration_domains (scop_p scop)
105 print_iteration_domains (stderr, scop);
108 /* Apply graphite transformations to all the basic blocks of SCOP. */
110 bool
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
132 NB_SUBSCRIPTS. */
134 void
135 new_poly_dr (poly_bb_p pbb, gimple *stmt, enum poly_dr_type type,
136 isl_map *acc, isl_set *subscript_sizes)
138 static int id = 0;
139 poly_dr_p pdr = XNEW (struct poly_dr);
141 pdr->stmt = stmt;
142 PDR_ID (pdr) = id++;
143 PDR_NB_REFS (pdr) = 1;
144 PDR_PBB (pdr) = pbb;
145 pdr->accesses = acc;
146 pdr->subscript_sizes = subscript_sizes;
147 PDR_TYPE (pdr) = type;
148 PBB_DRS (pbb).safe_push (pdr);
151 /* Free polyhedral data reference PDR. */
153 void
154 free_poly_dr (poly_dr_p pdr)
156 isl_map_free (pdr->accesses);
157 isl_set_free (pdr->subscript_sizes);
158 XDELETE (pdr);
161 /* Create a new polyhedral black box. */
163 poly_bb_p
164 new_poly_bb (scop_p scop, gimple_poly_bb_p black_box)
166 poly_bb_p pbb = XNEW (struct poly_bb);
168 pbb->domain = NULL;
169 pbb->schedule = NULL;
170 pbb->transformed = NULL;
171 pbb->saved = 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;
178 return pbb;
181 /* Free polyhedral black box. */
183 void
184 free_poly_bb (poly_bb_p pbb)
186 int i;
187 poly_dr_p pdr;
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)
196 free_poly_dr (pdr);
198 PBB_DRS (pbb).release ();
199 XDELETE (pbb);
202 /* Prints to FILE the polyhedral data reference PDR. */
204 void
205 print_pdr (FILE *file, poly_dr_p pdr)
207 fprintf (file, "pdr_%d (", PDR_ID (pdr));
209 switch (PDR_TYPE (pdr))
211 case PDR_READ:
212 fprintf (file, "read \n");
213 break;
215 case PDR_WRITE:
216 fprintf (file, "write \n");
217 break;
219 case PDR_MAY_WRITE:
220 fprintf (file, "may_write \n");
221 break;
223 default:
224 gcc_unreachable ();
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. */
238 DEBUG_FUNCTION void
239 debug_pdr (poly_dr_p pdr)
241 print_pdr (stderr, pdr);
244 /* Store the GRAPHITE representation of BB. */
246 gimple_poly_bb_p
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);
251 GBB_BB (gbb) = 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);
258 return gbb;
261 /* Frees GBB. */
263 void
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 ();
271 XDELETE (gbb);
274 /* Deletes all gimple bbs in SCOP. */
276 static void
277 remove_gbbs_in_scop (scop_p scop)
279 int i;
280 poly_bb_p pbb;
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). */
288 scop_p
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);
313 return scop;
316 /* Deletes SCOP. */
318 void
319 free_scop (scop_p scop)
321 int i;
322 poly_bb_p pbb;
324 remove_gbbs_in_scop (scop);
325 free_sese_info (scop->scop_info);
327 FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
328 free_poly_bb (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);
347 XDELETE (scop);
350 /* Print to FILE the domain of PBB. */
352 void
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. */
360 static void
361 dump_gbb_cases (FILE *file, gimple_poly_bb_p gbb)
363 int i;
364 gimple *stmt;
365 vec<gimple *> cases;
367 if (!gbb)
368 return;
370 cases = GBB_CONDITION_CASES (gbb);
371 if (cases.is_empty ())
372 return;
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. */
384 static void
385 dump_gbb_conditions (FILE *file, gimple_poly_bb_p gbb)
387 int i;
388 gimple *stmt;
389 vec<gimple *> conditions;
391 if (!gbb)
392 return;
394 conditions = GBB_CONDITIONS (gbb);
395 if (conditions.is_empty ())
396 return;
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. */
408 void
409 print_pdrs (FILE *file, poly_bb_p pbb)
411 int i;
412 poly_dr_p pdr;
413 int nb_reads = 0;
414 int nb_writes = 0;
416 if (PBB_DRS (pbb).is_empty ())
417 return;
419 fprintf (file, "Data references (\n");
421 FOR_EACH_VEC_ELT (PBB_DRS (pbb), i, pdr)
422 if (PDR_TYPE (pdr) == PDR_READ)
423 nb_reads++;
424 else
425 nb_writes++;
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. */
444 DEBUG_FUNCTION void
445 debug_pdrs (poly_bb_p pbb)
447 print_pdrs (stderr, pbb);
450 /* Print to FILE the body of PBB. */
452 static void
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. */
462 void
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. */
478 void
479 print_scop_params (FILE *file, scop_p scop)
481 if (scop->scop_info->params.is_empty ())
482 return;
484 int i;
485 tree t;
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. */
497 void
498 print_scop_context (FILE *file, scop_p scop)
500 if (!scop->param_context)
501 return;
503 fprintf (file, "Context (\n");
504 print_isl_set (file, scop->param_context);
505 fprintf (file, ")\n");
508 /* Print to FILE the SCOP. */
510 void
511 print_scop (FILE *file, scop_p scop)
513 int i;
514 poly_bb_p pbb;
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. */
531 DEBUG_FUNCTION void
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. */
539 DEBUG_FUNCTION void
540 debug_pbb (poly_bb_p pbb)
542 print_pbb (stderr, pbb);
545 /* Print to STDERR the context of SCOP. */
547 DEBUG_FUNCTION void
548 debug_scop_context (scop_p scop)
550 print_scop_context (stderr, scop);
553 /* Print to STDERR the SCOP. */
555 DEBUG_FUNCTION void
556 debug_scop (scop_p scop)
558 print_scop (stderr, scop);
561 /* Print to STDERR the parameters of SCOP. */
563 DEBUG_FUNCTION void
564 debug_scop_params (scop_p scop)
566 print_scop_params (stderr, scop);
569 extern isl_ctx *the_isl_ctx;
570 void
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);
579 DEBUG_FUNCTION void
580 debug_isl_set (isl_set *set)
582 print_isl_set (stderr, set);
585 void
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);
594 DEBUG_FUNCTION void
595 debug_isl_map (isl_map *map)
597 print_isl_map (stderr, map);
600 void
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);
609 DEBUG_FUNCTION void
610 debug_isl_union_map (isl_union_map *map)
612 print_isl_union_map (stderr, map);
616 void
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);
625 DEBUG_FUNCTION void
626 debug_isl_aff (isl_aff *aff)
628 print_isl_aff (stderr, aff);
631 void
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);
640 DEBUG_FUNCTION void
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. */
649 void
650 pbb_number_of_iterations_at_time (poly_bb_p pbb,
651 graphite_dim_t time_depth,
652 mpz_t res)
654 isl_set *transdomain;
655 isl_space *dc;
656 isl_aff *aff;
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);
679 isl_aff_free (aff);
680 isl_set_free (transdomain);
683 #endif /* HAVE_isl */