From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <gcc-bugs-return-346398-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Received: (qmail 8434 invoked by alias); 7 Feb 2011 14:50:56 -0000
Received: (qmail 8422 invoked by uid 22791); 7 Feb 2011 14:50:55 -0000
X-SWARE-Spam-Status: No, hits=-2.6 required=5.0	tests=ALL_TRUSTED,AWL,BAYES_00
X-Spam-Check-By: sourceware.org
Received: from localhost (HELO gcc.gnu.org) (127.0.0.1)    by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Mon, 07 Feb 2011 14:50:48 +0000
From: "rguenth at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [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
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: tree-optimization
X-Bugzilla-Keywords: ice-on-valid-code
X-Bugzilla-Severity: normal
X-Bugzilla-Who: rguenth at gcc dot gnu.org
X-Bugzilla-Status: ASSIGNED
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: rguenth at gcc dot gnu.org
X-Bugzilla-Target-Milestone: 4.6.0
X-Bugzilla-Changed-Fields:
Message-ID: <bug-47615-4-NqacqYUTo8@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-47615-4@http.gcc.gnu.org/bugzilla/>
References: <bug-47615-4@http.gcc.gnu.org/bugzilla/>
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
Content-Type: text/plain; charset="UTF-8"
MIME-Version: 1.0
Date: Mon, 07 Feb 2011 15:21:00 -0000
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
X-SW-Source: 2011-02/txt/msg00864.txt.bz2

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 ...