Some PINGs
Richard Biener
richard.guenther@gmail.com
Tue Nov 9 09:18:11 GMT 2021
On Mon, Nov 8, 2021 at 4:40 PM Richard Biener
<richard.guenther@gmail.com> wrote:
>
> On Mon, Nov 8, 2021 at 3:02 PM Roger Sayle <roger@nextmovesoftware.com> wrote:
> >
> >
> > Hi Richard,
> >
> > >> I wonder if reviewers could take a look (or a second look) at some of
> > >> my outstanding patches.
> > >> PR middle-end/100810: Penalize IV candidates with undefined value
> > >> bases
> > >> https://gcc.gnu.org/pipermail/gcc-patches/2021-August/578441.html
> > >
> > > I did comment on this one, noting the more general issue.
> > > My opinion is still that doing heavy lifting in IVOPTs is misplaced.
> >
> > I wasn't sure whether you'd had the opportunity to give this bug some more
> > thought.
> >
> > You're completely right, that it is theoretically possible for GCC to upgrade
> > its data flow (CCP/VRP) passes to use a finer grained definition of undefined/
> > uninitialized/indeterminate values; an indeterminate-value numbering pass
> > if you will. Under the constraints that the automatic variables are not volatile,
> > and the types don't supporting a trapping values, the compiler could determine
> > that "undef1 - undef1", or "undef2 ^ undef2" have defined values, but that
> > "undef1 - undef2" and "undef3 ^ undef4" remain indeterminate. Like
> > traditional value numbering, it may be possible to track "t1 = undef3 ^ undef4",
> > "t2 = t1 ^ undef4", "t3 = t2 - undef3". Conceptually, the same applies to
> > (floating point) mathematics and its numerous infinities, sometimes "+Inf - +Inf"
> > is known to be zero, provided that it is the exact same infinity (omega) that is
> > being subtracted.
> >
> > The two counter arguments for this solution as a fix for PR 100810, is that such
> > a pass doesn't yet exist, and it still (probably) falls foul of C/C++'s undefined
> > behaviour from use of an uninitialized automatic variable. From an engineering
> > perspective, it's a lot of effort to support poorly written code.
> >
> > Quick question to the language lawyers:
> >
> > int foo()
> > {
> > int undef;
> > return undef ^ undef;
> > }
> >
> > int bar()
> > {
> > volatile int undef;
> > return undef ^ undef;
> > }
> >
> > Do the above functions invoke undefined behaviour?
>
> Yes. C17 6.3.2.1 says so. Note that it has a strange restriction
> on being 'register' qualifiable, so taking the address of 'undef'
> in an unrelated stmt would make it not undefined? Whenever the
> language spec makes the use not undefined the argument is
> that the abstract machine would for
>
> int bar()
> {
> int undef;
> int tem = undef;
> return tem ^ tem;
> }
>
> cause 'undef' to have a single evaluation and thus 'tem' have
> a single consistent value. In GCC we'd have propagated those out,
> resulting in two evaluations (not sure if a SSA use can be considered
> an "evaluation" or whether the non-existing(!) single definition is the sole
> evaluation)
>
> > The approach taken by the proposed patch is that it's the pass/transformation that
> > introduces more undefined behaviour than was present in the original code, that is
> > at fault. Even if later passes, decided not to take advantage of UB, is there any benefit
> > for replacing an induction variable with a well-defined value (evolution) and substituting
> > it with one that depends upon indefinite values. I'd argue the correct fix is to go the other
> > way, and attempt to reduce the instances of undefined behaviour.
> >
> > So transform
> >
> > int undef;
> > while (cond())
> > undef++;
> > ...
> >
> > which invokes UB on each iteration with:
> >
> > int undef;
> > unsigned int count = 0;
> > while (cond())
> > count++;
> > undef += count;
> > ...
> >
> > which now only invokes UB after the loop.
> >
> > Consider:
> > int undef;
> > int result = 0;
> > while (cond())
> > result ^= undef;
> > return result;
> >
> > where the final value of result may be well-defined if the loop iterates
> > an even number of times.
> >
> > int undef;
> > int result = 0;
> > while (cond())
> > result ^= 1;
> > return result ? undef : 0;
> >
> >
> > Has anyone proposed an alternate fix to PR middle-end/100810?
> > We can always revert my proposed fix (for this P1 regression), once IV opts
> > is able to confirm that it is safe to make the substitution that it is proposing.
>
> I do agree with the idea to not increase the number of UNDEF uses. But the
> issue is that undefinedness as in what your patch would consider is brittle,
> it can be easily hidden in a function parameter and thus the bug will likely
> re-surface if you just hide the undefinedness from the pass in some way.
>
> So any place where we try to do sth when we see an UNDEF for _correctness_
> reasons should really be testing for must-definedness instead which I think
> is similarly infeasible and broken.
>
> So for the PR at hand it's actually ifcombine that turns the testcase from
> one not invoking undefined behavior first (all uses of 'i' are never executed)
> into one that does by turning
>
> if (!b)
> i &&d;
>
> into
>
> _Bool tem = b == 0 & i != 0;
> if (tem)
> d;
>
> the loop body is indeed mangled by IVOPTs by replacing h with a
> computation based on the undefined i and that elimination is
> invalid exactly because for
>
> # i_16 = PHI <i_24(D)(20), i_17(7)>
> _41 = (unsigned int) i_24(D);
> _51 = _28 + _41;
> _22 = (unsigned int) i_16;
> _48 = -_22;
>
> i_24(D) and i_16 do not cancel out on the edge from (20)
> where i_16 is defined as a copy from i_24(D) ... I do think that
> CCP is what really breaks things here - CCP assumes that
> each SSA use of an UNDEF value can yield a different value.
>
> "stabilizing" 'i's value by making it a parameter to the function
> (but still undefined) will make it work.
>
> That said, when we treat undefined as undefined we indeed
> have to be very careful about transforms we do (see signed
> overflow). For undefs the important part is to handle them
> optimistically in PHIs, anything else is likely going to cause
> more problems than it helps.
>
> But - I'm not fully set on any option to take. Btw, the bug
> is surely latent and it should be possible to craft a simpler
> testcase that also breaks on older GCC, thus P1 isn't
> appropriate here.
>
> I'll think a bit more tomorrow.
OK, so apart from trying to find a better balance of where
we exploit UNDEF I had a look at the IVOPTs patch again.
I think instead of attacking this at the cost side we should
avoid making IVs with SSA undefs candidates for USEs
that are not the original one.
One can do this - almost - by disregarding !IP_ORIGINAL
candidates with undef bases and making the IP_ORIGINAL
one not important (so it's not considered for other uses).
Almost - since we have the 'consider_all_candidates'
override. So the attached patch works with --param
iv-consider-all-candidates-bound=1
only.
I suppose the iv_cand->important two-state flag could be
made an enum to be able to single out some from
all-candidates processing as well.
Interestingly for the testcase it also works to not allow any
candidate with the SSA UNDEF (the IV then gets expressed
with the h_lsm candidate), but in general the IV might not
be eliminatable and thus IVOPTs likely will crash if we tie
its hand that way.
So the idea is to tie IVOPTs hands so it will simply keep
the original IVs when they have UNDEF bases and not
use them to eliminate other IVs. I think that should be
doable with the patch (apart from the all_candidates issue).
I've CCed Bin who knows the IVOPTs code best for an
opinion.
Thanks,
Richard.
> Thanks,
> Richard.
>
> > I'm curious to hear your (latest) thoughts.
> >
> > Thanks again for thinking about this.
> >
> > Best regards,
> > Roger
> > --
> >
> >
-------------- next part --------------
A non-text attachment was scrubbed...
Name: p
Type: application/octet-stream
Size: 5359 bytes
Desc: not available
URL: <https://gcc.gnu.org/pipermail/gcc-patches/attachments/20211109/0371ec06/attachment-0001.obj>
More information about the Gcc-patches
mailing list