gcc/
[official-gcc.git] / gcc / graphite-poly.c
blob1d52be59b2f8d4e99be7f89903986abdc7aa2a09
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 #include <isl/set.h>
26 #include <isl/map.h>
27 #include <isl/union_map.h>
28 #include <isl/constraint.h>
29 #include <isl/ilp.h>
30 #include <isl/aff.h>
31 #include <isl/val.h>
33 /* Since ISL-0.13, the extern is in val_gmp.h. */
34 #if !defined(HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE) && defined(__cplusplus)
35 extern "C" {
36 #endif
37 #include <isl/val_gmp.h>
38 #if !defined(HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE) && defined(__cplusplus)
40 #endif
41 #endif
43 #include "system.h"
44 #include "coretypes.h"
45 #include "diagnostic-core.h"
46 #include "alias.h"
47 #include "symtab.h"
48 #include "options.h"
49 #include "tree.h"
50 #include "fold-const.h"
51 #include "predict.h"
52 #include "tm.h"
53 #include "hard-reg-set.h"
54 #include "function.h"
55 #include "dominance.h"
56 #include "cfg.h"
57 #include "basic-block.h"
58 #include "tree-ssa-alias.h"
59 #include "internal-fn.h"
60 #include "gimple-expr.h"
61 #include "gimple.h"
62 #include "gimple-iterator.h"
63 #include "tree-ssa-loop.h"
64 #include "dumpfile.h"
65 #include "gimple-pretty-print.h"
66 #include "cfgloop.h"
67 #include "tree-chrec.h"
68 #include "tree-data-ref.h"
69 #include "tree-scalar-evolution.h"
70 #include "sese.h"
72 #ifdef HAVE_isl
73 #include "graphite-poly.h"
75 #define OPENSCOP_MAX_STRING 256
78 /* Print to STDERR the GMP value VAL. */
80 DEBUG_FUNCTION void
81 debug_gmp_value (mpz_t val)
83 gmp_fprintf (stderr, "%Zd", val);
86 /* Return the maximal loop depth in SCOP. */
88 int
89 scop_max_loop_depth (scop_p scop)
91 int i;
92 poly_bb_p pbb;
93 int max_nb_loops = 0;
95 FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb)
97 int nb_loops = pbb_dim_iter_domain (pbb);
98 if (max_nb_loops < nb_loops)
99 max_nb_loops = nb_loops;
102 return max_nb_loops;
105 /* Prints to FILE the scattering function of PBB, at some VERBOSITY
106 level. */
108 static void
109 print_scattering_function_1 (FILE *file, poly_bb_p pbb, int verbosity)
111 graphite_dim_t i;
113 if (verbosity > 0)
115 fprintf (file, "# scattering bb_%d (\n", pbb_index (pbb));
116 fprintf (file, "#eq");
118 for (i = 0; i < pbb_nb_scattering_transform (pbb); i++)
119 fprintf (file, " s%d", (int) i);
121 for (i = 0; i < pbb_nb_local_vars (pbb); i++)
122 fprintf (file, " lv%d", (int) i);
124 for (i = 0; i < pbb_dim_iter_domain (pbb); i++)
125 fprintf (file, " i%d", (int) i);
127 for (i = 0; i < pbb_nb_params (pbb); i++)
128 fprintf (file, " p%d", (int) i);
130 fprintf (file, " cst\n");
133 fprintf (file, "isl\n");
134 print_isl_map (file, pbb->transformed ? pbb->transformed : pbb->schedule);
136 if (verbosity > 0)
137 fprintf (file, "#)\n");
140 /* Prints to FILE the scattering function of PBB, at some VERBOSITY
141 level. */
143 void
144 print_scattering_function (FILE *file, poly_bb_p pbb, int verbosity)
146 if (!PBB_TRANSFORMED (pbb))
147 return;
149 if (pbb->schedule || pbb->transformed)
151 if (verbosity > 0)
152 fprintf (file, "# Scattering function is provided\n");
154 fprintf (file, "1\n");
156 else
158 if (verbosity > 0)
159 fprintf (file, "# Scattering function is not provided\n");
161 fprintf (file, "0\n");
162 return;
165 print_scattering_function_1 (file, pbb, verbosity);
167 if (verbosity > 0)
168 fprintf (file, "# Scattering names are not provided\n");
170 fprintf (file, "0\n");
174 /* Prints to FILE the iteration domain of PBB, at some VERBOSITY
175 level. */
177 void
178 print_iteration_domain (FILE *file, poly_bb_p pbb, int verbosity)
180 print_pbb_domain (file, pbb, verbosity);
183 /* Prints to FILE the scattering functions of every PBB of SCOP. */
185 void
186 print_scattering_functions (FILE *file, scop_p scop, int verbosity)
188 int i;
189 poly_bb_p pbb;
191 FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb)
192 print_scattering_function (file, pbb, verbosity);
195 /* Prints to FILE the iteration domains of every PBB of SCOP, at some
196 VERBOSITY level. */
198 void
199 print_iteration_domains (FILE *file, scop_p scop, int verbosity)
201 int i;
202 poly_bb_p pbb;
204 FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb)
205 print_iteration_domain (file, pbb, verbosity);
208 /* Prints to STDERR the scattering function of PBB, at some VERBOSITY
209 level. */
211 DEBUG_FUNCTION void
212 debug_scattering_function (poly_bb_p pbb, int verbosity)
214 print_scattering_function (stderr, pbb, verbosity);
217 /* Prints to STDERR the iteration domain of PBB, at some VERBOSITY
218 level. */
220 DEBUG_FUNCTION void
221 debug_iteration_domain (poly_bb_p pbb, int verbosity)
223 print_iteration_domain (stderr, pbb, verbosity);
226 /* Prints to STDERR the scattering functions of every PBB of SCOP, at
227 some VERBOSITY level. */
229 DEBUG_FUNCTION void
230 debug_scattering_functions (scop_p scop, int verbosity)
232 print_scattering_functions (stderr, scop, verbosity);
235 /* Prints to STDERR the iteration domains of every PBB of SCOP, at
236 some VERBOSITY level. */
238 DEBUG_FUNCTION void
239 debug_iteration_domains (scop_p scop, int verbosity)
241 print_iteration_domains (stderr, scop, verbosity);
244 /* Apply graphite transformations to all the basic blocks of SCOP. */
246 bool
247 apply_poly_transforms (scop_p scop)
249 bool transform_done = false;
251 /* Generate code even if we did not apply any real transformation.
252 This also allows to check the performance for the identity
253 transformation: GIMPLE -> GRAPHITE -> GIMPLE
254 Keep in mind that CLooG optimizes in control, so the loop structure
255 may change, even if we only use -fgraphite-identity. */
256 if (flag_graphite_identity)
257 transform_done = true;
259 if (flag_loop_parallelize_all)
260 transform_done = true;
262 if (flag_loop_block)
263 transform_done |= scop_do_block (scop);
264 else
266 if (flag_loop_strip_mine)
267 transform_done |= scop_do_strip_mine (scop, 0);
269 if (flag_loop_interchange)
270 transform_done |= scop_do_interchange (scop);
273 /* This pass needs to be run at the final stage, as it does not
274 update the lst. */
275 if (flag_loop_optimize_isl || flag_loop_unroll_jam)
276 transform_done |= optimize_isl (scop);
278 return transform_done;
281 /* Create a new polyhedral data reference and add it to PBB. It is
282 defined by its ACCESSES, its TYPE, and the number of subscripts
283 NB_SUBSCRIPTS. */
285 void
286 new_poly_dr (poly_bb_p pbb, int dr_base_object_set,
287 enum poly_dr_type type, void *cdr, graphite_dim_t nb_subscripts,
288 isl_map *acc, isl_set *extent)
290 static int id = 0;
291 poly_dr_p pdr = XNEW (struct poly_dr);
293 PDR_ID (pdr) = id++;
294 PDR_BASE_OBJECT_SET (pdr) = dr_base_object_set;
295 PDR_NB_REFS (pdr) = 1;
296 PDR_PBB (pdr) = pbb;
297 pdr->accesses = acc;
298 pdr->extent = extent;
299 PDR_TYPE (pdr) = type;
300 PDR_CDR (pdr) = cdr;
301 PDR_NB_SUBSCRIPTS (pdr) = nb_subscripts;
302 PBB_DRS (pbb).safe_push (pdr);
305 /* Free polyhedral data reference PDR. */
307 void
308 free_poly_dr (poly_dr_p pdr)
310 isl_map_free (pdr->accesses);
311 isl_set_free (pdr->extent);
312 XDELETE (pdr);
315 /* Create a new polyhedral black box. */
317 poly_bb_p
318 new_poly_bb (scop_p scop, void *black_box)
320 poly_bb_p pbb = XNEW (struct poly_bb);
322 pbb->domain = NULL;
323 pbb->schedule = NULL;
324 pbb->transformed = NULL;
325 pbb->saved = NULL;
326 pbb->map_sepclass = NULL;
327 PBB_SCOP (pbb) = scop;
328 pbb_set_black_box (pbb, black_box);
329 PBB_TRANSFORMED (pbb) = NULL;
330 PBB_SAVED (pbb) = NULL;
331 PBB_ORIGINAL (pbb) = NULL;
332 PBB_DRS (pbb).create (3);
333 PBB_IS_REDUCTION (pbb) = false;
334 GBB_PBB ((gimple_bb_p) black_box) = pbb;
336 return pbb;
339 /* Free polyhedral black box. */
341 void
342 free_poly_bb (poly_bb_p pbb)
344 int i;
345 poly_dr_p pdr;
347 isl_set_free (pbb->domain);
348 isl_map_free (pbb->schedule);
349 isl_map_free (pbb->transformed);
350 isl_map_free (pbb->saved);
352 if (PBB_DRS (pbb).exists ())
353 FOR_EACH_VEC_ELT (PBB_DRS (pbb), i, pdr)
354 free_poly_dr (pdr);
356 PBB_DRS (pbb).release ();
357 XDELETE (pbb);
360 static void
361 print_pdr_access_layout (FILE *file, poly_bb_p pbb, poly_dr_p pdr)
363 graphite_dim_t i;
365 fprintf (file, "# eq");
367 fprintf (file, " alias");
369 for (i = 0; i < PDR_NB_SUBSCRIPTS (pdr); i++)
370 fprintf (file, " sub%d", (int) i);
372 for (i = 0; i < pbb_dim_iter_domain (pbb); i++)
373 fprintf (file, " i%d", (int) i);
375 for (i = 0; i < pbb_nb_params (pbb); i++)
376 fprintf (file, " p%d", (int) i);
378 fprintf (file, " cst\n");
381 /* Prints to FILE the polyhedral data reference PDR, at some VERBOSITY
382 level. */
384 void
385 print_pdr (FILE *file, poly_dr_p pdr, int verbosity)
387 if (verbosity > 1)
389 fprintf (file, "# pdr_%d (", PDR_ID (pdr));
391 switch (PDR_TYPE (pdr))
393 case PDR_READ:
394 fprintf (file, "read \n");
395 break;
397 case PDR_WRITE:
398 fprintf (file, "write \n");
399 break;
401 case PDR_MAY_WRITE:
402 fprintf (file, "may_write \n");
403 break;
405 default:
406 gcc_unreachable ();
409 dump_data_reference (file, (data_reference_p) PDR_CDR (pdr));
412 if (verbosity > 0)
414 fprintf (file, "# data accesses (\n");
415 print_pdr_access_layout (file, PDR_PBB (pdr), pdr);
418 /* XXX isl dump accesses/subscripts */
420 if (verbosity > 0)
421 fprintf (file, "#)\n");
423 if (verbosity > 1)
424 fprintf (file, "#)\n");
427 /* Prints to STDERR the polyhedral data reference PDR, at some
428 VERBOSITY level. */
430 DEBUG_FUNCTION void
431 debug_pdr (poly_dr_p pdr, int verbosity)
433 print_pdr (stderr, pdr, verbosity);
436 /* Creates a new SCOP containing REGION. */
438 scop_p
439 new_scop (void *region)
441 scop_p scop = XNEW (struct scop);
443 scop->context = NULL;
444 scop->must_raw = NULL;
445 scop->may_raw = NULL;
446 scop->must_raw_no_source = NULL;
447 scop->may_raw_no_source = NULL;
448 scop->must_war = NULL;
449 scop->may_war = NULL;
450 scop->must_war_no_source = NULL;
451 scop->may_war_no_source = NULL;
452 scop->must_waw = NULL;
453 scop->may_waw = NULL;
454 scop->must_waw_no_source = NULL;
455 scop->may_waw_no_source = NULL;
456 scop_set_region (scop, region);
457 SCOP_BBS (scop).create (3);
458 SCOP_ORIGINAL_SCHEDULE (scop) = NULL;
459 SCOP_TRANSFORMED_SCHEDULE (scop) = NULL;
460 SCOP_SAVED_SCHEDULE (scop) = NULL;
461 POLY_SCOP_P (scop) = false;
463 return scop;
466 /* Deletes SCOP. */
468 void
469 free_scop (scop_p scop)
471 int i;
472 poly_bb_p pbb;
474 FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb)
475 free_poly_bb (pbb);
477 SCOP_BBS (scop).release ();
479 isl_set_free (scop->context);
480 isl_union_map_free (scop->must_raw);
481 isl_union_map_free (scop->may_raw);
482 isl_union_map_free (scop->must_raw_no_source);
483 isl_union_map_free (scop->may_raw_no_source);
484 isl_union_map_free (scop->must_war);
485 isl_union_map_free (scop->may_war);
486 isl_union_map_free (scop->must_war_no_source);
487 isl_union_map_free (scop->may_war_no_source);
488 isl_union_map_free (scop->must_waw);
489 isl_union_map_free (scop->may_waw);
490 isl_union_map_free (scop->must_waw_no_source);
491 isl_union_map_free (scop->may_waw_no_source);
492 free_lst (SCOP_ORIGINAL_SCHEDULE (scop));
493 free_lst (SCOP_TRANSFORMED_SCHEDULE (scop));
494 free_lst (SCOP_SAVED_SCHEDULE (scop));
495 XDELETE (scop);
498 /* Print to FILE the domain of PBB in OpenScop format, at some VERBOSITY
499 level. */
501 static void
502 openscop_print_pbb_domain (FILE *file, poly_bb_p pbb, int verbosity)
504 graphite_dim_t i;
505 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
507 if (!pbb->domain)
508 return;
510 if (verbosity > 0)
512 fprintf (file, "\n# Iteration domain of bb_%d (\n", GBB_BB (gbb)->index);
513 fprintf (file, "#eq");
515 for (i = 0; i < pbb_dim_iter_domain (pbb); i++)
516 fprintf (file, " i%d", (int) i);
518 for (i = 0; i < pbb_nb_params (pbb); i++)
519 fprintf (file, " p%d", (int) i);
521 fprintf (file, " cst\n");
524 fprintf (file, "XXX isl\n");
526 if (verbosity > 0)
527 fprintf (file, "#)\n");
530 /* Print to FILE the domain of PBB, at some VERBOSITY level. */
532 void
533 print_pbb_domain (FILE *file, poly_bb_p pbb, int verbosity ATTRIBUTE_UNUSED)
535 print_isl_set (file, pbb->domain);
538 /* Dump the cases of a graphite basic block GBB on FILE. */
540 static void
541 dump_gbb_cases (FILE *file, gimple_bb_p gbb)
543 int i;
544 gimple stmt;
545 vec<gimple> cases;
547 if (!gbb)
548 return;
550 cases = GBB_CONDITION_CASES (gbb);
551 if (cases.is_empty ())
552 return;
554 fprintf (file, "# cases bb_%d (\n", GBB_BB (gbb)->index);
556 FOR_EACH_VEC_ELT (cases, i, stmt)
558 fprintf (file, "# ");
559 print_gimple_stmt (file, stmt, 0, 0);
562 fprintf (file, "#)\n");
565 /* Dump conditions of a graphite basic block GBB on FILE. */
567 static void
568 dump_gbb_conditions (FILE *file, gimple_bb_p gbb)
570 int i;
571 gimple stmt;
572 vec<gimple> conditions;
574 if (!gbb)
575 return;
577 conditions = GBB_CONDITIONS (gbb);
578 if (conditions.is_empty ())
579 return;
581 fprintf (file, "# conditions bb_%d (\n", GBB_BB (gbb)->index);
583 FOR_EACH_VEC_ELT (conditions, i, stmt)
585 fprintf (file, "# ");
586 print_gimple_stmt (file, stmt, 0, 0);
589 fprintf (file, "#)\n");
592 /* Print to FILE all the data references of PBB, at some VERBOSITY
593 level. */
595 void
596 print_pdrs (FILE *file, poly_bb_p pbb, int verbosity)
598 int i;
599 poly_dr_p pdr;
600 int nb_reads = 0;
601 int nb_writes = 0;
603 if (PBB_DRS (pbb).length () == 0)
605 if (verbosity > 0)
606 fprintf (file, "# Access informations are not provided\n");\
607 fprintf (file, "0\n");
608 return;
611 if (verbosity > 1)
612 fprintf (file, "# Data references (\n");
614 if (verbosity > 0)
615 fprintf (file, "# Access informations are provided\n");
616 fprintf (file, "1\n");
618 FOR_EACH_VEC_ELT (PBB_DRS (pbb), i, pdr)
619 if (PDR_TYPE (pdr) == PDR_READ)
620 nb_reads++;
621 else
622 nb_writes++;
624 if (verbosity > 1)
625 fprintf (file, "# Read data references (\n");
627 if (verbosity > 0)
628 fprintf (file, "# Read access informations\n");
629 fprintf (file, "%d\n", nb_reads);
631 FOR_EACH_VEC_ELT (PBB_DRS (pbb), i, pdr)
632 if (PDR_TYPE (pdr) == PDR_READ)
633 print_pdr (file, pdr, verbosity);
635 if (verbosity > 1)
636 fprintf (file, "#)\n");
638 if (verbosity > 1)
639 fprintf (file, "# Write data references (\n");
641 if (verbosity > 0)
642 fprintf (file, "# Write access informations\n");
643 fprintf (file, "%d\n", nb_writes);
645 FOR_EACH_VEC_ELT (PBB_DRS (pbb), i, pdr)
646 if (PDR_TYPE (pdr) != PDR_READ)
647 print_pdr (file, pdr, verbosity);
649 if (verbosity > 1)
650 fprintf (file, "#)\n");
652 if (verbosity > 1)
653 fprintf (file, "#)\n");
656 /* Print to STDERR all the data references of PBB. */
658 DEBUG_FUNCTION void
659 debug_pdrs (poly_bb_p pbb, int verbosity)
661 print_pdrs (stderr, pbb, verbosity);
664 /* Print to FILE the body of PBB, at some VERBOSITY level.
665 If statement_body_provided is false statement body is not printed. */
667 static void
668 print_pbb_body (FILE *file, poly_bb_p pbb, int verbosity,
669 bool statement_body_provided)
671 if (verbosity > 1)
672 fprintf (file, "# Body (\n");
674 if (!statement_body_provided)
676 if (verbosity > 0)
677 fprintf (file, "# Statement body is not provided\n");
679 fprintf (file, "0\n");
681 if (verbosity > 1)
682 fprintf (file, "#)\n");
683 return;
686 if (verbosity > 0)
687 fprintf (file, "# Statement body is provided\n");
688 fprintf (file, "1\n");
690 if (verbosity > 0)
691 fprintf (file, "# Original iterator names\n# Iterator names are not provided yet.\n");
693 if (verbosity > 0)
694 fprintf (file, "# Statement body\n");
696 fprintf (file, "{\n");
697 dump_bb (file, pbb_bb (pbb), 0, 0);
698 fprintf (file, "}\n");
700 if (verbosity > 1)
701 fprintf (file, "#)\n");
704 /* Print to FILE the domain and scattering function of PBB, at some
705 VERBOSITY level. */
707 void
708 print_pbb (FILE *file, poly_bb_p pbb, int verbosity)
710 if (verbosity > 1)
712 fprintf (file, "# pbb_%d (\n", pbb_index (pbb));
713 dump_gbb_conditions (file, PBB_BLACK_BOX (pbb));
714 dump_gbb_cases (file, PBB_BLACK_BOX (pbb));
717 openscop_print_pbb_domain (file, pbb, verbosity);
718 print_scattering_function (file, pbb, verbosity);
719 print_pdrs (file, pbb, verbosity);
720 print_pbb_body (file, pbb, verbosity, false);
722 if (verbosity > 1)
723 fprintf (file, "#)\n");
726 /* Print to FILE the parameters of SCOP, at some VERBOSITY level. */
728 void
729 print_scop_params (FILE *file, scop_p scop, int verbosity)
731 int i;
732 tree t;
734 if (verbosity > 1)
735 fprintf (file, "# parameters (\n");
737 if (SESE_PARAMS (SCOP_REGION (scop)).length ())
739 if (verbosity > 0)
740 fprintf (file, "# Parameter names are provided\n");
742 fprintf (file, "1\n");
744 if (verbosity > 0)
745 fprintf (file, "# Parameter names\n");
747 else
749 if (verbosity > 0)
750 fprintf (file, "# Parameter names are not provided\n");
751 fprintf (file, "0\n");
754 FOR_EACH_VEC_ELT (SESE_PARAMS (SCOP_REGION (scop)), i, t)
756 print_generic_expr (file, t, 0);
757 fprintf (file, " ");
760 fprintf (file, "\n");
762 if (verbosity > 1)
763 fprintf (file, "#)\n");
766 /* Print to FILE the context of SCoP in OpenScop format, at some VERBOSITY
767 level. */
769 static void
770 openscop_print_scop_context (FILE *file, scop_p scop, int verbosity)
772 graphite_dim_t i;
774 if (verbosity > 0)
776 fprintf (file, "# Context (\n");
777 fprintf (file, "#eq");
779 for (i = 0; i < scop_nb_params (scop); i++)
780 fprintf (file, " p%d", (int) i);
782 fprintf (file, " cst\n");
785 if (scop->context)
786 /* XXX isl print context */
787 fprintf (file, "XXX isl\n");
788 else
789 fprintf (file, "0 %d 0 0 0 %d\n", (int) scop_nb_params (scop) + 2,
790 (int) scop_nb_params (scop));
792 if (verbosity > 0)
793 fprintf (file, "# )\n");
796 /* Print to FILE the context of SCoP, at some VERBOSITY level. */
798 void
799 print_scop_context (FILE *file, scop_p scop, int verbosity)
801 graphite_dim_t i;
803 if (verbosity > 0)
805 fprintf (file, "# Context (\n");
806 fprintf (file, "#eq");
808 for (i = 0; i < scop_nb_params (scop); i++)
809 fprintf (file, " p%d", (int) i);
811 fprintf (file, " cst\n");
814 if (scop->context)
815 print_isl_set (file, scop->context);
816 else
817 fprintf (file, "no isl context %d\n", (int) scop_nb_params (scop) + 2);
819 if (verbosity > 0)
820 fprintf (file, "# )\n");
823 /* Print to FILE the SCOP, at some VERBOSITY level. */
825 void
826 print_scop (FILE *file, scop_p scop, int verbosity)
828 int i;
829 poly_bb_p pbb;
831 fprintf (file, "SCoP 1\n#(\n");
832 fprintf (file, "# Language\nGimple\n");
833 openscop_print_scop_context (file, scop, verbosity);
834 print_scop_params (file, scop, verbosity);
836 if (verbosity > 0)
837 fprintf (file, "# Number of statements\n");
839 fprintf (file, "%d\n", SCOP_BBS (scop).length ());
841 FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb)
842 print_pbb (file, pbb, verbosity);
844 if (verbosity > 1)
846 fprintf (file, "# original_lst (\n");
847 print_lst (file, SCOP_ORIGINAL_SCHEDULE (scop), 0);
848 fprintf (file, "\n#)\n");
850 fprintf (file, "# transformed_lst (\n");
851 print_lst (file, SCOP_TRANSFORMED_SCHEDULE (scop), 0);
852 fprintf (file, "\n#)\n");
855 fprintf (file, "#)\n");
858 /* Print to STDERR the domain of PBB, at some VERBOSITY level. */
860 DEBUG_FUNCTION void
861 debug_pbb_domain (poly_bb_p pbb, int verbosity)
863 print_pbb_domain (stderr, pbb, verbosity);
866 /* Print to FILE the domain and scattering function of PBB, at some
867 VERBOSITY level. */
869 DEBUG_FUNCTION void
870 debug_pbb (poly_bb_p pbb, int verbosity)
872 print_pbb (stderr, pbb, verbosity);
875 /* Print to STDERR the context of SCOP, at some VERBOSITY level. */
877 DEBUG_FUNCTION void
878 debug_scop_context (scop_p scop, int verbosity)
880 print_scop_context (stderr, scop, verbosity);
883 /* Print to STDERR the SCOP, at some VERBOSITY level. */
885 DEBUG_FUNCTION void
886 debug_scop (scop_p scop, int verbosity)
888 print_scop (stderr, scop, verbosity);
891 /* Print to STDERR the parameters of SCOP, at some VERBOSITY
892 level. */
894 DEBUG_FUNCTION void
895 debug_scop_params (scop_p scop, int verbosity)
897 print_scop_params (stderr, scop, verbosity);
900 extern isl_ctx *the_isl_ctx;
901 void
902 print_isl_set (FILE *f, isl_set *set)
904 isl_printer *p = isl_printer_to_file (the_isl_ctx, f);
905 p = isl_printer_print_set (p, set);
906 isl_printer_free (p);
909 DEBUG_FUNCTION void
910 debug_isl_set (isl_set *set)
912 print_isl_set (stderr, set);
915 void
916 print_isl_map (FILE *f, isl_map *map)
918 isl_printer *p = isl_printer_to_file (the_isl_ctx, f);
919 p = isl_printer_print_map (p, map);
920 isl_printer_free (p);
923 DEBUG_FUNCTION void
924 debug_isl_map (isl_map *map)
926 print_isl_map (stderr, map);
929 void
930 print_isl_aff (FILE *f, isl_aff *aff)
932 isl_printer *p = isl_printer_to_file (the_isl_ctx, f);
933 p = isl_printer_print_aff (p, aff);
934 isl_printer_free (p);
937 DEBUG_FUNCTION void
938 debug_isl_aff (isl_aff *aff)
940 print_isl_aff (stderr, aff);
943 void
944 print_isl_constraint (FILE *f, isl_constraint *c)
946 isl_printer *p = isl_printer_to_file (the_isl_ctx, f);
947 p = isl_printer_print_constraint (p, c);
948 isl_printer_free (p);
951 DEBUG_FUNCTION void
952 debug_isl_constraint (isl_constraint *c)
954 print_isl_constraint (stderr, c);
957 /* Returns the number of iterations RES of the loop around PBB at
958 time(scattering) dimension TIME_DEPTH. */
960 void
961 pbb_number_of_iterations_at_time (poly_bb_p pbb,
962 graphite_dim_t time_depth,
963 mpz_t res)
965 isl_set *transdomain;
966 isl_space *dc;
967 isl_aff *aff;
968 isl_val *isllb, *islub;
970 /* Map the iteration domain through the current scatter, and work
971 on the resulting set. */
972 transdomain = isl_set_apply (isl_set_copy (pbb->domain),
973 isl_map_copy (pbb->transformed));
975 /* Select the time_depth' dimension via an affine expression. */
976 dc = isl_set_get_space (transdomain);
977 aff = isl_aff_zero_on_domain (isl_local_space_from_space (dc));
978 aff = isl_aff_set_coefficient_si (aff, isl_dim_in, time_depth, 1);
980 /* And find the min/max for that function. */
981 /* XXX isl check results? */
982 isllb = isl_set_min_val (transdomain, aff);
983 islub = isl_set_max_val (transdomain, aff);
985 islub = isl_val_sub (islub, isllb);
986 islub = isl_val_add_ui (islub, 1);
987 isl_val_get_num_gmp (islub, res);
989 isl_val_free (islub);
990 isl_aff_free (aff);
991 isl_set_free (transdomain);
994 /* Translates LOOP to LST. */
996 static lst_p
997 loop_to_lst (loop_p loop, vec<poly_bb_p> bbs, int *i)
999 poly_bb_p pbb;
1000 vec<lst_p> seq;
1001 seq.create (5);
1003 for (; bbs.iterate (*i, &pbb); (*i)++)
1005 lst_p stmt;
1006 basic_block bb = GBB_BB (PBB_BLACK_BOX (pbb));
1008 if (bb->loop_father == loop)
1009 stmt = new_lst_stmt (pbb);
1010 else if (flow_bb_inside_loop_p (loop, bb))
1012 loop_p next = loop->inner;
1014 while (next && !flow_bb_inside_loop_p (next, bb))
1015 next = next->next;
1017 stmt = loop_to_lst (next, bbs, i);
1019 else
1021 (*i)--;
1022 return new_lst_loop (seq);
1025 seq.safe_push (stmt);
1028 return new_lst_loop (seq);
1031 /* Reads the original scattering of the SCOP and returns an LST
1032 representing it. */
1034 void
1035 scop_to_lst (scop_p scop)
1037 lst_p res;
1038 int i, n = SCOP_BBS (scop).length ();
1039 vec<lst_p> seq;
1040 seq.create (5);
1041 sese region = SCOP_REGION (scop);
1043 for (i = 0; i < n; i++)
1045 poly_bb_p pbb = SCOP_BBS (scop)[i];
1046 loop_p loop = outermost_loop_in_sese (region, GBB_BB (PBB_BLACK_BOX (pbb)));
1048 if (loop_in_sese_p (loop, region))
1049 res = loop_to_lst (loop, SCOP_BBS (scop), &i);
1050 else
1051 res = new_lst_stmt (pbb);
1053 seq.safe_push (res);
1056 res = new_lst_loop (seq);
1057 SCOP_ORIGINAL_SCHEDULE (scop) = res;
1058 SCOP_TRANSFORMED_SCHEDULE (scop) = copy_lst (res);
1061 /* Print to FILE on a new line COLUMN white spaces. */
1063 static void
1064 lst_indent_to (FILE *file, int column)
1066 int i;
1068 if (column > 0)
1069 fprintf (file, "\n#");
1071 for (i = 0; i < column; i++)
1072 fprintf (file, " ");
1075 /* Print LST to FILE with INDENT spaces of indentation. */
1077 void
1078 print_lst (FILE *file, lst_p lst, int indent)
1080 if (!lst)
1081 return;
1083 lst_indent_to (file, indent);
1085 if (LST_LOOP_P (lst))
1087 int i;
1088 lst_p l;
1090 if (LST_LOOP_FATHER (lst))
1091 fprintf (file, "%d (loop", lst_dewey_number (lst));
1092 else
1093 fprintf (file, "#(root");
1095 FOR_EACH_VEC_ELT (LST_SEQ (lst), i, l)
1096 print_lst (file, l, indent + 2);
1098 fprintf (file, ")");
1100 else
1101 fprintf (file, "%d stmt_%d", lst_dewey_number (lst), pbb_index (LST_PBB (lst)));
1104 /* Print LST to STDERR. */
1106 DEBUG_FUNCTION void
1107 debug_lst (lst_p lst)
1109 print_lst (stderr, lst, 0);
1112 /* Pretty print to FILE the loop statement tree LST in DOT format. */
1114 static void
1115 dot_lst_1 (FILE *file, lst_p lst)
1117 if (!lst)
1118 return;
1120 if (LST_LOOP_P (lst))
1122 int i;
1123 lst_p l;
1125 if (!LST_LOOP_FATHER (lst))
1126 fprintf (file, "L -> L_%d_%d\n",
1127 lst_depth (lst),
1128 lst_dewey_number (lst));
1129 else
1130 fprintf (file, "L_%d_%d -> L_%d_%d\n",
1131 lst_depth (LST_LOOP_FATHER (lst)),
1132 lst_dewey_number (LST_LOOP_FATHER (lst)),
1133 lst_depth (lst),
1134 lst_dewey_number (lst));
1136 FOR_EACH_VEC_ELT (LST_SEQ (lst), i, l)
1137 dot_lst_1 (file, l);
1140 else
1141 fprintf (file, "L_%d_%d -> S_%d\n",
1142 lst_depth (LST_LOOP_FATHER (lst)),
1143 lst_dewey_number (LST_LOOP_FATHER (lst)),
1144 pbb_index (LST_PBB (lst)));
1148 /* Display the LST using dotty. */
1150 DEBUG_FUNCTION void
1151 dot_lst (lst_p lst)
1153 /* When debugging, enable the following code. This cannot be used
1154 in production compilers because it calls "system". */
1155 #if 0
1156 FILE *stream = fopen ("/tmp/lst.dot", "w");
1157 gcc_assert (stream);
1159 fputs ("digraph all {\n", stream);
1160 dot_lst_1 (stream, lst);
1161 fputs ("}\n\n", stream);
1162 fclose (stream);
1164 system ("dotty /tmp/lst.dot &");
1165 #else
1166 fputs ("digraph all {\n", stderr);
1167 dot_lst_1 (stderr, lst);
1168 fputs ("}\n\n", stderr);
1170 #endif
1173 /* Reverse the loop around PBB at level DEPTH. */
1175 isl_map *
1176 reverse_loop_at_level (poly_bb_p pbb, int depth)
1178 unsigned i, depth_dim = psct_dynamic_dim (pbb, depth);
1179 isl_space *d = isl_map_get_space (pbb->transformed);
1180 isl_space *d1 = isl_space_range (d);
1181 unsigned n = isl_space_dim (d1, isl_dim_out);
1182 isl_space *d2 = isl_space_add_dims (d1, isl_dim_in, n);
1183 isl_map *x = isl_map_universe (isl_space_copy (d2));
1184 isl_constraint *c = isl_equality_alloc (isl_local_space_from_space (d2));
1186 for (i = 0; i < n; i++)
1187 if (i != depth_dim)
1188 x = isl_map_equate (x, isl_dim_in, i, isl_dim_out, i);
1190 c = isl_constraint_set_coefficient_si (c, isl_dim_in, depth_dim, 1);
1191 c = isl_constraint_set_coefficient_si (c, isl_dim_out, depth_dim, 1);
1192 x = isl_map_add_constraint (x, c);
1193 return x;
1196 /* Reverse the loop at level DEPTH for all the PBBS. */
1198 isl_union_map *
1199 reverse_loop_for_pbbs (scop_p scop, vec<poly_bb_p> pbbs, int depth)
1201 poly_bb_p pbb;
1202 int i;
1203 isl_space *space = isl_space_from_domain (isl_set_get_space (scop->context));
1204 isl_union_map *res = isl_union_map_empty (space);
1206 for (i = 0; pbbs.iterate (i, &pbb); i++)
1207 res = isl_union_map_add_map (res, reverse_loop_at_level (pbb, depth));
1209 return res;
1213 #endif