Re: Uninit warnings due to optimizing short-circuit conditionals

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

On Mon, Feb 14, 2022 at 6:38 PM Mark Wielaard <mark@klomp.org> wrote:
>
> On Mon, 2022-02-14 at 12:20 -0500, David Malcolm wrote:
> > On Mon, 2022-02-14 at 17:57 +0100, Mark Wielaard wrote:
> > > On Mon, 2022-02-14 at 10:57 -0500, David Malcolm wrote:
> > > > [CCing Mark in the hopes of insight from the valgrind side of
> > > > things]
> > >
> > > Adding Julian to CC so he can correct me if I say something silly.
> > >
> > > > There is a false positive from -Wanalyzer-use-of-uninitialized-
> > > > value on
> > > > gcc.dg/analyzer/pr102692.c here:
> > > >
> > > >   ‘fix_overlays_before’: events 1-3
> > > >     |
> > > >     |   75 |   while (tail
> > > >     |      |          ~~~~
> > > >     |   76 |          && (tem = make_lisp_ptr (tail, 5),
> > > >     |      |          ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
> > > >     |      |          |
> > > >     |      |          (1) following ‘false’ branch (when ‘tail’ is
> > > > NULL)...
> > > >     |   77 |              (end = marker_position (XOVERLAY (tem)-
> > > > > end)) >= pos))
> > > >
> > > >     |      |
> > > > ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
> > > >     |......
> > > >     |   82 |   if (!tail || end < prev || !tail->next)
> > > >     |      |       ~~~~~    ~~~~~~~~~~
> > > >     |      |       |            |
> > > >     |      |       |            (3) use of uninitialized value
> > > > ‘end’ here
> > > >     |      |       (2) ...to here
> > > >     |
> > > >
> > > > The issue is that inner || of the conditionals have been folded
> > > > within the
> > > > frontend from a chain of control flow:
> > > >
> > > >    5   │   if (tail == 0B) goto <D.1986>; else goto <D.1988>;
> > > >    6   │   <D.1988>:
> > > >    7   │   if (end < prev) goto <D.1986>; else goto <D.1989>;
> > > >    8   │   <D.1989>:
> > > >    9   │   _1 = tail->next;
> > > >   10   │   if (_1 == 0B) goto <D.1986>; else goto <D.1987>;
> > > >   11   │   <D.1986>:
> > > >
> > > > to an OR expr (and then to a bitwise-or by the gimplifier):
> > > >
> > > >    5   │   _1 = tail == 0B;
> > > >    6   │   _2 = end < prev;
> > > >    7   │   _3 = _1 | _2;
> > > >    8   │   if (_3 != 0) goto <D.1986>; else goto <D.1988>;
> > > >    9   │   <D.1988>:
> > > >   10   │   _4 = tail->next;
> > > >   11   │   if (_4 == 0B) goto <D.1986>; else goto <D.1987>;
> > > >
> > > > This happens for sufficiently simple conditionals in
> > > > fold_truth_andor.
> > > > In particular, the (end < prev) is short-circuited without
> > > > optimization,
> > > > but is evaluated with optimization, leading to the false positive.
> > > >
> > > > Given how early this folding occurs, it seems the simplest fix is
> > > > to
> > > > try to detect places where this optimization appears to have
> > > > happened,
> > > > and suppress uninit warnings within the statement that would have
> > > > been short-circuited (and thus e.g. ignoring them when evaluating
> > > > _2
> > > > above for the case where _1 is known to be true at the (_1 | _2) ,
> > > > and
> > > > thus _2 being redundant).
> > > >
> > > > Attached is a patch that implements this.
> > > >
> > > > There are some more details in the patch, but I'm wondering if this
> > > > is a
> > > > known problem, and how e.g. valgrind copes with such code.  My
> > > > patch
> > > > feels like something of a hack, but I'm not sure of any other way
> > > > around
> > > > it given that the conditional is folded directly within the
> > > > frontend.
> > >
> > > As far as I know this is what valgrind memcheck also does with an
> > > bitwise or. It knows that _3 is defined and true if either _1 or _2
> > > is
> > > defined and true. Or more generically that the result bits of a
> > > bitwise
> > > or are defined for those bits that are both defined or where one is
> > > defined and has the value 1.
> >
> > Aha - thanks.  I think the distinction here is that:
> >
> > * GCC's -fanalyzer complains about uninitialized values immediately
> > when it sees one being fetched for use in any expression (replacing the
> > value with a safe one to avoid further complaints), without considering
> > how they are going to be used in the expression, whereas
> >
> > * it sounds like valgrind keeps track of uninitialized bits, propagates
> > the "uninit-ness" of the bits, and complains at certain times when
> > uninitialized bits are used in certain ways.
>
> Yes. valgrind keeps track of uninitialized bits and propagates them
> around till "use". Where use is anything that might alter the
> observable behavior of the program. Which is control flow transfers,
> conditional moves, addresses used in memory accesses, and data passed
> to system calls.
>
> This paper describes some of the memcheck tricks:
> https://valgrind.org/docs/memcheck2005.pdf

That probably means bugs like https://gcc.gnu.org/bugzilla/show_bug.cgi?id=63311
could be resolved as fixed (in valgrind).

But indeed GCCs own uninit diagnostics fall foul of this as well.  I suppose
one could track uses and if they are used in bitwise operations could
demote them to "maybe" even though they appear unconditionally.  Now,
we cannot distinguish

  if (a || b)

from

  if (b || a)

after combining the ifs of course.

Another possibility is to try to compute a kind of must-init analysis before
removing short-cutting transforms which practically means removing the
transform from GENERIC folding.

Richard.

> Cheers,
>
> Mark