OSDN Git Service

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