| Message ID | 3ed6bac0-46f4-097b-cc73-ad7f87ba16f5@redhat.com |
|---|---|
| State | New |
| Headers | show |
| Series | convert -Walloca pass to ranger | expand |
On Mon, 2020-10-05 at 11:51 +0200, Aldy Hernandez via Gcc-patches wrote: > The walloca pass is a mess. It has all sorts of heuristics to > divine > problematic ranges fed into alloca, none of them very good, and all > of > them unreadable. The mess therein was actually one of the original > motivators for the ranger project (along with array bounds checking). > > The attached patch is a conversion of the pass to ranger. It's > mostly > an exercise in removing code. The entire pass almost reduces to: > > + // If the user specified a limit, use it. > + int_range_max r; > + if (warn_limit_specified_p (is_vla) > + && TREE_CODE (len) == SSA_NAME > + && query.range_of_expr (r, len, stmt) > + && !r.varying_p ()) > + { > + // The invalid bits are anything outside of [0, MAX_SIZE]. > + static int_range<2> invalid_range (build_int_cst > (size_type_node, 0), > + build_int_cst > (size_type_node, > + max_size), > + VR_ANTI_RANGE); > + > + r.intersect (invalid_range); > + if (r.undefined_p ()) > + return alloca_type_and_limit (ALLOCA_OK); > + > + return alloca_type_and_limit (ALLOCA_BOUND_MAYBE_LARGE, > + wi::to_wide (integer_zero_node)); > } > > That is, if the range of the integer passed to alloca is outside of > [0,MAX_SIZE], warn, otherwise it's ok. Plain and simple. > > You will notice I removed the nuanced errors we gave before-- like > trying to guess whether the problematic range came by virtue of a > signed > cast conversion. These specific errors were never part of the > original > design, they were just stuff we could guess by how the IL > looked. It > was non-exact and fragile. Now we just say the alloca argument may > be > too large, period. > > It the future, I would even like to remove the specific range the > ranger > was able to compute from the error message itself. As will become > obvious, the ranger can get pretty outrageous ranges that are > entirely > non-obvious by looking at the code. Peppering the error messages > with > these ranges will ultimately just confuse the user. But alas, that's > a > problem for another patch to solve. I can't comment on the content of the patch itself, but with my "user experience hat" on I'm wondering what diagnostic messages involving ranges ought to look like. I worry that if we simply drop range information altogether from the messages, we're not giving the user enough information to make a judgment call on whether to pay attention to the diagnostic. That said, I'm unhappy with the status quo of our range-based messages, so I don't object to the patch. Some possible ideas: I added support for capturing and printing control-flow paths for diagnostics in gcc 10; see gcc/diagnostic-path.h. I added this for the analyzer code, but it's usable outside of it. It's possible to use this to associate a chain of events with a diagnostic, by building a diagnostic_path and associating it with a rich_location. Perhaps the ranger code could have a mode which captures diagnostic_paths, where the events in the path give pertinent information about ranges - e.g. the various conditionals that lead to a particular range. There's a pre-canned simple_diagnostic_path that can be populated with simple_diagnostic_event, or you could create your own ranger-specific event and path subclasses. These can be temporary objects that live on the stack next to the rich_location, just for the lifetime of emitting the diagnostic. Perhaps a "class ranger_rich_location" which implicitly supplies an instance of "class ranger_diagnostic_path" to the diagnostic, describing where the range information comes from? Here are some more out-there ideas I had some years ago (I can't remember if these ever made it to the mailing list). These ideas focus more on how the ranges are used, rather than where the ranges come from. There's an interaction, though, so I think it's on-topic - can the ranger code supply this kind of information? Consider this problematic call to sprintf: $ cat demo.c #include <stdio.h> const char *test_1 (const char *msg) { static char buf[16]; sprintf (buf, "msg: %s\n", msg); return buf; } void test_2 () { test_1 ("this is long enough to cause trouble"); } Right now, we emit this (this is trunk, plus some fixes for line- numbering bugs): $ ./xgcc -B. -c demo.c -Wall -O2 demo.c: In function ‘test_2’: demo.c:6:23: warning: ‘%s’ directive writing 36 bytes into a region of size 11 [-Wformat-overflow=] 6 | sprintf (buf, "msg: %s\n", msg); | ^~ demo.c:12:11: 12 | test_1 ("this is long enough to cause trouble"); | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ demo.c:6:3: note: ‘sprintf’ output 43 bytes into a destination of size 16 6 | sprintf (buf, "msg: %s\n", msg); | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ I brainstormed some ideas on making these kinds of warning easier for the user to understand. We could use the labeling-of-source-ranges to print something like: demo.c: In function ‘test_2’: demo.c:6:23: warning: ‘%s’ directive writing 36 bytes into a region of size 11 [-Wformat-overflow=] 6 | sprintf (buf, "msg: %s\n", msg); | ~~~ ^~ | | | | | required space: 36 bytes | remaining capacity: 11 bytes demo.c:12:11: 12 | test_1 ("this is long enough to cause trouble"); | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ | | | required space: 36 bytes demo.c:6:3: note: ‘sprintf’ output 43 bytes into a destination of size 16 6 | sprintf (buf, "msg: %s\n", msg); | ~~~ ^~~~~~~~~ | | | | | required space: 43 bytes | size: 16 bytes (making a distinction between "size" and "remaining capacity", depending on whether the code is writing to the start of the buffer or not) Underlining "buf" requires access to its source location, which might not be available yet in the C frontend. A tweak to this would be to show the point where the overflow occurs (if the substring location code is up to it...): demo.c: In function ‘test_2’: demo.c:6:23: warning: ‘%s’ directive writing 36 bytes into a region of size 11 [-Wformat-overflow=] 6 | sprintf (buf, "msg: %s\n", msg); | ~~~ ^~ | | | | | required space: 36 bytes | remaining capacity: 11 bytes demo.c:12:11: 12 | test_1 ("this is long enough to cause trouble"); | ^~~~~~~~~~~~~~~~~~~~~~~~~ | | | overflow occurs here demo.c:6:3: note: ‘sprintf’ output 43 bytes into a destination of size 16 6 | sprintf (buf, "msg: %s\n", msg); | ~~~ ^~~~~~~~~ | | | | | required space: 43 bytes | size: 16 bytes Getting really fancy, we could emit an ASCII art visualization to (hopefully) make the buffer overflow crystal-clear (with an option to disable it): demo.c:6:3: note: buffer overflow [-fdiagnostics-show-buffer-overflow] snprintf of "%s" from: |+---+---+ ... +---+---+|+---+---+ ... +---+---+| || 0| 1| | 9| 10||| 11| 12| | 41| 42|| ||'t'|'h'| |'o'|'n'|||'g'|' '| |'e'|NUL|| |+---+---+ ... +---+---+|+---+---+ ... +---+---+| vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv |<--- ok --->|<-- overflow -->| | | | to 'buf': | | | ++---+---+---+---+---+|+---+---+ ... +---+---+| || 0| 1| 2| 3| 4||5 | 6| | 14| 15|| ||'m'|'s'|'g'|':'|' '|||'t'|'h'| |'o'|'n'|| ++---+---+---+---+---+|+---+---+ ... +---+---+| | | (thus showing the buffer content where it's known, eliding the middle when it goes above 5 elements) The parts on the right-hand side ("overflow" etc) could be colorized in red. Here's another version of the same UI idea, for the same diagnostic, which tries to show the string data (in the name of readability; I think this one is better than the above): demo.c:6:3: note: buffer overflow... snprintf of "%s" from: |+-------------+|+---------------------------++---+| || 0 - 10 ||| 11 - 41 || 42|| ||"this is lon"|||"g enough to cause trouble"||NUL|| |+-------------+|+---------------------------++---+| vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv |<--- ok --->|<-- overflow -->| | | | to 'buf': | | | ++-------+|+-------------+| || 0 - 4 ||| 5 - 15 || ||"msg: "|||"this is lon"|| ++-------+|+-------------+| Here's another possible visualization, of a different overflow: snprintf of "%s" from: |+---+ ... +---+|+---+ ... +---| || 0 | | n |||n+1| | 31| |+---+ ... +---+|+---+ ... +---| vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv |<--- ok --->|<--overflow-->| | | | to 'buf': | | | ++---+ ... +---+|+---+ ... +---+| || 0 | | x |||x+1| | 15|| ++---+ ... +---+|+---+ ... +---+| In this one, 32 bytes are being written into an unknown point ("x+1") within a buffer of size 16. A simple example where the overflowing write is to the start of the buffer: sprintf of an unbounded string to a fixed-size buf[100]: demo.c:6:3: note: buffer overflow... snprintf of "%s" from: |+------+|+--------------++-------+| ||0...99|||100...strlen-1|| strlen|| || ||| || NUL || |+------+|+--------------++-------+| vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv |<--ok-->|<-- overflow -->| | | | to 'buf': | | |+------+| ||0...99|| |+------+| Copying a string to a buffer allocated with strlen(), rather than strlen() + 1: | | | |+----------------+|+--------+| ||0...strlen() - 1|| NUL || |+----------------+|+--------+| vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv |<--- ok -->|<overflow>| | | | to 'buf': | | |+----------------+| ||0...strlen() - 1|| |+----------------+| Further random UI ideas (brainstormed in Emacs; I have no idea if these are *good* ideas): warning: buffer overflow: writing 9-110 bytes into a buffer with capacity 80 [-Wformat-overflow=] 7 | __builtin_sprintf (buf, "/%s/%s-%i.tmp", tmpdir, fname, num); | ~~~ ~~~^~~~~~~~~~ | | | | | writing 9...110 bytes | capacity: 80 bytes note: details 7 | __builtin_sprintf (buf, "/%s/%s-%i.tmp", tmpdir, fname, num); | ~~~ ab~cd~ef~g~~~h | | || || || | | | | || || || | 1 byte (NUL terminator) | | || || || 4 bytes (".tmp") | | || || |1...16 bytes ("%i" on 'num') | | || || 1 byte ("-") | | || |0-8 bytes ("%s" on 'fname') | | || 1 byte ("/") | | |0-79 bytes ("%s" on 'tmpdir') | | 1 byte ("/") | capacity: 80 bytes note: layout [-fsome-option-enabling-this] (with alternating colorization to better distinguish all those ranges and labels) |+---+--------------+----+-------------+-----+-----------+------+------+ start @||0 |1 |1-80|2-81 |10-89|11-90 |12-106|16-110| size:|| 1| 0 - 79 | 1| 8| 1| 1-16???| 4| 1| ||"/"|%s on 'tmpdir'| "/"|%s on 'fname'| "-" |%i on 'num'|".tmp"| NUL | |+---+--------------+----+-------------+-----+-----------+------+------+ or with a vertical orientation: note: layout [-fsome-option-enabling-this] +----------------+-----------+--------+---------------+ |element |starting at| size|cumulative size| +----------------+-----------+--------+---------------+ |"/" | 0 | 1 | 1 | |"%s" on 'tmpdir'| 1 | 0 - 79 | 1 - 80 | |"/" | 1 - 80 | 1 | 2 - 81 | |"%s" on 'fname' | 2 - 81 | 0 - 7 | 2 - 88 | |"-" | 2 - 88 | 1 | 3 - 89 | |"%i" on 'num' | 3 - 89 | 1- 16 | 4 - 105 | |".tmp" | 4 - 105 | 4 | 8 - 109 | |NUL terminator | 8 - 109 | 1 | 9 - 110 | +----------------+-----------+--------+---------------+ (I've probably got some of the numbers wrong above, but hopefully you get the idea of where I'm going with this). Maybe some kind of highlight to show where we can exceed the buffer capacity. I like calling out the NUL terminator explicitly (as it's so easy to get wrong), and putting "buffer overflow" upfront in the text of the warning, as I did above. [...snip...] Hope this is constructive Dave
On 10/5/20 11:28 AM, David Malcolm via Gcc-patches wrote: > On Mon, 2020-10-05 at 11:51 +0200, Aldy Hernandez via Gcc-patches > wrote: >> The walloca pass is a mess. It has all sorts of heuristics to >> divine >> problematic ranges fed into alloca, none of them very good, and all >> of >> them unreadable. The mess therein was actually one of the original >> motivators for the ranger project (along with array bounds checking). >> >> The attached patch is a conversion of the pass to ranger. It's >> mostly >> an exercise in removing code. The entire pass almost reduces to: >> >> + // If the user specified a limit, use it. >> + int_range_max r; >> + if (warn_limit_specified_p (is_vla) >> + && TREE_CODE (len) == SSA_NAME >> + && query.range_of_expr (r, len, stmt) >> + && !r.varying_p ()) >> + { >> + // The invalid bits are anything outside of [0, MAX_SIZE]. >> + static int_range<2> invalid_range (build_int_cst >> (size_type_node, 0), >> + build_int_cst >> (size_type_node, >> + max_size), >> + VR_ANTI_RANGE); >> + >> + r.intersect (invalid_range); >> + if (r.undefined_p ()) >> + return alloca_type_and_limit (ALLOCA_OK); >> + >> + return alloca_type_and_limit (ALLOCA_BOUND_MAYBE_LARGE, >> + wi::to_wide (integer_zero_node)); >> } >> >> That is, if the range of the integer passed to alloca is outside of >> [0,MAX_SIZE], warn, otherwise it's ok. Plain and simple. >> >> You will notice I removed the nuanced errors we gave before-- like >> trying to guess whether the problematic range came by virtue of a >> signed >> cast conversion. These specific errors were never part of the >> original >> design, they were just stuff we could guess by how the IL >> looked. It >> was non-exact and fragile. Now we just say the alloca argument may >> be >> too large, period. >> >> It the future, I would even like to remove the specific range the >> ranger >> was able to compute from the error message itself. As will become >> obvious, the ranger can get pretty outrageous ranges that are >> entirely >> non-obvious by looking at the code. Peppering the error messages >> with >> these ranges will ultimately just confuse the user. But alas, that's >> a >> problem for another patch to solve. > I can't comment on the content of the patch itself, but with my "user > experience hat" on I'm wondering what diagnostic messages involving > ranges ought to look like. I worry that if we simply drop range > information altogether from the messages, we're not giving the user > enough information to make a judgment call on whether to pay attention > to the diagnostic. That said, I'm unhappy with the status quo of our > range-based messages, so I don't object to the patch. I also dont know what the right answer is regarding dumping of ranges. Most of the time I suspect the error only needs the end points, not the fun stuff in the middle if its a multi-range... but I suppose thats up to the actual issuer of the message to decide if thats important. > > Some possible ideas: > > I added support for capturing and printing control-flow paths for > diagnostics in gcc 10; see gcc/diagnostic-path.h. I added this for the > analyzer code, but it's usable outside of it. It's possible to use > this to associate a chain of events with a diagnostic, by building a > diagnostic_path and associating it with a rich_location. Perhaps the > ranger code could have a mode which captures diagnostic_paths, where > the events in the path give pertinent information about ranges - e.g. > the various conditionals that lead to a particular range. There's a > pre-canned simple_diagnostic_path that can be populated with > simple_diagnostic_event, or you could create your own ranger-specific > event and path subclasses. These can be temporary objects that live on > the stack next to the rich_location, just for the lifetime of emitting > the diagnostic. Perhaps a "class ranger_rich_location" which > implicitly supplies an instance of "class ranger_diagnostic_path" to > the diagnostic, describing where the range information comes from? For debugging I have a trace, but it doesnt log the trace. just sort of logs as it does the walk backwards to determine things. I use it to figure out where things have gone amok. THis sort of thing would probably be best tackled by simply inheriting from a ranger and overloading the core routines to log them.. thats effectively what the tracer does. just emits info before and after each of the core 5 calls. I suppose one could just as easily log the info that comes back, and with a little bit of extra understanding, determine whether this is a "new" value or a previously computed one and automatically do what I am doing manually when determining the origination of something. > > Here are some more out-there ideas I had some years ago (I can't > remember if these ever made it to the mailing list). These ideas focus > more on how the ranges are used, rather than where the ranges come > from. There's an interaction, though, so I think it's on-topic - can > the ranger code supply this kind of information? > > what kind of information are we talking about? if you are talking about where the ranges came from, im sure one could collect that together in a derived class. The ranger itself is really just cobbling together the various sources of information that are calculated by its components. Its really just an organizer and bookkeeper. You could probably cobble together whatever bits of information you wanted to stash them together. Andrew
On 10/5/20 3:51 AM, Aldy Hernandez via Gcc-patches wrote: > The walloca pass is a mess. It has all sorts of heuristics to divine > problematic ranges fed into alloca, none of them very good, and all of > them unreadable. The mess therein was actually one of the original > motivators for the ranger project (along with array bounds checking). > > The attached patch is a conversion of the pass to ranger. It's mostly > an exercise in removing code. The entire pass almost reduces to: > > + // If the user specified a limit, use it. > + int_range_max r; > + if (warn_limit_specified_p (is_vla) > + && TREE_CODE (len) == SSA_NAME > + && query.range_of_expr (r, len, stmt) > + && !r.varying_p ()) > + { > + // The invalid bits are anything outside of [0, MAX_SIZE]. > + static int_range<2> invalid_range (build_int_cst (size_type_node, > 0), > + build_int_cst (size_type_node, > + max_size), > + VR_ANTI_RANGE); > + > + r.intersect (invalid_range); > + if (r.undefined_p ()) > + return alloca_type_and_limit (ALLOCA_OK); > + > + return alloca_type_and_limit (ALLOCA_BOUND_MAYBE_LARGE, > + wi::to_wide (integer_zero_node)); > } > > That is, if the range of the integer passed to alloca is outside of > [0,MAX_SIZE], warn, otherwise it's ok. Plain and simple. It looks like a nice simplification to me! You're the author of the alloca pass so I have no concerns with the changes (but I appreciate the heads up). That said, I do want to respond to your commentary and add a few notes of my own. Eventually, I'd like all the -Wfoo-larger-than= warnings to use the same "core logic" when deciding whether to warn or not. As it is, they're not completely consistent with each other and some warn when others don't and vice versa. For instance: $ cat z.c && gcc -O2 -S -Wall -Walloca-larger-than=1000 -Walloc-size-larger-than=1000 z.c void f0 (void*); void f1 (int n) { f0 (__builtin_alloca (n * sizeof (int))); // warning } void f2 (int n) { f0 (__builtin_malloc (n * sizeof (int))); // silence } z.c: In function ‘f1’: z.c:5:3: warning: argument to ‘alloca’ may be too large [-Walloca-larger-than=] 5 | f0 (__builtin_alloca (n * sizeof (int))); // warning | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ z.c:5:3: note: limit is 1000 bytes, but argument may be as large as 18446744073709551612 That's because -Walloca-larger-than= (and -Wvla-larger-than=) is designed to warn when it can't prove that the argument isn't too large, while the others use the conventional approach of warning only when they can prove that the argument is excessive. On the other hand, without -Walloca-larger-than=, for the example below GCC issues -Walloc-size-larger-than= but not the former, even though the alloca call is more likely to cause serious trouble than the one to malloc. $ cat z.c && gcc -O2 -S -Wall z.c void f0 (void*); void f1 (int n) { if (n >= 0) n = -1; f0 (__builtin_alloca (n * sizeof (int))); } void f2 (int n) { if (n >= 0) n = -1; f0 (__builtin_malloc (n * sizeof (int))); } z.c: In function ‘f2’: z.c:12:3: warning: argument 1 range [18446744065119617024, 18446744073709551612] exceeds maximum object size 9223372036854775807 [-Walloc-size-larger-than=] 12 | f0 (__builtin_malloc (n * sizeof (int))); | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ z.c:12:3: note: in a call to built-in allocation function ‘__builtin_malloc’ (This seems like a bug/missing feature in -Walloca-larger-than=.) > You will notice I removed the nuanced errors we gave before-- like > trying to guess whether the problematic range came by virtue of a signed > cast conversion. These specific errors were never part of the original > design, they were just stuff we could guess by how the IL looked. It > was non-exact and fragile. Now we just say the alloca argument may be > too large, period. That makes sense to me, as long as the note following the warning still mentions the limit in effect and the range (or at least the bound in excess of the limit). > > It the future, I would even like to remove the specific range the ranger > was able to compute from the error message itself. As will become > obvious, the ranger can get pretty outrageous ranges that are entirely > non-obvious by looking at the code. Peppering the error messages with > these ranges will ultimately just confuse the user. But alas, that's a > problem for another patch to solve. I agree that when it comes to sizes where just one bound of the range is used to decide whether or not to warn (the lower bound in the case of most warnings but, as the example above shows, the upper bound for -Walloca-larger-than=), printing multiple subranges is unnecessary and could easily be confusing. Even printing the very large bounds (in decimal) in the warning above may be too much. At the same time, simply printing: warning: argument to ‘alloca’ may be too large and nothing else wouldn't be helpful either. (Though it would make the alloca pass real simple ;-) It's a matter of deciding what the right amount of detail is in each instance and choosing the best representation for the values included in it (small values are okay in decimal, larger values may be better formatted in hex, or involving well-known symbolic constants like INT_MAX or PTRDIFF_MAX). But different people have different ideas about how much detail is enough and what presentation is best. Rather than each of us imposing our individual preference on all users and ending up with arbitrary inconsistencies between warnings we should design them so that their output can be customized. If I like to see the full ranges in warnings in decimal I should be able to ask GCC to do that. If I just care about the high level details (say just the more important bound) and prefer hex for large numbers there should be a way to do that too. It's just a matter of adding a %R or some such to the pretty-printer to format a range and exposing an option that will let users choose the format. (It still leaves room for us to argue about the defaults ;) Martin > > This patch goes on top of the ranger which Andrew just posted. It's > likely to be adjusted as the ranger is committed. > > gcc/ChangeLog: > > * gimple-ssa-warn-alloca.c (enum alloca_type): Remove > ALLOCA_BOUND_UNKNOWN and ALLOCA_CAST_FROM_SIGNED. > (warn_limit_specified_p): New. > (alloca_call_type_by_arg): Remove. > (cast_from_signed_p): Remove. > (is_max): Remove. > (alloca_call_type): Remove heuristics and replace with call > into > ranger. > (pass_walloca::execute): Instantiate ranger. > > gcc/testsuite/ChangeLog: > > * gcc.dg/Walloca-1.c: Adjust for ranger. > * gcc.dg/Walloca-12.c: Same. > * gcc.dg/Walloca-13.c: Same. > * gcc.dg/Walloca-2.c: Same. > * gcc.dg/Walloca-3.c: Same. > * gcc.dg/Walloca-6.c: Same. > > diff --git a/gcc/gimple-ssa-warn-alloca.c b/gcc/gimple-ssa-warn-alloca.c > index 9e80e5dbbd9..33824a7a091 100644 > --- a/gcc/gimple-ssa-warn-alloca.c > +++ b/gcc/gimple-ssa-warn-alloca.c > @@ -36,6 +36,7 @@ along with GCC; see the file COPYING3. If not see > #include "calls.h" > #include "cfgloop.h" > #include "intl.h" > +#include "gimple-range.h" > > static unsigned HOST_WIDE_INT adjusted_warn_limit (bool); > > @@ -99,12 +100,6 @@ enum alloca_type { > // Alloca argument may be too large. > ALLOCA_BOUND_MAYBE_LARGE, > > - // Alloca argument is bounded but of an indeterminate size. > - ALLOCA_BOUND_UNKNOWN, > - > - // Alloca argument was casted from a signed integer. > - ALLOCA_CAST_FROM_SIGNED, > - > // Alloca appears in a loop. > ALLOCA_IN_LOOP, > > @@ -135,6 +130,15 @@ public: > } > }; > > +/* Return TRUE if the user specified a limit for either VLAs or > ALLOCAs. */ > + > +static bool > +warn_limit_specified_p (bool is_vla) > +{ > + unsigned HOST_WIDE_INT max = is_vla ? warn_vla_limit : > warn_alloca_limit; > + return max != HOST_WIDE_INT_MAX; > +} > + > /* Return the value of the argument N to -Walloca-larger-than= or > -Wvla-larger-than= adjusted for the target data model so that > when N == HOST_WIDE_INT_MAX, the adjusted value is set to > @@ -158,183 +162,15 @@ adjusted_warn_limit (bool idx) > return limits[idx]; > } > > - > -// NOTE: When we get better range info, this entire function becomes > -// irrelevant, as it should be possible to get range info for an SSA > -// name at any point in the program. > -// > -// We have a few heuristics up our sleeve to determine if a call to > -// alloca() is within bounds. Try them out and return the type of > -// alloca call with its assumed limit (if applicable). > -// > -// Given a known argument (ARG) to alloca() and an EDGE (E) > -// calculating said argument, verify that the last statement in the BB > -// in E->SRC is a gate comparing ARG to an acceptable bound for > -// alloca(). See examples below. > -// > -// If set, ARG_CASTED is the possible unsigned argument to which ARG > -// was casted to. This is to handle cases where the controlling > -// predicate is looking at a casted value, not the argument itself. > -// arg_casted = (size_t) arg; > -// if (arg_casted < N) > -// goto bb3; > -// else > -// goto bb5; > -// > -// MAX_SIZE is WARN_ALLOCA= adjusted for VLAs. It is the maximum size > -// in bytes we allow for arg. > - > -static class alloca_type_and_limit > -alloca_call_type_by_arg (tree arg, tree arg_casted, edge e, > - unsigned HOST_WIDE_INT max_size) > -{ > - basic_block bb = e->src; > - gimple_stmt_iterator gsi = gsi_last_bb (bb); > - gimple *last = gsi_stmt (gsi); > - > - const offset_int maxobjsize = tree_to_shwi (max_object_size ()); > - > - /* When MAX_SIZE is greater than or equal to PTRDIFF_MAX treat > - allocations that aren't visibly constrained as OK, otherwise > - report them as (potentially) unbounded. */ > - alloca_type unbounded_result = (max_size < maxobjsize.to_uhwi () > - ? ALLOCA_UNBOUNDED : ALLOCA_OK); > - > - if (!last || gimple_code (last) != GIMPLE_COND) > - { > - return alloca_type_and_limit (unbounded_result); > - } > - > - enum tree_code cond_code = gimple_cond_code (last); > - if (e->flags & EDGE_TRUE_VALUE) > - ; > - else if (e->flags & EDGE_FALSE_VALUE) > - cond_code = invert_tree_comparison (cond_code, false); > - else > - return alloca_type_and_limit (unbounded_result); > - > - // Check for: > - // if (ARG .COND. N) > - // goto <bb 3>; > - // else > - // goto <bb 4>; > - // <bb 3>: > - // alloca(ARG); > - if ((cond_code == LE_EXPR > - || cond_code == LT_EXPR > - || cond_code == GT_EXPR > - || cond_code == GE_EXPR) > - && (gimple_cond_lhs (last) == arg > - || gimple_cond_lhs (last) == arg_casted)) > - { > - if (TREE_CODE (gimple_cond_rhs (last)) == INTEGER_CST) > - { > - tree rhs = gimple_cond_rhs (last); > - int tst = wi::cmpu (wi::to_widest (rhs), max_size); > - if ((cond_code == LT_EXPR && tst == -1) > - || (cond_code == LE_EXPR && (tst == -1 || tst == 0))) > - return alloca_type_and_limit (ALLOCA_OK); > - else > - { > - // Let's not get too specific as to how large the limit > - // may be. Someone's clearly an idiot when things > - // degrade into "if (N > Y) alloca(N)". > - if (cond_code == GT_EXPR || cond_code == GE_EXPR) > - rhs = integer_zero_node; > - return alloca_type_and_limit (ALLOCA_BOUND_MAYBE_LARGE, > - wi::to_wide (rhs)); > - } > - } > - else > - { > - /* Analogous to ALLOCA_UNBOUNDED, when MAX_SIZE is greater > - than or equal to PTRDIFF_MAX, treat allocations with > - an unknown bound as OK. */ > - alloca_type unknown_result > - = (max_size < maxobjsize.to_uhwi () > - ? ALLOCA_BOUND_UNKNOWN : ALLOCA_OK); > - return alloca_type_and_limit (unknown_result); > - } > - } > - > - // Similarly, but check for a comparison with an unknown LIMIT. > - // if (LIMIT .COND. ARG) > - // alloca(arg); > - // > - // Where LIMIT has a bound of unknown range. > - // > - // Note: All conditions of the form (ARG .COND. XXXX) where covered > - // by the previous check above, so we only need to look for (LIMIT > - // .COND. ARG) here. > - tree limit = gimple_cond_lhs (last); > - if ((gimple_cond_rhs (last) == arg > - || gimple_cond_rhs (last) == arg_casted) > - && TREE_CODE (limit) == SSA_NAME) > - { > - wide_int min, max; > - value_range_kind range_type = get_range_info (limit, &min, &max); > - > - if (range_type == VR_UNDEFINED || range_type == VR_VARYING) > - return alloca_type_and_limit (ALLOCA_BOUND_UNKNOWN); > - > - // ?? It looks like the above `if' is unnecessary, as we never > - // get any VR_RANGE or VR_ANTI_RANGE here. If we had a range > - // for LIMIT, I suppose we would have taken care of it in > - // alloca_call_type(), or handled above where we handle (ARG > .COND. N). > - // > - // If this ever triggers, we should probably figure out why and > - // handle it, though it is likely to be just an ALLOCA_UNBOUNDED. > - return alloca_type_and_limit (unbounded_result); > - } > - > - return alloca_type_and_limit (unbounded_result); > -} > - > -// Return TRUE if SSA's definition is a cast from a signed type. > -// If so, set *INVALID_CASTED_TYPE to the signed type. > - > -static bool > -cast_from_signed_p (tree ssa, tree *invalid_casted_type) > -{ > - gimple *def = SSA_NAME_DEF_STMT (ssa); > - if (def > - && !gimple_nop_p (def) > - && gimple_assign_cast_p (def) > - && !TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (def)))) > - { > - *invalid_casted_type = TREE_TYPE (gimple_assign_rhs1 (def)); > - return true; > - } > - return false; > -} > - > -// Return TRUE if X has a maximum range of MAX, basically covering the > -// entire domain, in which case it's no range at all. > - > -static bool > -is_max (tree x, wide_int max) > -{ > - return wi::max_value (TREE_TYPE (x)) == max; > -} > - > // Analyze the alloca call in STMT and return the alloca type with its > // corresponding limit (if applicable). IS_VLA is set if the alloca > // call was created by the gimplifier for a VLA. > -// > -// If the alloca call may be too large because of a cast from a signed > -// type to an unsigned type, set *INVALID_CASTED_TYPE to the > -// problematic signed type. > > static class alloca_type_and_limit > -alloca_call_type (gimple *stmt, bool is_vla, tree *invalid_casted_type) > +alloca_call_type (range_query &query, gimple *stmt, bool is_vla) > { > gcc_assert (gimple_alloca_call_p (stmt)); > - bool tentative_cast_from_signed = false; > tree len = gimple_call_arg (stmt, 0); > - tree len_casted = NULL; > - wide_int min, max; > - edge_iterator ei; > - edge e; > > gcc_assert (!is_vla || warn_vla_limit >= 0); > gcc_assert (is_vla || warn_alloca_limit >= 0); > @@ -361,118 +197,9 @@ alloca_call_type (gimple *stmt, bool is_vla, tree > *invalid_casted_type) > return alloca_type_and_limit (ALLOCA_OK); > } > > - // Check the range info if available. > - if (TREE_CODE (len) == SSA_NAME) > - { > - value_range_kind range_type = get_range_info (len, &min, &max); > - if (range_type == VR_RANGE) > - { > - if (wi::leu_p (max, max_size)) > - return alloca_type_and_limit (ALLOCA_OK); > - else > - { > - // A cast may have created a range we don't care > - // about. For instance, a cast from 16-bit to > - // 32-bit creates a range of 0..65535, even if there > - // is not really a determinable range in the > - // underlying code. In this case, look through the > - // cast at the original argument, and fall through > - // to look at other alternatives. > - // > - // We only look at through the cast when its from > - // unsigned to unsigned, otherwise we may risk > - // looking at SIGNED_INT < N, which is clearly not > - // what we want. In this case, we'd be interested > - // in a VR_RANGE of [0..N]. > - // > - // Note: None of this is perfect, and should all go > - // away with better range information. But it gets > - // most of the cases. > - gimple *def = SSA_NAME_DEF_STMT (len); > - if (gimple_assign_cast_p (def)) > - { > - tree rhs1 = gimple_assign_rhs1 (def); > - tree rhs1type = TREE_TYPE (rhs1); > - > - // Bail if the argument type is not valid. > - if (!INTEGRAL_TYPE_P (rhs1type)) > - return alloca_type_and_limit (ALLOCA_OK); > - > - if (TYPE_UNSIGNED (rhs1type)) > - { > - len_casted = rhs1; > - range_type = get_range_info (len_casted, &min, &max); > - } > - } > - // An unknown range or a range of the entire domain is > - // really no range at all. > - if (range_type == VR_VARYING > - || (!len_casted && is_max (len, max)) > - || (len_casted && is_max (len_casted, max))) > - { > - // Fall through. > - } > - else if (range_type == VR_ANTI_RANGE) > - return alloca_type_and_limit (ALLOCA_UNBOUNDED); > - > - if (range_type != VR_VARYING) > - { > - const offset_int maxobjsize > - = wi::to_offset (max_object_size ()); > - alloca_type result = (max_size < maxobjsize > - ? ALLOCA_BOUND_MAYBE_LARGE : ALLOCA_OK); > - return alloca_type_and_limit (result, max); > - } > - } > - } > - else if (range_type == VR_ANTI_RANGE) > - { > - // There may be some wrapping around going on. Catch it > - // with this heuristic. Hopefully, this VR_ANTI_RANGE > - // nonsense will go away, and we won't have to catch the > - // sign conversion problems with this crap. > - // > - // This is here to catch things like: > - // void foo(signed int n) { > - // if (n < 100) > - // alloca(n); > - // ... > - // } > - if (cast_from_signed_p (len, invalid_casted_type)) > - { > - // Unfortunately this also triggers: > - // > - // __SIZE_TYPE__ n = (__SIZE_TYPE__)blah; > - // if (n < 100) > - // alloca(n); > - // > - // ...which is clearly bounded. So, double check that > - // the paths leading up to the size definitely don't > - // have a bound. > - tentative_cast_from_signed = true; > - } > - } > - // No easily determined range and try other things. > - } > - > - // If we couldn't find anything, try a few heuristics for things we > - // can easily determine. Check these misc cases but only accept > - // them if all predecessors have a known bound. > - class alloca_type_and_limit ret = alloca_type_and_limit (ALLOCA_OK); > - FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->preds) > - { > - gcc_assert (!len_casted || TYPE_UNSIGNED (TREE_TYPE (len_casted))); > - ret = alloca_call_type_by_arg (len, len_casted, e, max_size); > - if (ret.type != ALLOCA_OK) > - break; > - } > - > - if (ret.type != ALLOCA_OK && tentative_cast_from_signed) > - ret = alloca_type_and_limit (ALLOCA_CAST_FROM_SIGNED); > - > + struct alloca_type_and_limit ret = alloca_type_and_limit (ALLOCA_OK); > // If we have a declared maximum size, we can take it into account. > - if (ret.type != ALLOCA_OK > - && gimple_call_builtin_p (stmt, BUILT_IN_ALLOCA_WITH_ALIGN_AND_MAX)) > + if (gimple_call_builtin_p (stmt, BUILT_IN_ALLOCA_WITH_ALIGN_AND_MAX)) > { > tree arg = gimple_call_arg (stmt, 2); > if (compare_tree_int (arg, max_size) <= 0) > @@ -485,9 +212,37 @@ alloca_call_type (gimple *stmt, bool is_vla, tree > *invalid_casted_type) > ? ALLOCA_BOUND_MAYBE_LARGE : ALLOCA_OK); > ret = alloca_type_and_limit (result, wi::to_wide (arg)); > } > + return ret; > + } > + > + // If the user specified a limit, use it. > + int_range_max r; > + if (warn_limit_specified_p (is_vla) > + && TREE_CODE (len) == SSA_NAME > + && query.range_of_expr (r, len, stmt) > + && !r.varying_p ()) > + { > + // The invalid bits are anything outside of [0, MAX_SIZE]. > + static int_range<2> invalid_range (build_int_cst (size_type_node, > 0), > + build_int_cst (size_type_node, > + max_size), > + VR_ANTI_RANGE); > + > + r.intersect (invalid_range); > + if (r.undefined_p ()) > + return alloca_type_and_limit (ALLOCA_OK); > + > + return alloca_type_and_limit (ALLOCA_BOUND_MAYBE_LARGE, > + wi::to_wide (integer_zero_node)); > } > > - return ret; > + const offset_int maxobjsize = tree_to_shwi (max_object_size ()); > + /* When MAX_SIZE is greater than or equal to PTRDIFF_MAX treat > + allocations that aren't visibly constrained as OK, otherwise > + report them as (potentially) unbounded. */ > + alloca_type unbounded_result = (max_size < maxobjsize.to_uhwi () > + ? ALLOCA_UNBOUNDED : ALLOCA_OK); > + return alloca_type_and_limit (unbounded_result); > } > > // Return TRUE if STMT is in a loop, otherwise return FALSE. > @@ -503,6 +258,7 @@ in_loop_p (gimple *stmt) > unsigned int > pass_walloca::execute (function *fun) > { > + gimple_ranger ranger; > basic_block bb; > FOR_EACH_BB_FN (bb, fun) > { > @@ -535,9 +291,8 @@ pass_walloca::execute (function *fun) > else if (warn_alloca_limit < 0) > continue; > > - tree invalid_casted_type = NULL; > class alloca_type_and_limit t > - = alloca_call_type (stmt, is_vla, &invalid_casted_type); > + = alloca_call_type (ranger, stmt, is_vla); > > unsigned HOST_WIDE_INT adjusted_alloca_limit > = adjusted_warn_limit (false); > @@ -599,13 +354,6 @@ pass_walloca::execute (function *fun) > } > } > break; > - case ALLOCA_BOUND_UNKNOWN: > - warning_at (loc, wcode, > - (is_vla > - ? G_("%Gvariable-length array bound is unknown") > - : G_("%G%<alloca%> bound is unknown")), > - stmt); > - break; > case ALLOCA_UNBOUNDED: > warning_at (loc, wcode, > (is_vla > @@ -618,17 +366,6 @@ pass_walloca::execute (function *fun) > warning_at (loc, wcode, > "%Guse of %<alloca%> within a loop", stmt); > break; > - case ALLOCA_CAST_FROM_SIGNED: > - gcc_assert (invalid_casted_type != NULL_TREE); > - warning_at (loc, wcode, > - (is_vla > - ? G_("%Gargument to variable-length array " > - "may be too large due to " > - "conversion from %qT to %qT") > - : G_("%Gargument to %<alloca%> may be too large " > - "due to conversion from %qT to %qT")), > - stmt, invalid_casted_type, size_type_node); > - break; > case ALLOCA_ARG_IS_ZERO: > warning_at (loc, wcode, > (is_vla > diff --git a/gcc/testsuite/gcc.dg/Walloca-1.c > b/gcc/testsuite/gcc.dg/Walloca-1.c > index 85e9160e845..ed1fa929398 100644 > --- a/gcc/testsuite/gcc.dg/Walloca-1.c > +++ b/gcc/testsuite/gcc.dg/Walloca-1.c > @@ -24,8 +24,7 @@ void foo1 (size_t len, size_t len2, size_t len3) > char *s = alloca (123); > useit (s); // OK, constant argument to alloca > > - s = alloca (num); // { dg-warning "large due to conversion" "" > { target lp64 } } > - // { dg-warning "unbounded use of 'alloca'" "" { target { ! lp64 } } > .-1 } > + s = alloca (num); // { dg-warning "may be too large" } > useit (s); > > s = alloca (30000); /* { dg-warning "is too large" } */ > diff --git a/gcc/testsuite/gcc.dg/Walloca-12.c > b/gcc/testsuite/gcc.dg/Walloca-12.c > index 059c5f32129..d2d9413ab1e 100644 > --- a/gcc/testsuite/gcc.dg/Walloca-12.c > +++ b/gcc/testsuite/gcc.dg/Walloca-12.c > @@ -8,5 +8,5 @@ void g (unsigned int n) > { > if (n == 7) > n = 11; > - f (__builtin_alloca (n)); /* { dg-warning "unbounded use of 'alloca'" > } */ > + f (__builtin_alloca (n)); /* { dg-warning "may be too large" } */ > } > diff --git a/gcc/testsuite/gcc.dg/Walloca-13.c > b/gcc/testsuite/gcc.dg/Walloca-13.c > index 12e9f6c9281..99d62065e26 100644 > --- a/gcc/testsuite/gcc.dg/Walloca-13.c > +++ b/gcc/testsuite/gcc.dg/Walloca-13.c > @@ -8,5 +8,5 @@ void g (int *p, int *q) > { > __SIZE_TYPE__ n = (__SIZE_TYPE__)(p - q); > if (n < 100) > - f (__builtin_alloca (n)); // { dg-bogus "may be too large due to > conversion" "" { xfail { *-*-* } } } > + f (__builtin_alloca (n)); // { dg-bogus "may be too large" "" { > xfail { *-*-* } } } > } > diff --git a/gcc/testsuite/gcc.dg/Walloca-2.c > b/gcc/testsuite/gcc.dg/Walloca-2.c > index 766ff8d8af3..1cf9165c59f 100644 > --- a/gcc/testsuite/gcc.dg/Walloca-2.c > +++ b/gcc/testsuite/gcc.dg/Walloca-2.c > @@ -24,7 +24,7 @@ g2 (int n) > { > void *p; > if (n < 2000) > - p = __builtin_alloca (n); // { dg-warning "large due to conversion" } > + p = __builtin_alloca (n); // { dg-warning "may be too large" } > else > p = __builtin_malloc (n); > f (p); > @@ -36,9 +36,7 @@ g3 (int n) > void *p; > if (n > 0 && n < 3000) > { > - p = __builtin_alloca (n); // { dg-warning "'alloca' may be too > large" "" { target lp64} } > - // { dg-message "note:.*argument may be as large as 2999" "note" > { target lp64 } .-1 } > - // { dg-warning "unbounded use of 'alloca'" "" { target { ! lp64 > } } .-2 } > + p = __builtin_alloca (n); // { dg-warning "may be too large" } > } > else > p = __builtin_malloc (n); > diff --git a/gcc/testsuite/gcc.dg/Walloca-3.c > b/gcc/testsuite/gcc.dg/Walloca-3.c > index f5840673da0..b8000ff1249 100644 > --- a/gcc/testsuite/gcc.dg/Walloca-3.c > +++ b/gcc/testsuite/gcc.dg/Walloca-3.c > @@ -13,7 +13,7 @@ g1 (__SIZE_TYPE__ n) > { > void *p; > if (n < LIMIT) > - p = __builtin_alloca (n); // { dg-warning "'alloca' bound is > unknown" } > + p = __builtin_alloca (n); // { dg-warning "may be too large" } > else > p = __builtin_malloc (n); > f (p); > @@ -27,7 +27,7 @@ g2 (unsigned short n) > { > void *p; > if (n < SHORT_LIMIT) > - p = __builtin_alloca (n); // { dg-warning "'alloca' bound is > unknown" } > + p = __builtin_alloca (n); // { dg-warning "may be too large" } > else > p = __builtin_malloc (n); > f (p); > diff --git a/gcc/testsuite/gcc.dg/Walloca-6.c > b/gcc/testsuite/gcc.dg/Walloca-6.c > index 16b5d6f729d..ebe08aec838 100644 > --- a/gcc/testsuite/gcc.dg/Walloca-6.c > +++ b/gcc/testsuite/gcc.dg/Walloca-6.c > @@ -1,7 +1,6 @@ > /* { dg-do compile } */ > /* { dg-require-effective-target alloca } */ > /* { dg-options "-Walloca-larger-than=256 -O2" } */ > -/* { dg-xfail-if "Currently broken but Andrew's work should fix this" { > *-*-* } } */ > > void f (void*); > void g (__SIZE_TYPE__ n) >
On 10/5/20 7:12 PM, Martin Sebor wrote: >> It the future, I would even like to remove the specific range the >> ranger was able to compute from the error message itself. As will >> become obvious, the ranger can get pretty outrageous ranges that are >> entirely non-obvious by looking at the code. Peppering the error >> messages with these ranges will ultimately just confuse the user. But >> alas, that's a problem for another patch to solve. > > I agree that when it comes to sizes where just one bound of the range > is used to decide whether or not to warn (the lower bound in the case > of most warnings but, as the example above shows, the upper bound for > -Walloca-larger-than=), printing multiple subranges is unnecessary > and could easily be confusing. Even printing the very large bounds > (in decimal) in the warning above may be too much. At the same time, > simply printing: > > warning: argument to ‘alloca’ may be too large > > and nothing else wouldn't be helpful either. (Though it would make > the alloca pass real simple ;-) It's a matter of deciding what > the right amount of detail is in each instance and choosing the best > representation for the values included in it (small values are okay > in decimal, larger values may be better formatted in hex, or involving > well-known symbolic constants like INT_MAX or PTRDIFF_MAX). But > different people have different ideas about how much detail is enough > and what presentation is best. Rather than each of us imposing our > individual preference on all users and ending up with arbitrary > inconsistencies between warnings we should design them so that their > output can be customized. If I like to see the full ranges in warnings > in decimal I should be able to ask GCC to do that. If I just care about > the high level details (say just the more important bound) and prefer > hex for large numbers there should be a way to do that too. It's just > a matter of adding a %R or some such to the pretty-printer to format > a range and exposing an option that will let users choose the format. > (It still leaves room for us to argue about the defaults ;) Sure, some general shared infrastructure for reporting errors involving ranges would be nice, inasmuch as the testcases do not test for specific ranges since those are liable to change from release to release. Aldy
diff --git a/gcc/gimple-ssa-warn-alloca.c b/gcc/gimple-ssa-warn-alloca.c index 9e80e5dbbd9..33824a7a091 100644 --- a/gcc/gimple-ssa-warn-alloca.c +++ b/gcc/gimple-ssa-warn-alloca.c @@ -36,6 +36,7 @@ along with GCC; see the file COPYING3. If not see #include "calls.h" #include "cfgloop.h" #include "intl.h" +#include "gimple-range.h" static unsigned HOST_WIDE_INT adjusted_warn_limit (bool); @@ -99,12 +100,6 @@ enum alloca_type { // Alloca argument may be too large. ALLOCA_BOUND_MAYBE_LARGE, - // Alloca argument is bounded but of an indeterminate size. - ALLOCA_BOUND_UNKNOWN, - - // Alloca argument was casted from a signed integer. - ALLOCA_CAST_FROM_SIGNED, - // Alloca appears in a loop. ALLOCA_IN_LOOP, @@ -135,6 +130,15 @@ public: } }; +/* Return TRUE if the user specified a limit for either VLAs or ALLOCAs. */ + +static bool +warn_limit_specified_p (bool is_vla) +{ + unsigned HOST_WIDE_INT max = is_vla ? warn_vla_limit : warn_alloca_limit; + return max != HOST_WIDE_INT_MAX; +} + /* Return the value of the argument N to -Walloca-larger-than= or -Wvla-larger-than= adjusted for the target data model so that when N == HOST_WIDE_INT_MAX, the adjusted value is set to @@ -158,183 +162,15 @@ adjusted_warn_limit (bool idx) return limits[idx]; } - -// NOTE: When we get better range info, this entire function becomes -// irrelevant, as it should be possible to get range info for an SSA -// name at any point in the program. -// -// We have a few heuristics up our sleeve to determine if a call to -// alloca() is within bounds. Try them out and return the type of -// alloca call with its assumed limit (if applicable). -// -// Given a known argument (ARG) to alloca() and an EDGE (E) -// calculating said argument, verify that the last statement in the BB -// in E->SRC is a gate comparing ARG to an acceptable bound for -// alloca(). See examples below. -// -// If set, ARG_CASTED is the possible unsigned argument to which ARG -// was casted to. This is to handle cases where the controlling -// predicate is looking at a casted value, not the argument itself. -// arg_casted = (size_t) arg; -// if (arg_casted < N) -// goto bb3; -// else -// goto bb5; -// -// MAX_SIZE is WARN_ALLOCA= adjusted for VLAs. It is the maximum size -// in bytes we allow for arg. - -static class alloca_type_and_limit -alloca_call_type_by_arg (tree arg, tree arg_casted, edge e, - unsigned HOST_WIDE_INT max_size) -{ - basic_block bb = e->src; - gimple_stmt_iterator gsi = gsi_last_bb (bb); - gimple *last = gsi_stmt (gsi); - - const offset_int maxobjsize = tree_to_shwi (max_object_size ()); - - /* When MAX_SIZE is greater than or equal to PTRDIFF_MAX treat - allocations that aren't visibly constrained as OK, otherwise - report them as (potentially) unbounded. */ - alloca_type unbounded_result = (max_size < maxobjsize.to_uhwi () - ? ALLOCA_UNBOUNDED : ALLOCA_OK); - - if (!last || gimple_code (last) != GIMPLE_COND) - { - return alloca_type_and_limit (unbounded_result); - } - - enum tree_code cond_code = gimple_cond_code (last); - if (e->flags & EDGE_TRUE_VALUE) - ; - else if (e->flags & EDGE_FALSE_VALUE) - cond_code = invert_tree_comparison (cond_code, false); - else - return alloca_type_and_limit (unbounded_result); - - // Check for: - // if (ARG .COND. N) - // goto <bb 3>; - // else - // goto <bb 4>; - // <bb 3>: - // alloca(ARG); - if ((cond_code == LE_EXPR - || cond_code == LT_EXPR - || cond_code == GT_EXPR - || cond_code == GE_EXPR) - && (gimple_cond_lhs (last) == arg - || gimple_cond_lhs (last) == arg_casted)) - { - if (TREE_CODE (gimple_cond_rhs (last)) == INTEGER_CST) - { - tree rhs = gimple_cond_rhs (last); - int tst = wi::cmpu (wi::to_widest (rhs), max_size); - if ((cond_code == LT_EXPR && tst == -1) - || (cond_code == LE_EXPR && (tst == -1 || tst == 0))) - return alloca_type_and_limit (ALLOCA_OK); - else - { - // Let's not get too specific as to how large the limit - // may be. Someone's clearly an idiot when things - // degrade into "if (N > Y) alloca(N)". - if (cond_code == GT_EXPR || cond_code == GE_EXPR) - rhs = integer_zero_node; - return alloca_type_and_limit (ALLOCA_BOUND_MAYBE_LARGE, - wi::to_wide (rhs)); - } - } - else - { - /* Analogous to ALLOCA_UNBOUNDED, when MAX_SIZE is greater - than or equal to PTRDIFF_MAX, treat allocations with - an unknown bound as OK. */ - alloca_type unknown_result - = (max_size < maxobjsize.to_uhwi () - ? ALLOCA_BOUND_UNKNOWN : ALLOCA_OK); - return alloca_type_and_limit (unknown_result); - } - } - - // Similarly, but check for a comparison with an unknown LIMIT. - // if (LIMIT .COND. ARG) - // alloca(arg); - // - // Where LIMIT has a bound of unknown range. - // - // Note: All conditions of the form (ARG .COND. XXXX) where covered - // by the previous check above, so we only need to look for (LIMIT - // .COND. ARG) here. - tree limit = gimple_cond_lhs (last); - if ((gimple_cond_rhs (last) == arg - || gimple_cond_rhs (last) == arg_casted) - && TREE_CODE (limit) == SSA_NAME) - { - wide_int min, max; - value_range_kind range_type = get_range_info (limit, &min, &max); - - if (range_type == VR_UNDEFINED || range_type == VR_VARYING) - return alloca_type_and_limit (ALLOCA_BOUND_UNKNOWN); - - // ?? It looks like the above `if' is unnecessary, as we never - // get any VR_RANGE or VR_ANTI_RANGE here. If we had a range - // for LIMIT, I suppose we would have taken care of it in - // alloca_call_type(), or handled above where we handle (ARG .COND. N). - // - // If this ever triggers, we should probably figure out why and - // handle it, though it is likely to be just an ALLOCA_UNBOUNDED. - return alloca_type_and_limit (unbounded_result); - } - - return alloca_type_and_limit (unbounded_result); -} - -// Return TRUE if SSA's definition is a cast from a signed type. -// If so, set *INVALID_CASTED_TYPE to the signed type. - -static bool -cast_from_signed_p (tree ssa, tree *invalid_casted_type) -{ - gimple *def = SSA_NAME_DEF_STMT (ssa); - if (def - && !gimple_nop_p (def) - && gimple_assign_cast_p (def) - && !TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (def)))) - { - *invalid_casted_type = TREE_TYPE (gimple_assign_rhs1 (def)); - return true; - } - return false; -} - -// Return TRUE if X has a maximum range of MAX, basically covering the -// entire domain, in which case it's no range at all. - -static bool -is_max (tree x, wide_int max) -{ - return wi::max_value (TREE_TYPE (x)) == max; -} - // Analyze the alloca call in STMT and return the alloca type with its // corresponding limit (if applicable). IS_VLA is set if the alloca // call was created by the gimplifier for a VLA. -// -// If the alloca call may be too large because of a cast from a signed -// type to an unsigned type, set *INVALID_CASTED_TYPE to the -// problematic signed type. static class alloca_type_and_limit -alloca_call_type (gimple *stmt, bool is_vla, tree *invalid_casted_type) +alloca_call_type (range_query &query, gimple *stmt, bool is_vla) { gcc_assert (gimple_alloca_call_p (stmt)); - bool tentative_cast_from_signed = false; tree len = gimple_call_arg (stmt, 0); - tree len_casted = NULL; - wide_int min, max; - edge_iterator ei; - edge e; gcc_assert (!is_vla || warn_vla_limit >= 0); gcc_assert (is_vla || warn_alloca_limit >= 0); @@ -361,118 +197,9 @@ alloca_call_type (gimple *stmt, bool is_vla, tree *invalid_casted_type) return alloca_type_and_limit (ALLOCA_OK); } - // Check the range info if available. - if (TREE_CODE (len) == SSA_NAME) - { - value_range_kind range_type = get_range_info (len, &min, &max); - if (range_type == VR_RANGE) - { - if (wi::leu_p (max, max_size)) - return alloca_type_and_limit (ALLOCA_OK); - else - { - // A cast may have created a range we don't care - // about. For instance, a cast from 16-bit to - // 32-bit creates a range of 0..65535, even if there - // is not really a determinable range in the - // underlying code. In this case, look through the - // cast at the original argument, and fall through - // to look at other alternatives. - // - // We only look at through the cast when its from - // unsigned to unsigned, otherwise we may risk - // looking at SIGNED_INT < N, which is clearly not - // what we want. In this case, we'd be interested - // in a VR_RANGE of [0..N]. - // - // Note: None of this is perfect, and should all go - // away with better range information. But it gets - // most of the cases. - gimple *def = SSA_NAME_DEF_STMT (len); - if (gimple_assign_cast_p (def)) - { - tree rhs1 = gimple_assign_rhs1 (def); - tree rhs1type = TREE_TYPE (rhs1); - - // Bail if the argument type is not valid. - if (!INTEGRAL_TYPE_P (rhs1type)) - return alloca_type_and_limit (ALLOCA_OK); - - if (TYPE_UNSIGNED (rhs1type)) - { - len_casted = rhs1; - range_type = get_range_info (len_casted, &min, &max); - } - } - // An unknown range or a range of the entire domain is - // really no range at all. - if (range_type == VR_VARYING - || (!len_casted && is_max (len, max)) - || (len_casted && is_max (len_casted, max))) - { - // Fall through. - } - else if (range_type == VR_ANTI_RANGE) - return alloca_type_and_limit (ALLOCA_UNBOUNDED); - - if (range_type != VR_VARYING) - { - const offset_int maxobjsize - = wi::to_offset (max_object_size ()); - alloca_type result = (max_size < maxobjsize - ? ALLOCA_BOUND_MAYBE_LARGE : ALLOCA_OK); - return alloca_type_and_limit (result, max); - } - } - } - else if (range_type == VR_ANTI_RANGE) - { - // There may be some wrapping around going on. Catch it - // with this heuristic. Hopefully, this VR_ANTI_RANGE - // nonsense will go away, and we won't have to catch the - // sign conversion problems with this crap. - // - // This is here to catch things like: - // void foo(signed int n) { - // if (n < 100) - // alloca(n); - // ... - // } - if (cast_from_signed_p (len, invalid_casted_type)) - { - // Unfortunately this also triggers: - // - // __SIZE_TYPE__ n = (__SIZE_TYPE__)blah; - // if (n < 100) - // alloca(n); - // - // ...which is clearly bounded. So, double check that - // the paths leading up to the size definitely don't - // have a bound. - tentative_cast_from_signed = true; - } - } - // No easily determined range and try other things. - } - - // If we couldn't find anything, try a few heuristics for things we - // can easily determine. Check these misc cases but only accept - // them if all predecessors have a known bound. - class alloca_type_and_limit ret = alloca_type_and_limit (ALLOCA_OK); - FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->preds) - { - gcc_assert (!len_casted || TYPE_UNSIGNED (TREE_TYPE (len_casted))); - ret = alloca_call_type_by_arg (len, len_casted, e, max_size); - if (ret.type != ALLOCA_OK) - break; - } - - if (ret.type != ALLOCA_OK && tentative_cast_from_signed) - ret = alloca_type_and_limit (ALLOCA_CAST_FROM_SIGNED); - + struct alloca_type_and_limit ret = alloca_type_and_limit (ALLOCA_OK); // If we have a declared maximum size, we can take it into account. - if (ret.type != ALLOCA_OK - && gimple_call_builtin_p (stmt, BUILT_IN_ALLOCA_WITH_ALIGN_AND_MAX)) + if (gimple_call_builtin_p (stmt, BUILT_IN_ALLOCA_WITH_ALIGN_AND_MAX)) { tree arg = gimple_call_arg (stmt, 2); if (compare_tree_int (arg, max_size) <= 0) @@ -485,9 +212,37 @@ alloca_call_type (gimple *stmt, bool is_vla, tree *invalid_casted_type) ? ALLOCA_BOUND_MAYBE_LARGE : ALLOCA_OK); ret = alloca_type_and_limit (result, wi::to_wide (arg)); } + return ret; + } + + // If the user specified a limit, use it. + int_range_max r; + if (warn_limit_specified_p (is_vla) + && TREE_CODE (len) == SSA_NAME + && query.range_of_expr (r, len, stmt) + && !r.varying_p ()) + { + // The invalid bits are anything outside of [0, MAX_SIZE]. + static int_range<2> invalid_range (build_int_cst (size_type_node, 0), + build_int_cst (size_type_node, + max_size), + VR_ANTI_RANGE); + + r.intersect (invalid_range); + if (r.undefined_p ()) + return alloca_type_and_limit (ALLOCA_OK); + + return alloca_type_and_limit (ALLOCA_BOUND_MAYBE_LARGE, + wi::to_wide (integer_zero_node)); } - return ret; + const offset_int maxobjsize = tree_to_shwi (max_object_size ()); + /* When MAX_SIZE is greater than or equal to PTRDIFF_MAX treat + allocations that aren't visibly constrained as OK, otherwise + report them as (potentially) unbounded. */ + alloca_type unbounded_result = (max_size < maxobjsize.to_uhwi () + ? ALLOCA_UNBOUNDED : ALLOCA_OK); + return alloca_type_and_limit (unbounded_result); } // Return TRUE if STMT is in a loop, otherwise return FALSE. @@ -503,6 +258,7 @@ in_loop_p (gimple *stmt) unsigned int pass_walloca::execute (function *fun) { + gimple_ranger ranger; basic_block bb; FOR_EACH_BB_FN (bb, fun) { @@ -535,9 +291,8 @@ pass_walloca::execute (function *fun) else if (warn_alloca_limit < 0) continue; - tree invalid_casted_type = NULL; class alloca_type_and_limit t - = alloca_call_type (stmt, is_vla, &invalid_casted_type); + = alloca_call_type (ranger, stmt, is_vla); unsigned HOST_WIDE_INT adjusted_alloca_limit = adjusted_warn_limit (false); @@ -599,13 +354,6 @@ pass_walloca::execute (function *fun) } } break; - case ALLOCA_BOUND_UNKNOWN: - warning_at (loc, wcode, - (is_vla - ? G_("%Gvariable-length array bound is unknown") - : G_("%G%<alloca%> bound is unknown")), - stmt); - break; case ALLOCA_UNBOUNDED: warning_at (loc, wcode, (is_vla @@ -618,17 +366,6 @@ pass_walloca::execute (function *fun) warning_at (loc, wcode, "%Guse of %<alloca%> within a loop", stmt); break; - case ALLOCA_CAST_FROM_SIGNED: - gcc_assert (invalid_casted_type != NULL_TREE); - warning_at (loc, wcode, - (is_vla - ? G_("%Gargument to variable-length array " - "may be too large due to " - "conversion from %qT to %qT") - : G_("%Gargument to %<alloca%> may be too large " - "due to conversion from %qT to %qT")), - stmt, invalid_casted_type, size_type_node); - break; case ALLOCA_ARG_IS_ZERO: warning_at (loc, wcode, (is_vla diff --git a/gcc/testsuite/gcc.dg/Walloca-1.c b/gcc/testsuite/gcc.dg/Walloca-1.c index 85e9160e845..ed1fa929398 100644 --- a/gcc/testsuite/gcc.dg/Walloca-1.c +++ b/gcc/testsuite/gcc.dg/Walloca-1.c @@ -24,8 +24,7 @@ void foo1 (size_t len, size_t len2, size_t len3) char *s = alloca (123); useit (s); // OK, constant argument to alloca - s = alloca (num); // { dg-warning "large due to conversion" "" { target lp64 } } - // { dg-warning "unbounded use of 'alloca'" "" { target { ! lp64 } } .-1 } + s = alloca (num); // { dg-warning "may be too large" } useit (s); s = alloca (30000); /* { dg-warning "is too large" } */ diff --git a/gcc/testsuite/gcc.dg/Walloca-12.c b/gcc/testsuite/gcc.dg/Walloca-12.c index 059c5f32129..d2d9413ab1e 100644 --- a/gcc/testsuite/gcc.dg/Walloca-12.c +++ b/gcc/testsuite/gcc.dg/Walloca-12.c @@ -8,5 +8,5 @@ void g (unsigned int n) { if (n == 7) n = 11; - f (__builtin_alloca (n)); /* { dg-warning "unbounded use of 'alloca'" } */ + f (__builtin_alloca (n)); /* { dg-warning "may be too large" } */ } diff --git a/gcc/testsuite/gcc.dg/Walloca-13.c b/gcc/testsuite/gcc.dg/Walloca-13.c index 12e9f6c9281..99d62065e26 100644 --- a/gcc/testsuite/gcc.dg/Walloca-13.c +++ b/gcc/testsuite/gcc.dg/Walloca-13.c @@ -8,5 +8,5 @@ void g (int *p, int *q) { __SIZE_TYPE__ n = (__SIZE_TYPE__)(p - q); if (n < 100) - f (__builtin_alloca (n)); // { dg-bogus "may be too large due to conversion" "" { xfail { *-*-* } } } + f (__builtin_alloca (n)); // { dg-bogus "may be too large" "" { xfail { *-*-* } } } } diff --git a/gcc/testsuite/gcc.dg/Walloca-2.c b/gcc/testsuite/gcc.dg/Walloca-2.c index 766ff8d8af3..1cf9165c59f 100644 --- a/gcc/testsuite/gcc.dg/Walloca-2.c +++ b/gcc/testsuite/gcc.dg/Walloca-2.c @@ -24,7 +24,7 @@ g2 (int n) { void *p; if (n < 2000) - p = __builtin_alloca (n); // { dg-warning "large due to conversion" } + p = __builtin_alloca (n); // { dg-warning "may be too large" } else p = __builtin_malloc (n); f (p); @@ -36,9 +36,7 @@ g3 (int n) void *p; if (n > 0 && n < 3000) { - p = __builtin_alloca (n); // { dg-warning "'alloca' may be too large" "" { target lp64} } - // { dg-message "note:.*argument may be as large as 2999" "note" { target lp64 } .-1 } - // { dg-warning "unbounded use of 'alloca'" "" { target { ! lp64 } } .-2 } + p = __builtin_alloca (n); // { dg-warning "may be too large" } } else p = __builtin_malloc (n); diff --git a/gcc/testsuite/gcc.dg/Walloca-3.c b/gcc/testsuite/gcc.dg/Walloca-3.c index f5840673da0..b8000ff1249 100644 --- a/gcc/testsuite/gcc.dg/Walloca-3.c +++ b/gcc/testsuite/gcc.dg/Walloca-3.c @@ -13,7 +13,7 @@ g1 (__SIZE_TYPE__ n) { void *p; if (n < LIMIT) - p = __builtin_alloca (n); // { dg-warning "'alloca' bound is unknown" } + p = __builtin_alloca (n); // { dg-warning "may be too large" } else p = __builtin_malloc (n); f (p); @@ -27,7 +27,7 @@ g2 (unsigned short n) { void *p; if (n < SHORT_LIMIT) - p = __builtin_alloca (n); // { dg-warning "'alloca' bound is unknown" } + p = __builtin_alloca (n); // { dg-warning "may be too large" } else p = __builtin_malloc (n); f (p); diff --git a/gcc/testsuite/gcc.dg/Walloca-6.c b/gcc/testsuite/gcc.dg/Walloca-6.c index 16b5d6f729d..ebe08aec838 100644 --- a/gcc/testsuite/gcc.dg/Walloca-6.c +++ b/gcc/testsuite/gcc.dg/Walloca-6.c @@ -1,7 +1,6 @@ /* { dg-do compile } */ /* { dg-require-effective-target alloca } */ /* { dg-options "-Walloca-larger-than=256 -O2" } */ -/* { dg-xfail-if "Currently broken but Andrew's work should fix this" { *-*-* } } */ void f (void*);
The walloca pass is a mess. It has all sorts of heuristics to divine problematic ranges fed into alloca, none of them very good, and all of them unreadable. The mess therein was actually one of the original motivators for the ranger project (along with array bounds checking). The attached patch is a conversion of the pass to ranger. It's mostly an exercise in removing code. The entire pass almost reduces to: + // If the user specified a limit, use it. + int_range_max r; + if (warn_limit_specified_p (is_vla) + && TREE_CODE (len) == SSA_NAME + && query.range_of_expr (r, len, stmt) + && !r.varying_p ()) + { + // The invalid bits are anything outside of [0, MAX_SIZE]. + static int_range<2> invalid_range (build_int_cst (size_type_node, 0), + build_int_cst (size_type_node, + max_size), + VR_ANTI_RANGE); + + r.intersect (invalid_range); + if (r.undefined_p ()) + return alloca_type_and_limit (ALLOCA_OK); + + return alloca_type_and_limit (ALLOCA_BOUND_MAYBE_LARGE, + wi::to_wide (integer_zero_node)); } That is, if the range of the integer passed to alloca is outside of [0,MAX_SIZE], warn, otherwise it's ok. Plain and simple. You will notice I removed the nuanced errors we gave before-- like trying to guess whether the problematic range came by virtue of a signed cast conversion. These specific errors were never part of the original design, they were just stuff we could guess by how the IL looked. It was non-exact and fragile. Now we just say the alloca argument may be too large, period. It the future, I would even like to remove the specific range the ranger was able to compute from the error message itself. As will become obvious, the ranger can get pretty outrageous ranges that are entirely non-obvious by looking at the code. Peppering the error messages with these ranges will ultimately just confuse the user. But alas, that's a problem for another patch to solve. This patch goes on top of the ranger which Andrew just posted. It's likely to be adjusted as the ranger is committed. gcc/ChangeLog: * gimple-ssa-warn-alloca.c (enum alloca_type): Remove ALLOCA_BOUND_UNKNOWN and ALLOCA_CAST_FROM_SIGNED. (warn_limit_specified_p): New. (alloca_call_type_by_arg): Remove. (cast_from_signed_p): Remove. (is_max): Remove. (alloca_call_type): Remove heuristics and replace with call into ranger. (pass_walloca::execute): Instantiate ranger. gcc/testsuite/ChangeLog: * gcc.dg/Walloca-1.c: Adjust for ranger. * gcc.dg/Walloca-12.c: Same. * gcc.dg/Walloca-13.c: Same. * gcc.dg/Walloca-2.c: Same. * gcc.dg/Walloca-3.c: Same. * gcc.dg/Walloca-6.c: Same. void g (__SIZE_TYPE__ n)