OSDN Git Service

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