GCC and out-of-range constant array indexes?

GCC and out-of-range constant array indexes?

[Gary Funck]

Consider the following:

$ cat -n t.c
     1
     2  int A[10] = { 0 };
     3
     4  int main()
     5  {
     6    A[10] = 10;
     7    A[-1] = -1;
     8    return 0;
     9  }

In a compiler test case that I reviewed recently, there was the
expectation that the compiler would issue a compile-time warning
on the statements at lines 6 an 7 above.  I tried this with
GCC version "gcc (GCC) 4.4.4 20100630 (Red Hat 4.4.4-10)"
recently and was unable to find compilation switches that
would cause it to complain about the use of out-of-range
indexes above.

Is there a technical reason that the compiler should not
issue a warning, or might this feature become a legitimate RFE?

thanks,
- Gary

Re: GCC and out-of-range constant array indexes?

[Ian Lance Taylor]

Gary Funck <gary@intrepid.com> writes:

> Consider the following:
>
> $ cat -n t.c
>      1
>      2  int A[10] = { 0 };
>      3
>      4  int main()
>      5  {
>      6    A[10] = 10;
>      7    A[-1] = -1;
>      8    return 0;
>      9  }
>
> In a compiler test case that I reviewed recently, there was the
> expectation that the compiler would issue a compile-time warning
> on the statements at lines 6 an 7 above.  I tried this with
> GCC version "gcc (GCC) 4.4.4 20100630 (Red Hat 4.4.4-10)"
> recently and was unable to find compilation switches that
> would cause it to complain about the use of out-of-range
> indexes above.

-Warray-bounds, but that is one of the warnings which is unfortunately
only available when optimizing.  In this case it requires -O2.

There was an attempt a couple of years ago to implement this warning
when not optimizing, but it leds to http://gcc.gnu.org/PR36108 , where
the issue is that there are array bounds violations which occur in code
which is never executed.  When not optimizing, the compiler does not
currently know which code is executed and which is not.

Ian

Re: GCC and out-of-range constant array indexes?

[Gary Funck]

On 10/07/10 21:24:18, Ian Lance Taylor wrote:
> -Warray-bounds, but that is one of the warnings which is unfortunately
> only available when optimizing.  In this case it requires -O2.

Ian, thanks.  I had thought optimization might be involved, but didn't try -O2.

> There was an attempt a couple of years ago to implement this warning
> when not optimizing [...].

Would it be possible to compute enough of the control flow graph
to process warnings like this one, without running the
actual optimizations, unless those optimizations are requested?
Would the cost be too high?

- Gary

Re: GCC and out-of-range constant array indexes?

[Basile Starynkevitch]

On Fri, 8 Oct 2010 08:14:23 -0700
Gary Funck <gary@intrepid.com> wrote:

> On 10/07/10 21:24:18, Ian Lance Taylor wrote:
> > -Warray-bounds, but that is one of the warnings which is unfortunately
> > only available when optimizing.  In this case it requires -O2.
> 
> Ian, thanks.  I had thought optimization might be involved, but didn't try -O2.
> 
> Would it be possible to compute enough of the control flow graph
> to process warnings like this one, without running the
> actual optimizations, unless those optimizations are requested?
> Would the cost be too high?

I am not an expert on these optimizations, but why would you want that? 
The optimizations involved are indeed expensive (otherwise it would be
-O1 not -O2), but once you asked for them, why only get warnings
without the code generation improvement? (I am assuming that the
required computations in the compiler are mostly in the middle end, and
that getting such warnings are a side effect).

Cheers.


-- 
Basile STARYNKEVITCH         http://starynkevitch.net/Basile/
email: basile<at>starynkevitch<dot>net mobile: +33 6 8501 2359
8, rue de la Faiencerie, 92340 Bourg La Reine, France
*** opinions {are only mine, sont seulement les miennes} ***

Re: GCC and out-of-range constant array indexes?

[Gary Funck]

On 10/08/10 18:38:29, Basile Starynkevitch wrote:
> I am not an expert on these optimizations, but why would you want that? 

I routinely compile/build with "-O0 -g3" because the code is easier to debug.  I
also admit that I compile/build with "-O0" because it is faster than
"-O2" or "-O3" for example, and during development I am more interested
in faster turn-around time on builds than faster execution time.

Also, when I compile/build projects, I try to use the maximum level of warnings
and checking that the source code base will support.  I am willing to trade
off some support/build time in favor of more thorough warnings.

- Gary

Re: GCC and out-of-range constant array indexes?

[Ian Lance Taylor]

Gary Funck <gary@intrepid.com> writes:

>> There was an attempt a couple of years ago to implement this warning
>> when not optimizing [...].
>
> Would it be possible to compute enough of the control flow graph
> to process warnings like this one, without running the
> actual optimizations, unless those optimizations are requested?
> Would the cost be too high?

I think it could be done but I don't think it would be simple.  I do
think it would be a good idea to make warnings independent of
optimization level, except for those warnings like -Wstrict-aliasing
which are specifically about optimizations.

Ian

Re: GCC and out-of-range constant array indexes?

[Basile Starynkevitch]

On Fri, 8 Oct 2010 09:54:07 -0700
Gary Funck <gary@intrepid.com> wrote:

> On 10/08/10 18:38:29, Basile Starynkevitch wrote:
> > I am not an expert on these optimizations, but why would you want that? 
> 
> I routinely compile/build with "-O0 -g3" because the code is easier to debug.  I
> also admit that I compile/build with "-O0" because it is faster than
> "-O2" or "-O3" for example, and during development I am more interested
> in faster turn-around time on builds than faster execution time.

I understand that. Using "-O1 -g3" is a suitable compromise also.
> 
> Also, when I compile/build projects, I try to use the maximum level of warnings
> and checking that the source code base will support.  I am willing to trade
> off some support/build time in favor of more thorough warnings.

You could build both a release version with "-O2" or "-O2 -g" and a
development version with "-O0 -g3".

Howeer, I see a logic in needing -O2 to get some warnings.
Optimizations are expensive, and they compute static properties of the
source code, which are usable (& necessary and used) for additional
warnings.

Cheers.


-- 
Basile STARYNKEVITCH         http://starynkevitch.net/Basile/
email: basile<at>starynkevitch<dot>net mobile: +33 6 8501 2359
8, rue de la Faiencerie, 92340 Bourg La Reine, France
*** opinions {are only mine, sont seulement les miennes} ***

Re: GCC and out-of-range constant array indexes?

[Ian Lance Taylor]

Basile Starynkevitch <basile@starynkevitch.net> writes:

> Howeer, I see a logic in needing -O2 to get some warnings.
> Optimizations are expensive, and they compute static properties of the
> source code, which are usable (& necessary and used) for additional
> warnings.

The problem that I think we've discovered over the years is that when
warnings depend on optimizations, the warnings are unstable.  It means
that as optimizations change, the warnings appear and disappear.  And
that means that as people move their code to new compiler releases, they
get unpredictable new warnings.

That can be OK when the warnings are always true positives.  However, it
is very problematic when the warnings are sometimes false positives,
because it forces people to change their code for no reason, or to
disable the warning.

It might seem to be something like an out of bounds constant array index
can not go wrong, in the sense that it can never give a false positive.
However, we have already seen that it can go wrong if the compiler does
not reliably ignore code which is not executed.

Another reason that it's problematic to have warnings depend on
optimization level is that many people develop with -O0, and we want to
give them as many true positive warnings at that level as we can.

Ian

Re: GCC and out-of-range constant array indexes?

[Basile Starynkevitch]

On Fri, 08 Oct 2010 11:03:27 -0700
Ian Lance Taylor <iant@google.com> wrote:

> Basile Starynkevitch <basile@starynkevitch.net> writes:
> 
> > Howeer, I see a logic in needing -O2 to get some warnings.
> > Optimizations are expensive, and they compute static properties of the
> > source code, which are usable (& necessary and used) for additional
> > warnings.
> 
> The problem that I think we've discovered over the years is that when
> warnings depend on optimizations, the warnings are unstable.  It means
> that as optimizations change, the warnings appear and disappear.  And
> that means that as people move their code to new compiler releases, they
> get unpredictable new warnings.

Is this unstability of warnings related to the (perhaps stupid)
folklore of avoiding -O3 (what I mean is that, for instance, most Linux
distributions are built with -O2 at most; very few are using -O3; this
brings a chicken & egg issue: since -O3 is much less used, it is
probably more buggy & less usable!).

But I also noticed (even on the runtime inside the MELT branch of GCC)
that newer GCC releases give better & more warnings than older ones.

(BTW, Ian, I am still hoping for your review & ok of my gengtype patches!).

Cheers.

-- 
Basile STARYNKEVITCH         http://starynkevitch.net/Basile/
email: basile<at>starynkevitch<dot>net mobile: +33 6 8501 2359
8, rue de la Faiencerie, 92340 Bourg La Reine, France
*** opinions {are only mine, sont seulement les miennes} ***

Re: GCC and out-of-range constant array indexes?

[Gary Funck]

How about the following:

1) Default warnings are cheap, and work fine at -O0.

2) Expensive warnings (-Wall, -Warray-bounds, -Wuninitialized, -Wunused)
[not sure about the actual list] that require optimizations, will issue
a Warning when they are requested, but the appropriate optimization level
has not been asserted, that is required for those warnings to work in their
maximal fashion.

Or:

Specification of the expensive warnings will cause appropriate
control flow computations that are required to support those
warning levels. (as suggested previously)

Re: GCC and out-of-range constant array indexes?

[Ian Lance Taylor]

Gary Funck <gary@intrepid.com> writes:

> 2) Expensive warnings (-Wall, -Warray-bounds, -Wuninitialized, -Wunused)
> [not sure about the actual list] that require optimizations, will issue
> a Warning when they are requested, but the appropriate optimization level
> has not been asserted, that is required for those warnings to work in their
> maximal fashion.
>
> Or:
>
> Specification of the expensive warnings will cause appropriate
> control flow computations that are required to support those
> warning levels. (as suggested previously)

I think both of those alternatives would be surprising and easily
misunderstood behaviour for many compiler users.  The first means that
you have to use different warnings at different optimization levels, or
you need to use some mechanism to disable the default warning.  The
second means that adding a warning option could have a significant
effect on compile time, which is surprising.

My current thinking is that the following should be followed by all
warnings:

* They should be entirely independent of optimization level, or

* They should warn specifically about the consequences of some easily
  misunderstood optimization, or

* They should always be true positives.

Almost all current warnings already meet those requirements; the main
problem child is -Wuninitialized.

Ian

Re: GCC and out-of-range constant array indexes?

[Gary Funck]

On 10/08/10 13:22:46, Ian Lance Taylor wrote:
> I think both of those alternatives would be surprising and easily
> misunderstood behaviour for many compiler users.  [...]

I find the following behavior to be surprising:

$ gcc -Warray-bounds -O0 -c t.c
$ gcc -Warray-bounds -O1 -c t.c 
$ gcc -Warray-bounds -O2 -c t.c 
t.c: In function ‘main’:
t.c:6: warning: array subscript is above array bounds
t.c:7: warning: array subscript is below array bounds

The impact is that I may think that after I build my project at
-O0 or -O1, with various warnings enabled, that there are
potential surprises that await, when I perform a production build
at -O2 and higher.

It makes perfect sense to me that the following happens:

$ gcc -Warray-bounds -O1 -c t.c 
t.c: Warning: -Warray-bounds has no effect unless compiled
with optimization level -O2 and higher.

> Almost all current warnings already meet those requirements; the main
> problem child is -Wuninitialized.

... and -Warray-bounds?

RE: GCC and out-of-range constant array indexes?

[Hargett, Matt]

> The impact is that I may think that after I build my project at
> -O0 or -O1, with various warnings enabled, that there are
> potential surprises that await, when I perform a production build
> at -O2 and higher.

-Warray-bounds warnings can also be triggered only when using the aggressive inlining optimizations enabled by -O3. I assume the same is true for -flto, which would allow for a cross-module inlining and therefore deeper analysis.

I personally just use PC-Lint as an extra safety net to help find issues like this during my necessarily short TDD cycle. Then when the optimized build is compiled, all of the issues that GCC would have found were generally already found by PC-Lint. It's quite nice to have the two tools cross-check each other in a usage pattern that they are both well-suited to.

Re: GCC and out-of-range constant array indexes?

[Ian Lance Taylor]

Gary Funck <gary@intrepid.com> writes:

> On 10/08/10 13:22:46, Ian Lance Taylor wrote:
>> I think both of those alternatives would be surprising and easily
>> misunderstood behaviour for many compiler users.  [...]
>
> I find the following behavior to be surprising:
>
> $ gcc -Warray-bounds -O0 -c t.c
> $ gcc -Warray-bounds -O1 -c t.c 
> $ gcc -Warray-bounds -O2 -c t.c 
> t.c: In function ‘main’:
> t.c:6: warning: array subscript is above array bounds
> t.c:7: warning: array subscript is below array bounds
>
> The impact is that I may think that after I build my project at
> -O0 or -O1, with various warnings enabled, that there are
> potential surprises that await, when I perform a production build
> at -O2 and higher.
>
> It makes perfect sense to me that the following happens:
>
> $ gcc -Warray-bounds -O1 -c t.c 
> t.c: Warning: -Warray-bounds has no effect unless compiled
> with optimization level -O2 and higher.

Yes, that warning would be good for people, if it happened once.
It's like the spiel on the airplane about how to buckle your seat belt.
It's good for everybody to hear that once.  The tenth time you hear it,
it's pointless.  The hundredth time, it's annoying.

Many people compile with -Werror and most people use the same set of
warning options at all optimization levels.  So we would then require a
way to explicitly disable this warning.



>> Almost all current warnings already meet those requirements; the main
>> problem child is -Wuninitialized.
>
> ... and -Warray-bounds?

-Warray-bounds meets the criteria I listed, because it is pretty much
always a true positive.

I think you are basically suggesting that we drop the third criterion on
my list ("they should always be true positives").  I could support that
if others agree.

Ian

Re: GCC and out-of-range constant array indexes?

[Dave Korn]

On 08/10/2010 21:39, Gary Funck wrote:

> The impact is that I may think that after I build my project at
> -O0 or -O1, with various warnings enabled, that there are
> potential surprises that await, when I perform a production build
> at -O2 and higher.

  The moral of the story is that you should *test* the *production* build.
Not an experimental dev build.

    cheers,
      DaveK

Re: GCC and out-of-range constant array indexes?

[Gary Funck]

On 10/08/10 18:38:29, Basile Starynkevitch wrote:
> I am not an expert on these optimizations, but why would you want that? 
> The optimizations involved are indeed expensive (otherwise it would be
> -O1 not -O2), but once you asked for them, why only get warnings
> without the code generation improvement?

Because the optimizations also make the generated code more
difficult to debug, and can introduce new (buggy optimization) bugs.
I prefer to get the code working with -O0 and then verify that it
still works after optimization, because I think that minimizes
my development risk and maximizes my productivity.  Along those
lines, I would still like to have all the compile-time warnings
that I can get, and am willing to have my non-optimized builds
go a little slower (say, no more than 20% slower) to have the
additional warnings.

> However, I see a logic in needing -O2 to get some warnings.
> Optimizations are expensive, and they compute static properties of the
> source code, which are usable (& necessary and used) for additional
> warnings.

After hearing the pros/cons, I have come around to the point of view
that GCC's method of detecting things like uninitialized local variables
is part of its optimization architecture.  If I accept that my
development cycle is: ("first -O0, then full optimization"), then I
will have to accept that some warnings might show up when optimizations
are turned on.  Either that, or I might routinely run a tool like
PC-LINT, or Coverity during development, and this may minimize
the surprise warnings that pop up when optimizations are enabled.
Or as you suggested, always run two parallel builds: one optimized, and
one not.

I appreciate every one's ideas and suggestions.  This has
been an interesting discussion thread.

- Gary

Re: GCC and out-of-range constant array indexes?

[Florian Weimer]

* Geert Bosch:

> The Ada front end has very extensive warnings. I don't think
> they really contribute measurably to performance.
> We don't try to construct call graphs to determine
> wether the array reference will be executed or not.
> If the line appears in your program, it will cause an
> error if executed, so we will warn: either you wrote
> dead code, or wrong code.

In other languages, dead code doesn't come not just from the
programmer, but also from the preprocessor and from expansion of
generics (in fact, I've seen misleading warnings involving Ada
generics, too).  So the Ada exprience is not likely to translate to
other front ends.

Re: GCC and out-of-range constant array indexes?

[Manuel López-Ibáñez]

On 9 October 2010 21:34, Jakub Jelinek <jakub@redhat.com> wrote:
> On Sat, Oct 09, 2010 at 09:22:42PM +0200, Manuel L?pez-Ib??ez wrote:
>> My intention by answering Gary is to point out that if he is thinking
>> about working on this problem, he should consider building a cheap
>> FE-specific CFG, rather than try to share the current infrastructure
>> between FE and middle-end. I would like to see this implemented, so
>
> I don't think that's a good idea.  Much better would be just to
> not emit diagnostics, which shouldn't be emitted for dead code, right away,
> but instead of that queue it into the IL (in a form of something
> like __builtin_diagnostics, or something similar).  Then after cfg cleanup + DCE
> has been run (or at expansion time?) we could issue diagnostics for the
> __builtin_diagnostics left in the IL afterwards.  For -O0 if no DCE happens
> at all we could have some cheap pass that would just nuke obviously unreachable
> __builtin_diagnostics and don't modify the IL otherwise (of course gated on
> whether there are any in the IL).

That doesn't solve the problem of diagnostics changing at different
optimization levels. But I don't care much about that, so I wouldn't
complain if anyone implemented either option.

Cheers,

Manuel.

Re: GCC and out-of-range constant array indexes?

[Jakub Jelinek]

On Sat, Oct 09, 2010 at 09:22:42PM +0200, Manuel L?pez-Ib??ez wrote:
> My intention by answering Gary is to point out that if he is thinking
> about working on this problem, he should consider building a cheap
> FE-specific CFG, rather than try to share the current infrastructure
> between FE and middle-end. I would like to see this implemented, so

I don't think that's a good idea.  Much better would be just to
not emit diagnostics, which shouldn't be emitted for dead code, right away,
but instead of that queue it into the IL (in a form of something
like __builtin_diagnostics, or something similar).  Then after cfg cleanup + DCE
has been run (or at expansion time?) we could issue diagnostics for the
__builtin_diagnostics left in the IL afterwards.  For -O0 if no DCE happens
at all we could have some cheap pass that would just nuke obviously unreachable
__builtin_diagnostics and don't modify the IL otherwise (of course gated on
whether there are any in the IL).

	Jakub

Re: GCC and out-of-range constant array indexes?

[Manuel López-Ibáñez]

On 9 October 2010 05:22, Geert Bosch <bosch@adacore.com> wrote:
>
> On Oct 8, 2010, at 18:18, Manuel López-Ibáñez wrote:
>
>> It is possible to do it quite fast. Clang implements all warnings,
>> including Wuninitialized, in the FE using fast analysis and they claim
>> very low false positives.
>> However, there are various reasons why it has not been attempted in GCC:
>>
>> * GCC is too slow already at -O0, slowing it down further would not be
>> acceptable. So you need a really high-performing implementation.
>
> The Ada front end has very extensive warnings. I don't think
> they really contribute measurably to performance.
> We don't try to construct call graphs to determine
> wether the array reference will be executed or not.
> If the line appears in your program, it will cause an
> error if executed, so we will warn: either you wrote
> dead code, or wrong code.

This may be acceptable for Ada, but it seems not acceptable for C/C++.
In fact, warnings have been removed/tweaked because they broke GCC
build for such code.

In any case, it is possible to implement a basic flow-sensitive CFG in the FE:

http://clang.llvm.org/docs/InternalsManual.html#CFG

but it is not clear whether such a thing would be accepted in GCC.

My intention by answering Gary is to point out that if he is thinking
about working on this problem, he should consider building a cheap
FE-specific CFG, rather than try to share the current infrastructure
between FE and middle-end. I would like to see this implemented, so
I'd rather have a good-enough implementation committed to GCC than a
near-perfect solution that is never completed or accepted in trunk.

> To avoid false positives in inlined code, code instantiated
> from templates and the like, we have a notion of code that
> comes from source or not. For many warnings, we will only
> post the warning if the code comes from source, that is:
> is not generated by the compiler as part of the compilation
> process.

Good for Ada!

Unfortunately, the C/C++ FEs do not have such infrastructure. There is
some promising work  for macros http://gcc.gnu.org/PR7263 but it is
far from ready and it would still require the diagnostics machinery to
start using it, which is even further away. I hope Dodji manages to
find some time to finish it, because the possibilities are impressive.

See "Automatic Macro Expansion" here: http://clang.llvm.org/diagnostics.html

I think for templates it is currently feasible to do this for each
warning, but there is no general or straight-forward way.

See the often-reported bug: http://gcc.gnu.org/PR11856

A counter-example: http://gcc.gnu.org/PR43167

And (for once!!!) Clang doesn't get this right this either:
http://llvm.org/PR6418

I think it is generally acknowledged that Ada has the best diagnostics
among GCC FEs. Too bad Adacore customers do not use C/C++ ;-)

Cheers,

Manuel.

Re: GCC and out-of-range constant array indexes?

[Geert Bosch]

On Oct 8, 2010, at 18:18, Manuel López-Ibáñez wrote:

> It is possible to do it quite fast. Clang implements all warnings,
> including Wuninitialized, in the FE using fast analysis and they claim
> very low false positives.
> However, there are various reasons why it has not been attempted in GCC:
> 
> * GCC is too slow already at -O0, slowing it down further would not be
> acceptable. So you need a really high-performing implementation.

The Ada front end has very extensive warnings. I don't think
they really contribute measurably to performance.
We don't try to construct call graphs to determine
wether the array reference will be executed or not.
If the line appears in your program, it will cause an
error if executed, so we will warn: either you wrote
dead code, or wrong code.

To avoid false positives in inlined code, code instantiated
from templates and the like, we have a notion of code that
comes from source or not. For many warnings, we will only
post the warning if the code comes from source, that is:
is not generated by the compiler as part of the compilation
process.

  -Geert

Re: GCC and out-of-range constant array indexes?

[Manuel López-Ibáñez]

> Would it be possible to compute enough of the control flow graph
> to process warnings like this one, without running the
> actual optimizations, unless those optimizations are requested?
> Would the cost be too high?

It is possible to do it quite fast. Clang implements all warnings,
including Wuninitialized, in the FE using fast analysis and they claim
very low false positives.
However, there are various reasons why it has not been attempted in GCC:

* GCC is too slow already at -O0, slowing it down further would not be
acceptable. So you need a really high-performing implementation.

* The FEs are quite complex, and both C and C++ construct gimple in a
different way. It would be easier to do the analysis once the FE has
finished building generic/gimple. However,

* The FEs fold/transform expressions as they go, so you don't have a
1-to-1 relationship between the intermediate representation generated
by the FEs and the code.

Yet, anything is possible in principle. First, it would need someone
to do the work. As far as I know, there is no one planning or willing
to work on this. And second, it would need to be accepted by the
maintainers. I suggest you clarify the latter before implementing your
idea, or you will be seriously disappointed.

An alternative would be to move the heavier analysis to an external
tool that can be invoked by the compiler and share the same
infrastructure. As http://clang-analyzer.llvm.org/ does. However, GCC
is many years far away to enable implementing such technology. So
perhaps implementing some analysis on the FE would be a more promising
approach (despite the caveats mentioned above). But you have to find
out if the overhead would be acceptable for the respective
maintainers.

Cheers,

Manuel.