X-Git-Url: http://git.sourceforge.jp/view?p=pf3gnuchains%2Fgcc-fork.git;a=blobdiff_plain;f=gcc%2Fgraphite.c;h=b013447443f009154512419000c64f5fe98b8355;hp=645def2b8a7c57464b1cdc86a4f7da6c0b4937b0;hb=169d9eaf8c2d0c0f34b48dc474facc1c53546385;hpb=145bdf6a06711b00172139f310997813a7529d8c diff --git a/gcc/graphite.c b/gcc/graphite.c index 645def2b8a7..b013447443f 100644 --- a/gcc/graphite.c +++ b/gcc/graphite.c @@ -1,5 +1,5 @@ /* Gimple Represented as Polyhedra. - Copyright (C) 2006, 2007, 2008 Free Software Foundation, Inc. + Copyright (C) 2006, 2007, 2008, 2009, 2010 Free Software Foundation, Inc. Contributed by Sebastian Pop . This file is part of GCC. @@ -20,12 +20,12 @@ along with GCC; see the file COPYING3. If not see /* This pass converts GIMPLE to GRAPHITE, performs some loop transformations and then converts the resulting representation back - to GIMPLE. + to GIMPLE. An early description of this pass can be found in the GCC Summit'06 paper "GRAPHITE: Polyhedral Analyses and Optimizations for GCC". The wiki page http://gcc.gnu.org/wiki/Graphite contains pointers to - the related work. + the related work. One important document to read is CLooG's internal manual: http://repo.or.cz/w/cloog-ppl.git?a=blob_plain;f=doc/cloog.texi;hb=HEAD @@ -35,5993 +35,210 @@ along with GCC; see the file COPYING3. If not see #include "config.h" #include "system.h" #include "coretypes.h" -#include "tm.h" -#include "ggc.h" -#include "tree.h" -#include "rtl.h" -#include "basic-block.h" -#include "diagnostic.h" +#include "diagnostic-core.h" #include "tree-flow.h" -#include "toplev.h" #include "tree-dump.h" -#include "timevar.h" #include "cfgloop.h" #include "tree-chrec.h" #include "tree-data-ref.h" #include "tree-scalar-evolution.h" -#include "tree-pass.h" -#include "domwalk.h" -#include "value-prof.h" -#include "pointer-set.h" -#include "gimple.h" +#include "sese.h" +#include "dbgcnt.h" #ifdef HAVE_cloog -#include "cloog/cloog.h" -#include "graphite.h" -static VEC (scop_p, heap) *current_scops; +#include "ppl_c.h" +#include "graphite-ppl.h" +#include "graphite-poly.h" +#include "graphite-scop-detection.h" +#include "graphite-clast-to-gimple.h" +#include "graphite-sese-to-poly.h" -/* Converts a GMP constant V to a tree and returns it. */ +CloogState *cloog_state; -static tree -gmp_cst_to_tree (tree type, Value v) -{ - return build_int_cst (type, value_get_si (v)); -} - -/* Debug the list of old induction variables for this SCOP. */ - -void -debug_oldivs (scop_p scop) -{ - int i; - name_tree oldiv; - - fprintf (stderr, "Old IVs:"); - - for (i = 0; VEC_iterate (name_tree, SCOP_OLDIVS (scop), i, oldiv); i++) - { - fprintf (stderr, "("); - print_generic_expr (stderr, oldiv->t, 0); - fprintf (stderr, ", %s, %d)\n", oldiv->name, oldiv->loop->num); - } - fprintf (stderr, "\n"); -} - -/* Debug the loops around basic block GB. */ - -void -debug_loop_vec (graphite_bb_p gb) -{ - int i; - loop_p loop; - - fprintf (stderr, "Loop Vec:"); - - for (i = 0; VEC_iterate (loop_p, GBB_LOOPS (gb), i, loop); i++) - fprintf (stderr, "%d: %d, ", i, loop ? loop->num : -1); - - fprintf (stderr, "\n"); -} - -/* Returns true if stack ENTRY is a constant. */ - -static bool -iv_stack_entry_is_constant (iv_stack_entry *entry) -{ - return entry->kind == iv_stack_entry_const; -} - -/* Returns true if stack ENTRY is an induction variable. */ - -static bool -iv_stack_entry_is_iv (iv_stack_entry *entry) -{ - return entry->kind == iv_stack_entry_iv; -} - -/* Push (IV, NAME) on STACK. */ - -static void -loop_iv_stack_push_iv (loop_iv_stack stack, tree iv, const char *name) -{ - iv_stack_entry *entry = XNEW (iv_stack_entry); - name_tree named_iv = XNEW (struct name_tree); - - named_iv->t = iv; - named_iv->name = name; - - entry->kind = iv_stack_entry_iv; - entry->data.iv = named_iv; - - VEC_safe_push (iv_stack_entry_p, heap, *stack, entry); -} - -/* Inserts a CONSTANT in STACK at INDEX. */ - -static void -loop_iv_stack_insert_constant (loop_iv_stack stack, int index, - tree constant) -{ - iv_stack_entry *entry = XNEW (iv_stack_entry); - - entry->kind = iv_stack_entry_const; - entry->data.constant = constant; - - VEC_safe_insert (iv_stack_entry_p, heap, *stack, index, entry); -} - -/* Pops and frees an element out of STACK. */ - -static void -loop_iv_stack_pop (loop_iv_stack stack) -{ - iv_stack_entry_p entry = VEC_pop (iv_stack_entry_p, *stack); - - free (entry->data.iv); - free (entry); -} - -/* Get the IV at INDEX in STACK. */ - -static tree -loop_iv_stack_get_iv (loop_iv_stack stack, int index) -{ - iv_stack_entry_p entry = VEC_index (iv_stack_entry_p, *stack, index); - iv_stack_entry_data data = entry->data; - - return iv_stack_entry_is_iv (entry) ? data.iv->t : data.constant; -} - -/* Get the IV from its NAME in STACK. */ - -static tree -loop_iv_stack_get_iv_from_name (loop_iv_stack stack, const char* name) -{ - int i; - iv_stack_entry_p entry; - - for (i = 0; VEC_iterate (iv_stack_entry_p, *stack, i, entry); i++) - { - name_tree iv = entry->data.iv; - if (!strcmp (name, iv->name)) - return iv->t; - } - - return NULL; -} - -/* Prints on stderr the contents of STACK. */ - -void -debug_loop_iv_stack (loop_iv_stack stack) -{ - int i; - iv_stack_entry_p entry; - bool first = true; - - fprintf (stderr, "("); - - for (i = 0; VEC_iterate (iv_stack_entry_p, *stack, i, entry); i++) - { - if (first) - first = false; - else - fprintf (stderr, " "); - - if (iv_stack_entry_is_iv (entry)) - { - name_tree iv = entry->data.iv; - fprintf (stderr, "%s:", iv->name); - print_generic_expr (stderr, iv->t, 0); - } - else - { - tree constant = entry->data.constant; - print_generic_expr (stderr, constant, 0); - fprintf (stderr, ":"); - print_generic_expr (stderr, constant, 0); - } - } - - fprintf (stderr, ")\n"); -} - -/* Frees STACK. */ - -static void -free_loop_iv_stack (loop_iv_stack stack) -{ - int i; - iv_stack_entry_p entry; - - for (i = 0; VEC_iterate (iv_stack_entry_p, *stack, i, entry); i++) - { - free (entry->data.iv); - free (entry); - } - - VEC_free (iv_stack_entry_p, heap, *stack); -} - - - -/* Structure containing the mapping between the CLooG's induction - variable and the type of the old induction variable. */ -typedef struct ivtype_map_elt -{ - tree type; - const char *cloog_iv; -} *ivtype_map_elt; - -/* Print to stderr the element ELT. */ - -static void -debug_ivtype_elt (ivtype_map_elt elt) -{ - fprintf (stderr, "(%s, ", elt->cloog_iv); - print_generic_expr (stderr, elt->type, 0); - fprintf (stderr, ")\n"); -} - -/* Helper function for debug_ivtype_map. */ - -static int -debug_ivtype_map_1 (void **slot, void *s ATTRIBUTE_UNUSED) -{ - struct ivtype_map_elt *entry = (struct ivtype_map_elt *) *slot; - debug_ivtype_elt (entry); - return 1; -} - -/* Print to stderr all the elements of MAP. */ - -void -debug_ivtype_map (htab_t map) -{ - htab_traverse (map, debug_ivtype_map_1, NULL); -} - -/* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */ - -static inline ivtype_map_elt -new_ivtype_map_elt (const char *cloog_iv, tree type) -{ - ivtype_map_elt res; - - res = XNEW (struct ivtype_map_elt); - res->cloog_iv = cloog_iv; - res->type = type; - - return res; -} - -/* Computes a hash function for database element ELT. */ - -static hashval_t -ivtype_map_elt_info (const void *elt) -{ - return htab_hash_pointer (((const struct ivtype_map_elt *) elt)->cloog_iv); -} - -/* Compares database elements E1 and E2. */ - -static int -eq_ivtype_map_elts (const void *e1, const void *e2) -{ - const struct ivtype_map_elt *elt1 = (const struct ivtype_map_elt *) e1; - const struct ivtype_map_elt *elt2 = (const struct ivtype_map_elt *) e2; - - return (elt1->cloog_iv == elt2->cloog_iv); -} - - - -/* Given a CLOOG_IV, returns the type that it should have in GCC land. - If the information is not available, i.e. in the case one of the - transforms created the loop, just return integer_type_node. */ - -static tree -gcc_type_for_cloog_iv (const char *cloog_iv, graphite_bb_p gbb) -{ - struct ivtype_map_elt tmp; - PTR *slot; - - tmp.cloog_iv = cloog_iv; - slot = htab_find_slot (GBB_CLOOG_IV_TYPES (gbb), &tmp, NO_INSERT); - - if (slot && *slot) - return ((ivtype_map_elt) *slot)->type; - - return integer_type_node; -} - -/* Inserts constants derived from the USER_STMT argument list into the - STACK. This is needed to map old ivs to constants when loops have - been eliminated. */ - -static void -loop_iv_stack_patch_for_consts (loop_iv_stack stack, - struct clast_user_stmt *user_stmt) -{ - struct clast_stmt *t; - int index = 0; - CloogStatement *cs = user_stmt->statement; - graphite_bb_p gbb = (graphite_bb_p) cloog_statement_usr (cs); - - for (t = user_stmt->substitutions; t; t = t->next) - { - struct clast_expr *expr = (struct clast_expr *) - ((struct clast_assignment *)t)->RHS; - struct clast_term *term = (struct clast_term *) expr; - - /* FIXME: What should be done with expr_bin, expr_red? */ - if (expr->type == expr_term - && !term->var) - { - loop_p loop = gbb_loop_at_index (gbb, index); - tree oldiv = oldiv_for_loop (GBB_SCOP (gbb), loop); - tree type = oldiv ? TREE_TYPE (oldiv) : integer_type_node; - tree value = gmp_cst_to_tree (type, term->val); - loop_iv_stack_insert_constant (stack, index, value); - } - index = index + 1; - } -} - -/* Removes all constants in the iv STACK. */ - -static void -loop_iv_stack_remove_constants (loop_iv_stack stack) -{ - int i; - iv_stack_entry *entry; - - for (i = 0; VEC_iterate (iv_stack_entry_p, *stack, i, entry);) - { - if (iv_stack_entry_is_constant (entry)) - { - free (VEC_index (iv_stack_entry_p, *stack, i)); - VEC_ordered_remove (iv_stack_entry_p, *stack, i); - } - else - i++; - } -} - -/* Returns a new loop_to_cloog_loop_str structure. */ - -static inline struct loop_to_cloog_loop_str * -new_loop_to_cloog_loop_str (int loop_num, - int loop_position, - CloogLoop *cloog_loop) -{ - struct loop_to_cloog_loop_str *result; - - result = XNEW (struct loop_to_cloog_loop_str); - result->loop_num = loop_num; - result->cloog_loop = cloog_loop; - result->loop_position = loop_position; - - return result; -} - -/* Hash function for SCOP_LOOP2CLOOG_LOOP hash table. */ - -static hashval_t -hash_loop_to_cloog_loop (const void *elt) -{ - return ((const struct loop_to_cloog_loop_str *) elt)->loop_num; -} - -/* Equality function for SCOP_LOOP2CLOOG_LOOP hash table. */ - -static int -eq_loop_to_cloog_loop (const void *el1, const void *el2) -{ - const struct loop_to_cloog_loop_str *elt1, *elt2; - - elt1 = (const struct loop_to_cloog_loop_str *) el1; - elt2 = (const struct loop_to_cloog_loop_str *) el2; - return elt1->loop_num == elt2->loop_num; -} - -/* Compares two graphite bbs and returns an integer less than, equal to, or - greater than zero if the first argument is considered to be respectively - less than, equal to, or greater than the second. - We compare using the lexicographic order of the static schedules. */ - -static int -gbb_compare (const void *p_1, const void *p_2) -{ - const struct graphite_bb *const gbb_1 - = *(const struct graphite_bb *const*) p_1; - const struct graphite_bb *const gbb_2 - = *(const struct graphite_bb *const*) p_2; - - return lambda_vector_compare (GBB_STATIC_SCHEDULE (gbb_1), - gbb_nb_loops (gbb_1) + 1, - GBB_STATIC_SCHEDULE (gbb_2), - gbb_nb_loops (gbb_2) + 1); -} - -/* Sort graphite bbs in SCOP. */ - -static void -graphite_sort_gbbs (scop_p scop) -{ - VEC (graphite_bb_p, heap) *bbs = SCOP_BBS (scop); - - qsort (VEC_address (graphite_bb_p, bbs), - VEC_length (graphite_bb_p, bbs), - sizeof (graphite_bb_p), gbb_compare); -} - -/* Dump conditions of a graphite basic block GBB on FILE. */ - -static void -dump_gbb_conditions (FILE *file, graphite_bb_p gbb) -{ - int i; - gimple stmt; - VEC (gimple, heap) *conditions = GBB_CONDITIONS (gbb); - - if (VEC_empty (gimple, conditions)) - return; - - fprintf (file, "\tbb %d\t: cond = {", GBB_BB (gbb)->index); - - for (i = 0; VEC_iterate (gimple, conditions, i, stmt); i++) - print_gimple_stmt (file, stmt, 0, 0); - - fprintf (file, "}\n"); -} - -/* Converts the graphite scheduling function into a cloog scattering - matrix. This scattering matrix is used to limit the possible cloog - output to valid programs in respect to the scheduling function. - - SCATTERING_DIMENSIONS specifies the dimensionality of the scattering - matrix. CLooG 0.14.0 and previous versions require, that all scattering - functions of one CloogProgram have the same dimensionality, therefore we - allow to specify it. (Should be removed in future versions) */ - -static CloogMatrix * -schedule_to_scattering (graphite_bb_p gb, int scattering_dimensions) -{ - int i; - scop_p scop = GBB_SCOP (gb); - - int nb_iterators = gbb_nb_loops (gb); - - /* The cloog scattering matrix consists of these colums: - 1 col = Eq/Inq, - scattering_dimensions cols = Scattering dimensions, - nb_iterators cols = bb's iterators, - scop_nb_params cols = Parameters, - 1 col = Constant 1. - - Example: - - scattering_dimensions = 5 - max_nb_iterators = 2 - nb_iterators = 1 - scop_nb_params = 2 - - Schedule: - ? i - 4 5 - - Scattering Matrix: - s1 s2 s3 s4 s5 i p1 p2 1 - 1 0 0 0 0 0 0 0 -4 = 0 - 0 1 0 0 0 -1 0 0 0 = 0 - 0 0 1 0 0 0 0 0 -5 = 0 */ - int nb_params = scop_nb_params (scop); - int nb_cols = 1 + scattering_dimensions + nb_iterators + nb_params + 1; - int col_const = nb_cols - 1; - int col_iter_offset = 1 + scattering_dimensions; - - CloogMatrix *scat = cloog_matrix_alloc (scattering_dimensions, nb_cols); - - gcc_assert (scattering_dimensions >= nb_iterators * 2 + 1); - - /* Initialize the identity matrix. */ - for (i = 0; i < scattering_dimensions; i++) - value_set_si (scat->p[i][i + 1], 1); - - /* Textual order outside the first loop */ - value_set_si (scat->p[0][col_const], -GBB_STATIC_SCHEDULE (gb)[0]); - - /* For all surrounding loops. */ - for (i = 0; i < nb_iterators; i++) - { - int schedule = GBB_STATIC_SCHEDULE (gb)[i + 1]; - - /* Iterations of this loop. */ - value_set_si (scat->p[2 * i + 1][col_iter_offset + i], -1); - - /* Textual order inside this loop. */ - value_set_si (scat->p[2 * i + 2][col_const], -schedule); - } - - return scat; -} - -/* Print the schedules of GB to FILE with INDENT white spaces before. - VERBOSITY determines how verbose the code pretty printers are. */ - -void -print_graphite_bb (FILE *file, graphite_bb_p gb, int indent, int verbosity) -{ - CloogMatrix *scattering; - int i; - loop_p loop; - fprintf (file, "\nGBB (\n"); - - print_loops_bb (file, GBB_BB (gb), indent+2, verbosity); - - if (GBB_DOMAIN (gb)) - { - fprintf (file, " (domain: \n"); - cloog_matrix_print (file, GBB_DOMAIN (gb)); - fprintf (file, " )\n"); - } - - if (GBB_STATIC_SCHEDULE (gb)) - { - fprintf (file, " (static schedule: "); - print_lambda_vector (file, GBB_STATIC_SCHEDULE (gb), - gbb_nb_loops (gb) + 1); - fprintf (file, " )\n"); - } - - if (GBB_LOOPS (gb)) - { - fprintf (file, " (contained loops: \n"); - for (i = 0; VEC_iterate (loop_p, GBB_LOOPS (gb), i, loop); i++) - if (loop == NULL) - fprintf (file, " iterator %d => NULL \n", i); - else - fprintf (file, " iterator %d => loop %d \n", i, - loop->num); - fprintf (file, " )\n"); - } - - if (GBB_DATA_REFS (gb)) - dump_data_references (file, GBB_DATA_REFS (gb)); - - if (GBB_CONDITIONS (gb)) - { - fprintf (file, " (conditions: \n"); - dump_gbb_conditions (file, gb); - fprintf (file, " )\n"); - } - - if (GBB_SCOP (gb) - && GBB_STATIC_SCHEDULE (gb)) - { - fprintf (file, " (scattering: \n"); - scattering = schedule_to_scattering (gb, 2 * gbb_nb_loops (gb) + 1); - cloog_matrix_print (file, scattering); - cloog_matrix_free (scattering); - fprintf (file, " )\n"); - } - - fprintf (file, ")\n"); -} - -/* Print to STDERR the schedules of GB with VERBOSITY level. */ - -void -debug_gbb (graphite_bb_p gb, int verbosity) -{ - print_graphite_bb (stderr, gb, 0, verbosity); -} - - -/* Print SCOP to FILE. VERBOSITY determines how verbose the pretty - printers are. */ - -static void -print_scop (FILE *file, scop_p scop, int verbosity) -{ - if (scop == NULL) - return; - - fprintf (file, "\nSCoP_%d_%d (\n", - SCOP_ENTRY (scop)->index, SCOP_EXIT (scop)->index); - - fprintf (file, " (cloog: \n"); - cloog_program_print (file, SCOP_PROG (scop)); - fprintf (file, " )\n"); - - if (SCOP_BBS (scop)) - { - graphite_bb_p gb; - int i; - - for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++) - print_graphite_bb (file, gb, 0, verbosity); - } - - fprintf (file, ")\n"); -} - -/* Print all the SCOPs to FILE. VERBOSITY determines how verbose the - code pretty printers are. */ - -static void -print_scops (FILE *file, int verbosity) -{ - int i; - scop_p scop; - - for (i = 0; VEC_iterate (scop_p, current_scops, i, scop); i++) - print_scop (file, scop, verbosity); -} - -/* Debug SCOP. VERBOSITY determines how verbose the code pretty - printers are. */ - -void -debug_scop (scop_p scop, int verbosity) -{ - print_scop (stderr, scop, verbosity); -} - -/* Debug all SCOPs from CURRENT_SCOPS. VERBOSITY determines how - verbose the code pretty printers are. */ - -void -debug_scops (int verbosity) -{ - print_scops (stderr, verbosity); -} - -/* Pretty print to FILE the SCOP in DOT format. */ - -static void -dot_scop_1 (FILE *file, scop_p scop) -{ - edge e; - edge_iterator ei; - basic_block bb; - basic_block entry = SCOP_ENTRY (scop); - basic_block exit = SCOP_EXIT (scop); - - fprintf (file, "digraph SCoP_%d_%d {\n", entry->index, - exit->index); - - FOR_ALL_BB (bb) - { - if (bb == entry) - fprintf (file, "%d [shape=triangle];\n", bb->index); - - if (bb == exit) - fprintf (file, "%d [shape=box];\n", bb->index); - - if (bb_in_scop_p (bb, scop)) - fprintf (file, "%d [color=red];\n", bb->index); - - FOR_EACH_EDGE (e, ei, bb->succs) - fprintf (file, "%d -> %d;\n", bb->index, e->dest->index); - } - - fputs ("}\n\n", file); -} - -/* Display SCOP using dotty. */ - -void -dot_scop (scop_p scop) -{ - dot_scop_1 (stderr, scop); -} - -/* Pretty print all SCoPs in DOT format and mark them with different colors. - If there are not enough colors, paint later SCoPs gray. - Special nodes: - - "*" after the node number: entry of a SCoP, - - "#" after the node number: exit of a SCoP, - - "()" entry or exit not part of SCoP. */ - -static void -dot_all_scops_1 (FILE *file) -{ - basic_block bb; - edge e; - edge_iterator ei; - scop_p scop; - const char* color; - int i; - - /* Disable debugging while printing graph. */ - int tmp_dump_flags = dump_flags; - dump_flags = 0; - - fprintf (file, "digraph all {\n"); - - FOR_ALL_BB (bb) - { - int part_of_scop = false; - - /* Use HTML for every bb label. So we are able to print bbs - which are part of two different SCoPs, with two different - background colors. */ - fprintf (file, "%d [label=<\n index); - fprintf (file, "CELLSPACING=\"0\">\n"); - - /* Select color for SCoP. */ - for (i = 0; VEC_iterate (scop_p, current_scops, i, scop); i++) - if (bb_in_scop_p (bb, scop) - || (SCOP_EXIT (scop) == bb) - || (SCOP_ENTRY (scop) == bb)) - { - switch (i % 17) - { - case 0: /* red */ - color = "#e41a1c"; - break; - case 1: /* blue */ - color = "#377eb8"; - break; - case 2: /* green */ - color = "#4daf4a"; - break; - case 3: /* purple */ - color = "#984ea3"; - break; - case 4: /* orange */ - color = "#ff7f00"; - break; - case 5: /* yellow */ - color = "#ffff33"; - break; - case 6: /* brown */ - color = "#a65628"; - break; - case 7: /* rose */ - color = "#f781bf"; - break; - case 8: - color = "#8dd3c7"; - break; - case 9: - color = "#ffffb3"; - break; - case 10: - color = "#bebada"; - break; - case 11: - color = "#fb8072"; - break; - case 12: - color = "#80b1d3"; - break; - case 13: - color = "#fdb462"; - break; - case 14: - color = "#b3de69"; - break; - case 15: - color = "#fccde5"; - break; - case 16: - color = "#bc80bd"; - break; - default: /* gray */ - color = "#999999"; - } - - fprintf (file, " \n"); - part_of_scop = true; - } - - if (!part_of_scop) - { - fprintf (file, " \n", bb->index); - } - - fprintf (file, "
", color); - - if (!bb_in_scop_p (bb, scop)) - fprintf (file, " ("); - - if (bb == SCOP_ENTRY (scop) - && bb == SCOP_EXIT (scop)) - fprintf (file, " %d*# ", bb->index); - else if (bb == SCOP_ENTRY (scop)) - fprintf (file, " %d* ", bb->index); - else if (bb == SCOP_EXIT (scop)) - fprintf (file, " %d# ", bb->index); - else - fprintf (file, " %d ", bb->index); - - if (!bb_in_scop_p (bb, scop)) - fprintf (file, ")"); - - fprintf (file, "
"); - fprintf (file, " %d
>, shape=box, style=\"setlinewidth(0)\"]\n"); - } - - FOR_ALL_BB (bb) - { - FOR_EACH_EDGE (e, ei, bb->succs) - fprintf (file, "%d -> %d;\n", bb->index, e->dest->index); - } - - fputs ("}\n\n", file); - - /* Enable debugging again. */ - dump_flags = tmp_dump_flags; -} - -/* Display all SCoPs using dotty. */ - -void -dot_all_scops (void) -{ - /* When debugging, enable the following code. This cannot be used - in production compilers because it calls "system". */ -#if 0 - FILE *stream = fopen ("/tmp/allscops.dot", "w"); - gcc_assert (stream); - - dot_all_scops_1 (stream); - fclose (stream); - - system ("dotty /tmp/allscops.dot"); -#else - dot_all_scops_1 (stderr); -#endif -} - -/* Returns the outermost loop in SCOP that contains BB. */ - -static struct loop * -outermost_loop_in_scop (scop_p scop, basic_block bb) -{ - struct loop *nest; - - nest = bb->loop_father; - while (loop_outer (nest) && loop_in_scop_p (loop_outer (nest), scop)) - nest = loop_outer (nest); - - return nest; -} - -/* Returns the block preceding the entry of SCOP. */ - -static basic_block -block_before_scop (scop_p scop) -{ - return SESE_ENTRY (SCOP_REGION (scop))->src; -} - -/* Return true when EXPR is an affine function in LOOP with parameters - instantiated relative to SCOP_ENTRY. */ - -static bool -loop_affine_expr (basic_block scop_entry, struct loop *loop, tree expr) -{ - int n = loop->num; - tree scev = analyze_scalar_evolution (loop, expr); - - scev = instantiate_scev (scop_entry, loop, scev); - - return (evolution_function_is_invariant_p (scev, n) - || evolution_function_is_affine_multivariate_p (scev, n)); -} - -/* Return false if the tree_code of the operand OP or any of its operands - is component_ref. */ - -static bool -exclude_component_ref (tree op) -{ - int i; - int len; - - if (op) - { - if (TREE_CODE (op) == COMPONENT_REF) - return false; - else - { - len = TREE_OPERAND_LENGTH (op); - for (i = 0; i < len; ++i) - { - if (!exclude_component_ref (TREE_OPERAND (op, i))) - return false; - } - } - } - - return true; -} - -/* Return true if the operand OP is simple. */ - -static bool -is_simple_operand (loop_p loop, gimple stmt, tree op) -{ - /* It is not a simple operand when it is a declaration, */ - if (DECL_P (op) - /* or a structure, */ - || AGGREGATE_TYPE_P (TREE_TYPE (op)) - /* or a memory access that cannot be analyzed by the data - reference analysis. */ - || ((handled_component_p (op) || INDIRECT_REF_P (op)) - && !stmt_simple_memref_p (loop, stmt, op))) - return false; - - return exclude_component_ref (op); -} - -/* Return true only when STMT is simple enough for being handled by - Graphite. This depends on SCOP_ENTRY, as the parametetrs are - initialized relatively to this basic block. */ - -static bool -stmt_simple_for_scop_p (basic_block scop_entry, gimple stmt) -{ - basic_block bb = gimple_bb (stmt); - struct loop *loop = bb->loop_father; - - /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects. - Calls have side-effects, except those to const or pure - functions. */ - if (gimple_has_volatile_ops (stmt) - || (gimple_code (stmt) == GIMPLE_CALL - && !(gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE))) - || (gimple_code (stmt) == GIMPLE_ASM)) - return false; - - switch (gimple_code (stmt)) - { - case GIMPLE_RETURN: - case GIMPLE_LABEL: - return true; - - case GIMPLE_COND: - { - tree op; - ssa_op_iter op_iter; - enum tree_code code = gimple_cond_code (stmt); - - /* We can only handle this kind of conditional expressions. - For inequalities like "if (i != 3 * k)" we need unions of - polyhedrons. Expressions like "if (a)" or "if (a == 15)" need - them for the else branch. */ - if (!(code == LT_EXPR - || code == GT_EXPR - || code == LE_EXPR - || code == GE_EXPR)) - return false; - - if (!scop_entry) - return false; - - FOR_EACH_SSA_TREE_OPERAND (op, stmt, op_iter, SSA_OP_ALL_USES) - if (!loop_affine_expr (scop_entry, loop, op)) - return false; - - return true; - } - - case GIMPLE_ASSIGN: - { - enum tree_code code = gimple_assign_rhs_code (stmt); - - switch (get_gimple_rhs_class (code)) - { - case GIMPLE_UNARY_RHS: - case GIMPLE_SINGLE_RHS: - return (is_simple_operand (loop, stmt, gimple_assign_lhs (stmt)) - && is_simple_operand (loop, stmt, gimple_assign_rhs1 (stmt))); - - case GIMPLE_BINARY_RHS: - return (is_simple_operand (loop, stmt, gimple_assign_lhs (stmt)) - && is_simple_operand (loop, stmt, gimple_assign_rhs1 (stmt)) - && is_simple_operand (loop, stmt, gimple_assign_rhs2 (stmt))); - - case GIMPLE_INVALID_RHS: - default: - gcc_unreachable (); - } - } - - case GIMPLE_CALL: - { - size_t i; - size_t n = gimple_call_num_args (stmt); - tree lhs = gimple_call_lhs (stmt); - - for (i = 0; i < n; i++) - { - tree arg = gimple_call_arg (stmt, i); - - if (!(is_simple_operand (loop, stmt, lhs) - && is_simple_operand (loop, stmt, arg))) - return false; - } - - return true; - } - - default: - /* These nodes cut a new scope. */ - return false; - } - - return false; -} - -/* Returns the statement of BB that contains a harmful operation: that - can be a function call with side effects, the induction variables - are not linear with respect to SCOP_ENTRY, etc. The current open - scop should end before this statement. */ - -static gimple -harmful_stmt_in_bb (basic_block scop_entry, basic_block bb) -{ - gimple_stmt_iterator gsi; - - for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) - if (!stmt_simple_for_scop_p (scop_entry, gsi_stmt (gsi))) - return gsi_stmt (gsi); - - return NULL; -} - -/* Returns true when BB will be represented in graphite. Return false - for the basic blocks that contain code eliminated in the code - generation pass: i.e. induction variables and exit conditions. */ - -static bool -graphite_stmt_p (scop_p scop, basic_block bb, - VEC (data_reference_p, heap) *drs) -{ - gimple_stmt_iterator gsi; - loop_p loop = bb->loop_father; - - if (VEC_length (data_reference_p, drs) > 0) - return true; - - for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) - { - gimple stmt = gsi_stmt (gsi); - - switch (gimple_code (stmt)) - { - /* Control flow expressions can be ignored, as they are - represented in the iteration domains and will be - regenerated by graphite. */ - case GIMPLE_COND: - case GIMPLE_GOTO: - case GIMPLE_SWITCH: - break; - - case GIMPLE_ASSIGN: - { - tree var = gimple_assign_lhs (stmt); - var = analyze_scalar_evolution (loop, var); - var = instantiate_scev (block_before_scop (scop), loop, var); - - if (chrec_contains_undetermined (var)) - return true; - - break; - } - - default: - return true; - } - } - - return false; -} - -/* Store the GRAPHITE representation of BB. */ - -static void -new_graphite_bb (scop_p scop, basic_block bb) -{ - struct graphite_bb *gbb; - VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 5); - struct loop *nest = outermost_loop_in_scop (scop, bb); - gimple_stmt_iterator gsi; - - bitmap_set_bit (SCOP_BBS_B (scop), bb->index); - - for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) - find_data_references_in_stmt (nest, gsi_stmt (gsi), &drs); - - if (!graphite_stmt_p (scop, bb, drs)) - { - free_data_refs (drs); - return; - } - - gbb = XNEW (struct graphite_bb); - bb->aux = gbb; - GBB_BB (gbb) = bb; - GBB_SCOP (gbb) = scop; - GBB_DATA_REFS (gbb) = drs; - GBB_DOMAIN (gbb) = NULL; - GBB_CONDITIONS (gbb) = NULL; - GBB_CONDITION_CASES (gbb) = NULL; - GBB_LOOPS (gbb) = NULL; - GBB_STATIC_SCHEDULE (gbb) = NULL; - GBB_CLOOG_IV_TYPES (gbb) = NULL; - VEC_safe_push (graphite_bb_p, heap, SCOP_BBS (scop), gbb); -} - -/* Frees GBB. */ - -static void -free_graphite_bb (struct graphite_bb *gbb) -{ - if (GBB_DOMAIN (gbb)) - cloog_matrix_free (GBB_DOMAIN (gbb)); - - if (GBB_CLOOG_IV_TYPES (gbb)) - htab_delete (GBB_CLOOG_IV_TYPES (gbb)); - - /* FIXME: free_data_refs is disabled for the moment, but should be - enabled. - - free_data_refs (GBB_DATA_REFS (gbb)); */ - - VEC_free (gimple, heap, GBB_CONDITIONS (gbb)); - VEC_free (gimple, heap, GBB_CONDITION_CASES (gbb)); - VEC_free (loop_p, heap, GBB_LOOPS (gbb)); - GBB_BB (gbb)->aux = 0; - XDELETE (gbb); -} - - - -/* Structure containing the mapping between the old names and the new - names used after block copy in the new loop context. */ -typedef struct rename_map_elt -{ - tree old_name, new_name; -} *rename_map_elt; - - -/* Print to stderr the element ELT. */ - -static void -debug_rename_elt (rename_map_elt elt) -{ - fprintf (stderr, "("); - print_generic_expr (stderr, elt->old_name, 0); - fprintf (stderr, ", "); - print_generic_expr (stderr, elt->new_name, 0); - fprintf (stderr, ")\n"); -} - -/* Helper function for debug_rename_map. */ - -static int -debug_rename_map_1 (void **slot, void *s ATTRIBUTE_UNUSED) -{ - struct rename_map_elt *entry = (struct rename_map_elt *) *slot; - debug_rename_elt (entry); - return 1; -} - -/* Print to stderr all the elements of MAP. */ - -void -debug_rename_map (htab_t map) -{ - htab_traverse (map, debug_rename_map_1, NULL); -} - -/* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */ - -static inline rename_map_elt -new_rename_map_elt (tree old_name, tree new_name) -{ - rename_map_elt res; - - res = XNEW (struct rename_map_elt); - res->old_name = old_name; - res->new_name = new_name; - - return res; -} - -/* Computes a hash function for database element ELT. */ - -static hashval_t -rename_map_elt_info (const void *elt) -{ - return htab_hash_pointer (((const struct rename_map_elt *) elt)->old_name); -} - -/* Compares database elements E1 and E2. */ - -static int -eq_rename_map_elts (const void *e1, const void *e2) -{ - const struct rename_map_elt *elt1 = (const struct rename_map_elt *) e1; - const struct rename_map_elt *elt2 = (const struct rename_map_elt *) e2; - - return (elt1->old_name == elt2->old_name); -} - -/* Returns the new name associated to OLD_NAME in MAP. */ - -static tree -get_new_name_from_old_name (htab_t map, tree old_name) -{ - struct rename_map_elt tmp; - PTR *slot; - - tmp.old_name = old_name; - slot = htab_find_slot (map, &tmp, NO_INSERT); - - if (slot && *slot) - return ((rename_map_elt) *slot)->new_name; - - return old_name; -} - - - -/* Returns true when BB is in REGION. */ - -static bool -bb_in_sese_p (basic_block bb, sese region) -{ - return pointer_set_contains (SESE_REGION_BBS (region), bb); -} - -/* For a USE in BB, if BB is outside REGION, mark the USE in the - SESE_LIVEIN and SESE_LIVEOUT sets. */ - -static void -sese_build_livein_liveouts_use (sese region, basic_block bb, tree use) -{ - unsigned ver; - basic_block def_bb; - - if (TREE_CODE (use) != SSA_NAME) - return; - - ver = SSA_NAME_VERSION (use); - def_bb = gimple_bb (SSA_NAME_DEF_STMT (use)); - if (!def_bb - || !bb_in_sese_p (def_bb, region) - || bb_in_sese_p (bb, region)) - return; - - if (!SESE_LIVEIN_VER (region, ver)) - SESE_LIVEIN_VER (region, ver) = BITMAP_ALLOC (NULL); - - bitmap_set_bit (SESE_LIVEIN_VER (region, ver), bb->index); - bitmap_set_bit (SESE_LIVEOUT (region), ver); -} - -/* Marks for rewrite all the SSA_NAMES defined in REGION and that are - used in BB that is outside of the REGION. */ - -static void -sese_build_livein_liveouts_bb (sese region, basic_block bb) -{ - gimple_stmt_iterator bsi; - edge e; - edge_iterator ei; - ssa_op_iter iter; - tree var; - - FOR_EACH_EDGE (e, ei, bb->succs) - for (bsi = gsi_start_phis (e->dest); !gsi_end_p (bsi); gsi_next (&bsi)) - sese_build_livein_liveouts_use (region, bb, - PHI_ARG_DEF_FROM_EDGE (gsi_stmt (bsi), e)); - - for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi)) - FOR_EACH_SSA_TREE_OPERAND (var, gsi_stmt (bsi), iter, SSA_OP_ALL_USES) - sese_build_livein_liveouts_use (region, bb, var); -} - -/* Build the SESE_LIVEIN and SESE_LIVEOUT for REGION. */ - -void -sese_build_livein_liveouts (sese region) -{ - basic_block bb; - - SESE_LIVEOUT (region) = BITMAP_ALLOC (NULL); - SESE_NUM_VER (region) = num_ssa_names; - SESE_LIVEIN (region) = XCNEWVEC (bitmap, SESE_NUM_VER (region)); - - FOR_EACH_BB (bb) - sese_build_livein_liveouts_bb (region, bb); -} - -/* Register basic blocks belonging to a region in a pointer set. */ - -static void -register_bb_in_sese (basic_block entry_bb, basic_block exit_bb, sese region) -{ - edge_iterator ei; - edge e; - basic_block bb = entry_bb; - - FOR_EACH_EDGE (e, ei, bb->succs) - { - if (!pointer_set_contains (SESE_REGION_BBS (region), e->dest) && - e->dest->index != exit_bb->index) - { - pointer_set_insert (SESE_REGION_BBS (region), e->dest); - register_bb_in_sese (e->dest, exit_bb, region); - } - } -} - -/* Builds a new SESE region from edges ENTRY and EXIT. */ - -sese -new_sese (edge entry, edge exit) -{ - sese res = XNEW (struct sese); - - SESE_ENTRY (res) = entry; - SESE_EXIT (res) = exit; - SESE_REGION_BBS (res) = pointer_set_create (); - register_bb_in_sese (entry->dest, exit->dest, res); - - SESE_LIVEOUT (res) = NULL; - SESE_NUM_VER (res) = 0; - SESE_LIVEIN (res) = NULL; - - return res; -} - -/* Deletes REGION. */ - -void -free_sese (sese region) -{ - int i; - - for (i = 0; i < SESE_NUM_VER (region); i++) - BITMAP_FREE (SESE_LIVEIN_VER (region, i)); - - if (SESE_LIVEIN (region)) - free (SESE_LIVEIN (region)); - - if (SESE_LIVEOUT (region)) - BITMAP_FREE (SESE_LIVEOUT (region)); - - pointer_set_destroy (SESE_REGION_BBS (region)); - XDELETE (region); -} - - - -/* Creates a new scop starting with ENTRY. */ - -static scop_p -new_scop (edge entry, edge exit) -{ - scop_p scop = XNEW (struct scop); - - gcc_assert (entry && exit); - - SCOP_REGION (scop) = new_sese (entry, exit); - SCOP_BBS (scop) = VEC_alloc (graphite_bb_p, heap, 3); - SCOP_OLDIVS (scop) = VEC_alloc (name_tree, heap, 3); - SCOP_BBS_B (scop) = BITMAP_ALLOC (NULL); - SCOP_LOOPS (scop) = BITMAP_ALLOC (NULL); - SCOP_LOOP_NEST (scop) = VEC_alloc (loop_p, heap, 3); - SCOP_ADD_PARAMS (scop) = true; - SCOP_PARAMS (scop) = VEC_alloc (name_tree, heap, 3); - SCOP_PROG (scop) = cloog_program_malloc (); - cloog_program_set_names (SCOP_PROG (scop), cloog_names_malloc ()); - SCOP_LOOP2CLOOG_LOOP (scop) = htab_create (10, hash_loop_to_cloog_loop, - eq_loop_to_cloog_loop, - free); - SCOP_LIVEOUT_RENAMES (scop) = htab_create (10, rename_map_elt_info, - eq_rename_map_elts, free); - return scop; -} - -/* Deletes SCOP. */ - -static void -free_scop (scop_p scop) -{ - int i; - name_tree p; - struct graphite_bb *gb; - name_tree iv; - - for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++) - free_graphite_bb (gb); - - VEC_free (graphite_bb_p, heap, SCOP_BBS (scop)); - BITMAP_FREE (SCOP_BBS_B (scop)); - BITMAP_FREE (SCOP_LOOPS (scop)); - VEC_free (loop_p, heap, SCOP_LOOP_NEST (scop)); - - for (i = 0; VEC_iterate (name_tree, SCOP_OLDIVS (scop), i, iv); i++) - free (iv); - VEC_free (name_tree, heap, SCOP_OLDIVS (scop)); - - for (i = 0; VEC_iterate (name_tree, SCOP_PARAMS (scop), i, p); i++) - free (p); - - VEC_free (name_tree, heap, SCOP_PARAMS (scop)); - cloog_program_free (SCOP_PROG (scop)); - htab_delete (SCOP_LOOP2CLOOG_LOOP (scop)); - htab_delete (SCOP_LIVEOUT_RENAMES (scop)); - free_sese (SCOP_REGION (scop)); - XDELETE (scop); -} - -/* Deletes all scops in SCOPS. */ - -static void -free_scops (VEC (scop_p, heap) *scops) -{ - int i; - scop_p scop; - - for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++) - free_scop (scop); - - VEC_free (scop_p, heap, scops); -} - -typedef enum gbb_type { - GBB_UNKNOWN, - GBB_LOOP_SING_EXIT_HEADER, - GBB_LOOP_MULT_EXIT_HEADER, - GBB_LOOP_EXIT, - GBB_COND_HEADER, - GBB_SIMPLE, - GBB_LAST -} gbb_type; - -/* Detect the type of BB. Loop headers are only marked, if they are - new. This means their loop_father is different to LAST_LOOP. - Otherwise they are treated like any other bb and their type can be - any other type. */ - -static gbb_type -get_bb_type (basic_block bb, struct loop *last_loop) -{ - VEC (basic_block, heap) *dom; - int nb_dom, nb_suc; - struct loop *loop = bb->loop_father; - - /* Check, if we entry into a new loop. */ - if (loop != last_loop) - { - if (single_exit (loop) != NULL) - return GBB_LOOP_SING_EXIT_HEADER; - else if (loop->num != 0) - return GBB_LOOP_MULT_EXIT_HEADER; - else - return GBB_COND_HEADER; - } - - dom = get_dominated_by (CDI_DOMINATORS, bb); - nb_dom = VEC_length (basic_block, dom); - VEC_free (basic_block, heap, dom); - - if (nb_dom == 0) - return GBB_LAST; - - nb_suc = VEC_length (edge, bb->succs); - - if (nb_dom == 1 && nb_suc == 1) - return GBB_SIMPLE; - - return GBB_COND_HEADER; -} - -/* A SCoP detection region, defined using bbs as borders. - All control flow touching this region, comes in passing basic_block ENTRY and - leaves passing basic_block EXIT. By using bbs instead of edges for the - borders we are able to represent also regions that do not have a single - entry or exit edge. - But as they have a single entry basic_block and a single exit basic_block, we - are able to generate for every sd_region a single entry and exit edge. - - 1 2 - \ / - 3 <- entry - | - 4 - / \ This region contains: {3, 4, 5, 6, 7, 8} - 5 6 - | | - 7 8 - \ / - 9 <- exit */ - - -typedef struct sd_region_p -{ - /* The entry bb dominates all bbs in the sd_region. It is part of the - region. */ - basic_block entry; - - /* The exit bb postdominates all bbs in the sd_region, but is not - part of the region. */ - basic_block exit; -} sd_region; - -DEF_VEC_O(sd_region); -DEF_VEC_ALLOC_O(sd_region, heap); - - -/* Moves the scops from SOURCE to TARGET and clean up SOURCE. */ - -static void -move_sd_regions (VEC (sd_region, heap) **source, VEC (sd_region, heap) **target) -{ - sd_region *s; - int i; - - for (i = 0; VEC_iterate (sd_region, *source, i, s); i++) - VEC_safe_push (sd_region, heap, *target, s); - - VEC_free (sd_region, heap, *source); -} - -/* Return true when it is not possible to represent the upper bound of - LOOP in the polyhedral representation. */ - -static bool -graphite_cannot_represent_loop_niter (loop_p loop) -{ - tree niter = number_of_latch_executions (loop); - - return chrec_contains_undetermined (niter) - || !scev_is_linear_expression (niter); -} -/* Store information needed by scopdet_* functions. */ - -struct scopdet_info -{ - /* Where the last open scop would stop if the current BB is harmful. */ - basic_block last; - - /* Where the next scop would start if the current BB is harmful. */ - basic_block next; - - /* The bb or one of its children contains open loop exits. That means - loop exit nodes that are not surrounded by a loop dominated by bb. */ - bool exits; - - /* The bb or one of its children contains only structures we can handle. */ - bool difficult; -}; - - -static struct scopdet_info build_scops_1 (basic_block, VEC (sd_region, heap) **, - loop_p); - -/* Calculates BB infos. If bb is difficult we add valid SCoPs dominated by BB - to SCOPS. TYPE is the gbb_type of BB. */ - -static struct scopdet_info -scopdet_basic_block_info (basic_block bb, VEC (sd_region, heap) **scops, - gbb_type type) -{ - struct loop *loop = bb->loop_father; - struct scopdet_info result; - gimple stmt; - - /* XXX: ENTRY_BLOCK_PTR could be optimized in later steps. */ - stmt = harmful_stmt_in_bb (ENTRY_BLOCK_PTR, bb); - result.difficult = (stmt != NULL); - result.last = NULL; - - switch (type) - { - case GBB_LAST: - result.next = NULL; - result.exits = false; - result.last = bb; - break; - - case GBB_SIMPLE: - result.next = single_succ (bb); - result.exits = false; - result.last = bb; - break; - - case GBB_LOOP_SING_EXIT_HEADER: - { - VEC (sd_region, heap) *tmp_scops = VEC_alloc (sd_region, heap,3); - struct scopdet_info sinfo; - - sinfo = build_scops_1 (bb, &tmp_scops, loop); - - result.last = single_exit (bb->loop_father)->src; - result.next = single_exit (bb->loop_father)->dest; - - /* If we do not dominate result.next, remove it. It's either - the EXIT_BLOCK_PTR, or another bb dominates it and will - call the scop detection for this bb. */ - if (!dominated_by_p (CDI_DOMINATORS, result.next, bb)) - result.next = NULL; - - if (result.last->loop_father != loop) - result.next = NULL; - - if (graphite_cannot_represent_loop_niter (loop)) - result.difficult = true; - - if (sinfo.difficult) - move_sd_regions (&tmp_scops, scops); - else - VEC_free (sd_region, heap, tmp_scops); - - result.exits = false; - result.difficult |= sinfo.difficult; - break; - } - - case GBB_LOOP_MULT_EXIT_HEADER: - { - /* XXX: For now we just do not join loops with multiple exits. If the - exits lead to the same bb it may be possible to join the loop. */ - VEC (sd_region, heap) *tmp_scops = VEC_alloc (sd_region, heap, 3); - VEC (edge, heap) *exits = get_loop_exit_edges (loop); - edge e; - int i; - build_scops_1 (bb, &tmp_scops, loop); - - /* Scan the code dominated by this loop. This means all bbs, that are - are dominated by a bb in this loop, but are not part of this loop. - - The easiest case: - - The loop exit destination is dominated by the exit sources. - - TODO: We miss here the more complex cases: - - The exit destinations are dominated by another bb inside the - loop. - - The loop dominates bbs, that are not exit destinations. */ - for (i = 0; VEC_iterate (edge, exits, i, e); i++) - if (e->src->loop_father == loop - && dominated_by_p (CDI_DOMINATORS, e->dest, e->src)) - { - /* Pass loop_outer to recognize e->dest as loop header in - build_scops_1. */ - if (e->dest->loop_father->header == e->dest) - build_scops_1 (e->dest, &tmp_scops, - loop_outer (e->dest->loop_father)); - else - build_scops_1 (e->dest, &tmp_scops, e->dest->loop_father); - } - - result.next = NULL; - result.last = NULL; - result.difficult = true; - result.exits = false; - move_sd_regions (&tmp_scops, scops); - VEC_free (edge, heap, exits); - break; - } - case GBB_COND_HEADER: - { - VEC (sd_region, heap) *tmp_scops = VEC_alloc (sd_region, heap, 3); - struct scopdet_info sinfo; - VEC (basic_block, heap) *dominated; - int i; - basic_block dom_bb; - basic_block last_bb = NULL; - edge e; - result.exits = false; - - /* First check the successors of BB, and check if it is possible to join - the different branches. */ - for (i = 0; VEC_iterate (edge, bb->succs, i, e); i++) - { - /* Ignore loop exits. They will be handled after the loop body. */ - if (is_loop_exit (loop, e->dest)) - { - result.exits = true; - continue; - } - - /* Do not follow edges that lead to the end of the - conditions block. For example, in - - | 0 - | /|\ - | 1 2 | - | | | | - | 3 4 | - | \|/ - | 6 - - the edge from 0 => 6. Only check if all paths lead to - the same node 6. */ - - if (!single_pred_p (e->dest)) - { - /* Check, if edge leads directly to the end of this - condition. */ - if (!last_bb) - { - last_bb = e->dest; - } - - if (e->dest != last_bb) - result.difficult = true; - - continue; - } - - if (!dominated_by_p (CDI_DOMINATORS, e->dest, bb)) - { - result.difficult = true; - continue; - } - - sinfo = build_scops_1 (e->dest, &tmp_scops, loop); - - result.exits |= sinfo.exits; - result.last = sinfo.last; - result.difficult |= sinfo.difficult; - - /* Checks, if all branches end at the same point. - If that is true, the condition stays joinable. - Have a look at the example above. */ - if (sinfo.last && single_succ_p (sinfo.last)) - { - basic_block next_tmp = single_succ (sinfo.last); - - if (!last_bb) - last_bb = next_tmp; - - if (next_tmp != last_bb) - result.difficult = true; - } - else - result.difficult = true; - } - - /* If the condition is joinable. */ - if (!result.exits && !result.difficult) - { - /* Only return a next pointer if we dominate this pointer. - Otherwise it will be handled by the bb dominating it. */ - if (dominated_by_p (CDI_DOMINATORS, last_bb, bb) && last_bb != bb) - result.next = last_bb; - else - result.next = NULL; - - VEC_free (sd_region, heap, tmp_scops); - break; - } - - /* Scan remaining bbs dominated by BB. */ - dominated = get_dominated_by (CDI_DOMINATORS, bb); - - for (i = 0; VEC_iterate (basic_block, dominated, i, dom_bb); i++) - { - /* Ignore loop exits: they will be handled after the loop body. */ - if (loop_depth (find_common_loop (loop, dom_bb->loop_father)) - < loop_depth (loop)) - { - result.exits = true; - continue; - } - - /* Ignore the bbs processed above. */ - if (single_pred_p (dom_bb) && single_pred (dom_bb) == bb) - continue; - - if (loop_depth (loop) > loop_depth (dom_bb->loop_father)) - sinfo = build_scops_1 (dom_bb, &tmp_scops, loop_outer (loop)); - else - sinfo = build_scops_1 (dom_bb, &tmp_scops, loop); - - - result.exits |= sinfo.exits; - result.difficult = true; - result.last = NULL; - } - - VEC_free (basic_block, heap, dominated); - - result.next = NULL; - move_sd_regions (&tmp_scops, scops); - - break; - } - - default: - gcc_unreachable (); - } - - return result; -} - -/* Creates the SCoPs and writes entry and exit points for every SCoP. */ - -static struct scopdet_info -build_scops_1 (basic_block current, VEC (sd_region, heap) **scops, loop_p loop) -{ - bool in_scop = false; - sd_region open_scop; - struct scopdet_info sinfo; - - /* Initialize result. */ - struct scopdet_info result; - result.exits = false; - result.difficult = false; - result.next = NULL; - result.last = NULL; - open_scop.entry = NULL; - open_scop.exit = NULL; - sinfo.last = NULL; - - /* Loop over the dominance tree. If we meet a difficult bb, close - the current SCoP. Loop and condition header start a new layer, - and can only be added if all bbs in deeper layers are simple. */ - while (current != NULL) - { - sinfo = scopdet_basic_block_info (current, scops, get_bb_type (current, - loop)); - - if (!in_scop && !(sinfo.exits || sinfo.difficult)) - { - open_scop.entry = current; - open_scop.exit = NULL; - in_scop = true; - } - else if (in_scop && (sinfo.exits || sinfo.difficult)) - { - open_scop.exit = current; - VEC_safe_push (sd_region, heap, *scops, &open_scop); - in_scop = false; - } - - result.difficult |= sinfo.difficult; - result.exits |= sinfo.exits; - - current = sinfo.next; - } - - /* Try to close open_scop, if we are still in an open SCoP. */ - if (in_scop) - { - int i; - edge e; - - for (i = 0; VEC_iterate (edge, sinfo.last->succs, i, e); i++) - if (dominated_by_p (CDI_POST_DOMINATORS, sinfo.last, e->dest)) - open_scop.exit = e->dest; - - if (!open_scop.exit && open_scop.entry != sinfo.last) - open_scop.exit = sinfo.last; - - if (open_scop.exit) - VEC_safe_push (sd_region, heap, *scops, &open_scop); - - } - - result.last = sinfo.last; - return result; -} - -/* Checks if a bb is contained in REGION. */ - -static bool -bb_in_sd_region (basic_block bb, sd_region *region) -{ - return dominated_by_p (CDI_DOMINATORS, bb, region->entry) - && !(dominated_by_p (CDI_DOMINATORS, bb, region->exit) - && !dominated_by_p (CDI_DOMINATORS, region->entry, - region->exit)); -} - -/* Returns the single entry edge of REGION, if it does not exits NULL. */ - -static edge -find_single_entry_edge (sd_region *region) -{ - edge e; - edge_iterator ei; - edge entry = NULL; - - FOR_EACH_EDGE (e, ei, region->entry->preds) - if (!bb_in_sd_region (e->src, region)) - { - if (entry) - { - entry = NULL; - break; - } - - else - entry = e; - } - - return entry; -} - -/* Returns the single exit edge of REGION, if it does not exits NULL. */ - -static edge -find_single_exit_edge (sd_region *region) -{ - edge e; - edge_iterator ei; - edge exit = NULL; - - FOR_EACH_EDGE (e, ei, region->exit->preds) - if (bb_in_sd_region (e->src, region)) - { - if (exit) - { - exit = NULL; - break; - } - - else - exit = e; - } - - return exit; -} - -/* Create a single entry edge for REGION. */ - -static void -create_single_entry_edge (sd_region *region) -{ - if (find_single_entry_edge (region)) - return; - - /* There are multiple predecessors for bb_3 - - | 1 2 - | | / - | |/ - | 3 <- entry - | |\ - | | | - | 4 ^ - | | | - | |/ - | 5 - - There are two edges (1->3, 2->3), that point from outside into the region, - and another one (5->3), a loop latch, lead to bb_3. - - We split bb_3. - - | 1 2 - | | / - | |/ - |3.0 - | |\ (3.0 -> 3.1) = single entry edge - |3.1 | <- entry - | | | - | | | - | 4 ^ - | | | - | |/ - | 5 - - If the loop is part of the SCoP, we have to redirect the loop latches. - - | 1 2 - | | / - | |/ - |3.0 - | | (3.0 -> 3.1) = entry edge - |3.1 <- entry - | |\ - | | | - | 4 ^ - | | | - | |/ - | 5 */ - - if (region->entry->loop_father->header != region->entry - || dominated_by_p (CDI_DOMINATORS, - loop_latch_edge (region->entry->loop_father)->src, - region->exit)) - { - edge forwarder = split_block_after_labels (region->entry); - region->entry = forwarder->dest; - } - else - /* This case is never executed, as the loop headers seem always to have a - single edge pointing from outside into the loop. */ - gcc_unreachable (); - -#ifdef ENABLE_CHECKING - gcc_assert (find_single_entry_edge (region)); -#endif -} - -/* Check if the sd_region, mentioned in EDGE, has no exit bb. */ - -static bool -sd_region_without_exit (edge e) -{ - sd_region *r = (sd_region *) e->aux; - - if (r) - return r->exit == NULL; - else - return false; -} - -/* Create a single exit edge for REGION. */ - -static void -create_single_exit_edge (sd_region *region) -{ - edge e; - edge_iterator ei; - edge forwarder = NULL; - basic_block exit; - - if (find_single_exit_edge (region)) - return; - - /* We create a forwarder bb (5) for all edges leaving this region - (3->5, 4->5). All other edges leading to the same bb, are moved - to a new bb (6). If these edges where part of another region (2->5) - we update the region->exit pointer, of this region. - - To identify which edge belongs to which region we depend on the e->aux - pointer in every edge. It points to the region of the edge or to NULL, - if the edge is not part of any region. - - 1 2 3 4 1->5 no region, 2->5 region->exit = 5, - \| |/ 3->5 region->exit = NULL, 4->5 region->exit = NULL - 5 <- exit - - changes to - - 1 2 3 4 1->6 no region, 2->6 region->exit = 6, - | | \/ 3->5 no region, 4->5 no region, - | | 5 - \| / 5->6 region->exit = 6 - 6 - - Now there is only a single exit edge (5->6). */ - exit = region->exit; - region->exit = NULL; - forwarder = make_forwarder_block (exit, &sd_region_without_exit, NULL); - - /* Unmark the edges, that are no longer exit edges. */ - FOR_EACH_EDGE (e, ei, forwarder->src->preds) - if (e->aux) - e->aux = NULL; - - /* Mark the new exit edge. */ - single_succ_edge (forwarder->src)->aux = region; - - /* Update the exit bb of all regions, where exit edges lead to - forwarder->dest. */ - FOR_EACH_EDGE (e, ei, forwarder->dest->preds) - if (e->aux) - ((sd_region *) e->aux)->exit = forwarder->dest; - -#ifdef ENABLE_CHECKING - gcc_assert (find_single_exit_edge (region)); -#endif -} - -/* Unmark the exit edges of all REGIONS. - See comment in "create_single_exit_edge". */ - -static void -unmark_exit_edges (VEC (sd_region, heap) *regions) -{ - int i; - sd_region *s; - edge e; - edge_iterator ei; - - for (i = 0; VEC_iterate (sd_region, regions, i, s); i++) - FOR_EACH_EDGE (e, ei, s->exit->preds) - e->aux = NULL; -} - - -/* Mark the exit edges of all REGIONS. - See comment in "create_single_exit_edge". */ - -static void -mark_exit_edges (VEC (sd_region, heap) *regions) -{ - int i; - sd_region *s; - edge e; - edge_iterator ei; - - for (i = 0; VEC_iterate (sd_region, regions, i, s); i++) - FOR_EACH_EDGE (e, ei, s->exit->preds) - if (bb_in_sd_region (e->src, s)) - e->aux = s; -} - -/* Free and compute again all the dominators information. */ - -static inline void -recompute_all_dominators (void) -{ - mark_irreducible_loops (); - free_dominance_info (CDI_DOMINATORS); - free_dominance_info (CDI_POST_DOMINATORS); - calculate_dominance_info (CDI_DOMINATORS); - calculate_dominance_info (CDI_POST_DOMINATORS); -} - -/* Verifies properties that GRAPHITE should maintain during translation. */ - -static inline void -graphite_verify (void) -{ -#ifdef ENABLE_CHECKING - verify_loop_structure (); - verify_dominators (CDI_DOMINATORS); - verify_dominators (CDI_POST_DOMINATORS); - verify_ssa (false); -#endif -} - -/* Create for all scop regions a single entry and a single exit edge. */ - -static void -create_sese_edges (VEC (sd_region, heap) *regions) -{ - int i; - sd_region *s; - - for (i = 0; VEC_iterate (sd_region, regions, i, s); i++) - create_single_entry_edge (s); - - mark_exit_edges (regions); - - for (i = 0; VEC_iterate (sd_region, regions, i, s); i++) - create_single_exit_edge (s); - - unmark_exit_edges (regions); - - fix_loop_structure (NULL); - -#ifdef ENABLE_CHECKING - verify_loop_structure (); - verify_dominators (CDI_DOMINATORS); - verify_ssa (false); -#endif -} - -/* Create graphite SCoPs from an array of scop detection regions. */ - -static void -build_graphite_scops (VEC (sd_region, heap) *scop_regions) -{ - int i; - sd_region *s; - - for (i = 0; VEC_iterate (sd_region, scop_regions, i, s); i++) - { - edge entry = find_single_entry_edge (s); - edge exit = find_single_exit_edge (s); - scop_p scop = new_scop (entry, exit); - VEC_safe_push (scop_p, heap, current_scops, scop); - - /* Are there overlapping SCoPs? */ -#ifdef ENABLE_CHECKING - { - int j; - sd_region *s2; - - for (j = 0; VEC_iterate (sd_region, scop_regions, j, s2); j++) - if (s != s2) - gcc_assert (!bb_in_sd_region (s->entry, s2)); - } -#endif - } -} - -/* Find static control parts. */ - -static void -build_scops (void) -{ - struct loop *loop = current_loops->tree_root; - VEC (sd_region, heap) *tmp_scops = VEC_alloc (sd_region, heap, 3); - - build_scops_1 (single_succ (ENTRY_BLOCK_PTR), &tmp_scops, loop); - create_sese_edges (tmp_scops); - build_graphite_scops (tmp_scops); - VEC_free (sd_region, heap, tmp_scops); -} - -/* Gather the basic blocks belonging to the SCOP. */ - -static void -build_scop_bbs (scop_p scop) -{ - basic_block *stack = XNEWVEC (basic_block, n_basic_blocks + 1); - sbitmap visited = sbitmap_alloc (last_basic_block); - int sp = 0; - - sbitmap_zero (visited); - stack[sp++] = SCOP_ENTRY (scop); - - while (sp) - { - basic_block bb = stack[--sp]; - int depth = loop_depth (bb->loop_father); - int num = bb->loop_father->num; - edge_iterator ei; - edge e; - - /* Scop's exit is not in the scop. Exclude also bbs, which are - dominated by the SCoP exit. These are e.g. loop latches. */ - if (TEST_BIT (visited, bb->index) - || dominated_by_p (CDI_DOMINATORS, bb, SCOP_EXIT (scop)) - /* Every block in the scop is dominated by scop's entry. */ - || !dominated_by_p (CDI_DOMINATORS, bb, SCOP_ENTRY (scop))) - continue; - - new_graphite_bb (scop, bb); - SET_BIT (visited, bb->index); - - /* First push the blocks that have to be processed last. Note - that this means that the order in which the code is organized - below is important: do not reorder the following code. */ - FOR_EACH_EDGE (e, ei, bb->succs) - if (! TEST_BIT (visited, e->dest->index) - && (int) loop_depth (e->dest->loop_father) < depth) - stack[sp++] = e->dest; - - FOR_EACH_EDGE (e, ei, bb->succs) - if (! TEST_BIT (visited, e->dest->index) - && (int) loop_depth (e->dest->loop_father) == depth - && e->dest->loop_father->num != num) - stack[sp++] = e->dest; - - FOR_EACH_EDGE (e, ei, bb->succs) - if (! TEST_BIT (visited, e->dest->index) - && (int) loop_depth (e->dest->loop_father) == depth - && e->dest->loop_father->num == num - && EDGE_COUNT (e->dest->preds) > 1) - stack[sp++] = e->dest; - - FOR_EACH_EDGE (e, ei, bb->succs) - if (! TEST_BIT (visited, e->dest->index) - && (int) loop_depth (e->dest->loop_father) == depth - && e->dest->loop_father->num == num - && EDGE_COUNT (e->dest->preds) == 1) - stack[sp++] = e->dest; - - FOR_EACH_EDGE (e, ei, bb->succs) - if (! TEST_BIT (visited, e->dest->index) - && (int) loop_depth (e->dest->loop_father) > depth) - stack[sp++] = e->dest; - } - - free (stack); - sbitmap_free (visited); -} - -/* Returns the number of reduction phi nodes in LOOP. */ - -static int -nb_reductions_in_loop (loop_p loop) -{ - int res = 0; - gimple_stmt_iterator gsi; - - for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi)) - { - gimple phi = gsi_stmt (gsi); - tree scev; - affine_iv iv; - - if (!is_gimple_reg (PHI_RESULT (phi))) - continue; - - scev = analyze_scalar_evolution (loop, PHI_RESULT (phi)); - scev = instantiate_parameters (loop, scev); - if (!simple_iv (loop, phi, PHI_RESULT (phi), &iv, true)) - res++; - } - - return res; -} - -/* A LOOP is in normal form when it contains only one scalar phi node - that defines the main induction variable of the loop, only one - increment of the IV, and only one exit condition. */ - -static tree -graphite_loop_normal_form (loop_p loop) -{ - struct tree_niter_desc niter; - tree nit; - gimple_seq stmts; - edge exit = single_dom_exit (loop); - - gcc_assert (number_of_iterations_exit (loop, exit, &niter, false)); - nit = force_gimple_operand (unshare_expr (niter.niter), &stmts, true, - NULL_TREE); - if (stmts) - gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts); - - /* One IV per loop. */ - if (nb_reductions_in_loop (loop) > 0) - return NULL_TREE; - - return canonicalize_loop_ivs (loop, NULL, nit); -} - -/* Record LOOP as occuring in SCOP. Returns true when the operation - was successful. */ - -static bool -scop_record_loop (scop_p scop, loop_p loop) -{ - tree induction_var; - name_tree oldiv; - - if (bitmap_bit_p (SCOP_LOOPS (scop), loop->num)) - return true; - - bitmap_set_bit (SCOP_LOOPS (scop), loop->num); - VEC_safe_push (loop_p, heap, SCOP_LOOP_NEST (scop), loop); - - induction_var = graphite_loop_normal_form (loop); - if (!induction_var) - return false; - - oldiv = XNEW (struct name_tree); - oldiv->t = induction_var; - oldiv->name = get_name (SSA_NAME_VAR (oldiv->t)); - oldiv->loop = loop; - VEC_safe_push (name_tree, heap, SCOP_OLDIVS (scop), oldiv); - return true; -} - -/* Build the loop nests contained in SCOP. Returns true when the - operation was successful. */ - -static bool -build_scop_loop_nests (scop_p scop) -{ - unsigned i; - basic_block bb; - struct loop *loop0, *loop1; - - FOR_EACH_BB (bb) - if (bb_in_scop_p (bb, scop)) - { - struct loop *loop = bb->loop_father; - - /* Only add loops if they are completely contained in the SCoP. */ - if (loop->header == bb - && bb_in_scop_p (loop->latch, scop)) - { - if (!scop_record_loop (scop, loop)) - return false; - } - } - - /* Make sure that the loops in the SCOP_LOOP_NEST are ordered. It - can be the case that an inner loop is inserted before an outer - loop. To avoid this, semi-sort once. */ - for (i = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), i, loop0); i++) - { - if (VEC_length (loop_p, SCOP_LOOP_NEST (scop)) == i + 1) - break; - - loop1 = VEC_index (loop_p, SCOP_LOOP_NEST (scop), i + 1); - if (loop0->num > loop1->num) - { - VEC_replace (loop_p, SCOP_LOOP_NEST (scop), i, loop1); - VEC_replace (loop_p, SCOP_LOOP_NEST (scop), i + 1, loop0); - } - } - - return true; -} - -/* Build dynamic schedules for all the BBs. */ - -static void -build_scop_dynamic_schedules (scop_p scop) -{ - int i, dim, loop_num, row, col; - graphite_bb_p gb; - - for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++) - { - loop_num = GBB_BB (gb)->loop_father->num; - - if (loop_num != 0) - { - dim = nb_loops_around_gb (gb); - GBB_DYNAMIC_SCHEDULE (gb) = cloog_matrix_alloc (dim, dim); - - for (row = 0; row < GBB_DYNAMIC_SCHEDULE (gb)->NbRows; row++) - for (col = 0; col < GBB_DYNAMIC_SCHEDULE (gb)->NbColumns; col++) - if (row == col) - value_set_si (GBB_DYNAMIC_SCHEDULE (gb)->p[row][col], 1); - else - value_set_si (GBB_DYNAMIC_SCHEDULE (gb)->p[row][col], 0); - } - else - GBB_DYNAMIC_SCHEDULE (gb) = NULL; - } -} - -/* Build for BB the static schedule. - - The STATIC_SCHEDULE is defined like this: - - A - for (i: ...) - { - for (j: ...) - { - B - C - } - - for (k: ...) - { - D - E - } - } - F - - Static schedules for A to F: - - DEPTH - 0 1 2 - A 0 - B 1 0 0 - C 1 0 1 - D 1 1 0 - E 1 1 1 - F 2 -*/ - -static void -build_scop_canonical_schedules (scop_p scop) -{ - int i, j; - graphite_bb_p gb; - int nb = scop_nb_loops (scop) + 1; - - SCOP_STATIC_SCHEDULE (scop) = lambda_vector_new (nb); - - for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++) - { - int offset = nb_loops_around_gb (gb); - - /* After leaving a loop, it is possible that the schedule is not - set at zero. This loop reinitializes components located - after OFFSET. */ - - for (j = offset + 1; j < nb; j++) - if (SCOP_STATIC_SCHEDULE (scop)[j]) - { - memset (&(SCOP_STATIC_SCHEDULE (scop)[j]), 0, - sizeof (int) * (nb - j)); - ++SCOP_STATIC_SCHEDULE (scop)[offset]; - break; - } - - GBB_STATIC_SCHEDULE (gb) = lambda_vector_new (offset + 1); - lambda_vector_copy (SCOP_STATIC_SCHEDULE (scop), - GBB_STATIC_SCHEDULE (gb), offset + 1); - - ++SCOP_STATIC_SCHEDULE (scop)[offset]; - } -} - -/* Build the LOOPS vector for all bbs in SCOP. */ - -static void -build_bb_loops (scop_p scop) -{ - graphite_bb_p gb; - int i; - - for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++) - { - loop_p loop; - int depth; - - depth = nb_loops_around_gb (gb) - 1; - - GBB_LOOPS (gb) = VEC_alloc (loop_p, heap, 3); - VEC_safe_grow_cleared (loop_p, heap, GBB_LOOPS (gb), depth + 1); - - loop = GBB_BB (gb)->loop_father; - - while (scop_contains_loop (scop, loop)) - { - VEC_replace (loop_p, GBB_LOOPS (gb), depth, loop); - loop = loop_outer (loop); - depth--; - } - } -} - -/* Get the index for parameter VAR in SCOP. */ - -static int -param_index (tree var, scop_p scop) -{ - int i; - name_tree p; - name_tree nvar; - - gcc_assert (TREE_CODE (var) == SSA_NAME); - - for (i = 0; VEC_iterate (name_tree, SCOP_PARAMS (scop), i, p); i++) - if (p->t == var) - return i; - - gcc_assert (SCOP_ADD_PARAMS (scop)); - - nvar = XNEW (struct name_tree); - nvar->t = var; - nvar->name = NULL; - VEC_safe_push (name_tree, heap, SCOP_PARAMS (scop), nvar); - return VEC_length (name_tree, SCOP_PARAMS (scop)) - 1; -} - -/* Scan EXPR and translate it to an inequality vector INEQ that will - be added, or subtracted, in the constraint domain matrix C at row - R. K is the number of columns for loop iterators in C. */ - -static void -scan_tree_for_params (scop_p s, tree e, CloogMatrix *c, int r, Value k, - bool subtract) -{ - int cst_col, param_col; - - if (e == chrec_dont_know) - return; - - switch (TREE_CODE (e)) - { - case POLYNOMIAL_CHREC: - { - tree left = CHREC_LEFT (e); - tree right = CHREC_RIGHT (e); - int var = CHREC_VARIABLE (e); - - if (TREE_CODE (right) != INTEGER_CST) - return; - - if (c) - { - int loop_col = scop_gimple_loop_depth (s, get_loop (var)) + 1; - - if (subtract) - value_sub_int (c->p[r][loop_col], c->p[r][loop_col], - int_cst_value (right)); - else - value_add_int (c->p[r][loop_col], c->p[r][loop_col], - int_cst_value (right)); - } - - switch (TREE_CODE (left)) - { - case POLYNOMIAL_CHREC: - scan_tree_for_params (s, left, c, r, k, subtract); - return; - - case INTEGER_CST: - /* Constant part. */ - if (c) - { - int v = int_cst_value (left); - cst_col = c->NbColumns - 1; - - if (v < 0) - { - v = -v; - subtract = subtract ? false : true; - } - - if (subtract) - value_sub_int (c->p[r][cst_col], c->p[r][cst_col], v); - else - value_add_int (c->p[r][cst_col], c->p[r][cst_col], v); - } - return; - - default: - scan_tree_for_params (s, left, c, r, k, subtract); - return; - } - } - break; - - case MULT_EXPR: - if (chrec_contains_symbols (TREE_OPERAND (e, 0))) - { - if (c) - { - Value val; - gcc_assert (host_integerp (TREE_OPERAND (e, 1), 0)); - value_init (val); - value_set_si (val, int_cst_value (TREE_OPERAND (e, 1))); - value_multiply (k, k, val); - value_clear (val); - } - scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract); - } - else - { - if (c) - { - Value val; - gcc_assert (host_integerp (TREE_OPERAND (e, 0), 0)); - value_init (val); - value_set_si (val, int_cst_value (TREE_OPERAND (e, 0))); - value_multiply (k, k, val); - value_clear (val); - } - scan_tree_for_params (s, TREE_OPERAND (e, 1), c, r, k, subtract); - } - break; - - case PLUS_EXPR: - case POINTER_PLUS_EXPR: - scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract); - scan_tree_for_params (s, TREE_OPERAND (e, 1), c, r, k, subtract); - break; - - case MINUS_EXPR: - scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract); - value_oppose (k, k); - scan_tree_for_params (s, TREE_OPERAND (e, 1), c, r, k, subtract); - break; - - case NEGATE_EXPR: - value_oppose (k, k); - scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract); - break; - - case SSA_NAME: - param_col = param_index (e, s); - - if (c) - { - param_col += c->NbColumns - scop_nb_params (s) - 1; - - if (subtract) - value_subtract (c->p[r][param_col], c->p[r][param_col], k); - else - value_addto (c->p[r][param_col], c->p[r][param_col], k); - } - break; - - case INTEGER_CST: - if (c) - { - int v = int_cst_value (e); - cst_col = c->NbColumns - 1; - - if (v < 0) - { - v = -v; - subtract = subtract ? false : true; - } - - if (subtract) - value_sub_int (c->p[r][cst_col], c->p[r][cst_col], v); - else - value_add_int (c->p[r][cst_col], c->p[r][cst_col], v); - } - break; - - CASE_CONVERT: - case NON_LVALUE_EXPR: - scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract); - break; - - default: - gcc_unreachable (); - break; - } -} - -/* Data structure for idx_record_params. */ - -struct irp_data -{ - struct loop *loop; - scop_p scop; -}; - -/* For a data reference with an ARRAY_REF as its BASE, record the - parameters occurring in IDX. DTA is passed in as complementary - information, and is used by the automatic walker function. This - function is a callback for for_each_index. */ - -static bool -idx_record_params (tree base, tree *idx, void *dta) -{ - struct irp_data *data = (struct irp_data *) dta; - - if (TREE_CODE (base) != ARRAY_REF) - return true; - - if (TREE_CODE (*idx) == SSA_NAME) - { - tree scev; - scop_p scop = data->scop; - struct loop *loop = data->loop; - Value one; - - scev = analyze_scalar_evolution (loop, *idx); - scev = instantiate_scev (block_before_scop (scop), loop, scev); - - value_init (one); - value_set_si (one, 1); - scan_tree_for_params (scop, scev, NULL, 0, one, false); - value_clear (one); - } - - return true; -} - -/* Find parameters with respect to SCOP in BB. We are looking in memory - access functions, conditions and loop bounds. */ - -static void -find_params_in_bb (scop_p scop, graphite_bb_p gb) -{ - int i; - data_reference_p dr; - gimple stmt; - loop_p father = GBB_BB (gb)->loop_father; - - for (i = 0; VEC_iterate (data_reference_p, GBB_DATA_REFS (gb), i, dr); i++) - { - struct irp_data irp; - - irp.loop = father; - irp.scop = scop; - for_each_index (&dr->ref, idx_record_params, &irp); - } - - /* Find parameters in conditional statements. */ - for (i = 0; VEC_iterate (gimple, GBB_CONDITIONS (gb), i, stmt); i++) - { - Value one; - loop_p loop = father; - - tree lhs, rhs; - - lhs = gimple_cond_lhs (stmt); - lhs = analyze_scalar_evolution (loop, lhs); - lhs = instantiate_scev (block_before_scop (scop), loop, lhs); - - rhs = gimple_cond_rhs (stmt); - rhs = analyze_scalar_evolution (loop, rhs); - rhs = instantiate_scev (block_before_scop (scop), loop, rhs); - - value_init (one); - scan_tree_for_params (scop, lhs, NULL, 0, one, false); - value_set_si (one, 1); - scan_tree_for_params (scop, rhs, NULL, 0, one, false); - value_clear (one); - } -} - -/* Saves in NV the name of variable P->T. */ - -static void -save_var_name (char **nv, int i, name_tree p) -{ - const char *name = get_name (SSA_NAME_VAR (p->t)); - - if (name) - { - int len = strlen (name) + 16; - nv[i] = XNEWVEC (char, len); - snprintf (nv[i], len, "%s_%d", name, SSA_NAME_VERSION (p->t)); - } - else - { - nv[i] = XNEWVEC (char, 16); - snprintf (nv[i], 2 + 16, "T_%d", SSA_NAME_VERSION (p->t)); - } - - p->name = nv[i]; -} - -/* Return the maximal loop depth in SCOP. */ - -static int -scop_max_loop_depth (scop_p scop) -{ - int i; - graphite_bb_p gbb; - int max_nb_loops = 0; - - for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gbb); i++) - { - int nb_loops = gbb_nb_loops (gbb); - if (max_nb_loops < nb_loops) - max_nb_loops = nb_loops; - } - - return max_nb_loops; -} - -/* Initialize Cloog's parameter names from the names used in GIMPLE. - Initialize Cloog's iterator names, using 'graphite_iterator_%d' - from 0 to scop_nb_loops (scop). */ - -static void -initialize_cloog_names (scop_p scop) -{ - int i, nb_params = VEC_length (name_tree, SCOP_PARAMS (scop)); - char **params = XNEWVEC (char *, nb_params); - int nb_iterators = scop_max_loop_depth (scop); - int nb_scattering= cloog_program_nb_scattdims (SCOP_PROG (scop)); - char **iterators = XNEWVEC (char *, nb_iterators * 2); - char **scattering = XNEWVEC (char *, nb_scattering); - name_tree p; - - for (i = 0; VEC_iterate (name_tree, SCOP_PARAMS (scop), i, p); i++) - save_var_name (params, i, p); - - cloog_names_set_nb_parameters (cloog_program_names (SCOP_PROG (scop)), - nb_params); - cloog_names_set_parameters (cloog_program_names (SCOP_PROG (scop)), - params); - - for (i = 0; i < nb_iterators; i++) - { - int len = 18 + 16; - iterators[i] = XNEWVEC (char, len); - snprintf (iterators[i], len, "graphite_iterator_%d", i); - } - - cloog_names_set_nb_iterators (cloog_program_names (SCOP_PROG (scop)), - nb_iterators); - cloog_names_set_iterators (cloog_program_names (SCOP_PROG (scop)), - iterators); - - for (i = 0; i < nb_scattering; i++) - { - int len = 2 + 16; - scattering[i] = XNEWVEC (char, len); - snprintf (scattering[i], len, "s_%d", i); - } - - cloog_names_set_nb_scattering (cloog_program_names (SCOP_PROG (scop)), - nb_scattering); - cloog_names_set_scattering (cloog_program_names (SCOP_PROG (scop)), - scattering); -} - -/* Record the parameters used in the SCOP. A variable is a parameter - in a scop if it does not vary during the execution of that scop. */ - -static void -find_scop_parameters (scop_p scop) -{ - graphite_bb_p gb; - unsigned i; - struct loop *loop; - Value one; - - value_init (one); - value_set_si (one, 1); - - /* Find the parameters used in the loop bounds. */ - for (i = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), i, loop); i++) - { - tree nb_iters = number_of_latch_executions (loop); - - if (!chrec_contains_symbols (nb_iters)) - continue; - - nb_iters = analyze_scalar_evolution (loop, nb_iters); - nb_iters = instantiate_scev (block_before_scop (scop), loop, nb_iters); - scan_tree_for_params (scop, nb_iters, NULL, 0, one, false); - } - - value_clear (one); - - /* Find the parameters used in data accesses. */ - for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++) - find_params_in_bb (scop, gb); - - SCOP_ADD_PARAMS (scop) = false; -} - -/* Build the context constraints for SCOP: constraints and relations - on parameters. */ - -static void -build_scop_context (scop_p scop) -{ - int nb_params = scop_nb_params (scop); - CloogMatrix *matrix = cloog_matrix_alloc (1, nb_params + 2); - - /* Insert '0 >= 0' in the context matrix, as it is not allowed to be - empty. */ - - value_set_si (matrix->p[0][0], 1); - - value_set_si (matrix->p[0][nb_params + 1], 0); - - cloog_program_set_context (SCOP_PROG (scop), - cloog_domain_matrix2domain (matrix)); - cloog_matrix_free (matrix); -} - -/* Returns a graphite_bb from BB. */ - -static inline graphite_bb_p -gbb_from_bb (basic_block bb) -{ - return (graphite_bb_p) bb->aux; -} - -/* Builds the constraint matrix for LOOP in SCOP. NB_OUTER_LOOPS is the - number of loops surrounding LOOP in SCOP. OUTER_CSTR gives the - constraints matrix for the surrounding loops. */ - -static void -build_loop_iteration_domains (scop_p scop, struct loop *loop, - CloogMatrix *outer_cstr, int nb_outer_loops) -{ - int i, j, row; - CloogMatrix *cstr; - graphite_bb_p gb; - - int nb_rows = outer_cstr->NbRows + 1; - int nb_cols = outer_cstr->NbColumns + 1; - - /* Last column of CSTR is the column of constants. */ - int cst_col = nb_cols - 1; - - /* The column for the current loop is just after the columns of - other outer loops. */ - int loop_col = nb_outer_loops + 1; - - tree nb_iters = number_of_latch_executions (loop); - - /* When the number of iterations is a constant or a parameter, we - add a constraint for the upper bound of the loop. So add a row - to the constraint matrix before allocating it. */ - if (TREE_CODE (nb_iters) == INTEGER_CST - || !chrec_contains_undetermined (nb_iters)) - nb_rows++; - - cstr = cloog_matrix_alloc (nb_rows, nb_cols); - - /* Copy the outer constraints. */ - for (i = 0; i < outer_cstr->NbRows; i++) - { - /* Copy the eq/ineq and loops columns. */ - for (j = 0; j < loop_col; j++) - value_assign (cstr->p[i][j], outer_cstr->p[i][j]); - - /* Leave an empty column in CSTR for the current loop, and then - copy the parameter columns. */ - for (j = loop_col; j < outer_cstr->NbColumns; j++) - value_assign (cstr->p[i][j + 1], outer_cstr->p[i][j]); - } - - /* 0 <= loop_i */ - row = outer_cstr->NbRows; - value_set_si (cstr->p[row][0], 1); - value_set_si (cstr->p[row][loop_col], 1); - - /* loop_i <= nb_iters */ - if (TREE_CODE (nb_iters) == INTEGER_CST) - { - row++; - value_set_si (cstr->p[row][0], 1); - value_set_si (cstr->p[row][loop_col], -1); - - value_set_si (cstr->p[row][cst_col], - int_cst_value (nb_iters)); - } - else if (!chrec_contains_undetermined (nb_iters)) - { - /* Otherwise nb_iters contains parameters: scan the nb_iters - expression and build its matrix representation. */ - Value one; - - row++; - value_set_si (cstr->p[row][0], 1); - value_set_si (cstr->p[row][loop_col], -1); - - nb_iters = analyze_scalar_evolution (loop, nb_iters); - nb_iters = instantiate_scev (block_before_scop (scop), loop, nb_iters); - - value_init (one); - value_set_si (one, 1); - scan_tree_for_params (scop, nb_iters, cstr, row, one, false); - value_clear (one); - } - else - gcc_unreachable (); - - if (loop->inner && loop_in_scop_p (loop->inner, scop)) - build_loop_iteration_domains (scop, loop->inner, cstr, nb_outer_loops + 1); - - /* Only go to the next loops, if we are not at the outermost layer. These - have to be handled seperately, as we can be sure, that the chain at this - layer will be connected. */ - if (nb_outer_loops != 0 && loop->next && loop_in_scop_p (loop->next, scop)) - build_loop_iteration_domains (scop, loop->next, outer_cstr, nb_outer_loops); - - for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++) - if (gbb_loop (gb) == loop) - GBB_DOMAIN (gb) = cloog_matrix_copy (cstr); - - cloog_matrix_free (cstr); -} - -/* Add conditions to the domain of GB. */ - -static void -add_conditions_to_domain (graphite_bb_p gb) -{ - unsigned int i,j; - gimple stmt; - VEC (gimple, heap) *conditions = GBB_CONDITIONS (gb); - CloogMatrix *domain = GBB_DOMAIN (gb); - scop_p scop = GBB_SCOP (gb); - - unsigned nb_rows; - unsigned nb_cols; - unsigned nb_new_rows = 0; - unsigned row; - - if (VEC_empty (gimple, conditions)) - return; - - if (domain) - { - nb_rows = domain->NbRows; - nb_cols = domain->NbColumns; - } - else - { - nb_rows = 0; - nb_cols = scop_nb_params (scop) + 2; - } - - /* Count number of necessary new rows to add the conditions to the - domain. */ - for (i = 0; VEC_iterate (gimple, conditions, i, stmt); i++) - { - switch (gimple_code (stmt)) - { - case GIMPLE_COND: - { - enum tree_code code = gimple_cond_code (stmt); - - switch (code) - { - case NE_EXPR: - case EQ_EXPR: - /* NE and EQ statements are not supported right know. */ - gcc_unreachable (); - break; - case LT_EXPR: - case GT_EXPR: - case LE_EXPR: - case GE_EXPR: - nb_new_rows++; - break; - default: - gcc_unreachable (); - break; - } - break; - } - case SWITCH_EXPR: - /* Switch statements are not supported right know. */ - gcc_unreachable (); - break; - - default: - gcc_unreachable (); - break; - } - } - - - /* Enlarge the matrix. */ - { - CloogMatrix *new_domain; - new_domain = cloog_matrix_alloc (nb_rows + nb_new_rows, nb_cols); - - for (i = 0; i < nb_rows; i++) - for (j = 0; j < nb_cols; j++) - value_assign (new_domain->p[i][j], domain->p[i][j]); - - cloog_matrix_free (domain); - domain = new_domain; - GBB_DOMAIN (gb) = new_domain; - } - - /* Add the conditions to the new enlarged domain matrix. */ - row = nb_rows; - for (i = 0; VEC_iterate (gimple, conditions, i, stmt); i++) - { - switch (gimple_code (stmt)) - { - case GIMPLE_COND: - { - Value one; - enum tree_code code; - tree left; - tree right; - loop_p loop = GBB_BB (gb)->loop_father; - - left = gimple_cond_lhs (stmt); - right = gimple_cond_rhs (stmt); - - left = analyze_scalar_evolution (loop, left); - right = analyze_scalar_evolution (loop, right); - - left = instantiate_scev (block_before_scop (scop), loop, left); - right = instantiate_scev (block_before_scop (scop), loop, right); - - code = gimple_cond_code (stmt); - - /* The conditions for ELSE-branches are inverted. */ - if (VEC_index (gimple, gb->condition_cases, i) == NULL) - code = invert_tree_comparison (code, false); - - switch (code) - { - case NE_EXPR: - /* NE statements are not supported right know. */ - gcc_unreachable (); - break; - case EQ_EXPR: - value_set_si (domain->p[row][0], 1); - value_init (one); - value_set_si (one, 1); - scan_tree_for_params (scop, left, domain, row, one, true); - value_set_si (one, 1); - scan_tree_for_params (scop, right, domain, row, one, false); - row++; - value_set_si (domain->p[row][0], 1); - value_set_si (one, 1); - scan_tree_for_params (scop, left, domain, row, one, false); - value_set_si (one, 1); - scan_tree_for_params (scop, right, domain, row, one, true); - value_clear (one); - row++; - break; - case LT_EXPR: - value_set_si (domain->p[row][0], 1); - value_init (one); - value_set_si (one, 1); - scan_tree_for_params (scop, left, domain, row, one, true); - value_set_si (one, 1); - scan_tree_for_params (scop, right, domain, row, one, false); - value_sub_int (domain->p[row][nb_cols - 1], - domain->p[row][nb_cols - 1], 1); - value_clear (one); - row++; - break; - case GT_EXPR: - value_set_si (domain->p[row][0], 1); - value_init (one); - value_set_si (one, 1); - scan_tree_for_params (scop, left, domain, row, one, false); - value_set_si (one, 1); - scan_tree_for_params (scop, right, domain, row, one, true); - value_sub_int (domain->p[row][nb_cols - 1], - domain->p[row][nb_cols - 1], 1); - value_clear (one); - row++; - break; - case LE_EXPR: - value_set_si (domain->p[row][0], 1); - value_init (one); - value_set_si (one, 1); - scan_tree_for_params (scop, left, domain, row, one, true); - value_set_si (one, 1); - scan_tree_for_params (scop, right, domain, row, one, false); - value_clear (one); - row++; - break; - case GE_EXPR: - value_set_si (domain->p[row][0], 1); - value_init (one); - value_set_si (one, 1); - scan_tree_for_params (scop, left, domain, row, one, false); - value_set_si (one, 1); - scan_tree_for_params (scop, right, domain, row, one, true); - value_clear (one); - row++; - break; - default: - gcc_unreachable (); - break; - } - break; - } - case GIMPLE_SWITCH: - /* Switch statements are not supported right know. */ - gcc_unreachable (); - break; - - default: - gcc_unreachable (); - break; - } - } -} - -/* Returns true when PHI defines an induction variable in the loop - containing the PHI node. */ - -static bool -phi_node_is_iv (gimple phi) -{ - loop_p loop = gimple_bb (phi)->loop_father; - tree scev = analyze_scalar_evolution (loop, gimple_phi_result (phi)); - - return tree_contains_chrecs (scev, NULL); -} - -/* Returns true when BB contains scalar phi nodes that are not an - induction variable of a loop. */ - -static bool -bb_contains_non_iv_scalar_phi_nodes (basic_block bb) -{ - gimple phi = NULL; - gimple_stmt_iterator si; - - for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si)) - if (is_gimple_reg (gimple_phi_result (gsi_stmt (si)))) - { - /* Store the unique scalar PHI node: at this point, loops - should be in cannonical form, so we expect to see at most - one scalar phi node in the loop header. */ - if (phi - || bb != bb->loop_father->header) - return true; - - phi = gsi_stmt (si); - } - - if (!phi - || phi_node_is_iv (phi)) - return false; - - return true; -} - -/* Helper recursive function. Record in CONDITIONS and CASES all - conditions from 'if's and 'switch'es occurring in BB from SCOP. - - Returns false when the conditions contain scalar computations that - depend on the condition, i.e. when there are scalar phi nodes on - the junction after the condition. Only the computations occurring - on memory can be handled in the polyhedral model: operations that - define scalar evolutions in conditions, that can potentially be - used to index memory, can't be handled by the polyhedral model. */ - -static bool -build_scop_conditions_1 (VEC (gimple, heap) **conditions, - VEC (gimple, heap) **cases, basic_block bb, - scop_p scop) -{ - bool res = true; - int i, j; - graphite_bb_p gbb; - gimple_stmt_iterator gsi; - basic_block bb_child, bb_iter; - VEC (basic_block, heap) *dom; - - /* Make sure we are in the SCoP. */ - if (!bb_in_scop_p (bb, scop)) - return true; - - if (bb_contains_non_iv_scalar_phi_nodes (bb)) - return false; - - gbb = gbb_from_bb (bb); - if (gbb) - { - GBB_CONDITIONS (gbb) = VEC_copy (gimple, heap, *conditions); - GBB_CONDITION_CASES (gbb) = VEC_copy (gimple, heap, *cases); - add_conditions_to_domain (gbb); - } - - dom = get_dominated_by (CDI_DOMINATORS, bb); - - for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) - { - gimple stmt = gsi_stmt (gsi); - VEC (edge, gc) *edges; - edge e; - - switch (gimple_code (stmt)) - { - case GIMPLE_COND: - edges = bb->succs; - for (i = 0; VEC_iterate (edge, edges, i, e); i++) - if ((dominated_by_p (CDI_DOMINATORS, e->dest, bb)) - && VEC_length (edge, e->dest->preds) == 1) - { - /* Remove the scanned block from the dominator successors. */ - for (j = 0; VEC_iterate (basic_block, dom, j, bb_iter); j++) - if (bb_iter == e->dest) - { - VEC_unordered_remove (basic_block, dom, j); - break; - } - - /* Recursively scan the then or else part. */ - if (e->flags & EDGE_TRUE_VALUE) - VEC_safe_push (gimple, heap, *cases, stmt); - else - { - gcc_assert (e->flags & EDGE_FALSE_VALUE); - VEC_safe_push (gimple, heap, *cases, NULL); - } - - VEC_safe_push (gimple, heap, *conditions, stmt); - if (!build_scop_conditions_1 (conditions, cases, e->dest, scop)) - { - res = false; - goto done; - } - VEC_pop (gimple, *conditions); - VEC_pop (gimple, *cases); - } - break; - - case GIMPLE_SWITCH: - { - unsigned i; - gimple_stmt_iterator gsi_search_gimple_label; - - for (i = 0; i < gimple_switch_num_labels (stmt); ++i) - { - basic_block bb_iter; - size_t k; - size_t n_cases = VEC_length (gimple, *conditions); - unsigned n = gimple_switch_num_labels (stmt); - - bb_child = label_to_block - (CASE_LABEL (gimple_switch_label (stmt, i))); - - for (k = 0; k < n; k++) - if (i != k - && label_to_block - (CASE_LABEL (gimple_switch_label (stmt, k))) == bb_child) - break; - - /* Switches with multiple case values for the same - block are not handled. */ - if (k != n - /* Switch cases with more than one predecessor are - not handled. */ - || VEC_length (edge, bb_child->preds) != 1) - { - res = false; - goto done; - } - - /* Recursively scan the corresponding 'case' block. */ - for (gsi_search_gimple_label = gsi_start_bb (bb_child); - !gsi_end_p (gsi_search_gimple_label); - gsi_next (&gsi_search_gimple_label)) - { - gimple label = gsi_stmt (gsi_search_gimple_label); - - if (gimple_code (label) == GIMPLE_LABEL) - { - tree t = gimple_label_label (label); - - gcc_assert (t == gimple_switch_label (stmt, i)); - VEC_replace (gimple, *cases, n_cases, label); - break; - } - } - - if (!build_scop_conditions_1 (conditions, cases, bb_child, scop)) - { - res = false; - goto done; - } - - /* Remove the scanned block from the dominator successors. */ - for (j = 0; VEC_iterate (basic_block, dom, j, bb_iter); j++) - if (bb_iter == bb_child) - { - VEC_unordered_remove (basic_block, dom, j); - break; - } - } - - VEC_pop (gimple, *conditions); - VEC_pop (gimple, *cases); - break; - } - - default: - break; - } - } - - /* Scan all immediate dominated successors. */ - for (i = 0; VEC_iterate (basic_block, dom, i, bb_child); i++) - if (!build_scop_conditions_1 (conditions, cases, bb_child, scop)) - { - res = false; - goto done; - } - - done: - VEC_free (basic_block, heap, dom); - return res; -} - -/* Record all conditions from SCOP. - - Returns false when the conditions contain scalar computations that - depend on the condition, i.e. when there are scalar phi nodes on - the junction after the condition. Only the computations occurring - on memory can be handled in the polyhedral model: operations that - define scalar evolutions in conditions, that can potentially be - used to index memory, can't be handled by the polyhedral model. */ - -static bool -build_scop_conditions (scop_p scop) -{ - bool res; - VEC (gimple, heap) *conditions = NULL; - VEC (gimple, heap) *cases = NULL; - - res = build_scop_conditions_1 (&conditions, &cases, SCOP_ENTRY (scop), scop); - - VEC_free (gimple, heap, conditions); - VEC_free (gimple, heap, cases); - return res; -} - -/* Build the current domain matrix: the loops belonging to the current - SCOP, and that vary for the execution of the current basic block. - Returns false if there is no loop in SCOP. */ - -static bool -build_scop_iteration_domain (scop_p scop) -{ - struct loop *loop; - CloogMatrix *outer_cstr; - int i; - - /* Build cloog loop for all loops, that are in the uppermost loop layer of - this SCoP. */ - for (i = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), i, loop); i++) - if (!loop_in_scop_p (loop_outer (loop), scop)) - { - /* The outermost constraints is a matrix that has: - -first column: eq/ineq boolean - -last column: a constant - -scop_nb_params columns for the parameters used in the scop. */ - outer_cstr = cloog_matrix_alloc (0, scop_nb_params (scop) + 2); - build_loop_iteration_domains (scop, loop, outer_cstr, 0); - cloog_matrix_free (outer_cstr); - } - - return (i != 0); -} - -/* Initializes an equation CY of the access matrix using the - information for a subscript from AF, relatively to the loop - indexes from LOOP_NEST and parameter indexes from PARAMS. NDIM is - the dimension of the array access, i.e. the number of - subscripts. Returns true when the operation succeeds. */ - -static bool -build_access_matrix_with_af (tree af, lambda_vector cy, - scop_p scop, int ndim) -{ - int param_col; - - switch (TREE_CODE (af)) - { - case POLYNOMIAL_CHREC: - { - struct loop *outer_loop; - tree left = CHREC_LEFT (af); - tree right = CHREC_RIGHT (af); - int var; - - if (TREE_CODE (right) != INTEGER_CST) - return false; - - outer_loop = get_loop (CHREC_VARIABLE (af)); - var = nb_loops_around_loop_in_scop (outer_loop, scop); - cy[var] = int_cst_value (right); - - switch (TREE_CODE (left)) - { - case POLYNOMIAL_CHREC: - return build_access_matrix_with_af (left, cy, scop, ndim); - - case INTEGER_CST: - cy[ndim - 1] = int_cst_value (left); - return true; - - default: - return build_access_matrix_with_af (left, cy, scop, ndim); - } - } - - case PLUS_EXPR: - build_access_matrix_with_af (TREE_OPERAND (af, 0), cy, scop, ndim); - build_access_matrix_with_af (TREE_OPERAND (af, 1), cy, scop, ndim); - return true; - - case MINUS_EXPR: - build_access_matrix_with_af (TREE_OPERAND (af, 0), cy, scop, ndim); - build_access_matrix_with_af (TREE_OPERAND (af, 1), cy, scop, ndim); - return true; - - case INTEGER_CST: - cy[ndim - 1] = int_cst_value (af); - return true; - - case SSA_NAME: - param_col = param_index (af, scop); - cy [ndim - scop_nb_params (scop) + param_col - 1] = 1; - return true; - - default: - /* FIXME: access_fn can have parameters. */ - return false; - } -} - -/* Initialize the access matrix in the data reference REF with respect - to the loop nesting LOOP_NEST. Return true when the operation - succeeded. */ - -static bool -build_access_matrix (data_reference_p ref, graphite_bb_p gb) -{ - int i, ndim = DR_NUM_DIMENSIONS (ref); - struct access_matrix *am = GGC_NEW (struct access_matrix); - - AM_MATRIX (am) = VEC_alloc (lambda_vector, heap, ndim); - DR_SCOP (ref) = GBB_SCOP (gb); - - for (i = 0; i < ndim; i++) - { - lambda_vector v = lambda_vector_new (ref_nb_loops (ref)); - scop_p scop = GBB_SCOP (gb); - tree af = DR_ACCESS_FN (ref, i); - - if (!build_access_matrix_with_af (af, v, scop, ref_nb_loops (ref))) - return false; - - VEC_safe_push (lambda_vector, heap, AM_MATRIX (am), v); - } - - DR_ACCESS_MATRIX (ref) = am; - return true; -} - -/* Build the access matrices for the data references in the SCOP. */ - -static void -build_scop_data_accesses (scop_p scop) -{ - int i; - graphite_bb_p gb; - - /* FIXME: Construction of access matrix is disabled until some - pass, like the data dependence analysis, is using it. */ - return; - - for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++) - { - int j; - data_reference_p dr; - - /* Construct the access matrix for each data ref, with respect to - the loop nest of the current BB in the considered SCOP. */ - for (j = 0; - VEC_iterate (data_reference_p, GBB_DATA_REFS (gb), j, dr); - j++) - { - bool res = build_access_matrix (dr, gb); - - /* FIXME: At this point the DRs should always have an affine - form. For the moment this fails as build_access_matrix - does not build matrices with parameters. */ - gcc_assert (res); - } - } -} - -/* Returns the tree variable from the name NAME that was given in - Cloog representation. All the parameters are stored in PARAMS, and - all the loop induction variables are stored in IVSTACK. - - FIXME: This is a hack, and Cloog should be fixed to not work with - variable names represented as "char *string", but with void - pointers that could be casted back to a tree. The only problem in - doing that is that Cloog's pretty printer still assumes that - variable names are char *strings. The solution would be to have a - function pointer for pretty-printing that can be redirected to be - print_generic_stmt in our case, or fprintf by default. - ??? Too ugly to live. */ - -static tree -clast_name_to_gcc (const char *name, VEC (name_tree, heap) *params, - loop_iv_stack ivstack) -{ - int i; - name_tree t; - tree iv; - - if (params) - for (i = 0; VEC_iterate (name_tree, params, i, t); i++) - if (!strcmp (name, t->name)) - return t->t; - - iv = loop_iv_stack_get_iv_from_name (ivstack, name); - if (iv) - return iv; - - gcc_unreachable (); -} - -/* Returns the maximal precision type for expressions E1 and E2. */ - -static inline tree -max_precision_type (tree e1, tree e2) -{ - tree type1 = TREE_TYPE (e1); - tree type2 = TREE_TYPE (e2); - return TYPE_PRECISION (type1) > TYPE_PRECISION (type2) ? type1 : type2; -} - -/* Converts a Cloog AST expression E back to a GCC expression tree - of type TYPE. */ - -static tree -clast_to_gcc_expression (tree type, struct clast_expr *e, - VEC (name_tree, heap) *params, - loop_iv_stack ivstack) -{ - switch (e->type) - { - case expr_term: - { - struct clast_term *t = (struct clast_term *) e; - - if (t->var) - { - if (value_one_p (t->val)) - { - tree name = clast_name_to_gcc (t->var, params, ivstack); - return fold_convert (type, name); - } - - else if (value_mone_p (t->val)) - { - tree name = clast_name_to_gcc (t->var, params, ivstack); - name = fold_convert (type, name); - return fold_build1 (NEGATE_EXPR, type, name); - } - else - { - tree name = clast_name_to_gcc (t->var, params, ivstack); - tree cst = gmp_cst_to_tree (type, t->val); - name = fold_convert (type, name); - return fold_build2 (MULT_EXPR, type, cst, name); - } - } - else - return gmp_cst_to_tree (type, t->val); - } - - case expr_red: - { - struct clast_reduction *r = (struct clast_reduction *) e; - - switch (r->type) - { - case clast_red_sum: - if (r->n == 1) - return clast_to_gcc_expression (type, r->elts[0], params, ivstack); - - else - { - tree tl = clast_to_gcc_expression (type, r->elts[0], params, ivstack); - tree tr = clast_to_gcc_expression (type, r->elts[1], params, ivstack); - - gcc_assert (r->n >= 1 - && r->elts[0]->type == expr_term - && r->elts[1]->type == expr_term); - - return fold_build2 (PLUS_EXPR, type, tl, tr); - } - - break; - - case clast_red_min: - if (r->n == 1) - return clast_to_gcc_expression (type, r->elts[0], params, ivstack); - - else if (r->n == 2) - { - tree tl = clast_to_gcc_expression (type, r->elts[0], params, ivstack); - tree tr = clast_to_gcc_expression (type, r->elts[1], params, ivstack); - return fold_build2 (MIN_EXPR, type, tl, tr); - } - - else - gcc_unreachable(); - - break; - - case clast_red_max: - if (r->n == 1) - return clast_to_gcc_expression (type, r->elts[0], params, ivstack); - - else if (r->n == 2) - { - tree tl = clast_to_gcc_expression (type, r->elts[0], params, ivstack); - tree tr = clast_to_gcc_expression (type, r->elts[1], params, ivstack); - return fold_build2 (MAX_EXPR, type, tl, tr); - } - - else - gcc_unreachable(); - - break; - - default: - gcc_unreachable (); - } - break; - } - - case expr_bin: - { - struct clast_binary *b = (struct clast_binary *) e; - struct clast_expr *lhs = (struct clast_expr *) b->LHS; - tree tl = clast_to_gcc_expression (type, lhs, params, ivstack); - tree tr = gmp_cst_to_tree (type, b->RHS); - - switch (b->type) - { - case clast_bin_fdiv: - return fold_build2 (FLOOR_DIV_EXPR, type, tl, tr); - - case clast_bin_cdiv: - return fold_build2 (CEIL_DIV_EXPR, type, tl, tr); - - case clast_bin_div: - return fold_build2 (EXACT_DIV_EXPR, type, tl, tr); - - case clast_bin_mod: - return fold_build2 (TRUNC_MOD_EXPR, type, tl, tr); - - default: - gcc_unreachable (); - } - } - - default: - gcc_unreachable (); - } - - return NULL_TREE; -} - -/* Returns the type for the expression E. */ - -static tree -gcc_type_for_clast_expr (struct clast_expr *e, - VEC (name_tree, heap) *params, - loop_iv_stack ivstack) -{ - switch (e->type) - { - case expr_term: - { - struct clast_term *t = (struct clast_term *) e; - - if (t->var) - return TREE_TYPE (clast_name_to_gcc (t->var, params, ivstack)); - else - return NULL_TREE; - } - - case expr_red: - { - struct clast_reduction *r = (struct clast_reduction *) e; - - if (r->n == 1) - return gcc_type_for_clast_expr (r->elts[0], params, ivstack); - else - { - int i; - for (i = 0; i < r->n; i++) - { - tree type = gcc_type_for_clast_expr (r->elts[i], params, ivstack); - if (type) - return type; - } - return NULL_TREE; - } - } - - case expr_bin: - { - struct clast_binary *b = (struct clast_binary *) e; - struct clast_expr *lhs = (struct clast_expr *) b->LHS; - return gcc_type_for_clast_expr (lhs, params, ivstack); - } - - default: - gcc_unreachable (); - } - - return NULL_TREE; -} - -/* Returns the type for the equation CLEQ. */ - -static tree -gcc_type_for_clast_eq (struct clast_equation *cleq, - VEC (name_tree, heap) *params, - loop_iv_stack ivstack) -{ - tree type = gcc_type_for_clast_expr (cleq->LHS, params, ivstack); - if (type) - return type; - - return gcc_type_for_clast_expr (cleq->RHS, params, ivstack); -} - -/* Translates a clast equation CLEQ to a tree. */ - -static tree -graphite_translate_clast_equation (scop_p scop, - struct clast_equation *cleq, - loop_iv_stack ivstack) -{ - enum tree_code comp; - tree type = gcc_type_for_clast_eq (cleq, SCOP_PARAMS (scop), ivstack); - tree lhs = clast_to_gcc_expression (type, cleq->LHS, SCOP_PARAMS (scop), ivstack); - tree rhs = clast_to_gcc_expression (type, cleq->RHS, SCOP_PARAMS (scop), ivstack); - - if (cleq->sign == 0) - comp = EQ_EXPR; - - else if (cleq->sign > 0) - comp = GE_EXPR; - - else - comp = LE_EXPR; - - return fold_build2 (comp, type, lhs, rhs); -} - -/* Creates the test for the condition in STMT. */ - -static tree -graphite_create_guard_cond_expr (scop_p scop, struct clast_guard *stmt, - loop_iv_stack ivstack) -{ - tree cond = NULL; - int i; - - for (i = 0; i < stmt->n; i++) - { - tree eq = graphite_translate_clast_equation (scop, &stmt->eq[i], ivstack); - - if (cond) - cond = fold_build2 (TRUTH_AND_EXPR, TREE_TYPE (eq), cond, eq); - else - cond = eq; - } - - return cond; -} - -/* Creates a new if region corresponding to Cloog's guard. */ - -static edge -graphite_create_new_guard (scop_p scop, edge entry_edge, - struct clast_guard *stmt, - loop_iv_stack ivstack) -{ - tree cond_expr = graphite_create_guard_cond_expr (scop, stmt, ivstack); - edge exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr); - return exit_edge; -} - -/* Walks a CLAST and returns the first statement in the body of a - loop. */ - -static struct clast_user_stmt * -clast_get_body_of_loop (struct clast_stmt *stmt) -{ - if (!stmt - || CLAST_STMT_IS_A (stmt, stmt_user)) - return (struct clast_user_stmt *) stmt; - - if (CLAST_STMT_IS_A (stmt, stmt_for)) - return clast_get_body_of_loop (((struct clast_for *) stmt)->body); - - if (CLAST_STMT_IS_A (stmt, stmt_guard)) - return clast_get_body_of_loop (((struct clast_guard *) stmt)->then); - - if (CLAST_STMT_IS_A (stmt, stmt_block)) - return clast_get_body_of_loop (((struct clast_block *) stmt)->body); - - gcc_unreachable (); -} - -/* Returns the induction variable for the loop that gets translated to - STMT. */ - -static tree -gcc_type_for_iv_of_clast_loop (struct clast_for *stmt_for) -{ - struct clast_user_stmt *stmt = clast_get_body_of_loop ((struct clast_stmt *) stmt_for); - const char *cloog_iv = stmt_for->iterator; - CloogStatement *cs = stmt->statement; - graphite_bb_p gbb = (graphite_bb_p) cloog_statement_usr (cs); - - return gcc_type_for_cloog_iv (cloog_iv, gbb); -} - -/* Creates a new LOOP corresponding to Cloog's STMT. Inserts an induction - variable for the new LOOP. New LOOP is attached to CFG starting at - ENTRY_EDGE. LOOP is inserted into the loop tree and becomes the child - loop of the OUTER_LOOP. */ - -static struct loop * -graphite_create_new_loop (scop_p scop, edge entry_edge, - struct clast_for *stmt, loop_iv_stack ivstack, - loop_p outer) -{ - tree type = gcc_type_for_iv_of_clast_loop (stmt); - VEC (name_tree, heap) *params = SCOP_PARAMS (scop); - tree lb = clast_to_gcc_expression (type, stmt->LB, params, ivstack); - tree ub = clast_to_gcc_expression (type, stmt->UB, params, ivstack); - tree stride = gmp_cst_to_tree (type, stmt->stride); - tree ivvar = create_tmp_var (type, "graphiteIV"); - tree iv_before; - loop_p loop = create_empty_loop_on_edge - (entry_edge, lb, stride, ub, ivvar, &iv_before, - outer ? outer : entry_edge->src->loop_father); - - add_referenced_var (ivvar); - loop_iv_stack_push_iv (ivstack, iv_before, stmt->iterator); - return loop; -} - -/* Rename the SSA_NAMEs used in STMT and that appear in IVSTACK. */ - -static void -rename_variables_in_stmt (gimple stmt, htab_t map) -{ - ssa_op_iter iter; - use_operand_p use_p; - - FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE) - { - tree use = USE_FROM_PTR (use_p); - tree new_name = get_new_name_from_old_name (map, use); - - replace_exp (use_p, new_name); - } - - update_stmt (stmt); -} - -/* Returns true if SSA_NAME is a parameter of SCOP. */ - -static bool -is_parameter (scop_p scop, tree ssa_name) -{ - int i; - VEC (name_tree, heap) *params = SCOP_PARAMS (scop); - name_tree param; - - for (i = 0; VEC_iterate (name_tree, params, i, param); i++) - if (param->t == ssa_name) - return true; - - return false; -} - -/* Returns true if NAME is an induction variable. */ - -static bool -is_iv (tree name) -{ - return gimple_code (SSA_NAME_DEF_STMT (name)) == GIMPLE_PHI; -} - -static void expand_scalar_variables_stmt (gimple, basic_block, scop_p, - loop_p, htab_t); - -/* Constructs a tree which only contains old_ivs and parameters. Any - other variables that are defined outside BB will be eliminated by - using their definitions in the constructed tree. OLD_LOOP_FATHER - is the original loop that contained BB. */ - -static tree -expand_scalar_variables_expr (tree type, tree op0, enum tree_code code, - tree op1, basic_block bb, scop_p scop, - loop_p old_loop_father, htab_t map) -{ - if ((TREE_CODE_CLASS (code) == tcc_constant - && code == INTEGER_CST) - || TREE_CODE_CLASS (code) == tcc_reference) - return op0; - - if (TREE_CODE_CLASS (code) == tcc_unary) - { - tree op0_type = TREE_TYPE (op0); - enum tree_code op0_code = TREE_CODE (op0); - tree op0_expr = - expand_scalar_variables_expr (op0_type, op0, op0_code, - NULL, bb, scop, old_loop_father, map); - - return fold_build1 (code, type, op0_expr); - } - - if (TREE_CODE_CLASS (code) == tcc_binary) - { - tree op0_type = TREE_TYPE (op0); - enum tree_code op0_code = TREE_CODE (op0); - tree op0_expr = - expand_scalar_variables_expr (op0_type, op0, op0_code, - NULL, bb, scop, old_loop_father, map); - tree op1_type = TREE_TYPE (op1); - enum tree_code op1_code = TREE_CODE (op1); - tree op1_expr = - expand_scalar_variables_expr (op1_type, op1, op1_code, - NULL, bb, scop, old_loop_father, map); - - return fold_build2 (code, type, op0_expr, op1_expr); - } - - if (code == SSA_NAME) - { - tree var0, var1; - gimple def_stmt; - enum tree_code subcode; - - if (is_parameter (scop, op0) - || is_iv (op0)) - return get_new_name_from_old_name (map, op0); - - def_stmt = SSA_NAME_DEF_STMT (op0); - - if (gimple_bb (def_stmt) == bb) - { - /* If the defining statement is in the basic block already - we do not need to create a new expression for it, we - only need to ensure its operands are expanded. */ - expand_scalar_variables_stmt (def_stmt, bb, scop, - old_loop_father, map); - return get_new_name_from_old_name (map, op0); - } - else - { - if (gimple_code (def_stmt) != GIMPLE_ASSIGN - || !bb_in_scop_p (gimple_bb (def_stmt), scop)) - return get_new_name_from_old_name (map, op0); - - var0 = gimple_assign_rhs1 (def_stmt); - subcode = gimple_assign_rhs_code (def_stmt); - var1 = gimple_assign_rhs2 (def_stmt); - - return expand_scalar_variables_expr (type, var0, subcode, var1, - bb, scop, old_loop_father, map); - } - } - - gcc_unreachable (); - return NULL; -} - -/* Replicates any uses of non-parameters and non-old-ivs variablesthat - are defind outside BB with code that is inserted in BB. - OLD_LOOP_FATHER is the original loop that contained STMT. */ - -static void -expand_scalar_variables_stmt (gimple stmt, basic_block bb, scop_p scop, - loop_p old_loop_father, htab_t map) -{ - ssa_op_iter iter; - use_operand_p use_p; - - FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE) - { - tree use = USE_FROM_PTR (use_p); - tree type = TREE_TYPE (use); - enum tree_code code = TREE_CODE (use); - tree use_expr = expand_scalar_variables_expr (type, use, code, NULL, bb, - scop, old_loop_father, map); - if (use_expr != use) - { - gimple_stmt_iterator gsi = gsi_after_labels (bb); - tree new_use = - force_gimple_operand_gsi (&gsi, use_expr, true, NULL, - true, GSI_NEW_STMT); - replace_exp (use_p, new_use); - } - } - - update_stmt (stmt); -} - -/* Copies the definitions outside of BB of variables that are not - induction variables nor parameters. BB must only contain - "external" references to these types of variables. OLD_LOOP_FATHER - is the original loop that contained BB. */ - -static void -expand_scalar_variables (basic_block bb, scop_p scop, - loop_p old_loop_father, htab_t map) -{ - gimple_stmt_iterator gsi; - - for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi);) - { - gimple stmt = gsi_stmt (gsi); - expand_scalar_variables_stmt (stmt, bb, scop, old_loop_father, map); - gsi_next (&gsi); - } -} - -/* Rename all the SSA_NAMEs from block BB according to the MAP. */ - -static void -rename_variables (basic_block bb, htab_t map) -{ - gimple_stmt_iterator gsi; - - for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi)) - rename_variables_in_stmt (gsi_stmt (gsi), map); -} - -/* Remove condition from BB. */ - -static void -remove_condition (basic_block bb) -{ - gimple last = last_stmt (bb); - - if (last && gimple_code (last) == GIMPLE_COND) - { - gimple_stmt_iterator gsi = gsi_last_bb (bb); - gsi_remove (&gsi, true); - } -} - -/* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag set. */ - -static edge -get_true_edge_from_guard_bb (basic_block bb) -{ - edge e; - edge_iterator ei; - - FOR_EACH_EDGE (e, ei, bb->succs) - if (e->flags & EDGE_TRUE_VALUE) - return e; - - gcc_unreachable (); - return NULL; -} - -/* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag cleared. */ - -static edge -get_false_edge_from_guard_bb (basic_block bb) -{ - edge e; - edge_iterator ei; - - FOR_EACH_EDGE (e, ei, bb->succs) - if (!(e->flags & EDGE_TRUE_VALUE)) - return e; - - gcc_unreachable (); - return NULL; -} - -/* Inserts in MAP a tuple (OLD_NAME, NEW_NAME) for the induction - variables of the loops around GBB in SCOP, i.e. GBB_LOOPS. - NEW_NAME is obtained from IVSTACK. IVSTACK has the same stack - ordering as GBB_LOOPS. */ - -static void -build_iv_mapping (loop_iv_stack ivstack, htab_t map, gbb_p gbb, scop_p scop) -{ - int i; - name_tree iv; - PTR *slot; - - for (i = 0; VEC_iterate (name_tree, SCOP_OLDIVS (scop), i, iv); i++) - { - struct rename_map_elt tmp; - - if (!flow_bb_inside_loop_p (iv->loop, GBB_BB (gbb))) - continue; - - tmp.old_name = iv->t; - slot = htab_find_slot (map, &tmp, INSERT); - - if (!*slot) - { - tree new_name = loop_iv_stack_get_iv (ivstack, - gbb_loop_index (gbb, iv->loop)); - *slot = new_rename_map_elt (iv->t, new_name); - } - } -} - -/* Register in MAP the tuple (old_name, new_name). */ - -static void -register_old_and_new_names (htab_t map, tree old_name, tree new_name) -{ - struct rename_map_elt tmp; - PTR *slot; - - tmp.old_name = old_name; - slot = htab_find_slot (map, &tmp, INSERT); - - if (!*slot) - *slot = new_rename_map_elt (old_name, new_name); -} - -/* Create a duplicate of the basic block BB. NOTE: This does not - preserve SSA form. */ - -static void -graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb, htab_t map) -{ - gimple_stmt_iterator gsi, gsi_tgt; - - gsi_tgt = gsi_start_bb (new_bb); - for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) - { - def_operand_p def_p; - ssa_op_iter op_iter; - int region; - gimple stmt = gsi_stmt (gsi); - gimple copy; - - if (gimple_code (stmt) == GIMPLE_LABEL) - continue; - - /* Create a new copy of STMT and duplicate STMT's virtual - operands. */ - copy = gimple_copy (stmt); - gsi_insert_after (&gsi_tgt, copy, GSI_NEW_STMT); - mark_symbols_for_renaming (copy); - - region = lookup_stmt_eh_region (stmt); - if (region >= 0) - add_stmt_to_eh_region (copy, region); - gimple_duplicate_stmt_histograms (cfun, copy, cfun, stmt); - - /* Create new names for all the definitions created by COPY and - add replacement mappings for each new name. */ - FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_DEF) - { - tree old_name = DEF_FROM_PTR (def_p); - tree new_name = create_new_def_for (old_name, copy, def_p); - register_old_and_new_names (map, old_name, new_name); - } - } -} - -/* Records in SCOP_LIVEOUT_RENAMES the names that are live out of - the SCOP and that appear in the RENAME_MAP. */ - -static void -register_scop_liveout_renames (scop_p scop, htab_t rename_map) -{ - int i; - sese region = SCOP_REGION (scop); - - for (i = 0; i < SESE_NUM_VER (region); i++) - if (bitmap_bit_p (SESE_LIVEOUT (region), i) - && is_gimple_reg (ssa_name (i))) - { - tree old_name = ssa_name (i); - tree new_name = get_new_name_from_old_name (rename_map, old_name); - - register_old_and_new_names (SCOP_LIVEOUT_RENAMES (scop), - old_name, new_name); - } -} - -/* Copies BB and includes in the copied BB all the statements that can - be reached following the use-def chains from the memory accesses, - and returns the next edge following this new block. */ - -static edge -copy_bb_and_scalar_dependences (basic_block bb, scop_p scop, - loop_p context_loop, - edge next_e, htab_t map) -{ - basic_block new_bb = split_edge (next_e); - - next_e = single_succ_edge (new_bb); - graphite_copy_stmts_from_block (bb, new_bb, map); - remove_condition (new_bb); - rename_variables (new_bb, map); - remove_phi_nodes (new_bb); - expand_scalar_variables (new_bb, scop, context_loop, map); - register_scop_liveout_renames (scop, map); - - return next_e; -} - -/* Helper function for htab_traverse in insert_loop_close_phis. */ - -static int -add_loop_exit_phis (void **slot, void *s) -{ - struct rename_map_elt *entry = (struct rename_map_elt *) *slot; - tree new_name = entry->new_name; - basic_block bb = (basic_block) s; - gimple phi = create_phi_node (new_name, bb); - tree res = create_new_def_for (gimple_phi_result (phi), phi, - gimple_phi_result_ptr (phi)); - - add_phi_arg (phi, new_name, single_pred_edge (bb)); - - entry->new_name = res; - *slot = entry; - return 1; -} - -/* Iterate over the SCOP_LIVEOUT_RENAMES (SCOP) and get tuples of the - form (OLD_NAME, NEW_NAME). Insert in BB "RES = phi (NEW_NAME)", - and finally register in SCOP_LIVEOUT_RENAMES (scop) the tuple - (OLD_NAME, RES). */ - -static void -insert_loop_close_phis (scop_p scop, basic_block bb) -{ - update_ssa (TODO_update_ssa); - htab_traverse (SCOP_LIVEOUT_RENAMES (scop), add_loop_exit_phis, bb); - update_ssa (TODO_update_ssa); -} - -/* Helper structure for htab_traverse in insert_guard_phis. */ - -struct igp { - basic_block bb; - edge true_edge, false_edge; - htab_t liveout_before_guard; -}; - -/* Return the default name that is before the guard. */ - -static tree -default_liveout_before_guard (htab_t liveout_before_guard, tree old_name) -{ - tree res = get_new_name_from_old_name (liveout_before_guard, old_name); - - if (res == old_name) - { - if (is_gimple_reg (res)) - return fold_convert (TREE_TYPE (res), integer_zero_node); - return gimple_default_def (cfun, res); - } - - return res; -} - -/* Helper function for htab_traverse in insert_guard_phis. */ - -static int -add_guard_exit_phis (void **slot, void *s) -{ - struct rename_map_elt *entry = (struct rename_map_elt *) *slot; - struct igp *i = (struct igp *) s; - basic_block bb = i->bb; - edge true_edge = i->true_edge; - edge false_edge = i->false_edge; - tree name1 = entry->new_name; - tree name2 = default_liveout_before_guard (i->liveout_before_guard, - entry->old_name); - gimple phi = create_phi_node (name1, bb); - tree res = create_new_def_for (gimple_phi_result (phi), phi, - gimple_phi_result_ptr (phi)); - - add_phi_arg (phi, name1, true_edge); - add_phi_arg (phi, name2, false_edge); - - entry->new_name = res; - *slot = entry; - return 1; -} - -/* Iterate over the SCOP_LIVEOUT_RENAMES (SCOP) and get tuples of the - form (OLD_NAME, NAME1). If there is a correspondent tuple of - OLD_NAME in LIVEOUT_BEFORE_GUARD, i.e. (OLD_NAME, NAME2) then - insert in BB - - | RES = phi (NAME1 (on TRUE_EDGE), NAME2 (on FALSE_EDGE))" - - if there is no tuple for OLD_NAME in LIVEOUT_BEFORE_GUARD, insert - - | RES = phi (NAME1 (on TRUE_EDGE), - | DEFAULT_DEFINITION of NAME1 (on FALSE_EDGE))". - - Finally register in SCOP_LIVEOUT_RENAMES (scop) the tuple - (OLD_NAME, RES). */ - -static void -insert_guard_phis (scop_p scop, basic_block bb, edge true_edge, - edge false_edge, htab_t liveout_before_guard) -{ - struct igp i; - i.bb = bb; - i.true_edge = true_edge; - i.false_edge = false_edge; - i.liveout_before_guard = liveout_before_guard; - - update_ssa (TODO_update_ssa); - htab_traverse (SCOP_LIVEOUT_RENAMES (scop), add_guard_exit_phis, &i); - update_ssa (TODO_update_ssa); -} - -/* Helper function for htab_traverse. */ - -static int -copy_renames (void **slot, void *s) -{ - struct rename_map_elt *entry = (struct rename_map_elt *) *slot; - htab_t res = (htab_t) s; - tree old_name = entry->old_name; - tree new_name = entry->new_name; - struct rename_map_elt tmp; - PTR *x; - - tmp.old_name = old_name; - x = htab_find_slot (res, &tmp, INSERT); - - if (!*x) - *x = new_rename_map_elt (old_name, new_name); - - return 1; -} - -/* Translates a CLAST statement STMT to GCC representation in the - context of a SCOP. - - - NEXT_E is the edge where new generated code should be attached. - - CONTEXT_LOOP is the loop in which the generated code will be placed - (might be NULL). - - IVSTACK contains the surrounding loops around the statement to be - translated. -*/ - -static edge -translate_clast (scop_p scop, struct loop *context_loop, - struct clast_stmt *stmt, edge next_e, loop_iv_stack ivstack) -{ - if (!stmt) - return next_e; - - if (CLAST_STMT_IS_A (stmt, stmt_root)) - return translate_clast (scop, context_loop, stmt->next, next_e, ivstack); - - if (CLAST_STMT_IS_A (stmt, stmt_user)) - { - htab_t map; - CloogStatement *cs = ((struct clast_user_stmt *) stmt)->statement; - graphite_bb_p gbb = (graphite_bb_p) cloog_statement_usr (cs); - - if (GBB_BB (gbb) == ENTRY_BLOCK_PTR) - return next_e; - - map = htab_create (10, rename_map_elt_info, eq_rename_map_elts, free); - loop_iv_stack_patch_for_consts (ivstack, (struct clast_user_stmt *) stmt); - build_iv_mapping (ivstack, map, gbb, scop); - next_e = copy_bb_and_scalar_dependences (GBB_BB (gbb), scop, - context_loop, next_e, map); - htab_delete (map); - loop_iv_stack_remove_constants (ivstack); - update_ssa (TODO_update_ssa); - recompute_all_dominators (); - graphite_verify (); - return translate_clast (scop, context_loop, stmt->next, next_e, ivstack); - } - - if (CLAST_STMT_IS_A (stmt, stmt_for)) - { - struct loop *loop - = graphite_create_new_loop (scop, next_e, (struct clast_for *) stmt, - ivstack, context_loop ? context_loop - : get_loop (0)); - edge last_e = single_exit (loop); - - next_e = translate_clast (scop, loop, ((struct clast_for *) stmt)->body, - single_pred_edge (loop->latch), ivstack); - redirect_edge_succ_nodup (next_e, loop->latch); - - set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src); - loop_iv_stack_pop (ivstack); - last_e = single_succ_edge (split_edge (last_e)); - insert_loop_close_phis (scop, last_e->src); - - recompute_all_dominators (); - graphite_verify (); - return translate_clast (scop, context_loop, stmt->next, last_e, ivstack); - } - - if (CLAST_STMT_IS_A (stmt, stmt_guard)) - { - htab_t liveout_before_guard = htab_create (10, rename_map_elt_info, - eq_rename_map_elts, free); - edge last_e = graphite_create_new_guard (scop, next_e, - ((struct clast_guard *) stmt), - ivstack); - edge true_e = get_true_edge_from_guard_bb (next_e->dest); - edge false_e = get_false_edge_from_guard_bb (next_e->dest); - edge exit_true_e = single_succ_edge (true_e->dest); - edge exit_false_e = single_succ_edge (false_e->dest); - - htab_traverse (SCOP_LIVEOUT_RENAMES (scop), copy_renames, - liveout_before_guard); - - next_e = translate_clast (scop, context_loop, - ((struct clast_guard *) stmt)->then, - true_e, ivstack); - insert_guard_phis (scop, last_e->src, exit_true_e, exit_false_e, - liveout_before_guard); - htab_delete (liveout_before_guard); - recompute_all_dominators (); - graphite_verify (); - - return translate_clast (scop, context_loop, stmt->next, last_e, ivstack); - } - - if (CLAST_STMT_IS_A (stmt, stmt_block)) - { - next_e = translate_clast (scop, context_loop, - ((struct clast_block *) stmt)->body, - next_e, ivstack); - recompute_all_dominators (); - graphite_verify (); - return translate_clast (scop, context_loop, stmt->next, next_e, ivstack); - } - - gcc_unreachable (); -} - -/* Free the SCATTERING domain list. */ - -static void -free_scattering (CloogDomainList *scattering) -{ - while (scattering) - { - CloogDomain *dom = cloog_domain (scattering); - CloogDomainList *next = cloog_next_domain (scattering); - - cloog_domain_free (dom); - free (scattering); - scattering = next; - } -} - -/* Build cloog program for SCoP. */ - -static void -build_cloog_prog (scop_p scop) -{ - int i; - int max_nb_loops = scop_max_loop_depth (scop); - graphite_bb_p gbb; - CloogLoop *loop_list = NULL; - CloogBlockList *block_list = NULL; - CloogDomainList *scattering = NULL; - CloogProgram *prog = SCOP_PROG (scop); - int nbs = 2 * max_nb_loops + 1; - int *scaldims = (int *) xmalloc (nbs * (sizeof (int))); - - cloog_program_set_nb_scattdims (prog, nbs); - initialize_cloog_names (scop); - - for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gbb); i++) - { - /* Build new block. */ - CloogMatrix *domain = GBB_DOMAIN (gbb); - CloogStatement *stmt = cloog_statement_alloc (GBB_BB (gbb)->index); - CloogBlock *block = cloog_block_alloc (stmt, 0, NULL, - nb_loops_around_gb (gbb)); - cloog_statement_set_usr (stmt, gbb); - - /* Add empty domain to all bbs, which do not yet have a domain, as they - are not part of any loop. */ - if (domain == NULL) - { - domain = cloog_matrix_alloc (0, scop_nb_params (scop) + 2); - GBB_DOMAIN (gbb) = domain; - } - - /* Build loop list. */ - { - CloogLoop *new_loop_list = cloog_loop_malloc (); - cloog_loop_set_next (new_loop_list, loop_list); - cloog_loop_set_domain (new_loop_list, - cloog_domain_matrix2domain (domain)); - cloog_loop_set_block (new_loop_list, block); - loop_list = new_loop_list; - } - - /* Build block list. */ - { - CloogBlockList *new_block_list = cloog_block_list_malloc (); - - cloog_block_list_set_next (new_block_list, block_list); - cloog_block_list_set_block (new_block_list, block); - block_list = new_block_list; - } - - /* Build scattering list. */ - { - /* XXX: Replace with cloog_domain_list_alloc(), when available. */ - CloogDomainList *new_scattering - = (CloogDomainList *) xmalloc (sizeof (CloogDomainList)); - CloogMatrix *scat_mat = schedule_to_scattering (gbb, nbs); - - cloog_set_next_domain (new_scattering, scattering); - cloog_set_domain (new_scattering, - cloog_domain_matrix2domain (scat_mat)); - scattering = new_scattering; - cloog_matrix_free (scat_mat); - } - } - - cloog_program_set_loop (prog, loop_list); - cloog_program_set_blocklist (prog, block_list); - - for (i = 0; i < nbs; i++) - scaldims[i] = 0 ; - - cloog_program_set_scaldims (prog, scaldims); - - /* Extract scalar dimensions to simplify the code generation problem. */ - cloog_program_extract_scalars (prog, scattering); - - /* Apply scattering. */ - cloog_program_scatter (prog, scattering); - free_scattering (scattering); - - /* Iterators corresponding to scalar dimensions have to be extracted. */ - cloog_names_scalarize (cloog_program_names (prog), nbs, - cloog_program_scaldims (prog)); - - /* Free blocklist. */ - { - CloogBlockList *next = cloog_program_blocklist (prog); - - while (next) - { - CloogBlockList *toDelete = next; - next = cloog_block_list_next (next); - cloog_block_list_set_next (toDelete, NULL); - cloog_block_list_set_block (toDelete, NULL); - cloog_block_list_free (toDelete); - } - cloog_program_set_blocklist (prog, NULL); - } -} - -/* Return the options that will be used in GLOOG. */ - -static CloogOptions * -set_cloog_options (void) -{ - CloogOptions *options = cloog_options_malloc (); - - /* Change cloog output language to C. If we do use FORTRAN instead, cloog - will stop e.g. with "ERROR: unbounded loops not allowed in FORTRAN.", if - we pass an incomplete program to cloog. */ - options->language = LANGUAGE_C; - - /* Enable complex equality spreading: removes dummy statements - (assignments) in the generated code which repeats the - substitution equations for statements. This is useless for - GLooG. */ - options->esp = 1; - - /* Enable C pretty-printing mode: normalizes the substitution - equations for statements. */ - options->cpp = 1; - - /* Allow cloog to build strides with a stride width different to one. - This example has stride = 4: - - for (i = 0; i < 20; i += 4) - A */ - options->strides = 1; - - /* Disable optimizations and make cloog generate source code closer to the - input. This is useful for debugging, but later we want the optimized - code. - - XXX: We can not disable optimizations, as loop blocking is not working - without them. */ - if (0) - { - options->f = -1; - options->l = INT_MAX; - } - - return options; -} - -/* Prints STMT to STDERR. */ - -void -debug_clast_stmt (struct clast_stmt *stmt) -{ - CloogOptions *options = set_cloog_options (); - - pprint (stderr, stmt, 0, options); -} - -/* Find the right transform for the SCOP, and return a Cloog AST - representing the new form of the program. */ - -static struct clast_stmt * -find_transform (scop_p scop) -{ - struct clast_stmt *stmt; - CloogOptions *options = set_cloog_options (); - - /* Connect new cloog prog generation to graphite. */ - build_cloog_prog (scop); - - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "Cloog Input [\n"); - cloog_program_print (dump_file, SCOP_PROG(scop)); - fprintf (dump_file, "]\n"); - } - - SCOP_PROG (scop) = cloog_program_generate (SCOP_PROG (scop), options); - stmt = cloog_clast_create (SCOP_PROG (scop), options); - - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "Cloog Output[\n"); - pprint (dump_file, stmt, 0, options); - cloog_program_dump_cloog (dump_file, SCOP_PROG (scop)); - fprintf (dump_file, "]\n"); - } - - cloog_options_free (options); - return stmt; -} - -/* Returns true when it is possible to generate code for this STMT. - For the moment we cannot generate code when Cloog decides to - duplicate a statement, as we do not do a copy, but a move. - USED_BASIC_BLOCKS records the blocks that have already been seen. - We return false if we have to generate code twice for the same - block. */ - -static bool -can_generate_code_stmt (struct clast_stmt *stmt, - struct pointer_set_t *used_basic_blocks) -{ - if (!stmt) - return true; - - if (CLAST_STMT_IS_A (stmt, stmt_root)) - return can_generate_code_stmt (stmt->next, used_basic_blocks); - - if (CLAST_STMT_IS_A (stmt, stmt_user)) - { - CloogStatement *cs = ((struct clast_user_stmt *) stmt)->statement; - graphite_bb_p gbb = (graphite_bb_p) cloog_statement_usr (cs); - - if (pointer_set_contains (used_basic_blocks, gbb)) - return false; - pointer_set_insert (used_basic_blocks, gbb); - return can_generate_code_stmt (stmt->next, used_basic_blocks); - } - - if (CLAST_STMT_IS_A (stmt, stmt_for)) - return can_generate_code_stmt (((struct clast_for *) stmt)->body, - used_basic_blocks) - && can_generate_code_stmt (stmt->next, used_basic_blocks); - - if (CLAST_STMT_IS_A (stmt, stmt_guard)) - return can_generate_code_stmt (((struct clast_guard *) stmt)->then, - used_basic_blocks); - - if (CLAST_STMT_IS_A (stmt, stmt_block)) - return can_generate_code_stmt (((struct clast_block *) stmt)->body, - used_basic_blocks) - && can_generate_code_stmt (stmt->next, used_basic_blocks); - - return false; -} - -/* Returns true when it is possible to generate code for this STMT. */ - -static bool -can_generate_code (struct clast_stmt *stmt) -{ - bool result; - struct pointer_set_t *used_basic_blocks = pointer_set_create (); - - result = can_generate_code_stmt (stmt, used_basic_blocks); - pointer_set_destroy (used_basic_blocks); - return result; -} - -/* Remove from the CFG the REGION. */ - -static inline void -remove_sese_region (sese region) -{ - VEC (basic_block, heap) *bbs = NULL; - basic_block entry_bb = SESE_ENTRY (region)->dest; - basic_block exit_bb = SESE_EXIT (region)->dest; - basic_block bb; - int i; - - VEC_safe_push (basic_block, heap, bbs, entry_bb); - gather_blocks_in_sese_region (entry_bb, exit_bb, &bbs); - - for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++) - delete_basic_block (bb); - - VEC_free (basic_block, heap, bbs); -} - -typedef struct ifsese { - sese region; - sese true_region; - sese false_region; -} *ifsese; - -static inline edge -if_region_entry (ifsese if_region) -{ - return SESE_ENTRY (if_region->region); -} - -static inline edge -if_region_exit (ifsese if_region) -{ - return SESE_EXIT (if_region->region); -} - -static inline basic_block -if_region_get_condition_block (ifsese if_region) -{ - return if_region_entry (if_region)->dest; -} - -static inline void -if_region_set_false_region (ifsese if_region, sese region) -{ - basic_block condition = if_region_get_condition_block (if_region); - edge false_edge = get_false_edge_from_guard_bb (condition); - edge entry_region = SESE_ENTRY (region); - edge exit_region = SESE_EXIT (region); - basic_block before_region = entry_region->src; - basic_block last_in_region = exit_region->src; - void **slot = htab_find_slot_with_hash (current_loops->exits, exit_region, - htab_hash_pointer (exit_region), - NO_INSERT); - - entry_region->flags = false_edge->flags; - false_edge->flags = exit_region->flags; - - redirect_edge_pred (entry_region, condition); - redirect_edge_pred (exit_region, before_region); - redirect_edge_pred (false_edge, last_in_region); - - exit_region->flags = EDGE_FALLTHRU; - recompute_all_dominators (); - - SESE_EXIT (region) = single_succ_edge (false_edge->dest); - if_region->false_region = region; - - if (slot) - { - struct loop_exit *loop_exit = GGC_CNEW (struct loop_exit); - - memcpy (loop_exit, *((struct loop_exit **) slot), sizeof (struct loop_exit)); - htab_clear_slot (current_loops->exits, slot); - - slot = htab_find_slot_with_hash (current_loops->exits, false_edge, - htab_hash_pointer (false_edge), - INSERT); - loop_exit->e = false_edge; - *slot = loop_exit; - false_edge->src->loop_father->exits->next = loop_exit; - } -} - -static ifsese -create_if_region_on_edge (edge entry, tree condition) -{ - edge e; - edge_iterator ei; - sese sese_region = GGC_NEW (struct sese); - sese true_region = GGC_NEW (struct sese); - sese false_region = GGC_NEW (struct sese); - ifsese if_region = GGC_NEW (struct ifsese); - edge exit = create_empty_if_region_on_edge (entry, condition); - - if_region->region = sese_region; - if_region->region->entry = entry; - if_region->region->exit = exit; - - FOR_EACH_EDGE (e, ei, entry->dest->succs) - { - if (e->flags & EDGE_TRUE_VALUE) - { - true_region->entry = e; - true_region->exit = single_succ_edge (e->dest); - if_region->true_region = true_region; - } - else if (e->flags & EDGE_FALSE_VALUE) - { - false_region->entry = e; - false_region->exit = single_succ_edge (e->dest); - if_region->false_region = false_region; - } - } - - return if_region; -} - -/* Moves REGION in a condition expression: - | if (1) - | ; - | else - | REGION; -*/ - -static ifsese -move_sese_in_condition (sese region) -{ - basic_block pred_block = split_edge (SESE_ENTRY (region)); - ifsese if_region = NULL; - - SESE_ENTRY (region) = single_succ_edge (pred_block); - if_region = create_if_region_on_edge (single_pred_edge (pred_block), integer_one_node); - if_region_set_false_region (if_region, region); - - return if_region; -} - -/* Add exit phis for USE on EXIT. */ - -static void -scop_add_exit_phis_edge (basic_block exit, tree use, edge false_e, edge true_e) -{ - gimple phi = create_phi_node (use, exit); - - create_new_def_for (gimple_phi_result (phi), phi, - gimple_phi_result_ptr (phi)); - add_phi_arg (phi, use, false_e); - add_phi_arg (phi, use, true_e); -} - -/* Add phi nodes for VAR that is used in LIVEIN. Phi nodes are - inserted in block BB. */ - -static void -scop_add_exit_phis_var (basic_block bb, tree var, bitmap livein, - edge false_e, edge true_e) -{ - bitmap def; - basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (var)); - - if (is_gimple_reg (var)) - bitmap_clear_bit (livein, def_bb->index); - else - bitmap_set_bit (livein, def_bb->index); - - def = BITMAP_ALLOC (NULL); - bitmap_set_bit (def, def_bb->index); - compute_global_livein (livein, def); - BITMAP_FREE (def); - - scop_add_exit_phis_edge (bb, var, false_e, true_e); -} - -/* Insert in the block BB phi nodes for variables defined in REGION - and used outside the REGION. The code generation moves REGION in - the else clause of an "if (1)" and generates code in the then - clause that is at this point empty: - - | if (1) - | empty; - | else - | REGION; -*/ - -static void -scop_insert_phis_for_liveouts (sese region, basic_block bb, - edge false_e, edge true_e) -{ - unsigned i; - bitmap_iterator bi; - - update_ssa (TODO_update_ssa); - - EXECUTE_IF_SET_IN_BITMAP (SESE_LIVEOUT (region), 0, i, bi) - scop_add_exit_phis_var (bb, ssa_name (i), SESE_LIVEIN_VER (region, i), - false_e, true_e); - - update_ssa (TODO_update_ssa); -} - -/* Adjusts the phi nodes in the block BB for variables defined in - SCOP_REGION and used outside the SCOP_REGION. The code generation - moves SCOP_REGION in the else clause of an "if (1)" and generates - code in the then clause: - - | if (1) - | generated code from REGION; - | else - | REGION; - - To adjust the phi nodes after the condition, SCOP_LIVEOUT_RENAMES - hash table is used: this stores for a name that is part of the - LIVEOUT of SCOP_REGION its new name in the generated code. */ - -static void -scop_adjust_phis_for_liveouts (scop_p scop, basic_block bb, edge false_e, - edge true_e) -{ - gimple_stmt_iterator si; - - for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si)) - { - unsigned i, false_i; - gimple phi = gsi_stmt (si); - - if (!is_gimple_reg (PHI_RESULT (phi))) - continue; - - for (i = 0; i < gimple_phi_num_args (phi); i++) - if (gimple_phi_arg_edge (phi, i) == false_e) - { - false_i = i; - break; - } - - for (i = 0; i < gimple_phi_num_args (phi); i++) - if (gimple_phi_arg_edge (phi, i) == true_e) - { - tree old_name = gimple_phi_arg_def (phi, false_i); - tree new_name = get_new_name_from_old_name - (SCOP_LIVEOUT_RENAMES (scop), old_name); - - gcc_assert (old_name != new_name); - SET_PHI_ARG_DEF (phi, i, new_name); - } - } -} - -/* Returns the first cloog name used in EXPR. */ - -static const char * -find_cloog_iv_in_expr (struct clast_expr *expr) -{ - struct clast_term *term = (struct clast_term *) expr; - - if (expr->type == expr_term - && !term->var) - return NULL; - - if (expr->type == expr_term) - return term->var; - - if (expr->type == expr_red) - { - int i; - struct clast_reduction *red = (struct clast_reduction *) expr; - - for (i = 0; i < red->n; i++) - { - const char *res = find_cloog_iv_in_expr ((red)->elts[i]); - - if (res) - return res; - } - } - - return NULL; -} - -/* Build for a clast_user_stmt USER_STMT a map between the CLAST - induction variables and the corresponding GCC old induction - variables. This information is stored on each GRAPHITE_BB. */ +/* Print global statistics to FILE. */ static void -compute_cloog_iv_types_1 (graphite_bb_p gbb, - struct clast_user_stmt *user_stmt) +print_global_statistics (FILE* file) { - struct clast_stmt *t; - int index = 0; + long n_bbs = 0; + long n_loops = 0; + long n_stmts = 0; + long n_conditions = 0; + long n_p_bbs = 0; + long n_p_loops = 0; + long n_p_stmts = 0; + long n_p_conditions = 0; - for (t = user_stmt->substitutions; t; t = t->next, index++) - { - PTR *slot; - struct ivtype_map_elt tmp; - struct clast_expr *expr = (struct clast_expr *) - ((struct clast_assignment *)t)->RHS; + basic_block bb; - /* Create an entry (clast_var, type). */ - tmp.cloog_iv = find_cloog_iv_in_expr (expr); - if (!tmp.cloog_iv) - continue; + FOR_ALL_BB (bb) + { + gimple_stmt_iterator psi; - slot = htab_find_slot (GBB_CLOOG_IV_TYPES (gbb), &tmp, INSERT); + n_bbs++; + n_p_bbs += bb->count; - if (!*slot) + /* Ignore artificial surrounding loop. */ + if (bb == bb->loop_father->header + && bb->index != 0) { - loop_p loop = gbb_loop_at_index (gbb, index); - tree oldiv = oldiv_for_loop (GBB_SCOP (gbb), loop); - tree type = oldiv ? TREE_TYPE (oldiv) : integer_type_node; - *slot = new_ivtype_map_elt (tmp.cloog_iv, type); + n_loops++; + n_p_loops += bb->count; } - } -} - -/* Walk the CLAST tree starting from STMT and build for each - clast_user_stmt a map between the CLAST induction variables and the - corresponding GCC old induction variables. This information is - stored on each GRAPHITE_BB. */ - -static void -compute_cloog_iv_types (struct clast_stmt *stmt) -{ - if (!stmt) - return; - - if (CLAST_STMT_IS_A (stmt, stmt_root)) - goto next; - - if (CLAST_STMT_IS_A (stmt, stmt_user)) - { - CloogStatement *cs = ((struct clast_user_stmt *) stmt)->statement; - graphite_bb_p gbb = (graphite_bb_p) cloog_statement_usr (cs); - GBB_CLOOG_IV_TYPES (gbb) = htab_create (10, ivtype_map_elt_info, - eq_ivtype_map_elts, free); - compute_cloog_iv_types_1 (gbb, (struct clast_user_stmt *) stmt); - goto next; - } - - if (CLAST_STMT_IS_A (stmt, stmt_for)) - { - struct clast_stmt *s = ((struct clast_for *) stmt)->body; - compute_cloog_iv_types (s); - goto next; - } - - if (CLAST_STMT_IS_A (stmt, stmt_guard)) - { - struct clast_stmt *s = ((struct clast_guard *) stmt)->then; - compute_cloog_iv_types (s); - goto next; - } - - if (CLAST_STMT_IS_A (stmt, stmt_block)) - { - struct clast_stmt *s = ((struct clast_block *) stmt)->body; - compute_cloog_iv_types (s); - goto next; - } - gcc_unreachable (); - - next: - compute_cloog_iv_types (stmt->next); -} - -/* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for - the given SCOP. */ - -static void -gloog (scop_p scop, struct clast_stmt *stmt) -{ - edge new_scop_exit_edge = NULL; - VEC (iv_stack_entry_p, heap) *ivstack = VEC_alloc (iv_stack_entry_p, heap, - 10); - loop_p context_loop; - ifsese if_region = NULL; + if (VEC_length (edge, bb->succs) > 1) + { + n_conditions++; + n_p_conditions += bb->count; + } - if (!can_generate_code (stmt)) - { - cloog_clast_free (stmt); - return; + for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi)) + { + n_stmts++; + n_p_stmts += bb->count; + } } - if_region = move_sese_in_condition (SCOP_REGION (scop)); - sese_build_livein_liveouts (SCOP_REGION (scop)); - scop_insert_phis_for_liveouts (SCOP_REGION (scop), - if_region->region->exit->src, - if_region->false_region->exit, - if_region->true_region->exit); - recompute_all_dominators (); - graphite_verify (); - context_loop = SESE_ENTRY (SCOP_REGION (scop))->src->loop_father; - compute_cloog_iv_types (stmt); - - new_scop_exit_edge = translate_clast (scop, context_loop, stmt, - if_region->true_region->entry, - &ivstack); - free_loop_iv_stack (&ivstack); - cloog_clast_free (stmt); - - graphite_verify (); - scop_adjust_phis_for_liveouts (scop, - if_region->region->exit->src, - if_region->false_region->exit, - if_region->true_region->exit); - - recompute_all_dominators (); - graphite_verify (); - cleanup_tree_cfg (); - recompute_all_dominators (); - graphite_verify (); -} - -/* Returns the number of data references in SCOP. */ - -static int -nb_data_refs_in_scop (scop_p scop) -{ - int i; - graphite_bb_p gbb; - int res = 0; - - for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gbb); i++) - res += VEC_length (data_reference_p, GBB_DATA_REFS (gbb)); - - return res; + fprintf (file, "\nGlobal statistics ("); + fprintf (file, "BBS:%ld, ", n_bbs); + fprintf (file, "LOOPS:%ld, ", n_loops); + fprintf (file, "CONDITIONS:%ld, ", n_conditions); + fprintf (file, "STMTS:%ld)\n", n_stmts); + fprintf (file, "\nGlobal profiling statistics ("); + fprintf (file, "BBS:%ld, ", n_p_bbs); + fprintf (file, "LOOPS:%ld, ", n_p_loops); + fprintf (file, "CONDITIONS:%ld, ", n_p_conditions); + fprintf (file, "STMTS:%ld)\n", n_p_stmts); } -/* Move the loop at index LOOP and insert it before index NEW_LOOP_POS. - This transformartion is only valid, if the loop nest between i and k is - perfectly nested. Therefore we do not need to change the static schedule. - - Example: - - for (i = 0; i < 50; i++) - for (j ...) - for (k = 5; k < 100; k++) - A - - To move k before i use: - - graphite_trans_bb_move_loop (A, 2, 0) - - for (k = 5; k < 100; k++) - for (i = 0; i < 50; i++) - for (j ...) - A - - And to move k back: - - graphite_trans_bb_move_loop (A, 0, 2) - - This function does not check the validity of interchanging loops. - This should be checked before calling this function. */ +/* Print statistics for SCOP to FILE. */ static void -graphite_trans_bb_move_loop (graphite_bb_p gb, int loop, - int new_loop_pos) +print_graphite_scop_statistics (FILE* file, scop_p scop) { - CloogMatrix *domain = GBB_DOMAIN (gb); - int row, j; - loop_p tmp_loop_p; + long n_bbs = 0; + long n_loops = 0; + long n_stmts = 0; + long n_conditions = 0; + long n_p_bbs = 0; + long n_p_loops = 0; + long n_p_stmts = 0; + long n_p_conditions = 0; - gcc_assert (loop < gbb_nb_loops (gb) - && new_loop_pos < gbb_nb_loops (gb)); - - /* Update LOOPS vector. */ - tmp_loop_p = VEC_index (loop_p, GBB_LOOPS (gb), loop); - VEC_ordered_remove (loop_p, GBB_LOOPS (gb), loop); - VEC_safe_insert (loop_p, heap, GBB_LOOPS (gb), new_loop_pos, tmp_loop_p); - - /* Move the domain columns. */ - if (loop < new_loop_pos) - for (row = 0; row < domain->NbRows; row++) - { - Value tmp; - value_init (tmp); - value_assign (tmp, domain->p[row][loop + 1]); - - for (j = loop ; j < new_loop_pos - 1; j++) - value_assign (domain->p[row][j + 1], domain->p[row][j + 2]); - - value_assign (domain->p[row][new_loop_pos], tmp); - value_clear (tmp); - } - else - for (row = 0; row < domain->NbRows; row++) - { - Value tmp; - value_init (tmp); - value_assign (tmp, domain->p[row][loop + 1]); - - for (j = loop ; j > new_loop_pos; j--) - value_assign (domain->p[row][j + 1], domain->p[row][j]); - - value_assign (domain->p[row][new_loop_pos + 1], tmp); - value_clear (tmp); - } -} - -/* Get the index of the column representing constants in the DOMAIN - matrix. */ - -static int -const_column_index (CloogMatrix *domain) -{ - return domain->NbColumns - 1; -} - - -/* Get the first index that is positive or negative, determined - following the value of POSITIVE, in matrix DOMAIN in COLUMN. */ - -static int -get_first_matching_sign_row_index (CloogMatrix *domain, int column, - bool positive) -{ - int row; + basic_block bb; - for (row = 0; row < domain->NbRows; row++) + FOR_ALL_BB (bb) { - int val = value_get_si (domain->p[row][column]); - - if (val > 0 && positive) - return row; - - else if (val < 0 && !positive) - return row; - } - - gcc_unreachable (); -} - -/* Get the lower bound of COLUMN in matrix DOMAIN. */ - -static int -get_lower_bound_row (CloogMatrix *domain, int column) -{ - return get_first_matching_sign_row_index (domain, column, true); -} - -/* Get the upper bound of COLUMN in matrix DOMAIN. */ - -static int -get_upper_bound_row (CloogMatrix *domain, int column) -{ - return get_first_matching_sign_row_index (domain, column, false); -} - -/* Get the lower bound of LOOP. */ - -static void -get_lower_bound (CloogMatrix *domain, int loop, Value lower_bound_result) -{ - int lower_bound_row = get_lower_bound_row (domain, loop); - value_assign (lower_bound_result, - domain->p[lower_bound_row][const_column_index(domain)]); -} - -/* Get the upper bound of LOOP. */ - -static void -get_upper_bound (CloogMatrix *domain, int loop, Value upper_bound_result) -{ - int upper_bound_row = get_upper_bound_row (domain, loop); - value_assign (upper_bound_result, - domain->p[upper_bound_row][const_column_index(domain)]); -} - -/* Strip mines the loop of BB at the position LOOP_DEPTH with STRIDE. - Always valid, but not always a performance improvement. */ - -static void -graphite_trans_bb_strip_mine (graphite_bb_p gb, int loop_depth, int stride) -{ - int row, col; - - CloogMatrix *domain = GBB_DOMAIN (gb); - CloogMatrix *new_domain = cloog_matrix_alloc (domain->NbRows + 3, - domain->NbColumns + 1); - - int col_loop_old = loop_depth + 2; - int col_loop_strip = col_loop_old - 1; - - Value old_lower_bound; - Value old_upper_bound; - - gcc_assert (loop_depth <= gbb_nb_loops (gb) - 1); - - VEC_safe_insert (loop_p, heap, GBB_LOOPS (gb), loop_depth, NULL); - - GBB_DOMAIN (gb) = new_domain; - - /* - nrows = 4, ncols = 4 - eq i j c - 1 1 0 0 - 1 -1 0 99 - 1 0 1 0 - 1 0 -1 99 - */ - - /* Move domain. */ - for (row = 0; row < domain->NbRows; row++) - for (col = 0; col < domain->NbColumns; col++) - if (col <= loop_depth) - value_assign (new_domain->p[row][col], domain->p[row][col]); - else - value_assign (new_domain->p[row][col + 1], domain->p[row][col]); - - - /* - nrows = 6, ncols = 5 - outer inner - eq i jj j c - 1 1 0 0 0 - 1 -1 0 0 99 - 1 0 0 1 0 - 1 0 0 -1 99 - 0 0 0 0 0 - 0 0 0 0 0 - 0 0 0 0 0 - */ - - row = domain->NbRows; - - /* Add outer loop. */ - value_init (old_lower_bound); - value_init (old_upper_bound); - get_lower_bound (new_domain, col_loop_old, old_lower_bound); - get_upper_bound (new_domain, col_loop_old, old_upper_bound); - - /* Set Lower Bound */ - value_set_si (new_domain->p[row][0], 1); - value_set_si (new_domain->p[row][col_loop_strip], 1); - value_assign (new_domain->p[row][const_column_index (new_domain)], - old_lower_bound); - value_clear (old_lower_bound); - row++; - - - /* - 6 5 - eq i jj j c - 1 1 0 0 0 - 1 -1 0 0 99 - 1 0 0 1 0 - - 1 0 0 -1 99 | copy old lower bound - 1 0 1 0 0 <- - 0 0 0 0 0 - 0 0 0 0 0 - */ - - { - Value new_upper_bound; - Value strip_size_value; - - value_init (new_upper_bound); - value_init (strip_size_value); - value_set_si (strip_size_value, (int) stride); - - value_pdivision (new_upper_bound, old_upper_bound, strip_size_value); - value_add_int (new_upper_bound, new_upper_bound, 1); - - /* Set Upper Bound */ - value_set_si (new_domain->p[row][0], 1); - value_set_si (new_domain->p[row][col_loop_strip], -1); - value_assign (new_domain->p[row][const_column_index (new_domain)], - new_upper_bound); - - value_clear (strip_size_value); - value_clear (old_upper_bound); - value_clear (new_upper_bound); - row++; - } - /* - 6 5 - eq i jj j c - 1 1 0 0 0 - 1 -1 0 0 99 - 1 0 0 1 0 - 1 0 0 -1 99 - 1 0 1 0 0 - 1 0 -1 0 25 (divide old upper bound with stride) - 0 0 0 0 0 - */ + gimple_stmt_iterator psi; + loop_p loop = bb->loop_father; - { - row = get_lower_bound_row (new_domain, col_loop_old); - /* Add local variable to keep linear representation. */ - value_set_si (new_domain->p[row][0], 1); - value_set_si (new_domain->p[row][const_column_index (new_domain)],0); - value_set_si (new_domain->p[row][col_loop_old], 1); - value_set_si (new_domain->p[row][col_loop_strip], -1*((int)stride)); - } - - /* - 6 5 - eq i jj j c - 1 1 0 0 0 - 1 -1 0 0 99 - 1 0 -1 1 0 - 1 0 0 -1 99 - 1 0 1 0 0 - 1 0 -1 0 25 (divide old upper bound with stride) - 0 0 0 0 0 - */ - - { - row = new_domain->NbRows-1; - - value_set_si (new_domain->p[row][0], 1); - value_set_si (new_domain->p[row][col_loop_old], -1); - value_set_si (new_domain->p[row][col_loop_strip], stride); - value_set_si (new_domain->p[row][const_column_index (new_domain)], - stride-1); - } - - /* - 6 5 - eq i jj j c - 1 1 0 0 0 i >= 0 - 1 -1 0 0 99 99 >= i - 1 0 -4 1 0 j >= 4*jj - 1 0 0 -1 99 99 >= j - 1 0 1 0 0 jj >= 0 - 1 0 -1 0 25 25 >= jj - 0 0 4 -1 3 jj+3 >= j - */ - - cloog_matrix_free (domain); - - /* Update static schedule. */ - { - int i; - int nb_loops = gbb_nb_loops (gb); - lambda_vector new_schedule = lambda_vector_new (nb_loops + 1); - - for (i = 0; i <= loop_depth; i++) - new_schedule[i] = GBB_STATIC_SCHEDULE (gb)[i]; - - for (i = loop_depth + 1; i <= nb_loops - 2; i++) - new_schedule[i + 2] = GBB_STATIC_SCHEDULE (gb)[i]; - - GBB_STATIC_SCHEDULE (gb) = new_schedule; - } -} - -/* Returns true when the strip mining of LOOP_INDEX by STRIDE is - profitable or undecidable. GB is the statement around which the - loops will be strip mined. */ - -static bool -strip_mine_profitable_p (graphite_bb_p gb, int stride, - int loop_index) -{ - bool res = true; - edge exit = NULL; - tree niter; - loop_p loop; - long niter_val; - - loop = VEC_index (loop_p, GBB_LOOPS (gb), loop_index); - exit = single_exit (loop); + if (!bb_in_sese_p (bb, SCOP_REGION (scop))) + continue; - niter = find_loop_niter (loop, &exit); - if (niter == chrec_dont_know - || TREE_CODE (niter) != INTEGER_CST) - return true; - - niter_val = int_cst_value (niter); + n_bbs++; + n_p_bbs += bb->count; - if (niter_val < stride) - { - res = false; - if (dump_file && (dump_flags & TDF_DETAILS)) + if (VEC_length (edge, bb->succs) > 1) { - fprintf (dump_file, "\nStrip Mining is not profitable for loop %d:", - loop->num); - fprintf (dump_file, "number of iterations is too low.\n"); + n_conditions++; + n_p_conditions += bb->count; } - } - - return res; -} - -/* Determines when the interchange of LOOP_A and LOOP_B belonging to - SCOP is legal. DEPTH is the number of loops around. */ - -static bool -is_interchange_valid (scop_p scop, int loop_a, int loop_b, int depth) -{ - bool res; - VEC (ddr_p, heap) *dependence_relations; - VEC (data_reference_p, heap) *datarefs; - - struct loop *nest = VEC_index (loop_p, SCOP_LOOP_NEST (scop), loop_a); - lambda_trans_matrix trans; - - gcc_assert (loop_a < loop_b); - - dependence_relations = VEC_alloc (ddr_p, heap, 10 * 10); - datarefs = VEC_alloc (data_reference_p, heap, 10); - - if (!compute_data_dependences_for_loop (nest, true, &datarefs, - &dependence_relations)) - return false; - - if (dump_file && (dump_flags & TDF_DETAILS)) - dump_ddrs (dump_file, dependence_relations); - - trans = lambda_trans_matrix_new (depth, depth); - lambda_matrix_id (LTM_MATRIX (trans), depth); - - lambda_matrix_row_exchange (LTM_MATRIX (trans), 0, loop_b - loop_a); - - if (!lambda_transform_legal_p (trans, depth, dependence_relations)) - { - lambda_matrix_row_exchange (LTM_MATRIX (trans), 0, loop_b - loop_a); - res = false; - } - else - res = true; - - free_dependence_relations (dependence_relations); - free_data_refs (datarefs); - return res; -} - -/* Loop block the LOOPS innermost loops of GB with stride size STRIDE. - - Example - - for (i = 0; i <= 50; i++=4) - for (k = 0; k <= 100; k++=4) - for (l = 0; l <= 200; l++=4) - A - - To strip mine the two inner most loops with stride = 4 call: - - graphite_trans_bb_block (A, 4, 2) - for (i = 0; i <= 50; i++) - for (kk = 0; kk <= 100; kk+=4) - for (ll = 0; ll <= 200; ll+=4) - for (k = kk; k <= min (100, kk + 3); k++) - for (l = ll; l <= min (200, ll + 3); l++) - A -*/ - -static bool -graphite_trans_bb_block (graphite_bb_p gb, int stride, int loops) -{ - int i, j; - int nb_loops = gbb_nb_loops (gb); - int start = nb_loops - loops; - scop_p scop = GBB_SCOP (gb); - - gcc_assert (scop_contains_loop (scop, gbb_loop (gb))); - - for (i = start ; i < nb_loops; i++) - for (j = i + 1; j < nb_loops; j++) - if (!is_interchange_valid (scop, i, j, nb_loops)) + for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi)) { - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, - "\nInterchange not valid for loops %d and %d:\n", i, j); - return false; + n_stmts++; + n_p_stmts += bb->count; } - else if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, - "\nInterchange valid for loops %d and %d:\n", i, j); - - /* Check if strip mining is profitable for every loop. */ - for (i = 0; i < nb_loops - start; i++) - if (!strip_mine_profitable_p (gb, stride, start + i)) - return false; - - /* Strip mine loops. */ - for (i = 0; i < nb_loops - start; i++) - graphite_trans_bb_strip_mine (gb, start + 2 * i, stride); - /* Interchange loops. */ - for (i = 1; i < nb_loops - start; i++) - graphite_trans_bb_move_loop (gb, start + 2 * i, start + i); - - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "\nLoops containing BB %d will be loop blocked.\n", - GBB_BB (gb)->index); + if (loop->header == bb && loop_in_sese_p (loop, SCOP_REGION (scop))) + { + n_loops++; + n_p_loops += bb->count; + } + } - return true; + fprintf (file, "\nSCoP statistics ("); + fprintf (file, "BBS:%ld, ", n_bbs); + fprintf (file, "LOOPS:%ld, ", n_loops); + fprintf (file, "CONDITIONS:%ld, ", n_conditions); + fprintf (file, "STMTS:%ld)\n", n_stmts); + fprintf (file, "\nSCoP profiling statistics ("); + fprintf (file, "BBS:%ld, ", n_p_bbs); + fprintf (file, "LOOPS:%ld, ", n_p_loops); + fprintf (file, "CONDITIONS:%ld, ", n_p_conditions); + fprintf (file, "STMTS:%ld)\n", n_p_stmts); } -/* Loop block LOOPS innermost loops of a loop nest. BBS represent the - basic blocks that belong to the loop nest to be blocked. */ +/* Print statistics for SCOPS to FILE. */ -static bool -graphite_trans_loop_block (VEC (graphite_bb_p, heap) *bbs, int loops) +static void +print_graphite_statistics (FILE* file, VEC (scop_p, heap) *scops) { - graphite_bb_p gb; int i; - bool transform_done = false; - /* TODO: - Calculate the stride size automatically. */ - int stride_size = 64; - - for (i = 0; VEC_iterate (graphite_bb_p, bbs, i, gb); i++) - transform_done |= graphite_trans_bb_block (gb, stride_size, loops); + scop_p scop; - return transform_done; + FOR_EACH_VEC_ELT (scop_p, scops, i, scop) + print_graphite_scop_statistics (file, scop); } -/* Loop block all basic blocks of SCOP. Return false when the - transform is not performed. */ +/* Initialize graphite: when there are no loops returns false. */ static bool -graphite_trans_scop_block (scop_p scop) +graphite_initialize (void) { - graphite_bb_p gb; - int i, j; - int last_nb_loops; - int nb_loops; - bool perfect = true; - bool transform_done = false; - - VEC (graphite_bb_p, heap) *bbs = VEC_alloc (graphite_bb_p, heap, 3); - int max_schedule = scop_max_loop_depth (scop) + 1; - lambda_vector last_schedule = lambda_vector_new (max_schedule); - - if (VEC_length (graphite_bb_p, SCOP_BBS (scop)) == 0) - return false; + int ppl_initialized; - /* Get the data of the first bb. */ - gb = VEC_index (graphite_bb_p, SCOP_BBS (scop), 0); - last_nb_loops = gbb_nb_loops (gb); - lambda_vector_copy (GBB_STATIC_SCHEDULE (gb), last_schedule, - last_nb_loops + 1); - VEC_safe_push (graphite_bb_p, heap, bbs, gb); - - for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++) + if (number_of_loops () <= 1 + /* FIXME: This limit on the number of basic blocks of a function + should be removed when the SCOP detection is faster. */ + || n_basic_blocks > PARAM_VALUE (PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION)) { - /* We did the first bb before. */ - if (i == 0) - continue; - - nb_loops = gbb_nb_loops (gb); - - /* If the number of loops is unchanged and only the last element of the - schedule changes, we stay in the loop nest. */ - if (nb_loops == last_nb_loops - && (last_schedule [nb_loops + 1] - != GBB_STATIC_SCHEDULE (gb)[nb_loops + 1])) - { - VEC_safe_push (graphite_bb_p, heap, bbs, gb); - continue; - } - - /* Otherwise, we left the innermost loop. So check, if the last bb was in - a perfect loop nest and how many loops are contained in this perfect - loop nest. - - Count the number of zeros from the end of the schedule. They are the - number of surrounding loops. - - Example: - last_bb 2 3 2 0 0 0 0 3 - bb 2 4 0 - <------ j = 4 - - last_bb 2 3 2 0 0 0 0 3 - bb 2 3 2 0 1 - <-- j = 2 - - If there is no zero, there were other bbs in outer loops and the loop - nest is not perfect. */ - for (j = last_nb_loops - 1; j >= 0; j--) - { - if (last_schedule [j] != 0 - || (j <= nb_loops && GBB_STATIC_SCHEDULE (gb)[j] == 1)) - { - j--; - break; - } - } - - j++; - - /* Found perfect loop nest. */ - if (perfect && last_nb_loops - j >= 2) - transform_done |= graphite_trans_loop_block (bbs, last_nb_loops - j); - - /* Check if we start with a new loop. - - Example: - - last_bb 2 3 2 0 0 0 0 3 - bb 2 3 2 0 0 1 0 - - Here we start with the loop "2 3 2 0 0 1" - - last_bb 2 3 2 0 0 0 0 3 - bb 2 3 2 0 0 1 - - But here not, so the loop nest can never be perfect. */ - - perfect = (GBB_STATIC_SCHEDULE (gb)[nb_loops] == 0); + if (dump_file && (dump_flags & TDF_DETAILS)) + print_global_statistics (dump_file); - /* Update the last_bb infos. We do not do that for the bbs in the same - loop, as the data we use is not changed. */ - last_nb_loops = nb_loops; - lambda_vector_copy (GBB_STATIC_SCHEDULE (gb), last_schedule, - nb_loops + 1); - VEC_truncate (graphite_bb_p, bbs, 0); - VEC_safe_push (graphite_bb_p, heap, bbs, gb); + return false; } - /* Check if the last loop nest was perfect. It is the same check as above, - but the comparison with the next bb is missing. */ - for (j = last_nb_loops - 1; j >= 0; j--) - if (last_schedule [j] != 0) - { - j--; - break; - } - - j++; - - /* Found perfect loop nest. */ - if (last_nb_loops - j > 0) - transform_done |= graphite_trans_loop_block (bbs, last_nb_loops - j); - VEC_free (graphite_bb_p, heap, bbs); - - return transform_done; -} - -/* Apply graphite transformations to all the basic blocks of SCOP. */ - -static bool -graphite_apply_transformations (scop_p scop) -{ - bool transform_done = false; + scev_reset (); + recompute_all_dominators (); + initialize_original_copy_tables (); - /* Sort the list of bbs. Keep them always sorted. */ - graphite_sort_gbbs (scop); + ppl_initialized = ppl_initialize (); + gcc_assert (ppl_initialized == 0); - if (flag_loop_block) - transform_done = graphite_trans_scop_block (scop); + cloog_state = cloog_state_malloc (); + cloog_initialize (); - /* Generate code even if we did not apply any real transformation. - This also allows to check the performance for the identity - transformation: GIMPLE -> GRAPHITE -> GIMPLE - Keep in mind that CLooG optimizes in control, so the loop structure - may change, even if we only use -fgraphite-identity. */ - if (flag_graphite_identity) - transform_done = true; + if (dump_file && dump_flags) + dump_function_to_file (current_function_decl, dump_file, dump_flags); - return transform_done; + return true; } -/* We limit all SCoPs to SCoPs, that are completely surrounded by a loop. - - Example: - - for (i | - { | - for (j | SCoP 1 - for (k | - } | - - * SCoP frontier, as this line is not surrounded by any loop. * - - for (l | SCoP 2 - - This is necessary as scalar evolution and parameter detection need a - outermost loop to initialize parameters correctly. - - TODO: FIX scalar evolution and parameter detection to allow more flexible - SCoP frontiers. */ +/* Finalize graphite: perform CFG cleanup when NEED_CFG_CLEANUP_P is + true. */ static void -limit_scops (void) +graphite_finalize (bool need_cfg_cleanup_p) { - VEC (sd_region, heap) *tmp_scops = VEC_alloc (sd_region, heap, 3); - - int i; - scop_p scop; - - for (i = 0; VEC_iterate (scop_p, current_scops, i, scop); i++) + if (need_cfg_cleanup_p) { - int j; - loop_p loop; - build_scop_bbs (scop); - - if (!build_scop_loop_nests (scop)) - continue; - - for (j = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), j, loop); j++) - if (!loop_in_scop_p (loop_outer (loop), scop)) - { - sd_region open_scop; - open_scop.entry = loop->header; - open_scop.exit = single_exit (loop)->dest; - VEC_safe_push (sd_region, heap, tmp_scops, &open_scop); - } + scev_reset (); + cleanup_tree_cfg (); + profile_status = PROFILE_ABSENT; + release_recorded_exits (); + tree_estimate_probability (); } - free_scops (current_scops); - current_scops = VEC_alloc (scop_p, heap, 3); + cloog_state_free (cloog_state); + cloog_finalize (); + ppl_finalize (); + free_original_copy_tables (); - create_sese_edges (tmp_scops); - build_graphite_scops (tmp_scops); - VEC_free (sd_region, heap, tmp_scops); + if (dump_file && dump_flags) + print_loops (dump_file, 3); } /* Perform a set of linear transforms on the loops of the current @@ -6032,74 +249,37 @@ graphite_transform_loops (void) { int i; scop_p scop; + bool need_cfg_cleanup_p = false; + VEC (scop_p, heap) *scops = NULL; + htab_t bb_pbb_mapping; - if (number_of_loops () <= 1) + if (!graphite_initialize ()) return; - current_scops = VEC_alloc (scop_p, heap, 3); - recompute_all_dominators (); - - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "Graphite loop transformations \n"); - - initialize_original_copy_tables (); - cloog_initialize (); - build_scops (); - limit_scops (); + build_scops (&scops); if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "\nnumber of SCoPs: %d\n", - VEC_length (scop_p, current_scops)); - - for (i = 0; VEC_iterate (scop_p, current_scops, i, scop); i++) { - build_scop_bbs (scop); - if (!build_scop_loop_nests (scop)) - continue; - - build_scop_canonical_schedules (scop); - build_bb_loops (scop); - if (!build_scop_conditions (scop)) - continue; - find_scop_parameters (scop); - build_scop_context (scop); - - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "\n(In SCoP %d:\n", i); - fprintf (dump_file, "\nnumber of bbs: %d\n", - VEC_length (graphite_bb_p, SCOP_BBS (scop))); - fprintf (dump_file, "\nnumber of loops: %d)\n", - VEC_length (loop_p, SCOP_LOOP_NEST (scop))); - } - - if (!build_scop_iteration_domain (scop)) - continue; + print_graphite_statistics (dump_file, scops); + print_global_statistics (dump_file); + } - build_scop_data_accesses (scop); - build_scop_dynamic_schedules (scop); + bb_pbb_mapping = htab_create (10, bb_pbb_map_hash, eq_bb_pbb_map, free); - if (dump_file && (dump_flags & TDF_DETAILS)) - { - int nbrefs = nb_data_refs_in_scop (scop); - fprintf (dump_file, "\nnumber of data refs: %d\n", nbrefs); - } + FOR_EACH_VEC_ELT (scop_p, scops, i, scop) + if (dbg_cnt (graphite_scop)) + { + build_poly_scop (scop); - if (graphite_apply_transformations (scop)) - gloog (scop, find_transform (scop)); -#ifdef ENABLE_CHECKING - else - { - struct clast_stmt *stmt = find_transform (scop); - cloog_clast_free (stmt); - } -#endif - } + if (POLY_SCOP_P (scop) + && apply_poly_transforms (scop) + && gloog (scop, bb_pbb_mapping)) + need_cfg_cleanup_p = true; + } - /* Cleanup. */ - free_scops (current_scops); - cloog_finalize (); - free_original_copy_tables (); + htab_delete (bb_pbb_mapping); + free_scops (scops); + graphite_finalize (need_cfg_cleanup_p); } #else /* If Cloog is not available: #ifndef HAVE_cloog. */