/* Gimple Represented as Polyhedra.
- Copyright (C) 2006, 2007, 2008 Free Software Foundation, Inc.
+ Copyright (C) 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
Contributed by Sebastian Pop <sebastian.pop@inria.fr>.
This file is part of GCC.
/* Converts a GMP constant V to a tree and returns it. */
static tree
-gmp_cst_to_tree (Value v)
+gmp_cst_to_tree (tree type, Value v)
{
- return build_int_cst (integer_type_node, value_get_si (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);
+}
+
+\f
+
/* Debug the list of old induction variables for this SCOP. */
void
VEC_free (iv_stack_entry_p, heap, *stack);
}
+\f
+
+/* 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);
+}
+
+\f
+
+/* 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. */
{
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_term *term = (struct clast_term*)
+ 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 (((struct clast_assignment *)t)->RHS->type == expr_term
+ if (expr->type == expr_term
&& !term->var)
{
- tree value = gmp_cst_to_tree (term->val);
+ 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;
if (bb == exit)
fprintf (file, "%d [shape=box];\n", bb->index);
- if (bb_in_scop_p (bb, scop))
+ if (bb_in_sese_p (bb, SCOP_REGION (scop)))
fprintf (file, "%d [color=red];\n", bb->index);
FOR_EACH_EDGE (e, ei, bb->succs)
/* Select color for SCoP. */
for (i = 0; VEC_iterate (scop_p, current_scops, i, scop); i++)
- if (bb_in_scop_p (bb, scop)
+ if (bb_in_sese_p (bb, SCOP_REGION (scop))
|| (SCOP_EXIT (scop) == bb)
|| (SCOP_ENTRY (scop) == bb))
{
fprintf (file, " <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">", color);
- if (!bb_in_scop_p (bb, scop))
+ if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
fprintf (file, " (");
if (bb == SCOP_ENTRY (scop)
else
fprintf (file, " %d ", bb->index);
- if (!bb_in_scop_p (bb, scop))
+ if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
fprintf (file, ")");
fprintf (file, "</TD></TR>\n");
struct loop *nest;
nest = bb->loop_father;
- while (loop_outer (nest) && loop_in_scop_p (loop_outer (nest), scop))
+ while (loop_outer (nest)
+ && loop_in_sese_p (loop_outer (nest), SCOP_REGION (scop)))
nest = loop_outer (nest);
return nest;
|| evolution_function_is_affine_multivariate_p (scev, n));
}
-/* Return false if the tree_code of the operand OP or any of its operands
- is component_ref. */
+/* Return true if REF or any of its subtrees contains a
+ component_ref. */
static bool
-exclude_component_ref (tree op)
+contains_component_ref_p (tree ref)
{
- int i;
- int len;
+ if (!ref)
+ return false;
- if (op)
+ while (handled_component_p (ref))
{
- if (TREE_CODE (op) == COMPONENT_REF)
- return false;
- else
- {
- len = TREE_OPERAND_LENGTH (op);
- for (i = 0; i < len; ++i)
- {
- if (!exclude_component_ref (TREE_OPERAND (op, i)))
- return false;
- }
- }
+ if (TREE_CODE (ref) == COMPONENT_REF)
+ return true;
+
+ ref = TREE_OPERAND (ref, 0);
}
- return true;
+ return false;
}
/* Return true if the operand OP is simple. */
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 exclude_component_ref (op);
+ return true;
}
/* Return true only when STMT is simple enough for being handled by
size_t n = gimple_call_num_args (stmt);
tree lhs = gimple_call_lhs (stmt);
- for (i = 0; i < n; i++)
- {
- tree arg = gimple_call_arg (stmt, i);
+ if (lhs && !is_simple_operand (loop, stmt, lhs))
+ return false;
- if (!(is_simple_operand (loop, stmt, lhs)
- && is_simple_operand (loop, stmt, arg)))
- return false;
- }
+ for (i = 0; i < n; i++)
+ if (!is_simple_operand (loop, stmt, gimple_call_arg (stmt, i)))
+ return false;
return true;
}
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;
}
struct loop *nest = outermost_loop_in_scop (scop, bb);
gimple_stmt_iterator gsi;
- bitmap_set_bit (SCOP_BBS_B (scop), bb->index);
-
for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
find_data_references_in_stmt (nest, gsi_stmt (gsi), &drs);
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);
}
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));
XDELETE (gbb);
}
-/* Creates a new scop starting with ENTRY. */
+\f
-static scop_p
-new_scop (edge entry, edge exit)
+/* 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
{
- scop_p scop = XNEW (struct scop);
-
- gcc_assert (entry && exit);
+ tree old_name, new_name;
+} *rename_map_elt;
- SCOP_REGION (scop) = XNEW (struct sese);
- SESE_ENTRY (SCOP_REGION (scop)) = entry;
- SESE_EXIT (SCOP_REGION (scop)) = exit;
- SCOP_BBS (scop) = VEC_alloc (graphite_bb_p, heap, 3);
- SCOP_OLDIVS (scop) = VEC_alloc (name_tree, heap, 3);
- SCOP_BBS_B (scop) = BITMAP_ALLOC (NULL);
- SCOP_LOOPS (scop) = BITMAP_ALLOC (NULL);
- SCOP_LOOP_NEST (scop) = VEC_alloc (loop_p, heap, 3);
- SCOP_ADD_PARAMS (scop) = true;
- SCOP_PARAMS (scop) = VEC_alloc (name_tree, heap, 3);
- SCOP_PROG (scop) = cloog_program_malloc ();
- cloog_program_set_names (SCOP_PROG (scop), cloog_names_malloc ());
- SCOP_LOOP2CLOOG_LOOP (scop) = htab_create (10, hash_loop_to_cloog_loop,
- eq_loop_to_cloog_loop,
- free);
- return scop;
-}
-/* Deletes SCOP. */
+/* Print to stderr the element ELT. */
static void
-free_scop (scop_p scop)
+debug_rename_elt (rename_map_elt elt)
{
- int i;
- name_tree p;
- struct graphite_bb *gb;
- name_tree iv;
+ fprintf (stderr, "(");
+ print_generic_expr (stderr, elt->old_name, 0);
+ fprintf (stderr, ", ");
+ print_generic_expr (stderr, elt->new_name, 0);
+ fprintf (stderr, ")\n");
+}
- for (i = 0; VEC_iterate (graphite_bb_p, SCOP_BBS (scop), i, gb); i++)
- free_graphite_bb (gb);
+/* Helper function for debug_rename_map. */
- VEC_free (graphite_bb_p, heap, SCOP_BBS (scop));
- BITMAP_FREE (SCOP_BBS_B (scop));
- BITMAP_FREE (SCOP_LOOPS (scop));
- VEC_free (loop_p, heap, SCOP_LOOP_NEST (scop));
+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;
+}
- 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);
+/* Print to stderr all the elements of MAP. */
- VEC_free (name_tree, heap, SCOP_PARAMS (scop));
- cloog_program_free (SCOP_PROG (scop));
- htab_delete (SCOP_LOOP2CLOOG_LOOP (scop));
- XDELETE (SCOP_REGION (scop));
- XDELETE (scop);
+void
+debug_rename_map (htab_t map)
+{
+ htab_traverse (map, debug_rename_map_1, NULL);
}
-/* Deletes all scops in SCOPS. */
+/* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */
-static void
-free_scops (VEC (scop_p, heap) *scops)
+static inline rename_map_elt
+new_rename_map_elt (tree old_name, tree new_name)
{
- int i;
- scop_p scop;
-
- for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++)
- free_scop (scop);
+ rename_map_elt res;
+
+ res = XNEW (struct rename_map_elt);
+ res->old_name = old_name;
+ res->new_name = new_name;
- VEC_free (scop_p, heap, scops);
+ return res;
}
-typedef enum gbb_type {
- GBB_UNKNOWN,
+/* 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;
+}
+
+\f
+
+/* 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,
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
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:
if (result.last->loop_father != loop)
result.next = NULL;
- if (TREE_CODE (number_of_latch_executions (loop))
- == SCEV_NOT_KNOWN)
+ if (graphite_cannot_represent_loop_niter (loop))
result.difficult = true;
if (sinfo.difficult)
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;
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);
verify_dominators (CDI_DOMINATORS);
verify_dominators (CDI_POST_DOMINATORS);
verify_ssa (false);
+ verify_loop_closed_ssa ();
#endif
}
unmark_exit_edges (regions);
+ fix_loop_structure (NULL);
+
#ifdef ENABLE_CHECKING
verify_loop_structure ();
verify_dominators (CDI_DOMINATORS);
{
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 (chrec_contains_undetermined (scev))
+ if (!simple_iv (loop, loop, PHI_RESULT (phi), &iv, true))
res++;
}
tree nit;
gimple_seq stmts;
edge exit = single_dom_exit (loop);
+ bool known_niter = number_of_iterations_exit (loop, exit, &niter, false);
- if (!number_of_iterations_exit (loop, exit, &niter, false))
- gcc_unreachable ();
+ gcc_assert (known_niter);
nit = force_gimple_operand (unshare_expr (niter.niter), &stmts, true,
NULL_TREE);
if (nb_reductions_in_loop (loop) > 0)
return NULL_TREE;
- return canonicalize_loop_ivs (loop, NULL, nit);
+ return canonicalize_loop_ivs (loop, NULL, &nit);
}
/* Record LOOP as occuring in SCOP. Returns true when the operation
struct loop *loop0, *loop1;
FOR_EACH_BB (bb)
- if (bb_in_scop_p (bb, scop))
+ 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_scop_p (loop->latch, scop))
+ && bb_in_sese_p (loop->latch, SCOP_REGION (scop)))
{
if (!scop_record_loop (scop, loop))
return false;
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
}
}
+/* 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:
static void
build_scop_canonical_schedules (scop_p scop)
{
- int i, j;
+ int i;
graphite_bb_p gb;
- int nb = scop_nb_loops (scop) + 1;
+ int nb_loops = scop_nb_loops (scop);
+ lambda_vector static_schedule = lambda_vector_new (nb_loops + 1);
+ VEC (loop_p, heap) *loops_previous = NULL;
- SCOP_STATIC_SCHEDULE (scop) = lambda_vector_new (nb);
+ /* 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 offset = nb_loops_around_gb (gb);
-
- /* After leaving a loop, it is possible that the schedule is not
- set at zero. This loop reinitializes components located
- after OFFSET. */
-
- for (j = offset + 1; j < nb; j++)
- if (SCOP_STATIC_SCHEDULE (scop)[j])
- {
- memset (&(SCOP_STATIC_SCHEDULE (scop)[j]), 0,
- sizeof (int) * (nb - j));
- ++SCOP_STATIC_SCHEDULE (scop)[offset];
- break;
- }
-
- GBB_STATIC_SCHEDULE (gb) = lambda_vector_new (offset + 1);
- lambda_vector_copy (SCOP_STATIC_SCHEDULE (scop),
- GBB_STATIC_SCHEDULE (gb), offset + 1);
-
- ++SCOP_STATIC_SCHEDULE (scop)[offset];
+ 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);
}
}
case MINUS_EXPR:
scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
- value_oppose (k, k);
- scan_tree_for_params (s, TREE_OPERAND (e, 1), c, r, k, subtract);
+ scan_tree_for_params (s, TREE_OPERAND (e, 1), c, r, k, !subtract);
break;
case NEGATE_EXPR:
- value_oppose (k, k);
- scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
+ scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, !subtract);
break;
case SSA_NAME:
}
break;
- case NOP_EXPR:
- case CONVERT_EXPR:
+ CASE_CONVERT:
case NON_LVALUE_EXPR:
scan_tree_for_params (s, TREE_OPERAND (e, 0), c, r, k, subtract);
break;
irp.loop = father;
irp.scop = scop;
for_each_index (&dr->ref, idx_record_params, &irp);
- free_data_ref (dr);
}
/* Find parameters in conditional statements. */
else
gcc_unreachable ();
- if (loop->inner && loop_in_scop_p (loop->inner, scop))
+ 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_scop_p (loop->next, scop))
+ 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++)
else
{
nb_rows = 0;
- nb_cols = scop_nb_params (scop) + 2;
+ nb_cols = nb_loops_around_gb (gb) + scop_nb_params (scop) + 2;
}
/* Count number of necessary new rows to add the conditions to the
CloogMatrix *new_domain;
new_domain = cloog_matrix_alloc (nb_rows + nb_new_rows, nb_cols);
- for (i = 0; i < nb_rows; i++)
- for (j = 0; j < nb_cols; j++)
- value_assign (new_domain->p[i][j], domain->p[i][j]);
+ 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);
+ }
- cloog_matrix_free (domain);
domain = new_domain;
GBB_DOMAIN (gb) = new_domain;
- }
+ }
/* Add the conditions to the new enlarged domain matrix. */
row = nb_rows;
}
}
-/* Helper recursive function. */
+/* Returns true when PHI defines an induction variable in the loop
+ containing the PHI node. */
-static void
+static bool
+phi_node_is_iv (gimple phi)
+{
+ loop_p loop = gimple_bb (phi)->loop_father;
+ tree scev = analyze_scalar_evolution (loop, gimple_phi_result (phi));
+
+ return tree_contains_chrecs (scev, NULL);
+}
+
+/* Returns true when BB contains scalar phi nodes that are not an
+ induction variable of a loop. */
+
+static bool
+bb_contains_non_iv_scalar_phi_nodes (basic_block bb)
+{
+ gimple phi = NULL;
+ gimple_stmt_iterator si;
+
+ for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
+ if (is_gimple_reg (gimple_phi_result (gsi_stmt (si))))
+ {
+ /* Store the unique scalar PHI node: at this point, loops
+ should be in cannonical form, so we expect to see at most
+ one scalar phi node in the loop header. */
+ if (phi
+ || bb != bb->loop_father->header)
+ return true;
+
+ phi = gsi_stmt (si);
+ }
+
+ if (!phi
+ || phi_node_is_iv (phi))
+ return false;
+
+ return true;
+}
+
+/* Helper recursive function. Record in CONDITIONS and CASES all
+ conditions from 'if's and 'switch'es occurring in BB from SCOP.
+
+ Returns false when the conditions contain scalar computations that
+ depend on the condition, i.e. when there are scalar phi nodes on
+ the junction after the condition. Only the computations occurring
+ on memory can be handled in the polyhedral model: operations that
+ define scalar evolutions in conditions, that can potentially be
+ used to index memory, can't be handled by the polyhedral model. */
+
+static bool
build_scop_conditions_1 (VEC (gimple, heap) **conditions,
VEC (gimple, heap) **cases, basic_block bb,
scop_p scop)
{
+ bool res = true;
int i, j;
graphite_bb_p gbb;
- gimple_stmt_iterator gsi;
basic_block bb_child, bb_iter;
VEC (basic_block, heap) *dom;
+ gimple stmt;
/* Make sure we are in the SCoP. */
- if (!bb_in_scop_p (bb, scop))
- return;
+ if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
+ return true;
+
+ if (bb_contains_non_iv_scalar_phi_nodes (bb))
+ return false;
- /* Record conditions in graphite_bb. */
gbb = gbb_from_bb (bb);
if (gbb)
{
GBB_CONDITIONS (gbb) = VEC_copy (gimple, heap, *conditions);
GBB_CONDITION_CASES (gbb) = VEC_copy (gimple, heap, *cases);
- add_conditions_to_domain (gbb);
}
dom = get_dominated_by (CDI_DOMINATORS, bb);
- for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ stmt = last_stmt (bb);
+ if (stmt)
{
- gimple stmt = gsi_stmt (gsi);
VEC (edge, gc) *edges;
edge e;
/* Recursively scan the then or else part. */
if (e->flags & EDGE_TRUE_VALUE)
VEC_safe_push (gimple, heap, *cases, stmt);
- else if (e->flags & EDGE_FALSE_VALUE)
- VEC_safe_push (gimple, heap, *cases, NULL);
- else
- gcc_unreachable ();
+ else
+ {
+ gcc_assert (e->flags & EDGE_FALSE_VALUE);
+ VEC_safe_push (gimple, heap, *cases, NULL);
+ }
VEC_safe_push (gimple, heap, *conditions, stmt);
- build_scop_conditions_1 (conditions, cases, e->dest, scop);
+ if (!build_scop_conditions_1 (conditions, cases, e->dest, scop))
+ {
+ res = false;
+ goto done;
+ }
VEC_pop (gimple, *conditions);
VEC_pop (gimple, *cases);
}
bb_child = label_to_block
(CASE_LABEL (gimple_switch_label (stmt, i)));
- /* Do not handle multiple values for the same block. */
for (k = 0; k < n; k++)
if (i != k
&& label_to_block
(CASE_LABEL (gimple_switch_label (stmt, k))) == bb_child)
break;
- if (k != n)
- continue;
-
- /* Switch cases with more than one predecessor are not
- handled. */
- if (VEC_length (edge, bb_child->preds) != 1)
- continue;
+ /* 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 stmt_gimple_label
- = gsi_stmt (gsi_search_gimple_label);
+ gimple label = gsi_stmt (gsi_search_gimple_label);
- if (gimple_code (stmt_gimple_label) == GIMPLE_LABEL)
+ if (gimple_code (label) == GIMPLE_LABEL)
{
- tree t = gimple_label_label (stmt_gimple_label);
+ tree t = gimple_label_label (label);
- if (t == gimple_switch_label (stmt, i))
- VEC_replace (gimple, *cases, n_cases,
- stmt_gimple_label);
- else
- gcc_unreachable ();
+ gcc_assert (t == gimple_switch_label (stmt, i));
+ VEC_replace (gimple, *cases, n_cases, label);
+ break;
}
}
- build_scop_conditions_1 (conditions, cases, bb_child, scop);
+ 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++)
{
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++)
- build_scop_conditions_1 (conditions, cases, bb_child, scop);
+ 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 'if' and 'switch' conditions in each gbb of SCOP. */
+/* Record all conditions from SCOP.
-static void
+ 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;
- build_scop_conditions_1 (&conditions, &cases, SCOP_ENTRY (scop), scop);
+ 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
/* Build cloog loop for all loops, that are in the uppermost loop layer of
this SCoP. */
for (i = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), i, loop); i++)
- if (!loop_in_scop_p (loop_outer (loop), scop))
+ if (!loop_in_sese_p (loop_outer (loop), SCOP_REGION (scop)))
{
/* The outermost constraints is a matrix that has:
-first column: eq/ineq boolean
int i, ndim = DR_NUM_DIMENSIONS (ref);
struct access_matrix *am = GGC_NEW (struct access_matrix);
- AM_MATRIX (am) = VEC_alloc (lambda_vector, heap, ndim);
+ AM_MATRIX (am) = VEC_alloc (lambda_vector, gc, ndim);
DR_SCOP (ref) = GBB_SCOP (gb);
for (i = 0; i < ndim; i++)
if (!build_access_matrix_with_af (af, v, scop, ref_nb_loops (ref)))
return false;
- VEC_safe_push (lambda_vector, heap, AM_MATRIX (am), v);
+ VEC_quick_push (lambda_vector, AM_MATRIX (am), v);
}
DR_ACCESS_MATRIX (ref) = am;
name_tree t;
tree iv;
- for (i = 0; VEC_iterate (name_tree, params, i, t); i++)
- if (!strcmp (name, t->name))
- return t->t;
+ 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)
gcc_unreachable ();
}
-/* A union needed to convert from CLAST expressions to GMP values. */
+/* 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;
+}
-typedef union {
- struct clast_expr *c;
- Value v;
-} value_clast;
+static tree
+clast_to_gcc_expression (tree, struct clast_expr *, VEC (name_tree, heap) *,
+ loop_iv_stack);
-/* Converts a Cloog AST expression E back to a GCC expression tree. */
+/* 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 (struct clast_expr *e,
- VEC (name_tree, heap) *params,
- loop_iv_stack ivstack)
+clast_to_gcc_expression_red (tree type, enum tree_code op,
+ struct clast_reduction *r,
+ VEC (name_tree, heap) *params,
+ loop_iv_stack ivstack)
{
- tree type = integer_type_node;
+ 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;
+}
- gcc_assert (e);
+/* 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:
if (t->var)
{
if (value_one_p (t->val))
- return clast_name_to_gcc (t->var, params, ivstack);
+ {
+ tree name = clast_name_to_gcc (t->var, params, ivstack);
+ return fold_convert (type, name);
+ }
else if (value_mone_p (t->val))
- return fold_build1 (NEGATE_EXPR, type,
- clast_name_to_gcc (t->var, params, ivstack));
+ {
+ tree name = clast_name_to_gcc (t->var, params, ivstack);
+ name = fold_convert (type, name);
+ return fold_build1 (NEGATE_EXPR, type, name);
+ }
else
- return fold_build2 (MULT_EXPR, type,
- gmp_cst_to_tree (t->val),
- clast_name_to_gcc (t->var, params, ivstack));
+ {
+ 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 (t->val);
+ return gmp_cst_to_tree (type, t->val);
}
case expr_red:
{
struct clast_reduction *r = (struct clast_reduction *) e;
- tree left, right;
switch (r->type)
{
case clast_red_sum:
- if (r->n == 1)
- return clast_to_gcc_expression (r->elts[0], params, ivstack);
-
- else
- {
- gcc_assert (r->n >= 1
- && r->elts[0]->type == expr_term
- && r->elts[1]->type == expr_term);
-
- left = clast_to_gcc_expression (r->elts[0], params, ivstack);
- right = clast_to_gcc_expression (r->elts[1], params, ivstack);
- return fold_build2 (PLUS_EXPR, type, left, right);
- }
-
- break;
+ return clast_to_gcc_expression_red (type, PLUS_EXPR, r, params, ivstack);
case clast_red_min:
- if (r->n == 1)
- return clast_to_gcc_expression (r->elts[0], params, ivstack);
-
- else if (r->n == 2)
- {
- left = clast_to_gcc_expression (r->elts[0], params, ivstack);
- right = clast_to_gcc_expression (r->elts[1], params, ivstack);
- return fold_build2 (MIN_EXPR, type, left, right);
- }
-
- else
- gcc_unreachable();
-
- break;
+ return clast_to_gcc_expression_red (type, MIN_EXPR, r, params, ivstack);
case clast_red_max:
- if (r->n == 1)
- return clast_to_gcc_expression (r->elts[0], params, ivstack);
-
- else if (r->n == 2)
- {
- left = clast_to_gcc_expression (r->elts[0], params, ivstack);
- right = clast_to_gcc_expression (r->elts[1], params, ivstack);
- return fold_build2 (MAX_EXPR, type, left, right);
- }
-
- else
- gcc_unreachable();
-
- break;
+ return clast_to_gcc_expression_red (type, MAX_EXPR, r, params, ivstack);
default:
gcc_unreachable ();
{
struct clast_binary *b = (struct clast_binary *) e;
struct clast_expr *lhs = (struct clast_expr *) b->LHS;
- tree tl = clast_to_gcc_expression (lhs, params, ivstack);
- value_clast r;
- tree tr;
-
- r.c = (struct clast_expr *) b->RHS;
- tr = gmp_cst_to_tree (r.v);
+ tree tl = clast_to_gcc_expression (type, lhs, params, ivstack);
+ tree tr = gmp_cst_to_tree (type, b->RHS);
switch (b->type)
{
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
loop_iv_stack ivstack)
{
enum tree_code comp;
- tree lhs = clast_to_gcc_expression (cleq->LHS, SCOP_PARAMS (scop), ivstack);
- tree rhs = clast_to_gcc_expression (cleq->RHS, SCOP_PARAMS (scop), ivstack);
+ 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
comp = LE_EXPR;
- return fold_build2 (comp, integer_type_node, lhs, rhs);
+ return fold_build2 (comp, type, lhs, rhs);
}
/* Creates the test for the condition in STMT. */
tree eq = graphite_translate_clast_equation (scop, &stmt->eq[i], ivstack);
if (cond)
- cond = fold_build2 (TRUTH_AND_EXPR, integer_type_node, cond, eq);
+ cond = fold_build2 (TRUTH_AND_EXPR, TREE_TYPE (eq), cond, eq);
else
cond = eq;
}
return exit_edge;
}
+/* Walks a CLAST and returns the first statement in the body of a
+ loop. */
-/* 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)
-{
- struct loop *loop;
- tree ivvar;
- tree stride, lowb, upb;
- tree iv_before;
-
- gcc_assert (stmt->LB
- && stmt->UB);
-
- stride = gmp_cst_to_tree (stmt->stride);
- lowb = clast_to_gcc_expression (stmt->LB, SCOP_PARAMS (scop), ivstack);
- ivvar = create_tmp_var (integer_type_node, "graphiteIV");
- add_referenced_var (ivvar);
-
- upb = clast_to_gcc_expression (stmt->UB, SCOP_PARAMS (scop), ivstack);
- loop = create_empty_loop_on_edge (entry_edge, lowb, stride, upb, ivvar,
- &iv_before, outer ? outer
- : entry_edge->src->loop_father);
-
- loop_iv_stack_push_iv (ivstack, iv_before, stmt->iterator);
-
- return loop;
-}
-
-/* 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
+static struct clast_user_stmt *
+clast_get_body_of_loop (struct clast_stmt *stmt)
{
- tree old_name, new_name;
-} *rename_map_elt;
-
-
-/* Print to stderr the element ELT. */
+ if (!stmt
+ || CLAST_STMT_IS_A (stmt, stmt_user))
+ return (struct clast_user_stmt *) stmt;
-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;
+ if (CLAST_STMT_IS_A (stmt, stmt_for))
+ return clast_get_body_of_loop (((struct clast_for *) stmt)->body);
- return res;
-}
+ if (CLAST_STMT_IS_A (stmt, stmt_guard))
+ return clast_get_body_of_loop (((struct clast_guard *) stmt)->then);
-/* Computes a hash function for database element ELT. */
+ if (CLAST_STMT_IS_A (stmt, stmt_block))
+ return clast_get_body_of_loop (((struct clast_block *) stmt)->body);
-static hashval_t
-rename_map_elt_info (const void *elt)
-{
- return htab_hash_pointer (((const struct rename_map_elt *) elt)->old_name);
+ gcc_unreachable ();
}
-/* Compares database elements E1 and E2. */
+/* Returns the induction variable for the loop that gets translated to
+ STMT. */
-static int
-eq_rename_map_elts (const void *e1, const void *e2)
+static tree
+gcc_type_for_iv_of_clast_loop (struct clast_for *stmt_for)
{
- const struct rename_map_elt *elt1 = (const struct rename_map_elt *) e1;
- const struct rename_map_elt *elt2 = (const struct rename_map_elt *) e2;
+ 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 (elt1->old_name == elt2->old_name);
+ return gcc_type_for_cloog_iv (cloog_iv, gbb);
}
-/* Returns the new name associated to OLD_NAME in MAP. */
+/* 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 tree
-get_new_name_from_old_name (htab_t map, tree old_name)
+static struct loop *
+graphite_create_new_loop (scop_p scop, edge entry_edge,
+ struct clast_for *stmt, loop_iv_stack ivstack,
+ loop_p outer)
{
- 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;
+ 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);
- return old_name;
+ 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. */
ssa_op_iter iter;
use_operand_p use_p;
- FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
+ FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
{
tree use = USE_FROM_PTR (use_p);
tree new_name = get_new_name_from_old_name (map, use);
}
static void expand_scalar_variables_stmt (gimple, basic_block, scop_p,
- loop_p, htab_t);
+ 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);
+ }
+}
-/* Constructs a tree which only contains old_ivs and parameters. Any
- other variables that are defined outside BB will be eliminated by
- using their definitions in the constructed tree. OLD_LOOP_FATHER
- is the original loop that contained BB. */
+/* 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,
- loop_p old_loop_father, htab_t map)
+ htab_t map, gimple_stmt_iterator *gsi)
{
- if ((TREE_CODE_CLASS (code) == tcc_constant
- && code == INTEGER_CST)
- || TREE_CODE_CLASS (code) == tcc_reference)
+ 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);
+
+ 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, old_loop_father, map);
-
+ tree op0_expr = expand_scalar_variables_expr (op0_type, op0, op0_code,
+ NULL, bb, scop, map, gsi);
+
return fold_build1 (code, type, op0_expr);
}
{
tree op0_type = TREE_TYPE (op0);
enum tree_code op0_code = TREE_CODE (op0);
- tree op0_expr =
- expand_scalar_variables_expr (op0_type, op0, op0_code,
- NULL, bb, scop, old_loop_father, map);
+ tree 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, old_loop_father, map);
+ 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)
- {
- tree var0, var1;
- gimple def_stmt;
- enum tree_code subcode;
-
- if (is_parameter (scop, op0)
- || is_iv (op0))
- return get_new_name_from_old_name (map, op0);
-
- def_stmt = SSA_NAME_DEF_STMT (op0);
-
- if (gimple_bb (def_stmt) == bb)
- {
- /* If the defining statement is in the basic block already
- we do not need to create a new expression for it, we
- only need to ensure its operands are expanded. */
- expand_scalar_variables_stmt (def_stmt, bb, scop,
- old_loop_father, map);
- return get_new_name_from_old_name (map, op0);
-
- }
- else
- {
- if (gimple_code (def_stmt) != GIMPLE_ASSIGN
- || !bb_in_scop_p (gimple_bb (def_stmt), scop))
- return get_new_name_from_old_name (map, op0);
-
- var0 = gimple_assign_rhs1 (def_stmt);
- subcode = gimple_assign_rhs_code (def_stmt);
- var1 = gimple_assign_rhs2 (def_stmt);
-
- return expand_scalar_variables_expr (type, var0, subcode, var1,
- bb, scop, old_loop_father, map);
- }
- }
+ return expand_scalar_variables_ssa_name (op0, bb, scop, map, gsi);
gcc_unreachable ();
return NULL;
}
-/* Replicates any uses of non-parameters and non-old-ivs variablesthat
- are defind outside BB with code that is inserted in BB.
- OLD_LOOP_FATHER is the original loop that contained STMT. */
+/* 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,
- loop_p old_loop_father, htab_t map)
+ 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);
+ enum tree_code code = TREE_CODE (use);
tree use_expr = expand_scalar_variables_expr (type, use, code, NULL, bb,
- scop, old_loop_father, map);
+ scop, map, &gsi);
if (use_expr != use)
{
- gimple_stmt_iterator gsi = gsi_after_labels (bb);
tree new_use =
force_gimple_operand_gsi (&gsi, use_expr, true, NULL,
true, GSI_NEW_STMT);
update_stmt (stmt);
}
-/* Copies the definitions outside of BB of variables that are not
- induction variables nor parameters. BB must only contain
- "external" references to these types of variables. OLD_LOOP_FATHER
- is the original loop that contained BB. */
+/* 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,
- loop_p old_loop_father, htab_t map)
+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, old_loop_father, map);
+ expand_scalar_variables_stmt (stmt, bb, scop, map);
gsi_next (&gsi);
}
}
-/* Rename all the SSA_NAMEs from block BB that appear in IVSTACK in
- terms of new induction variables. OLD is the original loop that
- contained BB. */
+/* Rename all the SSA_NAMEs from block BB according to the MAP. */
static void
rename_variables (basic_block bb, htab_t map)
/* Register in MAP the tuple (old_name, new_name). */
static void
-register_old_new_names (htab_t map, tree old_name, tree new_name)
+register_old_and_new_names (htab_t map, tree old_name, tree new_name)
{
struct rename_map_elt tmp;
PTR *slot;
operands. */
copy = gimple_copy (stmt);
gsi_insert_after (&gsi_tgt, copy, GSI_NEW_STMT);
- mark_symbols_for_renaming (copy);
+ mark_sym_for_renaming (gimple_vop (cfun));
region = lookup_stmt_eh_region (stmt);
if (region >= 0)
/* 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)
+ FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_ALL_DEFS)
{
tree old_name = DEF_FROM_PTR (def_p);
tree new_name = create_new_def_for (old_name, copy, def_p);
- register_old_new_names (map, old_name, new_name);
+ register_old_and_new_names (map, old_name, new_name);
}
}
}
+/* Records in SCOP_LIVEOUT_RENAMES the names that are live out of
+ the SCOP and that appear in the RENAME_MAP. */
+
+static void
+register_scop_liveout_renames (scop_p scop, htab_t rename_map)
+{
+ int i;
+ sese region = SCOP_REGION (scop);
+
+ for (i = 0; i < SESE_NUM_VER (region); i++)
+ if (bitmap_bit_p (SESE_LIVEOUT (region), i)
+ && is_gimple_reg (ssa_name (i)))
+ {
+ tree old_name = ssa_name (i);
+ tree new_name = get_new_name_from_old_name (rename_map, old_name);
+
+ register_old_and_new_names (SCOP_LIVEOUT_RENAMES (scop),
+ old_name, new_name);
+ }
+}
+
/* Copies BB and includes in the copied BB all the statements that can
be reached following the use-def chains from the memory accesses,
and returns the next edge following this new block. */
static edge
copy_bb_and_scalar_dependences (basic_block bb, scop_p scop,
- loop_p context_loop,
edge next_e, htab_t map)
{
basic_block new_bb = split_edge (next_e);
remove_condition (new_bb);
rename_variables (new_bb, map);
remove_phi_nodes (new_bb);
- expand_scalar_variables (new_bb, scop, context_loop, map);
+ expand_scalar_variables (new_bb, scop, map);
+ register_scop_liveout_renames (scop, map);
return next_e;
}
-/* Translates a CLAST statement STMT to GCC representation. NEXT_E is
- the edge where new generated code should be attached. BB_EXIT is the last
- basic block that defines the scope of code generation. CONTEXT_LOOP is the
- loop in which the generated code will be placed (might be NULL). */
+/* 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,
loop_iv_stack_patch_for_consts (ivstack, (struct clast_user_stmt *) stmt);
build_iv_mapping (ivstack, map, gbb, scop);
next_e = copy_bb_and_scalar_dependences (GBB_BB (gbb), scop,
- context_loop, next_e, map);
+ next_e, map);
htab_delete (map);
loop_iv_stack_remove_constants (ivstack);
- update_ssa (TODO_update_ssa);
recompute_all_dominators ();
+ update_ssa (TODO_update_ssa);
graphite_verify ();
return translate_clast (scop, context_loop, stmt->next, next_e, ivstack);
}
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);
}
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);
}
find_transform (scop_p scop)
{
struct clast_stmt *stmt;
- CloogOptions *options = set_cloog_options ();
-
- /* Connect new cloog prog generation to graphite. */
- build_cloog_prog (scop);
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "Cloog Input [\n");
- cloog_program_print (dump_file, SCOP_PROG(scop));
- fprintf (dump_file, "]\n");
- }
-
- SCOP_PROG (scop) = cloog_program_generate (SCOP_PROG (scop), options);
- stmt = cloog_clast_create (SCOP_PROG (scop), options);
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "Cloog Output[\n");
- pprint (dump_file, stmt, 0, options);
- cloog_program_dump_cloog (dump_file, SCOP_PROG (scop));
- fprintf (dump_file, "]\n");
- }
-
- cloog_options_free (options);
- return stmt;
-}
-
-/* Returns true when it is possible to generate code for this STMT.
- For the moment we cannot generate code when Cloog decides to
- duplicate a statement, as we do not do a copy, but a move.
- USED_BASIC_BLOCKS records the blocks that have already been seen.
- We return false if we have to generate code twice for the same
- block. */
-
-static bool
-can_generate_code_stmt (struct clast_stmt *stmt,
- struct pointer_set_t *used_basic_blocks)
-{
- if (!stmt)
- return true;
-
- if (CLAST_STMT_IS_A (stmt, stmt_root))
- return can_generate_code_stmt (stmt->next, used_basic_blocks);
-
- if (CLAST_STMT_IS_A (stmt, stmt_user))
- {
- CloogStatement *cs = ((struct clast_user_stmt *) stmt)->statement;
- graphite_bb_p gbb = (graphite_bb_p) cloog_statement_usr (cs);
-
- if (pointer_set_contains (used_basic_blocks, gbb))
- return false;
- pointer_set_insert (used_basic_blocks, gbb);
- return can_generate_code_stmt (stmt->next, used_basic_blocks);
- }
-
- if (CLAST_STMT_IS_A (stmt, stmt_for))
- return can_generate_code_stmt (((struct clast_for *) stmt)->body,
- used_basic_blocks)
- && can_generate_code_stmt (stmt->next, used_basic_blocks);
-
- if (CLAST_STMT_IS_A (stmt, stmt_guard))
- return can_generate_code_stmt (((struct clast_guard *) stmt)->then,
- used_basic_blocks);
+ CloogOptions *options = set_cloog_options ();
- if (CLAST_STMT_IS_A (stmt, stmt_block))
- return can_generate_code_stmt (((struct clast_block *) stmt)->body,
- used_basic_blocks)
- && can_generate_code_stmt (stmt->next, used_basic_blocks);
+ /* Connect new cloog prog generation to graphite. */
+ build_cloog_prog (scop);
- return false;
-}
+ 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");
+ }
-/* Returns true when it is possible to generate code for this STMT. */
+ SCOP_PROG (scop) = cloog_program_generate (SCOP_PROG (scop), options);
+ stmt = cloog_clast_create (SCOP_PROG (scop), options);
-static bool
-can_generate_code (struct clast_stmt *stmt)
-{
- bool result;
- struct pointer_set_t *used_basic_blocks = pointer_set_create ();
+ 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");
+ }
- result = can_generate_code_stmt (stmt, used_basic_blocks);
- pointer_set_destroy (used_basic_blocks);
- return result;
+ cloog_options_free (options);
+ return stmt;
}
/* Remove from the CFG the 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;
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) = single_succ_edge (false_edge->dest);
+ SESE_EXIT (region) = false_edge;
if_region->false_region = region;
if (slot)
return if_region;
}
-/* Returns true when BB is in REGION. */
+/* Add exit phis for USE on EXIT. */
-static bool
-bb_in_sese_p (basic_block bb, sese region)
+static void
+scop_add_exit_phis_edge (basic_block exit, tree use, edge false_e, edge true_e)
{
- return (dominated_by_p (CDI_DOMINATORS, bb, SESE_ENTRY (region)->src)
- && dominated_by_p (CDI_POST_DOMINATORS, bb, SESE_EXIT (region)->dest));
+ 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);
}
-/* For USE in BB, if it is used outside of the REGION it is defined in,
- mark it for rewrite. Record basic block BB where it is used
- to USE_BLOCKS. Record the ssa name index to NEED_PHIS bitmap. */
+/* Add phi nodes for VAR that is used in LIVEIN. Phi nodes are
+ inserted in block BB. */
static void
-sese_find_uses_to_rename_use (sese region, basic_block bb, tree use,
- bitmap *use_blocks, bitmap need_phis)
+scop_add_exit_phis_var (basic_block bb, tree var, bitmap livein,
+ edge false_e, edge true_e)
{
- unsigned ver;
- basic_block def_bb;
+ bitmap def;
+ basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (var));
- if (TREE_CODE (use) != SSA_NAME)
- return;
+ 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);
- 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;
+ || !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);
- if (!use_blocks[ver])
- use_blocks[ver] = BITMAP_ALLOC (NULL);
- bitmap_set_bit (use_blocks[ver], 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;
- bitmap_set_bit (need_phis, ver);
+ default:
+ return NULL_TREE;
+ }
}
-/* Marks names that are used in BB and outside of the loop they are
- defined in for rewrite. Records the set of blocks in that the ssa
- names are defined to USE_BLOCKS. Record the SSA names that will
- need exit PHIs in NEED_PHIS. */
+/* 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
-sese_find_uses_to_rename_bb (sese region, basic_block bb,
- bitmap *use_blocks, bitmap need_phis)
+scop_adjust_vphi (scop_p scop, gimple phi, edge true_e)
{
- gimple_stmt_iterator bsi;
- edge e;
- edge_iterator ei;
- ssa_op_iter iter;
- tree var;
+ unsigned i;
- FOR_EACH_EDGE (e, ei, bb->succs)
- for (bsi = gsi_start_phis (e->dest); !gsi_end_p (bsi); gsi_next (&bsi))
- sese_find_uses_to_rename_use (region, bb,
- PHI_ARG_DEF_FROM_EDGE (gsi_stmt (bsi), e),
- use_blocks, need_phis);
+ gcc_assert (gimple_phi_num_args (phi) == 2);
- 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_find_uses_to_rename_use (region, bb, var, use_blocks, need_phis);
+ 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);
+ }
}
-/* Add exit phis for the USE on EXIT. */
+/* 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
-sese_add_exit_phis_edge (basic_block exit, tree use, edge false_e, edge true_e)
+scop_adjust_phis_for_liveouts (scop_p scop, basic_block bb, edge false_e,
+ edge true_e)
{
- gimple phi = create_phi_node (use, exit);
+ gimple_stmt_iterator si;
- 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, integer_zero_node, true_e);
+ 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);
+ }
+ }
}
-/* Add phi nodes for VAR that is used in LIVEIN. Phi nodes are
- inserted in block WHERE. */
+/* 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
-sese_add_exit_phis_var (basic_block where, tree var, bitmap livein,
- edge false_e, edge true_e)
+compute_cloog_iv_types_1 (graphite_bb_p gbb,
+ struct clast_user_stmt *user_stmt)
{
- bitmap def;
- basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (var));
+ struct clast_stmt *t;
+ int index = 0;
- if (is_gimple_reg (var))
- bitmap_clear_bit (livein, def_bb->index);
- else
- bitmap_set_bit (livein, def_bb->index);
+ 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;
- def = BITMAP_ALLOC (NULL);
- bitmap_set_bit (def, def_bb->index);
- compute_global_livein (livein, def);
- BITMAP_FREE (def);
+ /* 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);
- sese_add_exit_phis_edge (where, var, false_e, true_e);
+ 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);
+ }
+ }
}
-/* Insert in the block WHERE phi nodes for variables defined in REGION
- and used outside the REGION. */
+/* 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
-rewrite_into_sese_closed_ssa (sese region, basic_block where,
- edge false_e, edge true_e)
+compute_cloog_iv_types (struct clast_stmt *stmt)
{
- unsigned i;
- basic_block bb;
- bitmap_iterator bi;
- bitmap names_to_rename = BITMAP_ALLOC (NULL);
- unsigned old_num_ssa_names = num_ssa_names;
- bitmap *use_blocks = XCNEWVEC (bitmap, old_num_ssa_names);
+ if (!stmt)
+ return;
- update_ssa (TODO_update_ssa);
+ if (CLAST_STMT_IS_A (stmt, stmt_root))
+ goto next;
- FOR_EACH_BB (bb)
- sese_find_uses_to_rename_bb (region, bb, use_blocks, names_to_rename);
+ 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;
+ }
- EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i, bi)
- sese_add_exit_phis_var (where, ssa_name (i), use_blocks[i],
- false_e, true_e);
+ if (CLAST_STMT_IS_A (stmt, stmt_for))
+ {
+ struct clast_stmt *s = ((struct clast_for *) stmt)->body;
+ compute_cloog_iv_types (s);
+ goto next;
+ }
- update_ssa (TODO_update_ssa);
+ 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;
+ }
- for (i = 0; i < old_num_ssa_names; i++)
- BITMAP_FREE (use_blocks[i]);
+ gcc_unreachable ();
- free (use_blocks);
- BITMAP_FREE (names_to_rename);
+ next:
+ compute_cloog_iv_types (stmt->next);
}
/* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
- the given SCOP. */
+ the given SCOP. Return true if code generation succeeded. */
-static void
+static bool
gloog (scop_p scop, struct clast_stmt *stmt)
{
edge new_scop_exit_edge = NULL;
loop_p context_loop;
ifsese if_region = NULL;
- if (!can_generate_code (stmt))
- {
- cloog_clast_free (stmt);
- return;
- }
-
+ recompute_all_dominators ();
+ graphite_verify ();
if_region = move_sese_in_condition (SCOP_REGION (scop));
- rewrite_into_sese_closed_ssa (SCOP_REGION (scop),
- if_region->region->exit->src,
- if_region->false_region->exit,
- if_region->true_region->exit);
+ 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;
- new_scop_exit_edge = translate_clast (scop, context_loop,
- stmt, if_region->true_region->entry,
+ 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 ();
- cleanup_tree_cfg ();
+ 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 ();
- free_loop_iv_stack (&ivstack);
- cloog_clast_free (stmt);
+ return true;
}
/* Returns the number of data references in SCOP. */
return get_first_matching_sign_row_index (domain, column, false);
}
-/* Get the lower bound of LOOP. */
+/* 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
-get_lower_bound (CloogMatrix *domain, int loop, Value lower_bound_result)
+swap_constraint_variables (CloogMatrix *domain,
+ int r, int x, int y)
{
- int lower_bound_row = get_lower_bound_row (domain, loop);
- value_assign (lower_bound_result,
- domain->p[lower_bound_row][const_column_index(domain)]);
+ value_swap (domain->p[r][x], domain->p[r][y]);
}
-/* Get the upper bound of LOOP. */
+/* Scale by X the coefficient C of constraint at row R in DOMAIN. */
static void
-get_upper_bound (CloogMatrix *domain, int loop, Value upper_bound_result)
+scale_constraint_variable (CloogMatrix *domain,
+ int r, int c, int x)
{
- int upper_bound_row = get_upper_bound_row (domain, loop);
- value_assign (upper_bound_result,
- domain->p[upper_bound_row][const_column_index(domain)]);
+ 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.
int col_loop_old = loop_depth + 2;
int col_loop_strip = col_loop_old - 1;
- Value old_lower_bound;
- Value old_upper_bound;
-
gcc_assert (loop_depth <= gbb_nb_loops (gb) - 1);
VEC_safe_insert (loop_p, heap, GBB_LOOPS (gb), loop_depth, NULL);
GBB_DOMAIN (gb) = new_domain;
- /*
- nrows = 4, ncols = 4
- eq i j c
- 1 1 0 0
- 1 -1 0 99
- 1 0 1 0
- 1 0 -1 99
- */
-
- /* Move domain. */
for (row = 0; row < domain->NbRows; row++)
for (col = 0; col < domain->NbColumns; col++)
if (col <= loop_depth)
else
value_assign (new_domain->p[row][col + 1], domain->p[row][col]);
-
- /*
- nrows = 6, ncols = 5
- outer inner
- eq i jj j c
- 1 1 0 0 0
- 1 -1 0 0 99
- 1 0 0 1 0
- 1 0 0 -1 99
- 0 0 0 0 0
- 0 0 0 0 0
- 0 0 0 0 0
- */
-
row = domain->NbRows;
- /* Add outer loop. */
- value_init (old_lower_bound);
- value_init (old_upper_bound);
- get_lower_bound (new_domain, col_loop_old, old_lower_bound);
- get_upper_bound (new_domain, col_loop_old, old_upper_bound);
-
- /* Set Lower Bound */
- value_set_si (new_domain->p[row][0], 1);
- value_set_si (new_domain->p[row][col_loop_strip], 1);
- value_assign (new_domain->p[row][const_column_index (new_domain)],
- old_lower_bound);
- value_clear (old_lower_bound);
+ /* 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++;
- /*
- 6 5
- eq i jj j c
- 1 1 0 0 0
- 1 -1 0 0 99
- 1 0 0 1 0 -
- 1 0 0 -1 99 | copy old lower bound
- 1 0 1 0 0 <-
- 0 0 0 0 0
- 0 0 0 0 0
- */
-
- {
- Value new_upper_bound;
- Value strip_size_value;
-
- value_init (new_upper_bound);
- value_init (strip_size_value);
- value_set_si (strip_size_value, (int) stride);
-
- value_pdivision (new_upper_bound, old_upper_bound, strip_size_value);
- value_add_int (new_upper_bound, new_upper_bound, 1);
-
- /* Set Upper Bound */
- value_set_si (new_domain->p[row][0], 1);
- value_set_si (new_domain->p[row][col_loop_strip], -1);
- value_assign (new_domain->p[row][const_column_index (new_domain)],
- new_upper_bound);
-
- value_clear (strip_size_value);
- value_clear (old_upper_bound);
- value_clear (new_upper_bound);
- row++;
- }
- /*
- 6 5
- eq i jj j c
- 1 1 0 0 0
- 1 -1 0 0 99
- 1 0 0 1 0
- 1 0 0 -1 99
- 1 0 1 0 0
- 1 0 -1 0 25 (divide old upper bound with stride)
- 0 0 0 0 0
- */
-
- {
- row = get_lower_bound_row (new_domain, col_loop_old);
- /* Add local variable to keep linear representation. */
- value_set_si (new_domain->p[row][0], 1);
- value_set_si (new_domain->p[row][const_column_index (new_domain)],0);
- value_set_si (new_domain->p[row][col_loop_old], 1);
- value_set_si (new_domain->p[row][col_loop_strip], -1*((int)stride));
- }
-
- /*
- 6 5
- eq i jj j c
- 1 1 0 0 0
- 1 -1 0 0 99
- 1 0 -1 1 0
- 1 0 0 -1 99
- 1 0 1 0 0
- 1 0 -1 0 25 (divide old upper bound with stride)
- 0 0 0 0 0
- */
-
- {
- row = new_domain->NbRows-1;
-
- value_set_si (new_domain->p[row][0], 1);
- value_set_si (new_domain->p[row][col_loop_old], -1);
- value_set_si (new_domain->p[row][col_loop_strip], stride);
- value_set_si (new_domain->p[row][const_column_index (new_domain)],
- stride-1);
- }
+ /* 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);
- /*
- 6 5
- eq i jj j c
- 1 1 0 0 0 i >= 0
- 1 -1 0 0 99 99 >= i
- 1 0 -4 1 0 j >= 4*jj
- 1 0 0 -1 99 99 >= j
- 1 0 1 0 0 jj >= 0
- 1 0 -1 0 25 25 >= jj
- 0 0 4 -1 3 jj+3 >= j
- */
+ /* 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);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "\nStrip Mining is not profitable for loop %d:",
- loop_index);
+ loop->num);
fprintf (dump_file, "number of iterations is too low.\n");
}
}
}
/* Determines when the interchange of LOOP_A and LOOP_B belonging to
- SCOP is legal. */
+ SCOP is legal. DEPTH is the number of loops around. */
static bool
-is_interchange_valid (scop_p scop, int loop_a, int loop_b)
+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);
- int depth = perfect_loop_nest_depth (nest);
lambda_trans_matrix trans;
gcc_assert (loop_a < loop_b);
for (i = start ; i < nb_loops; i++)
for (j = i + 1; j < nb_loops; j++)
- if (!is_interchange_valid (scop, i, j))
+ if (!is_interchange_valid (scop, i, j, nb_loops))
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file,
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;
}
bool transform_done = false;
/* TODO: - Calculate the stride size automatically. */
- int stride_size = 64;
+ 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);
j++;
/* Found perfect loop nest. */
- if (last_nb_loops - j > 0)
+ if (last_nb_loops - j >= 2)
transform_done |= graphite_trans_loop_block (bbs, last_nb_loops - j);
VEC_free (graphite_bb_p, heap, bbs);
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "\nLoop blocked.\n");
-
return transform_done;
}
continue;
for (j = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), j, loop); j++)
- if (!loop_in_scop_p (loop_outer (loop), scop))
+ if (!loop_in_sese_p (loop_outer (loop), SCOP_REGION (scop)))
{
sd_region open_scop;
open_scop.entry = loop->header;
{
int i;
scop_p scop;
+ bool transform_done = false;
if (number_of_loops () <= 1)
return;
if (!build_scop_loop_nests (scop))
continue;
- build_scop_canonical_schedules (scop);
build_bb_loops (scop);
- build_scop_conditions (scop);
+
+ if (!build_scop_conditions (scop))
+ continue;
+
find_scop_parameters (scop);
build_scop_context (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 (graphite_apply_transformations (scop))
- gloog (scop, find_transform (scop));
+ transform_done = gloog (scop, find_transform (scop));
#ifdef ENABLE_CHECKING
else
{
}
/* Cleanup. */
+ if (transform_done)
+ cleanup_tree_cfg ();
+
free_scops (current_scops);
cloog_finalize ();
free_original_copy_tables ();
OSDN Git Service
