[PATCH][tree-optimization] Fix PR58088

[PATCH][tree-optimization] Fix PR58088

[Kyrylo Tkachov]

[-- Attachment #1: Type: text/plain, Size: 1203 bytes --]

Hi all,

In PR58088 the constant folder goes into an infinite recursion and runs out of
stack space because of two conflicting optimisations:
(X * C1) & C2 plays dirty when nested inside an IOR expression like so: ((X *
C1) & C2) | C4. One can undo the other leading to an infinite recursion.

Thanks to Marek for finding the IOR case.

This patch fixes that by checking in the IOR case that the change to C2 will
not conflict with the AND case transformation. Example testcases in the PR on
bugzilla.

This issue is present in 4.8.1 as well as trunk. However, I think 4.8 uses a
different API for double_int, so this patch will need to be reworked for 4.8.

In the meantime,
Ok for trunk?

Bootstrapped on x86_64-linux-gnu and tested arm-none-eabi on qemu.


Thanks,
Kyrill

2013-08-07  Kyrylo Tkachov  <kyrylo.tkachov@arm.com>

	* gcc/fold-const.c (mask_with_trailing_zeros): New function.
	(fold_binary_loc): Make sure we don't recurse infinitely
	when the X in (X & C1) | C2 is a tree of the form (Y * K1) & K2.
	Use mask_with_trailing_zeros where appropriate.
	
	
2013-08-07  Kyrylo Tkachov  <kyrylo.tkachov@arm.com>

	* gcc.c-torture/compile/pr58088.c: New test.

[-- Attachment #2: pr58088.patch --]
[-- Type: application/octet-stream, Size: 3560 bytes --]

diff --git a/gcc/fold-const.c b/gcc/fold-const.c
index 6506ae7..519d3b9 100644
--- a/gcc/fold-const.c
+++ b/gcc/fold-const.c
@@ -9927,6 +9927,24 @@ exact_inverse (tree type, tree cst)
     }
 }
 
+/*  Mask out the tz least significant bits of X of type TYPE where
+    tz is the number of trailing zeros in Y.  */
+static double_int
+mask_with_trailing_zeros (tree type, double_int x, double_int y)
+{
+  int tz = y.trailing_zeros ();
+
+  if (tz > 0)
+    {
+      double_int mask;
+
+      mask = ~double_int::mask (tz);
+      mask = mask.ext (TYPE_PRECISION (type), TYPE_UNSIGNED (type));
+      return mask & x;
+    }
+  return x;
+}
+
 /* Fold a binary expression of code CODE and type TYPE with operands
    OP0 and OP1.  LOC is the location of the resulting expression.
    Return the folded expression if folding is successful.  Otherwise,
@@ -11251,6 +11269,8 @@ fold_binary_loc (location_t loc,
 	{
 	  double_int c1, c2, c3, msk;
 	  int width = TYPE_PRECISION (type), w;
+	  bool valid = true;
+
 	  c1 = tree_to_double_int (TREE_OPERAND (arg0, 1));
 	  c2 = tree_to_double_int (arg1);
 
@@ -11285,7 +11305,21 @@ fold_binary_loc (location_t loc,
 		  break;
 		}
 	    }
-	  if (c3 != c1)
+	  /* If X is a tree of the form (Y * K1) & K2, this might conflict
+	     with that optimization from the BIT_AND_EXPR optimizations.
+	     This could end up in an infinite recursion.  */
+	  if (TREE_CODE (TREE_OPERAND (arg0, 0)) == MULT_EXPR
+	      && TREE_CODE (TREE_OPERAND (TREE_OPERAND (arg0, 0), 1))
+	                    == INTEGER_CST)
+	  {
+	    tree t = TREE_OPERAND (TREE_OPERAND (arg0, 0), 1);
+	    double_int masked
+	      = mask_with_trailing_zeros (type, c3, tree_to_double_int (t));
+
+	    valid = masked != c1;
+	  }
+
+	  if (c3 != c1 && valid)
 	    return fold_build2_loc (loc, BIT_IOR_EXPR, type,
 				    fold_build2_loc (loc, BIT_AND_EXPR, type,
 						     TREE_OPERAND (arg0, 0),
@@ -11675,22 +11709,17 @@ fold_binary_loc (location_t loc,
 	  && TREE_CODE (arg0) == MULT_EXPR
 	  && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST)
 	{
-	  int arg1tz
-	    = tree_to_double_int (TREE_OPERAND (arg0, 1)).trailing_zeros ();
-	  if (arg1tz > 0)
-	    {
-	      double_int arg1mask, masked;
-	      arg1mask = ~double_int::mask (arg1tz);
-	      arg1mask = arg1mask.ext (TYPE_PRECISION (type),
-					 TYPE_UNSIGNED (type));
-	      masked = arg1mask & tree_to_double_int (arg1);
-	      if (masked.is_zero ())
-		return omit_two_operands_loc (loc, type, build_zero_cst (type),
-					      arg0, arg1);
-	      else if (masked != tree_to_double_int (arg1))
-		return fold_build2_loc (loc, code, type, op0,
-					double_int_to_tree (type, masked));
-	    }
+	  tree t = TREE_OPERAND (arg0, 1);
+	  double_int masked
+	    = mask_with_trailing_zeros (type, tree_to_double_int (arg1),
+	                                tree_to_double_int (t));
+
+	  if (masked.is_zero ())
+	    return omit_two_operands_loc (loc, type, build_zero_cst (type),
+	                                  arg0, arg1);
+	  else if (masked != tree_to_double_int (arg1))
+	    return fold_build2_loc (loc, code, type, op0,
+	                            double_int_to_tree (type, masked));
 	}
 
       /* For constants M and N, if M == (1LL << cst) - 1 && (N & M) == M,
diff --git a/gcc/testsuite/gcc.c-torture/compile/pr58088.c b/gcc/testsuite/gcc.c-torture/compile/pr58088.c
new file mode 100644
index 0000000..07a9c68
--- /dev/null
+++ b/gcc/testsuite/gcc.c-torture/compile/pr58088.c
@@ -0,0 +1,5 @@
+int
+bar (int i)
+{
+  return 1 | ((i * 2) & 254);
+}

RE: [PATCH][tree-optimization] Fix PR58088

[Kyrylo Tkachov]

> This issue is present in 4.8.1 as well as trunk. However, I think 4.8
> uses a different API for double_int, so this patch will need to be reworked
for
> 4.8.

Actually, I was confused. This patch applies to 4.8.1 as well and fixes the
issue. Passes bootstrap on x86_64-linux-gnu and testing arm-none-eabi.

Therefore, OK to backport to 4.8 as well?

Thanks,
Kyrill

RE: [PATCH][tree-optimization] Fix PR58088

[Kyrylo Tkachov]

> Ok for trunk?
> 
> Bootstrapped on x86_64-linux-gnu and tested arm-none-eabi on qemu.
> 
> 
> Thanks,
> Kyrill
> 	* gcc.c-torture/compile/pr58088.c: New test.

Also, the ChangeLog entries should be:

2013-08-08  Kyrylo Tkachov  <kyrylo.tkachov@arm.com>

	PR tree-optimization/58088
	* gcc/fold-const.c (mask_with_trailing_zeros): New function.
	(fold_binary_loc): Make sure we don't recurse infinitely
	when the X in (X & C1) | C2 is a tree of the form (Y * K1) & K2.
	Use mask_with_trailing_zeros where appropriate.
	
	
2013-08-08  Kyrylo Tkachov  <kyrylo.tkachov@arm.com>

	PR tree-optimization/58088
	* gcc.c-torture/compile/pr58088.c: New test.

Re: [PATCH][tree-optimization] Fix PR58088

[Eric Botcazou]

> Also, the ChangeLog entries should be:
> 
> 2013-08-08  Kyrylo Tkachov  <kyrylo.tkachov@arm.com>
> 
> 	PR tree-optimization/58088
> 	* gcc/fold-const.c (mask_with_trailing_zeros): New function.
> 	(fold_binary_loc): Make sure we don't recurse infinitely
> 	when the X in (X & C1) | C2 is a tree of the form (Y * K1) & K2.
> 	Use mask_with_trailing_zeros where appropriate.

Without gcc/ prefix, paths are relative to the directory where ChangeLog lives.

> 2013-08-08  Kyrylo Tkachov  <kyrylo.tkachov@arm.com>
> 
> 	PR tree-optimization/58088
> 	* gcc.c-torture/compile/pr58088.c: New test.

This one is good.

-- 
Eric Botcazou

RE: [PATCH][tree-optimization] Fix PR58088

[Kyrylo Tkachov]

Ping.

Thanks,
Kyrill

2013-08-14  Kyrylo Tkachov  <kyrylo.tkachov@arm.com>

	PR tree-optimization/58088
	* fold-const.c (mask_with_trailing_zeros): New function.
	(fold_binary_loc): Make sure we don't recurse infinitely
	when the X in (X & C1) | C2 is a tree of the form (Y * K1) & K2.
	Use mask_with_trailing_zeros where appropriate.
	
	
2013-08-14  Kyrylo Tkachov  <kyrylo.tkachov@arm.com>

	PR tree-optimization/58088
	* gcc.c-torture/compile/pr58088.c: New test.


> -----Original Message-----
> From: gcc-patches-owner@gcc.gnu.org [mailto:gcc-patches-
> owner@gcc.gnu.org] On Behalf Of Kyrylo Tkachov
> Sent: 07 August 2013 14:22
> To: gcc-patches
> Cc: 'Richard Biener'; polacek@redhat.com
> Subject: [PATCH][tree-optimization] Fix PR58088
> 
> Hi all,
> 
> In PR58088 the constant folder goes into an infinite recursion and runs
> out of
> stack space because of two conflicting optimisations:
> (X * C1) & C2 plays dirty when nested inside an IOR expression like so:
> ((X *
> C1) & C2) | C4. One can undo the other leading to an infinite recursion.
> 
> Thanks to Marek for finding the IOR case.
> 
> This patch fixes that by checking in the IOR case that the change to C2
> will
> not conflict with the AND case transformation. Example testcases in the
> PR on
> bugzilla.
> 
> This issue is present in 4.8.1 as well as trunk. However, I think 4.8
> uses a
> different API for double_int, so this patch will need to be reworked for
> 4.8.
> 
> In the meantime,
> Ok for trunk?
> 
> Bootstrapped on x86_64-linux-gnu and tested arm-none-eabi on qemu.
> 
> 
> Thanks,
> Kyrill
> 
> 2013-08-07  Kyrylo Tkachov  <kyrylo.tkachov@arm.com>
> 
> 	* gcc/fold-const.c (mask_with_trailing_zeros): New function.
> 	(fold_binary_loc): Make sure we don't recurse infinitely
> 	when the X in (X & C1) | C2 is a tree of the form (Y * K1) & K2.
> 	Use mask_with_trailing_zeros where appropriate.
> 
> 
> 2013-08-07  Kyrylo Tkachov  <kyrylo.tkachov@arm.com>
> 
> 	* gcc.c-torture/compile/pr58088.c: New test.

[PATCH][Resend][tree-optimization] Fix PR58088

[Kyrylo Tkachov]

[-- Attachment #1: Type: text/plain, Size: 1221 bytes --]

[Resending, since I was away and not pinging it]


Hi all,

In PR58088 the constant folder goes into an infinite recursion and runs out of
stack space because of two conflicting optimisations:
(X * C1) & C2 plays dirty when nested inside an IOR expression like so: ((X *
C1) & C2) | C4. One can undo the other leading to an infinite recursion.

Thanks to Marek for finding the IOR case.

This patch fixes that by checking in the IOR case that the change to C2 will
not conflict with the AND case transformation. Example testcases in the PR on
bugzilla.

This affects both trunk and 4.8 and regresses and bootstraps cleanly on both.

Bootstrapped on x86_64-linux-gnu and tested arm-none-eabi on qemu.

Ok for trunk and 4.8?

Thanks,
Kyrill

2013-09-09  Kyrylo Tkachov  <kyrylo.tkachov@arm.com>

	PR tree-optimization/58088
	* fold-const.c (mask_with_trailing_zeros): New function.
	(fold_binary_loc): Make sure we don't recurse infinitely
	when the X in (X & C1) | C2 is a tree of the form (Y * K1) & K2.
	Use mask_with_trailing_zeros where appropriate.
	
	
2013-09-09  Kyrylo Tkachov  <kyrylo.tkachov@arm.com>

	PR tree-optimization/58088
	* gcc.c-torture/compile/pr58088.c: New test.

[-- Attachment #2: pr58088.patch --]
[-- Type: application/octet-stream, Size: 3481 bytes --]

diff --git a/gcc/fold-const.c b/gcc/fold-const.c
index 9956b2c..7ff66cd 100644
--- a/gcc/fold-const.c
+++ b/gcc/fold-const.c
@@ -9942,6 +9942,22 @@ exact_inverse (tree type, tree cst)
     }
 }
 
+/*  Mask out the tz least significant bits of X of type TYPE where
+    tz is the number of trailing zeroes in Y.  */
+static double_int
+mask_with_tz (tree type, double_int x, double_int y)
+{
+  int tz = y.trailing_zeros ();
+  if (tz > 0)
+    {
+      double_int mask;
+      mask = ~double_int::mask (tz);
+      mask = mask.ext (TYPE_PRECISION (type), TYPE_UNSIGNED (type));
+      return mask & x;
+    }
+  return x;
+}
+
 /* Fold a binary expression of code CODE and type TYPE with operands
    OP0 and OP1.  LOC is the location of the resulting expression.
    Return the folded expression if folding is successful.  Otherwise,
@@ -11266,6 +11282,7 @@ fold_binary_loc (location_t loc,
 	{
 	  double_int c1, c2, c3, msk;
 	  int width = TYPE_PRECISION (type), w;
+	  bool valid = true;
 	  c1 = tree_to_double_int (TREE_OPERAND (arg0, 1));
 	  c2 = tree_to_double_int (arg1);
 
@@ -11300,7 +11317,19 @@ fold_binary_loc (location_t loc,
 		  break;
 		}
 	    }
-	  if (c3 != c1)
+	  /* If X is a tree of the form (Y * K1) & K2, this might conflict
+	     with that optimization from the BIT_AND_EXPR optimizations.
+	     This could end up in an infinite recursion.  */
+	  if (TREE_CODE (TREE_OPERAND (arg0, 0)) == MULT_EXPR
+	      && TREE_CODE (TREE_OPERAND (TREE_OPERAND (arg0, 0), 1))
+	                    == INTEGER_CST)
+	  {
+	    tree t = TREE_OPERAND (TREE_OPERAND (arg0, 0), 1);
+	    double_int masked = mask_with_tz (type, c3, tree_to_double_int (t));
+	    valid = masked != c1;
+	  }
+
+	  if (c3 != c1 && valid)
 	    return fold_build2_loc (loc, BIT_IOR_EXPR, type,
 				    fold_build2_loc (loc, BIT_AND_EXPR, type,
 						     TREE_OPERAND (arg0, 0),
@@ -11690,22 +11719,16 @@ fold_binary_loc (location_t loc,
 	  && TREE_CODE (arg0) == MULT_EXPR
 	  && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST)
 	{
-	  int arg1tz
-	    = tree_to_double_int (TREE_OPERAND (arg0, 1)).trailing_zeros ();
-	  if (arg1tz > 0)
-	    {
-	      double_int arg1mask, masked;
-	      arg1mask = ~double_int::mask (arg1tz);
-	      arg1mask = arg1mask.ext (TYPE_PRECISION (type),
-					 TYPE_UNSIGNED (type));
-	      masked = arg1mask & tree_to_double_int (arg1);
-	      if (masked.is_zero ())
-		return omit_two_operands_loc (loc, type, build_zero_cst (type),
-					      arg0, arg1);
-	      else if (masked != tree_to_double_int (arg1))
-		return fold_build2_loc (loc, code, type, op0,
-					double_int_to_tree (type, masked));
-	    }
+	  double_int masked
+	    = mask_with_tz (type, tree_to_double_int (arg1),
+	                    tree_to_double_int (TREE_OPERAND (arg0, 1)));
+
+	  if (masked.is_zero ())
+	    return omit_two_operands_loc (loc, type, build_zero_cst (type),
+	                                  arg0, arg1);
+	  else if (masked != tree_to_double_int (arg1))
+	    return fold_build2_loc (loc, code, type, op0,
+	                            double_int_to_tree (type, masked));
 	}
 
       /* For constants M and N, if M == (1LL << cst) - 1 && (N & M) == M,
diff --git a/gcc/testsuite/gcc.c-torture/compile/pr58088.c b/gcc/testsuite/gcc.c-torture/compile/pr58088.c
new file mode 100644
index 0000000..07a9c68
--- /dev/null
+++ b/gcc/testsuite/gcc.c-torture/compile/pr58088.c
@@ -0,0 +1,5 @@
+int
+bar (int i)
+{
+  return 1 | ((i * 2) & 254);
+}

Re: [PATCH][Resend][tree-optimization] Fix PR58088

[Kyrill Tkachov]

Ping.

On 09/09/13 10:56, Kyrylo Tkachov wrote:
> [Resending, since I was away and not pinging it]
>
>
> Hi all,
>
> In PR58088 the constant folder goes into an infinite recursion and runs out of
> stack space because of two conflicting optimisations:
> (X * C1) & C2 plays dirty when nested inside an IOR expression like so: ((X *
> C1) & C2) | C4. One can undo the other leading to an infinite recursion.
>
> Thanks to Marek for finding the IOR case.
>
> This patch fixes that by checking in the IOR case that the change to C2 will
> not conflict with the AND case transformation. Example testcases in the PR on
> bugzilla.
>
> This affects both trunk and 4.8 and regresses and bootstraps cleanly on both.
>
> Bootstrapped on x86_64-linux-gnu and tested arm-none-eabi on qemu.
>
> Ok for trunk and 4.8?
>
> Thanks,
> Kyrill
>
> 2013-09-09  Kyrylo Tkachov  <kyrylo.tkachov@arm.com>
>
> 	PR tree-optimization/58088
> 	* fold-const.c (mask_with_trailing_zeros): New function.
> 	(fold_binary_loc): Make sure we don't recurse infinitely
> 	when the X in (X & C1) | C2 is a tree of the form (Y * K1) & K2.
> 	Use mask_with_trailing_zeros where appropriate.
> 	
> 	
> 2013-09-09  Kyrylo Tkachov  <kyrylo.tkachov@arm.com>
>
> 	PR tree-optimization/58088
> 	* gcc.c-torture/compile/pr58088.c: New test.

Re: [PATCH][Resend][tree-optimization] Fix PR58088

[Richard Earnshaw]

On 09/09/13 10:56, Kyrylo Tkachov wrote:
> [Resending, since I was away and not pinging it]
> 
> 
> Hi all,
> 
> In PR58088 the constant folder goes into an infinite recursion and runs out of
> stack space because of two conflicting optimisations:
> (X * C1) & C2 plays dirty when nested inside an IOR expression like so: ((X *
> C1) & C2) | C4. One can undo the other leading to an infinite recursion.
> 
> Thanks to Marek for finding the IOR case.
> 
> This patch fixes that by checking in the IOR case that the change to C2 will
> not conflict with the AND case transformation. Example testcases in the PR on
> bugzilla.
> 
> This affects both trunk and 4.8 and regresses and bootstraps cleanly on both.
> 
> Bootstrapped on x86_64-linux-gnu and tested arm-none-eabi on qemu.
> 
> Ok for trunk and 4.8?
> 
> Thanks,
> Kyrill
> 
> 2013-09-09  Kyrylo Tkachov  <kyrylo.tkachov@arm.com>
> 
> 	PR tree-optimization/58088
> 	* fold-const.c (mask_with_trailing_zeros): New function.
> 	(fold_binary_loc): Make sure we don't recurse infinitely
> 	when the X in (X & C1) | C2 is a tree of the form (Y * K1) & K2.
> 	Use mask_with_trailing_zeros where appropriate.
> 	
> 	
> 2013-09-09  Kyrylo Tkachov  <kyrylo.tkachov@arm.com>
> 
> 	PR tree-optimization/58088
> 	* gcc.c-torture/compile/pr58088.c: New test.=
> 
> 
> pr58088.patch
> 
> 

@@ -9942,6 +9942,22 @@ exact_inverse (tree type, tree cst)
     }
 }

+/*  Mask out the tz least significant bits of X of type TYPE where
+    tz is the number of trailing zeroes in Y.  */
+static double_int
+mask_with_tz (tree type, double_int x, double_int y)
+{
+  int tz = y.trailing_zeros ();
+  if (tz > 0)

blank line between declarations and statements.

@@ -11266,6 +11282,7 @@ fold_binary_loc (location_t loc,
 	{
 	  double_int c1, c2, c3, msk;
 	  int width = TYPE_PRECISION (type), w;
+	  bool valid = true;
 	  c1 = tree_to_double_int (TREE_OPERAND (arg0, 1));
 	  c2 = tree_to_double_int (arg1);

blank line after declarations before code body.

 	    }
-	  if (c3 != c1)
+	  /* If X is a tree of the form (Y * K1) & K2, this might conflict

Should be a blank line before the comment as well

+	     with that optimization from the BIT_AND_EXPR optimizations.
+	     This could end up in an infinite recursion.  */
+	  if (TREE_CODE (TREE_OPERAND (arg0, 0)) == MULT_EXPR
+	      && TREE_CODE (TREE_OPERAND (TREE_OPERAND (arg0, 0), 1))
+	                    == INTEGER_CST)
+	  {
+	    tree t = TREE_OPERAND (TREE_OPERAND (arg0, 0), 1);
+	    double_int masked = mask_with_tz (type, c3, tree_to_double_int (t));
+	    valid = masked != c1;

blank line before statements after declarations.
+	  }
+
+	  if (c3 != c1 && valid)

'valid' should come before the comparison test.  Furthermore, I think
'valid' is misleading; 'try_simplify' would be a more accurate
description of what the test is about.

OK with those changes.

R.