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 /* Print GMP value V on stderr. */
69 value_print (stderr, "%4s\n", v);
72 /* Converts a GMP constant V to a tree and returns it. */
75 gmp_cst_to_tree (tree type, Value v)
77 return build_int_cst (type, value_get_si (v));
80 /* Debug the list of old induction variables for this SCOP. */
83 debug_oldivs (scop_p scop)
88 fprintf (stderr, "Old IVs:");
90 for (i = 0; VEC_iterate (name_tree, SCOP_OLDIVS (scop), i, oldiv); i++)
92 fprintf (stderr, "(");
93 print_generic_expr (stderr, oldiv->t, 0);
94 fprintf (stderr, ", %s, %d)\n", oldiv->name, oldiv->loop->num);
96 fprintf (stderr, "\n");
99 /* Debug the loops around basic block GB. */
102 debug_loop_vec (graphite_bb_p gb)
107 fprintf (stderr, "Loop Vec:");
109 for (i = 0; VEC_iterate (loop_p, GBB_LOOPS (gb), i, loop); i++)
110 fprintf (stderr, "%d: %d, ", i, loop ? loop->num : -1);
112 fprintf (stderr, "\n");
115 /* Returns true if stack ENTRY is a constant. */
118 iv_stack_entry_is_constant (iv_stack_entry *entry)
120 return entry->kind == iv_stack_entry_const;
123 /* Returns true if stack ENTRY is an induction variable. */
126 iv_stack_entry_is_iv (iv_stack_entry *entry)
128 return entry->kind == iv_stack_entry_iv;
131 /* Push (IV, NAME) on STACK. */
134 loop_iv_stack_push_iv (loop_iv_stack stack, tree iv, const char *name)
136 iv_stack_entry *entry = XNEW (iv_stack_entry);
137 name_tree named_iv = XNEW (struct name_tree);
140 named_iv->name = name;
142 entry->kind = iv_stack_entry_iv;
143 entry->data.iv = named_iv;
145 VEC_safe_push (iv_stack_entry_p, heap, *stack, entry);
148 /* Inserts a CONSTANT in STACK at INDEX. */
151 loop_iv_stack_insert_constant (loop_iv_stack stack, int index,
154 iv_stack_entry *entry = XNEW (iv_stack_entry);
156 entry->kind = iv_stack_entry_const;
157 entry->data.constant = constant;
159 VEC_safe_insert (iv_stack_entry_p, heap, *stack, index, entry);
162 /* Pops and frees an element out of STACK. */
165 loop_iv_stack_pop (loop_iv_stack stack)
167 iv_stack_entry_p entry = VEC_pop (iv_stack_entry_p, *stack);
169 free (entry->data.iv);
173 /* Get the IV at INDEX in STACK. */
176 loop_iv_stack_get_iv (loop_iv_stack stack, int index)
178 iv_stack_entry_p entry = VEC_index (iv_stack_entry_p, *stack, index);
179 iv_stack_entry_data data = entry->data;
181 return iv_stack_entry_is_iv (entry) ? data.iv->t : data.constant;
184 /* Get the IV from its NAME in STACK. */
187 loop_iv_stack_get_iv_from_name (loop_iv_stack stack, const char* name)
190 iv_stack_entry_p entry;
192 for (i = 0; VEC_iterate (iv_stack_entry_p, *stack, i, entry); i++)
194 name_tree iv = entry->data.iv;
195 if (!strcmp (name, iv->name))
202 /* Prints on stderr the contents of STACK. */
205 debug_loop_iv_stack (loop_iv_stack stack)
208 iv_stack_entry_p entry;
211 fprintf (stderr, "(");
213 for (i = 0; VEC_iterate (iv_stack_entry_p, *stack, i, entry); i++)
218 fprintf (stderr, " ");
220 if (iv_stack_entry_is_iv (entry))
222 name_tree iv = entry->data.iv;
223 fprintf (stderr, "%s:", iv->name);
224 print_generic_expr (stderr, iv->t, 0);
228 tree constant = entry->data.constant;
229 print_generic_expr (stderr, constant, 0);
230 fprintf (stderr, ":");
231 print_generic_expr (stderr, constant, 0);
235 fprintf (stderr, ")\n");
241 free_loop_iv_stack (loop_iv_stack stack)
244 iv_stack_entry_p entry;
246 for (i = 0; VEC_iterate (iv_stack_entry_p, *stack, i, entry); i++)
248 free (entry->data.iv);
252 VEC_free (iv_stack_entry_p, heap, *stack);
257 /* Structure containing the mapping between the CLooG's induction
258 variable and the type of the old induction variable. */
259 typedef struct ivtype_map_elt
262 const char *cloog_iv;
265 /* Print to stderr the element ELT. */
268 debug_ivtype_elt (ivtype_map_elt elt)
270 fprintf (stderr, "(%s, ", elt->cloog_iv);
271 print_generic_expr (stderr, elt->type, 0);
272 fprintf (stderr, ")\n");
275 /* Helper function for debug_ivtype_map. */
278 debug_ivtype_map_1 (void **slot, void *s ATTRIBUTE_UNUSED)
280 struct ivtype_map_elt *entry = (struct ivtype_map_elt *) *slot;
281 debug_ivtype_elt (entry);
285 /* Print to stderr all the elements of MAP. */
288 debug_ivtype_map (htab_t map)
290 htab_traverse (map, debug_ivtype_map_1, NULL);
293 /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */
295 static inline ivtype_map_elt
296 new_ivtype_map_elt (const char *cloog_iv, tree type)
300 res = XNEW (struct ivtype_map_elt);
301 res->cloog_iv = cloog_iv;
307 /* Computes a hash function for database element ELT. */
310 ivtype_map_elt_info (const void *elt)
312 return htab_hash_pointer (((const struct ivtype_map_elt *) elt)->cloog_iv);
315 /* Compares database elements E1 and E2. */
318 eq_ivtype_map_elts (const void *e1, const void *e2)
320 const struct ivtype_map_elt *elt1 = (const struct ivtype_map_elt *) e1;
321 const struct ivtype_map_elt *elt2 = (const struct ivtype_map_elt *) e2;
323 return (elt1->cloog_iv == elt2->cloog_iv);
328 /* Given a CLOOG_IV, returns the type that it should have in GCC land.
329 If the information is not available, i.e. in the case one of the
330 transforms created the loop, just return integer_type_node. */
333 gcc_type_for_cloog_iv (const char *cloog_iv, graphite_bb_p gbb)
335 struct ivtype_map_elt tmp;
338 tmp.cloog_iv = cloog_iv;
339 slot = htab_find_slot (GBB_CLOOG_IV_TYPES (gbb), &tmp, NO_INSERT);
342 return ((ivtype_map_elt) *slot)->type;
344 return integer_type_node;
347 /* Inserts constants derived from the USER_STMT argument list into the
348 STACK. This is needed to map old ivs to constants when loops have
352 loop_iv_stack_patch_for_consts (loop_iv_stack stack,
353 struct clast_user_stmt *user_stmt)
355 struct clast_stmt *t;
357 CloogStatement *cs = user_stmt->statement;
358 graphite_bb_p gbb = (graphite_bb_p) cloog_statement_usr (cs);
360 for (t = user_stmt->substitutions; t; t = t->next)
362 struct clast_expr *expr = (struct clast_expr *)
363 ((struct clast_assignment *)t)->RHS;
364 struct clast_term *term = (struct clast_term *) expr;
366 /* FIXME: What should be done with expr_bin, expr_red? */
367 if (expr->type == expr_term
370 loop_p loop = gbb_loop_at_index (gbb, index);
371 tree oldiv = oldiv_for_loop (GBB_SCOP (gbb), loop);
372 tree type = oldiv ? TREE_TYPE (oldiv) : integer_type_node;
373 tree value = gmp_cst_to_tree (type, term->val);
374 loop_iv_stack_insert_constant (stack, index, value);
380 /* Removes all constants in the iv STACK. */
383 loop_iv_stack_remove_constants (loop_iv_stack stack)
386 iv_stack_entry *entry;
388 for (i = 0; VEC_iterate (iv_stack_entry_p, *stack, i, entry);)
390 if (iv_stack_entry_is_constant (entry))
392 free (VEC_index (iv_stack_entry_p, *stack, i));
393 VEC_ordered_remove (iv_stack_entry_p, *stack, i);
400 /* Returns a new loop_to_cloog_loop_str structure. */
402 static inline struct loop_to_cloog_loop_str *
403 new_loop_to_cloog_loop_str (int loop_num,
405 CloogLoop *cloog_loop)
407 struct loop_to_cloog_loop_str *result;
409 result = XNEW (struct loop_to_cloog_loop_str);
410 result->loop_num = loop_num;
411 result->cloog_loop = cloog_loop;
412 result->loop_position = loop_position;
417 /* Hash function for SCOP_LOOP2CLOOG_LOOP hash table. */
420 hash_loop_to_cloog_loop (const void *elt)
422 return ((const struct loop_to_cloog_loop_str *) elt)->loop_num;
425 /* Equality function for SCOP_LOOP2CLOOG_LOOP hash table. */
428 eq_loop_to_cloog_loop (const void *el1, const void *el2)
430 const struct loop_to_cloog_loop_str *elt1, *elt2;
432 elt1 = (const struct loop_to_cloog_loop_str *) el1;
433 elt2 = (const struct loop_to_cloog_loop_str *) el2;
434 return elt1->loop_num == elt2->loop_num;
437 /* Compares two graphite bbs and returns an integer less than, equal to, or
438 greater than zero if the first argument is considered to be respectively
439 less than, equal to, or greater than the second.
440 We compare using the lexicographic order of the static schedules. */
443 gbb_compare (const void *p_1, const void *p_2)
445 const struct graphite_bb *const gbb_1
446 = *(const struct graphite_bb *const*) p_1;
447 const struct graphite_bb *const gbb_2
448 = *(const struct graphite_bb *const*) p_2;
450 return lambda_vector_compare (GBB_STATIC_SCHEDULE (gbb_1),
451 gbb_nb_loops (gbb_1) + 1,
452 GBB_STATIC_SCHEDULE (gbb_2),
453 gbb_nb_loops (gbb_2) + 1);
456 /* Sort graphite bbs in SCOP. */
459 graphite_sort_gbbs (scop_p scop)
461 VEC (graphite_bb_p, heap) *bbs = SCOP_BBS (scop);
463 qsort (VEC_address (graphite_bb_p, bbs),
464 VEC_length (graphite_bb_p, bbs),
465 sizeof (graphite_bb_p), gbb_compare);
468 /* Dump conditions of a graphite basic block GBB on FILE. */
471 dump_gbb_conditions (FILE *file, graphite_bb_p gbb)
475 VEC (gimple, heap) *conditions = GBB_CONDITIONS (gbb);
477 if (VEC_empty (gimple, conditions))
480 fprintf (file, "\tbb %d\t: cond = {", GBB_BB (gbb)->index);
482 for (i = 0; VEC_iterate (gimple, conditions, i, stmt); i++)
483 print_gimple_stmt (file, stmt, 0, 0);
485 fprintf (file, "}\n");
488 /* Converts the graphite scheduling function into a cloog scattering
489 matrix. This scattering matrix is used to limit the possible cloog
490 output to valid programs in respect to the scheduling function.
492 SCATTERING_DIMENSIONS specifies the dimensionality of the scattering
493 matrix. CLooG 0.14.0 and previous versions require, that all scattering
494 functions of one CloogProgram have the same dimensionality, therefore we
495 allow to specify it. (Should be removed in future versions) */
498 schedule_to_scattering (graphite_bb_p gb, int scattering_dimensions)
501 scop_p scop = GBB_SCOP (gb);
503 int nb_iterators = gbb_nb_loops (gb);
505 /* The cloog scattering matrix consists of these colums:
507 scattering_dimensions cols = Scattering dimensions,
508 nb_iterators cols = bb's iterators,
509 scop_nb_params cols = Parameters,
514 scattering_dimensions = 5
524 s1 s2 s3 s4 s5 i p1 p2 1
525 1 0 0 0 0 0 0 0 -4 = 0
526 0 1 0 0 0 -1 0 0 0 = 0
527 0 0 1 0 0 0 0 0 -5 = 0 */
528 int nb_params = scop_nb_params (scop);
529 int nb_cols = 1 + scattering_dimensions + nb_iterators + nb_params + 1;
530 int col_const = nb_cols - 1;
531 int col_iter_offset = 1 + scattering_dimensions;
533 CloogMatrix *scat = cloog_matrix_alloc (scattering_dimensions, nb_cols);
535 gcc_assert (scattering_dimensions >= nb_iterators * 2 + 1);
537 /* Initialize the identity matrix. */
538 for (i = 0; i < scattering_dimensions; i++)
539 value_set_si (scat->p[i][i + 1], 1);
541 /* Textual order outside the first loop */
542 value_set_si (scat->p[0][col_const], -GBB_STATIC_SCHEDULE (gb)[0]);
544 /* For all surrounding loops. */
545 for (i = 0; i < nb_iterators; i++)
547 int schedule = GBB_STATIC_SCHEDULE (gb)[i + 1];
549 /* Iterations of this loop. */
550 value_set_si (scat->p[2 * i + 1][col_iter_offset + i], -1);
552 /* Textual order inside this loop. */
553 value_set_si (scat->p[2 * i + 2][col_const], -schedule);
559 /* Print the schedules of GB to FILE with INDENT white spaces before.
560 VERBOSITY determines how verbose the code pretty printers are. */
563 print_graphite_bb (FILE *file, graphite_bb_p gb, int indent, int verbosity)
565 CloogMatrix *scattering;
568 fprintf (file, "\nGBB (\n");
570 print_loops_bb (file, GBB_BB (gb), indent+2, verbosity);
574 fprintf (file, " (domain: \n");
575 cloog_matrix_print (file, GBB_DOMAIN (gb));
576 fprintf (file, " )\n");
579 if (GBB_STATIC_SCHEDULE (gb))
581 fprintf (file, " (static schedule: ");
582 print_lambda_vector (file, GBB_STATIC_SCHEDULE (gb),
583 gbb_nb_loops (gb) + 1);
584 fprintf (file, " )\n");
589 fprintf (file, " (contained loops: \n");
590 for (i = 0; VEC_iterate (loop_p, GBB_LOOPS (gb), i, loop); i++)
592 fprintf (file, " iterator %d => NULL \n", i);
594 fprintf (file, " iterator %d => loop %d \n", i,
596 fprintf (file, " )\n");
599 if (GBB_DATA_REFS (gb))
600 dump_data_references (file, GBB_DATA_REFS (gb));
602 if (GBB_CONDITIONS (gb))
604 fprintf (file, " (conditions: \n");
605 dump_gbb_conditions (file, gb);
606 fprintf (file, " )\n");
610 && GBB_STATIC_SCHEDULE (gb))
612 fprintf (file, " (scattering: \n");
613 scattering = schedule_to_scattering (gb, 2 * gbb_nb_loops (gb) + 1);
614 cloog_matrix_print (file, scattering);
615 cloog_matrix_free (scattering);
616 fprintf (file, " )\n");
619 fprintf (file, ")\n");
622 /* Print to STDERR the schedules of GB with VERBOSITY level. */
625 debug_gbb (graphite_bb_p gb, int verbosity)
627 print_graphite_bb (stderr, gb, 0, verbosity);
631 /* Print SCOP to FILE. VERBOSITY determines how verbose the pretty
635 print_scop (FILE *file, scop_p scop, int verbosity)
640 fprintf (file, "\nSCoP_%d_%d (\n",
641 SCOP_ENTRY (scop)->index, SCOP_EXIT (scop)->index);
643 fprintf (file, " (cloog: \n");
644 cloog_program_print (file, SCOP_PROG (scop));
645 fprintf (file, " )\n");
652 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
653 print_graphite_bb (file, gb, 0, verbosity);
656 fprintf (file, ")\n");
659 /* Print all the SCOPs to FILE. VERBOSITY determines how verbose the
660 code pretty printers are. */
663 print_scops (FILE *file, int verbosity)
668 for (i = 0; VEC_iterate (scop_p, current_scops, i, scop); i++)
669 print_scop (file, scop, verbosity);
672 /* Debug SCOP. VERBOSITY determines how verbose the code pretty
676 debug_scop (scop_p scop, int verbosity)
678 print_scop (stderr, scop, verbosity);
681 /* Debug all SCOPs from CURRENT_SCOPS. VERBOSITY determines how
682 verbose the code pretty printers are. */
685 debug_scops (int verbosity)
687 print_scops (stderr, verbosity);
690 /* Pretty print to FILE the SCOP in DOT format. */
693 dot_scop_1 (FILE *file, scop_p scop)
698 basic_block entry = SCOP_ENTRY (scop);
699 basic_block exit = SCOP_EXIT (scop);
701 fprintf (file, "digraph SCoP_%d_%d {\n", entry->index,
707 fprintf (file, "%d [shape=triangle];\n", bb->index);
710 fprintf (file, "%d [shape=box];\n", bb->index);
712 if (bb_in_scop_p (bb, scop))
713 fprintf (file, "%d [color=red];\n", bb->index);
715 FOR_EACH_EDGE (e, ei, bb->succs)
716 fprintf (file, "%d -> %d;\n", bb->index, e->dest->index);
719 fputs ("}\n\n", file);
722 /* Display SCOP using dotty. */
725 dot_scop (scop_p scop)
727 dot_scop_1 (stderr, scop);
730 /* Pretty print all SCoPs in DOT format and mark them with different colors.
731 If there are not enough colors, paint later SCoPs gray.
733 - "*" after the node number: entry of a SCoP,
734 - "#" after the node number: exit of a SCoP,
735 - "()" entry or exit not part of SCoP. */
738 dot_all_scops_1 (FILE *file)
747 /* Disable debugging while printing graph. */
748 int tmp_dump_flags = dump_flags;
751 fprintf (file, "digraph all {\n");
755 int part_of_scop = false;
757 /* Use HTML for every bb label. So we are able to print bbs
758 which are part of two different SCoPs, with two different
759 background colors. */
760 fprintf (file, "%d [label=<\n <TABLE BORDER=\"0\" CELLBORDER=\"1\" ",
762 fprintf (file, "CELLSPACING=\"0\">\n");
764 /* Select color for SCoP. */
765 for (i = 0; VEC_iterate (scop_p, current_scops, i, scop); i++)
766 if (bb_in_scop_p (bb, scop)
767 || (SCOP_EXIT (scop) == bb)
768 || (SCOP_ENTRY (scop) == bb))
827 fprintf (file, " <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">", color);
829 if (!bb_in_scop_p (bb, scop))
830 fprintf (file, " (");
832 if (bb == SCOP_ENTRY (scop)
833 && bb == SCOP_EXIT (scop))
834 fprintf (file, " %d*# ", bb->index);
835 else if (bb == SCOP_ENTRY (scop))
836 fprintf (file, " %d* ", bb->index);
837 else if (bb == SCOP_EXIT (scop))
838 fprintf (file, " %d# ", bb->index);
840 fprintf (file, " %d ", bb->index);
842 if (!bb_in_scop_p (bb, scop))
845 fprintf (file, "</TD></TR>\n");
851 fprintf (file, " <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">");
852 fprintf (file, " %d </TD></TR>\n", bb->index);
855 fprintf (file, " </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n");
860 FOR_EACH_EDGE (e, ei, bb->succs)
861 fprintf (file, "%d -> %d;\n", bb->index, e->dest->index);
864 fputs ("}\n\n", file);
866 /* Enable debugging again. */
867 dump_flags = tmp_dump_flags;
870 /* Display all SCoPs using dotty. */
875 /* When debugging, enable the following code. This cannot be used
876 in production compilers because it calls "system". */
878 FILE *stream = fopen ("/tmp/allscops.dot", "w");
881 dot_all_scops_1 (stream);
884 system ("dotty /tmp/allscops.dot");
886 dot_all_scops_1 (stderr);
890 /* Returns the outermost loop in SCOP that contains BB. */
893 outermost_loop_in_scop (scop_p scop, basic_block bb)
897 nest = bb->loop_father;
898 while (loop_outer (nest) && loop_in_scop_p (loop_outer (nest), scop))
899 nest = loop_outer (nest);
904 /* Returns the block preceding the entry of SCOP. */
907 block_before_scop (scop_p scop)
909 return SESE_ENTRY (SCOP_REGION (scop))->src;
912 /* Return true when EXPR is an affine function in LOOP with parameters
913 instantiated relative to SCOP_ENTRY. */
916 loop_affine_expr (basic_block scop_entry, struct loop *loop, tree expr)
919 tree scev = analyze_scalar_evolution (loop, expr);
921 scev = instantiate_scev (scop_entry, loop, scev);
923 return (evolution_function_is_invariant_p (scev, n)
924 || evolution_function_is_affine_multivariate_p (scev, n));
927 /* Return false if the tree_code of the operand OP or any of its operands
931 exclude_component_ref (tree op)
938 if (TREE_CODE (op) == COMPONENT_REF)
942 len = TREE_OPERAND_LENGTH (op);
943 for (i = 0; i < len; ++i)
945 if (!exclude_component_ref (TREE_OPERAND (op, i)))
954 /* Return true if the operand OP is simple. */
957 is_simple_operand (loop_p loop, gimple stmt, tree op)
959 /* It is not a simple operand when it is a declaration, */
961 /* or a structure, */
962 || AGGREGATE_TYPE_P (TREE_TYPE (op))
963 /* or a memory access that cannot be analyzed by the data
964 reference analysis. */
965 || ((handled_component_p (op) || INDIRECT_REF_P (op))
966 && !stmt_simple_memref_p (loop, stmt, op)))
969 return exclude_component_ref (op);
972 /* Return true only when STMT is simple enough for being handled by
973 Graphite. This depends on SCOP_ENTRY, as the parametetrs are
974 initialized relatively to this basic block. */
977 stmt_simple_for_scop_p (basic_block scop_entry, gimple stmt)
979 basic_block bb = gimple_bb (stmt);
980 struct loop *loop = bb->loop_father;
982 /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
983 Calls have side-effects, except those to const or pure
985 if (gimple_has_volatile_ops (stmt)
986 || (gimple_code (stmt) == GIMPLE_CALL
987 && !(gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE)))
988 || (gimple_code (stmt) == GIMPLE_ASM))
991 switch (gimple_code (stmt))
1000 ssa_op_iter op_iter;
1001 enum tree_code code = gimple_cond_code (stmt);
1003 /* We can only handle this kind of conditional expressions.
1004 For inequalities like "if (i != 3 * k)" we need unions of
1005 polyhedrons. Expressions like "if (a)" or "if (a == 15)" need
1006 them for the else branch. */
1007 if (!(code == LT_EXPR
1010 || code == GE_EXPR))
1016 FOR_EACH_SSA_TREE_OPERAND (op, stmt, op_iter, SSA_OP_ALL_USES)
1017 if (!loop_affine_expr (scop_entry, loop, op))
1025 enum tree_code code = gimple_assign_rhs_code (stmt);
1027 switch (get_gimple_rhs_class (code))
1029 case GIMPLE_UNARY_RHS:
1030 case GIMPLE_SINGLE_RHS:
1031 return (is_simple_operand (loop, stmt, gimple_assign_lhs (stmt))
1032 && is_simple_operand (loop, stmt, gimple_assign_rhs1 (stmt)));
1034 case GIMPLE_BINARY_RHS:
1035 return (is_simple_operand (loop, stmt, gimple_assign_lhs (stmt))
1036 && is_simple_operand (loop, stmt, gimple_assign_rhs1 (stmt))
1037 && is_simple_operand (loop, stmt, gimple_assign_rhs2 (stmt)));
1039 case GIMPLE_INVALID_RHS:
1048 size_t n = gimple_call_num_args (stmt);
1049 tree lhs = gimple_call_lhs (stmt);
1051 for (i = 0; i < n; i++)
1053 tree arg = gimple_call_arg (stmt, i);
1055 if (!(is_simple_operand (loop, stmt, lhs)
1056 && is_simple_operand (loop, stmt, arg)))
1064 /* These nodes cut a new scope. */
1071 /* Returns the statement of BB that contains a harmful operation: that
1072 can be a function call with side effects, the induction variables
1073 are not linear with respect to SCOP_ENTRY, etc. The current open
1074 scop should end before this statement. */
1077 harmful_stmt_in_bb (basic_block scop_entry, basic_block bb)
1079 gimple_stmt_iterator gsi;
1081 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1082 if (!stmt_simple_for_scop_p (scop_entry, gsi_stmt (gsi)))
1083 return gsi_stmt (gsi);
1088 /* Returns true when BB will be represented in graphite. Return false
1089 for the basic blocks that contain code eliminated in the code
1090 generation pass: i.e. induction variables and exit conditions. */
1093 graphite_stmt_p (scop_p scop, basic_block bb,
1094 VEC (data_reference_p, heap) *drs)
1096 gimple_stmt_iterator gsi;
1097 loop_p loop = bb->loop_father;
1099 if (VEC_length (data_reference_p, drs) > 0)
1102 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1104 gimple stmt = gsi_stmt (gsi);
1106 switch (gimple_code (stmt))
1108 /* Control flow expressions can be ignored, as they are
1109 represented in the iteration domains and will be
1110 regenerated by graphite. */
1118 tree var = gimple_assign_lhs (stmt);
1119 var = analyze_scalar_evolution (loop, var);
1120 var = instantiate_scev (block_before_scop (scop), loop, var);
1122 if (chrec_contains_undetermined (var))
1136 /* Store the GRAPHITE representation of BB. */
1139 new_graphite_bb (scop_p scop, basic_block bb)
1141 struct graphite_bb *gbb;
1142 VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 5);
1143 struct loop *nest = outermost_loop_in_scop (scop, bb);
1144 gimple_stmt_iterator gsi;
1146 bitmap_set_bit (SCOP_BBS_B (scop), bb->index);
1148 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1149 find_data_references_in_stmt (nest, gsi_stmt (gsi), &drs);
1151 if (!graphite_stmt_p (scop, bb, drs))
1153 free_data_refs (drs);
1157 gbb = XNEW (struct graphite_bb);
1160 GBB_SCOP (gbb) = scop;
1161 GBB_DATA_REFS (gbb) = drs;
1162 GBB_DOMAIN (gbb) = NULL;
1163 GBB_CONDITIONS (gbb) = NULL;
1164 GBB_CONDITION_CASES (gbb) = NULL;
1165 GBB_LOOPS (gbb) = NULL;
1166 GBB_STATIC_SCHEDULE (gbb) = NULL;
1167 GBB_CLOOG_IV_TYPES (gbb) = NULL;
1168 VEC_safe_push (graphite_bb_p, heap, SCOP_BBS (scop), gbb);
1174 free_graphite_bb (struct graphite_bb *gbb)
1176 if (GBB_DOMAIN (gbb))
1177 cloog_matrix_free (GBB_DOMAIN (gbb));
1179 if (GBB_CLOOG_IV_TYPES (gbb))
1180 htab_delete (GBB_CLOOG_IV_TYPES (gbb));
1182 /* FIXME: free_data_refs is disabled for the moment, but should be
1185 free_data_refs (GBB_DATA_REFS (gbb)); */
1187 VEC_free (gimple, heap, GBB_CONDITIONS (gbb));
1188 VEC_free (gimple, heap, GBB_CONDITION_CASES (gbb));
1189 VEC_free (loop_p, heap, GBB_LOOPS (gbb));
1190 GBB_BB (gbb)->aux = 0;
1196 /* Structure containing the mapping between the old names and the new
1197 names used after block copy in the new loop context. */
1198 typedef struct rename_map_elt
1200 tree old_name, new_name;
1204 /* Print to stderr the element ELT. */
1207 debug_rename_elt (rename_map_elt elt)
1209 fprintf (stderr, "(");
1210 print_generic_expr (stderr, elt->old_name, 0);
1211 fprintf (stderr, ", ");
1212 print_generic_expr (stderr, elt->new_name, 0);
1213 fprintf (stderr, ")\n");
1216 /* Helper function for debug_rename_map. */
1219 debug_rename_map_1 (void **slot, void *s ATTRIBUTE_UNUSED)
1221 struct rename_map_elt *entry = (struct rename_map_elt *) *slot;
1222 debug_rename_elt (entry);
1226 /* Print to stderr all the elements of MAP. */
1229 debug_rename_map (htab_t map)
1231 htab_traverse (map, debug_rename_map_1, NULL);
1234 /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */
1236 static inline rename_map_elt
1237 new_rename_map_elt (tree old_name, tree new_name)
1241 res = XNEW (struct rename_map_elt);
1242 res->old_name = old_name;
1243 res->new_name = new_name;
1248 /* Computes a hash function for database element ELT. */
1251 rename_map_elt_info (const void *elt)
1253 return htab_hash_pointer (((const struct rename_map_elt *) elt)->old_name);
1256 /* Compares database elements E1 and E2. */
1259 eq_rename_map_elts (const void *e1, const void *e2)
1261 const struct rename_map_elt *elt1 = (const struct rename_map_elt *) e1;
1262 const struct rename_map_elt *elt2 = (const struct rename_map_elt *) e2;
1264 return (elt1->old_name == elt2->old_name);
1267 /* Returns the new name associated to OLD_NAME in MAP. */
1270 get_new_name_from_old_name (htab_t map, tree old_name)
1272 struct rename_map_elt tmp;
1275 tmp.old_name = old_name;
1276 slot = htab_find_slot (map, &tmp, NO_INSERT);
1279 return ((rename_map_elt) *slot)->new_name;
1286 /* Returns true when BB is in REGION. */
1289 bb_in_sese_p (basic_block bb, sese region)
1291 return pointer_set_contains (SESE_REGION_BBS (region), bb);
1294 /* For a USE in BB, if BB is outside REGION, mark the USE in the
1295 SESE_LIVEIN and SESE_LIVEOUT sets. */
1298 sese_build_livein_liveouts_use (sese region, basic_block bb, tree use)
1303 if (TREE_CODE (use) != SSA_NAME)
1306 ver = SSA_NAME_VERSION (use);
1307 def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
1309 || !bb_in_sese_p (def_bb, region)
1310 || bb_in_sese_p (bb, region))
1313 if (!SESE_LIVEIN_VER (region, ver))
1314 SESE_LIVEIN_VER (region, ver) = BITMAP_ALLOC (NULL);
1316 bitmap_set_bit (SESE_LIVEIN_VER (region, ver), bb->index);
1317 bitmap_set_bit (SESE_LIVEOUT (region), ver);
1320 /* Marks for rewrite all the SSA_NAMES defined in REGION and that are
1321 used in BB that is outside of the REGION. */
1324 sese_build_livein_liveouts_bb (sese region, basic_block bb)
1326 gimple_stmt_iterator bsi;
1332 FOR_EACH_EDGE (e, ei, bb->succs)
1333 for (bsi = gsi_start_phis (e->dest); !gsi_end_p (bsi); gsi_next (&bsi))
1334 sese_build_livein_liveouts_use (region, bb,
1335 PHI_ARG_DEF_FROM_EDGE (gsi_stmt (bsi), e));
1337 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
1338 FOR_EACH_SSA_TREE_OPERAND (var, gsi_stmt (bsi), iter, SSA_OP_ALL_USES)
1339 sese_build_livein_liveouts_use (region, bb, var);
1342 /* Build the SESE_LIVEIN and SESE_LIVEOUT for REGION. */
1345 sese_build_livein_liveouts (sese region)
1349 SESE_LIVEOUT (region) = BITMAP_ALLOC (NULL);
1350 SESE_NUM_VER (region) = num_ssa_names;
1351 SESE_LIVEIN (region) = XCNEWVEC (bitmap, SESE_NUM_VER (region));
1354 sese_build_livein_liveouts_bb (region, bb);
1357 /* Register basic blocks belonging to a region in a pointer set. */
1360 register_bb_in_sese (basic_block entry_bb, basic_block exit_bb, sese region)
1364 basic_block bb = entry_bb;
1366 FOR_EACH_EDGE (e, ei, bb->succs)
1368 if (!pointer_set_contains (SESE_REGION_BBS (region), e->dest) &&
1369 e->dest->index != exit_bb->index)
1371 pointer_set_insert (SESE_REGION_BBS (region), e->dest);
1372 register_bb_in_sese (e->dest, exit_bb, region);
1377 /* Builds a new SESE region from edges ENTRY and EXIT. */
1380 new_sese (edge entry, edge exit)
1382 sese res = XNEW (struct sese);
1384 SESE_ENTRY (res) = entry;
1385 SESE_EXIT (res) = exit;
1386 SESE_REGION_BBS (res) = pointer_set_create ();
1387 register_bb_in_sese (entry->dest, exit->dest, res);
1389 SESE_LIVEOUT (res) = NULL;
1390 SESE_NUM_VER (res) = 0;
1391 SESE_LIVEIN (res) = NULL;
1396 /* Deletes REGION. */
1399 free_sese (sese region)
1403 for (i = 0; i < SESE_NUM_VER (region); i++)
1404 BITMAP_FREE (SESE_LIVEIN_VER (region, i));
1406 if (SESE_LIVEIN (region))
1407 free (SESE_LIVEIN (region));
1409 if (SESE_LIVEOUT (region))
1410 BITMAP_FREE (SESE_LIVEOUT (region));
1412 pointer_set_destroy (SESE_REGION_BBS (region));
1418 /* Creates a new scop starting with ENTRY. */
1421 new_scop (edge entry, edge exit)
1423 scop_p scop = XNEW (struct scop);
1425 gcc_assert (entry && exit);
1427 SCOP_REGION (scop) = new_sese (entry, exit);
1428 SCOP_BBS (scop) = VEC_alloc (graphite_bb_p, heap, 3);
1429 SCOP_OLDIVS (scop) = VEC_alloc (name_tree, heap, 3);
1430 SCOP_BBS_B (scop) = BITMAP_ALLOC (NULL);
1431 SCOP_LOOPS (scop) = BITMAP_ALLOC (NULL);
1432 SCOP_LOOP_NEST (scop) = VEC_alloc (loop_p, heap, 3);
1433 SCOP_ADD_PARAMS (scop) = true;
1434 SCOP_PARAMS (scop) = VEC_alloc (name_tree, heap, 3);
1435 SCOP_PROG (scop) = cloog_program_malloc ();
1436 cloog_program_set_names (SCOP_PROG (scop), cloog_names_malloc ());
1437 SCOP_LOOP2CLOOG_LOOP (scop) = htab_create (10, hash_loop_to_cloog_loop,
1438 eq_loop_to_cloog_loop,
1440 SCOP_LIVEOUT_RENAMES (scop) = htab_create (10, rename_map_elt_info,
1441 eq_rename_map_elts, free);
1448 free_scop (scop_p scop)
1452 struct graphite_bb *gb;
1455 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
1456 free_graphite_bb (gb);
1458 VEC_free (graphite_bb_p, heap, SCOP_BBS (scop));
1459 BITMAP_FREE (SCOP_BBS_B (scop));
1460 BITMAP_FREE (SCOP_LOOPS (scop));
1461 VEC_free (loop_p, heap, SCOP_LOOP_NEST (scop));
1463 for (i = 0; VEC_iterate (name_tree, SCOP_OLDIVS (scop), i, iv); i++)
1465 VEC_free (name_tree, heap, SCOP_OLDIVS (scop));
1467 for (i = 0; VEC_iterate (name_tree, SCOP_PARAMS (scop), i, p); i++)
1470 VEC_free (name_tree, heap, SCOP_PARAMS (scop));
1471 cloog_program_free (SCOP_PROG (scop));
1472 htab_delete (SCOP_LOOP2CLOOG_LOOP (scop));
1473 htab_delete (SCOP_LIVEOUT_RENAMES (scop));
1474 free_sese (SCOP_REGION (scop));
1478 /* Deletes all scops in SCOPS. */
1481 free_scops (VEC (scop_p, heap) *scops)
1486 for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++)
1489 VEC_free (scop_p, heap, scops);
1492 typedef enum gbb_type {
1494 GBB_LOOP_SING_EXIT_HEADER,
1495 GBB_LOOP_MULT_EXIT_HEADER,
1502 /* Detect the type of BB. Loop headers are only marked, if they are
1503 new. This means their loop_father is different to LAST_LOOP.
1504 Otherwise they are treated like any other bb and their type can be
1508 get_bb_type (basic_block bb, struct loop *last_loop)
1510 VEC (basic_block, heap) *dom;
1512 struct loop *loop = bb->loop_father;
1514 /* Check, if we entry into a new loop. */
1515 if (loop != last_loop)
1517 if (single_exit (loop) != NULL)
1518 return GBB_LOOP_SING_EXIT_HEADER;
1519 else if (loop->num != 0)
1520 return GBB_LOOP_MULT_EXIT_HEADER;
1522 return GBB_COND_HEADER;
1525 dom = get_dominated_by (CDI_DOMINATORS, bb);
1526 nb_dom = VEC_length (basic_block, dom);
1527 VEC_free (basic_block, heap, dom);
1532 nb_suc = VEC_length (edge, bb->succs);
1534 if (nb_dom == 1 && nb_suc == 1)
1537 return GBB_COND_HEADER;
1540 /* A SCoP detection region, defined using bbs as borders.
1541 All control flow touching this region, comes in passing basic_block ENTRY and
1542 leaves passing basic_block EXIT. By using bbs instead of edges for the
1543 borders we are able to represent also regions that do not have a single
1545 But as they have a single entry basic_block and a single exit basic_block, we
1546 are able to generate for every sd_region a single entry and exit edge.
1553 / \ This region contains: {3, 4, 5, 6, 7, 8}
1561 typedef struct sd_region_p
1563 /* The entry bb dominates all bbs in the sd_region. It is part of the
1567 /* The exit bb postdominates all bbs in the sd_region, but is not
1568 part of the region. */
1572 DEF_VEC_O(sd_region);
1573 DEF_VEC_ALLOC_O(sd_region, heap);
1576 /* Moves the scops from SOURCE to TARGET and clean up SOURCE. */
1579 move_sd_regions (VEC (sd_region, heap) **source, VEC (sd_region, heap) **target)
1584 for (i = 0; VEC_iterate (sd_region, *source, i, s); i++)
1585 VEC_safe_push (sd_region, heap, *target, s);
1587 VEC_free (sd_region, heap, *source);
1590 /* Return true when it is not possible to represent the upper bound of
1591 LOOP in the polyhedral representation. */
1594 graphite_cannot_represent_loop_niter (loop_p loop)
1596 tree niter = number_of_latch_executions (loop);
1598 return chrec_contains_undetermined (niter)
1599 || !scev_is_linear_expression (niter);
1601 /* Store information needed by scopdet_* functions. */
1605 /* Where the last open scop would stop if the current BB is harmful. */
1608 /* Where the next scop would start if the current BB is harmful. */
1611 /* The bb or one of its children contains open loop exits. That means
1612 loop exit nodes that are not surrounded by a loop dominated by bb. */
1615 /* The bb or one of its children contains only structures we can handle. */
1620 static struct scopdet_info build_scops_1 (basic_block, VEC (sd_region, heap) **,
1623 /* Calculates BB infos. If bb is difficult we add valid SCoPs dominated by BB
1624 to SCOPS. TYPE is the gbb_type of BB. */
1626 static struct scopdet_info
1627 scopdet_basic_block_info (basic_block bb, VEC (sd_region, heap) **scops,
1630 struct loop *loop = bb->loop_father;
1631 struct scopdet_info result;
1634 /* XXX: ENTRY_BLOCK_PTR could be optimized in later steps. */
1635 stmt = harmful_stmt_in_bb (ENTRY_BLOCK_PTR, bb);
1636 result.difficult = (stmt != NULL);
1643 result.exits = false;
1648 result.next = single_succ (bb);
1649 result.exits = false;
1653 case GBB_LOOP_SING_EXIT_HEADER:
1655 VEC (sd_region, heap) *tmp_scops = VEC_alloc (sd_region, heap,3);
1656 struct scopdet_info sinfo;
1658 sinfo = build_scops_1 (bb, &tmp_scops, loop);
1660 result.last = single_exit (bb->loop_father)->src;
1661 result.next = single_exit (bb->loop_father)->dest;
1663 /* If we do not dominate result.next, remove it. It's either
1664 the EXIT_BLOCK_PTR, or another bb dominates it and will
1665 call the scop detection for this bb. */
1666 if (!dominated_by_p (CDI_DOMINATORS, result.next, bb))
1669 if (result.last->loop_father != loop)
1672 if (graphite_cannot_represent_loop_niter (loop))
1673 result.difficult = true;
1675 if (sinfo.difficult)
1676 move_sd_regions (&tmp_scops, scops);
1678 VEC_free (sd_region, heap, tmp_scops);
1680 result.exits = false;
1681 result.difficult |= sinfo.difficult;
1685 case GBB_LOOP_MULT_EXIT_HEADER:
1687 /* XXX: For now we just do not join loops with multiple exits. If the
1688 exits lead to the same bb it may be possible to join the loop. */
1689 VEC (sd_region, heap) *tmp_scops = VEC_alloc (sd_region, heap, 3);
1690 VEC (edge, heap) *exits = get_loop_exit_edges (loop);
1693 build_scops_1 (bb, &tmp_scops, loop);
1695 /* Scan the code dominated by this loop. This means all bbs, that are
1696 are dominated by a bb in this loop, but are not part of this loop.
1699 - The loop exit destination is dominated by the exit sources.
1701 TODO: We miss here the more complex cases:
1702 - The exit destinations are dominated by another bb inside the
1704 - The loop dominates bbs, that are not exit destinations. */
1705 for (i = 0; VEC_iterate (edge, exits, i, e); i++)
1706 if (e->src->loop_father == loop
1707 && dominated_by_p (CDI_DOMINATORS, e->dest, e->src))
1709 /* Pass loop_outer to recognize e->dest as loop header in
1711 if (e->dest->loop_father->header == e->dest)
1712 build_scops_1 (e->dest, &tmp_scops,
1713 loop_outer (e->dest->loop_father));
1715 build_scops_1 (e->dest, &tmp_scops, e->dest->loop_father);
1720 result.difficult = true;
1721 result.exits = false;
1722 move_sd_regions (&tmp_scops, scops);
1723 VEC_free (edge, heap, exits);
1726 case GBB_COND_HEADER:
1728 VEC (sd_region, heap) *tmp_scops = VEC_alloc (sd_region, heap, 3);
1729 struct scopdet_info sinfo;
1730 VEC (basic_block, heap) *dominated;
1733 basic_block last_bb = NULL;
1735 result.exits = false;
1737 /* First check the successors of BB, and check if it is possible to join
1738 the different branches. */
1739 for (i = 0; VEC_iterate (edge, bb->succs, i, e); i++)
1741 /* Ignore loop exits. They will be handled after the loop body. */
1742 if (is_loop_exit (loop, e->dest))
1744 result.exits = true;
1748 /* Do not follow edges that lead to the end of the
1749 conditions block. For example, in
1759 the edge from 0 => 6. Only check if all paths lead to
1762 if (!single_pred_p (e->dest))
1764 /* Check, if edge leads directly to the end of this
1771 if (e->dest != last_bb)
1772 result.difficult = true;
1777 if (!dominated_by_p (CDI_DOMINATORS, e->dest, bb))
1779 result.difficult = true;
1783 sinfo = build_scops_1 (e->dest, &tmp_scops, loop);
1785 result.exits |= sinfo.exits;
1786 result.last = sinfo.last;
1787 result.difficult |= sinfo.difficult;
1789 /* Checks, if all branches end at the same point.
1790 If that is true, the condition stays joinable.
1791 Have a look at the example above. */
1792 if (sinfo.last && single_succ_p (sinfo.last))
1794 basic_block next_tmp = single_succ (sinfo.last);
1799 if (next_tmp != last_bb)
1800 result.difficult = true;
1803 result.difficult = true;
1806 /* If the condition is joinable. */
1807 if (!result.exits && !result.difficult)
1809 /* Only return a next pointer if we dominate this pointer.
1810 Otherwise it will be handled by the bb dominating it. */
1811 if (dominated_by_p (CDI_DOMINATORS, last_bb, bb) && last_bb != bb)
1812 result.next = last_bb;
1816 VEC_free (sd_region, heap, tmp_scops);
1820 /* Scan remaining bbs dominated by BB. */
1821 dominated = get_dominated_by (CDI_DOMINATORS, bb);
1823 for (i = 0; VEC_iterate (basic_block, dominated, i, dom_bb); i++)
1825 /* Ignore loop exits: they will be handled after the loop body. */
1826 if (loop_depth (find_common_loop (loop, dom_bb->loop_father))
1827 < loop_depth (loop))
1829 result.exits = true;
1833 /* Ignore the bbs processed above. */
1834 if (single_pred_p (dom_bb) && single_pred (dom_bb) == bb)
1837 if (loop_depth (loop) > loop_depth (dom_bb->loop_father))
1838 sinfo = build_scops_1 (dom_bb, &tmp_scops, loop_outer (loop));
1840 sinfo = build_scops_1 (dom_bb, &tmp_scops, loop);
1843 result.exits |= sinfo.exits;
1844 result.difficult = true;
1848 VEC_free (basic_block, heap, dominated);
1851 move_sd_regions (&tmp_scops, scops);
1863 /* Creates the SCoPs and writes entry and exit points for every SCoP. */
1865 static struct scopdet_info
1866 build_scops_1 (basic_block current, VEC (sd_region, heap) **scops, loop_p loop)
1868 bool in_scop = false;
1869 sd_region open_scop;
1870 struct scopdet_info sinfo;
1872 /* Initialize result. */
1873 struct scopdet_info result;
1874 result.exits = false;
1875 result.difficult = false;
1878 open_scop.entry = NULL;
1879 open_scop.exit = NULL;
1882 /* Loop over the dominance tree. If we meet a difficult bb, close
1883 the current SCoP. Loop and condition header start a new layer,
1884 and can only be added if all bbs in deeper layers are simple. */
1885 while (current != NULL)
1887 sinfo = scopdet_basic_block_info (current, scops, get_bb_type (current,
1890 if (!in_scop && !(sinfo.exits || sinfo.difficult))
1892 open_scop.entry = current;
1893 open_scop.exit = NULL;
1896 else if (in_scop && (sinfo.exits || sinfo.difficult))
1898 open_scop.exit = current;
1899 VEC_safe_push (sd_region, heap, *scops, &open_scop);
1903 result.difficult |= sinfo.difficult;
1904 result.exits |= sinfo.exits;
1906 current = sinfo.next;
1909 /* Try to close open_scop, if we are still in an open SCoP. */
1915 for (i = 0; VEC_iterate (edge, sinfo.last->succs, i, e); i++)
1916 if (dominated_by_p (CDI_POST_DOMINATORS, sinfo.last, e->dest))
1917 open_scop.exit = e->dest;
1919 if (!open_scop.exit && open_scop.entry != sinfo.last)
1920 open_scop.exit = sinfo.last;
1923 VEC_safe_push (sd_region, heap, *scops, &open_scop);
1927 result.last = sinfo.last;
1931 /* Checks if a bb is contained in REGION. */
1934 bb_in_sd_region (basic_block bb, sd_region *region)
1936 return dominated_by_p (CDI_DOMINATORS, bb, region->entry)
1937 && !(dominated_by_p (CDI_DOMINATORS, bb, region->exit)
1938 && !dominated_by_p (CDI_DOMINATORS, region->entry,
1942 /* Returns the single entry edge of REGION, if it does not exits NULL. */
1945 find_single_entry_edge (sd_region *region)
1951 FOR_EACH_EDGE (e, ei, region->entry->preds)
1952 if (!bb_in_sd_region (e->src, region))
1967 /* Returns the single exit edge of REGION, if it does not exits NULL. */
1970 find_single_exit_edge (sd_region *region)
1976 FOR_EACH_EDGE (e, ei, region->exit->preds)
1977 if (bb_in_sd_region (e->src, region))
1992 /* Create a single entry edge for REGION. */
1995 create_single_entry_edge (sd_region *region)
1997 if (find_single_entry_edge (region))
2000 /* There are multiple predecessors for bb_3
2013 There are two edges (1->3, 2->3), that point from outside into the region,
2014 and another one (5->3), a loop latch, lead to bb_3.
2022 | |\ (3.0 -> 3.1) = single entry edge
2031 If the loop is part of the SCoP, we have to redirect the loop latches.
2037 | | (3.0 -> 3.1) = entry edge
2046 if (region->entry->loop_father->header != region->entry
2047 || dominated_by_p (CDI_DOMINATORS,
2048 loop_latch_edge (region->entry->loop_father)->src,
2051 edge forwarder = split_block_after_labels (region->entry);
2052 region->entry = forwarder->dest;
2055 /* This case is never executed, as the loop headers seem always to have a
2056 single edge pointing from outside into the loop. */
2059 #ifdef ENABLE_CHECKING
2060 gcc_assert (find_single_entry_edge (region));
2064 /* Check if the sd_region, mentioned in EDGE, has no exit bb. */
2067 sd_region_without_exit (edge e)
2069 sd_region *r = (sd_region *) e->aux;
2072 return r->exit == NULL;
2077 /* Create a single exit edge for REGION. */
2080 create_single_exit_edge (sd_region *region)
2084 edge forwarder = NULL;
2087 if (find_single_exit_edge (region))
2090 /* We create a forwarder bb (5) for all edges leaving this region
2091 (3->5, 4->5). All other edges leading to the same bb, are moved
2092 to a new bb (6). If these edges where part of another region (2->5)
2093 we update the region->exit pointer, of this region.
2095 To identify which edge belongs to which region we depend on the e->aux
2096 pointer in every edge. It points to the region of the edge or to NULL,
2097 if the edge is not part of any region.
2099 1 2 3 4 1->5 no region, 2->5 region->exit = 5,
2100 \| |/ 3->5 region->exit = NULL, 4->5 region->exit = NULL
2105 1 2 3 4 1->6 no region, 2->6 region->exit = 6,
2106 | | \/ 3->5 no region, 4->5 no region,
2108 \| / 5->6 region->exit = 6
2111 Now there is only a single exit edge (5->6). */
2112 exit = region->exit;
2113 region->exit = NULL;
2114 forwarder = make_forwarder_block (exit, &sd_region_without_exit, NULL);
2116 /* Unmark the edges, that are no longer exit edges. */
2117 FOR_EACH_EDGE (e, ei, forwarder->src->preds)
2121 /* Mark the new exit edge. */
2122 single_succ_edge (forwarder->src)->aux = region;
2124 /* Update the exit bb of all regions, where exit edges lead to
2126 FOR_EACH_EDGE (e, ei, forwarder->dest->preds)
2128 ((sd_region *) e->aux)->exit = forwarder->dest;
2130 #ifdef ENABLE_CHECKING
2131 gcc_assert (find_single_exit_edge (region));
2135 /* Unmark the exit edges of all REGIONS.
2136 See comment in "create_single_exit_edge". */
2139 unmark_exit_edges (VEC (sd_region, heap) *regions)
2146 for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
2147 FOR_EACH_EDGE (e, ei, s->exit->preds)
2152 /* Mark the exit edges of all REGIONS.
2153 See comment in "create_single_exit_edge". */
2156 mark_exit_edges (VEC (sd_region, heap) *regions)
2163 for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
2164 FOR_EACH_EDGE (e, ei, s->exit->preds)
2165 if (bb_in_sd_region (e->src, s))
2169 /* Free and compute again all the dominators information. */
2172 recompute_all_dominators (void)
2174 mark_irreducible_loops ();
2175 free_dominance_info (CDI_DOMINATORS);
2176 free_dominance_info (CDI_POST_DOMINATORS);
2177 calculate_dominance_info (CDI_DOMINATORS);
2178 calculate_dominance_info (CDI_POST_DOMINATORS);
2181 /* Verifies properties that GRAPHITE should maintain during translation. */
2184 graphite_verify (void)
2186 #ifdef ENABLE_CHECKING
2187 verify_loop_structure ();
2188 verify_dominators (CDI_DOMINATORS);
2189 verify_dominators (CDI_POST_DOMINATORS);
2194 /* Create for all scop regions a single entry and a single exit edge. */
2197 create_sese_edges (VEC (sd_region, heap) *regions)
2202 for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
2203 create_single_entry_edge (s);
2205 mark_exit_edges (regions);
2207 for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
2208 create_single_exit_edge (s);
2210 unmark_exit_edges (regions);
2212 fix_loop_structure (NULL);
2214 #ifdef ENABLE_CHECKING
2215 verify_loop_structure ();
2216 verify_dominators (CDI_DOMINATORS);
2221 /* Create graphite SCoPs from an array of scop detection regions. */
2224 build_graphite_scops (VEC (sd_region, heap) *scop_regions)
2229 for (i = 0; VEC_iterate (sd_region, scop_regions, i, s); i++)
2231 edge entry = find_single_entry_edge (s);
2232 edge exit = find_single_exit_edge (s);
2233 scop_p scop = new_scop (entry, exit);
2234 VEC_safe_push (scop_p, heap, current_scops, scop);
2236 /* Are there overlapping SCoPs? */
2237 #ifdef ENABLE_CHECKING
2242 for (j = 0; VEC_iterate (sd_region, scop_regions, j, s2); j++)
2244 gcc_assert (!bb_in_sd_region (s->entry, s2));
2250 /* Find static control parts. */
2255 struct loop *loop = current_loops->tree_root;
2256 VEC (sd_region, heap) *tmp_scops = VEC_alloc (sd_region, heap, 3);
2258 build_scops_1 (single_succ (ENTRY_BLOCK_PTR), &tmp_scops, loop);
2259 create_sese_edges (tmp_scops);
2260 build_graphite_scops (tmp_scops);
2261 VEC_free (sd_region, heap, tmp_scops);
2264 /* Gather the basic blocks belonging to the SCOP. */
2267 build_scop_bbs (scop_p scop)
2269 basic_block *stack = XNEWVEC (basic_block, n_basic_blocks + 1);
2270 sbitmap visited = sbitmap_alloc (last_basic_block);
2273 sbitmap_zero (visited);
2274 stack[sp++] = SCOP_ENTRY (scop);
2278 basic_block bb = stack[--sp];
2279 int depth = loop_depth (bb->loop_father);
2280 int num = bb->loop_father->num;
2284 /* Scop's exit is not in the scop. Exclude also bbs, which are
2285 dominated by the SCoP exit. These are e.g. loop latches. */
2286 if (TEST_BIT (visited, bb->index)
2287 || dominated_by_p (CDI_DOMINATORS, bb, SCOP_EXIT (scop))
2288 /* Every block in the scop is dominated by scop's entry. */
2289 || !dominated_by_p (CDI_DOMINATORS, bb, SCOP_ENTRY (scop)))
2292 new_graphite_bb (scop, bb);
2293 SET_BIT (visited, bb->index);
2295 /* First push the blocks that have to be processed last. Note
2296 that this means that the order in which the code is organized
2297 below is important: do not reorder the following code. */
2298 FOR_EACH_EDGE (e, ei, bb->succs)
2299 if (! TEST_BIT (visited, e->dest->index)
2300 && (int) loop_depth (e->dest->loop_father) < depth)
2301 stack[sp++] = e->dest;
2303 FOR_EACH_EDGE (e, ei, bb->succs)
2304 if (! TEST_BIT (visited, e->dest->index)
2305 && (int) loop_depth (e->dest->loop_father) == depth
2306 && e->dest->loop_father->num != num)
2307 stack[sp++] = e->dest;
2309 FOR_EACH_EDGE (e, ei, bb->succs)
2310 if (! TEST_BIT (visited, e->dest->index)
2311 && (int) loop_depth (e->dest->loop_father) == depth
2312 && e->dest->loop_father->num == num
2313 && EDGE_COUNT (e->dest->preds) > 1)
2314 stack[sp++] = e->dest;
2316 FOR_EACH_EDGE (e, ei, bb->succs)
2317 if (! TEST_BIT (visited, e->dest->index)
2318 && (int) loop_depth (e->dest->loop_father) == depth
2319 && e->dest->loop_father->num == num
2320 && EDGE_COUNT (e->dest->preds) == 1)
2321 stack[sp++] = e->dest;
2323 FOR_EACH_EDGE (e, ei, bb->succs)
2324 if (! TEST_BIT (visited, e->dest->index)
2325 && (int) loop_depth (e->dest->loop_father) > depth)
2326 stack[sp++] = e->dest;
2330 sbitmap_free (visited);
2333 /* Returns the number of reduction phi nodes in LOOP. */
2336 nb_reductions_in_loop (loop_p loop)
2339 gimple_stmt_iterator gsi;
2341 for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
2343 gimple phi = gsi_stmt (gsi);
2347 if (!is_gimple_reg (PHI_RESULT (phi)))
2350 scev = analyze_scalar_evolution (loop, PHI_RESULT (phi));
2351 scev = instantiate_parameters (loop, scev);
2352 if (!simple_iv (loop, phi, PHI_RESULT (phi), &iv, true))
2359 /* A LOOP is in normal form when it contains only one scalar phi node
2360 that defines the main induction variable of the loop, only one
2361 increment of the IV, and only one exit condition. */
2364 graphite_loop_normal_form (loop_p loop)
2366 struct tree_niter_desc niter;
2369 edge exit = single_dom_exit (loop);
2371 gcc_assert (number_of_iterations_exit (loop, exit, &niter, false));
2372 nit = force_gimple_operand (unshare_expr (niter.niter), &stmts, true,
2375 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
2377 /* One IV per loop. */
2378 if (nb_reductions_in_loop (loop) > 0)
2381 return canonicalize_loop_ivs (loop, NULL, nit);
2384 /* Record LOOP as occuring in SCOP. Returns true when the operation
2388 scop_record_loop (scop_p scop, loop_p loop)
2393 if (bitmap_bit_p (SCOP_LOOPS (scop), loop->num))
2396 bitmap_set_bit (SCOP_LOOPS (scop), loop->num);
2397 VEC_safe_push (loop_p, heap, SCOP_LOOP_NEST (scop), loop);
2399 induction_var = graphite_loop_normal_form (loop);
2403 oldiv = XNEW (struct name_tree);
2404 oldiv->t = induction_var;
2405 oldiv->name = get_name (SSA_NAME_VAR (oldiv->t));
2407 VEC_safe_push (name_tree, heap, SCOP_OLDIVS (scop), oldiv);
2411 /* Build the loop nests contained in SCOP. Returns true when the
2412 operation was successful. */
2415 build_scop_loop_nests (scop_p scop)
2419 struct loop *loop0, *loop1;
2422 if (bb_in_scop_p (bb, scop))
2424 struct loop *loop = bb->loop_father;
2426 /* Only add loops if they are completely contained in the SCoP. */
2427 if (loop->header == bb
2428 && bb_in_scop_p (loop->latch, scop))
2430 if (!scop_record_loop (scop, loop))
2435 /* Make sure that the loops in the SCOP_LOOP_NEST are ordered. It
2436 can be the case that an inner loop is inserted before an outer
2437 loop. To avoid this, semi-sort once. */
2438 for (i = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), i, loop0); i++)
2440 if (VEC_length (loop_p, SCOP_LOOP_NEST (scop)) == i + 1)
2443 loop1 = VEC_index (loop_p, SCOP_LOOP_NEST (scop), i + 1);
2444 if (loop0->num > loop1->num)
2446 VEC_replace (loop_p, SCOP_LOOP_NEST (scop), i, loop1);
2447 VEC_replace (loop_p, SCOP_LOOP_NEST (scop), i + 1, loop0);
2454 /* Build dynamic schedules for all the BBs. */
2457 build_scop_dynamic_schedules (scop_p scop)
2459 int i, dim, loop_num, row, col;
2462 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
2464 loop_num = GBB_BB (gb)->loop_father->num;
2468 dim = nb_loops_around_gb (gb);
2469 GBB_DYNAMIC_SCHEDULE (gb) = cloog_matrix_alloc (dim, dim);
2471 for (row = 0; row < GBB_DYNAMIC_SCHEDULE (gb)->NbRows; row++)
2472 for (col = 0; col < GBB_DYNAMIC_SCHEDULE (gb)->NbColumns; col++)
2474 value_set_si (GBB_DYNAMIC_SCHEDULE (gb)->p[row][col], 1);
2476 value_set_si (GBB_DYNAMIC_SCHEDULE (gb)->p[row][col], 0);
2479 GBB_DYNAMIC_SCHEDULE (gb) = NULL;
2483 /* Build for BB the static schedule.
2485 The STATIC_SCHEDULE is defined like this:
2504 Static schedules for A to F:
2517 build_scop_canonical_schedules (scop_p scop)
2521 int nb = scop_nb_loops (scop) + 1;
2523 SCOP_STATIC_SCHEDULE (scop) = lambda_vector_new (nb);
2525 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
2527 int offset = nb_loops_around_gb (gb);
2529 /* After leaving a loop, it is possible that the schedule is not
2530 set at zero. This loop reinitializes components located
2533 for (j = offset + 1; j < nb; j++)
2534 if (SCOP_STATIC_SCHEDULE (scop)[j])
2536 memset (&(SCOP_STATIC_SCHEDULE (scop)[j]), 0,
2537 sizeof (int) * (nb - j));
2538 ++SCOP_STATIC_SCHEDULE (scop)[offset];
2542 GBB_STATIC_SCHEDULE (gb) = lambda_vector_new (offset + 1);
2543 lambda_vector_copy (SCOP_STATIC_SCHEDULE (scop),
2544 GBB_STATIC_SCHEDULE (gb), offset + 1);
2546 ++SCOP_STATIC_SCHEDULE (scop)[offset];
2550 /* Build the LOOPS vector for all bbs in SCOP. */
2553 build_bb_loops (scop_p scop)
2558 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
2563 depth = nb_loops_around_gb (gb) - 1;
2565 GBB_LOOPS (gb) = VEC_alloc (loop_p, heap, 3);
2566 VEC_safe_grow_cleared (loop_p, heap, GBB_LOOPS (gb), depth + 1);
2568 loop = GBB_BB (gb)->loop_father;
2570 while (scop_contains_loop (scop, loop))
2572 VEC_replace (loop_p, GBB_LOOPS (gb), depth, loop);
2573 loop = loop_outer (loop);
2579 /* Get the index for parameter VAR in SCOP. */
2582 param_index (tree var, scop_p scop)
2588 gcc_assert (TREE_CODE (var) == SSA_NAME);
2590 for (i = 0; VEC_iterate (name_tree, SCOP_PARAMS (scop), i, p); i++)
2594 gcc_assert (SCOP_ADD_PARAMS (scop));
2596 nvar = XNEW (struct name_tree);
2599 VEC_safe_push (name_tree, heap, SCOP_PARAMS (scop), nvar);
2600 return VEC_length (name_tree, SCOP_PARAMS (scop)) - 1;
2603 /* Scan EXPR and translate it to an inequality vector INEQ that will
2604 be added, or subtracted, in the constraint domain matrix C at row
2605 R. K is the number of columns for loop iterators in C. */
2608 scan_tree_for_params (scop_p s, tree e, CloogMatrix *c, int r, Value k,
2611 int cst_col, param_col;
2613 if (e == chrec_dont_know)
2616 switch (TREE_CODE (e))
2618 case POLYNOMIAL_CHREC:
2620 tree left = CHREC_LEFT (e);
2621 tree right = CHREC_RIGHT (e);
2622 int var = CHREC_VARIABLE (e);
2624 if (TREE_CODE (right) != INTEGER_CST)
2629 int loop_col = scop_gimple_loop_depth (s, get_loop (var)) + 1;
2632 value_sub_int (c->p[r][loop_col], c->p[r][loop_col],
2633 int_cst_value (right));
2635 value_add_int (c->p[r][loop_col], c->p[r][loop_col],
2636 int_cst_value (right));
2639 switch (TREE_CODE (left))
2641 case POLYNOMIAL_CHREC:
2642 scan_tree_for_params (s, left, c, r, k, subtract);
2646 /* Constant part. */
2649 int v = int_cst_value (left);
2650 cst_col = c->NbColumns - 1;
2655 subtract = subtract ? false : true;
2659 value_sub_int (c->p[r][cst_col], c->p[r][cst_col], v);
2661 value_add_int (c->p[r][cst_col], c->p[r][cst_col], v);
2666 scan_tree_for_params (s, left, c, r, k, subtract);
2673 if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
2678 gcc_assert (host_integerp (TREE_OPERAND (e, 1), 0));
2680 value_set_si (val, int_cst_value (TREE_OPERAND (e, 1)));
2681 value_multiply (k, k, val);
2684 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
2691 gcc_assert (host_integerp (TREE_OPERAND (e, 0), 0));
2693 value_set_si (val, int_cst_value (TREE_OPERAND (e, 0)));
2694 value_multiply (k, k, val);
2697 scan_tree_for_params (s, TREE_OPERAND (e, 1), c, r, k, subtract);
2702 case POINTER_PLUS_EXPR:
2703 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
2704 scan_tree_for_params (s, TREE_OPERAND (e, 1), c, r, k, subtract);
2708 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
2709 value_oppose (k, k);
2710 scan_tree_for_params (s, TREE_OPERAND (e, 1), c, r, k, subtract);
2714 value_oppose (k, k);
2715 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
2719 param_col = param_index (e, s);
2723 param_col += c->NbColumns - scop_nb_params (s) - 1;
2726 value_subtract (c->p[r][param_col], c->p[r][param_col], k);
2728 value_addto (c->p[r][param_col], c->p[r][param_col], k);
2735 int v = int_cst_value (e);
2736 cst_col = c->NbColumns - 1;
2741 subtract = subtract ? false : true;
2745 value_sub_int (c->p[r][cst_col], c->p[r][cst_col], v);
2747 value_add_int (c->p[r][cst_col], c->p[r][cst_col], v);
2752 case NON_LVALUE_EXPR:
2753 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
2762 /* Data structure for idx_record_params. */
2770 /* For a data reference with an ARRAY_REF as its BASE, record the
2771 parameters occurring in IDX. DTA is passed in as complementary
2772 information, and is used by the automatic walker function. This
2773 function is a callback for for_each_index. */
2776 idx_record_params (tree base, tree *idx, void *dta)
2778 struct irp_data *data = (struct irp_data *) dta;
2780 if (TREE_CODE (base) != ARRAY_REF)
2783 if (TREE_CODE (*idx) == SSA_NAME)
2786 scop_p scop = data->scop;
2787 struct loop *loop = data->loop;
2790 scev = analyze_scalar_evolution (loop, *idx);
2791 scev = instantiate_scev (block_before_scop (scop), loop, scev);
2794 value_set_si (one, 1);
2795 scan_tree_for_params (scop, scev, NULL, 0, one, false);
2802 /* Find parameters with respect to SCOP in BB. We are looking in memory
2803 access functions, conditions and loop bounds. */
2806 find_params_in_bb (scop_p scop, graphite_bb_p gb)
2809 data_reference_p dr;
2811 loop_p father = GBB_BB (gb)->loop_father;
2813 for (i = 0; VEC_iterate (data_reference_p, GBB_DATA_REFS (gb), i, dr); i++)
2815 struct irp_data irp;
2819 for_each_index (&dr->ref, idx_record_params, &irp);
2822 /* Find parameters in conditional statements. */
2823 for (i = 0; VEC_iterate (gimple, GBB_CONDITIONS (gb), i, stmt); i++)
2826 loop_p loop = father;
2830 lhs = gimple_cond_lhs (stmt);
2831 lhs = analyze_scalar_evolution (loop, lhs);
2832 lhs = instantiate_scev (block_before_scop (scop), loop, lhs);
2834 rhs = gimple_cond_rhs (stmt);
2835 rhs = analyze_scalar_evolution (loop, rhs);
2836 rhs = instantiate_scev (block_before_scop (scop), loop, rhs);
2839 scan_tree_for_params (scop, lhs, NULL, 0, one, false);
2840 value_set_si (one, 1);
2841 scan_tree_for_params (scop, rhs, NULL, 0, one, false);
2846 /* Saves in NV the name of variable P->T. */
2849 save_var_name (char **nv, int i, name_tree p)
2851 const char *name = get_name (SSA_NAME_VAR (p->t));
2855 int len = strlen (name) + 16;
2856 nv[i] = XNEWVEC (char, len);
2857 snprintf (nv[i], len, "%s_%d", name, SSA_NAME_VERSION (p->t));
2861 nv[i] = XNEWVEC (char, 16);
2862 snprintf (nv[i], 2 + 16, "T_%d", SSA_NAME_VERSION (p->t));
2868 /* Return the maximal loop depth in SCOP. */
2871 scop_max_loop_depth (scop_p scop)
2875 int max_nb_loops = 0;
2877 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gbb); i++)
2879 int nb_loops = gbb_nb_loops (gbb);
2880 if (max_nb_loops < nb_loops)
2881 max_nb_loops = nb_loops;
2884 return max_nb_loops;
2887 /* Initialize Cloog's parameter names from the names used in GIMPLE.
2888 Initialize Cloog's iterator names, using 'graphite_iterator_%d'
2889 from 0 to scop_nb_loops (scop). */
2892 initialize_cloog_names (scop_p scop)
2894 int i, nb_params = VEC_length (name_tree, SCOP_PARAMS (scop));
2895 char **params = XNEWVEC (char *, nb_params);
2896 int nb_iterators = scop_max_loop_depth (scop);
2897 int nb_scattering= cloog_program_nb_scattdims (SCOP_PROG (scop));
2898 char **iterators = XNEWVEC (char *, nb_iterators * 2);
2899 char **scattering = XNEWVEC (char *, nb_scattering);
2902 for (i = 0; VEC_iterate (name_tree, SCOP_PARAMS (scop), i, p); i++)
2903 save_var_name (params, i, p);
2905 cloog_names_set_nb_parameters (cloog_program_names (SCOP_PROG (scop)),
2907 cloog_names_set_parameters (cloog_program_names (SCOP_PROG (scop)),
2910 for (i = 0; i < nb_iterators; i++)
2913 iterators[i] = XNEWVEC (char, len);
2914 snprintf (iterators[i], len, "graphite_iterator_%d", i);
2917 cloog_names_set_nb_iterators (cloog_program_names (SCOP_PROG (scop)),
2919 cloog_names_set_iterators (cloog_program_names (SCOP_PROG (scop)),
2922 for (i = 0; i < nb_scattering; i++)
2925 scattering[i] = XNEWVEC (char, len);
2926 snprintf (scattering[i], len, "s_%d", i);
2929 cloog_names_set_nb_scattering (cloog_program_names (SCOP_PROG (scop)),
2931 cloog_names_set_scattering (cloog_program_names (SCOP_PROG (scop)),
2935 /* Record the parameters used in the SCOP. A variable is a parameter
2936 in a scop if it does not vary during the execution of that scop. */
2939 find_scop_parameters (scop_p scop)
2947 value_set_si (one, 1);
2949 /* Find the parameters used in the loop bounds. */
2950 for (i = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), i, loop); i++)
2952 tree nb_iters = number_of_latch_executions (loop);
2954 if (!chrec_contains_symbols (nb_iters))
2957 nb_iters = analyze_scalar_evolution (loop, nb_iters);
2958 nb_iters = instantiate_scev (block_before_scop (scop), loop, nb_iters);
2959 scan_tree_for_params (scop, nb_iters, NULL, 0, one, false);
2964 /* Find the parameters used in data accesses. */
2965 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
2966 find_params_in_bb (scop, gb);
2968 SCOP_ADD_PARAMS (scop) = false;
2971 /* Build the context constraints for SCOP: constraints and relations
2975 build_scop_context (scop_p scop)
2977 int nb_params = scop_nb_params (scop);
2978 CloogMatrix *matrix = cloog_matrix_alloc (1, nb_params + 2);
2980 /* Insert '0 >= 0' in the context matrix, as it is not allowed to be
2983 value_set_si (matrix->p[0][0], 1);
2985 value_set_si (matrix->p[0][nb_params + 1], 0);
2987 cloog_program_set_context (SCOP_PROG (scop),
2988 cloog_domain_matrix2domain (matrix));
2989 cloog_matrix_free (matrix);
2992 /* Returns a graphite_bb from BB. */
2994 static inline graphite_bb_p
2995 gbb_from_bb (basic_block bb)
2997 return (graphite_bb_p) bb->aux;
3000 /* Builds the constraint matrix for LOOP in SCOP. NB_OUTER_LOOPS is the
3001 number of loops surrounding LOOP in SCOP. OUTER_CSTR gives the
3002 constraints matrix for the surrounding loops. */
3005 build_loop_iteration_domains (scop_p scop, struct loop *loop,
3006 CloogMatrix *outer_cstr, int nb_outer_loops)
3012 int nb_rows = outer_cstr->NbRows + 1;
3013 int nb_cols = outer_cstr->NbColumns + 1;
3015 /* Last column of CSTR is the column of constants. */
3016 int cst_col = nb_cols - 1;
3018 /* The column for the current loop is just after the columns of
3019 other outer loops. */
3020 int loop_col = nb_outer_loops + 1;
3022 tree nb_iters = number_of_latch_executions (loop);
3024 /* When the number of iterations is a constant or a parameter, we
3025 add a constraint for the upper bound of the loop. So add a row
3026 to the constraint matrix before allocating it. */
3027 if (TREE_CODE (nb_iters) == INTEGER_CST
3028 || !chrec_contains_undetermined (nb_iters))
3031 cstr = cloog_matrix_alloc (nb_rows, nb_cols);
3033 /* Copy the outer constraints. */
3034 for (i = 0; i < outer_cstr->NbRows; i++)
3036 /* Copy the eq/ineq and loops columns. */
3037 for (j = 0; j < loop_col; j++)
3038 value_assign (cstr->p[i][j], outer_cstr->p[i][j]);
3040 /* Leave an empty column in CSTR for the current loop, and then
3041 copy the parameter columns. */
3042 for (j = loop_col; j < outer_cstr->NbColumns; j++)
3043 value_assign (cstr->p[i][j + 1], outer_cstr->p[i][j]);
3047 row = outer_cstr->NbRows;
3048 value_set_si (cstr->p[row][0], 1);
3049 value_set_si (cstr->p[row][loop_col], 1);
3051 /* loop_i <= nb_iters */
3052 if (TREE_CODE (nb_iters) == INTEGER_CST)
3055 value_set_si (cstr->p[row][0], 1);
3056 value_set_si (cstr->p[row][loop_col], -1);
3058 value_set_si (cstr->p[row][cst_col],
3059 int_cst_value (nb_iters));
3061 else if (!chrec_contains_undetermined (nb_iters))
3063 /* Otherwise nb_iters contains parameters: scan the nb_iters
3064 expression and build its matrix representation. */
3068 value_set_si (cstr->p[row][0], 1);
3069 value_set_si (cstr->p[row][loop_col], -1);
3071 nb_iters = analyze_scalar_evolution (loop, nb_iters);
3072 nb_iters = instantiate_scev (block_before_scop (scop), loop, nb_iters);
3075 value_set_si (one, 1);
3076 scan_tree_for_params (scop, nb_iters, cstr, row, one, false);
3082 if (loop->inner && loop_in_scop_p (loop->inner, scop))
3083 build_loop_iteration_domains (scop, loop->inner, cstr, nb_outer_loops + 1);
3085 /* Only go to the next loops, if we are not at the outermost layer. These
3086 have to be handled seperately, as we can be sure, that the chain at this
3087 layer will be connected. */
3088 if (nb_outer_loops != 0 && loop->next && loop_in_scop_p (loop->next, scop))
3089 build_loop_iteration_domains (scop, loop->next, outer_cstr, nb_outer_loops);
3091 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
3092 if (gbb_loop (gb) == loop)
3093 GBB_DOMAIN (gb) = cloog_matrix_copy (cstr);
3095 cloog_matrix_free (cstr);
3098 /* Add conditions to the domain of GB. */
3101 add_conditions_to_domain (graphite_bb_p gb)
3105 VEC (gimple, heap) *conditions = GBB_CONDITIONS (gb);
3106 CloogMatrix *domain = GBB_DOMAIN (gb);
3107 scop_p scop = GBB_SCOP (gb);
3111 unsigned nb_new_rows = 0;
3114 if (VEC_empty (gimple, conditions))
3119 nb_rows = domain->NbRows;
3120 nb_cols = domain->NbColumns;
3125 nb_cols = scop_nb_params (scop) + 2;
3128 /* Count number of necessary new rows to add the conditions to the
3130 for (i = 0; VEC_iterate (gimple, conditions, i, stmt); i++)
3132 switch (gimple_code (stmt))
3136 enum tree_code code = gimple_cond_code (stmt);
3142 /* NE and EQ statements are not supported right know. */
3158 /* Switch statements are not supported right know. */
3169 /* Enlarge the matrix. */
3171 CloogMatrix *new_domain;
3172 new_domain = cloog_matrix_alloc (nb_rows + nb_new_rows, nb_cols);
3174 for (i = 0; i < nb_rows; i++)
3175 for (j = 0; j < nb_cols; j++)
3176 value_assign (new_domain->p[i][j], domain->p[i][j]);
3178 cloog_matrix_free (domain);
3179 domain = new_domain;
3180 GBB_DOMAIN (gb) = new_domain;
3183 /* Add the conditions to the new enlarged domain matrix. */
3185 for (i = 0; VEC_iterate (gimple, conditions, i, stmt); i++)
3187 switch (gimple_code (stmt))
3192 enum tree_code code;
3195 loop_p loop = GBB_BB (gb)->loop_father;
3197 left = gimple_cond_lhs (stmt);
3198 right = gimple_cond_rhs (stmt);
3200 left = analyze_scalar_evolution (loop, left);
3201 right = analyze_scalar_evolution (loop, right);
3203 left = instantiate_scev (block_before_scop (scop), loop, left);
3204 right = instantiate_scev (block_before_scop (scop), loop, right);
3206 code = gimple_cond_code (stmt);
3208 /* The conditions for ELSE-branches are inverted. */
3209 if (VEC_index (gimple, gb->condition_cases, i) == NULL)
3210 code = invert_tree_comparison (code, false);
3215 /* NE statements are not supported right know. */
3219 value_set_si (domain->p[row][0], 1);
3221 value_set_si (one, 1);
3222 scan_tree_for_params (scop, left, domain, row, one, true);
3223 value_set_si (one, 1);
3224 scan_tree_for_params (scop, right, domain, row, one, false);
3226 value_set_si (domain->p[row][0], 1);
3227 value_set_si (one, 1);
3228 scan_tree_for_params (scop, left, domain, row, one, false);
3229 value_set_si (one, 1);
3230 scan_tree_for_params (scop, right, domain, row, one, true);
3235 value_set_si (domain->p[row][0], 1);
3237 value_set_si (one, 1);
3238 scan_tree_for_params (scop, left, domain, row, one, true);
3239 value_set_si (one, 1);
3240 scan_tree_for_params (scop, right, domain, row, one, false);
3241 value_sub_int (domain->p[row][nb_cols - 1],
3242 domain->p[row][nb_cols - 1], 1);
3247 value_set_si (domain->p[row][0], 1);
3249 value_set_si (one, 1);
3250 scan_tree_for_params (scop, left, domain, row, one, false);
3251 value_set_si (one, 1);
3252 scan_tree_for_params (scop, right, domain, row, one, true);
3253 value_sub_int (domain->p[row][nb_cols - 1],
3254 domain->p[row][nb_cols - 1], 1);
3259 value_set_si (domain->p[row][0], 1);
3261 value_set_si (one, 1);
3262 scan_tree_for_params (scop, left, domain, row, one, true);
3263 value_set_si (one, 1);
3264 scan_tree_for_params (scop, right, domain, row, one, false);
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, false);
3273 value_set_si (one, 1);
3274 scan_tree_for_params (scop, right, domain, row, one, true);
3285 /* Switch statements are not supported right know. */
3296 /* Returns true when PHI defines an induction variable in the loop
3297 containing the PHI node. */
3300 phi_node_is_iv (gimple phi)
3302 loop_p loop = gimple_bb (phi)->loop_father;
3303 tree scev = analyze_scalar_evolution (loop, gimple_phi_result (phi));
3305 return tree_contains_chrecs (scev, NULL);
3308 /* Returns true when BB contains scalar phi nodes that are not an
3309 induction variable of a loop. */
3312 bb_contains_non_iv_scalar_phi_nodes (basic_block bb)
3315 gimple_stmt_iterator si;
3317 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
3318 if (is_gimple_reg (gimple_phi_result (gsi_stmt (si))))
3320 /* Store the unique scalar PHI node: at this point, loops
3321 should be in cannonical form, so we expect to see at most
3322 one scalar phi node in the loop header. */
3324 || bb != bb->loop_father->header)
3327 phi = gsi_stmt (si);
3331 || phi_node_is_iv (phi))
3337 /* Helper recursive function. Record in CONDITIONS and CASES all
3338 conditions from 'if's and 'switch'es occurring in BB from SCOP.
3340 Returns false when the conditions contain scalar computations that
3341 depend on the condition, i.e. when there are scalar phi nodes on
3342 the junction after the condition. Only the computations occurring
3343 on memory can be handled in the polyhedral model: operations that
3344 define scalar evolutions in conditions, that can potentially be
3345 used to index memory, can't be handled by the polyhedral model. */
3348 build_scop_conditions_1 (VEC (gimple, heap) **conditions,
3349 VEC (gimple, heap) **cases, basic_block bb,
3355 gimple_stmt_iterator gsi;
3356 basic_block bb_child, bb_iter;
3357 VEC (basic_block, heap) *dom;
3359 /* Make sure we are in the SCoP. */
3360 if (!bb_in_scop_p (bb, scop))
3363 if (bb_contains_non_iv_scalar_phi_nodes (bb))
3366 gbb = gbb_from_bb (bb);
3369 GBB_CONDITIONS (gbb) = VEC_copy (gimple, heap, *conditions);
3370 GBB_CONDITION_CASES (gbb) = VEC_copy (gimple, heap, *cases);
3371 add_conditions_to_domain (gbb);
3374 dom = get_dominated_by (CDI_DOMINATORS, bb);
3376 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3378 gimple stmt = gsi_stmt (gsi);
3379 VEC (edge, gc) *edges;
3382 switch (gimple_code (stmt))
3386 for (i = 0; VEC_iterate (edge, edges, i, e); i++)
3387 if ((dominated_by_p (CDI_DOMINATORS, e->dest, bb))
3388 && VEC_length (edge, e->dest->preds) == 1)
3390 /* Remove the scanned block from the dominator successors. */
3391 for (j = 0; VEC_iterate (basic_block, dom, j, bb_iter); j++)
3392 if (bb_iter == e->dest)
3394 VEC_unordered_remove (basic_block, dom, j);
3398 /* Recursively scan the then or else part. */
3399 if (e->flags & EDGE_TRUE_VALUE)
3400 VEC_safe_push (gimple, heap, *cases, stmt);
3403 gcc_assert (e->flags & EDGE_FALSE_VALUE);
3404 VEC_safe_push (gimple, heap, *cases, NULL);
3407 VEC_safe_push (gimple, heap, *conditions, stmt);
3408 if (!build_scop_conditions_1 (conditions, cases, e->dest, scop))
3413 VEC_pop (gimple, *conditions);
3414 VEC_pop (gimple, *cases);
3421 gimple_stmt_iterator gsi_search_gimple_label;
3423 for (i = 0; i < gimple_switch_num_labels (stmt); ++i)
3425 basic_block bb_iter;
3427 size_t n_cases = VEC_length (gimple, *conditions);
3428 unsigned n = gimple_switch_num_labels (stmt);
3430 bb_child = label_to_block
3431 (CASE_LABEL (gimple_switch_label (stmt, i)));
3433 for (k = 0; k < n; k++)
3436 (CASE_LABEL (gimple_switch_label (stmt, k))) == bb_child)
3439 /* Switches with multiple case values for the same
3440 block are not handled. */
3442 /* Switch cases with more than one predecessor are
3444 || VEC_length (edge, bb_child->preds) != 1)
3450 /* Recursively scan the corresponding 'case' block. */
3451 for (gsi_search_gimple_label = gsi_start_bb (bb_child);
3452 !gsi_end_p (gsi_search_gimple_label);
3453 gsi_next (&gsi_search_gimple_label))
3455 gimple label = gsi_stmt (gsi_search_gimple_label);
3457 if (gimple_code (label) == GIMPLE_LABEL)
3459 tree t = gimple_label_label (label);
3461 gcc_assert (t == gimple_switch_label (stmt, i));
3462 VEC_replace (gimple, *cases, n_cases, label);
3467 if (!build_scop_conditions_1 (conditions, cases, bb_child, scop))
3473 /* Remove the scanned block from the dominator successors. */
3474 for (j = 0; VEC_iterate (basic_block, dom, j, bb_iter); j++)
3475 if (bb_iter == bb_child)
3477 VEC_unordered_remove (basic_block, dom, j);
3482 VEC_pop (gimple, *conditions);
3483 VEC_pop (gimple, *cases);
3492 /* Scan all immediate dominated successors. */
3493 for (i = 0; VEC_iterate (basic_block, dom, i, bb_child); i++)
3494 if (!build_scop_conditions_1 (conditions, cases, bb_child, scop))
3501 VEC_free (basic_block, heap, dom);
3505 /* Record all conditions from SCOP.
3507 Returns false when the conditions contain scalar computations that
3508 depend on the condition, i.e. when there are scalar phi nodes on
3509 the junction after the condition. Only the computations occurring
3510 on memory can be handled in the polyhedral model: operations that
3511 define scalar evolutions in conditions, that can potentially be
3512 used to index memory, can't be handled by the polyhedral model. */
3515 build_scop_conditions (scop_p scop)
3518 VEC (gimple, heap) *conditions = NULL;
3519 VEC (gimple, heap) *cases = NULL;
3521 res = build_scop_conditions_1 (&conditions, &cases, SCOP_ENTRY (scop), scop);
3523 VEC_free (gimple, heap, conditions);
3524 VEC_free (gimple, heap, cases);
3528 /* Build the current domain matrix: the loops belonging to the current
3529 SCOP, and that vary for the execution of the current basic block.
3530 Returns false if there is no loop in SCOP. */
3533 build_scop_iteration_domain (scop_p scop)
3536 CloogMatrix *outer_cstr;
3539 /* Build cloog loop for all loops, that are in the uppermost loop layer of
3541 for (i = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), i, loop); i++)
3542 if (!loop_in_scop_p (loop_outer (loop), scop))
3544 /* The outermost constraints is a matrix that has:
3545 -first column: eq/ineq boolean
3546 -last column: a constant
3547 -scop_nb_params columns for the parameters used in the scop. */
3548 outer_cstr = cloog_matrix_alloc (0, scop_nb_params (scop) + 2);
3549 build_loop_iteration_domains (scop, loop, outer_cstr, 0);
3550 cloog_matrix_free (outer_cstr);
3556 /* Initializes an equation CY of the access matrix using the
3557 information for a subscript from AF, relatively to the loop
3558 indexes from LOOP_NEST and parameter indexes from PARAMS. NDIM is
3559 the dimension of the array access, i.e. the number of
3560 subscripts. Returns true when the operation succeeds. */
3563 build_access_matrix_with_af (tree af, lambda_vector cy,
3564 scop_p scop, int ndim)
3568 switch (TREE_CODE (af))
3570 case POLYNOMIAL_CHREC:
3572 struct loop *outer_loop;
3573 tree left = CHREC_LEFT (af);
3574 tree right = CHREC_RIGHT (af);
3577 if (TREE_CODE (right) != INTEGER_CST)
3580 outer_loop = get_loop (CHREC_VARIABLE (af));
3581 var = nb_loops_around_loop_in_scop (outer_loop, scop);
3582 cy[var] = int_cst_value (right);
3584 switch (TREE_CODE (left))
3586 case POLYNOMIAL_CHREC:
3587 return build_access_matrix_with_af (left, cy, scop, ndim);
3590 cy[ndim - 1] = int_cst_value (left);
3594 return build_access_matrix_with_af (left, cy, scop, ndim);
3599 build_access_matrix_with_af (TREE_OPERAND (af, 0), cy, scop, ndim);
3600 build_access_matrix_with_af (TREE_OPERAND (af, 1), cy, scop, ndim);
3604 build_access_matrix_with_af (TREE_OPERAND (af, 0), cy, scop, ndim);
3605 build_access_matrix_with_af (TREE_OPERAND (af, 1), cy, scop, ndim);
3609 cy[ndim - 1] = int_cst_value (af);
3613 param_col = param_index (af, scop);
3614 cy [ndim - scop_nb_params (scop) + param_col - 1] = 1;
3618 /* FIXME: access_fn can have parameters. */
3623 /* Initialize the access matrix in the data reference REF with respect
3624 to the loop nesting LOOP_NEST. Return true when the operation
3628 build_access_matrix (data_reference_p ref, graphite_bb_p gb)
3630 int i, ndim = DR_NUM_DIMENSIONS (ref);
3631 struct access_matrix *am = GGC_NEW (struct access_matrix);
3633 AM_MATRIX (am) = VEC_alloc (lambda_vector, gc, ndim);
3634 DR_SCOP (ref) = GBB_SCOP (gb);
3636 for (i = 0; i < ndim; i++)
3638 lambda_vector v = lambda_vector_new (ref_nb_loops (ref));
3639 scop_p scop = GBB_SCOP (gb);
3640 tree af = DR_ACCESS_FN (ref, i);
3642 if (!build_access_matrix_with_af (af, v, scop, ref_nb_loops (ref)))
3645 VEC_quick_push (lambda_vector, AM_MATRIX (am), v);
3648 DR_ACCESS_MATRIX (ref) = am;
3652 /* Build the access matrices for the data references in the SCOP. */
3655 build_scop_data_accesses (scop_p scop)
3660 /* FIXME: Construction of access matrix is disabled until some
3661 pass, like the data dependence analysis, is using it. */
3664 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
3667 data_reference_p dr;
3669 /* Construct the access matrix for each data ref, with respect to
3670 the loop nest of the current BB in the considered SCOP. */
3672 VEC_iterate (data_reference_p, GBB_DATA_REFS (gb), j, dr);
3675 bool res = build_access_matrix (dr, gb);
3677 /* FIXME: At this point the DRs should always have an affine
3678 form. For the moment this fails as build_access_matrix
3679 does not build matrices with parameters. */
3685 /* Returns the tree variable from the name NAME that was given in
3686 Cloog representation. All the parameters are stored in PARAMS, and
3687 all the loop induction variables are stored in IVSTACK.
3689 FIXME: This is a hack, and Cloog should be fixed to not work with
3690 variable names represented as "char *string", but with void
3691 pointers that could be casted back to a tree. The only problem in
3692 doing that is that Cloog's pretty printer still assumes that
3693 variable names are char *strings. The solution would be to have a
3694 function pointer for pretty-printing that can be redirected to be
3695 print_generic_stmt in our case, or fprintf by default.
3696 ??? Too ugly to live. */
3699 clast_name_to_gcc (const char *name, VEC (name_tree, heap) *params,
3700 loop_iv_stack ivstack)
3707 for (i = 0; VEC_iterate (name_tree, params, i, t); i++)
3708 if (!strcmp (name, t->name))
3711 iv = loop_iv_stack_get_iv_from_name (ivstack, name);
3718 /* Returns the maximal precision type for expressions E1 and E2. */
3721 max_precision_type (tree e1, tree e2)
3723 tree type1 = TREE_TYPE (e1);
3724 tree type2 = TREE_TYPE (e2);
3725 return TYPE_PRECISION (type1) > TYPE_PRECISION (type2) ? type1 : type2;
3728 /* Converts a Cloog AST expression E back to a GCC expression tree
3732 clast_to_gcc_expression (tree type, struct clast_expr *e,
3733 VEC (name_tree, heap) *params,
3734 loop_iv_stack ivstack)
3740 struct clast_term *t = (struct clast_term *) e;
3744 if (value_one_p (t->val))
3746 tree name = clast_name_to_gcc (t->var, params, ivstack);
3747 return fold_convert (type, name);
3750 else if (value_mone_p (t->val))
3752 tree name = clast_name_to_gcc (t->var, params, ivstack);
3753 name = fold_convert (type, name);
3754 return fold_build1 (NEGATE_EXPR, type, name);
3758 tree name = clast_name_to_gcc (t->var, params, ivstack);
3759 tree cst = gmp_cst_to_tree (type, t->val);
3760 name = fold_convert (type, name);
3761 return fold_build2 (MULT_EXPR, type, cst, name);
3765 return gmp_cst_to_tree (type, t->val);
3770 struct clast_reduction *r = (struct clast_reduction *) e;
3776 return clast_to_gcc_expression (type, r->elts[0], params, ivstack);
3780 tree tl = clast_to_gcc_expression (type, r->elts[0], params, ivstack);
3781 tree tr = clast_to_gcc_expression (type, r->elts[1], params, ivstack);
3783 gcc_assert (r->n >= 1
3784 && r->elts[0]->type == expr_term
3785 && r->elts[1]->type == expr_term);
3787 return fold_build2 (PLUS_EXPR, type, tl, tr);
3794 return clast_to_gcc_expression (type, r->elts[0], params, ivstack);
3798 tree tl = clast_to_gcc_expression (type, r->elts[0], params, ivstack);
3799 tree tr = clast_to_gcc_expression (type, r->elts[1], params, ivstack);
3800 return fold_build2 (MIN_EXPR, type, tl, tr);
3810 return clast_to_gcc_expression (type, r->elts[0], params, ivstack);
3814 tree tl = clast_to_gcc_expression (type, r->elts[0], params, ivstack);
3815 tree tr = clast_to_gcc_expression (type, r->elts[1], params, ivstack);
3816 return fold_build2 (MAX_EXPR, type, tl, tr);
3832 struct clast_binary *b = (struct clast_binary *) e;
3833 struct clast_expr *lhs = (struct clast_expr *) b->LHS;
3834 tree tl = clast_to_gcc_expression (type, lhs, params, ivstack);
3835 tree tr = gmp_cst_to_tree (type, b->RHS);
3839 case clast_bin_fdiv:
3840 return fold_build2 (FLOOR_DIV_EXPR, type, tl, tr);
3842 case clast_bin_cdiv:
3843 return fold_build2 (CEIL_DIV_EXPR, type, tl, tr);
3846 return fold_build2 (EXACT_DIV_EXPR, type, tl, tr);
3849 return fold_build2 (TRUNC_MOD_EXPR, type, tl, tr);
3863 /* Returns the type for the expression E. */
3866 gcc_type_for_clast_expr (struct clast_expr *e,
3867 VEC (name_tree, heap) *params,
3868 loop_iv_stack ivstack)
3874 struct clast_term *t = (struct clast_term *) e;
3877 return TREE_TYPE (clast_name_to_gcc (t->var, params, ivstack));
3884 struct clast_reduction *r = (struct clast_reduction *) e;
3887 return gcc_type_for_clast_expr (r->elts[0], params, ivstack);
3891 for (i = 0; i < r->n; i++)
3893 tree type = gcc_type_for_clast_expr (r->elts[i], params, ivstack);
3903 struct clast_binary *b = (struct clast_binary *) e;
3904 struct clast_expr *lhs = (struct clast_expr *) b->LHS;
3905 return gcc_type_for_clast_expr (lhs, params, ivstack);
3915 /* Returns the type for the equation CLEQ. */
3918 gcc_type_for_clast_eq (struct clast_equation *cleq,
3919 VEC (name_tree, heap) *params,
3920 loop_iv_stack ivstack)
3922 tree type = gcc_type_for_clast_expr (cleq->LHS, params, ivstack);
3926 return gcc_type_for_clast_expr (cleq->RHS, params, ivstack);
3929 /* Translates a clast equation CLEQ to a tree. */
3932 graphite_translate_clast_equation (scop_p scop,
3933 struct clast_equation *cleq,
3934 loop_iv_stack ivstack)
3936 enum tree_code comp;
3937 tree type = gcc_type_for_clast_eq (cleq, SCOP_PARAMS (scop), ivstack);
3938 tree lhs = clast_to_gcc_expression (type, cleq->LHS, SCOP_PARAMS (scop), ivstack);
3939 tree rhs = clast_to_gcc_expression (type, cleq->RHS, SCOP_PARAMS (scop), ivstack);
3941 if (cleq->sign == 0)
3944 else if (cleq->sign > 0)
3950 return fold_build2 (comp, type, lhs, rhs);
3953 /* Creates the test for the condition in STMT. */
3956 graphite_create_guard_cond_expr (scop_p scop, struct clast_guard *stmt,
3957 loop_iv_stack ivstack)
3962 for (i = 0; i < stmt->n; i++)
3964 tree eq = graphite_translate_clast_equation (scop, &stmt->eq[i], ivstack);
3967 cond = fold_build2 (TRUTH_AND_EXPR, TREE_TYPE (eq), cond, eq);
3975 /* Creates a new if region corresponding to Cloog's guard. */
3978 graphite_create_new_guard (scop_p scop, edge entry_edge,
3979 struct clast_guard *stmt,
3980 loop_iv_stack ivstack)
3982 tree cond_expr = graphite_create_guard_cond_expr (scop, stmt, ivstack);
3983 edge exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
3987 /* Walks a CLAST and returns the first statement in the body of a
3990 static struct clast_user_stmt *
3991 clast_get_body_of_loop (struct clast_stmt *stmt)
3994 || CLAST_STMT_IS_A (stmt, stmt_user))
3995 return (struct clast_user_stmt *) stmt;
3997 if (CLAST_STMT_IS_A (stmt, stmt_for))
3998 return clast_get_body_of_loop (((struct clast_for *) stmt)->body);
4000 if (CLAST_STMT_IS_A (stmt, stmt_guard))
4001 return clast_get_body_of_loop (((struct clast_guard *) stmt)->then);
4003 if (CLAST_STMT_IS_A (stmt, stmt_block))
4004 return clast_get_body_of_loop (((struct clast_block *) stmt)->body);
4009 /* Returns the induction variable for the loop that gets translated to
4013 gcc_type_for_iv_of_clast_loop (struct clast_for *stmt_for)
4015 struct clast_user_stmt *stmt = clast_get_body_of_loop ((struct clast_stmt *) stmt_for);
4016 const char *cloog_iv = stmt_for->iterator;
4017 CloogStatement *cs = stmt->statement;
4018 graphite_bb_p gbb = (graphite_bb_p) cloog_statement_usr (cs);
4020 return gcc_type_for_cloog_iv (cloog_iv, gbb);
4023 /* Creates a new LOOP corresponding to Cloog's STMT. Inserts an induction
4024 variable for the new LOOP. New LOOP is attached to CFG starting at
4025 ENTRY_EDGE. LOOP is inserted into the loop tree and becomes the child
4026 loop of the OUTER_LOOP. */
4028 static struct loop *
4029 graphite_create_new_loop (scop_p scop, edge entry_edge,
4030 struct clast_for *stmt, loop_iv_stack ivstack,
4033 tree type = gcc_type_for_iv_of_clast_loop (stmt);
4034 VEC (name_tree, heap) *params = SCOP_PARAMS (scop);
4035 tree lb = clast_to_gcc_expression (type, stmt->LB, params, ivstack);
4036 tree ub = clast_to_gcc_expression (type, stmt->UB, params, ivstack);
4037 tree stride = gmp_cst_to_tree (type, stmt->stride);
4038 tree ivvar = create_tmp_var (type, "graphiteIV");
4040 loop_p loop = create_empty_loop_on_edge
4041 (entry_edge, lb, stride, ub, ivvar, &iv_before,
4042 outer ? outer : entry_edge->src->loop_father);
4044 add_referenced_var (ivvar);
4045 loop_iv_stack_push_iv (ivstack, iv_before, stmt->iterator);
4049 /* Rename the SSA_NAMEs used in STMT and that appear in IVSTACK. */
4052 rename_variables_in_stmt (gimple stmt, htab_t map)
4055 use_operand_p use_p;
4057 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
4059 tree use = USE_FROM_PTR (use_p);
4060 tree new_name = get_new_name_from_old_name (map, use);
4062 replace_exp (use_p, new_name);
4068 /* Returns true if SSA_NAME is a parameter of SCOP. */
4071 is_parameter (scop_p scop, tree ssa_name)
4074 VEC (name_tree, heap) *params = SCOP_PARAMS (scop);
4077 for (i = 0; VEC_iterate (name_tree, params, i, param); i++)
4078 if (param->t == ssa_name)
4084 /* Returns true if NAME is an induction variable. */
4089 return gimple_code (SSA_NAME_DEF_STMT (name)) == GIMPLE_PHI;
4092 static void expand_scalar_variables_stmt (gimple, basic_block, scop_p,
4095 /* Constructs a tree which only contains old_ivs and parameters. Any
4096 other variables that are defined outside BB will be eliminated by
4097 using their definitions in the constructed tree. OLD_LOOP_FATHER
4098 is the original loop that contained BB. */
4101 expand_scalar_variables_expr (tree type, tree op0, enum tree_code code,
4102 tree op1, basic_block bb, scop_p scop,
4103 loop_p old_loop_father, htab_t map)
4105 if ((TREE_CODE_CLASS (code) == tcc_constant
4106 && code == INTEGER_CST)
4107 || TREE_CODE_CLASS (code) == tcc_reference)
4110 if (TREE_CODE_CLASS (code) == tcc_unary)
4112 tree op0_type = TREE_TYPE (op0);
4113 enum tree_code op0_code = TREE_CODE (op0);
4115 expand_scalar_variables_expr (op0_type, op0, op0_code,
4116 NULL, bb, scop, old_loop_father, map);
4118 return fold_build1 (code, type, op0_expr);
4121 if (TREE_CODE_CLASS (code) == tcc_binary)
4123 tree op0_type = TREE_TYPE (op0);
4124 enum tree_code op0_code = TREE_CODE (op0);
4126 expand_scalar_variables_expr (op0_type, op0, op0_code,
4127 NULL, bb, scop, old_loop_father, map);
4128 tree op1_type = TREE_TYPE (op1);
4129 enum tree_code op1_code = TREE_CODE (op1);
4131 expand_scalar_variables_expr (op1_type, op1, op1_code,
4132 NULL, bb, scop, old_loop_father, map);
4134 return fold_build2 (code, type, op0_expr, op1_expr);
4137 if (code == SSA_NAME)
4141 enum tree_code subcode;
4143 if (is_parameter (scop, op0)
4145 return get_new_name_from_old_name (map, op0);
4147 def_stmt = SSA_NAME_DEF_STMT (op0);
4149 if (gimple_bb (def_stmt) == bb)
4151 /* If the defining statement is in the basic block already
4152 we do not need to create a new expression for it, we
4153 only need to ensure its operands are expanded. */
4154 expand_scalar_variables_stmt (def_stmt, bb, scop,
4155 old_loop_father, map);
4156 return get_new_name_from_old_name (map, op0);
4160 if (gimple_code (def_stmt) != GIMPLE_ASSIGN
4161 || !bb_in_scop_p (gimple_bb (def_stmt), scop))
4162 return get_new_name_from_old_name (map, op0);
4164 var0 = gimple_assign_rhs1 (def_stmt);
4165 subcode = gimple_assign_rhs_code (def_stmt);
4166 var1 = gimple_assign_rhs2 (def_stmt);
4168 return expand_scalar_variables_expr (type, var0, subcode, var1,
4169 bb, scop, old_loop_father, map);
4177 /* Replicates any uses of non-parameters and non-old-ivs variablesthat
4178 are defind outside BB with code that is inserted in BB.
4179 OLD_LOOP_FATHER is the original loop that contained STMT. */
4182 expand_scalar_variables_stmt (gimple stmt, basic_block bb, scop_p scop,
4183 loop_p old_loop_father, htab_t map)
4186 use_operand_p use_p;
4188 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
4190 tree use = USE_FROM_PTR (use_p);
4191 tree type = TREE_TYPE (use);
4192 enum tree_code code = TREE_CODE (use);
4193 tree use_expr = expand_scalar_variables_expr (type, use, code, NULL, bb,
4194 scop, old_loop_father, map);
4195 if (use_expr != use)
4197 gimple_stmt_iterator gsi = gsi_after_labels (bb);
4199 force_gimple_operand_gsi (&gsi, use_expr, true, NULL,
4200 true, GSI_NEW_STMT);
4201 replace_exp (use_p, new_use);
4208 /* Copies the definitions outside of BB of variables that are not
4209 induction variables nor parameters. BB must only contain
4210 "external" references to these types of variables. OLD_LOOP_FATHER
4211 is the original loop that contained BB. */
4214 expand_scalar_variables (basic_block bb, scop_p scop,
4215 loop_p old_loop_father, htab_t map)
4217 gimple_stmt_iterator gsi;
4219 for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi);)
4221 gimple stmt = gsi_stmt (gsi);
4222 expand_scalar_variables_stmt (stmt, bb, scop, old_loop_father, map);
4227 /* Rename all the SSA_NAMEs from block BB according to the MAP. */
4230 rename_variables (basic_block bb, htab_t map)
4232 gimple_stmt_iterator gsi;
4234 for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4235 rename_variables_in_stmt (gsi_stmt (gsi), map);
4238 /* Remove condition from BB. */
4241 remove_condition (basic_block bb)
4243 gimple last = last_stmt (bb);
4245 if (last && gimple_code (last) == GIMPLE_COND)
4247 gimple_stmt_iterator gsi = gsi_last_bb (bb);
4248 gsi_remove (&gsi, true);
4252 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag set. */
4255 get_true_edge_from_guard_bb (basic_block bb)
4260 FOR_EACH_EDGE (e, ei, bb->succs)
4261 if (e->flags & EDGE_TRUE_VALUE)
4268 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag cleared. */
4271 get_false_edge_from_guard_bb (basic_block bb)
4276 FOR_EACH_EDGE (e, ei, bb->succs)
4277 if (!(e->flags & EDGE_TRUE_VALUE))
4284 /* Inserts in MAP a tuple (OLD_NAME, NEW_NAME) for the induction
4285 variables of the loops around GBB in SCOP, i.e. GBB_LOOPS.
4286 NEW_NAME is obtained from IVSTACK. IVSTACK has the same stack
4287 ordering as GBB_LOOPS. */
4290 build_iv_mapping (loop_iv_stack ivstack, htab_t map, gbb_p gbb, scop_p scop)
4296 for (i = 0; VEC_iterate (name_tree, SCOP_OLDIVS (scop), i, iv); i++)
4298 struct rename_map_elt tmp;
4300 if (!flow_bb_inside_loop_p (iv->loop, GBB_BB (gbb)))
4303 tmp.old_name = iv->t;
4304 slot = htab_find_slot (map, &tmp, INSERT);
4308 tree new_name = loop_iv_stack_get_iv (ivstack,
4309 gbb_loop_index (gbb, iv->loop));
4310 *slot = new_rename_map_elt (iv->t, new_name);
4315 /* Register in MAP the tuple (old_name, new_name). */
4318 register_old_and_new_names (htab_t map, tree old_name, tree new_name)
4320 struct rename_map_elt tmp;
4323 tmp.old_name = old_name;
4324 slot = htab_find_slot (map, &tmp, INSERT);
4327 *slot = new_rename_map_elt (old_name, new_name);
4330 /* Create a duplicate of the basic block BB. NOTE: This does not
4331 preserve SSA form. */
4334 graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb, htab_t map)
4336 gimple_stmt_iterator gsi, gsi_tgt;
4338 gsi_tgt = gsi_start_bb (new_bb);
4339 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4341 def_operand_p def_p;
4342 ssa_op_iter op_iter;
4344 gimple stmt = gsi_stmt (gsi);
4347 if (gimple_code (stmt) == GIMPLE_LABEL)
4350 /* Create a new copy of STMT and duplicate STMT's virtual
4352 copy = gimple_copy (stmt);
4353 gsi_insert_after (&gsi_tgt, copy, GSI_NEW_STMT);
4354 mark_symbols_for_renaming (copy);
4356 region = lookup_stmt_eh_region (stmt);
4358 add_stmt_to_eh_region (copy, region);
4359 gimple_duplicate_stmt_histograms (cfun, copy, cfun, stmt);
4361 /* Create new names for all the definitions created by COPY and
4362 add replacement mappings for each new name. */
4363 FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_DEF)
4365 tree old_name = DEF_FROM_PTR (def_p);
4366 tree new_name = create_new_def_for (old_name, copy, def_p);
4367 register_old_and_new_names (map, old_name, new_name);
4372 /* Records in SCOP_LIVEOUT_RENAMES the names that are live out of
4373 the SCOP and that appear in the RENAME_MAP. */
4376 register_scop_liveout_renames (scop_p scop, htab_t rename_map)
4379 sese region = SCOP_REGION (scop);
4381 for (i = 0; i < SESE_NUM_VER (region); i++)
4382 if (bitmap_bit_p (SESE_LIVEOUT (region), i)
4383 && is_gimple_reg (ssa_name (i)))
4385 tree old_name = ssa_name (i);
4386 tree new_name = get_new_name_from_old_name (rename_map, old_name);
4388 register_old_and_new_names (SCOP_LIVEOUT_RENAMES (scop),
4389 old_name, new_name);
4393 /* Copies BB and includes in the copied BB all the statements that can
4394 be reached following the use-def chains from the memory accesses,
4395 and returns the next edge following this new block. */
4398 copy_bb_and_scalar_dependences (basic_block bb, scop_p scop,
4399 loop_p context_loop,
4400 edge next_e, htab_t map)
4402 basic_block new_bb = split_edge (next_e);
4404 next_e = single_succ_edge (new_bb);
4405 graphite_copy_stmts_from_block (bb, new_bb, map);
4406 remove_condition (new_bb);
4407 rename_variables (new_bb, map);
4408 remove_phi_nodes (new_bb);
4409 expand_scalar_variables (new_bb, scop, context_loop, map);
4410 register_scop_liveout_renames (scop, map);
4415 /* Helper function for htab_traverse in insert_loop_close_phis. */
4418 add_loop_exit_phis (void **slot, void *s)
4420 struct rename_map_elt *entry = (struct rename_map_elt *) *slot;
4421 tree new_name = entry->new_name;
4422 basic_block bb = (basic_block) s;
4423 gimple phi = create_phi_node (new_name, bb);
4424 tree res = create_new_def_for (gimple_phi_result (phi), phi,
4425 gimple_phi_result_ptr (phi));
4427 add_phi_arg (phi, new_name, single_pred_edge (bb));
4429 entry->new_name = res;
4434 /* Iterate over the SCOP_LIVEOUT_RENAMES (SCOP) and get tuples of the
4435 form (OLD_NAME, NEW_NAME). Insert in BB "RES = phi (NEW_NAME)",
4436 and finally register in SCOP_LIVEOUT_RENAMES (scop) the tuple
4440 insert_loop_close_phis (scop_p scop, basic_block bb)
4442 update_ssa (TODO_update_ssa);
4443 htab_traverse (SCOP_LIVEOUT_RENAMES (scop), add_loop_exit_phis, bb);
4444 update_ssa (TODO_update_ssa);
4447 /* Helper structure for htab_traverse in insert_guard_phis. */
4451 edge true_edge, false_edge;
4452 htab_t liveout_before_guard;
4455 /* Return the default name that is before the guard. */
4458 default_liveout_before_guard (htab_t liveout_before_guard, tree old_name)
4460 tree res = get_new_name_from_old_name (liveout_before_guard, old_name);
4462 if (res == old_name)
4464 if (is_gimple_reg (res))
4465 return fold_convert (TREE_TYPE (res), integer_zero_node);
4466 return gimple_default_def (cfun, res);
4472 /* Helper function for htab_traverse in insert_guard_phis. */
4475 add_guard_exit_phis (void **slot, void *s)
4477 struct rename_map_elt *entry = (struct rename_map_elt *) *slot;
4478 struct igp *i = (struct igp *) s;
4479 basic_block bb = i->bb;
4480 edge true_edge = i->true_edge;
4481 edge false_edge = i->false_edge;
4482 tree name1 = entry->new_name;
4483 tree name2 = default_liveout_before_guard (i->liveout_before_guard,
4485 gimple phi = create_phi_node (name1, bb);
4486 tree res = create_new_def_for (gimple_phi_result (phi), phi,
4487 gimple_phi_result_ptr (phi));
4489 add_phi_arg (phi, name1, true_edge);
4490 add_phi_arg (phi, name2, false_edge);
4492 entry->new_name = res;
4497 /* Iterate over the SCOP_LIVEOUT_RENAMES (SCOP) and get tuples of the
4498 form (OLD_NAME, NAME1). If there is a correspondent tuple of
4499 OLD_NAME in LIVEOUT_BEFORE_GUARD, i.e. (OLD_NAME, NAME2) then
4502 | RES = phi (NAME1 (on TRUE_EDGE), NAME2 (on FALSE_EDGE))"
4504 if there is no tuple for OLD_NAME in LIVEOUT_BEFORE_GUARD, insert
4506 | RES = phi (NAME1 (on TRUE_EDGE),
4507 | DEFAULT_DEFINITION of NAME1 (on FALSE_EDGE))".
4509 Finally register in SCOP_LIVEOUT_RENAMES (scop) the tuple
4513 insert_guard_phis (scop_p scop, basic_block bb, edge true_edge,
4514 edge false_edge, htab_t liveout_before_guard)
4518 i.true_edge = true_edge;
4519 i.false_edge = false_edge;
4520 i.liveout_before_guard = liveout_before_guard;
4522 update_ssa (TODO_update_ssa);
4523 htab_traverse (SCOP_LIVEOUT_RENAMES (scop), add_guard_exit_phis, &i);
4524 update_ssa (TODO_update_ssa);
4527 /* Helper function for htab_traverse. */
4530 copy_renames (void **slot, void *s)
4532 struct rename_map_elt *entry = (struct rename_map_elt *) *slot;
4533 htab_t res = (htab_t) s;
4534 tree old_name = entry->old_name;
4535 tree new_name = entry->new_name;
4536 struct rename_map_elt tmp;
4539 tmp.old_name = old_name;
4540 x = htab_find_slot (res, &tmp, INSERT);
4543 *x = new_rename_map_elt (old_name, new_name);
4548 /* Translates a CLAST statement STMT to GCC representation in the
4551 - NEXT_E is the edge where new generated code should be attached.
4552 - CONTEXT_LOOP is the loop in which the generated code will be placed
4554 - IVSTACK contains the surrounding loops around the statement to be
4559 translate_clast (scop_p scop, struct loop *context_loop,
4560 struct clast_stmt *stmt, edge next_e, loop_iv_stack ivstack)
4565 if (CLAST_STMT_IS_A (stmt, stmt_root))
4566 return translate_clast (scop, context_loop, stmt->next, next_e, ivstack);
4568 if (CLAST_STMT_IS_A (stmt, stmt_user))
4571 CloogStatement *cs = ((struct clast_user_stmt *) stmt)->statement;
4572 graphite_bb_p gbb = (graphite_bb_p) cloog_statement_usr (cs);
4574 if (GBB_BB (gbb) == ENTRY_BLOCK_PTR)
4577 map = htab_create (10, rename_map_elt_info, eq_rename_map_elts, free);
4578 loop_iv_stack_patch_for_consts (ivstack, (struct clast_user_stmt *) stmt);
4579 build_iv_mapping (ivstack, map, gbb, scop);
4580 next_e = copy_bb_and_scalar_dependences (GBB_BB (gbb), scop,
4581 context_loop, next_e, map);
4583 loop_iv_stack_remove_constants (ivstack);
4584 update_ssa (TODO_update_ssa);
4585 recompute_all_dominators ();
4587 return translate_clast (scop, context_loop, stmt->next, next_e, ivstack);
4590 if (CLAST_STMT_IS_A (stmt, stmt_for))
4593 = graphite_create_new_loop (scop, next_e, (struct clast_for *) stmt,
4594 ivstack, context_loop ? context_loop
4596 edge last_e = single_exit (loop);
4598 next_e = translate_clast (scop, loop, ((struct clast_for *) stmt)->body,
4599 single_pred_edge (loop->latch), ivstack);
4600 redirect_edge_succ_nodup (next_e, loop->latch);
4602 set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src);
4603 loop_iv_stack_pop (ivstack);
4604 last_e = single_succ_edge (split_edge (last_e));
4605 insert_loop_close_phis (scop, last_e->src);
4607 recompute_all_dominators ();
4609 return translate_clast (scop, context_loop, stmt->next, last_e, ivstack);
4612 if (CLAST_STMT_IS_A (stmt, stmt_guard))
4614 htab_t liveout_before_guard = htab_create (10, rename_map_elt_info,
4615 eq_rename_map_elts, free);
4616 edge last_e = graphite_create_new_guard (scop, next_e,
4617 ((struct clast_guard *) stmt),
4619 edge true_e = get_true_edge_from_guard_bb (next_e->dest);
4620 edge false_e = get_false_edge_from_guard_bb (next_e->dest);
4621 edge exit_true_e = single_succ_edge (true_e->dest);
4622 edge exit_false_e = single_succ_edge (false_e->dest);
4624 htab_traverse (SCOP_LIVEOUT_RENAMES (scop), copy_renames,
4625 liveout_before_guard);
4627 next_e = translate_clast (scop, context_loop,
4628 ((struct clast_guard *) stmt)->then,
4630 insert_guard_phis (scop, last_e->src, exit_true_e, exit_false_e,
4631 liveout_before_guard);
4632 htab_delete (liveout_before_guard);
4633 recompute_all_dominators ();
4636 return translate_clast (scop, context_loop, stmt->next, last_e, ivstack);
4639 if (CLAST_STMT_IS_A (stmt, stmt_block))
4641 next_e = translate_clast (scop, context_loop,
4642 ((struct clast_block *) stmt)->body,
4644 recompute_all_dominators ();
4646 return translate_clast (scop, context_loop, stmt->next, next_e, ivstack);
4652 /* Free the SCATTERING domain list. */
4655 free_scattering (CloogDomainList *scattering)
4659 CloogDomain *dom = cloog_domain (scattering);
4660 CloogDomainList *next = cloog_next_domain (scattering);
4662 cloog_domain_free (dom);
4668 /* Build cloog program for SCoP. */
4671 build_cloog_prog (scop_p scop)
4674 int max_nb_loops = scop_max_loop_depth (scop);
4676 CloogLoop *loop_list = NULL;
4677 CloogBlockList *block_list = NULL;
4678 CloogDomainList *scattering = NULL;
4679 CloogProgram *prog = SCOP_PROG (scop);
4680 int nbs = 2 * max_nb_loops + 1;
4681 int *scaldims = (int *) xmalloc (nbs * (sizeof (int)));
4683 cloog_program_set_nb_scattdims (prog, nbs);
4684 initialize_cloog_names (scop);
4686 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gbb); i++)
4688 /* Build new block. */
4689 CloogMatrix *domain = GBB_DOMAIN (gbb);
4690 CloogStatement *stmt = cloog_statement_alloc (GBB_BB (gbb)->index);
4691 CloogBlock *block = cloog_block_alloc (stmt, 0, NULL,
4692 nb_loops_around_gb (gbb));
4693 cloog_statement_set_usr (stmt, gbb);
4695 /* Add empty domain to all bbs, which do not yet have a domain, as they
4696 are not part of any loop. */
4699 domain = cloog_matrix_alloc (0, scop_nb_params (scop) + 2);
4700 GBB_DOMAIN (gbb) = domain;
4703 /* Build loop list. */
4705 CloogLoop *new_loop_list = cloog_loop_malloc ();
4706 cloog_loop_set_next (new_loop_list, loop_list);
4707 cloog_loop_set_domain (new_loop_list,
4708 cloog_domain_matrix2domain (domain));
4709 cloog_loop_set_block (new_loop_list, block);
4710 loop_list = new_loop_list;
4713 /* Build block list. */
4715 CloogBlockList *new_block_list = cloog_block_list_malloc ();
4717 cloog_block_list_set_next (new_block_list, block_list);
4718 cloog_block_list_set_block (new_block_list, block);
4719 block_list = new_block_list;
4722 /* Build scattering list. */
4724 /* XXX: Replace with cloog_domain_list_alloc(), when available. */
4725 CloogDomainList *new_scattering
4726 = (CloogDomainList *) xmalloc (sizeof (CloogDomainList));
4727 CloogMatrix *scat_mat = schedule_to_scattering (gbb, nbs);
4729 cloog_set_next_domain (new_scattering, scattering);
4730 cloog_set_domain (new_scattering,
4731 cloog_domain_matrix2domain (scat_mat));
4732 scattering = new_scattering;
4733 cloog_matrix_free (scat_mat);
4737 cloog_program_set_loop (prog, loop_list);
4738 cloog_program_set_blocklist (prog, block_list);
4740 for (i = 0; i < nbs; i++)
4743 cloog_program_set_scaldims (prog, scaldims);
4745 /* Extract scalar dimensions to simplify the code generation problem. */
4746 cloog_program_extract_scalars (prog, scattering);
4748 /* Apply scattering. */
4749 cloog_program_scatter (prog, scattering);
4750 free_scattering (scattering);
4752 /* Iterators corresponding to scalar dimensions have to be extracted. */
4753 cloog_names_scalarize (cloog_program_names (prog), nbs,
4754 cloog_program_scaldims (prog));
4756 /* Free blocklist. */
4758 CloogBlockList *next = cloog_program_blocklist (prog);
4762 CloogBlockList *toDelete = next;
4763 next = cloog_block_list_next (next);
4764 cloog_block_list_set_next (toDelete, NULL);
4765 cloog_block_list_set_block (toDelete, NULL);
4766 cloog_block_list_free (toDelete);
4768 cloog_program_set_blocklist (prog, NULL);
4772 /* Return the options that will be used in GLOOG. */
4774 static CloogOptions *
4775 set_cloog_options (void)
4777 CloogOptions *options = cloog_options_malloc ();
4779 /* Change cloog output language to C. If we do use FORTRAN instead, cloog
4780 will stop e.g. with "ERROR: unbounded loops not allowed in FORTRAN.", if
4781 we pass an incomplete program to cloog. */
4782 options->language = LANGUAGE_C;
4784 /* Enable complex equality spreading: removes dummy statements
4785 (assignments) in the generated code which repeats the
4786 substitution equations for statements. This is useless for
4790 /* Enable C pretty-printing mode: normalizes the substitution
4791 equations for statements. */
4794 /* Allow cloog to build strides with a stride width different to one.
4795 This example has stride = 4:
4797 for (i = 0; i < 20; i += 4)
4799 options->strides = 1;
4801 /* Disable optimizations and make cloog generate source code closer to the
4802 input. This is useful for debugging, but later we want the optimized
4805 XXX: We can not disable optimizations, as loop blocking is not working
4810 options->l = INT_MAX;
4816 /* Prints STMT to STDERR. */
4819 debug_clast_stmt (struct clast_stmt *stmt)
4821 CloogOptions *options = set_cloog_options ();
4823 pprint (stderr, stmt, 0, options);
4826 /* Find the right transform for the SCOP, and return a Cloog AST
4827 representing the new form of the program. */
4829 static struct clast_stmt *
4830 find_transform (scop_p scop)
4832 struct clast_stmt *stmt;
4833 CloogOptions *options = set_cloog_options ();
4835 /* Connect new cloog prog generation to graphite. */
4836 build_cloog_prog (scop);
4838 if (dump_file && (dump_flags & TDF_DETAILS))
4840 fprintf (dump_file, "Cloog Input [\n");
4841 cloog_program_print (dump_file, SCOP_PROG(scop));
4842 fprintf (dump_file, "]\n");
4845 SCOP_PROG (scop) = cloog_program_generate (SCOP_PROG (scop), options);
4846 stmt = cloog_clast_create (SCOP_PROG (scop), options);
4848 if (dump_file && (dump_flags & TDF_DETAILS))
4850 fprintf (dump_file, "Cloog Output[\n");
4851 pprint (dump_file, stmt, 0, options);
4852 cloog_program_dump_cloog (dump_file, SCOP_PROG (scop));
4853 fprintf (dump_file, "]\n");
4856 cloog_options_free (options);
4860 /* Returns true when it is possible to generate code for this STMT.
4861 For the moment we cannot generate code when Cloog decides to
4862 duplicate a statement, as we do not do a copy, but a move.
4863 USED_BASIC_BLOCKS records the blocks that have already been seen.
4864 We return false if we have to generate code twice for the same
4868 can_generate_code_stmt (struct clast_stmt *stmt,
4869 struct pointer_set_t *used_basic_blocks)
4874 if (CLAST_STMT_IS_A (stmt, stmt_root))
4875 return can_generate_code_stmt (stmt->next, used_basic_blocks);
4877 if (CLAST_STMT_IS_A (stmt, stmt_user))
4879 CloogStatement *cs = ((struct clast_user_stmt *) stmt)->statement;
4880 graphite_bb_p gbb = (graphite_bb_p) cloog_statement_usr (cs);
4882 if (pointer_set_contains (used_basic_blocks, gbb))
4884 pointer_set_insert (used_basic_blocks, gbb);
4885 return can_generate_code_stmt (stmt->next, used_basic_blocks);
4888 if (CLAST_STMT_IS_A (stmt, stmt_for))
4889 return can_generate_code_stmt (((struct clast_for *) stmt)->body,
4891 && can_generate_code_stmt (stmt->next, used_basic_blocks);
4893 if (CLAST_STMT_IS_A (stmt, stmt_guard))
4894 return can_generate_code_stmt (((struct clast_guard *) stmt)->then,
4897 if (CLAST_STMT_IS_A (stmt, stmt_block))
4898 return can_generate_code_stmt (((struct clast_block *) stmt)->body,
4900 && can_generate_code_stmt (stmt->next, used_basic_blocks);
4905 /* Returns true when it is possible to generate code for this STMT. */
4908 can_generate_code (struct clast_stmt *stmt)
4911 struct pointer_set_t *used_basic_blocks = pointer_set_create ();
4913 result = can_generate_code_stmt (stmt, used_basic_blocks);
4914 pointer_set_destroy (used_basic_blocks);
4918 /* Remove from the CFG the REGION. */
4921 remove_sese_region (sese region)
4923 VEC (basic_block, heap) *bbs = NULL;
4924 basic_block entry_bb = SESE_ENTRY (region)->dest;
4925 basic_block exit_bb = SESE_EXIT (region)->dest;
4929 VEC_safe_push (basic_block, heap, bbs, entry_bb);
4930 gather_blocks_in_sese_region (entry_bb, exit_bb, &bbs);
4932 for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
4933 delete_basic_block (bb);
4935 VEC_free (basic_block, heap, bbs);
4938 typedef struct ifsese {
4945 if_region_entry (ifsese if_region)
4947 return SESE_ENTRY (if_region->region);
4951 if_region_exit (ifsese if_region)
4953 return SESE_EXIT (if_region->region);
4956 static inline basic_block
4957 if_region_get_condition_block (ifsese if_region)
4959 return if_region_entry (if_region)->dest;
4963 if_region_set_false_region (ifsese if_region, sese region)
4965 basic_block condition = if_region_get_condition_block (if_region);
4966 edge false_edge = get_false_edge_from_guard_bb (condition);
4967 edge entry_region = SESE_ENTRY (region);
4968 edge exit_region = SESE_EXIT (region);
4969 basic_block before_region = entry_region->src;
4970 basic_block last_in_region = exit_region->src;
4971 void **slot = htab_find_slot_with_hash (current_loops->exits, exit_region,
4972 htab_hash_pointer (exit_region),
4975 entry_region->flags = false_edge->flags;
4976 false_edge->flags = exit_region->flags;
4978 redirect_edge_pred (entry_region, condition);
4979 redirect_edge_pred (exit_region, before_region);
4980 redirect_edge_pred (false_edge, last_in_region);
4982 exit_region->flags = EDGE_FALLTHRU;
4983 recompute_all_dominators ();
4985 SESE_EXIT (region) = single_succ_edge (false_edge->dest);
4986 if_region->false_region = region;
4990 struct loop_exit *loop_exit = GGC_CNEW (struct loop_exit);
4992 memcpy (loop_exit, *((struct loop_exit **) slot), sizeof (struct loop_exit));
4993 htab_clear_slot (current_loops->exits, slot);
4995 slot = htab_find_slot_with_hash (current_loops->exits, false_edge,
4996 htab_hash_pointer (false_edge),
4998 loop_exit->e = false_edge;
5000 false_edge->src->loop_father->exits->next = loop_exit;
5005 create_if_region_on_edge (edge entry, tree condition)
5009 sese sese_region = GGC_NEW (struct sese);
5010 sese true_region = GGC_NEW (struct sese);
5011 sese false_region = GGC_NEW (struct sese);
5012 ifsese if_region = GGC_NEW (struct ifsese);
5013 edge exit = create_empty_if_region_on_edge (entry, condition);
5015 if_region->region = sese_region;
5016 if_region->region->entry = entry;
5017 if_region->region->exit = exit;
5019 FOR_EACH_EDGE (e, ei, entry->dest->succs)
5021 if (e->flags & EDGE_TRUE_VALUE)
5023 true_region->entry = e;
5024 true_region->exit = single_succ_edge (e->dest);
5025 if_region->true_region = true_region;
5027 else if (e->flags & EDGE_FALSE_VALUE)
5029 false_region->entry = e;
5030 false_region->exit = single_succ_edge (e->dest);
5031 if_region->false_region = false_region;
5038 /* Moves REGION in a condition expression:
5046 move_sese_in_condition (sese region)
5048 basic_block pred_block = split_edge (SESE_ENTRY (region));
5049 ifsese if_region = NULL;
5051 SESE_ENTRY (region) = single_succ_edge (pred_block);
5052 if_region = create_if_region_on_edge (single_pred_edge (pred_block), integer_one_node);
5053 if_region_set_false_region (if_region, region);
5058 /* Add exit phis for USE on EXIT. */
5061 scop_add_exit_phis_edge (basic_block exit, tree use, edge false_e, edge true_e)
5063 gimple phi = create_phi_node (use, exit);
5065 create_new_def_for (gimple_phi_result (phi), phi,
5066 gimple_phi_result_ptr (phi));
5067 add_phi_arg (phi, use, false_e);
5068 add_phi_arg (phi, use, true_e);
5071 /* Add phi nodes for VAR that is used in LIVEIN. Phi nodes are
5072 inserted in block BB. */
5075 scop_add_exit_phis_var (basic_block bb, tree var, bitmap livein,
5076 edge false_e, edge true_e)
5079 basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (var));
5081 if (is_gimple_reg (var))
5082 bitmap_clear_bit (livein, def_bb->index);
5084 bitmap_set_bit (livein, def_bb->index);
5086 def = BITMAP_ALLOC (NULL);
5087 bitmap_set_bit (def, def_bb->index);
5088 compute_global_livein (livein, def);
5091 scop_add_exit_phis_edge (bb, var, false_e, true_e);
5094 /* Insert in the block BB phi nodes for variables defined in REGION
5095 and used outside the REGION. The code generation moves REGION in
5096 the else clause of an "if (1)" and generates code in the then
5097 clause that is at this point empty:
5106 scop_insert_phis_for_liveouts (sese region, basic_block bb,
5107 edge false_e, edge true_e)
5112 update_ssa (TODO_update_ssa);
5114 EXECUTE_IF_SET_IN_BITMAP (SESE_LIVEOUT (region), 0, i, bi)
5115 scop_add_exit_phis_var (bb, ssa_name (i), SESE_LIVEIN_VER (region, i),
5118 update_ssa (TODO_update_ssa);
5121 /* Adjusts the phi nodes in the block BB for variables defined in
5122 SCOP_REGION and used outside the SCOP_REGION. The code generation
5123 moves SCOP_REGION in the else clause of an "if (1)" and generates
5124 code in the then clause:
5127 | generated code from REGION;
5131 To adjust the phi nodes after the condition, SCOP_LIVEOUT_RENAMES
5132 hash table is used: this stores for a name that is part of the
5133 LIVEOUT of SCOP_REGION its new name in the generated code. */
5136 scop_adjust_phis_for_liveouts (scop_p scop, basic_block bb, edge false_e,
5139 gimple_stmt_iterator si;
5141 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
5143 unsigned i, false_i;
5144 gimple phi = gsi_stmt (si);
5146 if (!is_gimple_reg (PHI_RESULT (phi)))
5149 for (i = 0; i < gimple_phi_num_args (phi); i++)
5150 if (gimple_phi_arg_edge (phi, i) == false_e)
5156 for (i = 0; i < gimple_phi_num_args (phi); i++)
5157 if (gimple_phi_arg_edge (phi, i) == true_e)
5159 tree old_name = gimple_phi_arg_def (phi, false_i);
5160 tree new_name = get_new_name_from_old_name
5161 (SCOP_LIVEOUT_RENAMES (scop), old_name);
5163 gcc_assert (old_name != new_name);
5164 SET_PHI_ARG_DEF (phi, i, new_name);
5169 /* Returns the first cloog name used in EXPR. */
5172 find_cloog_iv_in_expr (struct clast_expr *expr)
5174 struct clast_term *term = (struct clast_term *) expr;
5176 if (expr->type == expr_term
5180 if (expr->type == expr_term)
5183 if (expr->type == expr_red)
5186 struct clast_reduction *red = (struct clast_reduction *) expr;
5188 for (i = 0; i < red->n; i++)
5190 const char *res = find_cloog_iv_in_expr ((red)->elts[i]);
5200 /* Build for a clast_user_stmt USER_STMT a map between the CLAST
5201 induction variables and the corresponding GCC old induction
5202 variables. This information is stored on each GRAPHITE_BB. */
5205 compute_cloog_iv_types_1 (graphite_bb_p gbb,
5206 struct clast_user_stmt *user_stmt)
5208 struct clast_stmt *t;
5211 for (t = user_stmt->substitutions; t; t = t->next, index++)
5214 struct ivtype_map_elt tmp;
5215 struct clast_expr *expr = (struct clast_expr *)
5216 ((struct clast_assignment *)t)->RHS;
5218 /* Create an entry (clast_var, type). */
5219 tmp.cloog_iv = find_cloog_iv_in_expr (expr);
5223 slot = htab_find_slot (GBB_CLOOG_IV_TYPES (gbb), &tmp, INSERT);
5227 loop_p loop = gbb_loop_at_index (gbb, index);
5228 tree oldiv = oldiv_for_loop (GBB_SCOP (gbb), loop);
5229 tree type = oldiv ? TREE_TYPE (oldiv) : integer_type_node;
5230 *slot = new_ivtype_map_elt (tmp.cloog_iv, type);
5235 /* Walk the CLAST tree starting from STMT and build for each
5236 clast_user_stmt a map between the CLAST induction variables and the
5237 corresponding GCC old induction variables. This information is
5238 stored on each GRAPHITE_BB. */
5241 compute_cloog_iv_types (struct clast_stmt *stmt)
5246 if (CLAST_STMT_IS_A (stmt, stmt_root))
5249 if (CLAST_STMT_IS_A (stmt, stmt_user))
5251 CloogStatement *cs = ((struct clast_user_stmt *) stmt)->statement;
5252 graphite_bb_p gbb = (graphite_bb_p) cloog_statement_usr (cs);
5253 GBB_CLOOG_IV_TYPES (gbb) = htab_create (10, ivtype_map_elt_info,
5254 eq_ivtype_map_elts, free);
5255 compute_cloog_iv_types_1 (gbb, (struct clast_user_stmt *) stmt);
5259 if (CLAST_STMT_IS_A (stmt, stmt_for))
5261 struct clast_stmt *s = ((struct clast_for *) stmt)->body;
5262 compute_cloog_iv_types (s);
5266 if (CLAST_STMT_IS_A (stmt, stmt_guard))
5268 struct clast_stmt *s = ((struct clast_guard *) stmt)->then;
5269 compute_cloog_iv_types (s);
5273 if (CLAST_STMT_IS_A (stmt, stmt_block))
5275 struct clast_stmt *s = ((struct clast_block *) stmt)->body;
5276 compute_cloog_iv_types (s);
5283 compute_cloog_iv_types (stmt->next);
5286 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
5290 gloog (scop_p scop, struct clast_stmt *stmt)
5292 edge new_scop_exit_edge = NULL;
5293 VEC (iv_stack_entry_p, heap) *ivstack = VEC_alloc (iv_stack_entry_p, heap,
5295 loop_p context_loop;
5296 ifsese if_region = NULL;
5298 if (!can_generate_code (stmt))
5300 cloog_clast_free (stmt);
5304 if_region = move_sese_in_condition (SCOP_REGION (scop));
5305 sese_build_livein_liveouts (SCOP_REGION (scop));
5306 scop_insert_phis_for_liveouts (SCOP_REGION (scop),
5307 if_region->region->exit->src,
5308 if_region->false_region->exit,
5309 if_region->true_region->exit);
5310 recompute_all_dominators ();
5312 context_loop = SESE_ENTRY (SCOP_REGION (scop))->src->loop_father;
5313 compute_cloog_iv_types (stmt);
5315 new_scop_exit_edge = translate_clast (scop, context_loop, stmt,
5316 if_region->true_region->entry,
5318 free_loop_iv_stack (&ivstack);
5319 cloog_clast_free (stmt);
5322 scop_adjust_phis_for_liveouts (scop,
5323 if_region->region->exit->src,
5324 if_region->false_region->exit,
5325 if_region->true_region->exit);
5327 recompute_all_dominators ();
5329 cleanup_tree_cfg ();
5330 recompute_all_dominators ();
5334 /* Returns the number of data references in SCOP. */
5337 nb_data_refs_in_scop (scop_p scop)
5343 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gbb); i++)
5344 res += VEC_length (data_reference_p, GBB_DATA_REFS (gbb));
5349 /* Move the loop at index LOOP and insert it before index NEW_LOOP_POS.
5350 This transformartion is only valid, if the loop nest between i and k is
5351 perfectly nested. Therefore we do not need to change the static schedule.
5355 for (i = 0; i < 50; i++)
5357 for (k = 5; k < 100; k++)
5360 To move k before i use:
5362 graphite_trans_bb_move_loop (A, 2, 0)
5364 for (k = 5; k < 100; k++)
5365 for (i = 0; i < 50; i++)
5371 graphite_trans_bb_move_loop (A, 0, 2)
5373 This function does not check the validity of interchanging loops.
5374 This should be checked before calling this function. */
5377 graphite_trans_bb_move_loop (graphite_bb_p gb, int loop,
5380 CloogMatrix *domain = GBB_DOMAIN (gb);
5384 gcc_assert (loop < gbb_nb_loops (gb)
5385 && new_loop_pos < gbb_nb_loops (gb));
5387 /* Update LOOPS vector. */
5388 tmp_loop_p = VEC_index (loop_p, GBB_LOOPS (gb), loop);
5389 VEC_ordered_remove (loop_p, GBB_LOOPS (gb), loop);
5390 VEC_safe_insert (loop_p, heap, GBB_LOOPS (gb), new_loop_pos, tmp_loop_p);
5392 /* Move the domain columns. */
5393 if (loop < new_loop_pos)
5394 for (row = 0; row < domain->NbRows; row++)
5398 value_assign (tmp, domain->p[row][loop + 1]);
5400 for (j = loop ; j < new_loop_pos - 1; j++)
5401 value_assign (domain->p[row][j + 1], domain->p[row][j + 2]);
5403 value_assign (domain->p[row][new_loop_pos], tmp);
5407 for (row = 0; row < domain->NbRows; row++)
5411 value_assign (tmp, domain->p[row][loop + 1]);
5413 for (j = loop ; j > new_loop_pos; j--)
5414 value_assign (domain->p[row][j + 1], domain->p[row][j]);
5416 value_assign (domain->p[row][new_loop_pos + 1], tmp);
5421 /* Get the index of the column representing constants in the DOMAIN
5425 const_column_index (CloogMatrix *domain)
5427 return domain->NbColumns - 1;
5431 /* Get the first index that is positive or negative, determined
5432 following the value of POSITIVE, in matrix DOMAIN in COLUMN. */
5435 get_first_matching_sign_row_index (CloogMatrix *domain, int column,
5440 for (row = 0; row < domain->NbRows; row++)
5442 int val = value_get_si (domain->p[row][column]);
5444 if (val > 0 && positive)
5447 else if (val < 0 && !positive)
5454 /* Get the lower bound of COLUMN in matrix DOMAIN. */
5457 get_lower_bound_row (CloogMatrix *domain, int column)
5459 return get_first_matching_sign_row_index (domain, column, true);
5462 /* Get the upper bound of COLUMN in matrix DOMAIN. */
5465 get_upper_bound_row (CloogMatrix *domain, int column)
5467 return get_first_matching_sign_row_index (domain, column, false);
5470 /* Copies the OLD_ROW constraint from OLD_DOMAIN to the NEW_DOMAIN at
5474 copy_constraint (CloogMatrix *old_domain, CloogMatrix *new_domain,
5475 int old_row, int new_row)
5479 gcc_assert (old_domain->NbColumns == new_domain->NbColumns
5480 && old_row < old_domain->NbRows
5481 && new_row < new_domain->NbRows);
5483 for (i = 0; i < old_domain->NbColumns; i++)
5484 value_assign (new_domain->p[new_row][i], old_domain->p[old_row][i]);
5487 /* Swap coefficients of variables X and Y on row R. */
5490 swap_constraint_variables (CloogMatrix *domain,
5491 int r, int x, int y)
5493 value_swap (domain->p[r][x], domain->p[r][y]);
5496 /* Scale by X the coefficient C of constraint at row R in DOMAIN. */
5499 scale_constraint_variable (CloogMatrix *domain,
5500 int r, int c, int x)
5502 Value strip_size_value;
5503 value_init (strip_size_value);
5504 value_set_si (strip_size_value, x);
5505 value_multiply (domain->p[r][c], domain->p[r][c], strip_size_value);
5506 value_clear (strip_size_value);
5509 /* Strip mines the loop of BB at the position LOOP_DEPTH with STRIDE.
5510 Always valid, but not always a performance improvement. */
5513 graphite_trans_bb_strip_mine (graphite_bb_p gb, int loop_depth, int stride)
5517 CloogMatrix *domain = GBB_DOMAIN (gb);
5518 CloogMatrix *new_domain = cloog_matrix_alloc (domain->NbRows + 3,
5519 domain->NbColumns + 1);
5521 int col_loop_old = loop_depth + 2;
5522 int col_loop_strip = col_loop_old - 1;
5524 gcc_assert (loop_depth <= gbb_nb_loops (gb) - 1);
5526 VEC_safe_insert (loop_p, heap, GBB_LOOPS (gb), loop_depth, NULL);
5528 GBB_DOMAIN (gb) = new_domain;
5530 for (row = 0; row < domain->NbRows; row++)
5531 for (col = 0; col < domain->NbColumns; col++)
5532 if (col <= loop_depth)
5533 value_assign (new_domain->p[row][col], domain->p[row][col]);
5535 value_assign (new_domain->p[row][col + 1], domain->p[row][col]);
5537 row = domain->NbRows;
5539 /* Lower bound of the outer stripped loop. */
5540 copy_constraint (new_domain, new_domain,
5541 get_lower_bound_row (new_domain, col_loop_old), row);
5542 swap_constraint_variables (new_domain, row, col_loop_old, col_loop_strip);
5545 /* Upper bound of the outer stripped loop. */
5546 copy_constraint (new_domain, new_domain,
5547 get_upper_bound_row (new_domain, col_loop_old), row);
5548 swap_constraint_variables (new_domain, row, col_loop_old, col_loop_strip);
5549 scale_constraint_variable (new_domain, row, col_loop_strip, stride);
5552 /* Lower bound of a tile starts at "stride * outer_iv". */
5553 row = get_lower_bound_row (new_domain, col_loop_old);
5554 value_set_si (new_domain->p[row][0], 1);
5555 value_set_si (new_domain->p[row][const_column_index (new_domain)], 0);
5556 value_set_si (new_domain->p[row][col_loop_old], 1);
5557 value_set_si (new_domain->p[row][col_loop_strip], -1 * stride);
5559 /* Upper bound of a tile stops at "stride * outer_iv + stride - 1",
5560 or at the old upper bound that is not modified. */
5561 row = new_domain->NbRows - 1;
5562 value_set_si (new_domain->p[row][0], 1);
5563 value_set_si (new_domain->p[row][col_loop_old], -1);
5564 value_set_si (new_domain->p[row][col_loop_strip], stride);
5565 value_set_si (new_domain->p[row][const_column_index (new_domain)],
5568 cloog_matrix_free (domain);
5570 /* Update static schedule. */
5573 int nb_loops = gbb_nb_loops (gb);
5574 lambda_vector new_schedule = lambda_vector_new (nb_loops + 1);
5576 for (i = 0; i <= loop_depth; i++)
5577 new_schedule[i] = GBB_STATIC_SCHEDULE (gb)[i];
5579 for (i = loop_depth + 1; i <= nb_loops - 2; i++)
5580 new_schedule[i + 2] = GBB_STATIC_SCHEDULE (gb)[i];
5582 GBB_STATIC_SCHEDULE (gb) = new_schedule;
5586 /* Returns true when the strip mining of LOOP_INDEX by STRIDE is
5587 profitable or undecidable. GB is the statement around which the
5588 loops will be strip mined. */
5591 strip_mine_profitable_p (graphite_bb_p gb, int stride,
5600 loop = VEC_index (loop_p, GBB_LOOPS (gb), loop_index);
5601 exit = single_exit (loop);
5603 niter = find_loop_niter (loop, &exit);
5604 if (niter == chrec_dont_know
5605 || TREE_CODE (niter) != INTEGER_CST)
5608 niter_val = int_cst_value (niter);
5610 if (niter_val < stride)
5613 if (dump_file && (dump_flags & TDF_DETAILS))
5615 fprintf (dump_file, "\nStrip Mining is not profitable for loop %d:",
5617 fprintf (dump_file, "number of iterations is too low.\n");
5624 /* Determines when the interchange of LOOP_A and LOOP_B belonging to
5625 SCOP is legal. DEPTH is the number of loops around. */
5628 is_interchange_valid (scop_p scop, int loop_a, int loop_b, int depth)
5631 VEC (ddr_p, heap) *dependence_relations;
5632 VEC (data_reference_p, heap) *datarefs;
5634 struct loop *nest = VEC_index (loop_p, SCOP_LOOP_NEST (scop), loop_a);
5635 lambda_trans_matrix trans;
5637 gcc_assert (loop_a < loop_b);
5639 dependence_relations = VEC_alloc (ddr_p, heap, 10 * 10);
5640 datarefs = VEC_alloc (data_reference_p, heap, 10);
5642 if (!compute_data_dependences_for_loop (nest, true, &datarefs,
5643 &dependence_relations))
5646 if (dump_file && (dump_flags & TDF_DETAILS))
5647 dump_ddrs (dump_file, dependence_relations);
5649 trans = lambda_trans_matrix_new (depth, depth);
5650 lambda_matrix_id (LTM_MATRIX (trans), depth);
5652 lambda_matrix_row_exchange (LTM_MATRIX (trans), 0, loop_b - loop_a);
5654 if (!lambda_transform_legal_p (trans, depth, dependence_relations))
5656 lambda_matrix_row_exchange (LTM_MATRIX (trans), 0, loop_b - loop_a);
5662 free_dependence_relations (dependence_relations);
5663 free_data_refs (datarefs);
5667 /* Loop block the LOOPS innermost loops of GB with stride size STRIDE.
5671 for (i = 0; i <= 50; i++=4)
5672 for (k = 0; k <= 100; k++=4)
5673 for (l = 0; l <= 200; l++=4)
5676 To strip mine the two inner most loops with stride = 4 call:
5678 graphite_trans_bb_block (A, 4, 2)
5680 for (i = 0; i <= 50; i++)
5681 for (kk = 0; kk <= 100; kk+=4)
5682 for (ll = 0; ll <= 200; ll+=4)
5683 for (k = kk; k <= min (100, kk + 3); k++)
5684 for (l = ll; l <= min (200, ll + 3); l++)
5689 graphite_trans_bb_block (graphite_bb_p gb, int stride, int loops)
5692 int nb_loops = gbb_nb_loops (gb);
5693 int start = nb_loops - loops;
5694 scop_p scop = GBB_SCOP (gb);
5696 gcc_assert (scop_contains_loop (scop, gbb_loop (gb)));
5698 for (i = start ; i < nb_loops; i++)
5699 for (j = i + 1; j < nb_loops; j++)
5700 if (!is_interchange_valid (scop, i, j, nb_loops))
5702 if (dump_file && (dump_flags & TDF_DETAILS))
5704 "\nInterchange not valid for loops %d and %d:\n", i, j);
5707 else if (dump_file && (dump_flags & TDF_DETAILS))
5709 "\nInterchange valid for loops %d and %d:\n", i, j);
5711 /* Check if strip mining is profitable for every loop. */
5712 for (i = 0; i < nb_loops - start; i++)
5713 if (!strip_mine_profitable_p (gb, stride, start + i))
5716 /* Strip mine loops. */
5717 for (i = 0; i < nb_loops - start; i++)
5718 graphite_trans_bb_strip_mine (gb, start + 2 * i, stride);
5720 /* Interchange loops. */
5721 for (i = 1; i < nb_loops - start; i++)
5722 graphite_trans_bb_move_loop (gb, start + 2 * i, start + i);
5724 if (dump_file && (dump_flags & TDF_DETAILS))
5725 fprintf (dump_file, "\nLoops containing BB %d will be loop blocked.\n",
5726 GBB_BB (gb)->index);
5731 /* Loop block LOOPS innermost loops of a loop nest. BBS represent the
5732 basic blocks that belong to the loop nest to be blocked. */
5735 graphite_trans_loop_block (VEC (graphite_bb_p, heap) *bbs, int loops)
5739 bool transform_done = false;
5741 /* TODO: - Calculate the stride size automatically. */
5742 int stride_size = 64;
5744 for (i = 0; VEC_iterate (graphite_bb_p, bbs, i, gb); i++)
5745 transform_done |= graphite_trans_bb_block (gb, stride_size, loops);
5747 return transform_done;
5750 /* Loop block all basic blocks of SCOP. Return false when the
5751 transform is not performed. */
5754 graphite_trans_scop_block (scop_p scop)
5760 bool perfect = true;
5761 bool transform_done = false;
5763 VEC (graphite_bb_p, heap) *bbs = VEC_alloc (graphite_bb_p, heap, 3);
5764 int max_schedule = scop_max_loop_depth (scop) + 1;
5765 lambda_vector last_schedule = lambda_vector_new (max_schedule);
5767 if (VEC_length (graphite_bb_p, SCOP_BBS (scop)) == 0)
5770 /* Get the data of the first bb. */
5771 gb = VEC_index (graphite_bb_p, SCOP_BBS (scop), 0);
5772 last_nb_loops = gbb_nb_loops (gb);
5773 lambda_vector_copy (GBB_STATIC_SCHEDULE (gb), last_schedule,
5775 VEC_safe_push (graphite_bb_p, heap, bbs, gb);
5777 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
5779 /* We did the first bb before. */
5783 nb_loops = gbb_nb_loops (gb);
5785 /* If the number of loops is unchanged and only the last element of the
5786 schedule changes, we stay in the loop nest. */
5787 if (nb_loops == last_nb_loops
5788 && (last_schedule [nb_loops + 1]
5789 != GBB_STATIC_SCHEDULE (gb)[nb_loops + 1]))
5791 VEC_safe_push (graphite_bb_p, heap, bbs, gb);
5795 /* Otherwise, we left the innermost loop. So check, if the last bb was in
5796 a perfect loop nest and how many loops are contained in this perfect
5799 Count the number of zeros from the end of the schedule. They are the
5800 number of surrounding loops.
5803 last_bb 2 3 2 0 0 0 0 3
5807 last_bb 2 3 2 0 0 0 0 3
5811 If there is no zero, there were other bbs in outer loops and the loop
5812 nest is not perfect. */
5813 for (j = last_nb_loops - 1; j >= 0; j--)
5815 if (last_schedule [j] != 0
5816 || (j <= nb_loops && GBB_STATIC_SCHEDULE (gb)[j] == 1))
5825 /* Found perfect loop nest. */
5826 if (perfect && last_nb_loops - j >= 2)
5827 transform_done |= graphite_trans_loop_block (bbs, last_nb_loops - j);
5829 /* Check if we start with a new loop.
5833 last_bb 2 3 2 0 0 0 0 3
5836 Here we start with the loop "2 3 2 0 0 1"
5838 last_bb 2 3 2 0 0 0 0 3
5841 But here not, so the loop nest can never be perfect. */
5843 perfect = (GBB_STATIC_SCHEDULE (gb)[nb_loops] == 0);
5845 /* Update the last_bb infos. We do not do that for the bbs in the same
5846 loop, as the data we use is not changed. */
5847 last_nb_loops = nb_loops;
5848 lambda_vector_copy (GBB_STATIC_SCHEDULE (gb), last_schedule,
5850 VEC_truncate (graphite_bb_p, bbs, 0);
5851 VEC_safe_push (graphite_bb_p, heap, bbs, gb);
5854 /* Check if the last loop nest was perfect. It is the same check as above,
5855 but the comparison with the next bb is missing. */
5856 for (j = last_nb_loops - 1; j >= 0; j--)
5857 if (last_schedule [j] != 0)
5865 /* Found perfect loop nest. */
5866 if (last_nb_loops - j > 0)
5867 transform_done |= graphite_trans_loop_block (bbs, last_nb_loops - j);
5868 VEC_free (graphite_bb_p, heap, bbs);
5870 return transform_done;
5873 /* Apply graphite transformations to all the basic blocks of SCOP. */
5876 graphite_apply_transformations (scop_p scop)
5878 bool transform_done = false;
5880 /* Sort the list of bbs. Keep them always sorted. */
5881 graphite_sort_gbbs (scop);
5883 if (flag_loop_block)
5884 transform_done = graphite_trans_scop_block (scop);
5886 /* Generate code even if we did not apply any real transformation.
5887 This also allows to check the performance for the identity
5888 transformation: GIMPLE -> GRAPHITE -> GIMPLE
5889 Keep in mind that CLooG optimizes in control, so the loop structure
5890 may change, even if we only use -fgraphite-identity. */
5891 if (flag_graphite_identity)
5892 transform_done = true;
5894 return transform_done;
5897 /* We limit all SCoPs to SCoPs, that are completely surrounded by a loop.
5907 * SCoP frontier, as this line is not surrounded by any loop. *
5911 This is necessary as scalar evolution and parameter detection need a
5912 outermost loop to initialize parameters correctly.
5914 TODO: FIX scalar evolution and parameter detection to allow more flexible
5920 VEC (sd_region, heap) *tmp_scops = VEC_alloc (sd_region, heap, 3);
5925 for (i = 0; VEC_iterate (scop_p, current_scops, i, scop); i++)
5929 build_scop_bbs (scop);
5931 if (!build_scop_loop_nests (scop))
5934 for (j = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), j, loop); j++)
5935 if (!loop_in_scop_p (loop_outer (loop), scop))
5937 sd_region open_scop;
5938 open_scop.entry = loop->header;
5939 open_scop.exit = single_exit (loop)->dest;
5940 VEC_safe_push (sd_region, heap, tmp_scops, &open_scop);
5944 free_scops (current_scops);
5945 current_scops = VEC_alloc (scop_p, heap, 3);
5947 create_sese_edges (tmp_scops);
5948 build_graphite_scops (tmp_scops);
5949 VEC_free (sd_region, heap, tmp_scops);
5952 /* Perform a set of linear transforms on the loops of the current
5956 graphite_transform_loops (void)
5961 if (number_of_loops () <= 1)
5964 current_scops = VEC_alloc (scop_p, heap, 3);
5965 recompute_all_dominators ();
5967 if (dump_file && (dump_flags & TDF_DETAILS))
5968 fprintf (dump_file, "Graphite loop transformations \n");
5970 initialize_original_copy_tables ();
5971 cloog_initialize ();
5975 if (dump_file && (dump_flags & TDF_DETAILS))
5976 fprintf (dump_file, "\nnumber of SCoPs: %d\n",
5977 VEC_length (scop_p, current_scops));
5979 for (i = 0; VEC_iterate (scop_p, current_scops, i, scop); i++)
5981 build_scop_bbs (scop);
5982 if (!build_scop_loop_nests (scop))
5985 build_scop_canonical_schedules (scop);
5986 build_bb_loops (scop);
5987 if (!build_scop_conditions (scop))
5989 find_scop_parameters (scop);
5990 build_scop_context (scop);
5992 if (dump_file && (dump_flags & TDF_DETAILS))
5994 fprintf (dump_file, "\n(In SCoP %d:\n", i);
5995 fprintf (dump_file, "\nnumber of bbs: %d\n",
5996 VEC_length (graphite_bb_p, SCOP_BBS (scop)));
5997 fprintf (dump_file, "\nnumber of loops: %d)\n",
5998 VEC_length (loop_p, SCOP_LOOP_NEST (scop)));
6001 if (!build_scop_iteration_domain (scop))
6004 build_scop_data_accesses (scop);
6005 build_scop_dynamic_schedules (scop);
6007 if (dump_file && (dump_flags & TDF_DETAILS))
6009 int nbrefs = nb_data_refs_in_scop (scop);
6010 fprintf (dump_file, "\nnumber of data refs: %d\n", nbrefs);
6013 if (graphite_apply_transformations (scop))
6014 gloog (scop, find_transform (scop));
6015 #ifdef ENABLE_CHECKING
6018 struct clast_stmt *stmt = find_transform (scop);
6019 cloog_clast_free (stmt);
6025 free_scops (current_scops);
6027 free_original_copy_tables ();
6030 #else /* If Cloog is not available: #ifndef HAVE_cloog. */
6033 graphite_transform_loops (void)
6035 sorry ("Graphite loop optimizations cannot be used");