GCC Bugzilla has been upgraded from version 4.4.9 to 5.0rc3. If you see any problem, please report it to bug 64968.
Bug 33870 - [4.3 Regression] miscompiles sqlite
Summary: [4.3 Regression] miscompiles sqlite
Status: RESOLVED FIXED
Alias: None
Product: gcc
Classification: Unclassified
Component: tree-optimization (show other bugs)
Version: 4.3.0
: P1 major
Target Milestone: 4.3.0
Assignee: Richard Biener
URL:
Keywords: alias, wrong-code
Depends on: 34148 36519
Blocks: 33974 34093 34683
  Show dependency treegraph
 
Reported: 2007-10-23 13:00 UTC by Richard Biener
Modified: 2008-06-13 09:15 UTC (History)
7 users (show)

See Also:
Host:
Target:
Build:
Known to work: 4.2.2 4.1.3
Known to fail:
Last reconfirmed: 2007-10-23 16:01:55


Attachments
full checking patch (793 bytes, text/plain)
2007-10-23 21:27 UTC, Richard Biener
Details

Note You need to log in before you can comment on or make changes to this bug.
Description Richard Biener 2007-10-23 13:00:58 UTC
The following aborts (or segfaults, depending on the size of PgHdr) with
-O2.

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, *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;
}
Comment 1 Richard Biener 2007-10-23 13:16:12 UTC
Also fails with -O --param max-aliased-vops=500 (the -O2 setting)
Comment 2 Richard Biener 2007-10-23 13:48:50 UTC
Janis, can you hunt this?  (in case it also fails for you that is)
Comment 3 H.J. Lu 2007-10-23 13:54:30 UTC
I started regression hunt. It is introduced between 127611 and 127769.
Comment 4 H.J. Lu 2007-10-23 14:24:57 UTC
Revision 127629

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

introduced this regression.
Comment 5 Richard Biener 2007-10-23 14:26:35 UTC
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.
Comment 6 Richard Biener 2007-10-23 14:38:58 UTC
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.
Comment 7 Richard Biener 2007-10-23 16:01:54 UTC
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.
Comment 8 Richard Biener 2007-10-23 21:26:46 UTC
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)));
            }
Comment 9 Richard Biener 2007-10-23 21:27:23 UTC
Created attachment 14403 [details]
full checking patch
Comment 10 Richard Biener 2007-10-23 21:28:19 UTC
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));
                }
            }
Comment 11 Richard Biener 2007-10-23 21:52:20 UTC
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?
Comment 12 Richard Biener 2007-10-24 10:13:31 UTC
One working patch/workaround:

http://gcc.gnu.org/ml/gcc-patches/2007-10/msg01377.html
Comment 13 Richard Biener 2007-10-24 11:56:11 UTC
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.
Comment 14 Richard Biener 2007-10-27 11:10:24 UTC
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

Comment 15 Richard Biener 2007-10-27 11:18:13 UTC
Fixed.
Comment 16 Richard Biener 2007-10-29 21:44:21 UTC
Reopen.
Comment 17 Richard Biener 2007-10-29 21:44:58 UTC
Assign to Diego.
Comment 18 Richard Biener 2007-10-29 21:47:53 UTC
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

Comment 19 Diego Novillo 2007-11-02 15:31:19 UTC
Working on a fix.
Comment 20 Diego Novillo 2007-11-08 00:01:57 UTC
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

Comment 21 Diego Novillo 2007-11-08 00:26:25 UTC
Fixed.  http://gcc.gnu.org/ml/gcc-patches/2007-11/msg00374.html
Comment 22 Richard Biener 2007-11-12 12:04:09 UTC
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;
}
Comment 23 Diego Novillo 2007-11-13 15:20:57 UTC
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

Comment 24 Diego Novillo 2007-11-13 15:47:12 UTC
Fixed.  http://gcc.gnu.org/ml/gcc-patches/2007-11/msg00719.html
Comment 25 Richard Biener 2007-11-16 12:28:38 UTC
Re-opening to not forget about the follow-up patch.
Comment 26 Richard Biener 2007-11-16 12:29:08 UTC
Which I have.
Comment 27 Richard Biener 2007-11-16 14:40:16 UTC
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

Comment 28 Richard Biener 2007-11-16 14:41:06 UTC
Fixed.  Again.