1 /* Translation of CLAST (CLooG AST) to Gimple.
2 Copyright (C) 2009, 2010, 2011 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <sebastian.pop@amd.com>.
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
10 any later version.
11
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
20
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 "cfgloop.h"
28 #include "tree-chrec.h"
29 #include "tree-data-ref.h"
30 #include "tree-scalar-evolution.h"
31 #include "sese.h"
32
33 #ifdef HAVE_cloog
34 #include "cloog/cloog.h"
35 #include "ppl_c.h"
36 #include "graphite-cloog-util.h"
37 #include "graphite-ppl.h"
38 #include "graphite-poly.h"
39 #include "graphite-clast-to-gimple.h"
40 #include "graphite-dependences.h"
41 #include "graphite-cloog-compat.h"
42
43 #ifndef CLOOG_LANGUAGE_C
44 #define CLOOG_LANGUAGE_C LANGUAGE_C
45 #endif
46
47 /* This flag is set when an error occurred during the translation of
48 CLAST to Gimple. */
49 static bool gloog_error;
50
51 /* Verifies properties that GRAPHITE should maintain during translation. */
52
53 static inline void
graphite_verify(void)54 graphite_verify (void)
55 {
56 #ifdef ENABLE_CHECKING
57 verify_loop_structure ();
58 verify_dominators (CDI_DOMINATORS);
59 verify_loop_closed_ssa (true);
60 #endif
61 }
62
63 /* Stores the INDEX in a vector and the loop nesting LEVEL for a given
64 clast NAME. BOUND_ONE and BOUND_TWO represent the exact lower and
65 upper bounds that can be inferred from the polyhedral representation. */
66
67 typedef struct clast_name_index {
68 int index;
69 int level;
70 mpz_t bound_one, bound_two;
71 const char *name;
72 } *clast_name_index_p;
73
74 /* Returns a pointer to a new element of type clast_name_index_p built
75 from NAME, INDEX, LEVEL, BOUND_ONE, and BOUND_TWO. */
76
77 static inline clast_name_index_p
new_clast_name_index(const char * name,int index,int level,mpz_t bound_one,mpz_t bound_two)78 new_clast_name_index (const char *name, int index, int level,
79 mpz_t bound_one, mpz_t bound_two)
80 {
81 clast_name_index_p res = XNEW (struct clast_name_index);
82
83 res->name = name;
84 res->level = level;
85 res->index = index;
86 mpz_init (res->bound_one);
87 mpz_init (res->bound_two);
88 mpz_set (res->bound_one, bound_one);
89 mpz_set (res->bound_two, bound_two);
90 return res;
91 }
92
93 /* Free the memory taken by a clast_name_index struct. */
94
95 static void
free_clast_name_index(void * ptr)96 free_clast_name_index (void *ptr)
97 {
98 struct clast_name_index *c = (struct clast_name_index *) ptr;
99 mpz_clear (c->bound_one);
100 mpz_clear (c->bound_two);
101 free (ptr);
102 }
103
104 /* For a given clast NAME, returns -1 if NAME is not in the
105 INDEX_TABLE, otherwise returns the loop level for the induction
106 variable NAME, or if it is a parameter, the parameter number in the
107 vector of parameters. */
108
109 static inline int
clast_name_to_level(clast_name_p name,htab_t index_table)110 clast_name_to_level (clast_name_p name, htab_t index_table)
111 {
112 struct clast_name_index tmp;
113 PTR *slot;
114
115 #ifdef CLOOG_ORG
116 gcc_assert (name->type == clast_expr_name);
117 tmp.name = ((const struct clast_name *) name)->name;
118 #else
119 tmp.name = name;
120 #endif
121
122 slot = htab_find_slot (index_table, &tmp, NO_INSERT);
123
124 if (slot && *slot)
125 return ((struct clast_name_index *) *slot)->level;
126
127 return -1;
128 }
129
130 /* For a given clast NAME, returns -1 if it does not correspond to any
131 parameter, or otherwise, returns the index in the PARAMS or
132 SCATTERING_DIMENSIONS vector. */
133
134 static inline int
clast_name_to_index(clast_name_p name,htab_t index_table)135 clast_name_to_index (clast_name_p name, htab_t index_table)
136 {
137 struct clast_name_index tmp;
138 PTR *slot;
139
140 #ifdef CLOOG_ORG
141 gcc_assert (name->type == clast_expr_name);
142 tmp.name = ((const struct clast_name *) name)->name;
143 #else
144 tmp.name = name;
145 #endif
146
147 slot = htab_find_slot (index_table, &tmp, NO_INSERT);
148
149 if (slot && *slot)
150 return ((struct clast_name_index *) *slot)->index;
151
152 return -1;
153 }
154
155 /* For a given clast NAME, initializes the lower and upper bounds BOUND_ONE
156 and BOUND_TWO stored in the INDEX_TABLE. Returns true when NAME has been
157 found in the INDEX_TABLE, false otherwise. */
158
159 static inline bool
clast_name_to_lb_ub(clast_name_p name,htab_t index_table,mpz_t bound_one,mpz_t bound_two)160 clast_name_to_lb_ub (clast_name_p name, htab_t index_table, mpz_t bound_one,
161 mpz_t bound_two)
162 {
163 struct clast_name_index tmp;
164 PTR *slot;
165
166 #ifdef CLOOG_ORG
167 gcc_assert (name->type == clast_expr_name);
168 tmp.name = ((const struct clast_name *) name)->name;
169 #else
170 tmp.name = name;
171 #endif
172
173 slot = htab_find_slot (index_table, &tmp, NO_INSERT);
174
175 if (slot && *slot)
176 {
177 mpz_set (bound_one, ((struct clast_name_index *) *slot)->bound_one);
178 mpz_set (bound_two, ((struct clast_name_index *) *slot)->bound_two);
179 return true;
180 }
181
182 return false;
183 }
184
185 /* Records in INDEX_TABLE the INDEX and LEVEL for NAME. */
186
187 static inline void
save_clast_name_index(htab_t index_table,const char * name,int index,int level,mpz_t bound_one,mpz_t bound_two)188 save_clast_name_index (htab_t index_table, const char *name,
189 int index, int level, mpz_t bound_one, mpz_t bound_two)
190 {
191 struct clast_name_index tmp;
192 PTR *slot;
193
194 tmp.name = name;
195 slot = htab_find_slot (index_table, &tmp, INSERT);
196
197 if (slot)
198 {
199 free (*slot);
200
201 *slot = new_clast_name_index (name, index, level, bound_one, bound_two);
202 }
203 }
204
205 /* Computes a hash function for database element ELT. */
206
207 static inline hashval_t
clast_name_index_elt_info(const void * elt)208 clast_name_index_elt_info (const void *elt)
209 {
210 return htab_hash_pointer (((const struct clast_name_index *) elt)->name);
211 }
212
213 /* Compares database elements E1 and E2. */
214
215 static inline int
eq_clast_name_indexes(const void * e1,const void * e2)216 eq_clast_name_indexes (const void *e1, const void *e2)
217 {
218 const struct clast_name_index *elt1 = (const struct clast_name_index *) e1;
219 const struct clast_name_index *elt2 = (const struct clast_name_index *) e2;
220
221 return (elt1->name == elt2->name);
222 }
223
224
225
226 /* NEWIVS_INDEX binds CLooG's scattering name to the index of the tree
227 induction variable in NEWIVS.
228
229 PARAMS_INDEX binds CLooG's parameter name to the index of the tree
230 parameter in PARAMS. */
231
232 typedef struct ivs_params {
233 VEC (tree, heap) *params, **newivs;
234 htab_t newivs_index, params_index;
235 sese region;
236 } *ivs_params_p;
237
238 /* Returns the tree variable from the name NAME that was given in
239 Cloog representation. */
240
241 static tree
clast_name_to_gcc(clast_name_p name,ivs_params_p ip)242 clast_name_to_gcc (clast_name_p name, ivs_params_p ip)
243 {
244 int index;
245
246 if (ip->params && ip->params_index)
247 {
248 index = clast_name_to_index (name, ip->params_index);
249
250 if (index >= 0)
251 return VEC_index (tree, ip->params, index);
252 }
253
254 gcc_assert (*(ip->newivs) && ip->newivs_index);
255 index = clast_name_to_index (name, ip->newivs_index);
256 gcc_assert (index >= 0);
257
258 return VEC_index (tree, *(ip->newivs), index);
259 }
260
261 /* Returns the maximal precision type for expressions TYPE1 and TYPE2. */
262
263 static tree
max_precision_type(tree type1,tree type2)264 max_precision_type (tree type1, tree type2)
265 {
266 enum machine_mode mode;
267 int p1, p2, precision;
268 tree type;
269
270 if (POINTER_TYPE_P (type1))
271 return type1;
272
273 if (POINTER_TYPE_P (type2))
274 return type2;
275
276 if (TYPE_UNSIGNED (type1)
277 && TYPE_UNSIGNED (type2))
278 return TYPE_PRECISION (type1) > TYPE_PRECISION (type2) ? type1 : type2;
279
280 p1 = TYPE_PRECISION (type1);
281 p2 = TYPE_PRECISION (type2);
282
283 if (p1 > p2)
284 precision = TYPE_UNSIGNED (type1) ? p1 * 2 : p1;
285 else
286 precision = TYPE_UNSIGNED (type2) ? p2 * 2 : p2;
287
288 if (precision > BITS_PER_WORD)
289 {
290 gloog_error = true;
291 return integer_type_node;
292 }
293
294 mode = smallest_mode_for_size (precision, MODE_INT);
295 precision = GET_MODE_PRECISION (mode);
296 type = build_nonstandard_integer_type (precision, false);
297
298 if (!type)
299 {
300 gloog_error = true;
301 return integer_type_node;
302 }
303
304 return type;
305 }
306
307 static tree
308 clast_to_gcc_expression (tree, struct clast_expr *, ivs_params_p);
309
310 /* Converts a Cloog reduction expression R with reduction operation OP
311 to a GCC expression tree of type TYPE. */
312
313 static tree
clast_to_gcc_expression_red(tree type,enum tree_code op,struct clast_reduction * r,ivs_params_p ip)314 clast_to_gcc_expression_red (tree type, enum tree_code op,
315 struct clast_reduction *r, ivs_params_p ip)
316 {
317 int i;
318 tree res = clast_to_gcc_expression (type, r->elts[0], ip);
319 tree operand_type = (op == POINTER_PLUS_EXPR) ? sizetype : type;
320
321 for (i = 1; i < r->n; i++)
322 {
323 tree t = clast_to_gcc_expression (operand_type, r->elts[i], ip);
324 res = fold_build2 (op, type, res, t);
325 }
326
327 return res;
328 }
329
330 /* Converts a Cloog AST expression E back to a GCC expression tree of
331 type TYPE. */
332
333 static tree
clast_to_gcc_expression(tree type,struct clast_expr * e,ivs_params_p ip)334 clast_to_gcc_expression (tree type, struct clast_expr *e, ivs_params_p ip)
335 {
336 switch (e->type)
337 {
338 case clast_expr_term:
339 {
340 struct clast_term *t = (struct clast_term *) e;
341
342 if (t->var)
343 {
344 if (mpz_cmp_si (t->val, 1) == 0)
345 {
346 tree name = clast_name_to_gcc (t->var, ip);
347
348 if (POINTER_TYPE_P (TREE_TYPE (name)) != POINTER_TYPE_P (type))
349 name = convert_to_ptrofftype (name);
350
351 name = fold_convert (type, name);
352 return name;
353 }
354
355 else if (mpz_cmp_si (t->val, -1) == 0)
356 {
357 tree name = clast_name_to_gcc (t->var, ip);
358
359 if (POINTER_TYPE_P (TREE_TYPE (name)) != POINTER_TYPE_P (type))
360 name = convert_to_ptrofftype (name);
361
362 name = fold_convert (type, name);
363
364 return fold_build1 (NEGATE_EXPR, type, name);
365 }
366 else
367 {
368 tree name = clast_name_to_gcc (t->var, ip);
369 tree cst = gmp_cst_to_tree (type, t->val);
370
371 if (POINTER_TYPE_P (TREE_TYPE (name)) != POINTER_TYPE_P (type))
372 name = convert_to_ptrofftype (name);
373
374 name = fold_convert (type, name);
375
376 if (!POINTER_TYPE_P (type))
377 return fold_build2 (MULT_EXPR, type, cst, name);
378
379 gloog_error = true;
380 return cst;
381 }
382 }
383 else
384 return gmp_cst_to_tree (type, t->val);
385 }
386
387 case clast_expr_red:
388 {
389 struct clast_reduction *r = (struct clast_reduction *) e;
390
391 switch (r->type)
392 {
393 case clast_red_sum:
394 return clast_to_gcc_expression_red
395 (type, POINTER_TYPE_P (type) ? POINTER_PLUS_EXPR : PLUS_EXPR,
396 r, ip);
397
398 case clast_red_min:
399 return clast_to_gcc_expression_red (type, MIN_EXPR, r, ip);
400
401 case clast_red_max:
402 return clast_to_gcc_expression_red (type, MAX_EXPR, r, ip);
403
404 default:
405 gcc_unreachable ();
406 }
407 break;
408 }
409
410 case clast_expr_bin:
411 {
412 struct clast_binary *b = (struct clast_binary *) e;
413 struct clast_expr *lhs = (struct clast_expr *) b->LHS;
414 tree tl = clast_to_gcc_expression (type, lhs, ip);
415 tree tr = gmp_cst_to_tree (type, b->RHS);
416
417 switch (b->type)
418 {
419 case clast_bin_fdiv:
420 return fold_build2 (FLOOR_DIV_EXPR, type, tl, tr);
421
422 case clast_bin_cdiv:
423 return fold_build2 (CEIL_DIV_EXPR, type, tl, tr);
424
425 case clast_bin_div:
426 return fold_build2 (EXACT_DIV_EXPR, type, tl, tr);
427
428 case clast_bin_mod:
429 return fold_build2 (TRUNC_MOD_EXPR, type, tl, tr);
430
431 default:
432 gcc_unreachable ();
433 }
434 }
435
436 default:
437 gcc_unreachable ();
438 }
439
440 return NULL_TREE;
441 }
442
443 /* Return a type that could represent the values between BOUND_ONE and
444 BOUND_TWO. */
445
446 static tree
type_for_interval(mpz_t bound_one,mpz_t bound_two)447 type_for_interval (mpz_t bound_one, mpz_t bound_two)
448 {
449 bool unsigned_p;
450 tree type;
451 enum machine_mode mode;
452 int wider_precision;
453 int precision = MAX (mpz_sizeinbase (bound_one, 2),
454 mpz_sizeinbase (bound_two, 2));
455
456 if (precision > BITS_PER_WORD)
457 {
458 gloog_error = true;
459 return integer_type_node;
460 }
461
462 if (mpz_cmp (bound_one, bound_two) <= 0)
463 unsigned_p = (mpz_sgn (bound_one) >= 0);
464 else
465 unsigned_p = (mpz_sgn (bound_two) >= 0);
466
467 mode = smallest_mode_for_size (precision, MODE_INT);
468 wider_precision = GET_MODE_PRECISION (mode);
469
470 /* As we want to generate signed types as much as possible, try to
471 fit the interval [bound_one, bound_two] in a signed type. For example,
472 supposing that we have the interval [0, 100], instead of
473 generating unsigned char, we want to generate a signed char. */
474 if (unsigned_p && precision < wider_precision)
475 unsigned_p = false;
476
477 type = build_nonstandard_integer_type (wider_precision, unsigned_p);
478
479 if (!type)
480 {
481 gloog_error = true;
482 return integer_type_node;
483 }
484
485 return type;
486 }
487
488 /* Return a type that could represent the integer value VAL, or
489 otherwise return NULL_TREE. */
490
491 static tree
type_for_value(mpz_t val)492 type_for_value (mpz_t val)
493 {
494 return type_for_interval (val, val);
495 }
496
497 /* Return the type for the clast_term T. Initializes BOUND_ONE and
498 BOUND_TWO to the bounds of the term. */
499
500 static tree
type_for_clast_term(struct clast_term * t,ivs_params_p ip,mpz_t bound_one,mpz_t bound_two)501 type_for_clast_term (struct clast_term *t, ivs_params_p ip, mpz_t bound_one,
502 mpz_t bound_two)
503 {
504 clast_name_p name = t->var;
505 bool found = false;
506
507 gcc_assert (t->expr.type == clast_expr_term);
508
509 if (!name)
510 {
511 mpz_set (bound_one, t->val);
512 mpz_set (bound_two, t->val);
513 return type_for_value (t->val);
514 }
515
516 if (ip->params && ip->params_index)
517 found = clast_name_to_lb_ub (name, ip->params_index, bound_one, bound_two);
518
519 if (!found)
520 {
521 gcc_assert (*(ip->newivs) && ip->newivs_index);
522 found = clast_name_to_lb_ub (name, ip->newivs_index,
523 bound_one, bound_two);
524 gcc_assert (found);
525 }
526
527 mpz_mul (bound_one, bound_one, t->val);
528 mpz_mul (bound_two, bound_two, t->val);
529
530 return TREE_TYPE (clast_name_to_gcc (name, ip));
531 }
532
533 static tree
534 type_for_clast_expr (struct clast_expr *, ivs_params_p, mpz_t, mpz_t);
535
536 /* Return the type for the clast_reduction R. Initializes BOUND_ONE
537 and BOUND_TWO to the bounds of the reduction expression. */
538
539 static tree
type_for_clast_red(struct clast_reduction * r,ivs_params_p ip,mpz_t bound_one,mpz_t bound_two)540 type_for_clast_red (struct clast_reduction *r, ivs_params_p ip,
541 mpz_t bound_one, mpz_t bound_two)
542 {
543 int i;
544 tree type = type_for_clast_expr (r->elts[0], ip, bound_one, bound_two);
545 mpz_t b1, b2, m1, m2;
546
547 if (r->n == 1)
548 return type;
549
550 mpz_init (b1);
551 mpz_init (b2);
552 mpz_init (m1);
553 mpz_init (m2);
554
555 for (i = 1; i < r->n; i++)
556 {
557 tree t = type_for_clast_expr (r->elts[i], ip, b1, b2);
558 type = max_precision_type (type, t);
559
560 switch (r->type)
561 {
562 case clast_red_sum:
563 value_min (m1, bound_one, bound_two);
564 value_min (m2, b1, b2);
565 mpz_add (bound_one, m1, m2);
566
567 value_max (m1, bound_one, bound_two);
568 value_max (m2, b1, b2);
569 mpz_add (bound_two, m1, m2);
570 break;
571
572 case clast_red_min:
573 value_min (bound_one, bound_one, bound_two);
574 value_min (bound_two, b1, b2);
575 break;
576
577 case clast_red_max:
578 value_max (bound_one, bound_one, bound_two);
579 value_max (bound_two, b1, b2);
580 break;
581
582 default:
583 gcc_unreachable ();
584 break;
585 }
586 }
587
588 mpz_clear (b1);
589 mpz_clear (b2);
590 mpz_clear (m1);
591 mpz_clear (m2);
592
593 /* Return a type that can represent the result of the reduction. */
594 return max_precision_type (type, type_for_interval (bound_one, bound_two));
595 }
596
597 /* Return the type for the clast_binary B used in STMT. */
598
599 static tree
type_for_clast_bin(struct clast_binary * b,ivs_params_p ip,mpz_t bound_one,mpz_t bound_two)600 type_for_clast_bin (struct clast_binary *b, ivs_params_p ip, mpz_t bound_one,
601 mpz_t bound_two)
602 {
603 mpz_t one;
604 tree l = type_for_clast_expr ((struct clast_expr *) b->LHS, ip,
605 bound_one, bound_two);
606 tree r = type_for_value (b->RHS);
607 tree type = max_precision_type (l, r);
608
609 switch (b->type)
610 {
611 case clast_bin_fdiv:
612 mpz_mdiv (bound_one, bound_one, b->RHS);
613 mpz_mdiv (bound_two, bound_two, b->RHS);
614 break;
615
616 case clast_bin_cdiv:
617 mpz_mdiv (bound_one, bound_one, b->RHS);
618 mpz_mdiv (bound_two, bound_two, b->RHS);
619 mpz_init (one);
620 mpz_add (bound_one, bound_one, one);
621 mpz_add (bound_two, bound_two, one);
622 mpz_clear (one);
623 break;
624
625 case clast_bin_div:
626 mpz_div (bound_one, bound_one, b->RHS);
627 mpz_div (bound_two, bound_two, b->RHS);
628 break;
629
630 case clast_bin_mod:
631 mpz_mod (bound_one, bound_one, b->RHS);
632 mpz_mod (bound_two, bound_two, b->RHS);
633 break;
634
635 default:
636 gcc_unreachable ();
637 }
638
639 /* Return a type that can represent the result of the reduction. */
640 return max_precision_type (type, type_for_interval (bound_one, bound_two));
641 }
642
643 /* Returns the type for the CLAST expression E when used in statement
644 STMT. */
645
646 static tree
type_for_clast_expr(struct clast_expr * e,ivs_params_p ip,mpz_t bound_one,mpz_t bound_two)647 type_for_clast_expr (struct clast_expr *e, ivs_params_p ip, mpz_t bound_one,
648 mpz_t bound_two)
649 {
650 switch (e->type)
651 {
652 case clast_expr_term:
653 return type_for_clast_term ((struct clast_term *) e, ip,
654 bound_one, bound_two);
655
656 case clast_expr_red:
657 return type_for_clast_red ((struct clast_reduction *) e, ip,
658 bound_one, bound_two);
659
660 case clast_expr_bin:
661 return type_for_clast_bin ((struct clast_binary *) e, ip,
662 bound_one, bound_two);
663
664 default:
665 gcc_unreachable ();
666 }
667
668 return NULL_TREE;
669 }
670
671 /* Returns the type for the equation CLEQ. */
672
673 static tree
type_for_clast_eq(struct clast_equation * cleq,ivs_params_p ip)674 type_for_clast_eq (struct clast_equation *cleq, ivs_params_p ip)
675 {
676 mpz_t bound_one, bound_two;
677 tree l, r;
678
679 mpz_init (bound_one);
680 mpz_init (bound_two);
681
682 l = type_for_clast_expr (cleq->LHS, ip, bound_one, bound_two);
683 r = type_for_clast_expr (cleq->RHS, ip, bound_one, bound_two);
684
685 mpz_clear (bound_one);
686 mpz_clear (bound_two);
687 return max_precision_type (l, r);
688 }
689
690 /* Translates a clast equation CLEQ to a tree. */
691
692 static tree
graphite_translate_clast_equation(struct clast_equation * cleq,ivs_params_p ip)693 graphite_translate_clast_equation (struct clast_equation *cleq,
694 ivs_params_p ip)
695 {
696 enum tree_code comp;
697 tree type = type_for_clast_eq (cleq, ip);
698 tree lhs = clast_to_gcc_expression (type, cleq->LHS, ip);
699 tree rhs = clast_to_gcc_expression (type, cleq->RHS, ip);
700
701 if (cleq->sign == 0)
702 comp = EQ_EXPR;
703
704 else if (cleq->sign > 0)
705 comp = GE_EXPR;
706
707 else
708 comp = LE_EXPR;
709
710 return fold_build2 (comp, boolean_type_node, lhs, rhs);
711 }
712
713 /* Creates the test for the condition in STMT. */
714
715 static tree
graphite_create_guard_cond_expr(struct clast_guard * stmt,ivs_params_p ip)716 graphite_create_guard_cond_expr (struct clast_guard *stmt,
717 ivs_params_p ip)
718 {
719 tree cond = NULL;
720 int i;
721
722 for (i = 0; i < stmt->n; i++)
723 {
724 tree eq = graphite_translate_clast_equation (&stmt->eq[i], ip);
725
726 if (cond)
727 cond = fold_build2 (TRUTH_AND_EXPR, TREE_TYPE (eq), cond, eq);
728 else
729 cond = eq;
730 }
731
732 return cond;
733 }
734
735 /* Creates a new if region corresponding to Cloog's guard. */
736
737 static edge
graphite_create_new_guard(edge entry_edge,struct clast_guard * stmt,ivs_params_p ip)738 graphite_create_new_guard (edge entry_edge, struct clast_guard *stmt,
739 ivs_params_p ip)
740 {
741 tree cond_expr = graphite_create_guard_cond_expr (stmt, ip);
742 edge exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
743 return exit_edge;
744 }
745
746 /* Compute the lower bound LOW and upper bound UP for the parameter
747 PARAM in scop SCOP based on the constraints in the context. */
748
749 static void
compute_bounds_for_param(scop_p scop,int param,mpz_t low,mpz_t up)750 compute_bounds_for_param (scop_p scop, int param, mpz_t low, mpz_t up)
751 {
752 ppl_Linear_Expression_t le;
753
754 /* Prepare the linear expression corresponding to the parameter that
755 we want to maximize/minimize. */
756 ppl_new_Linear_Expression_with_dimension (&le, scop_nb_params (scop));
757 ppl_set_coef (le, param, 1);
758
759 ppl_max_for_le_pointset (SCOP_CONTEXT (scop), le, up);
760 ppl_min_for_le_pointset (SCOP_CONTEXT (scop), le, low);
761 ppl_delete_Linear_Expression (le);
762 }
763
764 /* Compute the lower bound LOW and upper bound UP for the induction
765 variable at LEVEL for the statement PBB, based on the transformed
766 scattering of PBB: T|I|G|Cst, with T the scattering transform, I
767 the iteration domain, and G the context parameters. */
768
769 static void
compute_bounds_for_level(poly_bb_p pbb,int level,mpz_t low,mpz_t up)770 compute_bounds_for_level (poly_bb_p pbb, int level, mpz_t low, mpz_t up)
771 {
772 ppl_Pointset_Powerset_C_Polyhedron_t ps;
773 ppl_Linear_Expression_t le;
774
775 combine_context_id_scat (&ps, pbb, false);
776
777 /* Prepare the linear expression corresponding to the level that we
778 want to maximize/minimize. */
779 {
780 ppl_dimension_type dim = pbb_nb_scattering_transform (pbb)
781 + pbb_dim_iter_domain (pbb) + pbb_nb_params (pbb);
782
783 ppl_new_Linear_Expression_with_dimension (&le, dim);
784 ppl_set_coef (le, psct_dynamic_dim (pbb, level), 1);
785 }
786
787 ppl_max_for_le_pointset (ps, le, up);
788 ppl_min_for_le_pointset (ps, le, low);
789 ppl_delete_Linear_Expression (le);
790 ppl_delete_Pointset_Powerset_C_Polyhedron (ps);
791 }
792
793 /* Walks a CLAST and returns the first statement in the body of a
794 loop.
795
796 FIXME: This function should not be used to get a PBB in the STMT
797 loop in order to find out the iteration domain of the loop: the
798 counter example from Tobias is:
799
800 | for (i = 0; i < 100; i++)
801 | {
802 | if (i == 0)
803 | S1;
804 | S2;
805 | }
806
807 This function would return S1 whose iteration domain contains only
808 one point "i = 0", whereas the iteration domain of S2 has 100 points.
809
810 This should be implemented using some functionality existing in
811 CLooG-ISL. */
812
813 static struct clast_user_stmt *
clast_get_body_of_loop(struct clast_stmt * stmt)814 clast_get_body_of_loop (struct clast_stmt *stmt)
815 {
816 if (!stmt
817 || CLAST_STMT_IS_A (stmt, stmt_user))
818 return (struct clast_user_stmt *) stmt;
819
820 if (CLAST_STMT_IS_A (stmt, stmt_for))
821 return clast_get_body_of_loop (((struct clast_for *) stmt)->body);
822
823 if (CLAST_STMT_IS_A (stmt, stmt_guard))
824 return clast_get_body_of_loop (((struct clast_guard *) stmt)->then);
825
826 if (CLAST_STMT_IS_A (stmt, stmt_block))
827 return clast_get_body_of_loop (((struct clast_block *) stmt)->body);
828
829 if (CLAST_STMT_IS_A (stmt, stmt_ass))
830 return clast_get_body_of_loop (stmt->next);
831
832 gcc_unreachable ();
833 }
834
835 /* Returns the type for the induction variable for the loop translated
836 from STMT_FOR. */
837
838 static tree
type_for_clast_for(struct clast_for * stmt_for,ivs_params_p ip)839 type_for_clast_for (struct clast_for *stmt_for, ivs_params_p ip)
840 {
841 mpz_t bound_one, bound_two;
842 tree lb_type, ub_type;
843
844 mpz_init (bound_one);
845 mpz_init (bound_two);
846
847 lb_type = type_for_clast_expr (stmt_for->LB, ip, bound_one, bound_two);
848 ub_type = type_for_clast_expr (stmt_for->UB, ip, bound_one, bound_two);
849
850 mpz_clear (bound_one);
851 mpz_clear (bound_two);
852
853 return max_precision_type (lb_type, ub_type);
854 }
855
856 /* Creates a new LOOP corresponding to Cloog's STMT. Inserts an
857 induction variable for the new LOOP. New LOOP is attached to CFG
858 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
859 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
860 CLooG's scattering name to the induction variable created for the
861 loop of STMT. The new induction variable is inserted in the NEWIVS
862 vector and is of type TYPE. */
863
864 static struct loop *
graphite_create_new_loop(edge entry_edge,struct clast_for * stmt,loop_p outer,tree type,tree lb,tree ub,int level,ivs_params_p ip)865 graphite_create_new_loop (edge entry_edge, struct clast_for *stmt,
866 loop_p outer, tree type, tree lb, tree ub,
867 int level, ivs_params_p ip)
868 {
869 mpz_t low, up;
870
871 struct clast_user_stmt *body
872 = clast_get_body_of_loop ((struct clast_stmt *) stmt);
873 poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (body->statement);
874
875 tree stride = gmp_cst_to_tree (type, stmt->stride);
876 tree ivvar = create_tmp_var (type, "graphite_IV");
877 tree iv, iv_after_increment;
878 loop_p loop = create_empty_loop_on_edge
879 (entry_edge, lb, stride, ub, ivvar, &iv, &iv_after_increment,
880 outer ? outer : entry_edge->src->loop_father);
881
882 add_referenced_var (ivvar);
883
884 mpz_init (low);
885 mpz_init (up);
886 compute_bounds_for_level (pbb, level, low, up);
887 save_clast_name_index (ip->newivs_index, stmt->iterator,
888 VEC_length (tree, *(ip->newivs)), level, low, up);
889 mpz_clear (low);
890 mpz_clear (up);
891 VEC_safe_push (tree, heap, *(ip->newivs), iv);
892 return loop;
893 }
894
895 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the
896 induction variables of the loops around GBB in SESE. */
897
898 static void
build_iv_mapping(VEC (tree,heap)* iv_map,struct clast_user_stmt * user_stmt,ivs_params_p ip)899 build_iv_mapping (VEC (tree, heap) *iv_map, struct clast_user_stmt *user_stmt,
900 ivs_params_p ip)
901 {
902 struct clast_stmt *t;
903 int depth = 0;
904 CloogStatement *cs = user_stmt->statement;
905 poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (cs);
906 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
907 mpz_t bound_one, bound_two;
908
909 mpz_init (bound_one);
910 mpz_init (bound_two);
911
912 for (t = user_stmt->substitutions; t; t = t->next, depth++)
913 {
914 struct clast_expr *expr = (struct clast_expr *)
915 ((struct clast_assignment *)t)->RHS;
916 tree type = type_for_clast_expr (expr, ip, bound_one, bound_two);
917 tree new_name = clast_to_gcc_expression (type, expr, ip);
918 loop_p old_loop = gbb_loop_at_index (gbb, ip->region, depth);
919
920 VEC_replace (tree, iv_map, old_loop->num, new_name);
921 }
922
923 mpz_clear (bound_one);
924 mpz_clear (bound_two);
925 }
926
927 /* Construct bb_pbb_def with BB and PBB. */
928
929 static bb_pbb_def *
new_bb_pbb_def(basic_block bb,poly_bb_p pbb)930 new_bb_pbb_def (basic_block bb, poly_bb_p pbb)
931 {
932 bb_pbb_def *bb_pbb_p;
933
934 bb_pbb_p = XNEW (bb_pbb_def);
935 bb_pbb_p->bb = bb;
936 bb_pbb_p->pbb = pbb;
937
938 return bb_pbb_p;
939 }
940
941 /* Mark BB with it's relevant PBB via hashing table BB_PBB_MAPPING. */
942
943 static void
mark_bb_with_pbb(poly_bb_p pbb,basic_block bb,htab_t bb_pbb_mapping)944 mark_bb_with_pbb (poly_bb_p pbb, basic_block bb, htab_t bb_pbb_mapping)
945 {
946 bb_pbb_def tmp;
947 PTR *x;
948
949 tmp.bb = bb;
950 x = htab_find_slot (bb_pbb_mapping, &tmp, INSERT);
951
952 if (x && !*x)
953 *x = new_bb_pbb_def (bb, pbb);
954 }
955
956 /* Find BB's related poly_bb_p in hash table BB_PBB_MAPPING. */
957
958 static poly_bb_p
find_pbb_via_hash(htab_t bb_pbb_mapping,basic_block bb)959 find_pbb_via_hash (htab_t bb_pbb_mapping, basic_block bb)
960 {
961 bb_pbb_def tmp;
962 PTR *slot;
963
964 tmp.bb = bb;
965 slot = htab_find_slot (bb_pbb_mapping, &tmp, NO_INSERT);
966
967 if (slot && *slot)
968 return ((bb_pbb_def *) *slot)->pbb;
969
970 return NULL;
971 }
972
973 /* Check data dependency in LOOP at level LEVEL.
974 BB_PBB_MAPPING is a basic_block and it's related poly_bb_p
975 mapping. */
976
977 static bool
dependency_in_loop_p(loop_p loop,htab_t bb_pbb_mapping,int level)978 dependency_in_loop_p (loop_p loop, htab_t bb_pbb_mapping, int level)
979 {
980 unsigned i,j;
981 basic_block *bbs = get_loop_body_in_dom_order (loop);
982
983 for (i = 0; i < loop->num_nodes; i++)
984 {
985 poly_bb_p pbb1 = find_pbb_via_hash (bb_pbb_mapping, bbs[i]);
986
987 if (pbb1 == NULL)
988 continue;
989
990 for (j = 0; j < loop->num_nodes; j++)
991 {
992 poly_bb_p pbb2 = find_pbb_via_hash (bb_pbb_mapping, bbs[j]);
993
994 if (pbb2 == NULL)
995 continue;
996
997 if (dependency_between_pbbs_p (pbb1, pbb2, level))
998 {
999 free (bbs);
1000 return true;
1001 }
1002 }
1003 }
1004
1005 free (bbs);
1006
1007 return false;
1008 }
1009
1010 /* Translates a clast user statement STMT to gimple.
1011
1012 - NEXT_E is the edge where new generated code should be attached.
1013 - CONTEXT_LOOP is the loop in which the generated code will be placed
1014 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */
1015
1016 static edge
translate_clast_user(struct clast_user_stmt * stmt,edge next_e,htab_t bb_pbb_mapping,ivs_params_p ip)1017 translate_clast_user (struct clast_user_stmt *stmt, edge next_e,
1018 htab_t bb_pbb_mapping, ivs_params_p ip)
1019 {
1020 int i, nb_loops;
1021 basic_block new_bb;
1022 poly_bb_p pbb = (poly_bb_p) cloog_statement_usr (stmt->statement);
1023 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
1024 VEC (tree, heap) *iv_map;
1025
1026 if (GBB_BB (gbb) == ENTRY_BLOCK_PTR)
1027 return next_e;
1028
1029 nb_loops = number_of_loops ();
1030 iv_map = VEC_alloc (tree, heap, nb_loops);
1031 for (i = 0; i < nb_loops; i++)
1032 VEC_quick_push (tree, iv_map, NULL_TREE);
1033
1034 build_iv_mapping (iv_map, stmt, ip);
1035 next_e = copy_bb_and_scalar_dependences (GBB_BB (gbb), ip->region,
1036 next_e, iv_map, &gloog_error);
1037 VEC_free (tree, heap, iv_map);
1038
1039 new_bb = next_e->src;
1040 mark_bb_with_pbb (pbb, new_bb, bb_pbb_mapping);
1041 update_ssa (TODO_update_ssa);
1042
1043 return next_e;
1044 }
1045
1046 /* Creates a new if region protecting the loop to be executed, if the execution
1047 count is zero (lb > ub). */
1048
1049 static edge
graphite_create_new_loop_guard(edge entry_edge,struct clast_for * stmt,tree * type,tree * lb,tree * ub,ivs_params_p ip)1050 graphite_create_new_loop_guard (edge entry_edge, struct clast_for *stmt,
1051 tree *type, tree *lb, tree *ub,
1052 ivs_params_p ip)
1053 {
1054 tree cond_expr;
1055 edge exit_edge;
1056
1057 *type = type_for_clast_for (stmt, ip);
1058 *lb = clast_to_gcc_expression (*type, stmt->LB, ip);
1059 *ub = clast_to_gcc_expression (*type, stmt->UB, ip);
1060
1061 /* When ub is simply a constant or a parameter, use lb <= ub. */
1062 if (TREE_CODE (*ub) == INTEGER_CST || TREE_CODE (*ub) == SSA_NAME)
1063 cond_expr = fold_build2 (LE_EXPR, boolean_type_node, *lb, *ub);
1064 else
1065 {
1066 tree one = (POINTER_TYPE_P (*type)
1067 ? convert_to_ptrofftype (integer_one_node)
1068 : fold_convert (*type, integer_one_node));
1069 /* Adding +1 and using LT_EXPR helps with loop latches that have a
1070 loop iteration count of "PARAMETER - 1". For PARAMETER == 0 this becomes
1071 2^k-1 due to integer overflow, and the condition lb <= ub is true,
1072 even if we do not want this. However lb < ub + 1 is false, as
1073 expected. */
1074 tree ub_one = fold_build2 (POINTER_TYPE_P (*type) ? POINTER_PLUS_EXPR
1075 : PLUS_EXPR, *type, *ub, one);
1076
1077 cond_expr = fold_build2 (LT_EXPR, boolean_type_node, *lb, ub_one);
1078 }
1079
1080 exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
1081
1082 return exit_edge;
1083 }
1084
1085 static edge
1086 translate_clast (loop_p, struct clast_stmt *, edge, htab_t, int, ivs_params_p);
1087
1088 /* Create the loop for a clast for statement.
1089
1090 - NEXT_E is the edge where new generated code should be attached.
1091 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */
1092
1093 static edge
translate_clast_for_loop(loop_p context_loop,struct clast_for * stmt,edge next_e,htab_t bb_pbb_mapping,int level,tree type,tree lb,tree ub,ivs_params_p ip)1094 translate_clast_for_loop (loop_p context_loop, struct clast_for *stmt,
1095 edge next_e, htab_t bb_pbb_mapping, int level,
1096 tree type, tree lb, tree ub, ivs_params_p ip)
1097 {
1098 struct loop *loop = graphite_create_new_loop (next_e, stmt, context_loop,
1099 type, lb, ub, level, ip);
1100 edge last_e = single_exit (loop);
1101 edge to_body = single_succ_edge (loop->header);
1102 basic_block after = to_body->dest;
1103
1104 /* Create a basic block for loop close phi nodes. */
1105 last_e = single_succ_edge (split_edge (last_e));
1106
1107 /* Translate the body of the loop. */
1108 next_e = translate_clast (loop, stmt->body, to_body, bb_pbb_mapping,
1109 level + 1, ip);
1110 redirect_edge_succ_nodup (next_e, after);
1111 set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src);
1112
1113 if (flag_loop_parallelize_all
1114 && !dependency_in_loop_p (loop, bb_pbb_mapping, level))
1115 loop->can_be_parallel = true;
1116
1117 return last_e;
1118 }
1119
1120 /* Translates a clast for statement STMT to gimple. First a guard is created
1121 protecting the loop, if it is executed zero times. In this guard we create
1122 the real loop structure.
1123
1124 - NEXT_E is the edge where new generated code should be attached.
1125 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */
1126
1127 static edge
translate_clast_for(loop_p context_loop,struct clast_for * stmt,edge next_e,htab_t bb_pbb_mapping,int level,ivs_params_p ip)1128 translate_clast_for (loop_p context_loop, struct clast_for *stmt, edge next_e,
1129 htab_t bb_pbb_mapping, int level, ivs_params_p ip)
1130 {
1131 tree type, lb, ub;
1132 edge last_e = graphite_create_new_loop_guard (next_e, stmt, &type,
1133 &lb, &ub, ip);
1134 edge true_e = get_true_edge_from_guard_bb (next_e->dest);
1135
1136 translate_clast_for_loop (context_loop, stmt, true_e, bb_pbb_mapping, level,
1137 type, lb, ub, ip);
1138 return last_e;
1139 }
1140
1141 /* Translates a clast assignment STMT to gimple.
1142
1143 - NEXT_E is the edge where new generated code should be attached.
1144 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */
1145
1146 static edge
translate_clast_assignment(struct clast_assignment * stmt,edge next_e,int level,ivs_params_p ip)1147 translate_clast_assignment (struct clast_assignment *stmt, edge next_e,
1148 int level, ivs_params_p ip)
1149 {
1150 gimple_seq stmts;
1151 mpz_t bound_one, bound_two;
1152 tree type, new_name, var;
1153 edge res = single_succ_edge (split_edge (next_e));
1154 struct clast_expr *expr = (struct clast_expr *) stmt->RHS;
1155
1156 mpz_init (bound_one);
1157 mpz_init (bound_two);
1158 type = type_for_clast_expr (expr, ip, bound_one, bound_two);
1159 var = create_tmp_var (type, "graphite_var");
1160 new_name = force_gimple_operand (clast_to_gcc_expression (type, expr, ip),
1161 &stmts, true, var);
1162 add_referenced_var (var);
1163 if (stmts)
1164 {
1165 gsi_insert_seq_on_edge (next_e, stmts);
1166 gsi_commit_edge_inserts ();
1167 }
1168
1169 save_clast_name_index (ip->newivs_index, stmt->LHS,
1170 VEC_length (tree, *(ip->newivs)), level,
1171 bound_one, bound_two);
1172 VEC_safe_push (tree, heap, *(ip->newivs), new_name);
1173
1174 mpz_clear (bound_one);
1175 mpz_clear (bound_two);
1176
1177 return res;
1178 }
1179
1180 /* Translates a clast guard statement STMT to gimple.
1181
1182 - NEXT_E is the edge where new generated code should be attached.
1183 - CONTEXT_LOOP is the loop in which the generated code will be placed
1184 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */
1185
1186 static edge
translate_clast_guard(loop_p context_loop,struct clast_guard * stmt,edge next_e,htab_t bb_pbb_mapping,int level,ivs_params_p ip)1187 translate_clast_guard (loop_p context_loop, struct clast_guard *stmt,
1188 edge next_e, htab_t bb_pbb_mapping, int level,
1189 ivs_params_p ip)
1190 {
1191 edge last_e = graphite_create_new_guard (next_e, stmt, ip);
1192 edge true_e = get_true_edge_from_guard_bb (next_e->dest);
1193
1194 translate_clast (context_loop, stmt->then, true_e, bb_pbb_mapping, level, ip);
1195 return last_e;
1196 }
1197
1198 /* Translates a CLAST statement STMT to GCC representation in the
1199 context of a SESE.
1200
1201 - NEXT_E is the edge where new generated code should be attached.
1202 - CONTEXT_LOOP is the loop in which the generated code will be placed
1203 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */
1204
1205 static edge
translate_clast(loop_p context_loop,struct clast_stmt * stmt,edge next_e,htab_t bb_pbb_mapping,int level,ivs_params_p ip)1206 translate_clast (loop_p context_loop, struct clast_stmt *stmt, edge next_e,
1207 htab_t bb_pbb_mapping, int level, ivs_params_p ip)
1208 {
1209 if (!stmt)
1210 return next_e;
1211
1212 if (CLAST_STMT_IS_A (stmt, stmt_root))
1213 ; /* Do nothing. */
1214
1215 else if (CLAST_STMT_IS_A (stmt, stmt_user))
1216 next_e = translate_clast_user ((struct clast_user_stmt *) stmt,
1217 next_e, bb_pbb_mapping, ip);
1218
1219 else if (CLAST_STMT_IS_A (stmt, stmt_for))
1220 next_e = translate_clast_for (context_loop, (struct clast_for *) stmt,
1221 next_e, bb_pbb_mapping, level, ip);
1222
1223 else if (CLAST_STMT_IS_A (stmt, stmt_guard))
1224 next_e = translate_clast_guard (context_loop, (struct clast_guard *) stmt,
1225 next_e, bb_pbb_mapping, level, ip);
1226
1227 else if (CLAST_STMT_IS_A (stmt, stmt_block))
1228 next_e = translate_clast (context_loop, ((struct clast_block *) stmt)->body,
1229 next_e, bb_pbb_mapping, level, ip);
1230
1231 else if (CLAST_STMT_IS_A (stmt, stmt_ass))
1232 next_e = translate_clast_assignment ((struct clast_assignment *) stmt,
1233 next_e, level, ip);
1234 else
1235 gcc_unreachable();
1236
1237 recompute_all_dominators ();
1238 graphite_verify ();
1239
1240 return translate_clast (context_loop, stmt->next, next_e, bb_pbb_mapping,
1241 level, ip);
1242 }
1243
1244 /* Free the SCATTERING domain list. */
1245
1246 static void
free_scattering(CloogScatteringList * scattering)1247 free_scattering (CloogScatteringList *scattering)
1248 {
1249 while (scattering)
1250 {
1251 CloogScattering *dom = cloog_scattering (scattering);
1252 CloogScatteringList *next = cloog_next_scattering (scattering);
1253
1254 cloog_scattering_free (dom);
1255 free (scattering);
1256 scattering = next;
1257 }
1258 }
1259
1260 /* Initialize Cloog's parameter names from the names used in GIMPLE.
1261 Initialize Cloog's iterator names, using 'graphite_iterator_%d'
1262 from 0 to scop_nb_loops (scop). */
1263
1264 static void
initialize_cloog_names(scop_p scop,CloogProgram * prog)1265 initialize_cloog_names (scop_p scop, CloogProgram *prog)
1266 {
1267 sese region = SCOP_REGION (scop);
1268 int i;
1269 int nb_iterators = scop_max_loop_depth (scop);
1270 int nb_scattering = cloog_program_nb_scattdims (prog);
1271 int nb_parameters = VEC_length (tree, SESE_PARAMS (region));
1272 char **iterators = XNEWVEC (char *, nb_iterators * 2);
1273 char **scattering = XNEWVEC (char *, nb_scattering);
1274 char **parameters= XNEWVEC (char *, nb_parameters);
1275
1276 cloog_program_set_names (prog, cloog_names_malloc ());
1277
1278 for (i = 0; i < nb_parameters; i++)
1279 {
1280 tree param = VEC_index (tree, SESE_PARAMS (region), i);
1281 const char *name = get_name (param);
1282 int len;
1283
1284 if (!name)
1285 name = "T";
1286
1287 len = strlen (name);
1288 len += 17;
1289 parameters[i] = XNEWVEC (char, len + 1);
1290 snprintf (parameters[i], len, "%s_%d", name, SSA_NAME_VERSION (param));
1291 }
1292
1293 cloog_names_set_nb_parameters (cloog_program_names (prog), nb_parameters);
1294 cloog_names_set_parameters (cloog_program_names (prog), parameters);
1295
1296 for (i = 0; i < nb_iterators; i++)
1297 {
1298 int len = 4 + 16;
1299 iterators[i] = XNEWVEC (char, len);
1300 snprintf (iterators[i], len, "git_%d", i);
1301 }
1302
1303 cloog_names_set_nb_iterators (cloog_program_names (prog),
1304 nb_iterators);
1305 cloog_names_set_iterators (cloog_program_names (prog),
1306 iterators);
1307
1308 for (i = 0; i < nb_scattering; i++)
1309 {
1310 int len = 5 + 16;
1311 scattering[i] = XNEWVEC (char, len);
1312 snprintf (scattering[i], len, "scat_%d", i);
1313 }
1314
1315 cloog_names_set_nb_scattering (cloog_program_names (prog),
1316 nb_scattering);
1317 cloog_names_set_scattering (cloog_program_names (prog),
1318 scattering);
1319 }
1320
1321 /* Initialize a CLooG input file. */
1322
1323 static FILE *
init_cloog_input_file(int scop_number)1324 init_cloog_input_file (int scop_number)
1325 {
1326 FILE *graphite_out_file;
1327 int len = strlen (dump_base_name);
1328 char *dumpname = XNEWVEC (char, len + 25);
1329 char *s_scop_number = XNEWVEC (char, 15);
1330
1331 memcpy (dumpname, dump_base_name, len + 1);
1332 strip_off_ending (dumpname, len);
1333 sprintf (s_scop_number, ".%d", scop_number);
1334 strcat (dumpname, s_scop_number);
1335 strcat (dumpname, ".cloog");
1336 graphite_out_file = fopen (dumpname, "w+b");
1337
1338 if (graphite_out_file == 0)
1339 fatal_error ("can%'t open %s for writing: %m", dumpname);
1340
1341 free (dumpname);
1342
1343 return graphite_out_file;
1344 }
1345
1346 /* Build cloog program for SCoP. */
1347
1348 static void
build_cloog_prog(scop_p scop,CloogProgram * prog,CloogOptions * options)1349 build_cloog_prog (scop_p scop, CloogProgram *prog,
1350 CloogOptions *options)
1351 {
1352 int i;
1353 int max_nb_loops = scop_max_loop_depth (scop);
1354 poly_bb_p pbb;
1355 CloogLoop *loop_list = NULL;
1356 CloogBlockList *block_list = NULL;
1357 CloogScatteringList *scattering = NULL;
1358 int nbs = 2 * max_nb_loops + 1;
1359 int *scaldims;
1360
1361 cloog_program_set_context
1362 (prog, new_Cloog_Domain_from_ppl_Pointset_Powerset (SCOP_CONTEXT (scop),
1363 scop_nb_params (scop), cloog_state));
1364 nbs = unify_scattering_dimensions (scop);
1365 scaldims = (int *) xmalloc (nbs * (sizeof (int)));
1366 cloog_program_set_nb_scattdims (prog, nbs);
1367 initialize_cloog_names (scop, prog);
1368
1369 FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb)
1370 {
1371 CloogStatement *stmt;
1372 CloogBlock *block;
1373 CloogDomain *dom;
1374
1375 /* Dead code elimination: when the domain of a PBB is empty,
1376 don't generate code for the PBB. */
1377 if (ppl_Pointset_Powerset_C_Polyhedron_is_empty (PBB_DOMAIN (pbb)))
1378 continue;
1379
1380 /* Build the new statement and its block. */
1381 stmt = cloog_statement_alloc (cloog_state, pbb_index (pbb));
1382 dom = new_Cloog_Domain_from_ppl_Pointset_Powerset (PBB_DOMAIN (pbb),
1383 scop_nb_params (scop),
1384 cloog_state);
1385 block = cloog_block_alloc (stmt, 0, NULL, pbb_dim_iter_domain (pbb));
1386 cloog_statement_set_usr (stmt, pbb);
1387
1388 /* Build loop list. */
1389 {
1390 CloogLoop *new_loop_list = cloog_loop_malloc (cloog_state);
1391 cloog_loop_set_next (new_loop_list, loop_list);
1392 cloog_loop_set_domain (new_loop_list, dom);
1393 cloog_loop_set_block (new_loop_list, block);
1394 loop_list = new_loop_list;
1395 }
1396
1397 /* Build block list. */
1398 {
1399 CloogBlockList *new_block_list = cloog_block_list_malloc ();
1400
1401 cloog_block_list_set_next (new_block_list, block_list);
1402 cloog_block_list_set_block (new_block_list, block);
1403 block_list = new_block_list;
1404 }
1405
1406 /* Build scattering list. */
1407 {
1408 /* XXX: Replace with cloog_domain_list_alloc(), when available. */
1409 CloogScatteringList *new_scattering
1410 = (CloogScatteringList *) xmalloc (sizeof (CloogScatteringList));
1411 ppl_Polyhedron_t scat;
1412 CloogScattering *dom;
1413
1414 scat = PBB_TRANSFORMED_SCATTERING (pbb);
1415 dom = new_Cloog_Scattering_from_ppl_Polyhedron
1416 (scat, scop_nb_params (scop), pbb_nb_scattering_transform (pbb),
1417 cloog_state);
1418
1419 cloog_set_next_scattering (new_scattering, scattering);
1420 cloog_set_scattering (new_scattering, dom);
1421 scattering = new_scattering;
1422 }
1423 }
1424
1425 cloog_program_set_loop (prog, loop_list);
1426 cloog_program_set_blocklist (prog, block_list);
1427
1428 for (i = 0; i < nbs; i++)
1429 scaldims[i] = 0 ;
1430
1431 cloog_program_set_scaldims (prog, scaldims);
1432
1433 /* Extract scalar dimensions to simplify the code generation problem. */
1434 cloog_program_extract_scalars (prog, scattering, options);
1435
1436 /* Dump a .cloog input file, if requested. This feature is only
1437 enabled in the Graphite branch. */
1438 if (0)
1439 {
1440 static size_t file_scop_number = 0;
1441 FILE *cloog_file = init_cloog_input_file (file_scop_number);
1442
1443 cloog_program_dump_cloog (cloog_file, prog, scattering);
1444 ++file_scop_number;
1445 }
1446
1447 /* Apply scattering. */
1448 cloog_program_scatter (prog, scattering, options);
1449 free_scattering (scattering);
1450
1451 /* Iterators corresponding to scalar dimensions have to be extracted. */
1452 cloog_names_scalarize (cloog_program_names (prog), nbs,
1453 cloog_program_scaldims (prog));
1454
1455 /* Free blocklist. */
1456 {
1457 CloogBlockList *next = cloog_program_blocklist (prog);
1458
1459 while (next)
1460 {
1461 CloogBlockList *toDelete = next;
1462 next = cloog_block_list_next (next);
1463 cloog_block_list_set_next (toDelete, NULL);
1464 cloog_block_list_set_block (toDelete, NULL);
1465 cloog_block_list_free (toDelete);
1466 }
1467 cloog_program_set_blocklist (prog, NULL);
1468 }
1469 }
1470
1471 /* Return the options that will be used in GLOOG. */
1472
1473 static CloogOptions *
set_cloog_options(void)1474 set_cloog_options (void)
1475 {
1476 CloogOptions *options = cloog_options_malloc (cloog_state);
1477
1478 /* Change cloog output language to C. If we do use FORTRAN instead, cloog
1479 will stop e.g. with "ERROR: unbounded loops not allowed in FORTRAN.", if
1480 we pass an incomplete program to cloog. */
1481 options->language = CLOOG_LANGUAGE_C;
1482
1483 /* Enable complex equality spreading: removes dummy statements
1484 (assignments) in the generated code which repeats the
1485 substitution equations for statements. This is useless for
1486 GLooG. */
1487 options->esp = 1;
1488
1489 #ifdef CLOOG_ORG
1490 /* Silence CLooG to avoid failing tests due to debug output to stderr. */
1491 options->quiet = 1;
1492 #else
1493 /* Enable C pretty-printing mode: normalizes the substitution
1494 equations for statements. */
1495 options->cpp = 1;
1496 #endif
1497
1498 /* Allow cloog to build strides with a stride width different to one.
1499 This example has stride = 4:
1500
1501 for (i = 0; i < 20; i += 4)
1502 A */
1503 options->strides = 1;
1504
1505 /* Disable optimizations and make cloog generate source code closer to the
1506 input. This is useful for debugging, but later we want the optimized
1507 code.
1508
1509 XXX: We can not disable optimizations, as loop blocking is not working
1510 without them. */
1511 if (0)
1512 {
1513 options->f = -1;
1514 options->l = INT_MAX;
1515 }
1516
1517 return options;
1518 }
1519
1520 /* Prints STMT to STDERR. */
1521
1522 void
print_clast_stmt(FILE * file,struct clast_stmt * stmt)1523 print_clast_stmt (FILE *file, struct clast_stmt *stmt)
1524 {
1525 CloogOptions *options = set_cloog_options ();
1526
1527 clast_pprint (file, stmt, 0, options);
1528 cloog_options_free (options);
1529 }
1530
1531 /* Prints STMT to STDERR. */
1532
1533 DEBUG_FUNCTION void
debug_clast_stmt(struct clast_stmt * stmt)1534 debug_clast_stmt (struct clast_stmt *stmt)
1535 {
1536 print_clast_stmt (stderr, stmt);
1537 }
1538
1539 /* Translate SCOP to a CLooG program and clast. These two
1540 representations should be freed together: a clast cannot be used
1541 without a program. */
1542
1543 cloog_prog_clast
scop_to_clast(scop_p scop)1544 scop_to_clast (scop_p scop)
1545 {
1546 CloogOptions *options = set_cloog_options ();
1547 cloog_prog_clast pc;
1548
1549 /* Connect new cloog prog generation to graphite. */
1550 pc.prog = cloog_program_malloc ();
1551 build_cloog_prog (scop, pc.prog, options);
1552 pc.prog = cloog_program_generate (pc.prog, options);
1553 pc.stmt = cloog_clast_create (pc.prog, options);
1554
1555 cloog_options_free (options);
1556 return pc;
1557 }
1558
1559 /* Prints to FILE the code generated by CLooG for SCOP. */
1560
1561 void
print_generated_program(FILE * file,scop_p scop)1562 print_generated_program (FILE *file, scop_p scop)
1563 {
1564 CloogOptions *options = set_cloog_options ();
1565
1566 cloog_prog_clast pc = scop_to_clast (scop);
1567
1568 fprintf (file, " (prog: \n");
1569 cloog_program_print (file, pc.prog);
1570 fprintf (file, " )\n");
1571
1572 fprintf (file, " (clast: \n");
1573 clast_pprint (file, pc.stmt, 0, options);
1574 fprintf (file, " )\n");
1575
1576 cloog_options_free (options);
1577 cloog_clast_free (pc.stmt);
1578 cloog_program_free (pc.prog);
1579 }
1580
1581 /* Prints to STDERR the code generated by CLooG for SCOP. */
1582
1583 DEBUG_FUNCTION void
debug_generated_program(scop_p scop)1584 debug_generated_program (scop_p scop)
1585 {
1586 print_generated_program (stderr, scop);
1587 }
1588
1589 /* Add CLooG names to parameter index. The index is used to translate
1590 back from CLooG names to GCC trees. */
1591
1592 static void
create_params_index(scop_p scop,htab_t index_table,CloogProgram * prog)1593 create_params_index (scop_p scop, htab_t index_table, CloogProgram *prog) {
1594 CloogNames* names = cloog_program_names (prog);
1595 int nb_parameters = cloog_names_nb_parameters (names);
1596 char **parameters = cloog_names_parameters (names);
1597 int i;
1598 mpz_t bound_one, bound_two;
1599
1600 mpz_init (bound_one);
1601 mpz_init (bound_two);
1602
1603 for (i = 0; i < nb_parameters; i++)
1604 {
1605 compute_bounds_for_param (scop, i, bound_one, bound_two);
1606 save_clast_name_index (index_table, parameters[i], i, i,
1607 bound_one, bound_two);
1608 }
1609
1610 mpz_clear (bound_one);
1611 mpz_clear (bound_two);
1612 }
1613
1614 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
1615 the given SCOP. Return true if code generation succeeded.
1616 BB_PBB_MAPPING is a basic_block and it's related poly_bb_p mapping.
1617 */
1618
1619 bool
gloog(scop_p scop,htab_t bb_pbb_mapping)1620 gloog (scop_p scop, htab_t bb_pbb_mapping)
1621 {
1622 VEC (tree, heap) *newivs = VEC_alloc (tree, heap, 10);
1623 loop_p context_loop;
1624 sese region = SCOP_REGION (scop);
1625 ifsese if_region = NULL;
1626 htab_t newivs_index, params_index;
1627 cloog_prog_clast pc;
1628 struct ivs_params ip;
1629
1630 timevar_push (TV_GRAPHITE_CODE_GEN);
1631 gloog_error = false;
1632
1633 pc = scop_to_clast (scop);
1634
1635 if (dump_file && (dump_flags & TDF_DETAILS))
1636 {
1637 fprintf (dump_file, "\nCLAST generated by CLooG: \n");
1638 print_clast_stmt (dump_file, pc.stmt);
1639 fprintf (dump_file, "\n");
1640 }
1641
1642 recompute_all_dominators ();
1643 graphite_verify ();
1644
1645 if_region = move_sese_in_condition (region);
1646 sese_insert_phis_for_liveouts (region,
1647 if_region->region->exit->src,
1648 if_region->false_region->exit,
1649 if_region->true_region->exit);
1650 recompute_all_dominators ();
1651 graphite_verify ();
1652
1653 context_loop = SESE_ENTRY (region)->src->loop_father;
1654 newivs_index = htab_create (10, clast_name_index_elt_info,
1655 eq_clast_name_indexes, free_clast_name_index);
1656 params_index = htab_create (10, clast_name_index_elt_info,
1657 eq_clast_name_indexes, free_clast_name_index);
1658
1659 create_params_index (scop, params_index, pc.prog);
1660
1661 ip.newivs = &newivs;
1662 ip.newivs_index = newivs_index;
1663 ip.params = SESE_PARAMS (region);
1664 ip.params_index = params_index;
1665 ip.region = region;
1666
1667 translate_clast (context_loop, pc.stmt, if_region->true_region->entry,
1668 bb_pbb_mapping, 0, &ip);
1669 graphite_verify ();
1670 scev_reset ();
1671 recompute_all_dominators ();
1672 graphite_verify ();
1673
1674 if (gloog_error)
1675 set_ifsese_condition (if_region, integer_zero_node);
1676
1677 free (if_region->true_region);
1678 free (if_region->region);
1679 free (if_region);
1680
1681 htab_delete (newivs_index);
1682 htab_delete (params_index);
1683 VEC_free (tree, heap, newivs);
1684 cloog_clast_free (pc.stmt);
1685 cloog_program_free (pc.prog);
1686 timevar_pop (TV_GRAPHITE_CODE_GEN);
1687
1688 if (dump_file && (dump_flags & TDF_DETAILS))
1689 {
1690 loop_p loop;
1691 loop_iterator li;
1692 int num_no_dependency = 0;
1693
1694 FOR_EACH_LOOP (li, loop, 0)
1695 if (loop->can_be_parallel)
1696 num_no_dependency++;
1697
1698 fprintf (dump_file, "\n%d loops carried no dependency.\n",
1699 num_no_dependency);
1700 }
1701
1702 return !gloog_error;
1703 }
1704 #endif
1705