[Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed

[Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed

[rguenth at gcc dot gnu.org]

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

Richard Guenther <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.5.2                       |4.5.3

--- Comment #31 from Richard Guenther <rguenth at gcc dot gnu.org> 2010-12-16 13:02:50 UTC ---
GCC 4.5.2 is being released, adjusting target milestone.

[Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed

[rguenth at gcc dot gnu.org]

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

Richard Guenther <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.5.3                       |4.5.4

--- Comment #32 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-04-28 14:51:04 UTC ---
GCC 4.5.3 is being released, adjusting target milestone.

[Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed

[hubicka at gcc dot gnu.org]

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

Jan Hubicka <hubicka at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |NEW
      Known to work|                            |
         AssignedTo|hubicka at gcc dot gnu.org  |unassigned at gcc dot
                   |                            |gnu.org

--- Comment #33 from Jan Hubicka <hubicka at gcc dot gnu.org> 2012-03-23 14:51:20 UTC ---
Unassinging. Solved in 4.6+; no plans to backport this to 4.5.

[Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed

[rguenth at gcc dot gnu.org]

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

Richard Guenther <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |FIXED
   Target Milestone|4.5.4                       |4.6.0

--- Comment #34 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-07-02 10:29:01 UTC ---
Fixed in 4.6.0, the 4.5 branch is being closed.

[Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed

[rguenth at gcc dot gnu dot org]

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

[Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed

[hubicka at gcc dot gnu dot org]

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

[Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed

[hubicka at ucw dot cz]

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

[Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed

[rguenth at gcc dot gnu dot org]

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

[Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed

[hubicka at gcc dot gnu dot org]

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

[Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed

[hubicka at ucw dot cz]

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

[Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed

[hubicka at gcc dot gnu dot org]

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

[Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed

[hubicka at gcc dot gnu dot org]

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

[Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed

[rguenther at suse dot de]

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

[Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed

[changpeng dot fang at amd dot com]

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

[Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed

[rguenther at suse dot de]

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

[Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed

[changpeng dot fang at amd dot com]

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

[Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed

[changpeng dot fang at amd dot com]

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

[Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed

[pinskia at gcc dot gnu dot org]

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

[Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed

[changpeng dot fang at amd dot com]

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

[Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed

[rguenth at gcc dot gnu dot org]

-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P2


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

[Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed

[steven at gcc dot gnu dot org]

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

[Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed

[rguenth at gcc dot gnu dot org]

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

[Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed

[rguenth at gcc dot gnu dot org]

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

[Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed

[rguenth at gcc dot gnu dot org]

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

[Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed

[steven at gcc dot gnu dot org]

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

[Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed

[steven at gcc dot gnu dot org]

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

[Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed

[rguenth at gcc dot gnu dot org]

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

[Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed

[rguenth at gcc dot gnu dot org]

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

[Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed

[rguenth at gcc dot gnu dot org]

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

[Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed

[rguenth at gcc dot gnu dot org]

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

[Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed

[steven at gcc dot gnu dot org]

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

[Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed

[steven at gcc dot gnu dot org]

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

[Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed

[steven at gcc dot gnu dot org]

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

[Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed

[steven at gcc dot gnu dot org]

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

[Bug tree-optimization/42906] [4.5 Regression] Empty loop not removed

[rguenth at gcc dot gnu dot org]

-- 

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