Re: [PATCH] [PR105665] ivopts: check defs of names in base for undefs

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

On Tue, May 31, 2022 at 3:27 PM Alexandre Oliva <oliva@adacore.com> wrote:
>
> On May 30, 2022, Richard Biener <richard.guenther@gmail.com> wrote:
>
> > I don't think you can rely on TREE_VISITED not set at the start of the
> > pass (and you don't clear it either).
>
> I don't clear it, but I loop over all SSA names and set TREE_VISITED to
> either true or false, so that's covered.
>
> I even had a test patch that checked that TREE_VISITED remains unchanged
> and still matched the expected value, with a recursive verification.
>
> I could switch to an sbitmap if that's preferred, though.
>
> > I also wonder how you decide that tracking PHIs with (one) uninit arg
> > is "enough"?
>
> It's a conservative assumption, granted.  One could imagine cases in
> which an uninit def is never actually used, say because of conditionals
> forced by external circumstances the compiler cannot possibly know
> about.  But then, just as this sort of bug shows, sometimes even when an
> uninit is not actually used, the fact that it is uninit and thus
> undefined may end up percolating onto stuff that is actually used, so I
> figured we'd be better off leaving alone whatever is potentially derived
> from an uninit value.
>
> > Is it important which edge of the PHI the undef appears in?
>
> At some point, I added recursion to find_ssa_undef, at PHI nodes and
> assignments, and pondered whether to recurse at PHI nodes only for defs
> that were "earlier" ones, rather than coming from back edges.  I ended
> up reasoning that back edges would affect step and rule out an IV
> candidate even sooner.  But the forward propagation of maybe-undef
> obviated that reasoning.  Now, almost tautologically, if circumstances
> are such that the compiler could only tell that an ssa name is defined
> with external knowledge, then, since such external knowledge is not
> available to the compiler, it has to assume that the ssa name may be
> undefined.
>
> > I presume the testcase might have it on the loop entry edge?
>
> The original testcase did.  The modified one (the added increment) shows
> it can be an earlier edge that has the maybe-undef name.
>
> > I presume only PHIs in loop headers are to be considered?
>
> As in the modified testcase, earlier PHIs that are entirely outside the
> loop can still trigger the bug.  Adding more increments of g guarded by
> conditionals involving other global variables pushes the undef ssa name
> further and further away from the inner loop, while still rendering g an
> unsuitable IV.

So for example

void foo (int flag, int init, int n, int *p)
{
   int i;
   if (flag)
     i = init;
   for (; i < n; ++i)
     *(p++) = 1;
}

will now not consider 'i - i-on-entry' as an IV to express *(p++) = 1.
But

void foo (int flag, int init, int n, int *p)
{
   int i;
   if (flag)
     i = init;
   i++;
   for (; i < n; ++i)
     *(p++) = 1;
}

still would (the propagation stops at i++).  That said - I wonder if we
want to compute a conservative set of 'must-initialized' here or to
say, do we understand the failure mode good enough to say that
a must-def (even if from an SSA name without a definition) is good
enough to avoid the issues we are seeing?

One would argue that my example above invokes undefined behavior
if (!flag), but IIRC the cases in the PRs we talk about are not but
IVOPTs with its IV choice exposes undefined behavior - orignially
by relying on undef - undef being zero.

That said, the contains-undef thing tries to avoid rewriting expressions
with terms that possibly contain undefs which means if we want to
strenthen it then we look for must-defined (currently it's must-undefined)?

Richard.

> >> +int a, b, c[1], d[2], *e = c;
> >> +int main() {
> >> +  int f = 0;
> >> +  for (; b < 2; b++) {
> >> +    int g;
> >> +    if (f)
> >> +      g++, b = 40;
> >> +    a = d[b * b];
> >> +    for (f = 0; f < 3; f++) {
> >> +      if (e)
> >> +        break;
> >> +      g--;
> >> +      if (a)
> >> +        a = g;
> >> +    }
> >> +  }
> >> +  return 0;
> >> +}
>
> --
> Alexandre Oliva, happy hacker                https://FSFLA.org/blogs/lxo/
>    Free Software Activist                       GNU Toolchain Engineer
> Disinformation flourishes because many people care deeply about injustice
> but very few check the facts.  Ask me about <https://stallmansupport.org>