False positive from -Warray-bounds?

False positive from -Warray-bounds?

[Lars Gullik Bjønnes]

I have this code:

--------------
unsigned int f(unsigned int value)
{
    unsigned int i = (value & 0xffff);
    return (i == 0xffff ? 0xffffffff : i);
}


static int *arr1[10];

void t(unsigned int s)
{
    arr1[f(s)] = 0;
    arr1[f(s)] = 0;
}
------------------


When compiled with 'gcc -Wall -Wextra -c' I get a warning about
"subscript is above array bounds".
Shouldn't the -Warray-bounds only warn if will _always_ be out-of-bounds?

Is this a false positive, or is there something that I am completely missing?

I see this with gcc from trunk (some days ago), and with redhat gcc 4.6.2-1.

-- 
        Lgb

Re: False positive from -Warray-bounds?

[Ian Lance Taylor]

Lars Gullik Bjønnes <larsbj@gullik.org> writes:

> I have this code:
>
> --------------
> unsigned int f(unsigned int value)
> {
>     unsigned int i = (value & 0xffff);
>     return (i == 0xffff ? 0xffffffff : i);
> }
>
>
> static int *arr1[10];
>
> void t(unsigned int s)
> {
>     arr1[f(s)] = 0;
>     arr1[f(s)] = 0;
> }
> ------------------
>
>
> When compiled with 'gcc -Wall -Wextra -c' I get a warning about
> "subscript is above array bounds".
> Shouldn't the -Warray-bounds only warn if will _always_ be out-of-bounds?
>
> Is this a false positive, or is there something that I am completely missing?
>
> I see this with gcc from trunk (some days ago), and with redhat gcc 4.6.2-1.

The warning triggers if there is some code path in which the index is
provably out of bounds.  That is true of this code.  I don't think I
would describe this as a false positive.  I think it is a case where, as
the -Wall documentation says, the code should be modified to avoid the
warning.

Ian

Re: False positive from -Warray-bounds?

[Lars Gullik Bjønnes]

On Thu, Dec 29, 2011 at 23:02, Ian Lance Taylor <iant@google.com> wrote:
> Lars Gullik Bjønnes <larsbj@gullik.org> writes:
>
>> I have this code:
>>
>> --------------
>> unsigned int f(unsigned int value)
>> {
>>     unsigned int i = (value & 0xffff);
>>     return (i == 0xffff ? 0xffffffff : i);
>> }
>>
>>
>> static int *arr1[10];
>>
>> void t(unsigned int s)
>> {
>>     arr1[f(s)] = 0;
>>     arr1[f(s)] = 0;
>> }
>> ------------------
>>
>>
>> When compiled with 'gcc -Wall -Wextra -c' I get a warning about
>> "subscript is above array bounds".
>> Shouldn't the -Warray-bounds only warn if will _always_ be out-of-bounds?
>>
>> Is this a false positive, or is there something that I am completely missing?
>>
>> I see this with gcc from trunk (some days ago), and with redhat gcc 4.6.2-1.
>
> The warning triggers if there is some code path in which the index is
> provably out of bounds.  That is true of this code.  I don't think I
> would describe this as a false positive.  I think it is a case where, as
> the -Wall documentation says, the code should be modified to avoid the
> warning.

I won't argue too hard against that :-)

But I do not read the -Warray-bounds documentation that way:

           "It warns about subscripts to arrays that are always
           out of bounds."

So according to that I assumed (right...) that it not warn if there
exists a path that will not trigger out-of-bounds.

Thanks,

-- 
        Lgb

Re: False positive from -Warray-bounds?

[Ian Lance Taylor]

Lars Gullik Bjønnes <larsbj@gullik.org> writes:

> On Thu, Dec 29, 2011 at 23:02, Ian Lance Taylor <iant@google.com> wrote:
>> Lars Gullik Bjønnes <larsbj@gullik.org> writes:
>>
>>> I have this code:
>>>
>>> --------------
>>> unsigned int f(unsigned int value)
>>> {
>>>     unsigned int i = (value & 0xffff);
>>>     return (i == 0xffff ? 0xffffffff : i);
>>> }
>>>
>>>
>>> static int *arr1[10];
>>>
>>> void t(unsigned int s)
>>> {
>>>     arr1[f(s)] = 0;
>>>     arr1[f(s)] = 0;
>>> }
>>> ------------------
>>>
>>>
>>> When compiled with 'gcc -Wall -Wextra -c' I get a warning about
>>> "subscript is above array bounds".
>>> Shouldn't the -Warray-bounds only warn if will _always_ be out-of-bounds?
>>>
>>> Is this a false positive, or is there something that I am completely missing?
>>>
>>> I see this with gcc from trunk (some days ago), and with redhat gcc 4.6.2-1.
>>
>> The warning triggers if there is some code path in which the index is
>> provably out of bounds.  That is true of this code.  I don't think I
>> would describe this as a false positive.  I think it is a case where, as
>> the -Wall documentation says, the code should be modified to avoid the
>> warning.
>
> I won't argue too hard against that :-)
>
> But I do not read the -Warray-bounds documentation that way:
>
>            "It warns about subscripts to arrays that are always
>            out of bounds."
>
> So according to that I assumed (right...) that it not warn if there
> exists a path that will not trigger out-of-bounds.

I guess it's a matter of perspective.  What that text is intended to say
is: the compiler can prove that the array access is out of bounds.  It
is not intended to say: there is some conditional that guards the array
access and the conditional may or may not be true.

In this case there is an array access that is out of bounds, and there
is a conditional that guards the access.  The compiler can't tell
whether the conditional is true or not.  So it warns about the array
access.

The case where the compiler will not warn is
    a[i]
when the compiler does not know the value of i, or in general can not
prove that i will be out of bounds.

Ian

Re: False positive from -Warray-bounds?

[Vincent Lefevre]

On 2011-12-29 15:24:08 -0800, Ian Lance Taylor wrote:
> I guess it's a matter of perspective.  What that text is intended to say
> is: the compiler can prove that the array access is out of bounds.

... based on an incorrect hypothesis (that the path can be reached).
With an incorrect hypothesis, one can prove anything. So, I don't
think that would be a valid proof.

For instance, compiling the following code with -O2 -Warray-bounds -c
triggers the warning.

unsigned int f(unsigned int value)
{
  unsigned int i = (value & 0xffff);
  return (i == 0xffff ? 0xffffffff : i);
}

static int arr1[10];

void t(unsigned int s)
{
  if (s >> 1 == 0)
    {
      arr1[f(s)] = 0;
      arr1[f(s)] = 0;
    }
}

-- 
Vincent Lefèvre <vincent@vinc17.net> - Web: <http://www.vinc17.net/>
100% accessible validated (X)HTML - Blog: <http://www.vinc17.net/blog/>
Work: CR INRIA - computer arithmetic / Arénaire project (LIP, ENS-Lyon)

Re: False positive from -Warray-bounds?

[Vincent Lefevre]

Another interesting testcase:

static int a[10], b[10], c[10], d[10];

unsigned int f (unsigned int v)
{
  return v == 17 ? 11 : v;
}

unsigned int g (unsigned int v)
{
  return v == 17 ? 17 : v;
}

void t (unsigned int s)
{
  if (s >> 1 == 0)
    {
      a[f(s)] = 0;
      a[f(s)] = 0;
      b[f(s)] = 0;
      c[g(s)] = 0;
      c[g(s)] = 0;
      d[H(s)] = 0;
    }
}

$ gcc-snapshot -O2 -Warray-bounds -c bounds.c -DH=f
bounds.c: In function 't':
bounds.c:17:8: warning: array subscript is above array bounds [-Warray-bounds]
bounds.c:19:8: warning: array subscript is above array bounds [-Warray-bounds]
bounds.c:20:8: warning: array subscript is above array bounds [-Warray-bounds]

$ gcc-snapshot -O2 -Warray-bounds -c bounds.c -DH=g
bounds.c: In function 't':
bounds.c:17:8: warning: array subscript is above array bounds [-Warray-bounds]

I don't see the logic.

Note: line 17 is the first "a[f(s)] = 0;".

-- 
Vincent Lefèvre <vincent@vinc17.net> - Web: <http://www.vinc17.net/>
100% accessible validated (X)HTML - Blog: <http://www.vinc17.net/blog/>
Work: CR INRIA - computer arithmetic / Arénaire project (LIP, ENS-Lyon)

Re: False positive from -Warray-bounds?

[Ian Lance Taylor]

Vincent Lefevre <vincent+gcc@vinc17.org> writes:

> On 2011-12-29 15:24:08 -0800, Ian Lance Taylor wrote:
>> I guess it's a matter of perspective.  What that text is intended to say
>> is: the compiler can prove that the array access is out of bounds.
>
> ... based on an incorrect hypothesis (that the path can be reached).
> With an incorrect hypothesis, one can prove anything.

This is not logic.  It is compiler optimization.


> So, I don't
> think that would be a valid proof.
>
> For instance, compiling the following code with -O2 -Warray-bounds -c
> triggers the warning.
>
> unsigned int f(unsigned int value)
> {
>   unsigned int i = (value & 0xffff);
>   return (i == 0xffff ? 0xffffffff : i);
> }
>
> static int arr1[10];
>
> void t(unsigned int s)
> {
>   if (s >> 1 == 0)
>     {
>       arr1[f(s)] = 0;
>       arr1[f(s)] = 0;
>     }
> }

To me this only proves that the compiler is not smart enough to see that
(s >> 1 == 0) implies that ((s & 0xffff) == 0xffff) can not be true.

Are you suggesting that the compiler should never warn if there is a
conditional guarding the array access?  Would that in practice be better
or worse than the current behaviour?

Ian

Re: False positive from -Warray-bounds?

[Vincent Lefevre]

On 2011-12-29 16:20:48 -0800, Ian Lance Taylor wrote:
> To me this only proves that the compiler is not smart enough to see that
> (s >> 1 == 0) implies that ((s & 0xffff) == 0xffff) can not be true.
> 
> Are you suggesting that the compiler should never warn if there is a
> conditional guarding the array access?  Would that in practice be better
> or worse than the current behaviour?

I think there should be two different options:
  * one that would trigger the warning if the compiler can prove
    that there will always be an out-of-bound access when the
    function is executed (unless the compiler can prove that the
    function will never be executed);
  * one that would trigger the warning if there may be an out-of-bound
    access.

BTW, can the user inform the compiler that some condition holds?
i.e. some kind of assert() but specifically for the compiler.

-- 
Vincent Lefèvre <vincent@vinc17.net> - Web: <http://www.vinc17.net/>
100% accessible validated (X)HTML - Blog: <http://www.vinc17.net/blog/>
Work: CR INRIA - computer arithmetic / Arénaire project (LIP, ENS-Lyon)

Re: False positive from -Warray-bounds?

[Ian Lance Taylor]

Vincent Lefevre <vincent+gcc@vinc17.org> writes:

> On 2011-12-29 16:20:48 -0800, Ian Lance Taylor wrote:
>> To me this only proves that the compiler is not smart enough to see that
>> (s >> 1 == 0) implies that ((s & 0xffff) == 0xffff) can not be true.
>> 
>> Are you suggesting that the compiler should never warn if there is a
>> conditional guarding the array access?  Would that in practice be better
>> or worse than the current behaviour?
>
> I think there should be two different options:
>   * one that would trigger the warning if the compiler can prove
>     that there will always be an out-of-bound access when the
>     function is executed (unless the compiler can prove that the
>     function will never be executed);
>   * one that would trigger the warning if there may be an out-of-bound
>     access.

I wonder how often the first one would actually trigger.  And I wonder
how much correct code the second one triggers on today.  I personally
think it would be reasonable to rewrite the original example to avoid
the warning, since the code certainly looks like it can generate an out
of bounds access.


> BTW, can the user inform the compiler that some condition holds?
> i.e. some kind of assert() but specifically for the compiler.

As far as I know there is no way to do this directly.  The closest you
can come is something like

  if (!condition_which_must_be_true ())
    __builtin_unreachable ();

This will help the compiler in some cases but it won't track a complex
condition in any useful way.

Ian

Re: False positive from -Warray-bounds?

[David Brown]

On 30/12/2011 05:59, Ian Lance Taylor wrote:
> Vincent Lefevre<vincent+gcc@vinc17.org>  writes:
>
>> On 2011-12-29 16:20:48 -0800, Ian Lance Taylor wrote:
>>> To me this only proves that the compiler is not smart enough to see that
>>> (s>>  1 == 0) implies that ((s&  0xffff) == 0xffff) can not be true.
>>>
>>> Are you suggesting that the compiler should never warn if there is a
>>> conditional guarding the array access?  Would that in practice be better
>>> or worse than the current behaviour?
>>
>> I think there should be two different options:
>>    * one that would trigger the warning if the compiler can prove
>>      that there will always be an out-of-bound access when the
>>      function is executed (unless the compiler can prove that the
>>      function will never be executed);
>>    * one that would trigger the warning if there may be an out-of-bound
>>      access.
>
> I wonder how often the first one would actually trigger.  And I wonder
> how much correct code the second one triggers on today.  I personally
> think it would be reasonable to rewrite the original example to avoid
> the warning, since the code certainly looks like it can generate an out
> of bounds access.
>

The first one quickly reduces to the halting problem, amongst other 
issues.  Consider :

static int a[10];
extern int foo(int x);

void bar(void) {
	if (foo(1)) a[100]++;
}

You can't make a "no false negatives" warning here - it depends entirely 
on foo, what it returns, and /if/ it returns.

If code looks dodgy, it should be warned as dodgy - that's what warnings 
are for.  If you want to write code that looks dodgy but isn't, as one 
sometimes does, then disable the warning - either omit it from the 
command line, or use "#pragma GCC diagnostic" around the code in question.

Warnings are there to help people write clearer code and avoid common or 
accidental mistakes - a warning that triggers on /possible/ out-of-bound 
array access fits that purpose fine (IMHO, of course).

If the compiler could tell without any doubt that the array is being 
accessed illegally, then maybe an error would be better (since the code 
has undefined behaviour at run-time, is the compiler allowed to reject it?).

>
>> BTW, can the user inform the compiler that some condition holds?
>> i.e. some kind of assert() but specifically for the compiler.
>
> As far as I know there is no way to do this directly.  The closest you
> can come is something like
>
>    if (!condition_which_must_be_true ())
>      __builtin_unreachable ();
>
> This will help the compiler in some cases but it won't track a complex
> condition in any useful way.
>
> Ian
>

Some sort of general way to provide information to the compiler via 
assertions would be /really/ nice.  The most useful case I could think 
of would be to specify ranges of a variable or expression - if the 
compiler could track those ranges and use them for warnings and 
optimisation.  Imagine the possibilities of a generalised "nonnull" 
function parameter attribute with range limits, and the benefits that 
would have for compile-time error checking!

Re: False positive from -Warray-bounds?

[Vincent Lefevre]

On 2011-12-30 09:26:18 +0100, David Brown wrote:
> On 30/12/2011 05:59, Ian Lance Taylor wrote:
> >Vincent Lefevre<vincent+gcc@vinc17.org>  writes:
> >
> >>On 2011-12-29 16:20:48 -0800, Ian Lance Taylor wrote:
> >>>To me this only proves that the compiler is not smart enough to see that
> >>>(s>>  1 == 0) implies that ((s&  0xffff) == 0xffff) can not be true.
> >>>
> >>>Are you suggesting that the compiler should never warn if there is a
> >>>conditional guarding the array access?  Would that in practice be better
> >>>or worse than the current behaviour?
> >>
> >>I think there should be two different options:
> >>   * one that would trigger the warning if the compiler can prove
> >>     that there will always be an out-of-bound access when the
> >>     function is executed (unless the compiler can prove that the
> >>     function will never be executed);

Note: by "unless the compiler can prove that the function will never
be executed", I mean for instance that the function would be declared
as static *and* it is never called or its call is in dead code, like

  if (0)
    foo ();

> >>   * one that would trigger the warning if there may be an out-of-bound
> >>     access.
> >
> >I wonder how often the first one would actually trigger.  And I wonder
> >how much correct code the second one triggers on today.  I personally
> >think it would be reasonable to rewrite the original example to avoid
> >the warning, since the code certainly looks like it can generate an out
> >of bounds access.
> >
> 
> The first one quickly reduces to the halting problem, amongst other issues.

Of course not, unless you want to be perfect, but being perfect has
never been a requirement (just like with other warnings).

> Consider :
> 
> static int a[10];
> extern int foo(int x);
> 
> void bar(void) {
> 	if (foo(1)) a[100]++;
> }
> 
> You can't make a "no false negatives" warning here - it depends
> entirely on foo, what it returns, and /if/ it returns.

This is typically the case where (2) would trigger the warning, but
not (1). I have never said that there should be "no false negatives".
The goal of (1) is to trigger a warning only in the cases where it
is most certain (but without any strong guarantee) that there is a
real problem.

> If code looks dodgy, it should be warned as dodgy - that's what
> warnings are for.

The dodginess is very subjective, and that's not up to gcc to decide,
in particular because comments and function specifications can have
an influence. In the original example, the path from which gcc could
deduce an out-of-bound access was in different function. Perhaps in
the real code, this path was needed in some calls, but could never
occur in the case the array was accessed. I don't see this code as
particularly dodgy, and duplicating the function to handle both kinds
of calls could be worse.

>  If you want to write code that looks dodgy but isn't, as one sometimes
> does, then disable the warning

But disabling all the related warnings could be too much, and hide
real problems. Hence my proposition to have two kinds of warnings.

> - either omit it from the command line, or
> use "#pragma GCC diagnostic" around the code in question.

If the pragma can locally disable the warning, perhaps, but the
pragma itself may trigger warnings with other compilers. Something
that could be activated with the preprocessor would be much better:

#if defined(__GNUC__)
# define CORRECT ...specific GCC extension...
#else
# define CORRECT
#endif

and in the code, something like:

  CORRECT a[foo(1)] = 0;

or

  a[CORRECT(foo(1))] = 0;

> Warnings are there to help people write clearer code and avoid common or
> accidental mistakes - a warning that triggers on /possible/ out-of-bound
> array access fits that purpose fine (IMHO, of course).

The notion of clear code can't be reduced to some basic arbitrary
rules.

> If the compiler could tell without any doubt that the array is being
> accessed illegally, then maybe an error would be better (since the code has
> undefined behaviour at run-time, is the compiler allowed to reject it?).

The compiler cannot tell anything without any doubt, because it
doesn't know whether some function will ever be called (perhaps
except in the case of main() and it descendants when a program
is generated).

-- 
Vincent Lefèvre <vincent@vinc17.net> - Web: <http://www.vinc17.net/>
100% accessible validated (X)HTML - Blog: <http://www.vinc17.net/blog/>
Work: CR INRIA - computer arithmetic / Arénaire project (LIP, ENS-Lyon)

Re: False positive from -Warray-bounds?

[Vincent Lefevre]

On 2011-12-29 14:02:23 -0800, Ian Lance Taylor wrote:
> Lars Gullik Bjønnes <larsbj@gullik.org> writes:
> 
> > I have this code:
> >
> > --------------
> > unsigned int f(unsigned int value)
> > {
> >     unsigned int i = (value & 0xffff);
> >     return (i == 0xffff ? 0xffffffff : i);
> > }
> >
> >
> > static int *arr1[10];
> >
> > void t(unsigned int s)
> > {
> >     arr1[f(s)] = 0;
> >     arr1[f(s)] = 0;
> > }
> > ------------------
[...]
> The warning triggers if there is some code path in which the index is
> provably out of bounds.  That is true of this code.  I don't think I
> would describe this as a false positive.  I think it is a case where, as
> the -Wall documentation says, the code should be modified to avoid the
> warning.

The -Warray-bounds warning occurs with:

void t(unsigned int s)
{
    arr1[f(s)] = 0;
    arr1[f(s)] = 0;
}

but not with:

void t(unsigned int s)
{
    arr1[f(s)] = 0;
}

If "The warning triggers if there is some code path in which the index
is provably out of bounds." is the intended behavior (assuming that
the warning phrasing isn't really correct), isn't this proof the same
one in both cases? Why this difference in the gcc behavior?

Tested with the -O2 -Warray-bounds -c options and:
  gcc (Debian 4.6.2-9) 4.6.2
and
  gcc-snapshot (Debian 20111210-1) 4.7.0 20111210 (experimental) [trunk revision 182188]

-- 
Vincent Lefèvre <vincent@vinc17.net> - Web: <http://www.vinc17.net/>
100% accessible validated (X)HTML - Blog: <http://www.vinc17.net/blog/>
Work: CR INRIA - computer arithmetic / Arénaire project (LIP, ENS-Lyon)

Re: False positive from -Warray-bounds?

[Ian Lance Taylor]

Vincent Lefevre <vincent+gcc@vinc17.org> writes:

> The -Warray-bounds warning occurs with:
>
> void t(unsigned int s)
> {
>     arr1[f(s)] = 0;
>     arr1[f(s)] = 0;
> }
>
> but not with:
>
> void t(unsigned int s)
> {
>     arr1[f(s)] = 0;
> }
>
> If "The warning triggers if there is some code path in which the index
> is provably out of bounds." is the intended behavior (assuming that
> the warning phrasing isn't really correct), isn't this proof the same
> one in both cases? Why this difference in the gcc behavior?

Sounds like a bug somewhere to me.

The -Warray-bounds option is definitely optimization dependent, which is
a flaw.

Ian

Re: False positive from -Warray-bounds?

[Vincent Lefevre]

On 2011-12-29 22:37:48 +0100, Lars Gullik Bjønnes wrote:
> I have this code:
> 
> --------------
> unsigned int f(unsigned int value)
> {
>     unsigned int i = (value & 0xffff);
>     return (i == 0xffff ? 0xffffffff : i);
> }
> 
> 
> static int *arr1[10];
> 
> void t(unsigned int s)
> {
>     arr1[f(s)] = 0;
>     arr1[f(s)] = 0;
> }
> ------------------
> 
> 
> When compiled with 'gcc -Wall -Wextra -c' I get a warning about
> "subscript is above array bounds".

Under Debian, one also needs the -O2 option to make the warning appear.

-- 
Vincent Lefèvre <vincent@vinc17.net> - Web: <http://www.vinc17.net/>
100% accessible validated (X)HTML - Blog: <http://www.vinc17.net/blog/>
Work: CR INRIA - computer arithmetic / Arénaire project (LIP, ENS-Lyon)