Don't crash declaring a function named "_".
[gcc.git] / gcc / graphite-poly.c
1 /* Graphite polyhedral representation.
2 Copyright (C) 2009, 2010 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 "diagnostic-core.h"
25 #include "tree-flow.h"
26 #include "tree-dump.h"
27 #include "gimple-pretty-print.h"
28 #include "cfgloop.h"
29 #include "tree-chrec.h"
30 #include "tree-data-ref.h"
31 #include "tree-scalar-evolution.h"
32 #include "sese.h"
33
34 #ifdef HAVE_cloog
35 #include "ppl_c.h"
36 #include "graphite-ppl.h"
37 #include "graphite-poly.h"
38 #include "graphite-dependences.h"
39 #include "graphite-cloog-util.h"
40
41 #define OPENSCOP_MAX_STRING 256
42
43 /* Return the maximal loop depth in SCOP. */
44
45 int
46 scop_max_loop_depth (scop_p scop)
47 {
48 int i;
49 poly_bb_p pbb;
50 int max_nb_loops = 0;
51
52 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
53 {
54 int nb_loops = pbb_dim_iter_domain (pbb);
55 if (max_nb_loops < nb_loops)
56 max_nb_loops = nb_loops;
57 }
58
59 return max_nb_loops;
60 }
61
62 /* Extend the scattering matrix of PBB to MAX_SCATTERING scattering
63 dimensions. */
64
65 static void
66 extend_scattering (poly_bb_p pbb, int max_scattering)
67 {
68 ppl_dimension_type nb_old_dims, nb_new_dims;
69 int nb_added_dims, i;
70 ppl_Coefficient_t coef;
71 mpz_t one;
72
73 nb_added_dims = max_scattering - pbb_nb_scattering_transform (pbb);
74 mpz_init (one);
75 mpz_set_si (one, 1);
76 ppl_new_Coefficient (&coef);
77 ppl_assign_Coefficient_from_mpz_t (coef, one);
78
79 gcc_assert (nb_added_dims >= 0);
80
81 nb_old_dims = pbb_nb_scattering_transform (pbb) + pbb_dim_iter_domain (pbb)
82 + scop_nb_params (PBB_SCOP (pbb));
83 nb_new_dims = nb_old_dims + nb_added_dims;
84
85 ppl_insert_dimensions (PBB_TRANSFORMED_SCATTERING (pbb),
86 pbb_nb_scattering_transform (pbb), nb_added_dims);
87 PBB_NB_SCATTERING_TRANSFORM (pbb) += nb_added_dims;
88
89 /* Add identity matrix for the added dimensions. */
90 for (i = max_scattering - nb_added_dims; i < max_scattering; i++)
91 {
92 ppl_Constraint_t cstr;
93 ppl_Linear_Expression_t expr;
94
95 ppl_new_Linear_Expression_with_dimension (&expr, nb_new_dims);
96 ppl_Linear_Expression_add_to_coefficient (expr, i, coef);
97 ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_EQUAL);
98 ppl_Polyhedron_add_constraint (PBB_TRANSFORMED_SCATTERING (pbb), cstr);
99 ppl_delete_Constraint (cstr);
100 ppl_delete_Linear_Expression (expr);
101 }
102
103 ppl_delete_Coefficient (coef);
104 mpz_clear (one);
105 }
106
107 /* All scattering matrices in SCOP will have the same number of scattering
108 dimensions. */
109
110 int
111 unify_scattering_dimensions (scop_p scop)
112 {
113 int i;
114 poly_bb_p pbb;
115 graphite_dim_t max_scattering = 0;
116
117 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
118 max_scattering = MAX (pbb_nb_scattering_transform (pbb), max_scattering);
119
120 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
121 extend_scattering (pbb, max_scattering);
122
123 return max_scattering;
124 }
125
126 /* Print to FILE the pdr PH in OpenScop format. NB_SUBSCRIPTS is the number
127 of subscripts in PH, ALIAS_SET_DIM is the dimension of the alias set and
128 NB_PARAMS is the number of parameters in PH. */
129
130 static void
131 openscop_print_pdr_polyhedron (FILE *file, ppl_const_Polyhedron_t ph,
132 int nb_subscripts, int alias_set_dimension,
133 int nb_params)
134 {
135 int input, locals, output;
136 ppl_dimension_type alias_set_dim = (ppl_dimension_type) alias_set_dimension;
137 ppl_dimension_type sub_dim_last = alias_set_dim + nb_subscripts;
138 ppl_dimension_type *map, i, ph_space_dim = sub_dim_last + 1;
139 ppl_Polyhedron_t pph;
140
141 ppl_new_C_Polyhedron_from_C_Polyhedron (&pph, ph);
142
143 map = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, ph_space_dim);
144
145 for (i = 0; i < alias_set_dim - 1; i++)
146 map[i] = nb_subscripts + 1 + i;
147
148 for (i = alias_set_dim - 1; i < sub_dim_last; i++)
149 map[i] = i - alias_set_dim + 1;
150
151 ppl_Polyhedron_map_space_dimensions (pph, map, ph_space_dim - 1);
152
153 locals = 0;
154 input = alias_set_dim - nb_params - 1;
155
156 /* According to OpenScop specification, the alias set column is a part of
157 the output columns. */
158 output = nb_subscripts + 1;
159
160 openscop_print_polyhedron_matrix (file, pph, output, input, locals, nb_params);
161 }
162
163 /* Print to FILE the powerset PDR. NB_SUBSCRIPTS is the number of subscripts
164 in PDR, ALIAS_SET_DIM is the dimension of the alias set in PDR and
165 NB_PARAMS is the number of parameters in PDR. */
166
167 static void
168 openscop_print_pdr_powerset (FILE *file,
169 ppl_Pointset_Powerset_C_Polyhedron_t ps,
170 int nb_subscripts,
171 int alias_set_dim,
172 int nb_params)
173 {
174 size_t nb_disjuncts;
175 ppl_Pointset_Powerset_C_Polyhedron_iterator_t it, end;
176
177 ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&it);
178 ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&end);
179
180 ppl_Pointset_Powerset_C_Polyhedron_size (ps, &nb_disjuncts);
181 fprintf (file, "%d\n", (int) nb_disjuncts);
182
183 for (ppl_Pointset_Powerset_C_Polyhedron_iterator_begin (ps, it),
184 ppl_Pointset_Powerset_C_Polyhedron_iterator_end (ps, end);
185 !ppl_Pointset_Powerset_C_Polyhedron_iterator_equal_test (it, end);
186 ppl_Pointset_Powerset_C_Polyhedron_iterator_increment (it))
187 {
188 ppl_const_Polyhedron_t ph;
189
190 ppl_Pointset_Powerset_C_Polyhedron_iterator_dereference (it, &ph);
191 openscop_print_pdr_polyhedron (file, ph, nb_subscripts, alias_set_dim,
192 nb_params);
193 }
194
195 ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (it);
196 ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (end);
197 }
198
199 /* Print to FILE the powerset PS in its OpenScop matrix form. */
200
201 static void
202 openscop_print_powerset_matrix (FILE *file,
203 ppl_Pointset_Powerset_C_Polyhedron_t ps,
204 int output, int input, int locals,
205 int params)
206 {
207 size_t nb_disjuncts;
208 ppl_Pointset_Powerset_C_Polyhedron_iterator_t it, end;
209
210 ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&it);
211 ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&end);
212
213 ppl_Pointset_Powerset_C_Polyhedron_size (ps, &nb_disjuncts);
214 fprintf (file, "%d\n", (int) nb_disjuncts);
215
216 for (ppl_Pointset_Powerset_C_Polyhedron_iterator_begin (ps, it),
217 ppl_Pointset_Powerset_C_Polyhedron_iterator_end (ps, end);
218 !ppl_Pointset_Powerset_C_Polyhedron_iterator_equal_test (it, end);
219 ppl_Pointset_Powerset_C_Polyhedron_iterator_increment (it))
220 {
221 ppl_const_Polyhedron_t ph;
222
223 ppl_Pointset_Powerset_C_Polyhedron_iterator_dereference (it, &ph);
224 openscop_print_polyhedron_matrix (file, ph, output, input, locals,
225 params);
226 }
227
228 ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (it);
229 ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (end);
230 }
231
232 /* Prints to FILE the scattering function of PBB in OpenScop format, at some
233 VERBOSITY level. */
234
235 static void
236 openscop_print_scattering_function_1 (FILE *file, poly_bb_p pbb, int verbosity)
237 {
238 graphite_dim_t i;
239 ppl_const_Polyhedron_t ph;
240
241 if (verbosity > 0)
242 {
243 fprintf (file, "# scattering bb_%d (\n", pbb_index (pbb));
244 fprintf (file, "#eq");
245
246 for (i = 0; i < pbb_nb_scattering_transform (pbb); i++)
247 fprintf (file, " s%d", (int) i);
248
249 for (i = 0; i < pbb_nb_local_vars (pbb); i++)
250 fprintf (file, " lv%d", (int) i);
251
252 for (i = 0; i < pbb_dim_iter_domain (pbb); i++)
253 fprintf (file, " i%d", (int) i);
254
255 for (i = 0; i < pbb_nb_params (pbb); i++)
256 fprintf (file, " p%d", (int) i);
257
258 fprintf (file, " cst\n");
259 }
260
261 /* Number of disjunct components. Remove this when
262 PBB_TRANSFORMED_SCATTERING will be a pointset_powerset. */
263 fprintf (file, "1\n");
264
265 ph = PBB_TRANSFORMED_SCATTERING (pbb)
266 ? PBB_TRANSFORMED_SCATTERING (pbb)
267 : PBB_ORIGINAL_SCATTERING (pbb);
268
269 openscop_print_polyhedron_matrix (file, ph,
270 pbb_nb_scattering_transform (pbb),
271 pbb_dim_iter_domain (pbb),
272 pbb_nb_local_vars (pbb),
273 pbb_nb_params (pbb));
274
275 if (verbosity > 0)
276 fprintf (file, "#)\n");
277 }
278
279 /* Prints to FILE the scattering function of PBB, at some VERBOSITY
280 level. */
281
282 static void
283 print_scattering_function_1 (FILE *file, poly_bb_p pbb, int verbosity)
284 {
285 graphite_dim_t i;
286
287 if (verbosity > 0)
288 {
289 fprintf (file, "# scattering bb_%d (\n", pbb_index (pbb));
290 fprintf (file, "#eq");
291
292 for (i = 0; i < pbb_nb_scattering_transform (pbb); i++)
293 fprintf (file, " s%d", (int) i);
294
295 for (i = 0; i < pbb_nb_local_vars (pbb); i++)
296 fprintf (file, " lv%d", (int) i);
297
298 for (i = 0; i < pbb_dim_iter_domain (pbb); i++)
299 fprintf (file, " i%d", (int) i);
300
301 for (i = 0; i < pbb_nb_params (pbb); i++)
302 fprintf (file, " p%d", (int) i);
303
304 fprintf (file, " cst\n");
305 }
306
307 /* Number of disjunct components. Remove this when
308 PBB_TRANSFORMED_SCATTERING will be a pointset_powerset. */
309 fprintf (file, "1\n");
310 ppl_print_polyhedron_matrix (file, PBB_TRANSFORMED_SCATTERING (pbb)
311 ? PBB_TRANSFORMED_SCATTERING (pbb)
312 : PBB_ORIGINAL_SCATTERING (pbb));
313
314 if (verbosity > 0)
315 fprintf (file, "#)\n");
316 }
317
318 /* Prints to FILE the scattering function of PBB, at some VERBOSITY
319 level. */
320
321 void
322 print_scattering_function (FILE *file, poly_bb_p pbb, int verbosity)
323 {
324 if (!PBB_TRANSFORMED (pbb))
325 return;
326
327 if (PBB_TRANSFORMED_SCATTERING (pbb)
328 || PBB_ORIGINAL_SCATTERING (pbb))
329 {
330 if (verbosity > 0)
331 fprintf (file, "# Scattering function is provided\n");
332
333 fprintf (file, "1\n");
334 }
335 else
336 {
337 if (verbosity > 0)
338 fprintf (file, "# Scattering function is not provided\n");
339
340 fprintf (file, "0\n");
341 return;
342 }
343
344 openscop_print_scattering_function_1 (file, pbb, verbosity);
345
346 if (verbosity > 0)
347 fprintf (file, "# Scattering names are not provided\n");
348
349 fprintf (file, "0\n");
350
351 }
352
353 /* Prints to FILE the iteration domain of PBB, at some VERBOSITY
354 level. */
355
356 void
357 print_iteration_domain (FILE *file, poly_bb_p pbb, int verbosity)
358 {
359 print_pbb_domain (file, pbb, verbosity);
360 }
361
362 /* Prints to FILE the scattering functions of every PBB of SCOP. */
363
364 void
365 print_scattering_functions (FILE *file, scop_p scop, int verbosity)
366 {
367 int i;
368 poly_bb_p pbb;
369
370 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
371 print_scattering_function (file, pbb, verbosity);
372 }
373
374 /* Prints to FILE the iteration domains of every PBB of SCOP, at some
375 VERBOSITY level. */
376
377 void
378 print_iteration_domains (FILE *file, scop_p scop, int verbosity)
379 {
380 int i;
381 poly_bb_p pbb;
382
383 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
384 print_iteration_domain (file, pbb, verbosity);
385 }
386
387 /* Prints to STDERR the scattering function of PBB, at some VERBOSITY
388 level. */
389
390 DEBUG_FUNCTION void
391 debug_scattering_function (poly_bb_p pbb, int verbosity)
392 {
393 print_scattering_function (stderr, pbb, verbosity);
394 }
395
396 /* Prints to STDERR the iteration domain of PBB, at some VERBOSITY
397 level. */
398
399 DEBUG_FUNCTION void
400 debug_iteration_domain (poly_bb_p pbb, int verbosity)
401 {
402 print_iteration_domain (stderr, pbb, verbosity);
403 }
404
405 /* Prints to STDERR the scattering functions of every PBB of SCOP, at
406 some VERBOSITY level. */
407
408 DEBUG_FUNCTION void
409 debug_scattering_functions (scop_p scop, int verbosity)
410 {
411 print_scattering_functions (stderr, scop, verbosity);
412 }
413
414 /* Prints to STDERR the iteration domains of every PBB of SCOP, at
415 some VERBOSITY level. */
416
417 DEBUG_FUNCTION void
418 debug_iteration_domains (scop_p scop, int verbosity)
419 {
420 print_iteration_domains (stderr, scop, verbosity);
421 }
422
423 /* Read N integer from FILE. */
424
425 int *
426 openscop_read_N_int (FILE *file, int N)
427 {
428 char s[OPENSCOP_MAX_STRING];
429 char *str;
430 int i, *res = (int *) xmalloc (OPENSCOP_MAX_STRING * sizeof (int));
431
432 /* Skip blank and commented lines. */
433 while (fgets (s, sizeof s, file) == (char *) 0
434 || s[0] == '#'
435 || ISSPACE (s[0]))
436 ;
437
438 str = s;
439
440 for (i = 0; i < N; i++)
441 {
442 sscanf (str, "%d", &res[i]);
443
444 /* Jump the integer that was read. */
445 while ((*str) && !ISSPACE (*str) && (*str != '#'))
446 str++;
447
448 /* Jump spaces. */
449 while ((*str) && ISSPACE (*str) && (*str != '#'))
450 str++;
451 }
452
453 return res;
454 }
455
456 /* Read one integer from FILE. */
457
458 static int
459 openscop_read_one_int (FILE *file)
460 {
461 int *x = openscop_read_N_int (file, 1);
462 int res = *x;
463
464 free (x);
465 return res;
466 }
467
468 /* Read N string from FILE. */
469
470 static char *
471 openscop_read_N_string (FILE *file, int N)
472 {
473 int count, i;
474 char str[OPENSCOP_MAX_STRING];
475 char *tmp = (char *) xmalloc (sizeof (char) * OPENSCOP_MAX_STRING);
476 char *s = NULL;
477
478 /* Skip blank and commented lines. */
479 while (fgets (str, sizeof str, file) == (char *) 0
480 || str[0] == '#'
481 || ISSPACE (str[0]))
482 ;
483
484 s = str;
485 count = 0;
486
487 for (i = 0; i < N; i++)
488 {
489 /* Read the first word. */
490 for (; (*s) && (!ISSPACE (*s)) && (*s != '#'); ++count)
491 tmp[count] = *(s++);
492
493 tmp[count] = ' ';
494 count++;
495
496 /* Jump spaces. */
497 while ((*s) && ISSPACE (*s) && (*s != '#'))
498 s++;
499 }
500
501 tmp[count-1] = '\0';
502
503 return tmp;
504 }
505
506 /* Read one string from FILE. */
507
508 static char *
509 openscop_read_one_string (FILE *file)
510 {
511 return openscop_read_N_string (file, 1);
512 }
513
514 /* Read from FILE the powerset PS in its OpenScop matrix form. OUTPUT is the
515 number of output dimensions, INPUT is the number of input dimensions,
516 LOCALS is the number of existentially quantified variables and PARAMS is
517 the number of parameters. */
518
519 static void
520 openscop_read_powerset_matrix (FILE *file,
521 ppl_Pointset_Powerset_C_Polyhedron_t *ps,
522 int *output, int *input, int *locals,
523 int *params)
524 {
525 int nb_disjuncts, i;
526
527 nb_disjuncts = openscop_read_one_int (file);
528
529 for (i = 0; i < nb_disjuncts; i++)
530 {
531 ppl_Polyhedron_t ph;
532
533 openscop_read_polyhedron_matrix (file, &ph, output, input, locals,
534 params);
535 if (!ph)
536 *ps = NULL;
537 else if (i == 0)
538 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (ps, ph);
539 else
540 ppl_Pointset_Powerset_C_Polyhedron_add_disjunct (*ps, ph);
541 }
542 }
543
544 /* Read a scattering function from FILE and save it to PBB. Return whether
545 the scattering function was provided or not. */
546
547 static bool
548 graphite_read_scatt (FILE *file, poly_bb_p pbb)
549 {
550 bool scattering_provided = false;
551 int output, input, locals, params;
552 ppl_Polyhedron_t newp;
553
554 if (openscop_read_one_int (file) > 0)
555 {
556 /* Read number of disjunct components. */
557 openscop_read_one_int (file);
558
559 /* Read scattering function. */
560 openscop_read_polyhedron_matrix (file, &newp, &output, &input,
561 &locals, &params);
562 store_scattering (PBB_SCOP (pbb));
563 PBB_TRANSFORMED (pbb) = poly_scattering_new ();
564 PBB_TRANSFORMED_SCATTERING (pbb) = newp;
565 PBB_NB_LOCAL_VARIABLES (pbb) = locals;
566
567 /* New scattering dimension. */
568 PBB_NB_SCATTERING_TRANSFORM (pbb) = output;
569
570 scattering_provided = true;
571 }
572
573 return scattering_provided;
574 }
575
576 /* Read a scop file. Return true if the scop is transformed. */
577
578 static bool
579 graphite_read_scop_file (FILE *file, scop_p scop)
580 {
581 char *tmp, *language;
582 size_t i, j, nb_statements, nbr, nbw;
583 int input, output, locals, params;
584 ppl_Pointset_Powerset_C_Polyhedron_t ps;
585 poly_bb_p pbb;
586 bool transform_done = false;
587
588 /* Ensure that the file is in OpenScop format. */
589 tmp = openscop_read_N_string (file, 2);
590
591 if (strcmp (tmp, "SCoP 1"))
592 {
593 error ("the file is not in OpenScop format");
594 return false;
595 }
596
597 free (tmp);
598
599 /* Read the language. */
600 language = openscop_read_one_string (file);
601
602 if (strcmp (language, "Gimple"))
603 {
604 error ("the language is not recognized");
605 return false;
606 }
607
608 free (language);
609
610 /* Read the context but do not use it. */
611 openscop_read_powerset_matrix (file, &ps, &input, &output, &locals, &params);
612
613 if ((size_t) params != scop->nb_params)
614 {
615 error ("parameters number in the scop file is different from the"
616 " internal scop parameter number");
617 return false;
618 }
619
620 /* Read parameter names if provided. */
621 if (openscop_read_one_int (file))
622 openscop_read_N_string (file, scop->nb_params);
623
624 nb_statements = openscop_read_one_int (file);
625
626 if (nb_statements != VEC_length (poly_bb_p, SCOP_BBS (scop)))
627 {
628 error ("number of statements in the OpenScop file does not match"
629 " the graphite internal statements number");
630 return false;
631 }
632
633 for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
634 {
635 /* Read iteration domain. */
636 openscop_read_powerset_matrix (file, &ps, &input, &output, &locals,
637 &params);
638
639 /* Read scattering. */
640 transform_done = graphite_read_scatt (file, pbb);
641
642 /* Scattering names. */
643 openscop_read_one_int (file);
644
645 /* Read access functions. */
646 if (openscop_read_one_int (file) > 0)
647 {
648 nbr = openscop_read_one_int (file);
649
650 /* Read access functions. */
651 for (j = 0; j < nbr; j++)
652 openscop_read_powerset_matrix (file, &ps, &input, &output, &locals,
653 &params);
654
655 nbw = openscop_read_one_int (file);
656
657 /* Write access functions. */
658 for (j = 0; j < nbw; j++)
659 openscop_read_powerset_matrix (file, &ps, &input, &output, &locals,
660 &params);
661 }
662
663 /* Statement body. */
664 openscop_read_one_int (file);
665 }
666
667 return transform_done;
668 }
669
670 /* Initialize and return a file that will be used to write a scop. SCOP_NUMBER
671 is a sequential number (identifier) used to differentiate scop files.
672 Examples of the generated file names: dump_base_name.0.graphite,
673 dump_base_name.1.graphite, dump_base_name.2.graphite, etc. */
674
675 static FILE *
676 init_graphite_out_file (int scop_number)
677 {
678 FILE *graphite_out_file;
679 int len = strlen (dump_base_name);
680 char *dumpname = XNEWVEC (char, len + 25);
681 char *s_scop_number = XNEWVEC (char, 15);
682
683 memcpy (dumpname, dump_base_name, len + 1);
684 strip_off_ending (dumpname, len);
685 sprintf (s_scop_number, ".%d", scop_number);
686 strcat (dumpname, s_scop_number);
687 strcat (dumpname, ".graphite");
688 graphite_out_file = fopen (dumpname, "w+b");
689
690 if (graphite_out_file == 0)
691 fatal_error ("can%'t open %s for writing: %m", dumpname);
692
693 free (dumpname);
694
695 return graphite_out_file;
696 }
697
698 /* Open and return a file used for scop reading. SCOP_NUMBER is a sequential
699 number (identifier) used to differentiate scop files. Examples of the
700 generated file names: dump_base_name.0.graphite, dump_base_name.1.graphite,
701 dump_base_name.2.graphite, etc. */
702
703 static FILE *
704 init_graphite_in_file (int scop_number)
705 {
706 FILE *graphite_in_file;
707 int len = strlen (dump_base_name);
708 char *dumpname = XNEWVEC (char, len + 25);
709 char *s_scop_number = XNEWVEC (char, 15);
710
711 memcpy (dumpname, dump_base_name, len + 1);
712 strip_off_ending (dumpname, len);
713 sprintf (s_scop_number, ".%d", scop_number);
714 strcat (dumpname, s_scop_number);
715 strcat (dumpname, ".graphite");
716 graphite_in_file = fopen (dumpname, "r+b");
717
718 if (graphite_in_file == 0)
719 fatal_error ("can%'t open %s for reading: %m", dumpname);
720
721 free (dumpname);
722
723 return graphite_in_file;
724 }
725
726 /* Apply graphite transformations to all the basic blocks of SCOP. */
727
728 bool
729 apply_poly_transforms (scop_p scop)
730 {
731 bool transform_done = false;
732 FILE *graphite_file;
733 static size_t file_scop_number = 0;
734
735 /* This feature is only enabled in the Graphite branch. */
736 if (0)
737 {
738 graphite_file = init_graphite_in_file (file_scop_number);
739 transform_done |= graphite_read_scop_file (graphite_file, scop);
740
741 if (!graphite_legal_transform (scop))
742 fatal_error ("the graphite file read for scop %d does not contain a legal transform",
743 (int) file_scop_number);
744
745 file_scop_number++;
746 }
747
748 /* Generate code even if we did not apply any real transformation.
749 This also allows to check the performance for the identity
750 transformation: GIMPLE -> GRAPHITE -> GIMPLE
751 Keep in mind that CLooG optimizes in control, so the loop structure
752 may change, even if we only use -fgraphite-identity. */
753 if (flag_graphite_identity)
754 transform_done = true;
755
756 if (flag_loop_parallelize_all)
757 transform_done = true;
758
759 if (flag_loop_block)
760 transform_done |= scop_do_block (scop);
761 else
762 {
763 if (flag_loop_strip_mine)
764 transform_done |= scop_do_strip_mine (scop, 0);
765
766 if (flag_loop_interchange)
767 transform_done |= scop_do_interchange (scop);
768 }
769
770 if (flag_loop_flatten)
771 transform_done |= flatten_all_loops (scop);
772
773 /* This feature is only enabled in the Graphite branch. */
774 if (0)
775 {
776 graphite_file = init_graphite_out_file (file_scop_number);
777 print_scop (graphite_file, scop, 1);
778 file_scop_number++;
779 }
780
781 return transform_done;
782 }
783
784 /* Returns true when it PDR1 is a duplicate of PDR2: same PBB, and
785 their ACCESSES, TYPE, and NB_SUBSCRIPTS are the same. */
786
787 static inline bool
788 can_collapse_pdrs (poly_dr_p pdr1, poly_dr_p pdr2)
789 {
790 bool res;
791 ppl_Pointset_Powerset_C_Polyhedron_t af1, af2, diff;
792
793 if (PDR_PBB (pdr1) != PDR_PBB (pdr2)
794 || PDR_NB_SUBSCRIPTS (pdr1) != PDR_NB_SUBSCRIPTS (pdr2)
795 || PDR_TYPE (pdr1) != PDR_TYPE (pdr2))
796 return false;
797
798 af1 = PDR_ACCESSES (pdr1);
799 af2 = PDR_ACCESSES (pdr2);
800 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
801 (&diff, af1);
802 ppl_Pointset_Powerset_C_Polyhedron_difference_assign (diff, af2);
803
804 res = ppl_Pointset_Powerset_C_Polyhedron_is_empty (diff);
805 ppl_delete_Pointset_Powerset_C_Polyhedron (diff);
806 return res;
807 }
808
809 /* Removes duplicated data references in PBB. */
810
811 void
812 pbb_remove_duplicate_pdrs (poly_bb_p pbb)
813 {
814 int i, j;
815 poly_dr_p pdr1, pdr2;
816
817 FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb), i, pdr1)
818 for (j = i + 1; VEC_iterate (poly_dr_p, PBB_DRS (pbb), j, pdr2); j++)
819 if (can_collapse_pdrs (pdr1, pdr2))
820 {
821 PDR_NB_REFS (pdr1) += PDR_NB_REFS (pdr2);
822 free_poly_dr (pdr2);
823 VEC_ordered_remove (poly_dr_p, PBB_DRS (pbb), j);
824 }
825
826 PBB_PDR_DUPLICATES_REMOVED (pbb) = true;
827 }
828
829 /* Create a new polyhedral data reference and add it to PBB. It is
830 defined by its ACCESSES, its TYPE, and the number of subscripts
831 NB_SUBSCRIPTS. */
832
833 void
834 new_poly_dr (poly_bb_p pbb, int dr_base_object_set,
835 ppl_Pointset_Powerset_C_Polyhedron_t accesses,
836 enum poly_dr_type type, void *cdr, graphite_dim_t nb_subscripts)
837 {
838 static int id = 0;
839 poly_dr_p pdr = XNEW (struct poly_dr);
840
841 PDR_ID (pdr) = id++;
842 PDR_BASE_OBJECT_SET (pdr) = dr_base_object_set;
843 PDR_NB_REFS (pdr) = 1;
844 PDR_PBB (pdr) = pbb;
845 PDR_ACCESSES (pdr) = accesses;
846 PDR_TYPE (pdr) = type;
847 PDR_CDR (pdr) = cdr;
848 PDR_NB_SUBSCRIPTS (pdr) = nb_subscripts;
849 VEC_safe_push (poly_dr_p, heap, PBB_DRS (pbb), pdr);
850 }
851
852 /* Free polyhedral data reference PDR. */
853
854 void
855 free_poly_dr (poly_dr_p pdr)
856 {
857 ppl_delete_Pointset_Powerset_C_Polyhedron (PDR_ACCESSES (pdr));
858 XDELETE (pdr);
859 }
860
861 /* Create a new polyhedral black box. */
862
863 poly_bb_p
864 new_poly_bb (scop_p scop, void *black_box)
865 {
866 poly_bb_p pbb = XNEW (struct poly_bb);
867
868 PBB_DOMAIN (pbb) = NULL;
869 PBB_SCOP (pbb) = scop;
870 pbb_set_black_box (pbb, black_box);
871 PBB_TRANSFORMED (pbb) = NULL;
872 PBB_SAVED (pbb) = NULL;
873 PBB_ORIGINAL (pbb) = NULL;
874 PBB_DRS (pbb) = VEC_alloc (poly_dr_p, heap, 3);
875 PBB_IS_REDUCTION (pbb) = false;
876 PBB_PDR_DUPLICATES_REMOVED (pbb) = false;
877 GBB_PBB ((gimple_bb_p) black_box) = pbb;
878
879 return pbb;
880 }
881
882 /* Free polyhedral black box. */
883
884 void
885 free_poly_bb (poly_bb_p pbb)
886 {
887 int i;
888 poly_dr_p pdr;
889
890 ppl_delete_Pointset_Powerset_C_Polyhedron (PBB_DOMAIN (pbb));
891
892 if (PBB_TRANSFORMED (pbb))
893 poly_scattering_free (PBB_TRANSFORMED (pbb));
894
895 if (PBB_SAVED (pbb))
896 poly_scattering_free (PBB_SAVED (pbb));
897
898 if (PBB_ORIGINAL (pbb))
899 poly_scattering_free (PBB_ORIGINAL (pbb));
900
901 if (PBB_DRS (pbb))
902 FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb), i, pdr)
903 free_poly_dr (pdr);
904
905 VEC_free (poly_dr_p, heap, PBB_DRS (pbb));
906 XDELETE (pbb);
907 }
908
909 static void
910 print_pdr_access_layout (FILE *file, poly_bb_p pbb, poly_dr_p pdr)
911 {
912 graphite_dim_t i;
913
914 fprintf (file, "# eq");
915
916 fprintf (file, " alias");
917
918 for (i = 0; i < PDR_NB_SUBSCRIPTS (pdr); i++)
919 fprintf (file, " sub%d", (int) i);
920
921 for (i = 0; i < pbb_dim_iter_domain (pbb); i++)
922 fprintf (file, " i%d", (int) i);
923
924 for (i = 0; i < pbb_nb_params (pbb); i++)
925 fprintf (file, " p%d", (int) i);
926
927 fprintf (file, " cst\n");
928 }
929
930 /* Prints to FILE the polyhedral data reference PDR, at some VERBOSITY
931 level. */
932
933 void
934 print_pdr (FILE *file, poly_dr_p pdr, int verbosity)
935 {
936 int alias_set_dim;
937
938 if (verbosity > 1)
939 {
940 fprintf (file, "# pdr_%d (", PDR_ID (pdr));
941
942 switch (PDR_TYPE (pdr))
943 {
944 case PDR_READ:
945 fprintf (file, "read \n");
946 break;
947
948 case PDR_WRITE:
949 fprintf (file, "write \n");
950 break;
951
952 case PDR_MAY_WRITE:
953 fprintf (file, "may_write \n");
954 break;
955
956 default:
957 gcc_unreachable ();
958 }
959
960 dump_data_reference (file, (data_reference_p) PDR_CDR (pdr));
961 }
962
963 if (verbosity > 0)
964 {
965 fprintf (file, "# data accesses (\n");
966 print_pdr_access_layout (file, PDR_PBB (pdr), pdr);
967 }
968
969 alias_set_dim = pdr_alias_set_dim (pdr) + 1;
970
971 openscop_print_pdr_powerset (file,
972 PDR_ACCESSES (pdr),
973 PDR_NB_SUBSCRIPTS (pdr),
974 alias_set_dim,
975 pbb_nb_params (PDR_PBB (pdr)));
976
977 if (verbosity > 0)
978 fprintf (file, "#)\n");
979
980 if (verbosity > 1)
981 fprintf (file, "#)\n");
982 }
983
984 /* Prints to STDERR the polyhedral data reference PDR, at some
985 VERBOSITY level. */
986
987 DEBUG_FUNCTION void
988 debug_pdr (poly_dr_p pdr, int verbosity)
989 {
990 print_pdr (stderr, pdr, verbosity);
991 }
992
993 /* Creates a new SCOP containing REGION. */
994
995 scop_p
996 new_scop (void *region)
997 {
998 scop_p scop = XNEW (struct scop);
999
1000 SCOP_CONTEXT (scop) = NULL;
1001 scop_set_region (scop, region);
1002 SCOP_BBS (scop) = VEC_alloc (poly_bb_p, heap, 3);
1003 SCOP_ORIGINAL_PDDRS (scop) = htab_create (10, hash_poly_ddr_p,
1004 eq_poly_ddr_p, free_poly_ddr);
1005 SCOP_ORIGINAL_SCHEDULE (scop) = NULL;
1006 SCOP_TRANSFORMED_SCHEDULE (scop) = NULL;
1007 SCOP_SAVED_SCHEDULE (scop) = NULL;
1008 POLY_SCOP_P (scop) = false;
1009
1010 return scop;
1011 }
1012
1013 /* Deletes SCOP. */
1014
1015 void
1016 free_scop (scop_p scop)
1017 {
1018 int i;
1019 poly_bb_p pbb;
1020
1021 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
1022 free_poly_bb (pbb);
1023
1024 VEC_free (poly_bb_p, heap, SCOP_BBS (scop));
1025
1026 if (SCOP_CONTEXT (scop))
1027 ppl_delete_Pointset_Powerset_C_Polyhedron (SCOP_CONTEXT (scop));
1028
1029 htab_delete (SCOP_ORIGINAL_PDDRS (scop));
1030 free_lst (SCOP_ORIGINAL_SCHEDULE (scop));
1031 free_lst (SCOP_TRANSFORMED_SCHEDULE (scop));
1032 free_lst (SCOP_SAVED_SCHEDULE (scop));
1033 XDELETE (scop);
1034 }
1035
1036 /* Print to FILE the domain of PBB in OpenScop format, at some VERBOSITY
1037 level. */
1038
1039 static void
1040 openscop_print_pbb_domain (FILE *file, poly_bb_p pbb, int verbosity)
1041 {
1042 graphite_dim_t i;
1043 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
1044
1045 if (!PBB_DOMAIN (pbb))
1046 return;
1047
1048 if (verbosity > 0)
1049 {
1050 fprintf (file, "\n# Iteration domain of bb_%d (\n", GBB_BB (gbb)->index);
1051 fprintf (file, "#eq");
1052
1053 for (i = 0; i < pbb_dim_iter_domain (pbb); i++)
1054 fprintf (file, " i%d", (int) i);
1055
1056 for (i = 0; i < pbb_nb_params (pbb); i++)
1057 fprintf (file, " p%d", (int) i);
1058
1059 fprintf (file, " cst\n");
1060 }
1061
1062 if (PBB_DOMAIN (pbb))
1063 openscop_print_powerset_matrix (file, PBB_DOMAIN (pbb),
1064 pbb_dim_iter_domain (pbb),
1065 0,
1066 0,
1067 pbb_nb_params (pbb));
1068 else
1069 fprintf (file, "0\n");
1070
1071 if (verbosity > 0)
1072 fprintf (file, "#)\n");
1073 }
1074
1075 /* Print to FILE the domain of PBB, at some VERBOSITY level. */
1076
1077 void
1078 print_pbb_domain (FILE *file, poly_bb_p pbb, int verbosity)
1079 {
1080 graphite_dim_t i;
1081 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
1082
1083 if (!PBB_DOMAIN (pbb))
1084 return;
1085
1086 if (verbosity > 0)
1087 {
1088 fprintf (file, "# Iteration domain of bb_%d (\n", GBB_BB (gbb)->index);
1089 fprintf (file, "# eq");
1090
1091 for (i = 0; i < pbb_dim_iter_domain (pbb); i++)
1092 fprintf (file, " i%d", (int) i);
1093
1094 for (i = 0; i < pbb_nb_params (pbb); i++)
1095 fprintf (file, " p%d", (int) i);
1096
1097 fprintf (file, " cst\n");
1098 }
1099
1100 if (PBB_DOMAIN (pbb))
1101 ppl_print_powerset_matrix (file, PBB_DOMAIN (pbb));
1102 else
1103 fprintf (file, "0\n");
1104
1105 if (verbosity > 0)
1106 fprintf (file, "#)\n");
1107 }
1108
1109 /* Dump the cases of a graphite basic block GBB on FILE. */
1110
1111 static void
1112 dump_gbb_cases (FILE *file, gimple_bb_p gbb)
1113 {
1114 int i;
1115 gimple stmt;
1116 VEC (gimple, heap) *cases;
1117
1118 if (!gbb)
1119 return;
1120
1121 cases = GBB_CONDITION_CASES (gbb);
1122 if (VEC_empty (gimple, cases))
1123 return;
1124
1125 fprintf (file, "# cases bb_%d (\n", GBB_BB (gbb)->index);
1126
1127 FOR_EACH_VEC_ELT (gimple, cases, i, stmt)
1128 {
1129 fprintf (file, "# ");
1130 print_gimple_stmt (file, stmt, 0, 0);
1131 }
1132
1133 fprintf (file, "#)\n");
1134 }
1135
1136 /* Dump conditions of a graphite basic block GBB on FILE. */
1137
1138 static void
1139 dump_gbb_conditions (FILE *file, gimple_bb_p gbb)
1140 {
1141 int i;
1142 gimple stmt;
1143 VEC (gimple, heap) *conditions;
1144
1145 if (!gbb)
1146 return;
1147
1148 conditions = GBB_CONDITIONS (gbb);
1149 if (VEC_empty (gimple, conditions))
1150 return;
1151
1152 fprintf (file, "# conditions bb_%d (\n", GBB_BB (gbb)->index);
1153
1154 FOR_EACH_VEC_ELT (gimple, conditions, i, stmt)
1155 {
1156 fprintf (file, "# ");
1157 print_gimple_stmt (file, stmt, 0, 0);
1158 }
1159
1160 fprintf (file, "#)\n");
1161 }
1162
1163 /* Print to FILE all the data references of PBB, at some VERBOSITY
1164 level. */
1165
1166 void
1167 print_pdrs (FILE *file, poly_bb_p pbb, int verbosity)
1168 {
1169 int i;
1170 poly_dr_p pdr;
1171 int nb_reads = 0;
1172 int nb_writes = 0;
1173
1174 if (VEC_length (poly_dr_p, PBB_DRS (pbb)) == 0)
1175 {
1176 if (verbosity > 0)
1177 fprintf (file, "# Access informations are not provided\n");\
1178 fprintf (file, "0\n");
1179 return;
1180 }
1181
1182 if (verbosity > 1)
1183 fprintf (file, "# Data references (\n");
1184
1185 if (verbosity > 0)
1186 fprintf (file, "# Access informations are provided\n");
1187 fprintf (file, "1\n");
1188
1189 FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb), i, pdr)
1190 if (PDR_TYPE (pdr) == PDR_READ)
1191 nb_reads++;
1192 else
1193 nb_writes++;
1194
1195 if (verbosity > 1)
1196 fprintf (file, "# Read data references (\n");
1197
1198 if (verbosity > 0)
1199 fprintf (file, "# Read access informations\n");
1200 fprintf (file, "%d\n", nb_reads);
1201
1202 FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb), i, pdr)
1203 if (PDR_TYPE (pdr) == PDR_READ)
1204 print_pdr (file, pdr, verbosity);
1205
1206 if (verbosity > 1)
1207 fprintf (file, "#)\n");
1208
1209 if (verbosity > 1)
1210 fprintf (file, "# Write data references (\n");
1211
1212 if (verbosity > 0)
1213 fprintf (file, "# Write access informations\n");
1214 fprintf (file, "%d\n", nb_writes);
1215
1216 FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb), i, pdr)
1217 if (PDR_TYPE (pdr) != PDR_READ)
1218 print_pdr (file, pdr, verbosity);
1219
1220 if (verbosity > 1)
1221 fprintf (file, "#)\n");
1222
1223 if (verbosity > 1)
1224 fprintf (file, "#)\n");
1225 }
1226
1227 /* Print to STDERR all the data references of PBB. */
1228
1229 DEBUG_FUNCTION void
1230 debug_pdrs (poly_bb_p pbb, int verbosity)
1231 {
1232 print_pdrs (stderr, pbb, verbosity);
1233 }
1234
1235 /* Print to FILE the body of PBB, at some VERBOSITY level.
1236 If statement_body_provided is false statement body is not printed. */
1237
1238 static void
1239 print_pbb_body (FILE *file, poly_bb_p pbb, int verbosity,
1240 bool statement_body_provided)
1241 {
1242 if (verbosity > 1)
1243 fprintf (file, "# Body (\n");
1244
1245 if (!statement_body_provided)
1246 {
1247 if (verbosity > 0)
1248 fprintf (file, "# Statement body is not provided\n");
1249
1250 fprintf (file, "0\n");
1251
1252 if (verbosity > 1)
1253 fprintf (file, "#)\n");
1254 return;
1255 }
1256
1257 if (verbosity > 0)
1258 fprintf (file, "# Statement body is provided\n");
1259 fprintf (file, "1\n");
1260
1261 if (verbosity > 0)
1262 fprintf (file, "# Original iterator names\n# Iterator names are not provided yet.\n");
1263
1264 if (verbosity > 0)
1265 fprintf (file, "# Statement body\n");
1266
1267 fprintf (file, "{\n");
1268 dump_bb (pbb_bb (pbb), file, 0);
1269 fprintf (file, "}\n");
1270
1271 if (verbosity > 1)
1272 fprintf (file, "#)\n");
1273 }
1274
1275 /* Print to FILE the domain and scattering function of PBB, at some
1276 VERBOSITY level. */
1277
1278 void
1279 print_pbb (FILE *file, poly_bb_p pbb, int verbosity)
1280 {
1281 if (verbosity > 1)
1282 {
1283 fprintf (file, "# pbb_%d (\n", pbb_index (pbb));
1284 dump_gbb_conditions (file, PBB_BLACK_BOX (pbb));
1285 dump_gbb_cases (file, PBB_BLACK_BOX (pbb));
1286 }
1287
1288 openscop_print_pbb_domain (file, pbb, verbosity);
1289 print_scattering_function (file, pbb, verbosity);
1290 print_pdrs (file, pbb, verbosity);
1291 print_pbb_body (file, pbb, verbosity, false);
1292
1293 if (verbosity > 1)
1294 fprintf (file, "#)\n");
1295 }
1296
1297 /* Print to FILE the parameters of SCOP, at some VERBOSITY level. */
1298
1299 void
1300 print_scop_params (FILE *file, scop_p scop, int verbosity)
1301 {
1302 int i;
1303 tree t;
1304
1305 if (verbosity > 1)
1306 fprintf (file, "# parameters (\n");
1307
1308 if (VEC_length (tree, SESE_PARAMS (SCOP_REGION (scop))))
1309 {
1310 if (verbosity > 0)
1311 fprintf (file, "# Parameter names are provided\n");
1312
1313 fprintf (file, "1\n");
1314
1315 if (verbosity > 0)
1316 fprintf (file, "# Parameter names\n");
1317 }
1318 else
1319 {
1320 if (verbosity > 0)
1321 fprintf (file, "# Parameter names are not provided\n");
1322 fprintf (file, "0\n");
1323 }
1324
1325 FOR_EACH_VEC_ELT (tree, SESE_PARAMS (SCOP_REGION (scop)), i, t)
1326 {
1327 print_generic_expr (file, t, 0);
1328 fprintf (file, " ");
1329 }
1330
1331 fprintf (file, "\n");
1332
1333 if (verbosity > 1)
1334 fprintf (file, "#)\n");
1335 }
1336
1337 /* Print to FILE the context of SCoP in OpenScop format, at some VERBOSITY
1338 level. */
1339
1340 static void
1341 openscop_print_scop_context (FILE *file, scop_p scop, int verbosity)
1342 {
1343 graphite_dim_t i;
1344
1345 if (verbosity > 0)
1346 {
1347 fprintf (file, "# Context (\n");
1348 fprintf (file, "#eq");
1349
1350 for (i = 0; i < scop_nb_params (scop); i++)
1351 fprintf (file, " p%d", (int) i);
1352
1353 fprintf (file, " cst\n");
1354 }
1355
1356 if (SCOP_CONTEXT (scop))
1357 openscop_print_powerset_matrix (file, SCOP_CONTEXT (scop), 0, 0, 0,
1358 scop_nb_params (scop));
1359 else
1360 fprintf (file, "0 %d 0 0 0 %d\n", (int) scop_nb_params (scop) + 2,
1361 (int) scop_nb_params (scop));
1362
1363 if (verbosity > 0)
1364 fprintf (file, "# )\n");
1365 }
1366
1367 /* Print to FILE the context of SCoP, at some VERBOSITY level. */
1368
1369 void
1370 print_scop_context (FILE *file, scop_p scop, int verbosity)
1371 {
1372 graphite_dim_t i;
1373
1374 if (verbosity > 0)
1375 {
1376 fprintf (file, "# Context (\n");
1377 fprintf (file, "#eq");
1378
1379 for (i = 0; i < scop_nb_params (scop); i++)
1380 fprintf (file, " p%d", (int) i);
1381
1382 fprintf (file, " cst\n");
1383 }
1384
1385 if (SCOP_CONTEXT (scop))
1386 ppl_print_powerset_matrix (file, SCOP_CONTEXT (scop));
1387 else
1388 fprintf (file, "0 %d\n", (int) scop_nb_params (scop) + 2);
1389
1390 if (verbosity > 0)
1391 fprintf (file, "# )\n");
1392 }
1393
1394 /* Print to FILE the SCOP, at some VERBOSITY level. */
1395
1396 void
1397 print_scop (FILE *file, scop_p scop, int verbosity)
1398 {
1399 int i;
1400 poly_bb_p pbb;
1401
1402 fprintf (file, "SCoP 1\n#(\n");
1403 fprintf (file, "# Language\nGimple\n");
1404 openscop_print_scop_context (file, scop, verbosity);
1405 print_scop_params (file, scop, verbosity);
1406
1407 if (verbosity > 0)
1408 fprintf (file, "# Number of statements\n");
1409
1410 fprintf (file, "%d\n",VEC_length (poly_bb_p, SCOP_BBS (scop)));
1411
1412 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
1413 print_pbb (file, pbb, verbosity);
1414
1415 if (verbosity > 1)
1416 {
1417 fprintf (file, "# original_lst (\n");
1418 print_lst (file, SCOP_ORIGINAL_SCHEDULE (scop), 0);
1419 fprintf (file, "\n#)\n");
1420
1421 fprintf (file, "# transformed_lst (\n");
1422 print_lst (file, SCOP_TRANSFORMED_SCHEDULE (scop), 0);
1423 fprintf (file, "\n#)\n");
1424 }
1425
1426 fprintf (file, "#)\n");
1427 }
1428
1429 /* Print to FILE the input file that CLooG would expect as input, at
1430 some VERBOSITY level. */
1431
1432 void
1433 print_cloog (FILE *file, scop_p scop, int verbosity)
1434 {
1435 int i;
1436 poly_bb_p pbb;
1437
1438 fprintf (file, "# SCoP (generated by GCC/Graphite\n");
1439 if (verbosity > 0)
1440 fprintf (file, "# CLooG output language\n");
1441 fprintf (file, "c\n");
1442
1443 print_scop_context (file, scop, verbosity);
1444 print_scop_params (file, scop, verbosity);
1445
1446 if (verbosity > 0)
1447 fprintf (file, "# Number of statements\n");
1448
1449 fprintf (file, "%d\n", VEC_length (poly_bb_p, SCOP_BBS (scop)));
1450
1451 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
1452 {
1453 if (verbosity > 1)
1454 fprintf (file, "# pbb_%d (\n", pbb_index (pbb));
1455
1456 print_pbb_domain (file, pbb, verbosity);
1457 fprintf (file, "0 0 0");
1458
1459 if (verbosity > 0)
1460 fprintf (file, "# For future CLooG options.\n");
1461 else
1462 fprintf (file, "\n");
1463
1464 if (verbosity > 1)
1465 fprintf (file, "#)\n");
1466 }
1467
1468 fprintf (file, "0");
1469 if (verbosity > 0)
1470 fprintf (file, "# Don't set the iterator names.\n");
1471 else
1472 fprintf (file, "\n");
1473
1474 if (verbosity > 0)
1475 fprintf (file, "# Number of scattering functions\n");
1476
1477 fprintf (file, "%d\n", VEC_length (poly_bb_p, SCOP_BBS (scop)));
1478 unify_scattering_dimensions (scop);
1479
1480 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
1481 {
1482 if (!PBB_TRANSFORMED (pbb)
1483 || !(PBB_TRANSFORMED_SCATTERING (pbb)
1484 || PBB_ORIGINAL_SCATTERING (pbb)))
1485 continue;
1486
1487 if (verbosity > 1)
1488 fprintf (file, "# pbb_%d (\n", pbb_index (pbb));
1489
1490 print_scattering_function_1 (file, pbb, verbosity);
1491
1492 if (verbosity > 1)
1493 fprintf (file, "#)\n");
1494 }
1495
1496 fprintf (file, "0");
1497 if (verbosity > 0)
1498 fprintf (file, "# Don't set the scattering dimension names.\n");
1499 else
1500 fprintf (file, "\n");
1501
1502 fprintf (file, "#)\n");
1503 }
1504
1505 /* Print to STDERR the domain of PBB, at some VERBOSITY level. */
1506
1507 DEBUG_FUNCTION void
1508 debug_pbb_domain (poly_bb_p pbb, int verbosity)
1509 {
1510 print_pbb_domain (stderr, pbb, verbosity);
1511 }
1512
1513 /* Print to FILE the domain and scattering function of PBB, at some
1514 VERBOSITY level. */
1515
1516 DEBUG_FUNCTION void
1517 debug_pbb (poly_bb_p pbb, int verbosity)
1518 {
1519 print_pbb (stderr, pbb, verbosity);
1520 }
1521
1522 /* Print to STDERR the context of SCOP, at some VERBOSITY level. */
1523
1524 DEBUG_FUNCTION void
1525 debug_scop_context (scop_p scop, int verbosity)
1526 {
1527 print_scop_context (stderr, scop, verbosity);
1528 }
1529
1530 /* Print to STDERR the SCOP, at some VERBOSITY level. */
1531
1532 DEBUG_FUNCTION void
1533 debug_scop (scop_p scop, int verbosity)
1534 {
1535 print_scop (stderr, scop, verbosity);
1536 }
1537
1538 /* Print to STDERR the SCOP under CLooG format, at some VERBOSITY
1539 level. */
1540
1541 DEBUG_FUNCTION void
1542 debug_cloog (scop_p scop, int verbosity)
1543 {
1544 print_cloog (stderr, scop, verbosity);
1545 }
1546
1547 /* Print to STDERR the parameters of SCOP, at some VERBOSITY
1548 level. */
1549
1550 DEBUG_FUNCTION void
1551 debug_scop_params (scop_p scop, int verbosity)
1552 {
1553 print_scop_params (stderr, scop, verbosity);
1554 }
1555
1556
1557 /* The dimension in the transformed scattering polyhedron of PBB
1558 containing the scattering iterator for the loop at depth LOOP_DEPTH. */
1559
1560 ppl_dimension_type
1561 psct_scattering_dim_for_loop_depth (poly_bb_p pbb, graphite_dim_t loop_depth)
1562 {
1563 ppl_const_Constraint_System_t pcs;
1564 ppl_Constraint_System_const_iterator_t cit, cend;
1565 ppl_const_Constraint_t cstr;
1566 ppl_Polyhedron_t ph = PBB_TRANSFORMED_SCATTERING (pbb);
1567 ppl_dimension_type iter = psct_iterator_dim (pbb, loop_depth);
1568 ppl_Linear_Expression_t expr;
1569 ppl_Coefficient_t coef;
1570 mpz_t val;
1571 graphite_dim_t i;
1572
1573 mpz_init (val);
1574 ppl_new_Coefficient (&coef);
1575 ppl_Polyhedron_get_constraints (ph, &pcs);
1576 ppl_new_Constraint_System_const_iterator (&cit);
1577 ppl_new_Constraint_System_const_iterator (&cend);
1578
1579 for (ppl_Constraint_System_begin (pcs, cit),
1580 ppl_Constraint_System_end (pcs, cend);
1581 !ppl_Constraint_System_const_iterator_equal_test (cit, cend);
1582 ppl_Constraint_System_const_iterator_increment (cit))
1583 {
1584 ppl_Constraint_System_const_iterator_dereference (cit, &cstr);
1585 ppl_new_Linear_Expression_from_Constraint (&expr, cstr);
1586 ppl_Linear_Expression_coefficient (expr, iter, coef);
1587 ppl_Coefficient_to_mpz_t (coef, val);
1588
1589 if (mpz_sgn (val) == 0)
1590 {
1591 ppl_delete_Linear_Expression (expr);
1592 continue;
1593 }
1594
1595 for (i = 0; i < pbb_nb_scattering_transform (pbb); i++)
1596 {
1597 ppl_dimension_type scatter = psct_scattering_dim (pbb, i);
1598
1599 ppl_Linear_Expression_coefficient (expr, scatter, coef);
1600 ppl_Coefficient_to_mpz_t (coef, val);
1601
1602 if (mpz_sgn (val) != 0)
1603 {
1604 mpz_clear (val);
1605 ppl_delete_Linear_Expression (expr);
1606 ppl_delete_Coefficient (coef);
1607 ppl_delete_Constraint_System_const_iterator (cit);
1608 ppl_delete_Constraint_System_const_iterator (cend);
1609
1610 return scatter;
1611 }
1612 }
1613 }
1614
1615 gcc_unreachable ();
1616 }
1617
1618 /* Returns the number of iterations RES of the loop around PBB at
1619 time(scattering) dimension TIME_DEPTH. */
1620
1621 void
1622 pbb_number_of_iterations_at_time (poly_bb_p pbb,
1623 graphite_dim_t time_depth,
1624 mpz_t res)
1625 {
1626 ppl_Pointset_Powerset_C_Polyhedron_t domain, sctr_lb, sctr_ub;
1627 ppl_dimension_type domain_dim, sctr_dim;
1628 graphite_dim_t dim_iter_domain = pbb_dim_iter_domain (pbb);
1629 ppl_Linear_Expression_t le;
1630 mpz_t lb, ub, diff, one;
1631 int i;
1632
1633 ppl_Polyhedron_space_dimension (PBB_TRANSFORMED_SCATTERING (pbb), &sctr_dim);
1634
1635 ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1636 (&domain, PBB_DOMAIN (pbb));
1637
1638 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (domain, &domain_dim);
1639
1640 mpz_init (diff);
1641 mpz_init (lb);
1642 mpz_init (ub);
1643 mpz_init (one);
1644 mpz_set_si (one, 1);
1645
1646 /* Compute the upper bound on the original iteration domain and add
1647 that upper bound to the scattering. */
1648 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1649 (&sctr_ub, PBB_TRANSFORMED_SCATTERING (pbb));
1650 for (i = 0; i < (int) dim_iter_domain; i++)
1651 {
1652 ppl_Linear_Expression_t eq;
1653 ppl_Constraint_t pc;
1654 ppl_Constraint_System_t cs;
1655 ppl_Polyhedron_t ph;
1656 ppl_Pointset_Powerset_C_Polyhedron_t pph;
1657
1658 ppl_new_Linear_Expression_with_dimension (&le, domain_dim);
1659 ppl_set_coef (le, i, 1);
1660 ppl_min_for_le_pointset (domain, le, lb);
1661 ppl_max_for_le_pointset (domain, le, ub);
1662 mpz_sub (diff, ub, lb);
1663 mpz_add (diff, diff, one);
1664
1665 ppl_new_Linear_Expression_with_dimension (&eq, sctr_dim);
1666 ppl_set_coef (eq, psct_iterator_dim (pbb, i), -1);
1667 ppl_set_inhomogeneous_gmp (eq, diff);
1668
1669 ppl_new_Constraint (&pc, eq, PPL_CONSTRAINT_TYPE_EQUAL);
1670 ppl_new_Constraint_System_from_Constraint (&cs, pc);
1671 ppl_new_C_Polyhedron_from_Constraint_System (&ph, cs);
1672 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&pph, ph);
1673 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (sctr_ub, pph);
1674
1675 ppl_delete_Linear_Expression (le);
1676 ppl_delete_Linear_Expression (eq);
1677 ppl_delete_Polyhedron (ph);
1678 ppl_delete_Pointset_Powerset_C_Polyhedron (pph);
1679 ppl_delete_Constraint (pc);
1680 ppl_delete_Constraint_System (cs);
1681 }
1682
1683 /* Compute the lower bound on the original iteration domain and add
1684 it to the scattering. */
1685 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1686 (&sctr_lb, PBB_TRANSFORMED_SCATTERING (pbb));
1687 for (i = 0; i < (int) dim_iter_domain; i++)
1688 {
1689 ppl_Linear_Expression_t eq;
1690 ppl_Constraint_t pc;
1691 ppl_Constraint_System_t cs;
1692 ppl_Polyhedron_t ph;
1693 ppl_Pointset_Powerset_C_Polyhedron_t pph;
1694
1695 ppl_new_Linear_Expression_with_dimension (&le, domain_dim);
1696 ppl_set_coef (le, i, 1);
1697 ppl_min_for_le_pointset (domain, le, lb);
1698
1699 ppl_new_Linear_Expression_with_dimension (&eq, sctr_dim);
1700 ppl_set_coef (eq, psct_iterator_dim (pbb, i), -1);
1701 ppl_set_inhomogeneous_gmp (eq, lb);
1702
1703 ppl_new_Constraint (&pc, eq, PPL_CONSTRAINT_TYPE_EQUAL);
1704 ppl_new_Constraint_System_from_Constraint (&cs, pc);
1705 ppl_new_C_Polyhedron_from_Constraint_System (&ph, cs);
1706 ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&pph, ph);
1707 ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (sctr_lb, pph);
1708
1709 ppl_delete_Linear_Expression (le);
1710 ppl_delete_Linear_Expression (eq);
1711 ppl_delete_Polyhedron (ph);
1712 ppl_delete_Pointset_Powerset_C_Polyhedron (pph);
1713 ppl_delete_Constraint (pc);
1714 ppl_delete_Constraint_System (cs);
1715 }
1716
1717 /* Extract the number of iterations. */
1718 ppl_new_Linear_Expression_with_dimension (&le, sctr_dim);
1719 ppl_set_coef (le, time_depth, 1);
1720 ppl_min_for_le_pointset (sctr_lb, le, lb);
1721 ppl_max_for_le_pointset (sctr_ub, le, ub);
1722 mpz_sub (res, ub, lb);
1723
1724 mpz_clear (one);
1725 mpz_clear (diff);
1726 mpz_clear (lb);
1727 mpz_clear (ub);
1728 ppl_delete_Linear_Expression (le);
1729 ppl_delete_Pointset_Powerset_C_Polyhedron (sctr_ub);
1730 ppl_delete_Pointset_Powerset_C_Polyhedron (sctr_lb);
1731 ppl_delete_Pointset_Powerset_C_Polyhedron (domain);
1732 }
1733
1734 /* Translates LOOP to LST. */
1735
1736 static lst_p
1737 loop_to_lst (loop_p loop, VEC (poly_bb_p, heap) *bbs, int *i)
1738 {
1739 poly_bb_p pbb;
1740 VEC (lst_p, heap) *seq = VEC_alloc (lst_p, heap, 5);
1741
1742 for (; VEC_iterate (poly_bb_p, bbs, *i, pbb); (*i)++)
1743 {
1744 lst_p stmt;
1745 basic_block bb = GBB_BB (PBB_BLACK_BOX (pbb));
1746
1747 if (bb->loop_father == loop)
1748 stmt = new_lst_stmt (pbb);
1749 else if (flow_bb_inside_loop_p (loop, bb))
1750 {
1751 loop_p next = loop->inner;
1752
1753 while (next && !flow_bb_inside_loop_p (next, bb))
1754 next = next->next;
1755
1756 stmt = loop_to_lst (next, bbs, i);
1757 }
1758 else
1759 {
1760 (*i)--;
1761 return new_lst_loop (seq);
1762 }
1763
1764 VEC_safe_push (lst_p, heap, seq, stmt);
1765 }
1766
1767 return new_lst_loop (seq);
1768 }
1769
1770 /* Reads the original scattering of the SCOP and returns an LST
1771 representing it. */
1772
1773 void
1774 scop_to_lst (scop_p scop)
1775 {
1776 lst_p res;
1777 int i, n = VEC_length (poly_bb_p, SCOP_BBS (scop));
1778 VEC (lst_p, heap) *seq = VEC_alloc (lst_p, heap, 5);
1779 sese region = SCOP_REGION (scop);
1780
1781 for (i = 0; i < n; i++)
1782 {
1783 poly_bb_p pbb = VEC_index (poly_bb_p, SCOP_BBS (scop), i);
1784 loop_p loop = outermost_loop_in_sese (region, GBB_BB (PBB_BLACK_BOX (pbb)));
1785
1786 if (loop_in_sese_p (loop, region))
1787 res = loop_to_lst (loop, SCOP_BBS (scop), &i);
1788 else
1789 res = new_lst_stmt (pbb);
1790
1791 VEC_safe_push (lst_p, heap, seq, res);
1792 }
1793
1794 res = new_lst_loop (seq);
1795 SCOP_ORIGINAL_SCHEDULE (scop) = res;
1796 SCOP_TRANSFORMED_SCHEDULE (scop) = copy_lst (res);
1797 }
1798
1799 /* Print to FILE on a new line COLUMN white spaces. */
1800
1801 static void
1802 lst_indent_to (FILE *file, int column)
1803 {
1804 int i;
1805
1806 if (column > 0)
1807 fprintf (file, "\n#");
1808
1809 for (i = 0; i < column; i++)
1810 fprintf (file, " ");
1811 }
1812
1813 /* Print LST to FILE with INDENT spaces of indentation. */
1814
1815 void
1816 print_lst (FILE *file, lst_p lst, int indent)
1817 {
1818 if (!lst)
1819 return;
1820
1821 lst_indent_to (file, indent);
1822
1823 if (LST_LOOP_P (lst))
1824 {
1825 int i;
1826 lst_p l;
1827
1828 if (LST_LOOP_FATHER (lst))
1829 fprintf (file, "%d (loop", lst_dewey_number (lst));
1830 else
1831 fprintf (file, "#(root");
1832
1833 FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, l)
1834 print_lst (file, l, indent + 2);
1835
1836 fprintf (file, ")");
1837 }
1838 else
1839 fprintf (file, "%d stmt_%d", lst_dewey_number (lst), pbb_index (LST_PBB (lst)));
1840 }
1841
1842 /* Print LST to STDERR. */
1843
1844 DEBUG_FUNCTION void
1845 debug_lst (lst_p lst)
1846 {
1847 print_lst (stderr, lst, 0);
1848 }
1849
1850 /* Pretty print to FILE the loop statement tree LST in DOT format. */
1851
1852 static void
1853 dot_lst_1 (FILE *file, lst_p lst)
1854 {
1855 if (!lst)
1856 return;
1857
1858 if (LST_LOOP_P (lst))
1859 {
1860 int i;
1861 lst_p l;
1862
1863 if (!LST_LOOP_FATHER (lst))
1864 fprintf (file, "L -> L_%d_%d\n",
1865 lst_depth (lst),
1866 lst_dewey_number (lst));
1867 else
1868 fprintf (file, "L_%d_%d -> L_%d_%d\n",
1869 lst_depth (LST_LOOP_FATHER (lst)),
1870 lst_dewey_number (LST_LOOP_FATHER (lst)),
1871 lst_depth (lst),
1872 lst_dewey_number (lst));
1873
1874 FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, l)
1875 dot_lst_1 (file, l);
1876 }
1877
1878 else
1879 fprintf (file, "L_%d_%d -> S_%d\n",
1880 lst_depth (LST_LOOP_FATHER (lst)),
1881 lst_dewey_number (LST_LOOP_FATHER (lst)),
1882 pbb_index (LST_PBB (lst)));
1883
1884 }
1885
1886 /* Display the LST using dotty. */
1887
1888 DEBUG_FUNCTION void
1889 dot_lst (lst_p lst)
1890 {
1891 /* When debugging, enable the following code. This cannot be used
1892 in production compilers because it calls "system". */
1893 #if 0
1894 FILE *stream = fopen ("/tmp/lst.dot", "w");
1895 gcc_assert (stream);
1896
1897 fputs ("digraph all {\n", stream);
1898 dot_lst_1 (stream, lst);
1899 fputs ("}\n\n", stream);
1900 fclose (stream);
1901
1902 system ("dotty /tmp/lst.dot &");
1903 #else
1904 fputs ("digraph all {\n", stderr);
1905 dot_lst_1 (stderr, lst);
1906 fputs ("}\n\n", stderr);
1907
1908 #endif
1909 }
1910
1911 /* Computes a checksum for the code generated by CLooG for SCOP. */
1912
1913 DEBUG_FUNCTION void
1914 cloog_checksum (scop_p scop ATTRIBUTE_UNUSED)
1915 {
1916 /* When debugging, enable the following code. This cannot be used
1917 in production compilers because it calls "system". */
1918 #if 0
1919 FILE *stream = fopen ("/tmp/scop.cloog", "w");
1920 gcc_assert (stream);
1921 print_cloog (stream, scop, 0);
1922 fclose (stream);
1923
1924 fputs ("\n", stdout);
1925 system ("cloog -compilable 1 /tmp/scop.cloog > /tmp/scop.c ; gcc -O0 -g /tmp/scop.c -lm -o /tmp/scop; /tmp/scop | md5sum ");
1926 #endif
1927 }
1928
1929 #endif
1930