[COMMITTED 4/4] - Gimple range PHI analyzer and testcases

[Andrew MacLeod]

This patch provide the framework for a gimple-range phi analyzer.

Currently, the  primary purpose is to give better initial values for 
members of a "phi group"

a PHI group is defined as a a group of PHI nodes whose arguments are all 
either members of the same PHI group, or one of 2 other values:
  - An initializer, (typically a constant), but not necessarily,
  - A modifier, which is always of the form:   member_ssa = member_ssa 
OP op2

When the analyzer finds a group which matches this pattern, it tries to 
evaluate the modifier using the initial value and project a range for 
the entire group.

This initial version is fairly simplistic.  It looks for 2 things:

1) if there is a relation between LHS and the other ssa_name in the 
modifier, then we can project a range. ie,
         a_3 = a_2 + 1
if there is a relation generated by the stmt which say a_3 > a_2, and 
the initial value is 0, we can project a range of [0, +INF] as the 
moifier will cause the value to always increase, and not wrap.

Likewise, for a_3 = a_2 - 1,  we can project a range of [-INF, 0] based 
on the "<" relationship between a_3 and a_2.

2) If there is no relationship, then we use the initial range and 
"simulate" the modifier statement a set number of times looking to see 
if the value converges.
Currently I have arbitrarily hard coded 10 attempts, but intend to 
change this down the road with a --param, as well as to perhaps 
influence it with any known values from SCEV regarding known iterations 
of the loop and possibly change it based on optimization levels.

I also suspect something like one more than the number of bits in the 
type might help with any bitmasking tricks.

Theres a lot of additinal things we can do to enhance this, but this 
framework provides a start.  These 2 initial evaluations fix 107822, and 
part of 107986.

  There is about a 1.5% slowdown to VRP to invoke and utilize the 
analyzer in all 3 passes of VRP.  overall compile time is 0.06% slower.

Bootstraps on x86_64-pc-linux-gnu  with no regressions.  Pushed.

Andrew




-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0004-Gimple-range-PHI-analyzer-and-testcases.patch
Type: text/x-patch
Size: 25077 bytes
Desc: not available
URL: <https://gcc.gnu.org/pipermail/gcc-patches/attachments/20230524/dcb4dcd9/attachment-0001.bin>