| Message ID | a0841e6f-f3dc-e8e9-f439-5f11c69c285b@gmail.com |
|---|---|
| State | New |
| Headers | show |
On Tue, Dec 13, 2016 at 2:36 AM, Martin Sebor <msebor@gmail.com> wrote: > The attached patch avoids infinite recursion when traversing phi > nodes in maybe_warn_alloc_args_overflow by using a bitmap to keep > track of those already visited and breaking out. It looks somewhat excessive (the whole PHI node walk looks exponential in the number of alloca calls given a good enough testcase). It also looks like operand_signed_p really returns only a wild guess, neither conservatively true or false. Is that correct? Can you instead scrap the weird anti-range handling please? Thanks, Richard. > Thanks > Martin
On Mon, Dec 12, 2016 at 06:36:16PM -0700, Martin Sebor wrote: > +/* Return true if the type of OP is signed, looking through any casts > + to an unsigned type. */ > + > +static bool > +operand_signed_p (tree op) > +{ > + bitmap visited = NULL; > + bool ret = operand_signed_p (op, &visited); > + > + if (visited) > + BITMAP_FREE (visited); I think you can drop the if before BITMAP_FREE here. Marek
On 12/13/2016 03:52 AM, Marek Polacek wrote: > On Mon, Dec 12, 2016 at 06:36:16PM -0700, Martin Sebor wrote: >> +/* Return true if the type of OP is signed, looking through any casts >> + to an unsigned type. */ >> + >> +static bool >> +operand_signed_p (tree op) >> +{ >> + bitmap visited = NULL; >> + bool ret = operand_signed_p (op, &visited); >> + >> + if (visited) >> + BITMAP_FREE (visited); > > I think you can drop the if before BITMAP_FREE here. Correct. jeff
On 12/12/2016 06:36 PM, Martin Sebor wrote: > The attached patch avoids infinite recursion when traversing phi > nodes in maybe_warn_alloc_args_overflow by using a bitmap to keep > track of those already visited and breaking out. > > Thanks > Martin > > gcc-78775.diff > > > PR tree-optimization/78775 - ICE in maybe_warn_alloc_args_overflow > > gcc/ChangeLog: > > PR tree-optimization/78775 > * calls.c (operand_signed_p): Add overload and avoid getting into > infinite recursion when traversing phi nodes. > > gcc/testsuite/ChangeLog: > > PR tree-optimization/78775 > * gcc.dg/pr78775.c: New test. So Richi asked for removal of the VR_ANTI_RANGE handling, which would imply removal of operand_signed_p. What are the implications if we do that? Jeff
On 01/05/2017 11:03 AM, Jeff Law wrote: > On 12/12/2016 06:36 PM, Martin Sebor wrote: >> The attached patch avoids infinite recursion when traversing phi >> nodes in maybe_warn_alloc_args_overflow by using a bitmap to keep >> track of those already visited and breaking out. >> >> Thanks >> Martin >> >> gcc-78775.diff >> >> >> PR tree-optimization/78775 - ICE in maybe_warn_alloc_args_overflow >> >> gcc/ChangeLog: >> >> PR tree-optimization/78775 >> * calls.c (operand_signed_p): Add overload and avoid getting into >> infinite recursion when traversing phi nodes. >> >> gcc/testsuite/ChangeLog: >> >> PR tree-optimization/78775 >> * gcc.dg/pr78775.c: New test. > So Richi asked for removal of the VR_ANTI_RANGE handling, which would > imply removal of operand_signed_p. > > What are the implications if we do that? I just got back to this yesterday. The implications of the removal of the anti-range handling are a number of false negatives in the test suite: FAIL: gcc.dg/attr-alloc_size-3.c (test for warnings, line 448) FAIL: gcc.dg/attr-alloc_size-4.c (test for warnings, line 137) FAIL: gcc.dg/attr-alloc_size-4.c (test for warnings, line 139) FAIL: gcc.dg/attr-alloc_size-4.c (test for warnings, line 175) with the second one, for example, being: n = ~[-4, MAX]; (I.e., n is either negative or too big.) p = malloc (n); Passing signed integers as arguments to allocation functions is common so I've been looking into how else to avoid the phi recursion (which I assume is the concern here) without compromising this case. Removing just the operand_signed_p() handling causes a number of false positives in the test suite, such as for m = [-3, 7]; n = [-5, 11]; p = calloc (m, n); which I suspect are common in the wild as well. Martin
On 01/05/2017 11:49 AM, Martin Sebor wrote: > On 01/05/2017 11:03 AM, Jeff Law wrote: >> On 12/12/2016 06:36 PM, Martin Sebor wrote: >>> The attached patch avoids infinite recursion when traversing phi >>> nodes in maybe_warn_alloc_args_overflow by using a bitmap to keep >>> track of those already visited and breaking out. >>> >>> Thanks >>> Martin >>> >>> gcc-78775.diff >>> >>> >>> PR tree-optimization/78775 - ICE in maybe_warn_alloc_args_overflow >>> >>> gcc/ChangeLog: >>> >>> PR tree-optimization/78775 >>> * calls.c (operand_signed_p): Add overload and avoid getting into >>> infinite recursion when traversing phi nodes. >>> >>> gcc/testsuite/ChangeLog: >>> >>> PR tree-optimization/78775 >>> * gcc.dg/pr78775.c: New test. >> So Richi asked for removal of the VR_ANTI_RANGE handling, which would >> imply removal of operand_signed_p. >> >> What are the implications if we do that? > > I just got back to this yesterday. The implications of the removal > of the anti-range handling are a number of false negatives in the > test suite: I was thinking more at a higher level. ie, are the warnings still useful if we don't have the anti-range handling? I suspect so, but would like to hear your opinion. > > FAIL: gcc.dg/attr-alloc_size-3.c (test for warnings, line 448) > FAIL: gcc.dg/attr-alloc_size-4.c (test for warnings, line 137) > FAIL: gcc.dg/attr-alloc_size-4.c (test for warnings, line 139) > FAIL: gcc.dg/attr-alloc_size-4.c (test for warnings, line 175) > > with the second one, for example, being: > > n = ~[-4, MAX]; (I.e., n is either negative or too big.) > p = malloc (n); Understood. The low level question is do we get these kinds of ranges often enough in computations leading to allocation sizes? > > Passing signed integers as arguments to allocation functions is > common so I've been looking into how else to avoid the phi recursion > (which I assume is the concern here) without compromising this case. > Removing just the operand_signed_p() handling causes a number of > false positives in the test suite, such as for Yes, passing signed integers as arguments is common. But how often do we have one of these anti-ranges that allows us to do something useful? > > m = [-3, 7]; > n = [-5, 11]; > p = calloc (m, n); > > which I suspect are common in the wild as well. I must be missing something, given those ranges I wouldn't think we have a false positive. The resulting size computation is going to have a range [-35, 88], right? ISTM that we'd really want to warn for that. I must be missing something. Jeff
>>> So Richi asked for removal of the VR_ANTI_RANGE handling, which would >>> imply removal of operand_signed_p. >>> >>> What are the implications if we do that? >> >> I just got back to this yesterday. The implications of the removal >> of the anti-range handling are a number of false negatives in the >> test suite: > I was thinking more at a higher level. ie, are the warnings still > useful if we don't have the anti-range handling? I suspect so, but > would like to hear your opinion. ... >> n = ~[-4, MAX]; (I.e., n is either negative or too big.) >> p = malloc (n); > Understood. The low level question is do we get these kinds of ranges > often enough in computations leading to allocation sizes? My intuition tells me that they are likely common enough not to disregard but I don't have a lot of data to back it up with. In a Bash build a full 23% of all checked calls are of this kind (24 out of 106). In a Binutils build only 4% are (9 out of 228). In Glibc, a little under 3%. My guess is that the number will be inversely proportional to the quality of the code. >> m = [-3, 7]; >> n = [-5, 11]; >> p = calloc (m, n); >> >> which I suspect are common in the wild as well. > I must be missing something, given those ranges I wouldn't think we have > a false positive. The resulting size computation is going to have a > range [-35, 88], right? ISTM that we'd really want to warn for that. I > must be missing something. The warning is meant to trigger only for cases of arguments that are definitely too big (i.e., it's not a -Wmaybe-alloc-size-larger- than type of warning). Given a range with negative lower bound and a positive upper bound the warning uses zero as the lower bound (it always ignores the upper bound). Doing otherwise would likely trigger lots of false positives. (This is true for -Wstringop-overflow as well.) The tradeoff, of course, is false negatives. In the -Walloc-larger- than case it can be mitigated by setting a lower threshold (I think we might want to consider lowering the default to something less liberal than PTRDIFF_MAX -- it seems very unlikely that a program would try to allocate that much memory, especially in LP64). Martin
On 01/05/2017 08:52 PM, Martin Sebor wrote: >>>> So Richi asked for removal of the VR_ANTI_RANGE handling, which would >>>> imply removal of operand_signed_p. >>>> >>>> What are the implications if we do that? >>> >>> I just got back to this yesterday. The implications of the removal >>> of the anti-range handling are a number of false negatives in the >>> test suite: >> I was thinking more at a higher level. ie, are the warnings still >> useful if we don't have the anti-range handling? I suspect so, but >> would like to hear your opinion. > ... >>> n = ~[-4, MAX]; (I.e., n is either negative or too big.) >>> p = malloc (n); >> Understood. The low level question is do we get these kinds of ranges >> often enough in computations leading to allocation sizes? > > My intuition tells me that they are likely common enough not to > disregard but I don't have a lot of data to back it up with. In > a Bash build a full 23% of all checked calls are of this kind (24 > out of 106). In a Binutils build only 4% are (9 out of 228). In > Glibc, a little under 3%. My guess is that the number will be > inversely proportional to the quality of the code. 23% for bash is definitely concerning. > >>> m = [-3, 7]; >>> n = [-5, 11]; >>> p = calloc (m, n); >>> >>> which I suspect are common in the wild as well. >> I must be missing something, given those ranges I wouldn't think we have >> a false positive. The resulting size computation is going to have a >> range [-35, 88], right? ISTM that we'd really want to warn for that. I >> must be missing something. > > The warning is meant to trigger only for cases of arguments that > are definitely too big (i.e., it's not a -Wmaybe-alloc-size-larger- > than type of warning). OK. That's probably what I was missing. I guess I should have gone back to the option documentation first. So IIRC the range for any multiply is produced from the 4 cross products. If you clamp the lower bound at 0, then 3 cross products drop to 0 and you get a range [0, u0 * u1] And in that case you're not warning because we don't know it's definitely too big, right? Let me ponder a bit too :-) > > The tradeoff, of course, is false negatives. In the -Walloc-larger- > than case it can be mitigated by setting a lower threshold (I think > we might want to consider lowering the default to something less > liberal than PTRDIFF_MAX -- it seems very unlikely that a program > would try to allocate that much memory, especially in LP64). Yea, the trick (of course) is finding a suitable value other than PTRDIFF_MAX. jeff
On 01/05/2017 08:52 PM, Martin Sebor wrote: >>>> So Richi asked for removal of the VR_ANTI_RANGE handling, which would >>>> imply removal of operand_signed_p. >>>> >>>> What are the implications if we do that? >>> >>> I just got back to this yesterday. The implications of the removal >>> of the anti-range handling are a number of false negatives in the >>> test suite: >> I was thinking more at a higher level. ie, are the warnings still >> useful if we don't have the anti-range handling? I suspect so, but >> would like to hear your opinion. > ... >>> n = ~[-4, MAX]; (I.e., n is either negative or too big.) >>> p = malloc (n); >> Understood. The low level question is do we get these kinds of ranges >> often enough in computations leading to allocation sizes? > > My intuition tells me that they are likely common enough not to > disregard but I don't have a lot of data to back it up with. In > a Bash build a full 23% of all checked calls are of this kind (24 > out of 106). In a Binutils build only 4% are (9 out of 228). In > Glibc, a little under 3%. My guess is that the number will be > inversely proportional to the quality of the code. So I think you've made a case that we do want to handle this case. So what's left is how best to avoid the infinite recursion and mitigate the pathological cases. What you're computing seems to be "this object may have been derived from a signed type". Right? It's a property we can compute for any given SSA_NAME and it's not context/path specific beyond the context/path information encoded by the SSA graph. So just thinking out load here, could we walk the IL once to identify call sites and build a worklist of SSA_NAMEs we care about. Then we iterate on the worklist much like Aldy's code he's working on for the unswitching vs uninitialized variable issue? Jeff
Another approach would be to walk the SSA_NAME list and generate a bitmap of all the names which have a signed type or which were defined by a conversion to an unsigned type from a signed type. At that point what's left is just the PHIs. So we'd walk the dominator tree in RPO order to process the PHIs. You don't have to recurse on the actual PHI arguments, just look at each one and see if it was already marked as being signed or derived from a signed type. If all the args are marked as signed or derived from a signed type, then the PHI can be marked as well. That may be more costly in the common case, but should avoid the pathological cases Richi is worried about. jeff
PR tree-optimization/78775 - ICE in maybe_warn_alloc_args_overflow gcc/ChangeLog: PR tree-optimization/78775 * calls.c (operand_signed_p): Add overload and avoid getting into infinite recursion when traversing phi nodes. gcc/testsuite/ChangeLog: PR tree-optimization/78775 * gcc.dg/pr78775.c: New test. Index: gcc/calls.c =================================================================== --- gcc/calls.c (revision 243581) +++ gcc/calls.c (working copy) @@ -1247,10 +1247,12 @@ alloc_max_size (void) } /* Return true if the type of OP is signed, looking through any casts - to an unsigned type. */ + to an unsigned type. VISITED is expected to be initially null and + is used internally by recursive calls of the function. Caller + must free *VISITED if non-null after the function returns. */ static bool -operand_signed_p (tree op) +operand_signed_p (tree op, bitmap *visited) { if (TREE_CODE (op) == SSA_NAME) { @@ -1265,6 +1267,12 @@ static bool } else if (gimple_code (def) == GIMPLE_PHI) { + if (!*visited) + *visited = BITMAP_ALLOC (NULL); + + if (!bitmap_set_bit (*visited, SSA_NAME_VERSION (op))) + return true; + /* In a phi, a constant argument may be unsigned even if in the source it's signed and negative. Ignore those and consider the result of a phi signed if @@ -1274,7 +1282,7 @@ static bool { tree op = gimple_phi_arg_def (def, i); if (TREE_CODE (op) != INTEGER_CST - && !operand_signed_p (op)) + && !operand_signed_p (op, visited)) return false; } @@ -1285,6 +1293,21 @@ static bool return !TYPE_UNSIGNED (TREE_TYPE (op)); } +/* Return true if the type of OP is signed, looking through any casts + to an unsigned type. */ + +static bool +operand_signed_p (tree op) +{ + bitmap visited = NULL; + bool ret = operand_signed_p (op, &visited); + + if (visited) + BITMAP_FREE (visited); + + return ret; +} + /* Diagnose a call EXP to function FN decorated with attribute alloc_size whose argument numbers given by IDX with values given by ARGS exceed the maximum object size or cause an unsigned oveflow (wrapping) when Index: gcc/testsuite/gcc.dg/pr78775.c =================================================================== --- gcc/testsuite/gcc.dg/pr78775.c (revision 0) +++ gcc/testsuite/gcc.dg/pr78775.c (working copy) @@ -0,0 +1,19 @@ +/* PR c/78775 - [7 Regression] ICE in maybe_warn_alloc_args_overflow + { dg-do compile } + { dg-options "-O2" } */ + +int a, b, *c; + +int main (void) +{ + unsigned long d = 0; + while (1) + { + switch (b) + case 'S': + d = a; + c = __builtin_malloc (d); + } + + return 0; +}