[PATCH] Improve combining of conditionals

[PATCH] Improve combining of conditionals

[Maxim Kuvyrkov]

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

This patch fixes the problem with substituting expressions into IF_THEN_ELSE during combining.  Without this patch combining of conditionals inside IF_THEN_ELSE is seriously inhibited.

The problem this patch fixes is that combine_simplify_rtx() prefers to return an expression (say, <xor (a) (b)>) even when a comparison is prefered (say, <neq (xor (a) (b)) 0>).  Expressions are not recognized as valid conditions of if_then_else for most targets, so combiner misses a potential optimization.  This patch makes combine_simplify_rtx() aware of the context it was invoked in, and, when appropriate, does not discourage it from returning a conditional.

The motivating example for this fix was crcu8() routine from CoreMark.  Compiling this routine for MIPS32R2 at -O3 produces there are several instances of sequence

andi	$2,$2,0x1
xori	$2,$2,0x1
movn	$3,$5,$2  ; $2 dies here

which can be optimized into

andi	$2,$2,0x1
movz	$3,$5,$2  ; $2 dies here
.

The patch was successfully tested on {i686, arm, mips}-linux, both GCC testsuites and SPEC2000 runs.  For all targets there was no observable code difference in SPEC2000 benchmarks, so the example does not trigger very often.  Still, it speeds up CoreMark by about 1%.

OK for trunk?

--
Maxim Kuvyrkov
Mentor Graphics / CodeSourcery



[-- Attachment #2: gcc-combine-if_then_else.ChangeLog --]
[-- Type: application/octet-stream, Size: 228 bytes --]

2011-04-15  Maxim Kuvyrkov  <maxim@codesourcery.com>

	* combine.c (subst, combine_simlify_rtx): Add new argument, use it
	to track processing of conditionals.  Update all callers.
	(try_combine, simplify_if_then_else): Update.

[-- Attachment #3: gcc-combine-if_then_else.patch --]
[-- Type: application/octet-stream, Size: 9828 bytes --]

From 7738ca05728ebc1b5d46eabc9f3dedd73842850d Mon Sep 17 00:00:00 2001
From: Maxim Kuvyrkov <maxim@codesourcery.com>
Date: Fri, 8 Apr 2011 07:55:20 -0700
Subject: [PATCH] combine

---
 gcc/combine.c |   69 ++++++++++++++++++++++++++++++++++----------------------
 1 files changed, 42 insertions(+), 27 deletions(-)

diff --git a/gcc/combine.c b/gcc/combine.c
index 8771acf..ca54083 100644
--- a/gcc/combine.c
+++ b/gcc/combine.c
@@ -417,8 +417,8 @@ static rtx try_combine (rtx, rtx, rtx, rtx, int *, rtx);
 static void undo_all (void);
 static void undo_commit (void);
 static rtx *find_split_point (rtx *, rtx, bool);
-static rtx subst (rtx, rtx, rtx, int, int);
-static rtx combine_simplify_rtx (rtx, enum machine_mode, int);
+static rtx subst (rtx, rtx, rtx, int, int, int);
+static rtx combine_simplify_rtx (rtx, enum machine_mode, int, int);
 static rtx simplify_if_then_else (rtx);
 static rtx simplify_set (rtx);
 static rtx simplify_logical (rtx);
@@ -3117,11 +3117,11 @@ try_combine (rtx i3, rtx i2, rtx i1, rtx i0, int *new_direct_jump_p,
 	  if (i1)
 	    {
 	      subst_low_luid = DF_INSN_LUID (i1);
-	      i1src = subst (i1src, pc_rtx, pc_rtx, 0, 0);
+	      i1src = subst (i1src, pc_rtx, pc_rtx, 0, 0, 0);
 	    }
 
 	  subst_low_luid = DF_INSN_LUID (i2);
-	  i2src = subst (i2src, pc_rtx, pc_rtx, 0, 0);
+	  i2src = subst (i2src, pc_rtx, pc_rtx, 0, 0, 0);
 	}
 
       n_occurrences = 0;		/* `subst' counts here */
@@ -3132,7 +3132,7 @@ try_combine (rtx i3, rtx i2, rtx i1, rtx i0, int *new_direct_jump_p,
 	 self-referential RTL when we will be substituting I1SRC for I1DEST
 	 later.  Likewise if I0 feeds into I2, either directly or indirectly
 	 through I1, and I0DEST is in I0SRC.  */
-      newpat = subst (PATTERN (i3), i2dest, i2src, 0,
+      newpat = subst (PATTERN (i3), i2dest, i2src, 0, 0,
 		      (i1_feeds_i2_n && i1dest_in_i1src)
 		      || ((i0_feeds_i2_n || (i0_feeds_i1_n && i1_feeds_i2_n))
 			  && i0dest_in_i0src));
@@ -3171,7 +3171,7 @@ try_combine (rtx i3, rtx i2, rtx i1, rtx i0, int *new_direct_jump_p,
 	 copy of I1SRC each time we substitute it, in order to avoid creating
 	 self-referential RTL when we will be substituting I0SRC for I0DEST
 	 later.  */
-      newpat = subst (newpat, i1dest, i1src, 0,
+      newpat = subst (newpat, i1dest, i1src, 0, 0,
 		      i0_feeds_i1_n && i0dest_in_i0src);
       substed_i1 = 1;
 
@@ -3201,7 +3201,7 @@ try_combine (rtx i3, rtx i2, rtx i1, rtx i0, int *new_direct_jump_p,
 
       n_occurrences = 0;
       subst_low_luid = DF_INSN_LUID (i0);
-      newpat = subst (newpat, i0dest, i0src, 0, 0);
+      newpat = subst (newpat, i0dest, i0src, 0, 0, 0);
       substed_i0 = 1;
     }
 
@@ -3263,7 +3263,7 @@ try_combine (rtx i3, rtx i2, rtx i1, rtx i0, int *new_direct_jump_p,
 	{
 	  rtx t = i1pat;
 	  if (i0_feeds_i1_n)
-	    t = subst (t, i0dest, i0src, 0, 0);
+	    t = subst (t, i0dest, i0src, 0, 0, 0);
 
 	  XVECEXP (newpat, 0, --total_sets) = t;
 	}
@@ -3271,10 +3271,10 @@ try_combine (rtx i3, rtx i2, rtx i1, rtx i0, int *new_direct_jump_p,
 	{
 	  rtx t = i2pat;
 	  if (i1_feeds_i2_n)
-	    t = subst (t, i1dest, i1src_copy ? i1src_copy : i1src, 0,
+	    t = subst (t, i1dest, i1src_copy ? i1src_copy : i1src, 0, 0,
 		       i0_feeds_i1_n && i0dest_in_i0src);
 	  if ((i0_feeds_i1_n && i1_feeds_i2_n) || i0_feeds_i2_n)
-	    t = subst (t, i0dest, i0src, 0, 0);
+	    t = subst (t, i0dest, i0src, 0, 0, 0);
 
 	  XVECEXP (newpat, 0, --total_sets) = t;
 	}
@@ -4938,11 +4938,13 @@ find_split_point (rtx *loc, rtx insn, bool set_src)
 
    IN_DEST is nonzero if we are processing the SET_DEST of a SET.
 
+   IN_COND is nonzero if we are on top level of the condition.
+
    UNIQUE_COPY is nonzero if each substitution must be unique.  We do this
    by copying if `n_occurrences' is nonzero.  */
 
 static rtx
-subst (rtx x, rtx from, rtx to, int in_dest, int unique_copy)
+subst (rtx x, rtx from, rtx to, int in_dest, int in_cond, int unique_copy)
 {
   enum rtx_code code = GET_CODE (x);
   enum machine_mode op0_mode = VOIDmode;
@@ -5003,7 +5005,7 @@ subst (rtx x, rtx from, rtx to, int in_dest, int unique_copy)
       && GET_CODE (XVECEXP (x, 0, 0)) == SET
       && GET_CODE (SET_SRC (XVECEXP (x, 0, 0))) == ASM_OPERANDS)
     {
-      new_rtx = subst (XVECEXP (x, 0, 0), from, to, 0, unique_copy);
+      new_rtx = subst (XVECEXP (x, 0, 0), from, to, 0, 0, unique_copy);
 
       /* If this substitution failed, this whole thing fails.  */
       if (GET_CODE (new_rtx) == CLOBBER
@@ -5020,7 +5022,7 @@ subst (rtx x, rtx from, rtx to, int in_dest, int unique_copy)
 	      && GET_CODE (dest) != CC0
 	      && GET_CODE (dest) != PC)
 	    {
-	      new_rtx = subst (dest, from, to, 0, unique_copy);
+	      new_rtx = subst (dest, from, to, 0, 0, unique_copy);
 
 	      /* If this substitution failed, this whole thing fails.  */
 	      if (GET_CODE (new_rtx) == CLOBBER
@@ -5066,8 +5068,8 @@ subst (rtx x, rtx from, rtx to, int in_dest, int unique_copy)
 		    }
 		  else
 		    {
-		      new_rtx = subst (XVECEXP (x, i, j), from, to, 0,
-				   unique_copy);
+		      new_rtx = subst (XVECEXP (x, i, j), from, to, 0, 0,
+				       unique_copy);
 
 		      /* If this substitution failed, this whole thing
 			 fails.  */
@@ -5144,7 +5146,9 @@ subst (rtx x, rtx from, rtx to, int in_dest, int unique_copy)
 				&& (code == SUBREG || code == STRICT_LOW_PART
 				    || code == ZERO_EXTRACT))
 			       || code == SET)
-			      && i == 0), unique_copy);
+			      && i == 0),
+				 code == IF_THEN_ELSE && i == 0,
+				 unique_copy);
 
 	      /* If we found that we will have to reject this combination,
 		 indicate that by returning the CLOBBER ourselves, rather than
@@ -5201,7 +5205,7 @@ subst (rtx x, rtx from, rtx to, int in_dest, int unique_copy)
       /* If X is sufficiently simple, don't bother trying to do anything
 	 with it.  */
       if (code != CONST_INT && code != REG && code != CLOBBER)
-	x = combine_simplify_rtx (x, op0_mode, in_dest);
+	x = combine_simplify_rtx (x, op0_mode, in_dest, in_cond);
 
       if (GET_CODE (x) == code)
 	break;
@@ -5221,10 +5225,12 @@ subst (rtx x, rtx from, rtx to, int in_dest, int unique_copy)
    expression.
 
    OP0_MODE is the original mode of XEXP (x, 0).  IN_DEST is nonzero
-   if we are inside a SET_DEST.  */
+   if we are inside a SET_DEST.  IN_COND is nonzero if we are on the top level
+   of a condition.  */
 
 static rtx
-combine_simplify_rtx (rtx x, enum machine_mode op0_mode, int in_dest)
+combine_simplify_rtx (rtx x, enum machine_mode op0_mode, int in_dest,
+		      int in_cond)
 {
   enum rtx_code code = GET_CODE (x);
   enum machine_mode mode = GET_MODE (x);
@@ -5279,8 +5285,8 @@ combine_simplify_rtx (rtx x, enum machine_mode op0_mode, int in_dest)
 	     false arms to store-flag values.  Be careful to use copy_rtx
 	     here since true_rtx or false_rtx might share RTL with x as a
 	     result of the if_then_else_cond call above.  */
-	  true_rtx = subst (copy_rtx (true_rtx), pc_rtx, pc_rtx, 0, 0);
-	  false_rtx = subst (copy_rtx (false_rtx), pc_rtx, pc_rtx, 0, 0);
+	  true_rtx = subst (copy_rtx (true_rtx), pc_rtx, pc_rtx, 0, 0, 0);
+	  false_rtx = subst (copy_rtx (false_rtx), pc_rtx, pc_rtx, 0, 0, 0);
 
 	  /* If true_rtx and false_rtx are not general_operands, an if_then_else
 	     is unlikely to be simpler.  */
@@ -5624,7 +5630,7 @@ combine_simplify_rtx (rtx x, enum machine_mode op0_mode, int in_dest)
 	{
 	  /* Try to simplify the expression further.  */
 	  rtx tor = simplify_gen_binary (IOR, mode, XEXP (x, 0), XEXP (x, 1));
-	  temp = combine_simplify_rtx (tor, mode, in_dest);
+	  temp = combine_simplify_rtx (tor, mode, in_dest, 0);
 
 	  /* If we could, great.  If not, do not go ahead with the IOR
 	     replacement, since PLUS appears in many special purpose
@@ -5717,7 +5723,16 @@ combine_simplify_rtx (rtx x, enum machine_mode op0_mode, int in_dest)
 	     ZERO_EXTRACT is indeed appropriate, it will be placed back by
 	     the call to make_compound_operation in the SET case.  */
 
-	  if (STORE_FLAG_VALUE == 1
+	  if (in_cond)
+	    /* Don't apply below optimizations if the caller would
+	       prefer a comparison rather than a value.
+	       E.g., for the condition in an IF_THEN_ELSE most targets need
+	       an explicit comparison.  */
+	    {
+	      ;
+	    }
+
+	  else if (STORE_FLAG_VALUE == 1
 	      && new_code == NE && GET_MODE_CLASS (mode) == MODE_INT
 	      && op1 == const0_rtx
 	      && mode == GET_MODE (op0)
@@ -5961,11 +5976,11 @@ simplify_if_then_else (rtx x)
       if (reg_mentioned_p (from, true_rtx))
 	true_rtx = subst (known_cond (copy_rtx (true_rtx), true_code,
 				      from, true_val),
-		      pc_rtx, pc_rtx, 0, 0);
+			  pc_rtx, pc_rtx, 0, 0, 0);
       if (reg_mentioned_p (from, false_rtx))
 	false_rtx = subst (known_cond (copy_rtx (false_rtx), false_code,
 				   from, false_val),
-		       pc_rtx, pc_rtx, 0, 0);
+			   pc_rtx, pc_rtx, 0, 0, 0);
 
       SUBST (XEXP (x, 1), swapped ? false_rtx : true_rtx);
       SUBST (XEXP (x, 2), swapped ? true_rtx : false_rtx);
@@ -6182,11 +6197,11 @@ simplify_if_then_else (rtx x)
 	{
 	  temp = subst (simplify_gen_relational (true_code, m, VOIDmode,
 						 cond_op0, cond_op1),
-			pc_rtx, pc_rtx, 0, 0);
+			pc_rtx, pc_rtx, 0, 0, 0);
 	  temp = simplify_gen_binary (MULT, m, temp,
 				      simplify_gen_binary (MULT, m, c1,
 							   const_true_rtx));
-	  temp = subst (temp, pc_rtx, pc_rtx, 0, 0);
+	  temp = subst (temp, pc_rtx, pc_rtx, 0, 0, 0);
 	  temp = simplify_gen_binary (op, m, gen_lowpart (m, z), temp);
 
 	  if (extend_op != UNKNOWN)
-- 
1.7.4.1

Re: [PATCH] Improve combining of conditionals

[Eric Botcazou]

> The patch was successfully tested on {i686, arm, mips}-linux, both GCC
> testsuites and SPEC2000 runs.  For all targets there was no observable code
> difference in SPEC2000 benchmarks, so the example does not trigger very
> often.  Still, it speeds up CoreMark by about 1%.
>
> OK for trunk?

Yes, modulo the following nits:

@@ -4938,11 +4938,13 @@ find_split_point (rtx *loc, rtx insn, bool set_src)
 
    IN_DEST is nonzero if we are processing the SET_DEST of a SET.
 
+   IN_COND is nonzero if we are on top level of the condition.

"...we are at the top level of a condition."


@@ -5221,10 +5225,12 @@ subst (rtx x, rtx from, rtx to, int in_dest, int 
unique_copy)
    expression.
 
    OP0_MODE is the original mode of XEXP (x, 0).  IN_DEST is nonzero
-   if we are inside a SET_DEST.  */
+   if we are inside a SET_DEST.  IN_COND is nonzero if we are on the top level
+   of a condition.  */

Likewise.


@@ -5717,7 +5723,16 @@ combine_simplify_rtx (rtx x, enum machine_mode op0_mode, 
int in_dest)
 	     ZERO_EXTRACT is indeed appropriate, it will be placed back by
 	     the call to make_compound_operation in the SET case.  */
 
-	  if (STORE_FLAG_VALUE == 1
+	  if (in_cond)
+	    /* Don't apply below optimizations if the caller would
+	       prefer a comparison rather than a value.
+	       E.g., for the condition in an IF_THEN_ELSE most targets need
+	       an explicit comparison.  */
+	    {
+	      ;
+	    }

Remove the superfluous parentheses and move the comment to a new paragraph of 
the big comment just above.

No need to retest, just make sure this still compiles, thanks in advance.

-- 
Eric Botcazou

Re: [PATCH] Improve combining of conditionals

[Steven Bosscher]

On Fri, Apr 15, 2011 at 11:04 AM, Eric Botcazou <ebotcazou@adacore.com> wrote:
> @@ -4938,11 +4938,13 @@ find_split_point (rtx *loc, rtx insn, bool set_src)
>
>    IN_DEST is nonzero if we are processing the SET_DEST of a SET.
>
> +   IN_COND is nonzero if we are on top level of the condition.
>
> "...we are at the top level of a condition."

And make IN_COND a bool instead of an int?

Ciao!
Steven

Re: [PATCH] Improve combining of conditionals

[Maxim Kuvyrkov]

On Apr 15, 2011, at 2:38 PM, Steven Bosscher wrote:

> On Fri, Apr 15, 2011 at 11:04 AM, Eric Botcazou <ebotcazou@adacore.com> wrote:
>> @@ -4938,11 +4938,13 @@ find_split_point (rtx *loc, rtx insn, bool set_src)
>> 
>>    IN_DEST is nonzero if we are processing the SET_DEST of a SET.
>> 
>> +   IN_COND is nonzero if we are on top level of the condition.
>> 
>> "...we are at the top level of a condition."
> 
> And make IN_COND a bool instead of an int?

I think it's better to follow existing format of the function and make IN_COND to be of the same type as IN_DEST, i.e.,  an 'int'.  I agree that 'bool' should be preferred when adding a new function or significantly rewriting an existing one.

--
Maxim Kuvyrkov
Mentor Graphics / CodeSourcery

Re: [PATCH] Improve combining of conditionals

[Eric Botcazou]

> And make IN_COND a bool instead of an int?

I had the same initial reaction but then came to the same conclusion as Maxim.

-- 
Eric Botcazou

Re: [PATCH] Improve combining of conditionals

[Eric Botcazou]

> The problem this patch fixes is that combine_simplify_rtx() prefers to
> return an expression (say, <xor (a) (b)>) even when a comparison is
> prefered (say, <neq (xor (a) (b)) 0>).  Expressions are not recognized as
> valid conditions of if_then_else for most targets, so combiner misses a
> potential optimization.  This patch makes combine_simplify_rtx() aware of
> the context it was invoked in, and, when appropriate, does not discourage
> it from returning a conditional.

Btw, this is very likely also valid for targets with STORE_FLAG_VALUE == -1 so 
the same IN_COND short-circuit would need to be added a few lines below in 
combine_simplify_rtx.  But this would need to be tested.  Do you happen to 
have access to such a target, e.g. m68k?

-- 
Eric Botcazou

Re: [PATCH] Improve combining of conditionals

[Maxim Kuvyrkov]

On Apr 15, 2011, at 3:34 PM, Eric Botcazou wrote:

>> The problem this patch fixes is that combine_simplify_rtx() prefers to
>> return an expression (say, <xor (a) (b)>) even when a comparison is
>> prefered (say, <neq (xor (a) (b)) 0>).  Expressions are not recognized as
>> valid conditions of if_then_else for most targets, so combiner misses a
>> potential optimization.  This patch makes combine_simplify_rtx() aware of
>> the context it was invoked in, and, when appropriate, does not discourage
>> it from returning a conditional.
> 
> Btw, this is very likely also valid for targets with STORE_FLAG_VALUE == -1 so 
> the same IN_COND short-circuit would need to be added a few lines below in 
> combine_simplify_rtx.  But this would need to be tested.  Do you happen to 
> have access to such a target, e.g. m68k?

Hm, I didn't notice that one, thanks!  I have access to m68k (ColdFire, tbp) and will test this change there before committing.

--
Maxim Kuvyrkov
Mentor Graphics / CodeSourcery

Re: [PATCH] Improve combining of conditionals

[Mike Stump]

On Apr 15, 2011, at 3:44 AM, Eric Botcazou <ebotcazou@adacore.com> wrote:
>> And make IN_COND a bool instead of an int?
> 
> I had the same initial reaction but then came to the same conclusion as Maxim.

If it can be bool, it should be bool.

Re: [PATCH] Improve combining of conditionals

[Eric Botcazou]

> If it can be bool, it should be bool.

Rather basic principle IMO.  Consistency is of much greater value.

-- 
Eric Botcazou

Re: [PATCH] Improve combining of conditionals

[Mike Stump]

On Apr 15, 2011, at 10:22 AM, Eric Botcazou wrote:
>> If it can be bool, it should be bool.
> 
> Rather basic principle IMO.  Consistency is of much greater value.

Yes, and consistency is had by upgrading existing int uses that should be bool to bool as they are spotted....  :-)  I prefer doing this, even if done one at a time.  If one discourages it from being done, they run the risk of it being done later.  I'd rather have it sooner in this case.

Re: [PATCH] Improve combining of conditionals

[Maxim Kuvyrkov]

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

On Apr 15, 2011, at 4:38 PM, Maxim Kuvyrkov wrote:

> On Apr 15, 2011, at 3:34 PM, Eric Botcazou wrote:
> 
>>> The problem this patch fixes is that combine_simplify_rtx() prefers to
>>> return an expression (say, <xor (a) (b)>) even when a comparison is
>>> prefered (say, <neq (xor (a) (b)) 0>).  Expressions are not recognized as
>>> valid conditions of if_then_else for most targets, so combiner misses a
>>> potential optimization.  This patch makes combine_simplify_rtx() aware of
>>> the context it was invoked in, and, when appropriate, does not discourage
>>> it from returning a conditional.
>> 
>> Btw, this is very likely also valid for targets with STORE_FLAG_VALUE == -1 so 
>> the same IN_COND short-circuit would need to be added a few lines below in 
>> combine_simplify_rtx.  But this would need to be tested.  Do you happen to 
>> have access to such a target, e.g. m68k?
> 
> Hm, I didn't notice that one, thanks!  I have access to m68k (ColdFire, tbp) and will test this change there before committing.

I've successfully tested the following trivial patch on m68k-linux (cross-compiler, gcc, g++ and libstdc++ testsuites).

Checked in as obvious.

--
Maxim Kuvyrkov
Mentor Graphics / CodeSourcery


[-- Attachment #2: fsf-gcc-combine-fix-1.ChangeLog --]
[-- Type: application/octet-stream, Size: 202 bytes --]

2011-04-25  Maxim Kuvyrkov  <maxim@codesourcery.com>
	    Eric Botcazou  <ebotcazou@adacore.com>

	* combine.c (combine_simplify_rtx): Avoid mis-simplifying conditionals
	for STORE_FLAG_VALUE==-1 case.

[-- Attachment #3: fsf-gcc-combine-fix-1.patch --]
[-- Type: application/octet-stream, Size: 525 bytes --]

Index: combine.c
===================================================================
--- combine.c	(revision 172929)
+++ combine.c	(working copy)
@@ -5787,7 +5787,10 @@ combine_simplify_rtx (rtx x, enum machin
 
 	  /* If STORE_FLAG_VALUE is -1, we have cases similar to
 	     those above.  */
-	  if (STORE_FLAG_VALUE == -1
+	  if (in_cond)
+	    ;
+
+	  else if (STORE_FLAG_VALUE == -1
 	      && new_code == NE && GET_MODE_CLASS (mode) == MODE_INT
 	      && op1 == const0_rtx
 	      && (num_sign_bit_copies (op0, mode)