| /* Gimple Represented as Polyhedra. |
| Copyright (C) 2006, 2007, 2008, 2009 Free Software Foundation, Inc. |
| Contributed by Sebastian Pop <sebastian.pop@inria.fr>. |
| |
| This file is part of GCC. |
| |
| GCC is free software; you can redistribute it and/or modify |
| it under the terms of the GNU General Public License as published by |
| the Free Software Foundation; either version 3, or (at your option) |
| any later version. |
| |
| GCC is distributed in the hope that it will be useful, |
| but WITHOUT ANY WARRANTY; without even the implied warranty of |
| MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| GNU General Public License for more details. |
| |
| You should have received a copy of the GNU General Public License |
| along with GCC; see the file COPYING3. If not see |
| <http://www.gnu.org/licenses/>. */ |
| |
| /* This pass converts GIMPLE to GRAPHITE, performs some loop |
| transformations and then converts the resulting representation back |
| 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. |
| |
| 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 |
| that describes the data structure of loops used in this file, and |
| the functions that are used for transforming the code. */ |
| |
| #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 "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" |
| |
| #ifdef HAVE_cloog |
| #include "cloog/cloog.h" |
| #include "graphite.h" |
| |
| static VEC (scop_p, heap) *current_scops; |
| |
| /* Converts a GMP constant V to a tree and returns it. */ |
| |
| static tree |
| gmp_cst_to_tree (tree type, Value v) |
| { |
| return build_int_cst (type, value_get_si (v)); |
| } |
| |
| /* 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); |
| } |
| |
| /* Returns true when LOOP is in the SESE region R. */ |
| |
| static inline bool |
| loop_in_sese_p (struct loop *loop, sese r) |
| { |
| return (bb_in_sese_p (loop->header, r) |
| && bb_in_sese_p (loop->latch, r)); |
| } |
| |
| /* 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); |
| } |
| |
| |
| |
| /* 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_sese_p (bb, SCOP_REGION (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 <TABLE BORDER=\"0\" CELLBORDER=\"1\" ", |
| bb->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_sese_p (bb, SCOP_REGION (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, " <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">", color); |
| |
| if (!bb_in_sese_p (bb, SCOP_REGION (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_sese_p (bb, SCOP_REGION (scop))) |
| fprintf (file, ")"); |
| |
| fprintf (file, "</TD></TR>\n"); |
| part_of_scop = true; |
| } |
| |
| if (!part_of_scop) |
| { |
| fprintf (file, " <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">"); |
| fprintf (file, " %d </TD></TR>\n", bb->index); |
| } |
| |
| fprintf (file, " </TABLE>>, 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_sese_p (loop_outer (nest), SCOP_REGION (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 true if REF or any of its subtrees contains a |
| component_ref. */ |
| |
| static bool |
| contains_component_ref_p (tree ref) |
| { |
| if (!ref) |
| return false; |
| |
| while (handled_component_p (ref)) |
| { |
| if (TREE_CODE (ref) == COMPONENT_REF) |
| return true; |
| |
| ref = TREE_OPERAND (ref, 0); |
| } |
| |
| return false; |
| } |
| |
| /* 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 COMPONENT_REF, */ |
| || contains_component_ref_p (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 true; |
| } |
| |
| /* 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); |
| |
| if (lhs && !is_simple_operand (loop, stmt, lhs)) |
| return false; |
| |
| for (i = 0; i < n; i++) |
| if (!is_simple_operand (loop, stmt, gimple_call_arg (stmt, i))) |
| 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; |
| gimple stmt; |
| |
| 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); |
| |
| stmt = last_stmt (bb); |
| if (stmt && gimple_code (stmt) == GIMPLE_COND) |
| { |
| tree lhs = gimple_cond_lhs (stmt); |
| tree rhs = gimple_cond_rhs (stmt); |
| |
| if (TREE_CODE (TREE_TYPE (lhs)) == REAL_TYPE |
| || TREE_CODE (TREE_TYPE (rhs)) == REAL_TYPE) |
| return stmt; |
| } |
| |
| 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; |
| |
| 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; |
| } |
| |
| |
| |
| /* 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_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_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; |
| |
| /* Mark bbs terminating a SESE region difficult, if they start |
| a condition. */ |
| if (VEC_length (edge, bb->succs) > 1) |
| result.difficult = true; |
| |
| 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); |
| verify_loop_closed_ssa (); |
| #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, loop, 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); |
| bool known_niter = number_of_iterations_exit (loop, exit, &niter, false); |
| |
| gcc_assert (known_niter); |
| |
| 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_sese_p (bb, SCOP_REGION (scop))) |
| { |
| struct loop *loop = bb->loop_father; |
| |
| /* Only add loops if they are completely contained in the SCoP. */ |
| if (loop->header == bb |
| && bb_in_sese_p (loop->latch, SCOP_REGION (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; |
| } |
| |
| /* Calculate the number of loops around LOOP in the SCOP. */ |
| |
| static inline int |
| nb_loops_around_loop_in_scop (struct loop *l, scop_p scop) |
| { |
| int d = 0; |
| |
| for (; loop_in_sese_p (l, SCOP_REGION (scop)); d++, l = loop_outer (l)); |
| |
| return d; |
| } |
| |
| /* Calculate the number of loops around GB in the current SCOP. */ |
| |
| int |
| nb_loops_around_gb (graphite_bb_p gb) |
| { |
| return nb_loops_around_loop_in_scop (gbb_loop (gb), GBB_SCOP (gb)); |
| } |
| |
| /* Returns the dimensionality of an enclosing loop iteration domain |
| with respect to enclosing SCoP for a given data reference REF. The |
| returned dimensionality is homogeneous (depth of loop nest + number |
| of SCoP parameters + const). */ |
| |
| int |
| ref_nb_loops (data_reference_p ref) |
| { |
| loop_p loop = loop_containing_stmt (DR_STMT (ref)); |
| scop_p scop = DR_SCOP (ref); |
| |
| return nb_loops_around_loop_in_scop (loop, scop) + scop_nb_params (scop) + 2; |
| } |
| |
| /* 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; |
| } |
| } |
| |
| /* Returns the number of loops that are identical at the beginning of |
| the vectors A and B. */ |
| |
| static int |
| compare_prefix_loops (VEC (loop_p, heap) *a, VEC (loop_p, heap) *b) |
| { |
| int i; |
| loop_p ea; |
| int lb; |
| |
| if (!a || !b) |
| return 0; |
| |
| lb = VEC_length (loop_p, b); |
| |
| for (i = 0; VEC_iterate (loop_p, a, i, ea); i++) |
| if (i >= lb |
| || ea != VEC_index (loop_p, b, i)) |
| return i; |
| |
| return 0; |
| } |
| |
| /* 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; |
| graphite_bb_p gb; |
| int nb_loops = scop_nb_loops (scop); |
| lambda_vector static_schedule = lambda_vector_new (nb_loops + 1); |
| VEC (loop_p, heap) *loops_previous = NULL; |
| |
| /* We have to start schedules at 0 on the first component and |
| because we cannot compare_prefix_loops against a previous loop, |
| prefix will be equal to zero, and that index will be |
| incremented before copying. */ |
| static_schedule[0] = -1; |
| |
| for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++) |
| { |
| int prefix = compare_prefix_loops (loops_previous, GBB_LOOPS (gb)); |
| int nb = gbb_nb_loops (gb); |
| |
| loops_previous = GBB_LOOPS (gb); |
| memset (&(static_schedule[prefix + 1]), 0, sizeof (int) * (nb_loops - prefix)); |
| ++static_schedule[prefix]; |
| GBB_STATIC_SCHEDULE (gb) = lambda_vector_new (nb + 1); |
| lambda_vector_copy (static_schedule, |
| GBB_STATIC_SCHEDULE (gb), nb + 1); |
| } |
| } |
| |
| /* 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); |
| scan_tree_for_params (s, TREE_OPERAND (e, 1), c, r, k, !subtract); |
| break; |
| |
| case NEGATE_EXPR: |
| 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_sese_p (loop->inner, SCOP_REGION (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_sese_p (loop->next, |
| SCOP_REGION (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 = nb_loops_around_gb (gb) + 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); |
| |
| if (domain) |
| { |
| 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; |
| basic_block bb_child, bb_iter; |
| VEC (basic_block, heap) *dom; |
| gimple stmt; |
| |
| /* Make sure we are in the SCoP. */ |
| if (!bb_in_sese_p (bb, SCOP_REGION (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); |
| } |
| |
| dom = get_dominated_by (CDI_DOMINATORS, bb); |
| |
| stmt = last_stmt (bb); |
| if (stmt) |
| { |
| 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; |
| } |
| |
| /* Traverses all the GBBs of the SCOP and add their constraints to the |
| iteration domains. */ |
| |
| static void |
| add_conditions_to_constraints (scop_p scop) |
| { |
| int i; |
| graphite_bb_p gbb; |
| |
| for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gbb); i++) |
| add_conditions_to_domain (gbb); |
| } |
| |
| /* 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_sese_p (loop_outer (loop), SCOP_REGION (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, gc, 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_quick_push (lambda_vector, 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; |
| } |
| |
| static tree |
| clast_to_gcc_expression (tree, struct clast_expr *, VEC (name_tree, heap) *, |
| loop_iv_stack); |
| |
| /* Converts a Cloog reduction expression R with reduction operation OP |
| to a GCC expression tree of type TYPE. PARAMS is a vector of |
| parameters of the scop, and IVSTACK contains the stack of induction |
| variables. */ |
| |
| static tree |
| clast_to_gcc_expression_red (tree type, enum tree_code op, |
| struct clast_reduction *r, |
| VEC (name_tree, heap) *params, |
| loop_iv_stack ivstack) |
| { |
| int i; |
| tree res = clast_to_gcc_expression (type, r->elts[0], params, ivstack); |
| |
| for (i = 1; i < r->n; i++) |
| { |
| tree t = clast_to_gcc_expression (type, r->elts[i], params, ivstack); |
| res = fold_build2 (op, type, res, t); |
| } |
| return res; |
| } |
| |
| /* Converts a Cloog AST expression E back to a GCC expression tree of |
| type TYPE. PARAMS is a vector of parameters of the scop, and |
| IVSTACK contains the stack of induction variables. */ |
| |
| 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: |
| return clast_to_gcc_expression_red (type, PLUS_EXPR, r, params, ivstack); |
| |
| case clast_red_min: |
| return clast_to_gcc_expression_red (type, MIN_EXPR, r, params, ivstack); |
| |
| case clast_red_max: |
| return clast_to_gcc_expression_red (type, MAX_EXPR, r, params, ivstack); |
| |
| 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, |
| htab_t); |
| static tree |
| expand_scalar_variables_expr (tree, tree, enum tree_code, tree, basic_block, |
| scop_p, htab_t, gimple_stmt_iterator *); |
| |
| /* Copies at GSI all the scalar computations on which the ssa_name OP0 |
| depends on in the SCOP: these are all the scalar variables used in |
| the definition of OP0, that are defined outside BB and still in the |
| SCOP, i.e. not a parameter of the SCOP. The expression that is |
| returned contains only induction variables from the generated code: |
| MAP contains the induction variables renaming mapping, and is used |
| to translate the names of induction variables. */ |
| |
| static tree |
| expand_scalar_variables_ssa_name (tree op0, basic_block bb, |
| scop_p scop, htab_t map, |
| gimple_stmt_iterator *gsi) |
| { |
| tree var0, var1, type; |
| 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, map); |
| return get_new_name_from_old_name (map, op0); |
| } |
| else |
| { |
| if (gimple_code (def_stmt) != GIMPLE_ASSIGN |
| || !bb_in_sese_p (gimple_bb (def_stmt), SCOP_REGION (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); |
| type = gimple_expr_type (def_stmt); |
| |
| return expand_scalar_variables_expr (type, var0, subcode, var1, bb, scop, |
| map, gsi); |
| } |
| } |
| |
| /* Copies at GSI all the scalar computations on which the expression |
| OP0 CODE OP1 depends on in the SCOP: these are all the scalar |
| variables used in OP0 and OP1, defined outside BB and still defined |
| in the SCOP, i.e. not a parameter of the SCOP. The expression that |
| is returned contains only induction variables from the generated |
| code: MAP contains the induction variables renaming mapping, and is |
| used to translate the names of induction variables. */ |
| |
| static tree |
| expand_scalar_variables_expr (tree type, tree op0, enum tree_code code, |
| tree op1, basic_block bb, scop_p scop, |
| htab_t map, gimple_stmt_iterator *gsi) |
| { |
| if (TREE_CODE_CLASS (code) == tcc_constant |
| || TREE_CODE_CLASS (code) == tcc_declaration) |
| return op0; |
| |
| /* For data references we have to duplicate also its memory |
| indexing. */ |
| if (TREE_CODE_CLASS (code) == tcc_reference) |
| { |
| switch (code) |
| { |
| case INDIRECT_REF: |
| { |
| tree old_name = TREE_OPERAND (op0, 0); |
| tree expr = expand_scalar_variables_ssa_name |
| (old_name, bb, scop, map, gsi); |
| tree new_name = force_gimple_operand_gsi (gsi, expr, true, NULL, |
| true, GSI_SAME_STMT); |
| |
| set_symbol_mem_tag (SSA_NAME_VAR (new_name), |
| symbol_mem_tag (SSA_NAME_VAR (old_name))); |
| return fold_build1 (code, type, new_name); |
| } |
| |
| case ARRAY_REF: |
| { |
| tree op00 = TREE_OPERAND (op0, 0); |
| tree op01 = TREE_OPERAND (op0, 1); |
| tree op02 = TREE_OPERAND (op0, 2); |
| tree op03 = TREE_OPERAND (op0, 3); |
| tree base = expand_scalar_variables_expr |
| (TREE_TYPE (op00), op00, TREE_CODE (op00), NULL, bb, scop, |
| map, gsi); |
| tree subscript = expand_scalar_variables_expr |
| (TREE_TYPE (op01), op01, TREE_CODE (op01), NULL, bb, scop, |
| map, gsi); |
| |
| return build4 (ARRAY_REF, type, base, subscript, op02, op03); |
| } |
| |
| default: |
| /* The above cases should catch everything. */ |
| gcc_unreachable (); |
| } |
| } |
| |
| 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, map, gsi); |
| |
| 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, map, gsi); |
| 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, map, gsi); |
| |
| return fold_build2 (code, type, op0_expr, op1_expr); |
| } |
| |
| if (code == SSA_NAME) |
| return expand_scalar_variables_ssa_name (op0, bb, scop, map, gsi); |
| |
| gcc_unreachable (); |
| return NULL; |
| } |
| |
| /* Copies at the beginning of BB all the scalar computations on which |
| STMT depends on in the SCOP: these are all the scalar variables used |
| in STMT, defined outside BB and still defined in the SCOP, i.e. not a |
| parameter of the SCOP. The expression that is returned contains |
| only induction variables from the generated code: MAP contains the |
| induction variables renaming mapping, and is used to translate the |
| names of induction variables. */ |
| |
| static void |
| expand_scalar_variables_stmt (gimple stmt, basic_block bb, scop_p scop, |
| htab_t map) |
| { |
| ssa_op_iter iter; |
| use_operand_p use_p; |
| gimple_stmt_iterator gsi = gsi_after_labels (bb); |
| |
| 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, map, &gsi); |
| if (use_expr != use) |
| { |
| 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 at the beginning of BB all the scalar computations on which |
| BB depends on in the SCOP: these are all the scalar variables used |
| in BB, defined outside BB and still defined in the SCOP, i.e. not a |
| parameter of the SCOP. The expression that is returned contains |
| only induction variables from the generated code: MAP contains the |
| induction variables renaming mapping, and is used to translate the |
| names of induction variables. */ |
| |
| static void |
| expand_scalar_variables (basic_block bb, scop_p scop, 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, 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, |
| 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, 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, |
| 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; |
| } |
| |
| /* 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); |
| basic_block dummy = false_edge->dest; |
| 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); |
| redirect_edge_succ (false_edge, single_succ (dummy)); |
| delete_basic_block (dummy); |
| |
| exit_region->flags = EDGE_FALLTHRU; |
| recompute_all_dominators (); |
| |
| SESE_EXIT (region) = false_edge; |
| 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); |
| } |
| |
| /* Get the definition of NAME before the SCOP. Keep track of the |
| basic blocks that have been VISITED in a bitmap. */ |
| |
| static tree |
| get_vdef_before_scop (scop_p scop, tree name, sbitmap visited) |
| { |
| unsigned i; |
| gimple def_stmt = SSA_NAME_DEF_STMT (name); |
| basic_block def_bb = gimple_bb (def_stmt); |
| |
| if (!def_bb |
| || !bb_in_sese_p (def_bb, SCOP_REGION (scop))) |
| return name; |
| |
| if (TEST_BIT (visited, def_bb->index)) |
| return NULL_TREE; |
| |
| SET_BIT (visited, def_bb->index); |
| |
| switch (gimple_code (def_stmt)) |
| { |
| case GIMPLE_PHI: |
| for (i = 0; i < gimple_phi_num_args (def_stmt); i++) |
| { |
| tree arg = gimple_phi_arg_def (def_stmt, i); |
| tree res = get_vdef_before_scop (scop, arg, visited); |
| if (res) |
| return res; |
| } |
| return NULL_TREE; |
| |
| default: |
| return NULL_TREE; |
| } |
| } |
| |
| /* Adjust a virtual phi node PHI that is placed at the end of the |
| generated code for SCOP: |
| |
| | if (1) |
| | generated code from REGION; |
| | else |
| | REGION; |
| |
| The FALSE_E edge comes from the original code, TRUE_E edge comes |
| from the code generated for the SCOP. */ |
| |
| static void |
| scop_adjust_vphi (scop_p scop, gimple phi, edge true_e) |
| { |
| unsigned i; |
| |
| gcc_assert (gimple_phi_num_args (phi) == 2); |
| |
| for (i = 0; i < gimple_phi_num_args (phi); i++) |
| if (gimple_phi_arg_edge (phi, i) == true_e) |
| { |
| tree true_arg, false_arg, before_scop_arg; |
| sbitmap visited; |
| |
| true_arg = gimple_phi_arg_def (phi, i); |
| if (!SSA_NAME_IS_DEFAULT_DEF (true_arg)) |
| return; |
| |
| false_arg = gimple_phi_arg_def (phi, i == 0 ? 1 : 0); |
| if (SSA_NAME_IS_DEFAULT_DEF (false_arg)) |
| return; |
| |
| visited = sbitmap_alloc (last_basic_block); |
| sbitmap_zero (visited); |
| before_scop_arg = get_vdef_before_scop (scop, false_arg, visited); |
| gcc_assert (before_scop_arg != NULL_TREE); |
| SET_PHI_ARG_DEF (phi, i, before_scop_arg); |
| sbitmap_free (visited); |
| } |
| } |
| |
| /* 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; |
| unsigned false_i = 0; |
| gimple phi = gsi_stmt (si); |
| |
| if (!is_gimple_reg (PHI_RESULT (phi))) |
| { |
| scop_adjust_vphi (scop, phi, true_e); |
| 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. */ |
| |
| static void |
| compute_cloog_iv_types_1 (graphite_bb_p gbb, |
| struct clast_user_stmt *user_stmt) |
| { |
| struct clast_stmt *t; |
| int index = 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; |
| |
| /* Create an entry (clast_var, type). */ |
| tmp.cloog_iv = find_cloog_iv_in_expr (expr); |
| if (!tmp.cloog_iv) |
| continue; |
| |
| slot = htab_find_slot (GBB_CLOOG_IV_TYPES (gbb), &tmp, INSERT); |
| |
| if (!*slot) |
| { |
| 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); |
| } |
| } |
| } |
| |
| /* 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. Return true if code generation succeeded. */ |
| |
| static bool |
| 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; |
| |
| recompute_all_dominators (); |
| graphite_verify (); |
| 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 (); |
| return true; |
| } |
| |
| /* 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; |
| } |
| |
| /* 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. */ |
| |
| static void |
| graphite_trans_bb_move_loop (graphite_bb_p gb, int loop, |
| int new_loop_pos) |
| { |
| CloogMatrix *domain = GBB_DOMAIN (gb); |
| int row, j; |
| loop_p tmp_loop_p; |
| |
| 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; |
| |
| for (row = 0; row < domain->NbRows; row++) |
| { |
| 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); |
| } |
| |
| /* Copies the OLD_ROW constraint from OLD_DOMAIN to the NEW_DOMAIN at |
| row NEW_ROW. */ |
| |
| static void |
| copy_constraint (CloogMatrix *old_domain, CloogMatrix *new_domain, |
| int old_row, int new_row) |
| { |
| int i; |
| |
| gcc_assert (old_domain->NbColumns == new_domain->NbColumns |
| && old_row < old_domain->NbRows |
| && new_row < new_domain->NbRows); |
| |
| for (i = 0; i < old_domain->NbColumns; i++) |
| value_assign (new_domain->p[new_row][i], old_domain->p[old_row][i]); |
| } |
| |
| /* Swap coefficients of variables X and Y on row R. */ |
| |
| static void |
| swap_constraint_variables (CloogMatrix *domain, |
| int r, int x, int y) |
| { |
| value_swap (domain->p[r][x], domain->p[r][y]); |
| } |
| |
| /* Scale by X the coefficient C of constraint at row R in DOMAIN. */ |
| |
| static void |
| scale_constraint_variable (CloogMatrix *domain, |
| int r, int c, int x) |
| { |
| Value strip_size_value; |
| value_init (strip_size_value); |
| value_set_si (strip_size_value, x); |
| value_multiply (domain->p[r][c], domain->p[r][c], strip_size_value); |
| value_clear (strip_size_value); |
| } |
| |
| /* 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; |
| |
| 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; |
| |
| 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]); |
| |
| row = domain->NbRows; |
| |
| /* Lower bound of the outer stripped loop. */ |
| copy_constraint (new_domain, new_domain, |
| get_lower_bound_row (new_domain, col_loop_old), row); |
| swap_constraint_variables (new_domain, row, col_loop_old, col_loop_strip); |
| row++; |
| |
| /* Upper bound of the outer stripped loop. */ |
| copy_constraint (new_domain, new_domain, |
| get_upper_bound_row (new_domain, col_loop_old), row); |
| swap_constraint_variables (new_domain, row, col_loop_old, col_loop_strip); |
| scale_constraint_variable (new_domain, row, col_loop_strip, stride); |
| row++; |
| |
| /* Lower bound of a tile starts at "stride * outer_iv". */ |
| row = get_lower_bound_row (new_domain, col_loop_old); |
| 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 * stride); |
| |
| /* Upper bound of a tile stops at "stride * outer_iv + stride - 1", |
| or at the old upper bound that is not modified. */ |
| 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); |
| |
| 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); |
| |
| niter = find_loop_niter (loop, &exit); |
| if (niter == chrec_dont_know |
| || TREE_CODE (niter) != INTEGER_CST) |
| return true; |
| |
| niter_val = int_cst_value (niter); |
| |
| if (niter_val < stride) |
| { |
| res = false; |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| { |
| fprintf (dump_file, "\nStrip Mining is not profitable for loop %d:", |
| loop->num); |
| fprintf (dump_file, "number of iterations is too low.\n"); |
| } |
| } |
| |
| 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)) |
| { |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| fprintf (dump_file, |
| "\nInterchange not valid for loops %d and %d:\n", i, j); |
| return false; |
| } |
| 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); |
| |
| return true; |
| } |
| |
| /* Loop block LOOPS innermost loops of a loop nest. BBS represent the |
| basic blocks that belong to the loop nest to be blocked. */ |
| |
| static bool |
| graphite_trans_loop_block (VEC (graphite_bb_p, heap) *bbs, int loops) |
| { |
| graphite_bb_p gb; |
| int i; |
| bool transform_done = false; |
| |
| /* TODO: - Calculate the stride size automatically. */ |
| int stride_size = 51; |
| |
| for (i = 0; VEC_iterate (graphite_bb_p, bbs, i, gb); i++) |
| transform_done |= graphite_trans_bb_block (gb, stride_size, loops); |
| |
| return transform_done; |
| } |
| |
| /* Loop block all basic blocks of SCOP. Return false when the |
| transform is not performed. */ |
| |
| static bool |
| graphite_trans_scop_block (scop_p scop) |
| { |
| 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; |
| |
| /* 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++) |
| { |
| /* 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); |
| |
| /* 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); |
| } |
| |
| /* 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 >= 2) |
| 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; |
| |
| /* Sort the list of bbs. Keep them always sorted. */ |
| graphite_sort_gbbs (scop); |
| |
| if (flag_loop_block) |
| transform_done = graphite_trans_scop_block (scop); |
| |
| /* 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; |
| |
| return transform_done; |
| } |
| |
| /* 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. */ |
| |
| static void |
| limit_scops (void) |
| { |
| 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++) |
| { |
| 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_sese_p (loop_outer (loop), SCOP_REGION (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); |
| } |
| } |
| |
| free_scops (current_scops); |
| current_scops = VEC_alloc (scop_p, heap, 3); |
| |
| create_sese_edges (tmp_scops); |
| build_graphite_scops (tmp_scops); |
| VEC_free (sd_region, heap, tmp_scops); |
| } |
| |
| /* Perform a set of linear transforms on the loops of the current |
| function. */ |
| |
| void |
| graphite_transform_loops (void) |
| { |
| int i; |
| scop_p scop; |
| bool transform_done = false; |
| |
| if (number_of_loops () <= 1) |
| 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 (); |
| |
| 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_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; |
| |
| add_conditions_to_constraints (scop); |
| build_scop_canonical_schedules (scop); |
| |
| build_scop_data_accesses (scop); |
| build_scop_dynamic_schedules (scop); |
| |
| 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); |
| } |
| |
| if (graphite_apply_transformations (scop)) |
| transform_done = gloog (scop, find_transform (scop)); |
| #ifdef ENABLE_CHECKING |
| else |
| { |
| struct clast_stmt *stmt = find_transform (scop); |
| cloog_clast_free (stmt); |
| } |
| #endif |
| } |
| |
| /* Cleanup. */ |
| if (transform_done) |
| cleanup_tree_cfg (); |
| |
| free_scops (current_scops); |
| cloog_finalize (); |
| free_original_copy_tables (); |
| } |
| |
| #else /* If Cloog is not available: #ifndef HAVE_cloog. */ |
| |
| void |
| graphite_transform_loops (void) |
| { |
| sorry ("Graphite loop optimizations cannot be used"); |
| } |
| |
| #endif |