1 /* Gimple Represented as Polyhedra.
2 Copyright (C) 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <sebastian.pop@inria.fr>.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* This pass converts GIMPLE to GRAPHITE, performs some loop
22 transformations and then converts the resulting representation back
25 An early description of this pass can be found in the GCC Summit'06
26 paper "GRAPHITE: Polyhedral Analyses and Optimizations for GCC".
27 The wiki page http://gcc.gnu.org/wiki/Graphite contains pointers to
30 One important document to read is CLooG's internal manual:
31 http://repo.or.cz/w/cloog-ppl.git?a=blob_plain;f=doc/cloog.texi;hb=HEAD
32 that describes the data structure of loops used in this file, and
33 the functions that are used for transforming the code. */
37 #include "coretypes.h"
42 #include "basic-block.h"
43 #include "diagnostic.h"
44 #include "tree-flow.h"
46 #include "tree-dump.h"
49 #include "tree-chrec.h"
50 #include "tree-data-ref.h"
51 #include "tree-scalar-evolution.h"
52 #include "tree-pass.h"
54 #include "value-prof.h"
55 #include "pointer-set.h"
59 #include "cloog/cloog.h"
62 static VEC (scop_p, heap) *current_scops;
64 /* Converts a GMP constant V to a tree and returns it. */
67 gmp_cst_to_tree (tree type, Value v)
69 return build_int_cst (type, value_get_si (v));
72 /* Debug the list of old induction variables for this SCOP. */
75 debug_oldivs (scop_p scop)
80 fprintf (stderr, "Old IVs:");
82 for (i = 0; VEC_iterate (name_tree, SCOP_OLDIVS (scop), i, oldiv); i++)
84 fprintf (stderr, "(");
85 print_generic_expr (stderr, oldiv->t, 0);
86 fprintf (stderr, ", %s, %d)\n", oldiv->name, oldiv->loop->num);
88 fprintf (stderr, "\n");
91 /* Debug the loops around basic block GB. */
94 debug_loop_vec (graphite_bb_p gb)
99 fprintf (stderr, "Loop Vec:");
101 for (i = 0; VEC_iterate (loop_p, GBB_LOOPS (gb), i, loop); i++)
102 fprintf (stderr, "%d: %d, ", i, loop ? loop->num : -1);
104 fprintf (stderr, "\n");
107 /* Returns true if stack ENTRY is a constant. */
110 iv_stack_entry_is_constant (iv_stack_entry *entry)
112 return entry->kind == iv_stack_entry_const;
115 /* Returns true if stack ENTRY is an induction variable. */
118 iv_stack_entry_is_iv (iv_stack_entry *entry)
120 return entry->kind == iv_stack_entry_iv;
123 /* Push (IV, NAME) on STACK. */
126 loop_iv_stack_push_iv (loop_iv_stack stack, tree iv, const char *name)
128 iv_stack_entry *entry = XNEW (iv_stack_entry);
129 name_tree named_iv = XNEW (struct name_tree);
132 named_iv->name = name;
134 entry->kind = iv_stack_entry_iv;
135 entry->data.iv = named_iv;
137 VEC_safe_push (iv_stack_entry_p, heap, *stack, entry);
140 /* Inserts a CONSTANT in STACK at INDEX. */
143 loop_iv_stack_insert_constant (loop_iv_stack stack, int index,
146 iv_stack_entry *entry = XNEW (iv_stack_entry);
148 entry->kind = iv_stack_entry_const;
149 entry->data.constant = constant;
151 VEC_safe_insert (iv_stack_entry_p, heap, *stack, index, entry);
154 /* Pops and frees an element out of STACK. */
157 loop_iv_stack_pop (loop_iv_stack stack)
159 iv_stack_entry_p entry = VEC_pop (iv_stack_entry_p, *stack);
161 free (entry->data.iv);
165 /* Get the IV at INDEX in STACK. */
168 loop_iv_stack_get_iv (loop_iv_stack stack, int index)
170 iv_stack_entry_p entry = VEC_index (iv_stack_entry_p, *stack, index);
171 iv_stack_entry_data data = entry->data;
173 return iv_stack_entry_is_iv (entry) ? data.iv->t : data.constant;
176 /* Get the IV from its NAME in STACK. */
179 loop_iv_stack_get_iv_from_name (loop_iv_stack stack, const char* name)
182 iv_stack_entry_p entry;
184 for (i = 0; VEC_iterate (iv_stack_entry_p, *stack, i, entry); i++)
186 name_tree iv = entry->data.iv;
187 if (!strcmp (name, iv->name))
194 /* Prints on stderr the contents of STACK. */
197 debug_loop_iv_stack (loop_iv_stack stack)
200 iv_stack_entry_p entry;
203 fprintf (stderr, "(");
205 for (i = 0; VEC_iterate (iv_stack_entry_p, *stack, i, entry); i++)
210 fprintf (stderr, " ");
212 if (iv_stack_entry_is_iv (entry))
214 name_tree iv = entry->data.iv;
215 fprintf (stderr, "%s:", iv->name);
216 print_generic_expr (stderr, iv->t, 0);
220 tree constant = entry->data.constant;
221 print_generic_expr (stderr, constant, 0);
222 fprintf (stderr, ":");
223 print_generic_expr (stderr, constant, 0);
227 fprintf (stderr, ")\n");
233 free_loop_iv_stack (loop_iv_stack stack)
236 iv_stack_entry_p entry;
238 for (i = 0; VEC_iterate (iv_stack_entry_p, *stack, i, entry); i++)
240 free (entry->data.iv);
244 VEC_free (iv_stack_entry_p, heap, *stack);
249 /* Structure containing the mapping between the CLooG's induction
250 variable and the type of the old induction variable. */
251 typedef struct ivtype_map_elt
254 const char *cloog_iv;
257 /* Print to stderr the element ELT. */
260 debug_ivtype_elt (ivtype_map_elt elt)
262 fprintf (stderr, "(%s, ", elt->cloog_iv);
263 print_generic_expr (stderr, elt->type, 0);
264 fprintf (stderr, ")\n");
267 /* Helper function for debug_ivtype_map. */
270 debug_ivtype_map_1 (void **slot, void *s ATTRIBUTE_UNUSED)
272 struct ivtype_map_elt *entry = (struct ivtype_map_elt *) *slot;
273 debug_ivtype_elt (entry);
277 /* Print to stderr all the elements of MAP. */
280 debug_ivtype_map (htab_t map)
282 htab_traverse (map, debug_ivtype_map_1, NULL);
285 /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */
287 static inline ivtype_map_elt
288 new_ivtype_map_elt (const char *cloog_iv, tree type)
292 res = XNEW (struct ivtype_map_elt);
293 res->cloog_iv = cloog_iv;
299 /* Computes a hash function for database element ELT. */
302 ivtype_map_elt_info (const void *elt)
304 return htab_hash_pointer (((const struct ivtype_map_elt *) elt)->cloog_iv);
307 /* Compares database elements E1 and E2. */
310 eq_ivtype_map_elts (const void *e1, const void *e2)
312 const struct ivtype_map_elt *elt1 = (const struct ivtype_map_elt *) e1;
313 const struct ivtype_map_elt *elt2 = (const struct ivtype_map_elt *) e2;
315 return (elt1->cloog_iv == elt2->cloog_iv);
320 /* Given a CLOOG_IV, returns the type that it should have in GCC land.
321 If the information is not available, i.e. in the case one of the
322 transforms created the loop, just return integer_type_node. */
325 gcc_type_for_cloog_iv (const char *cloog_iv, graphite_bb_p gbb)
327 struct ivtype_map_elt tmp;
330 tmp.cloog_iv = cloog_iv;
331 slot = htab_find_slot (GBB_CLOOG_IV_TYPES (gbb), &tmp, NO_INSERT);
334 return ((ivtype_map_elt) *slot)->type;
336 return integer_type_node;
339 /* Inserts constants derived from the USER_STMT argument list into the
340 STACK. This is needed to map old ivs to constants when loops have
344 loop_iv_stack_patch_for_consts (loop_iv_stack stack,
345 struct clast_user_stmt *user_stmt)
347 struct clast_stmt *t;
349 CloogStatement *cs = user_stmt->statement;
350 graphite_bb_p gbb = (graphite_bb_p) cloog_statement_usr (cs);
352 for (t = user_stmt->substitutions; t; t = t->next)
354 struct clast_expr *expr = (struct clast_expr *)
355 ((struct clast_assignment *)t)->RHS;
356 struct clast_term *term = (struct clast_term *) expr;
358 /* FIXME: What should be done with expr_bin, expr_red? */
359 if (expr->type == expr_term
362 loop_p loop = gbb_loop_at_index (gbb, index);
363 tree oldiv = oldiv_for_loop (GBB_SCOP (gbb), loop);
364 tree type = oldiv ? TREE_TYPE (oldiv) : integer_type_node;
365 tree value = gmp_cst_to_tree (type, term->val);
366 loop_iv_stack_insert_constant (stack, index, value);
372 /* Removes all constants in the iv STACK. */
375 loop_iv_stack_remove_constants (loop_iv_stack stack)
378 iv_stack_entry *entry;
380 for (i = 0; VEC_iterate (iv_stack_entry_p, *stack, i, entry);)
382 if (iv_stack_entry_is_constant (entry))
384 free (VEC_index (iv_stack_entry_p, *stack, i));
385 VEC_ordered_remove (iv_stack_entry_p, *stack, i);
392 /* Returns a new loop_to_cloog_loop_str structure. */
394 static inline struct loop_to_cloog_loop_str *
395 new_loop_to_cloog_loop_str (int loop_num,
397 CloogLoop *cloog_loop)
399 struct loop_to_cloog_loop_str *result;
401 result = XNEW (struct loop_to_cloog_loop_str);
402 result->loop_num = loop_num;
403 result->cloog_loop = cloog_loop;
404 result->loop_position = loop_position;
409 /* Hash function for SCOP_LOOP2CLOOG_LOOP hash table. */
412 hash_loop_to_cloog_loop (const void *elt)
414 return ((const struct loop_to_cloog_loop_str *) elt)->loop_num;
417 /* Equality function for SCOP_LOOP2CLOOG_LOOP hash table. */
420 eq_loop_to_cloog_loop (const void *el1, const void *el2)
422 const struct loop_to_cloog_loop_str *elt1, *elt2;
424 elt1 = (const struct loop_to_cloog_loop_str *) el1;
425 elt2 = (const struct loop_to_cloog_loop_str *) el2;
426 return elt1->loop_num == elt2->loop_num;
429 /* Compares two graphite bbs and returns an integer less than, equal to, or
430 greater than zero if the first argument is considered to be respectively
431 less than, equal to, or greater than the second.
432 We compare using the lexicographic order of the static schedules. */
435 gbb_compare (const void *p_1, const void *p_2)
437 const struct graphite_bb *const gbb_1
438 = *(const struct graphite_bb *const*) p_1;
439 const struct graphite_bb *const gbb_2
440 = *(const struct graphite_bb *const*) p_2;
442 return lambda_vector_compare (GBB_STATIC_SCHEDULE (gbb_1),
443 gbb_nb_loops (gbb_1) + 1,
444 GBB_STATIC_SCHEDULE (gbb_2),
445 gbb_nb_loops (gbb_2) + 1);
448 /* Sort graphite bbs in SCOP. */
451 graphite_sort_gbbs (scop_p scop)
453 VEC (graphite_bb_p, heap) *bbs = SCOP_BBS (scop);
455 qsort (VEC_address (graphite_bb_p, bbs),
456 VEC_length (graphite_bb_p, bbs),
457 sizeof (graphite_bb_p), gbb_compare);
460 /* Dump conditions of a graphite basic block GBB on FILE. */
463 dump_gbb_conditions (FILE *file, graphite_bb_p gbb)
467 VEC (gimple, heap) *conditions = GBB_CONDITIONS (gbb);
469 if (VEC_empty (gimple, conditions))
472 fprintf (file, "\tbb %d\t: cond = {", GBB_BB (gbb)->index);
474 for (i = 0; VEC_iterate (gimple, conditions, i, stmt); i++)
475 print_gimple_stmt (file, stmt, 0, 0);
477 fprintf (file, "}\n");
480 /* Converts the graphite scheduling function into a cloog scattering
481 matrix. This scattering matrix is used to limit the possible cloog
482 output to valid programs in respect to the scheduling function.
484 SCATTERING_DIMENSIONS specifies the dimensionality of the scattering
485 matrix. CLooG 0.14.0 and previous versions require, that all scattering
486 functions of one CloogProgram have the same dimensionality, therefore we
487 allow to specify it. (Should be removed in future versions) */
490 schedule_to_scattering (graphite_bb_p gb, int scattering_dimensions)
493 scop_p scop = GBB_SCOP (gb);
495 int nb_iterators = gbb_nb_loops (gb);
497 /* The cloog scattering matrix consists of these colums:
499 scattering_dimensions cols = Scattering dimensions,
500 nb_iterators cols = bb's iterators,
501 scop_nb_params cols = Parameters,
506 scattering_dimensions = 5
516 s1 s2 s3 s4 s5 i p1 p2 1
517 1 0 0 0 0 0 0 0 -4 = 0
518 0 1 0 0 0 -1 0 0 0 = 0
519 0 0 1 0 0 0 0 0 -5 = 0 */
520 int nb_params = scop_nb_params (scop);
521 int nb_cols = 1 + scattering_dimensions + nb_iterators + nb_params + 1;
522 int col_const = nb_cols - 1;
523 int col_iter_offset = 1 + scattering_dimensions;
525 CloogMatrix *scat = cloog_matrix_alloc (scattering_dimensions, nb_cols);
527 gcc_assert (scattering_dimensions >= nb_iterators * 2 + 1);
529 /* Initialize the identity matrix. */
530 for (i = 0; i < scattering_dimensions; i++)
531 value_set_si (scat->p[i][i + 1], 1);
533 /* Textual order outside the first loop */
534 value_set_si (scat->p[0][col_const], -GBB_STATIC_SCHEDULE (gb)[0]);
536 /* For all surrounding loops. */
537 for (i = 0; i < nb_iterators; i++)
539 int schedule = GBB_STATIC_SCHEDULE (gb)[i + 1];
541 /* Iterations of this loop. */
542 value_set_si (scat->p[2 * i + 1][col_iter_offset + i], -1);
544 /* Textual order inside this loop. */
545 value_set_si (scat->p[2 * i + 2][col_const], -schedule);
551 /* Print the schedules of GB to FILE with INDENT white spaces before.
552 VERBOSITY determines how verbose the code pretty printers are. */
555 print_graphite_bb (FILE *file, graphite_bb_p gb, int indent, int verbosity)
557 CloogMatrix *scattering;
560 fprintf (file, "\nGBB (\n");
562 print_loops_bb (file, GBB_BB (gb), indent+2, verbosity);
566 fprintf (file, " (domain: \n");
567 cloog_matrix_print (file, GBB_DOMAIN (gb));
568 fprintf (file, " )\n");
571 if (GBB_STATIC_SCHEDULE (gb))
573 fprintf (file, " (static schedule: ");
574 print_lambda_vector (file, GBB_STATIC_SCHEDULE (gb),
575 gbb_nb_loops (gb) + 1);
576 fprintf (file, " )\n");
581 fprintf (file, " (contained loops: \n");
582 for (i = 0; VEC_iterate (loop_p, GBB_LOOPS (gb), i, loop); i++)
584 fprintf (file, " iterator %d => NULL \n", i);
586 fprintf (file, " iterator %d => loop %d \n", i,
588 fprintf (file, " )\n");
591 if (GBB_DATA_REFS (gb))
592 dump_data_references (file, GBB_DATA_REFS (gb));
594 if (GBB_CONDITIONS (gb))
596 fprintf (file, " (conditions: \n");
597 dump_gbb_conditions (file, gb);
598 fprintf (file, " )\n");
602 && GBB_STATIC_SCHEDULE (gb))
604 fprintf (file, " (scattering: \n");
605 scattering = schedule_to_scattering (gb, 2 * gbb_nb_loops (gb) + 1);
606 cloog_matrix_print (file, scattering);
607 cloog_matrix_free (scattering);
608 fprintf (file, " )\n");
611 fprintf (file, ")\n");
614 /* Print to STDERR the schedules of GB with VERBOSITY level. */
617 debug_gbb (graphite_bb_p gb, int verbosity)
619 print_graphite_bb (stderr, gb, 0, verbosity);
623 /* Print SCOP to FILE. VERBOSITY determines how verbose the pretty
627 print_scop (FILE *file, scop_p scop, int verbosity)
632 fprintf (file, "\nSCoP_%d_%d (\n",
633 SCOP_ENTRY (scop)->index, SCOP_EXIT (scop)->index);
635 fprintf (file, " (cloog: \n");
636 cloog_program_print (file, SCOP_PROG (scop));
637 fprintf (file, " )\n");
644 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
645 print_graphite_bb (file, gb, 0, verbosity);
648 fprintf (file, ")\n");
651 /* Print all the SCOPs to FILE. VERBOSITY determines how verbose the
652 code pretty printers are. */
655 print_scops (FILE *file, int verbosity)
660 for (i = 0; VEC_iterate (scop_p, current_scops, i, scop); i++)
661 print_scop (file, scop, verbosity);
664 /* Debug SCOP. VERBOSITY determines how verbose the code pretty
668 debug_scop (scop_p scop, int verbosity)
670 print_scop (stderr, scop, verbosity);
673 /* Debug all SCOPs from CURRENT_SCOPS. VERBOSITY determines how
674 verbose the code pretty printers are. */
677 debug_scops (int verbosity)
679 print_scops (stderr, verbosity);
682 /* Pretty print to FILE the SCOP in DOT format. */
685 dot_scop_1 (FILE *file, scop_p scop)
690 basic_block entry = SCOP_ENTRY (scop);
691 basic_block exit = SCOP_EXIT (scop);
693 fprintf (file, "digraph SCoP_%d_%d {\n", entry->index,
699 fprintf (file, "%d [shape=triangle];\n", bb->index);
702 fprintf (file, "%d [shape=box];\n", bb->index);
704 if (bb_in_scop_p (bb, scop))
705 fprintf (file, "%d [color=red];\n", bb->index);
707 FOR_EACH_EDGE (e, ei, bb->succs)
708 fprintf (file, "%d -> %d;\n", bb->index, e->dest->index);
711 fputs ("}\n\n", file);
714 /* Display SCOP using dotty. */
717 dot_scop (scop_p scop)
719 dot_scop_1 (stderr, scop);
722 /* Pretty print all SCoPs in DOT format and mark them with different colors.
723 If there are not enough colors, paint later SCoPs gray.
725 - "*" after the node number: entry of a SCoP,
726 - "#" after the node number: exit of a SCoP,
727 - "()" entry or exit not part of SCoP. */
730 dot_all_scops_1 (FILE *file)
739 /* Disable debugging while printing graph. */
740 int tmp_dump_flags = dump_flags;
743 fprintf (file, "digraph all {\n");
747 int part_of_scop = false;
749 /* Use HTML for every bb label. So we are able to print bbs
750 which are part of two different SCoPs, with two different
751 background colors. */
752 fprintf (file, "%d [label=<\n <TABLE BORDER=\"0\" CELLBORDER=\"1\" ",
754 fprintf (file, "CELLSPACING=\"0\">\n");
756 /* Select color for SCoP. */
757 for (i = 0; VEC_iterate (scop_p, current_scops, i, scop); i++)
758 if (bb_in_scop_p (bb, scop)
759 || (SCOP_EXIT (scop) == bb)
760 || (SCOP_ENTRY (scop) == bb))
819 fprintf (file, " <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">", color);
821 if (!bb_in_scop_p (bb, scop))
822 fprintf (file, " (");
824 if (bb == SCOP_ENTRY (scop)
825 && bb == SCOP_EXIT (scop))
826 fprintf (file, " %d*# ", bb->index);
827 else if (bb == SCOP_ENTRY (scop))
828 fprintf (file, " %d* ", bb->index);
829 else if (bb == SCOP_EXIT (scop))
830 fprintf (file, " %d# ", bb->index);
832 fprintf (file, " %d ", bb->index);
834 if (!bb_in_scop_p (bb, scop))
837 fprintf (file, "</TD></TR>\n");
843 fprintf (file, " <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">");
844 fprintf (file, " %d </TD></TR>\n", bb->index);
847 fprintf (file, " </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n");
852 FOR_EACH_EDGE (e, ei, bb->succs)
853 fprintf (file, "%d -> %d;\n", bb->index, e->dest->index);
856 fputs ("}\n\n", file);
858 /* Enable debugging again. */
859 dump_flags = tmp_dump_flags;
862 /* Display all SCoPs using dotty. */
867 /* When debugging, enable the following code. This cannot be used
868 in production compilers because it calls "system". */
870 FILE *stream = fopen ("/tmp/allscops.dot", "w");
873 dot_all_scops_1 (stream);
876 system ("dotty /tmp/allscops.dot");
878 dot_all_scops_1 (stderr);
882 /* Returns the outermost loop in SCOP that contains BB. */
885 outermost_loop_in_scop (scop_p scop, basic_block bb)
889 nest = bb->loop_father;
890 while (loop_outer (nest) && loop_in_scop_p (loop_outer (nest), scop))
891 nest = loop_outer (nest);
896 /* Returns the block preceding the entry of SCOP. */
899 block_before_scop (scop_p scop)
901 return SESE_ENTRY (SCOP_REGION (scop))->src;
904 /* Return true when EXPR is an affine function in LOOP with parameters
905 instantiated relative to SCOP_ENTRY. */
908 loop_affine_expr (basic_block scop_entry, struct loop *loop, tree expr)
911 tree scev = analyze_scalar_evolution (loop, expr);
913 scev = instantiate_scev (scop_entry, loop, scev);
915 return (evolution_function_is_invariant_p (scev, n)
916 || evolution_function_is_affine_multivariate_p (scev, n));
919 /* Return false if the tree_code of the operand OP or any of its operands
923 exclude_component_ref (tree op)
930 if (TREE_CODE (op) == COMPONENT_REF)
934 len = TREE_OPERAND_LENGTH (op);
935 for (i = 0; i < len; ++i)
937 if (!exclude_component_ref (TREE_OPERAND (op, i)))
946 /* Return true if the operand OP is simple. */
949 is_simple_operand (loop_p loop, gimple stmt, tree op)
951 /* It is not a simple operand when it is a declaration, */
953 /* or a structure, */
954 || AGGREGATE_TYPE_P (TREE_TYPE (op))
955 /* or a memory access that cannot be analyzed by the data
956 reference analysis. */
957 || ((handled_component_p (op) || INDIRECT_REF_P (op))
958 && !stmt_simple_memref_p (loop, stmt, op)))
961 return exclude_component_ref (op);
964 /* Return true only when STMT is simple enough for being handled by
965 Graphite. This depends on SCOP_ENTRY, as the parametetrs are
966 initialized relatively to this basic block. */
969 stmt_simple_for_scop_p (basic_block scop_entry, gimple stmt)
971 basic_block bb = gimple_bb (stmt);
972 struct loop *loop = bb->loop_father;
974 /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
975 Calls have side-effects, except those to const or pure
977 if (gimple_has_volatile_ops (stmt)
978 || (gimple_code (stmt) == GIMPLE_CALL
979 && !(gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE)))
980 || (gimple_code (stmt) == GIMPLE_ASM))
983 switch (gimple_code (stmt))
993 enum tree_code code = gimple_cond_code (stmt);
995 /* We can only handle this kind of conditional expressions.
996 For inequalities like "if (i != 3 * k)" we need unions of
997 polyhedrons. Expressions like "if (a)" or "if (a == 15)" need
998 them for the else branch. */
999 if (!(code == LT_EXPR
1002 || code == GE_EXPR))
1008 FOR_EACH_SSA_TREE_OPERAND (op, stmt, op_iter, SSA_OP_ALL_USES)
1009 if (!loop_affine_expr (scop_entry, loop, op))
1017 enum tree_code code = gimple_assign_rhs_code (stmt);
1019 switch (get_gimple_rhs_class (code))
1021 case GIMPLE_UNARY_RHS:
1022 case GIMPLE_SINGLE_RHS:
1023 return (is_simple_operand (loop, stmt, gimple_assign_lhs (stmt))
1024 && is_simple_operand (loop, stmt, gimple_assign_rhs1 (stmt)));
1026 case GIMPLE_BINARY_RHS:
1027 return (is_simple_operand (loop, stmt, gimple_assign_lhs (stmt))
1028 && is_simple_operand (loop, stmt, gimple_assign_rhs1 (stmt))
1029 && is_simple_operand (loop, stmt, gimple_assign_rhs2 (stmt)));
1031 case GIMPLE_INVALID_RHS:
1040 size_t n = gimple_call_num_args (stmt);
1041 tree lhs = gimple_call_lhs (stmt);
1043 for (i = 0; i < n; i++)
1045 tree arg = gimple_call_arg (stmt, i);
1047 if (!(is_simple_operand (loop, stmt, lhs)
1048 && is_simple_operand (loop, stmt, arg)))
1056 /* These nodes cut a new scope. */
1063 /* Returns the statement of BB that contains a harmful operation: that
1064 can be a function call with side effects, the induction variables
1065 are not linear with respect to SCOP_ENTRY, etc. The current open
1066 scop should end before this statement. */
1069 harmful_stmt_in_bb (basic_block scop_entry, basic_block bb)
1071 gimple_stmt_iterator gsi;
1073 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1074 if (!stmt_simple_for_scop_p (scop_entry, gsi_stmt (gsi)))
1075 return gsi_stmt (gsi);
1080 /* Returns true when BB will be represented in graphite. Return false
1081 for the basic blocks that contain code eliminated in the code
1082 generation pass: i.e. induction variables and exit conditions. */
1085 graphite_stmt_p (scop_p scop, basic_block bb,
1086 VEC (data_reference_p, heap) *drs)
1088 gimple_stmt_iterator gsi;
1089 loop_p loop = bb->loop_father;
1091 if (VEC_length (data_reference_p, drs) > 0)
1094 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1096 gimple stmt = gsi_stmt (gsi);
1098 switch (gimple_code (stmt))
1100 /* Control flow expressions can be ignored, as they are
1101 represented in the iteration domains and will be
1102 regenerated by graphite. */
1110 tree var = gimple_assign_lhs (stmt);
1111 var = analyze_scalar_evolution (loop, var);
1112 var = instantiate_scev (block_before_scop (scop), loop, var);
1114 if (chrec_contains_undetermined (var))
1128 /* Store the GRAPHITE representation of BB. */
1131 new_graphite_bb (scop_p scop, basic_block bb)
1133 struct graphite_bb *gbb;
1134 VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 5);
1135 struct loop *nest = outermost_loop_in_scop (scop, bb);
1136 gimple_stmt_iterator gsi;
1138 bitmap_set_bit (SCOP_BBS_B (scop), bb->index);
1140 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1141 find_data_references_in_stmt (nest, gsi_stmt (gsi), &drs);
1143 if (!graphite_stmt_p (scop, bb, drs))
1145 free_data_refs (drs);
1149 gbb = XNEW (struct graphite_bb);
1152 GBB_SCOP (gbb) = scop;
1153 GBB_DATA_REFS (gbb) = drs;
1154 GBB_DOMAIN (gbb) = NULL;
1155 GBB_CONDITIONS (gbb) = NULL;
1156 GBB_CONDITION_CASES (gbb) = NULL;
1157 GBB_LOOPS (gbb) = NULL;
1158 GBB_STATIC_SCHEDULE (gbb) = NULL;
1159 GBB_CLOOG_IV_TYPES (gbb) = NULL;
1160 VEC_safe_push (graphite_bb_p, heap, SCOP_BBS (scop), gbb);
1166 free_graphite_bb (struct graphite_bb *gbb)
1168 if (GBB_DOMAIN (gbb))
1169 cloog_matrix_free (GBB_DOMAIN (gbb));
1171 if (GBB_CLOOG_IV_TYPES (gbb))
1172 htab_delete (GBB_CLOOG_IV_TYPES (gbb));
1174 /* FIXME: free_data_refs is disabled for the moment, but should be
1177 free_data_refs (GBB_DATA_REFS (gbb)); */
1179 VEC_free (gimple, heap, GBB_CONDITIONS (gbb));
1180 VEC_free (gimple, heap, GBB_CONDITION_CASES (gbb));
1181 VEC_free (loop_p, heap, GBB_LOOPS (gbb));
1182 GBB_BB (gbb)->aux = 0;
1188 /* Structure containing the mapping between the old names and the new
1189 names used after block copy in the new loop context. */
1190 typedef struct rename_map_elt
1192 tree old_name, new_name;
1196 /* Print to stderr the element ELT. */
1199 debug_rename_elt (rename_map_elt elt)
1201 fprintf (stderr, "(");
1202 print_generic_expr (stderr, elt->old_name, 0);
1203 fprintf (stderr, ", ");
1204 print_generic_expr (stderr, elt->new_name, 0);
1205 fprintf (stderr, ")\n");
1208 /* Helper function for debug_rename_map. */
1211 debug_rename_map_1 (void **slot, void *s ATTRIBUTE_UNUSED)
1213 struct rename_map_elt *entry = (struct rename_map_elt *) *slot;
1214 debug_rename_elt (entry);
1218 /* Print to stderr all the elements of MAP. */
1221 debug_rename_map (htab_t map)
1223 htab_traverse (map, debug_rename_map_1, NULL);
1226 /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */
1228 static inline rename_map_elt
1229 new_rename_map_elt (tree old_name, tree new_name)
1233 res = XNEW (struct rename_map_elt);
1234 res->old_name = old_name;
1235 res->new_name = new_name;
1240 /* Computes a hash function for database element ELT. */
1243 rename_map_elt_info (const void *elt)
1245 return htab_hash_pointer (((const struct rename_map_elt *) elt)->old_name);
1248 /* Compares database elements E1 and E2. */
1251 eq_rename_map_elts (const void *e1, const void *e2)
1253 const struct rename_map_elt *elt1 = (const struct rename_map_elt *) e1;
1254 const struct rename_map_elt *elt2 = (const struct rename_map_elt *) e2;
1256 return (elt1->old_name == elt2->old_name);
1259 /* Returns the new name associated to OLD_NAME in MAP. */
1262 get_new_name_from_old_name (htab_t map, tree old_name)
1264 struct rename_map_elt tmp;
1267 tmp.old_name = old_name;
1268 slot = htab_find_slot (map, &tmp, NO_INSERT);
1271 return ((rename_map_elt) *slot)->new_name;
1278 /* Returns true when BB is in REGION. */
1281 bb_in_sese_p (basic_block bb, sese region)
1283 return pointer_set_contains (SESE_REGION_BBS (region), bb);
1286 /* For a USE in BB, if BB is outside REGION, mark the USE in the
1287 SESE_LIVEIN and SESE_LIVEOUT sets. */
1290 sese_build_livein_liveouts_use (sese region, basic_block bb, tree use)
1295 if (TREE_CODE (use) != SSA_NAME)
1298 ver = SSA_NAME_VERSION (use);
1299 def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
1301 || !bb_in_sese_p (def_bb, region)
1302 || bb_in_sese_p (bb, region))
1305 if (!SESE_LIVEIN_VER (region, ver))
1306 SESE_LIVEIN_VER (region, ver) = BITMAP_ALLOC (NULL);
1308 bitmap_set_bit (SESE_LIVEIN_VER (region, ver), bb->index);
1309 bitmap_set_bit (SESE_LIVEOUT (region), ver);
1312 /* Marks for rewrite all the SSA_NAMES defined in REGION and that are
1313 used in BB that is outside of the REGION. */
1316 sese_build_livein_liveouts_bb (sese region, basic_block bb)
1318 gimple_stmt_iterator bsi;
1324 FOR_EACH_EDGE (e, ei, bb->succs)
1325 for (bsi = gsi_start_phis (e->dest); !gsi_end_p (bsi); gsi_next (&bsi))
1326 sese_build_livein_liveouts_use (region, bb,
1327 PHI_ARG_DEF_FROM_EDGE (gsi_stmt (bsi), e));
1329 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
1330 FOR_EACH_SSA_TREE_OPERAND (var, gsi_stmt (bsi), iter, SSA_OP_ALL_USES)
1331 sese_build_livein_liveouts_use (region, bb, var);
1334 /* Build the SESE_LIVEIN and SESE_LIVEOUT for REGION. */
1337 sese_build_livein_liveouts (sese region)
1341 SESE_LIVEOUT (region) = BITMAP_ALLOC (NULL);
1342 SESE_NUM_VER (region) = num_ssa_names;
1343 SESE_LIVEIN (region) = XCNEWVEC (bitmap, SESE_NUM_VER (region));
1346 sese_build_livein_liveouts_bb (region, bb);
1349 /* Register basic blocks belonging to a region in a pointer set. */
1352 register_bb_in_sese (basic_block entry_bb, basic_block exit_bb, sese region)
1356 basic_block bb = entry_bb;
1358 FOR_EACH_EDGE (e, ei, bb->succs)
1360 if (!pointer_set_contains (SESE_REGION_BBS (region), e->dest) &&
1361 e->dest->index != exit_bb->index)
1363 pointer_set_insert (SESE_REGION_BBS (region), e->dest);
1364 register_bb_in_sese (e->dest, exit_bb, region);
1369 /* Builds a new SESE region from edges ENTRY and EXIT. */
1372 new_sese (edge entry, edge exit)
1374 sese res = XNEW (struct sese);
1376 SESE_ENTRY (res) = entry;
1377 SESE_EXIT (res) = exit;
1378 SESE_REGION_BBS (res) = pointer_set_create ();
1379 register_bb_in_sese (entry->dest, exit->dest, res);
1381 SESE_LIVEOUT (res) = NULL;
1382 SESE_NUM_VER (res) = 0;
1383 SESE_LIVEIN (res) = NULL;
1388 /* Deletes REGION. */
1391 free_sese (sese region)
1395 for (i = 0; i < SESE_NUM_VER (region); i++)
1396 BITMAP_FREE (SESE_LIVEIN_VER (region, i));
1398 if (SESE_LIVEIN (region))
1399 free (SESE_LIVEIN (region));
1401 if (SESE_LIVEOUT (region))
1402 BITMAP_FREE (SESE_LIVEOUT (region));
1404 pointer_set_destroy (SESE_REGION_BBS (region));
1410 /* Creates a new scop starting with ENTRY. */
1413 new_scop (edge entry, edge exit)
1415 scop_p scop = XNEW (struct scop);
1417 gcc_assert (entry && exit);
1419 SCOP_REGION (scop) = new_sese (entry, exit);
1420 SCOP_BBS (scop) = VEC_alloc (graphite_bb_p, heap, 3);
1421 SCOP_OLDIVS (scop) = VEC_alloc (name_tree, heap, 3);
1422 SCOP_BBS_B (scop) = BITMAP_ALLOC (NULL);
1423 SCOP_LOOPS (scop) = BITMAP_ALLOC (NULL);
1424 SCOP_LOOP_NEST (scop) = VEC_alloc (loop_p, heap, 3);
1425 SCOP_ADD_PARAMS (scop) = true;
1426 SCOP_PARAMS (scop) = VEC_alloc (name_tree, heap, 3);
1427 SCOP_PROG (scop) = cloog_program_malloc ();
1428 cloog_program_set_names (SCOP_PROG (scop), cloog_names_malloc ());
1429 SCOP_LOOP2CLOOG_LOOP (scop) = htab_create (10, hash_loop_to_cloog_loop,
1430 eq_loop_to_cloog_loop,
1432 SCOP_LIVEOUT_RENAMES (scop) = htab_create (10, rename_map_elt_info,
1433 eq_rename_map_elts, free);
1440 free_scop (scop_p scop)
1444 struct graphite_bb *gb;
1447 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
1448 free_graphite_bb (gb);
1450 VEC_free (graphite_bb_p, heap, SCOP_BBS (scop));
1451 BITMAP_FREE (SCOP_BBS_B (scop));
1452 BITMAP_FREE (SCOP_LOOPS (scop));
1453 VEC_free (loop_p, heap, SCOP_LOOP_NEST (scop));
1455 for (i = 0; VEC_iterate (name_tree, SCOP_OLDIVS (scop), i, iv); i++)
1457 VEC_free (name_tree, heap, SCOP_OLDIVS (scop));
1459 for (i = 0; VEC_iterate (name_tree, SCOP_PARAMS (scop), i, p); i++)
1462 VEC_free (name_tree, heap, SCOP_PARAMS (scop));
1463 cloog_program_free (SCOP_PROG (scop));
1464 htab_delete (SCOP_LOOP2CLOOG_LOOP (scop));
1465 htab_delete (SCOP_LIVEOUT_RENAMES (scop));
1466 free_sese (SCOP_REGION (scop));
1470 /* Deletes all scops in SCOPS. */
1473 free_scops (VEC (scop_p, heap) *scops)
1478 for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++)
1481 VEC_free (scop_p, heap, scops);
1484 typedef enum gbb_type {
1486 GBB_LOOP_SING_EXIT_HEADER,
1487 GBB_LOOP_MULT_EXIT_HEADER,
1494 /* Detect the type of BB. Loop headers are only marked, if they are
1495 new. This means their loop_father is different to LAST_LOOP.
1496 Otherwise they are treated like any other bb and their type can be
1500 get_bb_type (basic_block bb, struct loop *last_loop)
1502 VEC (basic_block, heap) *dom;
1504 struct loop *loop = bb->loop_father;
1506 /* Check, if we entry into a new loop. */
1507 if (loop != last_loop)
1509 if (single_exit (loop) != NULL)
1510 return GBB_LOOP_SING_EXIT_HEADER;
1511 else if (loop->num != 0)
1512 return GBB_LOOP_MULT_EXIT_HEADER;
1514 return GBB_COND_HEADER;
1517 dom = get_dominated_by (CDI_DOMINATORS, bb);
1518 nb_dom = VEC_length (basic_block, dom);
1519 VEC_free (basic_block, heap, dom);
1524 nb_suc = VEC_length (edge, bb->succs);
1526 if (nb_dom == 1 && nb_suc == 1)
1529 return GBB_COND_HEADER;
1532 /* A SCoP detection region, defined using bbs as borders.
1533 All control flow touching this region, comes in passing basic_block ENTRY and
1534 leaves passing basic_block EXIT. By using bbs instead of edges for the
1535 borders we are able to represent also regions that do not have a single
1537 But as they have a single entry basic_block and a single exit basic_block, we
1538 are able to generate for every sd_region a single entry and exit edge.
1545 / \ This region contains: {3, 4, 5, 6, 7, 8}
1553 typedef struct sd_region_p
1555 /* The entry bb dominates all bbs in the sd_region. It is part of the
1559 /* The exit bb postdominates all bbs in the sd_region, but is not
1560 part of the region. */
1564 DEF_VEC_O(sd_region);
1565 DEF_VEC_ALLOC_O(sd_region, heap);
1568 /* Moves the scops from SOURCE to TARGET and clean up SOURCE. */
1571 move_sd_regions (VEC (sd_region, heap) **source, VEC (sd_region, heap) **target)
1576 for (i = 0; VEC_iterate (sd_region, *source, i, s); i++)
1577 VEC_safe_push (sd_region, heap, *target, s);
1579 VEC_free (sd_region, heap, *source);
1582 /* Return true when it is not possible to represent the upper bound of
1583 LOOP in the polyhedral representation. */
1586 graphite_cannot_represent_loop_niter (loop_p loop)
1588 tree niter = number_of_latch_executions (loop);
1590 return chrec_contains_undetermined (niter)
1591 || !scev_is_linear_expression (niter);
1593 /* Store information needed by scopdet_* functions. */
1597 /* Where the last open scop would stop if the current BB is harmful. */
1600 /* Where the next scop would start if the current BB is harmful. */
1603 /* The bb or one of its children contains open loop exits. That means
1604 loop exit nodes that are not surrounded by a loop dominated by bb. */
1607 /* The bb or one of its children contains only structures we can handle. */
1612 static struct scopdet_info build_scops_1 (basic_block, VEC (sd_region, heap) **,
1615 /* Calculates BB infos. If bb is difficult we add valid SCoPs dominated by BB
1616 to SCOPS. TYPE is the gbb_type of BB. */
1618 static struct scopdet_info
1619 scopdet_basic_block_info (basic_block bb, VEC (sd_region, heap) **scops,
1622 struct loop *loop = bb->loop_father;
1623 struct scopdet_info result;
1626 /* XXX: ENTRY_BLOCK_PTR could be optimized in later steps. */
1627 stmt = harmful_stmt_in_bb (ENTRY_BLOCK_PTR, bb);
1628 result.difficult = (stmt != NULL);
1635 result.exits = false;
1640 result.next = single_succ (bb);
1641 result.exits = false;
1645 case GBB_LOOP_SING_EXIT_HEADER:
1647 VEC (sd_region, heap) *tmp_scops = VEC_alloc (sd_region, heap,3);
1648 struct scopdet_info sinfo;
1650 sinfo = build_scops_1 (bb, &tmp_scops, loop);
1652 result.last = single_exit (bb->loop_father)->src;
1653 result.next = single_exit (bb->loop_father)->dest;
1655 /* If we do not dominate result.next, remove it. It's either
1656 the EXIT_BLOCK_PTR, or another bb dominates it and will
1657 call the scop detection for this bb. */
1658 if (!dominated_by_p (CDI_DOMINATORS, result.next, bb))
1661 if (result.last->loop_father != loop)
1664 if (graphite_cannot_represent_loop_niter (loop))
1665 result.difficult = true;
1667 if (sinfo.difficult)
1668 move_sd_regions (&tmp_scops, scops);
1670 VEC_free (sd_region, heap, tmp_scops);
1672 result.exits = false;
1673 result.difficult |= sinfo.difficult;
1677 case GBB_LOOP_MULT_EXIT_HEADER:
1679 /* XXX: For now we just do not join loops with multiple exits. If the
1680 exits lead to the same bb it may be possible to join the loop. */
1681 VEC (sd_region, heap) *tmp_scops = VEC_alloc (sd_region, heap, 3);
1682 VEC (edge, heap) *exits = get_loop_exit_edges (loop);
1685 build_scops_1 (bb, &tmp_scops, loop);
1687 /* Scan the code dominated by this loop. This means all bbs, that are
1688 are dominated by a bb in this loop, but are not part of this loop.
1691 - The loop exit destination is dominated by the exit sources.
1693 TODO: We miss here the more complex cases:
1694 - The exit destinations are dominated by another bb inside the
1696 - The loop dominates bbs, that are not exit destinations. */
1697 for (i = 0; VEC_iterate (edge, exits, i, e); i++)
1698 if (e->src->loop_father == loop
1699 && dominated_by_p (CDI_DOMINATORS, e->dest, e->src))
1701 /* Pass loop_outer to recognize e->dest as loop header in
1703 if (e->dest->loop_father->header == e->dest)
1704 build_scops_1 (e->dest, &tmp_scops,
1705 loop_outer (e->dest->loop_father));
1707 build_scops_1 (e->dest, &tmp_scops, e->dest->loop_father);
1712 result.difficult = true;
1713 result.exits = false;
1714 move_sd_regions (&tmp_scops, scops);
1715 VEC_free (edge, heap, exits);
1718 case GBB_COND_HEADER:
1720 VEC (sd_region, heap) *tmp_scops = VEC_alloc (sd_region, heap, 3);
1721 struct scopdet_info sinfo;
1722 VEC (basic_block, heap) *dominated;
1725 basic_block last_bb = NULL;
1727 result.exits = false;
1729 /* First check the successors of BB, and check if it is possible to join
1730 the different branches. */
1731 for (i = 0; VEC_iterate (edge, bb->succs, i, e); i++)
1733 /* Ignore loop exits. They will be handled after the loop body. */
1734 if (is_loop_exit (loop, e->dest))
1736 result.exits = true;
1740 /* Do not follow edges that lead to the end of the
1741 conditions block. For example, in
1751 the edge from 0 => 6. Only check if all paths lead to
1754 if (!single_pred_p (e->dest))
1756 /* Check, if edge leads directly to the end of this
1763 if (e->dest != last_bb)
1764 result.difficult = true;
1769 if (!dominated_by_p (CDI_DOMINATORS, e->dest, bb))
1771 result.difficult = true;
1775 sinfo = build_scops_1 (e->dest, &tmp_scops, loop);
1777 result.exits |= sinfo.exits;
1778 result.last = sinfo.last;
1779 result.difficult |= sinfo.difficult;
1781 /* Checks, if all branches end at the same point.
1782 If that is true, the condition stays joinable.
1783 Have a look at the example above. */
1784 if (sinfo.last && single_succ_p (sinfo.last))
1786 basic_block next_tmp = single_succ (sinfo.last);
1791 if (next_tmp != last_bb)
1792 result.difficult = true;
1795 result.difficult = true;
1798 /* If the condition is joinable. */
1799 if (!result.exits && !result.difficult)
1801 /* Only return a next pointer if we dominate this pointer.
1802 Otherwise it will be handled by the bb dominating it. */
1803 if (dominated_by_p (CDI_DOMINATORS, last_bb, bb) && last_bb != bb)
1804 result.next = last_bb;
1808 VEC_free (sd_region, heap, tmp_scops);
1812 /* Scan remaining bbs dominated by BB. */
1813 dominated = get_dominated_by (CDI_DOMINATORS, bb);
1815 for (i = 0; VEC_iterate (basic_block, dominated, i, dom_bb); i++)
1817 /* Ignore loop exits: they will be handled after the loop body. */
1818 if (loop_depth (find_common_loop (loop, dom_bb->loop_father))
1819 < loop_depth (loop))
1821 result.exits = true;
1825 /* Ignore the bbs processed above. */
1826 if (single_pred_p (dom_bb) && single_pred (dom_bb) == bb)
1829 if (loop_depth (loop) > loop_depth (dom_bb->loop_father))
1830 sinfo = build_scops_1 (dom_bb, &tmp_scops, loop_outer (loop));
1832 sinfo = build_scops_1 (dom_bb, &tmp_scops, loop);
1835 result.exits |= sinfo.exits;
1836 result.difficult = true;
1840 VEC_free (basic_block, heap, dominated);
1843 move_sd_regions (&tmp_scops, scops);
1855 /* Creates the SCoPs and writes entry and exit points for every SCoP. */
1857 static struct scopdet_info
1858 build_scops_1 (basic_block current, VEC (sd_region, heap) **scops, loop_p loop)
1860 bool in_scop = false;
1861 sd_region open_scop;
1862 struct scopdet_info sinfo;
1864 /* Initialize result. */
1865 struct scopdet_info result;
1866 result.exits = false;
1867 result.difficult = false;
1870 open_scop.entry = NULL;
1871 open_scop.exit = NULL;
1874 /* Loop over the dominance tree. If we meet a difficult bb, close
1875 the current SCoP. Loop and condition header start a new layer,
1876 and can only be added if all bbs in deeper layers are simple. */
1877 while (current != NULL)
1879 sinfo = scopdet_basic_block_info (current, scops, get_bb_type (current,
1882 if (!in_scop && !(sinfo.exits || sinfo.difficult))
1884 open_scop.entry = current;
1885 open_scop.exit = NULL;
1888 else if (in_scop && (sinfo.exits || sinfo.difficult))
1890 open_scop.exit = current;
1891 VEC_safe_push (sd_region, heap, *scops, &open_scop);
1895 result.difficult |= sinfo.difficult;
1896 result.exits |= sinfo.exits;
1898 current = sinfo.next;
1901 /* Try to close open_scop, if we are still in an open SCoP. */
1907 for (i = 0; VEC_iterate (edge, sinfo.last->succs, i, e); i++)
1908 if (dominated_by_p (CDI_POST_DOMINATORS, sinfo.last, e->dest))
1909 open_scop.exit = e->dest;
1911 if (!open_scop.exit && open_scop.entry != sinfo.last)
1912 open_scop.exit = sinfo.last;
1915 VEC_safe_push (sd_region, heap, *scops, &open_scop);
1919 result.last = sinfo.last;
1923 /* Checks if a bb is contained in REGION. */
1926 bb_in_sd_region (basic_block bb, sd_region *region)
1928 return dominated_by_p (CDI_DOMINATORS, bb, region->entry)
1929 && !(dominated_by_p (CDI_DOMINATORS, bb, region->exit)
1930 && !dominated_by_p (CDI_DOMINATORS, region->entry,
1934 /* Returns the single entry edge of REGION, if it does not exits NULL. */
1937 find_single_entry_edge (sd_region *region)
1943 FOR_EACH_EDGE (e, ei, region->entry->preds)
1944 if (!bb_in_sd_region (e->src, region))
1959 /* Returns the single exit edge of REGION, if it does not exits NULL. */
1962 find_single_exit_edge (sd_region *region)
1968 FOR_EACH_EDGE (e, ei, region->exit->preds)
1969 if (bb_in_sd_region (e->src, region))
1984 /* Create a single entry edge for REGION. */
1987 create_single_entry_edge (sd_region *region)
1989 if (find_single_entry_edge (region))
1992 /* There are multiple predecessors for bb_3
2005 There are two edges (1->3, 2->3), that point from outside into the region,
2006 and another one (5->3), a loop latch, lead to bb_3.
2014 | |\ (3.0 -> 3.1) = single entry edge
2023 If the loop is part of the SCoP, we have to redirect the loop latches.
2029 | | (3.0 -> 3.1) = entry edge
2038 if (region->entry->loop_father->header != region->entry
2039 || dominated_by_p (CDI_DOMINATORS,
2040 loop_latch_edge (region->entry->loop_father)->src,
2043 edge forwarder = split_block_after_labels (region->entry);
2044 region->entry = forwarder->dest;
2047 /* This case is never executed, as the loop headers seem always to have a
2048 single edge pointing from outside into the loop. */
2051 #ifdef ENABLE_CHECKING
2052 gcc_assert (find_single_entry_edge (region));
2056 /* Check if the sd_region, mentioned in EDGE, has no exit bb. */
2059 sd_region_without_exit (edge e)
2061 sd_region *r = (sd_region *) e->aux;
2064 return r->exit == NULL;
2069 /* Create a single exit edge for REGION. */
2072 create_single_exit_edge (sd_region *region)
2076 edge forwarder = NULL;
2079 if (find_single_exit_edge (region))
2082 /* We create a forwarder bb (5) for all edges leaving this region
2083 (3->5, 4->5). All other edges leading to the same bb, are moved
2084 to a new bb (6). If these edges where part of another region (2->5)
2085 we update the region->exit pointer, of this region.
2087 To identify which edge belongs to which region we depend on the e->aux
2088 pointer in every edge. It points to the region of the edge or to NULL,
2089 if the edge is not part of any region.
2091 1 2 3 4 1->5 no region, 2->5 region->exit = 5,
2092 \| |/ 3->5 region->exit = NULL, 4->5 region->exit = NULL
2097 1 2 3 4 1->6 no region, 2->6 region->exit = 6,
2098 | | \/ 3->5 no region, 4->5 no region,
2100 \| / 5->6 region->exit = 6
2103 Now there is only a single exit edge (5->6). */
2104 exit = region->exit;
2105 region->exit = NULL;
2106 forwarder = make_forwarder_block (exit, &sd_region_without_exit, NULL);
2108 /* Unmark the edges, that are no longer exit edges. */
2109 FOR_EACH_EDGE (e, ei, forwarder->src->preds)
2113 /* Mark the new exit edge. */
2114 single_succ_edge (forwarder->src)->aux = region;
2116 /* Update the exit bb of all regions, where exit edges lead to
2118 FOR_EACH_EDGE (e, ei, forwarder->dest->preds)
2120 ((sd_region *) e->aux)->exit = forwarder->dest;
2122 #ifdef ENABLE_CHECKING
2123 gcc_assert (find_single_exit_edge (region));
2127 /* Unmark the exit edges of all REGIONS.
2128 See comment in "create_single_exit_edge". */
2131 unmark_exit_edges (VEC (sd_region, heap) *regions)
2138 for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
2139 FOR_EACH_EDGE (e, ei, s->exit->preds)
2144 /* Mark the exit edges of all REGIONS.
2145 See comment in "create_single_exit_edge". */
2148 mark_exit_edges (VEC (sd_region, heap) *regions)
2155 for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
2156 FOR_EACH_EDGE (e, ei, s->exit->preds)
2157 if (bb_in_sd_region (e->src, s))
2161 /* Free and compute again all the dominators information. */
2164 recompute_all_dominators (void)
2166 mark_irreducible_loops ();
2167 free_dominance_info (CDI_DOMINATORS);
2168 free_dominance_info (CDI_POST_DOMINATORS);
2169 calculate_dominance_info (CDI_DOMINATORS);
2170 calculate_dominance_info (CDI_POST_DOMINATORS);
2173 /* Verifies properties that GRAPHITE should maintain during translation. */
2176 graphite_verify (void)
2178 #ifdef ENABLE_CHECKING
2179 verify_loop_structure ();
2180 verify_dominators (CDI_DOMINATORS);
2181 verify_dominators (CDI_POST_DOMINATORS);
2186 /* Create for all scop regions a single entry and a single exit edge. */
2189 create_sese_edges (VEC (sd_region, heap) *regions)
2194 for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
2195 create_single_entry_edge (s);
2197 mark_exit_edges (regions);
2199 for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
2200 create_single_exit_edge (s);
2202 unmark_exit_edges (regions);
2204 fix_loop_structure (NULL);
2206 #ifdef ENABLE_CHECKING
2207 verify_loop_structure ();
2208 verify_dominators (CDI_DOMINATORS);
2213 /* Create graphite SCoPs from an array of scop detection regions. */
2216 build_graphite_scops (VEC (sd_region, heap) *scop_regions)
2221 for (i = 0; VEC_iterate (sd_region, scop_regions, i, s); i++)
2223 edge entry = find_single_entry_edge (s);
2224 edge exit = find_single_exit_edge (s);
2225 scop_p scop = new_scop (entry, exit);
2226 VEC_safe_push (scop_p, heap, current_scops, scop);
2228 /* Are there overlapping SCoPs? */
2229 #ifdef ENABLE_CHECKING
2234 for (j = 0; VEC_iterate (sd_region, scop_regions, j, s2); j++)
2236 gcc_assert (!bb_in_sd_region (s->entry, s2));
2242 /* Find static control parts. */
2247 struct loop *loop = current_loops->tree_root;
2248 VEC (sd_region, heap) *tmp_scops = VEC_alloc (sd_region, heap, 3);
2250 build_scops_1 (single_succ (ENTRY_BLOCK_PTR), &tmp_scops, loop);
2251 create_sese_edges (tmp_scops);
2252 build_graphite_scops (tmp_scops);
2253 VEC_free (sd_region, heap, tmp_scops);
2256 /* Gather the basic blocks belonging to the SCOP. */
2259 build_scop_bbs (scop_p scop)
2261 basic_block *stack = XNEWVEC (basic_block, n_basic_blocks + 1);
2262 sbitmap visited = sbitmap_alloc (last_basic_block);
2265 sbitmap_zero (visited);
2266 stack[sp++] = SCOP_ENTRY (scop);
2270 basic_block bb = stack[--sp];
2271 int depth = loop_depth (bb->loop_father);
2272 int num = bb->loop_father->num;
2276 /* Scop's exit is not in the scop. Exclude also bbs, which are
2277 dominated by the SCoP exit. These are e.g. loop latches. */
2278 if (TEST_BIT (visited, bb->index)
2279 || dominated_by_p (CDI_DOMINATORS, bb, SCOP_EXIT (scop))
2280 /* Every block in the scop is dominated by scop's entry. */
2281 || !dominated_by_p (CDI_DOMINATORS, bb, SCOP_ENTRY (scop)))
2284 new_graphite_bb (scop, bb);
2285 SET_BIT (visited, bb->index);
2287 /* First push the blocks that have to be processed last. Note
2288 that this means that the order in which the code is organized
2289 below is important: do not reorder the following code. */
2290 FOR_EACH_EDGE (e, ei, bb->succs)
2291 if (! TEST_BIT (visited, e->dest->index)
2292 && (int) loop_depth (e->dest->loop_father) < depth)
2293 stack[sp++] = e->dest;
2295 FOR_EACH_EDGE (e, ei, bb->succs)
2296 if (! TEST_BIT (visited, e->dest->index)
2297 && (int) loop_depth (e->dest->loop_father) == depth
2298 && e->dest->loop_father->num != num)
2299 stack[sp++] = e->dest;
2301 FOR_EACH_EDGE (e, ei, bb->succs)
2302 if (! TEST_BIT (visited, e->dest->index)
2303 && (int) loop_depth (e->dest->loop_father) == depth
2304 && e->dest->loop_father->num == num
2305 && EDGE_COUNT (e->dest->preds) > 1)
2306 stack[sp++] = e->dest;
2308 FOR_EACH_EDGE (e, ei, bb->succs)
2309 if (! TEST_BIT (visited, e->dest->index)
2310 && (int) loop_depth (e->dest->loop_father) == depth
2311 && e->dest->loop_father->num == num
2312 && EDGE_COUNT (e->dest->preds) == 1)
2313 stack[sp++] = e->dest;
2315 FOR_EACH_EDGE (e, ei, bb->succs)
2316 if (! TEST_BIT (visited, e->dest->index)
2317 && (int) loop_depth (e->dest->loop_father) > depth)
2318 stack[sp++] = e->dest;
2322 sbitmap_free (visited);
2325 /* Returns the number of reduction phi nodes in LOOP. */
2328 nb_reductions_in_loop (loop_p loop)
2331 gimple_stmt_iterator gsi;
2333 for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
2335 gimple phi = gsi_stmt (gsi);
2339 if (!is_gimple_reg (PHI_RESULT (phi)))
2342 scev = analyze_scalar_evolution (loop, PHI_RESULT (phi));
2343 scev = instantiate_parameters (loop, scev);
2344 if (!simple_iv (loop, phi, PHI_RESULT (phi), &iv, true))
2351 /* A LOOP is in normal form when it contains only one scalar phi node
2352 that defines the main induction variable of the loop, only one
2353 increment of the IV, and only one exit condition. */
2356 graphite_loop_normal_form (loop_p loop)
2358 struct tree_niter_desc niter;
2361 edge exit = single_dom_exit (loop);
2363 gcc_assert (number_of_iterations_exit (loop, exit, &niter, false));
2364 nit = force_gimple_operand (unshare_expr (niter.niter), &stmts, true,
2367 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
2369 /* One IV per loop. */
2370 if (nb_reductions_in_loop (loop) > 0)
2373 return canonicalize_loop_ivs (loop, NULL, nit);
2376 /* Record LOOP as occuring in SCOP. Returns true when the operation
2380 scop_record_loop (scop_p scop, loop_p loop)
2385 if (bitmap_bit_p (SCOP_LOOPS (scop), loop->num))
2388 bitmap_set_bit (SCOP_LOOPS (scop), loop->num);
2389 VEC_safe_push (loop_p, heap, SCOP_LOOP_NEST (scop), loop);
2391 induction_var = graphite_loop_normal_form (loop);
2395 oldiv = XNEW (struct name_tree);
2396 oldiv->t = induction_var;
2397 oldiv->name = get_name (SSA_NAME_VAR (oldiv->t));
2399 VEC_safe_push (name_tree, heap, SCOP_OLDIVS (scop), oldiv);
2403 /* Build the loop nests contained in SCOP. Returns true when the
2404 operation was successful. */
2407 build_scop_loop_nests (scop_p scop)
2411 struct loop *loop0, *loop1;
2414 if (bb_in_scop_p (bb, scop))
2416 struct loop *loop = bb->loop_father;
2418 /* Only add loops if they are completely contained in the SCoP. */
2419 if (loop->header == bb
2420 && bb_in_scop_p (loop->latch, scop))
2422 if (!scop_record_loop (scop, loop))
2427 /* Make sure that the loops in the SCOP_LOOP_NEST are ordered. It
2428 can be the case that an inner loop is inserted before an outer
2429 loop. To avoid this, semi-sort once. */
2430 for (i = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), i, loop0); i++)
2432 if (VEC_length (loop_p, SCOP_LOOP_NEST (scop)) == i + 1)
2435 loop1 = VEC_index (loop_p, SCOP_LOOP_NEST (scop), i + 1);
2436 if (loop0->num > loop1->num)
2438 VEC_replace (loop_p, SCOP_LOOP_NEST (scop), i, loop1);
2439 VEC_replace (loop_p, SCOP_LOOP_NEST (scop), i + 1, loop0);
2446 /* Build dynamic schedules for all the BBs. */
2449 build_scop_dynamic_schedules (scop_p scop)
2451 int i, dim, loop_num, row, col;
2454 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
2456 loop_num = GBB_BB (gb)->loop_father->num;
2460 dim = nb_loops_around_gb (gb);
2461 GBB_DYNAMIC_SCHEDULE (gb) = cloog_matrix_alloc (dim, dim);
2463 for (row = 0; row < GBB_DYNAMIC_SCHEDULE (gb)->NbRows; row++)
2464 for (col = 0; col < GBB_DYNAMIC_SCHEDULE (gb)->NbColumns; col++)
2466 value_set_si (GBB_DYNAMIC_SCHEDULE (gb)->p[row][col], 1);
2468 value_set_si (GBB_DYNAMIC_SCHEDULE (gb)->p[row][col], 0);
2471 GBB_DYNAMIC_SCHEDULE (gb) = NULL;
2475 /* Build for BB the static schedule.
2477 The STATIC_SCHEDULE is defined like this:
2496 Static schedules for A to F:
2509 build_scop_canonical_schedules (scop_p scop)
2513 int nb = scop_nb_loops (scop) + 1;
2515 SCOP_STATIC_SCHEDULE (scop) = lambda_vector_new (nb);
2517 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
2519 int offset = nb_loops_around_gb (gb);
2521 /* After leaving a loop, it is possible that the schedule is not
2522 set at zero. This loop reinitializes components located
2525 for (j = offset + 1; j < nb; j++)
2526 if (SCOP_STATIC_SCHEDULE (scop)[j])
2528 memset (&(SCOP_STATIC_SCHEDULE (scop)[j]), 0,
2529 sizeof (int) * (nb - j));
2530 ++SCOP_STATIC_SCHEDULE (scop)[offset];
2534 GBB_STATIC_SCHEDULE (gb) = lambda_vector_new (offset + 1);
2535 lambda_vector_copy (SCOP_STATIC_SCHEDULE (scop),
2536 GBB_STATIC_SCHEDULE (gb), offset + 1);
2538 ++SCOP_STATIC_SCHEDULE (scop)[offset];
2542 /* Build the LOOPS vector for all bbs in SCOP. */
2545 build_bb_loops (scop_p scop)
2550 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
2555 depth = nb_loops_around_gb (gb) - 1;
2557 GBB_LOOPS (gb) = VEC_alloc (loop_p, heap, 3);
2558 VEC_safe_grow_cleared (loop_p, heap, GBB_LOOPS (gb), depth + 1);
2560 loop = GBB_BB (gb)->loop_father;
2562 while (scop_contains_loop (scop, loop))
2564 VEC_replace (loop_p, GBB_LOOPS (gb), depth, loop);
2565 loop = loop_outer (loop);
2571 /* Get the index for parameter VAR in SCOP. */
2574 param_index (tree var, scop_p scop)
2580 gcc_assert (TREE_CODE (var) == SSA_NAME);
2582 for (i = 0; VEC_iterate (name_tree, SCOP_PARAMS (scop), i, p); i++)
2586 gcc_assert (SCOP_ADD_PARAMS (scop));
2588 nvar = XNEW (struct name_tree);
2591 VEC_safe_push (name_tree, heap, SCOP_PARAMS (scop), nvar);
2592 return VEC_length (name_tree, SCOP_PARAMS (scop)) - 1;
2595 /* Scan EXPR and translate it to an inequality vector INEQ that will
2596 be added, or subtracted, in the constraint domain matrix C at row
2597 R. K is the number of columns for loop iterators in C. */
2600 scan_tree_for_params (scop_p s, tree e, CloogMatrix *c, int r, Value k,
2603 int cst_col, param_col;
2605 if (e == chrec_dont_know)
2608 switch (TREE_CODE (e))
2610 case POLYNOMIAL_CHREC:
2612 tree left = CHREC_LEFT (e);
2613 tree right = CHREC_RIGHT (e);
2614 int var = CHREC_VARIABLE (e);
2616 if (TREE_CODE (right) != INTEGER_CST)
2621 int loop_col = scop_gimple_loop_depth (s, get_loop (var)) + 1;
2624 value_sub_int (c->p[r][loop_col], c->p[r][loop_col],
2625 int_cst_value (right));
2627 value_add_int (c->p[r][loop_col], c->p[r][loop_col],
2628 int_cst_value (right));
2631 switch (TREE_CODE (left))
2633 case POLYNOMIAL_CHREC:
2634 scan_tree_for_params (s, left, c, r, k, subtract);
2638 /* Constant part. */
2641 int v = int_cst_value (left);
2642 cst_col = c->NbColumns - 1;
2647 subtract = subtract ? false : true;
2651 value_sub_int (c->p[r][cst_col], c->p[r][cst_col], v);
2653 value_add_int (c->p[r][cst_col], c->p[r][cst_col], v);
2658 scan_tree_for_params (s, left, c, r, k, subtract);
2665 if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
2670 gcc_assert (host_integerp (TREE_OPERAND (e, 1), 0));
2672 value_set_si (val, int_cst_value (TREE_OPERAND (e, 1)));
2673 value_multiply (k, k, val);
2676 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
2683 gcc_assert (host_integerp (TREE_OPERAND (e, 0), 0));
2685 value_set_si (val, int_cst_value (TREE_OPERAND (e, 0)));
2686 value_multiply (k, k, val);
2689 scan_tree_for_params (s, TREE_OPERAND (e, 1), c, r, k, subtract);
2694 case POINTER_PLUS_EXPR:
2695 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
2696 scan_tree_for_params (s, TREE_OPERAND (e, 1), c, r, k, subtract);
2700 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
2701 value_oppose (k, k);
2702 scan_tree_for_params (s, TREE_OPERAND (e, 1), c, r, k, subtract);
2706 value_oppose (k, k);
2707 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
2711 param_col = param_index (e, s);
2715 param_col += c->NbColumns - scop_nb_params (s) - 1;
2718 value_subtract (c->p[r][param_col], c->p[r][param_col], k);
2720 value_addto (c->p[r][param_col], c->p[r][param_col], k);
2727 int v = int_cst_value (e);
2728 cst_col = c->NbColumns - 1;
2733 subtract = subtract ? false : true;
2737 value_sub_int (c->p[r][cst_col], c->p[r][cst_col], v);
2739 value_add_int (c->p[r][cst_col], c->p[r][cst_col], v);
2744 case NON_LVALUE_EXPR:
2745 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
2754 /* Data structure for idx_record_params. */
2762 /* For a data reference with an ARRAY_REF as its BASE, record the
2763 parameters occurring in IDX. DTA is passed in as complementary
2764 information, and is used by the automatic walker function. This
2765 function is a callback for for_each_index. */
2768 idx_record_params (tree base, tree *idx, void *dta)
2770 struct irp_data *data = (struct irp_data *) dta;
2772 if (TREE_CODE (base) != ARRAY_REF)
2775 if (TREE_CODE (*idx) == SSA_NAME)
2778 scop_p scop = data->scop;
2779 struct loop *loop = data->loop;
2782 scev = analyze_scalar_evolution (loop, *idx);
2783 scev = instantiate_scev (block_before_scop (scop), loop, scev);
2786 value_set_si (one, 1);
2787 scan_tree_for_params (scop, scev, NULL, 0, one, false);
2794 /* Find parameters with respect to SCOP in BB. We are looking in memory
2795 access functions, conditions and loop bounds. */
2798 find_params_in_bb (scop_p scop, graphite_bb_p gb)
2801 data_reference_p dr;
2803 loop_p father = GBB_BB (gb)->loop_father;
2805 for (i = 0; VEC_iterate (data_reference_p, GBB_DATA_REFS (gb), i, dr); i++)
2807 struct irp_data irp;
2811 for_each_index (&dr->ref, idx_record_params, &irp);
2814 /* Find parameters in conditional statements. */
2815 for (i = 0; VEC_iterate (gimple, GBB_CONDITIONS (gb), i, stmt); i++)
2818 loop_p loop = father;
2822 lhs = gimple_cond_lhs (stmt);
2823 lhs = analyze_scalar_evolution (loop, lhs);
2824 lhs = instantiate_scev (block_before_scop (scop), loop, lhs);
2826 rhs = gimple_cond_rhs (stmt);
2827 rhs = analyze_scalar_evolution (loop, rhs);
2828 rhs = instantiate_scev (block_before_scop (scop), loop, rhs);
2831 scan_tree_for_params (scop, lhs, NULL, 0, one, false);
2832 value_set_si (one, 1);
2833 scan_tree_for_params (scop, rhs, NULL, 0, one, false);
2838 /* Saves in NV the name of variable P->T. */
2841 save_var_name (char **nv, int i, name_tree p)
2843 const char *name = get_name (SSA_NAME_VAR (p->t));
2847 int len = strlen (name) + 16;
2848 nv[i] = XNEWVEC (char, len);
2849 snprintf (nv[i], len, "%s_%d", name, SSA_NAME_VERSION (p->t));
2853 nv[i] = XNEWVEC (char, 16);
2854 snprintf (nv[i], 2 + 16, "T_%d", SSA_NAME_VERSION (p->t));
2860 /* Return the maximal loop depth in SCOP. */
2863 scop_max_loop_depth (scop_p scop)
2867 int max_nb_loops = 0;
2869 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gbb); i++)
2871 int nb_loops = gbb_nb_loops (gbb);
2872 if (max_nb_loops < nb_loops)
2873 max_nb_loops = nb_loops;
2876 return max_nb_loops;
2879 /* Initialize Cloog's parameter names from the names used in GIMPLE.
2880 Initialize Cloog's iterator names, using 'graphite_iterator_%d'
2881 from 0 to scop_nb_loops (scop). */
2884 initialize_cloog_names (scop_p scop)
2886 int i, nb_params = VEC_length (name_tree, SCOP_PARAMS (scop));
2887 char **params = XNEWVEC (char *, nb_params);
2888 int nb_iterators = scop_max_loop_depth (scop);
2889 int nb_scattering= cloog_program_nb_scattdims (SCOP_PROG (scop));
2890 char **iterators = XNEWVEC (char *, nb_iterators * 2);
2891 char **scattering = XNEWVEC (char *, nb_scattering);
2894 for (i = 0; VEC_iterate (name_tree, SCOP_PARAMS (scop), i, p); i++)
2895 save_var_name (params, i, p);
2897 cloog_names_set_nb_parameters (cloog_program_names (SCOP_PROG (scop)),
2899 cloog_names_set_parameters (cloog_program_names (SCOP_PROG (scop)),
2902 for (i = 0; i < nb_iterators; i++)
2905 iterators[i] = XNEWVEC (char, len);
2906 snprintf (iterators[i], len, "graphite_iterator_%d", i);
2909 cloog_names_set_nb_iterators (cloog_program_names (SCOP_PROG (scop)),
2911 cloog_names_set_iterators (cloog_program_names (SCOP_PROG (scop)),
2914 for (i = 0; i < nb_scattering; i++)
2917 scattering[i] = XNEWVEC (char, len);
2918 snprintf (scattering[i], len, "s_%d", i);
2921 cloog_names_set_nb_scattering (cloog_program_names (SCOP_PROG (scop)),
2923 cloog_names_set_scattering (cloog_program_names (SCOP_PROG (scop)),
2927 /* Record the parameters used in the SCOP. A variable is a parameter
2928 in a scop if it does not vary during the execution of that scop. */
2931 find_scop_parameters (scop_p scop)
2939 value_set_si (one, 1);
2941 /* Find the parameters used in the loop bounds. */
2942 for (i = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), i, loop); i++)
2944 tree nb_iters = number_of_latch_executions (loop);
2946 if (!chrec_contains_symbols (nb_iters))
2949 nb_iters = analyze_scalar_evolution (loop, nb_iters);
2950 nb_iters = instantiate_scev (block_before_scop (scop), loop, nb_iters);
2951 scan_tree_for_params (scop, nb_iters, NULL, 0, one, false);
2956 /* Find the parameters used in data accesses. */
2957 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
2958 find_params_in_bb (scop, gb);
2960 SCOP_ADD_PARAMS (scop) = false;
2963 /* Build the context constraints for SCOP: constraints and relations
2967 build_scop_context (scop_p scop)
2969 int nb_params = scop_nb_params (scop);
2970 CloogMatrix *matrix = cloog_matrix_alloc (1, nb_params + 2);
2972 /* Insert '0 >= 0' in the context matrix, as it is not allowed to be
2975 value_set_si (matrix->p[0][0], 1);
2977 value_set_si (matrix->p[0][nb_params + 1], 0);
2979 cloog_program_set_context (SCOP_PROG (scop),
2980 cloog_domain_matrix2domain (matrix));
2981 cloog_matrix_free (matrix);
2984 /* Returns a graphite_bb from BB. */
2986 static inline graphite_bb_p
2987 gbb_from_bb (basic_block bb)
2989 return (graphite_bb_p) bb->aux;
2992 /* Builds the constraint matrix for LOOP in SCOP. NB_OUTER_LOOPS is the
2993 number of loops surrounding LOOP in SCOP. OUTER_CSTR gives the
2994 constraints matrix for the surrounding loops. */
2997 build_loop_iteration_domains (scop_p scop, struct loop *loop,
2998 CloogMatrix *outer_cstr, int nb_outer_loops)
3004 int nb_rows = outer_cstr->NbRows + 1;
3005 int nb_cols = outer_cstr->NbColumns + 1;
3007 /* Last column of CSTR is the column of constants. */
3008 int cst_col = nb_cols - 1;
3010 /* The column for the current loop is just after the columns of
3011 other outer loops. */
3012 int loop_col = nb_outer_loops + 1;
3014 tree nb_iters = number_of_latch_executions (loop);
3016 /* When the number of iterations is a constant or a parameter, we
3017 add a constraint for the upper bound of the loop. So add a row
3018 to the constraint matrix before allocating it. */
3019 if (TREE_CODE (nb_iters) == INTEGER_CST
3020 || !chrec_contains_undetermined (nb_iters))
3023 cstr = cloog_matrix_alloc (nb_rows, nb_cols);
3025 /* Copy the outer constraints. */
3026 for (i = 0; i < outer_cstr->NbRows; i++)
3028 /* Copy the eq/ineq and loops columns. */
3029 for (j = 0; j < loop_col; j++)
3030 value_assign (cstr->p[i][j], outer_cstr->p[i][j]);
3032 /* Leave an empty column in CSTR for the current loop, and then
3033 copy the parameter columns. */
3034 for (j = loop_col; j < outer_cstr->NbColumns; j++)
3035 value_assign (cstr->p[i][j + 1], outer_cstr->p[i][j]);
3039 row = outer_cstr->NbRows;
3040 value_set_si (cstr->p[row][0], 1);
3041 value_set_si (cstr->p[row][loop_col], 1);
3043 /* loop_i <= nb_iters */
3044 if (TREE_CODE (nb_iters) == INTEGER_CST)
3047 value_set_si (cstr->p[row][0], 1);
3048 value_set_si (cstr->p[row][loop_col], -1);
3050 value_set_si (cstr->p[row][cst_col],
3051 int_cst_value (nb_iters));
3053 else if (!chrec_contains_undetermined (nb_iters))
3055 /* Otherwise nb_iters contains parameters: scan the nb_iters
3056 expression and build its matrix representation. */
3060 value_set_si (cstr->p[row][0], 1);
3061 value_set_si (cstr->p[row][loop_col], -1);
3063 nb_iters = analyze_scalar_evolution (loop, nb_iters);
3064 nb_iters = instantiate_scev (block_before_scop (scop), loop, nb_iters);
3067 value_set_si (one, 1);
3068 scan_tree_for_params (scop, nb_iters, cstr, row, one, false);
3074 if (loop->inner && loop_in_scop_p (loop->inner, scop))
3075 build_loop_iteration_domains (scop, loop->inner, cstr, nb_outer_loops + 1);
3077 /* Only go to the next loops, if we are not at the outermost layer. These
3078 have to be handled seperately, as we can be sure, that the chain at this
3079 layer will be connected. */
3080 if (nb_outer_loops != 0 && loop->next && loop_in_scop_p (loop->next, scop))
3081 build_loop_iteration_domains (scop, loop->next, outer_cstr, nb_outer_loops);
3083 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
3084 if (gbb_loop (gb) == loop)
3085 GBB_DOMAIN (gb) = cloog_matrix_copy (cstr);
3087 cloog_matrix_free (cstr);
3090 /* Add conditions to the domain of GB. */
3093 add_conditions_to_domain (graphite_bb_p gb)
3097 VEC (gimple, heap) *conditions = GBB_CONDITIONS (gb);
3098 CloogMatrix *domain = GBB_DOMAIN (gb);
3099 scop_p scop = GBB_SCOP (gb);
3103 unsigned nb_new_rows = 0;
3106 if (VEC_empty (gimple, conditions))
3111 nb_rows = domain->NbRows;
3112 nb_cols = domain->NbColumns;
3117 nb_cols = scop_nb_params (scop) + 2;
3120 /* Count number of necessary new rows to add the conditions to the
3122 for (i = 0; VEC_iterate (gimple, conditions, i, stmt); i++)
3124 switch (gimple_code (stmt))
3128 enum tree_code code = gimple_cond_code (stmt);
3134 /* NE and EQ statements are not supported right know. */
3150 /* Switch statements are not supported right know. */
3161 /* Enlarge the matrix. */
3163 CloogMatrix *new_domain;
3164 new_domain = cloog_matrix_alloc (nb_rows + nb_new_rows, nb_cols);
3166 for (i = 0; i < nb_rows; i++)
3167 for (j = 0; j < nb_cols; j++)
3168 value_assign (new_domain->p[i][j], domain->p[i][j]);
3170 cloog_matrix_free (domain);
3171 domain = new_domain;
3172 GBB_DOMAIN (gb) = new_domain;
3175 /* Add the conditions to the new enlarged domain matrix. */
3177 for (i = 0; VEC_iterate (gimple, conditions, i, stmt); i++)
3179 switch (gimple_code (stmt))
3184 enum tree_code code;
3187 loop_p loop = GBB_BB (gb)->loop_father;
3189 left = gimple_cond_lhs (stmt);
3190 right = gimple_cond_rhs (stmt);
3192 left = analyze_scalar_evolution (loop, left);
3193 right = analyze_scalar_evolution (loop, right);
3195 left = instantiate_scev (block_before_scop (scop), loop, left);
3196 right = instantiate_scev (block_before_scop (scop), loop, right);
3198 code = gimple_cond_code (stmt);
3200 /* The conditions for ELSE-branches are inverted. */
3201 if (VEC_index (gimple, gb->condition_cases, i) == NULL)
3202 code = invert_tree_comparison (code, false);
3207 /* NE statements are not supported right know. */
3211 value_set_si (domain->p[row][0], 1);
3213 value_set_si (one, 1);
3214 scan_tree_for_params (scop, left, domain, row, one, true);
3215 value_set_si (one, 1);
3216 scan_tree_for_params (scop, right, domain, row, one, false);
3218 value_set_si (domain->p[row][0], 1);
3219 value_set_si (one, 1);
3220 scan_tree_for_params (scop, left, domain, row, one, false);
3221 value_set_si (one, 1);
3222 scan_tree_for_params (scop, right, domain, row, one, true);
3227 value_set_si (domain->p[row][0], 1);
3229 value_set_si (one, 1);
3230 scan_tree_for_params (scop, left, domain, row, one, true);
3231 value_set_si (one, 1);
3232 scan_tree_for_params (scop, right, domain, row, one, false);
3233 value_sub_int (domain->p[row][nb_cols - 1],
3234 domain->p[row][nb_cols - 1], 1);
3239 value_set_si (domain->p[row][0], 1);
3241 value_set_si (one, 1);
3242 scan_tree_for_params (scop, left, domain, row, one, false);
3243 value_set_si (one, 1);
3244 scan_tree_for_params (scop, right, domain, row, one, true);
3245 value_sub_int (domain->p[row][nb_cols - 1],
3246 domain->p[row][nb_cols - 1], 1);
3251 value_set_si (domain->p[row][0], 1);
3253 value_set_si (one, 1);
3254 scan_tree_for_params (scop, left, domain, row, one, true);
3255 value_set_si (one, 1);
3256 scan_tree_for_params (scop, right, domain, row, one, false);
3261 value_set_si (domain->p[row][0], 1);
3263 value_set_si (one, 1);
3264 scan_tree_for_params (scop, left, domain, row, one, false);
3265 value_set_si (one, 1);
3266 scan_tree_for_params (scop, right, domain, row, one, true);
3277 /* Switch statements are not supported right know. */
3288 /* Returns true when PHI defines an induction variable in the loop
3289 containing the PHI node. */
3292 phi_node_is_iv (gimple phi)
3294 loop_p loop = gimple_bb (phi)->loop_father;
3295 tree scev = analyze_scalar_evolution (loop, gimple_phi_result (phi));
3297 return tree_contains_chrecs (scev, NULL);
3300 /* Returns true when BB contains scalar phi nodes that are not an
3301 induction variable of a loop. */
3304 bb_contains_non_iv_scalar_phi_nodes (basic_block bb)
3307 gimple_stmt_iterator si;
3309 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
3310 if (is_gimple_reg (gimple_phi_result (gsi_stmt (si))))
3312 /* Store the unique scalar PHI node: at this point, loops
3313 should be in cannonical form, so we expect to see at most
3314 one scalar phi node in the loop header. */
3316 || bb != bb->loop_father->header)
3319 phi = gsi_stmt (si);
3323 || phi_node_is_iv (phi))
3329 /* Helper recursive function. Record in CONDITIONS and CASES all
3330 conditions from 'if's and 'switch'es occurring in BB from SCOP.
3332 Returns false when the conditions contain scalar computations that
3333 depend on the condition, i.e. when there are scalar phi nodes on
3334 the junction after the condition. Only the computations occurring
3335 on memory can be handled in the polyhedral model: operations that
3336 define scalar evolutions in conditions, that can potentially be
3337 used to index memory, can't be handled by the polyhedral model. */
3340 build_scop_conditions_1 (VEC (gimple, heap) **conditions,
3341 VEC (gimple, heap) **cases, basic_block bb,
3347 gimple_stmt_iterator gsi;
3348 basic_block bb_child, bb_iter;
3349 VEC (basic_block, heap) *dom;
3351 /* Make sure we are in the SCoP. */
3352 if (!bb_in_scop_p (bb, scop))
3355 if (bb_contains_non_iv_scalar_phi_nodes (bb))
3358 gbb = gbb_from_bb (bb);
3361 GBB_CONDITIONS (gbb) = VEC_copy (gimple, heap, *conditions);
3362 GBB_CONDITION_CASES (gbb) = VEC_copy (gimple, heap, *cases);
3363 add_conditions_to_domain (gbb);
3366 dom = get_dominated_by (CDI_DOMINATORS, bb);
3368 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3370 gimple stmt = gsi_stmt (gsi);
3371 VEC (edge, gc) *edges;
3374 switch (gimple_code (stmt))
3378 for (i = 0; VEC_iterate (edge, edges, i, e); i++)
3379 if ((dominated_by_p (CDI_DOMINATORS, e->dest, bb))
3380 && VEC_length (edge, e->dest->preds) == 1)
3382 /* Remove the scanned block from the dominator successors. */
3383 for (j = 0; VEC_iterate (basic_block, dom, j, bb_iter); j++)
3384 if (bb_iter == e->dest)
3386 VEC_unordered_remove (basic_block, dom, j);
3390 /* Recursively scan the then or else part. */
3391 if (e->flags & EDGE_TRUE_VALUE)
3392 VEC_safe_push (gimple, heap, *cases, stmt);
3395 gcc_assert (e->flags & EDGE_FALSE_VALUE);
3396 VEC_safe_push (gimple, heap, *cases, NULL);
3399 VEC_safe_push (gimple, heap, *conditions, stmt);
3400 if (!build_scop_conditions_1 (conditions, cases, e->dest, scop))
3405 VEC_pop (gimple, *conditions);
3406 VEC_pop (gimple, *cases);
3413 gimple_stmt_iterator gsi_search_gimple_label;
3415 for (i = 0; i < gimple_switch_num_labels (stmt); ++i)
3417 basic_block bb_iter;
3419 size_t n_cases = VEC_length (gimple, *conditions);
3420 unsigned n = gimple_switch_num_labels (stmt);
3422 bb_child = label_to_block
3423 (CASE_LABEL (gimple_switch_label (stmt, i)));
3425 for (k = 0; k < n; k++)
3428 (CASE_LABEL (gimple_switch_label (stmt, k))) == bb_child)
3431 /* Switches with multiple case values for the same
3432 block are not handled. */
3434 /* Switch cases with more than one predecessor are
3436 || VEC_length (edge, bb_child->preds) != 1)
3442 /* Recursively scan the corresponding 'case' block. */
3443 for (gsi_search_gimple_label = gsi_start_bb (bb_child);
3444 !gsi_end_p (gsi_search_gimple_label);
3445 gsi_next (&gsi_search_gimple_label))
3447 gimple label = gsi_stmt (gsi_search_gimple_label);
3449 if (gimple_code (label) == GIMPLE_LABEL)
3451 tree t = gimple_label_label (label);
3453 gcc_assert (t == gimple_switch_label (stmt, i));
3454 VEC_replace (gimple, *cases, n_cases, label);
3459 if (!build_scop_conditions_1 (conditions, cases, bb_child, scop))
3465 /* Remove the scanned block from the dominator successors. */
3466 for (j = 0; VEC_iterate (basic_block, dom, j, bb_iter); j++)
3467 if (bb_iter == bb_child)
3469 VEC_unordered_remove (basic_block, dom, j);
3474 VEC_pop (gimple, *conditions);
3475 VEC_pop (gimple, *cases);
3484 /* Scan all immediate dominated successors. */
3485 for (i = 0; VEC_iterate (basic_block, dom, i, bb_child); i++)
3486 if (!build_scop_conditions_1 (conditions, cases, bb_child, scop))
3493 VEC_free (basic_block, heap, dom);
3497 /* Record all conditions from SCOP.
3499 Returns false when the conditions contain scalar computations that
3500 depend on the condition, i.e. when there are scalar phi nodes on
3501 the junction after the condition. Only the computations occurring
3502 on memory can be handled in the polyhedral model: operations that
3503 define scalar evolutions in conditions, that can potentially be
3504 used to index memory, can't be handled by the polyhedral model. */
3507 build_scop_conditions (scop_p scop)
3510 VEC (gimple, heap) *conditions = NULL;
3511 VEC (gimple, heap) *cases = NULL;
3513 res = build_scop_conditions_1 (&conditions, &cases, SCOP_ENTRY (scop), scop);
3515 VEC_free (gimple, heap, conditions);
3516 VEC_free (gimple, heap, cases);
3520 /* Build the current domain matrix: the loops belonging to the current
3521 SCOP, and that vary for the execution of the current basic block.
3522 Returns false if there is no loop in SCOP. */
3525 build_scop_iteration_domain (scop_p scop)
3528 CloogMatrix *outer_cstr;
3531 /* Build cloog loop for all loops, that are in the uppermost loop layer of
3533 for (i = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), i, loop); i++)
3534 if (!loop_in_scop_p (loop_outer (loop), scop))
3536 /* The outermost constraints is a matrix that has:
3537 -first column: eq/ineq boolean
3538 -last column: a constant
3539 -scop_nb_params columns for the parameters used in the scop. */
3540 outer_cstr = cloog_matrix_alloc (0, scop_nb_params (scop) + 2);
3541 build_loop_iteration_domains (scop, loop, outer_cstr, 0);
3542 cloog_matrix_free (outer_cstr);
3548 /* Initializes an equation CY of the access matrix using the
3549 information for a subscript from AF, relatively to the loop
3550 indexes from LOOP_NEST and parameter indexes from PARAMS. NDIM is
3551 the dimension of the array access, i.e. the number of
3552 subscripts. Returns true when the operation succeeds. */
3555 build_access_matrix_with_af (tree af, lambda_vector cy,
3556 scop_p scop, int ndim)
3560 switch (TREE_CODE (af))
3562 case POLYNOMIAL_CHREC:
3564 struct loop *outer_loop;
3565 tree left = CHREC_LEFT (af);
3566 tree right = CHREC_RIGHT (af);
3569 if (TREE_CODE (right) != INTEGER_CST)
3572 outer_loop = get_loop (CHREC_VARIABLE (af));
3573 var = nb_loops_around_loop_in_scop (outer_loop, scop);
3574 cy[var] = int_cst_value (right);
3576 switch (TREE_CODE (left))
3578 case POLYNOMIAL_CHREC:
3579 return build_access_matrix_with_af (left, cy, scop, ndim);
3582 cy[ndim - 1] = int_cst_value (left);
3586 return build_access_matrix_with_af (left, cy, scop, ndim);
3591 build_access_matrix_with_af (TREE_OPERAND (af, 0), cy, scop, ndim);
3592 build_access_matrix_with_af (TREE_OPERAND (af, 1), cy, scop, ndim);
3596 build_access_matrix_with_af (TREE_OPERAND (af, 0), cy, scop, ndim);
3597 build_access_matrix_with_af (TREE_OPERAND (af, 1), cy, scop, ndim);
3601 cy[ndim - 1] = int_cst_value (af);
3605 param_col = param_index (af, scop);
3606 cy [ndim - scop_nb_params (scop) + param_col - 1] = 1;
3610 /* FIXME: access_fn can have parameters. */
3615 /* Initialize the access matrix in the data reference REF with respect
3616 to the loop nesting LOOP_NEST. Return true when the operation
3620 build_access_matrix (data_reference_p ref, graphite_bb_p gb)
3622 int i, ndim = DR_NUM_DIMENSIONS (ref);
3623 struct access_matrix *am = GGC_NEW (struct access_matrix);
3625 AM_MATRIX (am) = VEC_alloc (lambda_vector, gc, ndim);
3626 DR_SCOP (ref) = GBB_SCOP (gb);
3628 for (i = 0; i < ndim; i++)
3630 lambda_vector v = lambda_vector_new (ref_nb_loops (ref));
3631 scop_p scop = GBB_SCOP (gb);
3632 tree af = DR_ACCESS_FN (ref, i);
3634 if (!build_access_matrix_with_af (af, v, scop, ref_nb_loops (ref)))
3637 VEC_quick_push (lambda_vector, AM_MATRIX (am), v);
3640 DR_ACCESS_MATRIX (ref) = am;
3644 /* Build the access matrices for the data references in the SCOP. */
3647 build_scop_data_accesses (scop_p scop)
3652 /* FIXME: Construction of access matrix is disabled until some
3653 pass, like the data dependence analysis, is using it. */
3656 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
3659 data_reference_p dr;
3661 /* Construct the access matrix for each data ref, with respect to
3662 the loop nest of the current BB in the considered SCOP. */
3664 VEC_iterate (data_reference_p, GBB_DATA_REFS (gb), j, dr);
3667 bool res = build_access_matrix (dr, gb);
3669 /* FIXME: At this point the DRs should always have an affine
3670 form. For the moment this fails as build_access_matrix
3671 does not build matrices with parameters. */
3677 /* Returns the tree variable from the name NAME that was given in
3678 Cloog representation. All the parameters are stored in PARAMS, and
3679 all the loop induction variables are stored in IVSTACK.
3681 FIXME: This is a hack, and Cloog should be fixed to not work with
3682 variable names represented as "char *string", but with void
3683 pointers that could be casted back to a tree. The only problem in
3684 doing that is that Cloog's pretty printer still assumes that
3685 variable names are char *strings. The solution would be to have a
3686 function pointer for pretty-printing that can be redirected to be
3687 print_generic_stmt in our case, or fprintf by default.
3688 ??? Too ugly to live. */
3691 clast_name_to_gcc (const char *name, VEC (name_tree, heap) *params,
3692 loop_iv_stack ivstack)
3699 for (i = 0; VEC_iterate (name_tree, params, i, t); i++)
3700 if (!strcmp (name, t->name))
3703 iv = loop_iv_stack_get_iv_from_name (ivstack, name);
3710 /* Returns the maximal precision type for expressions E1 and E2. */
3713 max_precision_type (tree e1, tree e2)
3715 tree type1 = TREE_TYPE (e1);
3716 tree type2 = TREE_TYPE (e2);
3717 return TYPE_PRECISION (type1) > TYPE_PRECISION (type2) ? type1 : type2;
3720 /* Converts a Cloog AST expression E back to a GCC expression tree
3724 clast_to_gcc_expression (tree type, struct clast_expr *e,
3725 VEC (name_tree, heap) *params,
3726 loop_iv_stack ivstack)
3732 struct clast_term *t = (struct clast_term *) e;
3736 if (value_one_p (t->val))
3738 tree name = clast_name_to_gcc (t->var, params, ivstack);
3739 return fold_convert (type, name);
3742 else if (value_mone_p (t->val))
3744 tree name = clast_name_to_gcc (t->var, params, ivstack);
3745 name = fold_convert (type, name);
3746 return fold_build1 (NEGATE_EXPR, type, name);
3750 tree name = clast_name_to_gcc (t->var, params, ivstack);
3751 tree cst = gmp_cst_to_tree (type, t->val);
3752 name = fold_convert (type, name);
3753 return fold_build2 (MULT_EXPR, type, cst, name);
3757 return gmp_cst_to_tree (type, t->val);
3762 struct clast_reduction *r = (struct clast_reduction *) e;
3768 return clast_to_gcc_expression (type, r->elts[0], params, ivstack);
3772 tree tl = clast_to_gcc_expression (type, r->elts[0], params, ivstack);
3773 tree tr = clast_to_gcc_expression (type, r->elts[1], params, ivstack);
3775 gcc_assert (r->n >= 1
3776 && r->elts[0]->type == expr_term
3777 && r->elts[1]->type == expr_term);
3779 return fold_build2 (PLUS_EXPR, type, tl, tr);
3786 return clast_to_gcc_expression (type, r->elts[0], params, ivstack);
3790 tree tl = clast_to_gcc_expression (type, r->elts[0], params, ivstack);
3791 tree tr = clast_to_gcc_expression (type, r->elts[1], params, ivstack);
3792 return fold_build2 (MIN_EXPR, type, tl, tr);
3802 return clast_to_gcc_expression (type, r->elts[0], params, ivstack);
3806 tree tl = clast_to_gcc_expression (type, r->elts[0], params, ivstack);
3807 tree tr = clast_to_gcc_expression (type, r->elts[1], params, ivstack);
3808 return fold_build2 (MAX_EXPR, type, tl, tr);
3824 struct clast_binary *b = (struct clast_binary *) e;
3825 struct clast_expr *lhs = (struct clast_expr *) b->LHS;
3826 tree tl = clast_to_gcc_expression (type, lhs, params, ivstack);
3827 tree tr = gmp_cst_to_tree (type, b->RHS);
3831 case clast_bin_fdiv:
3832 return fold_build2 (FLOOR_DIV_EXPR, type, tl, tr);
3834 case clast_bin_cdiv:
3835 return fold_build2 (CEIL_DIV_EXPR, type, tl, tr);
3838 return fold_build2 (EXACT_DIV_EXPR, type, tl, tr);
3841 return fold_build2 (TRUNC_MOD_EXPR, type, tl, tr);
3855 /* Returns the type for the expression E. */
3858 gcc_type_for_clast_expr (struct clast_expr *e,
3859 VEC (name_tree, heap) *params,
3860 loop_iv_stack ivstack)
3866 struct clast_term *t = (struct clast_term *) e;
3869 return TREE_TYPE (clast_name_to_gcc (t->var, params, ivstack));
3876 struct clast_reduction *r = (struct clast_reduction *) e;
3879 return gcc_type_for_clast_expr (r->elts[0], params, ivstack);
3883 for (i = 0; i < r->n; i++)
3885 tree type = gcc_type_for_clast_expr (r->elts[i], params, ivstack);
3895 struct clast_binary *b = (struct clast_binary *) e;
3896 struct clast_expr *lhs = (struct clast_expr *) b->LHS;
3897 return gcc_type_for_clast_expr (lhs, params, ivstack);
3907 /* Returns the type for the equation CLEQ. */
3910 gcc_type_for_clast_eq (struct clast_equation *cleq,
3911 VEC (name_tree, heap) *params,
3912 loop_iv_stack ivstack)
3914 tree type = gcc_type_for_clast_expr (cleq->LHS, params, ivstack);
3918 return gcc_type_for_clast_expr (cleq->RHS, params, ivstack);
3921 /* Translates a clast equation CLEQ to a tree. */
3924 graphite_translate_clast_equation (scop_p scop,
3925 struct clast_equation *cleq,
3926 loop_iv_stack ivstack)
3928 enum tree_code comp;
3929 tree type = gcc_type_for_clast_eq (cleq, SCOP_PARAMS (scop), ivstack);
3930 tree lhs = clast_to_gcc_expression (type, cleq->LHS, SCOP_PARAMS (scop), ivstack);
3931 tree rhs = clast_to_gcc_expression (type, cleq->RHS, SCOP_PARAMS (scop), ivstack);
3933 if (cleq->sign == 0)
3936 else if (cleq->sign > 0)
3942 return fold_build2 (comp, type, lhs, rhs);
3945 /* Creates the test for the condition in STMT. */
3948 graphite_create_guard_cond_expr (scop_p scop, struct clast_guard *stmt,
3949 loop_iv_stack ivstack)
3954 for (i = 0; i < stmt->n; i++)
3956 tree eq = graphite_translate_clast_equation (scop, &stmt->eq[i], ivstack);
3959 cond = fold_build2 (TRUTH_AND_EXPR, TREE_TYPE (eq), cond, eq);
3967 /* Creates a new if region corresponding to Cloog's guard. */
3970 graphite_create_new_guard (scop_p scop, edge entry_edge,
3971 struct clast_guard *stmt,
3972 loop_iv_stack ivstack)
3974 tree cond_expr = graphite_create_guard_cond_expr (scop, stmt, ivstack);
3975 edge exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
3979 /* Walks a CLAST and returns the first statement in the body of a
3982 static struct clast_user_stmt *
3983 clast_get_body_of_loop (struct clast_stmt *stmt)
3986 || CLAST_STMT_IS_A (stmt, stmt_user))
3987 return (struct clast_user_stmt *) stmt;
3989 if (CLAST_STMT_IS_A (stmt, stmt_for))
3990 return clast_get_body_of_loop (((struct clast_for *) stmt)->body);
3992 if (CLAST_STMT_IS_A (stmt, stmt_guard))
3993 return clast_get_body_of_loop (((struct clast_guard *) stmt)->then);
3995 if (CLAST_STMT_IS_A (stmt, stmt_block))
3996 return clast_get_body_of_loop (((struct clast_block *) stmt)->body);
4001 /* Returns the induction variable for the loop that gets translated to
4005 gcc_type_for_iv_of_clast_loop (struct clast_for *stmt_for)
4007 struct clast_user_stmt *stmt = clast_get_body_of_loop ((struct clast_stmt *) stmt_for);
4008 const char *cloog_iv = stmt_for->iterator;
4009 CloogStatement *cs = stmt->statement;
4010 graphite_bb_p gbb = (graphite_bb_p) cloog_statement_usr (cs);
4012 return gcc_type_for_cloog_iv (cloog_iv, gbb);
4015 /* Creates a new LOOP corresponding to Cloog's STMT. Inserts an induction
4016 variable for the new LOOP. New LOOP is attached to CFG starting at
4017 ENTRY_EDGE. LOOP is inserted into the loop tree and becomes the child
4018 loop of the OUTER_LOOP. */
4020 static struct loop *
4021 graphite_create_new_loop (scop_p scop, edge entry_edge,
4022 struct clast_for *stmt, loop_iv_stack ivstack,
4025 tree type = gcc_type_for_iv_of_clast_loop (stmt);
4026 VEC (name_tree, heap) *params = SCOP_PARAMS (scop);
4027 tree lb = clast_to_gcc_expression (type, stmt->LB, params, ivstack);
4028 tree ub = clast_to_gcc_expression (type, stmt->UB, params, ivstack);
4029 tree stride = gmp_cst_to_tree (type, stmt->stride);
4030 tree ivvar = create_tmp_var (type, "graphiteIV");
4032 loop_p loop = create_empty_loop_on_edge
4033 (entry_edge, lb, stride, ub, ivvar, &iv_before,
4034 outer ? outer : entry_edge->src->loop_father);
4036 add_referenced_var (ivvar);
4037 loop_iv_stack_push_iv (ivstack, iv_before, stmt->iterator);
4041 /* Rename the SSA_NAMEs used in STMT and that appear in IVSTACK. */
4044 rename_variables_in_stmt (gimple stmt, htab_t map)
4047 use_operand_p use_p;
4049 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
4051 tree use = USE_FROM_PTR (use_p);
4052 tree new_name = get_new_name_from_old_name (map, use);
4054 replace_exp (use_p, new_name);
4060 /* Returns true if SSA_NAME is a parameter of SCOP. */
4063 is_parameter (scop_p scop, tree ssa_name)
4066 VEC (name_tree, heap) *params = SCOP_PARAMS (scop);
4069 for (i = 0; VEC_iterate (name_tree, params, i, param); i++)
4070 if (param->t == ssa_name)
4076 /* Returns true if NAME is an induction variable. */
4081 return gimple_code (SSA_NAME_DEF_STMT (name)) == GIMPLE_PHI;
4084 static void expand_scalar_variables_stmt (gimple, basic_block, scop_p,
4087 expand_scalar_variables_expr (tree, tree, enum tree_code, tree, basic_block,
4088 scop_p, htab_t, gimple_stmt_iterator *);
4090 /* Copies at GSI all the scalar computations on which the ssa_name OP0
4091 depends on in the SCOP: these are all the scalar variables used in
4092 the definition of OP0, that are defined outside BB and still in the
4093 SCOP, i.e. not a parameter of the SCOP. The expression that is
4094 returned contains only induction variables from the generated code:
4095 MAP contains the induction variables renaming mapping, and is used
4096 to translate the names of induction variables. */
4099 expand_scalar_variables_ssa_name (tree op0, basic_block bb,
4100 scop_p scop, htab_t map,
4101 gimple_stmt_iterator *gsi)
4103 tree var0, var1, type;
4105 enum tree_code subcode;
4107 if (is_parameter (scop, op0)
4109 return get_new_name_from_old_name (map, op0);
4111 def_stmt = SSA_NAME_DEF_STMT (op0);
4113 if (gimple_bb (def_stmt) == bb)
4115 /* If the defining statement is in the basic block already
4116 we do not need to create a new expression for it, we
4117 only need to ensure its operands are expanded. */
4118 expand_scalar_variables_stmt (def_stmt, bb, scop, map);
4119 return get_new_name_from_old_name (map, op0);
4123 if (gimple_code (def_stmt) != GIMPLE_ASSIGN
4124 || !bb_in_scop_p (gimple_bb (def_stmt), scop))
4125 return get_new_name_from_old_name (map, op0);
4127 var0 = gimple_assign_rhs1 (def_stmt);
4128 subcode = gimple_assign_rhs_code (def_stmt);
4129 var1 = gimple_assign_rhs2 (def_stmt);
4130 type = gimple_expr_type (def_stmt);
4132 return expand_scalar_variables_expr (type, var0, subcode, var1, bb, scop,
4137 /* Copies at GSI all the scalar computations on which the expression
4138 OP0 CODE OP1 depends on in the SCOP: these are all the scalar
4139 variables used in OP0 and OP1, defined outside BB and still defined
4140 in the SCOP, i.e. not a parameter of the SCOP. The expression that
4141 is returned contains only induction variables from the generated
4142 code: MAP contains the induction variables renaming mapping, and is
4143 used to translate the names of induction variables. */
4146 expand_scalar_variables_expr (tree type, tree op0, enum tree_code code,
4147 tree op1, basic_block bb, scop_p scop,
4148 htab_t map, gimple_stmt_iterator *gsi)
4150 if (TREE_CODE_CLASS (code) == tcc_constant
4151 || TREE_CODE_CLASS (code) == tcc_declaration)
4154 /* For data references we have to duplicate also its memory
4156 if (TREE_CODE_CLASS (code) == tcc_reference)
4162 tree old_name = TREE_OPERAND (op0, 0);
4163 tree expr = expand_scalar_variables_ssa_name
4164 (old_name, bb, scop, map, gsi);
4165 tree new_name = force_gimple_operand_gsi (gsi, expr, true, NULL,
4166 true, GSI_SAME_STMT);
4168 set_symbol_mem_tag (SSA_NAME_VAR (new_name),
4169 symbol_mem_tag (SSA_NAME_VAR (old_name)));
4170 return fold_build1 (code, type, new_name);
4175 tree op00 = TREE_OPERAND (op0, 0);
4176 tree op01 = TREE_OPERAND (op0, 1);
4177 tree op02 = TREE_OPERAND (op0, 2);
4178 tree op03 = TREE_OPERAND (op0, 3);
4179 tree base = expand_scalar_variables_expr
4180 (TREE_TYPE (op00), op00, TREE_CODE (op00), NULL, bb, scop,
4182 tree subscript = expand_scalar_variables_expr
4183 (TREE_TYPE (op01), op01, TREE_CODE (op01), NULL, bb, scop,
4186 return build4 (ARRAY_REF, type, base, subscript, op02, op03);
4190 /* The above cases should catch everything. */
4195 if (TREE_CODE_CLASS (code) == tcc_unary)
4197 tree op0_type = TREE_TYPE (op0);
4198 enum tree_code op0_code = TREE_CODE (op0);
4199 tree op0_expr = expand_scalar_variables_expr (op0_type, op0, op0_code,
4200 NULL, bb, scop, map, gsi);
4202 return fold_build1 (code, type, op0_expr);
4205 if (TREE_CODE_CLASS (code) == tcc_binary)
4207 tree op0_type = TREE_TYPE (op0);
4208 enum tree_code op0_code = TREE_CODE (op0);
4209 tree op0_expr = expand_scalar_variables_expr (op0_type, op0, op0_code,
4210 NULL, bb, scop, map, gsi);
4211 tree op1_type = TREE_TYPE (op1);
4212 enum tree_code op1_code = TREE_CODE (op1);
4213 tree op1_expr = expand_scalar_variables_expr (op1_type, op1, op1_code,
4214 NULL, bb, scop, map, gsi);
4216 return fold_build2 (code, type, op0_expr, op1_expr);
4219 if (code == SSA_NAME)
4220 return expand_scalar_variables_ssa_name (op0, bb, scop, map, gsi);
4226 /* Copies at the beginning of BB all the scalar computations on which
4227 STMT depends on in the SCOP: these are all the scalar variables used
4228 in STMT, defined outside BB and still defined in the SCOP, i.e. not a
4229 parameter of the SCOP. The expression that is returned contains
4230 only induction variables from the generated code: MAP contains the
4231 induction variables renaming mapping, and is used to translate the
4232 names of induction variables. */
4235 expand_scalar_variables_stmt (gimple stmt, basic_block bb, scop_p scop,
4239 use_operand_p use_p;
4240 gimple_stmt_iterator gsi = gsi_after_labels (bb);
4242 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
4244 tree use = USE_FROM_PTR (use_p);
4245 tree type = TREE_TYPE (use);
4246 enum tree_code code = TREE_CODE (use);
4247 tree use_expr = expand_scalar_variables_expr (type, use, code, NULL, bb,
4249 if (use_expr != use)
4252 force_gimple_operand_gsi (&gsi, use_expr, true, NULL,
4253 true, GSI_NEW_STMT);
4254 replace_exp (use_p, new_use);
4261 /* Copies at the beginning of BB all the scalar computations on which
4262 BB depends on in the SCOP: these are all the scalar variables used
4263 in BB, defined outside BB and still defined in the SCOP, i.e. not a
4264 parameter of the SCOP. The expression that is returned contains
4265 only induction variables from the generated code: MAP contains the
4266 induction variables renaming mapping, and is used to translate the
4267 names of induction variables. */
4270 expand_scalar_variables (basic_block bb, scop_p scop, htab_t map)
4272 gimple_stmt_iterator gsi;
4274 for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi);)
4276 gimple stmt = gsi_stmt (gsi);
4277 expand_scalar_variables_stmt (stmt, bb, scop, map);
4282 /* Rename all the SSA_NAMEs from block BB according to the MAP. */
4285 rename_variables (basic_block bb, htab_t map)
4287 gimple_stmt_iterator gsi;
4289 for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4290 rename_variables_in_stmt (gsi_stmt (gsi), map);
4293 /* Remove condition from BB. */
4296 remove_condition (basic_block bb)
4298 gimple last = last_stmt (bb);
4300 if (last && gimple_code (last) == GIMPLE_COND)
4302 gimple_stmt_iterator gsi = gsi_last_bb (bb);
4303 gsi_remove (&gsi, true);
4307 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag set. */
4310 get_true_edge_from_guard_bb (basic_block bb)
4315 FOR_EACH_EDGE (e, ei, bb->succs)
4316 if (e->flags & EDGE_TRUE_VALUE)
4323 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag cleared. */
4326 get_false_edge_from_guard_bb (basic_block bb)
4331 FOR_EACH_EDGE (e, ei, bb->succs)
4332 if (!(e->flags & EDGE_TRUE_VALUE))
4339 /* Inserts in MAP a tuple (OLD_NAME, NEW_NAME) for the induction
4340 variables of the loops around GBB in SCOP, i.e. GBB_LOOPS.
4341 NEW_NAME is obtained from IVSTACK. IVSTACK has the same stack
4342 ordering as GBB_LOOPS. */
4345 build_iv_mapping (loop_iv_stack ivstack, htab_t map, gbb_p gbb, scop_p scop)
4351 for (i = 0; VEC_iterate (name_tree, SCOP_OLDIVS (scop), i, iv); i++)
4353 struct rename_map_elt tmp;
4355 if (!flow_bb_inside_loop_p (iv->loop, GBB_BB (gbb)))
4358 tmp.old_name = iv->t;
4359 slot = htab_find_slot (map, &tmp, INSERT);
4363 tree new_name = loop_iv_stack_get_iv (ivstack,
4364 gbb_loop_index (gbb, iv->loop));
4365 *slot = new_rename_map_elt (iv->t, new_name);
4370 /* Register in MAP the tuple (old_name, new_name). */
4373 register_old_and_new_names (htab_t map, tree old_name, tree new_name)
4375 struct rename_map_elt tmp;
4378 tmp.old_name = old_name;
4379 slot = htab_find_slot (map, &tmp, INSERT);
4382 *slot = new_rename_map_elt (old_name, new_name);
4385 /* Create a duplicate of the basic block BB. NOTE: This does not
4386 preserve SSA form. */
4389 graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb, htab_t map)
4391 gimple_stmt_iterator gsi, gsi_tgt;
4393 gsi_tgt = gsi_start_bb (new_bb);
4394 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4396 def_operand_p def_p;
4397 ssa_op_iter op_iter;
4399 gimple stmt = gsi_stmt (gsi);
4402 if (gimple_code (stmt) == GIMPLE_LABEL)
4405 /* Create a new copy of STMT and duplicate STMT's virtual
4407 copy = gimple_copy (stmt);
4408 gsi_insert_after (&gsi_tgt, copy, GSI_NEW_STMT);
4409 mark_symbols_for_renaming (copy);
4411 region = lookup_stmt_eh_region (stmt);
4413 add_stmt_to_eh_region (copy, region);
4414 gimple_duplicate_stmt_histograms (cfun, copy, cfun, stmt);
4416 /* Create new names for all the definitions created by COPY and
4417 add replacement mappings for each new name. */
4418 FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_DEF)
4420 tree old_name = DEF_FROM_PTR (def_p);
4421 tree new_name = create_new_def_for (old_name, copy, def_p);
4422 register_old_and_new_names (map, old_name, new_name);
4427 /* Records in SCOP_LIVEOUT_RENAMES the names that are live out of
4428 the SCOP and that appear in the RENAME_MAP. */
4431 register_scop_liveout_renames (scop_p scop, htab_t rename_map)
4434 sese region = SCOP_REGION (scop);
4436 for (i = 0; i < SESE_NUM_VER (region); i++)
4437 if (bitmap_bit_p (SESE_LIVEOUT (region), i)
4438 && is_gimple_reg (ssa_name (i)))
4440 tree old_name = ssa_name (i);
4441 tree new_name = get_new_name_from_old_name (rename_map, old_name);
4443 register_old_and_new_names (SCOP_LIVEOUT_RENAMES (scop),
4444 old_name, new_name);
4448 /* Copies BB and includes in the copied BB all the statements that can
4449 be reached following the use-def chains from the memory accesses,
4450 and returns the next edge following this new block. */
4453 copy_bb_and_scalar_dependences (basic_block bb, scop_p scop,
4454 edge next_e, htab_t map)
4456 basic_block new_bb = split_edge (next_e);
4458 next_e = single_succ_edge (new_bb);
4459 graphite_copy_stmts_from_block (bb, new_bb, map);
4460 remove_condition (new_bb);
4461 rename_variables (new_bb, map);
4462 remove_phi_nodes (new_bb);
4463 expand_scalar_variables (new_bb, scop, map);
4464 register_scop_liveout_renames (scop, map);
4469 /* Helper function for htab_traverse in insert_loop_close_phis. */
4472 add_loop_exit_phis (void **slot, void *s)
4474 struct rename_map_elt *entry = (struct rename_map_elt *) *slot;
4475 tree new_name = entry->new_name;
4476 basic_block bb = (basic_block) s;
4477 gimple phi = create_phi_node (new_name, bb);
4478 tree res = create_new_def_for (gimple_phi_result (phi), phi,
4479 gimple_phi_result_ptr (phi));
4481 add_phi_arg (phi, new_name, single_pred_edge (bb));
4483 entry->new_name = res;
4488 /* Iterate over the SCOP_LIVEOUT_RENAMES (SCOP) and get tuples of the
4489 form (OLD_NAME, NEW_NAME). Insert in BB "RES = phi (NEW_NAME)",
4490 and finally register in SCOP_LIVEOUT_RENAMES (scop) the tuple
4494 insert_loop_close_phis (scop_p scop, basic_block bb)
4496 update_ssa (TODO_update_ssa);
4497 htab_traverse (SCOP_LIVEOUT_RENAMES (scop), add_loop_exit_phis, bb);
4498 update_ssa (TODO_update_ssa);
4501 /* Helper structure for htab_traverse in insert_guard_phis. */
4505 edge true_edge, false_edge;
4506 htab_t liveout_before_guard;
4509 /* Return the default name that is before the guard. */
4512 default_liveout_before_guard (htab_t liveout_before_guard, tree old_name)
4514 tree res = get_new_name_from_old_name (liveout_before_guard, old_name);
4516 if (res == old_name)
4518 if (is_gimple_reg (res))
4519 return fold_convert (TREE_TYPE (res), integer_zero_node);
4520 return gimple_default_def (cfun, res);
4526 /* Helper function for htab_traverse in insert_guard_phis. */
4529 add_guard_exit_phis (void **slot, void *s)
4531 struct rename_map_elt *entry = (struct rename_map_elt *) *slot;
4532 struct igp *i = (struct igp *) s;
4533 basic_block bb = i->bb;
4534 edge true_edge = i->true_edge;
4535 edge false_edge = i->false_edge;
4536 tree name1 = entry->new_name;
4537 tree name2 = default_liveout_before_guard (i->liveout_before_guard,
4539 gimple phi = create_phi_node (name1, bb);
4540 tree res = create_new_def_for (gimple_phi_result (phi), phi,
4541 gimple_phi_result_ptr (phi));
4543 add_phi_arg (phi, name1, true_edge);
4544 add_phi_arg (phi, name2, false_edge);
4546 entry->new_name = res;
4551 /* Iterate over the SCOP_LIVEOUT_RENAMES (SCOP) and get tuples of the
4552 form (OLD_NAME, NAME1). If there is a correspondent tuple of
4553 OLD_NAME in LIVEOUT_BEFORE_GUARD, i.e. (OLD_NAME, NAME2) then
4556 | RES = phi (NAME1 (on TRUE_EDGE), NAME2 (on FALSE_EDGE))"
4558 if there is no tuple for OLD_NAME in LIVEOUT_BEFORE_GUARD, insert
4560 | RES = phi (NAME1 (on TRUE_EDGE),
4561 | DEFAULT_DEFINITION of NAME1 (on FALSE_EDGE))".
4563 Finally register in SCOP_LIVEOUT_RENAMES (scop) the tuple
4567 insert_guard_phis (scop_p scop, basic_block bb, edge true_edge,
4568 edge false_edge, htab_t liveout_before_guard)
4572 i.true_edge = true_edge;
4573 i.false_edge = false_edge;
4574 i.liveout_before_guard = liveout_before_guard;
4576 update_ssa (TODO_update_ssa);
4577 htab_traverse (SCOP_LIVEOUT_RENAMES (scop), add_guard_exit_phis, &i);
4578 update_ssa (TODO_update_ssa);
4581 /* Helper function for htab_traverse. */
4584 copy_renames (void **slot, void *s)
4586 struct rename_map_elt *entry = (struct rename_map_elt *) *slot;
4587 htab_t res = (htab_t) s;
4588 tree old_name = entry->old_name;
4589 tree new_name = entry->new_name;
4590 struct rename_map_elt tmp;
4593 tmp.old_name = old_name;
4594 x = htab_find_slot (res, &tmp, INSERT);
4597 *x = new_rename_map_elt (old_name, new_name);
4602 /* Translates a CLAST statement STMT to GCC representation in the
4605 - NEXT_E is the edge where new generated code should be attached.
4606 - CONTEXT_LOOP is the loop in which the generated code will be placed
4608 - IVSTACK contains the surrounding loops around the statement to be
4613 translate_clast (scop_p scop, struct loop *context_loop,
4614 struct clast_stmt *stmt, edge next_e, loop_iv_stack ivstack)
4619 if (CLAST_STMT_IS_A (stmt, stmt_root))
4620 return translate_clast (scop, context_loop, stmt->next, next_e, ivstack);
4622 if (CLAST_STMT_IS_A (stmt, stmt_user))
4625 CloogStatement *cs = ((struct clast_user_stmt *) stmt)->statement;
4626 graphite_bb_p gbb = (graphite_bb_p) cloog_statement_usr (cs);
4628 if (GBB_BB (gbb) == ENTRY_BLOCK_PTR)
4631 map = htab_create (10, rename_map_elt_info, eq_rename_map_elts, free);
4632 loop_iv_stack_patch_for_consts (ivstack, (struct clast_user_stmt *) stmt);
4633 build_iv_mapping (ivstack, map, gbb, scop);
4634 next_e = copy_bb_and_scalar_dependences (GBB_BB (gbb), scop,
4637 loop_iv_stack_remove_constants (ivstack);
4638 update_ssa (TODO_update_ssa);
4639 recompute_all_dominators ();
4641 return translate_clast (scop, context_loop, stmt->next, next_e, ivstack);
4644 if (CLAST_STMT_IS_A (stmt, stmt_for))
4647 = graphite_create_new_loop (scop, next_e, (struct clast_for *) stmt,
4648 ivstack, context_loop ? context_loop
4650 edge last_e = single_exit (loop);
4652 next_e = translate_clast (scop, loop, ((struct clast_for *) stmt)->body,
4653 single_pred_edge (loop->latch), ivstack);
4654 redirect_edge_succ_nodup (next_e, loop->latch);
4656 set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src);
4657 loop_iv_stack_pop (ivstack);
4658 last_e = single_succ_edge (split_edge (last_e));
4659 insert_loop_close_phis (scop, last_e->src);
4661 recompute_all_dominators ();
4663 return translate_clast (scop, context_loop, stmt->next, last_e, ivstack);
4666 if (CLAST_STMT_IS_A (stmt, stmt_guard))
4668 htab_t liveout_before_guard = htab_create (10, rename_map_elt_info,
4669 eq_rename_map_elts, free);
4670 edge last_e = graphite_create_new_guard (scop, next_e,
4671 ((struct clast_guard *) stmt),
4673 edge true_e = get_true_edge_from_guard_bb (next_e->dest);
4674 edge false_e = get_false_edge_from_guard_bb (next_e->dest);
4675 edge exit_true_e = single_succ_edge (true_e->dest);
4676 edge exit_false_e = single_succ_edge (false_e->dest);
4678 htab_traverse (SCOP_LIVEOUT_RENAMES (scop), copy_renames,
4679 liveout_before_guard);
4681 next_e = translate_clast (scop, context_loop,
4682 ((struct clast_guard *) stmt)->then,
4684 insert_guard_phis (scop, last_e->src, exit_true_e, exit_false_e,
4685 liveout_before_guard);
4686 htab_delete (liveout_before_guard);
4687 recompute_all_dominators ();
4690 return translate_clast (scop, context_loop, stmt->next, last_e, ivstack);
4693 if (CLAST_STMT_IS_A (stmt, stmt_block))
4695 next_e = translate_clast (scop, context_loop,
4696 ((struct clast_block *) stmt)->body,
4698 recompute_all_dominators ();
4700 return translate_clast (scop, context_loop, stmt->next, next_e, ivstack);
4706 /* Free the SCATTERING domain list. */
4709 free_scattering (CloogDomainList *scattering)
4713 CloogDomain *dom = cloog_domain (scattering);
4714 CloogDomainList *next = cloog_next_domain (scattering);
4716 cloog_domain_free (dom);
4722 /* Build cloog program for SCoP. */
4725 build_cloog_prog (scop_p scop)
4728 int max_nb_loops = scop_max_loop_depth (scop);
4730 CloogLoop *loop_list = NULL;
4731 CloogBlockList *block_list = NULL;
4732 CloogDomainList *scattering = NULL;
4733 CloogProgram *prog = SCOP_PROG (scop);
4734 int nbs = 2 * max_nb_loops + 1;
4735 int *scaldims = (int *) xmalloc (nbs * (sizeof (int)));
4737 cloog_program_set_nb_scattdims (prog, nbs);
4738 initialize_cloog_names (scop);
4740 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gbb); i++)
4742 /* Build new block. */
4743 CloogMatrix *domain = GBB_DOMAIN (gbb);
4744 CloogStatement *stmt = cloog_statement_alloc (GBB_BB (gbb)->index);
4745 CloogBlock *block = cloog_block_alloc (stmt, 0, NULL,
4746 nb_loops_around_gb (gbb));
4747 cloog_statement_set_usr (stmt, gbb);
4749 /* Add empty domain to all bbs, which do not yet have a domain, as they
4750 are not part of any loop. */
4753 domain = cloog_matrix_alloc (0, scop_nb_params (scop) + 2);
4754 GBB_DOMAIN (gbb) = domain;
4757 /* Build loop list. */
4759 CloogLoop *new_loop_list = cloog_loop_malloc ();
4760 cloog_loop_set_next (new_loop_list, loop_list);
4761 cloog_loop_set_domain (new_loop_list,
4762 cloog_domain_matrix2domain (domain));
4763 cloog_loop_set_block (new_loop_list, block);
4764 loop_list = new_loop_list;
4767 /* Build block list. */
4769 CloogBlockList *new_block_list = cloog_block_list_malloc ();
4771 cloog_block_list_set_next (new_block_list, block_list);
4772 cloog_block_list_set_block (new_block_list, block);
4773 block_list = new_block_list;
4776 /* Build scattering list. */
4778 /* XXX: Replace with cloog_domain_list_alloc(), when available. */
4779 CloogDomainList *new_scattering
4780 = (CloogDomainList *) xmalloc (sizeof (CloogDomainList));
4781 CloogMatrix *scat_mat = schedule_to_scattering (gbb, nbs);
4783 cloog_set_next_domain (new_scattering, scattering);
4784 cloog_set_domain (new_scattering,
4785 cloog_domain_matrix2domain (scat_mat));
4786 scattering = new_scattering;
4787 cloog_matrix_free (scat_mat);
4791 cloog_program_set_loop (prog, loop_list);
4792 cloog_program_set_blocklist (prog, block_list);
4794 for (i = 0; i < nbs; i++)
4797 cloog_program_set_scaldims (prog, scaldims);
4799 /* Extract scalar dimensions to simplify the code generation problem. */
4800 cloog_program_extract_scalars (prog, scattering);
4802 /* Apply scattering. */
4803 cloog_program_scatter (prog, scattering);
4804 free_scattering (scattering);
4806 /* Iterators corresponding to scalar dimensions have to be extracted. */
4807 cloog_names_scalarize (cloog_program_names (prog), nbs,
4808 cloog_program_scaldims (prog));
4810 /* Free blocklist. */
4812 CloogBlockList *next = cloog_program_blocklist (prog);
4816 CloogBlockList *toDelete = next;
4817 next = cloog_block_list_next (next);
4818 cloog_block_list_set_next (toDelete, NULL);
4819 cloog_block_list_set_block (toDelete, NULL);
4820 cloog_block_list_free (toDelete);
4822 cloog_program_set_blocklist (prog, NULL);
4826 /* Return the options that will be used in GLOOG. */
4828 static CloogOptions *
4829 set_cloog_options (void)
4831 CloogOptions *options = cloog_options_malloc ();
4833 /* Change cloog output language to C. If we do use FORTRAN instead, cloog
4834 will stop e.g. with "ERROR: unbounded loops not allowed in FORTRAN.", if
4835 we pass an incomplete program to cloog. */
4836 options->language = LANGUAGE_C;
4838 /* Enable complex equality spreading: removes dummy statements
4839 (assignments) in the generated code which repeats the
4840 substitution equations for statements. This is useless for
4844 /* Enable C pretty-printing mode: normalizes the substitution
4845 equations for statements. */
4848 /* Allow cloog to build strides with a stride width different to one.
4849 This example has stride = 4:
4851 for (i = 0; i < 20; i += 4)
4853 options->strides = 1;
4855 /* Disable optimizations and make cloog generate source code closer to the
4856 input. This is useful for debugging, but later we want the optimized
4859 XXX: We can not disable optimizations, as loop blocking is not working
4864 options->l = INT_MAX;
4870 /* Prints STMT to STDERR. */
4873 debug_clast_stmt (struct clast_stmt *stmt)
4875 CloogOptions *options = set_cloog_options ();
4877 pprint (stderr, stmt, 0, options);
4880 /* Find the right transform for the SCOP, and return a Cloog AST
4881 representing the new form of the program. */
4883 static struct clast_stmt *
4884 find_transform (scop_p scop)
4886 struct clast_stmt *stmt;
4887 CloogOptions *options = set_cloog_options ();
4889 /* Connect new cloog prog generation to graphite. */
4890 build_cloog_prog (scop);
4892 if (dump_file && (dump_flags & TDF_DETAILS))
4894 fprintf (dump_file, "Cloog Input [\n");
4895 cloog_program_print (dump_file, SCOP_PROG(scop));
4896 fprintf (dump_file, "]\n");
4899 SCOP_PROG (scop) = cloog_program_generate (SCOP_PROG (scop), options);
4900 stmt = cloog_clast_create (SCOP_PROG (scop), options);
4902 if (dump_file && (dump_flags & TDF_DETAILS))
4904 fprintf (dump_file, "Cloog Output[\n");
4905 pprint (dump_file, stmt, 0, options);
4906 cloog_program_dump_cloog (dump_file, SCOP_PROG (scop));
4907 fprintf (dump_file, "]\n");
4910 cloog_options_free (options);
4914 /* Returns true when it is possible to generate code for this STMT.
4915 For the moment we cannot generate code when Cloog decides to
4916 duplicate a statement, as we do not do a copy, but a move.
4917 USED_BASIC_BLOCKS records the blocks that have already been seen.
4918 We return false if we have to generate code twice for the same
4922 can_generate_code_stmt (struct clast_stmt *stmt,
4923 struct pointer_set_t *used_basic_blocks)
4928 if (CLAST_STMT_IS_A (stmt, stmt_root))
4929 return can_generate_code_stmt (stmt->next, used_basic_blocks);
4931 if (CLAST_STMT_IS_A (stmt, stmt_user))
4933 CloogStatement *cs = ((struct clast_user_stmt *) stmt)->statement;
4934 graphite_bb_p gbb = (graphite_bb_p) cloog_statement_usr (cs);
4936 if (pointer_set_contains (used_basic_blocks, gbb))
4938 pointer_set_insert (used_basic_blocks, gbb);
4939 return can_generate_code_stmt (stmt->next, used_basic_blocks);
4942 if (CLAST_STMT_IS_A (stmt, stmt_for))
4943 return can_generate_code_stmt (((struct clast_for *) stmt)->body,
4945 && can_generate_code_stmt (stmt->next, used_basic_blocks);
4947 if (CLAST_STMT_IS_A (stmt, stmt_guard))
4948 return can_generate_code_stmt (((struct clast_guard *) stmt)->then,
4951 if (CLAST_STMT_IS_A (stmt, stmt_block))
4952 return can_generate_code_stmt (((struct clast_block *) stmt)->body,
4954 && can_generate_code_stmt (stmt->next, used_basic_blocks);
4959 /* Returns true when it is possible to generate code for this STMT. */
4962 can_generate_code (struct clast_stmt *stmt)
4965 struct pointer_set_t *used_basic_blocks = pointer_set_create ();
4967 result = can_generate_code_stmt (stmt, used_basic_blocks);
4968 pointer_set_destroy (used_basic_blocks);
4972 /* Remove from the CFG the REGION. */
4975 remove_sese_region (sese region)
4977 VEC (basic_block, heap) *bbs = NULL;
4978 basic_block entry_bb = SESE_ENTRY (region)->dest;
4979 basic_block exit_bb = SESE_EXIT (region)->dest;
4983 VEC_safe_push (basic_block, heap, bbs, entry_bb);
4984 gather_blocks_in_sese_region (entry_bb, exit_bb, &bbs);
4986 for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
4987 delete_basic_block (bb);
4989 VEC_free (basic_block, heap, bbs);
4992 typedef struct ifsese {
4999 if_region_entry (ifsese if_region)
5001 return SESE_ENTRY (if_region->region);
5005 if_region_exit (ifsese if_region)
5007 return SESE_EXIT (if_region->region);
5010 static inline basic_block
5011 if_region_get_condition_block (ifsese if_region)
5013 return if_region_entry (if_region)->dest;
5017 if_region_set_false_region (ifsese if_region, sese region)
5019 basic_block condition = if_region_get_condition_block (if_region);
5020 edge false_edge = get_false_edge_from_guard_bb (condition);
5021 edge entry_region = SESE_ENTRY (region);
5022 edge exit_region = SESE_EXIT (region);
5023 basic_block before_region = entry_region->src;
5024 basic_block last_in_region = exit_region->src;
5025 void **slot = htab_find_slot_with_hash (current_loops->exits, exit_region,
5026 htab_hash_pointer (exit_region),
5029 entry_region->flags = false_edge->flags;
5030 false_edge->flags = exit_region->flags;
5032 redirect_edge_pred (entry_region, condition);
5033 redirect_edge_pred (exit_region, before_region);
5034 redirect_edge_pred (false_edge, last_in_region);
5036 exit_region->flags = EDGE_FALLTHRU;
5037 recompute_all_dominators ();
5039 SESE_EXIT (region) = single_succ_edge (false_edge->dest);
5040 if_region->false_region = region;
5044 struct loop_exit *loop_exit = GGC_CNEW (struct loop_exit);
5046 memcpy (loop_exit, *((struct loop_exit **) slot), sizeof (struct loop_exit));
5047 htab_clear_slot (current_loops->exits, slot);
5049 slot = htab_find_slot_with_hash (current_loops->exits, false_edge,
5050 htab_hash_pointer (false_edge),
5052 loop_exit->e = false_edge;
5054 false_edge->src->loop_father->exits->next = loop_exit;
5059 create_if_region_on_edge (edge entry, tree condition)
5063 sese sese_region = GGC_NEW (struct sese);
5064 sese true_region = GGC_NEW (struct sese);
5065 sese false_region = GGC_NEW (struct sese);
5066 ifsese if_region = GGC_NEW (struct ifsese);
5067 edge exit = create_empty_if_region_on_edge (entry, condition);
5069 if_region->region = sese_region;
5070 if_region->region->entry = entry;
5071 if_region->region->exit = exit;
5073 FOR_EACH_EDGE (e, ei, entry->dest->succs)
5075 if (e->flags & EDGE_TRUE_VALUE)
5077 true_region->entry = e;
5078 true_region->exit = single_succ_edge (e->dest);
5079 if_region->true_region = true_region;
5081 else if (e->flags & EDGE_FALSE_VALUE)
5083 false_region->entry = e;
5084 false_region->exit = single_succ_edge (e->dest);
5085 if_region->false_region = false_region;
5092 /* Moves REGION in a condition expression:
5100 move_sese_in_condition (sese region)
5102 basic_block pred_block = split_edge (SESE_ENTRY (region));
5103 ifsese if_region = NULL;
5105 SESE_ENTRY (region) = single_succ_edge (pred_block);
5106 if_region = create_if_region_on_edge (single_pred_edge (pred_block), integer_one_node);
5107 if_region_set_false_region (if_region, region);
5112 /* Add exit phis for USE on EXIT. */
5115 scop_add_exit_phis_edge (basic_block exit, tree use, edge false_e, edge true_e)
5117 gimple phi = create_phi_node (use, exit);
5119 create_new_def_for (gimple_phi_result (phi), phi,
5120 gimple_phi_result_ptr (phi));
5121 add_phi_arg (phi, use, false_e);
5122 add_phi_arg (phi, use, true_e);
5125 /* Add phi nodes for VAR that is used in LIVEIN. Phi nodes are
5126 inserted in block BB. */
5129 scop_add_exit_phis_var (basic_block bb, tree var, bitmap livein,
5130 edge false_e, edge true_e)
5133 basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (var));
5135 if (is_gimple_reg (var))
5136 bitmap_clear_bit (livein, def_bb->index);
5138 bitmap_set_bit (livein, def_bb->index);
5140 def = BITMAP_ALLOC (NULL);
5141 bitmap_set_bit (def, def_bb->index);
5142 compute_global_livein (livein, def);
5145 scop_add_exit_phis_edge (bb, var, false_e, true_e);
5148 /* Insert in the block BB phi nodes for variables defined in REGION
5149 and used outside the REGION. The code generation moves REGION in
5150 the else clause of an "if (1)" and generates code in the then
5151 clause that is at this point empty:
5160 scop_insert_phis_for_liveouts (sese region, basic_block bb,
5161 edge false_e, edge true_e)
5166 update_ssa (TODO_update_ssa);
5168 EXECUTE_IF_SET_IN_BITMAP (SESE_LIVEOUT (region), 0, i, bi)
5169 scop_add_exit_phis_var (bb, ssa_name (i), SESE_LIVEIN_VER (region, i),
5172 update_ssa (TODO_update_ssa);
5175 /* Get the definition of NAME before the SCOP. Keep track of the
5176 basic blocks that have been VISITED in a bitmap. */
5179 get_vdef_before_scop (scop_p scop, tree name, sbitmap visited)
5182 gimple def_stmt = SSA_NAME_DEF_STMT (name);
5183 basic_block def_bb = gimple_bb (def_stmt);
5185 if (!bb_in_scop_p (def_bb, scop))
5188 if (TEST_BIT (visited, def_bb->index))
5191 SET_BIT (visited, def_bb->index);
5193 switch (gimple_code (def_stmt))
5196 for (i = 0; i < gimple_phi_num_args (def_stmt); i++)
5198 tree arg = gimple_phi_arg_def (def_stmt, i);
5199 tree res = get_vdef_before_scop (scop, arg, visited);
5210 /* Adjust a virtual phi node PHI that is placed at the end of the
5211 generated code for SCOP:
5214 | generated code from REGION;
5218 The FALSE_E edge comes from the original code, TRUE_E edge comes
5219 from the code generated for the SCOP. */
5222 scop_adjust_vphi (scop_p scop, gimple phi, edge true_e)
5226 gcc_assert (gimple_phi_num_args (phi) == 2);
5228 for (i = 0; i < gimple_phi_num_args (phi); i++)
5229 if (gimple_phi_arg_edge (phi, i) == true_e)
5231 tree true_arg, false_arg, before_scop_arg;
5234 true_arg = gimple_phi_arg_def (phi, i);
5235 if (!SSA_NAME_IS_DEFAULT_DEF (true_arg))
5238 false_arg = gimple_phi_arg_def (phi, i == 0 ? 1 : 0);
5239 if (SSA_NAME_IS_DEFAULT_DEF (false_arg))
5242 visited = sbitmap_alloc (last_basic_block);
5243 sbitmap_zero (visited);
5244 before_scop_arg = get_vdef_before_scop (scop, false_arg, visited);
5245 gcc_assert (before_scop_arg != NULL_TREE);
5246 SET_PHI_ARG_DEF (phi, i, before_scop_arg);
5247 sbitmap_free (visited);
5251 /* Adjusts the phi nodes in the block BB for variables defined in
5252 SCOP_REGION and used outside the SCOP_REGION. The code generation
5253 moves SCOP_REGION in the else clause of an "if (1)" and generates
5254 code in the then clause:
5257 | generated code from REGION;
5261 To adjust the phi nodes after the condition, SCOP_LIVEOUT_RENAMES
5262 hash table is used: this stores for a name that is part of the
5263 LIVEOUT of SCOP_REGION its new name in the generated code. */
5266 scop_adjust_phis_for_liveouts (scop_p scop, basic_block bb, edge false_e,
5269 gimple_stmt_iterator si;
5271 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
5273 unsigned i, false_i;
5274 gimple phi = gsi_stmt (si);
5276 if (!is_gimple_reg (PHI_RESULT (phi)))
5278 scop_adjust_vphi (scop, phi, true_e);
5282 for (i = 0; i < gimple_phi_num_args (phi); i++)
5283 if (gimple_phi_arg_edge (phi, i) == false_e)
5289 for (i = 0; i < gimple_phi_num_args (phi); i++)
5290 if (gimple_phi_arg_edge (phi, i) == true_e)
5292 tree old_name = gimple_phi_arg_def (phi, false_i);
5293 tree new_name = get_new_name_from_old_name
5294 (SCOP_LIVEOUT_RENAMES (scop), old_name);
5296 gcc_assert (old_name != new_name);
5297 SET_PHI_ARG_DEF (phi, i, new_name);
5302 /* Returns the first cloog name used in EXPR. */
5305 find_cloog_iv_in_expr (struct clast_expr *expr)
5307 struct clast_term *term = (struct clast_term *) expr;
5309 if (expr->type == expr_term
5313 if (expr->type == expr_term)
5316 if (expr->type == expr_red)
5319 struct clast_reduction *red = (struct clast_reduction *) expr;
5321 for (i = 0; i < red->n; i++)
5323 const char *res = find_cloog_iv_in_expr ((red)->elts[i]);
5333 /* Build for a clast_user_stmt USER_STMT a map between the CLAST
5334 induction variables and the corresponding GCC old induction
5335 variables. This information is stored on each GRAPHITE_BB. */
5338 compute_cloog_iv_types_1 (graphite_bb_p gbb,
5339 struct clast_user_stmt *user_stmt)
5341 struct clast_stmt *t;
5344 for (t = user_stmt->substitutions; t; t = t->next, index++)
5347 struct ivtype_map_elt tmp;
5348 struct clast_expr *expr = (struct clast_expr *)
5349 ((struct clast_assignment *)t)->RHS;
5351 /* Create an entry (clast_var, type). */
5352 tmp.cloog_iv = find_cloog_iv_in_expr (expr);
5356 slot = htab_find_slot (GBB_CLOOG_IV_TYPES (gbb), &tmp, INSERT);
5360 loop_p loop = gbb_loop_at_index (gbb, index);
5361 tree oldiv = oldiv_for_loop (GBB_SCOP (gbb), loop);
5362 tree type = oldiv ? TREE_TYPE (oldiv) : integer_type_node;
5363 *slot = new_ivtype_map_elt (tmp.cloog_iv, type);
5368 /* Walk the CLAST tree starting from STMT and build for each
5369 clast_user_stmt a map between the CLAST induction variables and the
5370 corresponding GCC old induction variables. This information is
5371 stored on each GRAPHITE_BB. */
5374 compute_cloog_iv_types (struct clast_stmt *stmt)
5379 if (CLAST_STMT_IS_A (stmt, stmt_root))
5382 if (CLAST_STMT_IS_A (stmt, stmt_user))
5384 CloogStatement *cs = ((struct clast_user_stmt *) stmt)->statement;
5385 graphite_bb_p gbb = (graphite_bb_p) cloog_statement_usr (cs);
5386 GBB_CLOOG_IV_TYPES (gbb) = htab_create (10, ivtype_map_elt_info,
5387 eq_ivtype_map_elts, free);
5388 compute_cloog_iv_types_1 (gbb, (struct clast_user_stmt *) stmt);
5392 if (CLAST_STMT_IS_A (stmt, stmt_for))
5394 struct clast_stmt *s = ((struct clast_for *) stmt)->body;
5395 compute_cloog_iv_types (s);
5399 if (CLAST_STMT_IS_A (stmt, stmt_guard))
5401 struct clast_stmt *s = ((struct clast_guard *) stmt)->then;
5402 compute_cloog_iv_types (s);
5406 if (CLAST_STMT_IS_A (stmt, stmt_block))
5408 struct clast_stmt *s = ((struct clast_block *) stmt)->body;
5409 compute_cloog_iv_types (s);
5416 compute_cloog_iv_types (stmt->next);
5419 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
5423 gloog (scop_p scop, struct clast_stmt *stmt)
5425 edge new_scop_exit_edge = NULL;
5426 VEC (iv_stack_entry_p, heap) *ivstack = VEC_alloc (iv_stack_entry_p, heap,
5428 loop_p context_loop;
5429 ifsese if_region = NULL;
5431 if (!can_generate_code (stmt))
5433 cloog_clast_free (stmt);
5437 if_region = move_sese_in_condition (SCOP_REGION (scop));
5438 sese_build_livein_liveouts (SCOP_REGION (scop));
5439 scop_insert_phis_for_liveouts (SCOP_REGION (scop),
5440 if_region->region->exit->src,
5441 if_region->false_region->exit,
5442 if_region->true_region->exit);
5443 recompute_all_dominators ();
5445 context_loop = SESE_ENTRY (SCOP_REGION (scop))->src->loop_father;
5446 compute_cloog_iv_types (stmt);
5448 new_scop_exit_edge = translate_clast (scop, context_loop, stmt,
5449 if_region->true_region->entry,
5451 free_loop_iv_stack (&ivstack);
5452 cloog_clast_free (stmt);
5455 scop_adjust_phis_for_liveouts (scop,
5456 if_region->region->exit->src,
5457 if_region->false_region->exit,
5458 if_region->true_region->exit);
5460 recompute_all_dominators ();
5464 /* Returns the number of data references in SCOP. */
5467 nb_data_refs_in_scop (scop_p scop)
5473 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gbb); i++)
5474 res += VEC_length (data_reference_p, GBB_DATA_REFS (gbb));
5479 /* Move the loop at index LOOP and insert it before index NEW_LOOP_POS.
5480 This transformartion is only valid, if the loop nest between i and k is
5481 perfectly nested. Therefore we do not need to change the static schedule.
5485 for (i = 0; i < 50; i++)
5487 for (k = 5; k < 100; k++)
5490 To move k before i use:
5492 graphite_trans_bb_move_loop (A, 2, 0)
5494 for (k = 5; k < 100; k++)
5495 for (i = 0; i < 50; i++)
5501 graphite_trans_bb_move_loop (A, 0, 2)
5503 This function does not check the validity of interchanging loops.
5504 This should be checked before calling this function. */
5507 graphite_trans_bb_move_loop (graphite_bb_p gb, int loop,
5510 CloogMatrix *domain = GBB_DOMAIN (gb);
5514 gcc_assert (loop < gbb_nb_loops (gb)
5515 && new_loop_pos < gbb_nb_loops (gb));
5517 /* Update LOOPS vector. */
5518 tmp_loop_p = VEC_index (loop_p, GBB_LOOPS (gb), loop);
5519 VEC_ordered_remove (loop_p, GBB_LOOPS (gb), loop);
5520 VEC_safe_insert (loop_p, heap, GBB_LOOPS (gb), new_loop_pos, tmp_loop_p);
5522 /* Move the domain columns. */
5523 if (loop < new_loop_pos)
5524 for (row = 0; row < domain->NbRows; row++)
5528 value_assign (tmp, domain->p[row][loop + 1]);
5530 for (j = loop ; j < new_loop_pos - 1; j++)
5531 value_assign (domain->p[row][j + 1], domain->p[row][j + 2]);
5533 value_assign (domain->p[row][new_loop_pos], tmp);
5537 for (row = 0; row < domain->NbRows; row++)
5541 value_assign (tmp, domain->p[row][loop + 1]);
5543 for (j = loop ; j > new_loop_pos; j--)
5544 value_assign (domain->p[row][j + 1], domain->p[row][j]);
5546 value_assign (domain->p[row][new_loop_pos + 1], tmp);
5551 /* Get the index of the column representing constants in the DOMAIN
5555 const_column_index (CloogMatrix *domain)
5557 return domain->NbColumns - 1;
5561 /* Get the first index that is positive or negative, determined
5562 following the value of POSITIVE, in matrix DOMAIN in COLUMN. */
5565 get_first_matching_sign_row_index (CloogMatrix *domain, int column,
5570 for (row = 0; row < domain->NbRows; row++)
5572 int val = value_get_si (domain->p[row][column]);
5574 if (val > 0 && positive)
5577 else if (val < 0 && !positive)
5584 /* Get the lower bound of COLUMN in matrix DOMAIN. */
5587 get_lower_bound_row (CloogMatrix *domain, int column)
5589 return get_first_matching_sign_row_index (domain, column, true);
5592 /* Get the upper bound of COLUMN in matrix DOMAIN. */
5595 get_upper_bound_row (CloogMatrix *domain, int column)
5597 return get_first_matching_sign_row_index (domain, column, false);
5600 /* Copies the OLD_ROW constraint from OLD_DOMAIN to the NEW_DOMAIN at
5604 copy_constraint (CloogMatrix *old_domain, CloogMatrix *new_domain,
5605 int old_row, int new_row)
5609 gcc_assert (old_domain->NbColumns == new_domain->NbColumns
5610 && old_row < old_domain->NbRows
5611 && new_row < new_domain->NbRows);
5613 for (i = 0; i < old_domain->NbColumns; i++)
5614 value_assign (new_domain->p[new_row][i], old_domain->p[old_row][i]);
5617 /* Swap coefficients of variables X and Y on row R. */
5620 swap_constraint_variables (CloogMatrix *domain,
5621 int r, int x, int y)
5623 value_swap (domain->p[r][x], domain->p[r][y]);
5626 /* Scale by X the coefficient C of constraint at row R in DOMAIN. */
5629 scale_constraint_variable (CloogMatrix *domain,
5630 int r, int c, int x)
5632 Value strip_size_value;
5633 value_init (strip_size_value);
5634 value_set_si (strip_size_value, x);
5635 value_multiply (domain->p[r][c], domain->p[r][c], strip_size_value);
5636 value_clear (strip_size_value);
5639 /* Strip mines the loop of BB at the position LOOP_DEPTH with STRIDE.
5640 Always valid, but not always a performance improvement. */
5643 graphite_trans_bb_strip_mine (graphite_bb_p gb, int loop_depth, int stride)
5647 CloogMatrix *domain = GBB_DOMAIN (gb);
5648 CloogMatrix *new_domain = cloog_matrix_alloc (domain->NbRows + 3,
5649 domain->NbColumns + 1);
5651 int col_loop_old = loop_depth + 2;
5652 int col_loop_strip = col_loop_old - 1;
5654 gcc_assert (loop_depth <= gbb_nb_loops (gb) - 1);
5656 VEC_safe_insert (loop_p, heap, GBB_LOOPS (gb), loop_depth, NULL);
5658 GBB_DOMAIN (gb) = new_domain;
5660 for (row = 0; row < domain->NbRows; row++)
5661 for (col = 0; col < domain->NbColumns; col++)
5662 if (col <= loop_depth)
5663 value_assign (new_domain->p[row][col], domain->p[row][col]);
5665 value_assign (new_domain->p[row][col + 1], domain->p[row][col]);
5667 row = domain->NbRows;
5669 /* Lower bound of the outer stripped loop. */
5670 copy_constraint (new_domain, new_domain,
5671 get_lower_bound_row (new_domain, col_loop_old), row);
5672 swap_constraint_variables (new_domain, row, col_loop_old, col_loop_strip);
5675 /* Upper bound of the outer stripped loop. */
5676 copy_constraint (new_domain, new_domain,
5677 get_upper_bound_row (new_domain, col_loop_old), row);
5678 swap_constraint_variables (new_domain, row, col_loop_old, col_loop_strip);
5679 scale_constraint_variable (new_domain, row, col_loop_strip, stride);
5682 /* Lower bound of a tile starts at "stride * outer_iv". */
5683 row = get_lower_bound_row (new_domain, col_loop_old);
5684 value_set_si (new_domain->p[row][0], 1);
5685 value_set_si (new_domain->p[row][const_column_index (new_domain)], 0);
5686 value_set_si (new_domain->p[row][col_loop_old], 1);
5687 value_set_si (new_domain->p[row][col_loop_strip], -1 * stride);
5689 /* Upper bound of a tile stops at "stride * outer_iv + stride - 1",
5690 or at the old upper bound that is not modified. */
5691 row = new_domain->NbRows - 1;
5692 value_set_si (new_domain->p[row][0], 1);
5693 value_set_si (new_domain->p[row][col_loop_old], -1);
5694 value_set_si (new_domain->p[row][col_loop_strip], stride);
5695 value_set_si (new_domain->p[row][const_column_index (new_domain)],
5698 cloog_matrix_free (domain);
5700 /* Update static schedule. */
5703 int nb_loops = gbb_nb_loops (gb);
5704 lambda_vector new_schedule = lambda_vector_new (nb_loops + 1);
5706 for (i = 0; i <= loop_depth; i++)
5707 new_schedule[i] = GBB_STATIC_SCHEDULE (gb)[i];
5709 for (i = loop_depth + 1; i <= nb_loops - 2; i++)
5710 new_schedule[i + 2] = GBB_STATIC_SCHEDULE (gb)[i];
5712 GBB_STATIC_SCHEDULE (gb) = new_schedule;
5716 /* Returns true when the strip mining of LOOP_INDEX by STRIDE is
5717 profitable or undecidable. GB is the statement around which the
5718 loops will be strip mined. */
5721 strip_mine_profitable_p (graphite_bb_p gb, int stride,
5730 loop = VEC_index (loop_p, GBB_LOOPS (gb), loop_index);
5731 exit = single_exit (loop);
5733 niter = find_loop_niter (loop, &exit);
5734 if (niter == chrec_dont_know
5735 || TREE_CODE (niter) != INTEGER_CST)
5738 niter_val = int_cst_value (niter);
5740 if (niter_val < stride)
5743 if (dump_file && (dump_flags & TDF_DETAILS))
5745 fprintf (dump_file, "\nStrip Mining is not profitable for loop %d:",
5747 fprintf (dump_file, "number of iterations is too low.\n");
5754 /* Determines when the interchange of LOOP_A and LOOP_B belonging to
5755 SCOP is legal. DEPTH is the number of loops around. */
5758 is_interchange_valid (scop_p scop, int loop_a, int loop_b, int depth)
5761 VEC (ddr_p, heap) *dependence_relations;
5762 VEC (data_reference_p, heap) *datarefs;
5764 struct loop *nest = VEC_index (loop_p, SCOP_LOOP_NEST (scop), loop_a);
5765 lambda_trans_matrix trans;
5767 gcc_assert (loop_a < loop_b);
5769 dependence_relations = VEC_alloc (ddr_p, heap, 10 * 10);
5770 datarefs = VEC_alloc (data_reference_p, heap, 10);
5772 if (!compute_data_dependences_for_loop (nest, true, &datarefs,
5773 &dependence_relations))
5776 if (dump_file && (dump_flags & TDF_DETAILS))
5777 dump_ddrs (dump_file, dependence_relations);
5779 trans = lambda_trans_matrix_new (depth, depth);
5780 lambda_matrix_id (LTM_MATRIX (trans), depth);
5782 lambda_matrix_row_exchange (LTM_MATRIX (trans), 0, loop_b - loop_a);
5784 if (!lambda_transform_legal_p (trans, depth, dependence_relations))
5786 lambda_matrix_row_exchange (LTM_MATRIX (trans), 0, loop_b - loop_a);
5792 free_dependence_relations (dependence_relations);
5793 free_data_refs (datarefs);
5797 /* Loop block the LOOPS innermost loops of GB with stride size STRIDE.
5801 for (i = 0; i <= 50; i++=4)
5802 for (k = 0; k <= 100; k++=4)
5803 for (l = 0; l <= 200; l++=4)
5806 To strip mine the two inner most loops with stride = 4 call:
5808 graphite_trans_bb_block (A, 4, 2)
5810 for (i = 0; i <= 50; i++)
5811 for (kk = 0; kk <= 100; kk+=4)
5812 for (ll = 0; ll <= 200; ll+=4)
5813 for (k = kk; k <= min (100, kk + 3); k++)
5814 for (l = ll; l <= min (200, ll + 3); l++)
5819 graphite_trans_bb_block (graphite_bb_p gb, int stride, int loops)
5822 int nb_loops = gbb_nb_loops (gb);
5823 int start = nb_loops - loops;
5824 scop_p scop = GBB_SCOP (gb);
5826 gcc_assert (scop_contains_loop (scop, gbb_loop (gb)));
5828 for (i = start ; i < nb_loops; i++)
5829 for (j = i + 1; j < nb_loops; j++)
5830 if (!is_interchange_valid (scop, i, j, nb_loops))
5832 if (dump_file && (dump_flags & TDF_DETAILS))
5834 "\nInterchange not valid for loops %d and %d:\n", i, j);
5837 else if (dump_file && (dump_flags & TDF_DETAILS))
5839 "\nInterchange valid for loops %d and %d:\n", i, j);
5841 /* Check if strip mining is profitable for every loop. */
5842 for (i = 0; i < nb_loops - start; i++)
5843 if (!strip_mine_profitable_p (gb, stride, start + i))
5846 /* Strip mine loops. */
5847 for (i = 0; i < nb_loops - start; i++)
5848 graphite_trans_bb_strip_mine (gb, start + 2 * i, stride);
5850 /* Interchange loops. */
5851 for (i = 1; i < nb_loops - start; i++)
5852 graphite_trans_bb_move_loop (gb, start + 2 * i, start + i);
5854 if (dump_file && (dump_flags & TDF_DETAILS))
5855 fprintf (dump_file, "\nLoops containing BB %d will be loop blocked.\n",
5856 GBB_BB (gb)->index);
5861 /* Loop block LOOPS innermost loops of a loop nest. BBS represent the
5862 basic blocks that belong to the loop nest to be blocked. */
5865 graphite_trans_loop_block (VEC (graphite_bb_p, heap) *bbs, int loops)
5869 bool transform_done = false;
5871 /* TODO: - Calculate the stride size automatically. */
5872 int stride_size = 64;
5874 for (i = 0; VEC_iterate (graphite_bb_p, bbs, i, gb); i++)
5875 transform_done |= graphite_trans_bb_block (gb, stride_size, loops);
5877 return transform_done;
5880 /* Loop block all basic blocks of SCOP. Return false when the
5881 transform is not performed. */
5884 graphite_trans_scop_block (scop_p scop)
5890 bool perfect = true;
5891 bool transform_done = false;
5893 VEC (graphite_bb_p, heap) *bbs = VEC_alloc (graphite_bb_p, heap, 3);
5894 int max_schedule = scop_max_loop_depth (scop) + 1;
5895 lambda_vector last_schedule = lambda_vector_new (max_schedule);
5897 if (VEC_length (graphite_bb_p, SCOP_BBS (scop)) == 0)
5900 /* Get the data of the first bb. */
5901 gb = VEC_index (graphite_bb_p, SCOP_BBS (scop), 0);
5902 last_nb_loops = gbb_nb_loops (gb);
5903 lambda_vector_copy (GBB_STATIC_SCHEDULE (gb), last_schedule,
5905 VEC_safe_push (graphite_bb_p, heap, bbs, gb);
5907 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
5909 /* We did the first bb before. */
5913 nb_loops = gbb_nb_loops (gb);
5915 /* If the number of loops is unchanged and only the last element of the
5916 schedule changes, we stay in the loop nest. */
5917 if (nb_loops == last_nb_loops
5918 && (last_schedule [nb_loops + 1]
5919 != GBB_STATIC_SCHEDULE (gb)[nb_loops + 1]))
5921 VEC_safe_push (graphite_bb_p, heap, bbs, gb);
5925 /* Otherwise, we left the innermost loop. So check, if the last bb was in
5926 a perfect loop nest and how many loops are contained in this perfect
5929 Count the number of zeros from the end of the schedule. They are the
5930 number of surrounding loops.
5933 last_bb 2 3 2 0 0 0 0 3
5937 last_bb 2 3 2 0 0 0 0 3
5941 If there is no zero, there were other bbs in outer loops and the loop
5942 nest is not perfect. */
5943 for (j = last_nb_loops - 1; j >= 0; j--)
5945 if (last_schedule [j] != 0
5946 || (j <= nb_loops && GBB_STATIC_SCHEDULE (gb)[j] == 1))
5955 /* Found perfect loop nest. */
5956 if (perfect && last_nb_loops - j >= 2)
5957 transform_done |= graphite_trans_loop_block (bbs, last_nb_loops - j);
5959 /* Check if we start with a new loop.
5963 last_bb 2 3 2 0 0 0 0 3
5966 Here we start with the loop "2 3 2 0 0 1"
5968 last_bb 2 3 2 0 0 0 0 3
5971 But here not, so the loop nest can never be perfect. */
5973 perfect = (GBB_STATIC_SCHEDULE (gb)[nb_loops] == 0);
5975 /* Update the last_bb infos. We do not do that for the bbs in the same
5976 loop, as the data we use is not changed. */
5977 last_nb_loops = nb_loops;
5978 lambda_vector_copy (GBB_STATIC_SCHEDULE (gb), last_schedule,
5980 VEC_truncate (graphite_bb_p, bbs, 0);
5981 VEC_safe_push (graphite_bb_p, heap, bbs, gb);
5984 /* Check if the last loop nest was perfect. It is the same check as above,
5985 but the comparison with the next bb is missing. */
5986 for (j = last_nb_loops - 1; j >= 0; j--)
5987 if (last_schedule [j] != 0)
5995 /* Found perfect loop nest. */
5996 if (last_nb_loops - j > 0)
5997 transform_done |= graphite_trans_loop_block (bbs, last_nb_loops - j);
5998 VEC_free (graphite_bb_p, heap, bbs);
6000 return transform_done;
6003 /* Apply graphite transformations to all the basic blocks of SCOP. */
6006 graphite_apply_transformations (scop_p scop)
6008 bool transform_done = false;
6010 /* Sort the list of bbs. Keep them always sorted. */
6011 graphite_sort_gbbs (scop);
6013 if (flag_loop_block)
6014 transform_done = graphite_trans_scop_block (scop);
6016 /* Generate code even if we did not apply any real transformation.
6017 This also allows to check the performance for the identity
6018 transformation: GIMPLE -> GRAPHITE -> GIMPLE
6019 Keep in mind that CLooG optimizes in control, so the loop structure
6020 may change, even if we only use -fgraphite-identity. */
6021 if (flag_graphite_identity)
6022 transform_done = true;
6024 return transform_done;
6027 /* We limit all SCoPs to SCoPs, that are completely surrounded by a loop.
6037 * SCoP frontier, as this line is not surrounded by any loop. *
6041 This is necessary as scalar evolution and parameter detection need a
6042 outermost loop to initialize parameters correctly.
6044 TODO: FIX scalar evolution and parameter detection to allow more flexible
6050 VEC (sd_region, heap) *tmp_scops = VEC_alloc (sd_region, heap, 3);
6055 for (i = 0; VEC_iterate (scop_p, current_scops, i, scop); i++)
6059 build_scop_bbs (scop);
6061 if (!build_scop_loop_nests (scop))
6064 for (j = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), j, loop); j++)
6065 if (!loop_in_scop_p (loop_outer (loop), scop))
6067 sd_region open_scop;
6068 open_scop.entry = loop->header;
6069 open_scop.exit = single_exit (loop)->dest;
6070 VEC_safe_push (sd_region, heap, tmp_scops, &open_scop);
6074 free_scops (current_scops);
6075 current_scops = VEC_alloc (scop_p, heap, 3);
6077 create_sese_edges (tmp_scops);
6078 build_graphite_scops (tmp_scops);
6079 VEC_free (sd_region, heap, tmp_scops);
6082 /* Perform a set of linear transforms on the loops of the current
6086 graphite_transform_loops (void)
6091 if (number_of_loops () <= 1)
6094 current_scops = VEC_alloc (scop_p, heap, 3);
6095 recompute_all_dominators ();
6097 if (dump_file && (dump_flags & TDF_DETAILS))
6098 fprintf (dump_file, "Graphite loop transformations \n");
6100 initialize_original_copy_tables ();
6101 cloog_initialize ();
6105 if (dump_file && (dump_flags & TDF_DETAILS))
6106 fprintf (dump_file, "\nnumber of SCoPs: %d\n",
6107 VEC_length (scop_p, current_scops));
6109 for (i = 0; VEC_iterate (scop_p, current_scops, i, scop); i++)
6111 build_scop_bbs (scop);
6112 if (!build_scop_loop_nests (scop))
6115 build_scop_canonical_schedules (scop);
6116 build_bb_loops (scop);
6117 if (!build_scop_conditions (scop))
6119 find_scop_parameters (scop);
6120 build_scop_context (scop);
6122 if (dump_file && (dump_flags & TDF_DETAILS))
6124 fprintf (dump_file, "\n(In SCoP %d:\n", i);
6125 fprintf (dump_file, "\nnumber of bbs: %d\n",
6126 VEC_length (graphite_bb_p, SCOP_BBS (scop)));
6127 fprintf (dump_file, "\nnumber of loops: %d)\n",
6128 VEC_length (loop_p, SCOP_LOOP_NEST (scop)));
6131 if (!build_scop_iteration_domain (scop))
6134 build_scop_data_accesses (scop);
6135 build_scop_dynamic_schedules (scop);
6137 if (dump_file && (dump_flags & TDF_DETAILS))
6139 int nbrefs = nb_data_refs_in_scop (scop);
6140 fprintf (dump_file, "\nnumber of data refs: %d\n", nbrefs);
6143 if (graphite_apply_transformations (scop))
6144 gloog (scop, find_transform (scop));
6145 #ifdef ENABLE_CHECKING
6148 struct clast_stmt *stmt = find_transform (scop);
6149 cloog_clast_free (stmt);
6155 cleanup_tree_cfg ();
6156 free_scops (current_scops);
6158 free_original_copy_tables ();
6161 #else /* If Cloog is not available: #ifndef HAVE_cloog. */
6164 graphite_transform_loops (void)
6166 sorry ("Graphite loop optimizations cannot be used");