Also fails with -O --param max-aliased-vops=500 (the -O2 setting)

Janis, can you hunt this?  (in case it also fails for you that is)

I started regression hunt. It is introduced between 127611 and 127769.

Revision 127629

http://gcc.gnu.org/ml/gcc-cvs/2007-08/msg00523.html

introduced this regression.

This is wrong alias info.  We hoist

  # VUSE <SFT.6_108>
  p_42 = result.pDirty;

out of the loop.  It looks like we don't have VUSEs of a and MPT.47 here like

  # VUSE <a_115, MPT.47_116>
  p_38 = p_35->pDirty;

because results address is only taken from within a PHI node:

  # pD.1574_36 = PHI <&resultD.1619(6), pD.1574_84(11)>


It also happens that with -O alias analysis only runs once.

The pointed-to vars of pD.1574_36 include SFT.6, but

  # aD.1573_113 = VDEF <aD.1573_90>
  # MPT.47D.1693_114 = VDEF <MPT.47D.1693_103>
  pD.1574_36->pDirtyD.1552 = pD.1574_33;

and SFT.6 is not in partition MPT.47.

Adding Diego, as disabling memory paritioning (--param max-aliased-vops=10000)
results in correct alias info.  Which hints at that the identified patch only
exposed the regression.

The bug goes like the following.  We partition some of struct PgHdr fields
into MPT.47, stopping to do partitioning before we reach SFT.6 (which also is
a field of struct PgHdr) here:

  for (i = 0; VEC_iterate (mem_sym_stats_t, mp_info, i, mp_p); i++)
    {
      tree mpt;

      /* If we are below the threshold, stop.  */
      if (!need_to_partition_p (mem_ref_stats))
        break;

      mpt = find_partition_for (mp_p);
      estimate_vop_reduction (mem_ref_stats, mp_p, mpt);
    }


now we have two kinds of stmts, reads from the local variable result:

  # VUSE <SFT.6D.1652_108>
  pD.1574_42 = resultD.1619.pDirtyD.1552;

where obviously only SFT.6 is read.  And reads through a pointer which is
defined as

  # pD.1574_36 = PHI <pD.1574_19(10), &resultD.1619(6)>

and look like

  # aD.1573_117 = VDEF <aD.1573_90>
  # MPT.47D.1693_118 = VDEF <MPT.47D.1693_103>
  pD.1574_36->pDirtyD.1552 = pD.1574_33;

because we prune SFT.6.  Looks like add_vars_for_offset is faulty.

I have a patch.

For the parent variable of the missing VOP SFT.6 there is no SFT with offset
zero in pD.1574_36 NMTs aliases.  So the following triggers:

!       EXECUTE_IF_SET_IN_BITMAP (aliases, 0, i, bi)
        {
!         al = referenced_var (i);
!         if (TREE_CODE (al) == STRUCT_FIELD_TAG)
            {
!             gcc_assert (SFT_OFFSET (get_subvars_for_var (SFT_PARENT_VAR (al))->var) == 0);
!             gcc_assert (bitmap_bit_p (aliases, DECL_UID (get_subvars_for_var (SFT_PARENT_VAR (al))->var)));
            }

Created attachment 14403 [details]
full checking patch

And sadly the following doesn't help.

Index: tree-ssa-structalias.c
===================================================================
--- tree-ssa-structalias.c      (revision 129582)
+++ tree-ssa-structalias.c      (working copy)
@@ -4738,7 +4738,8 @@ set_uids_in_ptset (tree ptr, bitmap into
                  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))
+                     || alias_sets_conflict_p (ptr_alias_set, var_alias_set)
+                     || vi->offset == 0)
                    bitmap_set_bit (into, DECL_UID (sft));
                }
            }

Now it is memory paritioning again ;)

static void
rewrite_alias_set_for (tree tag, bitmap new_aliases)
{
  bitmap_iterator bi;
  unsigned i;
  tree mpt, sym;

  EXECUTE_IF_SET_IN_BITMAP (MTAG_ALIASES (tag), 0, i, bi)
    {
      sym = referenced_var (i);
      mpt = memory_partition (sym);
      if (mpt)
        bitmap_set_bit (new_aliases, DECL_UID (mpt));
      else
        bitmap_set_bit (new_aliases, DECL_UID (sym));
    }

  /* Rebuild the may-alias array for TAG.  */
  bitmap_copy (MTAG_ALIASES (tag), new_aliases);
}

This happily separates the zero-offset SFT from the other SFTs, keeping
some in the NMT and puts some other in the MPT.

So, what's the fix?  Never divorce SFTs of a single variable to different
(or no) partitions?  Duplicate the zero-offset SFT in both the MPT and
the NMT?  Install the fix to not assume the zero-offset SFT is in the
set of aliases?

One working patch/workaround:

http://gcc.gnu.org/ml/gcc-patches/2007-10/msg01377.html

And another one:

http://gcc.gnu.org/ml/gcc-patches/2007-10/msg01398.html


unassigning - I neither feel responsible nor competent enough to fix this design
issue.

Subject: Bug 33870

Author: rguenth
Date: Sat Oct 27 11:10:09 2007
New Revision: 129675

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=129675
Log:
2007-10-27  Richard Guenther  <rguenther@suse.de>

	PR tree-optimization/33870
	* tree-ssa-operands.c (add_vars_for_offset): Reduce code
	duplication.  Remove redundant call to access_can_touch_variable.
	(add_vars_for_bitmap): New helper for recursing over MPT contents.
	(add_virtual_operand): Use it.

	* gcc.dg/tree-ssa/alias-15.c: New testcase.
	* gcc.c-torture/execute/pr33870.c: Likewise.

Added:
    trunk/gcc/testsuite/gcc.c-torture/execute/pr33870.c
    trunk/gcc/testsuite/gcc.dg/tree-ssa/alias-15.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-ssa-operands.c

Fixed.

Reopen.

Assign to Diego.

Subject: Bug 33870

Author: rguenth
Date: Mon Oct 29 21:47:05 2007
New Revision: 129738

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=129738
Log:
2007-10-29  Richard Guenther  <rguenther@suse.de>

	PR tree-optimization/33870
	* tree-ssa-operands.c (add_vars_for_offset): Remove mpt_vars parameter.
	(add_virtual_operand): Do not recurse into MPTs looking for pointed-to
	SFTs.

	* gcc.c-torture/execute/pr33870.x: XFAIL testcase for -O2 and -Os.

Added:
    trunk/gcc/testsuite/gcc.c-torture/execute/pr33870.x
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-ssa-operands.c

Working on a fix.

Subject: Bug 33870

Author: dnovillo
Date: Thu Nov  8 00:01:38 2007
New Revision: 129976

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=129976
Log:

	PR 33870
	* tree.h (struct tree_struct_field_tag): Add field in_nested_struct.
	(SFT_IN_NESTED_STRUCT): Define.
	* tree-dfa.c (dump_subvars_for): Show offset of each
	sub-var.
	* tree-flow.h (struct fieldoff): Add field in_nested_struct.
	* tree-ssa-structalias.c (struct variable_info): Likewise.
	(push_fields_onto_fieldstack): If OFFSET is positive,
	set in_nested_struct.
	(create_variable_info_for): Copy setting of
	in_nested_struct from the field offset object.
	(set_uids_in_ptset): Set SFT_IN_NESTED_STRUCT from the
	variable info object.
	* tree-ssa-operands.c (add_vars_for_offset): If VAR
	belongs to a nested structure, adjust OFFSET by
	SFT_OFFSET(VAR).

testsuite/ChangeLog

	* gcc.c-torture/execute/pr33870.x: Remove.



Removed:
    trunk/gcc/testsuite/gcc.c-torture/execute/pr33870.x
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-dfa.c
    trunk/gcc/tree-flow.h
    trunk/gcc/tree-ssa-operands.c
    trunk/gcc/tree-ssa-structalias.c
    trunk/gcc/tree.h

Fixed.  http://gcc.gnu.org/ml/gcc-patches/2007-11/msg00374.html

Re-opening, the following testcase still fails (the original underlying problem
has not been fully fixed).


extern void abort (void);

typedef struct PgHdr PgHdr;
typedef unsigned char u8;
struct PgHdr {
int y;
struct {
 unsigned int pgno;
 PgHdr *pNextHash, *pPrevHash;
 PgHdr *pNextFree, *pPrevFree;
 PgHdr *pNextAll;
 u8 inJournal;
 short int nRef;
 PgHdr *pDirty, *pPrevDirty;
 unsigned int notUsed;
} x;
};
volatile PgHdr **xx;
static inline PgHdr *merge_pagelist(PgHdr *pA, PgHdr *pB)
{
 PgHdr result;
 PgHdr *pTail;
 xx = &result.x.pDirty;
 pTail = &result;
 while( pA && pB ){
   if( pA->x.pgno<pB->x.pgno ){
     pTail->x.pDirty = pA;
     pTail = pA;
     pA = pA->x.pDirty;
   }else{
     pTail->x.pDirty = pB;
     pTail = pB;
     pB = pB->x.pDirty;
   }
 }
 if( pA ){
   pTail->x.pDirty = pA;
 }else if( pB ){
   pTail->x.pDirty = pB;
 }else{
   pTail->x.pDirty = 0;
 }
 return result.x.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->x.pDirty;
   p->x.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;
       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].x.pgno = 5;
 a[0].x.pDirty = &a[1];
 a[1].x.pgno = 4;
 a[1].x.pDirty = &a[2];
 a[2].x.pgno = 1;
 a[2].x.pDirty = &a[3];
 a[3].x.pgno = 3;
 a[3].x.pDirty = 0;
 p = sort_pagelist (&a[0]);
 if (p->x.pDirty == p)
   abort ();
 return 0;
}

Subject: Bug 33870

Author: dnovillo
Date: Tue Nov 13 15:20:40 2007
New Revision: 130141

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=130141
Log:

	pr 33870
	* tree.h (strcut tree_memory_tag): add field unpartitionable.
	remove field in_nested_struct.
	(struct tree_struct_field_tag): add field nesting_level.
	(sft_in_nested_struct): remove.
	(sft_nesting_level): define.
	(sft_unpartitionable_p): define.
	* tree-ssa-alias.c (mem_sym_score): if mp->var is not
	partitionable, return long_max.
	(compute_memory_partitions): do not partition sfts marked
	unpartitionable.
	(create_sft): add argument nesting_level.  set
	sft_nesting_level with it.  update all users.
	(create_overlap_variables_for): show nesting level.
	* tree-dfa.c (dump_subvars_for): likewise.
	(dump_variable): likewise.
	show whether the sft is partitionable or not.
	* tree-flow.h (struct fieldoff): remove field
	in_nested_struct.
	add field nesting_level.
	* tree-ssa-structalias.c (struct variable_info): remove
	field in_nested_struct.
	(push_fields_onto_fieldstack): add argument
	nesting_level.  update all users.
	update documentation.
	update pair->nesting_level with nesting_level.
	make recursive calls with nesting_level + 1.
	(set_uids_in_ptset): if an sft is added to the points-to
	set, mark it as unpartitionable.
	* tree-ssa-operands.c (ref_nesting_level): new.
	(add_vars_for_offset): call it.
	add argument full_ref.  update
	callers.
	if var is inside a nested structure and the nesting level
	of full_ref is lower than the nesting level of var,
	adjust offset by the offset of var.

testsuite/ChangeLog
	
	PR 33870
	* gcc.c-torture/execute/pr33870-1.c: New test.
	* gcc.dg/tree-ssa/alias-16.c: New test.


Added:
    trunk/gcc/testsuite/gcc.c-torture/execute/pr33870-1.c
    trunk/gcc/testsuite/gcc.dg/tree-ssa/alias-16.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-dfa.c
    trunk/gcc/tree-flow.h
    trunk/gcc/tree-ssa-alias.c
    trunk/gcc/tree-ssa-operands.c
    trunk/gcc/tree-ssa-structalias.c
    trunk/gcc/tree.h

Fixed.  http://gcc.gnu.org/ml/gcc-patches/2007-11/msg00719.html

Re-opening to not forget about the follow-up patch.

Which I have.

Subject: Bug 33870

Author: rguenth
Date: Fri Nov 16 14:40:04 2007
New Revision: 130231

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=130231
Log:
2007-11-16  Richard Guenther  <rguenther@suse.de>

	PR tree-optimization/33870
	* tree.h (struct tree_memory_tag): Add base_for_components flag.
	(struct tree_struct_field_tag): Remove nesting_level field.
	(SFT_NESTING_LEVEL): Remove.
	(SFT_BASE_FOR_COMPONENTS_P): Add.
	* tree-flow.h (struct fieldoff): Remove nesting_level field.  Add
	base_for_components flag.
	(push_fields_onto_fieldstack): Remove nesting_level parameter.
	* tree-ssa-alias.c (create_sft): Likewise.  Add base_for_components
	parameter.
	(create_overlap_variables_for): Deal with it.
	* tree-dfa.c (dump_subvars_for): Likewise.
	(dump_variable): Likewise.
	* tree-ssa-structalias.c (push_fields_onto_fieldstack): Likewise.
	Set base_for_components for first elements of sub-structures.
	(create_variable_info_for): Handle base_for_components.
	(set_uids_in_ptset): Always set SFT_UNPARTITIONABLE_P for
	pointed-to SFTs if SFT_BASE_FOR_COMPONENTS_P is set.
	* tree-ssa-operands.c (ref_nesting_level): Remove.
	(add_vars_for_offset): Remove full_ref parameter, always add
	the offset of the pointed-to SFT.
	(add_virtual_operand): Adjust for changed signature of
	add_vars_for_offset.

	* gcc.dg/torture/pr33870.c: New testcase.

Added:
    trunk/gcc/testsuite/gcc.dg/torture/pr33870.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-dfa.c
    trunk/gcc/tree-flow.h
    trunk/gcc/tree-ssa-alias.c
    trunk/gcc/tree-ssa-operands.c
    trunk/gcc/tree-ssa-structalias.c
    trunk/gcc/tree.h

Fixed.  Again.