Ping: PR25514: A problem with note distribution in combine

[Richard Sandiford <richard at codesourcery dot com>]

Ping

http://gcc.gnu.org/ml/gcc-patches/2006-04/msg00958.html

Richard Sandiford <richard@codesourcery.com> writes:
> This patch fixes PR rtl-optimization/25514.  The PR is closely
> related to PR22002, the patch for which was posted here:
>
>     http://gcc.gnu.org/ml/gcc-patches/2005-11/msg00598.html
>
> In the testcase below, the else block looks like this before combine:
>
>     A: (set (reg tmp) (reg node))
>          REG_EQUAL (symbol_ref "global_list")
>          REG_DEAD (reg node)
>
>     B: (set (reg node) (reg next))
>          REG_DEAD (reg next)
>
>     C: (set (mem (const (plus (symbol_ref "global_list") (const_int 4))))
>             (mem (plus (reg node) (const_int 4))))
>
>     D: (set (mem (reg tmp)) (mem (reg node)))
>          REG_DEAD (reg node)
>
> Combine considers combining A and D, but rightly declines because of the
> assignment to NODE in B.  It then replaces the right hand side of A with
> the REG_EQUAL note and tries again.  This time it succeeds with:
>
>     D': (set (mem (symbol_ref "global_list"))
>              (mem (reg node)))
>
> distribute_notes then has to update the live range of NODE that previously
> ended at A.
>
> So far this is the same as the situation Alan described.  The crucial
> difference is that in this case, the combined instruction reads the
> new value of the REG_DEAD register, whereas Alan's patch only handles
> the case where the REG_DEAD register is not used in the combined
> instruction at all.
>
> Alan added the comment:
>
>               /* You might think you could search back from FROM_INSN
>                  rather than from I3, but combine tries to split invalid
>                  combined instructions.  This can result in the old I2
>                  or I1 moving later in the insn sequence.  */
>               for (tem = PREV_INSN (tem); place == 0; tem = PREV_INSN (tem))
>
> But I don't quite follow that.  I think the idea of the original code
> was this:
>
>   (1) The REG_DEAD note refers to something that was used in the
>       right hand side of the old FROM_INSN pattern (if FROM_INSN
>       is nonnull)
>
>   (2) The right hand side of that pattern has been combined into
>       what is now I3 and I2 (if the latter is nonnull)
>
>   (3) The register used to die at FROM_INSN.
>
>   (4) Therefore, the register now dies at the last use before or
>       during I3.  If there is no such use, the definition of the
>       register is now unused.
>
>   (5) (4) implies searching back from I3 (== D') looking for the first
>       use or set of the REG_DEAD register.  If we find a use, we should
>       add the REG_DEAD note there.  If we find a set, we should try to
>       delete the set as dead, or add a REG_UNUSED note if that isn't
>       possible.
>
> The search described in (5) could be quite expensive, so
> distribute_notes has some straight-line code to handle common cases.
> One of the straight-line cases is where I3 itself uses the register.
> Having disposed of that, the main loop can start at the insn before
> I3 rather than I3 itself.
>
> Forgetting about the bug in hand, that approach seems correct to me,
> so I don't really see what the comment is trying to apologise for.
> Conceptually, the search really should start at I3.
>
> The problem of course is that (2) does not hold in this case.
> The original rhs of FROM_INSN (the one to which the REG_DEAD note
> applies) was _not_ used in the combination; a REG_EQUAL note was
> used instead.  Thus any use of the register after FROM_INSN
> cannot be part of the same live range.
>
> I therefore think we should base the start of the search on whether the
> REG_DEAD note refers to something that was combined (the usual case) or
> not (this case).  In the former case we start at I3, as now, and in the
> latter case we start before FROM_INSN.
>
> The patch uses a new global variable to distinguish the two cases.
> I know this isn't elegant, but I think it's simpler and faster
> than trying to propagate the information from combine_instructios
> by other means, and we already use global variables for other parts
> of the combiner state.
>
> I've tested this patch on m68k-linux-gnu on csl/coldfire-4_1 (it isn't
> possible to test Coldfire on mainline without unmerged patches).
> I've also run compile.exp=pr25514.c on an m68k-elf mainline
> crosscompiler before and after the patch to make sure it failed
> beforehand and passed afterwards.  Finally, I bootstrapped &
> regression-tested on i686-pc-linux-gnu.  OK to install?
>
> Richard
>
>
> 	PR rtl-optimization/25514
> 	* combine.c (replaced_rhs_insn): New variable.
> 	(combine_instructions): Set replaced_rhs_insn when trying to replace
> 	a SET_SRC with a REG_EQUAL note.
> 	(distribute_notes): Use replaced_rhs_insn when determining the live
> 	range of a REG_DEAD register.
>
> gcc/testsute
> 	* gcc.c-torture/compile/pr25514.c: New test.
>
> Index: gcc/testsuite/gcc.c-torture/compile/pr25514.c
> ===================================================================
> --- gcc/testsuite/gcc.c-torture/compile/pr25514.c	(revision 0)
> +++ gcc/testsuite/gcc.c-torture/compile/pr25514.c	(revision 0)
> @@ -0,0 +1,24 @@
> +struct node {
> +  struct node *next;
> +  int value;
> +};
> +
> +struct node *current_node, global_list;
> +
> +void
> +bar (void)
> +{
> +  struct node *node, *next;
> +
> +  node = current_node;
> +  next = node->next;
> +  if (node != &global_list)
> +    current_node = next;
> +  else
> +    {
> +      node = global_list.next;
> +      global_list.value = node->value;
> +      global_list.next = node->next;
> +    }
> +  foo (node);
> +}
> Index: gcc/combine.c
> ===================================================================
> --- gcc/combine.c	(revision 113248)
> +++ gcc/combine.c	(working copy)
> @@ -123,6 +123,11 @@ Software Foundation; either version 2, o
>  
>  static int total_attempts, total_merges, total_extras, total_successes;
>  
> +/* Sometimes combine tries to replace the right hand side of an insn
> +   with the value of a REG_EQUAL note.  This is the insn that has been
> +   so modified, or null if none.  */
> +
> +static rtx replaced_rhs_insn;
>  
>  /* Vector mapping INSN_UIDs to cuids.
>     The cuids are like uids but increase monotonically always.
> @@ -922,8 +927,10 @@ combine_instructions (rtx f, unsigned in
>  			 be deleted or recognized by try_combine.  */
>  		      rtx orig = SET_SRC (set);
>  		      SET_SRC (set) = note;
> +		      replaced_rhs_insn = temp;
>  		      next = try_combine (insn, temp, NULL_RTX,
>  					  &new_direct_jump_p);
> +		      replaced_rhs_insn = NULL;
>  		      if (next)
>  			goto retry;
>  		      SET_SRC (set) = orig;
> @@ -12085,7 +12092,15 @@ distribute_notes (rtx notes, rtx from_in
>  	  break;
>  
>  	case REG_DEAD:
> -	  /* If the register is used as an input in I3, it dies there.
> +	  /* If we replaced the right hand side of FROM_INSN with a
> +	     REG_EQUAL note, the original use of the dying register
> +	     will not have been combined into I3 and I2.  In such cases,
> +	     FROM_INSN is guaranteed to be the first of the combined
> +	     instructions, so we simply need to search back before
> +	     FROM_INSN for the previous use or set of this register,
> +	     then alter the notes there appropriately.
> +
> +	     If the register is used as an input in I3, it dies there.
>  	     Similarly for I2, if it is nonzero and adjacent to I3.
>  
>  	     If the register is not used as an input in either I3 or I2
> @@ -12099,30 +12114,30 @@ distribute_notes (rtx notes, rtx from_in
>  	     In both cases, we must search to see if we can find a previous
>  	     use of A and put the death note there.  */
>  
> -	  if (from_insn
> -	      && CALL_P (from_insn)
> -	      && find_reg_fusage (from_insn, USE, XEXP (note, 0)))
> -	    place = from_insn;
> -	  else if (reg_referenced_p (XEXP (note, 0), PATTERN (i3)))
> -	    place = i3;
> -	  else if (i2 != 0 && next_nonnote_insn (i2) == i3
> -		   && reg_referenced_p (XEXP (note, 0), PATTERN (i2)))
> -	    place = i2;
> -
> -	  if (place == 0
> -	      && (rtx_equal_p (XEXP (note, 0), elim_i2)
> -		  || rtx_equal_p (XEXP (note, 0), elim_i1)))
> -	    break;
> +	  if (from_insn && from_insn == replaced_rhs_insn)
> +	    tem = from_insn;
> +	  else
> +	    {
> +	      if (from_insn
> +		  && CALL_P (from_insn)
> +		  && find_reg_fusage (from_insn, USE, XEXP (note, 0)))
> +		place = from_insn;
> +	      else if (reg_referenced_p (XEXP (note, 0), PATTERN (i3)))
> +		place = i3;
> +	      else if (i2 != 0 && next_nonnote_insn (i2) == i3
> +		       && reg_referenced_p (XEXP (note, 0), PATTERN (i2)))
> +		place = i2;
> +	      else if (rtx_equal_p (XEXP (note, 0), elim_i2)
> +		       || rtx_equal_p (XEXP (note, 0), elim_i1))
> +		break;
> +	      tem = i3;
> +	    }
>  
>  	  if (place == 0)
>  	    {
>  	      basic_block bb = this_basic_block;
>  
> -	      /* You might think you could search back from FROM_INSN
> -		 rather than from I3, but combine tries to split invalid
> -		 combined instructions.  This can result in the old I2
> -		 or I1 moving later in the insn sequence.  */
> -	      for (tem = PREV_INSN (i3); place == 0; tem = PREV_INSN (tem))
> +	      for (tem = PREV_INSN (tem); place == 0; tem = PREV_INSN (tem))
>  		{
>  		  if (! INSN_P (tem))
>  		    {
> @@ -12222,22 +12237,6 @@ distribute_notes (rtx notes, rtx from_in
>  			   || (CALL_P (tem)
>  			       && find_reg_fusage (tem, USE, XEXP (note, 0))))
>  		    {
> -		      /* This may not be the correct place for the death
> -			 note if FROM_INSN is before TEM, and the reg is
> -			 set between FROM_INSN and TEM.  The reg might
> -			 die two or more times.  An existing death note
> -			 means we are looking at the wrong live range.  */
> -		      if (from_insn
> -			  && INSN_CUID (from_insn) < INSN_CUID (tem)
> -			  && find_regno_note (tem, REG_DEAD,
> -					      REGNO (XEXP (note, 0))))
> -			{
> -			  tem = from_insn;
> -			  if (tem == BB_HEAD (bb))
> -			    break;
> -			  continue;
> -			}
> -
>  		      place = tem;
>  
>  		      /* If we are doing a 3->2 combination, and we have a