1 /* Gimple Represented as Polyhedra.
2 Copyright (C) 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <sebastian.pop@inria.fr>.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* This pass converts GIMPLE to GRAPHITE, performs some loop
22 transformations and then converts the resulting representation back
25 An early description of this pass can be found in the GCC Summit'06
26 paper "GRAPHITE: Polyhedral Analyses and Optimizations for GCC".
27 The wiki page http://gcc.gnu.org/wiki/Graphite contains pointers to
30 One important document to read is CLooG's internal manual:
31 http://repo.or.cz/w/cloog-ppl.git?a=blob_plain;f=doc/cloog.texi;hb=HEAD
32 that describes the data structure of loops used in this file, and
33 the functions that are used for transforming the code. */
37 #include "coretypes.h"
42 #include "basic-block.h"
43 #include "diagnostic.h"
44 #include "tree-flow.h"
46 #include "tree-dump.h"
49 #include "tree-chrec.h"
50 #include "tree-data-ref.h"
51 #include "tree-scalar-evolution.h"
52 #include "tree-pass.h"
54 #include "value-prof.h"
55 #include "pointer-set.h"
59 #include "cloog/cloog.h"
62 static VEC (scop_p, heap) *current_scops;
64 /* Converts a GMP constant V to a tree and returns it. */
67 gmp_cst_to_tree (tree type, Value v)
69 return build_int_cst (type, value_get_si (v));
72 /* Returns true when BB is in REGION. */
75 bb_in_sese_p (basic_block bb, sese region)
77 return pointer_set_contains (SESE_REGION_BBS (region), bb);
80 /* Returns true when LOOP is in the SESE region R. */
83 loop_in_sese_p (struct loop *loop, sese r)
85 return (bb_in_sese_p (loop->header, r)
86 && bb_in_sese_p (loop->latch, r));
89 /* For a USE in BB, if BB is outside REGION, mark the USE in the
90 SESE_LIVEIN and SESE_LIVEOUT sets. */
93 sese_build_livein_liveouts_use (sese region, basic_block bb, tree use)
98 if (TREE_CODE (use) != SSA_NAME)
101 ver = SSA_NAME_VERSION (use);
102 def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
104 || !bb_in_sese_p (def_bb, region)
105 || bb_in_sese_p (bb, region))
108 if (!SESE_LIVEIN_VER (region, ver))
109 SESE_LIVEIN_VER (region, ver) = BITMAP_ALLOC (NULL);
111 bitmap_set_bit (SESE_LIVEIN_VER (region, ver), bb->index);
112 bitmap_set_bit (SESE_LIVEOUT (region), ver);
115 /* Marks for rewrite all the SSA_NAMES defined in REGION and that are
116 used in BB that is outside of the REGION. */
119 sese_build_livein_liveouts_bb (sese region, basic_block bb)
121 gimple_stmt_iterator bsi;
127 FOR_EACH_EDGE (e, ei, bb->succs)
128 for (bsi = gsi_start_phis (e->dest); !gsi_end_p (bsi); gsi_next (&bsi))
129 sese_build_livein_liveouts_use (region, bb,
130 PHI_ARG_DEF_FROM_EDGE (gsi_stmt (bsi), e));
132 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
133 FOR_EACH_SSA_TREE_OPERAND (var, gsi_stmt (bsi), iter, SSA_OP_ALL_USES)
134 sese_build_livein_liveouts_use (region, bb, var);
137 /* Build the SESE_LIVEIN and SESE_LIVEOUT for REGION. */
140 sese_build_livein_liveouts (sese region)
144 SESE_LIVEOUT (region) = BITMAP_ALLOC (NULL);
145 SESE_NUM_VER (region) = num_ssa_names;
146 SESE_LIVEIN (region) = XCNEWVEC (bitmap, SESE_NUM_VER (region));
149 sese_build_livein_liveouts_bb (region, bb);
152 /* Register basic blocks belonging to a region in a pointer set. */
155 register_bb_in_sese (basic_block entry_bb, basic_block exit_bb, sese region)
159 basic_block bb = entry_bb;
161 FOR_EACH_EDGE (e, ei, bb->succs)
163 if (!pointer_set_contains (SESE_REGION_BBS (region), e->dest) &&
164 e->dest->index != exit_bb->index)
166 pointer_set_insert (SESE_REGION_BBS (region), e->dest);
167 register_bb_in_sese (e->dest, exit_bb, region);
172 /* Builds a new SESE region from edges ENTRY and EXIT. */
175 new_sese (edge entry, edge exit)
177 sese res = XNEW (struct sese);
179 SESE_ENTRY (res) = entry;
180 SESE_EXIT (res) = exit;
181 SESE_REGION_BBS (res) = pointer_set_create ();
182 register_bb_in_sese (entry->dest, exit->dest, res);
184 SESE_LIVEOUT (res) = NULL;
185 SESE_NUM_VER (res) = 0;
186 SESE_LIVEIN (res) = NULL;
191 /* Deletes REGION. */
194 free_sese (sese region)
198 for (i = 0; i < SESE_NUM_VER (region); i++)
199 BITMAP_FREE (SESE_LIVEIN_VER (region, i));
201 if (SESE_LIVEIN (region))
202 free (SESE_LIVEIN (region));
204 if (SESE_LIVEOUT (region))
205 BITMAP_FREE (SESE_LIVEOUT (region));
207 pointer_set_destroy (SESE_REGION_BBS (region));
213 /* Debug the list of old induction variables for this SCOP. */
216 debug_oldivs (scop_p scop)
221 fprintf (stderr, "Old IVs:");
223 for (i = 0; VEC_iterate (name_tree, SCOP_OLDIVS (scop), i, oldiv); i++)
225 fprintf (stderr, "(");
226 print_generic_expr (stderr, oldiv->t, 0);
227 fprintf (stderr, ", %s, %d)\n", oldiv->name, oldiv->loop->num);
229 fprintf (stderr, "\n");
232 /* Debug the loops around basic block GB. */
235 debug_loop_vec (graphite_bb_p gb)
240 fprintf (stderr, "Loop Vec:");
242 for (i = 0; VEC_iterate (loop_p, GBB_LOOPS (gb), i, loop); i++)
243 fprintf (stderr, "%d: %d, ", i, loop ? loop->num : -1);
245 fprintf (stderr, "\n");
248 /* Returns true if stack ENTRY is a constant. */
251 iv_stack_entry_is_constant (iv_stack_entry *entry)
253 return entry->kind == iv_stack_entry_const;
256 /* Returns true if stack ENTRY is an induction variable. */
259 iv_stack_entry_is_iv (iv_stack_entry *entry)
261 return entry->kind == iv_stack_entry_iv;
264 /* Push (IV, NAME) on STACK. */
267 loop_iv_stack_push_iv (loop_iv_stack stack, tree iv, const char *name)
269 iv_stack_entry *entry = XNEW (iv_stack_entry);
270 name_tree named_iv = XNEW (struct name_tree);
273 named_iv->name = name;
275 entry->kind = iv_stack_entry_iv;
276 entry->data.iv = named_iv;
278 VEC_safe_push (iv_stack_entry_p, heap, *stack, entry);
281 /* Inserts a CONSTANT in STACK at INDEX. */
284 loop_iv_stack_insert_constant (loop_iv_stack stack, int index,
287 iv_stack_entry *entry = XNEW (iv_stack_entry);
289 entry->kind = iv_stack_entry_const;
290 entry->data.constant = constant;
292 VEC_safe_insert (iv_stack_entry_p, heap, *stack, index, entry);
295 /* Pops and frees an element out of STACK. */
298 loop_iv_stack_pop (loop_iv_stack stack)
300 iv_stack_entry_p entry = VEC_pop (iv_stack_entry_p, *stack);
302 free (entry->data.iv);
306 /* Get the IV at INDEX in STACK. */
309 loop_iv_stack_get_iv (loop_iv_stack stack, int index)
311 iv_stack_entry_p entry = VEC_index (iv_stack_entry_p, *stack, index);
312 iv_stack_entry_data data = entry->data;
314 return iv_stack_entry_is_iv (entry) ? data.iv->t : data.constant;
317 /* Get the IV from its NAME in STACK. */
320 loop_iv_stack_get_iv_from_name (loop_iv_stack stack, const char* name)
323 iv_stack_entry_p entry;
325 for (i = 0; VEC_iterate (iv_stack_entry_p, *stack, i, entry); i++)
327 name_tree iv = entry->data.iv;
328 if (!strcmp (name, iv->name))
335 /* Prints on stderr the contents of STACK. */
338 debug_loop_iv_stack (loop_iv_stack stack)
341 iv_stack_entry_p entry;
344 fprintf (stderr, "(");
346 for (i = 0; VEC_iterate (iv_stack_entry_p, *stack, i, entry); i++)
351 fprintf (stderr, " ");
353 if (iv_stack_entry_is_iv (entry))
355 name_tree iv = entry->data.iv;
356 fprintf (stderr, "%s:", iv->name);
357 print_generic_expr (stderr, iv->t, 0);
361 tree constant = entry->data.constant;
362 print_generic_expr (stderr, constant, 0);
363 fprintf (stderr, ":");
364 print_generic_expr (stderr, constant, 0);
368 fprintf (stderr, ")\n");
374 free_loop_iv_stack (loop_iv_stack stack)
377 iv_stack_entry_p entry;
379 for (i = 0; VEC_iterate (iv_stack_entry_p, *stack, i, entry); i++)
381 free (entry->data.iv);
385 VEC_free (iv_stack_entry_p, heap, *stack);
390 /* Structure containing the mapping between the CLooG's induction
391 variable and the type of the old induction variable. */
392 typedef struct ivtype_map_elt
395 const char *cloog_iv;
398 /* Print to stderr the element ELT. */
401 debug_ivtype_elt (ivtype_map_elt elt)
403 fprintf (stderr, "(%s, ", elt->cloog_iv);
404 print_generic_expr (stderr, elt->type, 0);
405 fprintf (stderr, ")\n");
408 /* Helper function for debug_ivtype_map. */
411 debug_ivtype_map_1 (void **slot, void *s ATTRIBUTE_UNUSED)
413 struct ivtype_map_elt *entry = (struct ivtype_map_elt *) *slot;
414 debug_ivtype_elt (entry);
418 /* Print to stderr all the elements of MAP. */
421 debug_ivtype_map (htab_t map)
423 htab_traverse (map, debug_ivtype_map_1, NULL);
426 /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */
428 static inline ivtype_map_elt
429 new_ivtype_map_elt (const char *cloog_iv, tree type)
433 res = XNEW (struct ivtype_map_elt);
434 res->cloog_iv = cloog_iv;
440 /* Computes a hash function for database element ELT. */
443 ivtype_map_elt_info (const void *elt)
445 return htab_hash_pointer (((const struct ivtype_map_elt *) elt)->cloog_iv);
448 /* Compares database elements E1 and E2. */
451 eq_ivtype_map_elts (const void *e1, const void *e2)
453 const struct ivtype_map_elt *elt1 = (const struct ivtype_map_elt *) e1;
454 const struct ivtype_map_elt *elt2 = (const struct ivtype_map_elt *) e2;
456 return (elt1->cloog_iv == elt2->cloog_iv);
461 /* Given a CLOOG_IV, returns the type that it should have in GCC land.
462 If the information is not available, i.e. in the case one of the
463 transforms created the loop, just return integer_type_node. */
466 gcc_type_for_cloog_iv (const char *cloog_iv, graphite_bb_p gbb)
468 struct ivtype_map_elt tmp;
471 tmp.cloog_iv = cloog_iv;
472 slot = htab_find_slot (GBB_CLOOG_IV_TYPES (gbb), &tmp, NO_INSERT);
475 return ((ivtype_map_elt) *slot)->type;
477 return integer_type_node;
480 /* Inserts constants derived from the USER_STMT argument list into the
481 STACK. This is needed to map old ivs to constants when loops have
485 loop_iv_stack_patch_for_consts (loop_iv_stack stack,
486 struct clast_user_stmt *user_stmt)
488 struct clast_stmt *t;
490 CloogStatement *cs = user_stmt->statement;
491 graphite_bb_p gbb = (graphite_bb_p) cloog_statement_usr (cs);
493 for (t = user_stmt->substitutions; t; t = t->next)
495 struct clast_expr *expr = (struct clast_expr *)
496 ((struct clast_assignment *)t)->RHS;
497 struct clast_term *term = (struct clast_term *) expr;
499 /* FIXME: What should be done with expr_bin, expr_red? */
500 if (expr->type == expr_term
503 loop_p loop = gbb_loop_at_index (gbb, index);
504 tree oldiv = oldiv_for_loop (GBB_SCOP (gbb), loop);
505 tree type = oldiv ? TREE_TYPE (oldiv) : integer_type_node;
506 tree value = gmp_cst_to_tree (type, term->val);
507 loop_iv_stack_insert_constant (stack, index, value);
513 /* Removes all constants in the iv STACK. */
516 loop_iv_stack_remove_constants (loop_iv_stack stack)
519 iv_stack_entry *entry;
521 for (i = 0; VEC_iterate (iv_stack_entry_p, *stack, i, entry);)
523 if (iv_stack_entry_is_constant (entry))
525 free (VEC_index (iv_stack_entry_p, *stack, i));
526 VEC_ordered_remove (iv_stack_entry_p, *stack, i);
533 /* Returns a new loop_to_cloog_loop_str structure. */
535 static inline struct loop_to_cloog_loop_str *
536 new_loop_to_cloog_loop_str (int loop_num,
538 CloogLoop *cloog_loop)
540 struct loop_to_cloog_loop_str *result;
542 result = XNEW (struct loop_to_cloog_loop_str);
543 result->loop_num = loop_num;
544 result->cloog_loop = cloog_loop;
545 result->loop_position = loop_position;
550 /* Hash function for SCOP_LOOP2CLOOG_LOOP hash table. */
553 hash_loop_to_cloog_loop (const void *elt)
555 return ((const struct loop_to_cloog_loop_str *) elt)->loop_num;
558 /* Equality function for SCOP_LOOP2CLOOG_LOOP hash table. */
561 eq_loop_to_cloog_loop (const void *el1, const void *el2)
563 const struct loop_to_cloog_loop_str *elt1, *elt2;
565 elt1 = (const struct loop_to_cloog_loop_str *) el1;
566 elt2 = (const struct loop_to_cloog_loop_str *) el2;
567 return elt1->loop_num == elt2->loop_num;
570 /* Compares two graphite bbs and returns an integer less than, equal to, or
571 greater than zero if the first argument is considered to be respectively
572 less than, equal to, or greater than the second.
573 We compare using the lexicographic order of the static schedules. */
576 gbb_compare (const void *p_1, const void *p_2)
578 const struct graphite_bb *const gbb_1
579 = *(const struct graphite_bb *const*) p_1;
580 const struct graphite_bb *const gbb_2
581 = *(const struct graphite_bb *const*) p_2;
583 return lambda_vector_compare (GBB_STATIC_SCHEDULE (gbb_1),
584 gbb_nb_loops (gbb_1) + 1,
585 GBB_STATIC_SCHEDULE (gbb_2),
586 gbb_nb_loops (gbb_2) + 1);
589 /* Sort graphite bbs in SCOP. */
592 graphite_sort_gbbs (scop_p scop)
594 VEC (graphite_bb_p, heap) *bbs = SCOP_BBS (scop);
596 qsort (VEC_address (graphite_bb_p, bbs),
597 VEC_length (graphite_bb_p, bbs),
598 sizeof (graphite_bb_p), gbb_compare);
601 /* Dump conditions of a graphite basic block GBB on FILE. */
604 dump_gbb_conditions (FILE *file, graphite_bb_p gbb)
608 VEC (gimple, heap) *conditions = GBB_CONDITIONS (gbb);
610 if (VEC_empty (gimple, conditions))
613 fprintf (file, "\tbb %d\t: cond = {", GBB_BB (gbb)->index);
615 for (i = 0; VEC_iterate (gimple, conditions, i, stmt); i++)
616 print_gimple_stmt (file, stmt, 0, 0);
618 fprintf (file, "}\n");
621 /* Converts the graphite scheduling function into a cloog scattering
622 matrix. This scattering matrix is used to limit the possible cloog
623 output to valid programs in respect to the scheduling function.
625 SCATTERING_DIMENSIONS specifies the dimensionality of the scattering
626 matrix. CLooG 0.14.0 and previous versions require, that all scattering
627 functions of one CloogProgram have the same dimensionality, therefore we
628 allow to specify it. (Should be removed in future versions) */
631 schedule_to_scattering (graphite_bb_p gb, int scattering_dimensions)
634 scop_p scop = GBB_SCOP (gb);
636 int nb_iterators = gbb_nb_loops (gb);
638 /* The cloog scattering matrix consists of these colums:
640 scattering_dimensions cols = Scattering dimensions,
641 nb_iterators cols = bb's iterators,
642 scop_nb_params cols = Parameters,
647 scattering_dimensions = 5
657 s1 s2 s3 s4 s5 i p1 p2 1
658 1 0 0 0 0 0 0 0 -4 = 0
659 0 1 0 0 0 -1 0 0 0 = 0
660 0 0 1 0 0 0 0 0 -5 = 0 */
661 int nb_params = scop_nb_params (scop);
662 int nb_cols = 1 + scattering_dimensions + nb_iterators + nb_params + 1;
663 int col_const = nb_cols - 1;
664 int col_iter_offset = 1 + scattering_dimensions;
666 CloogMatrix *scat = cloog_matrix_alloc (scattering_dimensions, nb_cols);
668 gcc_assert (scattering_dimensions >= nb_iterators * 2 + 1);
670 /* Initialize the identity matrix. */
671 for (i = 0; i < scattering_dimensions; i++)
672 value_set_si (scat->p[i][i + 1], 1);
674 /* Textual order outside the first loop */
675 value_set_si (scat->p[0][col_const], -GBB_STATIC_SCHEDULE (gb)[0]);
677 /* For all surrounding loops. */
678 for (i = 0; i < nb_iterators; i++)
680 int schedule = GBB_STATIC_SCHEDULE (gb)[i + 1];
682 /* Iterations of this loop. */
683 value_set_si (scat->p[2 * i + 1][col_iter_offset + i], -1);
685 /* Textual order inside this loop. */
686 value_set_si (scat->p[2 * i + 2][col_const], -schedule);
692 /* Print the schedules of GB to FILE with INDENT white spaces before.
693 VERBOSITY determines how verbose the code pretty printers are. */
696 print_graphite_bb (FILE *file, graphite_bb_p gb, int indent, int verbosity)
698 CloogMatrix *scattering;
701 fprintf (file, "\nGBB (\n");
703 print_loops_bb (file, GBB_BB (gb), indent+2, verbosity);
707 fprintf (file, " (domain: \n");
708 cloog_matrix_print (file, GBB_DOMAIN (gb));
709 fprintf (file, " )\n");
712 if (GBB_STATIC_SCHEDULE (gb))
714 fprintf (file, " (static schedule: ");
715 print_lambda_vector (file, GBB_STATIC_SCHEDULE (gb),
716 gbb_nb_loops (gb) + 1);
717 fprintf (file, " )\n");
722 fprintf (file, " (contained loops: \n");
723 for (i = 0; VEC_iterate (loop_p, GBB_LOOPS (gb), i, loop); i++)
725 fprintf (file, " iterator %d => NULL \n", i);
727 fprintf (file, " iterator %d => loop %d \n", i,
729 fprintf (file, " )\n");
732 if (GBB_DATA_REFS (gb))
733 dump_data_references (file, GBB_DATA_REFS (gb));
735 if (GBB_CONDITIONS (gb))
737 fprintf (file, " (conditions: \n");
738 dump_gbb_conditions (file, gb);
739 fprintf (file, " )\n");
743 && GBB_STATIC_SCHEDULE (gb))
745 fprintf (file, " (scattering: \n");
746 scattering = schedule_to_scattering (gb, 2 * gbb_nb_loops (gb) + 1);
747 cloog_matrix_print (file, scattering);
748 cloog_matrix_free (scattering);
749 fprintf (file, " )\n");
752 fprintf (file, ")\n");
755 /* Print to STDERR the schedules of GB with VERBOSITY level. */
758 debug_gbb (graphite_bb_p gb, int verbosity)
760 print_graphite_bb (stderr, gb, 0, verbosity);
764 /* Print SCOP to FILE. VERBOSITY determines how verbose the pretty
768 print_scop (FILE *file, scop_p scop, int verbosity)
773 fprintf (file, "\nSCoP_%d_%d (\n",
774 SCOP_ENTRY (scop)->index, SCOP_EXIT (scop)->index);
776 fprintf (file, " (cloog: \n");
777 cloog_program_print (file, SCOP_PROG (scop));
778 fprintf (file, " )\n");
785 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
786 print_graphite_bb (file, gb, 0, verbosity);
789 fprintf (file, ")\n");
792 /* Print all the SCOPs to FILE. VERBOSITY determines how verbose the
793 code pretty printers are. */
796 print_scops (FILE *file, int verbosity)
801 for (i = 0; VEC_iterate (scop_p, current_scops, i, scop); i++)
802 print_scop (file, scop, verbosity);
805 /* Debug SCOP. VERBOSITY determines how verbose the code pretty
809 debug_scop (scop_p scop, int verbosity)
811 print_scop (stderr, scop, verbosity);
814 /* Debug all SCOPs from CURRENT_SCOPS. VERBOSITY determines how
815 verbose the code pretty printers are. */
818 debug_scops (int verbosity)
820 print_scops (stderr, verbosity);
823 /* Pretty print to FILE the SCOP in DOT format. */
826 dot_scop_1 (FILE *file, scop_p scop)
831 basic_block entry = SCOP_ENTRY (scop);
832 basic_block exit = SCOP_EXIT (scop);
834 fprintf (file, "digraph SCoP_%d_%d {\n", entry->index,
840 fprintf (file, "%d [shape=triangle];\n", bb->index);
843 fprintf (file, "%d [shape=box];\n", bb->index);
845 if (bb_in_sese_p (bb, SCOP_REGION (scop)))
846 fprintf (file, "%d [color=red];\n", bb->index);
848 FOR_EACH_EDGE (e, ei, bb->succs)
849 fprintf (file, "%d -> %d;\n", bb->index, e->dest->index);
852 fputs ("}\n\n", file);
855 /* Display SCOP using dotty. */
858 dot_scop (scop_p scop)
860 dot_scop_1 (stderr, scop);
863 /* Pretty print all SCoPs in DOT format and mark them with different colors.
864 If there are not enough colors, paint later SCoPs gray.
866 - "*" after the node number: entry of a SCoP,
867 - "#" after the node number: exit of a SCoP,
868 - "()" entry or exit not part of SCoP. */
871 dot_all_scops_1 (FILE *file)
880 /* Disable debugging while printing graph. */
881 int tmp_dump_flags = dump_flags;
884 fprintf (file, "digraph all {\n");
888 int part_of_scop = false;
890 /* Use HTML for every bb label. So we are able to print bbs
891 which are part of two different SCoPs, with two different
892 background colors. */
893 fprintf (file, "%d [label=<\n <TABLE BORDER=\"0\" CELLBORDER=\"1\" ",
895 fprintf (file, "CELLSPACING=\"0\">\n");
897 /* Select color for SCoP. */
898 for (i = 0; VEC_iterate (scop_p, current_scops, i, scop); i++)
899 if (bb_in_sese_p (bb, SCOP_REGION (scop))
900 || (SCOP_EXIT (scop) == bb)
901 || (SCOP_ENTRY (scop) == bb))
960 fprintf (file, " <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">", color);
962 if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
963 fprintf (file, " (");
965 if (bb == SCOP_ENTRY (scop)
966 && bb == SCOP_EXIT (scop))
967 fprintf (file, " %d*# ", bb->index);
968 else if (bb == SCOP_ENTRY (scop))
969 fprintf (file, " %d* ", bb->index);
970 else if (bb == SCOP_EXIT (scop))
971 fprintf (file, " %d# ", bb->index);
973 fprintf (file, " %d ", bb->index);
975 if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
978 fprintf (file, "</TD></TR>\n");
984 fprintf (file, " <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">");
985 fprintf (file, " %d </TD></TR>\n", bb->index);
988 fprintf (file, " </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n");
993 FOR_EACH_EDGE (e, ei, bb->succs)
994 fprintf (file, "%d -> %d;\n", bb->index, e->dest->index);
997 fputs ("}\n\n", file);
999 /* Enable debugging again. */
1000 dump_flags = tmp_dump_flags;
1003 /* Display all SCoPs using dotty. */
1006 dot_all_scops (void)
1008 /* When debugging, enable the following code. This cannot be used
1009 in production compilers because it calls "system". */
1011 FILE *stream = fopen ("/tmp/allscops.dot", "w");
1012 gcc_assert (stream);
1014 dot_all_scops_1 (stream);
1017 system ("dotty /tmp/allscops.dot");
1019 dot_all_scops_1 (stderr);
1023 /* Returns the outermost loop in SCOP that contains BB. */
1025 static struct loop *
1026 outermost_loop_in_scop (scop_p scop, basic_block bb)
1030 nest = bb->loop_father;
1031 while (loop_outer (nest)
1032 && loop_in_sese_p (loop_outer (nest), SCOP_REGION (scop)))
1033 nest = loop_outer (nest);
1038 /* Returns the block preceding the entry of SCOP. */
1041 block_before_scop (scop_p scop)
1043 return SESE_ENTRY (SCOP_REGION (scop))->src;
1046 /* Return true when EXPR is an affine function in LOOP with parameters
1047 instantiated relative to SCOP_ENTRY. */
1050 loop_affine_expr (basic_block scop_entry, struct loop *loop, tree expr)
1053 tree scev = analyze_scalar_evolution (loop, expr);
1055 scev = instantiate_scev (scop_entry, loop, scev);
1057 return (evolution_function_is_invariant_p (scev, n)
1058 || evolution_function_is_affine_multivariate_p (scev, n));
1061 /* Return false if the tree_code of the operand OP or any of its operands
1062 is component_ref. */
1065 exclude_component_ref (tree op)
1072 if (TREE_CODE (op) == COMPONENT_REF)
1076 len = TREE_OPERAND_LENGTH (op);
1077 for (i = 0; i < len; ++i)
1079 if (!exclude_component_ref (TREE_OPERAND (op, i)))
1088 /* Return true if the operand OP is simple. */
1091 is_simple_operand (loop_p loop, gimple stmt, tree op)
1093 /* It is not a simple operand when it is a declaration, */
1095 /* or a structure, */
1096 || AGGREGATE_TYPE_P (TREE_TYPE (op))
1097 /* or a memory access that cannot be analyzed by the data
1098 reference analysis. */
1099 || ((handled_component_p (op) || INDIRECT_REF_P (op))
1100 && !stmt_simple_memref_p (loop, stmt, op)))
1103 return exclude_component_ref (op);
1106 /* Return true only when STMT is simple enough for being handled by
1107 Graphite. This depends on SCOP_ENTRY, as the parametetrs are
1108 initialized relatively to this basic block. */
1111 stmt_simple_for_scop_p (basic_block scop_entry, gimple stmt)
1113 basic_block bb = gimple_bb (stmt);
1114 struct loop *loop = bb->loop_father;
1116 /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
1117 Calls have side-effects, except those to const or pure
1119 if (gimple_has_volatile_ops (stmt)
1120 || (gimple_code (stmt) == GIMPLE_CALL
1121 && !(gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE)))
1122 || (gimple_code (stmt) == GIMPLE_ASM))
1125 switch (gimple_code (stmt))
1134 ssa_op_iter op_iter;
1135 enum tree_code code = gimple_cond_code (stmt);
1137 /* We can only handle this kind of conditional expressions.
1138 For inequalities like "if (i != 3 * k)" we need unions of
1139 polyhedrons. Expressions like "if (a)" or "if (a == 15)" need
1140 them for the else branch. */
1141 if (!(code == LT_EXPR
1144 || code == GE_EXPR))
1150 FOR_EACH_SSA_TREE_OPERAND (op, stmt, op_iter, SSA_OP_ALL_USES)
1151 if (!loop_affine_expr (scop_entry, loop, op))
1159 enum tree_code code = gimple_assign_rhs_code (stmt);
1161 switch (get_gimple_rhs_class (code))
1163 case GIMPLE_UNARY_RHS:
1164 case GIMPLE_SINGLE_RHS:
1165 return (is_simple_operand (loop, stmt, gimple_assign_lhs (stmt))
1166 && is_simple_operand (loop, stmt, gimple_assign_rhs1 (stmt)));
1168 case GIMPLE_BINARY_RHS:
1169 return (is_simple_operand (loop, stmt, gimple_assign_lhs (stmt))
1170 && is_simple_operand (loop, stmt, gimple_assign_rhs1 (stmt))
1171 && is_simple_operand (loop, stmt, gimple_assign_rhs2 (stmt)));
1173 case GIMPLE_INVALID_RHS:
1182 size_t n = gimple_call_num_args (stmt);
1183 tree lhs = gimple_call_lhs (stmt);
1185 if (lhs && !is_simple_operand (loop, stmt, lhs))
1188 for (i = 0; i < n; i++)
1189 if (!is_simple_operand (loop, stmt, gimple_call_arg (stmt, i)))
1196 /* These nodes cut a new scope. */
1203 /* Returns the statement of BB that contains a harmful operation: that
1204 can be a function call with side effects, the induction variables
1205 are not linear with respect to SCOP_ENTRY, etc. The current open
1206 scop should end before this statement. */
1209 harmful_stmt_in_bb (basic_block scop_entry, basic_block bb)
1211 gimple_stmt_iterator gsi;
1213 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1214 if (!stmt_simple_for_scop_p (scop_entry, gsi_stmt (gsi)))
1215 return gsi_stmt (gsi);
1220 /* Returns true when BB will be represented in graphite. Return false
1221 for the basic blocks that contain code eliminated in the code
1222 generation pass: i.e. induction variables and exit conditions. */
1225 graphite_stmt_p (scop_p scop, basic_block bb,
1226 VEC (data_reference_p, heap) *drs)
1228 gimple_stmt_iterator gsi;
1229 loop_p loop = bb->loop_father;
1231 if (VEC_length (data_reference_p, drs) > 0)
1234 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1236 gimple stmt = gsi_stmt (gsi);
1238 switch (gimple_code (stmt))
1240 /* Control flow expressions can be ignored, as they are
1241 represented in the iteration domains and will be
1242 regenerated by graphite. */
1250 tree var = gimple_assign_lhs (stmt);
1251 var = analyze_scalar_evolution (loop, var);
1252 var = instantiate_scev (block_before_scop (scop), loop, var);
1254 if (chrec_contains_undetermined (var))
1268 /* Store the GRAPHITE representation of BB. */
1271 new_graphite_bb (scop_p scop, basic_block bb)
1273 struct graphite_bb *gbb;
1274 VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 5);
1275 struct loop *nest = outermost_loop_in_scop (scop, bb);
1276 gimple_stmt_iterator gsi;
1278 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1279 find_data_references_in_stmt (nest, gsi_stmt (gsi), &drs);
1281 if (!graphite_stmt_p (scop, bb, drs))
1283 free_data_refs (drs);
1287 gbb = XNEW (struct graphite_bb);
1290 GBB_SCOP (gbb) = scop;
1291 GBB_DATA_REFS (gbb) = drs;
1292 GBB_DOMAIN (gbb) = NULL;
1293 GBB_CONDITIONS (gbb) = NULL;
1294 GBB_CONDITION_CASES (gbb) = NULL;
1295 GBB_LOOPS (gbb) = NULL;
1296 GBB_STATIC_SCHEDULE (gbb) = NULL;
1297 GBB_CLOOG_IV_TYPES (gbb) = NULL;
1298 VEC_safe_push (graphite_bb_p, heap, SCOP_BBS (scop), gbb);
1304 free_graphite_bb (struct graphite_bb *gbb)
1306 if (GBB_DOMAIN (gbb))
1307 cloog_matrix_free (GBB_DOMAIN (gbb));
1309 if (GBB_CLOOG_IV_TYPES (gbb))
1310 htab_delete (GBB_CLOOG_IV_TYPES (gbb));
1312 /* FIXME: free_data_refs is disabled for the moment, but should be
1315 free_data_refs (GBB_DATA_REFS (gbb)); */
1317 VEC_free (gimple, heap, GBB_CONDITIONS (gbb));
1318 VEC_free (gimple, heap, GBB_CONDITION_CASES (gbb));
1319 VEC_free (loop_p, heap, GBB_LOOPS (gbb));
1320 GBB_BB (gbb)->aux = 0;
1326 /* Structure containing the mapping between the old names and the new
1327 names used after block copy in the new loop context. */
1328 typedef struct rename_map_elt
1330 tree old_name, new_name;
1334 /* Print to stderr the element ELT. */
1337 debug_rename_elt (rename_map_elt elt)
1339 fprintf (stderr, "(");
1340 print_generic_expr (stderr, elt->old_name, 0);
1341 fprintf (stderr, ", ");
1342 print_generic_expr (stderr, elt->new_name, 0);
1343 fprintf (stderr, ")\n");
1346 /* Helper function for debug_rename_map. */
1349 debug_rename_map_1 (void **slot, void *s ATTRIBUTE_UNUSED)
1351 struct rename_map_elt *entry = (struct rename_map_elt *) *slot;
1352 debug_rename_elt (entry);
1356 /* Print to stderr all the elements of MAP. */
1359 debug_rename_map (htab_t map)
1361 htab_traverse (map, debug_rename_map_1, NULL);
1364 /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */
1366 static inline rename_map_elt
1367 new_rename_map_elt (tree old_name, tree new_name)
1371 res = XNEW (struct rename_map_elt);
1372 res->old_name = old_name;
1373 res->new_name = new_name;
1378 /* Computes a hash function for database element ELT. */
1381 rename_map_elt_info (const void *elt)
1383 return htab_hash_pointer (((const struct rename_map_elt *) elt)->old_name);
1386 /* Compares database elements E1 and E2. */
1389 eq_rename_map_elts (const void *e1, const void *e2)
1391 const struct rename_map_elt *elt1 = (const struct rename_map_elt *) e1;
1392 const struct rename_map_elt *elt2 = (const struct rename_map_elt *) e2;
1394 return (elt1->old_name == elt2->old_name);
1397 /* Returns the new name associated to OLD_NAME in MAP. */
1400 get_new_name_from_old_name (htab_t map, tree old_name)
1402 struct rename_map_elt tmp;
1405 tmp.old_name = old_name;
1406 slot = htab_find_slot (map, &tmp, NO_INSERT);
1409 return ((rename_map_elt) *slot)->new_name;
1416 /* Creates a new scop starting with ENTRY. */
1419 new_scop (edge entry, edge exit)
1421 scop_p scop = XNEW (struct scop);
1423 gcc_assert (entry && exit);
1425 SCOP_REGION (scop) = new_sese (entry, exit);
1426 SCOP_BBS (scop) = VEC_alloc (graphite_bb_p, heap, 3);
1427 SCOP_OLDIVS (scop) = VEC_alloc (name_tree, heap, 3);
1428 SCOP_LOOPS (scop) = BITMAP_ALLOC (NULL);
1429 SCOP_LOOP_NEST (scop) = VEC_alloc (loop_p, heap, 3);
1430 SCOP_ADD_PARAMS (scop) = true;
1431 SCOP_PARAMS (scop) = VEC_alloc (name_tree, heap, 3);
1432 SCOP_PROG (scop) = cloog_program_malloc ();
1433 cloog_program_set_names (SCOP_PROG (scop), cloog_names_malloc ());
1434 SCOP_LOOP2CLOOG_LOOP (scop) = htab_create (10, hash_loop_to_cloog_loop,
1435 eq_loop_to_cloog_loop,
1437 SCOP_LIVEOUT_RENAMES (scop) = htab_create (10, rename_map_elt_info,
1438 eq_rename_map_elts, free);
1445 free_scop (scop_p scop)
1449 struct graphite_bb *gb;
1452 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
1453 free_graphite_bb (gb);
1455 VEC_free (graphite_bb_p, heap, SCOP_BBS (scop));
1456 BITMAP_FREE (SCOP_LOOPS (scop));
1457 VEC_free (loop_p, heap, SCOP_LOOP_NEST (scop));
1459 for (i = 0; VEC_iterate (name_tree, SCOP_OLDIVS (scop), i, iv); i++)
1461 VEC_free (name_tree, heap, SCOP_OLDIVS (scop));
1463 for (i = 0; VEC_iterate (name_tree, SCOP_PARAMS (scop), i, p); i++)
1466 VEC_free (name_tree, heap, SCOP_PARAMS (scop));
1467 cloog_program_free (SCOP_PROG (scop));
1468 htab_delete (SCOP_LOOP2CLOOG_LOOP (scop));
1469 htab_delete (SCOP_LIVEOUT_RENAMES (scop));
1470 free_sese (SCOP_REGION (scop));
1474 /* Deletes all scops in SCOPS. */
1477 free_scops (VEC (scop_p, heap) *scops)
1482 for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++)
1485 VEC_free (scop_p, heap, scops);
1488 typedef enum gbb_type {
1490 GBB_LOOP_SING_EXIT_HEADER,
1491 GBB_LOOP_MULT_EXIT_HEADER,
1498 /* Detect the type of BB. Loop headers are only marked, if they are
1499 new. This means their loop_father is different to LAST_LOOP.
1500 Otherwise they are treated like any other bb and their type can be
1504 get_bb_type (basic_block bb, struct loop *last_loop)
1506 VEC (basic_block, heap) *dom;
1508 struct loop *loop = bb->loop_father;
1510 /* Check, if we entry into a new loop. */
1511 if (loop != last_loop)
1513 if (single_exit (loop) != NULL)
1514 return GBB_LOOP_SING_EXIT_HEADER;
1515 else if (loop->num != 0)
1516 return GBB_LOOP_MULT_EXIT_HEADER;
1518 return GBB_COND_HEADER;
1521 dom = get_dominated_by (CDI_DOMINATORS, bb);
1522 nb_dom = VEC_length (basic_block, dom);
1523 VEC_free (basic_block, heap, dom);
1528 nb_suc = VEC_length (edge, bb->succs);
1530 if (nb_dom == 1 && nb_suc == 1)
1533 return GBB_COND_HEADER;
1536 /* A SCoP detection region, defined using bbs as borders.
1537 All control flow touching this region, comes in passing basic_block ENTRY and
1538 leaves passing basic_block EXIT. By using bbs instead of edges for the
1539 borders we are able to represent also regions that do not have a single
1541 But as they have a single entry basic_block and a single exit basic_block, we
1542 are able to generate for every sd_region a single entry and exit edge.
1549 / \ This region contains: {3, 4, 5, 6, 7, 8}
1557 typedef struct sd_region_p
1559 /* The entry bb dominates all bbs in the sd_region. It is part of the
1563 /* The exit bb postdominates all bbs in the sd_region, but is not
1564 part of the region. */
1568 DEF_VEC_O(sd_region);
1569 DEF_VEC_ALLOC_O(sd_region, heap);
1572 /* Moves the scops from SOURCE to TARGET and clean up SOURCE. */
1575 move_sd_regions (VEC (sd_region, heap) **source, VEC (sd_region, heap) **target)
1580 for (i = 0; VEC_iterate (sd_region, *source, i, s); i++)
1581 VEC_safe_push (sd_region, heap, *target, s);
1583 VEC_free (sd_region, heap, *source);
1586 /* Return true when it is not possible to represent the upper bound of
1587 LOOP in the polyhedral representation. */
1590 graphite_cannot_represent_loop_niter (loop_p loop)
1592 tree niter = number_of_latch_executions (loop);
1594 return chrec_contains_undetermined (niter)
1595 || !scev_is_linear_expression (niter);
1597 /* Store information needed by scopdet_* functions. */
1601 /* Where the last open scop would stop if the current BB is harmful. */
1604 /* Where the next scop would start if the current BB is harmful. */
1607 /* The bb or one of its children contains open loop exits. That means
1608 loop exit nodes that are not surrounded by a loop dominated by bb. */
1611 /* The bb or one of its children contains only structures we can handle. */
1616 static struct scopdet_info build_scops_1 (basic_block, VEC (sd_region, heap) **,
1619 /* Calculates BB infos. If bb is difficult we add valid SCoPs dominated by BB
1620 to SCOPS. TYPE is the gbb_type of BB. */
1622 static struct scopdet_info
1623 scopdet_basic_block_info (basic_block bb, VEC (sd_region, heap) **scops,
1626 struct loop *loop = bb->loop_father;
1627 struct scopdet_info result;
1630 /* XXX: ENTRY_BLOCK_PTR could be optimized in later steps. */
1631 stmt = harmful_stmt_in_bb (ENTRY_BLOCK_PTR, bb);
1632 result.difficult = (stmt != NULL);
1639 result.exits = false;
1642 /* Mark bbs terminating a SESE region difficult, if they start
1644 if (VEC_length (edge, bb->succs) > 1)
1645 result.difficult = true;
1650 result.next = single_succ (bb);
1651 result.exits = false;
1655 case GBB_LOOP_SING_EXIT_HEADER:
1657 VEC (sd_region, heap) *tmp_scops = VEC_alloc (sd_region, heap,3);
1658 struct scopdet_info sinfo;
1660 sinfo = build_scops_1 (bb, &tmp_scops, loop);
1662 result.last = single_exit (bb->loop_father)->src;
1663 result.next = single_exit (bb->loop_father)->dest;
1665 /* If we do not dominate result.next, remove it. It's either
1666 the EXIT_BLOCK_PTR, or another bb dominates it and will
1667 call the scop detection for this bb. */
1668 if (!dominated_by_p (CDI_DOMINATORS, result.next, bb))
1671 if (result.last->loop_father != loop)
1674 if (graphite_cannot_represent_loop_niter (loop))
1675 result.difficult = true;
1677 if (sinfo.difficult)
1678 move_sd_regions (&tmp_scops, scops);
1680 VEC_free (sd_region, heap, tmp_scops);
1682 result.exits = false;
1683 result.difficult |= sinfo.difficult;
1687 case GBB_LOOP_MULT_EXIT_HEADER:
1689 /* XXX: For now we just do not join loops with multiple exits. If the
1690 exits lead to the same bb it may be possible to join the loop. */
1691 VEC (sd_region, heap) *tmp_scops = VEC_alloc (sd_region, heap, 3);
1692 VEC (edge, heap) *exits = get_loop_exit_edges (loop);
1695 build_scops_1 (bb, &tmp_scops, loop);
1697 /* Scan the code dominated by this loop. This means all bbs, that are
1698 are dominated by a bb in this loop, but are not part of this loop.
1701 - The loop exit destination is dominated by the exit sources.
1703 TODO: We miss here the more complex cases:
1704 - The exit destinations are dominated by another bb inside the
1706 - The loop dominates bbs, that are not exit destinations. */
1707 for (i = 0; VEC_iterate (edge, exits, i, e); i++)
1708 if (e->src->loop_father == loop
1709 && dominated_by_p (CDI_DOMINATORS, e->dest, e->src))
1711 /* Pass loop_outer to recognize e->dest as loop header in
1713 if (e->dest->loop_father->header == e->dest)
1714 build_scops_1 (e->dest, &tmp_scops,
1715 loop_outer (e->dest->loop_father));
1717 build_scops_1 (e->dest, &tmp_scops, e->dest->loop_father);
1722 result.difficult = true;
1723 result.exits = false;
1724 move_sd_regions (&tmp_scops, scops);
1725 VEC_free (edge, heap, exits);
1728 case GBB_COND_HEADER:
1730 VEC (sd_region, heap) *tmp_scops = VEC_alloc (sd_region, heap, 3);
1731 struct scopdet_info sinfo;
1732 VEC (basic_block, heap) *dominated;
1735 basic_block last_bb = NULL;
1737 result.exits = false;
1739 /* First check the successors of BB, and check if it is possible to join
1740 the different branches. */
1741 for (i = 0; VEC_iterate (edge, bb->succs, i, e); i++)
1743 /* Ignore loop exits. They will be handled after the loop body. */
1744 if (is_loop_exit (loop, e->dest))
1746 result.exits = true;
1750 /* Do not follow edges that lead to the end of the
1751 conditions block. For example, in
1761 the edge from 0 => 6. Only check if all paths lead to
1764 if (!single_pred_p (e->dest))
1766 /* Check, if edge leads directly to the end of this
1773 if (e->dest != last_bb)
1774 result.difficult = true;
1779 if (!dominated_by_p (CDI_DOMINATORS, e->dest, bb))
1781 result.difficult = true;
1785 sinfo = build_scops_1 (e->dest, &tmp_scops, loop);
1787 result.exits |= sinfo.exits;
1788 result.last = sinfo.last;
1789 result.difficult |= sinfo.difficult;
1791 /* Checks, if all branches end at the same point.
1792 If that is true, the condition stays joinable.
1793 Have a look at the example above. */
1794 if (sinfo.last && single_succ_p (sinfo.last))
1796 basic_block next_tmp = single_succ (sinfo.last);
1801 if (next_tmp != last_bb)
1802 result.difficult = true;
1805 result.difficult = true;
1808 /* If the condition is joinable. */
1809 if (!result.exits && !result.difficult)
1811 /* Only return a next pointer if we dominate this pointer.
1812 Otherwise it will be handled by the bb dominating it. */
1813 if (dominated_by_p (CDI_DOMINATORS, last_bb, bb) && last_bb != bb)
1814 result.next = last_bb;
1818 VEC_free (sd_region, heap, tmp_scops);
1822 /* Scan remaining bbs dominated by BB. */
1823 dominated = get_dominated_by (CDI_DOMINATORS, bb);
1825 for (i = 0; VEC_iterate (basic_block, dominated, i, dom_bb); i++)
1827 /* Ignore loop exits: they will be handled after the loop body. */
1828 if (loop_depth (find_common_loop (loop, dom_bb->loop_father))
1829 < loop_depth (loop))
1831 result.exits = true;
1835 /* Ignore the bbs processed above. */
1836 if (single_pred_p (dom_bb) && single_pred (dom_bb) == bb)
1839 if (loop_depth (loop) > loop_depth (dom_bb->loop_father))
1840 sinfo = build_scops_1 (dom_bb, &tmp_scops, loop_outer (loop));
1842 sinfo = build_scops_1 (dom_bb, &tmp_scops, loop);
1845 result.exits |= sinfo.exits;
1846 result.difficult = true;
1850 VEC_free (basic_block, heap, dominated);
1853 move_sd_regions (&tmp_scops, scops);
1865 /* Creates the SCoPs and writes entry and exit points for every SCoP. */
1867 static struct scopdet_info
1868 build_scops_1 (basic_block current, VEC (sd_region, heap) **scops, loop_p loop)
1870 bool in_scop = false;
1871 sd_region open_scop;
1872 struct scopdet_info sinfo;
1874 /* Initialize result. */
1875 struct scopdet_info result;
1876 result.exits = false;
1877 result.difficult = false;
1880 open_scop.entry = NULL;
1881 open_scop.exit = NULL;
1884 /* Loop over the dominance tree. If we meet a difficult bb, close
1885 the current SCoP. Loop and condition header start a new layer,
1886 and can only be added if all bbs in deeper layers are simple. */
1887 while (current != NULL)
1889 sinfo = scopdet_basic_block_info (current, scops, get_bb_type (current,
1892 if (!in_scop && !(sinfo.exits || sinfo.difficult))
1894 open_scop.entry = current;
1895 open_scop.exit = NULL;
1898 else if (in_scop && (sinfo.exits || sinfo.difficult))
1900 open_scop.exit = current;
1901 VEC_safe_push (sd_region, heap, *scops, &open_scop);
1905 result.difficult |= sinfo.difficult;
1906 result.exits |= sinfo.exits;
1908 current = sinfo.next;
1911 /* Try to close open_scop, if we are still in an open SCoP. */
1917 for (i = 0; VEC_iterate (edge, sinfo.last->succs, i, e); i++)
1918 if (dominated_by_p (CDI_POST_DOMINATORS, sinfo.last, e->dest))
1919 open_scop.exit = e->dest;
1921 if (!open_scop.exit && open_scop.entry != sinfo.last)
1922 open_scop.exit = sinfo.last;
1925 VEC_safe_push (sd_region, heap, *scops, &open_scop);
1929 result.last = sinfo.last;
1933 /* Checks if a bb is contained in REGION. */
1936 bb_in_sd_region (basic_block bb, sd_region *region)
1938 return dominated_by_p (CDI_DOMINATORS, bb, region->entry)
1939 && !(dominated_by_p (CDI_DOMINATORS, bb, region->exit)
1940 && !dominated_by_p (CDI_DOMINATORS, region->entry,
1944 /* Returns the single entry edge of REGION, if it does not exits NULL. */
1947 find_single_entry_edge (sd_region *region)
1953 FOR_EACH_EDGE (e, ei, region->entry->preds)
1954 if (!bb_in_sd_region (e->src, region))
1969 /* Returns the single exit edge of REGION, if it does not exits NULL. */
1972 find_single_exit_edge (sd_region *region)
1978 FOR_EACH_EDGE (e, ei, region->exit->preds)
1979 if (bb_in_sd_region (e->src, region))
1994 /* Create a single entry edge for REGION. */
1997 create_single_entry_edge (sd_region *region)
1999 if (find_single_entry_edge (region))
2002 /* There are multiple predecessors for bb_3
2015 There are two edges (1->3, 2->3), that point from outside into the region,
2016 and another one (5->3), a loop latch, lead to bb_3.
2024 | |\ (3.0 -> 3.1) = single entry edge
2033 If the loop is part of the SCoP, we have to redirect the loop latches.
2039 | | (3.0 -> 3.1) = entry edge
2048 if (region->entry->loop_father->header != region->entry
2049 || dominated_by_p (CDI_DOMINATORS,
2050 loop_latch_edge (region->entry->loop_father)->src,
2053 edge forwarder = split_block_after_labels (region->entry);
2054 region->entry = forwarder->dest;
2057 /* This case is never executed, as the loop headers seem always to have a
2058 single edge pointing from outside into the loop. */
2061 #ifdef ENABLE_CHECKING
2062 gcc_assert (find_single_entry_edge (region));
2066 /* Check if the sd_region, mentioned in EDGE, has no exit bb. */
2069 sd_region_without_exit (edge e)
2071 sd_region *r = (sd_region *) e->aux;
2074 return r->exit == NULL;
2079 /* Create a single exit edge for REGION. */
2082 create_single_exit_edge (sd_region *region)
2086 edge forwarder = NULL;
2089 if (find_single_exit_edge (region))
2092 /* We create a forwarder bb (5) for all edges leaving this region
2093 (3->5, 4->5). All other edges leading to the same bb, are moved
2094 to a new bb (6). If these edges where part of another region (2->5)
2095 we update the region->exit pointer, of this region.
2097 To identify which edge belongs to which region we depend on the e->aux
2098 pointer in every edge. It points to the region of the edge or to NULL,
2099 if the edge is not part of any region.
2101 1 2 3 4 1->5 no region, 2->5 region->exit = 5,
2102 \| |/ 3->5 region->exit = NULL, 4->5 region->exit = NULL
2107 1 2 3 4 1->6 no region, 2->6 region->exit = 6,
2108 | | \/ 3->5 no region, 4->5 no region,
2110 \| / 5->6 region->exit = 6
2113 Now there is only a single exit edge (5->6). */
2114 exit = region->exit;
2115 region->exit = NULL;
2116 forwarder = make_forwarder_block (exit, &sd_region_without_exit, NULL);
2118 /* Unmark the edges, that are no longer exit edges. */
2119 FOR_EACH_EDGE (e, ei, forwarder->src->preds)
2123 /* Mark the new exit edge. */
2124 single_succ_edge (forwarder->src)->aux = region;
2126 /* Update the exit bb of all regions, where exit edges lead to
2128 FOR_EACH_EDGE (e, ei, forwarder->dest->preds)
2130 ((sd_region *) e->aux)->exit = forwarder->dest;
2132 #ifdef ENABLE_CHECKING
2133 gcc_assert (find_single_exit_edge (region));
2137 /* Unmark the exit edges of all REGIONS.
2138 See comment in "create_single_exit_edge". */
2141 unmark_exit_edges (VEC (sd_region, heap) *regions)
2148 for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
2149 FOR_EACH_EDGE (e, ei, s->exit->preds)
2154 /* Mark the exit edges of all REGIONS.
2155 See comment in "create_single_exit_edge". */
2158 mark_exit_edges (VEC (sd_region, heap) *regions)
2165 for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
2166 FOR_EACH_EDGE (e, ei, s->exit->preds)
2167 if (bb_in_sd_region (e->src, s))
2171 /* Free and compute again all the dominators information. */
2174 recompute_all_dominators (void)
2176 mark_irreducible_loops ();
2177 free_dominance_info (CDI_DOMINATORS);
2178 free_dominance_info (CDI_POST_DOMINATORS);
2179 calculate_dominance_info (CDI_DOMINATORS);
2180 calculate_dominance_info (CDI_POST_DOMINATORS);
2183 /* Verifies properties that GRAPHITE should maintain during translation. */
2186 graphite_verify (void)
2188 #ifdef ENABLE_CHECKING
2189 verify_loop_structure ();
2190 verify_dominators (CDI_DOMINATORS);
2191 verify_dominators (CDI_POST_DOMINATORS);
2193 verify_loop_closed_ssa ();
2197 /* Create for all scop regions a single entry and a single exit edge. */
2200 create_sese_edges (VEC (sd_region, heap) *regions)
2205 for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
2206 create_single_entry_edge (s);
2208 mark_exit_edges (regions);
2210 for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
2211 create_single_exit_edge (s);
2213 unmark_exit_edges (regions);
2215 fix_loop_structure (NULL);
2217 #ifdef ENABLE_CHECKING
2218 verify_loop_structure ();
2219 verify_dominators (CDI_DOMINATORS);
2224 /* Create graphite SCoPs from an array of scop detection regions. */
2227 build_graphite_scops (VEC (sd_region, heap) *scop_regions)
2232 for (i = 0; VEC_iterate (sd_region, scop_regions, i, s); i++)
2234 edge entry = find_single_entry_edge (s);
2235 edge exit = find_single_exit_edge (s);
2236 scop_p scop = new_scop (entry, exit);
2237 VEC_safe_push (scop_p, heap, current_scops, scop);
2239 /* Are there overlapping SCoPs? */
2240 #ifdef ENABLE_CHECKING
2245 for (j = 0; VEC_iterate (sd_region, scop_regions, j, s2); j++)
2247 gcc_assert (!bb_in_sd_region (s->entry, s2));
2253 /* Find static control parts. */
2258 struct loop *loop = current_loops->tree_root;
2259 VEC (sd_region, heap) *tmp_scops = VEC_alloc (sd_region, heap, 3);
2261 build_scops_1 (single_succ (ENTRY_BLOCK_PTR), &tmp_scops, loop);
2262 create_sese_edges (tmp_scops);
2263 build_graphite_scops (tmp_scops);
2264 VEC_free (sd_region, heap, tmp_scops);
2267 /* Gather the basic blocks belonging to the SCOP. */
2270 build_scop_bbs (scop_p scop)
2272 basic_block *stack = XNEWVEC (basic_block, n_basic_blocks + 1);
2273 sbitmap visited = sbitmap_alloc (last_basic_block);
2276 sbitmap_zero (visited);
2277 stack[sp++] = SCOP_ENTRY (scop);
2281 basic_block bb = stack[--sp];
2282 int depth = loop_depth (bb->loop_father);
2283 int num = bb->loop_father->num;
2287 /* Scop's exit is not in the scop. Exclude also bbs, which are
2288 dominated by the SCoP exit. These are e.g. loop latches. */
2289 if (TEST_BIT (visited, bb->index)
2290 || dominated_by_p (CDI_DOMINATORS, bb, SCOP_EXIT (scop))
2291 /* Every block in the scop is dominated by scop's entry. */
2292 || !dominated_by_p (CDI_DOMINATORS, bb, SCOP_ENTRY (scop)))
2295 new_graphite_bb (scop, bb);
2296 SET_BIT (visited, bb->index);
2298 /* First push the blocks that have to be processed last. Note
2299 that this means that the order in which the code is organized
2300 below is important: do not reorder the following code. */
2301 FOR_EACH_EDGE (e, ei, bb->succs)
2302 if (! TEST_BIT (visited, e->dest->index)
2303 && (int) loop_depth (e->dest->loop_father) < depth)
2304 stack[sp++] = e->dest;
2306 FOR_EACH_EDGE (e, ei, bb->succs)
2307 if (! TEST_BIT (visited, e->dest->index)
2308 && (int) loop_depth (e->dest->loop_father) == depth
2309 && e->dest->loop_father->num != num)
2310 stack[sp++] = e->dest;
2312 FOR_EACH_EDGE (e, ei, bb->succs)
2313 if (! TEST_BIT (visited, e->dest->index)
2314 && (int) loop_depth (e->dest->loop_father) == depth
2315 && e->dest->loop_father->num == num
2316 && EDGE_COUNT (e->dest->preds) > 1)
2317 stack[sp++] = e->dest;
2319 FOR_EACH_EDGE (e, ei, bb->succs)
2320 if (! TEST_BIT (visited, e->dest->index)
2321 && (int) loop_depth (e->dest->loop_father) == depth
2322 && e->dest->loop_father->num == num
2323 && EDGE_COUNT (e->dest->preds) == 1)
2324 stack[sp++] = e->dest;
2326 FOR_EACH_EDGE (e, ei, bb->succs)
2327 if (! TEST_BIT (visited, e->dest->index)
2328 && (int) loop_depth (e->dest->loop_father) > depth)
2329 stack[sp++] = e->dest;
2333 sbitmap_free (visited);
2336 /* Returns the number of reduction phi nodes in LOOP. */
2339 nb_reductions_in_loop (loop_p loop)
2342 gimple_stmt_iterator gsi;
2344 for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
2346 gimple phi = gsi_stmt (gsi);
2350 if (!is_gimple_reg (PHI_RESULT (phi)))
2353 scev = analyze_scalar_evolution (loop, PHI_RESULT (phi));
2354 scev = instantiate_parameters (loop, scev);
2355 if (!simple_iv (loop, phi, PHI_RESULT (phi), &iv, true))
2362 /* A LOOP is in normal form when it contains only one scalar phi node
2363 that defines the main induction variable of the loop, only one
2364 increment of the IV, and only one exit condition. */
2367 graphite_loop_normal_form (loop_p loop)
2369 struct tree_niter_desc niter;
2372 edge exit = single_dom_exit (loop);
2374 gcc_assert (number_of_iterations_exit (loop, exit, &niter, false));
2375 nit = force_gimple_operand (unshare_expr (niter.niter), &stmts, true,
2378 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
2380 /* One IV per loop. */
2381 if (nb_reductions_in_loop (loop) > 0)
2384 return canonicalize_loop_ivs (loop, NULL, nit);
2387 /* Record LOOP as occuring in SCOP. Returns true when the operation
2391 scop_record_loop (scop_p scop, loop_p loop)
2396 if (bitmap_bit_p (SCOP_LOOPS (scop), loop->num))
2399 bitmap_set_bit (SCOP_LOOPS (scop), loop->num);
2400 VEC_safe_push (loop_p, heap, SCOP_LOOP_NEST (scop), loop);
2402 induction_var = graphite_loop_normal_form (loop);
2406 oldiv = XNEW (struct name_tree);
2407 oldiv->t = induction_var;
2408 oldiv->name = get_name (SSA_NAME_VAR (oldiv->t));
2410 VEC_safe_push (name_tree, heap, SCOP_OLDIVS (scop), oldiv);
2414 /* Build the loop nests contained in SCOP. Returns true when the
2415 operation was successful. */
2418 build_scop_loop_nests (scop_p scop)
2422 struct loop *loop0, *loop1;
2425 if (bb_in_sese_p (bb, SCOP_REGION (scop)))
2427 struct loop *loop = bb->loop_father;
2429 /* Only add loops if they are completely contained in the SCoP. */
2430 if (loop->header == bb
2431 && bb_in_sese_p (loop->latch, SCOP_REGION (scop)))
2433 if (!scop_record_loop (scop, loop))
2438 /* Make sure that the loops in the SCOP_LOOP_NEST are ordered. It
2439 can be the case that an inner loop is inserted before an outer
2440 loop. To avoid this, semi-sort once. */
2441 for (i = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), i, loop0); i++)
2443 if (VEC_length (loop_p, SCOP_LOOP_NEST (scop)) == i + 1)
2446 loop1 = VEC_index (loop_p, SCOP_LOOP_NEST (scop), i + 1);
2447 if (loop0->num > loop1->num)
2449 VEC_replace (loop_p, SCOP_LOOP_NEST (scop), i, loop1);
2450 VEC_replace (loop_p, SCOP_LOOP_NEST (scop), i + 1, loop0);
2457 /* Calculate the number of loops around LOOP in the SCOP. */
2460 nb_loops_around_loop_in_scop (struct loop *l, scop_p scop)
2464 for (; loop_in_sese_p (l, SCOP_REGION (scop)); d++, l = loop_outer (l));
2469 /* Calculate the number of loops around GB in the current SCOP. */
2472 nb_loops_around_gb (graphite_bb_p gb)
2474 return nb_loops_around_loop_in_scop (gbb_loop (gb), GBB_SCOP (gb));
2477 /* Returns the dimensionality of an enclosing loop iteration domain
2478 with respect to enclosing SCoP for a given data reference REF. The
2479 returned dimensionality is homogeneous (depth of loop nest + number
2480 of SCoP parameters + const). */
2483 ref_nb_loops (data_reference_p ref)
2485 loop_p loop = loop_containing_stmt (DR_STMT (ref));
2486 scop_p scop = DR_SCOP (ref);
2488 return nb_loops_around_loop_in_scop (loop, scop) + scop_nb_params (scop) + 2;
2491 /* Build dynamic schedules for all the BBs. */
2494 build_scop_dynamic_schedules (scop_p scop)
2496 int i, dim, loop_num, row, col;
2499 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
2501 loop_num = GBB_BB (gb)->loop_father->num;
2505 dim = nb_loops_around_gb (gb);
2506 GBB_DYNAMIC_SCHEDULE (gb) = cloog_matrix_alloc (dim, dim);
2508 for (row = 0; row < GBB_DYNAMIC_SCHEDULE (gb)->NbRows; row++)
2509 for (col = 0; col < GBB_DYNAMIC_SCHEDULE (gb)->NbColumns; col++)
2511 value_set_si (GBB_DYNAMIC_SCHEDULE (gb)->p[row][col], 1);
2513 value_set_si (GBB_DYNAMIC_SCHEDULE (gb)->p[row][col], 0);
2516 GBB_DYNAMIC_SCHEDULE (gb) = NULL;
2520 /* Returns the number of loops that are identical at the beginning of
2521 the vectors A and B. */
2524 compare_prefix_loops (VEC (loop_p, heap) *a, VEC (loop_p, heap) *b)
2533 lb = VEC_length (loop_p, b);
2535 for (i = 0; VEC_iterate (loop_p, a, i, ea); i++)
2537 || ea != VEC_index (loop_p, b, i))
2543 /* Build for BB the static schedule.
2545 The STATIC_SCHEDULE is defined like this:
2564 Static schedules for A to F:
2577 build_scop_canonical_schedules (scop_p scop)
2581 int nb_loops = scop_nb_loops (scop);
2582 lambda_vector static_schedule = lambda_vector_new (nb_loops + 1);
2583 VEC (loop_p, heap) *loops_previous = NULL;
2585 /* We have to start schedules at 0 on the first component and
2586 because we cannot compare_prefix_loops against a previous loop,
2587 prefix will be equal to zero, and that index will be
2588 incremented before copying. */
2589 static_schedule[0] = -1;
2591 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
2593 int prefix = compare_prefix_loops (loops_previous, GBB_LOOPS (gb));
2594 int nb = gbb_nb_loops (gb);
2596 loops_previous = GBB_LOOPS (gb);
2597 memset (&(static_schedule[prefix + 1]), 0, sizeof (int) * (nb_loops - prefix));
2598 ++static_schedule[prefix];
2599 GBB_STATIC_SCHEDULE (gb) = lambda_vector_new (nb + 1);
2600 lambda_vector_copy (static_schedule,
2601 GBB_STATIC_SCHEDULE (gb), nb + 1);
2605 /* Build the LOOPS vector for all bbs in SCOP. */
2608 build_bb_loops (scop_p scop)
2613 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
2618 depth = nb_loops_around_gb (gb) - 1;
2620 GBB_LOOPS (gb) = VEC_alloc (loop_p, heap, 3);
2621 VEC_safe_grow_cleared (loop_p, heap, GBB_LOOPS (gb), depth + 1);
2623 loop = GBB_BB (gb)->loop_father;
2625 while (scop_contains_loop (scop, loop))
2627 VEC_replace (loop_p, GBB_LOOPS (gb), depth, loop);
2628 loop = loop_outer (loop);
2634 /* Get the index for parameter VAR in SCOP. */
2637 param_index (tree var, scop_p scop)
2643 gcc_assert (TREE_CODE (var) == SSA_NAME);
2645 for (i = 0; VEC_iterate (name_tree, SCOP_PARAMS (scop), i, p); i++)
2649 gcc_assert (SCOP_ADD_PARAMS (scop));
2651 nvar = XNEW (struct name_tree);
2654 VEC_safe_push (name_tree, heap, SCOP_PARAMS (scop), nvar);
2655 return VEC_length (name_tree, SCOP_PARAMS (scop)) - 1;
2658 /* Scan EXPR and translate it to an inequality vector INEQ that will
2659 be added, or subtracted, in the constraint domain matrix C at row
2660 R. K is the number of columns for loop iterators in C. */
2663 scan_tree_for_params (scop_p s, tree e, CloogMatrix *c, int r, Value k,
2666 int cst_col, param_col;
2668 if (e == chrec_dont_know)
2671 switch (TREE_CODE (e))
2673 case POLYNOMIAL_CHREC:
2675 tree left = CHREC_LEFT (e);
2676 tree right = CHREC_RIGHT (e);
2677 int var = CHREC_VARIABLE (e);
2679 if (TREE_CODE (right) != INTEGER_CST)
2684 int loop_col = scop_gimple_loop_depth (s, get_loop (var)) + 1;
2687 value_sub_int (c->p[r][loop_col], c->p[r][loop_col],
2688 int_cst_value (right));
2690 value_add_int (c->p[r][loop_col], c->p[r][loop_col],
2691 int_cst_value (right));
2694 switch (TREE_CODE (left))
2696 case POLYNOMIAL_CHREC:
2697 scan_tree_for_params (s, left, c, r, k, subtract);
2701 /* Constant part. */
2704 int v = int_cst_value (left);
2705 cst_col = c->NbColumns - 1;
2710 subtract = subtract ? false : true;
2714 value_sub_int (c->p[r][cst_col], c->p[r][cst_col], v);
2716 value_add_int (c->p[r][cst_col], c->p[r][cst_col], v);
2721 scan_tree_for_params (s, left, c, r, k, subtract);
2728 if (chrec_contains_symbols (TREE_OPERAND (e, 0)))
2733 gcc_assert (host_integerp (TREE_OPERAND (e, 1), 0));
2735 value_set_si (val, int_cst_value (TREE_OPERAND (e, 1)));
2736 value_multiply (k, k, val);
2739 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
2746 gcc_assert (host_integerp (TREE_OPERAND (e, 0), 0));
2748 value_set_si (val, int_cst_value (TREE_OPERAND (e, 0)));
2749 value_multiply (k, k, val);
2752 scan_tree_for_params (s, TREE_OPERAND (e, 1), c, r, k, subtract);
2757 case POINTER_PLUS_EXPR:
2758 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
2759 scan_tree_for_params (s, TREE_OPERAND (e, 1), c, r, k, subtract);
2763 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
2764 scan_tree_for_params (s, TREE_OPERAND (e, 1), c, r, k, !subtract);
2768 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, !subtract);
2772 param_col = param_index (e, s);
2776 param_col += c->NbColumns - scop_nb_params (s) - 1;
2779 value_subtract (c->p[r][param_col], c->p[r][param_col], k);
2781 value_addto (c->p[r][param_col], c->p[r][param_col], k);
2788 int v = int_cst_value (e);
2789 cst_col = c->NbColumns - 1;
2794 subtract = subtract ? false : true;
2798 value_sub_int (c->p[r][cst_col], c->p[r][cst_col], v);
2800 value_add_int (c->p[r][cst_col], c->p[r][cst_col], v);
2805 case NON_LVALUE_EXPR:
2806 scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
2815 /* Data structure for idx_record_params. */
2823 /* For a data reference with an ARRAY_REF as its BASE, record the
2824 parameters occurring in IDX. DTA is passed in as complementary
2825 information, and is used by the automatic walker function. This
2826 function is a callback for for_each_index. */
2829 idx_record_params (tree base, tree *idx, void *dta)
2831 struct irp_data *data = (struct irp_data *) dta;
2833 if (TREE_CODE (base) != ARRAY_REF)
2836 if (TREE_CODE (*idx) == SSA_NAME)
2839 scop_p scop = data->scop;
2840 struct loop *loop = data->loop;
2843 scev = analyze_scalar_evolution (loop, *idx);
2844 scev = instantiate_scev (block_before_scop (scop), loop, scev);
2847 value_set_si (one, 1);
2848 scan_tree_for_params (scop, scev, NULL, 0, one, false);
2855 /* Find parameters with respect to SCOP in BB. We are looking in memory
2856 access functions, conditions and loop bounds. */
2859 find_params_in_bb (scop_p scop, graphite_bb_p gb)
2862 data_reference_p dr;
2864 loop_p father = GBB_BB (gb)->loop_father;
2866 for (i = 0; VEC_iterate (data_reference_p, GBB_DATA_REFS (gb), i, dr); i++)
2868 struct irp_data irp;
2872 for_each_index (&dr->ref, idx_record_params, &irp);
2875 /* Find parameters in conditional statements. */
2876 for (i = 0; VEC_iterate (gimple, GBB_CONDITIONS (gb), i, stmt); i++)
2879 loop_p loop = father;
2883 lhs = gimple_cond_lhs (stmt);
2884 lhs = analyze_scalar_evolution (loop, lhs);
2885 lhs = instantiate_scev (block_before_scop (scop), loop, lhs);
2887 rhs = gimple_cond_rhs (stmt);
2888 rhs = analyze_scalar_evolution (loop, rhs);
2889 rhs = instantiate_scev (block_before_scop (scop), loop, rhs);
2892 scan_tree_for_params (scop, lhs, NULL, 0, one, false);
2893 value_set_si (one, 1);
2894 scan_tree_for_params (scop, rhs, NULL, 0, one, false);
2899 /* Saves in NV the name of variable P->T. */
2902 save_var_name (char **nv, int i, name_tree p)
2904 const char *name = get_name (SSA_NAME_VAR (p->t));
2908 int len = strlen (name) + 16;
2909 nv[i] = XNEWVEC (char, len);
2910 snprintf (nv[i], len, "%s_%d", name, SSA_NAME_VERSION (p->t));
2914 nv[i] = XNEWVEC (char, 16);
2915 snprintf (nv[i], 2 + 16, "T_%d", SSA_NAME_VERSION (p->t));
2921 /* Return the maximal loop depth in SCOP. */
2924 scop_max_loop_depth (scop_p scop)
2928 int max_nb_loops = 0;
2930 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gbb); i++)
2932 int nb_loops = gbb_nb_loops (gbb);
2933 if (max_nb_loops < nb_loops)
2934 max_nb_loops = nb_loops;
2937 return max_nb_loops;
2940 /* Initialize Cloog's parameter names from the names used in GIMPLE.
2941 Initialize Cloog's iterator names, using 'graphite_iterator_%d'
2942 from 0 to scop_nb_loops (scop). */
2945 initialize_cloog_names (scop_p scop)
2947 int i, nb_params = VEC_length (name_tree, SCOP_PARAMS (scop));
2948 char **params = XNEWVEC (char *, nb_params);
2949 int nb_iterators = scop_max_loop_depth (scop);
2950 int nb_scattering= cloog_program_nb_scattdims (SCOP_PROG (scop));
2951 char **iterators = XNEWVEC (char *, nb_iterators * 2);
2952 char **scattering = XNEWVEC (char *, nb_scattering);
2955 for (i = 0; VEC_iterate (name_tree, SCOP_PARAMS (scop), i, p); i++)
2956 save_var_name (params, i, p);
2958 cloog_names_set_nb_parameters (cloog_program_names (SCOP_PROG (scop)),
2960 cloog_names_set_parameters (cloog_program_names (SCOP_PROG (scop)),
2963 for (i = 0; i < nb_iterators; i++)
2966 iterators[i] = XNEWVEC (char, len);
2967 snprintf (iterators[i], len, "graphite_iterator_%d", i);
2970 cloog_names_set_nb_iterators (cloog_program_names (SCOP_PROG (scop)),
2972 cloog_names_set_iterators (cloog_program_names (SCOP_PROG (scop)),
2975 for (i = 0; i < nb_scattering; i++)
2978 scattering[i] = XNEWVEC (char, len);
2979 snprintf (scattering[i], len, "s_%d", i);
2982 cloog_names_set_nb_scattering (cloog_program_names (SCOP_PROG (scop)),
2984 cloog_names_set_scattering (cloog_program_names (SCOP_PROG (scop)),
2988 /* Record the parameters used in the SCOP. A variable is a parameter
2989 in a scop if it does not vary during the execution of that scop. */
2992 find_scop_parameters (scop_p scop)
3000 value_set_si (one, 1);
3002 /* Find the parameters used in the loop bounds. */
3003 for (i = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), i, loop); i++)
3005 tree nb_iters = number_of_latch_executions (loop);
3007 if (!chrec_contains_symbols (nb_iters))
3010 nb_iters = analyze_scalar_evolution (loop, nb_iters);
3011 nb_iters = instantiate_scev (block_before_scop (scop), loop, nb_iters);
3012 scan_tree_for_params (scop, nb_iters, NULL, 0, one, false);
3017 /* Find the parameters used in data accesses. */
3018 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
3019 find_params_in_bb (scop, gb);
3021 SCOP_ADD_PARAMS (scop) = false;
3024 /* Build the context constraints for SCOP: constraints and relations
3028 build_scop_context (scop_p scop)
3030 int nb_params = scop_nb_params (scop);
3031 CloogMatrix *matrix = cloog_matrix_alloc (1, nb_params + 2);
3033 /* Insert '0 >= 0' in the context matrix, as it is not allowed to be
3036 value_set_si (matrix->p[0][0], 1);
3038 value_set_si (matrix->p[0][nb_params + 1], 0);
3040 cloog_program_set_context (SCOP_PROG (scop),
3041 cloog_domain_matrix2domain (matrix));
3042 cloog_matrix_free (matrix);
3045 /* Returns a graphite_bb from BB. */
3047 static inline graphite_bb_p
3048 gbb_from_bb (basic_block bb)
3050 return (graphite_bb_p) bb->aux;
3053 /* Builds the constraint matrix for LOOP in SCOP. NB_OUTER_LOOPS is the
3054 number of loops surrounding LOOP in SCOP. OUTER_CSTR gives the
3055 constraints matrix for the surrounding loops. */
3058 build_loop_iteration_domains (scop_p scop, struct loop *loop,
3059 CloogMatrix *outer_cstr, int nb_outer_loops)
3065 int nb_rows = outer_cstr->NbRows + 1;
3066 int nb_cols = outer_cstr->NbColumns + 1;
3068 /* Last column of CSTR is the column of constants. */
3069 int cst_col = nb_cols - 1;
3071 /* The column for the current loop is just after the columns of
3072 other outer loops. */
3073 int loop_col = nb_outer_loops + 1;
3075 tree nb_iters = number_of_latch_executions (loop);
3077 /* When the number of iterations is a constant or a parameter, we
3078 add a constraint for the upper bound of the loop. So add a row
3079 to the constraint matrix before allocating it. */
3080 if (TREE_CODE (nb_iters) == INTEGER_CST
3081 || !chrec_contains_undetermined (nb_iters))
3084 cstr = cloog_matrix_alloc (nb_rows, nb_cols);
3086 /* Copy the outer constraints. */
3087 for (i = 0; i < outer_cstr->NbRows; i++)
3089 /* Copy the eq/ineq and loops columns. */
3090 for (j = 0; j < loop_col; j++)
3091 value_assign (cstr->p[i][j], outer_cstr->p[i][j]);
3093 /* Leave an empty column in CSTR for the current loop, and then
3094 copy the parameter columns. */
3095 for (j = loop_col; j < outer_cstr->NbColumns; j++)
3096 value_assign (cstr->p[i][j + 1], outer_cstr->p[i][j]);
3100 row = outer_cstr->NbRows;
3101 value_set_si (cstr->p[row][0], 1);
3102 value_set_si (cstr->p[row][loop_col], 1);
3104 /* loop_i <= nb_iters */
3105 if (TREE_CODE (nb_iters) == INTEGER_CST)
3108 value_set_si (cstr->p[row][0], 1);
3109 value_set_si (cstr->p[row][loop_col], -1);
3111 value_set_si (cstr->p[row][cst_col],
3112 int_cst_value (nb_iters));
3114 else if (!chrec_contains_undetermined (nb_iters))
3116 /* Otherwise nb_iters contains parameters: scan the nb_iters
3117 expression and build its matrix representation. */
3121 value_set_si (cstr->p[row][0], 1);
3122 value_set_si (cstr->p[row][loop_col], -1);
3124 nb_iters = analyze_scalar_evolution (loop, nb_iters);
3125 nb_iters = instantiate_scev (block_before_scop (scop), loop, nb_iters);
3128 value_set_si (one, 1);
3129 scan_tree_for_params (scop, nb_iters, cstr, row, one, false);
3135 if (loop->inner && loop_in_sese_p (loop->inner, SCOP_REGION (scop)))
3136 build_loop_iteration_domains (scop, loop->inner, cstr, nb_outer_loops + 1);
3138 /* Only go to the next loops, if we are not at the outermost layer. These
3139 have to be handled seperately, as we can be sure, that the chain at this
3140 layer will be connected. */
3141 if (nb_outer_loops != 0 && loop->next && loop_in_sese_p (loop->next,
3142 SCOP_REGION (scop)))
3143 build_loop_iteration_domains (scop, loop->next, outer_cstr, nb_outer_loops);
3145 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
3146 if (gbb_loop (gb) == loop)
3147 GBB_DOMAIN (gb) = cloog_matrix_copy (cstr);
3149 cloog_matrix_free (cstr);
3152 /* Add conditions to the domain of GB. */
3155 add_conditions_to_domain (graphite_bb_p gb)
3159 VEC (gimple, heap) *conditions = GBB_CONDITIONS (gb);
3160 CloogMatrix *domain = GBB_DOMAIN (gb);
3161 scop_p scop = GBB_SCOP (gb);
3165 unsigned nb_new_rows = 0;
3168 if (VEC_empty (gimple, conditions))
3173 nb_rows = domain->NbRows;
3174 nb_cols = domain->NbColumns;
3179 nb_cols = nb_loops_around_gb (gb) + scop_nb_params (scop) + 2;
3182 /* Count number of necessary new rows to add the conditions to the
3184 for (i = 0; VEC_iterate (gimple, conditions, i, stmt); i++)
3186 switch (gimple_code (stmt))
3190 enum tree_code code = gimple_cond_code (stmt);
3196 /* NE and EQ statements are not supported right know. */
3212 /* Switch statements are not supported right know. */
3223 /* Enlarge the matrix. */
3225 CloogMatrix *new_domain;
3226 new_domain = cloog_matrix_alloc (nb_rows + nb_new_rows, nb_cols);
3230 for (i = 0; i < nb_rows; i++)
3231 for (j = 0; j < nb_cols; j++)
3232 value_assign (new_domain->p[i][j], domain->p[i][j]);
3234 cloog_matrix_free (domain);
3237 domain = new_domain;
3238 GBB_DOMAIN (gb) = new_domain;
3241 /* Add the conditions to the new enlarged domain matrix. */
3243 for (i = 0; VEC_iterate (gimple, conditions, i, stmt); i++)
3245 switch (gimple_code (stmt))
3250 enum tree_code code;
3253 loop_p loop = GBB_BB (gb)->loop_father;
3255 left = gimple_cond_lhs (stmt);
3256 right = gimple_cond_rhs (stmt);
3258 left = analyze_scalar_evolution (loop, left);
3259 right = analyze_scalar_evolution (loop, right);
3261 left = instantiate_scev (block_before_scop (scop), loop, left);
3262 right = instantiate_scev (block_before_scop (scop), loop, right);
3264 code = gimple_cond_code (stmt);
3266 /* The conditions for ELSE-branches are inverted. */
3267 if (VEC_index (gimple, gb->condition_cases, i) == NULL)
3268 code = invert_tree_comparison (code, false);
3273 /* NE statements are not supported right know. */
3277 value_set_si (domain->p[row][0], 1);
3279 value_set_si (one, 1);
3280 scan_tree_for_params (scop, left, domain, row, one, true);
3281 value_set_si (one, 1);
3282 scan_tree_for_params (scop, right, domain, row, one, false);
3284 value_set_si (domain->p[row][0], 1);
3285 value_set_si (one, 1);
3286 scan_tree_for_params (scop, left, domain, row, one, false);
3287 value_set_si (one, 1);
3288 scan_tree_for_params (scop, right, domain, row, one, true);
3293 value_set_si (domain->p[row][0], 1);
3295 value_set_si (one, 1);
3296 scan_tree_for_params (scop, left, domain, row, one, true);
3297 value_set_si (one, 1);
3298 scan_tree_for_params (scop, right, domain, row, one, false);
3299 value_sub_int (domain->p[row][nb_cols - 1],
3300 domain->p[row][nb_cols - 1], 1);
3305 value_set_si (domain->p[row][0], 1);
3307 value_set_si (one, 1);
3308 scan_tree_for_params (scop, left, domain, row, one, false);
3309 value_set_si (one, 1);
3310 scan_tree_for_params (scop, right, domain, row, one, true);
3311 value_sub_int (domain->p[row][nb_cols - 1],
3312 domain->p[row][nb_cols - 1], 1);
3317 value_set_si (domain->p[row][0], 1);
3319 value_set_si (one, 1);
3320 scan_tree_for_params (scop, left, domain, row, one, true);
3321 value_set_si (one, 1);
3322 scan_tree_for_params (scop, right, domain, row, one, false);
3327 value_set_si (domain->p[row][0], 1);
3329 value_set_si (one, 1);
3330 scan_tree_for_params (scop, left, domain, row, one, false);
3331 value_set_si (one, 1);
3332 scan_tree_for_params (scop, right, domain, row, one, true);
3343 /* Switch statements are not supported right know. */
3354 /* Returns true when PHI defines an induction variable in the loop
3355 containing the PHI node. */
3358 phi_node_is_iv (gimple phi)
3360 loop_p loop = gimple_bb (phi)->loop_father;
3361 tree scev = analyze_scalar_evolution (loop, gimple_phi_result (phi));
3363 return tree_contains_chrecs (scev, NULL);
3366 /* Returns true when BB contains scalar phi nodes that are not an
3367 induction variable of a loop. */
3370 bb_contains_non_iv_scalar_phi_nodes (basic_block bb)
3373 gimple_stmt_iterator si;
3375 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
3376 if (is_gimple_reg (gimple_phi_result (gsi_stmt (si))))
3378 /* Store the unique scalar PHI node: at this point, loops
3379 should be in cannonical form, so we expect to see at most
3380 one scalar phi node in the loop header. */
3382 || bb != bb->loop_father->header)
3385 phi = gsi_stmt (si);
3389 || phi_node_is_iv (phi))
3395 /* Helper recursive function. Record in CONDITIONS and CASES all
3396 conditions from 'if's and 'switch'es occurring in BB from SCOP.
3398 Returns false when the conditions contain scalar computations that
3399 depend on the condition, i.e. when there are scalar phi nodes on
3400 the junction after the condition. Only the computations occurring
3401 on memory can be handled in the polyhedral model: operations that
3402 define scalar evolutions in conditions, that can potentially be
3403 used to index memory, can't be handled by the polyhedral model. */
3406 build_scop_conditions_1 (VEC (gimple, heap) **conditions,
3407 VEC (gimple, heap) **cases, basic_block bb,
3413 gimple_stmt_iterator gsi;
3414 basic_block bb_child, bb_iter;
3415 VEC (basic_block, heap) *dom;
3417 /* Make sure we are in the SCoP. */
3418 if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
3421 if (bb_contains_non_iv_scalar_phi_nodes (bb))
3424 gbb = gbb_from_bb (bb);
3427 GBB_CONDITIONS (gbb) = VEC_copy (gimple, heap, *conditions);
3428 GBB_CONDITION_CASES (gbb) = VEC_copy (gimple, heap, *cases);
3431 dom = get_dominated_by (CDI_DOMINATORS, bb);
3433 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3435 gimple stmt = gsi_stmt (gsi);
3436 VEC (edge, gc) *edges;
3439 switch (gimple_code (stmt))
3443 for (i = 0; VEC_iterate (edge, edges, i, e); i++)
3444 if ((dominated_by_p (CDI_DOMINATORS, e->dest, bb))
3445 && VEC_length (edge, e->dest->preds) == 1)
3447 /* Remove the scanned block from the dominator successors. */
3448 for (j = 0; VEC_iterate (basic_block, dom, j, bb_iter); j++)
3449 if (bb_iter == e->dest)
3451 VEC_unordered_remove (basic_block, dom, j);
3455 /* Recursively scan the then or else part. */
3456 if (e->flags & EDGE_TRUE_VALUE)
3457 VEC_safe_push (gimple, heap, *cases, stmt);
3460 gcc_assert (e->flags & EDGE_FALSE_VALUE);
3461 VEC_safe_push (gimple, heap, *cases, NULL);
3464 VEC_safe_push (gimple, heap, *conditions, stmt);
3465 if (!build_scop_conditions_1 (conditions, cases, e->dest, scop))
3470 VEC_pop (gimple, *conditions);
3471 VEC_pop (gimple, *cases);
3478 gimple_stmt_iterator gsi_search_gimple_label;
3480 for (i = 0; i < gimple_switch_num_labels (stmt); ++i)
3482 basic_block bb_iter;
3484 size_t n_cases = VEC_length (gimple, *conditions);
3485 unsigned n = gimple_switch_num_labels (stmt);
3487 bb_child = label_to_block
3488 (CASE_LABEL (gimple_switch_label (stmt, i)));
3490 for (k = 0; k < n; k++)
3493 (CASE_LABEL (gimple_switch_label (stmt, k))) == bb_child)
3496 /* Switches with multiple case values for the same
3497 block are not handled. */
3499 /* Switch cases with more than one predecessor are
3501 || VEC_length (edge, bb_child->preds) != 1)
3507 /* Recursively scan the corresponding 'case' block. */
3508 for (gsi_search_gimple_label = gsi_start_bb (bb_child);
3509 !gsi_end_p (gsi_search_gimple_label);
3510 gsi_next (&gsi_search_gimple_label))
3512 gimple label = gsi_stmt (gsi_search_gimple_label);
3514 if (gimple_code (label) == GIMPLE_LABEL)
3516 tree t = gimple_label_label (label);
3518 gcc_assert (t == gimple_switch_label (stmt, i));
3519 VEC_replace (gimple, *cases, n_cases, label);
3524 if (!build_scop_conditions_1 (conditions, cases, bb_child, scop))
3530 /* Remove the scanned block from the dominator successors. */
3531 for (j = 0; VEC_iterate (basic_block, dom, j, bb_iter); j++)
3532 if (bb_iter == bb_child)
3534 VEC_unordered_remove (basic_block, dom, j);
3539 VEC_pop (gimple, *conditions);
3540 VEC_pop (gimple, *cases);
3549 /* Scan all immediate dominated successors. */
3550 for (i = 0; VEC_iterate (basic_block, dom, i, bb_child); i++)
3551 if (!build_scop_conditions_1 (conditions, cases, bb_child, scop))
3558 VEC_free (basic_block, heap, dom);
3562 /* Record all conditions from SCOP.
3564 Returns false when the conditions contain scalar computations that
3565 depend on the condition, i.e. when there are scalar phi nodes on
3566 the junction after the condition. Only the computations occurring
3567 on memory can be handled in the polyhedral model: operations that
3568 define scalar evolutions in conditions, that can potentially be
3569 used to index memory, can't be handled by the polyhedral model. */
3572 build_scop_conditions (scop_p scop)
3575 VEC (gimple, heap) *conditions = NULL;
3576 VEC (gimple, heap) *cases = NULL;
3578 res = build_scop_conditions_1 (&conditions, &cases, SCOP_ENTRY (scop), scop);
3580 VEC_free (gimple, heap, conditions);
3581 VEC_free (gimple, heap, cases);
3585 /* Traverses all the GBBs of the SCOP and add their constraints to the
3586 iteration domains. */
3589 add_conditions_to_constraints (scop_p scop)
3594 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gbb); i++)
3595 add_conditions_to_domain (gbb);
3598 /* Build the current domain matrix: the loops belonging to the current
3599 SCOP, and that vary for the execution of the current basic block.
3600 Returns false if there is no loop in SCOP. */
3603 build_scop_iteration_domain (scop_p scop)
3606 CloogMatrix *outer_cstr;
3609 /* Build cloog loop for all loops, that are in the uppermost loop layer of
3611 for (i = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), i, loop); i++)
3612 if (!loop_in_sese_p (loop_outer (loop), SCOP_REGION (scop)))
3614 /* The outermost constraints is a matrix that has:
3615 -first column: eq/ineq boolean
3616 -last column: a constant
3617 -scop_nb_params columns for the parameters used in the scop. */
3618 outer_cstr = cloog_matrix_alloc (0, scop_nb_params (scop) + 2);
3619 build_loop_iteration_domains (scop, loop, outer_cstr, 0);
3620 cloog_matrix_free (outer_cstr);
3626 /* Initializes an equation CY of the access matrix using the
3627 information for a subscript from AF, relatively to the loop
3628 indexes from LOOP_NEST and parameter indexes from PARAMS. NDIM is
3629 the dimension of the array access, i.e. the number of
3630 subscripts. Returns true when the operation succeeds. */
3633 build_access_matrix_with_af (tree af, lambda_vector cy,
3634 scop_p scop, int ndim)
3638 switch (TREE_CODE (af))
3640 case POLYNOMIAL_CHREC:
3642 struct loop *outer_loop;
3643 tree left = CHREC_LEFT (af);
3644 tree right = CHREC_RIGHT (af);
3647 if (TREE_CODE (right) != INTEGER_CST)
3650 outer_loop = get_loop (CHREC_VARIABLE (af));
3651 var = nb_loops_around_loop_in_scop (outer_loop, scop);
3652 cy[var] = int_cst_value (right);
3654 switch (TREE_CODE (left))
3656 case POLYNOMIAL_CHREC:
3657 return build_access_matrix_with_af (left, cy, scop, ndim);
3660 cy[ndim - 1] = int_cst_value (left);
3664 return build_access_matrix_with_af (left, cy, scop, ndim);
3669 build_access_matrix_with_af (TREE_OPERAND (af, 0), cy, scop, ndim);
3670 build_access_matrix_with_af (TREE_OPERAND (af, 1), cy, scop, ndim);
3674 build_access_matrix_with_af (TREE_OPERAND (af, 0), cy, scop, ndim);
3675 build_access_matrix_with_af (TREE_OPERAND (af, 1), cy, scop, ndim);
3679 cy[ndim - 1] = int_cst_value (af);
3683 param_col = param_index (af, scop);
3684 cy [ndim - scop_nb_params (scop) + param_col - 1] = 1;
3688 /* FIXME: access_fn can have parameters. */
3693 /* Initialize the access matrix in the data reference REF with respect
3694 to the loop nesting LOOP_NEST. Return true when the operation
3698 build_access_matrix (data_reference_p ref, graphite_bb_p gb)
3700 int i, ndim = DR_NUM_DIMENSIONS (ref);
3701 struct access_matrix *am = GGC_NEW (struct access_matrix);
3703 AM_MATRIX (am) = VEC_alloc (lambda_vector, gc, ndim);
3704 DR_SCOP (ref) = GBB_SCOP (gb);
3706 for (i = 0; i < ndim; i++)
3708 lambda_vector v = lambda_vector_new (ref_nb_loops (ref));
3709 scop_p scop = GBB_SCOP (gb);
3710 tree af = DR_ACCESS_FN (ref, i);
3712 if (!build_access_matrix_with_af (af, v, scop, ref_nb_loops (ref)))
3715 VEC_quick_push (lambda_vector, AM_MATRIX (am), v);
3718 DR_ACCESS_MATRIX (ref) = am;
3722 /* Build the access matrices for the data references in the SCOP. */
3725 build_scop_data_accesses (scop_p scop)
3730 /* FIXME: Construction of access matrix is disabled until some
3731 pass, like the data dependence analysis, is using it. */
3734 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
3737 data_reference_p dr;
3739 /* Construct the access matrix for each data ref, with respect to
3740 the loop nest of the current BB in the considered SCOP. */
3742 VEC_iterate (data_reference_p, GBB_DATA_REFS (gb), j, dr);
3745 bool res = build_access_matrix (dr, gb);
3747 /* FIXME: At this point the DRs should always have an affine
3748 form. For the moment this fails as build_access_matrix
3749 does not build matrices with parameters. */
3755 /* Returns the tree variable from the name NAME that was given in
3756 Cloog representation. All the parameters are stored in PARAMS, and
3757 all the loop induction variables are stored in IVSTACK.
3759 FIXME: This is a hack, and Cloog should be fixed to not work with
3760 variable names represented as "char *string", but with void
3761 pointers that could be casted back to a tree. The only problem in
3762 doing that is that Cloog's pretty printer still assumes that
3763 variable names are char *strings. The solution would be to have a
3764 function pointer for pretty-printing that can be redirected to be
3765 print_generic_stmt in our case, or fprintf by default.
3766 ??? Too ugly to live. */
3769 clast_name_to_gcc (const char *name, VEC (name_tree, heap) *params,
3770 loop_iv_stack ivstack)
3777 for (i = 0; VEC_iterate (name_tree, params, i, t); i++)
3778 if (!strcmp (name, t->name))
3781 iv = loop_iv_stack_get_iv_from_name (ivstack, name);
3788 /* Returns the maximal precision type for expressions E1 and E2. */
3791 max_precision_type (tree e1, tree e2)
3793 tree type1 = TREE_TYPE (e1);
3794 tree type2 = TREE_TYPE (e2);
3795 return TYPE_PRECISION (type1) > TYPE_PRECISION (type2) ? type1 : type2;
3799 clast_to_gcc_expression (tree, struct clast_expr *, VEC (name_tree, heap) *,
3802 /* Converts a Cloog reduction expression R with reduction operation OP
3803 to a GCC expression tree of type TYPE. PARAMS is a vector of
3804 parameters of the scop, and IVSTACK contains the stack of induction
3808 clast_to_gcc_expression_red (tree type, enum tree_code op,
3809 struct clast_reduction *r,
3810 VEC (name_tree, heap) *params,
3811 loop_iv_stack ivstack)
3814 tree res = clast_to_gcc_expression (type, r->elts[0], params, ivstack);
3816 for (i = 1; i < r->n; i++)
3818 tree t = clast_to_gcc_expression (type, r->elts[i], params, ivstack);
3819 res = fold_build2 (op, type, res, t);
3824 /* Converts a Cloog AST expression E back to a GCC expression tree of
3825 type TYPE. PARAMS is a vector of parameters of the scop, and
3826 IVSTACK contains the stack of induction variables. */
3829 clast_to_gcc_expression (tree type, struct clast_expr *e,
3830 VEC (name_tree, heap) *params,
3831 loop_iv_stack ivstack)
3837 struct clast_term *t = (struct clast_term *) e;
3841 if (value_one_p (t->val))
3843 tree name = clast_name_to_gcc (t->var, params, ivstack);
3844 return fold_convert (type, name);
3847 else if (value_mone_p (t->val))
3849 tree name = clast_name_to_gcc (t->var, params, ivstack);
3850 name = fold_convert (type, name);
3851 return fold_build1 (NEGATE_EXPR, type, name);
3855 tree name = clast_name_to_gcc (t->var, params, ivstack);
3856 tree cst = gmp_cst_to_tree (type, t->val);
3857 name = fold_convert (type, name);
3858 return fold_build2 (MULT_EXPR, type, cst, name);
3862 return gmp_cst_to_tree (type, t->val);
3867 struct clast_reduction *r = (struct clast_reduction *) e;
3872 return clast_to_gcc_expression_red (type, PLUS_EXPR, r, params, ivstack);
3875 return clast_to_gcc_expression_red (type, MIN_EXPR, r, params, ivstack);
3878 return clast_to_gcc_expression_red (type, MAX_EXPR, r, params, ivstack);
3888 struct clast_binary *b = (struct clast_binary *) e;
3889 struct clast_expr *lhs = (struct clast_expr *) b->LHS;
3890 tree tl = clast_to_gcc_expression (type, lhs, params, ivstack);
3891 tree tr = gmp_cst_to_tree (type, b->RHS);
3895 case clast_bin_fdiv:
3896 return fold_build2 (FLOOR_DIV_EXPR, type, tl, tr);
3898 case clast_bin_cdiv:
3899 return fold_build2 (CEIL_DIV_EXPR, type, tl, tr);
3902 return fold_build2 (EXACT_DIV_EXPR, type, tl, tr);
3905 return fold_build2 (TRUNC_MOD_EXPR, type, tl, tr);
3919 /* Returns the type for the expression E. */
3922 gcc_type_for_clast_expr (struct clast_expr *e,
3923 VEC (name_tree, heap) *params,
3924 loop_iv_stack ivstack)
3930 struct clast_term *t = (struct clast_term *) e;
3933 return TREE_TYPE (clast_name_to_gcc (t->var, params, ivstack));
3940 struct clast_reduction *r = (struct clast_reduction *) e;
3943 return gcc_type_for_clast_expr (r->elts[0], params, ivstack);
3947 for (i = 0; i < r->n; i++)
3949 tree type = gcc_type_for_clast_expr (r->elts[i], params, ivstack);
3959 struct clast_binary *b = (struct clast_binary *) e;
3960 struct clast_expr *lhs = (struct clast_expr *) b->LHS;
3961 return gcc_type_for_clast_expr (lhs, params, ivstack);
3971 /* Returns the type for the equation CLEQ. */
3974 gcc_type_for_clast_eq (struct clast_equation *cleq,
3975 VEC (name_tree, heap) *params,
3976 loop_iv_stack ivstack)
3978 tree type = gcc_type_for_clast_expr (cleq->LHS, params, ivstack);
3982 return gcc_type_for_clast_expr (cleq->RHS, params, ivstack);
3985 /* Translates a clast equation CLEQ to a tree. */
3988 graphite_translate_clast_equation (scop_p scop,
3989 struct clast_equation *cleq,
3990 loop_iv_stack ivstack)
3992 enum tree_code comp;
3993 tree type = gcc_type_for_clast_eq (cleq, SCOP_PARAMS (scop), ivstack);
3994 tree lhs = clast_to_gcc_expression (type, cleq->LHS, SCOP_PARAMS (scop), ivstack);
3995 tree rhs = clast_to_gcc_expression (type, cleq->RHS, SCOP_PARAMS (scop), ivstack);
3997 if (cleq->sign == 0)
4000 else if (cleq->sign > 0)
4006 return fold_build2 (comp, type, lhs, rhs);
4009 /* Creates the test for the condition in STMT. */
4012 graphite_create_guard_cond_expr (scop_p scop, struct clast_guard *stmt,
4013 loop_iv_stack ivstack)
4018 for (i = 0; i < stmt->n; i++)
4020 tree eq = graphite_translate_clast_equation (scop, &stmt->eq[i], ivstack);
4023 cond = fold_build2 (TRUTH_AND_EXPR, TREE_TYPE (eq), cond, eq);
4031 /* Creates a new if region corresponding to Cloog's guard. */
4034 graphite_create_new_guard (scop_p scop, edge entry_edge,
4035 struct clast_guard *stmt,
4036 loop_iv_stack ivstack)
4038 tree cond_expr = graphite_create_guard_cond_expr (scop, stmt, ivstack);
4039 edge exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
4043 /* Walks a CLAST and returns the first statement in the body of a
4046 static struct clast_user_stmt *
4047 clast_get_body_of_loop (struct clast_stmt *stmt)
4050 || CLAST_STMT_IS_A (stmt, stmt_user))
4051 return (struct clast_user_stmt *) stmt;
4053 if (CLAST_STMT_IS_A (stmt, stmt_for))
4054 return clast_get_body_of_loop (((struct clast_for *) stmt)->body);
4056 if (CLAST_STMT_IS_A (stmt, stmt_guard))
4057 return clast_get_body_of_loop (((struct clast_guard *) stmt)->then);
4059 if (CLAST_STMT_IS_A (stmt, stmt_block))
4060 return clast_get_body_of_loop (((struct clast_block *) stmt)->body);
4065 /* Returns the induction variable for the loop that gets translated to
4069 gcc_type_for_iv_of_clast_loop (struct clast_for *stmt_for)
4071 struct clast_user_stmt *stmt = clast_get_body_of_loop ((struct clast_stmt *) stmt_for);
4072 const char *cloog_iv = stmt_for->iterator;
4073 CloogStatement *cs = stmt->statement;
4074 graphite_bb_p gbb = (graphite_bb_p) cloog_statement_usr (cs);
4076 return gcc_type_for_cloog_iv (cloog_iv, gbb);
4079 /* Creates a new LOOP corresponding to Cloog's STMT. Inserts an induction
4080 variable for the new LOOP. New LOOP is attached to CFG starting at
4081 ENTRY_EDGE. LOOP is inserted into the loop tree and becomes the child
4082 loop of the OUTER_LOOP. */
4084 static struct loop *
4085 graphite_create_new_loop (scop_p scop, edge entry_edge,
4086 struct clast_for *stmt, loop_iv_stack ivstack,
4089 tree type = gcc_type_for_iv_of_clast_loop (stmt);
4090 VEC (name_tree, heap) *params = SCOP_PARAMS (scop);
4091 tree lb = clast_to_gcc_expression (type, stmt->LB, params, ivstack);
4092 tree ub = clast_to_gcc_expression (type, stmt->UB, params, ivstack);
4093 tree stride = gmp_cst_to_tree (type, stmt->stride);
4094 tree ivvar = create_tmp_var (type, "graphiteIV");
4096 loop_p loop = create_empty_loop_on_edge
4097 (entry_edge, lb, stride, ub, ivvar, &iv_before,
4098 outer ? outer : entry_edge->src->loop_father);
4100 add_referenced_var (ivvar);
4101 loop_iv_stack_push_iv (ivstack, iv_before, stmt->iterator);
4105 /* Rename the SSA_NAMEs used in STMT and that appear in IVSTACK. */
4108 rename_variables_in_stmt (gimple stmt, htab_t map)
4111 use_operand_p use_p;
4113 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
4115 tree use = USE_FROM_PTR (use_p);
4116 tree new_name = get_new_name_from_old_name (map, use);
4118 replace_exp (use_p, new_name);
4124 /* Returns true if SSA_NAME is a parameter of SCOP. */
4127 is_parameter (scop_p scop, tree ssa_name)
4130 VEC (name_tree, heap) *params = SCOP_PARAMS (scop);
4133 for (i = 0; VEC_iterate (name_tree, params, i, param); i++)
4134 if (param->t == ssa_name)
4140 /* Returns true if NAME is an induction variable. */
4145 return gimple_code (SSA_NAME_DEF_STMT (name)) == GIMPLE_PHI;
4148 static void expand_scalar_variables_stmt (gimple, basic_block, scop_p,
4151 expand_scalar_variables_expr (tree, tree, enum tree_code, tree, basic_block,
4152 scop_p, htab_t, gimple_stmt_iterator *);
4154 /* Copies at GSI all the scalar computations on which the ssa_name OP0
4155 depends on in the SCOP: these are all the scalar variables used in
4156 the definition of OP0, that are defined outside BB and still in the
4157 SCOP, i.e. not a parameter of the SCOP. The expression that is
4158 returned contains only induction variables from the generated code:
4159 MAP contains the induction variables renaming mapping, and is used
4160 to translate the names of induction variables. */
4163 expand_scalar_variables_ssa_name (tree op0, basic_block bb,
4164 scop_p scop, htab_t map,
4165 gimple_stmt_iterator *gsi)
4167 tree var0, var1, type;
4169 enum tree_code subcode;
4171 if (is_parameter (scop, op0)
4173 return get_new_name_from_old_name (map, op0);
4175 def_stmt = SSA_NAME_DEF_STMT (op0);
4177 if (gimple_bb (def_stmt) == bb)
4179 /* If the defining statement is in the basic block already
4180 we do not need to create a new expression for it, we
4181 only need to ensure its operands are expanded. */
4182 expand_scalar_variables_stmt (def_stmt, bb, scop, map);
4183 return get_new_name_from_old_name (map, op0);
4187 if (gimple_code (def_stmt) != GIMPLE_ASSIGN
4188 || !bb_in_sese_p (gimple_bb (def_stmt), SCOP_REGION (scop)))
4189 return get_new_name_from_old_name (map, op0);
4191 var0 = gimple_assign_rhs1 (def_stmt);
4192 subcode = gimple_assign_rhs_code (def_stmt);
4193 var1 = gimple_assign_rhs2 (def_stmt);
4194 type = gimple_expr_type (def_stmt);
4196 return expand_scalar_variables_expr (type, var0, subcode, var1, bb, scop,
4201 /* Copies at GSI all the scalar computations on which the expression
4202 OP0 CODE OP1 depends on in the SCOP: these are all the scalar
4203 variables used in OP0 and OP1, defined outside BB and still defined
4204 in the SCOP, i.e. not a parameter of the SCOP. The expression that
4205 is returned contains only induction variables from the generated
4206 code: MAP contains the induction variables renaming mapping, and is
4207 used to translate the names of induction variables. */
4210 expand_scalar_variables_expr (tree type, tree op0, enum tree_code code,
4211 tree op1, basic_block bb, scop_p scop,
4212 htab_t map, gimple_stmt_iterator *gsi)
4214 if (TREE_CODE_CLASS (code) == tcc_constant
4215 || TREE_CODE_CLASS (code) == tcc_declaration)
4218 /* For data references we have to duplicate also its memory
4220 if (TREE_CODE_CLASS (code) == tcc_reference)
4226 tree old_name = TREE_OPERAND (op0, 0);
4227 tree expr = expand_scalar_variables_ssa_name
4228 (old_name, bb, scop, map, gsi);
4229 tree new_name = force_gimple_operand_gsi (gsi, expr, true, NULL,
4230 true, GSI_SAME_STMT);
4232 set_symbol_mem_tag (SSA_NAME_VAR (new_name),
4233 symbol_mem_tag (SSA_NAME_VAR (old_name)));
4234 return fold_build1 (code, type, new_name);
4239 tree op00 = TREE_OPERAND (op0, 0);
4240 tree op01 = TREE_OPERAND (op0, 1);
4241 tree op02 = TREE_OPERAND (op0, 2);
4242 tree op03 = TREE_OPERAND (op0, 3);
4243 tree base = expand_scalar_variables_expr
4244 (TREE_TYPE (op00), op00, TREE_CODE (op00), NULL, bb, scop,
4246 tree subscript = expand_scalar_variables_expr
4247 (TREE_TYPE (op01), op01, TREE_CODE (op01), NULL, bb, scop,
4250 return build4 (ARRAY_REF, type, base, subscript, op02, op03);
4254 /* The above cases should catch everything. */
4259 if (TREE_CODE_CLASS (code) == tcc_unary)
4261 tree op0_type = TREE_TYPE (op0);
4262 enum tree_code op0_code = TREE_CODE (op0);
4263 tree op0_expr = expand_scalar_variables_expr (op0_type, op0, op0_code,
4264 NULL, bb, scop, map, gsi);
4266 return fold_build1 (code, type, op0_expr);
4269 if (TREE_CODE_CLASS (code) == tcc_binary)
4271 tree op0_type = TREE_TYPE (op0);
4272 enum tree_code op0_code = TREE_CODE (op0);
4273 tree op0_expr = expand_scalar_variables_expr (op0_type, op0, op0_code,
4274 NULL, bb, scop, map, gsi);
4275 tree op1_type = TREE_TYPE (op1);
4276 enum tree_code op1_code = TREE_CODE (op1);
4277 tree op1_expr = expand_scalar_variables_expr (op1_type, op1, op1_code,
4278 NULL, bb, scop, map, gsi);
4280 return fold_build2 (code, type, op0_expr, op1_expr);
4283 if (code == SSA_NAME)
4284 return expand_scalar_variables_ssa_name (op0, bb, scop, map, gsi);
4290 /* Copies at the beginning of BB all the scalar computations on which
4291 STMT depends on in the SCOP: these are all the scalar variables used
4292 in STMT, defined outside BB and still defined in the SCOP, i.e. not a
4293 parameter of the SCOP. The expression that is returned contains
4294 only induction variables from the generated code: MAP contains the
4295 induction variables renaming mapping, and is used to translate the
4296 names of induction variables. */
4299 expand_scalar_variables_stmt (gimple stmt, basic_block bb, scop_p scop,
4303 use_operand_p use_p;
4304 gimple_stmt_iterator gsi = gsi_after_labels (bb);
4306 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
4308 tree use = USE_FROM_PTR (use_p);
4309 tree type = TREE_TYPE (use);
4310 enum tree_code code = TREE_CODE (use);
4311 tree use_expr = expand_scalar_variables_expr (type, use, code, NULL, bb,
4313 if (use_expr != use)
4316 force_gimple_operand_gsi (&gsi, use_expr, true, NULL,
4317 true, GSI_NEW_STMT);
4318 replace_exp (use_p, new_use);
4325 /* Copies at the beginning of BB all the scalar computations on which
4326 BB depends on in the SCOP: these are all the scalar variables used
4327 in BB, defined outside BB and still defined in the SCOP, i.e. not a
4328 parameter of the SCOP. The expression that is returned contains
4329 only induction variables from the generated code: MAP contains the
4330 induction variables renaming mapping, and is used to translate the
4331 names of induction variables. */
4334 expand_scalar_variables (basic_block bb, scop_p scop, htab_t map)
4336 gimple_stmt_iterator gsi;
4338 for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi);)
4340 gimple stmt = gsi_stmt (gsi);
4341 expand_scalar_variables_stmt (stmt, bb, scop, map);
4346 /* Rename all the SSA_NAMEs from block BB according to the MAP. */
4349 rename_variables (basic_block bb, htab_t map)
4351 gimple_stmt_iterator gsi;
4353 for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4354 rename_variables_in_stmt (gsi_stmt (gsi), map);
4357 /* Remove condition from BB. */
4360 remove_condition (basic_block bb)
4362 gimple last = last_stmt (bb);
4364 if (last && gimple_code (last) == GIMPLE_COND)
4366 gimple_stmt_iterator gsi = gsi_last_bb (bb);
4367 gsi_remove (&gsi, true);
4371 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag set. */
4374 get_true_edge_from_guard_bb (basic_block bb)
4379 FOR_EACH_EDGE (e, ei, bb->succs)
4380 if (e->flags & EDGE_TRUE_VALUE)
4387 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag cleared. */
4390 get_false_edge_from_guard_bb (basic_block bb)
4395 FOR_EACH_EDGE (e, ei, bb->succs)
4396 if (!(e->flags & EDGE_TRUE_VALUE))
4403 /* Inserts in MAP a tuple (OLD_NAME, NEW_NAME) for the induction
4404 variables of the loops around GBB in SCOP, i.e. GBB_LOOPS.
4405 NEW_NAME is obtained from IVSTACK. IVSTACK has the same stack
4406 ordering as GBB_LOOPS. */
4409 build_iv_mapping (loop_iv_stack ivstack, htab_t map, gbb_p gbb, scop_p scop)
4415 for (i = 0; VEC_iterate (name_tree, SCOP_OLDIVS (scop), i, iv); i++)
4417 struct rename_map_elt tmp;
4419 if (!flow_bb_inside_loop_p (iv->loop, GBB_BB (gbb)))
4422 tmp.old_name = iv->t;
4423 slot = htab_find_slot (map, &tmp, INSERT);
4427 tree new_name = loop_iv_stack_get_iv (ivstack,
4428 gbb_loop_index (gbb, iv->loop));
4429 *slot = new_rename_map_elt (iv->t, new_name);
4434 /* Register in MAP the tuple (old_name, new_name). */
4437 register_old_and_new_names (htab_t map, tree old_name, tree new_name)
4439 struct rename_map_elt tmp;
4442 tmp.old_name = old_name;
4443 slot = htab_find_slot (map, &tmp, INSERT);
4446 *slot = new_rename_map_elt (old_name, new_name);
4449 /* Create a duplicate of the basic block BB. NOTE: This does not
4450 preserve SSA form. */
4453 graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb, htab_t map)
4455 gimple_stmt_iterator gsi, gsi_tgt;
4457 gsi_tgt = gsi_start_bb (new_bb);
4458 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4460 def_operand_p def_p;
4461 ssa_op_iter op_iter;
4463 gimple stmt = gsi_stmt (gsi);
4466 if (gimple_code (stmt) == GIMPLE_LABEL)
4469 /* Create a new copy of STMT and duplicate STMT's virtual
4471 copy = gimple_copy (stmt);
4472 gsi_insert_after (&gsi_tgt, copy, GSI_NEW_STMT);
4473 mark_symbols_for_renaming (copy);
4475 region = lookup_stmt_eh_region (stmt);
4477 add_stmt_to_eh_region (copy, region);
4478 gimple_duplicate_stmt_histograms (cfun, copy, cfun, stmt);
4480 /* Create new names for all the definitions created by COPY and
4481 add replacement mappings for each new name. */
4482 FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_DEF)
4484 tree old_name = DEF_FROM_PTR (def_p);
4485 tree new_name = create_new_def_for (old_name, copy, def_p);
4486 register_old_and_new_names (map, old_name, new_name);
4491 /* Records in SCOP_LIVEOUT_RENAMES the names that are live out of
4492 the SCOP and that appear in the RENAME_MAP. */
4495 register_scop_liveout_renames (scop_p scop, htab_t rename_map)
4498 sese region = SCOP_REGION (scop);
4500 for (i = 0; i < SESE_NUM_VER (region); i++)
4501 if (bitmap_bit_p (SESE_LIVEOUT (region), i)
4502 && is_gimple_reg (ssa_name (i)))
4504 tree old_name = ssa_name (i);
4505 tree new_name = get_new_name_from_old_name (rename_map, old_name);
4507 register_old_and_new_names (SCOP_LIVEOUT_RENAMES (scop),
4508 old_name, new_name);
4512 /* Copies BB and includes in the copied BB all the statements that can
4513 be reached following the use-def chains from the memory accesses,
4514 and returns the next edge following this new block. */
4517 copy_bb_and_scalar_dependences (basic_block bb, scop_p scop,
4518 edge next_e, htab_t map)
4520 basic_block new_bb = split_edge (next_e);
4522 next_e = single_succ_edge (new_bb);
4523 graphite_copy_stmts_from_block (bb, new_bb, map);
4524 remove_condition (new_bb);
4525 rename_variables (new_bb, map);
4526 remove_phi_nodes (new_bb);
4527 expand_scalar_variables (new_bb, scop, map);
4528 register_scop_liveout_renames (scop, map);
4533 /* Helper function for htab_traverse in insert_loop_close_phis. */
4536 add_loop_exit_phis (void **slot, void *s)
4538 struct rename_map_elt *entry = (struct rename_map_elt *) *slot;
4539 tree new_name = entry->new_name;
4540 basic_block bb = (basic_block) s;
4541 gimple phi = create_phi_node (new_name, bb);
4542 tree res = create_new_def_for (gimple_phi_result (phi), phi,
4543 gimple_phi_result_ptr (phi));
4545 add_phi_arg (phi, new_name, single_pred_edge (bb));
4547 entry->new_name = res;
4552 /* Iterate over the SCOP_LIVEOUT_RENAMES (SCOP) and get tuples of the
4553 form (OLD_NAME, NEW_NAME). Insert in BB "RES = phi (NEW_NAME)",
4554 and finally register in SCOP_LIVEOUT_RENAMES (scop) the tuple
4558 insert_loop_close_phis (scop_p scop, basic_block bb)
4560 update_ssa (TODO_update_ssa);
4561 htab_traverse (SCOP_LIVEOUT_RENAMES (scop), add_loop_exit_phis, bb);
4562 update_ssa (TODO_update_ssa);
4565 /* Helper structure for htab_traverse in insert_guard_phis. */
4569 edge true_edge, false_edge;
4570 htab_t liveout_before_guard;
4573 /* Return the default name that is before the guard. */
4576 default_liveout_before_guard (htab_t liveout_before_guard, tree old_name)
4578 tree res = get_new_name_from_old_name (liveout_before_guard, old_name);
4580 if (res == old_name)
4582 if (is_gimple_reg (res))
4583 return fold_convert (TREE_TYPE (res), integer_zero_node);
4584 return gimple_default_def (cfun, res);
4590 /* Helper function for htab_traverse in insert_guard_phis. */
4593 add_guard_exit_phis (void **slot, void *s)
4595 struct rename_map_elt *entry = (struct rename_map_elt *) *slot;
4596 struct igp *i = (struct igp *) s;
4597 basic_block bb = i->bb;
4598 edge true_edge = i->true_edge;
4599 edge false_edge = i->false_edge;
4600 tree name1 = entry->new_name;
4601 tree name2 = default_liveout_before_guard (i->liveout_before_guard,
4603 gimple phi = create_phi_node (name1, bb);
4604 tree res = create_new_def_for (gimple_phi_result (phi), phi,
4605 gimple_phi_result_ptr (phi));
4607 add_phi_arg (phi, name1, true_edge);
4608 add_phi_arg (phi, name2, false_edge);
4610 entry->new_name = res;
4615 /* Iterate over the SCOP_LIVEOUT_RENAMES (SCOP) and get tuples of the
4616 form (OLD_NAME, NAME1). If there is a correspondent tuple of
4617 OLD_NAME in LIVEOUT_BEFORE_GUARD, i.e. (OLD_NAME, NAME2) then
4620 | RES = phi (NAME1 (on TRUE_EDGE), NAME2 (on FALSE_EDGE))"
4622 if there is no tuple for OLD_NAME in LIVEOUT_BEFORE_GUARD, insert
4624 | RES = phi (NAME1 (on TRUE_EDGE),
4625 | DEFAULT_DEFINITION of NAME1 (on FALSE_EDGE))".
4627 Finally register in SCOP_LIVEOUT_RENAMES (scop) the tuple
4631 insert_guard_phis (scop_p scop, basic_block bb, edge true_edge,
4632 edge false_edge, htab_t liveout_before_guard)
4636 i.true_edge = true_edge;
4637 i.false_edge = false_edge;
4638 i.liveout_before_guard = liveout_before_guard;
4640 update_ssa (TODO_update_ssa);
4641 htab_traverse (SCOP_LIVEOUT_RENAMES (scop), add_guard_exit_phis, &i);
4642 update_ssa (TODO_update_ssa);
4645 /* Helper function for htab_traverse. */
4648 copy_renames (void **slot, void *s)
4650 struct rename_map_elt *entry = (struct rename_map_elt *) *slot;
4651 htab_t res = (htab_t) s;
4652 tree old_name = entry->old_name;
4653 tree new_name = entry->new_name;
4654 struct rename_map_elt tmp;
4657 tmp.old_name = old_name;
4658 x = htab_find_slot (res, &tmp, INSERT);
4661 *x = new_rename_map_elt (old_name, new_name);
4666 /* Translates a CLAST statement STMT to GCC representation in the
4669 - NEXT_E is the edge where new generated code should be attached.
4670 - CONTEXT_LOOP is the loop in which the generated code will be placed
4672 - IVSTACK contains the surrounding loops around the statement to be
4677 translate_clast (scop_p scop, struct loop *context_loop,
4678 struct clast_stmt *stmt, edge next_e, loop_iv_stack ivstack)
4683 if (CLAST_STMT_IS_A (stmt, stmt_root))
4684 return translate_clast (scop, context_loop, stmt->next, next_e, ivstack);
4686 if (CLAST_STMT_IS_A (stmt, stmt_user))
4689 CloogStatement *cs = ((struct clast_user_stmt *) stmt)->statement;
4690 graphite_bb_p gbb = (graphite_bb_p) cloog_statement_usr (cs);
4692 if (GBB_BB (gbb) == ENTRY_BLOCK_PTR)
4695 map = htab_create (10, rename_map_elt_info, eq_rename_map_elts, free);
4696 loop_iv_stack_patch_for_consts (ivstack, (struct clast_user_stmt *) stmt);
4697 build_iv_mapping (ivstack, map, gbb, scop);
4698 next_e = copy_bb_and_scalar_dependences (GBB_BB (gbb), scop,
4701 loop_iv_stack_remove_constants (ivstack);
4702 update_ssa (TODO_update_ssa);
4703 recompute_all_dominators ();
4705 return translate_clast (scop, context_loop, stmt->next, next_e, ivstack);
4708 if (CLAST_STMT_IS_A (stmt, stmt_for))
4711 = graphite_create_new_loop (scop, next_e, (struct clast_for *) stmt,
4712 ivstack, context_loop ? context_loop
4714 edge last_e = single_exit (loop);
4716 next_e = translate_clast (scop, loop, ((struct clast_for *) stmt)->body,
4717 single_pred_edge (loop->latch), ivstack);
4718 redirect_edge_succ_nodup (next_e, loop->latch);
4720 set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src);
4721 loop_iv_stack_pop (ivstack);
4722 last_e = single_succ_edge (split_edge (last_e));
4723 insert_loop_close_phis (scop, last_e->src);
4725 recompute_all_dominators ();
4727 return translate_clast (scop, context_loop, stmt->next, last_e, ivstack);
4730 if (CLAST_STMT_IS_A (stmt, stmt_guard))
4732 htab_t liveout_before_guard = htab_create (10, rename_map_elt_info,
4733 eq_rename_map_elts, free);
4734 edge last_e = graphite_create_new_guard (scop, next_e,
4735 ((struct clast_guard *) stmt),
4737 edge true_e = get_true_edge_from_guard_bb (next_e->dest);
4738 edge false_e = get_false_edge_from_guard_bb (next_e->dest);
4739 edge exit_true_e = single_succ_edge (true_e->dest);
4740 edge exit_false_e = single_succ_edge (false_e->dest);
4742 htab_traverse (SCOP_LIVEOUT_RENAMES (scop), copy_renames,
4743 liveout_before_guard);
4745 next_e = translate_clast (scop, context_loop,
4746 ((struct clast_guard *) stmt)->then,
4748 insert_guard_phis (scop, last_e->src, exit_true_e, exit_false_e,
4749 liveout_before_guard);
4750 htab_delete (liveout_before_guard);
4751 recompute_all_dominators ();
4754 return translate_clast (scop, context_loop, stmt->next, last_e, ivstack);
4757 if (CLAST_STMT_IS_A (stmt, stmt_block))
4759 next_e = translate_clast (scop, context_loop,
4760 ((struct clast_block *) stmt)->body,
4762 recompute_all_dominators ();
4764 return translate_clast (scop, context_loop, stmt->next, next_e, ivstack);
4770 /* Free the SCATTERING domain list. */
4773 free_scattering (CloogDomainList *scattering)
4777 CloogDomain *dom = cloog_domain (scattering);
4778 CloogDomainList *next = cloog_next_domain (scattering);
4780 cloog_domain_free (dom);
4786 /* Build cloog program for SCoP. */
4789 build_cloog_prog (scop_p scop)
4792 int max_nb_loops = scop_max_loop_depth (scop);
4794 CloogLoop *loop_list = NULL;
4795 CloogBlockList *block_list = NULL;
4796 CloogDomainList *scattering = NULL;
4797 CloogProgram *prog = SCOP_PROG (scop);
4798 int nbs = 2 * max_nb_loops + 1;
4799 int *scaldims = (int *) xmalloc (nbs * (sizeof (int)));
4801 cloog_program_set_nb_scattdims (prog, nbs);
4802 initialize_cloog_names (scop);
4804 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gbb); i++)
4806 /* Build new block. */
4807 CloogMatrix *domain = GBB_DOMAIN (gbb);
4808 CloogStatement *stmt = cloog_statement_alloc (GBB_BB (gbb)->index);
4809 CloogBlock *block = cloog_block_alloc (stmt, 0, NULL,
4810 nb_loops_around_gb (gbb));
4811 cloog_statement_set_usr (stmt, gbb);
4813 /* Add empty domain to all bbs, which do not yet have a domain, as they
4814 are not part of any loop. */
4817 domain = cloog_matrix_alloc (0, scop_nb_params (scop) + 2);
4818 GBB_DOMAIN (gbb) = domain;
4821 /* Build loop list. */
4823 CloogLoop *new_loop_list = cloog_loop_malloc ();
4824 cloog_loop_set_next (new_loop_list, loop_list);
4825 cloog_loop_set_domain (new_loop_list,
4826 cloog_domain_matrix2domain (domain));
4827 cloog_loop_set_block (new_loop_list, block);
4828 loop_list = new_loop_list;
4831 /* Build block list. */
4833 CloogBlockList *new_block_list = cloog_block_list_malloc ();
4835 cloog_block_list_set_next (new_block_list, block_list);
4836 cloog_block_list_set_block (new_block_list, block);
4837 block_list = new_block_list;
4840 /* Build scattering list. */
4842 /* XXX: Replace with cloog_domain_list_alloc(), when available. */
4843 CloogDomainList *new_scattering
4844 = (CloogDomainList *) xmalloc (sizeof (CloogDomainList));
4845 CloogMatrix *scat_mat = schedule_to_scattering (gbb, nbs);
4847 cloog_set_next_domain (new_scattering, scattering);
4848 cloog_set_domain (new_scattering,
4849 cloog_domain_matrix2domain (scat_mat));
4850 scattering = new_scattering;
4851 cloog_matrix_free (scat_mat);
4855 cloog_program_set_loop (prog, loop_list);
4856 cloog_program_set_blocklist (prog, block_list);
4858 for (i = 0; i < nbs; i++)
4861 cloog_program_set_scaldims (prog, scaldims);
4863 /* Extract scalar dimensions to simplify the code generation problem. */
4864 cloog_program_extract_scalars (prog, scattering);
4866 /* Apply scattering. */
4867 cloog_program_scatter (prog, scattering);
4868 free_scattering (scattering);
4870 /* Iterators corresponding to scalar dimensions have to be extracted. */
4871 cloog_names_scalarize (cloog_program_names (prog), nbs,
4872 cloog_program_scaldims (prog));
4874 /* Free blocklist. */
4876 CloogBlockList *next = cloog_program_blocklist (prog);
4880 CloogBlockList *toDelete = next;
4881 next = cloog_block_list_next (next);
4882 cloog_block_list_set_next (toDelete, NULL);
4883 cloog_block_list_set_block (toDelete, NULL);
4884 cloog_block_list_free (toDelete);
4886 cloog_program_set_blocklist (prog, NULL);
4890 /* Return the options that will be used in GLOOG. */
4892 static CloogOptions *
4893 set_cloog_options (void)
4895 CloogOptions *options = cloog_options_malloc ();
4897 /* Change cloog output language to C. If we do use FORTRAN instead, cloog
4898 will stop e.g. with "ERROR: unbounded loops not allowed in FORTRAN.", if
4899 we pass an incomplete program to cloog. */
4900 options->language = LANGUAGE_C;
4902 /* Enable complex equality spreading: removes dummy statements
4903 (assignments) in the generated code which repeats the
4904 substitution equations for statements. This is useless for
4908 /* Enable C pretty-printing mode: normalizes the substitution
4909 equations for statements. */
4912 /* Allow cloog to build strides with a stride width different to one.
4913 This example has stride = 4:
4915 for (i = 0; i < 20; i += 4)
4917 options->strides = 1;
4919 /* Disable optimizations and make cloog generate source code closer to the
4920 input. This is useful for debugging, but later we want the optimized
4923 XXX: We can not disable optimizations, as loop blocking is not working
4928 options->l = INT_MAX;
4934 /* Prints STMT to STDERR. */
4937 debug_clast_stmt (struct clast_stmt *stmt)
4939 CloogOptions *options = set_cloog_options ();
4941 pprint (stderr, stmt, 0, options);
4944 /* Find the right transform for the SCOP, and return a Cloog AST
4945 representing the new form of the program. */
4947 static struct clast_stmt *
4948 find_transform (scop_p scop)
4950 struct clast_stmt *stmt;
4951 CloogOptions *options = set_cloog_options ();
4953 /* Connect new cloog prog generation to graphite. */
4954 build_cloog_prog (scop);
4956 if (dump_file && (dump_flags & TDF_DETAILS))
4958 fprintf (dump_file, "Cloog Input [\n");
4959 cloog_program_print (dump_file, SCOP_PROG(scop));
4960 fprintf (dump_file, "]\n");
4963 SCOP_PROG (scop) = cloog_program_generate (SCOP_PROG (scop), options);
4964 stmt = cloog_clast_create (SCOP_PROG (scop), options);
4966 if (dump_file && (dump_flags & TDF_DETAILS))
4968 fprintf (dump_file, "Cloog Output[\n");
4969 pprint (dump_file, stmt, 0, options);
4970 cloog_program_dump_cloog (dump_file, SCOP_PROG (scop));
4971 fprintf (dump_file, "]\n");
4974 cloog_options_free (options);
4978 /* Remove from the CFG the REGION. */
4981 remove_sese_region (sese region)
4983 VEC (basic_block, heap) *bbs = NULL;
4984 basic_block entry_bb = SESE_ENTRY (region)->dest;
4985 basic_block exit_bb = SESE_EXIT (region)->dest;
4989 VEC_safe_push (basic_block, heap, bbs, entry_bb);
4990 gather_blocks_in_sese_region (entry_bb, exit_bb, &bbs);
4992 for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
4993 delete_basic_block (bb);
4995 VEC_free (basic_block, heap, bbs);
4998 typedef struct ifsese {
5005 if_region_entry (ifsese if_region)
5007 return SESE_ENTRY (if_region->region);
5011 if_region_exit (ifsese if_region)
5013 return SESE_EXIT (if_region->region);
5016 static inline basic_block
5017 if_region_get_condition_block (ifsese if_region)
5019 return if_region_entry (if_region)->dest;
5023 if_region_set_false_region (ifsese if_region, sese region)
5025 basic_block condition = if_region_get_condition_block (if_region);
5026 edge false_edge = get_false_edge_from_guard_bb (condition);
5027 basic_block dummy = false_edge->dest;
5028 edge entry_region = SESE_ENTRY (region);
5029 edge exit_region = SESE_EXIT (region);
5030 basic_block before_region = entry_region->src;
5031 basic_block last_in_region = exit_region->src;
5032 void **slot = htab_find_slot_with_hash (current_loops->exits, exit_region,
5033 htab_hash_pointer (exit_region),
5036 entry_region->flags = false_edge->flags;
5037 false_edge->flags = exit_region->flags;
5039 redirect_edge_pred (entry_region, condition);
5040 redirect_edge_pred (exit_region, before_region);
5041 redirect_edge_pred (false_edge, last_in_region);
5042 redirect_edge_succ (false_edge, single_succ (dummy));
5043 delete_basic_block (dummy);
5045 exit_region->flags = EDGE_FALLTHRU;
5046 recompute_all_dominators ();
5048 SESE_EXIT (region) = false_edge;
5049 if_region->false_region = region;
5053 struct loop_exit *loop_exit = GGC_CNEW (struct loop_exit);
5055 memcpy (loop_exit, *((struct loop_exit **) slot), sizeof (struct loop_exit));
5056 htab_clear_slot (current_loops->exits, slot);
5058 slot = htab_find_slot_with_hash (current_loops->exits, false_edge,
5059 htab_hash_pointer (false_edge),
5061 loop_exit->e = false_edge;
5063 false_edge->src->loop_father->exits->next = loop_exit;
5068 create_if_region_on_edge (edge entry, tree condition)
5072 sese sese_region = GGC_NEW (struct sese);
5073 sese true_region = GGC_NEW (struct sese);
5074 sese false_region = GGC_NEW (struct sese);
5075 ifsese if_region = GGC_NEW (struct ifsese);
5076 edge exit = create_empty_if_region_on_edge (entry, condition);
5078 if_region->region = sese_region;
5079 if_region->region->entry = entry;
5080 if_region->region->exit = exit;
5082 FOR_EACH_EDGE (e, ei, entry->dest->succs)
5084 if (e->flags & EDGE_TRUE_VALUE)
5086 true_region->entry = e;
5087 true_region->exit = single_succ_edge (e->dest);
5088 if_region->true_region = true_region;
5090 else if (e->flags & EDGE_FALSE_VALUE)
5092 false_region->entry = e;
5093 false_region->exit = single_succ_edge (e->dest);
5094 if_region->false_region = false_region;
5101 /* Moves REGION in a condition expression:
5109 move_sese_in_condition (sese region)
5111 basic_block pred_block = split_edge (SESE_ENTRY (region));
5112 ifsese if_region = NULL;
5114 SESE_ENTRY (region) = single_succ_edge (pred_block);
5115 if_region = create_if_region_on_edge (single_pred_edge (pred_block), integer_one_node);
5116 if_region_set_false_region (if_region, region);
5121 /* Add exit phis for USE on EXIT. */
5124 scop_add_exit_phis_edge (basic_block exit, tree use, edge false_e, edge true_e)
5126 gimple phi = create_phi_node (use, exit);
5128 create_new_def_for (gimple_phi_result (phi), phi,
5129 gimple_phi_result_ptr (phi));
5130 add_phi_arg (phi, use, false_e);
5131 add_phi_arg (phi, use, true_e);
5134 /* Add phi nodes for VAR that is used in LIVEIN. Phi nodes are
5135 inserted in block BB. */
5138 scop_add_exit_phis_var (basic_block bb, tree var, bitmap livein,
5139 edge false_e, edge true_e)
5142 basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (var));
5144 if (is_gimple_reg (var))
5145 bitmap_clear_bit (livein, def_bb->index);
5147 bitmap_set_bit (livein, def_bb->index);
5149 def = BITMAP_ALLOC (NULL);
5150 bitmap_set_bit (def, def_bb->index);
5151 compute_global_livein (livein, def);
5154 scop_add_exit_phis_edge (bb, var, false_e, true_e);
5157 /* Insert in the block BB phi nodes for variables defined in REGION
5158 and used outside the REGION. The code generation moves REGION in
5159 the else clause of an "if (1)" and generates code in the then
5160 clause that is at this point empty:
5169 scop_insert_phis_for_liveouts (sese region, basic_block bb,
5170 edge false_e, edge true_e)
5175 update_ssa (TODO_update_ssa);
5177 EXECUTE_IF_SET_IN_BITMAP (SESE_LIVEOUT (region), 0, i, bi)
5178 scop_add_exit_phis_var (bb, ssa_name (i), SESE_LIVEIN_VER (region, i),
5181 update_ssa (TODO_update_ssa);
5184 /* Get the definition of NAME before the SCOP. Keep track of the
5185 basic blocks that have been VISITED in a bitmap. */
5188 get_vdef_before_scop (scop_p scop, tree name, sbitmap visited)
5191 gimple def_stmt = SSA_NAME_DEF_STMT (name);
5192 basic_block def_bb = gimple_bb (def_stmt);
5195 || !bb_in_sese_p (def_bb, SCOP_REGION (scop)))
5198 if (TEST_BIT (visited, def_bb->index))
5201 SET_BIT (visited, def_bb->index);
5203 switch (gimple_code (def_stmt))
5206 for (i = 0; i < gimple_phi_num_args (def_stmt); i++)
5208 tree arg = gimple_phi_arg_def (def_stmt, i);
5209 tree res = get_vdef_before_scop (scop, arg, visited);
5220 /* Adjust a virtual phi node PHI that is placed at the end of the
5221 generated code for SCOP:
5224 | generated code from REGION;
5228 The FALSE_E edge comes from the original code, TRUE_E edge comes
5229 from the code generated for the SCOP. */
5232 scop_adjust_vphi (scop_p scop, gimple phi, edge true_e)
5236 gcc_assert (gimple_phi_num_args (phi) == 2);
5238 for (i = 0; i < gimple_phi_num_args (phi); i++)
5239 if (gimple_phi_arg_edge (phi, i) == true_e)
5241 tree true_arg, false_arg, before_scop_arg;
5244 true_arg = gimple_phi_arg_def (phi, i);
5245 if (!SSA_NAME_IS_DEFAULT_DEF (true_arg))
5248 false_arg = gimple_phi_arg_def (phi, i == 0 ? 1 : 0);
5249 if (SSA_NAME_IS_DEFAULT_DEF (false_arg))
5252 visited = sbitmap_alloc (last_basic_block);
5253 sbitmap_zero (visited);
5254 before_scop_arg = get_vdef_before_scop (scop, false_arg, visited);
5255 gcc_assert (before_scop_arg != NULL_TREE);
5256 SET_PHI_ARG_DEF (phi, i, before_scop_arg);
5257 sbitmap_free (visited);
5261 /* Adjusts the phi nodes in the block BB for variables defined in
5262 SCOP_REGION and used outside the SCOP_REGION. The code generation
5263 moves SCOP_REGION in the else clause of an "if (1)" and generates
5264 code in the then clause:
5267 | generated code from REGION;
5271 To adjust the phi nodes after the condition, SCOP_LIVEOUT_RENAMES
5272 hash table is used: this stores for a name that is part of the
5273 LIVEOUT of SCOP_REGION its new name in the generated code. */
5276 scop_adjust_phis_for_liveouts (scop_p scop, basic_block bb, edge false_e,
5279 gimple_stmt_iterator si;
5281 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
5284 unsigned false_i = 0;
5285 gimple phi = gsi_stmt (si);
5287 if (!is_gimple_reg (PHI_RESULT (phi)))
5289 scop_adjust_vphi (scop, phi, true_e);
5293 for (i = 0; i < gimple_phi_num_args (phi); i++)
5294 if (gimple_phi_arg_edge (phi, i) == false_e)
5300 for (i = 0; i < gimple_phi_num_args (phi); i++)
5301 if (gimple_phi_arg_edge (phi, i) == true_e)
5303 tree old_name = gimple_phi_arg_def (phi, false_i);
5304 tree new_name = get_new_name_from_old_name
5305 (SCOP_LIVEOUT_RENAMES (scop), old_name);
5307 gcc_assert (old_name != new_name);
5308 SET_PHI_ARG_DEF (phi, i, new_name);
5313 /* Returns the first cloog name used in EXPR. */
5316 find_cloog_iv_in_expr (struct clast_expr *expr)
5318 struct clast_term *term = (struct clast_term *) expr;
5320 if (expr->type == expr_term
5324 if (expr->type == expr_term)
5327 if (expr->type == expr_red)
5330 struct clast_reduction *red = (struct clast_reduction *) expr;
5332 for (i = 0; i < red->n; i++)
5334 const char *res = find_cloog_iv_in_expr ((red)->elts[i]);
5344 /* Build for a clast_user_stmt USER_STMT a map between the CLAST
5345 induction variables and the corresponding GCC old induction
5346 variables. This information is stored on each GRAPHITE_BB. */
5349 compute_cloog_iv_types_1 (graphite_bb_p gbb,
5350 struct clast_user_stmt *user_stmt)
5352 struct clast_stmt *t;
5355 for (t = user_stmt->substitutions; t; t = t->next, index++)
5358 struct ivtype_map_elt tmp;
5359 struct clast_expr *expr = (struct clast_expr *)
5360 ((struct clast_assignment *)t)->RHS;
5362 /* Create an entry (clast_var, type). */
5363 tmp.cloog_iv = find_cloog_iv_in_expr (expr);
5367 slot = htab_find_slot (GBB_CLOOG_IV_TYPES (gbb), &tmp, INSERT);
5371 loop_p loop = gbb_loop_at_index (gbb, index);
5372 tree oldiv = oldiv_for_loop (GBB_SCOP (gbb), loop);
5373 tree type = oldiv ? TREE_TYPE (oldiv) : integer_type_node;
5374 *slot = new_ivtype_map_elt (tmp.cloog_iv, type);
5379 /* Walk the CLAST tree starting from STMT and build for each
5380 clast_user_stmt a map between the CLAST induction variables and the
5381 corresponding GCC old induction variables. This information is
5382 stored on each GRAPHITE_BB. */
5385 compute_cloog_iv_types (struct clast_stmt *stmt)
5390 if (CLAST_STMT_IS_A (stmt, stmt_root))
5393 if (CLAST_STMT_IS_A (stmt, stmt_user))
5395 CloogStatement *cs = ((struct clast_user_stmt *) stmt)->statement;
5396 graphite_bb_p gbb = (graphite_bb_p) cloog_statement_usr (cs);
5397 GBB_CLOOG_IV_TYPES (gbb) = htab_create (10, ivtype_map_elt_info,
5398 eq_ivtype_map_elts, free);
5399 compute_cloog_iv_types_1 (gbb, (struct clast_user_stmt *) stmt);
5403 if (CLAST_STMT_IS_A (stmt, stmt_for))
5405 struct clast_stmt *s = ((struct clast_for *) stmt)->body;
5406 compute_cloog_iv_types (s);
5410 if (CLAST_STMT_IS_A (stmt, stmt_guard))
5412 struct clast_stmt *s = ((struct clast_guard *) stmt)->then;
5413 compute_cloog_iv_types (s);
5417 if (CLAST_STMT_IS_A (stmt, stmt_block))
5419 struct clast_stmt *s = ((struct clast_block *) stmt)->body;
5420 compute_cloog_iv_types (s);
5427 compute_cloog_iv_types (stmt->next);
5430 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
5431 the given SCOP. Return true if code generation succeeded. */
5434 gloog (scop_p scop, struct clast_stmt *stmt)
5436 edge new_scop_exit_edge = NULL;
5437 VEC (iv_stack_entry_p, heap) *ivstack = VEC_alloc (iv_stack_entry_p, heap,
5439 loop_p context_loop;
5440 ifsese if_region = NULL;
5442 recompute_all_dominators ();
5444 if_region = move_sese_in_condition (SCOP_REGION (scop));
5445 sese_build_livein_liveouts (SCOP_REGION (scop));
5446 scop_insert_phis_for_liveouts (SCOP_REGION (scop),
5447 if_region->region->exit->src,
5448 if_region->false_region->exit,
5449 if_region->true_region->exit);
5450 recompute_all_dominators ();
5452 context_loop = SESE_ENTRY (SCOP_REGION (scop))->src->loop_father;
5453 compute_cloog_iv_types (stmt);
5455 new_scop_exit_edge = translate_clast (scop, context_loop, stmt,
5456 if_region->true_region->entry,
5458 free_loop_iv_stack (&ivstack);
5459 cloog_clast_free (stmt);
5462 scop_adjust_phis_for_liveouts (scop,
5463 if_region->region->exit->src,
5464 if_region->false_region->exit,
5465 if_region->true_region->exit);
5467 recompute_all_dominators ();
5472 /* Returns the number of data references in SCOP. */
5475 nb_data_refs_in_scop (scop_p scop)
5481 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gbb); i++)
5482 res += VEC_length (data_reference_p, GBB_DATA_REFS (gbb));
5487 /* Move the loop at index LOOP and insert it before index NEW_LOOP_POS.
5488 This transformartion is only valid, if the loop nest between i and k is
5489 perfectly nested. Therefore we do not need to change the static schedule.
5493 for (i = 0; i < 50; i++)
5495 for (k = 5; k < 100; k++)
5498 To move k before i use:
5500 graphite_trans_bb_move_loop (A, 2, 0)
5502 for (k = 5; k < 100; k++)
5503 for (i = 0; i < 50; i++)
5509 graphite_trans_bb_move_loop (A, 0, 2)
5511 This function does not check the validity of interchanging loops.
5512 This should be checked before calling this function. */
5515 graphite_trans_bb_move_loop (graphite_bb_p gb, int loop,
5518 CloogMatrix *domain = GBB_DOMAIN (gb);
5522 gcc_assert (loop < gbb_nb_loops (gb)
5523 && new_loop_pos < gbb_nb_loops (gb));
5525 /* Update LOOPS vector. */
5526 tmp_loop_p = VEC_index (loop_p, GBB_LOOPS (gb), loop);
5527 VEC_ordered_remove (loop_p, GBB_LOOPS (gb), loop);
5528 VEC_safe_insert (loop_p, heap, GBB_LOOPS (gb), new_loop_pos, tmp_loop_p);
5530 /* Move the domain columns. */
5531 if (loop < new_loop_pos)
5532 for (row = 0; row < domain->NbRows; row++)
5536 value_assign (tmp, domain->p[row][loop + 1]);
5538 for (j = loop ; j < new_loop_pos - 1; j++)
5539 value_assign (domain->p[row][j + 1], domain->p[row][j + 2]);
5541 value_assign (domain->p[row][new_loop_pos], tmp);
5545 for (row = 0; row < domain->NbRows; row++)
5549 value_assign (tmp, domain->p[row][loop + 1]);
5551 for (j = loop ; j > new_loop_pos; j--)
5552 value_assign (domain->p[row][j + 1], domain->p[row][j]);
5554 value_assign (domain->p[row][new_loop_pos + 1], tmp);
5559 /* Get the index of the column representing constants in the DOMAIN
5563 const_column_index (CloogMatrix *domain)
5565 return domain->NbColumns - 1;
5569 /* Get the first index that is positive or negative, determined
5570 following the value of POSITIVE, in matrix DOMAIN in COLUMN. */
5573 get_first_matching_sign_row_index (CloogMatrix *domain, int column,
5578 for (row = 0; row < domain->NbRows; row++)
5580 int val = value_get_si (domain->p[row][column]);
5582 if (val > 0 && positive)
5585 else if (val < 0 && !positive)
5592 /* Get the lower bound of COLUMN in matrix DOMAIN. */
5595 get_lower_bound_row (CloogMatrix *domain, int column)
5597 return get_first_matching_sign_row_index (domain, column, true);
5600 /* Get the upper bound of COLUMN in matrix DOMAIN. */
5603 get_upper_bound_row (CloogMatrix *domain, int column)
5605 return get_first_matching_sign_row_index (domain, column, false);
5608 /* Copies the OLD_ROW constraint from OLD_DOMAIN to the NEW_DOMAIN at
5612 copy_constraint (CloogMatrix *old_domain, CloogMatrix *new_domain,
5613 int old_row, int new_row)
5617 gcc_assert (old_domain->NbColumns == new_domain->NbColumns
5618 && old_row < old_domain->NbRows
5619 && new_row < new_domain->NbRows);
5621 for (i = 0; i < old_domain->NbColumns; i++)
5622 value_assign (new_domain->p[new_row][i], old_domain->p[old_row][i]);
5625 /* Swap coefficients of variables X and Y on row R. */
5628 swap_constraint_variables (CloogMatrix *domain,
5629 int r, int x, int y)
5631 value_swap (domain->p[r][x], domain->p[r][y]);
5634 /* Scale by X the coefficient C of constraint at row R in DOMAIN. */
5637 scale_constraint_variable (CloogMatrix *domain,
5638 int r, int c, int x)
5640 Value strip_size_value;
5641 value_init (strip_size_value);
5642 value_set_si (strip_size_value, x);
5643 value_multiply (domain->p[r][c], domain->p[r][c], strip_size_value);
5644 value_clear (strip_size_value);
5647 /* Strip mines the loop of BB at the position LOOP_DEPTH with STRIDE.
5648 Always valid, but not always a performance improvement. */
5651 graphite_trans_bb_strip_mine (graphite_bb_p gb, int loop_depth, int stride)
5655 CloogMatrix *domain = GBB_DOMAIN (gb);
5656 CloogMatrix *new_domain = cloog_matrix_alloc (domain->NbRows + 3,
5657 domain->NbColumns + 1);
5659 int col_loop_old = loop_depth + 2;
5660 int col_loop_strip = col_loop_old - 1;
5662 gcc_assert (loop_depth <= gbb_nb_loops (gb) - 1);
5664 VEC_safe_insert (loop_p, heap, GBB_LOOPS (gb), loop_depth, NULL);
5666 GBB_DOMAIN (gb) = new_domain;
5668 for (row = 0; row < domain->NbRows; row++)
5669 for (col = 0; col < domain->NbColumns; col++)
5670 if (col <= loop_depth)
5671 value_assign (new_domain->p[row][col], domain->p[row][col]);
5673 value_assign (new_domain->p[row][col + 1], domain->p[row][col]);
5675 row = domain->NbRows;
5677 /* Lower bound of the outer stripped loop. */
5678 copy_constraint (new_domain, new_domain,
5679 get_lower_bound_row (new_domain, col_loop_old), row);
5680 swap_constraint_variables (new_domain, row, col_loop_old, col_loop_strip);
5683 /* Upper bound of the outer stripped loop. */
5684 copy_constraint (new_domain, new_domain,
5685 get_upper_bound_row (new_domain, col_loop_old), row);
5686 swap_constraint_variables (new_domain, row, col_loop_old, col_loop_strip);
5687 scale_constraint_variable (new_domain, row, col_loop_strip, stride);
5690 /* Lower bound of a tile starts at "stride * outer_iv". */
5691 row = get_lower_bound_row (new_domain, col_loop_old);
5692 value_set_si (new_domain->p[row][0], 1);
5693 value_set_si (new_domain->p[row][const_column_index (new_domain)], 0);
5694 value_set_si (new_domain->p[row][col_loop_old], 1);
5695 value_set_si (new_domain->p[row][col_loop_strip], -1 * stride);
5697 /* Upper bound of a tile stops at "stride * outer_iv + stride - 1",
5698 or at the old upper bound that is not modified. */
5699 row = new_domain->NbRows - 1;
5700 value_set_si (new_domain->p[row][0], 1);
5701 value_set_si (new_domain->p[row][col_loop_old], -1);
5702 value_set_si (new_domain->p[row][col_loop_strip], stride);
5703 value_set_si (new_domain->p[row][const_column_index (new_domain)],
5706 cloog_matrix_free (domain);
5708 /* Update static schedule. */
5711 int nb_loops = gbb_nb_loops (gb);
5712 lambda_vector new_schedule = lambda_vector_new (nb_loops + 1);
5714 for (i = 0; i <= loop_depth; i++)
5715 new_schedule[i] = GBB_STATIC_SCHEDULE (gb)[i];
5717 for (i = loop_depth + 1; i <= nb_loops - 2; i++)
5718 new_schedule[i + 2] = GBB_STATIC_SCHEDULE (gb)[i];
5720 GBB_STATIC_SCHEDULE (gb) = new_schedule;
5724 /* Returns true when the strip mining of LOOP_INDEX by STRIDE is
5725 profitable or undecidable. GB is the statement around which the
5726 loops will be strip mined. */
5729 strip_mine_profitable_p (graphite_bb_p gb, int stride,
5738 loop = VEC_index (loop_p, GBB_LOOPS (gb), loop_index);
5739 exit = single_exit (loop);
5741 niter = find_loop_niter (loop, &exit);
5742 if (niter == chrec_dont_know
5743 || TREE_CODE (niter) != INTEGER_CST)
5746 niter_val = int_cst_value (niter);
5748 if (niter_val < stride)
5751 if (dump_file && (dump_flags & TDF_DETAILS))
5753 fprintf (dump_file, "\nStrip Mining is not profitable for loop %d:",
5755 fprintf (dump_file, "number of iterations is too low.\n");
5762 /* Determines when the interchange of LOOP_A and LOOP_B belonging to
5763 SCOP is legal. DEPTH is the number of loops around. */
5766 is_interchange_valid (scop_p scop, int loop_a, int loop_b, int depth)
5769 VEC (ddr_p, heap) *dependence_relations;
5770 VEC (data_reference_p, heap) *datarefs;
5772 struct loop *nest = VEC_index (loop_p, SCOP_LOOP_NEST (scop), loop_a);
5773 lambda_trans_matrix trans;
5775 gcc_assert (loop_a < loop_b);
5777 dependence_relations = VEC_alloc (ddr_p, heap, 10 * 10);
5778 datarefs = VEC_alloc (data_reference_p, heap, 10);
5780 if (!compute_data_dependences_for_loop (nest, true, &datarefs,
5781 &dependence_relations))
5784 if (dump_file && (dump_flags & TDF_DETAILS))
5785 dump_ddrs (dump_file, dependence_relations);
5787 trans = lambda_trans_matrix_new (depth, depth);
5788 lambda_matrix_id (LTM_MATRIX (trans), depth);
5790 lambda_matrix_row_exchange (LTM_MATRIX (trans), 0, loop_b - loop_a);
5792 if (!lambda_transform_legal_p (trans, depth, dependence_relations))
5794 lambda_matrix_row_exchange (LTM_MATRIX (trans), 0, loop_b - loop_a);
5800 free_dependence_relations (dependence_relations);
5801 free_data_refs (datarefs);
5805 /* Loop block the LOOPS innermost loops of GB with stride size STRIDE.
5809 for (i = 0; i <= 50; i++=4)
5810 for (k = 0; k <= 100; k++=4)
5811 for (l = 0; l <= 200; l++=4)
5814 To strip mine the two inner most loops with stride = 4 call:
5816 graphite_trans_bb_block (A, 4, 2)
5818 for (i = 0; i <= 50; i++)
5819 for (kk = 0; kk <= 100; kk+=4)
5820 for (ll = 0; ll <= 200; ll+=4)
5821 for (k = kk; k <= min (100, kk + 3); k++)
5822 for (l = ll; l <= min (200, ll + 3); l++)
5827 graphite_trans_bb_block (graphite_bb_p gb, int stride, int loops)
5830 int nb_loops = gbb_nb_loops (gb);
5831 int start = nb_loops - loops;
5832 scop_p scop = GBB_SCOP (gb);
5834 gcc_assert (scop_contains_loop (scop, gbb_loop (gb)));
5836 for (i = start ; i < nb_loops; i++)
5837 for (j = i + 1; j < nb_loops; j++)
5838 if (!is_interchange_valid (scop, i, j, nb_loops))
5840 if (dump_file && (dump_flags & TDF_DETAILS))
5842 "\nInterchange not valid for loops %d and %d:\n", i, j);
5845 else if (dump_file && (dump_flags & TDF_DETAILS))
5847 "\nInterchange valid for loops %d and %d:\n", i, j);
5849 /* Check if strip mining is profitable for every loop. */
5850 for (i = 0; i < nb_loops - start; i++)
5851 if (!strip_mine_profitable_p (gb, stride, start + i))
5854 /* Strip mine loops. */
5855 for (i = 0; i < nb_loops - start; i++)
5856 graphite_trans_bb_strip_mine (gb, start + 2 * i, stride);
5858 /* Interchange loops. */
5859 for (i = 1; i < nb_loops - start; i++)
5860 graphite_trans_bb_move_loop (gb, start + 2 * i, start + i);
5862 if (dump_file && (dump_flags & TDF_DETAILS))
5863 fprintf (dump_file, "\nLoops containing BB %d will be loop blocked.\n",
5864 GBB_BB (gb)->index);
5869 /* Loop block LOOPS innermost loops of a loop nest. BBS represent the
5870 basic blocks that belong to the loop nest to be blocked. */
5873 graphite_trans_loop_block (VEC (graphite_bb_p, heap) *bbs, int loops)
5877 bool transform_done = false;
5879 /* TODO: - Calculate the stride size automatically. */
5880 int stride_size = 64;
5882 for (i = 0; VEC_iterate (graphite_bb_p, bbs, i, gb); i++)
5883 transform_done |= graphite_trans_bb_block (gb, stride_size, loops);
5885 return transform_done;
5888 /* Loop block all basic blocks of SCOP. Return false when the
5889 transform is not performed. */
5892 graphite_trans_scop_block (scop_p scop)
5898 bool perfect = true;
5899 bool transform_done = false;
5901 VEC (graphite_bb_p, heap) *bbs = VEC_alloc (graphite_bb_p, heap, 3);
5902 int max_schedule = scop_max_loop_depth (scop) + 1;
5903 lambda_vector last_schedule = lambda_vector_new (max_schedule);
5905 if (VEC_length (graphite_bb_p, SCOP_BBS (scop)) == 0)
5908 /* Get the data of the first bb. */
5909 gb = VEC_index (graphite_bb_p, SCOP_BBS (scop), 0);
5910 last_nb_loops = gbb_nb_loops (gb);
5911 lambda_vector_copy (GBB_STATIC_SCHEDULE (gb), last_schedule,
5913 VEC_safe_push (graphite_bb_p, heap, bbs, gb);
5915 for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
5917 /* We did the first bb before. */
5921 nb_loops = gbb_nb_loops (gb);
5923 /* If the number of loops is unchanged and only the last element of the
5924 schedule changes, we stay in the loop nest. */
5925 if (nb_loops == last_nb_loops
5926 && (last_schedule [nb_loops + 1]
5927 != GBB_STATIC_SCHEDULE (gb)[nb_loops + 1]))
5929 VEC_safe_push (graphite_bb_p, heap, bbs, gb);
5933 /* Otherwise, we left the innermost loop. So check, if the last bb was in
5934 a perfect loop nest and how many loops are contained in this perfect
5937 Count the number of zeros from the end of the schedule. They are the
5938 number of surrounding loops.
5941 last_bb 2 3 2 0 0 0 0 3
5945 last_bb 2 3 2 0 0 0 0 3
5949 If there is no zero, there were other bbs in outer loops and the loop
5950 nest is not perfect. */
5951 for (j = last_nb_loops - 1; j >= 0; j--)
5953 if (last_schedule [j] != 0
5954 || (j <= nb_loops && GBB_STATIC_SCHEDULE (gb)[j] == 1))
5963 /* Found perfect loop nest. */
5964 if (perfect && last_nb_loops - j >= 2)
5965 transform_done |= graphite_trans_loop_block (bbs, last_nb_loops - j);
5967 /* Check if we start with a new loop.
5971 last_bb 2 3 2 0 0 0 0 3
5974 Here we start with the loop "2 3 2 0 0 1"
5976 last_bb 2 3 2 0 0 0 0 3
5979 But here not, so the loop nest can never be perfect. */
5981 perfect = (GBB_STATIC_SCHEDULE (gb)[nb_loops] == 0);
5983 /* Update the last_bb infos. We do not do that for the bbs in the same
5984 loop, as the data we use is not changed. */
5985 last_nb_loops = nb_loops;
5986 lambda_vector_copy (GBB_STATIC_SCHEDULE (gb), last_schedule,
5988 VEC_truncate (graphite_bb_p, bbs, 0);
5989 VEC_safe_push (graphite_bb_p, heap, bbs, gb);
5992 /* Check if the last loop nest was perfect. It is the same check as above,
5993 but the comparison with the next bb is missing. */
5994 for (j = last_nb_loops - 1; j >= 0; j--)
5995 if (last_schedule [j] != 0)
6003 /* Found perfect loop nest. */
6004 if (last_nb_loops - j >= 2)
6005 transform_done |= graphite_trans_loop_block (bbs, last_nb_loops - j);
6006 VEC_free (graphite_bb_p, heap, bbs);
6008 return transform_done;
6011 /* Apply graphite transformations to all the basic blocks of SCOP. */
6014 graphite_apply_transformations (scop_p scop)
6016 bool transform_done = false;
6018 /* Sort the list of bbs. Keep them always sorted. */
6019 graphite_sort_gbbs (scop);
6021 if (flag_loop_block)
6022 transform_done = graphite_trans_scop_block (scop);
6024 /* Generate code even if we did not apply any real transformation.
6025 This also allows to check the performance for the identity
6026 transformation: GIMPLE -> GRAPHITE -> GIMPLE
6027 Keep in mind that CLooG optimizes in control, so the loop structure
6028 may change, even if we only use -fgraphite-identity. */
6029 if (flag_graphite_identity)
6030 transform_done = true;
6032 return transform_done;
6035 /* We limit all SCoPs to SCoPs, that are completely surrounded by a loop.
6045 * SCoP frontier, as this line is not surrounded by any loop. *
6049 This is necessary as scalar evolution and parameter detection need a
6050 outermost loop to initialize parameters correctly.
6052 TODO: FIX scalar evolution and parameter detection to allow more flexible
6058 VEC (sd_region, heap) *tmp_scops = VEC_alloc (sd_region, heap, 3);
6063 for (i = 0; VEC_iterate (scop_p, current_scops, i, scop); i++)
6067 build_scop_bbs (scop);
6069 if (!build_scop_loop_nests (scop))
6072 for (j = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), j, loop); j++)
6073 if (!loop_in_sese_p (loop_outer (loop), SCOP_REGION (scop)))
6075 sd_region open_scop;
6076 open_scop.entry = loop->header;
6077 open_scop.exit = single_exit (loop)->dest;
6078 VEC_safe_push (sd_region, heap, tmp_scops, &open_scop);
6082 free_scops (current_scops);
6083 current_scops = VEC_alloc (scop_p, heap, 3);
6085 create_sese_edges (tmp_scops);
6086 build_graphite_scops (tmp_scops);
6087 VEC_free (sd_region, heap, tmp_scops);
6090 /* Perform a set of linear transforms on the loops of the current
6094 graphite_transform_loops (void)
6098 bool transform_done = false;
6100 if (number_of_loops () <= 1)
6103 current_scops = VEC_alloc (scop_p, heap, 3);
6104 recompute_all_dominators ();
6106 if (dump_file && (dump_flags & TDF_DETAILS))
6107 fprintf (dump_file, "Graphite loop transformations \n");
6109 initialize_original_copy_tables ();
6110 cloog_initialize ();
6114 if (dump_file && (dump_flags & TDF_DETAILS))
6115 fprintf (dump_file, "\nnumber of SCoPs: %d\n",
6116 VEC_length (scop_p, current_scops));
6118 for (i = 0; VEC_iterate (scop_p, current_scops, i, scop); i++)
6120 build_scop_bbs (scop);
6121 if (!build_scop_loop_nests (scop))
6124 build_bb_loops (scop);
6126 if (!build_scop_conditions (scop))
6129 find_scop_parameters (scop);
6130 build_scop_context (scop);
6132 if (dump_file && (dump_flags & TDF_DETAILS))
6134 fprintf (dump_file, "\n(In SCoP %d:\n", i);
6135 fprintf (dump_file, "\nnumber of bbs: %d\n",
6136 VEC_length (graphite_bb_p, SCOP_BBS (scop)));
6137 fprintf (dump_file, "\nnumber of loops: %d)\n",
6138 VEC_length (loop_p, SCOP_LOOP_NEST (scop)));
6141 if (!build_scop_iteration_domain (scop))
6144 add_conditions_to_constraints (scop);
6145 build_scop_canonical_schedules (scop);
6147 build_scop_data_accesses (scop);
6148 build_scop_dynamic_schedules (scop);
6150 if (dump_file && (dump_flags & TDF_DETAILS))
6152 int nbrefs = nb_data_refs_in_scop (scop);
6153 fprintf (dump_file, "\nnumber of data refs: %d\n", nbrefs);
6156 if (graphite_apply_transformations (scop))
6157 transform_done = gloog (scop, find_transform (scop));
6158 #ifdef ENABLE_CHECKING
6161 struct clast_stmt *stmt = find_transform (scop);
6162 cloog_clast_free (stmt);
6169 cleanup_tree_cfg ();
6171 free_scops (current_scops);
6173 free_original_copy_tables ();
6176 #else /* If Cloog is not available: #ifndef HAVE_cloog. */
6179 graphite_transform_loops (void)
6181 sorry ("Graphite loop optimizations cannot be used");