[Bug tree-optimization/96487] New: cddce1 optimizer depends on order of basic blocks

[Bug tree-optimization/96487] New: cddce1 optimizer depends on order of basic blocks

[sandra at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=96487

            Bug ID: 96487
           Summary: cddce1 optimizer depends on order of basic blocks
           Product: gcc
           Version: 11.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: sandra at gcc dot gnu.org
  Target Milestone: ---

Created attachment 49007
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=49007&action=edit
c and c++ dump files

If the test case gcc.dg/tree-ssa/ssa-dce-3.c is compiled as C++ code
instead of as C, it fails to reduce to an empty loop as expected.

It seems to be triggered by a slight difference in the input coming
into the cddce1 pass.  The C front end canonicalizes the test to the
end of the loop so the latch (bb 5) falls through to the header (bb
6).  The C++ front end orders the latch (bb 6) last with a goto to the
header (bb 3).

I did some additional tracing of the flow through the pass beyond the
dump file output.  Because the latch in the C input does not end with
a control statement, it is ignored by mark_last_stmt_necessary, via
the call to mark_control_dependent_edges_necessary at the end of
find_obviously_necessary_stmts.  So in the C case, nothing gets added
to the work list, while for C++ it does process the latch block,
follow the control flow out of it, and ends up marking the loop end
test etc as necessary.

I am wondering if this is a bug in the way the C output is handled and
it is incorrectly optimizing away the loop body.  It seems like it
should not matter if the control transfer between blocks is done via
explicit goto or via fallthrough, anyway; either it ought to handle
the fallthrough case like the explicit goto case, or vice versa.

I originally noticed this problem in conjunction with these patches to
unify the loop handling in the C and C++ front ends:

https://gcc.gnu.org/pipermail/gcc-patches/2019-November/534142.html

But it can be reproduced with unmodified sources just by compiling
with g++ instead of gcc.  The commands used to produce the attached
dump files were

x86_64-linux-gnu-gcc /path/to/gcc/testsuite/gcc.dg/tree-ssa/ssa-dce-3.c  -O2
-fdump-tree-dse1 -fdump-tree-cddce1-details -S

x86_64-linux-gnu-g++ /path/to/gcc/testsuite/gcc.dg/tree-ssa/ssa-dce-3.c  -O2
-fdump-tree-dse1 -fdump-tree-cddce1-details -S

[Bug tree-optimization/96487] cddce1 optimizer depends on order of basic blocks

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=96487

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2020-08-06
     Ever confirmed|0                           |1
                 CC|                            |hubicka at gcc dot gnu.org,
                   |                            |rguenth at gcc dot gnu.org
             Status|UNCONFIRMED                 |NEW
           Keywords|                            |missed-optimization

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
I think the issue is that control dependence looks different - for C the latch
is control dependent on itself while for C++ it ends up being control dependent
on the outgoing edges from the conditional that ends up being marked necessary.
I guess both answers are somewhat "wrong" but it boils down to the
testcase not having any edges to exit and thus post-dominance being somewhat
ill-defined.  Doing connect_infinite_loops_to_exit () doesn't help because
that as well makes different decisions based on the BB order.

So the question is whether DCE should do sth different than marking
control dependent edges of each non-finites loop latch, especially in
the case where the loop has no exit (if there are exits we should get
to the "first" exit test - that's the whole idea here).  That is,
if there's no exit maybe simply mark the latch as bb_contains_live_stmts?

diff --git a/gcc/tree-ssa-dce.c b/gcc/tree-ssa-dce.c
index fae5ae72340..a66fc34c9e5 100644
--- a/gcc/tree-ssa-dce.c
+++ b/gcc/tree-ssa-dce.c
@@ -450,7 +450,10 @@ find_obviously_necessary_stmts (bool aggressive)
          {
            if (dump_file)
              fprintf (dump_file, "cannot prove finiteness of loop %i\n",
loop->num);
-           mark_control_dependent_edges_necessary (loop->latch, false);
+           if (loop->exits->next->e)
+             mark_control_dependent_edges_necessary (loop->latch, false);
+           else
+             bitmap_set_bit (bb_contains_live_stmts, loop->latch->index);
          }
     }
 }

[Bug tree-optimization/96487] cddce1 optimizer depends on order of basic blocks

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=96487

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           See Also|                            |https://gcc.gnu.org/bugzill
                   |                            |a/show_bug.cgi?id=45178,
                   |                            |https://gcc.gnu.org/bugzill
                   |                            |a/show_bug.cgi?id=102893

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #1)
> diff --git a/gcc/tree-ssa-dce.c b/gcc/tree-ssa-dce.c
> index fae5ae72340..a66fc34c9e5 100644
> --- a/gcc/tree-ssa-dce.c
> +++ b/gcc/tree-ssa-dce.c
> @@ -450,7 +450,10 @@ find_obviously_necessary_stmts (bool aggressive)
>           {
>             if (dump_file)
>               fprintf (dump_file, "cannot prove finiteness of loop %i\n",
> loop->num);
> -           mark_control_dependent_edges_necessary (loop->latch, false);
> +           if (loop->exits->next->e)
> +             mark_control_dependent_edges_necessary (loop->latch, false);
> +           else
> +             bitmap_set_bit (bb_contains_live_stmts, loop->latch->index);
>           }
>      }
>  }

A similar patch to the above was applied for PR 45178 (and then fixed such that
it is does the ->e part for PR 102893) ...

So is this fixed now?

[Bug tree-optimization/96487] cddce1 optimizer depends on order of basic blocks

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=96487

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|---                         |FIXED

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
Yes, I think so (verified the testcase).