Blindly ignoring MEM_EXPR or other attributes looks very wrong to me.
Guess in some cases it could return true even when MEM_ATTRS aren't identical,
but they'd need to have the same behavior during alias analysis at least, or
one of the attrs would need to be a superset of the other ones (but then it would need to be ensured that the callers pick up the superset instead of
the other MEM_ATTRS).

On this particular testcase, exp_equiv_p returns 1 for_gcse on
MEM_EXPRs c_4(D)->s1+0 and c_1->s1+0 (other attributes are the same).
c_1 is:
# c_1 = PHI <[rh712480.i : 41:7] [rh712480.i : 41] &e(2), c_4(D)(4), c_4(D)(5)>
and e is an automatic variable.  If GCSE thinks those two MEMs are
equivalent (one, c_4(D) based is present e.g. in the else branch of the if (c == 0) stmt, c_1 based afterwards) and merges those two into the one that has c_4(D)->s1 in it instead of c_1->s1, then aliasing oracle will see c_4(D)->s1
MEM_EXPR and e.s1 MEM_EXPR and will say that they can't alias (while for c_1->s1 and e.s1 they could and do).
I think such a change was ok in 4.4 and earlier era, where alias oracle hasn't been used to disambiguate RTL MEMs, but there also it would be NULL -> s1
rather than c_1 -> s1 etc.

Perhaps we should have some exceptions where we allow different MEM_ATTRS, but they need to be carefully chosen.  E.g. if both refs are indirect refs and are similar, with the same points-to info, it would be ok.

  if (MEM_VOLATILE_P (x) || MEM_VOLATILE_P (y))
    return 0;

  if (MEM_ATTRS (x) != MEM_ATTRS (y) && mem_attrs_equiv_p (x, y))
    return 0;

where mem_attrs_equiv_p would call ao_ref_from_mem on both x and y,
if at least one of them returns false, fail, compare all integer fields for
equality (alias sets using ao_ref_base_alias_set/ao_ref_alias_set) and compare base kinds, for indirect we could check for same type and same points-to info (couldn't find a points-to set comparison function, e.g. for pt->vars can just pointer equality be tested or does it need bitmap_equal_p?).

Perhaps, if the tests are more expensive, case MEM: if (for_gcse) could
first do the cheap tests, then
  if (!exp_equiv_p (XEXP (x, 0), XEXP (y, 0), validate, 1))
    return 0;
then do the more expensive tests and then just return 1; instead of falling
through into the generic code.

Case which I agree would be nice to say exp_equiv_p is true is e.g.:
  if (c->s1 == 0)
    c++;
  else
    foo (1, 0, c->s1, c->s2);
  foo (2, 0, c->s1, c->s2);
Here e.g. c_4(D)->s1 and c_1->s1 aren't equal MEM_EXPRs, but they have the same SSA_VAR_NAME (not sure if we need to check it, perhaps for restrict?), pt->vars
and all other pt members are the same too, so I think both MEM_ATTRS should behave the same in the alias oracle.

Created attachment 24510 [details]
gcc46-pr49390.patch

Untested patch.  Richard, what do you think about it?
Bernd, do you still have some testcases around which got suboptimal code generated before your reversion?

Author: jakub
Date: Tue Jun 14 14:59:52 2011
New Revision: 175023

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=175023
Log:
	PR rtl-optimization/49390
	Revert:
	2010-06-29  Bernd Schmidt  <bernds@codesourcery.com>

	* cse.c (exp_equiv_p): For MEMs, if for_gcse, only compare
	MEM_ALIAS_SET.

	* gcc.c-torture/execute/pr49390.c: New test.

Added:
    trunk/gcc/testsuite/gcc.c-torture/execute/pr49390.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/cse.c
    trunk/gcc/testsuite/ChangeLog

Author: jakub
Date: Tue Jun 14 15:01:10 2011
New Revision: 175024

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=175024
Log:
	PR rtl-optimization/49390
	Revert:
	2010-06-29  Bernd Schmidt  <bernds@codesourcery.com>

	* cse.c (exp_equiv_p): For MEMs, if for_gcse, only compare
	MEM_ALIAS_SET.

	* gcc.c-torture/execute/pr49390.c: New test.

Added:
    branches/gcc-4_6-branch/gcc/testsuite/gcc.c-torture/execute/pr49390.c
Modified:
    branches/gcc-4_6-branch/gcc/ChangeLog
    branches/gcc-4_6-branch/gcc/cse.c
    branches/gcc-4_6-branch/gcc/testsuite/ChangeLog

Fixed.