This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH]: Structure aliasing, part 1
- From: Daniel Berlin <dberlin at dberlin dot org>
- To: gcc-patches at gcc dot gnu dot org
- Date: Wed, 09 Mar 2005 10:07:45 -0500
- Subject: [PATCH]: Structure aliasing, part 1
This patch is the first part of the structure aliasing changes.
This lets the compiler perform tree-level optimizations on pieces of
structures without SRA.
SRA can't handle things that need to live in memory, as well as
optimizing the actual loads and stores from the structure into the
seperate variables.
structopt-3.c is a good example of something SRA can't do that we now
can.
The patch works by introducing a new type of memory tag, a "structure
field tag", that is used to represent a field of a structure as if it
were a variable.
These structure field tags are kept as "subvariables" of a regular
structure variable.
If a variable has subvariable we use the approriate subvariables in
place of the regular variable, for purposes of virtual operands.
In the vast majority of cases, we know something about a component
access that means we don't use all the subvariables, which is an
improvement over what we used to have, where the entire structure was
killed.
Of course, when we can't tell anything about the access, we must act as
if it touched all the subvariables.
We also now create must-defs for clear accesses to structure fields,
using the subvariables.
-fdump-tree-svars will give you the mapping between that SFT's that
appear in subvariables, and the actual fields they represent.
Alternative approaches were tried during the development phase, such as
introducing real partial defs and uses, but this turned out to be very
difficult algorithmically, and more expensive memory wise.
The current implementation does do pruning of what structure fields we
create.
During overlap discovery, we find a range that conservatively describes
the used portion of a structure inside a function, and only create SFT's
for fields in that range.
This helps immensely with things that use large structures, but are just
using one field. An oft-occuring example of this is the targetm and
lang_hooks structure. The majority of things only call one member of
those structures, and this pruning causes us to only create one
structure field tag for *that* piece of the structure.
Obviously, if you do something to a structure we can't tell the used
portion of, or take it's address, we have to mark the used range as the
entire variable.
The current implementation *not* handle structures with arrays inside
them.
One could handle constant sized arrays with a little work, but more
pruning would probably be necessary to avoid virtual operand explosion.
As for timings, the optimization pays for itself.
Timings of cc1-i-files before:
448 seconds
447 seconds
448 seconds
Timings of cc1-i-files after:
434 seconds
435 seconds
433 seconds
This is about what I expected. The backend catches some of the things
this optimization catches, the main purpose here has been to expose them
to the tree level optimizers, which are presumably better and can do
more. SRA catches most of the non-global cases, though we can now
eliminate loads and stores to structure accesses that we couldn't
before.
SPEC (which i haven't run in a month, but haven't made significant
algorithmic changes since then) shows 1-2 percent better on some of
tests, and no degradation. Some of these tests are fortran tests with
common variables, which are normally accessed through structures, which
we probably know more about now.
As i noted to Mark in my risks section, there is probably code out there
with very large structures and structure access patterns that will
defeat the pruning heuristics. In fact, it is probable someone will
report such a bug as a time regression. Once i see such code, i can do
some more pruning in what structures we create SFT's for, and what SFT's
we create, in order to make the compiler not slow down.
I tried profiling some likely suspects (fortran code with lots of common
variables, C++ code), but no luck. The profiles were relatively
unchanged.
Bootstrapped and regtested on i686-pc-linux-gnu, no regressions.
Bootstrapped and regtested on ppc-darwin, no regressions.
(Which was not an easy task this week :P)
Okay for mainline?
2005-03-09 Daniel Berlin <dberlin@dberlin.org>
* tree-flow-inline.h (ref_contains_array_ref): New function.
(lookup_subvars_for_var): Ditto.
(get_subvars_for_var): Ditto.
(var_can_have_subvars): Ditto.
(okay_component_ref_for_subvars): Ditto.
* tree-flow.h (mem_tag_kind): Add STRUCT_FIELD.
(struct subvar): New type.
* tree-optimize.c (init_tree_optimization_passes): Call
pass_create_structure_vars.
* tree-ssa-alias.c: Include vec.h.
(init_alias_info): Don't auto-clear call clobbered on struct-field
tags.
(compute_flow_insensitive_aliasing): Handle subvars.
(group_aliases): Handle STRUCT_FIELD aliases.
(setup_pointers_and_addressables): Ditto.
Don't mark variables non-addressable if they still have
addressable subvars.
Also mark subvars addressable when the real variable is marked
addressable.
(add_pointed_to_var): Try to prune the pointed-to set by only
pointing to subvars when possible.
Otherwise, make sure we set addresses_needed and pt_vars to
properly include subvars.
(bitpos_of_field): New function.
(push_fields_onto_fieldstack): Ditto.
(get_or_create_used_part_for): Ditto.
(create_overlap_variables_for): Ditto.
(find_used_portions): Ditto.
(create_structure_vars): Ditto.
(pass_create_structure_vars): New structure.
* tree-ssa-operands.c (finalize_ssa_v_must_defs): Remove assert.
(get_expr_operands): Handle subvars. Also try to turn
COMPONENT_REF accesses into must-defs now that we can accurately
portray it.
(note_addressable): Try to only mark as addressable those subvars
we know a COMPONENT_REF touches.
* tree-vect-analyze.c (vect_object_analysis): Add new parameter.
Handle subvar storing.
(vect_address_analysis): Update caller of vect_object_analysis.
* tree-vect-transform.c (vect_create_data_ref_ptr): Copy subvars.
* tree-vectorizer.h (struct _stmt_vec_info): Add subvars member.
(STMT_VINFO_SUBVARS): New macro.
* doc/invoke.texi: Document fdump-tree-svars.
* doc/tree-ssa.texi: Document structural alias analysis.
Index: tree-flow-inline.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow-inline.h,v
retrieving revision 2.31
diff -u -p -r2.31 tree-flow-inline.h
--- tree-flow-inline.h 2 Feb 2005 20:56:18 -0000 2.31
+++ tree-flow-inline.h 9 Mar 2005 14:21:47 -0000
@@ -878,4 +878,98 @@ op_iter_init_mustdef (ssa_op_iter *ptr,
op_iter_init (ptr, stmt, SSA_OP_VMUSTDEFKILL);
op_iter_next_mustdef (kill, def, ptr);
}
+
+/* Return true if REF, a COMPONENT_REF, has an ARRAY_REF somewhere in it. */
+
+static bool
+ref_contains_array_ref (tree ref)
+{
+ while (handled_component_p (ref))
+ {
+ if (TREE_CODE (ref) == ARRAY_REF)
+ return true;
+ ref = TREE_OPERAND (ref, 0);
+ }
+ return false;
+}
+
+/* Given a variable VAR, lookup and return a pointer to the list of
+ subvariables for it. */
+
+static inline subvar_t *
+lookup_subvars_for_var (tree var)
+{
+ var_ann_t ann = var_ann (var);
+ gcc_assert (ann);
+ return &ann->subvars;
+}
+
+/* Given a variable VAR, return a linked list of subvariables for VAR, or
+ NULL, if there are no subvariables. */
+
+static inline subvar_t
+get_subvars_for_var (tree var)
+{
+ subvar_t subvars;
+
+ gcc_assert (SSA_VAR_P (var));
+
+ subvars = *(lookup_subvars_for_var (var));
+ return subvars;
+}
+
+/* Return true if V is a tree that we can have subvars for.
+ Normally, this is any aggregate type, however, due to implementation
+ limitations ATM, we exclude array types as well. */
+static inline bool
+var_can_have_subvars (tree v)
+{
+ return (AGGREGATE_TYPE_P (TREE_TYPE (v)) &&
+ TREE_CODE (TREE_TYPE (v)) != ARRAY_TYPE);
+}
+
+
+/* Return the underlying variable for REF, if REF is something we can create
+ subvars for. If the return value is a SSA_VAR_P, POFFSET will be the
+ offset, in bits, of REF inside the return value. If the return value is a
+ SSA_VAR_P, PSIZE will be the size, in bits, of REF inside the return
+ value. */
+
+static inline tree
+okay_component_ref_for_subvars (tree ref, HOST_WIDE_INT *poffset,
+ HOST_WIDE_INT *psize)
+{
+ tree result = NULL;
+ HOST_WIDE_INT bitsize;
+ HOST_WIDE_INT bitpos;
+ tree offset;
+ enum machine_mode mode;
+ int unsignedp;
+ int volatilep;
+
+ gcc_assert (!SSA_VAR_P (ref));
+ *poffset = 0;
+ *psize = (unsigned int) -1;
+
+ if (ref_contains_array_ref (ref))
+ return result;
+ ref = get_inner_reference (ref, &bitsize, &bitpos, &offset, &mode,
+ &unsignedp, &volatilep, false);
+ if (TREE_CODE (ref) == INDIRECT_REF)
+ return result;
+ else if (offset == NULL && bitsize != -1)
+ {
+ *poffset = bitpos;
+ *psize = bitsize;
+ if (get_subvars_for_var (ref) != NULL)
+ return ref;
+ }
+ else if (SSA_VAR_P (ref))
+ {
+ if (get_subvars_for_var (ref) != NULL)
+ return ref;
+ }
+ return NULL_TREE;
+}
+
#endif /* _TREE_FLOW_INLINE_H */
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow.h,v
retrieving revision 2.84
diff -u -p -r2.84 tree-flow.h
--- tree-flow.h 8 Mar 2005 16:22:55 -0000 2.84
+++ tree-flow.h 9 Mar 2005 14:21:48 -0000
@@ -138,7 +138,26 @@ enum mem_tag_kind {
TYPE_TAG,
/* This variable is a name memory tag (NMT). */
- NAME_TAG
+ NAME_TAG,
+
+ /* This variable represents a structure field. */
+ STRUCT_FIELD
+};
+struct subvar;
+typedef struct subvar *subvar_t;
+
+/* This structure represents a fake sub-variable for a structure field. */
+
+struct subvar GTY(())
+{
+ /* Fake variable name */
+ tree var;
+ /* Offset inside structure. */
+ HOST_WIDE_INT offset;
+ /* Size of field. */
+ HOST_WIDE_INT size;
+ /* Next subvar for this structure. */
+ subvar_t next;
};
struct var_ann_d GTY(())
@@ -211,6 +230,8 @@ struct var_ann_d GTY(())
live at the same time and this can happen for each call to the
dominator optimizer. */
tree current_def;
+
+ subvar_t subvars;
};
@@ -555,6 +576,9 @@ extern tree make_rename_temp (tree, cons
extern void record_vars (tree);
extern bool block_may_fallthru (tree block);
+typedef tree tree_on_heap;
+DEF_VEC_MALLOC_P (tree_on_heap);
+
/* In tree-ssa-alias.c */
extern void dump_may_aliases_for (FILE *, tree);
extern void debug_may_aliases_for (tree);
@@ -566,13 +590,14 @@ extern void dump_points_to_info_for (FIL
extern void debug_points_to_info_for (tree);
extern bool may_be_aliased (tree);
extern struct ptr_info_def *get_ptr_info (tree);
-
+static inline subvar_t get_subvars_for_var (tree);
+static inline tree okay_component_ref_for_subvars (tree, HOST_WIDE_INT *,
+ HOST_WIDE_INT *);
+static inline bool var_can_have_subvars (tree);
/* Call-back function for walk_use_def_chains(). At each reaching
definition, a function with this prototype is called. */
typedef bool (*walk_use_def_chains_fn) (tree, tree, void *);
-typedef tree tree_on_heap;
-DEF_VEC_MALLOC_P (tree_on_heap);
/* In tree-ssa.c */
extern void init_tree_ssa (void);
Index: tree-optimize.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-optimize.c,v
retrieving revision 2.76
diff -u -p -r2.76 tree-optimize.c
--- tree-optimize.c 2 Mar 2005 11:09:48 -0000 2.76
+++ tree-optimize.c 9 Mar 2005 14:24:49 -0000
@@ -347,6 +347,7 @@ init_tree_optimization_passes (void)
p = &pass_all_optimizations.sub;
NEXT_PASS (pass_referenced_vars);
+ NEXT_PASS (pass_create_structure_vars);
NEXT_PASS (pass_build_ssa);
NEXT_PASS (pass_may_alias);
NEXT_PASS (pass_rename_ssa_copies);
Index: tree-pass.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-pass.h,v
retrieving revision 2.28
diff -u -p -r2.28 tree-pass.h
--- tree-pass.h 1 Mar 2005 17:59:05 -0000 2.28
+++ tree-pass.h 9 Mar 2005 14:21:48 -0000
@@ -167,5 +167,6 @@ extern struct tree_opt_pass pass_rest_of
extern struct tree_opt_pass pass_sink_code;
extern struct tree_opt_pass pass_fre;
extern struct tree_opt_pass pass_linear_transform;
+extern struct tree_opt_pass pass_create_structure_vars;
#endif /* GCC_TREE_PASS_H */
Index: tree-ssa-alias.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-alias.c,v
retrieving revision 2.72
diff -u -p -r2.72 tree-ssa-alias.c
--- tree-ssa-alias.c 26 Feb 2005 16:15:00 -0000 2.72
+++ tree-ssa-alias.c 9 Mar 2005 14:21:49 -0000
@@ -42,6 +42,7 @@ Boston, MA 02111-1307, USA. */
#include "tree-pass.h"
#include "convert.h"
#include "params.h"
+#include "vec.h"
/* 'true' after aliases have been computed (see compute_may_aliases). */
bool aliases_computed_p;
@@ -524,8 +525,15 @@ init_alias_info (void)
variables, clear the call-clobbered flag. Variables that
are intrinsically call-clobbered (globals, local statics,
etc) will not be marked by the aliasing code, so we can't
- remove them from CALL_CLOBBERED_VARS. */
- if (ann->mem_tag_kind != NOT_A_TAG || !is_global_var (var))
+ remove them from CALL_CLOBBERED_VARS.
+
+ NB: STRUCT_FIELDS are still call clobbered if they are for
+ a global variable, so we *don't* clear their call clobberedness
+ just because they are tags, though we will clear it if they
+ aren't for global variables. */
+ if (ann->mem_tag_kind == NAME_TAG
+ || ann->mem_tag_kind == TYPE_TAG
+ || !is_global_var (var))
clear_call_clobbered (var);
}
@@ -982,13 +990,28 @@ compute_flow_insensitive_aliasing (struc
if (may_alias_p (p_map->var, p_map->set, var, v_map->set))
{
+ subvar_t svars;
size_t num_tag_refs, num_var_refs;
num_tag_refs = VARRAY_UINT (ai->num_references, tag_ann->uid);
num_var_refs = VARRAY_UINT (ai->num_references, v_ann->uid);
/* Add VAR to TAG's may-aliases set. */
- add_may_alias (tag, var);
+
+ /* If this is an aggregate, we may have subvariables for it
+ that need to be pointed to. */
+ if (var_can_have_subvars (var)
+ && (svars = get_subvars_for_var (var)))
+ {
+ subvar_t sv;
+
+ for (sv = svars; sv; sv = sv->next)
+ add_may_alias (tag, sv->var);
+ }
+ else
+ {
+ add_may_alias (tag, var);
+ }
/* Update the total number of virtual operands due to
aliasing. Since we are adding one more alias to TAG's
@@ -1293,7 +1316,9 @@ group_aliases (struct alias_info *ai)
tree alias = VARRAY_TREE (aliases, j);
var_ann_t ann = var_ann (alias);
- if (ann->mem_tag_kind == NOT_A_TAG && ann->may_aliases)
+ if ((ann->mem_tag_kind == NOT_A_TAG
+ || ann->mem_tag_kind == STRUCT_FIELD)
+ && ann->may_aliases)
{
tree new_alias;
@@ -1378,13 +1403,19 @@ setup_pointers_and_addressables (struct
{
tree var = referenced_var (i);
var_ann_t v_ann = var_ann (var);
+ subvar_t svars;
/* Name memory tags already have flow-sensitive aliasing
information, so they need not be processed by
compute_flow_insensitive_aliasing. Similarly, type memory
tags are already accounted for when we process their
- associated pointer. */
- if (v_ann->mem_tag_kind != NOT_A_TAG)
+ associated pointer.
+
+ Structure fields, on the other hand, have to have some of this
+ information processed for them, but it's pointless to mark them
+ non-addressable (since they are fake variables anyway). */
+ if (v_ann->mem_tag_kind != NOT_A_TAG
+ && v_ann->mem_tag_kind != STRUCT_FIELD)
continue;
/* Remove the ADDRESSABLE flag from every addressable variable whose
@@ -1392,20 +1423,36 @@ setup_pointers_and_addressables (struct
of ADDR_EXPR constants into INDIRECT_REF expressions and the
removal of dead pointer assignments done by the early scalar
cleanup passes. */
- if (TREE_ADDRESSABLE (var))
+ if (TREE_ADDRESSABLE (var) && v_ann->mem_tag_kind != STRUCT_FIELD)
{
if (!bitmap_bit_p (ai->addresses_needed, v_ann->uid)
&& TREE_CODE (var) != RESULT_DECL
&& !is_global_var (var))
{
+ bool okay_to_mark = true;
+ /* Since VAR is now a regular GIMPLE register, we will need
+ to rename VAR into SSA afterwards. */
+ bitmap_set_bit (vars_to_rename, v_ann->uid);
+
+ if (var_can_have_subvars (var)
+ && (svars = get_subvars_for_var (var)))
+ {
+ subvar_t sv;
+
+ for (sv = svars; sv; sv = sv->next)
+ {
+ var_ann_t svann = var_ann (sv->var);
+ if (bitmap_bit_p (ai->addresses_needed, svann->uid))
+ okay_to_mark = false;
+ bitmap_set_bit (vars_to_rename, svann->uid);
+ }
+ }
/* The address of VAR is not needed, remove the
addressable bit, so that it can be optimized as a
regular variable. */
- mark_non_addressable (var);
+ if (okay_to_mark)
+ mark_non_addressable (var);
- /* Since VAR is now a regular GIMPLE register, we will need
- to rename VAR into SSA afterwards. */
- bitmap_set_bit (vars_to_rename, v_ann->uid);
}
else
{
@@ -1414,6 +1461,14 @@ setup_pointers_and_addressables (struct
clobber memory. In those cases, we need to clobber
all call-clobbered variables and all addressables. */
bitmap_set_bit (addressable_vars, v_ann->uid);
+ if (var_can_have_subvars (var)
+ && (svars = get_subvars_for_var (var)))
+ {
+ subvar_t sv;
+ for (sv = svars; sv; sv = sv->next)
+ bitmap_set_bit (addressable_vars, var_ann (sv->var)->uid);
+ }
+
}
}
@@ -1579,7 +1634,17 @@ maybe_create_global_var (struct alias_in
.GLOBAL_VAR has been created, make it an alias for all
call-clobbered variables. */
if (global_var && var != global_var)
- add_may_alias (var, global_var);
+ {
+ subvar_t svars;
+ add_may_alias (var, global_var);
+ if (var_can_have_subvars (var)
+ && (svars = get_subvars_for_var (var)))
+ {
+ subvar_t sv;
+ for (sv = svars; sv; sv = sv->next)
+ bitmap_set_bit (vars_to_rename, var_ann (sv->var)->uid);
+ }
+ }
bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
}
@@ -1895,23 +1959,73 @@ static void
add_pointed_to_var (struct alias_info *ai, tree ptr, tree value)
{
struct ptr_info_def *pi = get_ptr_info (ptr);
- tree pt_var;
+ tree pt_var = NULL_TREE;
+ HOST_WIDE_INT offset, size;
+ tree addrop;
size_t uid;
+ tree ref;
+ subvar_t svars;
gcc_assert (TREE_CODE (value) == ADDR_EXPR);
- pt_var = TREE_OPERAND (value, 0);
- if (REFERENCE_CLASS_P (pt_var))
- pt_var = get_base_address (pt_var);
+ addrop = TREE_OPERAND (value, 0);
+ if (REFERENCE_CLASS_P (addrop))
+ pt_var = get_base_address (addrop);
+ else
+ pt_var = addrop;
+
+ /* If this is a component_ref, see if we can get a smaller number of
+ variables to take the address of. */
+ if (TREE_CODE (addrop) == COMPONENT_REF
+ && (ref = okay_component_ref_for_subvars (addrop, &offset ,&size)))
+ {
+ subvar_t sv;
+ svars = get_subvars_for_var (ref);
+
+ uid = var_ann (pt_var)->uid;
+ bitmap_set_bit (ai->addresses_needed, uid);
+ if (pi->pt_vars == NULL)
+ pi->pt_vars = BITMAP_GGC_ALLOC ();
+ /* If the variable is a global, mark the pointer as pointing to
+ global memory (which will make its tag a global variable). */
+ if (is_global_var (pt_var))
+ pi->pt_global_mem = 1;
- if (pt_var && SSA_VAR_P (pt_var))
+ for (sv = svars; sv; sv = sv->next)
+ {
+ if (offset == sv->offset && size == sv->size)
+ bitmap_set_bit (pi->pt_vars, var_ann (sv->var)->uid);
+ else if (offset >= sv->offset && offset < (sv->offset + sv->size))
+ bitmap_set_bit (pi->pt_vars, var_ann (sv->var)->uid);
+ else if (offset < sv->offset
+ && (offset + size > sv->offset))
+ bitmap_set_bit (pi->pt_vars, var_ann (sv->var)->uid);
+ }
+ }
+ else if (pt_var && SSA_VAR_P (pt_var))
{
+
uid = var_ann (pt_var)->uid;
bitmap_set_bit (ai->addresses_needed, uid);
if (pi->pt_vars == NULL)
pi->pt_vars = BITMAP_GGC_ALLOC ();
- bitmap_set_bit (pi->pt_vars, uid);
+
+ /* If this is an aggregate, we may have subvariables for it that need
+ to be pointed to. */
+ if (var_can_have_subvars (pt_var)
+ && (svars = get_subvars_for_var (pt_var)))
+ {
+ subvar_t sv;
+ for (sv = svars; sv; sv = sv->next)
+ {
+ uid = var_ann (sv->var)->uid;
+ bitmap_set_bit (ai->addresses_needed, uid);
+ bitmap_set_bit (pi->pt_vars, uid);
+ }
+ }
+ else
+ bitmap_set_bit (pi->pt_vars, uid);
/* If the variable is a global, mark the pointer as pointing to
global memory (which will make its tag a global variable). */
@@ -2541,3 +2655,376 @@ may_be_aliased (tree var)
return true;
}
+
+/* This structure is simply used during pushing fields onto the fieldstack
+ to track the offset of the field, since bitpos_of_field gives it relative
+ to it's immediate containing type, and we want it relative to the ultimate
+ containing object. */
+typedef struct fieldoff
+{
+ tree field;
+ HOST_WIDE_INT offset;
+} *fieldoff_t;
+
+DEF_VEC_MALLOC_P(fieldoff_t);
+
+/* Return the position, in bits, of FIELD_DECL from the beginning of it's
+ structure. */
+
+static unsigned HOST_WIDE_INT
+bitpos_of_field (const tree fdecl)
+{
+ return (tree_low_cst (DECL_FIELD_OFFSET (fdecl), 1) * 8)
+ + tree_low_cst (DECL_FIELD_BIT_OFFSET (fdecl), 1);
+}
+
+/* Given a TYPE, and a vector of field offsets FIELDSTACK, push all the fields
+ of TYPE onto fieldstack, recording their offsets along the way.
+ OFFSET is used to keep track of the offset in this entire structure, rather
+ than just the immediately containing structure. */
+
+static void
+push_fields_onto_fieldstack (tree type, VEC(fieldoff_t) **fieldstack,
+ unsigned HOST_WIDE_INT offset)
+{
+ fieldoff_t pair;
+ tree field = TYPE_FIELDS (type);
+ if (!field)
+ return;
+ if (var_can_have_subvars (field)
+ && TREE_CODE (field) == FIELD_DECL)
+ {
+ size_t before = VEC_length (fieldoff_t, *fieldstack);
+ /* Empty structures may have actual size, like in C++. So see if we
+ actually end up pushing a field, and if not, if the size is non-zero,
+ push the field onto the stack */
+ push_fields_onto_fieldstack (TREE_TYPE (field), fieldstack, offset);
+ if (before == VEC_length (fieldoff_t, *fieldstack)
+ && DECL_SIZE (field)
+ && !integer_zerop (DECL_SIZE (field)))
+ {
+ pair = xmalloc (sizeof (struct fieldoff));
+ pair->field = field;
+ pair->offset = offset;
+ VEC_safe_push (fieldoff_t, *fieldstack, pair);
+ }
+ }
+ else if (TREE_CODE (field) == FIELD_DECL)
+ {
+ pair = xmalloc (sizeof (struct fieldoff));
+ pair->field = field;
+ pair->offset = offset + bitpos_of_field (field);
+ VEC_safe_push (fieldoff_t, *fieldstack, pair);
+ }
+ for (field = TREE_CHAIN (field); field; field = TREE_CHAIN (field))
+ {
+ if (TREE_CODE (field) != FIELD_DECL)
+ continue;
+ if (var_can_have_subvars (field))
+ {
+ push_fields_onto_fieldstack (TREE_TYPE (field), fieldstack,
+ offset + bitpos_of_field (field));
+ }
+ else
+ {
+ pair = xmalloc (sizeof (struct fieldoff));
+ pair->field = field;
+ pair->offset = offset + bitpos_of_field (field);
+ VEC_safe_push (fieldoff_t, *fieldstack, pair);
+ }
+ }
+}
+
+
+/* This represents the used range of a variable. */
+typedef struct used_part
+{
+ HOST_WIDE_INT minused;
+ HOST_WIDE_INT maxused;
+} *used_part_t;
+
+static used_part_t *used_portions;
+
+/* Given a variable uid, UID, get or create the entry in the used portions
+ table for the variable. */
+static used_part_t
+get_or_create_used_part_for (size_t uid)
+{
+ used_part_t up;
+ if (used_portions[uid] == NULL)
+ {
+ up = xcalloc (1, sizeof (struct used_part));
+ up->minused = INT_MAX;
+ up->maxused = 0;
+ }
+ else
+ up = used_portions[uid];
+ return up;
+}
+
+
+
+/* Given an aggregate VAR, create the subvariables that represent it's
+ fields. */
+
+static void
+create_overlap_variables_for (tree var)
+{
+ VEC(fieldoff_t) *fieldstack = NULL;
+ used_part_t up;
+ size_t uid = var_ann (var)->uid;
+
+ if (used_portions[uid] == NULL)
+ return;
+
+ push_fields_onto_fieldstack (TREE_TYPE (var), &fieldstack, 0);
+ if (VEC_length (fieldoff_t, fieldstack) != 0)
+ {
+ subvar_t *subvars;
+ fieldoff_t fo;
+ bool notokay = false;
+ int i;
+ /* Not all fields have DECL_SIZE set for some reason. Also, we can't
+ handle variable sized fields, or fields that are arrays.
+ We *could* handle fields that are arrays, but this would require some
+ additional hacking to tree-ssa-operands.c so ARRAY_REF's like
+ a.b.c[5] were handled correctly (The ARRAY_REF will be handled first,
+ so we need to go looking to see if it's part of a structure reference
+ at that point, rather than where we do now)*/
+ for (i = 0; VEC_iterate (fieldoff_t, fieldstack, i, fo); i++)
+ {
+ if (!DECL_SIZE (fo->field)
+ || TREE_CODE (DECL_SIZE (fo->field)) != INTEGER_CST
+ || TREE_CODE (TREE_TYPE (fo->field)) == ARRAY_TYPE)
+ {
+ notokay = true;
+ break;
+ }
+ }
+ /* Cleanup after ourselves if we can't create overlap variables. */
+ if (notokay)
+ {
+ while (VEC_length (fieldoff_t, fieldstack) != 0)
+ {
+ fo = VEC_pop (fieldoff_t, fieldstack);
+ free (fo);
+ }
+ VEC_free (fieldoff_t, fieldstack);
+ return;
+ }
+ /* Otherwise, create the variables. */
+ subvars = lookup_subvars_for_var (var);
+ up = used_portions[uid];
+
+ while (VEC_length (fieldoff_t, fieldstack) != 0)
+ {
+ subvar_t sv = ggc_alloc (sizeof (struct subvar));
+ HOST_WIDE_INT fosize;
+ var_ann_t ann;
+
+ fo = VEC_pop (fieldoff_t, fieldstack);
+ fosize = TREE_INT_CST_LOW (DECL_SIZE (fo->field));
+
+ if ((fo->offset <= up->minused
+ && fo->offset + fosize <= up->minused)
+ || fo->offset >= up->maxused)
+ {
+ free (fo);
+ continue;
+ }
+
+ sv->offset = fo->offset;
+ sv->size = fosize;
+ sv->next = *subvars;
+ sv->var = create_tmp_var_raw (TREE_TYPE (fo->field), "SFT");
+ if (dump_file)
+ {
+ fprintf (dump_file, "structure field tag %s created for var %s",
+ get_name (sv->var), get_name (var));
+ fprintf (dump_file, " offset " HOST_WIDE_INT_PRINT_DEC,
+ sv->offset);
+ fprintf (dump_file, " size " HOST_WIDE_INT_PRINT_DEC,
+ sv->size);
+ fprintf (dump_file, "\n");
+
+ }
+
+ /* We need to copy the various flags from var to sv->var, so that
+ they are is_global_var iff the original variable was. */
+
+ if (DECL_EXTERNAL (var))
+ DECL_EXTERNAL (sv->var) = 1;
+ if (TREE_PUBLIC (var))
+ TREE_PUBLIC (sv->var) = 1;
+ if (TREE_STATIC (var))
+ TREE_STATIC (sv->var) = 1;
+ if (TREE_READONLY (fo->field))
+ TREE_READONLY (sv->var) = 1;
+
+ TREE_ADDRESSABLE (sv->var) = 1;
+ DECL_CONTEXT (sv->var) = DECL_CONTEXT (var);
+
+ ann = get_var_ann (sv->var);
+ ann->mem_tag_kind = STRUCT_FIELD;
+ ann->type_mem_tag = NULL;
+ add_referenced_tmp_var (sv->var);
+
+ *subvars = sv;
+ free (fo);
+ }
+ }
+
+ VEC_free (fieldoff_t, fieldstack);
+}
+
+
+/* Find the conservative answer to the question of what portions of what
+ structures are used by this statement. We assume that if we have a
+ component ref with a known size + offset, that we only need that part
+ of the structure. For unknown cases, or cases where we do something
+ to the whole structure, we assume we need to create fields for the
+ entire structure. */
+static tree
+find_used_portions (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
+{
+ switch (TREE_CODE (*tp))
+ {
+ case COMPONENT_REF:
+ {
+ HOST_WIDE_INT bitsize;
+ HOST_WIDE_INT bitpos;
+ tree offset;
+ enum machine_mode mode;
+ int unsignedp;
+ int volatilep;
+ tree ref;
+ ref = get_inner_reference (*tp, &bitsize, &bitpos, &offset, &mode,
+ &unsignedp, &volatilep, false);
+ if (DECL_P (ref) && offset == NULL && bitsize != -1)
+ {
+ size_t uid = var_ann (ref)->uid;
+ used_part_t up;
+
+ up = get_or_create_used_part_for (uid);
+
+ if (bitpos <= up->minused)
+ up->minused = bitpos;
+ if ((bitpos + bitsize >= up->maxused))
+ up->maxused = bitpos + bitsize;
+
+ used_portions[uid] = up;
+
+ *walk_subtrees = 0;
+ return NULL_TREE;
+ }
+ else if (DECL_P (ref))
+ {
+ if (DECL_SIZE (ref)
+ && var_can_have_subvars (ref)
+ && TREE_CODE (DECL_SIZE (ref)) == INTEGER_CST)
+ {
+ used_part_t up;
+ size_t uid = var_ann (ref)->uid;
+
+ up = get_or_create_used_part_for (uid);
+
+ up->minused = 0;
+ up->maxused = TREE_INT_CST_LOW (DECL_SIZE (ref));
+
+ used_portions[uid] = up;
+
+ *walk_subtrees = 0;
+ return NULL_TREE;
+ }
+ }
+ }
+ break;
+ case VAR_DECL:
+ case PARM_DECL:
+ {
+ tree var = *tp;
+ if (DECL_SIZE (var)
+ && var_can_have_subvars (var)
+ && TREE_CODE (DECL_SIZE (var)) == INTEGER_CST)
+ {
+ used_part_t up;
+ size_t uid = var_ann (var)->uid;
+
+ up = get_or_create_used_part_for (uid);
+
+ up->minused = 0;
+ up->maxused = TREE_INT_CST_LOW (DECL_SIZE (var));
+
+ used_portions[uid] = up;
+ *walk_subtrees = 0;
+ return NULL_TREE;
+ }
+ }
+ break;
+
+ default:
+ break;
+
+ }
+ return NULL_TREE;
+}
+/* We are about to create some new referenced variables, and we need the
+ before size. */
+
+static size_t old_referenced_vars;
+
+
+/* Create structure field variables for structures used in this function. */
+
+static void
+create_structure_vars (void)
+{
+ basic_block bb;
+ size_t i;
+
+ old_referenced_vars = num_referenced_vars;
+ used_portions = xcalloc (num_referenced_vars, sizeof (used_part_t));
+
+ FOR_EACH_BB (bb)
+ {
+ block_stmt_iterator bsi;
+ for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ {
+ walk_tree_without_duplicates (bsi_stmt_ptr (bsi),
+ find_used_portions,
+ NULL);
+ }
+ }
+ for (i = 0; i < old_referenced_vars; i++)
+ {
+ tree var = referenced_var (i);
+ /* The C++ FE creates vars without DECL_SIZE set, for some reason. */
+ if (var
+ && DECL_SIZE (var)
+ && var_can_have_subvars (var)
+ && var_ann (var)->mem_tag_kind == NOT_A_TAG
+ && TREE_CODE (DECL_SIZE (var)) == INTEGER_CST)
+ create_overlap_variables_for (var);
+ }
+ for (i = 0; i < old_referenced_vars; i++)
+ free (used_portions[i]);
+
+ free (used_portions);
+}
+struct tree_opt_pass pass_create_structure_vars =
+{
+ "svars", /* name */
+ NULL, /* gate */
+ create_structure_vars, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ 0, /* tv_id */
+ PROP_cfg, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_dump_func, /* todo_flags_finish */
+ 0 /* letter */
+};
+
Index: tree-ssa-operands.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-operands.c,v
retrieving revision 2.64
diff -u -p -r2.64 tree-ssa-operands.c
--- tree-ssa-operands.c 7 Mar 2005 13:58:08 -0000 2.64
+++ tree-ssa-operands.c 9 Mar 2005 14:21:49 -0000
@@ -683,8 +683,12 @@ finalize_ssa_v_must_defs (v_must_def_opt
if (num == 0)
return NULL;
- /* There should only be a single V_MUST_DEF per assignment. */
- gcc_assert (TREE_CODE (stmt) != MODIFY_EXPR || num <= 1);
+ /* In the presence of subvars, there may be more than one V_MUST_DEF per
+ statement (one for each subvar). It is a bit expensive to verify that
+ all must-defs in a statement belong to subvars if there is more than one
+ MUST-def, so we don't do it. Suffice to say, if you reach here without
+ having subvars, and have num >1, you have hit a bug. */
+
old_ops = *old_ops_p;
@@ -907,7 +911,6 @@ build_ssa_operands (tree stmt, stmt_ann_
lhs = TREE_OPERAND (lhs, 0);
if (TREE_CODE (lhs) != ARRAY_REF && TREE_CODE (lhs) != ARRAY_RANGE_REF
- && TREE_CODE (lhs) != COMPONENT_REF
&& TREE_CODE (lhs) != BIT_FIELD_REF
&& TREE_CODE (lhs) != REALPART_EXPR
&& TREE_CODE (lhs) != IMAGPART_EXPR)
@@ -1072,11 +1075,25 @@ get_expr_operands (tree stmt, tree *expr
case PARM_DECL:
case RESULT_DECL:
case CONST_DECL:
- /* If we found a variable, add it to DEFS or USES depending
- on the operand flags. */
- add_stmt_operand (expr_p, s_ann, flags);
- return;
-
+ {
+ subvar_t svars;
+
+ /* Add the subvars for a variable if it has subvars, to DEFS or USES.
+ Otherwise, add the variable itself.
+ Whether it goes to USES or DEFS depends on the operand flags. */
+ if (var_can_have_subvars (expr)
+ && (svars = get_subvars_for_var (expr)))
+ {
+ subvar_t sv;
+ for (sv = svars; sv; sv = sv->next)
+ add_stmt_operand (&sv->var, s_ann, flags);
+ }
+ else
+ {
+ add_stmt_operand (expr_p, s_ann, flags);
+ }
+ return;
+ }
case MISALIGNED_INDIRECT_REF:
get_expr_operands (stmt, &TREE_OPERAND (expr, 1), flags);
/* fall through */
@@ -1108,30 +1125,41 @@ get_expr_operands (tree stmt, tree *expr
case COMPONENT_REF:
case REALPART_EXPR:
case IMAGPART_EXPR:
- /* Similarly to arrays, references to compound variables (complex
- types and structures/unions) are globbed.
-
- FIXME: This means that
-
- a.x = 6;
- a.y = 7;
- foo (a.x, a.y);
-
- will not be constant propagated because the two partial
- definitions to 'a' will kill each other. Note that SRA may be
- able to fix this problem if 'a' can be scalarized. */
-
- /* If the LHS of the compound reference is not a regular variable,
- recurse to keep looking for more operands in the subexpression. */
- if (SSA_VAR_P (TREE_OPERAND (expr, 0)))
- add_stmt_operand (expr_p, s_ann, flags);
- else
- get_expr_operands (stmt, &TREE_OPERAND (expr, 0), flags);
-
- if (code == COMPONENT_REF)
- get_expr_operands (stmt, &TREE_OPERAND (expr, 2), opf_none);
- return;
-
+ {
+ tree ref;
+ HOST_WIDE_INT offset, size;
+ /* This component ref becomes an access to all of the subvariables
+ it can touch, if we can determine that, but *NOT* the real one.
+ If we can't determine which fields we could touch, the recursion
+ will eventually get to a variable and add *all* of it's subvars, or
+ whatever is the minimum correct subset. */
+
+ ref = okay_component_ref_for_subvars (expr, &offset, &size);
+ if (ref)
+ {
+ subvar_t svars = get_subvars_for_var (ref);
+ subvar_t sv;
+ for (sv = svars; sv; sv = sv->next)
+ {
+
+ if (offset == sv->offset && size == sv->size)
+ add_stmt_operand (&sv->var, s_ann, flags);
+ else if (offset >= sv->offset
+ && offset < (sv->offset + sv->size))
+ add_stmt_operand (&sv->var, s_ann, flags & ~opf_kill_def);
+ else if (offset < sv->offset
+ && (offset + size > sv->offset))
+ add_stmt_operand (&sv->var, s_ann, flags & ~opf_kill_def);
+ }
+ }
+ else
+ get_expr_operands (stmt, &TREE_OPERAND (expr, 0),
+ flags & ~opf_kill_def);
+
+ if (code == COMPONENT_REF)
+ get_expr_operands (stmt, &TREE_OPERAND (expr, 2), opf_none);
+ return;
+ }
case WITH_SIZE_EXPR:
/* WITH_SIZE_EXPR is a pass-through reference to its first argument,
and an rvalue reference to its second argument. */
@@ -1162,7 +1190,6 @@ get_expr_operands (tree stmt, tree *expr
op = TREE_OPERAND (expr, 0);
if (TREE_CODE (op) == ARRAY_REF
|| TREE_CODE (op) == ARRAY_RANGE_REF
- || TREE_CODE (op) == COMPONENT_REF
|| TREE_CODE (op) == REALPART_EXPR
|| TREE_CODE (op) == IMAGPART_EXPR)
subflags = opf_is_def;
@@ -1558,9 +1585,10 @@ add_stmt_operand (tree *var_p, stmt_ann_
{
if (flags & opf_kill_def)
{
- /* Only regular variables may get a V_MUST_DEF
- operand. */
- gcc_assert (v_ann->mem_tag_kind == NOT_A_TAG);
+ /* Only regular variables or struct fields may get a
+ V_MUST_DEF operand. */
+ gcc_assert (v_ann->mem_tag_kind == NOT_A_TAG
+ || v_ann->mem_tag_kind == STRUCT_FIELD);
/* V_MUST_DEF for non-aliased, non-GIMPLE register
variable definitions. */
append_v_must_def (var);
@@ -1619,26 +1647,65 @@ add_stmt_operand (tree *var_p, stmt_ann_
}
}
-
+
/* Record that VAR had its address taken in the statement with annotations
S_ANN. */
static void
note_addressable (tree var, stmt_ann_t s_ann)
{
+ tree ref;
+ subvar_t svars;
+ HOST_WIDE_INT offset;
+ HOST_WIDE_INT size;
+
if (!s_ann)
return;
-
+
+ /* If this is a COMPONENT_REF, and we know exactly what it touches, we only
+ take the address of the subvariables it will touch.
+ Otherwise, we take the address of all the subvariables, plus the real
+ ones. */
+
+ if (var && TREE_CODE (var) == COMPONENT_REF
+ && (ref = okay_component_ref_for_subvars (var, &offset, &size)))
+ {
+ subvar_t sv;
+ svars = get_subvars_for_var (ref);
+
+ if (s_ann->addresses_taken == NULL)
+ s_ann->addresses_taken = BITMAP_GGC_ALLOC ();
+
+ for (sv = svars; sv; sv = sv->next)
+ {
+ if (offset == sv->offset && size == sv->size)
+ bitmap_set_bit (s_ann->addresses_taken, var_ann (sv->var)->uid);
+ else if (offset >= sv->offset && offset < (sv->offset + sv->size))
+ bitmap_set_bit (s_ann->addresses_taken, var_ann (sv->var)->uid);
+ else if (offset < sv->offset
+ && (offset + size > sv->offset))
+ bitmap_set_bit (s_ann->addresses_taken, var_ann (sv->var)->uid);
+ }
+ return;
+ }
+
var = get_base_address (var);
if (var && SSA_VAR_P (var))
{
if (s_ann->addresses_taken == NULL)
- s_ann->addresses_taken = BITMAP_GGC_ALLOC ();
+ s_ann->addresses_taken = BITMAP_GGC_ALLOC ();
+
bitmap_set_bit (s_ann->addresses_taken, var_ann (var)->uid);
+ if (var_can_have_subvars (var)
+ && (svars = get_subvars_for_var (var)))
+ {
+ subvar_t sv;
+ for (sv = svars; sv; sv = sv->next)
+ bitmap_set_bit (s_ann->addresses_taken, var_ann (sv->var)->uid);
+ }
}
}
-
/* Add clobbering definitions for .GLOBAL_VAR or for each of the call
clobbered variables in the function. */
Index: tree-vect-analyze.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-vect-analyze.c,v
retrieving revision 2.7
diff -u -p -r2.7 tree-vect-analyze.c
--- tree-vect-analyze.c 8 Mar 2005 13:57:01 -0000 2.7
+++ tree-vect-analyze.c 9 Mar 2005 14:21:49 -0000
@@ -70,7 +70,7 @@ static bool vect_base_addr_differ_p (str
struct data_reference *drb, bool *);
static tree vect_object_analysis (tree, tree, bool, tree,
struct data_reference **, tree *, tree *,
- tree *, bool *, tree *);
+ tree *, bool *, tree *, subvar_t *);
static tree vect_address_analysis (tree, tree, bool, tree,
struct data_reference *, tree *, tree *,
tree *, bool *);
@@ -1377,6 +1377,7 @@ vect_address_analysis (tree expr, tree s
tree oprnd0, oprnd1, base_address, offset_expr, base_addr0, base_addr1;
tree address_offset = ssize_int (0), address_misalign = ssize_int (0);
tree dummy;
+ subvar_t dummy2;
switch (TREE_CODE (expr))
{
@@ -1426,9 +1427,10 @@ vect_address_analysis (tree expr, tree s
return base_addr0 ? base_addr0 : base_addr1;
case ADDR_EXPR:
- base_address = vect_object_analysis (TREE_OPERAND (expr, 0), stmt, is_read,
- vectype, &dr, offset, misalign, step,
- base_aligned, &dummy);
+ base_address = vect_object_analysis (TREE_OPERAND (expr, 0), stmt,
+ is_read, vectype, &dr, offset,
+ misalign, step, base_aligned,
+ &dummy, &dummy2);
return base_address;
case SSA_NAME:
@@ -1507,6 +1509,7 @@ vect_address_analysis (tree expr, tree s
STEP - evolution of the DR_REF in the loop
BASE_ALIGNED - indicates if BASE is aligned
MEMTAG - memory tag for aliasing purposes
+ SUBVAR - Sub-variables of the variable
If something unexpected is encountered (an unsupported form of data-ref),
then NULL_TREE is returned. */
@@ -1515,7 +1518,8 @@ static tree
vect_object_analysis (tree memref, tree stmt, bool is_read,
tree vectype, struct data_reference **dr,
tree *offset, tree *misalign, tree *step,
- bool *base_aligned, tree *memtag)
+ bool *base_aligned, tree *memtag,
+ subvar_t *subvars)
{
tree base = NULL_TREE, base_address = NULL_TREE;
tree object_offset = ssize_int (0), object_misalign = ssize_int (0);
@@ -1611,6 +1615,8 @@ vect_object_analysis (tree memref, tree
us to object. */
DR_BASE_NAME ((*dr)) = memref;
+ if (SSA_VAR_P (memref) && var_can_have_subvars (memref))
+ *subvars = get_subvars_for_var (memref);
base_address = build_fold_addr_expr (memref);
*memtag = memref;
}
@@ -1698,6 +1704,9 @@ vect_object_analysis (tree memref, tree
/* MEMREF cannot be analyzed. */
return NULL_TREE;
+ if (SSA_VAR_P (*memtag) && var_can_have_subvars (*memtag))
+ *subvars = get_subvars_for_var (*memtag);
+
/* Part 2: Combine the results of object and address analysis to calculate
INITIAL_OFFSET, STEP and misalignment info. */
*offset = size_binop (PLUS_EXPR, object_offset, address_offset);
@@ -1780,6 +1789,7 @@ vect_analyze_data_refs (loop_vec_info lo
tree scalar_type, vectype;
tree base, offset, misalign, step, tag;
bool base_aligned;
+ subvar_t subvars;
/* Assumption: there exists a data-ref in stmt, if and only if
it has vuses/vdefs. */
@@ -1843,7 +1853,7 @@ vect_analyze_data_refs (loop_vec_info lo
dr = NULL;
base = vect_object_analysis (memref, stmt, is_read, vectype, &dr,
&offset, &misalign, &step,
- &base_aligned, &tag);
+ &base_aligned, &tag, &subvars);
if (!base)
{
if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
@@ -1860,6 +1870,7 @@ vect_analyze_data_refs (loop_vec_info lo
STMT_VINFO_VECT_MISALIGNMENT (stmt_info) = misalign;
STMT_VINFO_VECT_BASE_ALIGNED_P (stmt_info) = base_aligned;
STMT_VINFO_MEMTAG (stmt_info) = tag;
+ STMT_VINFO_SUBVARS (stmt_info) = subvars;
STMT_VINFO_VECTYPE (stmt_info) = vectype;
VARRAY_PUSH_GENERIC_PTR (*datarefs, dr);
STMT_VINFO_DATA_REF (stmt_info) = dr;
Index: tree-vect-transform.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-vect-transform.c,v
retrieving revision 2.3
diff -u -p -r2.3 tree-vect-transform.c
--- tree-vect-transform.c 7 Mar 2005 21:14:10 -0000 2.3
+++ tree-vect-transform.c 9 Mar 2005 14:21:50 -0000
@@ -356,12 +356,14 @@ vect_create_data_ref_ptr (tree stmt, blo
tag = STMT_VINFO_MEMTAG (stmt_info);
gcc_assert (tag);
get_var_ann (vect_ptr)->type_mem_tag = tag;
-
+ get_var_ann (vect_ptr)->subvars = STMT_VINFO_SUBVARS (stmt_info);
+
/* Mark for renaming all aliased variables
(i.e, the may-aliases of the type-mem-tag). */
nvuses = NUM_VUSES (vuses);
nv_may_defs = NUM_V_MAY_DEFS (v_may_defs);
nv_must_defs = NUM_V_MUST_DEFS (v_must_defs);
+
for (i = 0; i < nvuses; i++)
{
tree use = VUSE_OP (vuses, i);
Index: tree-vectorizer.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-vectorizer.h,v
retrieving revision 2.14
diff -u -p -r2.14 tree-vectorizer.h
--- tree-vectorizer.h 17 Feb 2005 08:47:28 -0000 2.14
+++ tree-vectorizer.h 9 Mar 2005 14:21:50 -0000
@@ -172,6 +172,7 @@ typedef struct _stmt_vec_info {
/* Aliasing information. */
tree memtag;
+ subvar_t subvars;
/** The following fields are used to store the information about
data-reference. {base_address + initial_offset} is the first location
@@ -213,6 +214,7 @@ typedef struct _stmt_vec_info {
#define STMT_VINFO_VEC_STMT(S) (S)->vectorized_stmt
#define STMT_VINFO_DATA_REF(S) (S)->data_ref_info
#define STMT_VINFO_MEMTAG(S) (S)->memtag
+#define STMT_VINFO_SUBVARS(S) (S)->subvars
#define STMT_VINFO_VECT_DR_BASE_ADDRESS(S)(S)->base_address
#define STMT_VINFO_VECT_INIT_OFFSET(S) (S)->initial_offset
#define STMT_VINFO_VECT_STEP(S) (S)->step
Index: doc/invoke.texi
===================================================================
RCS file: /cvs/gcc/gcc/gcc/doc/invoke.texi,v
retrieving revision 1.587
diff -u -p -r1.587 invoke.texi
--- doc/invoke.texi 5 Mar 2005 09:04:30 -0000 1.587
+++ doc/invoke.texi 9 Mar 2005 14:21:54 -0000
@@ -266,6 +266,7 @@ Objective-C and Objective-C++ Dialects}.
-fdump-tree-nrv -fdump-tree-vect @gol
-fdump-tree-sink @gol
-fdump-tree-sra@r{[}-@var{n}@r{]} @gol
+-fdump-tree-svars @gol
-fdump-tree-fre@r{[}-@var{n}@r{]} @gol
-ftree-vectorizer-verbose=@var{n} @gol
-feliminate-dwarf2-dups -feliminate-unused-debug-types @gol
@@ -3818,6 +3819,11 @@ appending @file{.ch} to the source file
Dump SSA related information to a file. The file name is made by appending
@file{.ssa} to the source file name.
+@item svars
+@opindex fdump-tree-svars
+Dump structure aliasing variable information to a file. This file name
+is made by appending @file{.svars} to the source file name.
+
@item alias
@opindex fdump-tree-alias
Dump aliasing information for each function. The file name is made by
Index: doc/tree-ssa.texi
===================================================================
RCS file: /cvs/gcc/gcc/gcc/doc/tree-ssa.texi,v
retrieving revision 1.17
diff -u -p -r1.17 tree-ssa.texi
--- doc/tree-ssa.texi 5 Mar 2005 19:56:31 -0000 1.17
+++ doc/tree-ssa.texi 9 Mar 2005 14:21:54 -0000
@@ -1208,9 +1208,47 @@ hooks to execute custom code at various
@cindex flow-sensitive alias analysis
@cindex flow-insensitive alias analysis
-Alias analysis proceeds in 3 main phases:
+Alias analysis proceeds in 4 main phases:
@enumerate
+@item Structural alias analysis.
+
+This phase walks the types for structure variables, and determines which
+of the fields can overlap using offset and size of each field. For each
+field, a ``subvariable'' called a ``Structure field tag'' (SFT)@ is
+created, which represents that field as a separate variable. All
+accesses that could possibly overlap with a given field will have
+virtual operands for the SFT of that field.
+
+@smallexample
+struct foo
+@{
+ int a;
+ int b;
+@}
+struct foo temp;
+int bar (void)
+@{
+ int tmp1, tmp2, tmp3;
+ SFT.0_2 = V_MUST_DEF <SFT.0_1>
+ temp.a = 5;
+ SFT.1_4 = V_MUST_DEF <SFT.1_3>
+ temp.b = 6;
+
+ VUSE <SFT.1_4>
+ tmp1_5 = temp.b;
+ VUSE <SFT.0_2>
+ tmp2_6 = temp.a;
+
+ tmp3_7 = tmp1_5 + tmp2_6;
+ return tmp3_7;
+@}
+@end smallexample
+
+Optimizations wishing to create new variables based on existing
+structure variables need to make sure to either mark the new variables
+for renaming, or copy the subvars.
+
@item Points-to and escape analysis.
This phase walks the use-def chains in the SSA web looking for
Index: testsuite/gcc.dg/tree-ssa/structopt-1.c
===================================================================
RCS file: testsuite/gcc.dg/tree-ssa/structopt-1.c
diff -N testsuite/gcc.dg/tree-ssa/structopt-1.c
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ testsuite/gcc.dg/tree-ssa/structopt-1.c 9 Mar 2005 14:21:56 -0000
@@ -0,0 +1,15 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-lim-details" } */
+int x; int y;
+struct { int x; int y; } global;
+int foo() {
+ int i;
+ for ( i=0; i<10; i++)
+ y += x*x;
+ for ( i=0; i<10; i++)
+ global.y += global.x*global.x;
+}
+
+/* { dg-final { scan-tree-dump-times "Executing store motion of global.y" 1 "lim" } } */
+/* XXX: We should also check for the load motion of global.x, but there is no easy way to do this. */
+
Index: testsuite/gcc.dg/tree-ssa/structopt-2.c
===================================================================
RCS file: testsuite/gcc.dg/tree-ssa/structopt-2.c
diff -N testsuite/gcc.dg/tree-ssa/structopt-2.c
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ testsuite/gcc.dg/tree-ssa/structopt-2.c 9 Mar 2005 14:21:56 -0000
@@ -0,0 +1,45 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized -fno-tree-sra" } */
+
+/* Even without SRA being enabled, we should be able to eliminate every structure store and load here. */
+extern void foo (const int);
+int main(void)
+{
+ struct a
+ {
+ int e;
+ int f;
+ int g;
+ } a;
+ struct a b;
+ int x, c;
+ a.e = 50;
+ a.f = 9;
+ a.g = a.e * a.f;
+ foo (a.f);
+ foo (a.g);
+ x = a.f;
+ c = a.e;
+ foo (x);
+ foo (c);
+ a.e = 5;
+ a.f = 40;
+ a.g = 90;
+ foo (a.e);
+ foo (a.f);
+ foo (a.g);
+ c = a.f;
+ foo (c);
+ b.e = 9;
+ a.e = b.e + 1 * c;
+ a.f = 30;
+ foo (a.e);
+ foo (a.f);
+ x = a.e * a.f;
+ foo (x);
+
+}
+/* { dg-final { scan-tree-dump-times "a.e" 0 "optimized" } } */
+/* { dg-final { scan-tree-dump-times "a.f" 0 "optimized" } } */
+/* { dg-final { scan-tree-dump-times "a.g" 0 "optimized" } } */
+/* { dg-final { scan-tree-dump-times "b.e" 0 "optimized" } } */
Index: testsuite/gcc.dg/tree-ssa/structopt-3.c
===================================================================
RCS file: testsuite/gcc.dg/tree-ssa/structopt-3.c
diff -N testsuite/gcc.dg/tree-ssa/structopt-3.c
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ testsuite/gcc.dg/tree-ssa/structopt-3.c 9 Mar 2005 14:21:56 -0000
@@ -0,0 +1,16 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+struct foo
+{
+ int a;
+ int b;
+} temp;
+/* We should be able to optimize this to return 11. */
+int main(void)
+{
+ temp.a = 5;
+ temp.b = 6;
+ return temp.a + temp.b;
+}
+/* { dg-final { scan-tree-dump-times "return 11" 1 "optimized" } } */