Re: Uninit warnings due to optimizing short-circuit conditionals

[Mark Wielaard <mark@klomp.org>]

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

Cheers,

Mark