On Tue, Aug 31, 2021 at 8:22 AM Roger Sayle <ro...@nextmovesoftware.com> wrote:
>
>
> Time to hopefully earn some goodwill from the team; this patch fixes
> a P1 wrong-code-on-valid regression in ivopts. Many thanks to Andrew
> Pinski for help with the analysis.
>
> Consider the code fragment below:
>
> int i;
> for (j=0; j<10; j++)
> i++;
>
> This results in a loop containing two induction variables, i and j,
> where j is initialized, but i isn't (typically indicated in tree dumps
> by qualified ssa names like i(D). In PR 100810, the loop optimizers
> end up selecting i as the "best" candidate (perhaps because having no
> initialization it's cheaper) which leads to problems in later passes
> when (the equivalent of) j is considered not to have the value 10 after
> the loop, as its definition is now computed from an undefined/uninitialized
> value.
>
> The fix below is to add a field to track whether any "iv_group" contains
> a use of an iv based on a undefined value, and then prohibit IVs that are
> based on undefined values from being candidates for groups that don't use
> undefined values. This may seem lenient, but it allows an IV with an
> undefined base to be a candidate for itself, and is a sufficient condition
> to avoid the above bug/regression. A stricter condition might be to only
> allow "undefined_value iv"s as candidates for iv_groups where *all*
> uses are to "undefined_value ivs"? My concern was that this might lead
> to cases/loops that no longer have suitable candidates (i.e. a possible
> performance regression).
>
> Hopefully, the tree-loop optimization experts agree with my analysis/fix.
So the reason why the generated code is "wrong" is that we end up with
# i_16 = PHI <i_24(D)(19), i_17(7)>
_40 = (unsigned int) b.7_13;
_47 = (unsigned int) i_24(D);
_49 = _40 + _47;
_39 = (unsigned int) i_16;
_22 = -_39;
_33 = _22 + _49;
where we relate i_24(D) and i_16 = PHI <i_24(D)(19), ...> but two
evaluations of the same undefined SSA name do not necessarily
yield the same value. The undefined SSA names pop in via
SCEV and niter analysis so trying to fix this in IVOPTs is plugging
the hole only in a single place. Not only do the SSA names not
evaluate to the same value in the end, but here CCP assumes
that UNDEFINED - UNDEFINED is UNDEFINED but
i_24(D) - i_24(D) is _not_ UNDEFINED.
So
Visiting statement:
_40 = (unsigned int) b.7_13;
which is likely CONSTANT
Lattice value changed to VARYING. Adding SSA edges to worklist.
Visiting statement:
_47 = (unsigned int) i_24(D);
which is likely UNDEFINED
Lattice value changed to UNDEFINED. Adding SSA edges to worklist.
marking stmt to be not simulated again
Visiting statement:
_49 = _47 + _40;
which is likely UNDEFINED
this last conclusion looks wrong to me, in fact most of the UNDEFINED
proapgation handling in CCP seems to assume that i_24(D) - i_24(D)
is not necessarily zero which is in conflict with us happily pulling
such not "stabilized" operands into expressions and propagating them
at will.
ISTR a paper about this very issue from the clang/llvm folks and they
inventing some special notion for not-quite-undefined or so ...
I don't have a good answer yet to the problem at hand (also given
CCP isn't the only place that doesn't treat i_24(D) as having the
same value in all contexts). The classical testcase for this would be
int __attribute__((noipa)) foo (int i)
{
int j, k, m;
int val = j;
if (i)
k = val;
else
k = 3;
if (i)
m = val;
else
m = 2;
return m - k;
}
int main()
{
if (foo (1) != 0)
__builtin_abort ();
}
where 'k' is optimistically 3 from merging UNDEFINED and 3
from two executable edges. The reasoning is that eventually
only initialized values may contribute to sth meaningful which
fails to consider X - X. We have not considered this to be a bug
but we now have to work towards making the compiler itself
avoid creating such cancellations ...
Richard.
> This patch has been tested on x86_64-pc-linux-gnu with a "make bootstrap"
> and "make -k check" with no new failures. Ok for mainline?
>
> 2021-08-31 Roger Sayle <ro...@nextmovesoftware.com>
> Andrew Pinski <apin...@marvell.com>
>
> gcc/ChangeLog
> PR middle-end/100810
> * tree-ssa-loop-ivopts.c (struct iv_group): Add a new
> uses_undefined_value_p field, indicating this group has
> uses of iv's whose base is ssa_undefined_value_p.
> (record_use): Update uses_undefined_value_p as required.
> (record_group): Initialize uses_undefined_value_p to false.
> (determine_group_iv_cost_generic): Consider a candidate with
> a ssa_undefined_value_p base to have infinite_cost for a
> group where uses_undefined_value_p is false.
>
> gcc/testsuite/ChangeLog
> PR middle-end/100810
> * gcc.dg/pr100810.c: New test case.
>
> Roger
> --
>
