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

[Alexandre Oliva <oliva@adacore.com>]

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.

>> +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>