2012-02-25 Catherine Moore <clm@codesourcery.com>
[official-gcc.git] / gcc / graphite-clast-to-gimple.c
blob58a69ed0b4be72c1ff5b7f3486992308f8672582
1 /* Translation of CLAST (CLooG AST) to Gimple.
2 Copyright (C) 2009-2013 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <sebastian.pop@amd.com>.
5 This file is part of GCC.
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.
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.
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/>. */
21 #include "config.h"
23 #ifdef HAVE_cloog
24 #include <isl/set.h>
25 #include <isl/map.h>
26 #include <isl/union_map.h>
27 #include <isl/list.h>
28 #include <isl/constraint.h>
29 #include <isl/ilp.h>
30 #include <isl/aff.h>
31 #include <cloog/cloog.h>
32 #include <cloog/isl/domain.h>
33 #endif
35 #include "system.h"
36 #include "coretypes.h"
37 #include "diagnostic-core.h"
38 #include "tree-flow.h"
39 #include "tree-pass.h"
40 #include "cfgloop.h"
41 #include "tree-chrec.h"
42 #include "tree-data-ref.h"
43 #include "tree-scalar-evolution.h"
44 #include "sese.h"
46 #ifdef HAVE_cloog
47 #include "cloog/cloog.h"
48 #include "graphite-poly.h"
49 #include "graphite-clast-to-gimple.h"
51 typedef const struct clast_expr *clast_name_p;
53 #ifndef CLOOG_LANGUAGE_C
54 #define CLOOG_LANGUAGE_C LANGUAGE_C
55 #endif
58 /* Converts a GMP constant VAL to a tree and returns it. */
60 static tree
61 gmp_cst_to_tree (tree type, mpz_t val)
63 tree t = type ? type : integer_type_node;
64 mpz_t tmp;
65 double_int di;
67 mpz_init (tmp);
68 mpz_set (tmp, val);
69 di = mpz_get_double_int (t, tmp, true);
70 mpz_clear (tmp);
72 return double_int_to_tree (t, di);
75 /* Sets RES to the min of V1 and V2. */
77 static void
78 value_min (mpz_t res, mpz_t v1, mpz_t v2)
80 if (mpz_cmp (v1, v2) < 0)
81 mpz_set (res, v1);
82 else
83 mpz_set (res, v2);
86 /* Sets RES to the max of V1 and V2. */
88 static void
89 value_max (mpz_t res, mpz_t v1, mpz_t v2)
91 if (mpz_cmp (v1, v2) < 0)
92 mpz_set (res, v2);
93 else
94 mpz_set (res, v1);
98 /* This flag is set when an error occurred during the translation of
99 CLAST to Gimple. */
100 static bool gloog_error;
102 /* Verifies properties that GRAPHITE should maintain during translation. */
104 static inline void
105 graphite_verify (void)
107 #ifdef ENABLE_CHECKING
108 verify_loop_structure ();
109 verify_loop_closed_ssa (true);
110 #endif
113 /* Stores the INDEX in a vector and the loop nesting LEVEL for a given
114 clast NAME. BOUND_ONE and BOUND_TWO represent the exact lower and
115 upper bounds that can be inferred from the polyhedral representation. */
117 typedef struct clast_name_index {
118 int index;
119 int level;
120 mpz_t bound_one, bound_two;
121 const char *name;
122 /* If free_name is set, the content of name was allocated by us and needs
123 to be freed. */
124 char *free_name;
125 } *clast_name_index_p;
127 /* Returns a pointer to a new element of type clast_name_index_p built
128 from NAME, INDEX, LEVEL, BOUND_ONE, and BOUND_TWO. */
130 static inline clast_name_index_p
131 new_clast_name_index (const char *name, int index, int level,
132 mpz_t bound_one, mpz_t bound_two)
134 clast_name_index_p res = XNEW (struct clast_name_index);
135 char *new_name = XNEWVEC (char, strlen (name) + 1);
136 strcpy (new_name, name);
138 res->name = new_name;
139 res->free_name = new_name;
140 res->level = level;
141 res->index = index;
142 mpz_init (res->bound_one);
143 mpz_init (res->bound_two);
144 mpz_set (res->bound_one, bound_one);
145 mpz_set (res->bound_two, bound_two);
146 return res;
149 /* Free the memory taken by a clast_name_index struct. */
151 static void
152 free_clast_name_index (void *ptr)
154 struct clast_name_index *c = (struct clast_name_index *) ptr;
155 if (c->free_name)
156 free (c->free_name);
157 mpz_clear (c->bound_one);
158 mpz_clear (c->bound_two);
159 free (ptr);
162 /* For a given clast NAME, returns -1 if NAME is not in the
163 INDEX_TABLE, otherwise returns the loop level for the induction
164 variable NAME, or if it is a parameter, the parameter number in the
165 vector of parameters. */
167 static inline int
168 clast_name_to_level (clast_name_p name, htab_t index_table)
170 struct clast_name_index tmp;
171 PTR *slot;
173 gcc_assert (name->type == clast_expr_name);
174 tmp.name = ((const struct clast_name *) name)->name;
175 tmp.free_name = NULL;
177 slot = htab_find_slot (index_table, &tmp, NO_INSERT);
179 if (slot && *slot)
180 return ((struct clast_name_index *) *slot)->level;
182 return -1;
185 /* For a given clast NAME, returns -1 if it does not correspond to any
186 parameter, or otherwise, returns the index in the PARAMS or
187 SCATTERING_DIMENSIONS vector. */
189 static inline int
190 clast_name_to_index (struct clast_name *name, htab_t index_table)
192 struct clast_name_index tmp;
193 PTR *slot;
195 tmp.name = ((const struct clast_name *) name)->name;
196 tmp.free_name = NULL;
198 slot = htab_find_slot (index_table, &tmp, NO_INSERT);
200 if (slot && *slot)
201 return ((struct clast_name_index *) *slot)->index;
203 return -1;
206 /* For a given clast NAME, initializes the lower and upper bounds BOUND_ONE
207 and BOUND_TWO stored in the INDEX_TABLE. Returns true when NAME has been
208 found in the INDEX_TABLE, false otherwise. */
210 static inline bool
211 clast_name_to_lb_ub (struct clast_name *name, htab_t index_table,
212 mpz_t bound_one, mpz_t bound_two)
214 struct clast_name_index tmp;
215 PTR *slot;
217 tmp.name = name->name;
218 tmp.free_name = NULL;
220 slot = htab_find_slot (index_table, &tmp, NO_INSERT);
222 if (slot && *slot)
224 mpz_set (bound_one, ((struct clast_name_index *) *slot)->bound_one);
225 mpz_set (bound_two, ((struct clast_name_index *) *slot)->bound_two);
226 return true;
229 return false;
232 /* Records in INDEX_TABLE the INDEX and LEVEL for NAME. */
234 static inline void
235 save_clast_name_index (htab_t index_table, const char *name,
236 int index, int level, mpz_t bound_one, mpz_t bound_two)
238 struct clast_name_index tmp;
239 PTR *slot;
241 tmp.name = name;
242 tmp.free_name = NULL;
243 slot = htab_find_slot (index_table, &tmp, INSERT);
245 if (slot)
247 free (*slot);
249 *slot = new_clast_name_index (name, index, level, bound_one, bound_two);
253 /* Computes a hash function for database element ELT. */
255 static inline hashval_t
256 clast_name_index_elt_info (const void *elt)
258 const struct clast_name_index *e = ((const struct clast_name_index *) elt);
259 hashval_t hash = 0;
261 int length = strlen (e->name);
262 int i;
264 for (i = 0; i < length; ++i)
265 hash = hash | (e->name[i] << (i % 4));
267 return hash;
270 /* Compares database elements E1 and E2. */
272 static inline int
273 eq_clast_name_indexes (const void *e1, const void *e2)
275 const struct clast_name_index *elt1 = (const struct clast_name_index *) e1;
276 const struct clast_name_index *elt2 = (const struct clast_name_index *) e2;
278 return strcmp (elt1->name, elt2->name) == 0;
283 /* NEWIVS_INDEX binds CLooG's scattering name to the index of the tree
284 induction variable in NEWIVS.
286 PARAMS_INDEX binds CLooG's parameter name to the index of the tree
287 parameter in PARAMS. */
289 typedef struct ivs_params {
290 vec<tree> params, *newivs;
291 htab_t newivs_index, params_index;
292 sese region;
293 } *ivs_params_p;
295 /* Returns the tree variable from the name NAME that was given in
296 Cloog representation. */
298 static tree
299 clast_name_to_gcc (struct clast_name *name, ivs_params_p ip)
301 int index;
303 if (ip->params.exists () && ip->params_index)
305 index = clast_name_to_index (name, ip->params_index);
307 if (index >= 0)
308 return ip->params[index];
311 gcc_assert (ip->newivs && ip->newivs_index);
312 index = clast_name_to_index (name, ip->newivs_index);
313 gcc_assert (index >= 0);
315 return (*ip->newivs)[index];
318 /* Returns the maximal precision type for expressions TYPE1 and TYPE2. */
320 static tree
321 max_precision_type (tree type1, tree type2)
323 enum machine_mode mode;
324 int p1, p2, precision;
325 tree type;
327 if (POINTER_TYPE_P (type1))
328 return type1;
330 if (POINTER_TYPE_P (type2))
331 return type2;
333 if (TYPE_UNSIGNED (type1)
334 && TYPE_UNSIGNED (type2))
335 return TYPE_PRECISION (type1) > TYPE_PRECISION (type2) ? type1 : type2;
337 p1 = TYPE_PRECISION (type1);
338 p2 = TYPE_PRECISION (type2);
340 if (p1 > p2)
341 precision = TYPE_UNSIGNED (type1) ? p1 * 2 : p1;
342 else
343 precision = TYPE_UNSIGNED (type2) ? p2 * 2 : p2;
345 if (precision > BITS_PER_WORD)
347 gloog_error = true;
348 return integer_type_node;
351 mode = smallest_mode_for_size (precision, MODE_INT);
352 precision = GET_MODE_PRECISION (mode);
353 type = build_nonstandard_integer_type (precision, false);
355 if (!type)
357 gloog_error = true;
358 return integer_type_node;
361 return type;
364 static tree
365 clast_to_gcc_expression (tree, struct clast_expr *, ivs_params_p);
367 /* Converts a Cloog reduction expression R with reduction operation OP
368 to a GCC expression tree of type TYPE. */
370 static tree
371 clast_to_gcc_expression_red (tree type, enum tree_code op,
372 struct clast_reduction *r, ivs_params_p ip)
374 int i;
375 tree res = clast_to_gcc_expression (type, r->elts[0], ip);
376 tree operand_type = (op == POINTER_PLUS_EXPR) ? sizetype : type;
378 for (i = 1; i < r->n; i++)
380 tree t = clast_to_gcc_expression (operand_type, r->elts[i], ip);
381 res = fold_build2 (op, type, res, t);
384 return res;
387 /* Converts a Cloog AST expression E back to a GCC expression tree of
388 type TYPE. */
390 static tree
391 clast_to_gcc_expression (tree type, struct clast_expr *e, ivs_params_p ip)
393 switch (e->type)
395 case clast_expr_name:
397 return clast_name_to_gcc ((struct clast_name *) e, ip);
399 case clast_expr_term:
401 struct clast_term *t = (struct clast_term *) e;
403 if (t->var)
405 if (mpz_cmp_si (t->val, 1) == 0)
407 tree name = clast_to_gcc_expression (type, t->var, ip);
409 if (POINTER_TYPE_P (TREE_TYPE (name)) != POINTER_TYPE_P (type))
410 name = convert_to_ptrofftype (name);
412 name = fold_convert (type, name);
413 return name;
416 else if (mpz_cmp_si (t->val, -1) == 0)
418 tree name = clast_to_gcc_expression (type, t->var, ip);
420 if (POINTER_TYPE_P (TREE_TYPE (name)) != POINTER_TYPE_P (type))
421 name = convert_to_ptrofftype (name);
423 name = fold_convert (type, name);
425 return fold_build1 (NEGATE_EXPR, type, name);
427 else
429 tree name = clast_to_gcc_expression (type, t->var, ip);
430 tree cst = gmp_cst_to_tree (type, t->val);
432 if (POINTER_TYPE_P (TREE_TYPE (name)) != POINTER_TYPE_P (type))
433 name = convert_to_ptrofftype (name);
435 name = fold_convert (type, name);
437 if (!POINTER_TYPE_P (type))
438 return fold_build2 (MULT_EXPR, type, cst, name);
440 gloog_error = true;
441 return cst;
444 else
445 return gmp_cst_to_tree (type, t->val);
448 case clast_expr_red:
450 struct clast_reduction *r = (struct clast_reduction *) e;
452 switch (r->type)
454 case clast_red_sum:
455 return clast_to_gcc_expression_red
456 (type, POINTER_TYPE_P (type) ? POINTER_PLUS_EXPR : PLUS_EXPR,
457 r, ip);
459 case clast_red_min:
460 return clast_to_gcc_expression_red (type, MIN_EXPR, r, ip);
462 case clast_red_max:
463 return clast_to_gcc_expression_red (type, MAX_EXPR, r, ip);
465 default:
466 gcc_unreachable ();
468 break;
471 case clast_expr_bin:
473 struct clast_binary *b = (struct clast_binary *) e;
474 struct clast_expr *lhs = (struct clast_expr *) b->LHS;
475 tree tl = clast_to_gcc_expression (type, lhs, ip);
476 tree tr = gmp_cst_to_tree (type, b->RHS);
478 switch (b->type)
480 case clast_bin_fdiv:
481 return fold_build2 (FLOOR_DIV_EXPR, type, tl, tr);
483 case clast_bin_cdiv:
484 return fold_build2 (CEIL_DIV_EXPR, type, tl, tr);
486 case clast_bin_div:
487 return fold_build2 (EXACT_DIV_EXPR, type, tl, tr);
489 case clast_bin_mod:
490 return fold_build2 (TRUNC_MOD_EXPR, type, tl, tr);
492 default:
493 gcc_unreachable ();
497 default:
498 gcc_unreachable ();
501 return NULL_TREE;
504 /* Return a type that could represent the values between BOUND_ONE and
505 BOUND_TWO. */
507 static tree
508 type_for_interval (mpz_t bound_one, mpz_t bound_two)
510 bool unsigned_p;
511 tree type;
512 enum machine_mode mode;
513 int wider_precision;
514 int precision = MAX (mpz_sizeinbase (bound_one, 2),
515 mpz_sizeinbase (bound_two, 2));
517 if (precision > BITS_PER_WORD)
519 gloog_error = true;
520 return integer_type_node;
523 if (mpz_cmp (bound_one, bound_two) <= 0)
524 unsigned_p = (mpz_sgn (bound_one) >= 0);
525 else
526 unsigned_p = (mpz_sgn (bound_two) >= 0);
528 mode = smallest_mode_for_size (precision, MODE_INT);
529 wider_precision = GET_MODE_PRECISION (mode);
531 /* As we want to generate signed types as much as possible, try to
532 fit the interval [bound_one, bound_two] in a signed type. For example,
533 supposing that we have the interval [0, 100], instead of
534 generating unsigned char, we want to generate a signed char. */
535 if (unsigned_p && precision < wider_precision)
536 unsigned_p = false;
538 type = build_nonstandard_integer_type (wider_precision, unsigned_p);
540 if (!type)
542 gloog_error = true;
543 return integer_type_node;
546 return type;
549 /* Return a type that could represent the integer value VAL, or
550 otherwise return NULL_TREE. */
552 static tree
553 type_for_value (mpz_t val)
555 return type_for_interval (val, val);
558 static tree
559 type_for_clast_expr (struct clast_expr *, ivs_params_p, mpz_t, mpz_t);
561 /* Return the type for the clast_term T. Initializes BOUND_ONE and
562 BOUND_TWO to the bounds of the term. */
564 static tree
565 type_for_clast_term (struct clast_term *t, ivs_params_p ip, mpz_t bound_one,
566 mpz_t bound_two)
568 tree type;
569 gcc_assert (t->expr.type == clast_expr_term);
571 if (!t->var)
573 mpz_set (bound_one, t->val);
574 mpz_set (bound_two, t->val);
575 return type_for_value (t->val);
578 type = type_for_clast_expr (t->var, ip, bound_one, bound_two);
580 mpz_mul (bound_one, bound_one, t->val);
581 mpz_mul (bound_two, bound_two, t->val);
583 return max_precision_type (type, type_for_interval (bound_one, bound_two));
586 /* Return the type for the clast_reduction R. Initializes BOUND_ONE
587 and BOUND_TWO to the bounds of the reduction expression. */
589 static tree
590 type_for_clast_red (struct clast_reduction *r, ivs_params_p ip,
591 mpz_t bound_one, mpz_t bound_two)
593 int i;
594 tree type = type_for_clast_expr (r->elts[0], ip, bound_one, bound_two);
595 mpz_t b1, b2, m1, m2;
597 if (r->n == 1)
598 return type;
600 mpz_init (b1);
601 mpz_init (b2);
602 mpz_init (m1);
603 mpz_init (m2);
605 for (i = 1; i < r->n; i++)
607 tree t = type_for_clast_expr (r->elts[i], ip, b1, b2);
608 type = max_precision_type (type, t);
610 switch (r->type)
612 case clast_red_sum:
613 value_min (m1, bound_one, bound_two);
614 value_min (m2, b1, b2);
615 mpz_add (bound_one, m1, m2);
617 value_max (m1, bound_one, bound_two);
618 value_max (m2, b1, b2);
619 mpz_add (bound_two, m1, m2);
620 break;
622 case clast_red_min:
623 value_min (bound_one, bound_one, bound_two);
624 value_min (bound_two, b1, b2);
625 break;
627 case clast_red_max:
628 value_max (bound_one, bound_one, bound_two);
629 value_max (bound_two, b1, b2);
630 break;
632 default:
633 gcc_unreachable ();
634 break;
638 mpz_clear (b1);
639 mpz_clear (b2);
640 mpz_clear (m1);
641 mpz_clear (m2);
643 /* Return a type that can represent the result of the reduction. */
644 return max_precision_type (type, type_for_interval (bound_one, bound_two));
647 /* Return the type for the clast_binary B used in STMT. */
649 static tree
650 type_for_clast_bin (struct clast_binary *b, ivs_params_p ip, mpz_t bound_one,
651 mpz_t bound_two)
653 mpz_t one;
654 tree l = type_for_clast_expr ((struct clast_expr *) b->LHS, ip,
655 bound_one, bound_two);
656 tree r = type_for_value (b->RHS);
657 tree type = max_precision_type (l, r);
659 switch (b->type)
661 case clast_bin_fdiv:
662 mpz_mdiv (bound_one, bound_one, b->RHS);
663 mpz_mdiv (bound_two, bound_two, b->RHS);
664 break;
666 case clast_bin_cdiv:
667 mpz_mdiv (bound_one, bound_one, b->RHS);
668 mpz_mdiv (bound_two, bound_two, b->RHS);
669 mpz_init (one);
670 mpz_add (bound_one, bound_one, one);
671 mpz_add (bound_two, bound_two, one);
672 mpz_clear (one);
673 break;
675 case clast_bin_div:
676 mpz_div (bound_one, bound_one, b->RHS);
677 mpz_div (bound_two, bound_two, b->RHS);
678 break;
680 case clast_bin_mod:
681 mpz_mod (bound_one, bound_one, b->RHS);
682 mpz_mod (bound_two, bound_two, b->RHS);
683 break;
685 default:
686 gcc_unreachable ();
689 /* Return a type that can represent the result of the reduction. */
690 return max_precision_type (type, type_for_interval (bound_one, bound_two));
693 /* Return the type for the clast_name NAME. Initializes BOUND_ONE and
694 BOUND_TWO to the bounds of the term. */
696 static tree
697 type_for_clast_name (struct clast_name *name, ivs_params_p ip, mpz_t bound_one,
698 mpz_t bound_two)
700 bool found = false;
702 if (ip->params.exists () && ip->params_index)
703 found = clast_name_to_lb_ub (name, ip->params_index, bound_one, bound_two);
705 if (!found)
707 gcc_assert (ip->newivs && ip->newivs_index);
708 found = clast_name_to_lb_ub (name, ip->newivs_index, bound_one,
709 bound_two);
710 gcc_assert (found);
713 return TREE_TYPE (clast_name_to_gcc (name, ip));
716 /* Returns the type for the CLAST expression E when used in statement
717 STMT. */
719 static tree
720 type_for_clast_expr (struct clast_expr *e, ivs_params_p ip, mpz_t bound_one,
721 mpz_t bound_two)
723 switch (e->type)
725 case clast_expr_term:
726 return type_for_clast_term ((struct clast_term *) e, ip,
727 bound_one, bound_two);
729 case clast_expr_red:
730 return type_for_clast_red ((struct clast_reduction *) e, ip,
731 bound_one, bound_two);
733 case clast_expr_bin:
734 return type_for_clast_bin ((struct clast_binary *) e, ip,
735 bound_one, bound_two);
737 case clast_expr_name:
738 return type_for_clast_name ((struct clast_name *) e, ip,
739 bound_one, bound_two);
741 default:
742 gcc_unreachable ();
745 return NULL_TREE;
748 /* Returns true if the clast expression E is a constant with VALUE. */
750 static bool
751 clast_expr_const_value_p (struct clast_expr *e, int value)
753 struct clast_term *t;
754 if (e->type != clast_expr_term)
755 return false;
756 t = (struct clast_term *)e;
757 if (t->var)
758 return false;
759 return 0 == mpz_cmp_si (t->val, value);
762 /* Translates a clast equation CLEQ to a tree. */
764 static tree
765 graphite_translate_clast_equation (struct clast_equation *cleq,
766 ivs_params_p ip)
768 enum tree_code comp;
769 tree type, lhs, rhs, ltype, rtype;
770 mpz_t bound_one, bound_two;
771 struct clast_expr *clhs, *crhs;
773 clhs = cleq->LHS;
774 crhs = cleq->RHS;
775 if (cleq->sign == 0)
776 comp = EQ_EXPR;
777 else if (cleq->sign > 0)
778 comp = GE_EXPR;
779 else
780 comp = LE_EXPR;
782 /* Special cases to reduce range of arguments to hopefully
783 don't need types with larger precision than the input. */
784 if (crhs->type == clast_expr_red
785 && comp != EQ_EXPR)
787 struct clast_reduction *r = (struct clast_reduction *) crhs;
788 /* X >= A+1 --> X > A and
789 X <= A-1 --> X < A */
790 if (r->n == 2
791 && r->type == clast_red_sum
792 && clast_expr_const_value_p (r->elts[1], comp == GE_EXPR ? 1 : -1))
794 crhs = r->elts[0];
795 comp = comp == GE_EXPR ? GT_EXPR : LT_EXPR;
799 mpz_init (bound_one);
800 mpz_init (bound_two);
802 ltype = type_for_clast_expr (clhs, ip, bound_one, bound_two);
803 rtype = type_for_clast_expr (crhs, ip, bound_one, bound_two);
805 mpz_clear (bound_one);
806 mpz_clear (bound_two);
807 type = max_precision_type (ltype, rtype);
809 lhs = clast_to_gcc_expression (type, clhs, ip);
810 rhs = clast_to_gcc_expression (type, crhs, ip);
812 return fold_build2 (comp, boolean_type_node, lhs, rhs);
815 /* Creates the test for the condition in STMT. */
817 static tree
818 graphite_create_guard_cond_expr (struct clast_guard *stmt,
819 ivs_params_p ip)
821 tree cond = NULL;
822 int i;
824 for (i = 0; i < stmt->n; i++)
826 tree eq = graphite_translate_clast_equation (&stmt->eq[i], ip);
828 if (cond)
829 cond = fold_build2 (TRUTH_AND_EXPR, TREE_TYPE (eq), cond, eq);
830 else
831 cond = eq;
834 return cond;
837 /* Creates a new if region corresponding to Cloog's guard. */
839 static edge
840 graphite_create_new_guard (edge entry_edge, struct clast_guard *stmt,
841 ivs_params_p ip)
843 tree cond_expr = graphite_create_guard_cond_expr (stmt, ip);
844 edge exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
845 return exit_edge;
848 /* Compute the lower bound LOW and upper bound UP for the parameter
849 PARAM in scop SCOP based on the constraints in the context. */
851 static void
852 compute_bounds_for_param (scop_p scop, int param, mpz_t low, mpz_t up)
854 isl_int v;
855 isl_aff *aff = isl_aff_zero_on_domain
856 (isl_local_space_from_space (isl_set_get_space (scop->context)));
858 aff = isl_aff_add_coefficient_si (aff, isl_dim_param, param, 1);
860 isl_int_init (v);
861 isl_set_min (scop->context, aff, &v);
862 isl_int_get_gmp (v, low);
863 isl_set_max (scop->context, aff, &v);
864 isl_int_get_gmp (v, up);
865 isl_int_clear (v);
866 isl_aff_free (aff);
869 /* Compute the lower bound LOW and upper bound UP for the induction
870 variable of loop LOOP.
872 FIXME: This one is not entirely correct, as min/max expressions in the
873 calculation can yield to incorrect results. To be completely
874 correct, we need to evaluate each subexpression generated by
875 CLooG. CLooG does not yet support this, so this is as good as
876 it can be. */
878 static void
879 compute_bounds_for_loop (struct clast_for *loop, mpz_t low, mpz_t up)
881 isl_set *domain;
882 isl_aff *dimension;
883 isl_local_space *local_space;
884 isl_int isl_value;
885 enum isl_lp_result lp_result;
887 domain = isl_set_copy (isl_set_from_cloog_domain (loop->domain));
888 local_space = isl_local_space_from_space (isl_set_get_space (domain));
889 dimension = isl_aff_zero_on_domain (local_space);
890 dimension = isl_aff_add_coefficient_si (dimension, isl_dim_in,
891 isl_set_dim (domain, isl_dim_set) - 1,
894 isl_int_init (isl_value);
896 lp_result = isl_set_min (domain, dimension, &isl_value);
897 assert (lp_result == isl_lp_ok);
898 isl_int_get_gmp (isl_value, low);
900 lp_result = isl_set_max (domain, dimension, &isl_value);
901 assert (lp_result == isl_lp_ok);
902 isl_int_get_gmp (isl_value, up);
904 isl_int_clear (isl_value);
905 isl_set_free (domain);
906 isl_aff_free (dimension);
909 /* Returns the type for the induction variable for the loop translated
910 from STMT_FOR. */
912 static tree
913 type_for_clast_for (struct clast_for *stmt_for, ivs_params_p ip)
915 mpz_t bound_one, bound_two;
916 tree lb_type, ub_type;
918 mpz_init (bound_one);
919 mpz_init (bound_two);
921 lb_type = type_for_clast_expr (stmt_for->LB, ip, bound_one, bound_two);
922 ub_type = type_for_clast_expr (stmt_for->UB, ip, bound_one, bound_two);
924 mpz_clear (bound_one);
925 mpz_clear (bound_two);
927 return max_precision_type (lb_type, ub_type);
930 /* Creates a new LOOP corresponding to Cloog's STMT. Inserts an
931 induction variable for the new LOOP. New LOOP is attached to CFG
932 starting at ENTRY_EDGE. LOOP is inserted into the loop tree and
933 becomes the child loop of the OUTER_LOOP. NEWIVS_INDEX binds
934 CLooG's scattering name to the induction variable created for the
935 loop of STMT. The new induction variable is inserted in the NEWIVS
936 vector and is of type TYPE. */
938 static struct loop *
939 graphite_create_new_loop (edge entry_edge, struct clast_for *stmt,
940 loop_p outer, tree type, tree lb, tree ub,
941 int level, ivs_params_p ip)
943 mpz_t low, up;
945 tree stride = gmp_cst_to_tree (type, stmt->stride);
946 tree ivvar = create_tmp_var (type, "graphite_IV");
947 tree iv, iv_after_increment;
948 loop_p loop = create_empty_loop_on_edge
949 (entry_edge, lb, stride, ub, ivvar, &iv, &iv_after_increment,
950 outer ? outer : entry_edge->src->loop_father);
952 mpz_init (low);
953 mpz_init (up);
954 compute_bounds_for_loop (stmt, low, up);
955 save_clast_name_index (ip->newivs_index, stmt->iterator,
956 (*ip->newivs).length (), level, low, up);
957 mpz_clear (low);
958 mpz_clear (up);
959 (*ip->newivs).safe_push (iv);
960 return loop;
963 /* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the
964 induction variables of the loops around GBB in SESE. */
966 static void
967 build_iv_mapping (vec<tree> iv_map, struct clast_user_stmt *user_stmt,
968 ivs_params_p ip)
970 struct clast_stmt *t;
971 int depth = 0;
972 CloogStatement *cs = user_stmt->statement;
973 poly_bb_p pbb = (poly_bb_p) cs->usr;
974 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
975 mpz_t bound_one, bound_two;
977 mpz_init (bound_one);
978 mpz_init (bound_two);
980 for (t = user_stmt->substitutions; t; t = t->next, depth++)
982 struct clast_expr *expr = (struct clast_expr *)
983 ((struct clast_assignment *)t)->RHS;
984 tree type = type_for_clast_expr (expr, ip, bound_one, bound_two);
985 tree new_name = clast_to_gcc_expression (type, expr, ip);
986 loop_p old_loop = gbb_loop_at_index (gbb, ip->region, depth);
988 iv_map[old_loop->num] = new_name;
991 mpz_clear (bound_one);
992 mpz_clear (bound_two);
995 /* Construct bb_pbb_def with BB and PBB. */
997 static bb_pbb_def *
998 new_bb_pbb_def (basic_block bb, poly_bb_p pbb)
1000 bb_pbb_def *bb_pbb_p;
1002 bb_pbb_p = XNEW (bb_pbb_def);
1003 bb_pbb_p->bb = bb;
1004 bb_pbb_p->pbb = pbb;
1006 return bb_pbb_p;
1009 /* Mark BB with it's relevant PBB via hashing table BB_PBB_MAPPING. */
1011 static void
1012 mark_bb_with_pbb (poly_bb_p pbb, basic_block bb, htab_t bb_pbb_mapping)
1014 bb_pbb_def tmp;
1015 PTR *x;
1017 tmp.bb = bb;
1018 x = htab_find_slot (bb_pbb_mapping, &tmp, INSERT);
1020 if (x && !*x)
1021 *x = new_bb_pbb_def (bb, pbb);
1024 /* Find BB's related poly_bb_p in hash table BB_PBB_MAPPING. */
1026 poly_bb_p
1027 find_pbb_via_hash (htab_t bb_pbb_mapping, basic_block bb)
1029 bb_pbb_def tmp;
1030 PTR *slot;
1032 tmp.bb = bb;
1033 slot = htab_find_slot (bb_pbb_mapping, &tmp, NO_INSERT);
1035 if (slot && *slot)
1036 return ((bb_pbb_def *) *slot)->pbb;
1038 return NULL;
1041 /* Return the scop of the loop and initialize PBBS the set of
1042 poly_bb_p that belong to the LOOP. BB_PBB_MAPPING is a map created
1043 by the CLAST code generator between a generated basic_block and its
1044 related poly_bb_p. */
1046 scop_p
1047 get_loop_body_pbbs (loop_p loop, htab_t bb_pbb_mapping,
1048 vec<poly_bb_p> *pbbs)
1050 unsigned i;
1051 basic_block *bbs = get_loop_body_in_dom_order (loop);
1052 scop_p scop = NULL;
1054 for (i = 0; i < loop->num_nodes; i++)
1056 poly_bb_p pbb = find_pbb_via_hash (bb_pbb_mapping, bbs[i]);
1058 if (pbb == NULL)
1059 continue;
1061 scop = PBB_SCOP (pbb);
1062 (*pbbs).safe_push (pbb);
1065 free (bbs);
1066 return scop;
1069 /* Translates a clast user statement STMT to gimple.
1071 - NEXT_E is the edge where new generated code should be attached.
1072 - CONTEXT_LOOP is the loop in which the generated code will be placed
1073 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */
1075 static edge
1076 translate_clast_user (struct clast_user_stmt *stmt, edge next_e,
1077 htab_t bb_pbb_mapping, ivs_params_p ip)
1079 int i, nb_loops;
1080 basic_block new_bb;
1081 poly_bb_p pbb = (poly_bb_p) stmt->statement->usr;
1082 gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
1083 vec<tree> iv_map;
1085 if (GBB_BB (gbb) == ENTRY_BLOCK_PTR)
1086 return next_e;
1088 nb_loops = number_of_loops ();
1089 iv_map.create (nb_loops);
1090 for (i = 0; i < nb_loops; i++)
1091 iv_map.quick_push (NULL_TREE);
1093 build_iv_mapping (iv_map, stmt, ip);
1094 next_e = copy_bb_and_scalar_dependences (GBB_BB (gbb), ip->region,
1095 next_e, iv_map, &gloog_error);
1096 iv_map.release ();
1098 new_bb = next_e->src;
1099 mark_bb_with_pbb (pbb, new_bb, bb_pbb_mapping);
1100 mark_virtual_operands_for_renaming (cfun);
1101 update_ssa (TODO_update_ssa);
1103 return next_e;
1106 /* Creates a new if region protecting the loop to be executed, if the execution
1107 count is zero (lb > ub). */
1109 static edge
1110 graphite_create_new_loop_guard (edge entry_edge, struct clast_for *stmt,
1111 tree *type, tree *lb, tree *ub,
1112 ivs_params_p ip)
1114 tree cond_expr;
1115 edge exit_edge;
1117 *type = type_for_clast_for (stmt, ip);
1118 *lb = clast_to_gcc_expression (*type, stmt->LB, ip);
1119 *ub = clast_to_gcc_expression (*type, stmt->UB, ip);
1121 /* When ub is simply a constant or a parameter, use lb <= ub. */
1122 if (TREE_CODE (*ub) == INTEGER_CST || TREE_CODE (*ub) == SSA_NAME)
1123 cond_expr = fold_build2 (LE_EXPR, boolean_type_node, *lb, *ub);
1124 else
1126 tree one = (POINTER_TYPE_P (*type)
1127 ? convert_to_ptrofftype (integer_one_node)
1128 : fold_convert (*type, integer_one_node));
1129 /* Adding +1 and using LT_EXPR helps with loop latches that have a
1130 loop iteration count of "PARAMETER - 1". For PARAMETER == 0 this becomes
1131 2^k-1 due to integer overflow, and the condition lb <= ub is true,
1132 even if we do not want this. However lb < ub + 1 is false, as
1133 expected. */
1134 tree ub_one = fold_build2 (POINTER_TYPE_P (*type) ? POINTER_PLUS_EXPR
1135 : PLUS_EXPR, *type, *ub, one);
1137 cond_expr = fold_build2 (LT_EXPR, boolean_type_node, *lb, ub_one);
1140 exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
1142 return exit_edge;
1145 static edge
1146 translate_clast (loop_p, struct clast_stmt *, edge, htab_t, int, ivs_params_p);
1148 /* Create the loop for a clast for statement.
1150 - NEXT_E is the edge where new generated code should be attached.
1151 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */
1153 static edge
1154 translate_clast_for_loop (loop_p context_loop, struct clast_for *stmt,
1155 edge next_e, htab_t bb_pbb_mapping, int level,
1156 tree type, tree lb, tree ub, ivs_params_p ip)
1158 struct loop *loop = graphite_create_new_loop (next_e, stmt, context_loop,
1159 type, lb, ub, level, ip);
1160 edge last_e = single_exit (loop);
1161 edge to_body = single_succ_edge (loop->header);
1162 basic_block after = to_body->dest;
1164 /* Create a basic block for loop close phi nodes. */
1165 last_e = single_succ_edge (split_edge (last_e));
1167 /* Translate the body of the loop. */
1168 next_e = translate_clast (loop, stmt->body, to_body, bb_pbb_mapping,
1169 level + 1, ip);
1170 redirect_edge_succ_nodup (next_e, after);
1171 set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src);
1173 if (flag_loop_parallelize_all
1174 && loop_is_parallel_p (loop, bb_pbb_mapping, level))
1175 loop->can_be_parallel = true;
1177 return last_e;
1180 /* Translates a clast for statement STMT to gimple. First a guard is created
1181 protecting the loop, if it is executed zero times. In this guard we create
1182 the real loop structure.
1184 - NEXT_E is the edge where new generated code should be attached.
1185 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */
1187 static edge
1188 translate_clast_for (loop_p context_loop, struct clast_for *stmt, edge next_e,
1189 htab_t bb_pbb_mapping, int level, ivs_params_p ip)
1191 tree type, lb, ub;
1192 edge last_e = graphite_create_new_loop_guard (next_e, stmt, &type,
1193 &lb, &ub, ip);
1194 edge true_e = get_true_edge_from_guard_bb (next_e->dest);
1196 translate_clast_for_loop (context_loop, stmt, true_e, bb_pbb_mapping, level,
1197 type, lb, ub, ip);
1198 return last_e;
1201 /* Translates a clast assignment STMT to gimple.
1203 - NEXT_E is the edge where new generated code should be attached.
1204 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */
1206 static edge
1207 translate_clast_assignment (struct clast_assignment *stmt, edge next_e,
1208 int level, ivs_params_p ip)
1210 gimple_seq stmts;
1211 mpz_t bound_one, bound_two;
1212 tree type, new_name, var;
1213 edge res = single_succ_edge (split_edge (next_e));
1214 struct clast_expr *expr = (struct clast_expr *) stmt->RHS;
1216 mpz_init (bound_one);
1217 mpz_init (bound_two);
1218 type = type_for_clast_expr (expr, ip, bound_one, bound_two);
1219 var = create_tmp_var (type, "graphite_var");
1220 new_name = force_gimple_operand (clast_to_gcc_expression (type, expr, ip),
1221 &stmts, true, var);
1222 if (stmts)
1224 gsi_insert_seq_on_edge (next_e, stmts);
1225 gsi_commit_edge_inserts ();
1228 save_clast_name_index (ip->newivs_index, stmt->LHS,
1229 (*ip->newivs).length (), level,
1230 bound_one, bound_two);
1231 (*ip->newivs).safe_push (new_name);
1233 mpz_clear (bound_one);
1234 mpz_clear (bound_two);
1236 return res;
1239 /* Translates a clast guard statement STMT to gimple.
1241 - NEXT_E is the edge where new generated code should be attached.
1242 - CONTEXT_LOOP is the loop in which the generated code will be placed
1243 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */
1245 static edge
1246 translate_clast_guard (loop_p context_loop, struct clast_guard *stmt,
1247 edge next_e, htab_t bb_pbb_mapping, int level,
1248 ivs_params_p ip)
1250 edge last_e = graphite_create_new_guard (next_e, stmt, ip);
1251 edge true_e = get_true_edge_from_guard_bb (next_e->dest);
1253 translate_clast (context_loop, stmt->then, true_e, bb_pbb_mapping, level, ip);
1254 return last_e;
1257 /* Translates a CLAST statement STMT to GCC representation in the
1258 context of a SESE.
1260 - NEXT_E is the edge where new generated code should be attached.
1261 - CONTEXT_LOOP is the loop in which the generated code will be placed
1262 - BB_PBB_MAPPING is is a basic_block and it's related poly_bb_p mapping. */
1264 static edge
1265 translate_clast (loop_p context_loop, struct clast_stmt *stmt, edge next_e,
1266 htab_t bb_pbb_mapping, int level, ivs_params_p ip)
1268 if (!stmt)
1269 return next_e;
1271 if (CLAST_STMT_IS_A (stmt, stmt_root))
1272 ; /* Do nothing. */
1274 else if (CLAST_STMT_IS_A (stmt, stmt_user))
1275 next_e = translate_clast_user ((struct clast_user_stmt *) stmt,
1276 next_e, bb_pbb_mapping, ip);
1278 else if (CLAST_STMT_IS_A (stmt, stmt_for))
1279 next_e = translate_clast_for (context_loop, (struct clast_for *) stmt,
1280 next_e, bb_pbb_mapping, level, ip);
1282 else if (CLAST_STMT_IS_A (stmt, stmt_guard))
1283 next_e = translate_clast_guard (context_loop, (struct clast_guard *) stmt,
1284 next_e, bb_pbb_mapping, level, ip);
1286 else if (CLAST_STMT_IS_A (stmt, stmt_block))
1287 next_e = translate_clast (context_loop, ((struct clast_block *) stmt)->body,
1288 next_e, bb_pbb_mapping, level, ip);
1290 else if (CLAST_STMT_IS_A (stmt, stmt_ass))
1291 next_e = translate_clast_assignment ((struct clast_assignment *) stmt,
1292 next_e, level, ip);
1293 else
1294 gcc_unreachable();
1296 recompute_all_dominators ();
1297 graphite_verify ();
1299 return translate_clast (context_loop, stmt->next, next_e, bb_pbb_mapping,
1300 level, ip);
1303 /* Add parameter and iterator names to the CloogUnionDomain. */
1305 static CloogUnionDomain *
1306 add_names_to_union_domain (scop_p scop, CloogUnionDomain *union_domain,
1307 int nb_scattering_dims, htab_t params_index)
1309 sese region = SCOP_REGION (scop);
1310 int i;
1311 int nb_iterators = scop_max_loop_depth (scop);
1312 int nb_parameters = SESE_PARAMS (region).length ();
1313 mpz_t bound_one, bound_two;
1315 mpz_init (bound_one);
1316 mpz_init (bound_two);
1318 for (i = 0; i < nb_parameters; i++)
1320 tree param = SESE_PARAMS (region)[i];
1321 const char *name = get_name (param);
1322 int len;
1323 char *parameter;
1325 if (!name)
1326 name = "T";
1328 len = strlen (name);
1329 len += 17;
1330 parameter = XNEWVEC (char, len + 1);
1331 snprintf (parameter, len, "%s_%d", name, SSA_NAME_VERSION (param));
1332 save_clast_name_index (params_index, parameter, i, i, bound_one,
1333 bound_two);
1334 union_domain = cloog_union_domain_set_name (union_domain, CLOOG_PARAM, i,
1335 parameter);
1336 compute_bounds_for_param (scop, i, bound_one, bound_two);
1337 free (parameter);
1340 mpz_clear (bound_one);
1341 mpz_clear (bound_two);
1343 for (i = 0; i < nb_iterators; i++)
1345 int len = 4 + 16;
1346 char *iterator;
1347 iterator = XNEWVEC (char, len);
1348 snprintf (iterator, len, "git_%d", i);
1349 union_domain = cloog_union_domain_set_name (union_domain, CLOOG_ITER, i,
1350 iterator);
1351 free (iterator);
1354 for (i = 0; i < nb_scattering_dims; i++)
1356 int len = 5 + 16;
1357 char *scattering;
1358 scattering = XNEWVEC (char, len);
1359 snprintf (scattering, len, "scat_%d", i);
1360 union_domain = cloog_union_domain_set_name (union_domain, CLOOG_SCAT, i,
1361 scattering);
1362 free (scattering);
1365 return union_domain;
1368 /* Initialize a CLooG input file. */
1370 static FILE *
1371 init_cloog_input_file (int scop_number)
1373 FILE *graphite_out_file;
1374 int len = strlen (dump_base_name);
1375 char *dumpname = XNEWVEC (char, len + 25);
1376 char *s_scop_number = XNEWVEC (char, 15);
1378 memcpy (dumpname, dump_base_name, len + 1);
1379 strip_off_ending (dumpname, len);
1380 sprintf (s_scop_number, ".%d", scop_number);
1381 strcat (dumpname, s_scop_number);
1382 strcat (dumpname, ".cloog");
1383 graphite_out_file = fopen (dumpname, "w+b");
1385 if (graphite_out_file == 0)
1386 fatal_error ("can%'t open %s for writing: %m", dumpname);
1388 free (dumpname);
1390 return graphite_out_file;
1393 /* Extend the scattering to NEW_DIMS scattering dimensions. */
1395 static
1396 isl_map *extend_scattering(isl_map *scattering, int new_dims)
1398 int old_dims, i;
1399 isl_space *space;
1400 isl_basic_map *change_scattering;
1401 isl_map *change_scattering_map;
1403 old_dims = isl_map_dim (scattering, isl_dim_out);
1405 space = isl_space_alloc (isl_map_get_ctx (scattering), 0, old_dims, new_dims);
1406 change_scattering = isl_basic_map_universe (isl_space_copy (space));
1408 for (i = 0; i < old_dims; i++)
1410 isl_constraint *c;
1411 c = isl_equality_alloc
1412 (isl_local_space_from_space (isl_space_copy (space)));
1413 isl_constraint_set_coefficient_si (c, isl_dim_in, i, 1);
1414 isl_constraint_set_coefficient_si (c, isl_dim_out, i, -1);
1415 change_scattering = isl_basic_map_add_constraint (change_scattering, c);
1418 for (i = old_dims; i < new_dims; i++)
1420 isl_constraint *c;
1421 c = isl_equality_alloc
1422 (isl_local_space_from_space (isl_space_copy (space)));
1423 isl_constraint_set_coefficient_si (c, isl_dim_out, i, 1);
1424 change_scattering = isl_basic_map_add_constraint (change_scattering, c);
1427 change_scattering_map = isl_map_from_basic_map (change_scattering);
1428 change_scattering_map = isl_map_align_params (change_scattering_map, space);
1429 return isl_map_apply_range (scattering, change_scattering_map);
1432 /* Build cloog union domain for SCoP. */
1434 static CloogUnionDomain *
1435 build_cloog_union_domain (scop_p scop, int nb_scattering_dims)
1437 int i;
1438 poly_bb_p pbb;
1439 CloogUnionDomain *union_domain =
1440 cloog_union_domain_alloc (scop_nb_params (scop));
1442 FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb)
1444 CloogDomain *domain;
1445 CloogScattering *scattering;
1447 /* Dead code elimination: when the domain of a PBB is empty,
1448 don't generate code for the PBB. */
1449 if (isl_set_is_empty(pbb->domain))
1450 continue;
1452 domain = cloog_domain_from_isl_set(isl_set_copy(pbb->domain));
1453 scattering = cloog_scattering_from_isl_map(extend_scattering(isl_map_copy(pbb->transformed),
1454 nb_scattering_dims));
1456 union_domain = cloog_union_domain_add_domain (union_domain, "", domain,
1457 scattering, pbb);
1460 return union_domain;
1463 /* Return the options that will be used in GLOOG. */
1465 static CloogOptions *
1466 set_cloog_options (void)
1468 CloogOptions *options = cloog_options_malloc (cloog_state);
1470 /* Change cloog output language to C. If we do use FORTRAN instead, cloog
1471 will stop e.g. with "ERROR: unbounded loops not allowed in FORTRAN.", if
1472 we pass an incomplete program to cloog. */
1473 options->language = CLOOG_LANGUAGE_C;
1475 /* Enable complex equality spreading: removes dummy statements
1476 (assignments) in the generated code which repeats the
1477 substitution equations for statements. This is useless for
1478 GLooG. */
1479 options->esp = 1;
1481 /* Silence CLooG to avoid failing tests due to debug output to stderr. */
1482 options->quiet = 1;
1484 /* Allow cloog to build strides with a stride width different to one.
1485 This example has stride = 4:
1487 for (i = 0; i < 20; i += 4)
1488 A */
1489 options->strides = 1;
1491 /* We want the clast to provide the iteration domains of the executed loops.
1492 This allows us to derive minimal/maximal values for the induction
1493 variables. */
1494 options->save_domains = 1;
1496 /* Disable optimizations and make cloog generate source code closer to the
1497 input. This is useful for debugging, but later we want the optimized
1498 code.
1500 XXX: We can not disable optimizations, as loop blocking is not working
1501 without them. */
1502 if (0)
1504 options->f = -1;
1505 options->l = INT_MAX;
1508 return options;
1511 /* Prints STMT to STDERR. */
1513 void
1514 print_clast_stmt (FILE *file, struct clast_stmt *stmt)
1516 CloogOptions *options = set_cloog_options ();
1518 clast_pprint (file, stmt, 0, options);
1519 cloog_options_free (options);
1522 /* Prints STMT to STDERR. */
1524 DEBUG_FUNCTION void
1525 debug_clast_stmt (struct clast_stmt *stmt)
1527 print_clast_stmt (stderr, stmt);
1530 /* Get the maximal number of scattering dimensions in the scop SCOP. */
1532 static
1533 int get_max_scattering_dimensions (scop_p scop)
1535 int i;
1536 poly_bb_p pbb;
1537 int scattering_dims = 0;
1539 FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb)
1541 int pbb_scatt_dims = isl_map_dim (pbb->transformed, isl_dim_out);
1542 if (pbb_scatt_dims > scattering_dims)
1543 scattering_dims = pbb_scatt_dims;
1546 return scattering_dims;
1549 static CloogInput *
1550 generate_cloog_input (scop_p scop, htab_t params_index)
1552 CloogUnionDomain *union_domain;
1553 CloogInput *cloog_input;
1554 CloogDomain *context;
1555 int nb_scattering_dims = get_max_scattering_dimensions (scop);
1557 union_domain = build_cloog_union_domain (scop, nb_scattering_dims);
1558 union_domain = add_names_to_union_domain (scop, union_domain,
1559 nb_scattering_dims,
1560 params_index);
1561 context = cloog_domain_from_isl_set (isl_set_copy (scop->context));
1563 cloog_input = cloog_input_alloc (context, union_domain);
1565 return cloog_input;
1568 /* Translate SCOP to a CLooG program and clast. These two
1569 representations should be freed together: a clast cannot be used
1570 without a program. */
1572 static struct clast_stmt *
1573 scop_to_clast (scop_p scop, htab_t params_index)
1575 CloogInput *cloog_input;
1576 struct clast_stmt *clast;
1577 CloogOptions *options = set_cloog_options ();
1579 cloog_input = generate_cloog_input (scop, params_index);
1581 /* Dump a .cloog input file, if requested. This feature is only
1582 enabled in the Graphite branch. */
1583 if (0)
1585 static size_t file_scop_number = 0;
1586 FILE *cloog_file = init_cloog_input_file (file_scop_number);
1587 cloog_input_dump_cloog (cloog_file, cloog_input, options);
1590 clast = cloog_clast_create_from_input (cloog_input, options);
1592 cloog_options_free (options);
1593 return clast;
1596 /* Prints to FILE the code generated by CLooG for SCOP. */
1598 void
1599 print_generated_program (FILE *file, scop_p scop)
1601 CloogOptions *options = set_cloog_options ();
1602 htab_t params_index;
1603 struct clast_stmt *clast;
1605 params_index = htab_create (10, clast_name_index_elt_info,
1606 eq_clast_name_indexes, free_clast_name_index);
1608 clast = scop_to_clast (scop, params_index);
1610 fprintf (file, " (clast: \n");
1611 clast_pprint (file, clast, 0, options);
1612 fprintf (file, " )\n");
1614 cloog_options_free (options);
1615 cloog_clast_free (clast);
1618 /* Prints to STDERR the code generated by CLooG for SCOP. */
1620 DEBUG_FUNCTION void
1621 debug_generated_program (scop_p scop)
1623 print_generated_program (stderr, scop);
1626 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
1627 the given SCOP. Return true if code generation succeeded.
1628 BB_PBB_MAPPING is a basic_block and it's related poly_bb_p mapping.
1631 bool
1632 gloog (scop_p scop, htab_t bb_pbb_mapping)
1634 vec<tree> newivs;
1635 newivs.create (10);
1636 loop_p context_loop;
1637 sese region = SCOP_REGION (scop);
1638 ifsese if_region = NULL;
1639 htab_t newivs_index, params_index;
1640 struct clast_stmt *clast;
1641 struct ivs_params ip;
1643 timevar_push (TV_GRAPHITE_CODE_GEN);
1644 gloog_error = false;
1646 params_index = htab_create (10, clast_name_index_elt_info,
1647 eq_clast_name_indexes, free_clast_name_index);
1649 clast = scop_to_clast (scop, params_index);
1651 if (dump_file && (dump_flags & TDF_DETAILS))
1653 fprintf (dump_file, "\nCLAST generated by CLooG: \n");
1654 print_clast_stmt (dump_file, clast);
1655 fprintf (dump_file, "\n");
1658 recompute_all_dominators ();
1659 graphite_verify ();
1661 if_region = move_sese_in_condition (region);
1662 sese_insert_phis_for_liveouts (region,
1663 if_region->region->exit->src,
1664 if_region->false_region->exit,
1665 if_region->true_region->exit);
1666 recompute_all_dominators ();
1667 graphite_verify ();
1669 context_loop = SESE_ENTRY (region)->src->loop_father;
1670 newivs_index = htab_create (10, clast_name_index_elt_info,
1671 eq_clast_name_indexes, free_clast_name_index);
1673 ip.newivs = &newivs;
1674 ip.newivs_index = newivs_index;
1675 ip.params = SESE_PARAMS (region);
1676 ip.params_index = params_index;
1677 ip.region = region;
1679 translate_clast (context_loop, clast, if_region->true_region->entry,
1680 bb_pbb_mapping, 0, &ip);
1681 graphite_verify ();
1682 scev_reset ();
1683 recompute_all_dominators ();
1684 graphite_verify ();
1686 if (gloog_error)
1687 set_ifsese_condition (if_region, integer_zero_node);
1689 free (if_region->true_region);
1690 free (if_region->region);
1691 free (if_region);
1693 htab_delete (newivs_index);
1694 htab_delete (params_index);
1695 newivs.release ();
1696 cloog_clast_free (clast);
1697 timevar_pop (TV_GRAPHITE_CODE_GEN);
1699 if (dump_file && (dump_flags & TDF_DETAILS))
1701 loop_p loop;
1702 loop_iterator li;
1703 int num_no_dependency = 0;
1705 FOR_EACH_LOOP (li, loop, 0)
1706 if (loop->can_be_parallel)
1707 num_no_dependency++;
1709 fprintf (dump_file, "\n%d loops carried no dependency.\n",
1710 num_no_dependency);
1713 return !gloog_error;
1715 #endif