Re: [PATCH] PR tree-optimization/109192 - Terminate GORI calculations if a relation is not relevant.

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

On Tue, Mar 21, 2023 at 2:44 PM Andrew MacLeod via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
> As mentioned in the PR, the originally GORI terminated calculation if
> the LHS was varying as it could not provide any additional useful
> information on an outgoing edge beyond what folding would give.
>
> The original patch  introduced relations, and aloowed GORI to keep going
> with the hope that the relation might provide new info.  This PR trips
> over a case where there are a lot of relations, and GORI is unbounded in
> the path query with is already quadratic.
>
> This patch first checks if the relation can have an effect on the
> outgoing calculation, and if not, terminates the calculation like we use
> to.  This prevents a lot of excessive checking.  there are 2 cases where
> the relation is considered relevant:
>
>   1- both argument to the relation are in the defchain of the operand
> currently being calculated:
>
> b_2 = x_3 < y_5
> c_3 = b_2 != 0
> if (c_3 &&  x_3 < y_5)
>
> on te true side, we will ge the relation x_3 < y_5,  both of which are
> in the defchain for c_3.  THis will enable use to evaluate that on the
> true side, c_3 must be [1,1], and therefore b_2 must be[1, 1], and the
> relation can be applied to the calculation [1,1] = x_3 < y_5    to
> establish that c_3 will indeed be [1,1] always if x_3<y_5
> Without this, c_3 will evaluate to VARYING and the calcultion will
> terminate and we wont know b_2.
>
>
> 2 - AS in the original PR, the relation can be applied to the current
> statement as a def/operand relation:
>
>      _1 = (sizetype) off_3(D);
>    q_5 = p_4(D) + _1;
>    if (p_4(D) == q_5)
>
> applying p_4 == q_5 to   q_5 = p_4(D) + _1; allows us to evaluate _1 as
> [0,0] on the true side and ~[0,0] on the false side through the
> op2_range calculation for pointer_plus.
>
> Without this, q_5 has a value of varying, and the calculation will
> terminate without getting better value sfor _1 or off_3.
>
> 3 -  If  zero or one element of the relation is in the def chain, the
> relation should not have any impact on the calculation, and we can
> simply stop calculating.
>
> The performance impact is negligible (its actually slightly faster)
> across 230 GCC source files.  When there is a relation, the extra work
> to determine relevance is offset by the pointless calculations avoided.
>
> A slight tweak was needed to the value_relation class as I was tripping
> over a fortran testcase failure resulting from an old assumption we
> could not have a value_relation record for  op1 VREL_EQ op1, which GORI
> is counting on.. It was sneaking through before because we we're
> assuming that the relation record has to be set properly.
>
> Bootstraps on x86_64-pc-linux-gnu with no regressions.  OK for trunk?

OK.

Richard.

> Andrew