On Mon, Nov 8, 2021 at 3:02 PM Roger Sayle <ro...@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.
Thanks,
Richard.
> I'm curious to hear your (latest) thoughts.
>
> Thanks again for thinking about this.
>
> Best regards,
> Roger
> --
>
>
