OSDN Git Service

5305df44d77774ba69444ba84c1594de05fc686e
[pf3gnuchains/gcc-fork.git] / gcc / graphite-poly.c
1 /* Graphite polyhedral representation.
2    Copyright (C) 2009 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 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "ggc.h"
26 #include "tree.h"
27 #include "rtl.h"
28 #include "output.h"
29 #include "basic-block.h"
30 #include "diagnostic.h"
31 #include "tree-flow.h"
32 #include "toplev.h"
33 #include "tree-dump.h"
34 #include "timevar.h"
35 #include "cfgloop.h"
36 #include "tree-chrec.h"
37 #include "tree-data-ref.h"
38 #include "tree-scalar-evolution.h"
39 #include "tree-pass.h"
40 #include "domwalk.h"
41 #include "value-prof.h"
42 #include "pointer-set.h"
43 #include "gimple.h"
44 #include "params.h"
45
46 #ifdef HAVE_cloog
47 #include "cloog/cloog.h"
48 #include "ppl_c.h"
49 #include "sese.h"
50 #include "graphite-ppl.h"
51 #include "graphite.h"
52 #include "graphite-poly.h"
53 #include "graphite-dependences.h"
54
55 /* Return the maximal loop depth in SCOP.  */
56
57 int
58 scop_max_loop_depth (scop_p scop)
59 {
60   int i;
61   poly_bb_p pbb;
62   int max_nb_loops = 0;
63
64   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
65     {
66       int nb_loops = pbb_dim_iter_domain (pbb);
67       if (max_nb_loops < nb_loops)
68         max_nb_loops = nb_loops;
69     }
70
71   return max_nb_loops;
72 }
73
74 /* Extend the scattering matrix of PBB to MAX_SCATTERING scattering
75    dimensions.  */
76
77 static void
78 extend_scattering (poly_bb_p pbb, int max_scattering)
79 {
80   ppl_dimension_type nb_old_dims, nb_new_dims;
81   int nb_added_dims, i;
82   ppl_Coefficient_t coef;
83   Value one;
84
85   nb_added_dims = max_scattering - pbb_nb_scattering_transform (pbb);
86   value_init (one);
87   value_set_si (one, 1);
88   ppl_new_Coefficient (&coef);
89   ppl_assign_Coefficient_from_mpz_t (coef, one);
90
91   gcc_assert (nb_added_dims >= 0);
92
93   nb_old_dims = pbb_nb_scattering_transform (pbb) + pbb_dim_iter_domain (pbb)
94     + scop_nb_params (PBB_SCOP (pbb));
95   nb_new_dims = nb_old_dims + nb_added_dims;
96
97   ppl_insert_dimensions (PBB_TRANSFORMED_SCATTERING (pbb),
98                          pbb_nb_scattering_transform (pbb), nb_added_dims);
99   PBB_NB_SCATTERING_TRANSFORM (pbb) += nb_added_dims;
100
101   /* Add identity matrix for the added dimensions.  */
102   for (i = max_scattering - nb_added_dims; i < max_scattering; i++)
103     {
104       ppl_Constraint_t cstr;
105       ppl_Linear_Expression_t expr;
106
107       ppl_new_Linear_Expression_with_dimension (&expr, nb_new_dims);
108       ppl_Linear_Expression_add_to_coefficient (expr, i, coef);
109       ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_EQUAL);
110       ppl_Polyhedron_add_constraint (PBB_TRANSFORMED_SCATTERING (pbb), cstr);
111       ppl_delete_Constraint (cstr);
112       ppl_delete_Linear_Expression (expr);
113     }
114
115   ppl_delete_Coefficient (coef);
116   value_clear (one);
117 }
118
119 /* All scattering matrices in SCOP will have the same number of scattering
120    dimensions.  */
121
122 int
123 unify_scattering_dimensions (scop_p scop)
124 {
125   int i;
126   poly_bb_p pbb;
127   graphite_dim_t max_scattering = 0;
128
129   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
130     max_scattering = MAX (pbb_nb_scattering_transform (pbb), max_scattering);
131
132   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
133     extend_scattering (pbb, max_scattering);
134
135   return max_scattering;
136 }
137
138 /* Prints to FILE the scattering function of PBB.  */
139
140 static void
141 print_scattering_function_1 (FILE *file, poly_bb_p pbb)
142 {
143   graphite_dim_t i;
144
145   fprintf (file, "# scattering bb_%d (\n", pbb_index (pbb));
146   fprintf (file, "#  eq");
147
148   for (i = 0; i < pbb_nb_scattering_transform (pbb); i++)
149     fprintf (file, "     s%d", (int) i);
150
151   for (i = 0; i < pbb_nb_local_vars (pbb); i++)
152     fprintf (file, "    lv%d", (int) i);
153
154   for (i = 0; i < pbb_dim_iter_domain (pbb); i++)
155     fprintf (file, "     i%d", (int) i);
156
157   for (i = 0; i < pbb_nb_params (pbb); i++)
158     fprintf (file, "     p%d", (int) i);
159
160   fprintf (file, "    cst\n");
161
162   /* Number of disjunct components.  Remove this when
163      PBB_TRANSFORMED_SCATTERING will be a pointset_powerset.  */
164   fprintf (file, "1\n");
165   ppl_print_polyhedron_matrix (file, PBB_TRANSFORMED_SCATTERING (pbb)
166                                ? PBB_TRANSFORMED_SCATTERING (pbb)
167                                : PBB_ORIGINAL_SCATTERING (pbb));
168
169   fprintf (file, "#)\n");
170 }
171
172 /* Prints to FILE the scattering function of PBB.  */
173
174 void
175 print_scattering_function (FILE *file, poly_bb_p pbb)
176 {
177   if (!PBB_TRANSFORMED (pbb))
178     return;
179
180   if (PBB_TRANSFORMED_SCATTERING (pbb)
181       || PBB_ORIGINAL_SCATTERING (pbb))
182     fprintf (file, "# Scattering function is provided\n1\n");
183   else
184     {
185       fprintf (file, "# Scattering function is not provided\n0\n");
186       return;
187     }
188
189   print_scattering_function_1 (file, pbb);
190 }
191
192 /* Prints to FILE the iteration domain of PBB.  */
193
194 void
195 print_iteration_domain (FILE *file, poly_bb_p pbb)
196 {
197   print_pbb_domain (file, pbb);
198 }
199
200 /* Prints to FILE the scattering functions of every PBB of SCOP.  */
201
202 void
203 print_scattering_functions (FILE *file, scop_p scop)
204 {
205   int i;
206   poly_bb_p pbb;
207
208   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
209     print_scattering_function (file, pbb);
210 }
211
212 /* Prints to FILE the iteration domains of every PBB of SCOP.  */
213
214 void
215 print_iteration_domains (FILE *file, scop_p scop)
216 {
217   int i;
218   poly_bb_p pbb;
219
220   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
221     print_iteration_domain (file, pbb);
222 }
223
224 /* Prints to STDERR the scattering function of PBB.  */
225
226 void
227 debug_scattering_function (poly_bb_p pbb)
228 {
229   print_scattering_function (stderr, pbb);
230 }
231
232 /* Prints to STDERR the iteration domain of PBB.  */
233
234 void
235 debug_iteration_domain (poly_bb_p pbb)
236 {
237   print_iteration_domain (stderr, pbb);
238 }
239
240 /* Prints to STDERR the scattering functions of every PBB of SCOP.  */
241
242 void
243 debug_scattering_functions (scop_p scop)
244 {
245   print_scattering_functions (stderr, scop);
246 }
247
248 /* Prints to STDERR the iteration domains of every PBB of SCOP.  */
249
250 void
251 debug_iteration_domains (scop_p scop)
252 {
253   print_iteration_domains (stderr, scop);
254 }
255
256 /* Apply graphite transformations to all the basic blocks of SCOP.  */
257
258 bool
259 apply_poly_transforms (scop_p scop)
260 {
261   bool transform_done = false;
262
263   /* Generate code even if we did not apply any real transformation.
264      This also allows to check the performance for the identity
265      transformation: GIMPLE -> GRAPHITE -> GIMPLE
266      Keep in mind that CLooG optimizes in control, so the loop structure
267      may change, even if we only use -fgraphite-identity.  */
268   if (flag_graphite_identity)
269     transform_done = true;
270
271   if (flag_loop_parallelize_all)
272     transform_done = true;
273
274   if (flag_loop_block)
275     transform_done |= scop_do_block (scop);
276   else
277     {
278       if (flag_loop_strip_mine)
279         transform_done |= scop_do_strip_mine (scop);
280
281       if (flag_loop_interchange)
282         transform_done |= scop_do_interchange (scop);
283     }
284
285   return transform_done;
286 }
287
288 /* Returns true when it PDR1 is a duplicate of PDR2: same PBB, and
289    their ACCESSES, TYPE, and NB_SUBSCRIPTS are the same.  */
290
291 static inline bool
292 can_collapse_pdrs (poly_dr_p pdr1, poly_dr_p pdr2)
293 {
294   bool res;
295   ppl_Pointset_Powerset_C_Polyhedron_t af1, af2, diff;
296
297   if (PDR_PBB (pdr1) != PDR_PBB (pdr2)
298       || PDR_NB_SUBSCRIPTS (pdr1) != PDR_NB_SUBSCRIPTS (pdr2)
299       || PDR_TYPE (pdr1) != PDR_TYPE (pdr2))
300     return false;
301
302   af1 = PDR_ACCESSES (pdr1);
303   af2 = PDR_ACCESSES (pdr2);
304   ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
305     (&diff, af1);
306   ppl_Pointset_Powerset_C_Polyhedron_difference_assign (diff, af2);
307
308   res = ppl_Pointset_Powerset_C_Polyhedron_is_empty (diff);
309   ppl_delete_Pointset_Powerset_C_Polyhedron (diff);
310   return res;
311 }
312
313 /* Removes duplicated data references in PBB.  */
314
315 void
316 pbb_remove_duplicate_pdrs (poly_bb_p pbb)
317 {
318   int i, j;
319   poly_dr_p pdr1, pdr2;
320   unsigned n = VEC_length (poly_dr_p, PBB_DRS (pbb));
321   VEC (poly_dr_p, heap) *collapsed = VEC_alloc (poly_dr_p, heap, n);
322
323   for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb), i, pdr1); i++)
324     for (j = 0; VEC_iterate (poly_dr_p, collapsed, j, pdr2); j++)
325       if (!can_collapse_pdrs (pdr1, pdr2))
326         VEC_quick_push (poly_dr_p, collapsed, pdr1);
327
328   VEC_free (poly_dr_p, heap, collapsed);
329   PBB_PDR_DUPLICATES_REMOVED (pbb) = true;
330 }
331
332 /* Create a new polyhedral data reference and add it to PBB.  It is
333    defined by its ACCESSES, its TYPE, and the number of subscripts
334    NB_SUBSCRIPTS.  */
335
336 void
337 new_poly_dr (poly_bb_p pbb, int dr_base_object_set,
338              ppl_Pointset_Powerset_C_Polyhedron_t accesses,
339              enum poly_dr_type type, void *cdr, graphite_dim_t nb_subscripts)
340 {
341   static int id = 0;
342   poly_dr_p pdr = XNEW (struct poly_dr);
343
344   PDR_ID (pdr) = id++;
345   PDR_BASE_OBJECT_SET (pdr) = dr_base_object_set;
346   PDR_NB_REFS (pdr) = 1;
347   PDR_PBB (pdr) = pbb;
348   PDR_ACCESSES (pdr) = accesses;
349   PDR_TYPE (pdr) = type;
350   PDR_CDR (pdr) = cdr;
351   PDR_NB_SUBSCRIPTS (pdr) = nb_subscripts;
352   VEC_safe_push (poly_dr_p, heap, PBB_DRS (pbb), pdr);
353 }
354
355 /* Free polyhedral data reference PDR.  */
356
357 void
358 free_poly_dr (poly_dr_p pdr)
359 {
360   ppl_delete_Pointset_Powerset_C_Polyhedron (PDR_ACCESSES (pdr));
361   XDELETE (pdr);
362 }
363
364 /* Create a new polyhedral black box.  */
365
366 void
367 new_poly_bb (scop_p scop, void *black_box, bool reduction)
368 {
369   poly_bb_p pbb = XNEW (struct poly_bb);
370
371   PBB_DOMAIN (pbb) = NULL;
372   PBB_SCOP (pbb) = scop;
373   pbb_set_black_box (pbb, black_box);
374   PBB_TRANSFORMED (pbb) = NULL;
375   PBB_SAVED (pbb) = NULL;
376   PBB_ORIGINAL (pbb) = NULL;
377   PBB_DRS (pbb) = VEC_alloc (poly_dr_p, heap, 3);
378   PBB_IS_REDUCTION (pbb) = reduction;
379   PBB_PDR_DUPLICATES_REMOVED (pbb) = false;
380   VEC_safe_push (poly_bb_p, heap, SCOP_BBS (scop), pbb);
381 }
382
383 /* Free polyhedral black box.  */
384
385 void
386 free_poly_bb (poly_bb_p pbb)
387 {
388   int i;
389   poly_dr_p pdr;
390
391   ppl_delete_Pointset_Powerset_C_Polyhedron (PBB_DOMAIN (pbb));
392
393   if (PBB_TRANSFORMED (pbb))
394     poly_scattering_free (PBB_TRANSFORMED (pbb));
395
396   if (PBB_SAVED (pbb))
397     poly_scattering_free (PBB_SAVED (pbb));
398
399   if (PBB_ORIGINAL (pbb))
400     poly_scattering_free (PBB_ORIGINAL (pbb));
401
402   if (PBB_DRS (pbb))
403     for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb), i, pdr); i++)
404       free_poly_dr (pdr);
405
406   VEC_free (poly_dr_p, heap, PBB_DRS (pbb));
407   XDELETE (pbb);
408 }
409
410 static void
411 print_pdr_access_layout (FILE *file, poly_dr_p pdr)
412 {
413   graphite_dim_t i;
414
415   fprintf (file, "#  eq");
416
417   for (i = 0; i < pdr_dim_iter_domain (pdr); i++)
418     fprintf (file, "     i%d", (int) i);
419
420   for (i = 0; i < pdr_nb_params (pdr); i++)
421     fprintf (file, "     p%d", (int) i);
422
423   fprintf (file, "  alias");
424
425   for (i = 0; i < PDR_NB_SUBSCRIPTS (pdr); i++)
426     fprintf (file, "   sub%d", (int) i);
427
428   fprintf (file, "    cst\n");
429 }
430
431 /* Prints to FILE the polyhedral data reference PDR.  */
432
433 void
434 print_pdr (FILE *file, poly_dr_p pdr)
435 {
436   fprintf (file, "# pdr_%d (", PDR_ID (pdr));
437
438   switch (PDR_TYPE (pdr))
439     {
440     case PDR_READ:
441       fprintf (file, "read \n");
442       break;
443
444     case PDR_WRITE:
445       fprintf (file, "write \n");
446       break;
447
448     case PDR_MAY_WRITE:
449       fprintf (file, "may_write \n");
450       break;
451
452     default:
453       gcc_unreachable ();
454     }
455
456   dump_data_reference (file, (data_reference_p) PDR_CDR (pdr));
457
458   fprintf (file, "# data accesses (\n");
459   print_pdr_access_layout (file, pdr);
460   ppl_print_powerset_matrix (file, PDR_ACCESSES (pdr));
461   fprintf (file, "#)\n");
462
463   fprintf (file, "#)\n");
464 }
465
466 /* Prints to STDERR the polyhedral data reference PDR.  */
467
468 void
469 debug_pdr (poly_dr_p pdr)
470 {
471   print_pdr (stderr, pdr);
472 }
473
474 /* Creates a new SCOP containing REGION.  */
475
476 scop_p
477 new_scop (void *region)
478 {
479   scop_p scop = XNEW (struct scop);
480
481   SCOP_CONTEXT (scop) = NULL;
482   scop_set_region (scop, region);
483   SCOP_BBS (scop) = VEC_alloc (poly_bb_p, heap, 3);
484   SCOP_ORIGINAL_PDDRS (scop) = htab_create (10, hash_poly_ddr_p,
485                                             eq_poly_ddr_p, free_poly_ddr);
486   SCOP_ORIGINAL_SCHEDULE (scop) = NULL;
487   SCOP_TRANSFORMED_SCHEDULE (scop) = NULL;
488   SCOP_SAVED_SCHEDULE (scop) = NULL;
489   POLY_SCOP_P (scop) = false;
490
491   return scop;
492 }
493
494 /* Deletes SCOP.  */
495
496 void
497 free_scop (scop_p scop)
498 {
499   int i;
500   poly_bb_p pbb;
501
502   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
503     free_poly_bb (pbb);
504
505   VEC_free (poly_bb_p, heap, SCOP_BBS (scop));
506
507   if (SCOP_CONTEXT (scop))
508     ppl_delete_Pointset_Powerset_C_Polyhedron (SCOP_CONTEXT (scop));
509
510   htab_delete (SCOP_ORIGINAL_PDDRS (scop));
511   free_lst (SCOP_ORIGINAL_SCHEDULE (scop));
512   free_lst (SCOP_TRANSFORMED_SCHEDULE (scop));
513   free_lst (SCOP_SAVED_SCHEDULE (scop));
514   XDELETE (scop);
515 }
516
517 /* Print to FILE the domain of PBB.  */
518
519 void
520 print_pbb_domain (FILE *file, poly_bb_p pbb)
521 {
522   graphite_dim_t i;
523   gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
524
525   if (!PBB_DOMAIN (pbb))
526     return;
527
528   fprintf (file, "# Iteration domain of bb_%d (\n", GBB_BB (gbb)->index);
529   fprintf (file, "#  eq");
530
531   for (i = 0; i < pbb_dim_iter_domain (pbb); i++)
532     fprintf (file, "     i%d", (int) i);
533
534   for (i = 0; i < pbb_nb_params (pbb); i++)
535     fprintf (file, "     p%d", (int) i);
536
537   fprintf (file, "    cst\n");
538
539   if (PBB_DOMAIN (pbb))
540     ppl_print_powerset_matrix (file, PBB_DOMAIN (pbb));
541   else
542     fprintf (file, "0\n");
543
544   fprintf (file, "#)\n");
545 }
546
547 /* Dump the cases of a graphite basic block GBB on FILE.  */
548
549 static void
550 dump_gbb_cases (FILE *file, gimple_bb_p gbb)
551 {
552   int i;
553   gimple stmt;
554   VEC (gimple, heap) *cases;
555
556   if (!gbb)
557     return;
558
559   cases = GBB_CONDITION_CASES (gbb);
560   if (VEC_empty (gimple, cases))
561     return;
562
563   fprintf (file, "# cases bb_%d (\n", GBB_BB (gbb)->index);
564
565   for (i = 0; VEC_iterate (gimple, cases, i, stmt); i++)
566     {
567       fprintf (file, "# ");
568       print_gimple_stmt (file, stmt, 0, 0);
569     }
570
571   fprintf (file, "#)\n");
572 }
573
574 /* Dump conditions of a graphite basic block GBB on FILE.  */
575
576 static void
577 dump_gbb_conditions (FILE *file, gimple_bb_p gbb)
578 {
579   int i;
580   gimple stmt;
581   VEC (gimple, heap) *conditions;
582
583   if (!gbb)
584     return;
585
586   conditions = GBB_CONDITIONS (gbb);
587   if (VEC_empty (gimple, conditions))
588     return;
589
590   fprintf (file, "# conditions bb_%d (\n", GBB_BB (gbb)->index);
591
592   for (i = 0; VEC_iterate (gimple, conditions, i, stmt); i++)
593     {
594       fprintf (file, "# ");
595       print_gimple_stmt (file, stmt, 0, 0);
596     }
597
598   fprintf (file, "#)\n");
599 }
600
601 /* Print to FILE all the data references of PBB.  */
602
603 void
604 print_pdrs (FILE *file, poly_bb_p pbb)
605 {
606   int i;
607   poly_dr_p pdr;
608   int nb_reads = 0;
609   int nb_writes = 0;
610
611   if (VEC_length (poly_dr_p, PBB_DRS (pbb)) == 0)
612     {
613       fprintf (file, "# Access informations are not provided\n0\n");
614       return;
615     }
616
617   fprintf (file, "# Data references (\n");
618   fprintf (file, "# Access informations are provided\n1\n");
619
620   for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb), i, pdr); i++)
621     if (PDR_TYPE (pdr) == PDR_READ)
622       nb_reads++;
623     else
624       nb_writes++;
625
626   fprintf (file, "# Read data references (\n");
627   fprintf (file, "# Read access informations\n%d\n", nb_reads);
628   for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb), i, pdr); i++)
629     if (PDR_TYPE (pdr) == PDR_READ)
630       print_pdr (file, pdr);
631   fprintf (file, "#)\n");
632
633   fprintf (file, "# Write data references (\n");
634   fprintf (file, "# Write access informations\n%d\n", nb_writes);
635   for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb), i, pdr); i++)
636     if (PDR_TYPE (pdr) != PDR_READ)
637       print_pdr (file, pdr);
638   fprintf (file, "#)\n");
639   fprintf (file, "#)\n");
640 }
641
642 /* Print to STDERR all the data references of PBB.  */
643
644 void
645 debug_pdrs (poly_bb_p pbb)
646 {
647   print_pdrs (stderr, pbb);
648 }
649
650 /* Print to FILE the body of PBB.  */
651
652 static void
653 print_pbb_body (FILE *file, poly_bb_p pbb)
654 {
655   fprintf (file, "# Body (\n");
656   fprintf (file, "# Statement body is provided\n1\n");
657   fprintf (file, "# Original iterator names\n# Iterator names are not provided yet.\n");
658   fprintf (file, "# Statement body\n");
659   fprintf (file, "{\n");
660   dump_bb (pbb_bb (pbb), file, 0);
661   fprintf (file, "}\n");
662   fprintf (file, "#)\n");
663 }
664
665 /* Print to FILE the domain and scattering function of PBB.  */
666
667 void
668 print_pbb (FILE *file, poly_bb_p pbb)
669 {
670   fprintf (file, "# pbb_%d (\n", pbb_index (pbb));
671   dump_gbb_conditions (file, PBB_BLACK_BOX (pbb));
672   dump_gbb_cases (file, PBB_BLACK_BOX (pbb));
673   print_pbb_domain (file, pbb);
674   print_scattering_function (file, pbb);
675   print_pdrs (file, pbb);
676   print_pbb_body (file, pbb);
677   fprintf (file, "#)\n");
678 }
679
680 /* Print to FILE the parameters of SCOP.  */
681
682 void
683 print_scop_params (FILE *file, scop_p scop)
684 {
685   int i;
686   tree t;
687
688   fprintf (file, "# parameters (\n");
689
690   if (VEC_length (tree, SESE_PARAMS (SCOP_REGION (scop))))
691     fprintf (file, "# Parameter names are provided\n1\n# Parameter names\n");
692   else
693     fprintf (file, "# Parameter names are not provided\n0\n");
694
695   for (i = 0; VEC_iterate (tree, SESE_PARAMS (SCOP_REGION (scop)), i, t); i++)
696     {
697       print_generic_expr (file, t, 0);
698       fprintf (file, " ");
699     }
700   fprintf (file, "#)\n");
701 }
702
703 /* Print to FILE the context of SCoP.  */
704 void
705 print_scop_context (FILE *file, scop_p scop)
706 {
707   graphite_dim_t i;
708
709   fprintf (file, "# Context (\n");
710   fprintf (file, "#  eq");
711
712   for (i = 0; i < scop_nb_params (scop); i++)
713     fprintf (file, "     p%d", (int) i);
714
715   fprintf (file, "    cst\n");
716
717   if (SCOP_CONTEXT (scop))
718     ppl_print_powerset_matrix (file, SCOP_CONTEXT (scop));
719   else
720     fprintf (file, "0 %d\n", (int) scop_nb_params (scop) + 2);
721
722   fprintf (file, "# )\n");
723 }
724
725 /* Print to FILE the SCOP.  */
726
727 void
728 print_scop (FILE *file, scop_p scop)
729 {
730   int i;
731   poly_bb_p pbb;
732
733   fprintf (file, "SCoP #(\n");
734   fprintf (file, "# Language\nGimple\n");
735   print_scop_context (file, scop);
736   print_scop_params (file, scop);
737   fprintf (file, "# Number of statements\n%d\n",
738            VEC_length (poly_bb_p, SCOP_BBS (scop)));
739
740   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
741     print_pbb (file, pbb);
742
743   fprintf (file, "# original_lst (\n");
744   print_lst (file, SCOP_ORIGINAL_SCHEDULE (scop), 0);
745   fprintf (file, "\n#)\n");
746
747   fprintf (file, "# transformed_lst (\n");
748   print_lst (file, SCOP_TRANSFORMED_SCHEDULE (scop), 0);
749   fprintf (file, "\n#)\n");
750
751   fprintf (file, "#)\n");
752 }
753
754 /* Print to FILE the input file that CLooG would expect as input.  */
755
756 void
757 print_cloog (FILE *file, scop_p scop)
758 {
759   int i;
760   poly_bb_p pbb;
761
762   fprintf (file, "# SCoP (generated by GCC/Graphite\n");
763   fprintf (file, "# CLooG output language\nc\n");
764   print_scop_context (file, scop);
765   print_scop_params (file, scop);
766   fprintf (file, "# Number of statements\n%d\n",
767            VEC_length (poly_bb_p, SCOP_BBS (scop)));
768
769   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
770     {
771       fprintf (file, "# pbb_%d (\n", pbb_index (pbb));
772       print_pbb_domain (file, pbb);
773       fprintf (file, "0 0 0 # For future CLooG options.\n#)\n");
774     }
775
776   fprintf (file, "0 # Don't set the iterator names.\n");
777
778   fprintf (file, "# Number of scattering functions\n%d\n",
779            VEC_length (poly_bb_p, SCOP_BBS (scop)));
780   unify_scattering_dimensions (scop);
781
782   for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
783     {
784       if (!PBB_TRANSFORMED (pbb)
785           || !(PBB_TRANSFORMED_SCATTERING (pbb)
786                || PBB_ORIGINAL_SCATTERING (pbb)))
787         continue;
788
789       fprintf (file, "# pbb_%d (\n", pbb_index (pbb));
790       print_scattering_function_1 (file, pbb);
791       fprintf (file, "#)\n");
792     }
793
794   fprintf (file, "0 # Don't set the scattering dimension names.\n");
795   fprintf (file, "#)\n");
796 }
797
798 /* Print to STDERR the domain of PBB.  */
799
800 void
801 debug_pbb_domain (poly_bb_p pbb)
802 {
803   print_pbb_domain (stderr, pbb);
804 }
805
806 /* Print to FILE the domain and scattering function of PBB.  */
807
808 void
809 debug_pbb (poly_bb_p pbb)
810 {
811   print_pbb (stderr, pbb);
812 }
813
814 /* Print to STDERR the context of SCOP.  */
815
816 void
817 debug_scop_context (scop_p scop)
818 {
819   print_scop_context (stderr, scop);
820 }
821
822 /* Print to STDERR the SCOP.  */
823
824 void
825 debug_scop (scop_p scop)
826 {
827   print_scop (stderr, scop);
828 }
829
830 /* Print to STDERR the SCOP under CLooG format.  */
831
832 void
833 debug_cloog (scop_p scop)
834 {
835   print_cloog (stderr, scop);
836 }
837
838 /* Print to STDERR the parameters of SCOP.  */
839
840 void
841 debug_scop_params (scop_p scop)
842 {
843   print_scop_params (stderr, scop);
844 }
845
846
847 /* The dimension in the transformed scattering polyhedron of PBB
848    containing the scattering iterator for the loop at depth LOOP_DEPTH.  */
849
850 ppl_dimension_type
851 psct_scattering_dim_for_loop_depth (poly_bb_p pbb, graphite_dim_t loop_depth)
852 {
853   ppl_const_Constraint_System_t pcs;
854   ppl_Constraint_System_const_iterator_t cit, cend;
855   ppl_const_Constraint_t cstr;
856   ppl_Polyhedron_t ph = PBB_TRANSFORMED_SCATTERING (pbb);
857   ppl_dimension_type iter = psct_iterator_dim (pbb, loop_depth);
858   ppl_Linear_Expression_t expr;
859   ppl_Coefficient_t coef;
860   Value val;
861   graphite_dim_t i;
862
863   value_init (val);
864   ppl_new_Coefficient (&coef);
865   ppl_Polyhedron_get_constraints (ph, &pcs);
866   ppl_new_Constraint_System_const_iterator (&cit);
867   ppl_new_Constraint_System_const_iterator (&cend);
868
869   for (ppl_Constraint_System_begin (pcs, cit),
870          ppl_Constraint_System_end (pcs, cend);
871        !ppl_Constraint_System_const_iterator_equal_test (cit, cend);
872        ppl_Constraint_System_const_iterator_increment (cit))
873     {
874       ppl_Constraint_System_const_iterator_dereference (cit, &cstr);
875       ppl_new_Linear_Expression_from_Constraint (&expr, cstr);
876       ppl_Linear_Expression_coefficient (expr, iter, coef);
877       ppl_Coefficient_to_mpz_t (coef, val);
878
879       if (value_zero_p (val))
880         {
881           ppl_delete_Linear_Expression (expr);
882           continue;
883         }
884
885       for (i = 0; i < pbb_nb_scattering_transform (pbb); i++)
886         {
887           ppl_dimension_type scatter = psct_scattering_dim (pbb, i);
888
889           ppl_Linear_Expression_coefficient (expr, scatter, coef);
890           ppl_Coefficient_to_mpz_t (coef, val);
891
892           if (value_notzero_p (val))
893             {
894               value_clear (val);
895               ppl_delete_Linear_Expression (expr);
896               ppl_delete_Coefficient (coef);
897               ppl_delete_Constraint_System_const_iterator (cit);
898               ppl_delete_Constraint_System_const_iterator (cend);
899
900               return scatter;
901             }
902         }
903     }
904
905   gcc_unreachable ();
906 }
907
908 /* Returns the number of iterations NITER of the loop around PBB at
909    depth LOOP_DEPTH.  */
910
911 void
912 pbb_number_of_iterations (poly_bb_p pbb,
913                           graphite_dim_t loop_depth,
914                           Value niter)
915 {
916   ppl_Linear_Expression_t le;
917   ppl_dimension_type dim;
918
919   ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PBB_DOMAIN (pbb), &dim);
920   ppl_new_Linear_Expression_with_dimension (&le, dim);
921   ppl_set_coef (le, pbb_iterator_dim (pbb, loop_depth), 1);
922   value_set_si (niter, -1);
923   ppl_max_for_le_pointset (PBB_DOMAIN (pbb), le, niter);
924   ppl_delete_Linear_Expression (le);
925 }
926
927 /* Returns the number of iterations NITER of the loop around PBB at
928    time(scattering) dimension TIME_DEPTH.  */
929
930 void
931 pbb_number_of_iterations_at_time (poly_bb_p pbb,
932                                   graphite_dim_t time_depth,
933                                   Value niter)
934 {
935   ppl_Pointset_Powerset_C_Polyhedron_t ext_domain, sctr;
936   ppl_Linear_Expression_t le;
937   ppl_dimension_type dim;
938
939   /* Takes together domain and scattering polyhedrons, and composes
940      them into the bigger polyhedron that has the following format:
941
942      t0..t_{n-1} | l0..l_{nlcl-1} | i0..i_{niter-1} | g0..g_{nparm-1}
943
944      where
945      | t0..t_{n-1} are time dimensions (scattering dimensions)
946      | l0..l_{nclc-1} are local variables in scattering function
947      | i0..i_{niter-1} are original iteration variables
948      | g0..g_{nparam-1} are global parameters.  */
949
950   ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&sctr,
951       PBB_TRANSFORMED_SCATTERING (pbb));
952
953   /* Extend the iteration domain with the scattering dimensions:
954      0..0 | 0..0 | i0..i_{niter-1} | g0..g_{nparm-1}.   */
955   ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
956     (&ext_domain, PBB_DOMAIN (pbb));
957   ppl_insert_dimensions_pointset (ext_domain, 0,
958                                   pbb_nb_scattering_transform (pbb)
959                                   + pbb_nb_local_vars (pbb));
960
961   /* Add to sctr the extended domain.  */
962   ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (sctr, ext_domain);
963
964   /* Extract the number of iterations.  */
965   ppl_Pointset_Powerset_C_Polyhedron_space_dimension (sctr, &dim);
966   ppl_new_Linear_Expression_with_dimension (&le, dim);
967   ppl_set_coef (le, time_depth, 1);
968   value_set_si (niter, -1);
969   ppl_max_for_le_pointset (sctr, le, niter);
970
971   ppl_delete_Linear_Expression (le);
972   ppl_delete_Pointset_Powerset_C_Polyhedron (sctr);
973   ppl_delete_Pointset_Powerset_C_Polyhedron (ext_domain);
974 }
975
976 /* Translates LOOP to LST.  */
977
978 static lst_p
979 loop_to_lst (loop_p loop, VEC (poly_bb_p, heap) *bbs, int *i)
980 {
981   poly_bb_p pbb;
982   VEC (lst_p, heap) *seq = VEC_alloc (lst_p, heap, 5);
983
984   for (; VEC_iterate (poly_bb_p, bbs, *i, pbb); (*i)++)
985     {
986       lst_p stmt;
987       basic_block bb = GBB_BB (PBB_BLACK_BOX (pbb));
988
989       if (bb->loop_father == loop)
990         stmt = new_lst_stmt (pbb);
991       else if (flow_bb_inside_loop_p (loop, bb))
992         {
993           loop_p next = loop->inner;
994
995           while (next && !flow_bb_inside_loop_p (next, bb))
996             next = next->next;
997
998           stmt = loop_to_lst (next, bbs, i);
999         }
1000       else
1001         {
1002           (*i)--;
1003           return new_lst_loop (seq);
1004         }
1005
1006       VEC_safe_push (lst_p, heap, seq, stmt);
1007     }
1008
1009   return new_lst_loop (seq);
1010 }
1011
1012 /* Reads the original scattering of the SCOP and returns an LST
1013    representing it.  */
1014
1015 void
1016 scop_to_lst (scop_p scop)
1017 {
1018   lst_p res;
1019   int i, n = VEC_length (poly_bb_p, SCOP_BBS (scop));
1020   VEC (lst_p, heap) *seq = VEC_alloc (lst_p, heap, 5);
1021   sese region = SCOP_REGION (scop);
1022
1023   for (i = 0; i < n; i++)
1024     {
1025       poly_bb_p pbb = VEC_index (poly_bb_p, SCOP_BBS (scop), i);
1026       loop_p loop = outermost_loop_in_sese (region, GBB_BB (PBB_BLACK_BOX (pbb)));
1027
1028       if (loop_in_sese_p (loop, region))
1029         res = loop_to_lst (loop, SCOP_BBS (scop), &i);
1030       else
1031         res = new_lst_stmt (pbb);
1032
1033       VEC_safe_push (lst_p, heap, seq, res);
1034     }
1035
1036   res = new_lst_loop (seq);
1037   SCOP_ORIGINAL_SCHEDULE (scop) = res;
1038   SCOP_TRANSFORMED_SCHEDULE (scop) = copy_lst (res);
1039 }
1040
1041 /* Print to FILE on a new line COLUMN white spaces.  */
1042
1043 static void
1044 lst_indent_to (FILE *file, int column)
1045 {
1046   int i;
1047
1048   if (column > 0)
1049     fprintf (file, "\n#");
1050
1051   for (i = 0; i < column; i++)
1052     fprintf (file, " ");
1053 }
1054
1055 /* Print LST to FILE with INDENT spaces of indentation.  */
1056
1057 void
1058 print_lst (FILE *file, lst_p lst, int indent)
1059 {
1060   if (!lst)
1061     return;
1062
1063   lst_indent_to (file, indent);
1064
1065   if (LST_LOOP_P (lst))
1066     {
1067       int i;
1068       lst_p l;
1069
1070       if (LST_LOOP_FATHER (lst))
1071         fprintf (file, "%d (loop", lst_dewey_number (lst));
1072       else
1073         fprintf (file, "#(root");
1074
1075       for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
1076         print_lst (file, l, indent + 2);
1077
1078       fprintf (file, ")");
1079     }
1080   else
1081     fprintf (file, "%d stmt_%d", lst_dewey_number (lst), pbb_index (LST_PBB (lst)));
1082 }
1083
1084 /* Print LST to STDERR.  */
1085
1086 void
1087 debug_lst (lst_p lst)
1088 {
1089   print_lst (stderr, lst, 0);
1090 }
1091
1092 /* Pretty print to FILE the loop statement tree LST in DOT format.  */
1093
1094 static void
1095 dot_lst_1 (FILE *file, lst_p lst)
1096 {
1097   if (!lst)
1098     return;
1099
1100   if (LST_LOOP_P (lst))
1101     {
1102       int i;
1103       lst_p l;
1104
1105       if (!LST_LOOP_FATHER (lst))
1106         fprintf (file, "L -> L_%d_%d\n",
1107                  lst_depth (lst),
1108                  lst_dewey_number (lst));
1109       else
1110         fprintf (file, "L_%d_%d -> L_%d_%d\n",
1111                  lst_depth (LST_LOOP_FATHER (lst)),
1112                  lst_dewey_number (LST_LOOP_FATHER (lst)),
1113                  lst_depth (lst),
1114                  lst_dewey_number (lst));
1115
1116       for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
1117         dot_lst_1 (file, l);
1118     }
1119
1120   else
1121     fprintf (file, "L_%d_%d -> S_%d\n",
1122              lst_depth (LST_LOOP_FATHER (lst)),
1123              lst_dewey_number (LST_LOOP_FATHER (lst)),
1124              pbb_index (LST_PBB (lst)));
1125
1126 }
1127
1128 /* Display the LST using dotty.  */
1129
1130 void
1131 dot_lst (lst_p lst)
1132 {
1133   /* When debugging, enable the following code.  This cannot be used
1134      in production compilers because it calls "system".  */
1135 #if 0
1136   int x;
1137   FILE *stream = fopen ("/tmp/lst.dot", "w");
1138   gcc_assert (stream);
1139
1140   fputs ("digraph all {\n", stream);
1141   dot_lst_1 (stream, lst);
1142   fputs ("}\n\n", stream);
1143   fclose (stream);
1144
1145   x = system ("dotty /tmp/lst.dot");
1146 #else
1147   fputs ("digraph all {\n", stderr);
1148   dot_lst_1 (stderr, lst);
1149   fputs ("}\n\n", stderr);
1150
1151 #endif
1152 }
1153
1154 #endif
1155