[Bug tree-optimization/101186] predictable comparison of integer variables not folded

[aldyh at gcc dot gnu.org]

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

Aldy Hernandez <aldyh at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |aldyh at gcc dot gnu.org,
                   |                            |jeffreyalaw at gmail dot com

--- Comment #4 from Aldy Hernandez <aldyh at gcc dot gnu.org> ---
To give a little more context, the IL at thread1 looks like this:

  <bb 3> [local count: 59055800]:
  goto <bb 9>; [100.00%]

  <bb 4> [local count: 955630225]:
  if (a_5(D) != 0)
    goto <bb 5>; [67.00%]
  else
    goto <bb 7>; [33.00%]

  <bb 5> [local count: 640272253]:
  if (x_8(D) < c_12)
    goto <bb 6>; [33.00%]
  else
    goto <bb 8>; [67.00%]

  <bb 6> [local count: 211289842]:
  unreachable ();
  goto <bb 8>; [100.00%]

  <bb 7> [local count: 315357972]:
  blah ();

  <bb 8> [local count: 955630227]:
  b_11 = b_1 + 1;
  goto <bb 10>; [100.00%]

  <bb 9> [local count: 118111600]:
  # c_12 = PHI <x_8(D)(3), y_4(D)(2)>

  <bb 10> [local count: 1073741824]:
  # b_1 = PHI <b_6(D)(9), b_11(8)>
  if (b_1 <= 999)
    goto <bb 4>; [89.00%]
  else
    goto <bb 11>; [11.00%]

The path from 3->9->10->4->5 could *theoretically* resolve the conditional in
BB5.  If this were a permissible jump threading path, the threader would
replace the conditional in BB5 into a jump to BB8, thus eliding the
unreachable.

However, BB9->BB10 would cross loop boundaries which is not permitted in the
backwards threader.  Specifically, the threading candidate conditional is BB5,
which is in a loop:

;; Loop 1
;;  header 10, latch 8
;;  depth 1, outer 0
;;  nodes: 10 8 6 7 5 4 (<-- note BB5 & BB10 in here)

And BB9 is outside said loop.

See path_crosses_loops in tree-ssa-threadbackward.c as well as handle_phi()
where we specifically skip PHI edges pointing outside the current loop.

Note that even though my upcoming rewrite of the backward threader does not use
the relational oracle, Andrew says it would be trivial to do so.  In which
case, we *could* resolve the above path, but would still fail to thread it
because it crosses a loop boundary.

Perhaps Jeff can opine on whether the path duplicator in the threader back-end,
could be taught to thread through loops.