static VEC (scop_p, heap) *current_scops;
+/* Converts a GMP constant V to a tree and returns it. */
+
+static tree
+gmp_cst_to_tree (Value v)
+{
+ return build_int_cst (integer_type_node, value_get_si (v));
+}
+
/* Debug the list of old induction variables for this SCOP. */
void
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 (loop_iv_stack stack, tree iv, const char *name)
+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;
- VEC_safe_push (name_tree, heap, *stack, named_iv);
+
+ 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 an element out of STACK. */
+/* Pops and frees an element out of STACK. */
static void
loop_iv_stack_pop (loop_iv_stack stack)
{
- VEC_pop (name_tree, *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)
{
- name_tree named_iv = VEC_index (name_tree, *stack, index);
+ iv_stack_entry_p entry = VEC_index (iv_stack_entry_p, *stack, index);
+
+ tree result = NULL;
- return named_iv->t;
+ if (entry->kind != iv_stack_entry_const)
+ result = entry->data.iv->t;
+
+ return result;
}
/* Get the IV from its NAME in STACK. */
loop_iv_stack_get_iv_from_name (loop_iv_stack stack, const char* name)
{
int i;
- name_tree iv;
+ iv_stack_entry_p entry;
- for (i = 0; VEC_iterate (name_tree, *stack, i, iv); i++)
- if (!strcmp (name, iv->name))
- return iv->t;
+ 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
-loop_iv_stack_debug (loop_iv_stack stack)
+debug_loop_iv_stack (loop_iv_stack stack)
{
int i;
- name_tree iv;
+ iv_stack_entry_p entry;
bool first = true;
fprintf (stderr, "(");
- for (i = 0; VEC_iterate (name_tree, *stack, i, iv); i++)
+ for (i = 0; VEC_iterate (iv_stack_entry_p, *stack, i, entry); i++)
{
if (first)
first = false;
else
fprintf (stderr, " ");
- fprintf (stderr, "%s:", iv->name);
- print_generic_expr (stderr, iv->t, 0);
+
+ 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);
+}
+
+/* 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;
+ for (t = user_stmt->substitutions; t; t = t->next)
+ {
+ struct clast_term *term = (struct clast_term*)
+ ((struct clast_assignment *)t)->RHS;
+
+ /* FIXME: What should be done with expr_bin, expr_red? */
+ if (((struct clast_assignment *)t)->RHS->type == expr_term
+ && !term->var)
+ {
+ tree value = gmp_cst_to_tree (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++;
+ }
+}
+
/* In SCOP, get the induction variable from NAME. OLD is the original
loop that contained the definition of NAME. */
|| evolution_function_is_affine_multivariate_p (scev, n));
}
+/* Return false if the tree_code of the operand OP or any of its operands
+ is component_ref. */
+
+static bool
+exclude_component_ref (tree op)
+{
+ int i;
+ int len;
+
+ if (op)
+ {
+ if (TREE_CODE (op) == COMPONENT_REF)
+ return false;
+ else
+ {
+ len = TREE_OPERAND_LENGTH (op);
+ for (i = 0; i < len; ++i)
+ {
+ if (!exclude_component_ref (TREE_OPERAND (op, i)))
+ return false;
+ }
+ }
+ }
+
+ return true;
+}
+
/* Return true if the operand OP is simple. */
static bool
&& !stmt_simple_memref_p (loop, stmt, op)))
return false;
- return true;
+ return exclude_component_ref (op);
}
/* Return true only when STMT is simple enough for being handled by
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);
BITMAP_FREE (SCOP_BBS_B (scop));
BITMAP_FREE (SCOP_LOOPS (scop));
VEC_free (loop_p, heap, SCOP_LOOP_NEST (scop));
+
+ for (i = 0; VEC_iterate (name_tree, SCOP_OLDIVS (scop), i, iv); i++)
+ free (iv);
VEC_free (name_tree, heap, SCOP_OLDIVS (scop));
for (i = 0; VEC_iterate (name_tree, SCOP_PARAMS (scop), i, p); i++)
int i;
build_scops_1 (bb, &tmp_scops, loop);
- /* XXX: Use 'e->src' ot better 'bb'? */
+
+ /* Start at all bbs dominated by a loop exit that only exists in this
+ loop. */
for (i = 0; VEC_iterate (edge, exits, i, e); i++)
- if (dominated_by_p (CDI_DOMINATORS, e->dest, e->src)
- && e->src->loop_father == loop)
- build_scops_1 (e->dest, &tmp_scops, e->dest->loop_father);
+ if (e->src->loop_father == loop)
+ {
+ VEC (basic_block, heap) *dominated;
+ basic_block b;
+ int j;
+ dominated = get_dominated_by (CDI_DOMINATORS, e->src);
+ for (j = 0; VEC_iterate (basic_block, dominated, j, b); j++)
+ /* Loop exit. */
+ if (loop_depth (find_common_loop (loop, b->loop_father))
+ < loop_depth (loop))
+ {
+ /* Pass loop_outer to recognize b as loop header in
+ build_scops_1. */
+ if (b->loop_father->header == b)
+ build_scops_1 (b, &tmp_scops, loop_outer (b->loop_father));
+ else
+ build_scops_1 (b, &tmp_scops, b->loop_father);
+ }
+ }
result.next = NULL;
result.last = NULL;
for (i = 0; VEC_iterate (basic_block, dominated, i, dom_bb); i++)
{
/* Ignore loop exits: they will be handled after the loop body. */
- if (is_loop_exit (loop, dom_bb))
+ if (loop_depth (find_common_loop (loop, dom_bb->loop_father))
+ < loop_depth (loop))
{
result.exits = true;
continue;
int i;
sd_region *s;
-
for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
create_single_entry_edge (s);
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. */
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;
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. */
+ 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]);
}
-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);
- }
+ 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);
}
}
}
-/* Converts a GMP constant value to a tree and returns it. */
-
-static tree
-gmp_cst_to_tree (Value v)
-{
- return build_int_cst (integer_type_node, value_get_si (v));
-}
-
/* 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.
&iv_before, outer ? outer
: entry_edge->src->loop_father);
- loop_iv_stack_push (ivstack, iv_before, stmt->iterator);
+ loop_iv_stack_push_iv (ivstack, iv_before, stmt->iterator);
return loop;
}
tree op1, graphite_bb_p gbb, scop_p scop,
loop_p old_loop_father, loop_iv_stack ivstack)
{
- if (TREE_CODE_CLASS (code) == tcc_constant
- && code == INTEGER_CST)
- return op0;
+ if ((TREE_CODE_CLASS (code) == tcc_constant
+ && code == INTEGER_CST)
+ || TREE_CODE_CLASS (code) == tcc_reference)
+ return op0;
if (TREE_CODE_CLASS (code) == tcc_unary)
{
mark_virtual_ops_in_bb (bb);
next_e = make_edge (bb,
context_loop ? context_loop->latch : EXIT_BLOCK_PTR,
- EDGE_FALLTHRU);;
+ EDGE_FALLTHRU);
+ loop_iv_stack_patch_for_consts (ivstack,
+ (struct clast_user_stmt *) stmt);
graphite_rename_ivs (gbb, scop, old_loop_father, ivstack);
+ loop_iv_stack_remove_constants (ivstack);
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
/* 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,
static struct clast_stmt *
find_transform (scop_p scop)
{
- CloogProgram *prog;
struct clast_stmt *stmt;
CloogOptions *options = set_cloog_options ();
fprintf (dump_file, "]\n");
}
- prog = cloog_program_generate (SCOP_PROG (scop), options);
- stmt = cloog_clast_create (prog, options);
+ 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, prog);
+ cloog_program_dump_cloog (dump_file, SCOP_PROG (scop));
fprintf (dump_file, "]\n");
}
gsi = gsi_for_stmt (phi);
remove_phi_node (&gsi, false);
}
+
+ VEC_free (gimple, heap, virtual_phis);
}
/* Mark the original loops of SCOP for removal, replacing their header
{
edge new_scop_exit_edge = NULL;
basic_block scop_exit = SCOP_EXIT (scop);
- VEC (tree, heap)* phi_args =
+ VEC (tree, heap) *phi_args =
collect_scop_exit_phi_args (SESE_EXIT (SCOP_REGION (scop)));
- VEC (name_tree, heap) *ivstack = VEC_alloc (name_tree, heap, 10);
+ VEC (iv_stack_entry_p, heap) *ivstack =
+ VEC_alloc (iv_stack_entry_p, heap, 10);
edge construction_edge = SESE_ENTRY (SCOP_REGION (scop));
basic_block old_scop_exit_idom = get_immediate_dominator (CDI_DOMINATORS,
scop_exit);
return;
}
+ redirect_edge_succ_nodup (construction_edge, EXIT_BLOCK_PTR);
new_scop_exit_edge = translate_clast (scop,
construction_edge->src->loop_father,
stmt, construction_edge, &ivstack);
+ free_loop_iv_stack (&ivstack);
redirect_edge_succ (new_scop_exit_edge, scop_exit);
+
if (!old_scop_exit_idom
|| !dominated_by_p (CDI_DOMINATORS, SCOP_ENTRY (scop),
old_scop_exit_idom)
if (new_scop_exit_edge->dest == EXIT_BLOCK_PTR)
new_scop_exit_edge->flags = 0;
- find_unreachable_blocks ();
delete_unreachable_blocks ();
patch_phis_for_virtual_defs ();
patch_scop_exit_phi_args (new_scop_exit_edge, phi_args);
+ VEC_free (tree, heap, phi_args);
mark_old_loops (scop);
remove_dead_loops ();
rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
get_lower_bound (CloogMatrix *domain, int loop, Value lower_bound_result)
{
int lower_bound_row = get_lower_bound_row (domain, loop);
- value_init (lower_bound_result);
value_assign (lower_bound_result,
domain->p[lower_bound_row][const_column_index(domain)]);
}
get_upper_bound (CloogMatrix *domain, int loop, Value upper_bound_result)
{
int upper_bound_row = get_upper_bound_row (domain, loop);
- value_init (upper_bound_result);
value_assign (upper_bound_result,
domain->p[upper_bound_row][const_column_index(domain)]);
}
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);
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]);
- }
+ value_assign (new_domain->p[row][col], domain->p[row][col]);
else
- {
- value_assign (new_domain->p[row][col + 1], domain->p[row][col]);
- }
+ value_assign (new_domain->p[row][col + 1], domain->p[row][col]);
/*
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);
value_set_si (new_domain->p[row][col_loop_strip], 1);
value_assign (new_domain->p[row][const_column_index (new_domain)],
old_lower_bound);
+ value_clear (old_lower_bound);
row++;
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_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][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++;
}
/*
/* TODO: - Calculate the stride size automatically. */
int stride_size = 64;
+ /* It makes no sense to block a single loop. */
+ for (i = 0; VEC_iterate (graphite_bb_p, bbs, i, gb); i++)
+ if (gbb_nb_loops (gb) < 2)
+ return false;
+
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. */
+/* Loop block all basic blocks of SCOP. Return false when the
+ transform is not performed. */
static bool
graphite_trans_scop_block (scop_p scop)
lambda_vector last_schedule = lambda_vector_new (max_schedule);
if (VEC_length (graphite_bb_p, SCOP_BBS (scop)) == 0)
- return transform_done;
+ return false;
/* Get the data of the first bb. */
- gb = VEC_index (graphite_bb_p, SCOP_BBS (scop), 0);
+ 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);
if (flag_loop_block)
transform_done = graphite_trans_scop_block (scop);
-#if 0 && ENABLE_CHECKING
- /* When the compiler is configured with ENABLE_CHECKING, always
- generate code, even if we did not apply any transformation. This
- provides better code coverage of the backend code generator.
-
- This also allows to check the performance for an identity
- transform: GIMPLE -> GRAPHITE -> GIMPLE; and the output of CLooG
- is never an identity: if CLooG optimizations are not disabled,
- the CLooG output is always optimized in control flow. */
- transform_done = true;
-#endif
+ /* 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;
}
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
OSDN Git Service
