public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug tree-optimization/20640] New: [4.0 Regression] ICE on NULL PHI_ARG_DEF
@ 2005-03-25 20:57 jakub at gcc dot gnu dot org
2005-03-25 20:58 ` [Bug tree-optimization/20640] " jakub at gcc dot gnu dot org
` (13 more replies)
0 siblings, 14 replies; 15+ messages in thread
From: jakub at gcc dot gnu dot org @ 2005-03-25 20:57 UTC (permalink / raw)
To: gcc-bugs
static int a = 0;
extern int foo (void);
extern int *bar (void) __attribute__ ((__const__));
void
test (int x)
{
int b = 10;
while (foo () == -1 && *bar () == 4 && b > 0)
--b;
a = x;
}
ICEs on i386 and x86_64 with -O2 -funroll-loops (and e.g. -O3
-fomit-frame-pointer -funroll-loops too).
The ICE is in dse2 pass, when compute_immediate_uses_for_phi sees a PHI node
with NULL 3rd argument:
# aD.1460_16 = PHI <aD.1460_13(2), aD.1460_17(3), (1)>;
Before cddce pass that PHI node looked correctly:
# aD.1460_16 = PHI <aD.1460_13(2), aD.1460_17(4), aD.1460_11(5)>;
--
Summary: [4.0 Regression] ICE on NULL PHI_ARG_DEF
Product: gcc
Version: 4.0.0
Status: UNCONFIRMED
Keywords: ice-on-valid-code
Severity: critical
Priority: P2
Component: tree-optimization
AssignedTo: unassigned at gcc dot gnu dot org
ReportedBy: jakub at gcc dot gnu dot org
CC: gcc-bugs at gcc dot gnu dot org
GCC target triplet: i386-linux, x86_64-linux
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=20640
^ permalink raw reply [flat|nested] 15+ messages in thread
* [Bug tree-optimization/20640] [4.0 Regression] ICE on NULL PHI_ARG_DEF
2005-03-25 20:57 [Bug tree-optimization/20640] New: [4.0 Regression] ICE on NULL PHI_ARG_DEF jakub at gcc dot gnu dot org
@ 2005-03-25 20:58 ` jakub at gcc dot gnu dot org
2005-03-25 21:07 ` pinskia at gcc dot gnu dot org
` (12 subsequent siblings)
13 siblings, 0 replies; 15+ messages in thread
From: jakub at gcc dot gnu dot org @ 2005-03-25 20:58 UTC (permalink / raw)
To: gcc-bugs
--
What |Removed |Added
----------------------------------------------------------------------------
Target Milestone|--- |4.0.0
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=20640
^ permalink raw reply [flat|nested] 15+ messages in thread
* [Bug tree-optimization/20640] [4.0 Regression] ICE on NULL PHI_ARG_DEF
2005-03-25 20:57 [Bug tree-optimization/20640] New: [4.0 Regression] ICE on NULL PHI_ARG_DEF jakub at gcc dot gnu dot org
2005-03-25 20:58 ` [Bug tree-optimization/20640] " jakub at gcc dot gnu dot org
@ 2005-03-25 21:07 ` pinskia at gcc dot gnu dot org
2005-03-25 21:11 ` pinskia at gcc dot gnu dot org
` (11 subsequent siblings)
13 siblings, 0 replies; 15+ messages in thread
From: pinskia at gcc dot gnu dot org @ 2005-03-25 21:07 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From pinskia at gcc dot gnu dot org 2005-03-25 21:07 -------
Confirmed, for some reason on the mainline we are not unrolling the loop.
--
What |Removed |Added
----------------------------------------------------------------------------
CC| |pinskia at gcc dot gnu dot
| |org
Status|UNCONFIRMED |NEW
Ever Confirmed| |1
Last reconfirmed|0000-00-00 00:00:00 |2005-03-25 21:07:19
date| |
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=20640
^ permalink raw reply [flat|nested] 15+ messages in thread
* [Bug tree-optimization/20640] [4.0 Regression] ICE on NULL PHI_ARG_DEF
2005-03-25 20:57 [Bug tree-optimization/20640] New: [4.0 Regression] ICE on NULL PHI_ARG_DEF jakub at gcc dot gnu dot org
2005-03-25 20:58 ` [Bug tree-optimization/20640] " jakub at gcc dot gnu dot org
2005-03-25 21:07 ` pinskia at gcc dot gnu dot org
@ 2005-03-25 21:11 ` pinskia at gcc dot gnu dot org
2005-03-25 21:12 ` pinskia at gcc dot gnu dot org
` (10 subsequent siblings)
13 siblings, 0 replies; 15+ messages in thread
From: pinskia at gcc dot gnu dot org @ 2005-03-25 21:11 UTC (permalink / raw)
To: gcc-bugs
[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 522 bytes --]
------- Additional Comments From pinskia at gcc dot gnu dot org 2005-03-25 21:11 -------
With checking enabled we get:
t.c: In function test:
t.c:7: error: PHI argument is missing for edge 1->4
for PHI node
a_13 = PHI <a_11(2), a_14(3), (1)>;
t.c:7: internal compiler error: verify_ssa failed.
Please submit a full bug report,
with preprocessed source if appropriate.
See <URL:http://gcc.gnu.org/bugs.html> for instructions.
This started after 2004-12-11.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=20640
^ permalink raw reply [flat|nested] 15+ messages in thread
* [Bug tree-optimization/20640] [4.0 Regression] ICE on NULL PHI_ARG_DEF
2005-03-25 20:57 [Bug tree-optimization/20640] New: [4.0 Regression] ICE on NULL PHI_ARG_DEF jakub at gcc dot gnu dot org
` (2 preceding siblings ...)
2005-03-25 21:11 ` pinskia at gcc dot gnu dot org
@ 2005-03-25 21:12 ` pinskia at gcc dot gnu dot org
2005-03-30 5:20 ` aoliva at gcc dot gnu dot org
` (9 subsequent siblings)
13 siblings, 0 replies; 15+ messages in thread
From: pinskia at gcc dot gnu dot org @ 2005-03-25 21:12 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From pinskia at gcc dot gnu dot org 2005-03-25 21:12 -------
And was happening when the 4.0 branch was created: 20050225.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=20640
^ permalink raw reply [flat|nested] 15+ messages in thread
* [Bug tree-optimization/20640] [4.0 Regression] ICE on NULL PHI_ARG_DEF
2005-03-25 20:57 [Bug tree-optimization/20640] New: [4.0 Regression] ICE on NULL PHI_ARG_DEF jakub at gcc dot gnu dot org
` (3 preceding siblings ...)
2005-03-25 21:12 ` pinskia at gcc dot gnu dot org
@ 2005-03-30 5:20 ` aoliva at gcc dot gnu dot org
2005-03-30 7:56 ` jakub at redhat dot com
` (8 subsequent siblings)
13 siblings, 0 replies; 15+ messages in thread
From: aoliva at gcc dot gnu dot org @ 2005-03-30 5:20 UTC (permalink / raw)
To: gcc-bugs
--
What |Removed |Added
----------------------------------------------------------------------------
AssignedTo|unassigned at gcc dot gnu |aoliva at gcc dot gnu dot
|dot org |org
Status|NEW |ASSIGNED
Last reconfirmed|2005-03-25 21:07:19 |2005-03-30 05:19:07
date| |
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=20640
^ permalink raw reply [flat|nested] 15+ messages in thread
* [Bug tree-optimization/20640] [4.0 Regression] ICE on NULL PHI_ARG_DEF
2005-03-25 20:57 [Bug tree-optimization/20640] New: [4.0 Regression] ICE on NULL PHI_ARG_DEF jakub at gcc dot gnu dot org
` (4 preceding siblings ...)
2005-03-30 5:20 ` aoliva at gcc dot gnu dot org
@ 2005-03-30 7:56 ` jakub at redhat dot com
2005-03-31 8:29 ` aoliva at redhat dot com
` (7 subsequent siblings)
13 siblings, 0 replies; 15+ messages in thread
From: jakub at redhat dot com @ 2005-03-30 7:56 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From jakub at redhat dot com 2005-03-30 07:56 -------
Subject: Re: [PR tree-optimization/20640] add phi args to dests of dce-redirected edges
On Wed, Mar 30, 2005 at 02:56:24AM -0300, Alexandre Oliva wrote:
> When remove_dead_stmt() redirects a control stmt, the edge redirection
> reserves space for the phi arg for the new incoming edge in all phi
> nodes, but, instead of filling them in with information obtained from
> the edge redirection, we simply discard this information. This leaves
> NULL in the phi args, which may cause crashes later on.
>
> This patch fixes the problem by filling in the phi args using the
> PENDING_STMT list created during edge redirection. This appears to be
> the intended use for this information, and it is used similarly in
> e.g. loop unrolling.
>
> Bootstrapping mainline and 4.0 branch on amd64-linux-gnu, and mainline
> on i686-pc-linux-gnu. Ok to install if bootstrap and regtesting pass?
>
> The patch below is for the 4.0 branch, but it applies cleanly and
> correctly in mainline as well, since it's just a few lines off.
Note this is PR tree-optimization/20640, not PR 20460
(typo in ChangeLog as well as subject line, while the testcase is ok).
Jakub
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=20640
^ permalink raw reply [flat|nested] 15+ messages in thread
* [Bug tree-optimization/20640] [4.0 Regression] ICE on NULL PHI_ARG_DEF
2005-03-25 20:57 [Bug tree-optimization/20640] New: [4.0 Regression] ICE on NULL PHI_ARG_DEF jakub at gcc dot gnu dot org
` (5 preceding siblings ...)
2005-03-30 7:56 ` jakub at redhat dot com
@ 2005-03-31 8:29 ` aoliva at redhat dot com
2005-03-31 8:42 ` aoliva at redhat dot com
` (6 subsequent siblings)
13 siblings, 0 replies; 15+ messages in thread
From: aoliva at redhat dot com @ 2005-03-31 8:29 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From aoliva at gcc dot gnu dot org 2005-03-31 08:28 -------
Subject: Re: [PR tree-optimization/20640] add phi args to dests of dce-redirected edges
On Mar 31, 2005, Alexandre Oliva <aoliva@redhat.com> wrote:
> I have a gut feeling that we'll always get a PHI arg from one of the
> previous successors of the src of the redirected edge, but I can't
> quite prove it. What do you think?
A few seconds after posting the patch, ssa-dce-3.c failed, showing my
gut feeling was wrong. Oh well...
On Mar 30, 2005, Jeffrey A Law <law@redhat.com> wrote:
>> This code is triggered rarely, I would expect it to be even rarer still
>> for POST_DOM_BB to have PHI nodes. You could probably just ignore dead
>> control statements where the post dominator has PHI nodes and I doubt
>> it would ever be noticed.
It is noticed if we take the same path as the no-post_dom_bb,
infinite-loop case, because then the instruction that remains may
still reference variables that were deleted.
This patch, however, arranges for us to turn the edge into a
fall-through edge to its original destination should the immediate
post dominator be found to have PHI nodes.
I've also tweaked the code so as to remove all dead phi nodes before
removing all other statements, thereby improving the odds of
redirecting a dead control stmt to the post dominator.
Interestingly, the resulting code was no different for some cases I
inspected (the testcase included in the patch and ssa-dce-3.c).
That's because the edge dest bb ends up becoming a simple forwarding
block that is later removed.
As for infinite loops, I'm wondering if we should somehow try to
remove the condition from the loop. If the conditional branch is
found to be dead, it's quite possible that the set of that variable is
dead as well, and so we'd be keeping a reference to a deleted
variable. I couldn't actually exercise such an error, and I'm not
convinced it's possible, but I thought I'd bring this up. Thoughts?
Anyway, how does this patch look?
Index: gcc/ChangeLog
from Alexandre Oliva <aoliva@redhat.com>
PR tree-optimization/20640
* tree-ssa-dce.c (remove_dead_stmt): Don't redirect edge to
post-dominator if it has phi nodes.
(eliminate_unnecessary_stmts): Remove dead phis in all blocks
before dead statements.
Index: gcc/tree-ssa-dce.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-dce.c,v
retrieving revision 2.37
diff -u -p -r2.37 tree-ssa-dce.c
--- gcc/tree-ssa-dce.c 12 Mar 2005 20:53:18 -0000 2.37
+++ gcc/tree-ssa-dce.c 31 Mar 2005 07:56:42 -0000
@@ -637,7 +637,10 @@ eliminate_unnecessary_stmts (void)
{
/* Remove dead PHI nodes. */
remove_dead_phis (bb);
+ }
+ FOR_EACH_BB (bb)
+ {
/* Remove dead statements. */
for (i = bsi_start (bb); ! bsi_end_p (i) ; )
{
@@ -724,6 +727,7 @@ remove_dead_stmt (block_stmt_iterator *i
if (is_ctrl_stmt (t))
{
basic_block post_dom_bb;
+
/* The post dominance info has to be up-to-date. */
gcc_assert (dom_computed[CDI_POST_DOMINATORS] == DOM_OK);
/* Get the immediate post dominator of bb. */
@@ -737,6 +741,15 @@ remove_dead_stmt (block_stmt_iterator *i
return;
}
+ /* If the post dominator block has PHI nodes, we might be unable
+ to compute the right PHI args for them. Since the control
+ statement is unnecessary, all edges can be regarded as
+ equivalent, but we have to get rid of the condition, since it
+ might reference a variable that was determined to be
+ unnecessary and thus removed. */
+ if (phi_nodes (post_dom_bb))
+ post_dom_bb = EDGE_SUCC (bb, 0)->dest;
+
/* Redirect the first edge out of BB to reach POST_DOM_BB. */
redirect_edge_and_branch (EDGE_SUCC (bb, 0), post_dom_bb);
PENDING_STMT (EDGE_SUCC (bb, 0)) = NULL;
Index: gcc/testsuite/ChangeLog
from Alexandre Oliva <aoliva@redhat.com>
PR tree-optimization/20640
* gcc.dg/torture/tree-loop-1.c: New.
Index: gcc/testsuite/gcc.dg/torture/tree-loop-1.c
===================================================================
RCS file: gcc/testsuite/gcc.dg/torture/tree-loop-1.c
diff -N gcc/testsuite/gcc.dg/torture/tree-loop-1.c
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ gcc/testsuite/gcc.dg/torture/tree-loop-1.c 30 Mar 2005 05:28:22 -0000
@@ -0,0 +1,21 @@
+/* PR tree-optimization/20640 */
+
+/* After unrolling the loop, we'd turn some conditional branches into
+ unconditional ones, but branch redirection would fail to compute
+ the PHI args for the PHI nodes in the replacement edge
+ destination, so they'd remain NULL causing crashes later on. */
+
+/* { dg-do compile } */
+
+static int a = 0;
+extern int foo (void);
+extern int *bar (void) __attribute__ ((__const__));
+
+void
+test (int x)
+{
+ int b = 10;
+ while (foo () == -1 && *bar () == 4 && b > 0)
+ --b;
+ a = x;
+}
--
Alexandre Oliva http://www.ic.unicamp.br/~oliva/
Red Hat Compiler Engineer aoliva@{redhat.com, gcc.gnu.org}
Free Software Evangelist oliva@{lsd.ic.unicamp.br, gnu.org}
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=20640
^ permalink raw reply [flat|nested] 15+ messages in thread
* [Bug tree-optimization/20640] [4.0 Regression] ICE on NULL PHI_ARG_DEF
2005-03-25 20:57 [Bug tree-optimization/20640] New: [4.0 Regression] ICE on NULL PHI_ARG_DEF jakub at gcc dot gnu dot org
` (6 preceding siblings ...)
2005-03-31 8:29 ` aoliva at redhat dot com
@ 2005-03-31 8:42 ` aoliva at redhat dot com
2005-03-31 17:59 ` law at redhat dot com
` (5 subsequent siblings)
13 siblings, 0 replies; 15+ messages in thread
From: aoliva at redhat dot com @ 2005-03-31 8:42 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From aoliva at gcc dot gnu dot org 2005-03-31 08:41 -------
Subject: Re: [PR tree-optimization/20640] add phi args to dests of dce-redirected edges
On Mar 30, 2005, Jeffrey A Law <law@redhat.com> wrote:
> - PENDING_STMT (EDGE_SUCC (bb, 0)) = NULL;
> + flush_pending_stmts (EDGE_SUCC (bb, 0));
> I'm having trouble seeing how this can be correct.
After looking at what flush_pending_stmts() actually does, I must
confess I'm disappointed. I expected it to be far smarter than it
actually is.
Here's a newer version of the patch that survived bootstrap on
x86_64-linux-gnu, with default BOOT_CFLAGS in mainline, and with
BOOT_CFLAGS='-O3 -g -funroll-all-loops' in the 4.0 branch. I found
that the 4.0 branch would fail to bootstrap even with default
BOOT_CFLAGS if I added code to flush_pending_stmts() to verify that
the PHI args actually matched the corresponding PHI nodes.
My concern is that, if the code in this patch fails and we reach the
hopefully-unreachable point, we won't be able to obtain a PHI arg very
easily. I have a gut feeling that we'll always get a PHI arg from one
of the previous successors of the src of the redirected edge, but I
can't quite prove it. What do you think?
> This code is triggered rarely, I would expect it to be even rarer still
> for POST_DOM_BB to have PHI nodes. You could probably just ignore dead
> control statements where the post dominator has PHI nodes and I doubt
> it would ever be noticed.
Index: gcc/ChangeLog
from Alexandre Oliva <aoliva@redhat.com>
PR tree-optimization/20640
* tree-ssa-dce.c (remove_dead_stmt): Add phi args to phi nodes
affected by an edge redirection.
Index: gcc/tree-ssa-dce.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-dce.c,v
retrieving revision 2.37
diff -u -p -r2.37 tree-ssa-dce.c
--- gcc/tree-ssa-dce.c 12 Mar 2005 20:53:18 -0000 2.37
+++ gcc/tree-ssa-dce.c 31 Mar 2005 06:39:48 -0000
@@ -724,6 +724,10 @@ remove_dead_stmt (block_stmt_iterator *i
if (is_ctrl_stmt (t))
{
basic_block post_dom_bb;
+ edge e;
+ tree phi;
+ tree pending_stmts;
+
/* The post dominance info has to be up-to-date. */
gcc_assert (dom_computed[CDI_POST_DOMINATORS] == DOM_OK);
/* Get the immediate post dominator of bb. */
@@ -739,7 +743,13 @@ remove_dead_stmt (block_stmt_iterator *i
/* Redirect the first edge out of BB to reach POST_DOM_BB. */
redirect_edge_and_branch (EDGE_SUCC (bb, 0), post_dom_bb);
+
+ e = EDGE_SUCC (bb, 0);
+
+ pending_stmts = PENDING_STMT (e);
+
PENDING_STMT (EDGE_SUCC (bb, 0)) = NULL;
+
EDGE_SUCC (bb, 0)->probability = REG_BR_PROB_BASE;
EDGE_SUCC (bb, 0)->count = bb->count;
@@ -755,6 +765,76 @@ remove_dead_stmt (block_stmt_iterator *i
else
EDGE_SUCC (bb, 0)->flags &= ~EDGE_FALLTHRU;
+ /* Now adjust the PHI args for the new edge in the new dest. */
+ for (phi = phi_nodes (e->dest);
+ phi;
+ phi = PHI_CHAIN (phi))
+ {
+ tree arg = NULL;
+ tree *pendp = &pending_stmts;
+ tree phi1;
+ edge e1;
+ edge_iterator ei;
+
+ /* If it's already set for a variable, we're done! */
+ if (PHI_ARG_DEF (phi, e->dest_idx))
+ continue;
+
+ /* Try to locate a value in the list of PHI args collected
+ while removing the old edge. */
+ while (*pendp)
+ {
+ if (SSA_NAME_VAR (PHI_RESULT (phi))
+ == SSA_NAME_VAR (TREE_PURPOSE (*pendp)))
+ {
+ arg = TREE_VALUE (*pendp);
+ *pendp = TREE_CHAIN (*pendp);
+ break;
+ }
+ pendp = &TREE_CHAIN (*pendp);
+ }
+
+ if (arg)
+ {
+ add_phi_arg (phi, arg, e);
+ continue;
+ }
+
+ /* As a last resort, we can try to find ssa args in the
+ other outgoing edges of the src block. */
+ FOR_EACH_EDGE (e1, ei, bb->succs)
+ {
+ if (e1 == e)
+ continue;
+
+ for (phi1 = phi_nodes (e1->dest); phi1;
+ phi1 = PHI_CHAIN (phi1))
+ {
+ if (SSA_NAME_VAR (PHI_RESULT (phi1))
+ == SSA_NAME_VAR (PHI_RESULT (phi)))
+ {
+ arg = PHI_ARG_DEF (phi1, e1->dest_idx);
+ break;
+ }
+ }
+
+ if (arg)
+ break;
+ }
+
+ if (arg)
+ {
+ add_phi_arg (phi, arg, e);
+ continue;
+ }
+
+ /* There's a slight possibility that we won't have been able
+ to find a PHI arg in any of the previously-existing
+ outgoing edges. Should this ever happen, we'd have to
+ scan the BB or its preds for a definition. */
+ gcc_unreachable ();
+ }
+
/* Remove the remaining the outgoing edges. */
while (!single_succ_p (bb))
remove_edge (EDGE_SUCC (bb, 1));
Index: gcc/testsuite/ChangeLog
from Alexandre Oliva <aoliva@redhat.com>
PR tree-optimization/20640
* gcc.dg/torture/tree-loop-1.c: New.
Index: gcc/testsuite/gcc.dg/torture/tree-loop-1.c
===================================================================
RCS file: gcc/testsuite/gcc.dg/torture/tree-loop-1.c
diff -N gcc/testsuite/gcc.dg/torture/tree-loop-1.c
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ gcc/testsuite/gcc.dg/torture/tree-loop-1.c 30 Mar 2005 05:28:22 -0000
@@ -0,0 +1,21 @@
+/* PR tree-optimization/20640 */
+
+/* After unrolling the loop, we'd turn some conditional branches into
+ unconditional ones, but branch redirection would fail to compute
+ the PHI args for the PHI nodes in the replacement edge
+ destination, so they'd remain NULL causing crashes later on. */
+
+/* { dg-do compile } */
+
+static int a = 0;
+extern int foo (void);
+extern int *bar (void) __attribute__ ((__const__));
+
+void
+test (int x)
+{
+ int b = 10;
+ while (foo () == -1 && *bar () == 4 && b > 0)
+ --b;
+ a = x;
+}
--
Alexandre Oliva http://www.ic.unicamp.br/~oliva/
Red Hat Compiler Engineer aoliva@{redhat.com, gcc.gnu.org}
Free Software Evangelist oliva@{lsd.ic.unicamp.br, gnu.org}
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=20640
^ permalink raw reply [flat|nested] 15+ messages in thread
* [Bug tree-optimization/20640] [4.0 Regression] ICE on NULL PHI_ARG_DEF
2005-03-25 20:57 [Bug tree-optimization/20640] New: [4.0 Regression] ICE on NULL PHI_ARG_DEF jakub at gcc dot gnu dot org
` (7 preceding siblings ...)
2005-03-31 8:42 ` aoliva at redhat dot com
@ 2005-03-31 17:59 ` law at redhat dot com
2005-03-31 18:00 ` law at redhat dot com
` (4 subsequent siblings)
13 siblings, 0 replies; 15+ messages in thread
From: law at redhat dot com @ 2005-03-31 17:59 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From law at redhat dot com 2005-03-31 17:59 -------
Subject: Re: [PR tree-optimization/20640] add phi args to dests of
dce-redirected edges
On Thu, 2005-03-31 at 05:26 -0300, Alexandre Oliva wrote:
> On Mar 31, 2005, Alexandre Oliva <aoliva@redhat.com> wrote:
>
> > I have a gut feeling that we'll always get a PHI arg from one of the
> > previous successors of the src of the redirected edge, but I can't
> > quite prove it. What do you think?
>
> A few seconds after posting the patch, ssa-dce-3.c failed, showing my
> gut feeling was wrong. Oh well...
Worse yet, you can't depend on testing SSA_NAME_VAR to find your
PHI node. It's rare, but possible to have two PHIs in the same block
with the same underlying SSA_NAME_VAR. It's also possible to get a
mis-match between the underlying var for PHI_RESULT and PHI_ARG_...
At which point you're probably coming to realize that updating PHI
nodes is a non-trivial problem in the general case.
Fundamentally, this code is trying to optimize the case where selection
of either arm of the conditional has no visible impact on the behavior
of the program. So while the arms may contain code, we know that we
could execute either arm or even bypass both completely and get correct
code. From this you can derive that any assignments in the arms must
be dead and any PHIs those assignments feed must also be dead, and so
on.
So we could proceed by first eliminating all the assignments and PHI
nodes which are dead, then we proceed to eliminate the dead control
statements. As you noted, this makes it less likely that there will be
any PHIs in the post-dominator node. It also makes it easier to update
any PHIs which remain in the post-dominator node.
For each PHI in post_dominator_bb
For each PHI argument
if (dominated_by_p (arg->edge->src, control_statement_bb))
arg->value is the value we want to associate with the new edge
from control_statement_bb to post_dominator_bb
At least I think that or something similar should do the trick. I
haven't finished my first coke for the day, but it feels right.
Alternately, we could go with your second approach which is to
remove all the dead phis first, then avoid redirecting to a
post-dominator with phis (instead redirecting to the fall-thru
edge).
> On Mar 30, 2005, Jeffrey A Law <law@redhat.com> wrote:
>
> >> This code is triggered rarely, I would expect it to be even rarer still
> >> for POST_DOM_BB to have PHI nodes. You could probably just ignore dead
> >> control statements where the post dominator has PHI nodes and I doubt
> >> it would ever be noticed.
>
> It is noticed if we take the same path as the no-post_dom_bb,
> infinite-loop case, because then the instruction that remains may
> still reference variables that were deleted.
We can change the COND_EXPR_COND to be anything we want --
remember, the whole point is that we've determined that the branch
itself is dead -- we can take either arm and nothing can tell the
difference. So we could just change the condition to if (0) and
we would be safe. Or we could just delete the condition and
fall-thru as you've suggested.
The only advantage of redirecting to the post-dominator block is that
we have less cleanup work to do later. It's not clear to me if there
is an advantage (compile-time wise) to redirecting to the post-dominator
block or just redirecting to the fall-thru and letting cleanup_tree_cfg
remove the forwarders.
> This patch, however, arranges for us to turn the edge into a
> fall-through edge to its original destination should the immediate
> post dominator be found to have PHI nodes.
Which would be fine.
> I've also tweaked the code so as to remove all dead phi nodes before
> removing all other statements, thereby improving the odds of
> redirecting a dead control stmt to the post dominator.
Right. That was a good piece of insight. I think this is really the
key step for either solution (update the post-dominator phis, or
just redirect to the fall-thru edge).
> Interestingly, the resulting code was no different for some cases I
> inspected (the testcase included in the patch and ssa-dce-3.c).
> That's because the edge dest bb ends up becoming a simple forwarding
> block that is later removed.
Precisely. Again, redirecting to the post-dominator is just avoiding
some of the later cleanup work.
>
> As for infinite loops, I'm wondering if we should somehow try to
> remove the condition from the loop. If the conditional branch is
> found to be dead, it's quite possible that the set of that variable is
> dead as well, and so we'd be keeping a reference to a deleted
> variable. I couldn't actually exercise such an error, and I'm not
> convinced it's possible, but I thought I'd bring this up. Thoughts?
I'm not sure either. I haven't thought much about the infinite loop
cases much. It would seem to me that we could/should remove the
conditional as well. Presumably this code is meant to handle the case
where the conditional will always end up looping, regardless of
whether or not the conditional is true or false.
Jeff
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=20640
^ permalink raw reply [flat|nested] 15+ messages in thread
* [Bug tree-optimization/20640] [4.0 Regression] ICE on NULL PHI_ARG_DEF
2005-03-25 20:57 [Bug tree-optimization/20640] New: [4.0 Regression] ICE on NULL PHI_ARG_DEF jakub at gcc dot gnu dot org
` (8 preceding siblings ...)
2005-03-31 17:59 ` law at redhat dot com
@ 2005-03-31 18:00 ` law at redhat dot com
2005-04-02 16:59 ` aoliva at redhat dot com
` (3 subsequent siblings)
13 siblings, 0 replies; 15+ messages in thread
From: law at redhat dot com @ 2005-03-31 18:00 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From law at redhat dot com 2005-03-31 18:00 -------
Subject: Re: [PR tree-optimization/20640] add phi args to dests of
dce-redirected edges
On Thu, 2005-03-31 at 05:26 -0300, Alexandre Oliva wrote:
> On Mar 31, 2005, Alexandre Oliva <aoliva@redhat.com> wrote:
[ ... ]
> Anyway, how does this patch look?
> Index: gcc/ChangeLog
from Alexandre Oliva <aoliva@redhat.com>
PR tree-optimization/20640
* tree-ssa-dce.c (remove_dead_stmt): Don't redirect edge to
post-dominator if it has phi nodes.
(eliminate_unnecessary_stmts): Remove dead phis in all blocks
before dead statements.
BTW, if you want to go forward with this version, it looks OK to me
assuming it passes bootstrapping and regression testing.
Jeff
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=20640
^ permalink raw reply [flat|nested] 15+ messages in thread
* [Bug tree-optimization/20640] [4.0 Regression] ICE on NULL PHI_ARG_DEF
2005-03-25 20:57 [Bug tree-optimization/20640] New: [4.0 Regression] ICE on NULL PHI_ARG_DEF jakub at gcc dot gnu dot org
` (9 preceding siblings ...)
2005-03-31 18:00 ` law at redhat dot com
@ 2005-04-02 16:59 ` aoliva at redhat dot com
2005-04-02 17:02 ` cvs-commit at gcc dot gnu dot org
` (2 subsequent siblings)
13 siblings, 0 replies; 15+ messages in thread
From: aoliva at redhat dot com @ 2005-04-02 16:59 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From aoliva at gcc dot gnu dot org 2005-04-02 16:59 -------
Subject: Re: [PR tree-optimization/20640] add phi args to dests of dce-redirected edges
On Mar 31, 2005, Jeffrey A Law <law@redhat.com> wrote:
> On Thu, 2005-03-31 at 05:26 -0300, Alexandre Oliva wrote:
>> On Mar 31, 2005, Alexandre Oliva <aoliva@redhat.com> wrote:
> [ ... ]
>> Anyway, how does this patch look?
>> Index: gcc/ChangeLog
> from Alexandre Oliva <aoliva@redhat.com>
> PR tree-optimization/20640
> * tree-ssa-dce.c (remove_dead_stmt): Don't redirect edge to
> post-dominator if it has phi nodes.
> (eliminate_unnecessary_stmts): Remove dead phis in all blocks
> before dead statements.
> BTW, if you want to go forward with this version, it looks OK to me
> assuming it passes bootstrapping and regression testing.
It does, so I'm checking it in with a minor change: it doesn't make
sense to request the edge to be redirected to itself, since it's a
no-op, so I moved the call into the `else' branch of the new
conditional.
Thanks,
Index: gcc/ChangeLog
from Alexandre Oliva <aoliva@redhat.com>
PR tree-optimization/20640
* tree-ssa-dce.c (remove_dead_stmt): Don't redirect edge to
post-dominator if it has phi nodes.
(eliminate_unnecessary_stmts): Remove dead phis in all blocks
before dead statements.
Index: gcc/tree-ssa-dce.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-dce.c,v
retrieving revision 2.37
diff -u -p -r2.37 tree-ssa-dce.c
--- gcc/tree-ssa-dce.c 12 Mar 2005 20:53:18 -0000 2.37
+++ gcc/tree-ssa-dce.c 1 Apr 2005 20:30:24 -0000
@@ -637,7 +637,10 @@ eliminate_unnecessary_stmts (void)
{
/* Remove dead PHI nodes. */
remove_dead_phis (bb);
+ }
+ FOR_EACH_BB (bb)
+ {
/* Remove dead statements. */
for (i = bsi_start (bb); ! bsi_end_p (i) ; )
{
@@ -724,6 +727,7 @@ remove_dead_stmt (block_stmt_iterator *i
if (is_ctrl_stmt (t))
{
basic_block post_dom_bb;
+
/* The post dominance info has to be up-to-date. */
gcc_assert (dom_computed[CDI_POST_DOMINATORS] == DOM_OK);
/* Get the immediate post dominator of bb. */
@@ -737,9 +741,20 @@ remove_dead_stmt (block_stmt_iterator *i
return;
}
- /* Redirect the first edge out of BB to reach POST_DOM_BB. */
- redirect_edge_and_branch (EDGE_SUCC (bb, 0), post_dom_bb);
- PENDING_STMT (EDGE_SUCC (bb, 0)) = NULL;
+ /* If the post dominator block has PHI nodes, we might be unable
+ to compute the right PHI args for them. Since the control
+ statement is unnecessary, all edges can be regarded as
+ equivalent, but we have to get rid of the condition, since it
+ might reference a variable that was determined to be
+ unnecessary and thus removed. */
+ if (phi_nodes (post_dom_bb))
+ post_dom_bb = EDGE_SUCC (bb, 0)->dest;
+ else
+ {
+ /* Redirect the first edge out of BB to reach POST_DOM_BB. */
+ redirect_edge_and_branch (EDGE_SUCC (bb, 0), post_dom_bb);
+ PENDING_STMT (EDGE_SUCC (bb, 0)) = NULL;
+ }
EDGE_SUCC (bb, 0)->probability = REG_BR_PROB_BASE;
EDGE_SUCC (bb, 0)->count = bb->count;
Index: gcc/testsuite/ChangeLog
from Alexandre Oliva <aoliva@redhat.com>
PR tree-optimization/20640
* gcc.dg/torture/tree-loop-1.c: New.
Index: gcc/testsuite/gcc.dg/torture/tree-loop-1.c
===================================================================
RCS file: gcc/testsuite/gcc.dg/torture/tree-loop-1.c
diff -N gcc/testsuite/gcc.dg/torture/tree-loop-1.c
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ gcc/testsuite/gcc.dg/torture/tree-loop-1.c 30 Mar 2005 05:28:22 -0000
@@ -0,0 +1,21 @@
+/* PR tree-optimization/20640 */
+
+/* After unrolling the loop, we'd turn some conditional branches into
+ unconditional ones, but branch redirection would fail to compute
+ the PHI args for the PHI nodes in the replacement edge
+ destination, so they'd remain NULL causing crashes later on. */
+
+/* { dg-do compile } */
+
+static int a = 0;
+extern int foo (void);
+extern int *bar (void) __attribute__ ((__const__));
+
+void
+test (int x)
+{
+ int b = 10;
+ while (foo () == -1 && *bar () == 4 && b > 0)
+ --b;
+ a = x;
+}
--
Alexandre Oliva http://www.ic.unicamp.br/~oliva/
Red Hat Compiler Engineer aoliva@{redhat.com, gcc.gnu.org}
Free Software Evangelist oliva@{lsd.ic.unicamp.br, gnu.org}
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=20640
^ permalink raw reply [flat|nested] 15+ messages in thread
* [Bug tree-optimization/20640] [4.0 Regression] ICE on NULL PHI_ARG_DEF
2005-03-25 20:57 [Bug tree-optimization/20640] New: [4.0 Regression] ICE on NULL PHI_ARG_DEF jakub at gcc dot gnu dot org
` (10 preceding siblings ...)
2005-04-02 16:59 ` aoliva at redhat dot com
@ 2005-04-02 17:02 ` cvs-commit at gcc dot gnu dot org
2005-04-02 17:03 ` cvs-commit at gcc dot gnu dot org
2005-04-02 17:07 ` aoliva at gcc dot gnu dot org
13 siblings, 0 replies; 15+ messages in thread
From: cvs-commit at gcc dot gnu dot org @ 2005-04-02 17:02 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From cvs-commit at gcc dot gnu dot org 2005-04-02 17:02 -------
Subject: Bug 20640
CVSROOT: /cvs/gcc
Module name: gcc
Changes by: aoliva@gcc.gnu.org 2005-04-02 17:02:15
Modified files:
gcc : ChangeLog tree-ssa-dce.c
gcc/testsuite : ChangeLog
Added files:
gcc/testsuite/gcc.dg/torture: tree-loop-1.c
Log message:
gcc/ChangeLog:
PR tree-optimization/20640
* tree-ssa-dce.c (remove_dead_stmt): Don't redirect edge to
post-dominator if it has phi nodes.
(eliminate_unnecessary_stmts): Remove dead phis in all blocks
before dead statements.
gcc/testsuite/ChangeLog:
PR tree-optimization/20640
* gcc.dg/torture/tree-loop-1.c: New.
Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/ChangeLog.diff?cvsroot=gcc&r1=2.8088&r2=2.8089
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/tree-ssa-dce.c.diff?cvsroot=gcc&r1=2.37&r2=2.38
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/ChangeLog.diff?cvsroot=gcc&r1=1.5268&r2=1.5269
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/gcc.dg/torture/tree-loop-1.c.diff?cvsroot=gcc&r1=NONE&r2=1.1
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=20640
^ permalink raw reply [flat|nested] 15+ messages in thread
* [Bug tree-optimization/20640] [4.0 Regression] ICE on NULL PHI_ARG_DEF
2005-03-25 20:57 [Bug tree-optimization/20640] New: [4.0 Regression] ICE on NULL PHI_ARG_DEF jakub at gcc dot gnu dot org
` (11 preceding siblings ...)
2005-04-02 17:02 ` cvs-commit at gcc dot gnu dot org
@ 2005-04-02 17:03 ` cvs-commit at gcc dot gnu dot org
2005-04-02 17:07 ` aoliva at gcc dot gnu dot org
13 siblings, 0 replies; 15+ messages in thread
From: cvs-commit at gcc dot gnu dot org @ 2005-04-02 17:03 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From cvs-commit at gcc dot gnu dot org 2005-04-02 17:03 -------
Subject: Bug 20640
CVSROOT: /cvs/gcc
Module name: gcc
Branch: gcc-4_0-branch
Changes by: aoliva@gcc.gnu.org 2005-04-02 17:02:55
Modified files:
gcc : ChangeLog tree-ssa-dce.c
gcc/testsuite : ChangeLog
Added files:
gcc/testsuite/gcc.dg/torture: tree-loop-1.c
Log message:
gcc/ChangeLog:
PR tree-optimization/20640
* tree-ssa-dce.c (remove_dead_stmt): Don't redirect edge to
post-dominator if it has phi nodes.
(eliminate_unnecessary_stmts): Remove dead phis in all blocks
before dead statements.
gcc/testsuite/ChangeLog:
PR tree-optimization/20640
* gcc.dg/torture/tree-loop-1.c: New.
Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/ChangeLog.diff?cvsroot=gcc&only_with_tag=gcc-4_0-branch&r1=2.7592.2.115&r2=2.7592.2.116
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/tree-ssa-dce.c.diff?cvsroot=gcc&only_with_tag=gcc-4_0-branch&r1=2.32&r2=2.32.4.1
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/ChangeLog.diff?cvsroot=gcc&only_with_tag=gcc-4_0-branch&r1=1.5084.2.88&r2=1.5084.2.89
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/gcc.dg/torture/tree-loop-1.c.diff?cvsroot=gcc&only_with_tag=gcc-4_0-branch&r1=NONE&r2=1.1.2.1
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=20640
^ permalink raw reply [flat|nested] 15+ messages in thread
* [Bug tree-optimization/20640] [4.0 Regression] ICE on NULL PHI_ARG_DEF
2005-03-25 20:57 [Bug tree-optimization/20640] New: [4.0 Regression] ICE on NULL PHI_ARG_DEF jakub at gcc dot gnu dot org
` (12 preceding siblings ...)
2005-04-02 17:03 ` cvs-commit at gcc dot gnu dot org
@ 2005-04-02 17:07 ` aoliva at gcc dot gnu dot org
13 siblings, 0 replies; 15+ messages in thread
From: aoliva at gcc dot gnu dot org @ 2005-04-02 17:07 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From aoliva at gcc dot gnu dot org 2005-04-02 17:07 -------
Fixed
--
What |Removed |Added
----------------------------------------------------------------------------
Status|ASSIGNED |RESOLVED
Resolution| |FIXED
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=20640
^ permalink raw reply [flat|nested] 15+ messages in thread
end of thread, other threads:[~2005-04-02 17:07 UTC | newest]
Thread overview: 15+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2005-03-25 20:57 [Bug tree-optimization/20640] New: [4.0 Regression] ICE on NULL PHI_ARG_DEF jakub at gcc dot gnu dot org
2005-03-25 20:58 ` [Bug tree-optimization/20640] " jakub at gcc dot gnu dot org
2005-03-25 21:07 ` pinskia at gcc dot gnu dot org
2005-03-25 21:11 ` pinskia at gcc dot gnu dot org
2005-03-25 21:12 ` pinskia at gcc dot gnu dot org
2005-03-30 5:20 ` aoliva at gcc dot gnu dot org
2005-03-30 7:56 ` jakub at redhat dot com
2005-03-31 8:29 ` aoliva at redhat dot com
2005-03-31 8:42 ` aoliva at redhat dot com
2005-03-31 17:59 ` law at redhat dot com
2005-03-31 18:00 ` law at redhat dot com
2005-04-02 16:59 ` aoliva at redhat dot com
2005-04-02 17:02 ` cvs-commit at gcc dot gnu dot org
2005-04-02 17:03 ` cvs-commit at gcc dot gnu dot org
2005-04-02 17:07 ` aoliva at gcc dot gnu dot org
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).