[PATCH] Improve alias information for arrays
Richard Guenther
rguenther@suse.de
Sun Jan 8 16:27:00 GMT 2006
This is a version of the array aliasing patch that passes bootstrap
and regtesting on x86_64-unknown-linux-gnu for all languages including
Ada. It adds the ability to distinguish between array elements wrt
aliasing queries by decomposing arrays into subvars if they have at
most a --param number of elements (defaults to 4, which is good for
graphics and physics operations on n-Vectors and -Matrices). This
allows standard scalar optimizers optimizing operations on these
kind of arrays.
I SPEC tested an earlier version of this patch against IAB and mainline
with overall neutral results apart from the expected improvements on
mesa and eon (I can dig out the results, if anyone is interested, but
I think I may even have posted them some time ago). The change is
compile-time neutral on bootstrap and tramp3d testing, which of course
improves most with the optimization, as with it, some vectorization
is possible (yay!).
Ok for mainline?
Thanks,
Richard.
2006-01-08 Richard Guenther <rguenther@suse.de>
PR tree-optimization/22548
PR tree-optimization/22555
PR tree-optimization/22501
* Makefile.in (tree-ssa-structalias.o): Depend on $(PARAMS_H).
* params.def (salias-max-array-elements): New parameter.
* params.h (SALIAS_MAX_ARRAY_ELEMENTS): Define.
* doc/invoke.texi (salias-max-array-elements): Document.
* tree-flow-inline.h (var_can_have_subvars): We also handle
arrays now.
* tree-ssa-alias.c (find_used_portions): Handle ARRAY_REF like
COMPONENT_REF.
* tree-ssa-structalias.c (params.h): Include.
(push_fields_onto_fieldstack): Handle ARRAY_TYPE.
(find_func_aliases): Handle multiple constraints from ARRAY_REF.
(get_constraint_for): For ADDR_EXPR operating on something
containing an ARRAY_REF, add all subvars to the solution.
(handle_ptr_arith): Handle ARRAY_TYPE like RECORD_TYPE types.
* tree-ssa-operands.c (parse_ssa_operands): Handle ARRAY_REF
for creating MUST_DEFs.
(get_expr_operands): Treat ARRAY_REF like COMPONENT_REF wrt subvars.
* gcc.dg/tree-ssa/alias-[456789].c: New testcases.
* gcc.dg/tree-ssa/alias-1[012].c: Likewise.
Index: gcc/doc/invoke.texi
===================================================================
*** gcc/doc/invoke.texi (revision 109472)
--- gcc/doc/invoke.texi (working copy)
*************** The maximum number of fields in a variab
*** 5744,5749 ****
--- 5744,5753 ----
structure accesses for which structure aliasing will consider trying
to track each field. The default is 5
+ @item salias-max-array-elements
+ The maximum number of elements an array can have and its elements
+ still be tracked individually by structure aliasing. The default is 4
+
@item sra-max-structure-size
The maximum structure size, in bytes, at which the scalar replacement
of aggregates (SRA) optimization will perform block copies. The
Index: gcc/params.h
===================================================================
*** gcc/params.h (revision 109472)
--- gcc/params.h (working copy)
*************** typedef enum compiler_param
*** 91,96 ****
--- 91,98 ----
/* Macros for the various parameters. */
#define SALIAS_MAX_IMPLICIT_FIELDS \
PARAM_VALUE (PARAM_SALIAS_MAX_IMPLICIT_FIELDS)
+ #define SALIAS_MAX_ARRAY_ELEMENTS \
+ PARAM_VALUE (PARAM_SALIAS_MAX_ARRAY_ELEMENTS)
#define SRA_MAX_STRUCTURE_SIZE \
PARAM_VALUE (PARAM_SRA_MAX_STRUCTURE_SIZE)
#define SRA_MAX_STRUCTURE_COUNT \
Index: gcc/testsuite/gcc.dg/tree-ssa/alias-8.c
===================================================================
*** gcc/testsuite/gcc.dg/tree-ssa/alias-8.c (revision 0)
--- gcc/testsuite/gcc.dg/tree-ssa/alias-8.c (revision 0)
***************
*** 0 ****
--- 1,15 ----
+ /* { dg-do run } */
+ /* { dg-options "-O2" } */
+
+ void abort(void);
+ int main()
+ {
+ int a[2];
+ int i = 1;
+ a[0] = 1;
+ a[1] = 2;
+ if (*(a + i) != 2)
+ abort();
+ return 0;
+ }
+
Index: gcc/testsuite/gcc.dg/tree-ssa/alias-9.c
===================================================================
*** gcc/testsuite/gcc.dg/tree-ssa/alias-9.c (revision 0)
--- gcc/testsuite/gcc.dg/tree-ssa/alias-9.c (revision 0)
***************
*** 0 ****
--- 1,15 ----
+ /* { dg-do run } */
+ /* { dg-options "-O2" } */
+
+ void abort(void);
+ int main()
+ {
+ int a[32];
+ int i = 1;
+ a[0] = 1;
+ a[1] = 2;
+ if (*(a + i) != 2)
+ abort();
+ return 0;
+ }
+
Index: gcc/testsuite/gcc.dg/tree-ssa/alias-4.c
===================================================================
*** gcc/testsuite/gcc.dg/tree-ssa/alias-4.c (revision 0)
--- gcc/testsuite/gcc.dg/tree-ssa/alias-4.c (revision 0)
***************
*** 0 ****
--- 1,21 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O2 -fdump-tree-optimized" } */
+
+ struct {
+ int i;
+ struct {
+ int x[2];
+ } b;
+ } a;
+
+ int foo(void)
+ {
+ a.i = 1;
+ a.b.x[0] = 0;
+ a.b.x[1] = 1;
+ return a.i + a.b.x[0];
+ }
+
+ /* { dg-final { scan-tree-dump "return 1;" "optimized" } } */
+ /* { dg-final { cleanup-tree-dump "optimized" } } */
+
Index: gcc/testsuite/gcc.dg/tree-ssa/alias-5.c
===================================================================
*** gcc/testsuite/gcc.dg/tree-ssa/alias-5.c (revision 0)
--- gcc/testsuite/gcc.dg/tree-ssa/alias-5.c (revision 0)
***************
*** 0 ****
--- 1,23 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O2 -fdump-tree-optimized" } */
+
+ struct {
+ int i;
+ struct {
+ struct {
+ int i;
+ } x[2];
+ } b;
+ } a;
+
+ int foo(void)
+ {
+ a.i = 1;
+ a.b.x[0].i = 0;
+ a.b.x[1].i = 1;
+ return a.i + a.b.x[0].i;
+ }
+
+ /* { dg-final { scan-tree-dump "return 1;" "optimized" } } */
+ /* { dg-final { cleanup-tree-dump "optimized" } } */
+
Index: gcc/testsuite/gcc.dg/tree-ssa/alias-10.c
===================================================================
*** gcc/testsuite/gcc.dg/tree-ssa/alias-10.c (revision 0)
--- gcc/testsuite/gcc.dg/tree-ssa/alias-10.c (revision 0)
***************
*** 0 ****
--- 1,20 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O2 -fdump-tree-optimized" } */
+
+ struct {
+ int i;
+ int x[2];
+ int j;
+ } a;
+
+ int foo(int i)
+ {
+ a.i = 1;
+ a.j = 2;
+ a.x[i] = 0;
+ return a.i + a.j;
+ }
+
+ /* { dg-final { scan-tree-dump "return 3;" "optimized" } } */
+ /* { dg-final { cleanup-tree-dump "optimized" } } */
+
Index: gcc/testsuite/gcc.dg/tree-ssa/alias-6.c
===================================================================
*** gcc/testsuite/gcc.dg/tree-ssa/alias-6.c (revision 0)
--- gcc/testsuite/gcc.dg/tree-ssa/alias-6.c (revision 0)
***************
*** 0 ****
--- 1,19 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O2 -fdump-tree-optimized" } */
+
+ struct param { int *a; };
+ void foo(struct param *p);
+ int bar(void)
+ {
+ int a[2];
+ struct param p;
+ a[0] = 1;
+ a[1] = 1;
+ p.a = &a[0];
+ foo(&p);
+ return a[0] + *p.a;
+ }
+
+ /* { dg-final { scan-tree-dump "return \\*p\\.a \\\+ a.0.;" "optimized" } } */
+ /* { dg-final { cleanup-tree-dump "optimized" } } */
+
Index: gcc/testsuite/gcc.dg/tree-ssa/alias-11.c
===================================================================
*** gcc/testsuite/gcc.dg/tree-ssa/alias-11.c (revision 0)
--- gcc/testsuite/gcc.dg/tree-ssa/alias-11.c (revision 0)
***************
*** 0 ****
--- 1,19 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O2 -fdump-tree-optimized" } */
+
+ struct param { int *a; };
+ void foo(struct param *p);
+ int bar(void)
+ {
+ int a[32];
+ struct param p;
+ a[0] = 1;
+ a[1] = 1;
+ p.a = &a[0];
+ foo(&p);
+ return a[0] + *p.a;
+ }
+
+ /* { dg-final { scan-tree-dump "return \\*p\\.a \\\+ a.0.;" "optimized" } } */
+ /* { dg-final { cleanup-tree-dump "optimized" } } */
+
Index: gcc/testsuite/gcc.dg/tree-ssa/alias-7.c
===================================================================
*** gcc/testsuite/gcc.dg/tree-ssa/alias-7.c (revision 0)
--- gcc/testsuite/gcc.dg/tree-ssa/alias-7.c (revision 0)
***************
*** 0 ****
--- 1,17 ----
+ /* { dg-do run } */
+ /* { dg-options "-O2" } */
+
+ void abort(void);
+ int main()
+ {
+ int a[2];
+ int *p = a;
+ int i;
+ a[0] = 1;
+ a[1] = 2;
+ for (i=0; i<2; ++i)
+ if (p[i] != i+1)
+ abort();
+ return 0;
+ }
+
Index: gcc/testsuite/gcc.dg/tree-ssa/alias-12.c
===================================================================
*** gcc/testsuite/gcc.dg/tree-ssa/alias-12.c (revision 0)
--- gcc/testsuite/gcc.dg/tree-ssa/alias-12.c (revision 0)
***************
*** 0 ****
--- 1,18 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O2 -fdump-tree-alias1-vops" } */
+
+ struct {
+ int i;
+ int x[128];
+ int j;
+ } a;
+
+ int foo(int i)
+ {
+ a.x[i] = 0;
+ return a.x[i];
+ }
+
+ /* { dg-final { scan-tree-dump "V_MAY_DEF" "alias1" } } */
+ /* { dg-final { cleanup-tree-dump "alias1" } } */
+
Index: gcc/tree-ssa-alias.c
===================================================================
*** gcc/tree-ssa-alias.c (revision 109472)
--- gcc/tree-ssa-alias.c (working copy)
*************** find_used_portions (tree *tp, int *walk_
*** 2697,2702 ****
--- 2697,2703 ----
case REALPART_EXPR:
case IMAGPART_EXPR:
case COMPONENT_REF:
+ case ARRAY_REF:
{
HOST_WIDE_INT bitsize;
HOST_WIDE_INT bitmaxsize;
Index: gcc/tree-flow-inline.h
===================================================================
*** gcc/tree-flow-inline.h (revision 109472)
--- gcc/tree-flow-inline.h (working copy)
*************** get_subvar_at (tree var, unsigned HOST_W
*** 1489,1496 ****
}
/* 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. Also complex
types which are not gimple registers can have subvars. */
static inline bool
--- 1489,1495 ----
}
/* Return true if V is a tree that we can have subvars for.
! Normally, this is any aggregate type. Also complex
types which are not gimple registers can have subvars. */
static inline bool
*************** var_can_have_subvars (tree v)
*** 1500,1508 ****
if (!DECL_P (v) || MTAG_P (v))
return false;
! /* Aggregates besides arrays can have subvars. */
! if (AGGREGATE_TYPE_P (TREE_TYPE (v))
! && TREE_CODE (TREE_TYPE (v)) != ARRAY_TYPE)
return true;
/* Complex types variables which are not also a gimple register can
--- 1499,1506 ----
if (!DECL_P (v) || MTAG_P (v))
return false;
! /* Aggregates can have subvars. */
! if (AGGREGATE_TYPE_P (TREE_TYPE (v)))
return true;
/* Complex types variables which are not also a gimple register can
Index: gcc/Makefile.in
===================================================================
*** gcc/Makefile.in (revision 109472)
--- gcc/Makefile.in (working copy)
*************** stor-layout.o : stor-layout.c $(CONFIG_H
*** 1791,1797 ****
tree-ssa-structalias.o: tree-ssa-structalias.c tree-ssa-structalias.h \
$(SYSTEM_H) $(CONFIG_H) $(GGC_H) $(TREE_H) $(TREE_FLOW_H) \
$(TM_H) coretypes.h cgraph.h tree-pass.h $(TIMEVAR_H) \
! gt-tree-ssa-structalias.h
tree-ssa.o : tree-ssa.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \
$(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) output.h $(DIAGNOSTIC_H) \
toplev.h function.h $(TIMEVAR_H) $(TM_H) coretypes.h \
--- 1791,1797 ----
tree-ssa-structalias.o: tree-ssa-structalias.c tree-ssa-structalias.h \
$(SYSTEM_H) $(CONFIG_H) $(GGC_H) $(TREE_H) $(TREE_FLOW_H) \
$(TM_H) coretypes.h cgraph.h tree-pass.h $(TIMEVAR_H) \
! gt-tree-ssa-structalias.h $(PARAMS_H)
tree-ssa.o : tree-ssa.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \
$(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) output.h $(DIAGNOSTIC_H) \
toplev.h function.h $(TIMEVAR_H) $(TM_H) coretypes.h \
Index: gcc/tree-ssa-structalias.c
===================================================================
*** gcc/tree-ssa-structalias.c (revision 109472)
--- gcc/tree-ssa-structalias.c (working copy)
*************** Foundation, Inc., 51 Franklin Street, Fi
*** 48,53 ****
--- 48,54 ----
#include "timevar.h"
#include "alloc-pool.h"
#include "splay-tree.h"
+ #include "params.h"
#include "tree-ssa-structalias.h"
#include "cgraph.h"
*************** get_constraint_for_component_ref (tree t
*** 2381,2388 ****
result->type = SCALAR;
/* If we know where this goes, then yay. Otherwise, booo. */
! if (bitmaxsize != -1
! && bitsize == bitmaxsize)
{
result->offset = bitpos;
}
--- 2382,2388 ----
result->type = SCALAR;
/* If we know where this goes, then yay. Otherwise, booo. */
! if (bitmaxsize != -1)
{
result->offset = bitpos;
}
*************** get_constraint_for_component_ref (tree t
*** 2409,2415 ****
for (curr = get_varinfo (result->var); curr; curr = curr->next)
{
if (offset_overlaps_with_access (curr->offset, curr->size,
! result->offset, bitsize))
{
result->var = curr->id;
break;
--- 2409,2415 ----
for (curr = get_varinfo (result->var); curr; curr = curr->next)
{
if (offset_overlaps_with_access (curr->offset, curr->size,
! result->offset, bitmaxsize))
{
result->var = curr->id;
break;
*************** get_constraint_for (tree t, VEC (ce_s, h
*** 2506,2511 ****
--- 2506,2530 ----
unsigned int i;
get_constraint_for (TREE_OPERAND (t, 0), results);
+ if ((handled_component_p (TREE_OPERAND (t, 0))
+ && ref_contains_array_ref (TREE_OPERAND (t, 0)))
+ || TREE_CODE (TREE_TYPE (TREE_OPERAND (t, 0))) == ARRAY_TYPE)
+ {
+ struct constraint_expr *origrhs;
+ varinfo_t origvar;
+ struct constraint_expr tmp;
+
+ gcc_assert (VEC_length (ce_s, *results) == 1);
+ origrhs = VEC_last (ce_s, *results);
+ tmp = *origrhs;
+ VEC_pop (ce_s, *results);
+ origvar = get_varinfo (origrhs->var);
+ for (; origvar; origvar = origvar->next)
+ {
+ tmp.var = origvar->id;
+ VEC_safe_push (ce_s, heap, *results, &tmp);
+ }
+ }
for (i = 0; VEC_iterate (ce_s, *results, i, c); i++)
{
if (c->type == DEREF)
*************** handle_ptr_arith (VEC (ce_s, heap) *lhsc
*** 3162,3168 ****
get_constraint_for (op0, &temp);
if (POINTER_TYPE_P (TREE_TYPE (op0))
- && TREE_CODE (TREE_TYPE (TREE_TYPE (op0))) == RECORD_TYPE
&& TREE_CODE (op1) == INTEGER_CST)
{
rhsoffset = TREE_INT_CST_LOW (op1) * BITS_PER_UNIT;
--- 3181,3186 ----
*************** find_func_aliases (tree origt)
*** 3389,3395 ****
get_constraint_for (rhsop, &rhsc);
if (TREE_CODE (strippedrhs) == ADDR_EXPR
! && AGGREGATE_TYPE_P (TREE_TYPE (rhstype)))
{
struct constraint_expr *origrhs;
varinfo_t origvar;
--- 3407,3414 ----
get_constraint_for (rhsop, &rhsc);
if (TREE_CODE (strippedrhs) == ADDR_EXPR
! && AGGREGATE_TYPE_P (TREE_TYPE (rhstype))
! && VEC_length (ce_s, rhsc) == 1)
{
struct constraint_expr *origrhs;
varinfo_t origvar;
*************** push_fields_onto_fieldstack (tree type,
*** 3579,3584 ****
--- 3598,3658 ----
return 2;
}
+ if (TREE_CODE (type) == ARRAY_TYPE)
+ {
+ tree sz = TYPE_SIZE (type);
+ tree elsz = TYPE_SIZE (TREE_TYPE (type));
+ HOST_WIDE_INT nr;
+ int i;
+
+ if (! sz || ! host_integerp (sz, 1)
+ || TREE_INT_CST_LOW (sz) == 0
+ || ! elsz || ! host_integerp (elsz, 1)
+ || TREE_INT_CST_LOW (elsz) == 0)
+ return 0;
+
+ nr = TREE_INT_CST_LOW (sz) / TREE_INT_CST_LOW (elsz);
+ if (nr > SALIAS_MAX_ARRAY_ELEMENTS)
+ return 0;
+
+ for (i = 0; i<nr; ++i)
+ {
+ bool push = false;
+ int pushed = 0;
+
+ if (has_union
+ && (TREE_CODE (TREE_TYPE (type)) == QUAL_UNION_TYPE
+ || TREE_CODE (TREE_TYPE (type)) == UNION_TYPE))
+ *has_union = true;
+
+ if (!AGGREGATE_TYPE_P (TREE_TYPE (type))) /* var_can_have_subvars */
+ push = true;
+ else if (!(pushed = push_fields_onto_fieldstack
+ (TREE_TYPE (type), fieldstack,
+ offset + i * TREE_INT_CST_LOW (elsz), has_union)))
+ /* Empty structures may have actual size, like in C++. So
+ see if we didn't push any subfields and the size is
+ nonzero, push the field onto the stack */
+ push = true;
+
+ if (push)
+ {
+ fieldoff_s *pair;
+
+ pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
+ pair->type = TREE_TYPE (type);
+ pair->size = elsz;
+ pair->decl = NULL_TREE;
+ pair->offset = offset + i * TREE_INT_CST_LOW (elsz);
+ count++;
+ }
+ else
+ count += pushed;
+ }
+
+ return count;
+ }
+
for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
if (TREE_CODE (field) == FIELD_DECL)
{
Index: gcc/params.def
===================================================================
*** gcc/params.def (revision 109472)
--- gcc/params.def (working copy)
*************** DEFPARAM (PARAM_SALIAS_MAX_IMPLICIT_FIEL
*** 47,53 ****
"salias-max-implicit-fields",
"The maximum number of fields in a structure variable without direct structure accesses that GCC will attempt to track separately",
5, 0, 0)
!
/* The maximum structure size at which the scalar replacement of
aggregates (SRA) pass will perform block copies. The default
value, 0, implies that GCC will select the most appropriate size
--- 47,60 ----
"salias-max-implicit-fields",
"The maximum number of fields in a structure variable without direct structure accesses that GCC will attempt to track separately",
5, 0, 0)
!
! /* The maximum number of array elements structure aliasing will decompose
! an array for. The default is 4. */
! DEFPARAM (PARAM_SALIAS_MAX_ARRAY_ELEMENTS,
! "salias-max-array-elements",
! "The maximum number of elements in an array for wich we track its elements separately",
! 4, 0, 0)
!
/* The maximum structure size at which the scalar replacement of
aggregates (SRA) pass will perform block copies. The default
value, 0, implies that GCC will select the most appropriate size
Index: gcc/tree-ssa-operands.c
===================================================================
*** gcc/tree-ssa-operands.c (revision 109472)
--- gcc/tree-ssa-operands.c (working copy)
*************** parse_ssa_operands (tree stmt)
*** 732,739 ****
if (TREE_CODE (lhs) == VIEW_CONVERT_EXPR)
lhs = TREE_OPERAND (lhs, 0);
! if (TREE_CODE (lhs) != ARRAY_REF
! && TREE_CODE (lhs) != ARRAY_RANGE_REF
&& TREE_CODE (lhs) != BIT_FIELD_REF)
lhs_flags |= opf_kill_def;
--- 732,738 ----
if (TREE_CODE (lhs) == VIEW_CONVERT_EXPR)
lhs = TREE_OPERAND (lhs, 0);
! if (TREE_CODE (lhs) != ARRAY_RANGE_REF
&& TREE_CODE (lhs) != BIT_FIELD_REF)
lhs_flags |= opf_kill_def;
*************** get_expr_operands (tree stmt, tree *expr
*** 1103,1109 ****
get_tmr_operands (stmt, expr, flags);
return;
- case ARRAY_REF:
case ARRAY_RANGE_REF:
/* Treat array references as references to the virtual variable
representing the array. The virtual variable for an ARRAY_REF
--- 1102,1107 ----
*************** get_expr_operands (tree stmt, tree *expr
*** 1122,1127 ****
--- 1120,1126 ----
get_expr_operands (stmt, &TREE_OPERAND (expr, 3), opf_none);
return;
+ case ARRAY_REF:
case COMPONENT_REF:
case REALPART_EXPR:
case IMAGPART_EXPR:
*************** get_expr_operands (tree stmt, tree *expr
*** 1169,1174 ****
--- 1168,1179 ----
s_ann->has_volatile_ops = true;
get_expr_operands (stmt, &TREE_OPERAND (expr, 2), opf_none);
}
+ else if (code == ARRAY_REF)
+ {
+ get_expr_operands (stmt, &TREE_OPERAND (expr, 1), opf_none);
+ get_expr_operands (stmt, &TREE_OPERAND (expr, 2), opf_none);
+ get_expr_operands (stmt, &TREE_OPERAND (expr, 3), opf_none);
+ }
return;
}
case WITH_SIZE_EXPR:
*************** get_expr_operands (tree stmt, tree *expr
*** 1199,1206 ****
op = TREE_OPERAND (expr, 0);
if (TREE_CODE (op) == WITH_SIZE_EXPR)
op = TREE_OPERAND (expr, 0);
! if (TREE_CODE (op) == ARRAY_REF
! || TREE_CODE (op) == ARRAY_RANGE_REF
|| TREE_CODE (op) == REALPART_EXPR
|| TREE_CODE (op) == IMAGPART_EXPR)
subflags = opf_is_def;
--- 1204,1210 ----
op = TREE_OPERAND (expr, 0);
if (TREE_CODE (op) == WITH_SIZE_EXPR)
op = TREE_OPERAND (expr, 0);
! if (TREE_CODE (op) == ARRAY_RANGE_REF
|| TREE_CODE (op) == REALPART_EXPR
|| TREE_CODE (op) == IMAGPART_EXPR)
subflags = opf_is_def;
More information about the Gcc-patches
mailing list