OSDN Git Service

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