This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH] (another one) Fix PR33870, PTA and partitoning interaction
- From: Richard Guenther <rguenther at suse dot de>
- To: gcc-patches at gcc dot gnu dot org
- Cc: Daniel Berlin <dberlin at dberlin dot org>, dnovillo at google dot com
- Date: Wed, 24 Oct 2007 13:55:21 +0200 (CEST)
- Subject: [PATCH] (another one) Fix PR33870, PTA and partitoning interaction
So, as opposed to the earlier patch which papered over one specific case
of the problem (which is that alias partitioning rips apart SFTs belonging
to the same parent variable), this is a hammer that really solves it
but at a cost (maybe, to be investigated).
IMHO the operand scanning part of accesses through pointers is fragile
in that it requires that the full set of SFTs that possibly are addressed
by the pointer is available together as aliases of a symbol. The operand
scanner in this way is able to use PTA results and the memory reference
[offset, size[ information to prune the SFTs that can possibly alias
the access based on location information. Note that this operation is
quadratic O(number of pointed-to places) * O(number of subvariables of
the parent var of the pointed-to place).
The solution is to drop this ability. We only retain TBAA pruning of
accesses through pointers (which may make the other patch which does
TBAA pruning in access_can_touch_variable necessary).
For this to work we need to make sure to add all SFTs that can be
accessed through the pointer (via a valid gimple reference, including
COMPONENT_REFs and ARRAY_REFs) to its aliases. This is done in
set_uids_in_ptset which for now only added the directly pointed-to
SFT. (The patch also includes a fix for the alias set used for
TBAA pruning in this function)
This has been bootstrapped and tested on x86_64-unknown-linux-gnu.
Note that accesses through pointers are seldom (you have to force
those via late inlining as in the alias-15.c testcase added, otherwise
ccp and forwprop do their best job to re-combine those to accesses
based on the pointed-to variable).
Another possible "fix" for PR33870 would be to force memory partitioning
to either never put SFTs into MPTs or if an SFT goes into a MPT also
add all other SFTs belonging to its parent variable. Of course this
perverts memory partition heuristics and effectively makes SFTs
useless (unless doing option one which makes one point of MPTs, reduced
number of VOPs moot).
?
For reference, the TBAA pruning patch is appended after the patch for
PR33870.
Richard.
2007-10-24 Richard Guenther <rguenther@suse.de>
PR tree-optimization/33870
* tree-ssa-structalias.c (set_uids_in_ptset): Use the correct
pointed-to alias set for TBAA pruning. Add all subvariables
that have their parent variable and itself conflict as of TBAA.
* tree-ssa-operands.c (add_vars_for_offset): Remove.
(add_virtual_operand): Add all aliases that can touch the access.
(get_indirect_ref_operands): Do not take offset and size parametes.
(get_expr_operands): Adjust accordingly.
* gcc.c-torture/execute/pr33870.c: New testcase.
* gcc.dg/tree-ssa/alias-15.c: Likewise.
Index: testsuite/gcc.c-torture/execute/pr33870.c
===================================================================
*** testsuite/gcc.c-torture/execute/pr33870.c (revision 0)
--- testsuite/gcc.c-torture/execute/pr33870.c (revision 0)
***************
*** 0 ****
--- 1,87 ----
+ extern void abort (void);
+
+ typedef struct PgHdr PgHdr;
+ typedef unsigned char u8;
+ struct PgHdr {
+ unsigned int pgno;
+ PgHdr *pNextHash, *pPrevHash;
+ PgHdr *pNextFree, *pPrevFree;
+ PgHdr *pNextAll;
+ u8 inJournal;
+ short int nRef;
+ PgHdr *pDirty, *pPrevDirty;
+ unsigned int notUsed;
+ };
+
+ static inline PgHdr *merge_pagelist(PgHdr *pA, PgHdr *pB)
+ {
+ PgHdr result;
+ PgHdr *pTail;
+ pTail = &result;
+ while( pA && pB ){
+ if( pA->pgno<pB->pgno ){
+ pTail->pDirty = pA;
+ pTail = pA;
+ pA = pA->pDirty;
+ }else{
+ pTail->pDirty = pB;
+ pTail = pB;
+ pB = pB->pDirty;
+ }
+ }
+ if( pA ){
+ pTail->pDirty = pA;
+ }else if( pB ){
+ pTail->pDirty = pB;
+ }else{
+ pTail->pDirty = 0;
+ }
+ return result.pDirty;
+ }
+
+ PgHdr * __attribute__((noinline)) sort_pagelist(PgHdr *pIn)
+ {
+ PgHdr *a[25], *p;
+ int i;
+ __builtin_memset (a, 0, sizeof (a));
+ while( pIn ){
+ p = pIn;
+ pIn = p->pDirty;
+ p->pDirty = 0;
+ for(i=0; i<25 -1; i++){
+ if( a[i]==0 ){
+ a[i] = p;
+ break;
+ }else{
+ p = merge_pagelist(a[i], p);
+ a[i] = 0;
+ }
+ }
+ if( i==25 -1 ){
+ a[i] = merge_pagelist(a[i], p);
+ }
+ }
+ p = a[0];
+ for(i=1; i<25; i++){
+ p = merge_pagelist (p, a[i]);
+ }
+ return p;
+ }
+
+ int main()
+ {
+ PgHdr a[5];
+ PgHdr *p;
+ a[0].pgno = 5;
+ a[0].pDirty = &a[1];
+ a[1].pgno = 4;
+ a[1].pDirty = &a[2];
+ a[2].pgno = 1;
+ a[2].pDirty = &a[3];
+ a[3].pgno = 3;
+ a[3].pDirty = 0;
+ p = sort_pagelist (&a[0]);
+ if (p->pDirty == p)
+ abort ();
+ return 0;
+ }
Index: testsuite/gcc.dg/tree-ssa/alias-15.c
===================================================================
*** testsuite/gcc.dg/tree-ssa/alias-15.c (revision 0)
--- testsuite/gcc.dg/tree-ssa/alias-15.c (revision 0)
***************
*** 0 ****
--- 1,20 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O -fno-early-inlining -fdump-tree-salias-vops-details" } */
+
+ struct foo {
+ int a;
+ struct X {
+ int b[4];
+ } b;
+ } m;
+ static inline struct X *wrap(struct X *p) { return p; }
+ int test2(void)
+ {
+ struct X *p = wrap(&m.b);
+ /* Both memory references need to alias the same SFT. */
+ return p->b[3] - m.b.b[3];
+ }
+
+ /* { dg-final { scan-tree-dump "SFT.1 created for var m offset 128" "salias" } } */
+ /* { dg-final { scan-tree-dump-times "VUSE <SFT.1_" 2 "salias" } } */
+ /* { dg-final { cleanup-tree-dump "salias" } } */
Index: tree-ssa-structalias.c
===================================================================
*** tree-ssa-structalias.c (revision 129598)
--- tree-ssa-structalias.c (working copy)
*************** set_uids_in_ptset (tree ptr, bitmap into
*** 4703,4714 ****
unsigned int i;
bitmap_iterator bi;
subvar_t sv;
! alias_set_type ptr_alias_set = get_alias_set (TREE_TYPE (ptr));
EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
{
varinfo_t vi = get_varinfo (i);
- alias_set_type var_alias_set;
/* The only artificial variables that are allowed in a may-alias
set are heap variables. */
--- 4703,4716 ----
unsigned int i;
bitmap_iterator bi;
subvar_t sv;
! /* ??? We want to ask about the alias set of *ptr here to be able
! to handle DECL_POINTER_ALIAS_SET. */
! alias_set_type ptr_alias_set = POINTER_TYPE_P (TREE_TYPE (ptr))
! ? get_alias_set (TREE_TYPE (TREE_TYPE (ptr))) : 0;
EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
{
varinfo_t vi = get_varinfo (i);
/* The only artificial variables that are allowed in a may-alias
set are heap variables. */
*************** set_uids_in_ptset (tree ptr, bitmap into
*** 4726,4745 ****
|| TREE_CODE (vi->decl) == PARM_DECL
|| TREE_CODE (vi->decl) == RESULT_DECL)
{
if (var_can_have_subvars (vi->decl)
&& get_subvars_for_var (vi->decl))
{
/* If VI->DECL is an aggregate for which we created
! SFTs, add the SFT corresponding to VI->OFFSET. */
! tree sft = get_subvar_at (vi->decl, vi->offset);
! gcc_assert (sft);
! if (sft)
{
! var_alias_set = get_alias_set (sft);
if (no_tbaa_pruning
|| (!is_derefed && !vi->directly_dereferenced)
! || alias_sets_conflict_p (ptr_alias_set, var_alias_set))
! bitmap_set_bit (into, DECL_UID (sft));
}
}
else
--- 4728,4759 ----
|| TREE_CODE (vi->decl) == PARM_DECL
|| TREE_CODE (vi->decl) == RESULT_DECL)
{
+ alias_set_type var_alias_set = get_alias_set (vi->decl);
+
if (var_can_have_subvars (vi->decl)
&& get_subvars_for_var (vi->decl))
{
+ subvar_t sv;
+
+ /* If the pointer alias set does not conflict with the
+ pointed to variable, then a subvariable cannot be
+ accessed through it either. */
+ if (!(no_tbaa_pruning
+ || (!is_derefed && !vi->directly_dereferenced)
+ || alias_sets_conflict_p (ptr_alias_set, var_alias_set)))
+ continue;
+
/* If VI->DECL is an aggregate for which we created
! SFTs, add all SFTs conflicting with accesses possible
! through this pointer. */
! sv = get_subvars_for_var (vi->decl);
! for (; sv; sv = sv->next)
{
! alias_set_type sft_alias_set = get_alias_set (sv->var);
if (no_tbaa_pruning
|| (!is_derefed && !vi->directly_dereferenced)
! || alias_sets_conflict_p (ptr_alias_set, sft_alias_set))
! bitmap_set_bit (into, DECL_UID (sv->var));
}
}
else
*************** set_uids_in_ptset (tree ptr, bitmap into
*** 4750,4756 ****
bitmap_set_bit (into, DECL_UID (vi->decl));
else
{
- var_alias_set = get_alias_set (vi->decl);
if (no_tbaa_pruning
|| (!is_derefed && !vi->directly_dereferenced)
|| alias_sets_conflict_p (ptr_alias_set, var_alias_set))
--- 4764,4769 ----
Index: tree-ssa-operands.c
===================================================================
*** tree-ssa-operands.c (revision 129598)
--- tree-ssa-operands.c (working copy)
*************** access_can_touch_variable (tree ref, tre
*** 1367,1473 ****
return true;
}
- /* Add the actual variables FULL_REF can access, given a member of
- full_ref's points-to set VAR, where FULL_REF is an access of SIZE at
- OFFSET from var. IS_CALL_SITE is true if this is a call, and IS_DEF
- is true if this is supposed to be a vdef, and false if this should
- be a VUSE.
-
- The real purpose of this function is to take a points-to set for a
- pointer to a structure, say
-
- struct s {
- int a;
- int b;
- } foo, *foop = &foo;
-
- and discover which variables an access, such as foop->b, can alias.
-
- This is necessary because foop only actually points to foo's first
- member, so that is all the points-to set contains. However, an access
- to foop->a may be touching some single SFT if we have created some
- SFT's for a structure. */
-
- static bool
- add_vars_for_offset (tree full_ref, tree var, HOST_WIDE_INT offset,
- HOST_WIDE_INT size, bool is_call_site, bool is_def)
- {
- /* Call-clobbered tags may have non-call-clobbered
- symbols in their alias sets. Ignore them if we are
- adding VOPs for a call site. */
- if (is_call_site && !is_call_clobbered (var))
- return false;
-
- /* For offset 0, we already have the right variable. If there is no
- full_ref, this is not a place we care about (All component
- related accesses that go through pointers will have full_ref not
- NULL).
- Any var for which we didn't create SFT's can't be
- distinguished. */
- if (!full_ref || (offset == 0 && size != -1)
- || (TREE_CODE (var) != STRUCT_FIELD_TAG
- && (!var_can_have_subvars (var) || !get_subvars_for_var (var))))
- {
- if (!access_can_touch_variable (full_ref, var, offset, size))
- return false;
-
- if (is_def)
- append_vdef (var);
- else
- append_vuse (var);
- return true;
- }
- else if (TREE_CODE (var) == STRUCT_FIELD_TAG)
- {
- if (size == -1)
- {
- bool added = false;
- subvar_t sv = get_subvars_for_var (SFT_PARENT_VAR (var));
- for (; sv; sv = sv->next)
- {
- if (overlap_subvar (SFT_OFFSET (var) + offset, size,
- sv->var, NULL)
- && access_can_touch_variable (full_ref, sv->var,
- offset, size))
- {
- added = true;
- if (is_def)
- append_vdef (sv->var);
- else
- append_vuse (sv->var);
- }
- }
- return added;
- }
- else
- {
- bool added = false;
- subvar_t sv = get_subvars_for_var (SFT_PARENT_VAR (var));
- for (; sv; sv = sv->next)
- {
- /* Once we hit the end of the parts that could touch,
- stop looking. */
- if (SFT_OFFSET (var) + offset + size <= SFT_OFFSET (sv->var))
- break;
- if (overlap_subvar (SFT_OFFSET (var) + offset, size,
- sv->var, NULL)
- && access_can_touch_variable (full_ref, sv->var, offset,
- size))
- {
- added = true;
- if (is_def)
- append_vdef (sv->var);
- else
- append_vuse (sv->var);
- }
- }
- return added;
- }
- }
-
- return false;
- }
-
/* Add VAR to the virtual operands array. FLAGS is as in
get_expr_operands. FULL_REF is a tree that contains the entire
pointer dereference expression, if available, or NULL otherwise.
--- 1367,1372 ----
*************** add_virtual_operand (tree var, stmt_ann_
*** 1533,1553 ****
bitmap_iterator bi;
unsigned int i;
tree al;
/* The variable is aliased. Add its aliases to the virtual
operands. */
gcc_assert (!bitmap_empty_p (aliases));
!
! if (flags & opf_def)
{
! bool none_added = true;
! EXECUTE_IF_SET_IN_BITMAP (aliases, 0, i, bi)
! {
! al = referenced_var (i);
! none_added &= !add_vars_for_offset (full_ref, al, offset, size,
! is_call_site, true);
! }
/* If the variable is also an alias tag, add a virtual
operand for it, otherwise we will miss representing
references to the members of the variable's alias set.
--- 1432,1467 ----
bitmap_iterator bi;
unsigned int i;
tree al;
+ bool none_added;
/* The variable is aliased. Add its aliases to the virtual
operands. */
gcc_assert (!bitmap_empty_p (aliases));
! none_added = true;
! EXECUTE_IF_SET_IN_BITMAP (aliases, 0, i, bi)
{
! al = referenced_var (i);
!
! /* Call-clobbered tags may have non-call-clobbered
! symbols in their alias sets. Ignore them if we are
! adding VOPs for a call site. */
! if (is_call_site && !is_call_clobbered (al))
! continue;
!
! /* If the access cannot possibly touch the var, don't add it.
! Accesses through pointers arrive with [0, -1[ access only. */
! if (!access_can_touch_variable (full_ref, al, offset, size))
! continue;
!
! if (flags & opf_def)
! append_vdef (al);
! else
! append_vuse (al);
! none_added = false;
! }
+ if (flags & opf_def)
+ {
/* If the variable is also an alias tag, add a virtual
operand for it, otherwise we will miss representing
references to the members of the variable's alias set.
*************** add_virtual_operand (tree var, stmt_ann_
*** 1566,1580 ****
}
else
{
- bool none_added = true;
- EXECUTE_IF_SET_IN_BITMAP (aliases, 0, i, bi)
- {
- al = referenced_var (i);
- none_added &= !add_vars_for_offset (full_ref, al, offset, size,
- is_call_site, false);
-
- }
-
/* Even if no aliases have been added, we still need to
establish def-use and use-def chains, lest
transformations think that this is not a memory
--- 1480,1485 ----
*************** add_stmt_operand (tree *var_p, stmt_ann_
*** 1641,1649 ****
static void
get_indirect_ref_operands (tree stmt, tree expr, int flags,
! tree full_ref,
! HOST_WIDE_INT offset, HOST_WIDE_INT size,
! bool recurse_on_base)
{
tree *pptr = &TREE_OPERAND (expr, 0);
tree ptr = *pptr;
--- 1546,1552 ----
static void
get_indirect_ref_operands (tree stmt, tree expr, int flags,
! tree full_ref, bool recurse_on_base)
{
tree *pptr = &TREE_OPERAND (expr, 0);
tree ptr = *pptr;
*************** get_indirect_ref_operands (tree stmt, tr
*** 1664,1670 ****
{
/* PTR has its own memory tag. Use it. */
add_virtual_operand (pi->name_mem_tag, s_ann, flags,
! full_ref, offset, size, false);
}
else
{
--- 1567,1573 ----
{
/* PTR has its own memory tag. Use it. */
add_virtual_operand (pi->name_mem_tag, s_ann, flags,
! full_ref, 0, -1, false);
}
else
{
*************** get_indirect_ref_operands (tree stmt, tr
*** 1693,1699 ****
if (v_ann->symbol_mem_tag)
add_virtual_operand (v_ann->symbol_mem_tag, s_ann, flags,
! full_ref, offset, size, false);
/* Aliasing information is missing; mark statement as
volatile so we won't optimize it out too actively. */
--- 1596,1602 ----
if (v_ann->symbol_mem_tag)
add_virtual_operand (v_ann->symbol_mem_tag, s_ann, flags,
! full_ref, 0, -1, false);
/* Aliasing information is missing; mark statement as
volatile so we won't optimize it out too actively. */
*************** get_expr_operands (tree stmt, tree *expr
*** 2122,2128 ****
case ALIGN_INDIRECT_REF:
case INDIRECT_REF:
! get_indirect_ref_operands (stmt, expr, flags, expr, 0, -1, true);
return;
case TARGET_MEM_REF:
--- 2025,2031 ----
case ALIGN_INDIRECT_REF:
case INDIRECT_REF:
! get_indirect_ref_operands (stmt, expr, flags, expr, true);
return;
case TARGET_MEM_REF:
*************** get_expr_operands (tree stmt, tree *expr
*** 2176,2183 ****
}
else if (TREE_CODE (ref) == INDIRECT_REF)
{
! get_indirect_ref_operands (stmt, ref, flags, expr, offset,
! maxsize, false);
flags |= opf_no_vops;
}
--- 2079,2085 ----
}
else if (TREE_CODE (ref) == INDIRECT_REF)
{
! get_indirect_ref_operands (stmt, ref, flags, expr, false);
flags |= opf_no_vops;
}
2007-10-19 Richard Guenther <rguenther@suse.de>
PR middle-end/32921
* tree-ssa-operands.c (access_can_touch_variable): Aliases
with non-conflicting alias sets with the reference do not
touch the access. Re-structure function a bit.
* tree-flow-inline.h (var_can_have_subvars): Unions cannot
have subvars.
Index: tree-flow-inline.h
===================================================================
*** tree-flow-inline.h (revision 129483)
--- tree-flow-inline.h (working copy)
*************** var_can_have_subvars (const_tree v)
*** 1634,1640 ****
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
--- 1634,1642 ----
return false;
/* Aggregates can have subvars. */
! if (AGGREGATE_TYPE_P (TREE_TYPE (v))
! && TREE_CODE (TREE_TYPE (v)) != UNION_TYPE
! && TREE_CODE (TREE_TYPE (v)) != QUAL_UNION_TYPE)
return true;
/* Complex types variables which are not also a gimple register can
Index: tree-ssa-operands.c
===================================================================
*** tree-ssa-operands.c (revision 129576)
--- tree-ssa-operands.c (working copy)
*************** append_vuse (tree var)
*** 1189,1194 ****
--- 1189,1195 ----
expression, if available, or NULL otherwise. ALIAS is the variable
we are asking if REF can access. OFFSET and SIZE come from the
memory access expression that generated this virtual operand.
+ IS_WRITE should be true if the access is a store, otherwise false.
XXX: We should handle the NO_ALIAS attributes here. */
*************** access_can_touch_variable (tree ref, tre
*** 1198,1204 ****
{
bool offsetgtz = offset > 0;
unsigned HOST_WIDE_INT uoffset = (unsigned HOST_WIDE_INT) offset;
! tree base = ref ? get_base_address (ref) : NULL;
/* If ALIAS is .GLOBAL_VAR then the memory reference REF must be
using a call-clobbered memory tag. By definition, call-clobbered
--- 1199,1209 ----
{
bool offsetgtz = offset > 0;
unsigned HOST_WIDE_INT uoffset = (unsigned HOST_WIDE_INT) offset;
! tree base;
!
! /* For NULL refs we cannot prune based on the unknown access. */
! if (!ref)
! return true;
/* If ALIAS is .GLOBAL_VAR then the memory reference REF must be
using a call-clobbered memory tag. By definition, call-clobbered
*************** access_can_touch_variable (tree ref, tre
*** 1206,1216 ****
if (alias == gimple_global_var (cfun))
return true;
/* If ref is a TARGET_MEM_REF, just return true, as we can't really
! disambiguate them right now. */
! if (ref && TREE_CODE (ref) == TARGET_MEM_REF)
return true;
!
/* If ALIAS is an SFT, it can't be touched if the offset
and size of the access is not overlapping with the SFT offset and
size. This is only true if we are accessing through a pointer
--- 1211,1236 ----
if (alias == gimple_global_var (cfun))
return true;
+ /* If the alias sets of the alias and the ref do not conflict then
+ then the access does not touch the alias. This is pruning based
+ on TBAA. */
+ if (flag_strict_aliasing
+ /* Memory partitions represent multiple types and need different
+ treatment for TBAA pruning. */
+ && TREE_CODE (alias) != MEMORY_PARTITION_TAG
+ /* HEAP variables do not have types that are meaningful for TBAA. */
+ && !var_ann (alias)->is_heapvar
+ && !alias_sets_conflict_p (get_alias_set (alias),
+ get_alias_set (ref)))
+ return false;
+
/* If ref is a TARGET_MEM_REF, just return true, as we can't really
! disambiguate them based on offsets right now. */
! if (TREE_CODE (ref) == TARGET_MEM_REF)
return true;
!
! base = get_base_address (ref);
!
/* If ALIAS is an SFT, it can't be touched if the offset
and size of the access is not overlapping with the SFT offset and
size. This is only true if we are accessing through a pointer
*************** access_can_touch_variable (tree ref, tre
*** 1309,1316 ****
my_char_ref_1 = (char[1:1] &) &my_char;
D.874_2 = (*my_char_ref_1)[1]{lb: 1 sz: 1};
*/
! else if (ref
! && flag_strict_aliasing
&& TREE_CODE (ref) != INDIRECT_REF
&& !MTAG_P (alias)
&& base
--- 1329,1335 ----
my_char_ref_1 = (char[1:1] &) &my_char;
D.874_2 = (*my_char_ref_1)[1]{lb: 1 sz: 1};
*/
! else if (flag_strict_aliasing
&& TREE_CODE (ref) != INDIRECT_REF
&& !MTAG_P (alias)
&& base
*************** access_can_touch_variable (tree ref, tre
*** 1344,1351 ****
/* If the offset of the access is greater than the size of one of
the possible aliases, it can't be touching that alias, because it
would be past the end of the structure. */
! else if (ref
! && flag_strict_aliasing
&& TREE_CODE (ref) != INDIRECT_REF
&& !MTAG_P (alias)
&& !POINTER_TYPE_P (TREE_TYPE (alias))
--- 1363,1369 ----
/* If the offset of the access is greater than the size of one of
the possible aliases, it can't be touching that alias, because it
would be past the end of the structure. */
! else if (flag_strict_aliasing
&& TREE_CODE (ref) != INDIRECT_REF
&& !MTAG_P (alias)
&& !POINTER_TYPE_P (TREE_TYPE (alias))