Mercurial > hg > CbC > CbC_gcc

comparison gcc/graphite-poly.c @ 55:77e2b8dfacca gcc-4.4.5

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