[PATCH,RFC] combine: Remove use_crosses_set_p

[PATCH,RFC] combine: Remove use_crosses_set_p

[Segher Boessenkool]

This removes use_crosses_set_p, and uses modified_between_p instead
everywhere it was used.  This improves optimisation.  I'm a little bit
worried it might increase compile time; so far I haven't seen it do
that though.

Longer term I would like to get rid of reg_stat completely, perhaps
use dataflow everywhere.

Comments/ideas welcome, both on this patch and that longer-term plan.


Segher


2017-11-30  Segher Boessenkool  <segher@kernel.crashing.org>

	* combine.c: Adjust comment.
	(use_crosses_set_p): Delete.
	(can_combine_p): Use modified_between_p instead of use_crosses_set_p.
	(try_combine): Ditto.

---
 gcc/combine.c | 69 ++++++-----------------------------------------------------
 1 file changed, 7 insertions(+), 62 deletions(-)

diff --git a/gcc/combine.c b/gcc/combine.c
index 22a382d..748c9a8 100644
--- a/gcc/combine.c
+++ b/gcc/combine.c
@@ -39,7 +39,7 @@ along with GCC; see the file COPYING3.  If not see
    insn as having a logical link to the preceding insn.  The same is true
    for an insn explicitly using CC0.
 
-   We check (with use_crosses_set_p) to avoid combining in such a way
+   We check (with modified_between_p) to avoid combining in such a way
    as to move a computation to a place where its value would be different.
 
    Combination is done by mathematically substituting the previous
@@ -482,7 +482,6 @@ static void record_dead_and_set_regs_1 (rtx, const_rtx, void *);
 static void record_dead_and_set_regs (rtx_insn *);
 static int get_last_value_validate (rtx *, rtx_insn *, int, int);
 static rtx get_last_value (const_rtx);
-static int use_crosses_set_p (const_rtx, int);
 static void reg_dead_at_p_1 (rtx, const_rtx, void *);
 static int reg_dead_at_p (rtx, rtx_insn *);
 static void move_deaths (rtx, rtx, int, rtx_insn *, rtx *);
@@ -2011,7 +2010,7 @@ can_combine_p (rtx_insn *insn, rtx_insn *i3, rtx_insn *pred ATTRIBUTE_UNUSED,
       || (! all_adjacent
 	  && (((!MEM_P (src)
 		|| ! find_reg_note (insn, REG_EQUIV, src))
-	       && use_crosses_set_p (src, DF_INSN_LUID (insn)))
+	       && modified_between_p (src, insn, i3))
 	      || (GET_CODE (src) == ASM_OPERANDS && MEM_VOLATILE_P (src))
 	      || GET_CODE (src) == UNSPEC_VOLATILE))
       /* Don't combine across a CALL_INSN, because that would possibly
@@ -3727,7 +3726,7 @@ try_combine (rtx_insn *i3, rtx_insn *i2, rtx_insn *i1, rtx_insn *i0,
 	}
       else if (m_split_insn && NEXT_INSN (NEXT_INSN (m_split_insn)) == NULL_RTX
 	       && (next_nonnote_nondebug_insn (i2) == i3
-		   || ! use_crosses_set_p (PATTERN (m_split_insn), DF_INSN_LUID (i2))))
+		   || !modified_between_p (PATTERN (m_split_insn), i2, i3)))
 	{
 	  rtx i2set, i3set;
 	  rtx newi3pat = PATTERN (NEXT_INSN (m_split_insn));
@@ -3791,7 +3790,7 @@ try_combine (rtx_insn *i3, rtx_insn *i2, rtx_insn *i1, rtx_insn *i0,
 	      || can_change_dest_mode (i2dest, added_sets_2,
 				       GET_MODE (*split)))
 	  && (next_nonnote_nondebug_insn (i2) == i3
-	      || ! use_crosses_set_p (*split, DF_INSN_LUID (i2)))
+	      || !modified_between_p (*split, i2, i3))
 	  /* We can't overwrite I2DEST if its value is still used by
 	     NEWPAT.  */
 	  && ! reg_referenced_p (i2dest, newpat))
@@ -3982,8 +3981,7 @@ try_combine (rtx_insn *i3, rtx_insn *i2, rtx_insn *i1, rtx_insn *i0,
 	   && GET_CODE (XVECEXP (newpat, 0, 1)) == SET
 	   && rtx_equal_p (SET_SRC (XVECEXP (newpat, 0, 1)),
 			   XEXP (SET_SRC (XVECEXP (newpat, 0, 0)), 0))
-	   && ! use_crosses_set_p (SET_SRC (XVECEXP (newpat, 0, 1)),
-				   DF_INSN_LUID (i2))
+	   && !modified_between_p (SET_SRC (XVECEXP (newpat, 0, 1)), i2, i3)
 	   && GET_CODE (SET_DEST (XVECEXP (newpat, 0, 1))) != ZERO_EXTRACT
 	   && GET_CODE (SET_DEST (XVECEXP (newpat, 0, 1))) != STRICT_LOW_PART
 	   && ! (temp_expr = SET_DEST (XVECEXP (newpat, 0, 1)),
@@ -4057,7 +4055,7 @@ try_combine (rtx_insn *i3, rtx_insn *i2, rtx_insn *i1, rtx_insn *i0,
 	 be first.  The PARALLEL might also have been pre-existing in i3,
 	 so we need to make sure that we won't wrongly hoist a SET to i2
 	 that would conflict with a death note present in there.  */
-      if (!use_crosses_set_p (SET_SRC (set1), DF_INSN_LUID (i2))
+      if (!modified_between_p (SET_SRC (set1), i2, i3)
 	  && !(REG_P (SET_DEST (set1))
 	       && find_reg_note (i2, REG_DEAD, SET_DEST (set1)))
 	  && !(GET_CODE (SET_DEST (set1)) == SUBREG
@@ -4072,7 +4070,7 @@ try_combine (rtx_insn *i3, rtx_insn *i2, rtx_insn *i1, rtx_insn *i0,
 	  newi2pat = set1;
 	  newpat = set0;
 	}
-      else if (!use_crosses_set_p (SET_SRC (set0), DF_INSN_LUID (i2))
+      else if (!modified_between_p (SET_SRC (set0), i2, i3)
 	       && !(REG_P (SET_DEST (set0))
 		    && find_reg_note (i2, REG_DEAD, SET_DEST (set0)))
 	       && !(GET_CODE (SET_DEST (set0)) == SUBREG
@@ -13695,59 +13693,6 @@ get_last_value (const_rtx x)
   return 0;
 }
 \f
-/* Return nonzero if expression X refers to a REG or to memory
-   that is set in an instruction more recent than FROM_LUID.  */
-
-static int
-use_crosses_set_p (const_rtx x, int from_luid)
-{
-  const char *fmt;
-  int i;
-  enum rtx_code code = GET_CODE (x);
-
-  if (code == REG)
-    {
-      unsigned int regno = REGNO (x);
-      unsigned endreg = END_REGNO (x);
-
-#ifdef PUSH_ROUNDING
-      /* Don't allow uses of the stack pointer to be moved,
-	 because we don't know whether the move crosses a push insn.  */
-      if (regno == STACK_POINTER_REGNUM && PUSH_ARGS)
-	return 1;
-#endif
-      for (; regno < endreg; regno++)
-	{
-	  reg_stat_type *rsp = &reg_stat[regno];
-	  if (rsp->last_set
-	      && rsp->last_set_label == label_tick
-	      && DF_INSN_LUID (rsp->last_set) > from_luid)
-	    return 1;
-	}
-      return 0;
-    }
-
-  if (code == MEM && mem_last_set > from_luid)
-    return 1;
-
-  fmt = GET_RTX_FORMAT (code);
-
-  for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
-    {
-      if (fmt[i] == 'E')
-	{
-	  int j;
-	  for (j = XVECLEN (x, i) - 1; j >= 0; j--)
-	    if (use_crosses_set_p (XVECEXP (x, i, j), from_luid))
-	      return 1;
-	}
-      else if (fmt[i] == 'e'
-	       && use_crosses_set_p (XEXP (x, i), from_luid))
-	return 1;
-    }
-  return 0;
-}
-\f
 /* Define three variables used for communication between the following
    routines.  */
 
-- 
1.8.3.1

Re: [PATCH,RFC] combine: Remove use_crosses_set_p

[Segher Boessenkool]

On Thu, Nov 30, 2017 at 09:26:37AM +0000, Segher Boessenkool wrote:
> This removes use_crosses_set_p, and uses modified_between_p instead
> everywhere it was used.  This improves optimisation.  I'm a little bit
> worried it might increase compile time; so far I haven't seen it do
> that though.
> 
> Longer term I would like to get rid of reg_stat completely, perhaps
> use dataflow everywhere.
> 
> Comments/ideas welcome, both on this patch and that longer-term plan.

Since there are no comments, I'll commit it now.


Segher


> 2017-11-30  Segher Boessenkool  <segher@kernel.crashing.org>
> 
> 	* combine.c: Adjust comment.
> 	(use_crosses_set_p): Delete.
> 	(can_combine_p): Use modified_between_p instead of use_crosses_set_p.
> 	(try_combine): Ditto.
> 
> ---
>  gcc/combine.c | 69 ++++++-----------------------------------------------------
>  1 file changed, 7 insertions(+), 62 deletions(-)
> 
> diff --git a/gcc/combine.c b/gcc/combine.c
> index 22a382d..748c9a8 100644
> --- a/gcc/combine.c
> +++ b/gcc/combine.c
> @@ -39,7 +39,7 @@ along with GCC; see the file COPYING3.  If not see
>     insn as having a logical link to the preceding insn.  The same is true
>     for an insn explicitly using CC0.
>  
> -   We check (with use_crosses_set_p) to avoid combining in such a way
> +   We check (with modified_between_p) to avoid combining in such a way
>     as to move a computation to a place where its value would be different.
>  
>     Combination is done by mathematically substituting the previous
> @@ -482,7 +482,6 @@ static void record_dead_and_set_regs_1 (rtx, const_rtx, void *);
>  static void record_dead_and_set_regs (rtx_insn *);
>  static int get_last_value_validate (rtx *, rtx_insn *, int, int);
>  static rtx get_last_value (const_rtx);
> -static int use_crosses_set_p (const_rtx, int);
>  static void reg_dead_at_p_1 (rtx, const_rtx, void *);
>  static int reg_dead_at_p (rtx, rtx_insn *);
>  static void move_deaths (rtx, rtx, int, rtx_insn *, rtx *);
> @@ -2011,7 +2010,7 @@ can_combine_p (rtx_insn *insn, rtx_insn *i3, rtx_insn *pred ATTRIBUTE_UNUSED,
>        || (! all_adjacent
>  	  && (((!MEM_P (src)
>  		|| ! find_reg_note (insn, REG_EQUIV, src))
> -	       && use_crosses_set_p (src, DF_INSN_LUID (insn)))
> +	       && modified_between_p (src, insn, i3))
>  	      || (GET_CODE (src) == ASM_OPERANDS && MEM_VOLATILE_P (src))
>  	      || GET_CODE (src) == UNSPEC_VOLATILE))
>        /* Don't combine across a CALL_INSN, because that would possibly
> @@ -3727,7 +3726,7 @@ try_combine (rtx_insn *i3, rtx_insn *i2, rtx_insn *i1, rtx_insn *i0,
>  	}
>        else if (m_split_insn && NEXT_INSN (NEXT_INSN (m_split_insn)) == NULL_RTX
>  	       && (next_nonnote_nondebug_insn (i2) == i3
> -		   || ! use_crosses_set_p (PATTERN (m_split_insn), DF_INSN_LUID (i2))))
> +		   || !modified_between_p (PATTERN (m_split_insn), i2, i3)))
>  	{
>  	  rtx i2set, i3set;
>  	  rtx newi3pat = PATTERN (NEXT_INSN (m_split_insn));
> @@ -3791,7 +3790,7 @@ try_combine (rtx_insn *i3, rtx_insn *i2, rtx_insn *i1, rtx_insn *i0,
>  	      || can_change_dest_mode (i2dest, added_sets_2,
>  				       GET_MODE (*split)))
>  	  && (next_nonnote_nondebug_insn (i2) == i3
> -	      || ! use_crosses_set_p (*split, DF_INSN_LUID (i2)))
> +	      || !modified_between_p (*split, i2, i3))
>  	  /* We can't overwrite I2DEST if its value is still used by
>  	     NEWPAT.  */
>  	  && ! reg_referenced_p (i2dest, newpat))
> @@ -3982,8 +3981,7 @@ try_combine (rtx_insn *i3, rtx_insn *i2, rtx_insn *i1, rtx_insn *i0,
>  	   && GET_CODE (XVECEXP (newpat, 0, 1)) == SET
>  	   && rtx_equal_p (SET_SRC (XVECEXP (newpat, 0, 1)),
>  			   XEXP (SET_SRC (XVECEXP (newpat, 0, 0)), 0))
> -	   && ! use_crosses_set_p (SET_SRC (XVECEXP (newpat, 0, 1)),
> -				   DF_INSN_LUID (i2))
> +	   && !modified_between_p (SET_SRC (XVECEXP (newpat, 0, 1)), i2, i3)
>  	   && GET_CODE (SET_DEST (XVECEXP (newpat, 0, 1))) != ZERO_EXTRACT
>  	   && GET_CODE (SET_DEST (XVECEXP (newpat, 0, 1))) != STRICT_LOW_PART
>  	   && ! (temp_expr = SET_DEST (XVECEXP (newpat, 0, 1)),
> @@ -4057,7 +4055,7 @@ try_combine (rtx_insn *i3, rtx_insn *i2, rtx_insn *i1, rtx_insn *i0,
>  	 be first.  The PARALLEL might also have been pre-existing in i3,
>  	 so we need to make sure that we won't wrongly hoist a SET to i2
>  	 that would conflict with a death note present in there.  */
> -      if (!use_crosses_set_p (SET_SRC (set1), DF_INSN_LUID (i2))
> +      if (!modified_between_p (SET_SRC (set1), i2, i3)
>  	  && !(REG_P (SET_DEST (set1))
>  	       && find_reg_note (i2, REG_DEAD, SET_DEST (set1)))
>  	  && !(GET_CODE (SET_DEST (set1)) == SUBREG
> @@ -4072,7 +4070,7 @@ try_combine (rtx_insn *i3, rtx_insn *i2, rtx_insn *i1, rtx_insn *i0,
>  	  newi2pat = set1;
>  	  newpat = set0;
>  	}
> -      else if (!use_crosses_set_p (SET_SRC (set0), DF_INSN_LUID (i2))
> +      else if (!modified_between_p (SET_SRC (set0), i2, i3)
>  	       && !(REG_P (SET_DEST (set0))
>  		    && find_reg_note (i2, REG_DEAD, SET_DEST (set0)))
>  	       && !(GET_CODE (SET_DEST (set0)) == SUBREG
> @@ -13695,59 +13693,6 @@ get_last_value (const_rtx x)
>    return 0;
>  }
>  \f
> -/* Return nonzero if expression X refers to a REG or to memory
> -   that is set in an instruction more recent than FROM_LUID.  */
> -
> -static int
> -use_crosses_set_p (const_rtx x, int from_luid)
> -{
> -  const char *fmt;
> -  int i;
> -  enum rtx_code code = GET_CODE (x);
> -
> -  if (code == REG)
> -    {
> -      unsigned int regno = REGNO (x);
> -      unsigned endreg = END_REGNO (x);
> -
> -#ifdef PUSH_ROUNDING
> -      /* Don't allow uses of the stack pointer to be moved,
> -	 because we don't know whether the move crosses a push insn.  */
> -      if (regno == STACK_POINTER_REGNUM && PUSH_ARGS)
> -	return 1;
> -#endif
> -      for (; regno < endreg; regno++)
> -	{
> -	  reg_stat_type *rsp = &reg_stat[regno];
> -	  if (rsp->last_set
> -	      && rsp->last_set_label == label_tick
> -	      && DF_INSN_LUID (rsp->last_set) > from_luid)
> -	    return 1;
> -	}
> -      return 0;
> -    }
> -
> -  if (code == MEM && mem_last_set > from_luid)
> -    return 1;
> -
> -  fmt = GET_RTX_FORMAT (code);
> -
> -  for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
> -    {
> -      if (fmt[i] == 'E')
> -	{
> -	  int j;
> -	  for (j = XVECLEN (x, i) - 1; j >= 0; j--)
> -	    if (use_crosses_set_p (XVECEXP (x, i, j), from_luid))
> -	      return 1;
> -	}
> -      else if (fmt[i] == 'e'
> -	       && use_crosses_set_p (XEXP (x, i), from_luid))
> -	return 1;
> -    }
> -  return 0;
> -}
> -\f
>  /* Define three variables used for communication between the following
>     routines.  */
>  
> -- 
> 1.8.3.1

Re: [PATCH,RFC] combine: Remove use_crosses_set_p

[Eric Botcazou]

> Since there are no comments, I'll commit it now.

The idea looks interesting but the timing is a bit more questionable.

-- 
Eric Botcazou

Re: [PATCH,RFC] combine: Remove use_crosses_set_p

[Christophe Lyon]

Hi,

On 4 December 2017 at 18:18, Eric Botcazou <ebotcazou@adacore.com> wrote:
>> Since there are no comments, I'll commit it now.
>
> The idea looks interesting but the timing is a bit more questionable.
>
> --
> Eric Botcazou

Since this was committed (r255384), I've noticed a regression on
arm-none-linux-gnueabi --with-mode thumb --with-cpu cortex-a9
FAIL:     gcc.c-torture/execute/pr61725.c   -O3 -fomit-frame-pointer
-funroll-loops -fpeel-loops -ftracer -finline-functions  execution
test

Christophe

Re: [PATCH,RFC] combine: Remove use_crosses_set_p

[Kyrill Tkachov]

On 06/12/17 11:51, Christophe Lyon wrote:
> Hi,
>
> On 4 December 2017 at 18:18, Eric Botcazou <ebotcazou@adacore.com> wrote:
> >> Since there are no comments, I'll commit it now.
> >
> > The idea looks interesting but the timing is a bit more questionable.
> >
> > --
> > Eric Botcazou
>
> Since this was committed (r255384), I've noticed a regression on
> arm-none-linux-gnueabi --with-mode thumb --with-cpu cortex-a9
> FAIL:     gcc.c-torture/execute/pr61725.c   -O3 -fomit-frame-pointer
> -funroll-loops -fpeel-loops -ftracer -finline-functions execution
> test
>

I've noticed that as well. I've filed PR 83304.

Thanks,
Kyrill

> Christophe