OSDN Git Service

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