[stage1] Fallback to copy-prop if constant-prop not possible

Hi,

The RTL cprop pass in GCC operates by doing a local constant/copy propagation first and then a global one. In the local one, if a constant cannot be propagated (eg. due to constraints of the destination instruction) a copy propagation is done instead. However, at the global level copy propagation is only tried if no constant can be propagated, ie. if a constant can be propagated but the constraints of the destination instruction forbids it, no copy propagation will be tried. This patch fixes this issue. This solves the redundant ldr problem in GCC32RM-439.

ChangeLog entries are as follows:

*** gcc/ChangeLog ***

2015-01-21 Thomas Preud'homme thomas.preudhomme@arm.com

    * cprop.c (find_avail_set): Return up to two sets, one whose source is
    a register and one whose source is a constant.  Sets are returned in
    an array passed as parameter rather than as a return value.
    (cprop_insn): Use a do while loop rather than a goto.  Try each of the
    sets returned by find_avail_set, starting with the one whose source is
    a constant.


*** gcc/testsuite/ChangeLog ***

2015-01-21 Thomas Preud'homme thomas.preudhomme@arm.com

    * gcc.target/arm/pr64616.c: New file.

Following testing was done:

    Bootstrapped on x86_64 and ran the testsuite without regression
    Build an arm-none-eabi cross-compilers and ran the testsuite without regression with QEMU emulating a Cortex-M3
    Compiled CSiBE targeting x86_64 and Cortex-M3 arm-none-eabi without regression


Is this ok for stage1?

Best regards,

Thomas

On Mon, 16 Feb 2015, Thomas Preud'homme wrote:

> Hi,
> 
> The RTL cprop pass in GCC operates by doing a local constant/copy 
> propagation first and then a global one. In the local one, if a constant 
> cannot be propagated (eg. due to constraints of the destination 
> instruction) a copy propagation is done instead. However, at the global 
> level copy propagation is only tried if no constant can be propagated, 
> ie. if a constant can be propagated but the constraints of the 
> destination instruction forbids it, no copy propagation will be tried. 
> This patch fixes this issue. This solves the redundant ldr problem in 
> GCC32RM-439.

I think Steven is more familiar with this code.

Richard.

> ChangeLog entries are as follows:
> 
> *** gcc/ChangeLog ***
> 
> 2015-01-21 Thomas Preud'homme thomas.preudhomme@arm.com
> 
>     * cprop.c (find_avail_set): Return up to two sets, one whose source is
>     a register and one whose source is a constant.  Sets are returned in
>     an array passed as parameter rather than as a return value.
>     (cprop_insn): Use a do while loop rather than a goto.  Try each of the
>     sets returned by find_avail_set, starting with the one whose source is
>     a constant.
> 
> 
> *** gcc/testsuite/ChangeLog ***
> 
> 2015-01-21 Thomas Preud'homme thomas.preudhomme@arm.com
> 
>     * gcc.target/arm/pr64616.c: New file.
> 
> Following testing was done:
> 
>     Bootstrapped on x86_64 and ran the testsuite without regression
>     Build an arm-none-eabi cross-compilers and ran the testsuite without regression with QEMU emulating a Cortex-M3
>     Compiled CSiBE targeting x86_64 and Cortex-M3 arm-none-eabi without regression
> 
> diff --git a/gcc/cprop.c b/gcc/cprop.c
> index 4538291..c246d4b 100644
> --- a/gcc/cprop.c
> +++ b/gcc/cprop.c
> @@ -815,15 +815,15 @@ try_replace_reg (rtx from, rtx to, rtx_insn *insn)
>    return success;
>  }
>  
> -/* Find a set of REGNOs that are available on entry to INSN's block.  Return
> -   NULL no such set is found.  */
> +/* Find a set of REGNOs that are available on entry to INSN's block.  If found,
> +   SET_RET[0] will be assigned a set with a register source and SET_RET[1] a
> +   set with a constant source.  If not found the corresponding entry is set to
> +   NULL.  */
>  
> -static struct cprop_expr *
> -find_avail_set (int regno, rtx_insn *insn)
> +static void
> +find_avail_set (int regno, rtx_insn *insn, struct cprop_expr *set_ret[2])
>  {
> -  /* SET1 contains the last set found that can be returned to the caller for
> -     use in a substitution.  */
> -  struct cprop_expr *set1 = 0;
> +  set_ret[0] = set_ret[1] = NULL;
>  
>    /* Loops are not possible here.  To get a loop we would need two sets
>       available at the start of the block containing INSN.  i.e. we would
> @@ -863,8 +863,10 @@ find_avail_set (int regno, rtx_insn *insn)
>           If the source operand changed, we may still use it for the next
>           iteration of this loop, but we may not use it for substitutions.  */
>  
> -      if (cprop_constant_p (src) || reg_not_set_p (src, insn))
> -	set1 = set;
> +      if (cprop_constant_p (src))
> +	set_ret[1] = set;
> +      else if (reg_not_set_p (src, insn))
> +	set_ret[0] = set;
>  
>        /* If the source of the set is anything except a register, then
>  	 we have reached the end of the copy chain.  */
> @@ -875,10 +877,6 @@ find_avail_set (int regno, rtx_insn *insn)
>  	 and see if we have an available copy into SRC.  */
>        regno = REGNO (src);
>      }
> -
> -  /* SET1 holds the last set that was available and anticipatable at
> -     INSN.  */
> -  return set1;
>  }
>  
>  /* Subroutine of cprop_insn that tries to propagate constants into
> @@ -1044,40 +1042,41 @@ cprop_insn (rtx_insn *insn)
>    int changed = 0, changed_this_round;
>    rtx note;
>  
> -retry:
> -  changed_this_round = 0;
> -  reg_use_count = 0;
> -  note_uses (&PATTERN (insn), find_used_regs, NULL);
> +  do
> +    {
> +      changed_this_round = 0;
> +      reg_use_count = 0;
> +      note_uses (&PATTERN (insn), find_used_regs, NULL);
>  
> -  /* We may win even when propagating constants into notes.  */
> -  note = find_reg_equal_equiv_note (insn);
> -  if (note)
> -    find_used_regs (&XEXP (note, 0), NULL);
> +      /* We may win even when propagating constants into notes.  */
> +      note = find_reg_equal_equiv_note (insn);
> +      if (note)
> +	find_used_regs (&XEXP (note, 0), NULL);
>  
> -  for (i = 0; i < reg_use_count; i++)
> -    {
> -      rtx reg_used = reg_use_table[i];
> -      unsigned int regno = REGNO (reg_used);
> -      rtx src;
> -      struct cprop_expr *set;
> +      for (i = 0; i < reg_use_count; i++)
> +	{
> +	  rtx reg_used = reg_use_table[i];
> +	  unsigned int regno = REGNO (reg_used);
> +	  rtx src_cst = NULL, src_reg = NULL;
> +	  struct cprop_expr *set[2];
>  
> -      /* If the register has already been set in this block, there's
> -	 nothing we can do.  */
> -      if (! reg_not_set_p (reg_used, insn))
> -	continue;
> +	  /* If the register has already been set in this block, there's
> +	     nothing we can do.  */
> +	  if (! reg_not_set_p (reg_used, insn))
> +	    continue;
>  
> -      /* Find an assignment that sets reg_used and is available
> -	 at the start of the block.  */
> -      set = find_avail_set (regno, insn);
> -      if (! set)
> -	continue;
> +	  /* Find an assignment that sets reg_used and is available
> +	     at the start of the block.  */
> +	  find_avail_set (regno, insn, set);
>  
> -      src = set->src;
> +	  if (set[0])
> +	    src_reg = set[0]->src;
> +	  if (set[1])
> +	    src_cst = set[1]->src;
>  
> -      /* Constant propagation.  */
> -      if (cprop_constant_p (src))
> -	{
> -          if (constprop_register (reg_used, src, insn))
> +	  /* Constant propagation.  */
> +	  if (src_cst && cprop_constant_p (src_cst)
> +	      && constprop_register (reg_used, src_cst, insn))
>  	    {
>  	      changed_this_round = changed = 1;
>  	      global_const_prop_count++;
> @@ -1087,18 +1086,16 @@ retry:
>  			   "GLOBAL CONST-PROP: Replacing reg %d in ", regno);
>  		  fprintf (dump_file, "insn %d with constant ",
>  			   INSN_UID (insn));
> -		  print_rtl (dump_file, src);
> +		  print_rtl (dump_file, src_cst);
>  		  fprintf (dump_file, "\n");
>  		}
>  	      if (insn->deleted ())
>  		return 1;
>  	    }
> -	}
> -      else if (REG_P (src)
> -	       && REGNO (src) >= FIRST_PSEUDO_REGISTER
> -	       && REGNO (src) != regno)
> -	{
> -	  if (try_replace_reg (reg_used, src, insn))
> +	  else if (src_reg && REG_P (src_reg)
> +		   && REGNO (src_reg) >= FIRST_PSEUDO_REGISTER
> +		   && REGNO (src_reg) != regno
> +		   && try_replace_reg (reg_used, src_reg, insn))
>  	    {
>  	      changed_this_round = changed = 1;
>  	      global_copy_prop_count++;
> @@ -1107,22 +1104,20 @@ retry:
>  		  fprintf (dump_file,
>  			   "GLOBAL COPY-PROP: Replacing reg %d in insn %d",
>  			   regno, INSN_UID (insn));
> -		  fprintf (dump_file, " with reg %d\n", REGNO (src));
> +		  fprintf (dump_file, " with reg %d\n", REGNO (src_reg));
>  		}
>  
>  	      /* The original insn setting reg_used may or may not now be
>  		 deletable.  We leave the deletion to DCE.  */
> -	      /* FIXME: If it turns out that the insn isn't deletable,
> -		 then we may have unnecessarily extended register lifetimes
> +	      /* FIXME: If it turns out that the insn isn't deletable, then we
> +		 then we may have unnecessarily extended register lifetimes and
>  		 and made things worse.  */
>  	    }
>  	}
> -
> -      /* If try_replace_reg simplified the insn, the regs found
> -	 by find_used_regs may not be valid anymore.  Start over.  */
> -      if (changed_this_round)
> -	goto retry;
>      }
> +  /* If try_replace_reg simplified the insn, the regs found
> +     by find_used_regs may not be valid anymore.  Start over.  */
> +  while (changed_this_round);
>  
>    if (changed && DEBUG_INSN_P (insn))
>      return 0;
> diff --git a/gcc/testsuite/gcc.target/arm/pr64616.c b/gcc/testsuite/gcc.target/arm/pr64616.c
> new file mode 100644
> index 0000000..c686ffa
> --- /dev/null
> +++ b/gcc/testsuite/gcc.target/arm/pr64616.c
> @@ -0,0 +1,14 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2" } */
> +
> +int f (int);
> +unsigned int glob;
> +
> +void
> +g ()
> +{
> +  while (f (glob));
> +  glob = 5;
> +}
> +
> +/* { dg-final { scan-assembler-times "ldr" 2 } } */
> 
> Is this ok for stage1?
> 
> Best regards,
> 
> Thomas
> 
> 
> 
>

On Mon, Feb 16, 2015 at 11:26 AM, Thomas Preud'homme
<thomas.preudhomme@arm.com> wrote:
> Hi,
>
> The RTL cprop pass in GCC operates by doing a local constant/copy propagation first and then a global one. In the local one, if a constant cannot be propagated (eg. due to constraints of the destination instruction) a copy propagation is done instead. However, at the global level copy propagation is only tried if no constant can be propagated, ie. if a constant can be propagated but the constraints of the destination instruction forbids it, no copy propagation will be tried. This patch fixes this issue. This solves the redundant ldr problem in GCC32RM-439.
>

This would address https://gcc.gnu.org/bugzilla/show_bug.cgi?id=34503#c4

I'll have a look at the patch tonight.

Ciao!
Seven

On Mon, Feb 16, 2015 at 11:26 AM, Thomas Preud'homme wrote:

>  /* Subroutine of cprop_insn that tries to propagate constants into
> @@ -1044,40 +1042,41 @@ cprop_insn (rtx_insn *insn)

> -      /* Constant propagation.  */
> -      if (cprop_constant_p (src))
> -       {
> -          if (constprop_register (reg_used, src, insn))
> +         /* Constant propagation.  */
> +         if (src_cst && cprop_constant_p (src_cst)
> +             && constprop_register (reg_used, src_cst, insn))
>             {
>               changed_this_round = changed = 1;
>               global_const_prop_count++;

The cprop_constant_p test is redundant, you only have non-NULL src_cst
if it is a cprop_constant_p (as you test for it in find_avail_set()).


> @@ -1087,18 +1086,16 @@ retry:
>                            "GLOBAL CONST-PROP: Replacing reg %d in ", regno);
>                   fprintf (dump_file, "insn %d with constant ",
>                            INSN_UID (insn));
> -                 print_rtl (dump_file, src);
> +                 print_rtl (dump_file, src_cst);
>                   fprintf (dump_file, "\n");
>                 }
>               if (insn->deleted ())
>                 return 1;
>             }
> -       }
> -      else if (REG_P (src)
> -              && REGNO (src) >= FIRST_PSEUDO_REGISTER
> -              && REGNO (src) != regno)
> -       {
> -         if (try_replace_reg (reg_used, src, insn))
> +         else if (src_reg && REG_P (src_reg)
> +                  && REGNO (src_reg) >= FIRST_PSEUDO_REGISTER
> +                  && REGNO (src_reg) != regno
> +                  && try_replace_reg (reg_used, src_reg, insn))

Likewise for the REG_P and ">= FIRST_PSEUDO_REGISTER" tests here (with
the equivalent and IMHO preferable HARD_REGISTER_P test in
find_avail_set()).


Looks good to me otherwise.

Ciao!
Steven

> From: Steven Bosscher [mailto:stevenb.gcc@gmail.com]
> Sent: Tuesday, February 17, 2015 4:19 AM
> To: Thomas Preud'homme
> Cc: GCC Patches; Richard Biener
> Subject: Re: [PATCH, GCC, stage1] Fallback to copy-prop if constant-prop
> not possible
> 
> On Mon, Feb 16, 2015 at 11:26 AM, Thomas Preud'homme wrote:
> 
> >  /* Subroutine of cprop_insn that tries to propagate constants into
> > @@ -1044,40 +1042,41 @@ cprop_insn (rtx_insn *insn)
> 
> > -      /* Constant propagation.  */
> > -      if (cprop_constant_p (src))
> > -       {
> > -          if (constprop_register (reg_used, src, insn))
> > +         /* Constant propagation.  */
> > +         if (src_cst && cprop_constant_p (src_cst)
> > +             && constprop_register (reg_used, src_cst, insn))
> >             {
> >               changed_this_round = changed = 1;
> >               global_const_prop_count++;
> 
> The cprop_constant_p test is redundant, you only have non-NULL
> src_cst
> if it is a cprop_constant_p (as you test for it in find_avail_set()).

Ack.

> 
> 
> > @@ -1087,18 +1086,16 @@ retry:
> >                            "GLOBAL CONST-PROP: Replacing reg %d in ", regno);
> >                   fprintf (dump_file, "insn %d with constant ",
> >                            INSN_UID (insn));
> > -                 print_rtl (dump_file, src);
> > +                 print_rtl (dump_file, src_cst);
> >                   fprintf (dump_file, "\n");
> >                 }
> >               if (insn->deleted ())
> >                 return 1;
> >             }
> > -       }
> > -      else if (REG_P (src)
> > -              && REGNO (src) >= FIRST_PSEUDO_REGISTER
> > -              && REGNO (src) != regno)
> > -       {
> > -         if (try_replace_reg (reg_used, src, insn))
> > +         else if (src_reg && REG_P (src_reg)
> > +                  && REGNO (src_reg) >= FIRST_PSEUDO_REGISTER
> > +                  && REGNO (src_reg) != regno
> > +                  && try_replace_reg (reg_used, src_reg, insn))
> 
> Likewise for the REG_P and ">= FIRST_PSEUDO_REGISTER" tests here
> (with
> the equivalent and IMHO preferable HARD_REGISTER_P test in
> find_avail_set()).

I'm not sure I follow you here. First, it seems to me that the equivalent
test is rather REG_P && !HARD_REGISTER_P since here it checks if it's
a pseudo register.

Then, do you mean the test can be simply removed because of the
REG_P && !HARD_REGISTER_P in hash_scan_set () called indirectly by
compute_hash_table () when called in one_cprop_pass () before any
cprop_insn ()? Or do you mean I should move the check in
find_avail_set ()?

Best regards,

Thomas

Ping?

> From: gcc-patches-owner@gcc.gnu.org [mailto:gcc-patches-
> owner@gcc.gnu.org] On Behalf Of Thomas Preud'homme

[SNIP]

> >
> > Likewise for the REG_P and ">= FIRST_PSEUDO_REGISTER" tests here
> > (with
> > the equivalent and IMHO preferable HARD_REGISTER_P test in
> > find_avail_set()).
> 
> I'm not sure I follow you here. First, it seems to me that the equivalent
> test is rather REG_P && !HARD_REGISTER_P since here it checks if it's
> a pseudo register.
> 
> Then, do you mean the test can be simply removed because of the
> REG_P && !HARD_REGISTER_P in hash_scan_set () called indirectly by
> compute_hash_table () when called in one_cprop_pass () before any
> cprop_insn ()? Or do you mean I should move the check in
> find_avail_set ()?
> 
> Best regards,
> 
> Thomas
> 
> 
> 
>

On 02/16/2015 03:26 AM, Thomas Preud'homme wrote:
> Hi,
>
> The RTL cprop pass in GCC operates by doing a local constant/copy propagation first and then a global one. In the local one, if a constant cannot be propagated (eg. due to constraints of the destination instruction) a copy propagation is done instead. However, at the global level copy propagation is only tried if no constant can be propagated, ie. if a constant can be propagated but the constraints of the destination instruction forbids it, no copy propagation will be tried. This patch fixes this issue. This solves the redundant ldr problem in GCC32RM-439.
>
> ChangeLog entries are as follows:
>
> *** gcc/ChangeLog ***
>
> 2015-01-21 Thomas Preud'homme thomas.preudhomme@arm.com
>
>      * cprop.c (find_avail_set): Return up to two sets, one whose source is
>      a register and one whose source is a constant.  Sets are returned in
>      an array passed as parameter rather than as a return value.
>      (cprop_insn): Use a do while loop rather than a goto.  Try each of the
>      sets returned by find_avail_set, starting with the one whose source is
>      a constant.
>
>
> *** gcc/testsuite/ChangeLog ***
>
> 2015-01-21 Thomas Preud'homme thomas.preudhomme@arm.com
>
>      * gcc.target/arm/pr64616.c: New file.
Thomas,

I know there were several followups between Steven and yourself.  With 
stage1 now open, can you post a final version and do a final 
bootstrap/test with it?

Thanks,
jeff

> From: Jeff Law [mailto:law@redhat.com]
> Sent: Monday, April 13, 2015 8:48 PM
> Thomas,
> 
> I know there were several followups between Steven and yourself.
> With
> stage1 now open, can you post a final version and do a final
> bootstrap/test with it?

Sure, I'm testing it right now. Sorry for not doing it earlier, I wasn't sure what
constitute "too much disruption" as per GCC 6.0 Status Report email.

Best regards,

Thomas