* [Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed
2010-01-30 16:06 [Bug tree-optimization/42906] New: " rguenth at gcc dot gnu dot org
@ 2010-01-30 16:06 ` rguenth at gcc dot gnu dot org
2010-01-30 16:37 ` steven at gcc dot gnu dot org
` (29 subsequent siblings)
30 siblings, 0 replies; 35+ messages in thread
From: rguenth at gcc dot gnu dot org @ 2010-01-30 16:06 UTC (permalink / raw)
To: gcc-bugs
--
rguenth at gcc dot gnu dot org changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |hubicka at gcc dot gnu dot
| |org
Known to work| |4.4.2
Target Milestone|--- |4.5.0
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42906
^ permalink raw reply [flat|nested] 35+ messages in thread* [Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed
2010-01-30 16:06 [Bug tree-optimization/42906] New: " rguenth at gcc dot gnu dot org
2010-01-30 16:06 ` [Bug tree-optimization/42906] " rguenth at gcc dot gnu dot org
@ 2010-01-30 16:37 ` steven at gcc dot gnu dot org
2010-01-30 16:42 ` steven at gcc dot gnu dot org
` (28 subsequent siblings)
30 siblings, 0 replies; 35+ messages in thread
From: steven at gcc dot gnu dot org @ 2010-01-30 16:37 UTC (permalink / raw)
To: gcc-bugs
------- Comment #1 from steven at gcc dot gnu dot org 2010-01-30 16:37 -------
The loop is deemed necessary because the loop block (bb 6) is control dependent
on itself (?!):
(gdb)
mark_control_dependent_edges_necessary (bb=0x7ffff7f264e0, el=0x142c5d0) at
../../trunk/gcc/tree-ssa-dce.c:388
388 EXECUTE_IF_CONTROL_DEPENDENT (bi, bb->index, edge_number)
(gdb)
391 basic_block cd_bb = INDEX_EDGE_PRED_BB (el, edge_number);
(gdb)
393 if (TEST_BIT (last_stmt_necessary, cd_bb->index))
(gdb) p debug_bb(cd_bb)
;; basic block 6, loop depth 1, count 0
;; prev block 3, next block 5
;; pred: 4 [100.0%] (fallthru) 3 (fallthru,dfs_back,exec)
;; succ: 3 (true,exec) 5 (false,exec)
<bb 6>:
# i_2 = PHI <i_8(4), i_6(3)>
if (i_2 <= 999)
goto <bb 3>;
else
goto <bb 5>;
$22 = void
(gdb) p debug_bb(bb)
;; basic block 6, loop depth 1, count 0
;; prev block 3, next block 5
;; pred: 4 [100.0%] (fallthru) 3 (fallthru,dfs_back,exec)
;; succ: 3 (true,exec) 5 (false,exec)
<bb 6>:
# i_2 = PHI <i_8(4), i_6(3)>
if (i_2 <= 999)
goto <bb 3>;
else
goto <bb 5>;
$23 = void
(gdb)
--
steven at gcc dot gnu dot org changed:
What |Removed |Added
----------------------------------------------------------------------------
Status|UNCONFIRMED |NEW
Ever Confirmed|0 |1
Last reconfirmed|0000-00-00 00:00:00 |2010-01-30 16:37:37
date| |
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42906
^ permalink raw reply [flat|nested] 35+ messages in thread* [Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed
2010-01-30 16:06 [Bug tree-optimization/42906] New: " rguenth at gcc dot gnu dot org
2010-01-30 16:06 ` [Bug tree-optimization/42906] " rguenth at gcc dot gnu dot org
2010-01-30 16:37 ` steven at gcc dot gnu dot org
@ 2010-01-30 16:42 ` steven at gcc dot gnu dot org
2010-01-30 16:46 ` steven at gcc dot gnu dot org
` (27 subsequent siblings)
30 siblings, 0 replies; 35+ messages in thread
From: steven at gcc dot gnu dot org @ 2010-01-30 16:42 UTC (permalink / raw)
To: gcc-bugs
------- Comment #2 from steven at gcc dot gnu dot org 2010-01-30 16:42 -------
Even more fun: mark_control_dependent_edges_necessary is called on basic block
6 because a PHI argument is fed to "j_1 = PHI <j_5(D)(2), 0(6)>" i.e. a
constant coming from basic block 6:
#1 0x0000000000a16627 in propagate_necessity (el=0x142c5d0) at
../../trunk/gcc/tree-ssa-dce.c:691
691 mark_control_dependent_edges_necessary (arg_bb,
el);
(gdb) l
686 basic_block arg_bb = gimple_phi_arg_edge (stmt,
k)->src;
687 if (arg_bb != ENTRY_BLOCK_PTR
688 && ! TEST_BIT (visited_control_parents,
arg_bb->index))
689 {
690 SET_BIT (visited_control_parents, arg_bb->index);
691 mark_control_dependent_edges_necessary (arg_bb,
el);
692 }
693 }
694 }
695 }
(gdb) p stmt
$28 = (gimple) 0x7ffff5ce0c00
(gdb) p debug_gimple_stmt(stmt)
j_1 = PHI <j_4(D)(2), 0(6)>
The CD-DCE algorithm is not prepared to deal with this situation.
(I have said years ago that I didn't think having constants as PHI arguments
was always a helpful thing...)
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42906
^ permalink raw reply [flat|nested] 35+ messages in thread* [Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed
2010-01-30 16:06 [Bug tree-optimization/42906] New: " rguenth at gcc dot gnu dot org
` (2 preceding siblings ...)
2010-01-30 16:42 ` steven at gcc dot gnu dot org
@ 2010-01-30 16:46 ` steven at gcc dot gnu dot org
2010-01-30 16:51 ` steven at gcc dot gnu dot org
` (26 subsequent siblings)
30 siblings, 0 replies; 35+ messages in thread
From: steven at gcc dot gnu dot org @ 2010-01-30 16:46 UTC (permalink / raw)
To: gcc-bugs
------- Comment #3 from steven at gcc dot gnu dot org 2010-01-30 16:45 -------
Hack that may be worth trying:
Index: tree-ssa-dce.c
===================================================================
--- tree-ssa-dce.c (revision 156352)
+++ tree-ssa-dce.c (working copy)
@@ -683,7 +683,10 @@ propagate_necessity (struct edge_list *e
{
for (k = 0; k < gimple_phi_num_args (stmt); k++)
{
+ tree t = gimple_phi_arg_def (stmt, k);
basic_block arg_bb = gimple_phi_arg_edge (stmt, k)->src;
+ if (is_gimple_min_invariant (t))
+ continue;
if (arg_bb != ENTRY_BLOCK_PTR
&& ! TEST_BIT (visited_control_parents, arg_bb->index))
{
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42906
^ permalink raw reply [flat|nested] 35+ messages in thread* [Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed
2010-01-30 16:06 [Bug tree-optimization/42906] New: " rguenth at gcc dot gnu dot org
` (3 preceding siblings ...)
2010-01-30 16:46 ` steven at gcc dot gnu dot org
@ 2010-01-30 16:51 ` steven at gcc dot gnu dot org
2010-01-30 16:53 ` rguenth at gcc dot gnu dot org
` (25 subsequent siblings)
30 siblings, 0 replies; 35+ messages in thread
From: steven at gcc dot gnu dot org @ 2010-01-30 16:51 UTC (permalink / raw)
To: gcc-bugs
------- Comment #4 from steven at gcc dot gnu dot org 2010-01-30 16:51 -------
Eh, ignore comment #3. My understanding of CD-DCE really *is* rusty :-).
Being more careful now: IIRC the statement "j = 0" would have been control
dependent on "if (b)" and marking "j = 0" would result in marking "if (b)"
necessary.
But since the value "0" is propagated into the PHI, there is no statement left
to mark "if (b)" necessary. So ignoring the edge with the constant (like the
very wrong patch of comment #3) results in *nothing* needing "if (b)" anymore.
So the function is incorrectly transformed to just "return j".
What is necessary here, is a reason to mark "if (b)" necessary, but not the
loop. But since the loop now falls through directly to the PHI for "j_1", I
don't see how...
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42906
^ permalink raw reply [flat|nested] 35+ messages in thread* [Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed
2010-01-30 16:06 [Bug tree-optimization/42906] New: " rguenth at gcc dot gnu dot org
` (4 preceding siblings ...)
2010-01-30 16:51 ` steven at gcc dot gnu dot org
@ 2010-01-30 16:53 ` rguenth at gcc dot gnu dot org
2010-01-30 16:55 ` rguenth at gcc dot gnu dot org
` (24 subsequent siblings)
30 siblings, 0 replies; 35+ messages in thread
From: rguenth at gcc dot gnu dot org @ 2010-01-30 16:53 UTC (permalink / raw)
To: gcc-bugs
------- Comment #5 from rguenth at gcc dot gnu dot org 2010-01-30 16:52 -------
(In reply to comment #3)
> Hack that may be worth trying:
> Index: tree-ssa-dce.c
> ===================================================================
> --- tree-ssa-dce.c (revision 156352)
> +++ tree-ssa-dce.c (working copy)
> @@ -683,7 +683,10 @@ propagate_necessity (struct edge_list *e
> {
> for (k = 0; k < gimple_phi_num_args (stmt); k++)
> {
> + tree t = gimple_phi_arg_def (stmt, k);
> basic_block arg_bb = gimple_phi_arg_edge (stmt, k)->src;
> + if (is_gimple_min_invariant (t))
> + continue;
> if (arg_bb != ENTRY_BLOCK_PTR
> && ! TEST_BIT (visited_control_parents, arg_bb->index))
> {
>
But that would break for example
if (i)
j = 1;
else
j = 0;
where the PHI only has constants. I think the problem is that the control
dependence for the constant is the wrong one (if we didn't have a constant
argument in the PHI but an assignment as in the original source the same
thing would happen - we'd mark an unrelated control stmt necessary).
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42906
^ permalink raw reply [flat|nested] 35+ messages in thread* [Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed
2010-01-30 16:06 [Bug tree-optimization/42906] New: " rguenth at gcc dot gnu dot org
` (5 preceding siblings ...)
2010-01-30 16:53 ` rguenth at gcc dot gnu dot org
@ 2010-01-30 16:55 ` rguenth at gcc dot gnu dot org
2010-01-30 16:58 ` rguenth at gcc dot gnu dot org
` (23 subsequent siblings)
30 siblings, 0 replies; 35+ messages in thread
From: rguenth at gcc dot gnu dot org @ 2010-01-30 16:55 UTC (permalink / raw)
To: gcc-bugs
------- Comment #6 from rguenth at gcc dot gnu dot org 2010-01-30 16:54 -------
(In reply to comment #4)
> Eh, ignore comment #3. My understanding of CD-DCE really *is* rusty :-).
>
> Being more careful now: IIRC the statement "j = 0" would have been control
> dependent on "if (b)" and marking "j = 0" would result in marking "if (b)"
> necessary.
>
> But since the value "0" is propagated into the PHI, there is no statement left
> to mark "if (b)" necessary. So ignoring the edge with the constant (like the
> very wrong patch of comment #3) results in *nothing* needing "if (b)" anymore.
> So the function is incorrectly transformed to just "return j".
>
> What is necessary here, is a reason to mark "if (b)" necessary, but not the
> loop. But since the loop now falls through directly to the PHI for "j_1", I
> don't see how...
You have the other PHI argument for that which _is_ control-dependent on
if (b) (like the constant PHI arg should be).
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42906
^ permalink raw reply [flat|nested] 35+ messages in thread* [Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed
2010-01-30 16:06 [Bug tree-optimization/42906] New: " rguenth at gcc dot gnu dot org
` (6 preceding siblings ...)
2010-01-30 16:55 ` rguenth at gcc dot gnu dot org
@ 2010-01-30 16:58 ` rguenth at gcc dot gnu dot org
2010-01-30 16:58 ` rguenth at gcc dot gnu dot org
` (22 subsequent siblings)
30 siblings, 0 replies; 35+ messages in thread
From: rguenth at gcc dot gnu dot org @ 2010-01-30 16:58 UTC (permalink / raw)
To: gcc-bugs
------- Comment #7 from rguenth at gcc dot gnu dot org 2010-01-30 16:58 -------
Indeed it works for
void bar (void);
int foo (int b, int j)
{
if (b)
{
int i;
for (i = 0; i<1000; ++i)
;
bar ();
j = 0;
}
return j;
}
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42906
^ permalink raw reply [flat|nested] 35+ messages in thread* [Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed
2010-01-30 16:06 [Bug tree-optimization/42906] New: " rguenth at gcc dot gnu dot org
` (7 preceding siblings ...)
2010-01-30 16:58 ` rguenth at gcc dot gnu dot org
@ 2010-01-30 16:58 ` rguenth at gcc dot gnu dot org
2010-01-30 17:31 ` steven at gcc dot gnu dot org
` (21 subsequent siblings)
30 siblings, 0 replies; 35+ messages in thread
From: rguenth at gcc dot gnu dot org @ 2010-01-30 16:58 UTC (permalink / raw)
To: gcc-bugs
------- Comment #8 from rguenth at gcc dot gnu dot org 2010-01-30 16:58 -------
And
int foo (int b, int j)
{
if (b)
{
int i;
for (i = 0; i<1000; ++i)
;
j = b;
}
return j;
}
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42906
^ permalink raw reply [flat|nested] 35+ messages in thread* [Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed
2010-01-30 16:06 [Bug tree-optimization/42906] New: " rguenth at gcc dot gnu dot org
` (8 preceding siblings ...)
2010-01-30 16:58 ` rguenth at gcc dot gnu dot org
@ 2010-01-30 17:31 ` steven at gcc dot gnu dot org
2010-01-30 20:32 ` steven at gcc dot gnu dot org
` (20 subsequent siblings)
30 siblings, 0 replies; 35+ messages in thread
From: steven at gcc dot gnu dot org @ 2010-01-30 17:31 UTC (permalink / raw)
To: gcc-bugs
------- Comment #9 from steven at gcc dot gnu dot org 2010-01-30 17:30 -------
The loop is also properly eliminated if I split the (critical) edge from bb6 to
bb5 the edge that brings in the constant "0" to the "j_1 = PHI <j_4(D)(2),
0(6)>".
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42906
^ permalink raw reply [flat|nested] 35+ messages in thread* [Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed
2010-01-30 16:06 [Bug tree-optimization/42906] New: " rguenth at gcc dot gnu dot org
` (9 preceding siblings ...)
2010-01-30 17:31 ` steven at gcc dot gnu dot org
@ 2010-01-30 20:32 ` steven at gcc dot gnu dot org
2010-01-30 20:56 ` rguenth at gcc dot gnu dot org
` (19 subsequent siblings)
30 siblings, 0 replies; 35+ messages in thread
From: steven at gcc dot gnu dot org @ 2010-01-30 20:32 UTC (permalink / raw)
To: gcc-bugs
------- Comment #10 from steven at gcc dot gnu dot org 2010-01-30 20:32 -------
The safe thing to do, may be to ignore self control dependence, like so:
------------------------------------------------- 8< --------------
Index: tree-ssa-dce.c
===================================================================
--- tree-ssa-dce.c (revision 156352)
+++ tree-ssa-dce.c (working copy)
@@ -390,6 +390,11 @@
gimple stmt;
basic_block cd_bb = INDEX_EDGE_PRED_BB (el, edge_number);
+ /* Ignore control dependence on BB itself. This can happen with loops
+ but since we are here, we have already made BB necessary. */
+ if (cd_bb == bb)
+ continue;
+
if (TEST_BIT (last_stmt_necessary, cd_bb->index))
continue;
SET_BIT (last_stmt_necessary, cd_bb->index);
------------------------------------------------- 8< --------------
Needs testing, but I can't do that right now. Honza, richi...?
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42906
^ permalink raw reply [flat|nested] 35+ messages in thread* [Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed
2010-01-30 16:06 [Bug tree-optimization/42906] New: " rguenth at gcc dot gnu dot org
` (10 preceding siblings ...)
2010-01-30 20:32 ` steven at gcc dot gnu dot org
@ 2010-01-30 20:56 ` rguenth at gcc dot gnu dot org
2010-01-30 21:12 ` rguenth at gcc dot gnu dot org
` (18 subsequent siblings)
30 siblings, 0 replies; 35+ messages in thread
From: rguenth at gcc dot gnu dot org @ 2010-01-30 20:56 UTC (permalink / raw)
To: gcc-bugs
------- Comment #11 from rguenth at gcc dot gnu dot org 2010-01-30 20:56 -------
I'll test it (but I wonder if find_control_dependence is to be corrected
instead).
--
rguenth at gcc dot gnu dot org changed:
What |Removed |Added
----------------------------------------------------------------------------
AssignedTo|unassigned at gcc dot gnu |rguenth at gcc dot gnu dot
|dot org |org
Status|NEW |ASSIGNED
Last reconfirmed|2010-01-30 16:37:37 |2010-01-30 20:56:15
date| |
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42906
^ permalink raw reply [flat|nested] 35+ messages in thread* [Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed
2010-01-30 16:06 [Bug tree-optimization/42906] New: " rguenth at gcc dot gnu dot org
` (11 preceding siblings ...)
2010-01-30 20:56 ` rguenth at gcc dot gnu dot org
@ 2010-01-30 21:12 ` rguenth at gcc dot gnu dot org
2010-01-30 23:04 ` rguenth at gcc dot gnu dot org
` (17 subsequent siblings)
30 siblings, 0 replies; 35+ messages in thread
From: rguenth at gcc dot gnu dot org @ 2010-01-30 21:12 UTC (permalink / raw)
To: gcc-bugs
------- Comment #12 from rguenth at gcc dot gnu dot org 2010-01-30 21:11 -------
We seem to miscompile gen*.c. I'll check out the testsuite.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42906
^ permalink raw reply [flat|nested] 35+ messages in thread* [Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed
2010-01-30 16:06 [Bug tree-optimization/42906] New: " rguenth at gcc dot gnu dot org
` (12 preceding siblings ...)
2010-01-30 21:12 ` rguenth at gcc dot gnu dot org
@ 2010-01-30 23:04 ` rguenth at gcc dot gnu dot org
2010-01-30 23:15 ` steven at gcc dot gnu dot org
` (16 subsequent siblings)
30 siblings, 0 replies; 35+ messages in thread
From: rguenth at gcc dot gnu dot org @ 2010-01-30 23:04 UTC (permalink / raw)
To: gcc-bugs
------- Comment #13 from rguenth at gcc dot gnu dot org 2010-01-30 23:04 -------
FAIL: gcc.c-torture/execute/991016-1.c execution, -O2
FAIL: gcc.c-torture/execute/loop-3.c execution, -O2
FAIL: gcc.c-torture/execute/loop-3b.c execution, -O2
FAIL: gcc.dg/doloop-2.c execution test
and other optimization levels (and more fails elsewhere).
So, it doesn't work ;)
--
rguenth at gcc dot gnu dot org changed:
What |Removed |Added
----------------------------------------------------------------------------
AssignedTo|rguenth at gcc dot gnu dot |unassigned at gcc dot gnu
|org |dot org
Status|ASSIGNED |NEW
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42906
^ permalink raw reply [flat|nested] 35+ messages in thread* [Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed
2010-01-30 16:06 [Bug tree-optimization/42906] New: " rguenth at gcc dot gnu dot org
` (13 preceding siblings ...)
2010-01-30 23:04 ` rguenth at gcc dot gnu dot org
@ 2010-01-30 23:15 ` steven at gcc dot gnu dot org
2010-02-02 13:31 ` rguenth at gcc dot gnu dot org
` (15 subsequent siblings)
30 siblings, 0 replies; 35+ messages in thread
From: steven at gcc dot gnu dot org @ 2010-01-30 23:15 UTC (permalink / raw)
To: gcc-bugs
------- Comment #14 from steven at gcc dot gnu dot org 2010-01-30 23:15 -------
Yes, it fails with all "do ... while(...)" loops, I think.
We'll have to think of something else, then.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42906
^ permalink raw reply [flat|nested] 35+ messages in thread* [Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed
2010-01-30 16:06 [Bug tree-optimization/42906] New: " rguenth at gcc dot gnu dot org
` (14 preceding siblings ...)
2010-01-30 23:15 ` steven at gcc dot gnu dot org
@ 2010-02-02 13:31 ` rguenth at gcc dot gnu dot org
2010-02-16 19:54 ` changpeng dot fang at amd dot com
` (14 subsequent siblings)
30 siblings, 0 replies; 35+ messages in thread
From: rguenth at gcc dot gnu dot org @ 2010-02-02 13:31 UTC (permalink / raw)
To: gcc-bugs
--
rguenth at gcc dot gnu dot org changed:
What |Removed |Added
----------------------------------------------------------------------------
Priority|P3 |P2
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42906
^ permalink raw reply [flat|nested] 35+ messages in thread* [Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed
2010-01-30 16:06 [Bug tree-optimization/42906] New: " rguenth at gcc dot gnu dot org
` (15 preceding siblings ...)
2010-02-02 13:31 ` rguenth at gcc dot gnu dot org
@ 2010-02-16 19:54 ` changpeng dot fang at amd dot com
2010-02-16 19:57 ` pinskia at gcc dot gnu dot org
` (13 subsequent siblings)
30 siblings, 0 replies; 35+ messages in thread
From: changpeng dot fang at amd dot com @ 2010-02-16 19:54 UTC (permalink / raw)
To: gcc-bugs
------- Comment #15 from changpeng dot fang at amd dot com 2010-02-16 19:54 -------
Hello,
I am not sure whether CD-DCE can fully replace remove_empty_loop. However,
I would prefer to keep remove_empty_loop pass. There are two reasons for
this proposal:
(1) remove_empty_loop was at level -O1 and above, but CD-DCE at -O2 and above.
(2) remove_empty_loop can be extended to handle other cases which CD-DCE is not
able to:
for(i=0; i<n; i++);
j = i;
In this case, the loop itself is "empty" and we can replace every use of the
phi with "n" (exit value of the iv).
What do you think about this (put back the empty loop removal code)? Thanks,
--
changpeng dot fang at amd dot com changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |cfang at gcc dot gnu dot org
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42906
^ permalink raw reply [flat|nested] 35+ messages in thread* [Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed
2010-01-30 16:06 [Bug tree-optimization/42906] New: " rguenth at gcc dot gnu dot org
` (16 preceding siblings ...)
2010-02-16 19:54 ` changpeng dot fang at amd dot com
@ 2010-02-16 19:57 ` pinskia at gcc dot gnu dot org
2010-03-17 0:19 ` changpeng dot fang at amd dot com
` (12 subsequent siblings)
30 siblings, 0 replies; 35+ messages in thread
From: pinskia at gcc dot gnu dot org @ 2010-02-16 19:57 UTC (permalink / raw)
To: gcc-bugs
------- Comment #16 from pinskia at gcc dot gnu dot org 2010-02-16 19:57 -------
> In this case, the loop itself is "empty" and we can replace every use of the
> phi with "n" (exit value of the iv).
I don't think that is done by remove_empty_loop anyways and it is already done
by sccp (Propagation of constants using scev) which is enabled at -O1.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42906
^ permalink raw reply [flat|nested] 35+ messages in thread* [Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed
2010-01-30 16:06 [Bug tree-optimization/42906] New: " rguenth at gcc dot gnu dot org
` (17 preceding siblings ...)
2010-02-16 19:57 ` pinskia at gcc dot gnu dot org
@ 2010-03-17 0:19 ` changpeng dot fang at amd dot com
2010-03-17 0:22 ` changpeng dot fang at amd dot com
` (11 subsequent siblings)
30 siblings, 0 replies; 35+ messages in thread
From: changpeng dot fang at amd dot com @ 2010-03-17 0:19 UTC (permalink / raw)
To: gcc-bugs
------- Comment #17 from changpeng dot fang at amd dot com 2010-03-17 00:18 -------
(In reply to comment #8)
> And
>
> int foo (int b, int j)
> {
> if (b)
> {
> int i;
> for (i = 0; i<1000; ++i)
> ;
> j = b;
> }
> return j;
> }
>
With "j=b", "b" is not folded as a phi argument:
<bb 5>:
# i_2 = PHI <0(3), i_6(4)>
if (i_2 <= 999)
goto <bb 4>;
else
goto <bb 6>;
<bb 6>:
j_7 = b_3(D);
<bb 7>:
# j_1 = PHI <j_4(D)(2), j_7(6)>
However, if "j=0", it is:
<bb 6>:
j_7 = 0;
<bb 7>:
# j_1 = PHI <j_4(D)(2), 0(6)>
j_8 = j_1;
return j_8;
Then copy propagation will remove "j_7 = 0" (and thus <bb 6>) because it has no
user.
So, one possible solution is "do not remove trival dead code" in
copy_propagation pass. Any dce pass will remove such code.
Of course, if we follow Steven's suggestion not use constants as phi arguments,
"j_7=0" will not be removed by constant propagation, and we are all fine.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42906
^ permalink raw reply [flat|nested] 35+ messages in thread* [Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed
2010-01-30 16:06 [Bug tree-optimization/42906] New: " rguenth at gcc dot gnu dot org
` (18 preceding siblings ...)
2010-03-17 0:19 ` changpeng dot fang at amd dot com
@ 2010-03-17 0:22 ` changpeng dot fang at amd dot com
2010-03-17 10:01 ` rguenther at suse dot de
` (10 subsequent siblings)
30 siblings, 0 replies; 35+ messages in thread
From: changpeng dot fang at amd dot com @ 2010-03-17 0:22 UTC (permalink / raw)
To: gcc-bugs
------- Comment #18 from changpeng dot fang at amd dot com 2010-03-17 00:22 -------
(In reply to comment #16)
> > In this case, the loop itself is "empty" and we can replace every use of the
> > phi with "n" (exit value of the iv).
>
> I don't think that is done by remove_empty_loop anyways and it is already done
> by sccp (Propagation of constants using scev) which is enabled at -O1.
>
But n "is" not a constant. Of course we can modify the pass to compute the exit
value of iv (integer overflow may be an issue).
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42906
^ permalink raw reply [flat|nested] 35+ messages in thread* [Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed
2010-01-30 16:06 [Bug tree-optimization/42906] New: " rguenth at gcc dot gnu dot org
` (19 preceding siblings ...)
2010-03-17 0:22 ` changpeng dot fang at amd dot com
@ 2010-03-17 10:01 ` rguenther at suse dot de
2010-03-18 17:24 ` changpeng dot fang at amd dot com
` (9 subsequent siblings)
30 siblings, 0 replies; 35+ messages in thread
From: rguenther at suse dot de @ 2010-03-17 10:01 UTC (permalink / raw)
To: gcc-bugs
------- Comment #19 from rguenther at suse dot de 2010-03-17 10:01 -------
Subject: Re: [4.5 Regression] Empty loop not
removed
On Wed, 17 Mar 2010, changpeng dot fang at amd dot com wrote:
>
>
> ------- Comment #17 from changpeng dot fang at amd dot com 2010-03-17 00:18 -------
> (In reply to comment #8)
> > And
> >
> > int foo (int b, int j)
> > {
> > if (b)
> > {
> > int i;
> > for (i = 0; i<1000; ++i)
> > ;
> > j = b;
> > }
> > return j;
> > }
> >
>
> With "j=b", "b" is not folded as a phi argument:
>
> <bb 5>:
> # i_2 = PHI <0(3), i_6(4)>
> if (i_2 <= 999)
> goto <bb 4>;
> else
> goto <bb 6>;
>
> <bb 6>:
> j_7 = b_3(D);
>
> <bb 7>:
> # j_1 = PHI <j_4(D)(2), j_7(6)>
>
> However, if "j=0", it is:
> <bb 6>:
> j_7 = 0;
>
> <bb 7>:
> # j_1 = PHI <j_4(D)(2), 0(6)>
> j_8 = j_1;
> return j_8;
>
> Then copy propagation will remove "j_7 = 0" (and thus <bb 6>) because it has no
> user.
>
> So, one possible solution is "do not remove trival dead code" in
> copy_propagation pass. Any dce pass will remove such code.
>
> Of course, if we follow Steven's suggestion not use constants as phi arguments,
> "j_7=0" will not be removed by constant propagation, and we are all fine.
Splitting critical edges for CDDCE will probably also solve this problem.
Richard.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42906
^ permalink raw reply [flat|nested] 35+ messages in thread* [Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed
2010-01-30 16:06 [Bug tree-optimization/42906] New: " rguenth at gcc dot gnu dot org
` (20 preceding siblings ...)
2010-03-17 10:01 ` rguenther at suse dot de
@ 2010-03-18 17:24 ` changpeng dot fang at amd dot com
2010-03-18 17:30 ` rguenther at suse dot de
` (8 subsequent siblings)
30 siblings, 0 replies; 35+ messages in thread
From: changpeng dot fang at amd dot com @ 2010-03-18 17:24 UTC (permalink / raw)
To: gcc-bugs
------- Comment #20 from changpeng dot fang at amd dot com 2010-03-18 17:24 -------
(In reply to comment #19)
> Splitting critical edges for CDDCE will probably also solve this problem.
>
> Richard.
>
Yes, splitting critical edges is an enhancement to CDDCE and can solve this
problem. There are two approaches to do this (1) add pass_split_crit_edges
before each pass_cd_dce or (2) encode split_crit_edges into cddce as an
initialization. What do you think? Thanks.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42906
^ permalink raw reply [flat|nested] 35+ messages in thread* [Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed
2010-01-30 16:06 [Bug tree-optimization/42906] New: " rguenth at gcc dot gnu dot org
` (21 preceding siblings ...)
2010-03-18 17:24 ` changpeng dot fang at amd dot com
@ 2010-03-18 17:30 ` rguenther at suse dot de
2010-03-24 18:18 ` hubicka at gcc dot gnu dot org
` (7 subsequent siblings)
30 siblings, 0 replies; 35+ messages in thread
From: rguenther at suse dot de @ 2010-03-18 17:30 UTC (permalink / raw)
To: gcc-bugs
------- Comment #21 from rguenther at suse dot de 2010-03-18 17:30 -------
Subject: Re: [4.5 Regression] Empty loop not
removed
On Thu, 18 Mar 2010, changpeng dot fang at amd dot com wrote:
> ------- Comment #20 from changpeng dot fang at amd dot com 2010-03-18 17:24 -------
> (In reply to comment #19)
> > Splitting critical edges for CDDCE will probably also solve this problem.
> >
> > Richard.
> >
>
> Yes, splitting critical edges is an enhancement to CDDCE and can solve this
> problem. There are two approaches to do this (1) add pass_split_crit_edges
> before each pass_cd_dce or (2) encode split_crit_edges into cddce as an
> initialization. What do you think? Thanks.
Ideally we'd handle this with pass properties and the pass manager
(but that requires larger changes). For now I'd do it like the crited
pass before PRE, thus schedule a new pass before CDDCEs.
I also think that we can consider not fixing this for 4.5 and
do it properly for 4.6.
Richard.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42906
^ permalink raw reply [flat|nested] 35+ messages in thread* [Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed
2010-01-30 16:06 [Bug tree-optimization/42906] New: " rguenth at gcc dot gnu dot org
` (22 preceding siblings ...)
2010-03-18 17:30 ` rguenther at suse dot de
@ 2010-03-24 18:18 ` hubicka at gcc dot gnu dot org
2010-03-24 19:02 ` hubicka at gcc dot gnu dot org
` (6 subsequent siblings)
30 siblings, 0 replies; 35+ messages in thread
From: hubicka at gcc dot gnu dot org @ 2010-03-24 18:18 UTC (permalink / raw)
To: gcc-bugs
------- Comment #22 from hubicka at gcc dot gnu dot org 2010-03-24 18:17 -------
Hi,
I am teaching CD-DCE today so I took oppurtunity to figure out what happens.
1) The original formulation by Cytron et. al. has mistake in it. It claims
that after removal of dead conditional one can take any edge and follow to it.
This was bug I was solving while ago that closes empty loop to infinite loop.
This was subsequently corrected by Rob Shiler. He added clause for redirection
of dead conditionals to nearest useful postdominator and he also use reverse
dominance frontiers instead of control dependency to mark useful statements.
2) Formulation in Cytron et al. and Morgan's textbook has both problem with not
handling PHIs specially as we do. This has nothing to do with allowing
constants in operands, but it fails on overlapping live ranges:
a_1=exp1
a_2=exp2
if (test)
empty
else
empty
a_3=phi(a_1,a_2)
here we must mark control dependency for the PHI operands.
So Steven's argument about problems with constant arguments in PHIs seems
false.
3) as Steven observed, problem is that BB6 is control dependent on itself. It
has to be. Control dependency is for basic blocks and if something in basic
block is useful, it must be executed same number of times as before. So one
can not mark as useful only the source
4) I think problem is that we mark BB as useful for PHI argument while we
really need to know if control flow arrived from that BB or other BB.
Steven is right that splitting the edge and introducing new BB on the way is
correct way to get this issue resolved.
I believe that same effect can be by modifying
mark_control_dependent_edges_necessary to exclude self control dependences when
marking PHI edges (since we are not interested in BB itself).
Say that we B is the basic block with PHI. C is BB of PHI source.
Now if B postdominates C, then C' (slpitting edge from B to C) will sit in
dominance tree just in between B and C and result of control dependence will be
same as for C just with C omitted (since C' postdominate C). This follows from
equivalency of control dependence and reverse dominance frontiers and way
reverse dominance frontiers computatio nworks.
If B does not postdominate C, then the split C' would be predecestor of B
without any succesors. We already mark reverse dominance frontier of B (since
it is live) so we should be happy here.
I am testing patch to do that, it bootstraps and solves the testcase.
Honza
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42906
^ permalink raw reply [flat|nested] 35+ messages in thread* [Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed
2010-01-30 16:06 [Bug tree-optimization/42906] New: " rguenth at gcc dot gnu dot org
` (23 preceding siblings ...)
2010-03-24 18:18 ` hubicka at gcc dot gnu dot org
@ 2010-03-24 19:02 ` hubicka at gcc dot gnu dot org
2010-03-25 17:23 ` hubicka at ucw dot cz
` (5 subsequent siblings)
30 siblings, 0 replies; 35+ messages in thread
From: hubicka at gcc dot gnu dot org @ 2010-03-24 19:02 UTC (permalink / raw)
To: gcc-bugs
------- Comment #23 from hubicka at gcc dot gnu dot org 2010-03-24 19:02 -------
Created an attachment (id=20188)
--> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=20188&action=view)
Patch in testing
Hi,
this is patch I am testing.
I was also re-thinking the problem of redirecting BB with dead conditional to
next useful postdominator (that is the "fixed" version of algorihm by shiller).
I am not convinced we can pick random PHI argument here as Richard changed my
original code looking for source of control dependent graph.
The testcase would be something like
BB1 with succesors BB2 and BB6
BB2 with succesors BB3 and BB4
BB3 and BB4 with succesors BB5
and BB6 containing PHI that is A from BB1 and B from BB3 or BB4
If we end up eliminating BB3 and BB4 and thus condition in BB3, we will
redirect BB3 to BB5. The argument of PHI however must be updated to B for new
edge, not A as we pick currently.
I will try to create real world testcase and I think we can fix this by
avoidiging the redirection. Cytron et al suggest using random edge leaving BB
with dead conditional. This is wrong since it closes infinite loops. I think
we can instead of that just pick random edge that is not loopback edge in DFS.
That won't close loops and will result in acyclic reverse EBBS of empty blocks
we easilly cleanup afterwards.
Honza
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42906
^ permalink raw reply [flat|nested] 35+ messages in thread* [Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed
2010-01-30 16:06 [Bug tree-optimization/42906] New: " rguenth at gcc dot gnu dot org
` (24 preceding siblings ...)
2010-03-24 19:02 ` hubicka at gcc dot gnu dot org
@ 2010-03-25 17:23 ` hubicka at ucw dot cz
2010-03-27 18:31 ` hubicka at gcc dot gnu dot org
` (4 subsequent siblings)
30 siblings, 0 replies; 35+ messages in thread
From: hubicka at ucw dot cz @ 2010-03-25 17:23 UTC (permalink / raw)
To: gcc-bugs
------- Comment #24 from hubicka at ucw dot cz 2010-03-25 17:22 -------
Subject: Re: [4.5 Regression] Empty loop not
removed
Hi,
this is updated version of patch that bootstraps/regtests. In previous one
there was bug that BB was marked when processed even when only edge was
processed. cc1plus binary seems for some reason 5k smaller now, tramp3d does
not change.
Honza
------- Comment #25 from hubicka at ucw dot cz 2010-03-25 17:22 -------
Created an attachment (id=20200)
--> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=20200&action=view)
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42906
^ permalink raw reply [flat|nested] 35+ messages in thread* [Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed
2010-01-30 16:06 [Bug tree-optimization/42906] New: " rguenth at gcc dot gnu dot org
` (25 preceding siblings ...)
2010-03-25 17:23 ` hubicka at ucw dot cz
@ 2010-03-27 18:31 ` hubicka at gcc dot gnu dot org
2010-04-06 11:26 ` rguenth at gcc dot gnu dot org
` (3 subsequent siblings)
30 siblings, 0 replies; 35+ messages in thread
From: hubicka at gcc dot gnu dot org @ 2010-03-27 18:31 UTC (permalink / raw)
To: gcc-bugs
------- Comment #26 from hubicka at gcc dot gnu dot org 2010-03-27 18:31 -------
Patch queued for next stage1
--
hubicka at gcc dot gnu dot org changed:
What |Removed |Added
----------------------------------------------------------------------------
AssignedTo|unassigned at gcc dot gnu |hubicka at gcc dot gnu dot
|dot org |org
Status|NEW |ASSIGNED
Last reconfirmed|2010-01-30 20:56:15 |2010-03-27 18:31:13
date| |
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42906
^ permalink raw reply [flat|nested] 35+ messages in thread* [Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed
2010-01-30 16:06 [Bug tree-optimization/42906] New: " rguenth at gcc dot gnu dot org
` (26 preceding siblings ...)
2010-03-27 18:31 ` hubicka at gcc dot gnu dot org
@ 2010-04-06 11:26 ` rguenth at gcc dot gnu dot org
2010-04-06 11:38 ` hubicka at ucw dot cz
` (2 subsequent siblings)
30 siblings, 0 replies; 35+ messages in thread
From: rguenth at gcc dot gnu dot org @ 2010-04-06 11:26 UTC (permalink / raw)
To: gcc-bugs
------- Comment #27 from rguenth at gcc dot gnu dot org 2010-04-06 11:20 -------
GCC 4.5.0 is being released. Deferring to 4.5.1.
--
rguenth at gcc dot gnu dot org changed:
What |Removed |Added
----------------------------------------------------------------------------
Target Milestone|4.5.0 |4.5.1
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42906
^ permalink raw reply [flat|nested] 35+ messages in thread* [Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed
2010-01-30 16:06 [Bug tree-optimization/42906] New: " rguenth at gcc dot gnu dot org
` (27 preceding siblings ...)
2010-04-06 11:26 ` rguenth at gcc dot gnu dot org
@ 2010-04-06 11:38 ` hubicka at ucw dot cz
2010-04-06 15:19 ` hubicka at gcc dot gnu dot org
2010-07-31 9:35 ` rguenth at gcc dot gnu dot org
30 siblings, 0 replies; 35+ messages in thread
From: hubicka at ucw dot cz @ 2010-04-06 11:38 UTC (permalink / raw)
To: gcc-bugs
------- Comment #28 from hubicka at ucw dot cz 2010-04-06 11:37 -------
Subject: Re: [4.5 Regression] Empty loop not
removed
I will apply the CD-DCE fix to pretty IPA tomorrow (after testing the inliner
problems) so we get some extra testing for that patch too.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42906
^ permalink raw reply [flat|nested] 35+ messages in thread* [Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed
2010-01-30 16:06 [Bug tree-optimization/42906] New: " rguenth at gcc dot gnu dot org
` (28 preceding siblings ...)
2010-04-06 11:38 ` hubicka at ucw dot cz
@ 2010-04-06 15:19 ` hubicka at gcc dot gnu dot org
2010-07-31 9:35 ` rguenth at gcc dot gnu dot org
30 siblings, 0 replies; 35+ messages in thread
From: hubicka at gcc dot gnu dot org @ 2010-04-06 15:19 UTC (permalink / raw)
To: gcc-bugs
------- Comment #29 from hubicka at gcc dot gnu dot org 2010-04-06 15:18 -------
Subject: Bug 42906
Author: hubicka
Date: Tue Apr 6 15:18:18 2010
New Revision: 158004
URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=158004
Log:
PR tree-optimization/42906
* tree-ssa-dce.c (mark_control_dependent_edges_necessary): Add
IGNORE_SELF
argument; set visited_control_parents for fully processed BBs.
(find_obviously_necessary_stmts): Update call of
mark_control_dependent_edges_necessary.
(propagate_necessity): Likewise; handle PHI edges more curefully.
* gcc.dg/tree-ssa/dce-1.c: New testcase.
Added:
trunk/gcc/testsuite/gcc.dg/tree-ssa/dce-1.c
Modified:
trunk/gcc/ChangeLog
trunk/gcc/testsuite/ChangeLog
trunk/gcc/tree-ssa-dce.c
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42906
^ permalink raw reply [flat|nested] 35+ messages in thread* [Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed
2010-01-30 16:06 [Bug tree-optimization/42906] New: " rguenth at gcc dot gnu dot org
` (29 preceding siblings ...)
2010-04-06 15:19 ` hubicka at gcc dot gnu dot org
@ 2010-07-31 9:35 ` rguenth at gcc dot gnu dot org
30 siblings, 0 replies; 35+ messages in thread
From: rguenth at gcc dot gnu dot org @ 2010-07-31 9:35 UTC (permalink / raw)
To: gcc-bugs
------- Comment #30 from rguenth at gcc dot gnu dot org 2010-07-31 09:29 -------
GCC 4.5.1 is being released, adjusting target milestone.
--
rguenth at gcc dot gnu dot org changed:
What |Removed |Added
----------------------------------------------------------------------------
Target Milestone|4.5.1 |4.5.2
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42906
^ permalink raw reply [flat|nested] 35+ messages in thread