diff mbox

[PR64817-related,2/3] don't alloc rtl when failing to simplify XOR of AND

Message ID orzj8up5oo.fsf@livre.home
State New
Headers show

Commit Message

Alexandre Oliva Feb. 4, 2015, 6:11 a.m. UTC 
We have a problem in simplify_binary_operation_1 that causes memory
waste in general, and memory explosion in pathological testcases such as
that of PR64817, with large exprs amounting to XOR of AND of XOR of AND
of...

I believe rtl simplifiers are not supposed to allocate rtl before
committing to simplifying the expr at hand.  The code that simplies XORs
of ANDs, whose second operands are both constants, used to do this.

In the pathological rtl resulting from the PR64817 testcases, the
recursive attempts to simplify the large exprs with lots of such
opportunities end up calling simplify_gen_unary O(2^n) times, where n is
the number of XORs in the large expr, each call allocating memory that
will ultimately not be used because simplification is not possible.

This patch rearranges the simplification so as to avoid the early
allocation.  First, we attempt to simplify a negated variant of the
temporary exprs we used to generate, that avoids the need for
simplify_gen_unary and covers the second case in the simplification just
as well as the original code.

If we take the first case, however, even if the negated version failed
to simplify, we know we can simplify the whole thing by combining the
constants, so we negate the sub-expression simplified before, or create
the non-negated sub-expression only if the negation of its operand
simplifies successfully.  This should cover all cases we covered before,
but without allocating rtl before committing to a simplification.

I made a cursory look at the other simplification paths and couldn't
find any similar problem in them.

This fixes the memory explosion problem in var-tracking exposed by the
testcase in patch 1/3 of this series, as well as by the original PR64817
testcase with the fix in patch 1/3.

Regstrapped on x86_64-linux-gnu and i686-pc-linux-gnu.  Ok to install?


for  gcc/ChangeLog

	PR debug/64817
	* simplify-rtx.c (simplify_binary_operation_1): Rewrite
	simplification of XOR of AND to not allocate new rtx before
	committing to a simplification.
---
 gcc/simplify-rtx.c |   29 ++++++++++++++++++++++++-----
 1 file changed, 24 insertions(+), 5 deletions(-)

Comments

Jakub Jelinek Feb. 4, 2015, 8:12 a.m. UTC | #1 
On Wed, Feb 04, 2015 at 04:11:03AM -0200, Alexandre Oliva wrote:
> for  gcc/ChangeLog
> 
> 	PR debug/64817
> 	* simplify-rtx.c (simplify_binary_operation_1): Rewrite
> 	simplification of XOR of AND to not allocate new rtx before
> 	committing to a simplification.

Ok, thanks.

	Jakub
diff mbox

Patch

diff --git a/gcc/simplify-rtx.c b/gcc/simplify-rtx.c
index 5c9e3bf..bea9ec3 100644
--- a/gcc/simplify-rtx.c
+++ b/gcc/simplify-rtx.c
@@ -2724,12 +2724,31 @@  simplify_binary_operation_1 (enum rtx_code code, machine_mode mode,
 	  HOST_WIDE_INT bval = INTVAL (b);
 	  HOST_WIDE_INT cval = INTVAL (c);
 
-	  rtx na_c
-	    = simplify_binary_operation (AND, mode,
-					 simplify_gen_unary (NOT, mode, a, mode),
-					 c);
+	  /* Instead of computing ~A&C, we compute its negated value,
+	     ~(A|~C).  If it yields -1, ~A&C is zero, so we can
+	     optimize for sure.  If it does not simplify, we still try
+	     to compute ~A&C below, but since that always allocates
+	     RTL, we don't try that before committing to returning a
+	     simplified expression.  */
+	  rtx n_na_c = simplify_binary_operation (IOR, mode, a,
+						  GEN_INT (~cval));
+
 	  if ((~cval & bval) == 0)
 	    {
+	      rtx na_c = NULL_RTX;
+	      if (n_na_c)
+		na_c = simplify_gen_unary (NOT, mode, n_na_c, mode);
+	      else
+		{
+		  /* If ~A does not simplify, don't bother: we don't
+		     want to simplify 2 operations into 3, and if na_c
+		     were to simplify with na, n_na_c would have
+		     simplified as well.  */
+		  rtx na = simplify_unary_operation (NOT, mode, a, mode);
+		  if (na)
+		    na_c = simplify_gen_binary (AND, mode, na, c);
+		}
+
 	      /* Try to simplify ~A&C | ~B&C.  */
 	      if (na_c != NULL_RTX)
 		return simplify_gen_binary (IOR, mode, na_c,
@@ -2738,7 +2757,7 @@  simplify_binary_operation_1 (enum rtx_code code, machine_mode mode,
 	  else
 	    {
 	      /* If ~A&C is zero, simplify A&(~C&B) | ~B&C.  */
-	      if (na_c == const0_rtx)
+	      if (n_na_c == CONSTM1_RTX (mode))
 		{
 		  rtx a_nc_b = simplify_gen_binary (AND, mode, a,
 						    gen_int_mode (~cval & bval,