Mercurial > hg > CbC > CbC_gcc

comparison gcc/graphite-clast-to-gimple.c @ 55:77e2b8dfacca gcc-4.4.5

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