Contributed by Diego Novillo <dnovillo@redhat.com>
This file is part of GCC.
-
+
GCC is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by the
Free Software Foundation; either version 2, or (at your option) any
later version.
-
+
GCC is distributed in the hope that it will be useful, but WITHOUT
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
for more details.
-
+
You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING. If not, write to the Free
Software Foundation, 59 Temple Place - Suite 330, Boston, MA
/* This object of this pass is to replace a non-addressable aggregate with a
set of independent variables. Most of the time, all of these variables
- will be scalars. But a secondary objective is to break up larger
+ will be scalars. But a secondary objective is to break up larger
aggregates into smaller aggregates. In the process we may find that some
bits of the larger aggregate can be deleted as unreferenced.
};
/* Random access to the child of a parent is performed by hashing.
- This prevents quadratic behaviour, and allows SRA to function
+ This prevents quadratic behavior, and allows SRA to function
reasonably on larger records. */
static htab_t sra_map;
if (bitmap_bit_p (sra_type_decomp_cache, cache+1))
return false;
- /* The type must have a definite non-zero size. */
+ /* The type must have a definite nonzero size. */
if (TYPE_SIZE (type) == NULL || integer_zerop (TYPE_SIZE (type)))
goto fail;
return true;
default:
- abort ();
+ gcc_unreachable ();
}
}
static hashval_t
sra_hash_tree (tree t)
{
+ hashval_t h;
+
switch (TREE_CODE (t))
{
case VAR_DECL:
case PARM_DECL:
case RESULT_DECL:
- case FIELD_DECL:
- return DECL_UID (t);
+ h = DECL_UID (t);
+ break;
+
case INTEGER_CST:
- return TREE_INT_CST_LOW (t) ^ TREE_INT_CST_HIGH (t);
+ h = TREE_INT_CST_LOW (t) ^ TREE_INT_CST_HIGH (t);
+ break;
+
+ case FIELD_DECL:
+ /* We can have types that are compatible, but have different member
+ lists, so we can't hash fields by ID. Use offsets instead. */
+ h = iterative_hash_expr (DECL_FIELD_OFFSET (t), 0);
+ h = iterative_hash_expr (DECL_FIELD_BIT_OFFSET (t), h);
+ break;
+
default:
- abort ();
+ gcc_unreachable ();
}
+
+ return h;
}
/* Hash function for type SRA_PAIR. */
/* Take into account everything back up the chain. Given that chain
lengths are rarely very long, this should be acceptable. If we
- truely identify this as a performance problem, it should work to
+ truly identify this as a performance problem, it should work to
hash the pointer value "e->parent". */
for (p = e->parent; p ; p = p->parent)
h = (h * 65521) ^ sra_hash_tree (p->element);
return h;
}
-
+
/* Equality function for type SRA_PAIR. */
static int
{
const struct sra_elt *a = x;
const struct sra_elt *b = y;
+ tree ae, be;
if (a->parent != b->parent)
return false;
- /* All the field/decl stuff is unique. */
- if (a->element == b->element)
- return true;
+ ae = a->element;
+ be = b->element;
- /* The only thing left is integer equality. */
- if (TREE_CODE (a->element) == INTEGER_CST
- && TREE_CODE (b->element) == INTEGER_CST)
- return tree_int_cst_equal (a->element, b->element);
- else
+ if (ae == be)
+ return true;
+ if (TREE_CODE (ae) != TREE_CODE (be))
return false;
+
+ switch (TREE_CODE (ae))
+ {
+ case VAR_DECL:
+ case PARM_DECL:
+ case RESULT_DECL:
+ /* These are all pointer unique. */
+ return false;
+
+ case INTEGER_CST:
+ /* Integers are not pointer unique, so compare their values. */
+ return tree_int_cst_equal (ae, be);
+
+ case FIELD_DECL:
+ /* Fields are unique within a record, but not between
+ compatible records. */
+ if (DECL_FIELD_CONTEXT (ae) == DECL_FIELD_CONTEXT (be))
+ return false;
+ return fields_compatible_p (ae, be);
+
+ default:
+ gcc_unreachable ();
+ }
}
/* Create or return the SRA_ELT structure for CHILD in PARENT. PARENT
return true;
}
-/* Create or return the SRA_ELT structure for EXPR if the expression
+/* Create or return the SRA_ELT structure for EXPR if the expression
refers to a scalarizable variable. */
static struct sra_elt *
block_stmt_iterator *bsi);
/* Invoked when ELT is initialized from a constant. VALUE may be NULL,
- in which case it should be treated as an empty CONSTRUCTOR. Return
- false if we found a case we couldn't handle. */
- bool (*init) (struct sra_elt *elt, tree value, block_stmt_iterator *bsi);
+ in which case it should be treated as an empty CONSTRUCTOR. */
+ void (*init) (struct sra_elt *elt, tree value, block_stmt_iterator *bsi);
/* Invoked when we have a copy between one scalarizable reference ELT
and one non-scalarizable reference OTHER. IS_OUTPUT is true if ELT
index reference inside a loop being overridden by several constant
index references during loop setup. It's possible that this could
be avoided by using dynamic usage counts based on BB trip counts
- (based on loop analysis or profiling), but that hardly seems worth
+ (based on loop analysis or profiling), but that hardly seems worth
the effort. */
/* ??? Hack. Figure out how to push this into the scan routines
without duplicating too much code. */
case BIT_FIELD_REF:
/* A bit field reference (access to *multiple* fields simultaneously)
- is not currently scalarized. Consider this an access to the
+ is not currently scalarized. Consider this an access to the
complete outer element, to which walk_tree will bring us next. */
goto use_all;
type other than the one we've scalarized. */
goto use_all;
+ case WITH_SIZE_EXPR:
+ /* This is a transparent wrapper. The entire inner expression really
+ is being used. */
+ goto use_all;
+
use_all:
expr_p = &TREE_OPERAND (inner, 0);
inner = expr = *expr_p;
default:
#ifdef ENABLE_CHECKING
/* Validate that we're not missing any references. */
- if (walk_tree (&inner, sra_find_candidate_decl, NULL, NULL))
- abort ();
+ gcc_assert (!walk_tree (&inner, sra_find_candidate_decl, NULL, NULL));
#endif
return;
}
{
/* If this is an assignment from a constant, or constructor, then
we have access to all of the elements individually. Invoke INIT. */
- if ((TREE_CODE (rhs) == COMPLEX_EXPR
- || TREE_CODE (rhs) == COMPLEX_CST
- || TREE_CODE (rhs) == CONSTRUCTOR)
- && fns->init (lhs_elt, rhs, bsi))
- ;
+ if (TREE_CODE (rhs) == COMPLEX_EXPR
+ || TREE_CODE (rhs) == COMPLEX_CST
+ || TREE_CODE (rhs) == CONSTRUCTOR)
+ fns->init (lhs_elt, rhs, bsi);
/* If this is an assignment from read-only memory, treat this as if
we'd been passed the constructor directly. Invoke INIT. */
else if (TREE_CODE (rhs) == VAR_DECL
&& TREE_STATIC (rhs)
&& TREE_READONLY (rhs)
- && targetm.binds_local_p (rhs)
- && DECL_INITIAL (rhs)
- && fns->init (lhs_elt, DECL_INITIAL (rhs), bsi))
- ;
+ && targetm.binds_local_p (rhs))
+ fns->init (lhs_elt, DECL_INITIAL (rhs), bsi);
/* If this is a copy from a non-scalarizable lvalue, invoke LDST.
The lvalue requirement prevents us from trying to directly scalarize
the result of a function call. Which would result in trying to call
the function multiple times, and other evil things. */
- else if (!lhs_elt->is_scalar && is_gimple_addr_expr_arg (rhs))
+ else if (!lhs_elt->is_scalar && is_gimple_addressable (rhs))
fns->ldst (lhs_elt, rhs, bsi, true);
-
+
/* Otherwise we're being used in some context that requires the
aggregate to be seen as a whole. Invoke USE. */
else
else
fns->use (rhs_elt, &TREE_OPERAND (expr, 1), bsi, false);
}
- else if (TREE_CODE (rhs) == CALL_EXPR)
- sra_walk_call_expr (rhs, bsi, fns);
else
- sra_walk_expr (&TREE_OPERAND (expr, 1), bsi, false, fns);
+ {
+ tree call = get_call_expr_in (rhs);
+ if (call)
+ sra_walk_call_expr (call, bsi, fns);
+ else
+ sra_walk_expr (&TREE_OPERAND (expr, 1), bsi, false, fns);
+ }
}
/* Entry point to the walk functions. Search the entire function,
any_set = true;
}
}
-
+
return any_set;
}
rhs_elt->n_copies += 1;
}
-static bool
+static void
scan_init (struct sra_elt *lhs_elt, tree rhs ATTRIBUTE_UNUSED,
block_stmt_iterator *bsi ATTRIBUTE_UNUSED)
{
lhs_elt->n_copies += 1;
- return true;
}
static void
break;
default:
- abort ();
+ gcc_unreachable ();
}
}
full_size = tree_low_cst (size_tree, 1);
- /* ??? What to do here. If there are two fields, and we've only
+ /* ??? What to do here. If there are two fields, and we've only
instantiated one, then instantiating the other is clearly a win.
If there are a large number of fields then the size of the copy
is much more of a factor. */
if (cleared_any)
{
- bitmap_operation (sra_candidates, sra_candidates, &done_head,
+ bitmap_operation (sra_candidates, sra_candidates, &done_head,
BITMAP_AND_COMPL);
- bitmap_operation (needs_copy_in, needs_copy_in, &done_head,
+ bitmap_operation (needs_copy_in, needs_copy_in, &done_head,
BITMAP_AND_COMPL);
}
bitmap_clear (&done_head);
static void
mark_all_v_defs (tree stmt)
{
- v_may_def_optype v_may_defs;
- v_must_def_optype v_must_defs;
- size_t i, n;
+ tree sym;
+ ssa_op_iter iter;
get_stmt_operands (stmt);
- v_may_defs = V_MAY_DEF_OPS (stmt_ann (stmt));
- n = NUM_V_MAY_DEFS (v_may_defs);
- for (i = 0; i < n; i++)
+ FOR_EACH_SSA_TREE_OPERAND (sym, stmt, iter, SSA_OP_VIRTUAL_DEFS)
{
- tree sym = V_MAY_DEF_RESULT (v_may_defs, i);
- if (TREE_CODE (sym) == SSA_NAME)
- sym = SSA_NAME_VAR (sym);
- bitmap_set_bit (vars_to_rename, var_ann (sym)->uid);
- }
-
- v_must_defs = V_MUST_DEF_OPS (stmt_ann (stmt));
- n = NUM_V_MUST_DEFS (v_must_defs);
- for (i = 0; i < n; i++)
- {
- tree sym = V_MUST_DEF_OP (v_must_defs, i);
if (TREE_CODE (sym) == SSA_NAME)
sym = SSA_NAME_VAR (sym);
bitmap_set_bit (vars_to_rename, var_ann (sym)->uid);
switch (TREE_CODE (TREE_TYPE (base)))
{
case RECORD_TYPE:
- return build (COMPONENT_REF, elt->type, base, elt->element, NULL);
+ {
+ tree field = elt->element;
+
+ /* Watch out for compatible records with differing field lists. */
+ if (DECL_FIELD_CONTEXT (field) != TYPE_MAIN_VARIANT (TREE_TYPE (base)))
+ field = find_compatible_field (TREE_TYPE (base), field);
+
+ return build (COMPONENT_REF, elt->type, base, field, NULL);
+ }
case ARRAY_TYPE:
return build (ARRAY_REF, elt->type, base, elt->element, NULL, NULL);
return build (IMAGPART_EXPR, elt->type, base);
default:
- abort ();
+ gcc_unreachable ();
}
}
for (dc = dst->children; dc ; dc = dc->sibling)
{
sc = lookup_element (src, dc->element, NULL, NO_INSERT);
- if (sc == NULL)
- abort ();
+ gcc_assert (sc);
generate_element_copy (dc, sc, list_p);
}
{
tree t;
- if (src->replacement == NULL)
- abort ();
+ gcc_assert (src->replacement);
t = build (MODIFY_EXPR, void_type_node, dst->replacement,
src->replacement);
{
struct sra_elt *c;
+ if (elt->visited)
+ {
+ elt->visited = false;
+ return;
+ }
+
for (c = elt->children; c ; c = c->sibling)
generate_element_zero (c, list_p);
- if (elt->visited)
- elt->visited = false;
- else if (elt->replacement)
+ if (elt->replacement)
{
tree t;
- if (elt->is_scalar)
- t = fold_convert (elt->type, integer_zero_node);
- else
- /* We generated a replacement for a non-scalar? */
- abort ();
+ gcc_assert (elt->is_scalar);
+ t = fold_convert (elt->type, integer_zero_node);
t = build (MODIFY_EXPR, void_type_node, elt->replacement, t);
append_to_statement_list (t, list_p);
}
}
+/* Find all variables within the gimplified statement that were not previously
+ visible to the function and add them to the referenced variables list. */
+
+static tree
+find_new_referenced_vars_1 (tree *tp, int *walk_subtrees,
+ void *data ATTRIBUTE_UNUSED)
+{
+ tree t = *tp;
+
+ if (TREE_CODE (t) == VAR_DECL && !var_ann (t))
+ add_referenced_tmp_var (t);
+
+ if (IS_TYPE_OR_DECL_P (t))
+ *walk_subtrees = 0;
+
+ return NULL;
+}
+
+static inline void
+find_new_referenced_vars (tree *stmt_p)
+{
+ walk_tree (stmt_p, find_new_referenced_vars_1, NULL, NULL);
+}
+
+/* Generate an assignment VAR = INIT, where INIT may need gimplification.
+ Add the result to *LIST_P. */
+
+static void
+generate_one_element_init (tree var, tree init, tree *list_p)
+{
+ tree stmt;
+
+ /* The replacement can be almost arbitrarily complex. Gimplify. */
+ stmt = build (MODIFY_EXPR, void_type_node, var, init);
+ gimplify_stmt (&stmt);
+
+ /* The replacement can expose previously unreferenced variables. */
+ if (TREE_CODE (stmt) == STATEMENT_LIST)
+ {
+ tree_stmt_iterator i;
+ for (i = tsi_start (stmt); !tsi_end_p (i); tsi_next (&i))
+ find_new_referenced_vars (tsi_stmt_ptr (i));
+ }
+ else
+ find_new_referenced_vars (&stmt);
+
+ append_to_statement_list (stmt, list_p);
+}
+
/* Generate a set of assignment statements in *LIST_P to set all instantiated
elements under ELT with the contents of the initializer INIT. In addition,
mark all assigned elements VISITED; this allows easy coordination with
{
if (elt->replacement)
{
- t = build (MODIFY_EXPR, void_type_node, elt->replacement, init);
- append_to_statement_list (t, list_p);
+ generate_one_element_init (elt->replacement, init, list_p);
elt->visited = true;
}
return result;
break;
default:
+ elt->visited = true;
result = false;
}
first_copy = false;
}
else
- bsi_insert_on_edge (e, lhd_unsave_expr_now (stmt));
+ bsi_insert_on_edge (e, unsave_expr_now (stmt));
}
}
}
generate_copy_inout (elt, is_output, generate_element_ref (elt), &list);
if (list == NULL)
return;
+ mark_all_v_defs (expr_first (list));
if (is_output)
- {
- mark_all_v_defs (expr_first (list));
- sra_insert_after (bsi, list);
- }
+ sra_insert_after (bsi, list);
else
sra_insert_before (bsi, list);
}
/* If we have two scalar operands, modify the existing statement. */
stmt = bsi_stmt (*bsi);
-#ifdef ENABLE_CHECKING
/* See the commentary in sra_walk_function concerning
RETURN_EXPR, and why we should never see one here. */
- if (TREE_CODE (stmt) != MODIFY_EXPR)
- abort ();
-#endif
+ gcc_assert (TREE_CODE (stmt) == MODIFY_EXPR);
TREE_OPERAND (stmt, 0) = lhs_elt->replacement;
TREE_OPERAND (stmt, 1) = rhs_elt->replacement;
else if (lhs_elt->use_block_copy || rhs_elt->use_block_copy)
{
/* If either side requires a block copy, then sync the RHS back
- to the original structure, leave the original assignment
+ to the original structure, leave the original assignment
statement (which will perform the block copy), then load the
LHS values out of its now-updated original structure. */
/* ??? Could perform a modified pair-wise element copy. That
list = NULL;
generate_element_copy (lhs_elt, rhs_elt, &list);
- if (list == NULL)
- abort ();
+ gcc_assert (list);
sra_replace (bsi, list);
}
}
/* Scalarize an INIT. To recap, this is an assignment to a scalarizable
reference from some form of constructor: CONSTRUCTOR, COMPLEX_CST or
COMPLEX_EXPR. If RHS is NULL, it should be treated as an empty
- CONSTRUCTOR. Return false if we didn't handle this case. */
+ CONSTRUCTOR. */
-static bool
+static void
scalarize_init (struct sra_elt *lhs_elt, tree rhs, block_stmt_iterator *bsi)
{
bool result = true;
/* Generate initialization statements for all members extant in the RHS. */
if (rhs)
- result = generate_element_init (lhs_elt, rhs, &list);
+ {
+ push_gimplify_context ();
+ result = generate_element_init (lhs_elt, rhs, &list);
+ pop_gimplify_context (NULL);
+ }
/* CONSTRUCTOR is defined such that any member not mentioned is assigned
a zero value. Initialize the rest of the instantiated elements. */
generate_element_zero (lhs_elt, &list);
- /* If we didn't generate anything or couldn't handle this case return.
- Say which it was. */
- if (!result || list == NULL)
- return result;
+ if (!result)
+ {
+ /* If we failed to convert the entire initializer, then we must
+ leave the structure assignment in place and must load values
+ from the structure into the slots for which we did not find
+ constants. The easiest way to do this is to generate a complete
+ copy-out, and then follow that with the constant assignments
+ that we were able to build. DCE will clean things up. */
+ tree list0 = NULL;
+ generate_copy_inout (lhs_elt, true, generate_element_ref (lhs_elt),
+ &list0);
+ append_to_statement_list (list, &list0);
+ list = list0;
+ }
- if (lhs_elt->use_block_copy)
+ if (lhs_elt->use_block_copy || !result)
{
/* Since LHS is not fully instantiated, we must leave the structure
assignment in place. Treating this case differently from a USE
exposes constants to later optimizations. */
- mark_all_v_defs (expr_first (list));
- sra_insert_after (bsi, list);
+ if (list)
+ {
+ mark_all_v_defs (expr_first (list));
+ sra_insert_after (bsi, list);
+ }
}
else
{
/* The LHS is fully instantiated. The list of initializations
replaces the original structure assignment. */
+ gcc_assert (list);
mark_all_v_defs (bsi_stmt (*bsi));
sra_replace (bsi, list);
}
-
- return true;
}
/* A subroutine of scalarize_ldst called via walk_tree. Set TREE_NO_TRAP
TREE_THIS_NOTRAP (t) = 1;
*walk_subtrees = 0;
}
- else if (DECL_P (t) || TYPE_P (t))
+ else if (IS_TYPE_OR_DECL_P (t))
*walk_subtrees = 0;
return NULL;
block_stmt_iterator *bsi, bool is_output)
{
/* Shouldn't have gotten called for a scalar. */
- if (elt->replacement)
- abort ();
+ gcc_assert (!elt->replacement);
if (elt->use_block_copy)
{
mark_all_v_defs (stmt);
generate_copy_inout (elt, is_output, other, &list);
- if (list == NULL)
- abort ();
+ gcc_assert (list);
/* Preserve EH semantics. */
if (stmt_ends_bb_p (stmt))
/* Replace the old statement with this new representative. */
bsi_replace (bsi, first, true);
-
+
if (!tsi_end_p (tsi))
{
/* If any reference would trap, then they all would. And more
size_t i;
EXECUTE_IF_SET_IN_BITMAP (needs_copy_in, 0, i,
- {
+ {
tree var = referenced_var (i);
struct sra_elt *elt = lookup_element (NULL, var, NULL, NO_INSERT);
generate_copy_inout (elt, true, var, &list);
return flag_tree_sra != 0;
}
-struct tree_opt_pass pass_sra =
+struct tree_opt_pass pass_sra =
{
"sra", /* name */
gate_sra, /* gate */
NULL, /* next */
0, /* static_pass_number */
TV_TREE_SRA, /* tv_id */
- PROP_cfg | PROP_ssa, /* properties_required */
+ PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
TODO_dump_func | TODO_rename_vars
- | TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */
+ | TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */
+ 0 /* letter */
};