Re: Update for cprop patch

[Bernd Schmidt <bernds at cygnus dot co dot uk>]

(Jeff, sorry for sending this twice - the first time I misspelt the
egcs-patches address)

Here's a new version of the patch.  Changes since the last one:
  - try to avoid entering obvious no-ops into the hash table
  - move the second oprs_not_set_p call into find_avail_set.  This function
    now guarantees that the rtx it returns can safely be substituted.

I left in the code to avoid infinite loops for now - I'd be happy to remove
it if I was convinced they can't happen anymore.

The patch compiles and passes make check on i686-linux with no additional
failures.  I also ran a benchmark which showed a very minor improvement.

Bernd

	* gcse.c (hash_scan_set): Treat SYMBOL_REFs like CONST_INTs.
	(find_avail_set): Follow chains of register-register copies.
	Use oprs_not_set_p to guarantee that the returned value can be
	substituted.
	(cprop_jump): New function, broken out of cprop_insn.
	(cprop_cc0_jump): New function.
	(cprop_insn): Treat SYMBOL_REFs like CONST_INTs.
	Break out new function cprop_jump and use it.
	Also use cprop_cc0_jump for machines with CC0.
	Don't verify the return value of find_avail_set with oprs_not_set_p.
	(cprop): Don't crash if cprop_insn turned the insn into a NOTE.

Index: gcse.c
===================================================================
RCS file: /egcs/carton/cvsfiles/egcs/gcc/gcse.c,v
retrieving revision 1.39
diff -u -p -r1.39 gcse.c
--- gcse.c	1999/06/03 00:19:42	1.39
+++ gcse.c	1999/07/16 09:56:45
@@ -511,6 +511,11 @@ static sbitmap *rd_kill, *rd_gen, *reach
 /* for available exprs */
 static sbitmap *ae_kill, *ae_gen, *ae_in, *ae_out;
 
+/* Structure used by copy/constant propagation.  */
+struct reg_use {
+  rtx reg_rtx;
+};
+
 
 static void compute_can_copy	  PROTO ((void));
 
@@ -574,6 +579,8 @@ static void compute_cprop_data	PROTO ((v
 static void find_used_regs	    PROTO ((rtx));
 static int try_replace_reg	    PROTO ((rtx, rtx, rtx));
 static struct expr *find_avail_set    PROTO ((int, rtx));
+static int cprop_jump			PROTO((rtx, rtx, struct reg_use *, rtx));
+static int cprop_cc0_jump		PROTO((rtx, struct reg_use *, rtx));
 static int cprop_insn		 PROTO ((rtx, int));
 static int cprop		      PROTO ((int));
 static int one_cprop_pass	     PROTO ((int, int));
@@ -1865,6 +1872,7 @@ hash_scan_set (pat, insn, set_p)
 		    && can_copy_p [GET_MODE (dest)])
 		   /* ??? CONST_INT:wip */
 		   || GET_CODE (src) == CONST_INT
+		   || GET_CODE (src) == SYMBOL_REF
 		   || GET_CODE (src) == CONST_DOUBLE)
 	       /* A copy is not available if its src or dest is subsequently
 		  modified.  Here we want to search from INSN+1 on, but
@@ -1915,7 +1923,11 @@ hash_scan_insn (insn, set_p, in_libcall_
      what's been modified.  */
 
   if (GET_CODE (pat) == SET && ! in_libcall_block)
-    hash_scan_set (pat, insn, set_p);
+    {
+      /* Ignore obvious no-ops.  */
+      if (SET_SRC (pat) != SET_DEST (pat))
+	hash_scan_set (pat, insn, set_p);
+    }
   else if (GET_CODE (pat) == PARALLEL)
     {
       int i;
@@ -3534,10 +3546,6 @@ compute_cprop_data ()
 
 /* Copy/constant propagation.  */
 
-struct reg_use {
-  rtx reg_rtx;
-};
-
 /* Maximum number of register uses in an insn that we handle.  */
 #define MAX_USES 8
 
@@ -3656,17 +3664,154 @@ find_avail_set (regno, insn)
      int regno;
      rtx insn;
 {
-  struct expr *set = lookup_set (regno, NULL_RTX);
+  int i;
+  /* SET1 contains the last set found that can be returned to the caller for
+     use in a substitution.  */
+  struct expr *set1 = 0;
 
-  while (set)
+  /* Limit the number of iterations, in case we run into a cycle.  */
+  for (i = 0; i < 5; i++)
     {
-      if (TEST_BIT (cprop_avin[BLOCK_NUM (insn)], set->bitmap_index))
+      rtx src;
+      struct expr *set = lookup_set (regno, NULL_RTX);
+
+      while (set)
+	{
+	  if (TEST_BIT (cprop_avin[BLOCK_NUM (insn)], set->bitmap_index))
+	    break;
+	  set = next_set (regno, set);
+	}
+      if (set == 0)
 	break;
-      set = next_set (regno, set);
+
+      if (GET_CODE (set->expr) != SET)
+	abort ();
+
+      src = SET_SRC (set->expr);
+
+      /* We know the set is available.
+	 Now check that SRC is ANTLOC (i.e. none of the source operands
+	 have changed since the start of the block).  
+         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 (CONSTANT_P (src) || oprs_not_set_p (src, insn))
+	set1 = set;
+
+      if (GET_CODE (src) != REG || REGNO (src) == regno)
+	break;
+
+      regno = REGNO (src);
     }
+  return set1;
+}
+
+/* Subroutine of cprop_insn that tries to propagate constants into
+   JUMP_INSNS.  INSN must be a conditional jump; COPY is a copy of it
+   that we can use for substitutions.
+   REG_USED is the use we will try to replace, SRC is the constant we
+   will try to substitute for it.
+   Returns nonzero if a change was made.  */
+static int
+cprop_jump (insn, copy, reg_used, src)
+     rtx insn, copy;
+     struct reg_use *reg_used;
+     rtx src;
+{
+  rtx set = PATTERN (copy);
+  rtx temp;
+
+  /* Replace the register with the appropriate constant.  */
+  replace_rtx (SET_SRC (set), reg_used->reg_rtx, src);
+
+  temp = simplify_ternary_operation (GET_CODE (SET_SRC (set)),
+				     GET_MODE (SET_SRC (set)),
+				     GET_MODE (XEXP (SET_SRC (set), 0)),
+				     XEXP (SET_SRC (set), 0),
+				     XEXP (SET_SRC (set), 1),
+				     XEXP (SET_SRC (set), 2));
+
+  /* If no simplification can be made, then try the next
+     register.  */
+  if (temp == 0)
+    return 0;
 
-  return set;
+  SET_SRC (set) = temp;
+
+  /* That may have changed the structure of TEMP, so
+     force it to be rerecognized if it has not turned
+     into a nop or unconditional jump.  */
+		
+  INSN_CODE (copy) = -1;
+  if ((SET_DEST (set) == pc_rtx
+       && (SET_SRC (set) == pc_rtx
+	   || GET_CODE (SET_SRC (set)) == LABEL_REF))
+      || recog (PATTERN (copy), copy, NULL) >= 0)
+    {
+      /* This has either become an unconditional jump
+	 or a nop-jump.  We'd like to delete nop jumps
+	 here, but doing so confuses gcse.  So we just
+	 make the replacement and let later passes
+	 sort things out.  */
+      PATTERN (insn) = set;
+      INSN_CODE (insn) = -1;
+
+      /* One less use of the label this insn used to jump to
+	 if we turned this into a NOP jump.  */
+      if (SET_SRC (set) == pc_rtx && JUMP_LABEL (insn) != 0)
+	--LABEL_NUSES (JUMP_LABEL (insn));
+
+      /* If this has turned into an unconditional jump,
+	 then put a barrier after it so that the unreachable
+	 code will be deleted.  */
+      if (GET_CODE (SET_SRC (set)) == LABEL_REF)
+	emit_barrier_after (insn);
+
+      run_jump_opt_after_gcse = 1;
+
+      const_prop_count++;
+      if (gcse_file != NULL)
+	{
+	  int regno = REGNO (reg_used->reg_rtx);
+	  fprintf (gcse_file, "CONST-PROP: Replacing reg %d in insn %d with constant ",
+		   regno, INSN_UID (insn));
+	  print_rtl (gcse_file, src);
+	  fprintf (gcse_file, "\n");
+	}
+      return 1;
+    }
+  return 0;
+}
+
+#ifdef HAVE_cc0
+/* Subroutine of cprop_insn that tries to propagate constants into
+   JUMP_INSNS for machines that have CC0.  INSN is a single set that
+   stores into CC0; the insn following it is a conditional jump.
+   REG_USED is the use we will try to replace, SRC is the constant we
+   will try to substitute for it.
+   Returns nonzero if a change was made.  */
+static int
+cprop_cc0_jump (insn, reg_used, src)
+     rtx insn;
+     struct reg_use *reg_used;
+     rtx src;
+{
+  rtx jump = NEXT_INSN (insn);
+  rtx copy = copy_rtx (jump);
+  rtx set = PATTERN (copy);
+
+  /* We need to copy the source of the cc0 setter, as cprop_jump is going to
+     substitute into it.  */
+  replace_rtx (SET_SRC (set), cc0_rtx, copy_rtx (SET_SRC (PATTERN (insn))));
+  if (! cprop_jump (jump, copy, reg_used, src))
+    return 0;
+
+  /* If we succeeded, delete the cc0 setter.  */
+  PUT_CODE (insn, NOTE);
+  NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
+  NOTE_SOURCE_FILE (insn) = 0;
+  return 1;
 }
+#endif
 
 /* Perform constant and copy propagation on INSN.
    The result is non-zero if a change was made.  */
@@ -3719,7 +3864,8 @@ cprop_insn (insn, alter_jumps)
       src = SET_SRC (pat);
 
       /* Constant propagation.  */
-      if (GET_CODE (src) == CONST_INT || GET_CODE (src) == CONST_DOUBLE)
+      if (GET_CODE (src) == CONST_INT || GET_CODE (src) == CONST_DOUBLE
+	  || GET_CODE (src) == SYMBOL_REF)
 	{
 	  /* Handle normal insns first.  */
 	  if (GET_CODE (insn) == INSN
@@ -3744,106 +3890,43 @@ cprop_insn (insn, alter_jumps)
 	     code, we can extend this as necessary over time.
 
 	     Right now the insn in question must look like
-
-	     (set (pc) (if_then_else ...))
-
-	     Note this does not currently handle machines which use cc0.  */
+	     (set (pc) (if_then_else ...))  */
 	  else if (alter_jumps
 		   && GET_CODE (insn) == JUMP_INSN
 		   && condjump_p (insn)
 		   && ! simplejump_p (insn))
-	    {
-	      /* We want a copy of the JUMP_INSN so we can modify it
-		 in-place as needed without effecting the original.  */
-	      rtx copy = copy_rtx (insn);
-	      rtx set = PATTERN (copy);
-	      rtx temp;
-
-	      /* Replace the register with the appropriate constant.  */
-	      replace_rtx (SET_SRC (set), reg_used->reg_rtx, src);
-
-	      temp = simplify_ternary_operation (GET_CODE (SET_SRC (set)),
-						 GET_MODE (SET_SRC (set)),
-						 GET_MODE (XEXP (SET_SRC (set), 0)),
-						 XEXP (SET_SRC (set), 0),
-						 XEXP (SET_SRC (set), 1),
-						 XEXP (SET_SRC (set), 2));
-
-	      /* If no simplification can be made, then try the next
-		 register.  */
-	      if (temp)
-		SET_SRC (set) = temp;
-	      else
-		continue;
-
-	      /* That may have changed the structure of TEMP, so
-		 force it to be rerecognized if it has not turned
-		 into a nop or unconditional jump.  */
-		
-	      INSN_CODE (copy) = -1;
-	      if ((SET_DEST (set) == pc_rtx
-		   && (SET_SRC (set) == pc_rtx
-		       || GET_CODE (SET_SRC (set)) == LABEL_REF))
-		  || recog (PATTERN (copy), copy, NULL) >= 0)
-		{
-		  /* This has either become an unconditional jump
-		     or a nop-jump.  We'd like to delete nop jumps
-		     here, but doing so confuses gcse.  So we just
-		     make the replacement and let later passes
-		     sort things out.  */
-		  PATTERN (insn) = set;
-		  INSN_CODE (insn) = -1;
-
-		  /* One less use of the label this insn used to jump to
-		     if we turned this into a NOP jump.  */
-		  if (SET_SRC (set) == pc_rtx && JUMP_LABEL (insn) != 0)
-		    --LABEL_NUSES (JUMP_LABEL (insn));
-
-		  /* If this has turned into an unconditional jump,
-		     then put a barrier after it so that the unreachable
-		     code will be deleted.  */
-		  if (GET_CODE (SET_SRC (set)) == LABEL_REF)
-		    emit_barrier_after (insn);
-
-		  run_jump_opt_after_gcse = 1;
-
-		  changed = 1;
-		  const_prop_count++;
-		  if (gcse_file != NULL)
-		    {
-		      fprintf (gcse_file, "CONST-PROP: Replacing reg %d in insn %d with constant ",
-			       regno, INSN_UID (insn));
-		      print_rtl (gcse_file, src);
-		      fprintf (gcse_file, "\n");
-		    }
-		}
-	    }
+	    changed |= cprop_jump (insn, copy_rtx (insn), reg_used, src);
+#ifdef HAVE_cc0
+	  /* Similar code for machines that use a pair of CC0 setter and
+	     conditional jump insn.  */
+	  else if (alter_jumps
+		   && GET_CODE (PATTERN (insn)) == SET
+		   && SET_DEST (PATTERN (insn)) == cc0_rtx
+		   && GET_CODE (NEXT_INSN (insn)) == JUMP_INSN
+		   && condjump_p (NEXT_INSN (insn))
+		   && ! simplejump_p (NEXT_INSN (insn)))
+	    changed |= cprop_cc0_jump (insn, reg_used, src);
+#endif
 	}
       else if (GET_CODE (src) == REG
 	       && REGNO (src) >= FIRST_PSEUDO_REGISTER
 	       && REGNO (src) != regno)
 	{
-	  /* We know the set is available.
-	     Now check that SET_SRC is ANTLOC (i.e. none of the source operands
-	     have changed since the start of the block).  */
-	  if (oprs_not_set_p (src, insn))
+	  if (try_replace_reg (reg_used->reg_rtx, src, insn))
 	    {
-	      if (try_replace_reg (reg_used->reg_rtx, src, insn))
+	      changed = 1;
+	      copy_prop_count++;
+	      if (gcse_file != NULL)
 		{
-		  changed = 1;
-		  copy_prop_count++;
-		  if (gcse_file != NULL)
-		    {
-		      fprintf (gcse_file, "COPY-PROP: Replacing reg %d in insn %d with reg %d\n",
-			       regno, INSN_UID (insn), REGNO (src));
-		    }
-
-		  /* The original insn setting reg_used may or may not now be
-		     deletable.  We leave the deletion to flow.  */
-		  /* FIXME: If it turns out that the insn isn't deletable,
-		     then we may have unnecessarily extended register lifetimes
-		     and made things worse.  */
+		  fprintf (gcse_file, "COPY-PROP: Replacing reg %d in insn %d with reg %d\n",
+			   regno, INSN_UID (insn), REGNO (src));
 		}
+
+	      /* The original insn setting reg_used may or may not now be
+		 deletable.  We leave the deletion to flow.  */
+	      /* FIXME: If it turns out that the insn isn't deletable,
+		 then we may have unnecessarily extended register lifetimes
+		 and made things worse.  */
 	    }
 	}
     }
@@ -3880,8 +3963,10 @@ cprop (alter_jumps)
 	      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.  */
-	      mark_oprs_set (insn);
+	      /* ??? Need to be careful w.r.t. mods done to INSN.  Don't
+	         call mark_oprs_set if we turned the insn into a NOTE.  */
+	      if (GET_CODE (insn) != NOTE)
+		mark_oprs_set (insn);
 	    }
 	}
     }