[Bug tree-optimization/126965] [17 Regression] ICE on valid code at -O{2, 3} with -fno-tree-dominator-opts on x86_64-linux-gnu: Segmentation fault since r17-2788

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Assignee|unassigned at gcc dot gnu.org      |rguenth at gcc dot gnu.org
             Status|NEW                         |ASSIGNED

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
So PRE seems to end up with a recursively defined expression to insert:

Found partial redundancy for expression {nop_expr,_34} (0013)

on 18->6 _37 is the AVAIL expression, somehow on 16->6 as well, but
it's not directly available there.

avail_out[18] := { c.0_24 (0007), b_lsm.13_26 (0009), c.6_12 (0003), _37
(0013), _38 (0014), _39 (0015) }

avail_out[16] := { c.0_24 (0007), b_lsm.13_26 (0009), c.6_12 (0003) }

Created SSA_NAME representative pretmp_21 for expression:{ssa_name,_37} (0020)
ANTIC_OUT[16] := { c.6_12 (0003), {nop_expr,c.6_12} (0011),
{plus_expr,pretmp_30,1} (0012), {ssa_name,_37} (0020), {nop_expr,pretmp_21}
(0022) }
warning: intersecting with old ANTIC_IN shrinks the set
ANTIC_IN[16] := { c.6_12 (0003), {nop_expr,c.6_12} (0011),
{plus_expr,pretmp_30,1} (0012), {ssa_name,_37} (0020) }
S[16] := { c.6_12 (0003), {nop_expr,c.6_12} (0011), {plus_expr,pretmp_30,1}
(0012), {ssa_name,_37} (0020), {nop_expr,pretmp_21} (0022) }

I'll note we have NARY for what should be just NAME here.  Fixing that
doesn't help, we still try to insert

{nop_expr,pretmp_40}

where we do not find a leader for pretmp_40 in block 16 and then look
at the expressions we have for value 12:

0012[0] := { c.8_28 (0012), {nop_expr,c.6_18} (0012), _34 (0012),
{plus_expr,c.5_33,1} (0012), {plus_expr,pretmp_30,1} (0012), pretmp_40 (0012),
{nop_expr,c.6_27} (0012) }

where we pick the first, {nop_expr,c.6_18} (0012), to recurse, again
c.6_18 has no leader, it's value expressions are

0013[0] := { c.6_18 (0013), _35 (0013), {nop_expr,_34} (0013), c_lsm.14_6
(0013), c.6_27 (0013), c_lsm.14_4 (0013), c.6_2 (0013), _37 (0013),
{plus_expr,c.6_12,1} (0013), {nop_expr,pretmp_40} (0013), pretmp_19 (0013) }

and we're toast as we'll recurse with {nop_expr,_34} (0013) where _34 has
value 12 again.

There's a cycle in the expr/value graph and there's no means to "avoid" it.

The comment

  /* It must be a complex expression, so generate it recursively.  Note
     that this is only necessary to handle gcc.dg/tree-ssa/ssa-pre28.c
     where the insert algorithm fails to insert a required expression.  */
  bitmap exprset = value_expressions[lookfor];
  bitmap_iterator bi;
  unsigned int i;
  if (exprset)
    EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi)

indicates this recursive processing must be a side-effect of imperfect
ordering - ordering which I might have fixed, but the testcase still FAILs
when I comment this block out.

A defensive approach would be to simply limit the expression complexity
(aka the recursion depth).

As I figured in PR125040, the value graph can have cycles (to my surprise).