1 /* Gimple Represented as Polyhedra.
2 Copyright (C) 2006, 2007, 2008 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 "pointer-set.h"
58 #include "cloog/cloog.h"
61 static VEC (scop_p, heap) *current_scops;
63 /* Debug the list of old induction variables for this SCOP. */
66 debug_oldivs (scop_p scop)
71 fprintf (stderr, "Old IVs:");
73 for (i = 0; VEC_iterate (name_tree, SCOP_OLDIVS (scop), i, oldiv); i++)
75 fprintf (stderr, "(");
76 print_generic_expr (stderr, oldiv->t, 0);
77 fprintf (stderr, ", %s, %d)\n", oldiv->name, oldiv->loop->num);
79 fprintf (stderr, "\n");
82 /* Debug the loops around basic block GB. */
85 debug_loop_vec (graphite_bb_p gb)
90 fprintf (stderr, "Loop Vec:");
92 for (i = 0; VEC_iterate (loop_p, GBB_LOOPS (gb), i, loop); i++)
93 fprintf (stderr, "%d: %d, ", i, loop ? loop->num : -1);
95 fprintf (stderr, "\n");
98 /* Push (IV, NAME) on STACK. */
101 loop_iv_stack_push (loop_iv_stack stack, tree iv, const char *name)
103 name_tree named_iv = XNEW (struct name_tree);
106 named_iv->name = name;
107 VEC_safe_push (name_tree, heap, *stack, named_iv);
110 /* Pops an element out of STACK. */
113 loop_iv_stack_pop (loop_iv_stack stack)
115 VEC_pop (name_tree, *stack);
118 /* Get the IV at INDEX in STACK. */
121 loop_iv_stack_get_iv (loop_iv_stack stack, int index)
123 name_tree named_iv = VEC_index (name_tree, *stack, index);
128 /* Get the IV from its NAME in STACK. */
131 loop_iv_stack_get_iv_from_name (loop_iv_stack stack, const char* name)
136 for (i = 0; VEC_iterate (name_tree, *stack, i, iv); i++)
137 if (!strcmp (name, iv->name))
143 /* Prints on stderr the contents of STACK. */
146 loop_iv_stack_debug (loop_iv_stack stack)
152 fprintf (stderr, "(");
154 for (i = 0; VEC_iterate (name_tree, *stack, i, iv); i++)
159 fprintf (stderr, " ");
160 fprintf (stderr, "%s:", iv->name);
161 print_generic_expr (stderr, iv->t, 0);
164 fprintf (stderr, ")\n");
167 /* In SCOP, get the induction variable from NAME. OLD is the original
168 loop that contained the definition of NAME. */
171 get_old_iv_from_ssa_name (scop_p scop, loop_p old, tree name)
173 tree var = SSA_NAME_VAR (name);
177 for (i = 0; VEC_iterate (name_tree, SCOP_OLDIVS (scop), i, oldiv); i++)
179 loop_p current = old;
184 && oldiv->loop == current)
187 current = loop_outer (current);
194 /* Returns a new loop_to_cloog_loop_str structure. */
196 static inline struct loop_to_cloog_loop_str *
197 new_loop_to_cloog_loop_str (int loop_num,
199 CloogLoop *cloog_loop)
201 struct loop_to_cloog_loop_str *result;
203 result = XNEW (struct loop_to_cloog_loop_str);
204 result->loop_num = loop_num;
205 result->cloog_loop = cloog_loop;
206 result->loop_position = loop_position;
211 /* Hash function for SCOP_LOOP2CLOOG_LOOP hash table. */
214 hash_loop_to_cloog_loop (const void *elt)
216 return ((const struct loop_to_cloog_loop_str *) elt)->loop_num;
219 /* Equality function for SCOP_LOOP2CLOOG_LOOP hash table. */
222 eq_loop_to_cloog_loop (const void *el1, const void *el2)
224 const struct loop_to_cloog_loop_str *elt1, *elt2;
226 elt1 = (const struct loop_to_cloog_loop_str *) el1;
227 elt2 = (const struct loop_to_cloog_loop_str *) el2;
228 return elt1->loop_num == elt2->loop_num;
231 /* Compares two graphite bbs and returns an integer less than, equal to, or
232 greater than zero if the first argument is considered to be respectively
233 less than, equal to, or greater than the second.
234 We compare using the lexicographic order of the static schedules. */
237 gbb_compare (const void *p_1, const void *p_2)
239 const struct graphite_bb *const gbb_1
240 = *(const struct graphite_bb *const*) p_1;
241 const struct graphite_bb *const gbb_2
242 = *(const struct graphite_bb *const*) p_2;
244 return lambda_vector_compare (GBB_STATIC_SCHEDULE (gbb_1),
245 gbb_nb_loops (gbb_1) + 1,
246 GBB_STATIC_SCHEDULE (gbb_2),
247 gbb_nb_loops (gbb_2) + 1);
250 /* Sort graphite bbs in SCOP. */
253 graphite_sort_gbbs (scop_p scop)
255 VEC (graphite_bb_p, heap) *bbs = SCOP_BBS (scop);
257 qsort (VEC_address (graphite_bb_p, bbs),
258 VEC_length (graphite_bb_p, bbs),
259 sizeof (graphite_bb_p), gbb_compare);
262 /* Dump conditions of a graphite basic block GBB on FILE. */
265 dump_gbb_conditions (FILE *file, graphite_bb_p gbb)
269 VEC (gimple, heap) *conditions = GBB_CONDITIONS (gbb);
271 if (VEC_empty (gimple, conditions))
274 fprintf (file, "\tbb %d\t: cond = {", GBB_BB (gbb)->index);
276 for (i = 0; VEC_iterate (gimple, conditions, i, stmt); i++)
277 print_gimple_stmt (file, stmt, 0, 0);
279 fprintf (file, "}\n");
282 /* Converts the graphite scheduling function into a cloog scattering
283 matrix. This scattering matrix is used to limit the possible cloog
284 output to valid programs in respect to the scheduling function.
286 SCATTERING_DIMENSIONS specifies the dimensionality of the scattering
287 matrix. CLooG 0.14.0 and previous versions require, that all scattering
288 functions of one CloogProgram have the same dimensionality, therefore we
289 allow to specify it. (Should be removed in future versions) */
292 schedule_to_scattering (graphite_bb_p gb, int scattering_dimensions)
295 scop_p scop = GBB_SCOP (gb);
297 int nb_iterators = gbb_nb_loops (gb);
299 /* The cloog scattering matrix consists of these colums:
301 scattering_dimensions cols = Scattering dimensions,
302 nb_iterators cols = bb's iterators,
303 scop_nb_params cols = Parameters,
308 scattering_dimensions = 5
318 s1 s2 s3 s4 s5 i p1 p2 1
319 1 0 0 0 0 0 0 0 -4 = 0
320 0 1 0 0 0 -1 0 0 0 = 0
321 0 0 1 0 0 0 0 0 -5 = 0 */
322 int nb_params = scop_nb_params (scop);
323 int nb_cols = 1 + scattering_dimensions + nb_iterators + nb_params + 1;
324 int col_const = nb_cols - 1;
325 int col_iter_offset = 1 + scattering_dimensions;
327 CloogMatrix *scat = cloog_matrix_alloc (scattering_dimensions, nb_cols);
329 gcc_assert (scattering_dimensions >= nb_iterators * 2 + 1);
331 /* Initialize the identity matrix. */
332 for (i = 0; i < scattering_dimensions; i++)
333 value_set_si (scat->p[i][i + 1], 1);
335 /* Textual order outside the first loop */
336 value_set_si (scat->p[0][col_const], -GBB_STATIC_SCHEDULE (gb)[0]);
338 /* For all surrounding loops. */
339 for (i = 0; i < nb_iterators; i++)
341 int schedule = GBB_STATIC_SCHEDULE (gb)[i + 1];
343 /* Iterations of this loop. */
344 value_set_si (scat->p[2 * i + 1][col_iter_offset + i], -1);
346 /* Textual order inside this loop. */
347 value_set_si (scat->p[2 * i + 2][col_const], -schedule);
353 /* Print the schedules of GB to FILE with INDENT white spaces before.
354 VERBOSITY determines how verbose the code pretty printers are. */
357 print_graphite_bb (FILE *file, graphite_bb_p gb, int indent, int verbosity)
359 CloogMatrix *scattering;
362 fprintf (file, "\nGBB (\n");
364 print_loops_bb (file, GBB_BB (gb), indent+2, verbosity);
368 fprintf (file, " (domain: \n");
369 cloog_matrix_print (dump_file, GBB_DOMAIN (gb));
370 fprintf (file, " )\n");
373 if (GBB_STATIC_SCHEDULE (gb))
375 fprintf (file, " (static schedule: ");
376 print_lambda_vector (file, GBB_STATIC_SCHEDULE (gb),
377 gbb_nb_loops (gb) + 1);
378 fprintf (file, " )\n");
383 fprintf (file, " (contained loops: \n");
384 for (i = 0; VEC_iterate (loop_p, GBB_LOOPS (gb), i, loop); i++)
386 fprintf (file, " iterator %d => NULL \n", i);
388 fprintf (file, " iterator %d => loop %d \n", i,
390 fprintf (file, " )\n");
393 if (GBB_DATA_REFS (gb))
394 dump_data_references (file, GBB_DATA_REFS (gb));
396 if (GBB_CONDITIONS (gb))
398 fprintf (file, " (conditions: \n");
399 dump_gbb_conditions (dump_file, gb);
400 fprintf (file, " )\n");
404 && GBB_STATIC_SCHEDULE (gb))
406 fprintf (file, " (scattering: \n");
407 scattering = schedule_to_scattering (gb, 2 * gbb_nb_loops (gb) + 1);
408 cloog_matrix_print (file, scattering);
409 cloog_matrix_free (scattering);
410 fprintf (file, " )\n");
413 fprintf (file, ")\n");
416 /* Print to STDERR the schedules of GB with VERBOSITY level. */
419 debug_gbb (graphite_bb_p gb, int verbosity)
421 print_graphite_bb (stderr, gb, 0, verbosity);
425 /* Print SCOP to FILE. VERBOSITY determines how verbose the pretty
429 print_scop (FILE *file, scop_p scop, int verbosity)
434 fprintf (file, "\nSCoP_%d_%d (\n",
435 SCOP_ENTRY (scop)->index, SCOP_EXIT (scop)->index);
437 fprintf (file, " (cloog: \n");
438 cloog_program_print (file, SCOP_PROG (scop));
439 fprintf (file, " )\n");
446 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
447 print_graphite_bb (file, gb, 0, verbosity);
450 fprintf (file, ")\n");
453 /* Print all the SCOPs to FILE. VERBOSITY determines how verbose the
454 code pretty printers are. */
457 print_scops (FILE *file, int verbosity)
462 for (i = 0; VEC_iterate (scop_p, current_scops, i, scop); i++)
463 print_scop (file, scop, verbosity);
466 /* Debug SCOP. VERBOSITY determines how verbose the code pretty
470 debug_scop (scop_p scop, int verbosity)
472 print_scop (stderr, scop, verbosity);
475 /* Debug all SCOPs from CURRENT_SCOPS. VERBOSITY determines how
476 verbose the code pretty printers are. */
479 debug_scops (int verbosity)
481 print_scops (stderr, verbosity);
484 /* Return true when BB is contained in SCOP. */
487 bb_in_scop_p (basic_block bb, scop_p scop)
489 return bitmap_bit_p (SCOP_BBS_B (scop), bb->index);
492 /* Pretty print to FILE the SCOP in DOT format. */
495 dot_scop_1 (FILE *file, scop_p scop)
500 basic_block entry = SCOP_ENTRY (scop);
501 basic_block exit = SCOP_EXIT (scop);
503 fprintf (file, "digraph SCoP_%d_%d {\n", entry->index,
509 fprintf (file, "%d [shape=triangle];\n", bb->index);
512 fprintf (file, "%d [shape=box];\n", bb->index);
514 if (bb_in_scop_p (bb, scop))
515 fprintf (file, "%d [color=red];\n", bb->index);
517 FOR_EACH_EDGE (e, ei, bb->succs)
518 fprintf (file, "%d -> %d;\n", bb->index, e->dest->index);
521 fputs ("}\n\n", file);
524 /* Display SCOP using dotty. */
527 dot_scop (scop_p scop)
529 dot_scop_1 (stderr, scop);
532 /* Pretty print all SCoPs in DOT format and mark them with different colors.
533 If there are not enough colors, paint later SCoPs gray.
535 - "*" after the node number: entry of a SCoP,
536 - "#" after the node number: exit of a SCoP,
537 - "()" entry or exit not part of SCoP. */
540 dot_all_scops_1 (FILE *file)
549 /* Disable debugging while printing graph. */
550 int tmp_dump_flags = dump_flags;
553 fprintf (file, "digraph all {\n");
557 int part_of_scop = false;
559 /* Use HTML for every bb label. So we are able to print bbs
560 which are part of two different SCoPs, with two different
561 background colors. */
562 fprintf (file, "%d [label=<\n <TABLE BORDER=\"0\" CELLBORDER=\"1\" ",
564 fprintf (file, "CELLSPACING=\"0\">\n");
566 /* Select color for SCoP. */
567 for (i = 0; VEC_iterate (scop_p, current_scops, i, scop); i++)
568 if (bb_in_scop_p (bb, scop)
569 || (SESE_EXIT (SCOP_REGION (scop)) && SCOP_EXIT (scop) == bb)
570 || (SESE_ENTRY (SCOP_REGION (scop)) && SCOP_ENTRY (scop) == bb))
629 fprintf (file, " <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">", color);
631 if (!bb_in_scop_p (bb, scop))
632 fprintf (file, " (");
634 if (SESE_ENTRY (SCOP_REGION (scop))
635 && SESE_EXIT (SCOP_REGION (scop))
636 && bb == SCOP_ENTRY (scop)
637 && bb == SCOP_EXIT (scop))
638 fprintf (file, " %d*# ", bb->index);
639 else if (SESE_ENTRY (SCOP_REGION (scop))
640 && bb == SCOP_ENTRY (scop))
641 fprintf (file, " %d* ", bb->index);
642 else if (SESE_EXIT (SCOP_REGION (scop))
643 && bb == SCOP_EXIT (scop))
644 fprintf (file, " %d# ", bb->index);
646 fprintf (file, " %d ", bb->index);
648 if (!bb_in_scop_p (bb, scop))
651 fprintf (file, "</TD></TR>\n");
658 fprintf (file, " <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">");
659 fprintf (file, " %d </TD></TR>\n", bb->index);
662 fprintf (file, " </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n");
667 FOR_EACH_EDGE (e, ei, bb->succs)
668 fprintf (file, "%d -> %d;\n", bb->index, e->dest->index);
671 fputs ("}\n\n", file);
673 /* Enable debugging again. */
674 dump_flags = tmp_dump_flags;
677 /* Display all SCoPs using dotty. */
682 /* When debugging, enable the following code. This cannot be used
683 in production compilers because it calls "system". */
685 FILE *stream = fopen ("/tmp/allscops.dot", "w");
688 dot_all_scops_1 (stream);
691 system ("dotty /tmp/allscops.dot");
693 dot_all_scops_1 (stderr);
697 /* Returns true when LOOP is in SCOP. */
700 loop_in_scop_p (struct loop *loop, scop_p scop)
702 return (bb_in_scop_p (loop->header, scop)
703 && bb_in_scop_p (loop->latch, scop));
706 /* Returns the outermost loop in SCOP that contains BB. */
709 outermost_loop_in_scop (scop_p scop, basic_block bb)
713 nest = bb->loop_father;
714 while (loop_outer (nest) && loop_in_scop_p (loop_outer (nest), scop))
715 nest = loop_outer (nest);
720 /* Returns the block preceding the entry of SCOP. */
723 block_before_scop (scop_p scop)
725 return SESE_ENTRY (SCOP_REGION (scop))->src;
728 /* Return true when EXPR is an affine function in LOOP with parameters
729 instantiated relative to SCOP_ENTRY. */
732 loop_affine_expr (basic_block scop_entry, struct loop *loop, tree expr)
734 int n = scop_entry->loop_father->num;
735 tree scev = analyze_scalar_evolution (loop, expr);
737 scev = instantiate_scev (scop_entry, loop, scev);
739 return (evolution_function_is_invariant_p (scev, n)
740 || evolution_function_is_affine_multivariate_p (scev, n));
743 /* Return true if the operand OP is simple. */
746 is_simple_operand (loop_p loop, gimple stmt, tree op)
748 /* It is not a simple operand when it is a declaration, */
750 /* or a structure, */
751 || AGGREGATE_TYPE_P (TREE_TYPE (op))
752 /* or a memory access that cannot be analyzed by the data
753 reference analysis. */
754 || ((handled_component_p (op) || INDIRECT_REF_P (op))
755 && !stmt_simple_memref_p (loop, stmt, op)))
761 /* Return true only when STMT is simple enough for being handled by
762 Graphite. This depends on SCOP_ENTRY, as the parametetrs are
763 initialized relatively to this basic block. */
766 stmt_simple_for_scop_p (basic_block scop_entry, gimple stmt)
768 basic_block bb = gimple_bb (stmt);
769 struct loop *loop = bb->loop_father;
771 /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
772 Calls have side-effects, except those to const or pure
774 if (gimple_has_volatile_ops (stmt)
775 || (gimple_code (stmt) == GIMPLE_CALL
776 && !(gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE)))
777 || (gimple_code (stmt) == GIMPLE_ASM))
780 switch (gimple_code (stmt))
790 enum tree_code code = gimple_cond_code (stmt);
792 /* We can only handle this kind of conditional expressions.
793 For inequalities like "if (i != 3 * k)" we need unions of
794 polyhedrons. Expressions like "if (a)" or "if (a == 15)" need
795 them for the else branch. */
796 if (!(code == LT_EXPR
805 FOR_EACH_SSA_TREE_OPERAND (op, stmt, op_iter, SSA_OP_ALL_USES)
806 if (!loop_affine_expr (scop_entry, loop, op))
814 enum tree_code code = gimple_assign_rhs_code (stmt);
816 switch (get_gimple_rhs_class (code))
818 case GIMPLE_UNARY_RHS:
819 case GIMPLE_SINGLE_RHS:
820 return (is_simple_operand (loop, stmt, gimple_assign_lhs (stmt))
821 && is_simple_operand (loop, stmt, gimple_assign_rhs1 (stmt)));
823 case GIMPLE_BINARY_RHS:
824 return (is_simple_operand (loop, stmt, gimple_assign_lhs (stmt))
825 && is_simple_operand (loop, stmt, gimple_assign_rhs1 (stmt))
826 && is_simple_operand (loop, stmt, gimple_assign_rhs2 (stmt)));
828 case GIMPLE_INVALID_RHS:
837 size_t n = gimple_call_num_args (stmt);
838 tree lhs = gimple_call_lhs (stmt);
840 for (i = 0; i < n; i++)
842 tree arg = gimple_call_arg (stmt, i);
844 if (!(is_simple_operand (loop, stmt, lhs)
845 && is_simple_operand (loop, stmt, arg)))
853 /* These nodes cut a new scope. */
860 /* Returns the statement of BB that contains a harmful operation: that
861 can be a function call with side effects, the induction variables
862 are not linear with respect to SCOP_ENTRY, etc. The current open
863 scop should end before this statement. */
866 harmful_stmt_in_bb (basic_block scop_entry, basic_block bb)
868 gimple_stmt_iterator gsi;
870 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
871 if (!stmt_simple_for_scop_p (scop_entry, gsi_stmt (gsi)))
872 return gsi_stmt (gsi);
877 /* Store the GRAPHITE representation of BB. */
880 new_graphite_bb (scop_p scop, basic_block bb)
882 struct graphite_bb *gbb = XNEW (struct graphite_bb);
886 GBB_SCOP (gbb) = scop;
887 GBB_DATA_REFS (gbb) = NULL;
888 GBB_DOMAIN (gbb) = NULL;
889 GBB_CONDITIONS (gbb) = NULL;
890 GBB_CONDITION_CASES (gbb) = NULL;
891 GBB_LOOPS (gbb) = NULL;
892 VEC_safe_push (graphite_bb_p, heap, SCOP_BBS (scop), gbb);
893 bitmap_set_bit (SCOP_BBS_B (scop), bb->index);
899 free_graphite_bb (struct graphite_bb *gbb)
901 if (GBB_DOMAIN (gbb))
902 cloog_matrix_free (GBB_DOMAIN (gbb));
904 free_data_refs (GBB_DATA_REFS (gbb));
905 VEC_free (gimple, heap, GBB_CONDITIONS (gbb));
906 VEC_free (gimple, heap, GBB_CONDITION_CASES (gbb));
907 VEC_free (loop_p, heap, GBB_LOOPS (gbb));
909 GBB_BB (gbb)->aux = 0;
913 /* Creates a new scop starting with ENTRY. */
916 new_scop (edge entry)
918 scop_p scop = XNEW (struct scop);
920 SCOP_REGION (scop) = XNEW (struct sese);
921 SESE_ENTRY (SCOP_REGION (scop)) = entry;
922 SESE_EXIT (SCOP_REGION (scop)) = NULL;
923 SCOP_BBS (scop) = VEC_alloc (graphite_bb_p, heap, 3);
924 SCOP_OLDIVS (scop) = VEC_alloc (name_tree, heap, 3);
925 SCOP_BBS_B (scop) = BITMAP_ALLOC (NULL);
926 SCOP_LOOPS (scop) = BITMAP_ALLOC (NULL);
927 SCOP_LOOP_NEST (scop) = VEC_alloc (loop_p, heap, 3);
928 SCOP_PARAMS (scop) = VEC_alloc (name_tree, heap, 3);
929 SCOP_PROG (scop) = cloog_program_malloc ();
930 cloog_program_set_names (SCOP_PROG (scop), cloog_names_malloc ());
931 SCOP_LOOP2CLOOG_LOOP (scop) = htab_create (10, hash_loop_to_cloog_loop,
932 eq_loop_to_cloog_loop,
940 free_scop (scop_p scop)
944 struct graphite_bb *gb;
946 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
947 free_graphite_bb (gb);
949 VEC_free (graphite_bb_p, heap, SCOP_BBS (scop));
950 BITMAP_FREE (SCOP_BBS_B (scop));
951 BITMAP_FREE (SCOP_LOOPS (scop));
952 VEC_free (loop_p, heap, SCOP_LOOP_NEST (scop));
953 VEC_free (name_tree, heap, SCOP_OLDIVS (scop));
955 for (i = 0; VEC_iterate (name_tree, SCOP_PARAMS (scop), i, p); i++)
958 VEC_free (name_tree, heap, SCOP_PARAMS (scop));
959 cloog_program_free (SCOP_PROG (scop));
960 htab_delete (SCOP_LOOP2CLOOG_LOOP (scop));
961 XDELETE (SCOP_REGION (scop));
965 /* Deletes all scops in SCOPS. */
968 free_scops (VEC (scop_p, heap) *scops)
973 for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++)
976 VEC_free (scop_p, heap, scops);
979 typedef enum gbb_type {
981 GBB_LOOP_SING_EXIT_HEADER,
982 GBB_LOOP_MULT_EXIT_HEADER,
989 /* Detect the type of BB. Loop headers are only marked, if they are
990 new. This means their loop_father is different to LAST_LOOP.
991 Otherwise they are treated like any other bb and their type can be
995 get_bb_type (basic_block bb, struct loop *last_loop)
997 VEC (basic_block, heap) *dom;
999 struct loop *loop = bb->loop_father;
1001 /* Check, if we entry into a new loop. */
1002 if (loop != last_loop)
1004 if (single_exit (loop) != NULL)
1005 return GBB_LOOP_SING_EXIT_HEADER;
1006 else if (loop->num != 0)
1007 return GBB_LOOP_MULT_EXIT_HEADER;
1009 return GBB_COND_HEADER;
1012 dom = get_dominated_by (CDI_DOMINATORS, bb);
1013 nb_dom = VEC_length (basic_block, dom);
1014 VEC_free (basic_block, heap, dom);
1018 nb_suc = VEC_length (edge, bb->succs);
1019 if (nb_dom == 1 && nb_suc == 1)
1022 return GBB_COND_HEADER;
1025 /* Moves the scops from SOURCE to TARGET and clean up SOURCE. */
1028 move_scops (VEC (scop_p, heap) **source, VEC (scop_p, heap) **target)
1033 for (i = 0; VEC_iterate (scop_p, *source, i, s); i++)
1034 VEC_safe_push (scop_p, heap, *target, s);
1036 VEC_free (scop_p, heap, *source);
1039 /* Store information needed by scopdet_* functions. */
1043 /* Where the last open scop would stop if the current BB is harmful. */
1046 /* Where the next scop would start if the current BB is harmful. */
1049 /* The bb or one of its children contains open loop exits. That means
1050 loop exit nodes that are not surrounded by a loop dominated by bb. */
1053 /* The bb or one of its children contains only structures we can handle. */
1057 static struct scopdet_info build_scops_1 (edge, VEC (scop_p, heap) **,
1060 /* Checks, if a bb can be added to a SCoP. */
1062 static struct scopdet_info
1063 scopdet_edge_info (edge ee,
1064 VEC (scop_p, heap) **scops, gbb_type type, gimple *stmt)
1067 basic_block bb = ee->dest;
1068 struct loop *loop = bb->loop_father;
1069 struct scopdet_info result;
1070 basic_block scop_entry;
1072 if (VEC_length (scop_p, *scops) != 0)
1073 scop_entry = block_before_scop (VEC_last (scop_p, *scops));
1074 else if (loop->header)
1075 scop_entry = loop->header;
1077 scop_entry = ENTRY_BLOCK_PTR;
1079 *stmt = harmful_stmt_in_bb (scop_entry, bb);
1080 result.difficult = (*stmt != NULL);
1087 result.exits = false;
1092 result.next = single_succ_edge (bb);
1093 result.exits = false;
1097 case GBB_LOOP_SING_EXIT_HEADER:
1099 VEC (scop_p, heap) *tmp_scops = VEC_alloc (scop_p, heap, 3);
1100 struct scopdet_info sinfo;
1102 sinfo = build_scops_1 (ee, &tmp_scops, loop);
1104 result.last = single_exit (bb->loop_father);
1106 if (single_succ_p (result.last->dest)
1107 && get_bb_type (result.last->dest, loop) == GBB_SIMPLE)
1108 result.next = single_succ_edge (result.last->dest);
1110 result.next = split_block (result.last->dest, NULL);
1112 /* If we do not dominate result.next, remove it. It's either
1113 the EXIT_BLOCK_PTR, or another bb dominates it and will
1114 call the scop detection for this bb. */
1115 if (!dominated_by_p (CDI_DOMINATORS, result.next->dest, bb))
1118 if (TREE_CODE (number_of_latch_executions (loop))
1120 result.difficult = true;
1122 if (sinfo.difficult)
1123 move_scops (&tmp_scops, scops);
1125 free_scops (tmp_scops);
1127 result.exits = false;
1128 result.difficult |= sinfo.difficult;
1132 case GBB_LOOP_MULT_EXIT_HEADER:
1134 /* XXX: Handle loop nests with the same header. */
1135 /* XXX: For now we just do not join loops with multiple exits. If the
1136 exits lead to the same bb it may be possible to join the loop. */
1137 VEC (scop_p, heap) *tmp_scops = VEC_alloc (scop_p, heap, 3);
1138 VEC (edge, heap) *exits = get_loop_exit_edges (loop);
1141 build_scops_1 (ee, &tmp_scops, loop);
1143 for (i = 0; VEC_iterate (edge, exits, i, e); i++)
1144 if (dominated_by_p (CDI_DOMINATORS, e->dest, e->src)
1145 && e->dest->loop_father == loop_outer (loop))
1146 build_scops_1 (e, &tmp_scops, e->dest->loop_father);
1150 result.difficult = true;
1151 result.exits = false;
1152 move_scops (&tmp_scops, scops);
1153 VEC_free (edge, heap, exits);
1156 case GBB_COND_HEADER:
1158 VEC (scop_p, heap) *tmp_scops = VEC_alloc (scop_p, heap, 3);
1159 struct scopdet_info sinfo;
1160 VEC (basic_block, heap) *dominated;
1163 basic_block last_bb = NULL;
1166 result.exits = false;
1168 /* First check the successors of BB, and check if it is possible to join
1169 the different branches. */
1170 for (i = 0; VEC_iterate (edge, bb->succs, i, e); i++)
1172 /* Ignore loop exits. They will be handled after the loop body. */
1173 if (is_loop_exit (loop, e->dest))
1175 result.exits = true;
1179 /* Do not follow edges that lead to the end of the
1180 conditions block. For example, in
1190 the edge from 0 => 6. Only check if all paths lead to
1193 if (!single_pred_p (e->dest))
1195 /* Check, if edge leads directly to the end of this
1203 if (e->dest != last_bb)
1204 result.difficult = true;
1209 if (!dominated_by_p (CDI_DOMINATORS, e->dest, bb))
1211 result.difficult = true;
1215 sinfo = build_scops_1 (e, &tmp_scops, loop);
1217 result.exits |= sinfo.exits;
1218 result.last = sinfo.last;
1219 result.difficult |= sinfo.difficult;
1221 /* Checks, if all branches end at the same point.
1222 If that is true, the condition stays joinable.
1223 Have a look at the example above. */
1224 if (sinfo.last && single_succ_p (sinfo.last->dest))
1226 basic_block next_tmp = single_succ (sinfo.last->dest);
1231 last_e = single_succ_edge (sinfo.last->dest);
1234 if (next_tmp != last_bb)
1235 result.difficult = true;
1238 result.difficult = true;
1241 /* If the condition is joinable. */
1242 if (!result.exits && !result.difficult)
1244 /* Only return a next pointer if we dominate this pointer.
1245 Otherwise it will be handled by the bb dominating it. */
1246 if (dominated_by_p (CDI_DOMINATORS, last_bb, bb) && last_bb != bb)
1247 result.next = last_e;
1251 move_scops (&tmp_scops, scops);
1255 /* Scan remaining bbs dominated by BB. */
1256 dominated = get_dominated_by (CDI_DOMINATORS, bb);
1258 for (i = 0; VEC_iterate (basic_block, dominated, i, dom_bb); i++)
1260 /* Ignore loop exits: they will be handled after the loop body. */
1261 if (is_loop_exit (loop, dom_bb))
1263 result.exits = true;
1267 /* Ignore the bbs processed above. */
1268 if (single_pred_p (dom_bb) && single_pred (dom_bb) == bb)
1271 if (single_pred_p (dom_bb))
1272 e = single_pred_edge (dom_bb);
1274 e = split_block (dom_bb, NULL);
1276 if (loop_depth (loop) > loop_depth (dom_bb->loop_father))
1277 sinfo = build_scops_1 (e, &tmp_scops, loop_outer (loop));
1279 sinfo = build_scops_1 (e, &tmp_scops, loop);
1282 result.exits |= sinfo.exits;
1283 result.difficult = true;
1287 VEC_free (basic_block, heap, dominated);
1290 move_scops (&tmp_scops, scops);
1302 /* Split EXIT before STMT when STMT is non NULL. */
1305 split_difficult_bb (basic_block exit, edge *last, gimple stmt)
1307 if (stmt && VEC_length (edge, exit->preds) == 1)
1311 if (stmt == gsi_stmt (gsi_after_labels (exit)))
1315 gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
1317 stmt = gsi_stmt (gsi);
1320 e = split_block (exit, stmt);
1321 set_immediate_dominator (CDI_DOMINATORS, e->dest, e->src);
1322 set_immediate_dominator (CDI_POST_DOMINATORS, e->src, e->dest);
1334 /* End SCOP with edge EXIT. */
1337 end_scop (scop_p scop, edge exit, bool split_entry)
1340 && !single_pred_p (SCOP_ENTRY (scop))
1341 && exit->dest->loop_father == SCOP_ENTRY (scop)->loop_father)
1342 SESE_ENTRY (SCOP_REGION (scop)) = split_block (SCOP_ENTRY (scop), NULL);
1344 SESE_EXIT (SCOP_REGION (scop)) = exit;
1347 /* Creates the SCoPs and writes entry and exit points for every SCoP. */
1349 static struct scopdet_info
1350 build_scops_1 (edge start, VEC (scop_p, heap) **scops, loop_p loop)
1352 edge current = start;
1354 bool in_scop = false;
1355 scop_p open_scop = NULL;
1357 struct scopdet_info sinfo;
1359 /* Initialize result. */
1360 struct scopdet_info result;
1361 result.exits = false;
1362 result.difficult = false;
1366 /* Loop over the dominance tree. If we meet a difficult bb, close
1367 the current SCoP. Loop and condition header start a new layer,
1368 and can only be added if all bbs in deeper layers are simple. */
1369 while (current != NULL)
1371 sinfo = scopdet_edge_info (current, scops,
1372 get_bb_type (current->dest, loop), &stmt);
1374 if (!in_scop && !(sinfo.exits || sinfo.difficult))
1376 open_scop = new_scop (current);
1378 VEC_safe_push (scop_p, heap, *scops, open_scop);
1381 else if (in_scop && (sinfo.exits || sinfo.difficult))
1383 edge exit = split_difficult_bb (current->dest, &sinfo.last, stmt);
1388 end_scop (open_scop, exit, sinfo.difficult);
1392 result.difficult |= sinfo.difficult;
1393 result.exits |= sinfo.exits;
1395 current = sinfo.next;
1398 /* Finish the SCOP, if it is left open. The exit is the bb, that
1399 postdominates sinfo.last. If no such bb exists, we use info.last
1400 or delete the scop. */
1406 for (i = 0; VEC_iterate (edge, sinfo.last->dest->succs, i, e); i++)
1407 if (dominated_by_p (CDI_POST_DOMINATORS, sinfo.last->dest, e->dest))
1409 edge exit = split_difficult_bb (e->dest, &sinfo.last, stmt);
1412 end_scop (open_scop, exit, sinfo.difficult);
1414 end_scop (open_scop, e, sinfo.difficult);
1419 if (SCOP_ENTRY (open_scop) != sinfo.last->dest)
1421 edge exit = split_difficult_bb (sinfo.last->dest, NULL, stmt);
1424 end_scop (open_scop, exit, sinfo.difficult);
1426 end_scop (open_scop, sinfo.last, sinfo.difficult);
1430 VEC_pop (scop_p, *scops);
1431 free_scop (open_scop);
1436 result.last = sinfo.last;
1441 /* Find static control parts. */
1446 struct loop *loop = current_loops->tree_root;
1447 build_scops_1 (single_succ_edge (ENTRY_BLOCK_PTR), ¤t_scops, loop);
1450 /* Gather the basic blocks belonging to the SCOP. */
1453 build_scop_bbs (scop_p scop)
1455 basic_block *stack = XNEWVEC (basic_block, n_basic_blocks + 1);
1456 sbitmap visited = sbitmap_alloc (last_basic_block);
1459 sbitmap_zero (visited);
1460 stack[sp++] = SCOP_ENTRY (scop);
1464 basic_block bb = stack[--sp];
1465 int depth = loop_depth (bb->loop_father);
1466 int num = bb->loop_father->num;
1470 /* Scop's exit is not in the scop. Exclude also bbs, which are
1471 dominated by the SCoP exit. These are e.g. loop latches. */
1472 if (TEST_BIT (visited, bb->index)
1473 || dominated_by_p (CDI_DOMINATORS, bb, SCOP_EXIT (scop))
1474 /* Every block in the scop is dominated by scop's entry. */
1475 || !dominated_by_p (CDI_DOMINATORS, bb, SCOP_ENTRY (scop)))
1478 new_graphite_bb (scop, bb);
1479 SET_BIT (visited, bb->index);
1481 /* First push the blocks that have to be processed last. Note
1482 that this means that the order in which the code is organized
1483 below is important: do not reorder the following code. */
1484 FOR_EACH_EDGE (e, ei, bb->succs)
1485 if (! TEST_BIT (visited, e->dest->index)
1486 && (int) loop_depth (e->dest->loop_father) < depth)
1487 stack[sp++] = e->dest;
1489 FOR_EACH_EDGE (e, ei, bb->succs)
1490 if (! TEST_BIT (visited, e->dest->index)
1491 && (int) loop_depth (e->dest->loop_father) == depth
1492 && e->dest->loop_father->num != num)
1493 stack[sp++] = e->dest;
1495 FOR_EACH_EDGE (e, ei, bb->succs)
1496 if (! TEST_BIT (visited, e->dest->index)
1497 && (int) loop_depth (e->dest->loop_father) == depth
1498 && e->dest->loop_father->num == num
1499 && EDGE_COUNT (e->dest->preds) > 1)
1500 stack[sp++] = e->dest;
1502 FOR_EACH_EDGE (e, ei, bb->succs)
1503 if (! TEST_BIT (visited, e->dest->index)
1504 && (int) loop_depth (e->dest->loop_father) == depth
1505 && e->dest->loop_father->num == num
1506 && EDGE_COUNT (e->dest->preds) == 1)
1507 stack[sp++] = e->dest;
1509 FOR_EACH_EDGE (e, ei, bb->succs)
1510 if (! TEST_BIT (visited, e->dest->index)
1511 && (int) loop_depth (e->dest->loop_father) > depth)
1512 stack[sp++] = e->dest;
1516 sbitmap_free (visited);
1520 /* Record LOOP as occuring in SCOP. */
1523 scop_record_loop (scop_p scop, struct loop *loop)
1528 if (bitmap_bit_p (SCOP_LOOPS (scop), loop->num))
1531 parent = loop_outer (loop);
1532 induction_var = find_induction_var_from_exit_cond (loop);
1534 if (!bb_in_scop_p (parent->latch, scop))
1537 if (induction_var != NULL_TREE)
1539 name_tree oldiv = XNEW (struct name_tree);
1540 oldiv->t = SSA_NAME_VAR (induction_var);
1541 if (DECL_NAME (oldiv->t))
1542 oldiv->name = IDENTIFIER_POINTER (DECL_NAME (oldiv->t));
1545 char *n = XNEWVEC (char, 16);
1546 sprintf (n, "D.%u", DECL_UID (oldiv->t));
1551 VEC_safe_push (name_tree, heap, SCOP_OLDIVS (scop), oldiv);
1554 bitmap_set_bit (SCOP_LOOPS (scop), loop->num);
1555 VEC_safe_push (loop_p, heap, SCOP_LOOP_NEST (scop), loop);
1558 /* Build the loop nests contained in SCOP. */
1561 build_scop_loop_nests (scop_p scop)
1565 struct loop *loop0, *loop1;
1567 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
1569 struct loop *loop = gbb_loop (gb);
1571 /* Only add loops, if they are completely contained in the SCoP. */
1572 if (loop->header == GBB_BB (gb)
1573 && bb_in_scop_p (loop->latch, scop))
1574 scop_record_loop (scop, gbb_loop (gb));
1577 /* Make sure that the loops in the SCOP_LOOP_NEST are ordered. It
1578 can be the case that an inner loop is inserted before an outer
1579 loop. To avoid this, semi-sort once. */
1580 for (i = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), i, loop0); i++)
1582 if (VEC_length (loop_p, SCOP_LOOP_NEST (scop)) == i + 1)
1585 loop1 = VEC_index (loop_p, SCOP_LOOP_NEST (scop), i + 1);
1586 if (loop0->num > loop1->num)
1588 VEC_replace (loop_p, SCOP_LOOP_NEST (scop), i, loop1);
1589 VEC_replace (loop_p, SCOP_LOOP_NEST (scop), i + 1, loop0);
1594 /* Calculate the number of loops around GB in the current SCOP. */
1597 nb_loops_around_gb (graphite_bb_p gb)
1599 scop_p scop = GBB_SCOP (gb);
1600 struct loop *l = gbb_loop (gb);
1603 for (; loop_in_scop_p (l, scop); d++, l = loop_outer (l));
1608 /* Build for BB the static schedule.
1610 The STATIC_SCHEDULE is defined like this:
1629 Static schedules for A to F:
1642 build_scop_canonical_schedules (scop_p scop)
1646 int nb = scop_nb_loops (scop) + 1;
1648 SCOP_STATIC_SCHEDULE (scop) = lambda_vector_new (nb);
1650 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
1652 int offset = nb_loops_around_gb (gb);
1654 /* After leaving a loop, it is possible that the schedule is not
1655 set at zero. This loop reinitializes components located
1658 for (j = offset + 1; j < nb; j++)
1659 if (SCOP_STATIC_SCHEDULE (scop)[j])
1661 memset (&(SCOP_STATIC_SCHEDULE (scop)[j]), 0,
1662 sizeof (int) * (nb - j));
1663 ++SCOP_STATIC_SCHEDULE (scop)[offset];
1667 GBB_STATIC_SCHEDULE (gb) = lambda_vector_new (offset + 1);
1668 lambda_vector_copy (SCOP_STATIC_SCHEDULE (scop),
1669 GBB_STATIC_SCHEDULE (gb), offset + 1);
1671 ++SCOP_STATIC_SCHEDULE (scop)[offset];
1675 /* Build the LOOPS vector for all bbs in SCOP. */
1678 build_bb_loops (scop_p scop)
1683 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
1688 depth = nb_loops_around_gb (gb) - 1;
1690 GBB_LOOPS (gb) = VEC_alloc (loop_p, heap, 3);
1691 VEC_safe_grow_cleared (loop_p, heap, GBB_LOOPS (gb), depth + 1);
1693 loop = GBB_BB (gb)->loop_father;
1695 while (scop_contains_loop (scop, loop))
1697 VEC_replace (loop_p, GBB_LOOPS (gb), depth, loop);
1698 loop = loop_outer (loop);
1704 /* Get the index for parameter VAR in SCOP. */
1707 param_index (tree var, scop_p scop)
1713 gcc_assert (TREE_CODE (var) == SSA_NAME);
1715 for (i = 0; VEC_iterate (name_tree, SCOP_PARAMS (scop), i, p); i++)
1719 nvar = XNEW (struct name_tree);
1722 VEC_safe_push (name_tree, heap, SCOP_PARAMS (scop), nvar);
1723 return VEC_length (name_tree, SCOP_PARAMS (scop)) - 1;
1726 /* Scan EXPR and translate it to an inequality vector INEQ that will
1727 be added, or subtracted, in the constraint domain matrix C at row
1728 R. K is the number of columns for loop iterators in C. */
1731 scan_tree_for_params (scop_p s, tree e, CloogMatrix *c, int r, Value k,
1734 int cst_col, param_col;
1736 if (e == chrec_dont_know)
1739 switch (TREE_CODE (e))
1741 case POLYNOMIAL_CHREC:
1743 tree left = CHREC_LEFT (e);
1744 tree right = CHREC_RIGHT (e);
1745 int var = CHREC_VARIABLE (e);
1747 if (TREE_CODE (right) != INTEGER_CST)
1752 int loop_col = scop_gimple_loop_depth (s, get_loop (var)) + 1;
1755 value_sub_int (c->p[r][loop_col], c->p[r][loop_col],
1756 int_cst_value (right));
1758 value_add_int (c->p[r][loop_col], c->p[r][loop_col],
1759 int_cst_value (right));
1762 switch (TREE_CODE (left))
1764 case POLYNOMIAL_CHREC:
1765 scan_tree_for_params (s, left, c, r, k, subtract);
1769 /* Constant part. */
1772 int v = int_cst_value (left);
1773 cst_col = c->NbColumns - 1;
1778 subtract = subtract ? false : true;
1782 value_sub_int (c->p[r][cst_col], c->p[r][cst_col], v);
1784 value_add_int (c->p[r][cst_col], c->p[r][cst_col], v);
1789 scan_tree_for_params (s, left, c, r, k, subtract);
1796 if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
1800 gcc_assert (host_integerp (TREE_OPERAND (e, 1), 0));
1803 value_set_si (val, int_cst_value (TREE_OPERAND (e, 1)));
1804 value_multiply (k, k, val);
1806 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
1812 gcc_assert (host_integerp (TREE_OPERAND (e, 0), 0));
1815 value_set_si (val, int_cst_value (TREE_OPERAND (e, 0)));
1816 value_multiply (k, k, val);
1818 scan_tree_for_params (s, TREE_OPERAND (e, 1), c, r, k, subtract);
1823 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
1824 scan_tree_for_params (s, TREE_OPERAND (e, 1), c, r, k, subtract);
1828 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
1829 value_oppose (k, k);
1830 scan_tree_for_params (s, TREE_OPERAND (e, 1), c, r, k, subtract);
1834 value_oppose (k, k);
1835 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
1839 param_col = param_index (e, s);
1843 param_col += c->NbColumns - scop_nb_params (s) - 1;
1846 value_subtract (c->p[r][param_col], c->p[r][param_col], k);
1848 value_addto (c->p[r][param_col], c->p[r][param_col], k);
1855 int v = int_cst_value (e);
1856 cst_col = c->NbColumns - 1;
1861 subtract = subtract ? false : true;
1865 value_sub_int (c->p[r][cst_col], c->p[r][cst_col], v);
1867 value_add_int (c->p[r][cst_col], c->p[r][cst_col], v);
1873 case NON_LVALUE_EXPR:
1874 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
1883 /* Data structure for idx_record_params. */
1891 /* For a data reference with an ARRAY_REF as its BASE, record the
1892 parameters occurring in IDX. DTA is passed in as complementary
1893 information, and is used by the automatic walker function. This
1894 function is a callback for for_each_index. */
1897 idx_record_params (tree base, tree *idx, void *dta)
1899 struct irp_data *data = (struct irp_data *) dta;
1901 if (TREE_CODE (base) != ARRAY_REF)
1904 if (TREE_CODE (*idx) == SSA_NAME)
1907 scop_p scop = data->scop;
1908 struct loop *loop = data->loop;
1911 scev = analyze_scalar_evolution (loop, *idx);
1912 scev = instantiate_scev (block_before_scop (scop), loop, scev);
1915 value_set_si (one, 1);
1916 scan_tree_for_params (scop, scev, NULL, 0, one, false);
1923 /* Find parameters with respect to SCOP in BB. We are looking in memory
1924 access functions, conditions and loop bounds. */
1927 find_params_in_bb (scop_p scop, basic_block bb)
1930 data_reference_p dr;
1931 VEC (data_reference_p, heap) *drs;
1932 gimple_stmt_iterator gsi;
1933 struct loop *nest = outermost_loop_in_scop (scop, bb);
1935 /* Find the parameters used in the memory access functions. */
1936 drs = VEC_alloc (data_reference_p, heap, 5);
1937 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1938 find_data_references_in_stmt (nest, gsi_stmt (gsi), &drs);
1940 for (i = 0; VEC_iterate (data_reference_p, drs, i, dr); i++)
1942 struct irp_data irp;
1944 irp.loop = bb->loop_father;
1946 for_each_index (&dr->ref, idx_record_params, &irp);
1950 VEC_free (data_reference_p, heap, drs);
1952 /* Find parameters in conditional statements. */
1953 gsi = gsi_last_bb (bb);
1954 if (!gsi_end_p (gsi))
1956 gimple stmt = gsi_stmt (gsi);
1958 if (gimple_code (stmt) == GIMPLE_COND)
1961 loop_p loop = bb->loop_father;
1965 lhs = gimple_cond_lhs (stmt);
1966 lhs = analyze_scalar_evolution (loop, lhs);
1967 lhs = instantiate_scev (block_before_scop (scop), loop, lhs);
1969 rhs = gimple_cond_rhs (stmt);
1970 rhs = analyze_scalar_evolution (loop, rhs);
1971 rhs = instantiate_scev (block_before_scop (scop), loop, rhs);
1974 scan_tree_for_params (scop, lhs, NULL, 0, one, false);
1975 value_set_si (one, 1);
1976 scan_tree_for_params (scop, rhs, NULL, 0, one, false);
1982 /* Saves in NV the name of variable P->T. */
1985 save_var_name (char **nv, int i, name_tree p)
1987 const char *name = get_name (SSA_NAME_VAR (p->t));
1991 nv[i] = XNEWVEC (char, strlen (name) + 12);
1992 sprintf (nv[i], "%s_%12d", name, SSA_NAME_VERSION (p->t));
1996 nv[i] = XNEWVEC (char, 12);
1997 sprintf (nv[i], "T_%12d", SSA_NAME_VERSION (p->t));
2003 /* Return the maximal loop depth in SCOP. */
2006 scop_max_loop_depth (scop_p scop)
2010 int max_nb_loops = 0;
2012 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gbb); i++)
2014 int nb_loops = gbb_nb_loops (gbb);
2015 if (max_nb_loops < nb_loops)
2016 max_nb_loops = nb_loops;
2019 return max_nb_loops;
2022 /* Initialize Cloog's parameter names from the names used in GIMPLE.
2023 Initialize Cloog's iterator names, using 'graphite_iterator_%d'
2024 from 0 to scop_nb_loops (scop). */
2027 initialize_cloog_names (scop_p scop)
2029 int i, nb_params = VEC_length (name_tree, SCOP_PARAMS (scop));
2030 char **params = XNEWVEC (char *, nb_params);
2031 int nb_iterators = scop_max_loop_depth (scop);
2032 int nb_scattering= cloog_program_nb_scattdims (SCOP_PROG (scop));
2033 char **iterators = XNEWVEC (char *, nb_iterators * 2);
2034 char **scattering = XNEWVEC (char *, nb_scattering);
2037 for (i = 0; VEC_iterate (name_tree, SCOP_PARAMS (scop), i, p); i++)
2038 save_var_name (params, i, p);
2040 cloog_names_set_nb_parameters (cloog_program_names (SCOP_PROG (scop)),
2042 cloog_names_set_parameters (cloog_program_names (SCOP_PROG (scop)),
2045 for (i = 0; i < nb_iterators; i++)
2047 iterators[i] = XNEWVEC (char, 18 + 12);
2048 sprintf (iterators[i], "graphite_iterator_%d", i);
2051 cloog_names_set_nb_iterators (cloog_program_names (SCOP_PROG (scop)),
2053 cloog_names_set_iterators (cloog_program_names (SCOP_PROG (scop)),
2056 for (i = 0; i < nb_scattering; i++)
2058 scattering[i] = XNEWVEC (char, 2 + 12);
2059 sprintf (scattering[i], "s_%d", i);
2062 cloog_names_set_nb_scattering (cloog_program_names (SCOP_PROG (scop)),
2064 cloog_names_set_scattering (cloog_program_names (SCOP_PROG (scop)),
2068 /* Record the parameters used in the SCOP. A variable is a parameter
2069 in a scop if it does not vary during the execution of that scop. */
2072 find_scop_parameters (scop_p scop)
2080 value_set_si (one, 1);
2082 /* Find the parameters used in the loop bounds. */
2083 for (i = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), i, loop); i++)
2085 tree nb_iters = number_of_latch_executions (loop);
2087 if (!chrec_contains_symbols (nb_iters))
2090 nb_iters = analyze_scalar_evolution (loop, nb_iters);
2091 nb_iters = instantiate_scev (block_before_scop (scop), loop, nb_iters);
2092 scan_tree_for_params (scop, nb_iters, NULL, 0, one, false);
2097 /* Find the parameters used in data accesses. */
2098 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
2099 find_params_in_bb (scop, GBB_BB (gb));
2102 /* Build the context constraints for SCOP: constraints and relations
2106 build_scop_context (scop_p scop)
2108 int nb_params = scop_nb_params (scop);
2109 CloogMatrix *matrix = cloog_matrix_alloc (1, nb_params + 2);
2111 /* Insert '0 >= 0' in the context matrix, as it is not allowed to be
2114 value_set_si (matrix->p[0][0], 1);
2116 value_set_si (matrix->p[0][nb_params + 1], 0);
2118 cloog_program_set_context (SCOP_PROG (scop),
2119 cloog_domain_matrix2domain (matrix));
2120 cloog_matrix_free (matrix);
2123 /* Returns a graphite_bb from BB. */
2125 static inline graphite_bb_p
2126 gbb_from_bb (basic_block bb)
2128 return (graphite_bb_p) bb->aux;
2131 /* Add DOMAIN to all the basic blocks in LOOP. */
2134 add_bb_domains (struct loop *loop, CloogMatrix *domain)
2136 basic_block *bbs = get_loop_body (loop);
2139 for (i = 0; i < loop->num_nodes; i++)
2140 if (bbs[i]->loop_father == loop)
2142 graphite_bb_p gbb = gbb_from_bb (bbs[i]);
2143 GBB_DOMAIN (gbb) = cloog_matrix_copy (domain);
2149 /* Builds the constraint matrix for LOOP in SCOP. NB_OUTER_LOOPS is the
2150 number of loops surrounding LOOP in SCOP. OUTER_CSTR gives the
2151 constraints matrix for the surrounding loops. */
2154 build_loop_iteration_domains (scop_p scop, struct loop *loop,
2155 CloogMatrix *outer_cstr, int nb_outer_loops)
2160 int nb_rows = outer_cstr->NbRows + 1;
2161 int nb_cols = outer_cstr->NbColumns + 1;
2163 /* Last column of CSTR is the column of constants. */
2164 int cst_col = nb_cols - 1;
2166 /* The column for the current loop is just after the columns of
2167 other outer loops. */
2168 int loop_col = nb_outer_loops + 1;
2170 tree nb_iters = number_of_latch_executions (loop);
2172 /* When the number of iterations is a constant or a parameter, we
2173 add a constraint for the upper bound of the loop. So add a row
2174 to the constraint matrix before allocating it. */
2175 if (TREE_CODE (nb_iters) == INTEGER_CST
2176 || !chrec_contains_undetermined (nb_iters))
2179 cstr = cloog_matrix_alloc (nb_rows, nb_cols);
2181 /* Copy the outer constraints. */
2182 for (i = 0; i < outer_cstr->NbRows; i++)
2184 /* Copy the eq/ineq and loops columns. */
2185 for (j = 0; j < loop_col; j++)
2186 value_assign (cstr->p[i][j], outer_cstr->p[i][j]);
2188 /* Leave an empty column in CSTR for the current loop, and then
2189 copy the parameter columns. */
2190 for (j = loop_col; j < outer_cstr->NbColumns; j++)
2191 value_assign (cstr->p[i][j + 1], outer_cstr->p[i][j]);
2195 row = outer_cstr->NbRows;
2196 value_set_si (cstr->p[row][0], 1);
2197 value_set_si (cstr->p[row][loop_col], 1);
2199 /* loop_i <= nb_iters */
2200 if (TREE_CODE (nb_iters) == INTEGER_CST)
2203 value_set_si (cstr->p[row][0], 1);
2204 value_set_si (cstr->p[row][loop_col], -1);
2206 value_set_si (cstr->p[row][cst_col],
2207 int_cst_value (nb_iters));
2209 else if (!chrec_contains_undetermined (nb_iters))
2211 /* Otherwise nb_iters contains parameters: scan the nb_iters
2212 expression and build its matrix representation. */
2216 value_set_si (cstr->p[row][0], 1);
2217 value_set_si (cstr->p[row][loop_col], -1);
2219 nb_iters = analyze_scalar_evolution (loop, nb_iters);
2220 nb_iters = instantiate_scev (block_before_scop (scop), loop, nb_iters);
2223 value_set_si (one, 1);
2224 scan_tree_for_params (scop, nb_iters, cstr, row, one, false);
2230 if (loop->inner && loop_in_scop_p (loop->inner, scop))
2231 build_loop_iteration_domains (scop, loop->inner, cstr, nb_outer_loops + 1);
2233 /* Only go to the next loops, if we are not at the outermost layer. These
2234 have to be handled seperately, as we can be sure, that the chain at this
2235 layer will be connected. */
2236 if (nb_outer_loops != 0 && loop->next && loop_in_scop_p (loop->next, scop))
2237 build_loop_iteration_domains (scop, loop->next, outer_cstr, nb_outer_loops);
2239 add_bb_domains (loop, cstr);
2241 cloog_matrix_free (cstr);
2244 /* Add conditions to the domain of GB. */
2247 add_conditions_to_domain (graphite_bb_p gb)
2251 VEC (gimple, heap) *conditions = GBB_CONDITIONS (gb);
2252 CloogMatrix *domain = GBB_DOMAIN (gb);
2253 scop_p scop = GBB_SCOP (gb);
2257 unsigned nb_new_rows = 0;
2260 if (VEC_empty (gimple, conditions))
2265 nb_rows = domain->NbRows;
2266 nb_cols = domain->NbColumns;
2271 nb_cols = scop_nb_params (scop) + 2;
2274 /* Count number of necessary new rows to add the conditions to the
2276 for (i = 0; VEC_iterate (gimple, conditions, i, stmt); i++)
2278 switch (gimple_code (stmt))
2282 enum tree_code code = gimple_cond_code (stmt);
2288 /* NE and EQ statements are not supported right know. */
2304 /* Switch statements are not supported right know. */
2315 /* Enlarge the matrix. */
2317 CloogMatrix *new_domain;
2318 new_domain = cloog_matrix_alloc (nb_rows + nb_new_rows, nb_cols);
2320 for (i = 0; i < nb_rows; i++)
2321 for (j = 0; j < nb_cols; j++)
2322 value_assign (new_domain->p[i][j], domain->p[i][j]);
2324 cloog_matrix_free (domain);
2325 domain = new_domain;
2326 GBB_DOMAIN (gb) = new_domain;
2329 /* Add the conditions to the new enlarged domain matrix. */
2331 for (i = 0; VEC_iterate (gimple, conditions, i, stmt); i++)
2333 switch (gimple_code (stmt))
2338 enum tree_code code;
2341 loop_p loop = GBB_BB (gb)->loop_father;
2343 left = gimple_cond_lhs (stmt);
2344 right = gimple_cond_rhs (stmt);
2346 left = analyze_scalar_evolution (loop, left);
2347 right = analyze_scalar_evolution (loop, right);
2349 left = instantiate_scev (block_before_scop (scop), loop, left);
2350 right = instantiate_scev (block_before_scop (scop), loop, right);
2352 code = gimple_cond_code (stmt);
2354 /* The conditions for ELSE-branches are inverted. */
2355 if (VEC_index (gimple, gb->condition_cases, i) == NULL)
2356 code = invert_tree_comparison (code, false);
2361 /* NE statements are not supported right know. */
2365 value_set_si (domain->p[row][0], 1);
2367 value_set_si (one, 1);
2368 scan_tree_for_params (scop, left, domain, row, one, true);
2369 value_set_si (one, 1);
2370 scan_tree_for_params (scop, right, domain, row, one, false);
2372 value_set_si (domain->p[row][0], 1);
2373 value_set_si (one, 1);
2374 scan_tree_for_params (scop, left, domain, row, one, false);
2375 value_set_si (one, 1);
2376 scan_tree_for_params (scop, right, domain, row, one, true);
2381 value_set_si (domain->p[row][0], 1);
2383 value_set_si (one, 1);
2384 scan_tree_for_params (scop, left, domain, row, one, true);
2385 value_set_si (one, 1);
2386 scan_tree_for_params (scop, right, domain, row, one, false);
2387 value_sub_int (domain->p[row][nb_cols - 1],
2388 domain->p[row][nb_cols - 1], 1);
2393 value_set_si (domain->p[row][0], 1);
2395 value_set_si (one, 1);
2396 scan_tree_for_params (scop, left, domain, row, one, false);
2397 value_set_si (one, 1);
2398 scan_tree_for_params (scop, right, domain, row, one, true);
2399 value_sub_int (domain->p[row][nb_cols - 1],
2400 domain->p[row][nb_cols - 1], 1);
2405 value_set_si (domain->p[row][0], 1);
2407 value_set_si (one, 1);
2408 scan_tree_for_params (scop, left, domain, row, one, true);
2409 value_set_si (one, 1);
2410 scan_tree_for_params (scop, right, domain, row, one, false);
2415 value_set_si (domain->p[row][0], 1);
2417 value_set_si (one, 1);
2418 scan_tree_for_params (scop, left, domain, row, one, false);
2419 value_set_si (one, 1);
2420 scan_tree_for_params (scop, right, domain, row, one, true);
2431 /* Switch statements are not supported right know. */
2442 /* Helper recursive function. */
2445 build_scop_conditions_1 (VEC (gimple, heap) **conditions,
2446 VEC (gimple, heap) **cases, basic_block bb,
2451 gimple_stmt_iterator gsi;
2452 basic_block bb_child, bb_iter;
2453 VEC (basic_block, heap) *dom;
2455 /* Make sure we are in the SCoP. */
2456 if (!bb_in_scop_p (bb, scop))
2459 /* Record conditions in graphite_bb. */
2460 gbb = gbb_from_bb (bb);
2461 GBB_CONDITIONS (gbb) = VEC_copy (gimple, heap, *conditions);
2462 GBB_CONDITION_CASES (gbb) = VEC_copy (gimple, heap, *cases);
2464 add_conditions_to_domain (gbb);
2466 dom = get_dominated_by (CDI_DOMINATORS, bb);
2468 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2470 gimple stmt = gsi_stmt (gsi);
2471 VEC (edge, gc) *edges;
2474 switch (gimple_code (stmt))
2478 for (i = 0; VEC_iterate (edge, edges, i, e); i++)
2479 if ((dominated_by_p (CDI_DOMINATORS, e->dest, bb))
2480 && VEC_length (edge, e->dest->preds) == 1)
2482 /* Remove the scanned block from the dominator successors. */
2483 for (j = 0; VEC_iterate (basic_block, dom, j, bb_iter); j++)
2484 if (bb_iter == e->dest)
2486 VEC_unordered_remove (basic_block, dom, j);
2490 /* Recursively scan the then or else part. */
2491 if (e->flags & EDGE_TRUE_VALUE)
2492 VEC_safe_push (gimple, heap, *cases, stmt);
2493 else if (e->flags & EDGE_FALSE_VALUE)
2494 VEC_safe_push (gimple, heap, *cases, NULL);
2498 VEC_safe_push (gimple, heap, *conditions, stmt);
2499 build_scop_conditions_1 (conditions, cases, e->dest, scop);
2500 VEC_pop (gimple, *conditions);
2501 VEC_pop (gimple, *cases);
2508 gimple_stmt_iterator gsi_search_gimple_label;
2510 for (i = 0; i < gimple_switch_num_labels (stmt); ++i)
2512 basic_block bb_iter;
2514 size_t n_cases = VEC_length (gimple, *conditions);
2515 unsigned n = gimple_switch_num_labels (stmt);
2517 bb_child = label_to_block
2518 (CASE_LABEL (gimple_switch_label (stmt, i)));
2520 /* Do not handle multiple values for the same block. */
2521 for (k = 0; k < n; k++)
2524 (CASE_LABEL (gimple_switch_label (stmt, k))) == bb_child)
2530 /* Switch cases with more than one predecessor are not
2532 if (VEC_length (edge, bb_child->preds) != 1)
2535 /* Recursively scan the corresponding 'case' block. */
2537 for (gsi_search_gimple_label = gsi_start_bb (bb_child);
2538 !gsi_end_p (gsi_search_gimple_label);
2539 gsi_next (&gsi_search_gimple_label))
2541 gimple stmt_gimple_label
2542 = gsi_stmt (gsi_search_gimple_label);
2544 if (gimple_code (stmt_gimple_label) == GIMPLE_LABEL)
2546 tree t = gimple_label_label (stmt_gimple_label);
2548 if (t == gimple_switch_label (stmt, i))
2549 VEC_replace (gimple, *cases, n_cases,
2556 build_scop_conditions_1 (conditions, cases, bb_child, scop);
2558 /* Remove the scanned block from the dominator successors. */
2559 for (j = 0; VEC_iterate (basic_block, dom, j, bb_iter); j++)
2560 if (bb_iter == bb_child)
2562 VEC_unordered_remove (basic_block, dom, j);
2567 VEC_pop (gimple, *conditions);
2568 VEC_pop (gimple, *cases);
2576 /* Scan all immediate dominated successors. */
2577 for (i = 0; VEC_iterate (basic_block, dom, i, bb_child); i++)
2578 build_scop_conditions_1 (conditions, cases, bb_child, scop);
2580 VEC_free (basic_block, heap, dom);
2583 /* Record all 'if' and 'switch' conditions in each gbb of SCOP. */
2586 build_scop_conditions (scop_p scop)
2588 VEC (gimple, heap) *conditions = NULL;
2589 VEC (gimple, heap) *cases = NULL;
2591 build_scop_conditions_1 (&conditions, &cases, SCOP_ENTRY (scop), scop);
2593 VEC_free (gimple, heap, conditions);
2594 VEC_free (gimple, heap, cases);
2597 /* Build the current domain matrix: the loops belonging to the current
2598 SCOP, and that vary for the execution of the current basic block.
2599 Returns false if there is no loop in SCOP. */
2602 build_scop_iteration_domain (scop_p scop)
2605 CloogMatrix *outer_cstr;
2608 /* Build cloog loop for all loops, that are in the uppermost loop layer of
2610 for (i = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), i, loop); i++)
2611 if (!loop_in_scop_p (loop_outer (loop), scop))
2613 /* The outermost constraints is a matrix that has:
2614 -first column: eq/ineq boolean
2615 -last column: a constant
2616 -scop_nb_params columns for the parameters used in the scop. */
2617 outer_cstr = cloog_matrix_alloc (0, scop_nb_params (scop) + 2);
2618 build_loop_iteration_domains (scop, loop, outer_cstr, 0);
2619 cloog_matrix_free (outer_cstr);
2625 /* Initializes an equation CY of the access matrix using the
2626 information for a subscript from ACCESS_FUN, relatively to the loop
2627 indexes from LOOP_NEST and parameter indexes from PARAMS. NDIM is
2628 the dimension of the array access, i.e. the number of
2629 subscripts. Returns true when the operation succeeds. */
2632 build_access_matrix_with_af (tree access_fun, lambda_vector cy,
2633 scop_p scop, int ndim)
2635 switch (TREE_CODE (access_fun))
2637 case POLYNOMIAL_CHREC:
2639 tree left = CHREC_LEFT (access_fun);
2640 tree right = CHREC_RIGHT (access_fun);
2643 if (TREE_CODE (right) != INTEGER_CST)
2646 var = loop_iteration_vector_dim (CHREC_VARIABLE (access_fun), scop);
2647 cy[var] = int_cst_value (right);
2649 switch (TREE_CODE (left))
2651 case POLYNOMIAL_CHREC:
2652 return build_access_matrix_with_af (left, cy, scop, ndim);
2655 cy[ndim - 1] = int_cst_value (left);
2659 /* FIXME: access_fn can have parameters. */
2664 cy[ndim - 1] = int_cst_value (access_fun);
2668 /* FIXME: access_fn can have parameters. */
2673 /* Initialize the access matrix in the data reference REF with respect
2674 to the loop nesting LOOP_NEST. Return true when the operation
2678 build_access_matrix (data_reference_p ref, graphite_bb_p gb)
2680 int i, ndim = DR_NUM_DIMENSIONS (ref);
2681 struct access_matrix *am = GGC_NEW (struct access_matrix);
2683 AM_MATRIX (am) = VEC_alloc (lambda_vector, heap, ndim);
2684 DR_SCOP (ref) = GBB_SCOP (gb);
2686 for (i = 0; i < ndim; i++)
2688 lambda_vector v = lambda_vector_new (ref_nb_loops (ref));
2689 scop_p scop = GBB_SCOP (gb);
2690 tree af = DR_ACCESS_FN (ref, i);
2692 if (!build_access_matrix_with_af (af, v, scop, ref_nb_loops (ref)))
2695 VEC_safe_push (lambda_vector, heap, AM_MATRIX (am), v);
2698 DR_ACCESS_MATRIX (ref) = am;
2702 /* Build the access matrices for the data references in the SCOP. */
2705 build_scop_data_accesses (scop_p scop)
2710 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
2713 gimple_stmt_iterator gsi;
2714 data_reference_p dr;
2715 struct loop *nest = outermost_loop_in_scop (scop, GBB_BB (gb));
2717 /* On each statement of the basic block, gather all the occurences
2718 to read/write memory. */
2719 GBB_DATA_REFS (gb) = VEC_alloc (data_reference_p, heap, 5);
2720 for (gsi = gsi_start_bb (GBB_BB (gb)); !gsi_end_p (gsi); gsi_next (&gsi))
2721 find_data_references_in_stmt (nest, gsi_stmt (gsi),
2722 &GBB_DATA_REFS (gb));
2724 /* FIXME: Construction of access matrix is disabled until some
2725 pass, like the data dependence analysis, is using it. */
2728 /* Construct the access matrix for each data ref, with respect to
2729 the loop nest of the current BB in the considered SCOP. */
2731 VEC_iterate (data_reference_p, GBB_DATA_REFS (gb), j, dr);
2734 bool res = build_access_matrix (dr, gb);
2736 /* FIXME: At this point the DRs should always have an affine
2737 form. For the moment this fails as build_access_matrix
2738 does not build matrices with parameters. */
2744 /* Converts a GMP constant value to a tree and returns it. */
2747 gmp_cst_to_tree (Value v)
2749 return build_int_cst (integer_type_node, value_get_si (v));
2752 /* Returns the tree variable from the name NAME that was given in
2753 Cloog representation. All the parameters are stored in PARAMS, and
2754 all the loop induction variables are stored in IVSTACK.
2756 FIXME: This is a hack, and Cloog should be fixed to not work with
2757 variable names represented as "char *string", but with void
2758 pointers that could be casted back to a tree. The only problem in
2759 doing that is that Cloog's pretty printer still assumes that
2760 variable names are char *strings. The solution would be to have a
2761 function pointer for pretty-printing that can be redirected to be
2762 print_generic_stmt in our case, or fprintf by default.
2763 ??? Too ugly to live. */
2766 clast_name_to_gcc (const char *name, VEC (name_tree, heap) *params,
2767 loop_iv_stack ivstack)
2773 for (i = 0; VEC_iterate (name_tree, params, i, t); i++)
2774 if (!strcmp (name, t->name))
2777 iv = loop_iv_stack_get_iv_from_name (ivstack, name);
2784 /* Converts a Cloog AST expression E back to a GCC expression tree. */
2787 clast_to_gcc_expression (struct clast_expr *e,
2788 VEC (name_tree, heap) *params,
2789 loop_iv_stack ivstack)
2791 tree type = integer_type_node;
2799 struct clast_term *t = (struct clast_term *) e;
2803 if (value_one_p (t->val))
2804 return clast_name_to_gcc (t->var, params, ivstack);
2806 else if (value_mone_p (t->val))
2807 return fold_build1 (NEGATE_EXPR, type,
2808 clast_name_to_gcc (t->var, params, ivstack));
2810 return fold_build2 (MULT_EXPR, type,
2811 gmp_cst_to_tree (t->val),
2812 clast_name_to_gcc (t->var, params, ivstack));
2815 return gmp_cst_to_tree (t->val);
2820 struct clast_reduction *r = (struct clast_reduction *) e;
2827 return clast_to_gcc_expression (r->elts[0], params, ivstack);
2831 gcc_assert (r->n >= 1
2832 && r->elts[0]->type == expr_term
2833 && r->elts[1]->type == expr_term);
2835 left = clast_to_gcc_expression (r->elts[0], params, ivstack);
2836 right = clast_to_gcc_expression (r->elts[1], params, ivstack);
2837 return fold_build2 (PLUS_EXPR, type, left, right);
2844 return clast_to_gcc_expression (r->elts[0], params, ivstack);
2848 left = clast_to_gcc_expression (r->elts[0], params, ivstack);
2849 right = clast_to_gcc_expression (r->elts[1], params, ivstack);
2850 return fold_build2 (MIN_EXPR, type, left, right);
2860 return clast_to_gcc_expression (r->elts[0], params, ivstack);
2864 left = clast_to_gcc_expression (r->elts[0], params, ivstack);
2865 right = clast_to_gcc_expression (r->elts[1], params, ivstack);
2866 return fold_build2 (MAX_EXPR, type, left, right);
2882 struct clast_binary *b = (struct clast_binary *) e;
2883 struct clast_expr *lhs = (struct clast_expr *) b->LHS;
2884 struct clast_expr *rhs = (struct clast_expr *) b->RHS;
2885 tree tl = clast_to_gcc_expression (lhs, params, ivstack);
2887 /* FIXME: The next statement produces a warning: Cloog assumes
2888 that the RHS is a constant, but this is a "void *" pointer
2889 that should be casted into a Value, but this cast cannot be
2890 done as Value is a GMP type, that is an array. Cloog must
2891 be fixed for removing this warning. */
2892 tree tr = gmp_cst_to_tree (rhs);
2896 case clast_bin_fdiv:
2897 return fold_build2 (FLOOR_DIV_EXPR, type, tl, tr);
2899 case clast_bin_cdiv:
2900 return fold_build2 (CEIL_DIV_EXPR, type, tl, tr);
2903 return fold_build2 (EXACT_DIV_EXPR, type, tl, tr);
2906 return fold_build2 (TRUNC_MOD_EXPR, type, tl, tr);
2920 /* Translates a clast equation CLEQ to a tree. */
2923 graphite_translate_clast_equation (scop_p scop,
2924 struct clast_equation *cleq,
2925 loop_iv_stack ivstack)
2927 enum tree_code comp;
2928 tree lhs = clast_to_gcc_expression (cleq->LHS, SCOP_PARAMS (scop), ivstack);
2929 tree rhs = clast_to_gcc_expression (cleq->RHS, SCOP_PARAMS (scop), ivstack);
2931 if (cleq->sign == 0)
2934 else if (cleq->sign > 0)
2940 return fold_build2 (comp, integer_type_node, lhs, rhs);
2943 /* Creates the test for the condition in STMT. */
2946 graphite_create_guard_cond_expr (scop_p scop, struct clast_guard *stmt,
2947 loop_iv_stack ivstack)
2952 for (i = 0; i < stmt->n; i++)
2954 tree eq = graphite_translate_clast_equation (scop, &stmt->eq[i], ivstack);
2957 cond = fold_build2 (TRUTH_AND_EXPR, integer_type_node, cond, eq);
2965 /* Creates a new if region corresponding to Cloog's guard. */
2968 graphite_create_new_guard (scop_p scop, edge entry_edge,
2969 struct clast_guard *stmt,
2970 loop_iv_stack ivstack)
2972 tree cond_expr = graphite_create_guard_cond_expr (scop, stmt, ivstack);
2973 edge exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
2978 /* Creates a new LOOP corresponding to Cloog's STMT. Inserts an induction
2979 variable for the new LOOP. New LOOP is attached to CFG starting at
2980 ENTRY_EDGE. LOOP is inserted into the loop tree and becomes the child
2981 loop of the OUTER_LOOP. */
2983 static struct loop *
2984 graphite_create_new_loop (scop_p scop, edge entry_edge,
2985 struct clast_for *stmt, loop_iv_stack ivstack,
2990 tree stride, lowb, upb;
2993 gcc_assert (stmt->LB
2996 stride = gmp_cst_to_tree (stmt->stride);
2997 lowb = clast_to_gcc_expression (stmt->LB, SCOP_PARAMS (scop), ivstack);
2998 ivvar = create_tmp_var (integer_type_node, "graphiteIV");
2999 add_referenced_var (ivvar);
3001 upb = clast_to_gcc_expression (stmt->UB, SCOP_PARAMS (scop), ivstack);
3002 loop = create_empty_loop_on_edge (entry_edge, lowb, stride, upb, ivvar,
3003 &iv_before, outer ? outer
3004 : entry_edge->src->loop_father);
3006 loop_iv_stack_push (ivstack, iv_before, stmt->iterator);
3011 /* Remove all the edges from EDGES except the edge KEEP. */
3014 remove_all_edges_1 (VEC (edge, gc) *edges, edge keep)
3019 for (ei = ei_start (edges); (e = ei_safe_edge (ei)); )
3024 e = ei_safe_edge (ei);
3031 /* Remove all the edges from BB except the edge KEEP. */
3034 remove_all_edges (basic_block bb, edge keep)
3036 remove_all_edges_1 (bb->succs, keep);
3037 remove_all_edges_1 (bb->preds, keep);
3040 /* Rename the SSA_NAMEs used in STMT and that appear in IVSTACK. */
3043 graphite_rename_ivs_stmt (gimple stmt, graphite_bb_p gbb, scop_p scop,
3044 loop_p old, loop_iv_stack ivstack)
3047 use_operand_p use_p;
3049 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
3051 tree use = USE_FROM_PTR (use_p);
3053 name_tree old_iv = get_old_iv_from_ssa_name (scop, old, use);
3056 new_iv = loop_iv_stack_get_iv (ivstack,
3057 gbb_loop_index (gbb, old_iv->loop));
3060 SET_USE (use_p, new_iv);
3064 /* Returns true if SSA_NAME is a parameter of SCOP. */
3067 is_parameter (scop_p scop, tree ssa_name)
3070 VEC (name_tree, heap) *params = SCOP_PARAMS (scop);
3073 for (i = 0; VEC_iterate (name_tree, params, i, param); i++)
3074 if (param->t == ssa_name)
3080 /* Returns true if NAME is an old induction variable in SCOP. OLD is
3081 the original loop that contained the definition of NAME. */
3084 is_old_iv (scop_p scop, loop_p old, tree name)
3086 return get_old_iv_from_ssa_name (scop, old, name) != NULL;
3090 static void expand_scalar_variables_stmt (gimple, graphite_bb_p, scop_p, loop_p,
3093 /* Constructs a tree which only contains old_ivs and parameters. Any
3094 other variables that are defined outside GBB will be eliminated by
3095 using their definitions in the constructed tree. OLD_LOOP_FATHER
3096 is the original loop that contained GBB. */
3099 expand_scalar_variables_expr (tree type, tree op0, enum tree_code code,
3100 tree op1, graphite_bb_p gbb, scop_p scop,
3101 loop_p old_loop_father, loop_iv_stack ivstack)
3103 if (TREE_CODE_CLASS (code) == tcc_constant
3104 && code == INTEGER_CST)
3107 if (TREE_CODE_CLASS (code) == tcc_unary)
3109 tree op0_type = TREE_TYPE (op0);
3110 enum tree_code op0_code = TREE_CODE (op0);
3112 expand_scalar_variables_expr (op0_type, op0, op0_code,
3113 NULL, gbb, scop, old_loop_father,
3116 return fold_build1 (code, type, op0_expr);
3119 if (TREE_CODE_CLASS (code) == tcc_binary)
3121 tree op0_type = TREE_TYPE (op0);
3122 enum tree_code op0_code = TREE_CODE (op0);
3124 expand_scalar_variables_expr (op0_type, op0, op0_code,
3125 NULL, gbb, scop, old_loop_father,
3127 tree op1_type = TREE_TYPE (op1);
3128 enum tree_code op1_code = TREE_CODE (op1);
3130 expand_scalar_variables_expr (op1_type, op1, op1_code,
3131 NULL, gbb, scop, old_loop_father,
3134 return fold_build2 (code, type, op0_expr, op1_expr);
3137 if (code == SSA_NAME)
3141 enum tree_code subcode;
3143 if(is_parameter (scop, op0) ||
3144 is_old_iv (scop, old_loop_father, op0))
3147 def_stmt = SSA_NAME_DEF_STMT (op0);
3149 if (gimple_bb (def_stmt) == GBB_BB (gbb))
3151 /* If the defining statement is in the basic block already
3152 we do not need to create a new expression for it, we
3153 only need to ensure its operands are expanded. */
3154 expand_scalar_variables_stmt (def_stmt, gbb, scop,
3155 old_loop_father, ivstack);
3161 if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
3164 var0 = gimple_assign_rhs1 (def_stmt);
3165 subcode = gimple_assign_rhs_code (def_stmt);
3166 var1 = gimple_assign_rhs2 (def_stmt);
3168 return expand_scalar_variables_expr (type, var0, subcode, var1,
3169 gbb, scop, old_loop_father,
3178 /* Replicates any uses of non-parameters and non-old-ivs variablesthat
3179 are defind outside GBB with code that is inserted in GBB.
3180 OLD_LOOP_FATHER is the original loop that contained STMT. */
3183 expand_scalar_variables_stmt (gimple stmt, graphite_bb_p gbb, scop_p scop,
3184 loop_p old_loop_father, loop_iv_stack ivstack)
3187 use_operand_p use_p;
3188 basic_block bb = GBB_BB (gbb);
3190 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
3192 tree use = USE_FROM_PTR (use_p);
3193 tree type = TREE_TYPE (use);
3194 enum tree_code code = TREE_CODE (use);
3195 tree use_expr = expand_scalar_variables_expr (type, use, code, NULL,
3196 gbb, scop, old_loop_father,
3198 if (use_expr != use)
3200 gimple_stmt_iterator gsi = gsi_after_labels (bb);
3202 force_gimple_operand_gsi (&gsi, use_expr, true, NULL,
3203 true, GSI_NEW_STMT);
3204 SET_USE (use_p, new_use);
3209 /* Copies the definitions outside of GBB of variables that are not
3210 induction variables nor parameters. GBB must only contain
3211 "external" references to these types of variables. OLD_LOOP_FATHER
3212 is the original loop that contained GBB. */
3215 expand_scalar_variables (graphite_bb_p gbb, scop_p scop,
3216 loop_p old_loop_father, loop_iv_stack ivstack)
3218 basic_block bb = GBB_BB (gbb);
3219 gimple_stmt_iterator gsi;
3221 for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi);)
3223 gimple stmt = gsi_stmt (gsi);
3224 expand_scalar_variables_stmt (stmt, gbb, scop, old_loop_father,
3230 /* Rename all the SSA_NAMEs from block GBB that appear in IVSTACK in
3231 terms of new induction variables. OLD_LOOP_FATHER is the original
3232 loop that contained GBB. */
3235 graphite_rename_ivs (graphite_bb_p gbb, scop_p scop, loop_p old_loop_father,
3236 loop_iv_stack ivstack)
3238 basic_block bb = GBB_BB (gbb);
3239 gimple_stmt_iterator gsi;
3241 for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi);)
3243 gimple stmt = gsi_stmt (gsi);
3245 if (gimple_get_lhs (stmt)
3246 && TREE_CODE (gimple_get_lhs (stmt)) == SSA_NAME
3247 && get_old_iv_from_ssa_name (scop, old_loop_father,
3248 gimple_get_lhs (stmt)))
3249 gsi_remove (&gsi, false);
3252 graphite_rename_ivs_stmt (stmt, gbb, scop, old_loop_father, ivstack);
3258 /* Move all the PHI nodes from block FROM to block TO.
3259 OLD_LOOP_FATHER is the original loop that contained FROM. */
3262 move_phi_nodes (scop_p scop, loop_p old_loop_father, basic_block from,
3265 gimple_stmt_iterator gsi;
3267 for (gsi = gsi_start_phis (from); !gsi_end_p (gsi);)
3269 gimple phi = gsi_stmt (gsi);
3270 tree op = gimple_phi_result (phi);
3272 if (get_old_iv_from_ssa_name (scop, old_loop_father, op) == NULL)
3274 gimple new_phi = make_phi_node (op, 0);
3275 add_phi_node_to_bb (new_phi, to);
3277 remove_phi_node (&gsi, false);
3281 /* Remove condition from BB. */
3284 remove_condition (basic_block bb)
3286 gimple last = last_stmt (bb);
3288 if (last && gimple_code (last) == GIMPLE_COND)
3290 gimple_stmt_iterator gsi = gsi_last_bb (bb);
3291 gsi_remove (&gsi, true);
3295 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag set. */
3298 get_true_edge_from_guard_bb (basic_block bb)
3303 FOR_EACH_EDGE (e, ei, bb->succs)
3304 if (e->flags & EDGE_TRUE_VALUE)
3311 /* Translates a CLAST statement STMT to GCC representation. NEXT_E is
3312 the edge where new generated code should be attached. BB_EXIT is the last
3313 basic block that defines the scope of code generation. CONTEXT_LOOP is the
3314 loop in which the generated code will be placed (might be NULL). */
3317 translate_clast (scop_p scop, struct loop *context_loop,
3318 struct clast_stmt *stmt, edge next_e, loop_iv_stack ivstack)
3323 if (CLAST_STMT_IS_A (stmt, stmt_root))
3324 return translate_clast (scop, context_loop, stmt->next, next_e, ivstack);
3326 if (CLAST_STMT_IS_A (stmt, stmt_user))
3328 CloogStatement *cs = ((struct clast_user_stmt *) stmt)->statement;
3329 graphite_bb_p gbb = (graphite_bb_p) cloog_statement_usr (cs);
3330 basic_block bb = gbb->bb;
3331 loop_p old_loop_father = bb->loop_father;
3333 if (bb == ENTRY_BLOCK_PTR)
3336 remove_condition (bb);
3337 expand_scalar_variables (gbb, scop, old_loop_father, ivstack);
3338 remove_all_edges (bb, next_e);
3339 move_phi_nodes (scop, old_loop_father, bb, next_e->src);
3340 redirect_edge_succ_nodup (next_e, bb);
3344 remove_bb_from_loops (bb);
3345 add_bb_to_loop (bb, context_loop);
3348 set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src);
3349 mark_virtual_ops_in_bb (bb);
3350 next_e = make_edge (bb,
3351 context_loop ? context_loop->latch : EXIT_BLOCK_PTR,
3353 graphite_rename_ivs (gbb, scop, old_loop_father, ivstack);
3354 return translate_clast (scop, context_loop, stmt->next, next_e, ivstack);
3357 if (CLAST_STMT_IS_A (stmt, stmt_for))
3360 = graphite_create_new_loop (scop, next_e, (struct clast_for *) stmt,
3361 ivstack, context_loop ? context_loop
3363 edge last_e = single_exit (loop);
3365 next_e = translate_clast (scop, loop, ((struct clast_for *) stmt)->body,
3366 single_pred_edge (loop->latch), ivstack);
3367 redirect_edge_succ_nodup (next_e, loop->latch);
3369 set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src);
3370 loop_iv_stack_pop (ivstack);
3372 return translate_clast (scop, context_loop, stmt->next, last_e, ivstack);
3375 if (CLAST_STMT_IS_A (stmt, stmt_guard))
3377 edge last_e = graphite_create_new_guard (scop, next_e,
3378 ((struct clast_guard *) stmt),
3380 edge true_e = get_true_edge_from_guard_bb (next_e->dest);
3381 next_e = translate_clast (scop, context_loop,
3382 ((struct clast_guard *) stmt)->then,
3384 redirect_edge_succ_nodup (next_e, last_e->src);
3385 return translate_clast (scop, context_loop, stmt->next, last_e, ivstack);
3388 if (CLAST_STMT_IS_A (stmt, stmt_block))
3390 next_e = translate_clast (scop, context_loop,
3391 ((struct clast_block *) stmt)->body,
3393 return translate_clast (scop, context_loop, stmt->next, next_e, ivstack);
3399 /* Build cloog program for SCoP. */
3402 build_cloog_prog (scop_p scop)
3405 int max_nb_loops = scop_max_loop_depth (scop);
3407 CloogLoop *loop_list = NULL;
3408 CloogBlockList *block_list = NULL;
3409 CloogDomainList *scattering = NULL;
3410 CloogProgram *prog = SCOP_PROG (scop);
3411 int nbs = 2 * max_nb_loops + 1;
3412 int *scaldims = (int *) xmalloc (nbs * (sizeof (int)));
3414 cloog_program_set_nb_scattdims (prog, nbs);
3415 initialize_cloog_names (scop);
3417 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gbb); i++)
3419 /* Build new block. */
3420 CloogMatrix *domain = GBB_DOMAIN (gbb);
3421 CloogStatement *stmt = cloog_statement_alloc (GBB_BB (gbb)->index);
3422 CloogBlock *block = cloog_block_alloc (stmt, 0, NULL,
3423 nb_loops_around_gb (gbb));
3424 cloog_statement_set_usr (stmt, gbb);
3426 /* Add empty domain to all bbs, which do not yet have a domain, as they
3427 are not part of any loop. */
3430 domain = cloog_matrix_alloc (0, scop_nb_params (scop) + 2);
3431 GBB_DOMAIN (gbb) = domain;
3434 /* Build loop list. */
3436 CloogLoop *new_loop_list = cloog_loop_malloc ();
3437 cloog_loop_set_next (new_loop_list, loop_list);
3438 cloog_loop_set_domain (new_loop_list,
3439 cloog_domain_matrix2domain (domain));
3440 cloog_loop_set_block (new_loop_list, block);
3441 loop_list = new_loop_list;
3444 /* Build block list. */
3446 CloogBlockList *new_block_list = cloog_block_list_malloc ();
3448 cloog_block_list_set_next (new_block_list, block_list);
3449 cloog_block_list_set_block (new_block_list, block);
3450 block_list = new_block_list;
3453 /* Build scattering list. */
3455 /* XXX: Replace with cloog_domain_list_alloc(), when available. */
3456 CloogDomainList *new_scattering
3457 = (CloogDomainList *) xmalloc (sizeof (CloogDomainList));
3458 CloogMatrix *scat_mat = schedule_to_scattering (gbb, nbs);
3460 cloog_set_next_domain (new_scattering, scattering);
3461 cloog_set_domain (new_scattering,
3462 cloog_domain_matrix2domain (scat_mat));
3463 scattering = new_scattering;
3464 cloog_matrix_free (scat_mat);
3468 cloog_program_set_loop (prog, loop_list);
3469 cloog_program_set_blocklist (prog, block_list);
3471 for (i = 0; i < nbs; i++)
3474 cloog_program_set_scaldims (prog, scaldims);
3476 /* Extract scalar dimensions to simplify the code generation problem. */
3477 cloog_program_extract_scalars (prog, scattering);
3479 /* Apply scattering. */
3480 cloog_program_scatter (prog, scattering);
3482 /* Iterators corresponding to scalar dimensions have to be extracted. */
3483 cloog_names_scalarize (cloog_program_names (prog), nbs,
3484 cloog_program_scaldims (prog));
3486 /* Free blocklist. */
3488 CloogBlockList *next = cloog_program_blocklist (prog);
3492 CloogBlockList *toDelete = next;
3493 next = cloog_block_list_next (next);
3494 cloog_block_list_set_next (toDelete, NULL);
3495 cloog_block_list_set_block (toDelete, NULL);
3496 cloog_block_list_free (toDelete);
3498 cloog_program_set_blocklist (prog, NULL);
3502 /* Return the options that will be used in GLOOG. */
3504 static CloogOptions *
3505 set_cloog_options (void)
3507 CloogOptions *options = cloog_options_malloc ();
3509 /* Change cloog output language to C. If we do use FORTRAN instead, cloog
3510 will stop e.g. with "ERROR: unbounded loops not allowed in FORTRAN.", if
3511 we pass an incomplete program to cloog. */
3512 options->language = LANGUAGE_C;
3514 /* Enable complex equality spreading: removes dummy statements
3515 (assignments) in the generated code which repeats the
3516 substitution equations for statements. This is useless for
3520 /* Enable C pretty-printing mode: normalizes the substitution
3521 equations for statements. */
3524 /* Allow cloog to build strides with a stride width different to one.
3525 This example has stride = 4:
3527 for (i = 0; i < 20; i += 4)
3529 options->strides = 1;
3531 /* Disable optimizations and make cloog generate source code closer to the
3532 input. This is useful for debugging, but later we want the optimized
3535 XXX: We can not disable optimizations, as loop blocking is not working
3540 options->l = INT_MAX;
3546 /* Prints STMT to STDERR. */
3549 debug_clast_stmt (struct clast_stmt *stmt)
3551 CloogOptions *options = set_cloog_options ();
3553 pprint (stderr, stmt, 0, options);
3556 /* Find the right transform for the SCOP, and return a Cloog AST
3557 representing the new form of the program. */
3559 static struct clast_stmt *
3560 find_transform (scop_p scop)
3563 struct clast_stmt *stmt;
3564 CloogOptions *options = set_cloog_options ();
3566 /* Connect new cloog prog generation to graphite. */
3567 build_cloog_prog (scop);
3569 if (dump_file && (dump_flags & TDF_DETAILS))
3571 fprintf (dump_file, "Cloog Input [\n");
3572 cloog_program_print (dump_file, SCOP_PROG(scop));
3573 fprintf (dump_file, "]\n");
3576 prog = cloog_program_generate (SCOP_PROG (scop), options);
3577 stmt = cloog_clast_create (prog, options);
3579 if (dump_file && (dump_flags & TDF_DETAILS))
3581 fprintf (dump_file, "Cloog Output[\n");
3582 pprint (dump_file, stmt, 0, options);
3583 cloog_program_dump_cloog (dump_file, prog);
3584 fprintf (dump_file, "]\n");
3587 cloog_options_free (options);
3591 /* Return a vector of all the virtual phi nodes in the current
3594 static VEC (gimple, heap) *
3595 collect_virtual_phis (void)
3597 gimple_stmt_iterator si;
3598 gimple_vec phis = VEC_alloc (gimple, heap, 3);
3602 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
3603 /* The phis we moved will have 0 arguments because the
3604 original edges were removed. */
3605 if (gimple_phi_num_args (gsi_stmt (si)) == 0)
3606 VEC_safe_push (gimple, heap, phis, gsi_stmt (si));
3608 /* Deallocate if we did not find any. */
3609 if (VEC_length (gimple, phis) == 0)
3611 VEC_free (gimple, heap, phis);
3618 /* Find a virtual definition for variable VAR in BB. */
3621 find_vdef_for_var_in_bb (basic_block bb, tree var)
3623 gimple_stmt_iterator gsi;
3625 def_operand_p def_var;
3627 ssa_op_iter op_iter;
3629 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
3630 FOR_EACH_SSA_VDEF_OPERAND (def_var, vv, gsi_stmt (gsi), op_iter)
3631 if (SSA_NAME_VAR (*def_var) == var)
3634 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
3635 FOR_EACH_SSA_DEF_OPERAND (def_var, gsi_stmt (gsi), op_iter, SSA_OP_DEF)
3636 if (SSA_NAME_VAR (*def_var) == var)
3639 for (gsi = gsi_start_phis (bb); !gsi_end_p(gsi); gsi_next (&gsi))
3641 phi = gsi_stmt (gsi);
3642 if (SSA_NAME_VAR (PHI_RESULT (phi)) == var)
3643 return PHI_RESULT (phi);
3649 /* Recursive helper. */
3652 find_vdef_for_var_1 (basic_block bb, struct pointer_set_t *visited, tree var)
3658 if (pointer_set_contains (visited, bb))
3661 pointer_set_insert (visited, bb);
3662 result = find_vdef_for_var_in_bb (bb, var);
3665 FOR_EACH_EDGE (pred_edge, ei, bb->preds)
3667 result = find_vdef_for_var_1 (pred_edge->src, visited, var);
3672 /* Finds a virtual definition for variable VAR. */
3675 find_vdef_for_var (basic_block bb, tree var)
3677 struct pointer_set_t *visited = pointer_set_create ();
3678 tree def = find_vdef_for_var_1 (bb, visited, var);
3680 pointer_set_destroy (visited);
3684 /* Update the virtual phis after loop bodies are moved to new
3688 patch_phis_for_virtual_defs (void)
3692 VEC (gimple, heap) *virtual_phis = collect_virtual_phis ();
3694 for (i = 0; VEC_iterate (gimple, virtual_phis, i, phi); i++)
3696 basic_block bb = gimple_bb (phi);
3699 gimple_stmt_iterator gsi;
3701 tree phi_result = PHI_RESULT (phi);
3702 tree var = SSA_NAME_VAR (phi_result);
3704 new_phi = create_phi_node (phi_result, bb);
3705 SSA_NAME_DEF_STMT (phi_result) = new_phi;
3707 FOR_EACH_EDGE (pred_edge, ei, bb->preds)
3709 tree def = find_vdef_for_var (pred_edge->src, var);
3712 add_phi_arg (new_phi, def, pred_edge);
3714 add_phi_arg (new_phi, gimple_default_def (cfun, var), pred_edge);
3717 gsi = gsi_for_stmt (phi);
3718 remove_phi_node (&gsi, false);
3722 /* Mark the original loops of SCOP for removal, replacing their header
3726 mark_old_loops (scop_p scop)
3731 for (i = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), i, loop); i++)
3733 loop->header = NULL;
3738 /* Scan the loops and remove the ones that have been marked for
3742 remove_dead_loops (void)
3744 struct loop *loop, *ploop;
3747 FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
3749 /* Remove only those loops that we marked to be removed with
3756 ploop = loop->inner;
3757 flow_loop_tree_node_remove (ploop);
3758 flow_loop_tree_node_add (loop_outer (loop), ploop);
3761 /* Remove the loop and free its data. */
3766 /* Returns true when it is possible to generate code for this STMT.
3767 For the moment we cannot generate code when Cloog decides to
3768 duplicate a statement, as we do not do a copy, but a move.
3769 USED_BASIC_BLOCKS records the blocks that have already been seen.
3770 We return false if we have to generate code twice for the same
3774 can_generate_code_stmt (struct clast_stmt *stmt,
3775 struct pointer_set_t *used_basic_blocks)
3780 if (CLAST_STMT_IS_A (stmt, stmt_root))
3781 return can_generate_code_stmt (stmt->next, used_basic_blocks);
3783 if (CLAST_STMT_IS_A (stmt, stmt_user))
3785 CloogStatement *cs = ((struct clast_user_stmt *) stmt)->statement;
3786 graphite_bb_p gbb = (graphite_bb_p) cloog_statement_usr (cs);
3788 if (pointer_set_contains (used_basic_blocks, gbb))
3790 pointer_set_insert (used_basic_blocks, gbb);
3791 return can_generate_code_stmt (stmt->next, used_basic_blocks);
3794 if (CLAST_STMT_IS_A (stmt, stmt_for))
3795 return can_generate_code_stmt (((struct clast_for *) stmt)->body,
3797 && can_generate_code_stmt (stmt->next, used_basic_blocks);
3799 if (CLAST_STMT_IS_A (stmt, stmt_guard))
3800 return can_generate_code_stmt (((struct clast_guard *) stmt)->then,
3803 if (CLAST_STMT_IS_A (stmt, stmt_block))
3804 return can_generate_code_stmt (((struct clast_block *) stmt)->body,
3806 && can_generate_code_stmt (stmt->next, used_basic_blocks);
3811 /* Returns true when it is possible to generate code for this STMT. */
3814 can_generate_code (struct clast_stmt *stmt)
3817 struct pointer_set_t *used_basic_blocks = pointer_set_create ();
3819 result = can_generate_code_stmt (stmt, used_basic_blocks);
3820 pointer_set_destroy (used_basic_blocks);
3824 /* Skip any definition that is a phi node with a single phi def. */
3827 skip_phi_defs (tree ssa_name)
3829 tree result = ssa_name;
3830 gimple def_stmt = SSA_NAME_DEF_STMT (ssa_name);
3832 if (gimple_code (def_stmt) == GIMPLE_PHI
3833 && gimple_phi_num_args (def_stmt) == 1)
3834 result = skip_phi_defs (gimple_phi_arg(def_stmt,0)->def);
3839 /* Returns a VEC containing the phi-arg defs coming from SCOP_EXIT in
3840 the destination block of SCOP_EXIT. */
3842 static VEC (tree, heap) *
3843 collect_scop_exit_phi_args (edge scop_exit)
3845 VEC (tree, heap) *phi_args = VEC_alloc (tree, heap, 1);
3846 gimple_stmt_iterator gsi;
3848 for (gsi = gsi_start_phis (scop_exit->dest); !gsi_end_p (gsi); gsi_next (&gsi))
3850 gimple phi = gsi_stmt (gsi);
3851 tree phi_arg = skip_phi_defs(PHI_ARG_DEF_FROM_EDGE (phi, scop_exit));
3853 VEC_safe_push (tree, heap, phi_args, phi_arg);
3859 /* Patches (adds) PHI_ARGS to the phi nodes in SCOP_EXIT destination. */
3862 patch_scop_exit_phi_args (edge scop_exit,
3863 VEC (tree, heap) *phi_args)
3866 gimple_stmt_iterator gsi;
3868 for (gsi = gsi_start_phis (scop_exit->dest); !gsi_end_p (gsi);
3869 gsi_next (&gsi), i++)
3871 tree def = VEC_index (tree, phi_args, i);
3872 gimple phi = gsi_stmt (gsi);
3874 gcc_assert (PHI_ARG_DEF_FROM_EDGE (phi, scop_exit) == NULL);
3876 add_phi_arg (phi, def, scop_exit);
3880 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
3884 gloog (scop_p scop, struct clast_stmt *stmt)
3886 edge new_scop_exit_edge = NULL;
3887 basic_block scop_exit = SCOP_EXIT (scop);
3888 VEC (tree, heap)* phi_args =
3889 collect_scop_exit_phi_args (SESE_EXIT (SCOP_REGION (scop)));
3890 VEC (name_tree, heap) *ivstack = VEC_alloc (name_tree, heap, 10);
3891 edge construction_edge = SESE_ENTRY (SCOP_REGION (scop));
3892 basic_block old_scop_exit_idom = get_immediate_dominator (CDI_DOMINATORS,
3895 if (!can_generate_code (stmt))
3897 cloog_clast_free (stmt);
3901 new_scop_exit_edge = translate_clast (scop,
3902 construction_edge->src->loop_father,
3903 stmt, construction_edge, &ivstack);
3904 redirect_edge_succ (new_scop_exit_edge, scop_exit);
3905 if (!old_scop_exit_idom
3906 || !dominated_by_p (CDI_DOMINATORS, SCOP_ENTRY (scop),
3908 || SCOP_ENTRY (scop) == old_scop_exit_idom)
3909 set_immediate_dominator (CDI_DOMINATORS,
3910 new_scop_exit_edge->dest,
3911 new_scop_exit_edge->src);
3913 cloog_clast_free (stmt);
3915 if (new_scop_exit_edge->dest == EXIT_BLOCK_PTR)
3916 new_scop_exit_edge->flags = 0;
3918 find_unreachable_blocks ();
3919 delete_unreachable_blocks ();
3920 patch_phis_for_virtual_defs ();
3921 patch_scop_exit_phi_args (new_scop_exit_edge, phi_args);
3922 mark_old_loops (scop);
3923 remove_dead_loops ();
3924 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
3926 #ifdef ENABLE_CHECKING
3927 verify_loop_structure ();
3928 verify_dominators (CDI_DOMINATORS);
3933 /* Returns the number of data references in SCOP. */
3936 nb_data_refs_in_scop (scop_p scop)
3942 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gbb); i++)
3943 res += VEC_length (data_reference_p, GBB_DATA_REFS (gbb));
3948 /* Check if a graphite bb can be ignored in graphite. We ignore all
3949 bbs, that only contain code, that will be eliminated later.
3951 TODO: - Move PHI nodes and scalar variables out of these bbs, that only
3952 remain conditions and induction variables. */
3955 gbb_can_be_ignored (graphite_bb_p gb)
3957 gimple_stmt_iterator gsi;
3958 scop_p scop = GBB_SCOP (gb);
3959 loop_p loop = GBB_BB (gb)->loop_father;
3961 if (VEC_length (data_reference_p, GBB_DATA_REFS(gb)))
3964 /* Check statements. */
3965 for (gsi = gsi_start_bb (GBB_BB (gb)); !gsi_end_p (gsi); gsi_next (&gsi))
3967 gimple stmt = gsi_stmt (gsi);
3968 switch (gimple_code (stmt))
3970 /* Control flow expressions can be ignored, as they are
3971 represented in the iteration domains and will be
3972 regenerated by graphite. */
3978 /* Scalar variables can be ignored, if we can regenerate
3979 them later using their scalar evolution function.
3980 XXX: Just a heuristic, that needs further investigation. */
3983 tree var = gimple_assign_lhs (stmt);
3984 var = analyze_scalar_evolution (loop, var);
3985 var = instantiate_scev (block_before_scop (scop), loop, var);
3987 if (TREE_CODE (var) == SCEV_NOT_KNOWN)
3992 /* Otherwise not ignoreable. */
4001 /* Remove all ignoreable gbbs from SCOP. */
4004 scop_remove_ignoreable_gbbs (scop_p scop)
4009 int max_schedule = scop_max_loop_depth (scop) + 1;
4010 lambda_vector last_schedule = lambda_vector_new (max_schedule);
4011 lambda_vector_clear (last_schedule, max_schedule);
4013 /* Update schedules. */
4014 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
4016 int nb_loops = gbb_nb_loops (gb);
4018 if (GBB_STATIC_SCHEDULE (gb) [nb_loops] == 0)
4019 last_schedule [nb_loops] = 0;
4021 if (gbb_can_be_ignored (gb))
4023 /* Mark gbb for remove. */
4024 bitmap_clear_bit (SCOP_BBS_B (scop), gb->bb->index);
4025 GBB_SCOP (gb) = NULL;
4026 last_schedule [nb_loops]--;
4029 lambda_vector_add (GBB_STATIC_SCHEDULE (gb), last_schedule,
4030 GBB_STATIC_SCHEDULE (gb), nb_loops + 1);
4034 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
4035 if (GBB_SCOP (gb) == NULL)
4037 VEC_unordered_remove (graphite_bb_p, SCOP_BBS (scop), i);
4038 free_graphite_bb (gb);
4039 /* XXX: Hackish? But working. */
4043 graphite_sort_gbbs (scop);
4046 /* Move the loop at index LOOP and insert it before index NEW_LOOP_POS.
4047 This transformartion is only valid, if the loop nest between i and k is
4048 perfectly nested. Therefore we do not need to change the static schedule.
4052 for (i = 0; i < 50; i++)
4054 for (k = 5; k < 100; k++)
4057 To move k before i use:
4059 graphite_trans_bb_move_loop (A, 2, 0)
4061 for (k = 5; k < 100; k++)
4062 for (i = 0; i < 50; i++)
4068 graphite_trans_bb_move_loop (A, 0, 2)
4070 This function does not check the validity of interchanging loops.
4071 This should be checked before calling this function. */
4074 graphite_trans_bb_move_loop (graphite_bb_p gb, int loop,
4077 CloogMatrix *domain = GBB_DOMAIN (gb);
4081 gcc_assert (loop < gbb_nb_loops (gb)
4082 && new_loop_pos < gbb_nb_loops (gb));
4084 /* Update LOOPS vector. */
4085 tmp_loop_p = VEC_index (loop_p, GBB_LOOPS (gb), loop);
4086 VEC_ordered_remove (loop_p, GBB_LOOPS (gb), loop);
4087 VEC_safe_insert (loop_p, heap, GBB_LOOPS (gb), new_loop_pos, tmp_loop_p);
4089 /* Move the domain columns. */
4090 if (loop < new_loop_pos)
4091 for (row = 0; row < domain->NbRows; row++)
4095 value_assign (tmp, domain->p[row][loop + 1]);
4097 for (j = loop ; j < new_loop_pos - 1; j++)
4098 value_assign (domain->p[row][j + 1], domain->p[row][j + 2]);
4100 value_assign (domain->p[row][new_loop_pos], tmp);
4104 for (row = 0; row < domain->NbRows; row++)
4108 value_assign (tmp, domain->p[row][loop + 1]);
4110 for (j = loop ; j > new_loop_pos; j--)
4111 value_assign (domain->p[row][j + 1], domain->p[row][j]);
4113 value_assign (domain->p[row][new_loop_pos + 1], tmp);
4118 /* Get the index of the column representing constants in the DOMAIN
4122 const_column_index (CloogMatrix *domain)
4124 return domain->NbColumns - 1;
4128 /* Get the first index that is positive or negative, determined
4129 following the value of POSITIVE, in matrix DOMAIN in COLUMN. */
4132 get_first_matching_sign_row_index (CloogMatrix *domain, int column,
4137 for (row = 0; row < domain->NbRows; row++)
4139 int val = value_get_si (domain->p[row][column]);
4141 if (val > 0 && positive)
4144 else if (val < 0 && !positive)
4151 /* Get the lower bound of COLUMN in matrix DOMAIN. */
4154 get_lower_bound_row (CloogMatrix *domain, int column)
4156 return get_first_matching_sign_row_index (domain, column, true);
4159 /* Get the upper bound of COLUMN in matrix DOMAIN. */
4162 get_upper_bound_row (CloogMatrix *domain, int column)
4164 return get_first_matching_sign_row_index (domain, column, false);
4167 /* Get the lower bound of LOOP. */
4170 get_lower_bound (CloogMatrix *domain, int loop, Value lower_bound_result)
4172 int lower_bound_row = get_lower_bound_row (domain, loop);
4173 value_init (lower_bound_result);
4174 value_assign (lower_bound_result,
4175 domain->p[lower_bound_row][const_column_index(domain)]);
4178 /* Get the upper bound of LOOP. */
4181 get_upper_bound (CloogMatrix *domain, int loop, Value upper_bound_result)
4183 int upper_bound_row = get_upper_bound_row (domain, loop);
4184 value_init (upper_bound_result);
4185 value_assign (upper_bound_result,
4186 domain->p[upper_bound_row][const_column_index(domain)]);
4189 /* Strip mines the loop of BB at the position LOOP_DEPTH with STRIDE.
4190 Always valid, but not always a performance improvement. */
4193 graphite_trans_bb_strip_mine (graphite_bb_p gb, int loop_depth, int stride)
4197 CloogMatrix *domain = GBB_DOMAIN (gb);
4198 CloogMatrix *new_domain = cloog_matrix_alloc (domain->NbRows + 3,
4199 domain->NbColumns + 1);
4201 int col_loop_old = loop_depth + 2;
4202 int col_loop_strip = col_loop_old - 1;
4204 Value old_lower_bound;
4205 Value old_upper_bound;
4208 gcc_assert (loop_depth <= gbb_nb_loops (gb) - 1);
4210 VEC_safe_insert (loop_p, heap, GBB_LOOPS (gb), loop_depth, NULL);
4212 GBB_DOMAIN (gb) = new_domain;
4215 nrows = 4, ncols = 4
4224 for (row = 0; row < domain->NbRows; row++)
4225 for (col = 0; col < domain->NbColumns; col++)
4226 if (col <= loop_depth)
4228 value_assign (new_domain->p[row][col], domain->p[row][col]);
4232 value_assign (new_domain->p[row][col + 1], domain->p[row][col]);
4237 nrows = 6, ncols = 5
4249 row = domain->NbRows;
4251 /* Add outer loop. */
4253 get_lower_bound (new_domain, col_loop_old, old_lower_bound);
4254 get_upper_bound (new_domain, col_loop_old, old_upper_bound);
4256 /* Set Lower Bound */
4257 value_set_si (new_domain->p[row][0], 1);
4258 value_set_si (new_domain->p[row][col_loop_strip], 1);
4259 value_assign (new_domain->p[row][const_column_index (new_domain)],
4270 1 0 0 -1 99 | copy old lower bound
4277 Value new_upper_bound;
4278 Value strip_size_value;
4280 value_init (new_upper_bound);
4282 value_init (strip_size_value);
4283 value_set_si (strip_size_value, (int) stride);
4286 value_pdivision(new_upper_bound,old_upper_bound,strip_size_value);
4287 value_add_int (new_upper_bound, new_upper_bound, 1);
4289 /* Set Upper Bound */
4290 value_set_si (new_domain->p[row][0], 1);
4291 value_set_si (new_domain->p[row][col_loop_strip], -1);
4292 value_assign (new_domain->p[row][const_column_index (new_domain)],
4304 1 0 -1 0 25 (divide old upper bound with stride)
4309 row = get_lower_bound_row (new_domain, col_loop_old);
4310 /* Add local variable to keep linear representation. */
4311 value_set_si (new_domain->p[row][0], 1);
4312 value_set_si (new_domain->p[row][const_column_index (new_domain)],0);
4313 value_set_si (new_domain->p[row][col_loop_old], 1);
4314 value_set_si (new_domain->p[row][col_loop_strip], -1*((int)stride));
4325 1 0 -1 0 25 (divide old upper bound with stride)
4330 row = new_domain->NbRows-1;
4332 value_set_si (new_domain->p[row][0], 1);
4333 value_set_si (new_domain->p[row][col_loop_old], -1);
4334 value_set_si (new_domain->p[row][col_loop_strip], stride);
4335 value_set_si (new_domain->p[row][const_column_index (new_domain)],
4344 1 0 -4 1 0 j >= 4*jj
4347 1 0 -1 0 25 25 >= jj
4348 0 0 4 -1 3 jj+3 >= j
4351 cloog_matrix_free (domain);
4353 /* Update static schedule. */
4356 int nb_loops = gbb_nb_loops (gb);
4357 lambda_vector new_schedule = lambda_vector_new (nb_loops + 1);
4359 for (i = 0; i <= loop_depth; i++)
4360 new_schedule[i] = GBB_STATIC_SCHEDULE (gb)[i];
4362 for (i = loop_depth + 1; i <= nb_loops - 2; i++)
4363 new_schedule[i + 2] = GBB_STATIC_SCHEDULE (gb)[i];
4365 GBB_STATIC_SCHEDULE (gb) = new_schedule;
4369 /* Returns true when the strip mining of LOOP_INDEX by STRIDE is
4370 profitable or undecidable. GB is the statement around which the
4371 loops will be strip mined. */
4374 strip_mine_profitable_p (graphite_bb_p gb, int stride,
4383 loop = VEC_index (loop_p, GBB_LOOPS (gb), loop_index);
4384 exit = single_exit (loop);
4386 niter = find_loop_niter (loop, &exit);
4387 if (niter == chrec_dont_know
4388 || TREE_CODE (niter) != INTEGER_CST)
4391 niter_val = int_cst_value (niter);
4393 if (niter_val < stride)
4396 if (dump_file && (dump_flags & TDF_DETAILS))
4398 fprintf (dump_file, "\nStrip Mining is not profitable for loop %d:",
4400 fprintf (dump_file, "number of iterations is too low.\n");
4407 /* Determines when the interchange of LOOP_A and LOOP_B belonging to
4411 is_interchange_valid (scop_p scop, int loop_a, int loop_b)
4414 VEC (ddr_p, heap) *dependence_relations;
4415 VEC (data_reference_p, heap) *datarefs;
4417 struct loop *nest = VEC_index (loop_p, SCOP_LOOP_NEST (scop), loop_a);
4418 int depth = perfect_loop_nest_depth (nest);
4419 lambda_trans_matrix trans;
4421 gcc_assert (loop_a < loop_b);
4423 dependence_relations = VEC_alloc (ddr_p, heap, 10 * 10);
4424 datarefs = VEC_alloc (data_reference_p, heap, 10);
4426 if (!compute_data_dependences_for_loop (nest, true, &datarefs,
4427 &dependence_relations))
4430 if (dump_file && (dump_flags & TDF_DETAILS))
4431 dump_ddrs (dump_file, dependence_relations);
4433 trans = lambda_trans_matrix_new (depth, depth);
4434 lambda_matrix_id (LTM_MATRIX (trans), depth);
4436 lambda_matrix_row_exchange (LTM_MATRIX (trans), 0, loop_b - loop_a);
4438 if (!lambda_transform_legal_p (trans, depth, dependence_relations))
4440 lambda_matrix_row_exchange (LTM_MATRIX (trans), 0, loop_b - loop_a);
4446 free_dependence_relations (dependence_relations);
4447 free_data_refs (datarefs);
4451 /* Loop block the LOOPS innermost loops of GB with stride size STRIDE.
4455 for (i = 0; i <= 50; i++=4)
4456 for (k = 0; k <= 100; k++=4)
4457 for (l = 0; l <= 200; l++=4)
4460 To strip mine the two inner most loops with stride = 4 call:
4462 graphite_trans_bb_block (A, 4, 2)
4464 for (i = 0; i <= 50; i++)
4465 for (kk = 0; kk <= 100; kk+=4)
4466 for (ll = 0; ll <= 200; ll+=4)
4467 for (k = kk; k <= min (100, kk + 3); k++)
4468 for (l = ll; l <= min (200, ll + 3); l++)
4473 graphite_trans_bb_block (graphite_bb_p gb, int stride, int loops)
4476 int nb_loops = gbb_nb_loops (gb);
4477 int start = nb_loops - loops;
4478 scop_p scop = GBB_SCOP (gb);
4480 gcc_assert (scop_contains_loop (scop, gbb_loop (gb)));
4482 for (i = start ; i < nb_loops; i++)
4483 for (j = i + 1; j < nb_loops; j++)
4484 if (!is_interchange_valid (scop, i, j))
4486 if (dump_file && (dump_flags & TDF_DETAILS))
4488 "\nInterchange not valid for loops %d and %d:\n", i, j);
4491 else if (dump_file && (dump_flags & TDF_DETAILS))
4493 "\nInterchange valid for loops %d and %d:\n", i, j);
4495 /* Check if strip mining is profitable for every loop. */
4496 for (i = 0; i < nb_loops - start; i++)
4497 if (!strip_mine_profitable_p (gb, stride, start + i))
4500 /* Strip mine loops. */
4501 for (i = 0; i < nb_loops - start; i++)
4502 graphite_trans_bb_strip_mine (gb, start + 2 * i, stride);
4504 /* Interchange loops. */
4505 for (i = 1; i < nb_loops - start; i++)
4506 graphite_trans_bb_move_loop (gb, start + 2 * i, start + i);
4511 /* Loop block LOOPS innermost loops of a loop nest. BBS represent the
4512 basic blocks that belong to the loop nest to be blocked. */
4515 graphite_trans_loop_block (VEC (graphite_bb_p, heap) *bbs, int loops)
4519 bool transform_done = false;
4521 /* TODO: - Calculate the stride size automatically. */
4522 int stride_size = 64;
4524 for (i = 0; VEC_iterate (graphite_bb_p, bbs, i, gb); i++)
4525 transform_done |= graphite_trans_bb_block (gb, stride_size, loops);
4527 return transform_done;
4530 /* Loop block all basic blocks of SCOP. */
4533 graphite_trans_scop_block (scop_p scop)
4539 bool perfect = true;
4540 bool transform_done = false;
4542 VEC (graphite_bb_p, heap) *bbs = VEC_alloc (graphite_bb_p, heap, 3);
4543 int max_schedule = scop_max_loop_depth (scop) + 1;
4544 lambda_vector last_schedule = lambda_vector_new (max_schedule);
4546 if (VEC_length (graphite_bb_p, SCOP_BBS (scop)) == 0)
4547 return transform_done;
4549 /* Get the data of the first bb. */
4550 gb = VEC_index (graphite_bb_p, SCOP_BBS (scop), 0);
4551 last_nb_loops = gbb_nb_loops (gb);
4552 lambda_vector_copy (GBB_STATIC_SCHEDULE (gb), last_schedule,
4554 VEC_safe_push (graphite_bb_p, heap, bbs, gb);
4556 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
4558 /* We did the first bb before. */
4562 nb_loops = gbb_nb_loops (gb);
4564 /* If the number of loops is unchanged and only the last element of the
4565 schedule changes, we stay in the loop nest. */
4566 if (nb_loops == last_nb_loops
4567 && (last_schedule [nb_loops + 1]
4568 != GBB_STATIC_SCHEDULE (gb)[nb_loops + 1]))
4570 VEC_safe_push (graphite_bb_p, heap, bbs, gb);
4574 /* Otherwise, we left the innermost loop. So check, if the last bb was in
4575 a perfect loop nest and how many loops are contained in this perfect
4578 Count the number of zeros from the end of the schedule. They are the
4579 number of surrounding loops.
4582 last_bb 2 3 2 0 0 0 0 3
4586 last_bb 2 3 2 0 0 0 0 3
4590 If there is no zero, there were other bbs in outer loops and the loop
4591 nest is not perfect. */
4592 for (j = last_nb_loops - 1; j >= 0; j--)
4594 if (last_schedule [j] != 0
4595 || (j <= nb_loops && GBB_STATIC_SCHEDULE (gb)[j] == 1))
4604 /* Found perfect loop nest. */
4605 if (perfect && last_nb_loops - j > 0)
4606 transform_done |= graphite_trans_loop_block (bbs, last_nb_loops - j);
4608 /* Check if we start with a new loop.
4612 last_bb 2 3 2 0 0 0 0 3
4615 Here we start with the loop "2 3 2 0 0 1"
4617 last_bb 2 3 2 0 0 0 0 3
4620 But here not, so the loop nest can never be perfect. */
4622 perfect = (GBB_STATIC_SCHEDULE (gb)[nb_loops] == 0);
4624 /* Update the last_bb infos. We do not do that for the bbs in the same
4625 loop, as the data we use is not changed. */
4626 last_nb_loops = nb_loops;
4627 lambda_vector_copy (GBB_STATIC_SCHEDULE (gb), last_schedule,
4629 VEC_truncate (graphite_bb_p, bbs, 0);
4630 VEC_safe_push (graphite_bb_p, heap, bbs, gb);
4633 /* Check if the last loop nest was perfect. It is the same check as above,
4634 but the comparison with the next bb is missing. */
4635 for (j = last_nb_loops - 1; j >= 0; j--)
4636 if (last_schedule [j] != 0)
4644 /* Found perfect loop nest. */
4645 if (last_nb_loops - j > 0)
4646 transform_done |= graphite_trans_loop_block (bbs, last_nb_loops - j);
4647 VEC_free (graphite_bb_p, heap, bbs);
4649 if (dump_file && (dump_flags & TDF_DETAILS))
4650 fprintf (dump_file, "\nLoop blocked.\n");
4652 return transform_done;
4655 /* Apply graphite transformations to all the basic blocks of SCOP. */
4658 graphite_apply_transformations (scop_p scop)
4660 bool transform_done = false;
4662 /* Sort the list of bbs. Keep them always sorted. */
4663 graphite_sort_gbbs (scop);
4664 scop_remove_ignoreable_gbbs (scop);
4666 if (flag_loop_block)
4667 transform_done = graphite_trans_scop_block (scop);
4669 #if 0 && ENABLE_CHECKING
4670 /* When the compiler is configured with ENABLE_CHECKING, always
4671 generate code, even if we did not apply any transformation. This
4672 provides better code coverage of the backend code generator.
4674 This also allows to check the performance for an identity
4675 transform: GIMPLE -> GRAPHITE -> GIMPLE; and the output of CLooG
4676 is never an identity: if CLooG optimizations are not disabled,
4677 the CLooG output is always optimized in control flow. */
4678 transform_done = true;
4681 return transform_done;
4684 /* We limit all SCoPs to SCoPs, that are completely surrounded by a loop.
4694 * SCoP frontier, as this line is not surrounded by any loop. *
4698 This is necessary as scalar evolution and parameter detection need a
4699 outermost loop to initialize parameters correctly.
4701 TODO: FIX scalar evolution and parameter detection to allow mor flexible
4707 VEC (scop_p, heap) *new_scops = VEC_alloc (scop_p, heap, 3);
4711 for (i = 0; VEC_iterate (scop_p, current_scops, i, scop); i++)
4715 build_scop_bbs (scop);
4716 build_scop_loop_nests (scop);
4718 for (j = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), j, loop); j++)
4719 if (!loop_in_scop_p (loop_outer (loop), scop))
4721 scop_p n_scop = new_scop (loop_preheader_edge (loop));
4722 end_scop (n_scop, single_exit (loop), false);
4723 VEC_safe_push (scop_p, heap, new_scops, n_scop);
4727 free_scops (current_scops);
4728 current_scops = new_scops;
4731 /* Perform a set of linear transforms on the loops of the current
4735 graphite_transform_loops (void)
4740 if (number_of_loops () <= 1)
4743 current_scops = VEC_alloc (scop_p, heap, 3);
4745 calculate_dominance_info (CDI_DOMINATORS);
4746 calculate_dominance_info (CDI_POST_DOMINATORS);
4748 if (dump_file && (dump_flags & TDF_DETAILS))
4749 fprintf (dump_file, "Graphite loop transformations \n");
4751 cloog_initialize ();
4755 if (dump_file && (dump_flags & TDF_DETAILS))
4756 fprintf (dump_file, "\nnumber of SCoPs: %d\n",
4757 VEC_length (scop_p, current_scops));
4759 for (i = 0; VEC_iterate (scop_p, current_scops, i, scop); i++)
4761 build_scop_bbs (scop);
4762 build_scop_loop_nests (scop);
4763 build_scop_canonical_schedules (scop);
4764 build_bb_loops (scop);
4765 find_scop_parameters (scop);
4766 build_scop_context (scop);
4768 if (dump_file && (dump_flags & TDF_DETAILS))
4770 fprintf (dump_file, "\n(In SCoP %d:\n", i);
4771 fprintf (dump_file, "\nnumber of bbs: %d\n",
4772 VEC_length (graphite_bb_p, SCOP_BBS (scop)));
4773 fprintf (dump_file, "\nnumber of loops: %d)\n",
4774 VEC_length (loop_p, SCOP_LOOP_NEST (scop)));
4777 if (!build_scop_iteration_domain (scop))
4780 build_scop_conditions (scop);
4781 build_scop_data_accesses (scop);
4783 if (dump_file && (dump_flags & TDF_DETAILS))
4785 int nbrefs = nb_data_refs_in_scop (scop);
4786 fprintf (dump_file, "\nnumber of data refs: %d\n", nbrefs);
4789 if (graphite_apply_transformations (scop))
4790 gloog (scop, find_transform (scop));
4794 free_scops (current_scops);
4798 #else /* If Cloog is not available: #ifndef HAVE_cloog. */
4801 graphite_transform_loops (void)
4803 if (dump_file && (dump_flags & TDF_DETAILS))
4805 fprintf (dump_file, "Graphite loop optimizations cannot be used.\n");
4806 fprintf (dump_file, "GCC has not been configured with the required "
4807 "libraries for Graphite loop optimizations.");
4809 sorry ("Graphite loop optimizations cannot be used");