diff mbox

avoid infinite recursion in maybe_warn_alloc_args_overflow (pr 78775)

Message ID a0841e6f-f3dc-e8e9-f439-5f11c69c285b@gmail.com
State New
Headers show

Commit Message

Martin Sebor Dec. 13, 2016, 1:36 a.m. UTC
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

Comments

Richard Biener Dec. 13, 2016, 10:32 a.m. UTC | #1
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
Marek Polacek Dec. 13, 2016, 10:52 a.m. UTC | #2
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
Jeff Law Dec. 13, 2016, 4:22 p.m. UTC | #3
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
Jeff Law Jan. 5, 2017, 6:03 p.m. UTC | #4
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
Martin Sebor Jan. 5, 2017, 6:49 p.m. UTC | #5
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
Jeff Law Jan. 6, 2017, 12:14 a.m. UTC | #6
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
Martin Sebor Jan. 6, 2017, 3:52 a.m. UTC | #7
>>> 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
Jeff Law Jan. 6, 2017, 4:23 p.m. UTC | #8
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
Jeff Law Jan. 6, 2017, 4:45 p.m. UTC | #9
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
Jeff Law Jan. 6, 2017, 5:10 p.m. UTC | #10
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
diff mbox

Patch

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;
+}