[Bug tree-optimization/47615] [4.6 Regression] ICE: too deep recursion in phi_translate/phi_translate_1 with -ftree-pre -fno-tree-fre -fno-tree-sra

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=47615

--- Comment #3 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-02-07 14:50:43 UTC ---
;; basic block 2, loop depth 0, count 0
;; prev block 0, next block 11
;; pred:       ENTRY [100.0%]  (fallthru,exec)
;; succ:       11 [50.0%]  (true,exec) 3 [50.0%]  (false,exec)
<bb 2>:
p_y_5 = p_nd_2(D)->m_p_parent;
p_y_5->m_p_right = p_nd_2(D);
D.3165.m_p_nd = p_nd_2(D);
node_it = D.3165;
if (D.3177_7(D) != 0)
  goto <bb 11>;
else
  goto <bb 3>;

...

;; basic block 5, loop depth 0, count 0
;; prev block 12, next block 6
;; pred:       4 [61.0%]  (false,exec)
;; succ:       6 [100.0%]  (fallthru,exec)
<bb 5>:
D.3176_15 = r_child_it.m_p_nd;
r_rank_16 = MEM[(const long unsigned int &)D.3176_15 + 16];

;; basic block 6, loop depth 0, count 0
;; prev block 5, next block 13
;; pred:       12 [100.0%]  (fallthru) 5 [100.0%]  (fallthru,exec)
;; succ:       13 [50.0%]  (true,exec) 7 [50.0%]  (false,exec)
<bb 6>:
# r_rank_19 = PHI <1(12), r_rank_16(5)>
D.3178_17 = node_it.m_p_nd;
D.3184_20 = r_rank_19 + l_rank_18;
MEM[(long unsigned int &)D.3178_17 + 16] = D.3184_20;
D.3160_6 = p_nd_2(D)->m_p_parent;
D.3189.m_p_nd = D.3160_6;
node_it = D.3189;
if (D.3201_21(D) != 0)
  goto <bb 13>;
else
  goto <bb 7>;

<bb 13>:
  goto <bb 8>;

<bb 7>:
  # VUSE <.MEM_47>
  D.3199_23 = l_child_it.m_p_nd;
  # VUSE <.MEM_47>
  l_rank_24 = MEM[(const long unsigned int &)D.3199_23 + 16];

<bb 8>:
  # l_rank_32 = PHI <1(13), l_rank_24(7)>
  # VUSE <.MEM_47>
  D.3206_25 = node_it.m_p_nd;
  # VUSE <.MEM_47>
  D.3207_26 = D.3206_25->m_p_right;


translating
  {component_ref<m_p_right>,mem_ref<0B>,p_y_5}@.MEM_35
to BB 5 results in translating
  {component_ref<m_p_parent>,mem_ref<0B>,p_nd_2(D)}@.MEM_3(D)
which is the leader for p_y_5 which results in translating
  {component_ref<m_p_right>,mem_ref<0B>,p_y_5}@.MEM_35
which is the leader for p_nd_2(D)

and we end up with a cycle.  D.3206_25 is value-numbered to p_y_5
by SCCVN which looks ok.

The problem seems to be that we have a cycle for leaders. Simply caused by

p_y_5 = p_nd_2(D)->m_p_parent;
p_y_5->m_p_right = p_nd_2(D);

what seems bogus is that p_nd_2(D) isn't the leader for itself but
p_y_5->m_p_right is.

The issue is that we look at the intersection of the current ANTIC set

{ {component_ref<m_p_parent>,mem_ref<0B>,p_nd_2(D)}@.MEM_3(D) (0005), l_rank_18
(0012), r_rank_19 (0013), {plus_expr,l_rank_18,r_rank_19} (0014),
{component_ref<m_p_right>,mem_ref<0B>,p_y_5}@.MEM_35 (0002) }

with the expression set of the value

{ p_nd_2(D) (0002), {component_ref<m_p_nd>,D.3165}@.MEM_37 (0002), D.3182_11
(0002), D.3178_17 (0002), D.3207_26 (0002),
{component_ref<m_p_right>,mem_ref<0B>,p_y_5}@.MEM_35 (0002),
{component_ref<m_p_nd>,D.3205}@.MEM_49 (0002), D.3200_29 (0002) }

and the only common one is {component_ref<m_p_right>,mem_ref<0B>,p_y_5}@.MEM_35
(0002), p_nd_2(D) isn't ANTIC itself (which is what the referenced patch
changed - previously we'd recognized that the original reference we
now try to translate is equal to p_nd_2(D)).

It looks like fixing this disparity is the easiest thing we can do ...