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 if (lhs && !is_simple_operand (loop, stmt, lhs))
1046 for (i = 0; i < n; i++)
1047 if (!is_simple_operand (loop, stmt, gimple_call_arg (stmt, i)))
1054 /* These nodes cut a new scope. */
1061 /* Returns the statement of BB that contains a harmful operation: that
1062 can be a function call with side effects, the induction variables
1063 are not linear with respect to SCOP_ENTRY, etc. The current open
1064 scop should end before this statement. */
1067 harmful_stmt_in_bb (basic_block scop_entry, basic_block bb)
1069 gimple_stmt_iterator gsi;
1071 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1072 if (!stmt_simple_for_scop_p (scop_entry, gsi_stmt (gsi)))
1073 return gsi_stmt (gsi);
1078 /* Returns true when BB will be represented in graphite. Return false
1079 for the basic blocks that contain code eliminated in the code
1080 generation pass: i.e. induction variables and exit conditions. */
1083 graphite_stmt_p (scop_p scop, basic_block bb,
1084 VEC (data_reference_p, heap) *drs)
1086 gimple_stmt_iterator gsi;
1087 loop_p loop = bb->loop_father;
1089 if (VEC_length (data_reference_p, drs) > 0)
1092 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1094 gimple stmt = gsi_stmt (gsi);
1096 switch (gimple_code (stmt))
1098 /* Control flow expressions can be ignored, as they are
1099 represented in the iteration domains and will be
1100 regenerated by graphite. */
1108 tree var = gimple_assign_lhs (stmt);
1109 var = analyze_scalar_evolution (loop, var);
1110 var = instantiate_scev (block_before_scop (scop), loop, var);
1112 if (chrec_contains_undetermined (var))
1126 /* Store the GRAPHITE representation of BB. */
1129 new_graphite_bb (scop_p scop, basic_block bb)
1131 struct graphite_bb *gbb;
1132 VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 5);
1133 struct loop *nest = outermost_loop_in_scop (scop, bb);
1134 gimple_stmt_iterator gsi;
1136 bitmap_set_bit (SCOP_BBS_B (scop), bb->index);
1138 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1139 find_data_references_in_stmt (nest, gsi_stmt (gsi), &drs);
1141 if (!graphite_stmt_p (scop, bb, drs))
1143 free_data_refs (drs);
1147 gbb = XNEW (struct graphite_bb);
1150 GBB_SCOP (gbb) = scop;
1151 GBB_DATA_REFS (gbb) = drs;
1152 GBB_DOMAIN (gbb) = NULL;
1153 GBB_CONDITIONS (gbb) = NULL;
1154 GBB_CONDITION_CASES (gbb) = NULL;
1155 GBB_LOOPS (gbb) = NULL;
1156 GBB_STATIC_SCHEDULE (gbb) = NULL;
1157 GBB_CLOOG_IV_TYPES (gbb) = NULL;
1158 VEC_safe_push (graphite_bb_p, heap, SCOP_BBS (scop), gbb);
1164 free_graphite_bb (struct graphite_bb *gbb)
1166 if (GBB_DOMAIN (gbb))
1167 cloog_matrix_free (GBB_DOMAIN (gbb));
1169 if (GBB_CLOOG_IV_TYPES (gbb))
1170 htab_delete (GBB_CLOOG_IV_TYPES (gbb));
1172 /* FIXME: free_data_refs is disabled for the moment, but should be
1175 free_data_refs (GBB_DATA_REFS (gbb)); */
1177 VEC_free (gimple, heap, GBB_CONDITIONS (gbb));
1178 VEC_free (gimple, heap, GBB_CONDITION_CASES (gbb));
1179 VEC_free (loop_p, heap, GBB_LOOPS (gbb));
1180 GBB_BB (gbb)->aux = 0;
1186 /* Structure containing the mapping between the old names and the new
1187 names used after block copy in the new loop context. */
1188 typedef struct rename_map_elt
1190 tree old_name, new_name;
1194 /* Print to stderr the element ELT. */
1197 debug_rename_elt (rename_map_elt elt)
1199 fprintf (stderr, "(");
1200 print_generic_expr (stderr, elt->old_name, 0);
1201 fprintf (stderr, ", ");
1202 print_generic_expr (stderr, elt->new_name, 0);
1203 fprintf (stderr, ")\n");
1206 /* Helper function for debug_rename_map. */
1209 debug_rename_map_1 (void **slot, void *s ATTRIBUTE_UNUSED)
1211 struct rename_map_elt *entry = (struct rename_map_elt *) *slot;
1212 debug_rename_elt (entry);
1216 /* Print to stderr all the elements of MAP. */
1219 debug_rename_map (htab_t map)
1221 htab_traverse (map, debug_rename_map_1, NULL);
1224 /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */
1226 static inline rename_map_elt
1227 new_rename_map_elt (tree old_name, tree new_name)
1231 res = XNEW (struct rename_map_elt);
1232 res->old_name = old_name;
1233 res->new_name = new_name;
1238 /* Computes a hash function for database element ELT. */
1241 rename_map_elt_info (const void *elt)
1243 return htab_hash_pointer (((const struct rename_map_elt *) elt)->old_name);
1246 /* Compares database elements E1 and E2. */
1249 eq_rename_map_elts (const void *e1, const void *e2)
1251 const struct rename_map_elt *elt1 = (const struct rename_map_elt *) e1;
1252 const struct rename_map_elt *elt2 = (const struct rename_map_elt *) e2;
1254 return (elt1->old_name == elt2->old_name);
1257 /* Returns the new name associated to OLD_NAME in MAP. */
1260 get_new_name_from_old_name (htab_t map, tree old_name)
1262 struct rename_map_elt tmp;
1265 tmp.old_name = old_name;
1266 slot = htab_find_slot (map, &tmp, NO_INSERT);
1269 return ((rename_map_elt) *slot)->new_name;
1276 /* Returns true when BB is in REGION. */
1279 bb_in_sese_p (basic_block bb, sese region)
1281 return pointer_set_contains (SESE_REGION_BBS (region), bb);
1284 /* For a USE in BB, if BB is outside REGION, mark the USE in the
1285 SESE_LIVEIN and SESE_LIVEOUT sets. */
1288 sese_build_livein_liveouts_use (sese region, basic_block bb, tree use)
1293 if (TREE_CODE (use) != SSA_NAME)
1296 ver = SSA_NAME_VERSION (use);
1297 def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
1299 || !bb_in_sese_p (def_bb, region)
1300 || bb_in_sese_p (bb, region))
1303 if (!SESE_LIVEIN_VER (region, ver))
1304 SESE_LIVEIN_VER (region, ver) = BITMAP_ALLOC (NULL);
1306 bitmap_set_bit (SESE_LIVEIN_VER (region, ver), bb->index);
1307 bitmap_set_bit (SESE_LIVEOUT (region), ver);
1310 /* Marks for rewrite all the SSA_NAMES defined in REGION and that are
1311 used in BB that is outside of the REGION. */
1314 sese_build_livein_liveouts_bb (sese region, basic_block bb)
1316 gimple_stmt_iterator bsi;
1322 FOR_EACH_EDGE (e, ei, bb->succs)
1323 for (bsi = gsi_start_phis (e->dest); !gsi_end_p (bsi); gsi_next (&bsi))
1324 sese_build_livein_liveouts_use (region, bb,
1325 PHI_ARG_DEF_FROM_EDGE (gsi_stmt (bsi), e));
1327 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
1328 FOR_EACH_SSA_TREE_OPERAND (var, gsi_stmt (bsi), iter, SSA_OP_ALL_USES)
1329 sese_build_livein_liveouts_use (region, bb, var);
1332 /* Build the SESE_LIVEIN and SESE_LIVEOUT for REGION. */
1335 sese_build_livein_liveouts (sese region)
1339 SESE_LIVEOUT (region) = BITMAP_ALLOC (NULL);
1340 SESE_NUM_VER (region) = num_ssa_names;
1341 SESE_LIVEIN (region) = XCNEWVEC (bitmap, SESE_NUM_VER (region));
1344 sese_build_livein_liveouts_bb (region, bb);
1347 /* Register basic blocks belonging to a region in a pointer set. */
1350 register_bb_in_sese (basic_block entry_bb, basic_block exit_bb, sese region)
1354 basic_block bb = entry_bb;
1356 FOR_EACH_EDGE (e, ei, bb->succs)
1358 if (!pointer_set_contains (SESE_REGION_BBS (region), e->dest) &&
1359 e->dest->index != exit_bb->index)
1361 pointer_set_insert (SESE_REGION_BBS (region), e->dest);
1362 register_bb_in_sese (e->dest, exit_bb, region);
1367 /* Builds a new SESE region from edges ENTRY and EXIT. */
1370 new_sese (edge entry, edge exit)
1372 sese res = XNEW (struct sese);
1374 SESE_ENTRY (res) = entry;
1375 SESE_EXIT (res) = exit;
1376 SESE_REGION_BBS (res) = pointer_set_create ();
1377 register_bb_in_sese (entry->dest, exit->dest, res);
1379 SESE_LIVEOUT (res) = NULL;
1380 SESE_NUM_VER (res) = 0;
1381 SESE_LIVEIN (res) = NULL;
1386 /* Deletes REGION. */
1389 free_sese (sese region)
1393 for (i = 0; i < SESE_NUM_VER (region); i++)
1394 BITMAP_FREE (SESE_LIVEIN_VER (region, i));
1396 if (SESE_LIVEIN (region))
1397 free (SESE_LIVEIN (region));
1399 if (SESE_LIVEOUT (region))
1400 BITMAP_FREE (SESE_LIVEOUT (region));
1402 pointer_set_destroy (SESE_REGION_BBS (region));
1408 /* Creates a new scop starting with ENTRY. */
1411 new_scop (edge entry, edge exit)
1413 scop_p scop = XNEW (struct scop);
1415 gcc_assert (entry && exit);
1417 SCOP_REGION (scop) = new_sese (entry, exit);
1418 SCOP_BBS (scop) = VEC_alloc (graphite_bb_p, heap, 3);
1419 SCOP_OLDIVS (scop) = VEC_alloc (name_tree, heap, 3);
1420 SCOP_BBS_B (scop) = BITMAP_ALLOC (NULL);
1421 SCOP_LOOPS (scop) = BITMAP_ALLOC (NULL);
1422 SCOP_LOOP_NEST (scop) = VEC_alloc (loop_p, heap, 3);
1423 SCOP_ADD_PARAMS (scop) = true;
1424 SCOP_PARAMS (scop) = VEC_alloc (name_tree, heap, 3);
1425 SCOP_PROG (scop) = cloog_program_malloc ();
1426 cloog_program_set_names (SCOP_PROG (scop), cloog_names_malloc ());
1427 SCOP_LOOP2CLOOG_LOOP (scop) = htab_create (10, hash_loop_to_cloog_loop,
1428 eq_loop_to_cloog_loop,
1430 SCOP_LIVEOUT_RENAMES (scop) = htab_create (10, rename_map_elt_info,
1431 eq_rename_map_elts, free);
1438 free_scop (scop_p scop)
1442 struct graphite_bb *gb;
1445 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
1446 free_graphite_bb (gb);
1448 VEC_free (graphite_bb_p, heap, SCOP_BBS (scop));
1449 BITMAP_FREE (SCOP_BBS_B (scop));
1450 BITMAP_FREE (SCOP_LOOPS (scop));
1451 VEC_free (loop_p, heap, SCOP_LOOP_NEST (scop));
1453 for (i = 0; VEC_iterate (name_tree, SCOP_OLDIVS (scop), i, iv); i++)
1455 VEC_free (name_tree, heap, SCOP_OLDIVS (scop));
1457 for (i = 0; VEC_iterate (name_tree, SCOP_PARAMS (scop), i, p); i++)
1460 VEC_free (name_tree, heap, SCOP_PARAMS (scop));
1461 cloog_program_free (SCOP_PROG (scop));
1462 htab_delete (SCOP_LOOP2CLOOG_LOOP (scop));
1463 htab_delete (SCOP_LIVEOUT_RENAMES (scop));
1464 free_sese (SCOP_REGION (scop));
1468 /* Deletes all scops in SCOPS. */
1471 free_scops (VEC (scop_p, heap) *scops)
1476 for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++)
1479 VEC_free (scop_p, heap, scops);
1482 typedef enum gbb_type {
1484 GBB_LOOP_SING_EXIT_HEADER,
1485 GBB_LOOP_MULT_EXIT_HEADER,
1492 /* Detect the type of BB. Loop headers are only marked, if they are
1493 new. This means their loop_father is different to LAST_LOOP.
1494 Otherwise they are treated like any other bb and their type can be
1498 get_bb_type (basic_block bb, struct loop *last_loop)
1500 VEC (basic_block, heap) *dom;
1502 struct loop *loop = bb->loop_father;
1504 /* Check, if we entry into a new loop. */
1505 if (loop != last_loop)
1507 if (single_exit (loop) != NULL)
1508 return GBB_LOOP_SING_EXIT_HEADER;
1509 else if (loop->num != 0)
1510 return GBB_LOOP_MULT_EXIT_HEADER;
1512 return GBB_COND_HEADER;
1515 dom = get_dominated_by (CDI_DOMINATORS, bb);
1516 nb_dom = VEC_length (basic_block, dom);
1517 VEC_free (basic_block, heap, dom);
1522 nb_suc = VEC_length (edge, bb->succs);
1524 if (nb_dom == 1 && nb_suc == 1)
1527 return GBB_COND_HEADER;
1530 /* A SCoP detection region, defined using bbs as borders.
1531 All control flow touching this region, comes in passing basic_block ENTRY and
1532 leaves passing basic_block EXIT. By using bbs instead of edges for the
1533 borders we are able to represent also regions that do not have a single
1535 But as they have a single entry basic_block and a single exit basic_block, we
1536 are able to generate for every sd_region a single entry and exit edge.
1543 / \ This region contains: {3, 4, 5, 6, 7, 8}
1551 typedef struct sd_region_p
1553 /* The entry bb dominates all bbs in the sd_region. It is part of the
1557 /* The exit bb postdominates all bbs in the sd_region, but is not
1558 part of the region. */
1562 DEF_VEC_O(sd_region);
1563 DEF_VEC_ALLOC_O(sd_region, heap);
1566 /* Moves the scops from SOURCE to TARGET and clean up SOURCE. */
1569 move_sd_regions (VEC (sd_region, heap) **source, VEC (sd_region, heap) **target)
1574 for (i = 0; VEC_iterate (sd_region, *source, i, s); i++)
1575 VEC_safe_push (sd_region, heap, *target, s);
1577 VEC_free (sd_region, heap, *source);
1580 /* Return true when it is not possible to represent the upper bound of
1581 LOOP in the polyhedral representation. */
1584 graphite_cannot_represent_loop_niter (loop_p loop)
1586 tree niter = number_of_latch_executions (loop);
1588 return chrec_contains_undetermined (niter)
1589 || !scev_is_linear_expression (niter);
1591 /* Store information needed by scopdet_* functions. */
1595 /* Where the last open scop would stop if the current BB is harmful. */
1598 /* Where the next scop would start if the current BB is harmful. */
1601 /* The bb or one of its children contains open loop exits. That means
1602 loop exit nodes that are not surrounded by a loop dominated by bb. */
1605 /* The bb or one of its children contains only structures we can handle. */
1610 static struct scopdet_info build_scops_1 (basic_block, VEC (sd_region, heap) **,
1613 /* Calculates BB infos. If bb is difficult we add valid SCoPs dominated by BB
1614 to SCOPS. TYPE is the gbb_type of BB. */
1616 static struct scopdet_info
1617 scopdet_basic_block_info (basic_block bb, VEC (sd_region, heap) **scops,
1620 struct loop *loop = bb->loop_father;
1621 struct scopdet_info result;
1624 /* XXX: ENTRY_BLOCK_PTR could be optimized in later steps. */
1625 stmt = harmful_stmt_in_bb (ENTRY_BLOCK_PTR, bb);
1626 result.difficult = (stmt != NULL);
1633 result.exits = false;
1638 result.next = single_succ (bb);
1639 result.exits = false;
1643 case GBB_LOOP_SING_EXIT_HEADER:
1645 VEC (sd_region, heap) *tmp_scops = VEC_alloc (sd_region, heap,3);
1646 struct scopdet_info sinfo;
1648 sinfo = build_scops_1 (bb, &tmp_scops, loop);
1650 result.last = single_exit (bb->loop_father)->src;
1651 result.next = single_exit (bb->loop_father)->dest;
1653 /* If we do not dominate result.next, remove it. It's either
1654 the EXIT_BLOCK_PTR, or another bb dominates it and will
1655 call the scop detection for this bb. */
1656 if (!dominated_by_p (CDI_DOMINATORS, result.next, bb))
1659 if (result.last->loop_father != loop)
1662 if (graphite_cannot_represent_loop_niter (loop))
1663 result.difficult = true;
1665 if (sinfo.difficult)
1666 move_sd_regions (&tmp_scops, scops);
1668 VEC_free (sd_region, heap, tmp_scops);
1670 result.exits = false;
1671 result.difficult |= sinfo.difficult;
1675 case GBB_LOOP_MULT_EXIT_HEADER:
1677 /* XXX: For now we just do not join loops with multiple exits. If the
1678 exits lead to the same bb it may be possible to join the loop. */
1679 VEC (sd_region, heap) *tmp_scops = VEC_alloc (sd_region, heap, 3);
1680 VEC (edge, heap) *exits = get_loop_exit_edges (loop);
1683 build_scops_1 (bb, &tmp_scops, loop);
1685 /* Scan the code dominated by this loop. This means all bbs, that are
1686 are dominated by a bb in this loop, but are not part of this loop.
1689 - The loop exit destination is dominated by the exit sources.
1691 TODO: We miss here the more complex cases:
1692 - The exit destinations are dominated by another bb inside the
1694 - The loop dominates bbs, that are not exit destinations. */
1695 for (i = 0; VEC_iterate (edge, exits, i, e); i++)
1696 if (e->src->loop_father == loop
1697 && dominated_by_p (CDI_DOMINATORS, e->dest, e->src))
1699 /* Pass loop_outer to recognize e->dest as loop header in
1701 if (e->dest->loop_father->header == e->dest)
1702 build_scops_1 (e->dest, &tmp_scops,
1703 loop_outer (e->dest->loop_father));
1705 build_scops_1 (e->dest, &tmp_scops, e->dest->loop_father);
1710 result.difficult = true;
1711 result.exits = false;
1712 move_sd_regions (&tmp_scops, scops);
1713 VEC_free (edge, heap, exits);
1716 case GBB_COND_HEADER:
1718 VEC (sd_region, heap) *tmp_scops = VEC_alloc (sd_region, heap, 3);
1719 struct scopdet_info sinfo;
1720 VEC (basic_block, heap) *dominated;
1723 basic_block last_bb = NULL;
1725 result.exits = false;
1727 /* First check the successors of BB, and check if it is possible to join
1728 the different branches. */
1729 for (i = 0; VEC_iterate (edge, bb->succs, i, e); i++)
1731 /* Ignore loop exits. They will be handled after the loop body. */
1732 if (is_loop_exit (loop, e->dest))
1734 result.exits = true;
1738 /* Do not follow edges that lead to the end of the
1739 conditions block. For example, in
1749 the edge from 0 => 6. Only check if all paths lead to
1752 if (!single_pred_p (e->dest))
1754 /* Check, if edge leads directly to the end of this
1761 if (e->dest != last_bb)
1762 result.difficult = true;
1767 if (!dominated_by_p (CDI_DOMINATORS, e->dest, bb))
1769 result.difficult = true;
1773 sinfo = build_scops_1 (e->dest, &tmp_scops, loop);
1775 result.exits |= sinfo.exits;
1776 result.last = sinfo.last;
1777 result.difficult |= sinfo.difficult;
1779 /* Checks, if all branches end at the same point.
1780 If that is true, the condition stays joinable.
1781 Have a look at the example above. */
1782 if (sinfo.last && single_succ_p (sinfo.last))
1784 basic_block next_tmp = single_succ (sinfo.last);
1789 if (next_tmp != last_bb)
1790 result.difficult = true;
1793 result.difficult = true;
1796 /* If the condition is joinable. */
1797 if (!result.exits && !result.difficult)
1799 /* Only return a next pointer if we dominate this pointer.
1800 Otherwise it will be handled by the bb dominating it. */
1801 if (dominated_by_p (CDI_DOMINATORS, last_bb, bb) && last_bb != bb)
1802 result.next = last_bb;
1806 VEC_free (sd_region, heap, tmp_scops);
1810 /* Scan remaining bbs dominated by BB. */
1811 dominated = get_dominated_by (CDI_DOMINATORS, bb);
1813 for (i = 0; VEC_iterate (basic_block, dominated, i, dom_bb); i++)
1815 /* Ignore loop exits: they will be handled after the loop body. */
1816 if (loop_depth (find_common_loop (loop, dom_bb->loop_father))
1817 < loop_depth (loop))
1819 result.exits = true;
1823 /* Ignore the bbs processed above. */
1824 if (single_pred_p (dom_bb) && single_pred (dom_bb) == bb)
1827 if (loop_depth (loop) > loop_depth (dom_bb->loop_father))
1828 sinfo = build_scops_1 (dom_bb, &tmp_scops, loop_outer (loop));
1830 sinfo = build_scops_1 (dom_bb, &tmp_scops, loop);
1833 result.exits |= sinfo.exits;
1834 result.difficult = true;
1838 VEC_free (basic_block, heap, dominated);
1841 move_sd_regions (&tmp_scops, scops);
1853 /* Creates the SCoPs and writes entry and exit points for every SCoP. */
1855 static struct scopdet_info
1856 build_scops_1 (basic_block current, VEC (sd_region, heap) **scops, loop_p loop)
1858 bool in_scop = false;
1859 sd_region open_scop;
1860 struct scopdet_info sinfo;
1862 /* Initialize result. */
1863 struct scopdet_info result;
1864 result.exits = false;
1865 result.difficult = false;
1868 open_scop.entry = NULL;
1869 open_scop.exit = NULL;
1872 /* Loop over the dominance tree. If we meet a difficult bb, close
1873 the current SCoP. Loop and condition header start a new layer,
1874 and can only be added if all bbs in deeper layers are simple. */
1875 while (current != NULL)
1877 sinfo = scopdet_basic_block_info (current, scops, get_bb_type (current,
1880 if (!in_scop && !(sinfo.exits || sinfo.difficult))
1882 open_scop.entry = current;
1883 open_scop.exit = NULL;
1886 else if (in_scop && (sinfo.exits || sinfo.difficult))
1888 open_scop.exit = current;
1889 VEC_safe_push (sd_region, heap, *scops, &open_scop);
1893 result.difficult |= sinfo.difficult;
1894 result.exits |= sinfo.exits;
1896 current = sinfo.next;
1899 /* Try to close open_scop, if we are still in an open SCoP. */
1905 for (i = 0; VEC_iterate (edge, sinfo.last->succs, i, e); i++)
1906 if (dominated_by_p (CDI_POST_DOMINATORS, sinfo.last, e->dest))
1907 open_scop.exit = e->dest;
1909 if (!open_scop.exit && open_scop.entry != sinfo.last)
1910 open_scop.exit = sinfo.last;
1913 VEC_safe_push (sd_region, heap, *scops, &open_scop);
1917 result.last = sinfo.last;
1921 /* Checks if a bb is contained in REGION. */
1924 bb_in_sd_region (basic_block bb, sd_region *region)
1926 return dominated_by_p (CDI_DOMINATORS, bb, region->entry)
1927 && !(dominated_by_p (CDI_DOMINATORS, bb, region->exit)
1928 && !dominated_by_p (CDI_DOMINATORS, region->entry,
1932 /* Returns the single entry edge of REGION, if it does not exits NULL. */
1935 find_single_entry_edge (sd_region *region)
1941 FOR_EACH_EDGE (e, ei, region->entry->preds)
1942 if (!bb_in_sd_region (e->src, region))
1957 /* Returns the single exit edge of REGION, if it does not exits NULL. */
1960 find_single_exit_edge (sd_region *region)
1966 FOR_EACH_EDGE (e, ei, region->exit->preds)
1967 if (bb_in_sd_region (e->src, region))
1982 /* Create a single entry edge for REGION. */
1985 create_single_entry_edge (sd_region *region)
1987 if (find_single_entry_edge (region))
1990 /* There are multiple predecessors for bb_3
2003 There are two edges (1->3, 2->3), that point from outside into the region,
2004 and another one (5->3), a loop latch, lead to bb_3.
2012 | |\ (3.0 -> 3.1) = single entry edge
2021 If the loop is part of the SCoP, we have to redirect the loop latches.
2027 | | (3.0 -> 3.1) = entry edge
2036 if (region->entry->loop_father->header != region->entry
2037 || dominated_by_p (CDI_DOMINATORS,
2038 loop_latch_edge (region->entry->loop_father)->src,
2041 edge forwarder = split_block_after_labels (region->entry);
2042 region->entry = forwarder->dest;
2045 /* This case is never executed, as the loop headers seem always to have a
2046 single edge pointing from outside into the loop. */
2049 #ifdef ENABLE_CHECKING
2050 gcc_assert (find_single_entry_edge (region));
2054 /* Check if the sd_region, mentioned in EDGE, has no exit bb. */
2057 sd_region_without_exit (edge e)
2059 sd_region *r = (sd_region *) e->aux;
2062 return r->exit == NULL;
2067 /* Create a single exit edge for REGION. */
2070 create_single_exit_edge (sd_region *region)
2074 edge forwarder = NULL;
2077 if (find_single_exit_edge (region))
2080 /* We create a forwarder bb (5) for all edges leaving this region
2081 (3->5, 4->5). All other edges leading to the same bb, are moved
2082 to a new bb (6). If these edges where part of another region (2->5)
2083 we update the region->exit pointer, of this region.
2085 To identify which edge belongs to which region we depend on the e->aux
2086 pointer in every edge. It points to the region of the edge or to NULL,
2087 if the edge is not part of any region.
2089 1 2 3 4 1->5 no region, 2->5 region->exit = 5,
2090 \| |/ 3->5 region->exit = NULL, 4->5 region->exit = NULL
2095 1 2 3 4 1->6 no region, 2->6 region->exit = 6,
2096 | | \/ 3->5 no region, 4->5 no region,
2098 \| / 5->6 region->exit = 6
2101 Now there is only a single exit edge (5->6). */
2102 exit = region->exit;
2103 region->exit = NULL;
2104 forwarder = make_forwarder_block (exit, &sd_region_without_exit, NULL);
2106 /* Unmark the edges, that are no longer exit edges. */
2107 FOR_EACH_EDGE (e, ei, forwarder->src->preds)
2111 /* Mark the new exit edge. */
2112 single_succ_edge (forwarder->src)->aux = region;
2114 /* Update the exit bb of all regions, where exit edges lead to
2116 FOR_EACH_EDGE (e, ei, forwarder->dest->preds)
2118 ((sd_region *) e->aux)->exit = forwarder->dest;
2120 #ifdef ENABLE_CHECKING
2121 gcc_assert (find_single_exit_edge (region));
2125 /* Unmark the exit edges of all REGIONS.
2126 See comment in "create_single_exit_edge". */
2129 unmark_exit_edges (VEC (sd_region, heap) *regions)
2136 for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
2137 FOR_EACH_EDGE (e, ei, s->exit->preds)
2142 /* Mark the exit edges of all REGIONS.
2143 See comment in "create_single_exit_edge". */
2146 mark_exit_edges (VEC (sd_region, heap) *regions)
2153 for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
2154 FOR_EACH_EDGE (e, ei, s->exit->preds)
2155 if (bb_in_sd_region (e->src, s))
2159 /* Free and compute again all the dominators information. */
2162 recompute_all_dominators (void)
2164 mark_irreducible_loops ();
2165 free_dominance_info (CDI_DOMINATORS);
2166 free_dominance_info (CDI_POST_DOMINATORS);
2167 calculate_dominance_info (CDI_DOMINATORS);
2168 calculate_dominance_info (CDI_POST_DOMINATORS);
2171 /* Verifies properties that GRAPHITE should maintain during translation. */
2174 graphite_verify (void)
2176 #ifdef ENABLE_CHECKING
2177 verify_loop_structure ();
2178 verify_dominators (CDI_DOMINATORS);
2179 verify_dominators (CDI_POST_DOMINATORS);
2184 /* Create for all scop regions a single entry and a single exit edge. */
2187 create_sese_edges (VEC (sd_region, heap) *regions)
2192 for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
2193 create_single_entry_edge (s);
2195 mark_exit_edges (regions);
2197 for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
2198 create_single_exit_edge (s);
2200 unmark_exit_edges (regions);
2202 fix_loop_structure (NULL);
2204 #ifdef ENABLE_CHECKING
2205 verify_loop_structure ();
2206 verify_dominators (CDI_DOMINATORS);
2211 /* Create graphite SCoPs from an array of scop detection regions. */
2214 build_graphite_scops (VEC (sd_region, heap) *scop_regions)
2219 for (i = 0; VEC_iterate (sd_region, scop_regions, i, s); i++)
2221 edge entry = find_single_entry_edge (s);
2222 edge exit = find_single_exit_edge (s);
2223 scop_p scop = new_scop (entry, exit);
2224 VEC_safe_push (scop_p, heap, current_scops, scop);
2226 /* Are there overlapping SCoPs? */
2227 #ifdef ENABLE_CHECKING
2232 for (j = 0; VEC_iterate (sd_region, scop_regions, j, s2); j++)
2234 gcc_assert (!bb_in_sd_region (s->entry, s2));
2240 /* Find static control parts. */
2245 struct loop *loop = current_loops->tree_root;
2246 VEC (sd_region, heap) *tmp_scops = VEC_alloc (sd_region, heap, 3);
2248 build_scops_1 (single_succ (ENTRY_BLOCK_PTR), &tmp_scops, loop);
2249 create_sese_edges (tmp_scops);
2250 build_graphite_scops (tmp_scops);
2251 VEC_free (sd_region, heap, tmp_scops);
2254 /* Gather the basic blocks belonging to the SCOP. */
2257 build_scop_bbs (scop_p scop)
2259 basic_block *stack = XNEWVEC (basic_block, n_basic_blocks + 1);
2260 sbitmap visited = sbitmap_alloc (last_basic_block);
2263 sbitmap_zero (visited);
2264 stack[sp++] = SCOP_ENTRY (scop);
2268 basic_block bb = stack[--sp];
2269 int depth = loop_depth (bb->loop_father);
2270 int num = bb->loop_father->num;
2274 /* Scop's exit is not in the scop. Exclude also bbs, which are
2275 dominated by the SCoP exit. These are e.g. loop latches. */
2276 if (TEST_BIT (visited, bb->index)
2277 || dominated_by_p (CDI_DOMINATORS, bb, SCOP_EXIT (scop))
2278 /* Every block in the scop is dominated by scop's entry. */
2279 || !dominated_by_p (CDI_DOMINATORS, bb, SCOP_ENTRY (scop)))
2282 new_graphite_bb (scop, bb);
2283 SET_BIT (visited, bb->index);
2285 /* First push the blocks that have to be processed last. Note
2286 that this means that the order in which the code is organized
2287 below is important: do not reorder the following code. */
2288 FOR_EACH_EDGE (e, ei, bb->succs)
2289 if (! TEST_BIT (visited, e->dest->index)
2290 && (int) loop_depth (e->dest->loop_father) < depth)
2291 stack[sp++] = e->dest;
2293 FOR_EACH_EDGE (e, ei, bb->succs)
2294 if (! TEST_BIT (visited, e->dest->index)
2295 && (int) loop_depth (e->dest->loop_father) == depth
2296 && e->dest->loop_father->num != num)
2297 stack[sp++] = e->dest;
2299 FOR_EACH_EDGE (e, ei, bb->succs)
2300 if (! TEST_BIT (visited, e->dest->index)
2301 && (int) loop_depth (e->dest->loop_father) == depth
2302 && e->dest->loop_father->num == num
2303 && EDGE_COUNT (e->dest->preds) > 1)
2304 stack[sp++] = e->dest;
2306 FOR_EACH_EDGE (e, ei, bb->succs)
2307 if (! TEST_BIT (visited, e->dest->index)
2308 && (int) loop_depth (e->dest->loop_father) == depth
2309 && e->dest->loop_father->num == num
2310 && EDGE_COUNT (e->dest->preds) == 1)
2311 stack[sp++] = e->dest;
2313 FOR_EACH_EDGE (e, ei, bb->succs)
2314 if (! TEST_BIT (visited, e->dest->index)
2315 && (int) loop_depth (e->dest->loop_father) > depth)
2316 stack[sp++] = e->dest;
2320 sbitmap_free (visited);
2323 /* Returns the number of reduction phi nodes in LOOP. */
2326 nb_reductions_in_loop (loop_p loop)
2329 gimple_stmt_iterator gsi;
2331 for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
2333 gimple phi = gsi_stmt (gsi);
2337 if (!is_gimple_reg (PHI_RESULT (phi)))
2340 scev = analyze_scalar_evolution (loop, PHI_RESULT (phi));
2341 scev = instantiate_parameters (loop, scev);
2342 if (!simple_iv (loop, phi, PHI_RESULT (phi), &iv, true))
2349 /* A LOOP is in normal form when it contains only one scalar phi node
2350 that defines the main induction variable of the loop, only one
2351 increment of the IV, and only one exit condition. */
2354 graphite_loop_normal_form (loop_p loop)
2356 struct tree_niter_desc niter;
2359 edge exit = single_dom_exit (loop);
2361 gcc_assert (number_of_iterations_exit (loop, exit, &niter, false));
2362 nit = force_gimple_operand (unshare_expr (niter.niter), &stmts, true,
2365 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
2367 /* One IV per loop. */
2368 if (nb_reductions_in_loop (loop) > 0)
2371 return canonicalize_loop_ivs (loop, NULL, nit);
2374 /* Record LOOP as occuring in SCOP. Returns true when the operation
2378 scop_record_loop (scop_p scop, loop_p loop)
2383 if (bitmap_bit_p (SCOP_LOOPS (scop), loop->num))
2386 bitmap_set_bit (SCOP_LOOPS (scop), loop->num);
2387 VEC_safe_push (loop_p, heap, SCOP_LOOP_NEST (scop), loop);
2389 induction_var = graphite_loop_normal_form (loop);
2393 oldiv = XNEW (struct name_tree);
2394 oldiv->t = induction_var;
2395 oldiv->name = get_name (SSA_NAME_VAR (oldiv->t));
2397 VEC_safe_push (name_tree, heap, SCOP_OLDIVS (scop), oldiv);
2401 /* Build the loop nests contained in SCOP. Returns true when the
2402 operation was successful. */
2405 build_scop_loop_nests (scop_p scop)
2409 struct loop *loop0, *loop1;
2412 if (bb_in_scop_p (bb, scop))
2414 struct loop *loop = bb->loop_father;
2416 /* Only add loops if they are completely contained in the SCoP. */
2417 if (loop->header == bb
2418 && bb_in_scop_p (loop->latch, scop))
2420 if (!scop_record_loop (scop, loop))
2425 /* Make sure that the loops in the SCOP_LOOP_NEST are ordered. It
2426 can be the case that an inner loop is inserted before an outer
2427 loop. To avoid this, semi-sort once. */
2428 for (i = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), i, loop0); i++)
2430 if (VEC_length (loop_p, SCOP_LOOP_NEST (scop)) == i + 1)
2433 loop1 = VEC_index (loop_p, SCOP_LOOP_NEST (scop), i + 1);
2434 if (loop0->num > loop1->num)
2436 VEC_replace (loop_p, SCOP_LOOP_NEST (scop), i, loop1);
2437 VEC_replace (loop_p, SCOP_LOOP_NEST (scop), i + 1, loop0);
2444 /* Build dynamic schedules for all the BBs. */
2447 build_scop_dynamic_schedules (scop_p scop)
2449 int i, dim, loop_num, row, col;
2452 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
2454 loop_num = GBB_BB (gb)->loop_father->num;
2458 dim = nb_loops_around_gb (gb);
2459 GBB_DYNAMIC_SCHEDULE (gb) = cloog_matrix_alloc (dim, dim);
2461 for (row = 0; row < GBB_DYNAMIC_SCHEDULE (gb)->NbRows; row++)
2462 for (col = 0; col < GBB_DYNAMIC_SCHEDULE (gb)->NbColumns; col++)
2464 value_set_si (GBB_DYNAMIC_SCHEDULE (gb)->p[row][col], 1);
2466 value_set_si (GBB_DYNAMIC_SCHEDULE (gb)->p[row][col], 0);
2469 GBB_DYNAMIC_SCHEDULE (gb) = NULL;
2473 /* Returns the number of loops that are identical at the beginning of
2474 the vectors A and B. */
2477 compare_prefix_loops (VEC (loop_p, heap) *a, VEC (loop_p, heap) *b)
2486 lb = VEC_length (loop_p, b);
2488 for (i = 0; VEC_iterate (loop_p, a, i, ea); i++)
2490 || ea != VEC_index (loop_p, b, i))
2496 /* Build for BB the static schedule.
2498 The STATIC_SCHEDULE is defined like this:
2517 Static schedules for A to F:
2530 build_scop_canonical_schedules (scop_p scop)
2534 int nb_loops = scop_nb_loops (scop);
2535 lambda_vector static_schedule = lambda_vector_new (nb_loops + 1);
2536 VEC (loop_p, heap) *loops_previous = NULL;
2538 /* We have to start schedules at 0 on the first component and
2539 because we cannot compare_prefix_loops against a previous loop,
2540 prefix will be equal to zero, and that index will be
2541 incremented before copying. */
2542 static_schedule[0] = -1;
2544 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
2546 int prefix = compare_prefix_loops (loops_previous, GBB_LOOPS (gb));
2547 int nb = gbb_nb_loops (gb);
2549 loops_previous = GBB_LOOPS (gb);
2550 memset (&(static_schedule[prefix + 1]), 0, sizeof (int) * (nb_loops - prefix));
2551 ++static_schedule[prefix];
2552 GBB_STATIC_SCHEDULE (gb) = lambda_vector_new (nb + 1);
2553 lambda_vector_copy (static_schedule,
2554 GBB_STATIC_SCHEDULE (gb), nb + 1);
2558 /* Build the LOOPS vector for all bbs in SCOP. */
2561 build_bb_loops (scop_p scop)
2566 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
2571 depth = nb_loops_around_gb (gb) - 1;
2573 GBB_LOOPS (gb) = VEC_alloc (loop_p, heap, 3);
2574 VEC_safe_grow_cleared (loop_p, heap, GBB_LOOPS (gb), depth + 1);
2576 loop = GBB_BB (gb)->loop_father;
2578 while (scop_contains_loop (scop, loop))
2580 VEC_replace (loop_p, GBB_LOOPS (gb), depth, loop);
2581 loop = loop_outer (loop);
2587 /* Get the index for parameter VAR in SCOP. */
2590 param_index (tree var, scop_p scop)
2596 gcc_assert (TREE_CODE (var) == SSA_NAME);
2598 for (i = 0; VEC_iterate (name_tree, SCOP_PARAMS (scop), i, p); i++)
2602 gcc_assert (SCOP_ADD_PARAMS (scop));
2604 nvar = XNEW (struct name_tree);
2607 VEC_safe_push (name_tree, heap, SCOP_PARAMS (scop), nvar);
2608 return VEC_length (name_tree, SCOP_PARAMS (scop)) - 1;
2611 /* Scan EXPR and translate it to an inequality vector INEQ that will
2612 be added, or subtracted, in the constraint domain matrix C at row
2613 R. K is the number of columns for loop iterators in C. */
2616 scan_tree_for_params (scop_p s, tree e, CloogMatrix *c, int r, Value k,
2619 int cst_col, param_col;
2621 if (e == chrec_dont_know)
2624 switch (TREE_CODE (e))
2626 case POLYNOMIAL_CHREC:
2628 tree left = CHREC_LEFT (e);
2629 tree right = CHREC_RIGHT (e);
2630 int var = CHREC_VARIABLE (e);
2632 if (TREE_CODE (right) != INTEGER_CST)
2637 int loop_col = scop_gimple_loop_depth (s, get_loop (var)) + 1;
2640 value_sub_int (c->p[r][loop_col], c->p[r][loop_col],
2641 int_cst_value (right));
2643 value_add_int (c->p[r][loop_col], c->p[r][loop_col],
2644 int_cst_value (right));
2647 switch (TREE_CODE (left))
2649 case POLYNOMIAL_CHREC:
2650 scan_tree_for_params (s, left, c, r, k, subtract);
2654 /* Constant part. */
2657 int v = int_cst_value (left);
2658 cst_col = c->NbColumns - 1;
2663 subtract = subtract ? false : true;
2667 value_sub_int (c->p[r][cst_col], c->p[r][cst_col], v);
2669 value_add_int (c->p[r][cst_col], c->p[r][cst_col], v);
2674 scan_tree_for_params (s, left, c, r, k, subtract);
2681 if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
2686 gcc_assert (host_integerp (TREE_OPERAND (e, 1), 0));
2688 value_set_si (val, int_cst_value (TREE_OPERAND (e, 1)));
2689 value_multiply (k, k, val);
2692 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
2699 gcc_assert (host_integerp (TREE_OPERAND (e, 0), 0));
2701 value_set_si (val, int_cst_value (TREE_OPERAND (e, 0)));
2702 value_multiply (k, k, val);
2705 scan_tree_for_params (s, TREE_OPERAND (e, 1), c, r, k, subtract);
2710 case POINTER_PLUS_EXPR:
2711 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
2712 scan_tree_for_params (s, TREE_OPERAND (e, 1), c, r, k, subtract);
2716 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
2717 scan_tree_for_params (s, TREE_OPERAND (e, 1), c, r, k, !subtract);
2721 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, !subtract);
2725 param_col = param_index (e, s);
2729 param_col += c->NbColumns - scop_nb_params (s) - 1;
2732 value_subtract (c->p[r][param_col], c->p[r][param_col], k);
2734 value_addto (c->p[r][param_col], c->p[r][param_col], k);
2741 int v = int_cst_value (e);
2742 cst_col = c->NbColumns - 1;
2747 subtract = subtract ? false : true;
2751 value_sub_int (c->p[r][cst_col], c->p[r][cst_col], v);
2753 value_add_int (c->p[r][cst_col], c->p[r][cst_col], v);
2758 case NON_LVALUE_EXPR:
2759 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
2768 /* Data structure for idx_record_params. */
2776 /* For a data reference with an ARRAY_REF as its BASE, record the
2777 parameters occurring in IDX. DTA is passed in as complementary
2778 information, and is used by the automatic walker function. This
2779 function is a callback for for_each_index. */
2782 idx_record_params (tree base, tree *idx, void *dta)
2784 struct irp_data *data = (struct irp_data *) dta;
2786 if (TREE_CODE (base) != ARRAY_REF)
2789 if (TREE_CODE (*idx) == SSA_NAME)
2792 scop_p scop = data->scop;
2793 struct loop *loop = data->loop;
2796 scev = analyze_scalar_evolution (loop, *idx);
2797 scev = instantiate_scev (block_before_scop (scop), loop, scev);
2800 value_set_si (one, 1);
2801 scan_tree_for_params (scop, scev, NULL, 0, one, false);
2808 /* Find parameters with respect to SCOP in BB. We are looking in memory
2809 access functions, conditions and loop bounds. */
2812 find_params_in_bb (scop_p scop, graphite_bb_p gb)
2815 data_reference_p dr;
2817 loop_p father = GBB_BB (gb)->loop_father;
2819 for (i = 0; VEC_iterate (data_reference_p, GBB_DATA_REFS (gb), i, dr); i++)
2821 struct irp_data irp;
2825 for_each_index (&dr->ref, idx_record_params, &irp);
2828 /* Find parameters in conditional statements. */
2829 for (i = 0; VEC_iterate (gimple, GBB_CONDITIONS (gb), i, stmt); i++)
2832 loop_p loop = father;
2836 lhs = gimple_cond_lhs (stmt);
2837 lhs = analyze_scalar_evolution (loop, lhs);
2838 lhs = instantiate_scev (block_before_scop (scop), loop, lhs);
2840 rhs = gimple_cond_rhs (stmt);
2841 rhs = analyze_scalar_evolution (loop, rhs);
2842 rhs = instantiate_scev (block_before_scop (scop), loop, rhs);
2845 scan_tree_for_params (scop, lhs, NULL, 0, one, false);
2846 value_set_si (one, 1);
2847 scan_tree_for_params (scop, rhs, NULL, 0, one, false);
2852 /* Saves in NV the name of variable P->T. */
2855 save_var_name (char **nv, int i, name_tree p)
2857 const char *name = get_name (SSA_NAME_VAR (p->t));
2861 int len = strlen (name) + 16;
2862 nv[i] = XNEWVEC (char, len);
2863 snprintf (nv[i], len, "%s_%d", name, SSA_NAME_VERSION (p->t));
2867 nv[i] = XNEWVEC (char, 16);
2868 snprintf (nv[i], 2 + 16, "T_%d", SSA_NAME_VERSION (p->t));
2874 /* Return the maximal loop depth in SCOP. */
2877 scop_max_loop_depth (scop_p scop)
2881 int max_nb_loops = 0;
2883 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gbb); i++)
2885 int nb_loops = gbb_nb_loops (gbb);
2886 if (max_nb_loops < nb_loops)
2887 max_nb_loops = nb_loops;
2890 return max_nb_loops;
2893 /* Initialize Cloog's parameter names from the names used in GIMPLE.
2894 Initialize Cloog's iterator names, using 'graphite_iterator_%d'
2895 from 0 to scop_nb_loops (scop). */
2898 initialize_cloog_names (scop_p scop)
2900 int i, nb_params = VEC_length (name_tree, SCOP_PARAMS (scop));
2901 char **params = XNEWVEC (char *, nb_params);
2902 int nb_iterators = scop_max_loop_depth (scop);
2903 int nb_scattering= cloog_program_nb_scattdims (SCOP_PROG (scop));
2904 char **iterators = XNEWVEC (char *, nb_iterators * 2);
2905 char **scattering = XNEWVEC (char *, nb_scattering);
2908 for (i = 0; VEC_iterate (name_tree, SCOP_PARAMS (scop), i, p); i++)
2909 save_var_name (params, i, p);
2911 cloog_names_set_nb_parameters (cloog_program_names (SCOP_PROG (scop)),
2913 cloog_names_set_parameters (cloog_program_names (SCOP_PROG (scop)),
2916 for (i = 0; i < nb_iterators; i++)
2919 iterators[i] = XNEWVEC (char, len);
2920 snprintf (iterators[i], len, "graphite_iterator_%d", i);
2923 cloog_names_set_nb_iterators (cloog_program_names (SCOP_PROG (scop)),
2925 cloog_names_set_iterators (cloog_program_names (SCOP_PROG (scop)),
2928 for (i = 0; i < nb_scattering; i++)
2931 scattering[i] = XNEWVEC (char, len);
2932 snprintf (scattering[i], len, "s_%d", i);
2935 cloog_names_set_nb_scattering (cloog_program_names (SCOP_PROG (scop)),
2937 cloog_names_set_scattering (cloog_program_names (SCOP_PROG (scop)),
2941 /* Record the parameters used in the SCOP. A variable is a parameter
2942 in a scop if it does not vary during the execution of that scop. */
2945 find_scop_parameters (scop_p scop)
2953 value_set_si (one, 1);
2955 /* Find the parameters used in the loop bounds. */
2956 for (i = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), i, loop); i++)
2958 tree nb_iters = number_of_latch_executions (loop);
2960 if (!chrec_contains_symbols (nb_iters))
2963 nb_iters = analyze_scalar_evolution (loop, nb_iters);
2964 nb_iters = instantiate_scev (block_before_scop (scop), loop, nb_iters);
2965 scan_tree_for_params (scop, nb_iters, NULL, 0, one, false);
2970 /* Find the parameters used in data accesses. */
2971 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
2972 find_params_in_bb (scop, gb);
2974 SCOP_ADD_PARAMS (scop) = false;
2977 /* Build the context constraints for SCOP: constraints and relations
2981 build_scop_context (scop_p scop)
2983 int nb_params = scop_nb_params (scop);
2984 CloogMatrix *matrix = cloog_matrix_alloc (1, nb_params + 2);
2986 /* Insert '0 >= 0' in the context matrix, as it is not allowed to be
2989 value_set_si (matrix->p[0][0], 1);
2991 value_set_si (matrix->p[0][nb_params + 1], 0);
2993 cloog_program_set_context (SCOP_PROG (scop),
2994 cloog_domain_matrix2domain (matrix));
2995 cloog_matrix_free (matrix);
2998 /* Returns a graphite_bb from BB. */
3000 static inline graphite_bb_p
3001 gbb_from_bb (basic_block bb)
3003 return (graphite_bb_p) bb->aux;
3006 /* Builds the constraint matrix for LOOP in SCOP. NB_OUTER_LOOPS is the
3007 number of loops surrounding LOOP in SCOP. OUTER_CSTR gives the
3008 constraints matrix for the surrounding loops. */
3011 build_loop_iteration_domains (scop_p scop, struct loop *loop,
3012 CloogMatrix *outer_cstr, int nb_outer_loops)
3018 int nb_rows = outer_cstr->NbRows + 1;
3019 int nb_cols = outer_cstr->NbColumns + 1;
3021 /* Last column of CSTR is the column of constants. */
3022 int cst_col = nb_cols - 1;
3024 /* The column for the current loop is just after the columns of
3025 other outer loops. */
3026 int loop_col = nb_outer_loops + 1;
3028 tree nb_iters = number_of_latch_executions (loop);
3030 /* When the number of iterations is a constant or a parameter, we
3031 add a constraint for the upper bound of the loop. So add a row
3032 to the constraint matrix before allocating it. */
3033 if (TREE_CODE (nb_iters) == INTEGER_CST
3034 || !chrec_contains_undetermined (nb_iters))
3037 cstr = cloog_matrix_alloc (nb_rows, nb_cols);
3039 /* Copy the outer constraints. */
3040 for (i = 0; i < outer_cstr->NbRows; i++)
3042 /* Copy the eq/ineq and loops columns. */
3043 for (j = 0; j < loop_col; j++)
3044 value_assign (cstr->p[i][j], outer_cstr->p[i][j]);
3046 /* Leave an empty column in CSTR for the current loop, and then
3047 copy the parameter columns. */
3048 for (j = loop_col; j < outer_cstr->NbColumns; j++)
3049 value_assign (cstr->p[i][j + 1], outer_cstr->p[i][j]);
3053 row = outer_cstr->NbRows;
3054 value_set_si (cstr->p[row][0], 1);
3055 value_set_si (cstr->p[row][loop_col], 1);
3057 /* loop_i <= nb_iters */
3058 if (TREE_CODE (nb_iters) == INTEGER_CST)
3061 value_set_si (cstr->p[row][0], 1);
3062 value_set_si (cstr->p[row][loop_col], -1);
3064 value_set_si (cstr->p[row][cst_col],
3065 int_cst_value (nb_iters));
3067 else if (!chrec_contains_undetermined (nb_iters))
3069 /* Otherwise nb_iters contains parameters: scan the nb_iters
3070 expression and build its matrix representation. */
3074 value_set_si (cstr->p[row][0], 1);
3075 value_set_si (cstr->p[row][loop_col], -1);
3077 nb_iters = analyze_scalar_evolution (loop, nb_iters);
3078 nb_iters = instantiate_scev (block_before_scop (scop), loop, nb_iters);
3081 value_set_si (one, 1);
3082 scan_tree_for_params (scop, nb_iters, cstr, row, one, false);
3088 if (loop->inner && loop_in_scop_p (loop->inner, scop))
3089 build_loop_iteration_domains (scop, loop->inner, cstr, nb_outer_loops + 1);
3091 /* Only go to the next loops, if we are not at the outermost layer. These
3092 have to be handled seperately, as we can be sure, that the chain at this
3093 layer will be connected. */
3094 if (nb_outer_loops != 0 && loop->next && loop_in_scop_p (loop->next, scop))
3095 build_loop_iteration_domains (scop, loop->next, outer_cstr, nb_outer_loops);
3097 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
3098 if (gbb_loop (gb) == loop)
3099 GBB_DOMAIN (gb) = cloog_matrix_copy (cstr);
3101 cloog_matrix_free (cstr);
3104 /* Add conditions to the domain of GB. */
3107 add_conditions_to_domain (graphite_bb_p gb)
3111 VEC (gimple, heap) *conditions = GBB_CONDITIONS (gb);
3112 CloogMatrix *domain = GBB_DOMAIN (gb);
3113 scop_p scop = GBB_SCOP (gb);
3117 unsigned nb_new_rows = 0;
3120 if (VEC_empty (gimple, conditions))
3125 nb_rows = domain->NbRows;
3126 nb_cols = domain->NbColumns;
3131 nb_cols = nb_loops_around_gb (gb) + scop_nb_params (scop) + 2;
3134 /* Count number of necessary new rows to add the conditions to the
3136 for (i = 0; VEC_iterate (gimple, conditions, i, stmt); i++)
3138 switch (gimple_code (stmt))
3142 enum tree_code code = gimple_cond_code (stmt);
3148 /* NE and EQ statements are not supported right know. */
3164 /* Switch statements are not supported right know. */
3175 /* Enlarge the matrix. */
3177 CloogMatrix *new_domain;
3178 new_domain = cloog_matrix_alloc (nb_rows + nb_new_rows, nb_cols);
3182 for (i = 0; i < nb_rows; i++)
3183 for (j = 0; j < nb_cols; j++)
3184 value_assign (new_domain->p[i][j], domain->p[i][j]);
3186 cloog_matrix_free (domain);
3189 domain = new_domain;
3190 GBB_DOMAIN (gb) = new_domain;
3193 /* Add the conditions to the new enlarged domain matrix. */
3195 for (i = 0; VEC_iterate (gimple, conditions, i, stmt); i++)
3197 switch (gimple_code (stmt))
3202 enum tree_code code;
3205 loop_p loop = GBB_BB (gb)->loop_father;
3207 left = gimple_cond_lhs (stmt);
3208 right = gimple_cond_rhs (stmt);
3210 left = analyze_scalar_evolution (loop, left);
3211 right = analyze_scalar_evolution (loop, right);
3213 left = instantiate_scev (block_before_scop (scop), loop, left);
3214 right = instantiate_scev (block_before_scop (scop), loop, right);
3216 code = gimple_cond_code (stmt);
3218 /* The conditions for ELSE-branches are inverted. */
3219 if (VEC_index (gimple, gb->condition_cases, i) == NULL)
3220 code = invert_tree_comparison (code, false);
3225 /* NE statements are not supported right know. */
3229 value_set_si (domain->p[row][0], 1);
3231 value_set_si (one, 1);
3232 scan_tree_for_params (scop, left, domain, row, one, true);
3233 value_set_si (one, 1);
3234 scan_tree_for_params (scop, right, domain, row, one, false);
3236 value_set_si (domain->p[row][0], 1);
3237 value_set_si (one, 1);
3238 scan_tree_for_params (scop, left, domain, row, one, false);
3239 value_set_si (one, 1);
3240 scan_tree_for_params (scop, right, domain, row, one, true);
3245 value_set_si (domain->p[row][0], 1);
3247 value_set_si (one, 1);
3248 scan_tree_for_params (scop, left, domain, row, one, true);
3249 value_set_si (one, 1);
3250 scan_tree_for_params (scop, right, domain, row, one, false);
3251 value_sub_int (domain->p[row][nb_cols - 1],
3252 domain->p[row][nb_cols - 1], 1);
3257 value_set_si (domain->p[row][0], 1);
3259 value_set_si (one, 1);
3260 scan_tree_for_params (scop, left, domain, row, one, false);
3261 value_set_si (one, 1);
3262 scan_tree_for_params (scop, right, domain, row, one, true);
3263 value_sub_int (domain->p[row][nb_cols - 1],
3264 domain->p[row][nb_cols - 1], 1);
3269 value_set_si (domain->p[row][0], 1);
3271 value_set_si (one, 1);
3272 scan_tree_for_params (scop, left, domain, row, one, true);
3273 value_set_si (one, 1);
3274 scan_tree_for_params (scop, right, domain, row, one, false);
3279 value_set_si (domain->p[row][0], 1);
3281 value_set_si (one, 1);
3282 scan_tree_for_params (scop, left, domain, row, one, false);
3283 value_set_si (one, 1);
3284 scan_tree_for_params (scop, right, domain, row, one, true);
3295 /* Switch statements are not supported right know. */
3306 /* Returns true when PHI defines an induction variable in the loop
3307 containing the PHI node. */
3310 phi_node_is_iv (gimple phi)
3312 loop_p loop = gimple_bb (phi)->loop_father;
3313 tree scev = analyze_scalar_evolution (loop, gimple_phi_result (phi));
3315 return tree_contains_chrecs (scev, NULL);
3318 /* Returns true when BB contains scalar phi nodes that are not an
3319 induction variable of a loop. */
3322 bb_contains_non_iv_scalar_phi_nodes (basic_block bb)
3325 gimple_stmt_iterator si;
3327 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
3328 if (is_gimple_reg (gimple_phi_result (gsi_stmt (si))))
3330 /* Store the unique scalar PHI node: at this point, loops
3331 should be in cannonical form, so we expect to see at most
3332 one scalar phi node in the loop header. */
3334 || bb != bb->loop_father->header)
3337 phi = gsi_stmt (si);
3341 || phi_node_is_iv (phi))
3347 /* Helper recursive function. Record in CONDITIONS and CASES all
3348 conditions from 'if's and 'switch'es occurring in BB from SCOP.
3350 Returns false when the conditions contain scalar computations that
3351 depend on the condition, i.e. when there are scalar phi nodes on
3352 the junction after the condition. Only the computations occurring
3353 on memory can be handled in the polyhedral model: operations that
3354 define scalar evolutions in conditions, that can potentially be
3355 used to index memory, can't be handled by the polyhedral model. */
3358 build_scop_conditions_1 (VEC (gimple, heap) **conditions,
3359 VEC (gimple, heap) **cases, basic_block bb,
3365 gimple_stmt_iterator gsi;
3366 basic_block bb_child, bb_iter;
3367 VEC (basic_block, heap) *dom;
3369 /* Make sure we are in the SCoP. */
3370 if (!bb_in_scop_p (bb, scop))
3373 if (bb_contains_non_iv_scalar_phi_nodes (bb))
3376 gbb = gbb_from_bb (bb);
3379 GBB_CONDITIONS (gbb) = VEC_copy (gimple, heap, *conditions);
3380 GBB_CONDITION_CASES (gbb) = VEC_copy (gimple, heap, *cases);
3383 dom = get_dominated_by (CDI_DOMINATORS, bb);
3385 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3387 gimple stmt = gsi_stmt (gsi);
3388 VEC (edge, gc) *edges;
3391 switch (gimple_code (stmt))
3395 for (i = 0; VEC_iterate (edge, edges, i, e); i++)
3396 if ((dominated_by_p (CDI_DOMINATORS, e->dest, bb))
3397 && VEC_length (edge, e->dest->preds) == 1)
3399 /* Remove the scanned block from the dominator successors. */
3400 for (j = 0; VEC_iterate (basic_block, dom, j, bb_iter); j++)
3401 if (bb_iter == e->dest)
3403 VEC_unordered_remove (basic_block, dom, j);
3407 /* Recursively scan the then or else part. */
3408 if (e->flags & EDGE_TRUE_VALUE)
3409 VEC_safe_push (gimple, heap, *cases, stmt);
3412 gcc_assert (e->flags & EDGE_FALSE_VALUE);
3413 VEC_safe_push (gimple, heap, *cases, NULL);
3416 VEC_safe_push (gimple, heap, *conditions, stmt);
3417 if (!build_scop_conditions_1 (conditions, cases, e->dest, scop))
3422 VEC_pop (gimple, *conditions);
3423 VEC_pop (gimple, *cases);
3430 gimple_stmt_iterator gsi_search_gimple_label;
3432 for (i = 0; i < gimple_switch_num_labels (stmt); ++i)
3434 basic_block bb_iter;
3436 size_t n_cases = VEC_length (gimple, *conditions);
3437 unsigned n = gimple_switch_num_labels (stmt);
3439 bb_child = label_to_block
3440 (CASE_LABEL (gimple_switch_label (stmt, i)));
3442 for (k = 0; k < n; k++)
3445 (CASE_LABEL (gimple_switch_label (stmt, k))) == bb_child)
3448 /* Switches with multiple case values for the same
3449 block are not handled. */
3451 /* Switch cases with more than one predecessor are
3453 || VEC_length (edge, bb_child->preds) != 1)
3459 /* Recursively scan the corresponding 'case' block. */
3460 for (gsi_search_gimple_label = gsi_start_bb (bb_child);
3461 !gsi_end_p (gsi_search_gimple_label);
3462 gsi_next (&gsi_search_gimple_label))
3464 gimple label = gsi_stmt (gsi_search_gimple_label);
3466 if (gimple_code (label) == GIMPLE_LABEL)
3468 tree t = gimple_label_label (label);
3470 gcc_assert (t == gimple_switch_label (stmt, i));
3471 VEC_replace (gimple, *cases, n_cases, label);
3476 if (!build_scop_conditions_1 (conditions, cases, bb_child, scop))
3482 /* Remove the scanned block from the dominator successors. */
3483 for (j = 0; VEC_iterate (basic_block, dom, j, bb_iter); j++)
3484 if (bb_iter == bb_child)
3486 VEC_unordered_remove (basic_block, dom, j);
3491 VEC_pop (gimple, *conditions);
3492 VEC_pop (gimple, *cases);
3501 /* Scan all immediate dominated successors. */
3502 for (i = 0; VEC_iterate (basic_block, dom, i, bb_child); i++)
3503 if (!build_scop_conditions_1 (conditions, cases, bb_child, scop))
3510 VEC_free (basic_block, heap, dom);
3514 /* Record all conditions from SCOP.
3516 Returns false when the conditions contain scalar computations that
3517 depend on the condition, i.e. when there are scalar phi nodes on
3518 the junction after the condition. Only the computations occurring
3519 on memory can be handled in the polyhedral model: operations that
3520 define scalar evolutions in conditions, that can potentially be
3521 used to index memory, can't be handled by the polyhedral model. */
3524 build_scop_conditions (scop_p scop)
3527 VEC (gimple, heap) *conditions = NULL;
3528 VEC (gimple, heap) *cases = NULL;
3530 res = build_scop_conditions_1 (&conditions, &cases, SCOP_ENTRY (scop), scop);
3532 VEC_free (gimple, heap, conditions);
3533 VEC_free (gimple, heap, cases);
3537 /* Traverses all the GBBs of the SCOP and add their constraints to the
3538 iteration domains. */
3541 add_conditions_to_constraints (scop_p scop)
3546 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gbb); i++)
3547 add_conditions_to_domain (gbb);
3550 /* Build the current domain matrix: the loops belonging to the current
3551 SCOP, and that vary for the execution of the current basic block.
3552 Returns false if there is no loop in SCOP. */
3555 build_scop_iteration_domain (scop_p scop)
3558 CloogMatrix *outer_cstr;
3561 /* Build cloog loop for all loops, that are in the uppermost loop layer of
3563 for (i = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), i, loop); i++)
3564 if (!loop_in_scop_p (loop_outer (loop), scop))
3566 /* The outermost constraints is a matrix that has:
3567 -first column: eq/ineq boolean
3568 -last column: a constant
3569 -scop_nb_params columns for the parameters used in the scop. */
3570 outer_cstr = cloog_matrix_alloc (0, scop_nb_params (scop) + 2);
3571 build_loop_iteration_domains (scop, loop, outer_cstr, 0);
3572 cloog_matrix_free (outer_cstr);
3578 /* Initializes an equation CY of the access matrix using the
3579 information for a subscript from AF, relatively to the loop
3580 indexes from LOOP_NEST and parameter indexes from PARAMS. NDIM is
3581 the dimension of the array access, i.e. the number of
3582 subscripts. Returns true when the operation succeeds. */
3585 build_access_matrix_with_af (tree af, lambda_vector cy,
3586 scop_p scop, int ndim)
3590 switch (TREE_CODE (af))
3592 case POLYNOMIAL_CHREC:
3594 struct loop *outer_loop;
3595 tree left = CHREC_LEFT (af);
3596 tree right = CHREC_RIGHT (af);
3599 if (TREE_CODE (right) != INTEGER_CST)
3602 outer_loop = get_loop (CHREC_VARIABLE (af));
3603 var = nb_loops_around_loop_in_scop (outer_loop, scop);
3604 cy[var] = int_cst_value (right);
3606 switch (TREE_CODE (left))
3608 case POLYNOMIAL_CHREC:
3609 return build_access_matrix_with_af (left, cy, scop, ndim);
3612 cy[ndim - 1] = int_cst_value (left);
3616 return build_access_matrix_with_af (left, cy, scop, ndim);
3621 build_access_matrix_with_af (TREE_OPERAND (af, 0), cy, scop, ndim);
3622 build_access_matrix_with_af (TREE_OPERAND (af, 1), cy, scop, ndim);
3626 build_access_matrix_with_af (TREE_OPERAND (af, 0), cy, scop, ndim);
3627 build_access_matrix_with_af (TREE_OPERAND (af, 1), cy, scop, ndim);
3631 cy[ndim - 1] = int_cst_value (af);
3635 param_col = param_index (af, scop);
3636 cy [ndim - scop_nb_params (scop) + param_col - 1] = 1;
3640 /* FIXME: access_fn can have parameters. */
3645 /* Initialize the access matrix in the data reference REF with respect
3646 to the loop nesting LOOP_NEST. Return true when the operation
3650 build_access_matrix (data_reference_p ref, graphite_bb_p gb)
3652 int i, ndim = DR_NUM_DIMENSIONS (ref);
3653 struct access_matrix *am = GGC_NEW (struct access_matrix);
3655 AM_MATRIX (am) = VEC_alloc (lambda_vector, gc, ndim);
3656 DR_SCOP (ref) = GBB_SCOP (gb);
3658 for (i = 0; i < ndim; i++)
3660 lambda_vector v = lambda_vector_new (ref_nb_loops (ref));
3661 scop_p scop = GBB_SCOP (gb);
3662 tree af = DR_ACCESS_FN (ref, i);
3664 if (!build_access_matrix_with_af (af, v, scop, ref_nb_loops (ref)))
3667 VEC_quick_push (lambda_vector, AM_MATRIX (am), v);
3670 DR_ACCESS_MATRIX (ref) = am;
3674 /* Build the access matrices for the data references in the SCOP. */
3677 build_scop_data_accesses (scop_p scop)
3682 /* FIXME: Construction of access matrix is disabled until some
3683 pass, like the data dependence analysis, is using it. */
3686 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
3689 data_reference_p dr;
3691 /* Construct the access matrix for each data ref, with respect to
3692 the loop nest of the current BB in the considered SCOP. */
3694 VEC_iterate (data_reference_p, GBB_DATA_REFS (gb), j, dr);
3697 bool res = build_access_matrix (dr, gb);
3699 /* FIXME: At this point the DRs should always have an affine
3700 form. For the moment this fails as build_access_matrix
3701 does not build matrices with parameters. */
3707 /* Returns the tree variable from the name NAME that was given in
3708 Cloog representation. All the parameters are stored in PARAMS, and
3709 all the loop induction variables are stored in IVSTACK.
3711 FIXME: This is a hack, and Cloog should be fixed to not work with
3712 variable names represented as "char *string", but with void
3713 pointers that could be casted back to a tree. The only problem in
3714 doing that is that Cloog's pretty printer still assumes that
3715 variable names are char *strings. The solution would be to have a
3716 function pointer for pretty-printing that can be redirected to be
3717 print_generic_stmt in our case, or fprintf by default.
3718 ??? Too ugly to live. */
3721 clast_name_to_gcc (const char *name, VEC (name_tree, heap) *params,
3722 loop_iv_stack ivstack)
3729 for (i = 0; VEC_iterate (name_tree, params, i, t); i++)
3730 if (!strcmp (name, t->name))
3733 iv = loop_iv_stack_get_iv_from_name (ivstack, name);
3740 /* Returns the maximal precision type for expressions E1 and E2. */
3743 max_precision_type (tree e1, tree e2)
3745 tree type1 = TREE_TYPE (e1);
3746 tree type2 = TREE_TYPE (e2);
3747 return TYPE_PRECISION (type1) > TYPE_PRECISION (type2) ? type1 : type2;
3751 clast_to_gcc_expression (tree, struct clast_expr *, VEC (name_tree, heap) *,
3754 /* Converts a Cloog reduction expression R with reduction operation OP
3755 to a GCC expression tree of type TYPE. PARAMS is a vector of
3756 parameters of the scop, and IVSTACK contains the stack of induction
3760 clast_to_gcc_expression_red (tree type, enum tree_code op,
3761 struct clast_reduction *r,
3762 VEC (name_tree, heap) *params,
3763 loop_iv_stack ivstack)
3766 tree res = clast_to_gcc_expression (type, r->elts[0], params, ivstack);
3768 for (i = 1; i < r->n; i++)
3770 tree t = clast_to_gcc_expression (type, r->elts[i], params, ivstack);
3771 res = fold_build2 (op, type, res, t);
3776 /* Converts a Cloog AST expression E back to a GCC expression tree of
3777 type TYPE. PARAMS is a vector of parameters of the scop, and
3778 IVSTACK contains the stack of induction variables. */
3781 clast_to_gcc_expression (tree type, struct clast_expr *e,
3782 VEC (name_tree, heap) *params,
3783 loop_iv_stack ivstack)
3789 struct clast_term *t = (struct clast_term *) e;
3793 if (value_one_p (t->val))
3795 tree name = clast_name_to_gcc (t->var, params, ivstack);
3796 return fold_convert (type, name);
3799 else if (value_mone_p (t->val))
3801 tree name = clast_name_to_gcc (t->var, params, ivstack);
3802 name = fold_convert (type, name);
3803 return fold_build1 (NEGATE_EXPR, type, name);
3807 tree name = clast_name_to_gcc (t->var, params, ivstack);
3808 tree cst = gmp_cst_to_tree (type, t->val);
3809 name = fold_convert (type, name);
3810 return fold_build2 (MULT_EXPR, type, cst, name);
3814 return gmp_cst_to_tree (type, t->val);
3819 struct clast_reduction *r = (struct clast_reduction *) e;
3824 return clast_to_gcc_expression_red (type, PLUS_EXPR, r, params, ivstack);
3827 return clast_to_gcc_expression_red (type, MIN_EXPR, r, params, ivstack);
3830 return clast_to_gcc_expression_red (type, MAX_EXPR, r, params, ivstack);
3840 struct clast_binary *b = (struct clast_binary *) e;
3841 struct clast_expr *lhs = (struct clast_expr *) b->LHS;
3842 tree tl = clast_to_gcc_expression (type, lhs, params, ivstack);
3843 tree tr = gmp_cst_to_tree (type, b->RHS);
3847 case clast_bin_fdiv:
3848 return fold_build2 (FLOOR_DIV_EXPR, type, tl, tr);
3850 case clast_bin_cdiv:
3851 return fold_build2 (CEIL_DIV_EXPR, type, tl, tr);
3854 return fold_build2 (EXACT_DIV_EXPR, type, tl, tr);
3857 return fold_build2 (TRUNC_MOD_EXPR, type, tl, tr);
3871 /* Returns the type for the expression E. */
3874 gcc_type_for_clast_expr (struct clast_expr *e,
3875 VEC (name_tree, heap) *params,
3876 loop_iv_stack ivstack)
3882 struct clast_term *t = (struct clast_term *) e;
3885 return TREE_TYPE (clast_name_to_gcc (t->var, params, ivstack));
3892 struct clast_reduction *r = (struct clast_reduction *) e;
3895 return gcc_type_for_clast_expr (r->elts[0], params, ivstack);
3899 for (i = 0; i < r->n; i++)
3901 tree type = gcc_type_for_clast_expr (r->elts[i], params, ivstack);
3911 struct clast_binary *b = (struct clast_binary *) e;
3912 struct clast_expr *lhs = (struct clast_expr *) b->LHS;
3913 return gcc_type_for_clast_expr (lhs, params, ivstack);
3923 /* Returns the type for the equation CLEQ. */
3926 gcc_type_for_clast_eq (struct clast_equation *cleq,
3927 VEC (name_tree, heap) *params,
3928 loop_iv_stack ivstack)
3930 tree type = gcc_type_for_clast_expr (cleq->LHS, params, ivstack);
3934 return gcc_type_for_clast_expr (cleq->RHS, params, ivstack);
3937 /* Translates a clast equation CLEQ to a tree. */
3940 graphite_translate_clast_equation (scop_p scop,
3941 struct clast_equation *cleq,
3942 loop_iv_stack ivstack)
3944 enum tree_code comp;
3945 tree type = gcc_type_for_clast_eq (cleq, SCOP_PARAMS (scop), ivstack);
3946 tree lhs = clast_to_gcc_expression (type, cleq->LHS, SCOP_PARAMS (scop), ivstack);
3947 tree rhs = clast_to_gcc_expression (type, cleq->RHS, SCOP_PARAMS (scop), ivstack);
3949 if (cleq->sign == 0)
3952 else if (cleq->sign > 0)
3958 return fold_build2 (comp, type, lhs, rhs);
3961 /* Creates the test for the condition in STMT. */
3964 graphite_create_guard_cond_expr (scop_p scop, struct clast_guard *stmt,
3965 loop_iv_stack ivstack)
3970 for (i = 0; i < stmt->n; i++)
3972 tree eq = graphite_translate_clast_equation (scop, &stmt->eq[i], ivstack);
3975 cond = fold_build2 (TRUTH_AND_EXPR, TREE_TYPE (eq), cond, eq);
3983 /* Creates a new if region corresponding to Cloog's guard. */
3986 graphite_create_new_guard (scop_p scop, edge entry_edge,
3987 struct clast_guard *stmt,
3988 loop_iv_stack ivstack)
3990 tree cond_expr = graphite_create_guard_cond_expr (scop, stmt, ivstack);
3991 edge exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
3995 /* Walks a CLAST and returns the first statement in the body of a
3998 static struct clast_user_stmt *
3999 clast_get_body_of_loop (struct clast_stmt *stmt)
4002 || CLAST_STMT_IS_A (stmt, stmt_user))
4003 return (struct clast_user_stmt *) stmt;
4005 if (CLAST_STMT_IS_A (stmt, stmt_for))
4006 return clast_get_body_of_loop (((struct clast_for *) stmt)->body);
4008 if (CLAST_STMT_IS_A (stmt, stmt_guard))
4009 return clast_get_body_of_loop (((struct clast_guard *) stmt)->then);
4011 if (CLAST_STMT_IS_A (stmt, stmt_block))
4012 return clast_get_body_of_loop (((struct clast_block *) stmt)->body);
4017 /* Returns the induction variable for the loop that gets translated to
4021 gcc_type_for_iv_of_clast_loop (struct clast_for *stmt_for)
4023 struct clast_user_stmt *stmt = clast_get_body_of_loop ((struct clast_stmt *) stmt_for);
4024 const char *cloog_iv = stmt_for->iterator;
4025 CloogStatement *cs = stmt->statement;
4026 graphite_bb_p gbb = (graphite_bb_p) cloog_statement_usr (cs);
4028 return gcc_type_for_cloog_iv (cloog_iv, gbb);
4031 /* Creates a new LOOP corresponding to Cloog's STMT. Inserts an induction
4032 variable for the new LOOP. New LOOP is attached to CFG starting at
4033 ENTRY_EDGE. LOOP is inserted into the loop tree and becomes the child
4034 loop of the OUTER_LOOP. */
4036 static struct loop *
4037 graphite_create_new_loop (scop_p scop, edge entry_edge,
4038 struct clast_for *stmt, loop_iv_stack ivstack,
4041 tree type = gcc_type_for_iv_of_clast_loop (stmt);
4042 VEC (name_tree, heap) *params = SCOP_PARAMS (scop);
4043 tree lb = clast_to_gcc_expression (type, stmt->LB, params, ivstack);
4044 tree ub = clast_to_gcc_expression (type, stmt->UB, params, ivstack);
4045 tree stride = gmp_cst_to_tree (type, stmt->stride);
4046 tree ivvar = create_tmp_var (type, "graphiteIV");
4048 loop_p loop = create_empty_loop_on_edge
4049 (entry_edge, lb, stride, ub, ivvar, &iv_before,
4050 outer ? outer : entry_edge->src->loop_father);
4052 add_referenced_var (ivvar);
4053 loop_iv_stack_push_iv (ivstack, iv_before, stmt->iterator);
4057 /* Rename the SSA_NAMEs used in STMT and that appear in IVSTACK. */
4060 rename_variables_in_stmt (gimple stmt, htab_t map)
4063 use_operand_p use_p;
4065 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
4067 tree use = USE_FROM_PTR (use_p);
4068 tree new_name = get_new_name_from_old_name (map, use);
4070 replace_exp (use_p, new_name);
4076 /* Returns true if SSA_NAME is a parameter of SCOP. */
4079 is_parameter (scop_p scop, tree ssa_name)
4082 VEC (name_tree, heap) *params = SCOP_PARAMS (scop);
4085 for (i = 0; VEC_iterate (name_tree, params, i, param); i++)
4086 if (param->t == ssa_name)
4092 /* Returns true if NAME is an induction variable. */
4097 return gimple_code (SSA_NAME_DEF_STMT (name)) == GIMPLE_PHI;
4100 static void expand_scalar_variables_stmt (gimple, basic_block, scop_p,
4103 expand_scalar_variables_expr (tree, tree, enum tree_code, tree, basic_block,
4104 scop_p, htab_t, gimple_stmt_iterator *);
4106 /* Copies at GSI all the scalar computations on which the ssa_name OP0
4107 depends on in the SCOP: these are all the scalar variables used in
4108 the definition of OP0, that are defined outside BB and still in the
4109 SCOP, i.e. not a parameter of the SCOP. The expression that is
4110 returned contains only induction variables from the generated code:
4111 MAP contains the induction variables renaming mapping, and is used
4112 to translate the names of induction variables. */
4115 expand_scalar_variables_ssa_name (tree op0, basic_block bb,
4116 scop_p scop, htab_t map,
4117 gimple_stmt_iterator *gsi)
4119 tree var0, var1, type;
4121 enum tree_code subcode;
4123 if (is_parameter (scop, op0)
4125 return get_new_name_from_old_name (map, op0);
4127 def_stmt = SSA_NAME_DEF_STMT (op0);
4129 if (gimple_bb (def_stmt) == bb)
4131 /* If the defining statement is in the basic block already
4132 we do not need to create a new expression for it, we
4133 only need to ensure its operands are expanded. */
4134 expand_scalar_variables_stmt (def_stmt, bb, scop, map);
4135 return get_new_name_from_old_name (map, op0);
4139 if (gimple_code (def_stmt) != GIMPLE_ASSIGN
4140 || !bb_in_scop_p (gimple_bb (def_stmt), scop))
4141 return get_new_name_from_old_name (map, op0);
4143 var0 = gimple_assign_rhs1 (def_stmt);
4144 subcode = gimple_assign_rhs_code (def_stmt);
4145 var1 = gimple_assign_rhs2 (def_stmt);
4146 type = gimple_expr_type (def_stmt);
4148 return expand_scalar_variables_expr (type, var0, subcode, var1, bb, scop,
4153 /* Copies at GSI all the scalar computations on which the expression
4154 OP0 CODE OP1 depends on in the SCOP: these are all the scalar
4155 variables used in OP0 and OP1, defined outside BB and still defined
4156 in the SCOP, i.e. not a parameter of the SCOP. The expression that
4157 is returned contains only induction variables from the generated
4158 code: MAP contains the induction variables renaming mapping, and is
4159 used to translate the names of induction variables. */
4162 expand_scalar_variables_expr (tree type, tree op0, enum tree_code code,
4163 tree op1, basic_block bb, scop_p scop,
4164 htab_t map, gimple_stmt_iterator *gsi)
4166 if (TREE_CODE_CLASS (code) == tcc_constant
4167 || TREE_CODE_CLASS (code) == tcc_declaration)
4170 /* For data references we have to duplicate also its memory
4172 if (TREE_CODE_CLASS (code) == tcc_reference)
4178 tree old_name = TREE_OPERAND (op0, 0);
4179 tree expr = expand_scalar_variables_ssa_name
4180 (old_name, bb, scop, map, gsi);
4181 tree new_name = force_gimple_operand_gsi (gsi, expr, true, NULL,
4182 true, GSI_SAME_STMT);
4184 set_symbol_mem_tag (SSA_NAME_VAR (new_name),
4185 symbol_mem_tag (SSA_NAME_VAR (old_name)));
4186 return fold_build1 (code, type, new_name);
4191 tree op00 = TREE_OPERAND (op0, 0);
4192 tree op01 = TREE_OPERAND (op0, 1);
4193 tree op02 = TREE_OPERAND (op0, 2);
4194 tree op03 = TREE_OPERAND (op0, 3);
4195 tree base = expand_scalar_variables_expr
4196 (TREE_TYPE (op00), op00, TREE_CODE (op00), NULL, bb, scop,
4198 tree subscript = expand_scalar_variables_expr
4199 (TREE_TYPE (op01), op01, TREE_CODE (op01), NULL, bb, scop,
4202 return build4 (ARRAY_REF, type, base, subscript, op02, op03);
4206 /* The above cases should catch everything. */
4211 if (TREE_CODE_CLASS (code) == tcc_unary)
4213 tree op0_type = TREE_TYPE (op0);
4214 enum tree_code op0_code = TREE_CODE (op0);
4215 tree op0_expr = expand_scalar_variables_expr (op0_type, op0, op0_code,
4216 NULL, bb, scop, map, gsi);
4218 return fold_build1 (code, type, op0_expr);
4221 if (TREE_CODE_CLASS (code) == tcc_binary)
4223 tree op0_type = TREE_TYPE (op0);
4224 enum tree_code op0_code = TREE_CODE (op0);
4225 tree op0_expr = expand_scalar_variables_expr (op0_type, op0, op0_code,
4226 NULL, bb, scop, map, gsi);
4227 tree op1_type = TREE_TYPE (op1);
4228 enum tree_code op1_code = TREE_CODE (op1);
4229 tree op1_expr = expand_scalar_variables_expr (op1_type, op1, op1_code,
4230 NULL, bb, scop, map, gsi);
4232 return fold_build2 (code, type, op0_expr, op1_expr);
4235 if (code == SSA_NAME)
4236 return expand_scalar_variables_ssa_name (op0, bb, scop, map, gsi);
4242 /* Copies at the beginning of BB all the scalar computations on which
4243 STMT depends on in the SCOP: these are all the scalar variables used
4244 in STMT, defined outside BB and still defined in the SCOP, i.e. not a
4245 parameter of the SCOP. The expression that is returned contains
4246 only induction variables from the generated code: MAP contains the
4247 induction variables renaming mapping, and is used to translate the
4248 names of induction variables. */
4251 expand_scalar_variables_stmt (gimple stmt, basic_block bb, scop_p scop,
4255 use_operand_p use_p;
4256 gimple_stmt_iterator gsi = gsi_after_labels (bb);
4258 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
4260 tree use = USE_FROM_PTR (use_p);
4261 tree type = TREE_TYPE (use);
4262 enum tree_code code = TREE_CODE (use);
4263 tree use_expr = expand_scalar_variables_expr (type, use, code, NULL, bb,
4265 if (use_expr != use)
4268 force_gimple_operand_gsi (&gsi, use_expr, true, NULL,
4269 true, GSI_NEW_STMT);
4270 replace_exp (use_p, new_use);
4277 /* Copies at the beginning of BB all the scalar computations on which
4278 BB depends on in the SCOP: these are all the scalar variables used
4279 in BB, defined outside BB and still defined in the SCOP, i.e. not a
4280 parameter of the SCOP. The expression that is returned contains
4281 only induction variables from the generated code: MAP contains the
4282 induction variables renaming mapping, and is used to translate the
4283 names of induction variables. */
4286 expand_scalar_variables (basic_block bb, scop_p scop, htab_t map)
4288 gimple_stmt_iterator gsi;
4290 for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi);)
4292 gimple stmt = gsi_stmt (gsi);
4293 expand_scalar_variables_stmt (stmt, bb, scop, map);
4298 /* Rename all the SSA_NAMEs from block BB according to the MAP. */
4301 rename_variables (basic_block bb, htab_t map)
4303 gimple_stmt_iterator gsi;
4305 for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4306 rename_variables_in_stmt (gsi_stmt (gsi), map);
4309 /* Remove condition from BB. */
4312 remove_condition (basic_block bb)
4314 gimple last = last_stmt (bb);
4316 if (last && gimple_code (last) == GIMPLE_COND)
4318 gimple_stmt_iterator gsi = gsi_last_bb (bb);
4319 gsi_remove (&gsi, true);
4323 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag set. */
4326 get_true_edge_from_guard_bb (basic_block bb)
4331 FOR_EACH_EDGE (e, ei, bb->succs)
4332 if (e->flags & EDGE_TRUE_VALUE)
4339 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag cleared. */
4342 get_false_edge_from_guard_bb (basic_block bb)
4347 FOR_EACH_EDGE (e, ei, bb->succs)
4348 if (!(e->flags & EDGE_TRUE_VALUE))
4355 /* Inserts in MAP a tuple (OLD_NAME, NEW_NAME) for the induction
4356 variables of the loops around GBB in SCOP, i.e. GBB_LOOPS.
4357 NEW_NAME is obtained from IVSTACK. IVSTACK has the same stack
4358 ordering as GBB_LOOPS. */
4361 build_iv_mapping (loop_iv_stack ivstack, htab_t map, gbb_p gbb, scop_p scop)
4367 for (i = 0; VEC_iterate (name_tree, SCOP_OLDIVS (scop), i, iv); i++)
4369 struct rename_map_elt tmp;
4371 if (!flow_bb_inside_loop_p (iv->loop, GBB_BB (gbb)))
4374 tmp.old_name = iv->t;
4375 slot = htab_find_slot (map, &tmp, INSERT);
4379 tree new_name = loop_iv_stack_get_iv (ivstack,
4380 gbb_loop_index (gbb, iv->loop));
4381 *slot = new_rename_map_elt (iv->t, new_name);
4386 /* Register in MAP the tuple (old_name, new_name). */
4389 register_old_and_new_names (htab_t map, tree old_name, tree new_name)
4391 struct rename_map_elt tmp;
4394 tmp.old_name = old_name;
4395 slot = htab_find_slot (map, &tmp, INSERT);
4398 *slot = new_rename_map_elt (old_name, new_name);
4401 /* Create a duplicate of the basic block BB. NOTE: This does not
4402 preserve SSA form. */
4405 graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb, htab_t map)
4407 gimple_stmt_iterator gsi, gsi_tgt;
4409 gsi_tgt = gsi_start_bb (new_bb);
4410 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4412 def_operand_p def_p;
4413 ssa_op_iter op_iter;
4415 gimple stmt = gsi_stmt (gsi);
4418 if (gimple_code (stmt) == GIMPLE_LABEL)
4421 /* Create a new copy of STMT and duplicate STMT's virtual
4423 copy = gimple_copy (stmt);
4424 gsi_insert_after (&gsi_tgt, copy, GSI_NEW_STMT);
4425 mark_symbols_for_renaming (copy);
4427 region = lookup_stmt_eh_region (stmt);
4429 add_stmt_to_eh_region (copy, region);
4430 gimple_duplicate_stmt_histograms (cfun, copy, cfun, stmt);
4432 /* Create new names for all the definitions created by COPY and
4433 add replacement mappings for each new name. */
4434 FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_DEF)
4436 tree old_name = DEF_FROM_PTR (def_p);
4437 tree new_name = create_new_def_for (old_name, copy, def_p);
4438 register_old_and_new_names (map, old_name, new_name);
4443 /* Records in SCOP_LIVEOUT_RENAMES the names that are live out of
4444 the SCOP and that appear in the RENAME_MAP. */
4447 register_scop_liveout_renames (scop_p scop, htab_t rename_map)
4450 sese region = SCOP_REGION (scop);
4452 for (i = 0; i < SESE_NUM_VER (region); i++)
4453 if (bitmap_bit_p (SESE_LIVEOUT (region), i)
4454 && is_gimple_reg (ssa_name (i)))
4456 tree old_name = ssa_name (i);
4457 tree new_name = get_new_name_from_old_name (rename_map, old_name);
4459 register_old_and_new_names (SCOP_LIVEOUT_RENAMES (scop),
4460 old_name, new_name);
4464 /* Copies BB and includes in the copied BB all the statements that can
4465 be reached following the use-def chains from the memory accesses,
4466 and returns the next edge following this new block. */
4469 copy_bb_and_scalar_dependences (basic_block bb, scop_p scop,
4470 edge next_e, htab_t map)
4472 basic_block new_bb = split_edge (next_e);
4474 next_e = single_succ_edge (new_bb);
4475 graphite_copy_stmts_from_block (bb, new_bb, map);
4476 remove_condition (new_bb);
4477 rename_variables (new_bb, map);
4478 remove_phi_nodes (new_bb);
4479 expand_scalar_variables (new_bb, scop, map);
4480 register_scop_liveout_renames (scop, map);
4485 /* Helper function for htab_traverse in insert_loop_close_phis. */
4488 add_loop_exit_phis (void **slot, void *s)
4490 struct rename_map_elt *entry = (struct rename_map_elt *) *slot;
4491 tree new_name = entry->new_name;
4492 basic_block bb = (basic_block) s;
4493 gimple phi = create_phi_node (new_name, bb);
4494 tree res = create_new_def_for (gimple_phi_result (phi), phi,
4495 gimple_phi_result_ptr (phi));
4497 add_phi_arg (phi, new_name, single_pred_edge (bb));
4499 entry->new_name = res;
4504 /* Iterate over the SCOP_LIVEOUT_RENAMES (SCOP) and get tuples of the
4505 form (OLD_NAME, NEW_NAME). Insert in BB "RES = phi (NEW_NAME)",
4506 and finally register in SCOP_LIVEOUT_RENAMES (scop) the tuple
4510 insert_loop_close_phis (scop_p scop, basic_block bb)
4512 update_ssa (TODO_update_ssa);
4513 htab_traverse (SCOP_LIVEOUT_RENAMES (scop), add_loop_exit_phis, bb);
4514 update_ssa (TODO_update_ssa);
4517 /* Helper structure for htab_traverse in insert_guard_phis. */
4521 edge true_edge, false_edge;
4522 htab_t liveout_before_guard;
4525 /* Return the default name that is before the guard. */
4528 default_liveout_before_guard (htab_t liveout_before_guard, tree old_name)
4530 tree res = get_new_name_from_old_name (liveout_before_guard, old_name);
4532 if (res == old_name)
4534 if (is_gimple_reg (res))
4535 return fold_convert (TREE_TYPE (res), integer_zero_node);
4536 return gimple_default_def (cfun, res);
4542 /* Helper function for htab_traverse in insert_guard_phis. */
4545 add_guard_exit_phis (void **slot, void *s)
4547 struct rename_map_elt *entry = (struct rename_map_elt *) *slot;
4548 struct igp *i = (struct igp *) s;
4549 basic_block bb = i->bb;
4550 edge true_edge = i->true_edge;
4551 edge false_edge = i->false_edge;
4552 tree name1 = entry->new_name;
4553 tree name2 = default_liveout_before_guard (i->liveout_before_guard,
4555 gimple phi = create_phi_node (name1, bb);
4556 tree res = create_new_def_for (gimple_phi_result (phi), phi,
4557 gimple_phi_result_ptr (phi));
4559 add_phi_arg (phi, name1, true_edge);
4560 add_phi_arg (phi, name2, false_edge);
4562 entry->new_name = res;
4567 /* Iterate over the SCOP_LIVEOUT_RENAMES (SCOP) and get tuples of the
4568 form (OLD_NAME, NAME1). If there is a correspondent tuple of
4569 OLD_NAME in LIVEOUT_BEFORE_GUARD, i.e. (OLD_NAME, NAME2) then
4572 | RES = phi (NAME1 (on TRUE_EDGE), NAME2 (on FALSE_EDGE))"
4574 if there is no tuple for OLD_NAME in LIVEOUT_BEFORE_GUARD, insert
4576 | RES = phi (NAME1 (on TRUE_EDGE),
4577 | DEFAULT_DEFINITION of NAME1 (on FALSE_EDGE))".
4579 Finally register in SCOP_LIVEOUT_RENAMES (scop) the tuple
4583 insert_guard_phis (scop_p scop, basic_block bb, edge true_edge,
4584 edge false_edge, htab_t liveout_before_guard)
4588 i.true_edge = true_edge;
4589 i.false_edge = false_edge;
4590 i.liveout_before_guard = liveout_before_guard;
4592 update_ssa (TODO_update_ssa);
4593 htab_traverse (SCOP_LIVEOUT_RENAMES (scop), add_guard_exit_phis, &i);
4594 update_ssa (TODO_update_ssa);
4597 /* Helper function for htab_traverse. */
4600 copy_renames (void **slot, void *s)
4602 struct rename_map_elt *entry = (struct rename_map_elt *) *slot;
4603 htab_t res = (htab_t) s;
4604 tree old_name = entry->old_name;
4605 tree new_name = entry->new_name;
4606 struct rename_map_elt tmp;
4609 tmp.old_name = old_name;
4610 x = htab_find_slot (res, &tmp, INSERT);
4613 *x = new_rename_map_elt (old_name, new_name);
4618 /* Translates a CLAST statement STMT to GCC representation in the
4621 - NEXT_E is the edge where new generated code should be attached.
4622 - CONTEXT_LOOP is the loop in which the generated code will be placed
4624 - IVSTACK contains the surrounding loops around the statement to be
4629 translate_clast (scop_p scop, struct loop *context_loop,
4630 struct clast_stmt *stmt, edge next_e, loop_iv_stack ivstack)
4635 if (CLAST_STMT_IS_A (stmt, stmt_root))
4636 return translate_clast (scop, context_loop, stmt->next, next_e, ivstack);
4638 if (CLAST_STMT_IS_A (stmt, stmt_user))
4641 CloogStatement *cs = ((struct clast_user_stmt *) stmt)->statement;
4642 graphite_bb_p gbb = (graphite_bb_p) cloog_statement_usr (cs);
4644 if (GBB_BB (gbb) == ENTRY_BLOCK_PTR)
4647 map = htab_create (10, rename_map_elt_info, eq_rename_map_elts, free);
4648 loop_iv_stack_patch_for_consts (ivstack, (struct clast_user_stmt *) stmt);
4649 build_iv_mapping (ivstack, map, gbb, scop);
4650 next_e = copy_bb_and_scalar_dependences (GBB_BB (gbb), scop,
4653 loop_iv_stack_remove_constants (ivstack);
4654 update_ssa (TODO_update_ssa);
4655 recompute_all_dominators ();
4657 return translate_clast (scop, context_loop, stmt->next, next_e, ivstack);
4660 if (CLAST_STMT_IS_A (stmt, stmt_for))
4663 = graphite_create_new_loop (scop, next_e, (struct clast_for *) stmt,
4664 ivstack, context_loop ? context_loop
4666 edge last_e = single_exit (loop);
4668 next_e = translate_clast (scop, loop, ((struct clast_for *) stmt)->body,
4669 single_pred_edge (loop->latch), ivstack);
4670 redirect_edge_succ_nodup (next_e, loop->latch);
4672 set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src);
4673 loop_iv_stack_pop (ivstack);
4674 last_e = single_succ_edge (split_edge (last_e));
4675 insert_loop_close_phis (scop, last_e->src);
4677 recompute_all_dominators ();
4679 return translate_clast (scop, context_loop, stmt->next, last_e, ivstack);
4682 if (CLAST_STMT_IS_A (stmt, stmt_guard))
4684 htab_t liveout_before_guard = htab_create (10, rename_map_elt_info,
4685 eq_rename_map_elts, free);
4686 edge last_e = graphite_create_new_guard (scop, next_e,
4687 ((struct clast_guard *) stmt),
4689 edge true_e = get_true_edge_from_guard_bb (next_e->dest);
4690 edge false_e = get_false_edge_from_guard_bb (next_e->dest);
4691 edge exit_true_e = single_succ_edge (true_e->dest);
4692 edge exit_false_e = single_succ_edge (false_e->dest);
4694 htab_traverse (SCOP_LIVEOUT_RENAMES (scop), copy_renames,
4695 liveout_before_guard);
4697 next_e = translate_clast (scop, context_loop,
4698 ((struct clast_guard *) stmt)->then,
4700 insert_guard_phis (scop, last_e->src, exit_true_e, exit_false_e,
4701 liveout_before_guard);
4702 htab_delete (liveout_before_guard);
4703 recompute_all_dominators ();
4706 return translate_clast (scop, context_loop, stmt->next, last_e, ivstack);
4709 if (CLAST_STMT_IS_A (stmt, stmt_block))
4711 next_e = translate_clast (scop, context_loop,
4712 ((struct clast_block *) stmt)->body,
4714 recompute_all_dominators ();
4716 return translate_clast (scop, context_loop, stmt->next, next_e, ivstack);
4722 /* Free the SCATTERING domain list. */
4725 free_scattering (CloogDomainList *scattering)
4729 CloogDomain *dom = cloog_domain (scattering);
4730 CloogDomainList *next = cloog_next_domain (scattering);
4732 cloog_domain_free (dom);
4738 /* Build cloog program for SCoP. */
4741 build_cloog_prog (scop_p scop)
4744 int max_nb_loops = scop_max_loop_depth (scop);
4746 CloogLoop *loop_list = NULL;
4747 CloogBlockList *block_list = NULL;
4748 CloogDomainList *scattering = NULL;
4749 CloogProgram *prog = SCOP_PROG (scop);
4750 int nbs = 2 * max_nb_loops + 1;
4751 int *scaldims = (int *) xmalloc (nbs * (sizeof (int)));
4753 cloog_program_set_nb_scattdims (prog, nbs);
4754 initialize_cloog_names (scop);
4756 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gbb); i++)
4758 /* Build new block. */
4759 CloogMatrix *domain = GBB_DOMAIN (gbb);
4760 CloogStatement *stmt = cloog_statement_alloc (GBB_BB (gbb)->index);
4761 CloogBlock *block = cloog_block_alloc (stmt, 0, NULL,
4762 nb_loops_around_gb (gbb));
4763 cloog_statement_set_usr (stmt, gbb);
4765 /* Add empty domain to all bbs, which do not yet have a domain, as they
4766 are not part of any loop. */
4769 domain = cloog_matrix_alloc (0, scop_nb_params (scop) + 2);
4770 GBB_DOMAIN (gbb) = domain;
4773 /* Build loop list. */
4775 CloogLoop *new_loop_list = cloog_loop_malloc ();
4776 cloog_loop_set_next (new_loop_list, loop_list);
4777 cloog_loop_set_domain (new_loop_list,
4778 cloog_domain_matrix2domain (domain));
4779 cloog_loop_set_block (new_loop_list, block);
4780 loop_list = new_loop_list;
4783 /* Build block list. */
4785 CloogBlockList *new_block_list = cloog_block_list_malloc ();
4787 cloog_block_list_set_next (new_block_list, block_list);
4788 cloog_block_list_set_block (new_block_list, block);
4789 block_list = new_block_list;
4792 /* Build scattering list. */
4794 /* XXX: Replace with cloog_domain_list_alloc(), when available. */
4795 CloogDomainList *new_scattering
4796 = (CloogDomainList *) xmalloc (sizeof (CloogDomainList));
4797 CloogMatrix *scat_mat = schedule_to_scattering (gbb, nbs);
4799 cloog_set_next_domain (new_scattering, scattering);
4800 cloog_set_domain (new_scattering,
4801 cloog_domain_matrix2domain (scat_mat));
4802 scattering = new_scattering;
4803 cloog_matrix_free (scat_mat);
4807 cloog_program_set_loop (prog, loop_list);
4808 cloog_program_set_blocklist (prog, block_list);
4810 for (i = 0; i < nbs; i++)
4813 cloog_program_set_scaldims (prog, scaldims);
4815 /* Extract scalar dimensions to simplify the code generation problem. */
4816 cloog_program_extract_scalars (prog, scattering);
4818 /* Apply scattering. */
4819 cloog_program_scatter (prog, scattering);
4820 free_scattering (scattering);
4822 /* Iterators corresponding to scalar dimensions have to be extracted. */
4823 cloog_names_scalarize (cloog_program_names (prog), nbs,
4824 cloog_program_scaldims (prog));
4826 /* Free blocklist. */
4828 CloogBlockList *next = cloog_program_blocklist (prog);
4832 CloogBlockList *toDelete = next;
4833 next = cloog_block_list_next (next);
4834 cloog_block_list_set_next (toDelete, NULL);
4835 cloog_block_list_set_block (toDelete, NULL);
4836 cloog_block_list_free (toDelete);
4838 cloog_program_set_blocklist (prog, NULL);
4842 /* Return the options that will be used in GLOOG. */
4844 static CloogOptions *
4845 set_cloog_options (void)
4847 CloogOptions *options = cloog_options_malloc ();
4849 /* Change cloog output language to C. If we do use FORTRAN instead, cloog
4850 will stop e.g. with "ERROR: unbounded loops not allowed in FORTRAN.", if
4851 we pass an incomplete program to cloog. */
4852 options->language = LANGUAGE_C;
4854 /* Enable complex equality spreading: removes dummy statements
4855 (assignments) in the generated code which repeats the
4856 substitution equations for statements. This is useless for
4860 /* Enable C pretty-printing mode: normalizes the substitution
4861 equations for statements. */
4864 /* Allow cloog to build strides with a stride width different to one.
4865 This example has stride = 4:
4867 for (i = 0; i < 20; i += 4)
4869 options->strides = 1;
4871 /* Disable optimizations and make cloog generate source code closer to the
4872 input. This is useful for debugging, but later we want the optimized
4875 XXX: We can not disable optimizations, as loop blocking is not working
4880 options->l = INT_MAX;
4886 /* Prints STMT to STDERR. */
4889 debug_clast_stmt (struct clast_stmt *stmt)
4891 CloogOptions *options = set_cloog_options ();
4893 pprint (stderr, stmt, 0, options);
4896 /* Find the right transform for the SCOP, and return a Cloog AST
4897 representing the new form of the program. */
4899 static struct clast_stmt *
4900 find_transform (scop_p scop)
4902 struct clast_stmt *stmt;
4903 CloogOptions *options = set_cloog_options ();
4905 /* Connect new cloog prog generation to graphite. */
4906 build_cloog_prog (scop);
4908 if (dump_file && (dump_flags & TDF_DETAILS))
4910 fprintf (dump_file, "Cloog Input [\n");
4911 cloog_program_print (dump_file, SCOP_PROG(scop));
4912 fprintf (dump_file, "]\n");
4915 SCOP_PROG (scop) = cloog_program_generate (SCOP_PROG (scop), options);
4916 stmt = cloog_clast_create (SCOP_PROG (scop), options);
4918 if (dump_file && (dump_flags & TDF_DETAILS))
4920 fprintf (dump_file, "Cloog Output[\n");
4921 pprint (dump_file, stmt, 0, options);
4922 cloog_program_dump_cloog (dump_file, SCOP_PROG (scop));
4923 fprintf (dump_file, "]\n");
4926 cloog_options_free (options);
4930 /* Remove from the CFG the REGION. */
4933 remove_sese_region (sese region)
4935 VEC (basic_block, heap) *bbs = NULL;
4936 basic_block entry_bb = SESE_ENTRY (region)->dest;
4937 basic_block exit_bb = SESE_EXIT (region)->dest;
4941 VEC_safe_push (basic_block, heap, bbs, entry_bb);
4942 gather_blocks_in_sese_region (entry_bb, exit_bb, &bbs);
4944 for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
4945 delete_basic_block (bb);
4947 VEC_free (basic_block, heap, bbs);
4950 typedef struct ifsese {
4957 if_region_entry (ifsese if_region)
4959 return SESE_ENTRY (if_region->region);
4963 if_region_exit (ifsese if_region)
4965 return SESE_EXIT (if_region->region);
4968 static inline basic_block
4969 if_region_get_condition_block (ifsese if_region)
4971 return if_region_entry (if_region)->dest;
4975 if_region_set_false_region (ifsese if_region, sese region)
4977 basic_block condition = if_region_get_condition_block (if_region);
4978 edge false_edge = get_false_edge_from_guard_bb (condition);
4979 edge entry_region = SESE_ENTRY (region);
4980 edge exit_region = SESE_EXIT (region);
4981 basic_block before_region = entry_region->src;
4982 basic_block last_in_region = exit_region->src;
4983 void **slot = htab_find_slot_with_hash (current_loops->exits, exit_region,
4984 htab_hash_pointer (exit_region),
4987 entry_region->flags = false_edge->flags;
4988 false_edge->flags = exit_region->flags;
4990 redirect_edge_pred (entry_region, condition);
4991 redirect_edge_pred (exit_region, before_region);
4992 redirect_edge_pred (false_edge, last_in_region);
4994 exit_region->flags = EDGE_FALLTHRU;
4995 recompute_all_dominators ();
4997 SESE_EXIT (region) = single_succ_edge (false_edge->dest);
4998 if_region->false_region = region;
5002 struct loop_exit *loop_exit = GGC_CNEW (struct loop_exit);
5004 memcpy (loop_exit, *((struct loop_exit **) slot), sizeof (struct loop_exit));
5005 htab_clear_slot (current_loops->exits, slot);
5007 slot = htab_find_slot_with_hash (current_loops->exits, false_edge,
5008 htab_hash_pointer (false_edge),
5010 loop_exit->e = false_edge;
5012 false_edge->src->loop_father->exits->next = loop_exit;
5017 create_if_region_on_edge (edge entry, tree condition)
5021 sese sese_region = GGC_NEW (struct sese);
5022 sese true_region = GGC_NEW (struct sese);
5023 sese false_region = GGC_NEW (struct sese);
5024 ifsese if_region = GGC_NEW (struct ifsese);
5025 edge exit = create_empty_if_region_on_edge (entry, condition);
5027 if_region->region = sese_region;
5028 if_region->region->entry = entry;
5029 if_region->region->exit = exit;
5031 FOR_EACH_EDGE (e, ei, entry->dest->succs)
5033 if (e->flags & EDGE_TRUE_VALUE)
5035 true_region->entry = e;
5036 true_region->exit = single_succ_edge (e->dest);
5037 if_region->true_region = true_region;
5039 else if (e->flags & EDGE_FALSE_VALUE)
5041 false_region->entry = e;
5042 false_region->exit = single_succ_edge (e->dest);
5043 if_region->false_region = false_region;
5050 /* Moves REGION in a condition expression:
5058 move_sese_in_condition (sese region)
5060 basic_block pred_block = split_edge (SESE_ENTRY (region));
5061 ifsese if_region = NULL;
5063 SESE_ENTRY (region) = single_succ_edge (pred_block);
5064 if_region = create_if_region_on_edge (single_pred_edge (pred_block), integer_one_node);
5065 if_region_set_false_region (if_region, region);
5070 /* Add exit phis for USE on EXIT. */
5073 scop_add_exit_phis_edge (basic_block exit, tree use, edge false_e, edge true_e)
5075 gimple phi = create_phi_node (use, exit);
5077 create_new_def_for (gimple_phi_result (phi), phi,
5078 gimple_phi_result_ptr (phi));
5079 add_phi_arg (phi, use, false_e);
5080 add_phi_arg (phi, use, true_e);
5083 /* Add phi nodes for VAR that is used in LIVEIN. Phi nodes are
5084 inserted in block BB. */
5087 scop_add_exit_phis_var (basic_block bb, tree var, bitmap livein,
5088 edge false_e, edge true_e)
5091 basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (var));
5093 if (is_gimple_reg (var))
5094 bitmap_clear_bit (livein, def_bb->index);
5096 bitmap_set_bit (livein, def_bb->index);
5098 def = BITMAP_ALLOC (NULL);
5099 bitmap_set_bit (def, def_bb->index);
5100 compute_global_livein (livein, def);
5103 scop_add_exit_phis_edge (bb, var, false_e, true_e);
5106 /* Insert in the block BB phi nodes for variables defined in REGION
5107 and used outside the REGION. The code generation moves REGION in
5108 the else clause of an "if (1)" and generates code in the then
5109 clause that is at this point empty:
5118 scop_insert_phis_for_liveouts (sese region, basic_block bb,
5119 edge false_e, edge true_e)
5124 update_ssa (TODO_update_ssa);
5126 EXECUTE_IF_SET_IN_BITMAP (SESE_LIVEOUT (region), 0, i, bi)
5127 scop_add_exit_phis_var (bb, ssa_name (i), SESE_LIVEIN_VER (region, i),
5130 update_ssa (TODO_update_ssa);
5133 /* Get the definition of NAME before the SCOP. Keep track of the
5134 basic blocks that have been VISITED in a bitmap. */
5137 get_vdef_before_scop (scop_p scop, tree name, sbitmap visited)
5140 gimple def_stmt = SSA_NAME_DEF_STMT (name);
5141 basic_block def_bb = gimple_bb (def_stmt);
5144 || !bb_in_scop_p (def_bb, scop))
5147 if (TEST_BIT (visited, def_bb->index))
5150 SET_BIT (visited, def_bb->index);
5152 switch (gimple_code (def_stmt))
5155 for (i = 0; i < gimple_phi_num_args (def_stmt); i++)
5157 tree arg = gimple_phi_arg_def (def_stmt, i);
5158 tree res = get_vdef_before_scop (scop, arg, visited);
5169 /* Adjust a virtual phi node PHI that is placed at the end of the
5170 generated code for SCOP:
5173 | generated code from REGION;
5177 The FALSE_E edge comes from the original code, TRUE_E edge comes
5178 from the code generated for the SCOP. */
5181 scop_adjust_vphi (scop_p scop, gimple phi, edge true_e)
5185 gcc_assert (gimple_phi_num_args (phi) == 2);
5187 for (i = 0; i < gimple_phi_num_args (phi); i++)
5188 if (gimple_phi_arg_edge (phi, i) == true_e)
5190 tree true_arg, false_arg, before_scop_arg;
5193 true_arg = gimple_phi_arg_def (phi, i);
5194 if (!SSA_NAME_IS_DEFAULT_DEF (true_arg))
5197 false_arg = gimple_phi_arg_def (phi, i == 0 ? 1 : 0);
5198 if (SSA_NAME_IS_DEFAULT_DEF (false_arg))
5201 visited = sbitmap_alloc (last_basic_block);
5202 sbitmap_zero (visited);
5203 before_scop_arg = get_vdef_before_scop (scop, false_arg, visited);
5204 gcc_assert (before_scop_arg != NULL_TREE);
5205 SET_PHI_ARG_DEF (phi, i, before_scop_arg);
5206 sbitmap_free (visited);
5210 /* Adjusts the phi nodes in the block BB for variables defined in
5211 SCOP_REGION and used outside the SCOP_REGION. The code generation
5212 moves SCOP_REGION in the else clause of an "if (1)" and generates
5213 code in the then clause:
5216 | generated code from REGION;
5220 To adjust the phi nodes after the condition, SCOP_LIVEOUT_RENAMES
5221 hash table is used: this stores for a name that is part of the
5222 LIVEOUT of SCOP_REGION its new name in the generated code. */
5225 scop_adjust_phis_for_liveouts (scop_p scop, basic_block bb, edge false_e,
5228 gimple_stmt_iterator si;
5230 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
5232 unsigned i, false_i;
5233 gimple phi = gsi_stmt (si);
5235 if (!is_gimple_reg (PHI_RESULT (phi)))
5237 scop_adjust_vphi (scop, phi, true_e);
5241 for (i = 0; i < gimple_phi_num_args (phi); i++)
5242 if (gimple_phi_arg_edge (phi, i) == false_e)
5248 for (i = 0; i < gimple_phi_num_args (phi); i++)
5249 if (gimple_phi_arg_edge (phi, i) == true_e)
5251 tree old_name = gimple_phi_arg_def (phi, false_i);
5252 tree new_name = get_new_name_from_old_name
5253 (SCOP_LIVEOUT_RENAMES (scop), old_name);
5255 gcc_assert (old_name != new_name);
5256 SET_PHI_ARG_DEF (phi, i, new_name);
5261 /* Returns the first cloog name used in EXPR. */
5264 find_cloog_iv_in_expr (struct clast_expr *expr)
5266 struct clast_term *term = (struct clast_term *) expr;
5268 if (expr->type == expr_term
5272 if (expr->type == expr_term)
5275 if (expr->type == expr_red)
5278 struct clast_reduction *red = (struct clast_reduction *) expr;
5280 for (i = 0; i < red->n; i++)
5282 const char *res = find_cloog_iv_in_expr ((red)->elts[i]);
5292 /* Build for a clast_user_stmt USER_STMT a map between the CLAST
5293 induction variables and the corresponding GCC old induction
5294 variables. This information is stored on each GRAPHITE_BB. */
5297 compute_cloog_iv_types_1 (graphite_bb_p gbb,
5298 struct clast_user_stmt *user_stmt)
5300 struct clast_stmt *t;
5303 for (t = user_stmt->substitutions; t; t = t->next, index++)
5306 struct ivtype_map_elt tmp;
5307 struct clast_expr *expr = (struct clast_expr *)
5308 ((struct clast_assignment *)t)->RHS;
5310 /* Create an entry (clast_var, type). */
5311 tmp.cloog_iv = find_cloog_iv_in_expr (expr);
5315 slot = htab_find_slot (GBB_CLOOG_IV_TYPES (gbb), &tmp, INSERT);
5319 loop_p loop = gbb_loop_at_index (gbb, index);
5320 tree oldiv = oldiv_for_loop (GBB_SCOP (gbb), loop);
5321 tree type = oldiv ? TREE_TYPE (oldiv) : integer_type_node;
5322 *slot = new_ivtype_map_elt (tmp.cloog_iv, type);
5327 /* Walk the CLAST tree starting from STMT and build for each
5328 clast_user_stmt a map between the CLAST induction variables and the
5329 corresponding GCC old induction variables. This information is
5330 stored on each GRAPHITE_BB. */
5333 compute_cloog_iv_types (struct clast_stmt *stmt)
5338 if (CLAST_STMT_IS_A (stmt, stmt_root))
5341 if (CLAST_STMT_IS_A (stmt, stmt_user))
5343 CloogStatement *cs = ((struct clast_user_stmt *) stmt)->statement;
5344 graphite_bb_p gbb = (graphite_bb_p) cloog_statement_usr (cs);
5345 GBB_CLOOG_IV_TYPES (gbb) = htab_create (10, ivtype_map_elt_info,
5346 eq_ivtype_map_elts, free);
5347 compute_cloog_iv_types_1 (gbb, (struct clast_user_stmt *) stmt);
5351 if (CLAST_STMT_IS_A (stmt, stmt_for))
5353 struct clast_stmt *s = ((struct clast_for *) stmt)->body;
5354 compute_cloog_iv_types (s);
5358 if (CLAST_STMT_IS_A (stmt, stmt_guard))
5360 struct clast_stmt *s = ((struct clast_guard *) stmt)->then;
5361 compute_cloog_iv_types (s);
5365 if (CLAST_STMT_IS_A (stmt, stmt_block))
5367 struct clast_stmt *s = ((struct clast_block *) stmt)->body;
5368 compute_cloog_iv_types (s);
5375 compute_cloog_iv_types (stmt->next);
5378 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
5382 gloog (scop_p scop, struct clast_stmt *stmt)
5384 edge new_scop_exit_edge = NULL;
5385 VEC (iv_stack_entry_p, heap) *ivstack = VEC_alloc (iv_stack_entry_p, heap,
5387 loop_p context_loop;
5388 ifsese if_region = NULL;
5390 if_region = move_sese_in_condition (SCOP_REGION (scop));
5391 sese_build_livein_liveouts (SCOP_REGION (scop));
5392 scop_insert_phis_for_liveouts (SCOP_REGION (scop),
5393 if_region->region->exit->src,
5394 if_region->false_region->exit,
5395 if_region->true_region->exit);
5396 recompute_all_dominators ();
5398 context_loop = SESE_ENTRY (SCOP_REGION (scop))->src->loop_father;
5399 compute_cloog_iv_types (stmt);
5401 new_scop_exit_edge = translate_clast (scop, context_loop, stmt,
5402 if_region->true_region->entry,
5404 free_loop_iv_stack (&ivstack);
5405 cloog_clast_free (stmt);
5408 scop_adjust_phis_for_liveouts (scop,
5409 if_region->region->exit->src,
5410 if_region->false_region->exit,
5411 if_region->true_region->exit);
5413 recompute_all_dominators ();
5417 /* Returns the number of data references in SCOP. */
5420 nb_data_refs_in_scop (scop_p scop)
5426 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gbb); i++)
5427 res += VEC_length (data_reference_p, GBB_DATA_REFS (gbb));
5432 /* Move the loop at index LOOP and insert it before index NEW_LOOP_POS.
5433 This transformartion is only valid, if the loop nest between i and k is
5434 perfectly nested. Therefore we do not need to change the static schedule.
5438 for (i = 0; i < 50; i++)
5440 for (k = 5; k < 100; k++)
5443 To move k before i use:
5445 graphite_trans_bb_move_loop (A, 2, 0)
5447 for (k = 5; k < 100; k++)
5448 for (i = 0; i < 50; i++)
5454 graphite_trans_bb_move_loop (A, 0, 2)
5456 This function does not check the validity of interchanging loops.
5457 This should be checked before calling this function. */
5460 graphite_trans_bb_move_loop (graphite_bb_p gb, int loop,
5463 CloogMatrix *domain = GBB_DOMAIN (gb);
5467 gcc_assert (loop < gbb_nb_loops (gb)
5468 && new_loop_pos < gbb_nb_loops (gb));
5470 /* Update LOOPS vector. */
5471 tmp_loop_p = VEC_index (loop_p, GBB_LOOPS (gb), loop);
5472 VEC_ordered_remove (loop_p, GBB_LOOPS (gb), loop);
5473 VEC_safe_insert (loop_p, heap, GBB_LOOPS (gb), new_loop_pos, tmp_loop_p);
5475 /* Move the domain columns. */
5476 if (loop < new_loop_pos)
5477 for (row = 0; row < domain->NbRows; row++)
5481 value_assign (tmp, domain->p[row][loop + 1]);
5483 for (j = loop ; j < new_loop_pos - 1; j++)
5484 value_assign (domain->p[row][j + 1], domain->p[row][j + 2]);
5486 value_assign (domain->p[row][new_loop_pos], tmp);
5490 for (row = 0; row < domain->NbRows; row++)
5494 value_assign (tmp, domain->p[row][loop + 1]);
5496 for (j = loop ; j > new_loop_pos; j--)
5497 value_assign (domain->p[row][j + 1], domain->p[row][j]);
5499 value_assign (domain->p[row][new_loop_pos + 1], tmp);
5504 /* Get the index of the column representing constants in the DOMAIN
5508 const_column_index (CloogMatrix *domain)
5510 return domain->NbColumns - 1;
5514 /* Get the first index that is positive or negative, determined
5515 following the value of POSITIVE, in matrix DOMAIN in COLUMN. */
5518 get_first_matching_sign_row_index (CloogMatrix *domain, int column,
5523 for (row = 0; row < domain->NbRows; row++)
5525 int val = value_get_si (domain->p[row][column]);
5527 if (val > 0 && positive)
5530 else if (val < 0 && !positive)
5537 /* Get the lower bound of COLUMN in matrix DOMAIN. */
5540 get_lower_bound_row (CloogMatrix *domain, int column)
5542 return get_first_matching_sign_row_index (domain, column, true);
5545 /* Get the upper bound of COLUMN in matrix DOMAIN. */
5548 get_upper_bound_row (CloogMatrix *domain, int column)
5550 return get_first_matching_sign_row_index (domain, column, false);
5553 /* Copies the OLD_ROW constraint from OLD_DOMAIN to the NEW_DOMAIN at
5557 copy_constraint (CloogMatrix *old_domain, CloogMatrix *new_domain,
5558 int old_row, int new_row)
5562 gcc_assert (old_domain->NbColumns == new_domain->NbColumns
5563 && old_row < old_domain->NbRows
5564 && new_row < new_domain->NbRows);
5566 for (i = 0; i < old_domain->NbColumns; i++)
5567 value_assign (new_domain->p[new_row][i], old_domain->p[old_row][i]);
5570 /* Swap coefficients of variables X and Y on row R. */
5573 swap_constraint_variables (CloogMatrix *domain,
5574 int r, int x, int y)
5576 value_swap (domain->p[r][x], domain->p[r][y]);
5579 /* Scale by X the coefficient C of constraint at row R in DOMAIN. */
5582 scale_constraint_variable (CloogMatrix *domain,
5583 int r, int c, int x)
5585 Value strip_size_value;
5586 value_init (strip_size_value);
5587 value_set_si (strip_size_value, x);
5588 value_multiply (domain->p[r][c], domain->p[r][c], strip_size_value);
5589 value_clear (strip_size_value);
5592 /* Strip mines the loop of BB at the position LOOP_DEPTH with STRIDE.
5593 Always valid, but not always a performance improvement. */
5596 graphite_trans_bb_strip_mine (graphite_bb_p gb, int loop_depth, int stride)
5600 CloogMatrix *domain = GBB_DOMAIN (gb);
5601 CloogMatrix *new_domain = cloog_matrix_alloc (domain->NbRows + 3,
5602 domain->NbColumns + 1);
5604 int col_loop_old = loop_depth + 2;
5605 int col_loop_strip = col_loop_old - 1;
5607 gcc_assert (loop_depth <= gbb_nb_loops (gb) - 1);
5609 VEC_safe_insert (loop_p, heap, GBB_LOOPS (gb), loop_depth, NULL);
5611 GBB_DOMAIN (gb) = new_domain;
5613 for (row = 0; row < domain->NbRows; row++)
5614 for (col = 0; col < domain->NbColumns; col++)
5615 if (col <= loop_depth)
5616 value_assign (new_domain->p[row][col], domain->p[row][col]);
5618 value_assign (new_domain->p[row][col + 1], domain->p[row][col]);
5620 row = domain->NbRows;
5622 /* Lower bound of the outer stripped loop. */
5623 copy_constraint (new_domain, new_domain,
5624 get_lower_bound_row (new_domain, col_loop_old), row);
5625 swap_constraint_variables (new_domain, row, col_loop_old, col_loop_strip);
5628 /* Upper bound of the outer stripped loop. */
5629 copy_constraint (new_domain, new_domain,
5630 get_upper_bound_row (new_domain, col_loop_old), row);
5631 swap_constraint_variables (new_domain, row, col_loop_old, col_loop_strip);
5632 scale_constraint_variable (new_domain, row, col_loop_strip, stride);
5635 /* Lower bound of a tile starts at "stride * outer_iv". */
5636 row = get_lower_bound_row (new_domain, col_loop_old);
5637 value_set_si (new_domain->p[row][0], 1);
5638 value_set_si (new_domain->p[row][const_column_index (new_domain)], 0);
5639 value_set_si (new_domain->p[row][col_loop_old], 1);
5640 value_set_si (new_domain->p[row][col_loop_strip], -1 * stride);
5642 /* Upper bound of a tile stops at "stride * outer_iv + stride - 1",
5643 or at the old upper bound that is not modified. */
5644 row = new_domain->NbRows - 1;
5645 value_set_si (new_domain->p[row][0], 1);
5646 value_set_si (new_domain->p[row][col_loop_old], -1);
5647 value_set_si (new_domain->p[row][col_loop_strip], stride);
5648 value_set_si (new_domain->p[row][const_column_index (new_domain)],
5651 cloog_matrix_free (domain);
5653 /* Update static schedule. */
5656 int nb_loops = gbb_nb_loops (gb);
5657 lambda_vector new_schedule = lambda_vector_new (nb_loops + 1);
5659 for (i = 0; i <= loop_depth; i++)
5660 new_schedule[i] = GBB_STATIC_SCHEDULE (gb)[i];
5662 for (i = loop_depth + 1; i <= nb_loops - 2; i++)
5663 new_schedule[i + 2] = GBB_STATIC_SCHEDULE (gb)[i];
5665 GBB_STATIC_SCHEDULE (gb) = new_schedule;
5669 /* Returns true when the strip mining of LOOP_INDEX by STRIDE is
5670 profitable or undecidable. GB is the statement around which the
5671 loops will be strip mined. */
5674 strip_mine_profitable_p (graphite_bb_p gb, int stride,
5683 loop = VEC_index (loop_p, GBB_LOOPS (gb), loop_index);
5684 exit = single_exit (loop);
5686 niter = find_loop_niter (loop, &exit);
5687 if (niter == chrec_dont_know
5688 || TREE_CODE (niter) != INTEGER_CST)
5691 niter_val = int_cst_value (niter);
5693 if (niter_val < stride)
5696 if (dump_file && (dump_flags & TDF_DETAILS))
5698 fprintf (dump_file, "\nStrip Mining is not profitable for loop %d:",
5700 fprintf (dump_file, "number of iterations is too low.\n");
5707 /* Determines when the interchange of LOOP_A and LOOP_B belonging to
5708 SCOP is legal. DEPTH is the number of loops around. */
5711 is_interchange_valid (scop_p scop, int loop_a, int loop_b, int depth)
5714 VEC (ddr_p, heap) *dependence_relations;
5715 VEC (data_reference_p, heap) *datarefs;
5717 struct loop *nest = VEC_index (loop_p, SCOP_LOOP_NEST (scop), loop_a);
5718 lambda_trans_matrix trans;
5720 gcc_assert (loop_a < loop_b);
5722 dependence_relations = VEC_alloc (ddr_p, heap, 10 * 10);
5723 datarefs = VEC_alloc (data_reference_p, heap, 10);
5725 if (!compute_data_dependences_for_loop (nest, true, &datarefs,
5726 &dependence_relations))
5729 if (dump_file && (dump_flags & TDF_DETAILS))
5730 dump_ddrs (dump_file, dependence_relations);
5732 trans = lambda_trans_matrix_new (depth, depth);
5733 lambda_matrix_id (LTM_MATRIX (trans), depth);
5735 lambda_matrix_row_exchange (LTM_MATRIX (trans), 0, loop_b - loop_a);
5737 if (!lambda_transform_legal_p (trans, depth, dependence_relations))
5739 lambda_matrix_row_exchange (LTM_MATRIX (trans), 0, loop_b - loop_a);
5745 free_dependence_relations (dependence_relations);
5746 free_data_refs (datarefs);
5750 /* Loop block the LOOPS innermost loops of GB with stride size STRIDE.
5754 for (i = 0; i <= 50; i++=4)
5755 for (k = 0; k <= 100; k++=4)
5756 for (l = 0; l <= 200; l++=4)
5759 To strip mine the two inner most loops with stride = 4 call:
5761 graphite_trans_bb_block (A, 4, 2)
5763 for (i = 0; i <= 50; i++)
5764 for (kk = 0; kk <= 100; kk+=4)
5765 for (ll = 0; ll <= 200; ll+=4)
5766 for (k = kk; k <= min (100, kk + 3); k++)
5767 for (l = ll; l <= min (200, ll + 3); l++)
5772 graphite_trans_bb_block (graphite_bb_p gb, int stride, int loops)
5775 int nb_loops = gbb_nb_loops (gb);
5776 int start = nb_loops - loops;
5777 scop_p scop = GBB_SCOP (gb);
5779 gcc_assert (scop_contains_loop (scop, gbb_loop (gb)));
5781 for (i = start ; i < nb_loops; i++)
5782 for (j = i + 1; j < nb_loops; j++)
5783 if (!is_interchange_valid (scop, i, j, nb_loops))
5785 if (dump_file && (dump_flags & TDF_DETAILS))
5787 "\nInterchange not valid for loops %d and %d:\n", i, j);
5790 else if (dump_file && (dump_flags & TDF_DETAILS))
5792 "\nInterchange valid for loops %d and %d:\n", i, j);
5794 /* Check if strip mining is profitable for every loop. */
5795 for (i = 0; i < nb_loops - start; i++)
5796 if (!strip_mine_profitable_p (gb, stride, start + i))
5799 /* Strip mine loops. */
5800 for (i = 0; i < nb_loops - start; i++)
5801 graphite_trans_bb_strip_mine (gb, start + 2 * i, stride);
5803 /* Interchange loops. */
5804 for (i = 1; i < nb_loops - start; i++)
5805 graphite_trans_bb_move_loop (gb, start + 2 * i, start + i);
5807 if (dump_file && (dump_flags & TDF_DETAILS))
5808 fprintf (dump_file, "\nLoops containing BB %d will be loop blocked.\n",
5809 GBB_BB (gb)->index);
5814 /* Loop block LOOPS innermost loops of a loop nest. BBS represent the
5815 basic blocks that belong to the loop nest to be blocked. */
5818 graphite_trans_loop_block (VEC (graphite_bb_p, heap) *bbs, int loops)
5822 bool transform_done = false;
5824 /* TODO: - Calculate the stride size automatically. */
5825 int stride_size = 64;
5827 for (i = 0; VEC_iterate (graphite_bb_p, bbs, i, gb); i++)
5828 transform_done |= graphite_trans_bb_block (gb, stride_size, loops);
5830 return transform_done;
5833 /* Loop block all basic blocks of SCOP. Return false when the
5834 transform is not performed. */
5837 graphite_trans_scop_block (scop_p scop)
5843 bool perfect = true;
5844 bool transform_done = false;
5846 VEC (graphite_bb_p, heap) *bbs = VEC_alloc (graphite_bb_p, heap, 3);
5847 int max_schedule = scop_max_loop_depth (scop) + 1;
5848 lambda_vector last_schedule = lambda_vector_new (max_schedule);
5850 if (VEC_length (graphite_bb_p, SCOP_BBS (scop)) == 0)
5853 /* Get the data of the first bb. */
5854 gb = VEC_index (graphite_bb_p, SCOP_BBS (scop), 0);
5855 last_nb_loops = gbb_nb_loops (gb);
5856 lambda_vector_copy (GBB_STATIC_SCHEDULE (gb), last_schedule,
5858 VEC_safe_push (graphite_bb_p, heap, bbs, gb);
5860 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
5862 /* We did the first bb before. */
5866 nb_loops = gbb_nb_loops (gb);
5868 /* If the number of loops is unchanged and only the last element of the
5869 schedule changes, we stay in the loop nest. */
5870 if (nb_loops == last_nb_loops
5871 && (last_schedule [nb_loops + 1]
5872 != GBB_STATIC_SCHEDULE (gb)[nb_loops + 1]))
5874 VEC_safe_push (graphite_bb_p, heap, bbs, gb);
5878 /* Otherwise, we left the innermost loop. So check, if the last bb was in
5879 a perfect loop nest and how many loops are contained in this perfect
5882 Count the number of zeros from the end of the schedule. They are the
5883 number of surrounding loops.
5886 last_bb 2 3 2 0 0 0 0 3
5890 last_bb 2 3 2 0 0 0 0 3
5894 If there is no zero, there were other bbs in outer loops and the loop
5895 nest is not perfect. */
5896 for (j = last_nb_loops - 1; j >= 0; j--)
5898 if (last_schedule [j] != 0
5899 || (j <= nb_loops && GBB_STATIC_SCHEDULE (gb)[j] == 1))
5908 /* Found perfect loop nest. */
5909 if (perfect && last_nb_loops - j >= 2)
5910 transform_done |= graphite_trans_loop_block (bbs, last_nb_loops - j);
5912 /* Check if we start with a new loop.
5916 last_bb 2 3 2 0 0 0 0 3
5919 Here we start with the loop "2 3 2 0 0 1"
5921 last_bb 2 3 2 0 0 0 0 3
5924 But here not, so the loop nest can never be perfect. */
5926 perfect = (GBB_STATIC_SCHEDULE (gb)[nb_loops] == 0);
5928 /* Update the last_bb infos. We do not do that for the bbs in the same
5929 loop, as the data we use is not changed. */
5930 last_nb_loops = nb_loops;
5931 lambda_vector_copy (GBB_STATIC_SCHEDULE (gb), last_schedule,
5933 VEC_truncate (graphite_bb_p, bbs, 0);
5934 VEC_safe_push (graphite_bb_p, heap, bbs, gb);
5937 /* Check if the last loop nest was perfect. It is the same check as above,
5938 but the comparison with the next bb is missing. */
5939 for (j = last_nb_loops - 1; j >= 0; j--)
5940 if (last_schedule [j] != 0)
5948 /* Found perfect loop nest. */
5949 if (last_nb_loops - j >= 2)
5950 transform_done |= graphite_trans_loop_block (bbs, last_nb_loops - j);
5951 VEC_free (graphite_bb_p, heap, bbs);
5953 return transform_done;
5956 /* Apply graphite transformations to all the basic blocks of SCOP. */
5959 graphite_apply_transformations (scop_p scop)
5961 bool transform_done = false;
5963 /* Sort the list of bbs. Keep them always sorted. */
5964 graphite_sort_gbbs (scop);
5966 if (flag_loop_block)
5967 transform_done = graphite_trans_scop_block (scop);
5969 /* Generate code even if we did not apply any real transformation.
5970 This also allows to check the performance for the identity
5971 transformation: GIMPLE -> GRAPHITE -> GIMPLE
5972 Keep in mind that CLooG optimizes in control, so the loop structure
5973 may change, even if we only use -fgraphite-identity. */
5974 if (flag_graphite_identity)
5975 transform_done = true;
5977 return transform_done;
5980 /* We limit all SCoPs to SCoPs, that are completely surrounded by a loop.
5990 * SCoP frontier, as this line is not surrounded by any loop. *
5994 This is necessary as scalar evolution and parameter detection need a
5995 outermost loop to initialize parameters correctly.
5997 TODO: FIX scalar evolution and parameter detection to allow more flexible
6003 VEC (sd_region, heap) *tmp_scops = VEC_alloc (sd_region, heap, 3);
6008 for (i = 0; VEC_iterate (scop_p, current_scops, i, scop); i++)
6012 build_scop_bbs (scop);
6014 if (!build_scop_loop_nests (scop))
6017 for (j = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), j, loop); j++)
6018 if (!loop_in_scop_p (loop_outer (loop), scop))
6020 sd_region open_scop;
6021 open_scop.entry = loop->header;
6022 open_scop.exit = single_exit (loop)->dest;
6023 VEC_safe_push (sd_region, heap, tmp_scops, &open_scop);
6027 free_scops (current_scops);
6028 current_scops = VEC_alloc (scop_p, heap, 3);
6030 create_sese_edges (tmp_scops);
6031 build_graphite_scops (tmp_scops);
6032 VEC_free (sd_region, heap, tmp_scops);
6035 /* Perform a set of linear transforms on the loops of the current
6039 graphite_transform_loops (void)
6044 if (number_of_loops () <= 1)
6047 current_scops = VEC_alloc (scop_p, heap, 3);
6048 recompute_all_dominators ();
6050 if (dump_file && (dump_flags & TDF_DETAILS))
6051 fprintf (dump_file, "Graphite loop transformations \n");
6053 initialize_original_copy_tables ();
6054 cloog_initialize ();
6058 if (dump_file && (dump_flags & TDF_DETAILS))
6059 fprintf (dump_file, "\nnumber of SCoPs: %d\n",
6060 VEC_length (scop_p, current_scops));
6062 for (i = 0; VEC_iterate (scop_p, current_scops, i, scop); i++)
6064 build_scop_bbs (scop);
6065 if (!build_scop_loop_nests (scop))
6068 build_bb_loops (scop);
6070 if (!build_scop_conditions (scop))
6073 find_scop_parameters (scop);
6074 build_scop_context (scop);
6076 if (dump_file && (dump_flags & TDF_DETAILS))
6078 fprintf (dump_file, "\n(In SCoP %d:\n", i);
6079 fprintf (dump_file, "\nnumber of bbs: %d\n",
6080 VEC_length (graphite_bb_p, SCOP_BBS (scop)));
6081 fprintf (dump_file, "\nnumber of loops: %d)\n",
6082 VEC_length (loop_p, SCOP_LOOP_NEST (scop)));
6085 if (!build_scop_iteration_domain (scop))
6088 add_conditions_to_constraints (scop);
6089 build_scop_canonical_schedules (scop);
6091 build_scop_data_accesses (scop);
6092 build_scop_dynamic_schedules (scop);
6094 if (dump_file && (dump_flags & TDF_DETAILS))
6096 int nbrefs = nb_data_refs_in_scop (scop);
6097 fprintf (dump_file, "\nnumber of data refs: %d\n", nbrefs);
6100 if (graphite_apply_transformations (scop))
6101 gloog (scop, find_transform (scop));
6102 #ifdef ENABLE_CHECKING
6105 struct clast_stmt *stmt = find_transform (scop);
6106 cloog_clast_free (stmt);
6112 cleanup_tree_cfg ();
6113 free_scops (current_scops);
6115 free_original_copy_tables ();
6118 #else /* If Cloog is not available: #ifndef HAVE_cloog. */
6121 graphite_transform_loops (void)
6123 sorry ("Graphite loop optimizations cannot be used");