[Bug c++/99101] New: optimization bug with -ffinite-loops

[Bug c++/99101] New: optimization bug with -ffinite-loops

[251078896 at qq dot com]

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

            Bug ID: 99101
           Summary: optimization bug with -ffinite-loops
           Product: gcc
           Version: og10 (devel/omp/gcc-10)
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: 251078896 at qq dot com
  Target Milestone: ---

we have a reduced code to show this bug:

#include <iostream>

class CompactMD {
 public:
  void operator()() {
    while (true) {
      auto num_job = jobs_;
      for (auto i = 0; i < jobs_; i++) SendNextMd();
      jobs_ -= num_job;
    }
  }
  void SendNextMd() {
    if (at_eof_) return;
    if (read_finish_) {
      at_eof_ = true;
      std::cout << 1 << std::endl;
    }
  }

  bool read_finish_ = true;
  int jobs_{1};
  bool at_eof_{false};
};

int main() {
  CompactMD comp_md_;
  comp_md_();
  return 0;
}

The expected output is only one line of "1", after that the program should be
in a "while true" loop forever.
With O2 optimization level, the output are infinite lines of "1"s.

We can reproduce this in RedHat's devtoolset-10, and Ubuntu 20.10's bundled
gcc10. After some tests, I find this bug is related to -ffinite-loops

This bug cannot be reproduced with gcc9 or lower version.

btw, I cannot further simplify this code for now, any change to it the bug is
likely to be gone.

[Bug tree-optimization/99101] optimization bug with -ffinite-loops

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Version|og10 (devel/omp/gcc-10)     |11.0
             Status|UNCONFIRMED                 |ASSIGNED
           Assignee|unassigned at gcc dot gnu.org      |rguenth at gcc dot gnu.org
           Keywords|                            |wrong-code
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2021-02-15
          Component|c++                         |tree-optimization

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
Confirmed.  But note that C++ requires forward progress and thus technically
the infinite loop invokes undefined behavior.

CDDCE2 does (with -fno-tree-sra to show at_eof_)

Assume loop 1 to be finite: it has an exit and -ffinite-loops is on.
Removing basic block 14

   <bb 2> [local count: 1073741824]:
-  comp_md_.at_eof_ = 0;

   <bb 3> [local count: 108447916235]:
-  # prephitmp_47 = PHI <1(2), 0(15)>
-  # prephitmp_22 = PHI <0(2), prephitmp_27(15)>
-  if (prephitmp_47 > 0)
-    goto <bb 16>; [33.00%]
-  else
-    goto <bb 15>; [67.00%]
-
-  <bb 16> [local count: 35787812164]:
-
-  <bb 4> [local count: 53412352861]:
-  # i_9 = PHI <i_8(14), 0(16)>
-  # prephitmp_11 = PHI <pretmp_2(14), prephitmp_22(16)>
-  if (prephitmp_11 != 0)
-    goto <bb 12>; [34.00%]
-  else
-    goto <bb 5>; [66.00%]
-
-  <bb 5> [local count: 11633210387]:
-  comp_md_.at_eof_ = 1;
   _14 = std::basic_ostream<char>::operator<< (&cout, 1);
   _15 = _14->_vptr.basic_ostream;
   _16 = MEM[(long int *)_15 + -24B];
@@ -99,28 +88,12 @@
   _43 = OBJ_TYPE_REF(_37;(const struct ctype)_23->6) (_23, 10);
   _10 = (int) _43;

-  <bb 11> [local count: 11628557050]:
+  <bb 11> [local count: 53407699675]:
   # prephitmp_24 = PHI <_13(8), 10(9), _10(10)>
   _21 = std::basic_ostream<char>::put (_14, prephitmp_24);
   std::basic_ostream<char>::flush (_21);

-  <bb 12> [local count: 53407699675]:
-  i_8 = i_9 + 1;
-  if (i_8 < prephitmp_47)
-    goto <bb 14>; [33.00%]
-  else
-    goto <bb 13>; [67.00%]
-
-  <bb 13> [local count: 35783158878]:
-  pretmp_25 = comp_md_.at_eof_;
-  goto <bb 15>; [100.00%]
-
-  <bb 14> [local count: 17624540797]:
-  pretmp_2 = comp_md_.at_eof_;
-  goto <bb 4>; [100.00%]
-
   <bb 15> [local count: 108443262898]:
-  # prephitmp_27 = PHI <pretmp_25(13), prephitmp_22(3)>
   goto <bb 3>; [100.00%]

 }

so the question would be why the std::cout << 1 call doesn't add its
control dependence as necessary here.  Hmm, and the reason is we have
BB 5 only control dependent on itself.

And I have a hunch that this boils down to post dominators being
"wrong" here because of the missing edges to exit.  Indeed if
connecting infinite loops to exit in CD-DCE the bug is fixed.

[Bug tree-optimization/99101] optimization bug with -ffinite-loops

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |amker at gcc dot gnu.org

--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
And the heuristic in post-dom compute for infinite loops does not trigger
because we do have an exit from the loop via EH which is noreturn and the
processing
of those CFG dead-ends first makes the loop reverse reachable but makes
post-dominance "wrong".

Bin, you poked into this code recently as well, just in case you have any
thoughts.

It might be that control dependence calculation should not use post dominators.

[Bug tree-optimization/99101] optimization bug with -ffinite-loops

[251078896 at qq dot com]

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

--- Comment #3 from Rex <251078896 at qq dot com> ---
Dear Richard,

Your post is informative, but I can't follow them all. Where does those "<bb
2>", "basic block 14", "local count" come from? I'm very interested in this
kind of analysis (and tools). Could you give a hint to me? Thank you very
much.(In reply to Richard Biener from comment #2)
> And the heuristic in post-dom compute for infinite loops does not trigger
> because we do have an exit from the loop via EH which is noreturn and the
> processing
> of those CFG dead-ends first makes the loop reverse reachable but makes
> post-dominance "wrong".
> 
> Bin, you poked into this code recently as well, just in case you have any
> thoughts.
> 
> It might be that control dependence calculation should not use post
> dominators.

(In reply to Richard Biener from comment #2)
> And the heuristic in post-dom compute for infinite loops does not trigger
> because we do have an exit from the loop via EH which is noreturn and the
> processing
> of those CFG dead-ends first makes the loop reverse reachable but makes
> post-dominance "wrong".
> 
> Bin, you poked into this code recently as well, just in case you have any
> thoughts.
> 
> It might be that control dependence calculation should not use post
> dominators.

[Bug tree-optimization/99101] optimization bug with -ffinite-loops

[jakub at gcc dot gnu.org]

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

--- Comment #4 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
If there are EH edges, doesn't it fit then the -ffinite-loops description:
'-ffinite-loops'
     Assume that a loop with an exit will eventually take the exit and
     not loop indefinitely.  This allows the compiler to remove loops
     that otherwise have no side-effects, not considering eventual
     endless looping as such.

     This option is enabled by default at '-O2' for C++ with -std=c++11
     or higher.
?  EH is an exit as well...

[Bug tree-optimization/99101] optimization bug with -ffinite-loops

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |matz at gcc dot gnu.org

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
Oh, and that connect_infinite_loops_to_exit () chooses to connect the loop
(fine)
and not the noreturn exit block is pure luck.  So the fix that works isn't
really a fix.

The bogus control dependence we end up is that we make BB5 dependent on the
edge 5->7 since BB5 controls the exit and thus 5->7 is a backedge and 5
becomes controlled by itself [only].

I guess that's not even technically wrong as to the definition of control
dependence with regard to paths to exit.  Meh.

[Bug tree-optimization/99101] optimization bug with -ffinite-loops

[rguenth at gcc dot gnu.org]

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

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Jakub Jelinek from comment #4)
> If there are EH edges, doesn't it fit then the -ffinite-loops description:
> '-ffinite-loops'
>      Assume that a loop with an exit will eventually take the exit and
>      not loop indefinitely.  This allows the compiler to remove loops
>      that otherwise have no side-effects, not considering eventual
>      endless looping as such.
> 
>      This option is enabled by default at '-O2' for C++ with -std=c++11
>      or higher.
> ?  EH is an exit as well...

Note the exit isn't an EH edge (sorry for misleading), it's a conditional
controlled exit to noreturn std::__throw_bad_cast ():

  <bb 5> [local count: 11633210387]:
  comp_md_.at_eof_ = 1;
  _14 = std::basic_ostream<char>::operator<< (&cout, 1);
  _15 = _14->_vptr.basic_ostream;
  _16 = MEM[(long int *)_15 + -24B];
  _17 = (sizetype) _16;
  _18 = _14 + _17;
  _23 = MEM[(const struct __ctype_type * *)_18 + 240B];
  if (_23 == 0B)
    goto <bb 6>; [0.04%]
  else
    goto <bb 7>; [99.96%]

  <bb 6> [local count: 4653337]:
  std::__throw_bad_cast ();

and handling this call first in the post-dom DFS when walking not
reverse reachable blocks makes control dependence behave wrong (or
CD-DCEs expectation is).

Note _not_ treating EH or abnormals as exit makes us more conservative
(we consider the loop to be _not_ finite then).

Again, sorry for misleading.

[Bug tree-optimization/99101] optimization bug with -ffinite-loops

[rguenth at gcc dot gnu.org]

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

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> ---
So

@@ -1661,6 +1662,7 @@ perform_tree_ssa_dce (bool aggressive)
   if (aggressive)
     {
       /* Compute control dependence.  */
+      connect_infinite_loops_to_exit ();
       calculate_dominance_info (CDI_POST_DOMINATORS);
       cd = new control_dependences ();


"fixes" it (plus related changes), but

@@ -1661,6 +1662,7 @@ perform_tree_ssa_dce (bool aggressive)
   if (aggressive)
     {
       /* Compute control dependence.  */
+      add_noreturn_fake_exit_edges ();
+      connect_infinite_loops_to_exit ();
       calculate_dominance_info (CDI_POST_DOMINATORS);
       cd = new control_dependences ();


breaks it again.  Similar to perturbing block numbering in a way so that
connect_infinite_loops_to_exit would first visit the noreturn block.

[Bug tree-optimization/99101] optimization bug with -ffinite-loops

[rguenth at gcc dot gnu.org]

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

--- Comment #8 from Richard Biener <rguenth at gcc dot gnu.org> ---
The following reduced testcase fails in the described way at -O2 with the C++
FE and with the C FE if you specify -ffinite-loops in addition to -O2.  Already
CDDCE1 does the problematic transform which means the first breakpoint
hit on perform_tree_ssa_dce is the problematic one easing further
investigation.

volatile int xx;
int main()
{
  int read_finish_ = 1;
  int jobs_ = 1;
  int at_eof_ = 0;
  while (1)
    {
      int num_job = jobs_;
      for (int i = 0; i < jobs_; i++)
        {
          if (at_eof_) continue;
          if (read_finish_)
            {
              at_eof_ = 1;
              __builtin_printf ("1\n");
              if (xx)
                __builtin_abort ();
            }
        }
      jobs_ -= num_job;
    }
  return 0;
}

[Bug tree-optimization/99101] optimization bug with -ffinite-loops

[rguenth at gcc dot gnu.org]

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

--- Comment #9 from Richard Biener <rguenth at gcc dot gnu.org> ---
Another fix for the finite-loop issue would be to avoid considering loops not
post-dominated by the exit block as finite.  Like with the imperfect

diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c
index 3817ec423e7..388c03ee6fc 100644
--- a/gcc/tree-ssa-loop-niter.c
+++ b/gcc/tree-ssa-loop-niter.c
@@ -2865,6 +2865,16 @@ finite_loop_p (class loop *loop)
       FOR_EACH_VEC_ELT (exits, i, ex)
        if (!(ex->flags & (EDGE_EH | EDGE_ABNORMAL | EDGE_FAKE)))
          {
+           /* But do not count noreturn regions as exit.
+              ???  This is a to simple check, we'd have to either
+              use post-dominance by the exit block (which isn't
+              computed) or a DFS walk.  See PR99101 where the
+              the fact that control dependence (and post-dominance)
+              is not well-defined for not backward reachable regions
+              causes issues otherwise.  */
+           if (ex->dest->index != EXIT_BLOCK
+               && EDGE_COUNT (ex->dest->succs) == 0)
+             continue;
            if (dump_file)
              fprintf (dump_file, "Assume loop %i to be finite: it has an exit
"
                       "and -ffinite-loops is on.\n", loop->num);

but that still leaves post-dominance and thus control dependence not
well-defined in not backwards reachable regions and thus possibly "bogus"
control-dependent DCE decisions in those.  Note even with the above
CD-DCE will then use control-dependence to make the loop control necessary:

      FOR_EACH_LOOP (loop, 0)
        if (!finite_loop_p (loop))
          {
            if (dump_file)
              fprintf (dump_file, "cannot prove finiteness of loop %i\n",
loop->num);
            mark_control_dependent_edges_necessary (loop->latch, false);
          }

Which means to be absolutely sure we could use non-CD DCE whenever there
are not backwards reachable blocks in the function.

[Bug tree-optimization/99101] optimization bug with -ffinite-loops

[rguenth at gcc dot gnu.org]

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

--- Comment #10 from Richard Biener <rguenth at gcc dot gnu.org> ---
Created attachment 50248
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=50248&action=edit
dot of the CFG as CD-DCE sees it

[Bug tree-optimization/99101] optimization bug with -ffinite-loops

[rguenth at gcc dot gnu.org]

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

--- Comment #11 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #10)
> Created attachment 50248 [details]
> dot of the CFG as CD-DCE sees it

(gdb) p debug_dominance_info (CDI_POST_DOMINATORS)
2 3
3 11
4 6
5 9
6 7
7 1
9 11
11 4
12 3

[Bug tree-optimization/99101] optimization bug with -ffinite-loops

[rguenth at gcc dot gnu.org]

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

--- Comment #12 from Richard Biener <rguenth at gcc dot gnu.org> ---
So we can massage post-dom compute to make control dependence which is defined
in terms of pdom do what we want.  We have

void
dom_info::calc_dfs_tree ()
{
...
      /* In the post-dom case we may have nodes without a path to EXIT_BLOCK.
         They are reverse-unreachable.  In the dom-case we disallow such
         nodes, but in post-dom we have to deal with them.

         There are two situations in which this occurs.  First, noreturn
         functions.  Second, infinite loops.  In the first case we need to
         pretend that there is an edge to the exit block.  In the second
         case, we wind up with a forest.  We need to process all noreturn
         blocks before we know if we've got any infinite loops.  */

which then first visits blocks w/o successors, breaking our expectations.

So with that in mind indeed connecting infinite loops to exit would
circumvent the issue, but connect_infinite_loops_to_exit does not
reliably avoid making the edge from the noreturn block (if that came first),
dfs_find_deadend also likes noreturn blocks very much.

Heuristically one could use loop info, but that fails to work for irreducible
regions.  One could also use marked backedges from a forward DFS walk
(blocks with just backedges outgoing).

[Bug tree-optimization/99101] optimization bug with -ffinite-loops

[rguenth at gcc dot gnu.org]

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

--- Comment #13 from Richard Biener <rguenth at gcc dot gnu.org> ---
Created attachment 50253
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=50253&action=edit
patch to streamline connect_infinite_loops_to_exit

I'm considering this patch to make connect_infinite_loops_to_exit first connect
noreturn blocks and only then process remaining unreachable blocks.  For the
testcase this avoids ending up with two fake edges to exit but it also means
connect_inifinite_loops_to_exit no longer fixes the bug.

I guess the function is then badly named (it was before) and it should instead
be named add_fake_exit_edges or so, or
connect_backwards_unreachable_blocks_to_exit.

[Bug tree-optimization/99101] optimization bug with -ffinite-loops

[rguenth at gcc dot gnu.org]

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

--- Comment #14 from Richard Biener <rguenth at gcc dot gnu.org> ---
Oh, and the testcase does not require the abort () call but can do with a
regular exit and no unreachable blocks:

volatile int xx;
int main()
{
  int read_finish_ = 1;
  int jobs_ = 1;
  int at_eof_ = 0;
  while (1)
    {
      int num_job = jobs_;
      for (int i = 0; i < jobs_; i++)
        {
          if (at_eof_) continue;
          if (read_finish_)
            {
              at_eof_ = 1;
              __builtin_printf ("1\n");
              if (xx)
                return 1;
            }
        }
      jobs_ -= num_job;
    }
  return 0;
}

but it then of course shows the same post-dominance structure and thus
exhibits the same control dependences which do not agree with what
CD-DCE expects.

[Bug tree-optimization/99101] optimization bug with -ffinite-loops

[rguenth at gcc dot gnu.org]

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

--- Comment #15 from Richard Biener <rguenth at gcc dot gnu.org> ---
Further simplified, but still depends on -ffinite-loops

volatile int xx;
int main()
{
  int jobs_ = 1;
  int at_eof_ = 0;
  while (1)
    {
      for (int i = 0; i < jobs_; i++)
        {
          if (at_eof_)
            continue;
          at_eof_ = 1;
          __builtin_printf ("1\n");
          if (xx)
            return 1;
        }
      jobs_ = 0;
    }
  return 0;
}

if one exchanges the at_eof_ test with a function call like if (at_eof ()) then
the side-effect of at_eof() marks the if necessary by means of the block
being control dependent on itself.

[Bug tree-optimization/99101] optimization bug with -ffinite-loops

[rguenth at gcc dot gnu.org]

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

--- Comment #16 from Richard Biener <rguenth at gcc dot gnu.org> ---
Of course since -ffinite-loops and the C++ standard require forward progress
here and all testcases expect the loop to not terminate we're in the realm of
undefined behavior.  But I'm not yet convinced the control-dependence / CD-DCE
issue only shows up in such cases.  That said, it's fully expected that

int xx;
int main()
{
  int jobs_ = 1;
  int at_eof_ = 0;
  while (1)
    {
      for (int i = 0; i < jobs_; i++)
        {
          if (at_eof_)
            continue;
          at_eof_ = 1;
          if (xx)
            return 1;
        }
      jobs_ = 0;
    }
  return 0;
}

is eventually optimized to just return 1 with -ffinite-loops and we should
try to preserve that behavior.

[Bug tree-optimization/99101] optimization bug with -ffinite-loops

[matz at gcc dot gnu.org]

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

--- Comment #17 from Michael Matz <matz at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #16)
> Of course since -ffinite-loops and the C++ standard require forward progress
> here and all testcases expect the loop to not terminate we're in the realm
> of undefined behavior.  But I'm not yet convinced the control-dependence /
> CD-DCE issue only shows up in such cases.  That said, it's fully expected
> that
> 
> int xx;
> int main()
> {
>   int jobs_ = 1;
>   int at_eof_ = 0;
>   while (1)
>     {
>       for (int i = 0; i < jobs_; i++)
>         {
>           if (at_eof_)
>             continue;
>           at_eof_ = 1;
>           if (xx)
>             return 1;
>         }
>       jobs_ = 0;
>     }
>   return 0;
> }
> 
> is eventually optimized to just return 1 with -ffinite-loops and we should
> try to preserve that behavior.

Just commenting on this last statement: I think that's wrong.  It's provable
that 'xx' doesn't change in the loop, and that it starts out as 0 (this is main
here).  So in fact we have produced an endless loop without a return, and hence
can do anything (when endless loops are undefined).

[Bug tree-optimization/99101] optimization bug with -ffinite-loops

[matz at gcc dot gnu.org]

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

--- Comment #18 from Michael Matz <matz at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #11)
> (In reply to Richard Biener from comment #10)
> > Created attachment 50248 [details]
> > dot of the CFG as CD-DCE sees it
> 
> (gdb) p debug_dominance_info (CDI_POST_DOMINATORS)
> 2 3
> 3 11
> 4 6
> 5 9
> 6 7
> 7 1
> 9 11
> 11 4
> 12 3

So, on IRC you said that the at_eof is completely eliminated.  I wonder why.
It's true that bb6 post-dominates bb4, hence bb6 is not control dependend on
bb4.

But there are other blocks control dependend on bb4, namely bb5 and bb9.
To see this observe that bb9 doesn't pdom bb4, but there's a path from bb4 to
bb9 (e.g. bb4 -> bb5 -> bb9), where one node in that path that isn't bb4 is
pdom by bb9 (here bb5 and bb9 are such path nodes).  With same reasoning also
bb5 is
control dependend on bb4 (the example path being bb4->bb5, and bb5 the only
test 
node to check for pdom by bb5).

So, we have that bb5 and bb9 are control dependend on bb4, so removing of
bb4 (or it's predicate) would be wrong.  If our control dependence machinery
doesn't figure out that cdep(bb4) = {bb5,bb9}, then that would be the bug.

(I haven't checked what our cdep calculation gives as result here, the above is
what should have happened).

[Bug tree-optimization/99101] optimization bug with -ffinite-loops

[matz at gcc dot gnu.org]

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

--- Comment #19 from Michael Matz <matz at gcc dot gnu.org> ---
(In reply to Michael Matz from comment #18)
> But there are other blocks control dependend on bb4, namely bb5 and bb9.
> To see this observe that bb9 doesn't pdom bb4, but there's a path from bb4 to
> bb9 (e.g. bb4 -> bb5 -> bb9), where one node in that path that isn't bb4 is

... where _each_ node in that path that isn't bb4 ...  Sorry.

(Essentially this captures the idea that the path-start node that is the
control
node is the _latest_ node that determines (non)execution of the path-end, i.e.
all
further nodes after the control node unavoidably pass through path-end).

[Bug tree-optimization/99101] optimization bug with -ffinite-loops

[rguenth at gcc dot gnu.org]

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

--- Comment #20 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Michael Matz from comment #19)
> (In reply to Michael Matz from comment #18)
> > But there are other blocks control dependend on bb4, namely bb5 and bb9.
> > To see this observe that bb9 doesn't pdom bb4, but there's a path from bb4 to
> > bb9 (e.g. bb4 -> bb5 -> bb9), where one node in that path that isn't bb4 is
> 
> ... where _each_ node in that path that isn't bb4 ...  Sorry.
> 
> (Essentially this captures the idea that the path-start node that is the
> control
> node is the _latest_ node that determines (non)execution of the path-end,
> i.e. all
> further nodes after the control node unavoidably pass through path-end).

Yes, bb5 and bb9 are control dependent on bb4.

But nothing in bb5 or bb9 ends up necessary (so the IV 'i' is elminated as
well).
We start with obviously necessary stmts

Marking useful stmt: __builtin_puts (&"1"[0]);

Marking useful stmt: xx.0_1 ={v} xx;

Marking useful stmt: __builtin_abort ();

And the only thing we deem necessary is

Marking useful stmt: if (xx.0_1 != 0)

because we mark this due to the self control-dependence of bb6 to itself
when processing the necessary call.  If we didn't do that we'd end up
optimizing
the testcase to just

int main()
{
  __builtin_puts ("1");
  xx;
  abort ();
}

hmm, actually when removing the if (xx) stmt we end up redirecting the
incoming edge to the loop latch and so we'd produce

  <bb 3> :
  __builtin_puts (&"1"[0]);
  xx.0_1 ={v} xx;
  goto <bb 3>; [100.00%]

because we're using yet another idea of post-dominance, that by
inverted_post_order_compute and it's kludge how to handle backwards
unreachable blocks ... (it produces 7, 5, 9, 0, 2, 12, 3, 11, 4, 6, 1)
At one point the code used to walk immediate post-dominators.  This
was changed for PR65337 in g:e4dbb0d449e778bc810d0d627a5aaefd0d7847b1

[Bug tree-optimization/99101] optimization bug with -ffinite-loops

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |hubicka at gcc dot gnu.org

--- Comment #21 from Richard Biener <rguenth at gcc dot gnu.org> ---
So I'm somewhat lost in pointing to the actual error.  And I'm not sure there
is any error, just unfortuate optimization behavior in the face of the testcase
being undefined with -ffinite-loops (or in C++).

That said, more "sensible" optimization from the undefined behavior would
have been to exit the loop, not preserving the if (xx) test.  With preserving
it we either end up with infinite puts() or no puts() calls both which
have the "wrong" number of invocations of the side-effect in the loop.

There's still the intuitively missing control dependence on the if (at_eof)
check (which is also missing without -ffinite-loops but doesn't cause any
wrong DCE there).  But as said my gut feeling is that control dependence
doesn't capture the number of invocations but only whether something is
invoked.  That's likely why we manually add control dependences of the
latch of loops for possibly infinite loops.

CCing Honza who added the control-dependence stuff and who may remember
some extra details.

[Bug tree-optimization/99101] optimization bug with -ffinite-loops

[matz at gcc dot gnu.org]

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

--- Comment #22 from Michael Matz <matz at gcc dot gnu.org> ---
Over the last days I came to a similar conclusion.  Control dependence as
defined
with postdoms doesn't capture the number of invocations of an instruction, just
wether it's invoked at all.  I.e. paths with and without cycles are regarded
the
same on that level.

Basically the path expression for the testcase is (just inner loop):

  (bb11 -> bb4 -> ((bb5->bb9) | (bb6 -> (bb7->leave-cycle | bb9))))*

It's clear that bb7 is reached exactly once (because as soon as it's reached
it's
also the end of this function, and it must be reached because it's the only end
of
the function).

The thing with bb6 is that it can be invoked many times, and doesn't always
need
to lead to bb7, but rather can fall into bb9 (and the cycle restarts).
But it's also the case that bb6 doesn't need to be invoked in _all_ invocations
of
the cycle.  bb4 can choose to skip it (via bb5->bb9).

So, while it's true that bb6 and bb7 are not control dependend on bb4 in the
post-domincance formulation it's pretty clear that bb4 isn't useless because it
exactly can cause bb6 to be skipped _in the current cycle_.

If control dependence via postdoms doesn't capture the number of invocations
of a node then it simply cannot be used in cyclic regions to determine
uselessness
of predicates.

[Bug tree-optimization/99101] optimization bug with -ffinite-loops

[rguenth at gcc dot gnu.org]

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

--- Comment #23 from Richard Biener <rguenth at gcc dot gnu.org> ---
Just for the record we had the idea to apply the "bolt" of marking the latch
control dependence (as done for possibly infinite loops) for loops containing
stmts with side-effects.

diff --git a/gcc/tree-ssa-dce.c b/gcc/tree-ssa-dce.c
index c027230acdc..c07b60bf25c 100644
--- a/gcc/tree-ssa-dce.c
+++ b/gcc/tree-ssa-dce.c
@@ -695,6 +695,12 @@ propagate_necessity (bool aggressive)
          if (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)
              && !bitmap_bit_p (visited_control_parents, bb->index))
            mark_control_dependent_edges_necessary (bb, false);
+         /* If the stmt has side-effects the number of invocations matter.
+            In this case mark the containing loop control.  */
+         if (gimple_has_side_effects (stmt)
+             && bb->loop_father->num != 0)
+           mark_control_dependent_edges_necessary (bb->loop_father->latch,
+                                                   false);
        }

       if (gimple_code (stmt) == GIMPLE_PHI

But while that works for CDDCE1, CDDCE2 is presented a slightly altered CFG
that somehow prevents it from working.  Which also means that both loops
need to be considered infinite for the present bolting to work.

[Bug tree-optimization/99101] optimization bug with -ffinite-loops

[hubicka at gcc dot gnu.org]

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

--- Comment #24 from Jan Hubicka <hubicka at gcc dot gnu.org> ---
I do not think there is problem with pdom for cyclic WRT acyclic paths. Both
notions are equivalent here. 

If you have instruction I in, say, header of a loop and you determine it live
then the condition controlling loopback is in control dependent blocks and that
will bring it live which transitively brings everything else.

The thing is that post dominance assumes that every path must progress to exit
node (as promised by -ffinite-loops)

volatile int xx;
int main()
{
  int jobs_ = 1;
  int at_eof_ = 0;
  while (1)
    {
      for (int i = 0; i < jobs_; i++)
        {
          if (at_eof_)
            continue;
          at_eof_ = 1;
          __builtin_printf ("1\n");
          if (xx)
            return 1;
        }
      jobs_ = 0;
    }
  return 0;
}

has infinite loop that is sort of equivalent to

volatile int xx;
int main()
{
  int jobs_ = 1;
  int at_eof_ = 0;
  while (1)
    {
      if (at_eof_)
        continue;
      at_eof_ = 1;
      __builtin_printf ("1\n");
      if (xx)
        return 1;
      jobs_ = 0;
      while (jobs_ == 0);
    }
  return 0;
}
and we manage to "shortcut" "while (jobs_ == 0);" rather than forcing the
original lop to be finite. Since the difference is not visible across any path
that must progress to exit node, both are valid in this sense.

With -fno-finite-loops pdoms still do not consider infinite paths, but since we
make sure that every BB has a path to exit every infinite path can be
approximated by sequence of finite paths. Since we keep all the finite paths
consitent, the only problem may be that we will optimize out the condtiion
deciding on back edge but we don't do that becuase we mark them necessary...