OSDN Git Service

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