Created attachment 13063 [details]
C++ source code

Reducing ...

Confirmed, reduced testcase as far as I can do it:
typedef struct rxvt_term *rxvt_t;
struct rxvt_salloc {
   	struct chain {
		struct chain *next;
	};
  	chain *firstline;
	unsigned int firstfree;
   	inline void alloc ();
};
struct rxvt_perl_interp {
	bool invoke (rxvt_term *term);
};
extern struct rxvt_perl_interp rxvt_perl;
struct rxvt_term   {
	int term_start;
	int *row_buf;
 	rxvt_salloc *talloc;
 	void scr_reset (int pend, int qlines);
};
inline void rxvt_salloc::alloc ()
{
 	if (firstline)
		firstline = firstline->next;
 	else 	{
		if (firstfree > 65536)
			firstfree = sizeof (chain);
		firstfree += firstfree;
	}
}
void rxvt_term::scr_reset (int pend, int qlines) {
	do 	{
		int *qline;
		for (int qrow = term_start; qlines--; qrow++)
		{
			qline = row_buf + qrow;
			talloc->alloc ();
			talloc->alloc ();
		}
		qline[0]  &= ~0x0001;
		talloc->alloc ();
		talloc->alloc ();
	} 	while (term_start != pend);
 	rxvt_perl.invoke (this);
}

It seems to be a problem with ssa-edge simulation ordering.  We have

# SMT.6_95 = VDEF <SMT.6_60>
# SMT.8_96 = VDEF <SMT.8_70>
this_22->firstfree = D.2527_46;

in particular, adding only the first output to simulate

      /* Note that for propagation purposes, we are only interested in
         visiting statements that load the exact same memory reference
         stored here.  Those statements will have the exact same list
         of virtual uses, so it is enough to set the output of this
         statement to be its first virtual definition.  */
      *output_p = first_vdef (stmt);
      if (changed)
        {
          if (val.lattice_val == VARYING)
            retval = SSA_PROP_VARYING;

will cause a missed propagation of the new lattice value to PHI results.
Another point is that get_value_loaded_by will return NULL for the two
VOPs where one has a CONSTANT and one a VARYING value and so we'll call
evaluate_stmt on the stmt which will return UNDEFINED which causes us to
go back from VARYING to UNDEFINED.  Boom.

Sth. like the following fixes it (note 'VARYING' is unknown to tree-ssa-propagate.c):

Index: tree-ssa-propagate.c
===================================================================
*** tree-ssa-propagate.c        (revision 122127)
--- tree-ssa-propagate.c        (working copy)
*************** get_value_loaded_by (tree stmt, prop_val
*** 835,850 ****
    tree vuse;
    prop_value_t *prev_val = NULL;
    prop_value_t *val = NULL;
  
    FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, i, SSA_OP_VIRTUAL_USES)
      {
        val = &values[SSA_NAME_VERSION (vuse)];
        if (prev_val && prev_val->value != val->value)
!       return NULL;
!       prev_val = val;
      }
  
!   return val;
  }
  
  
--- 841,860 ----
    tree vuse;
    prop_value_t *prev_val = NULL;
    prop_value_t *val = NULL;
+   bool valid = true;
  
+   /* Make sure to set the result to varying if any of the operands is
+      varying.  */
    FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, i, SSA_OP_VIRTUAL_USES)
      {
        val = &values[SSA_NAME_VERSION (vuse)];
        if (prev_val && prev_val->value != val->value)
!       valid = false;
!       if (!prev_val || prev_val->lattice_val < val->lattice_val)
!         prev_val = val;
      }
  
!   return (valid || prev_val->lattice_val == 3) ? prev_val : NULL;
  }
  
  
Index: tree-ssa-ccp.c
===================================================================
*** tree-ssa-ccp.c      (revision 122127)
--- tree-ssa-ccp.c      (working copy)
*************** visit_assignment (tree stmt, tree *outpu
*** 1208,1215 ****
        prop_value_t *nval = get_value_loaded_by (stmt, const_val);
  
        if (nval
!         && nval->mem_ref
!         && operand_equal_p (nval->mem_ref, rhs, 0))
        val = *nval;
        else
        val = evaluate_stmt (stmt);
--- 1208,1216 ----
        prop_value_t *nval = get_value_loaded_by (stmt, const_val);
  
        if (nval
!         && ((nval->mem_ref
!              && operand_equal_p (nval->mem_ref, rhs, 0))
!             || nval->lattice_val == VARYING))
        val = *nval;
        else
        val = evaluate_stmt (stmt);

We can also simply check before the fact like

Index: tree-ssa-ccp.c
===================================================================
*** tree-ssa-ccp.c      (revision 122127)
--- tree-ssa-ccp.c      (working copy)
*************** visit_assignment (tree stmt, tree *outpu
*** 1212,1218 ****
          && operand_equal_p (nval->mem_ref, rhs, 0))
        val = *nval;
        else
!       val = evaluate_stmt (stmt);
      }
    else
      /* Evaluate the statement.  */
--- 1212,1226 ----
          && operand_equal_p (nval->mem_ref, rhs, 0))
        val = *nval;
        else
!       {
!         val = evaluate_stmt (stmt);
!         /* We need to be careful not to drop back to UNDEFINED from
!            VARYING.  This can happen because we only re-process the
!            first virtual operand of a store.  */
!         if (val.lattice_val == UNDEFINED
!             && get_value (lhs)->lattice_val > UNDEFINED)
!           val.lattice_val = VARYING;
!       }
      }
    else
      /* Evaluate the statement.  */

still not simulating the ssa edges for the other virtual operands does not
seem to be the best approach.

*** Bug 31926 has been marked as a duplicate of this bug. ***

This testcase works on the trunk on, it was fixed between 20070513 and 20070531.  I will check on the other testcase too.

The following simplified testcase still crashes on mainline when compiled
with "-O2":

==============================
struct A
{
  int i, *p;
  A* a;

  void foo()
  {
    if (p)
      p++;
    else
    {
      if (i)
        i = 1;
      i++;
    }
  }

  A();
};

A::A()
{
  int j;
  A* q;

  while (j)
  {
    j--;
    while (j--)
    {
      q = this;
      a->foo();
      a->foo();
    }

    q->a++;
    a->foo();
    a->foo();
  }

  A b;
}
==============================

This testcase needs a rereduction, the two reductions here work now.
Reducing now.

Here is a new reduced testcase (compile at -O3 -fno-strict-aliasing):
struct rxvt_salloc {
  char *firstblock;
  unsigned int firstfree;
};
struct line_t {
   unsigned int *t;
   unsigned int f;
};
struct rxvt_salloc *talloc;
struct line_t *row_buf;
static inline unsigned * alloc (struct rxvt_salloc *this1)
{
  void *r;
  if (this1->firstfree > 65536)
    this1->firstfree = 4;
  r = (void *) ((char *)this1->firstblock + this1->firstfree);
  return (unsigned *)r;
}
void
scr_reset (int qlines)
{
  struct line_t *qline;
  int qrow;
  for (qrow = 0; qlines--; qrow++)
      (qline = row_buf)->t = alloc (talloc);
  qline->f &= ~0x0001;
  qline->t = alloc (talloc);
}

> Here is a new reduced testcase (compile at -O3 -fno-strict-aliasing):
One more note, this testcase ICEs with the C front-end now :).

You can also now invoke it just with "-O1 -ftree-store-ccp" :).

Here's an even smaller testcase:

=============================
int *p;

inline int foo(int *q)
{
  if (*q)
    *q = 0;
  return *q;
}

void bar(int *r, int i)
{
  int *s;
  while (--i)
    *(s = r) = foo(p);
  ++(*s);
  *s = foo(p);
}
==============================

*** Bug 32607 has been marked as a duplicate of this bug. ***

*** Bug 31926 has been marked as a duplicate of this bug. ***

A regression hunt on powerpc-linux using the testcase from comment #3 identified this patch:

    http://gcc.gnu.org/viewcvs?view=rev&rev=119502

    r119502 | dberlin | 2006-12-04 19:07:05 +0000 (Mon, 04 Dec 2006)

Can't reproduce any ICE on {x86_64,i686,ppc}-linux with here referenced testcases at various flags (including e.g. -O3 -fno-strict-aliasing -fno-tree-vectorize to make it more similar to the old setup).
The #c1 testcase went away on x86_64-linux between 200708{20,30}, the #c13
testcase between 200709{07,11}.

The dups also all work.  Let's close this as fixed then.

The testcase that was broken longest is #c3, which got fixed by
http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=130222