Re: cprop "fix"

Re: cprop "fix"

[John David Anglin]

On Sat, Jul 13, 2002 at 08:49:02PM +0200, Jan Hubicka wrote:
>       * gcse.c: Include cselib.h
>       (constptop_register): Break out from ...
>       (cprop_insn): ... here; kill basic_block argument.
>       (do_local_cprop, local_cprop_pass): New functions.
>       (one_cprop_pass): Call local_cprop_pass.

I have identified the above patch as causing the failure of
gcc-torture/execute/980505-1.c under hppa-linux and other hppa
ports at -O2 and above.  It appears to "cprop" the return value
from the second call to f(x).

Dave
-- 
J. David Anglin                                  dave.anglin@nrc.ca
National Research Council of Canada              (613) 990-0752 (FAX: 952-6605)

Re: cprop "fix"

[Richard Henderson]

On Sat, Jul 13, 2002 at 08:49:02PM +0200, Jan Hubicka wrote:
> 	* gcse.c: Include cselib.h
> 	(constptop_register): Break out from ...
> 	(cprop_insn): ... here; kill basic_block argument.
> 	(do_local_cprop, local_cprop_pass): New functions.
> 	(one_cprop_pass): Call local_cprop_pass.

Ok.


r~

Re: cprop "fix"

[Jan Hubicka]

> Jan Hubicka wrote:
> 
> > It does basically same as 386 version - slightly more PRE improvements
> > as PRE does not have to work around parallels as i386 compiler does.
> > 
> > I can't benchmark, as the machine is busy by something else :)
> > But the patch has passed full bootstrap and regtesting on that machine
> > as well, so hope the try_replace_reg works as supposed to now.
> 
> Hmmm, yes, thanks, but are you going to commit the stuff, or am I better
> off just aplying it to the current trunk and see what it buys us ?

I am waiting for Richard's "OK" if possible :)

I have the SPEC results with and without patch as I noted earlier, I can
dig out the full table.  It brings about 1% improvement to SPECint and
3% to SPECfp in the second case all comming from single test, so I think
it is quite effective.

Honza
> 
> Thanks in advance,
> 
> -- 
> Toon Moene - mailto:toon@moene.indiv.nluug.nl - phoneto: +31 346 214290
> Saturnushof 14, 3738 XG  Maartensdijk, The Netherlands
> Maintainer, GNU Fortran 77: http://gcc.gnu.org/onlinedocs/g77_news.html
> Join GNU Fortran 95: http://g95.sourceforge.net/ (under construction)

Re: cprop "fix"

[Toon Moene]

Jan Hubicka wrote:

> It does basically same as 386 version - slightly more PRE improvements
> as PRE does not have to work around parallels as i386 compiler does.
> 
> I can't benchmark, as the machine is busy by something else :)
> But the patch has passed full bootstrap and regtesting on that machine
> as well, so hope the try_replace_reg works as supposed to now.

Hmmm, yes, thanks, but are you going to commit the stuff, or am I better
off just aplying it to the current trunk and see what it buys us ?

Thanks in advance,

-- 
Toon Moene - mailto:toon@moene.indiv.nluug.nl - phoneto: +31 346 214290
Saturnushof 14, 3738 XG  Maartensdijk, The Netherlands
Maintainer, GNU Fortran 77: http://gcc.gnu.org/onlinedocs/g77_news.html
Join GNU Fortran 95: http://g95.sourceforge.net/ (under construction)

Re: cprop "fix"

[Jan Hubicka]

> Jan Hubicka wrote:
> 
> > Just FYI, I've got to stage2 of alpha bootstrap, so the bug went away.
> > I will try to get some data how effective the stuff is on Alpha :)
> 
> ... and then, nothing happens (reminds me of Catweasle).
> 
> What's up, Doc ?

It does basically same as 386 version - slightly more PRE improvements
as PRE does not have to work around parallels as i386 compiler does.

I can't benchmark, as the machine is busy by something else :)
But the patch has passed full bootstrap and regtesting on that machine
as well, so hope the try_replace_reg works as supposed to now.

Honza
> 
> -- 
> Toon Moene - mailto:toon@moene.indiv.nluug.nl - phoneto: +31 346 214290
> Saturnushof 14, 3738 XG  Maartensdijk, The Netherlands
> Maintainer, GNU Fortran 77: http://gcc.gnu.org/onlinedocs/g77_news.html
> Join GNU Fortran 95: http://g95.sourceforge.net/ (under construction)

Re: cprop "fix"

[Toon Moene]

Jan Hubicka wrote:

> Just FYI, I've got to stage2 of alpha bootstrap, so the bug went away.
> I will try to get some data how effective the stuff is on Alpha :)

... and then, nothing happens (reminds me of Catweasle).

What's up, Doc ?

-- 
Toon Moene - mailto:toon@moene.indiv.nluug.nl - phoneto: +31 346 214290
Saturnushof 14, 3738 XG  Maartensdijk, The Netherlands
Maintainer, GNU Fortran 77: http://gcc.gnu.org/onlinedocs/g77_news.html
Join GNU Fortran 95: http://g95.sourceforge.net/ (under construction)

Re: cprop "fix"

[Jan Hubicka]

> > On Wed, Jul 17, 2002 at 06:35:35PM +0200, Jan Hubicka wrote:
> > > And uhm, did you checked actually after the try_replace_rtx fix?
> > > I am not sure I did commited it or whether it is still in testing.  I
> > > think the second.
> > 
> > I guess not.  I thought it had gone in.
> 
> It is not there.  I am just about to commit it.

Just FYI, I've got to stage2 of alpha bootstrap, so the bug went away.
I will try to get some data how effective the stuff is on Alpha :)

Honza
> 
> Honza
> > 
> > 
> > r~

Re: cprop "fix"

[Jan Hubicka]

> On Wed, Jul 17, 2002 at 06:35:35PM +0200, Jan Hubicka wrote:
> > And uhm, did you checked actually after the try_replace_rtx fix?
> > I am not sure I did commited it or whether it is still in testing.  I
> > think the second.
> 
> I guess not.  I thought it had gone in.

It is not there.  I am just about to commit it.

Honza
> 
> 
> r~

Re: cprop "fix"

[Richard Henderson]

On Wed, Jul 17, 2002 at 06:35:35PM +0200, Jan Hubicka wrote:
> And uhm, did you checked actually after the try_replace_rtx fix?
> I am not sure I did commited it or whether it is still in testing.  I
> think the second.

I guess not.  I thought it had gone in.


r~

Re: cprop "fix"

[Jan Hubicka]

> > On Sat, Jul 13, 2002 at 08:49:02PM +0200, Jan Hubicka wrote:
> > > The attached patch "fixes" our cprop implementation by adding the local
> > > counterpart that is really easy given the infrastructure we developed.
> > 
> > Makes sense, generally.
> > 
> > Your implementation does not terminate building unwind-dw2-fde-glibc.c
> > on alpha though.
> 
> Can I get the preprocessed file?
> It should be the case that try_repalace_reg is still returning false
> positives.  It is related to apply_change group stuff we've discussed.
> I believe we can simply add num_pending_changes () function to make this
> stuff easier.  Sounds sane?

And uhm, did you checked actually after the try_replace_rtx fix?
I am not sure I did commited it or whether it is still in testing.  I
think the second.

Honza
> 
> Honza
> > 
> > 
> > r~

Re: cprop "fix"

[Jan Hubicka]

> On Sat, Jul 13, 2002 at 08:49:02PM +0200, Jan Hubicka wrote:
> > The attached patch "fixes" our cprop implementation by adding the local
> > counterpart that is really easy given the infrastructure we developed.
> 
> Makes sense, generally.
> 
> Your implementation does not terminate building unwind-dw2-fde-glibc.c
> on alpha though.

Can I get the preprocessed file?
It should be the case that try_repalace_reg is still returning false
positives.  It is related to apply_change group stuff we've discussed.
I believe we can simply add num_pending_changes () function to make this
stuff easier.  Sounds sane?

Honza
> 
> 
> r~

Re: cprop "fix"

[Richard Henderson]

On Sat, Jul 13, 2002 at 08:49:02PM +0200, Jan Hubicka wrote:
> The attached patch "fixes" our cprop implementation by adding the local
> counterpart that is really easy given the infrastructure we developed.

Makes sense, generally.

Your implementation does not terminate building unwind-dw2-fde-glibc.c
on alpha though.


r~

Re: cprop "fix"

[Paolo Carlini]

Jan Hubicka wrote:

>Hi,
>for record, it makes 3 point difference from specint (1%) and 8 point
>difference for specfp (3%) according to Andreas' tests.
>
Great!

Paolo.

Re: cprop "fix"

[Jan Hubicka]

Hi,
for record, it makes 3 point difference from specint (1%) and 8 point
difference for specfp (3%) according to Andreas' tests.

Honza

cprop "fix"

[Jan Hubicka]

Hi,
when the copy propagation is formulated in literature, it always contain local
and global passes.  Our cprop does only the global stuff, probably assuming
that local CSE will do rest of job.  It does not - the main problem is that CSE
does contain register pressure reduction heuristics that makes it sometimes to
decide to use new register instead of original after copy instruction defacto
reverting effect of copy propagation.  Since CSE looses track of things on
complex CFG, it does so partly making both copies to be alive increasing
register pressure.  

In the past I experimented with patch disabling the heuristics but it
does waste code quallity and additionally PRE pass is seriously crippled
by this fact especially in the second iteration, when redundant reg-reg
copies are more common and thus expressions appears to be different when
they are not.

The attached patch "fixes" our cprop implementation by adding the local
counterpart that is really easy given the infrastructure we developed.
It is effective on about any more complex function. For instance on
combine.c there is done 492 constant propagation instead of 130 and
1141 copy propagation instead of 486.  Additionally 862 redundant
expressions are elliminated instead of 712 and in combine_simplify_rtx
after GCSE 216 trivially dead instructions are killed, next 5 after
local CSE pass, while oriiginaly 15 instructions are killed after GCSE
and 80 after local CSE. (I believe the local CSE pass run just after
GCSE can be elliminated now saving compilation time).

The results on code size are bit smaller - about 800 instructions for
combine.s, still I believe it is good thing to do and additionally if we
break up GCSE I think we should run cprop before first local CSE and
cleanup the CFG to elliminate dead and unreachable code before the slow
CSE beast.

I've also implemented the simple local CSE for a experiment but it is not that
effective doing just about 60 substitutions in combine. All of them seems to be
of the form:
(set (mem) (reg X))
(set (reg Y) (same mem))
I am surprised our local CSE don't know how to handle it, but I will check it
separately.

Honza

Sat Jul 13 20:31:17 CEST 2002  Jan Hubicka  <jh@suse.cz>
	* gcse.c: Include cselib.h
	(constptop_register): Break out from ...
	(cprop_insn): ... here; kill basic_block argument.
	(do_local_cprop, local_cprop_pass): New functions.
	(one_cprop_pass): Call local_cprop_pass.
Index: gcse.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/gcse.c,v
retrieving revision 1.208
diff -c -3 -p -r1.208 gcse.c
*** gcse.c	28 Jun 2002 23:41:19 -0000	1.208
--- gcse.c	13 Jul 2002 18:30:07 -0000
*************** Software Foundation, 59 Temple Place - S
*** 162,167 ****
--- 162,168 ----
  #include "except.h"
  #include "ggc.h"
  #include "params.h"
+ #include "cselib.h"
  
  #include "obstack.h"
  #define obstack_chunk_alloc gmalloc
*************** static int cprop_jump		PARAMS ((basic_bl
*** 613,621 ****
  static void mems_conflict_for_gcse_p PARAMS ((rtx, rtx, void *));
  static int load_killed_in_block_p    PARAMS ((basic_block, int, rtx, int));
  static void canon_list_insert        PARAMS ((rtx, rtx, void *));
! static int cprop_insn		PARAMS ((basic_block, rtx, int));
  static int cprop		PARAMS ((int));
  static int one_cprop_pass	PARAMS ((int, int));
  static struct expr *find_bypass_set PARAMS ((int, int));
  static int bypass_block		    PARAMS ((basic_block, rtx, rtx));
  static int bypass_conditional_jumps PARAMS ((void));
--- 614,623 ----
  static void mems_conflict_for_gcse_p PARAMS ((rtx, rtx, void *));
  static int load_killed_in_block_p    PARAMS ((basic_block, int, rtx, int));
  static void canon_list_insert        PARAMS ((rtx, rtx, void *));
! static int cprop_insn		PARAMS ((rtx, int));
  static int cprop		PARAMS ((int));
  static int one_cprop_pass	PARAMS ((int, int));
+ static bool constprop_register	PARAMS ((rtx, rtx, rtx, int));
  static struct expr *find_bypass_set PARAMS ((int, int));
  static int bypass_block		    PARAMS ((basic_block, rtx, rtx));
  static int bypass_conditional_jumps PARAMS ((void));
*************** static void free_insn_expr_list_list	PAR
*** 701,706 ****
--- 703,710 ----
  static void clear_modify_mem_tables	PARAMS ((void));
  static void free_modify_mem_tables	PARAMS ((void));
  static rtx gcse_emit_move_after		PARAMS ((rtx, rtx, rtx));
+ static bool do_local_cprop		PARAMS ((rtx, rtx, int));
+ static void local_cprop_pass		PARAMS ((int));
  \f
  /* Entry point for global common subexpression elimination.
     F is the first instruction in the function.  */
*************** cprop_jump (bb, setcc, jump, from, src)
*** 4149,4160 ****
    return 1;
  }
  
  /* Perform constant and copy propagation on INSN.
     The result is non-zero if a change was made.  */
  
  static int
! cprop_insn (bb, insn, alter_jumps)
!      basic_block bb;
       rtx insn;
       int alter_jumps;
  {
--- 4153,4200 ----
    return 1;
  }
  
+ static bool
+ constprop_register (insn, from, to, alter_jumps)
+      rtx insn;
+      rtx from;
+      rtx to;
+      int alter_jumps;
+ {
+   rtx sset;
+ 
+   /* Check for reg or cc0 setting instructions followed by
+      conditional branch instructions first.  */
+   if (alter_jumps
+       && (sset = single_set (insn)) != NULL
+       && any_condjump_p (NEXT_INSN (insn)) && onlyjump_p (NEXT_INSN (insn)))
+     {
+       rtx dest = SET_DEST (sset);
+       if ((REG_P (dest) || CC0_P (dest))
+ 	  && cprop_jump (BLOCK_FOR_INSN (insn), insn, NEXT_INSN (insn), from, to))
+ 	return 1;
+     }
+ 
+   /* Handle normal insns next.  */
+   if (GET_CODE (insn) == INSN
+       && try_replace_reg (from, to, insn))
+     return 1;
+ 
+   /* Try to propagate a CONST_INT into a conditional jump.
+      We're pretty specific about what we will handle in this
+      code, we can extend this as necessary over time.
+ 
+      Right now the insn in question must look like
+      (set (pc) (if_then_else ...))  */
+   else if (alter_jumps && any_condjump_p (insn) && onlyjump_p (insn))
+     return cprop_jump (BLOCK_FOR_INSN (insn), NULL, insn, from, to);
+   return 0;
+ }
+ 
  /* Perform constant and copy propagation on INSN.
     The result is non-zero if a change was made.  */
  
  static int
! cprop_insn (insn, alter_jumps)
       rtx insn;
       int alter_jumps;
  {
*************** cprop_insn (bb, insn, alter_jumps)
*** 4207,4262 ****
        /* Constant propagation.  */
        if (CONSTANT_P (src))
  	{
! 	  rtx sset;
! 
! 	  /* Check for reg or cc0 setting instructions followed by
! 	     conditional branch instructions first.  */
! 	  if (alter_jumps
! 	      && (sset = single_set (insn)) != NULL
! 	      && any_condjump_p (NEXT_INSN (insn))
! 	      && onlyjump_p (NEXT_INSN (insn)))
! 	    {
! 	      rtx dest = SET_DEST (sset);
! 	      if ((REG_P (dest) || CC0_P (dest))
! 		  && cprop_jump (bb, insn, NEXT_INSN (insn),
! 				 reg_used->reg_rtx, src))
! 		{
! 		  changed = 1;
! 		  break;
! 		}
! 	    }
! 
! 	  /* Handle normal insns next.  */
! 	  if (GET_CODE (insn) == INSN
! 	      && try_replace_reg (reg_used->reg_rtx, src, insn))
  	    {
  	      changed = 1;
  	      const_prop_count++;
  	      if (gcse_file != NULL)
  		{
! 		  fprintf (gcse_file, "CONST-PROP: Replacing reg %d in ",
! 			   regno);
! 		  fprintf (gcse_file, "insn %d with constant ",
! 			   INSN_UID (insn));
  		  print_rtl (gcse_file, src);
  		  fprintf (gcse_file, "\n");
  		}
- 
- 	      /* The original insn setting reg_used may or may not now be
- 		 deletable.  We leave the deletion to flow.  */
  	    }
- 
- 	  /* Try to propagate a CONST_INT into a conditional jump.
- 	     We're pretty specific about what we will handle in this
- 	     code, we can extend this as necessary over time.
- 
- 	     Right now the insn in question must look like
- 	     (set (pc) (if_then_else ...))  */
- 	  else if (alter_jumps
- 		   && any_condjump_p (insn)
- 		   && onlyjump_p (insn))
- 	    changed |= cprop_jump (bb, NULL, insn, reg_used->reg_rtx, src);
- 
  	}
        else if (GET_CODE (src) == REG
  	       && REGNO (src) >= FIRST_PSEUDO_REGISTER
--- 4247,4264 ----
        /* Constant propagation.  */
        if (CONSTANT_P (src))
  	{
!           if (constprop_register (insn, reg_used->reg_rtx, src, alter_jumps))
  	    {
  	      changed = 1;
  	      const_prop_count++;
  	      if (gcse_file != NULL)
  		{
! 		  fprintf (gcse_file, "GLOBAL CONST-PROP: Replacing reg %d in ", regno);
! 		  fprintf (gcse_file, "insn %d with constant ", INSN_UID (insn));
  		  print_rtl (gcse_file, src);
  		  fprintf (gcse_file, "\n");
  		}
  	    }
  	}
        else if (GET_CODE (src) == REG
  	       && REGNO (src) >= FIRST_PSEUDO_REGISTER
*************** cprop_insn (bb, insn, alter_jumps)
*** 4268,4274 ****
  	      copy_prop_count++;
  	      if (gcse_file != NULL)
  		{
! 		  fprintf (gcse_file, "COPY-PROP: Replacing reg %d in insn %d",
  			   regno, INSN_UID (insn));
  		  fprintf (gcse_file, " with reg %d\n", REGNO (src));
  		}
--- 4270,4276 ----
  	      copy_prop_count++;
  	      if (gcse_file != NULL)
  		{
! 		  fprintf (gcse_file, "GLOBAL COPY-PROP: Replacing reg %d in insn %d",
  			   regno, INSN_UID (insn));
  		  fprintf (gcse_file, " with reg %d\n", REGNO (src));
  		}
*************** cprop_insn (bb, insn, alter_jumps)
*** 4285,4290 ****
--- 4287,4382 ----
    return changed;
  }
  
+ static bool
+ do_local_cprop (x, insn, alter_jumps)
+      rtx x;
+      rtx insn;
+      int alter_jumps;
+ {
+   rtx newreg = NULL, newcnst = NULL;
+ 
+   /* Rule out USE instructions and ASM statements as we don't want to change the hard
+      registers mentioned.  */
+   if (GET_CODE (x) == REG
+       && (REGNO (x) >= FIRST_PSEUDO_REGISTER
+           || (GET_CODE (PATTERN (insn)) != USE && asm_noperands (PATTERN (insn)) < 0)))
+     {
+       cselib_val *val = cselib_lookup (x, GET_MODE (x), 0);
+       struct elt_loc_list *l;
+ 
+       if (!val)
+ 	return false;
+       for (l = val->locs; l; l = l->next)
+ 	{
+ 	  rtx this_rtx = l->loc;
+ 	  if (CONSTANT_P (this_rtx))
+ 	    newcnst = this_rtx;
+ 	  if (REG_P (this_rtx) && REGNO (this_rtx) >= FIRST_PSEUDO_REGISTER)
+ 	    newreg = this_rtx;
+ 	}
+       if (newcnst && constprop_register (insn, x, newcnst, alter_jumps))
+ 	{
+ 	  if (gcse_file != NULL)
+ 	    {
+ 	      fprintf (gcse_file, "LOCAL CONST-PROP: Replacing reg %d in ",
+ 		       REGNO (x));
+ 	      fprintf (gcse_file, "insn %d with constant ",
+ 		       INSN_UID (insn));
+ 	      print_rtl (gcse_file, newcnst);
+ 	      fprintf (gcse_file, "\n");
+ 	    }
+ 	  const_prop_count++;
+ 	  return true;
+ 	}
+       else if (newreg && newreg != x && try_replace_reg (x, newreg, insn))
+ 	{
+ 	  if (gcse_file != NULL)
+ 	    {
+ 	      fprintf (gcse_file,
+ 		       "LOCAL COPY-PROP: Replacing reg %d in insn %d",
+ 		       REGNO (x), INSN_UID (insn));
+ 	      fprintf (gcse_file, " with reg %d\n", REGNO (newreg));
+ 	    }
+ 	  copy_prop_count++;
+ 	  return true;
+ 	}
+     }
+   return false;
+ }
+ 
+ static void
+ local_cprop_pass (alter_jumps)
+      int alter_jumps;
+ {
+   rtx insn;
+   struct reg_use *reg_used;
+ 
+   cselib_init ();
+   for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
+     {
+       if (INSN_P (insn))
+ 	{
+ 	  rtx note = find_reg_equal_equiv_note (insn);
+ 
+ 	  do
+ 	    {
+ 	      reg_use_count = 0;
+ 	      note_uses (&PATTERN (insn), find_used_regs, NULL);
+ 	      if (note)
+ 		find_used_regs (&XEXP (note, 0), NULL);
+ 
+ 	      for (reg_used = &reg_use_table[0]; reg_use_count > 0;
+ 		   reg_used++, reg_use_count--)
+ 		if (do_local_cprop (reg_used->reg_rtx, insn, alter_jumps))
+ 		  break;
+ 	    }
+ 	  while (reg_use_count);
+ 	}
+       cselib_process_insn (insn);
+     }
+   cselib_finish ();
+ }
+ 
  /* Forward propagate copies.  This includes copies and constants.  Return
     non-zero if a change was made.  */
  
*************** cprop (alter_jumps)
*** 4316,4322 ****
  	   insn = NEXT_INSN (insn))
  	if (INSN_P (insn))
  	  {
! 	    changed |= cprop_insn (bb, insn, alter_jumps);
  
  	    /* Keep track of everything modified by this insn.  */
  	    /* ??? Need to be careful w.r.t. mods done to INSN.  Don't
--- 4408,4414 ----
  	   insn = NEXT_INSN (insn))
  	if (INSN_P (insn))
  	  {
! 	    changed |= cprop_insn (insn, alter_jumps);
  
  	    /* Keep track of everything modified by this insn.  */
  	    /* ??? Need to be careful w.r.t. mods done to INSN.  Don't
*************** one_cprop_pass (pass, alter_jumps)
*** 4346,4351 ****
--- 4438,4445 ----
    const_prop_count = 0;
    copy_prop_count = 0;
  
+   local_cprop_pass (alter_jumps);
+ 
    alloc_set_hash_table (max_cuid);
    compute_set_hash_table ();
    if (gcse_file)