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

[Richard Biener <richard.guenther@gmail.com>]

On Wed, May 24, 2023 at 11:21 PM Andrew MacLeod via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
> 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.

Hm.  What I've noticed the last time looking at how ranger deals
with PHIs is that it diverts to SCEV analysis for all of them but
it could restrict itself to analyze PHIs in loop headers
(bb->loop_father->header == bb).  That only handles natural
loops of course but that was good enough for the old VRP implementation.
That might also help to keep the PHI anlyzer leaner by less entires.

I've only quickly looked at the PHI analyzer and I failed to understand
how you discover cycles.  I'm pointing you to the SCC value-numbering
cycle finding which you can find for example on the GCC 7 branch
(it's gone for quite some time) in tree-ssa-sccvn.c:DFS - that collects
strongly connected SSA components (it walks all uses, you probably
want to ignore virtuals).  SCEV also has its own cycle finding
(well, sort of) with the scev_dfs class and it restricts itself to
operations it handles (so it's more close to what you do).

I fear you're developing sth very ad-hoc here.

Richard.


> Andrew
>
>
>
>