Preprocessed source stored into /tmp/ccXWRPxa.out file, please attach this to your bugreport.

Created attachment 29682 [details]
Preprocessed source

Sorry, looks like it was too big.  Here it is compressed.

markus@x4 tmp % cat test.ii
template<typename>struct A;
template<typename _Tp>A<_Tp>operator/(A<_Tp>, A<_Tp>& p2)
{
  A<_Tp> a;
  a /= p2;
  return a;
}

template<typename _Tp>bool operator!=(A<_Tp>& p1, A<_Tp>&)
{
  return p1.real();
}

template<>struct A<double>
{
  double& real()
  {
    return __real__ _M_value;
  }

  template<typename _Tp>void operator/=(A<_Tp>&)
  {
    _M_value /= 10;
  }

  _Complex double _M_value;
};

template<class T>class B {
  T *buf;

public:

  B(int, bool);
  T& operator[](int)
  {
    return buf[0];
  }
};

struct C
{
  C(const int&);
  typedef A<double>Ty;
  typedef B<Ty>    DataT;
  A<double>zero;
  enum InitType
  { NOZERO };
  virtual C* DivInv(C *);
};
template<class Sp>class D : Sp {
  typedef typename Sp::Ty    Ty;
  typedef typename Sp::DataT DataT;
  DataT dd;

public:

  D(const int&, C::InitType);
  Ty& operator[](int)
  {
    return dd[0];
  }

  D* DivInv(C *);
};

template<class Sp>D<Sp> *D<Sp>::DivInv(C *)
{
  if ((*this)[0] != this->zero) (*this)[0] = (*static_cast<D *>(0))[0] /
                                             (*this)[0];
  else (*this)[0] = (*static_cast<D *>(0))[0];
  return 0;
}

D<C> *b = new D<C>(0, C::NOZERO);
template<class Sp>D<Sp>::D(const int&, C::InitType) : Sp(0), dd(0, 0)
{}

markus@x4 tmp % c++ -Wextra -Wall -c -O3 test.ii
test.ii: In member function ‘D<Sp>* D<Sp>::DivInv(C*) [with Sp = C]’:
test.ii:67:26: internal compiler error: in find_lattice_value, at tree-complex.c:151
 template<class Sp>D<Sp> *D<Sp>::DivInv(C *)
                          ^

Reduced testcase (-O3):
struct A { _Complex double a; };
struct B { A *b; void foo (void *); };

A
operator / (A x, A y)
{
  A r;
  r.a = x.a / y.a;
  return r;
}

void
B::foo (void *x)
{
  if (__real__ b[0].a)
    b[0] = (static_cast <B *>(x))->b[0] / b[0];
  else
    b[0] = (static_cast <B *>(x))->b[0];
}

The ICE is actually
pr56635.C: In member function ‘void B::foo(void*)’:
pr56635.C:13:1: error: invalid PHI argument
 B::foo (void *x)
 ^
MEM[(const struct A &)_9]
pr56635.C:13:1: error: incompatible types in PHI argument 1
complex double

const struct A

cstore_10 = PHI <_11(3), MEM[(const struct A &)_9](4)>

pr56635.C:13:1: internal compiler error: verify_gimple failed

and looks like cselim bug.
Started with http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=186501 but guess it just has been latent before that.

Even more reduced (-O3):
struct A { _Complex double a; };

void
foo (A **x, A **y)
{
  A r;
  if (__real__ x[0]->a)
    {
      r.a = y[0]->a / x[0]->a;
      **x = r;
    }
  else
    **x = **y;
}

Created attachment 29688 [details]
gcc48-pr56635.patch

Untested fix.

Author: jakub
Date: Mon Mar 18 13:01:49 2013
New Revision: 196781

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=196781
Log:
	PR tree-optimization/56635
	* fold-const.c (operand_equal_p): For MEM_REF and TARGET_MEM_REF,
	require types_compatible_p types.

	* g++.dg/torture/pr56635.C: New test.

Added:
    trunk/gcc/testsuite/g++.dg/torture/pr56635.C
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/fold-const.c
    trunk/gcc/testsuite/ChangeLog

Author: jakub
Date: Wed Mar 20 08:40:08 2013
New Revision: 196808

URL: http://gcc.gnu.org/viewcvs?rev=196808&root=gcc&view=rev
Log:
	PR tree-optimization/56635
	* tree-ssa-phiopt.c (cond_if_else_store_replacement_1): Give up
	if lhs of then_assign and else_assign don't have compatible types.

	* g++.dg/torture/pr56635.C: New test.

Added:
    branches/gcc-4_8-branch/gcc/testsuite/g++.dg/torture/pr56635.C
Modified:
    branches/gcc-4_8-branch/gcc/ChangeLog
    branches/gcc-4_8-branch/gcc/testsuite/ChangeLog
    branches/gcc-4_8-branch/gcc/tree-ssa-phiopt.c

Fixed.