[17/23] recog: Add a class for propagating into insns

[Richard Sandiford <richard.sandiford@arm.com>]

This patch adds yet another way of propagating into an instruction and
simplifying the result.  (The net effect of the series is to keep the
total number of propagation approaches the same though, since a later
patch removes the fwprop.c routines.)

One of the drawbacks of the validate_replace_* routines is that
they only do simple simplifications, mostly canonicalisations:

  /* Do changes needed to keep rtx consistent.  Don't do any other
     simplifications, as it is not our job.  */
  if (simplify)
    simplify_while_replacing (loc, to, object, op0_mode);

But substituting can often lead to real simplification opportunities.
simplify-rtx.c:simplify_replace_rtx does fully simplify the result,
but it only operates on specific rvalues rather than full instruction
patterns.  It is also nondestructive, which means that it returns a
new rtx whenever a substitution or simplification was possible.
This can create quite a bit of garbage rtl in the context of a
speculative recog, where changing the contents of a pointer is
often enough.

The new routines are therefore supposed to provide simplify_replace_rtx-
style substitution in recog.  They go to some effort to prevent garbage
rtl from being created.

At the moment, the new routines fail if the pattern would still refer
to the old "from" value in some way.  That might be unnecessary in
some contexts; if so, it could be put behind a configuration parameter.

gcc/
	* recog.h (insn_propagation): New class.
	* recog.c (insn_propagation::apply_to_mem_1): New function.
	(insn_propagation::apply_to_rvalue_1): Likewise.
	(insn_propagation::apply_to_lvalue_1): Likewise.
	(insn_propagation::apply_to_pattern_1): Likewise.
	(insn_propagation::apply_to_pattern): Likewise.
	(insn_propagation::apply_to_rvalue): Likewise.
---
 gcc/recog.c | 372 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 gcc/recog.h | 100 ++++++++++++++
 2 files changed, 472 insertions(+)

diff --git a/gcc/recog.c b/gcc/recog.c
index 309a578a151..cb0952d8c6c 100644
--- a/gcc/recog.c
+++ b/gcc/recog.c
@@ -989,6 +989,378 @@ validate_simplify_insn (rtx_insn *insn)
   return ((num_changes_pending () > 0) && (apply_change_group () > 0));
 }
 
+/* Try to process the address of memory expression MEM.  Return true on
+   success; leave the caller to clean up on failure.  */
+
+bool
+insn_propagation::apply_to_mem_1 (rtx mem)
+{
+  auto old_num_changes = num_validated_changes ();
+  mem_depth += 1;
+  bool res = apply_to_rvalue_1 (&XEXP (mem, 0));
+  mem_depth -= 1;
+  if (!res)
+    return false;
+
+  if (old_num_changes != num_validated_changes ()
+      && should_check_mems
+      && !check_mem (old_num_changes, mem))
+    return false;
+
+  return true;
+}
+
+/* Try to process the rvalue expression at *LOC.  Return true on success;
+   leave the caller to clean up on failure.  */
+
+bool
+insn_propagation::apply_to_rvalue_1 (rtx *loc)
+{
+  rtx x = *loc;
+  enum rtx_code code = GET_CODE (x);
+  machine_mode mode = GET_MODE (x);
+
+  auto old_num_changes = num_validated_changes ();
+  if (from && GET_CODE (x) == GET_CODE (from) && rtx_equal_p (x, from))
+    {
+      if (should_unshare)
+	validate_unshare_change (insn, loc, to, 1);
+      else
+	validate_change (insn, loc, to, 1);
+      if (mem_depth && !REG_P (to) && !CONSTANT_P (to))
+	{
+	  /* We're substituting into an address, but TO will have the
+	     form expected outside an address.  Canonicalize it if
+	     necessary.  */
+	  insn_propagation subprop (insn);
+	  subprop.mem_depth += 1;
+	  if (!subprop.apply_to_rvalue (loc))
+	    gcc_unreachable ();
+	  if (should_unshare
+	      && num_validated_changes () != old_num_changes + 1)
+	    {
+	      /* TO is owned by someone else, so create a copy and
+		 return TO to its original form.  */
+	      rtx to = copy_rtx (*loc);
+	      cancel_changes (old_num_changes);
+	      validate_change (insn, loc, to, 1);
+	    }
+	}
+      num_replacements += 1;
+      should_unshare = true;
+      result_flags |= UNSIMPLIFIED;
+      return true;
+    }
+
+  /* Recursively apply the substitution and see if we can simplify
+     the result.  This specifically shouldn't use simplify_gen_* for
+     speculative simplifications, since we want to avoid generating new
+     expressions where possible.  */
+  auto old_result_flags = result_flags;
+  rtx newx = NULL_RTX;
+  bool recurse_p = false;
+  switch (GET_RTX_CLASS (code))
+    {
+    case RTX_UNARY:
+      {
+	machine_mode op0_mode = GET_MODE (XEXP (x, 0));
+	if (!apply_to_rvalue_1 (&XEXP (x, 0)))
+	  return false;
+	if (from && old_num_changes == num_validated_changes ())
+	  return true;
+
+	newx = simplify_unary_operation (code, mode, XEXP (x, 0), op0_mode);
+	break;
+      }
+
+    case RTX_BIN_ARITH:
+    case RTX_COMM_ARITH:
+      {
+	if (!apply_to_rvalue_1 (&XEXP (x, 0))
+	    || !apply_to_rvalue_1 (&XEXP (x, 1)))
+	  return false;
+	if (from && old_num_changes == num_validated_changes ())
+	  return true;
+
+	if (GET_RTX_CLASS (code) == RTX_COMM_ARITH
+	    && swap_commutative_operands_p (XEXP (x, 0), XEXP (x, 1)))
+	  newx = simplify_gen_binary (code, mode, XEXP (x, 1), XEXP (x, 0));
+	else
+	  newx = simplify_binary_operation (code, mode,
+					    XEXP (x, 0), XEXP (x, 1));
+	break;
+      }
+
+    case RTX_COMPARE:
+    case RTX_COMM_COMPARE:
+      {
+	machine_mode op_mode = (GET_MODE (XEXP (x, 0)) != VOIDmode
+				? GET_MODE (XEXP (x, 0))
+				: GET_MODE (XEXP (x, 1)));
+	if (!apply_to_rvalue_1 (&XEXP (x, 0))
+	    || !apply_to_rvalue_1 (&XEXP (x, 1)))
+	  return false;
+	if (from && old_num_changes == num_validated_changes ())
+	  return true;
+
+	newx = simplify_relational_operation (code, mode, op_mode,
+					      XEXP (x, 0), XEXP (x, 1));
+	break;
+      }
+
+    case RTX_TERNARY:
+    case RTX_BITFIELD_OPS:
+      {
+	machine_mode op0_mode = GET_MODE (XEXP (x, 0));
+	if (!apply_to_rvalue_1 (&XEXP (x, 0))
+	    || !apply_to_rvalue_1 (&XEXP (x, 1))
+	    || !apply_to_rvalue_1 (&XEXP (x, 2)))
+	  return false;
+	if (from && old_num_changes == num_validated_changes ())
+	  return true;
+
+	newx = simplify_ternary_operation (code, mode, op0_mode,
+					   XEXP (x, 0), XEXP (x, 1),
+					   XEXP (x, 2));
+	break;
+      }
+
+    case RTX_EXTRA:
+      if (code == SUBREG)
+	{
+	  machine_mode inner_mode = GET_MODE (SUBREG_REG (x));
+	  if (!apply_to_rvalue_1 (&SUBREG_REG (x)))
+	    return false;
+	  if (from && old_num_changes == num_validated_changes ())
+	    return true;
+
+	  rtx inner = SUBREG_REG (x);
+	  newx = simplify_subreg (mode, inner, inner_mode, SUBREG_BYTE (x));
+	  /* Reject the same cases that simplify_gen_subreg would.  */
+	  if (!newx
+	      && (GET_CODE (inner) == SUBREG
+		  || GET_CODE (inner) == CONCAT
+		  || GET_MODE (inner) == VOIDmode
+		  || !validate_subreg (mode, inner_mode,
+				       inner, SUBREG_BYTE (x))))
+	    {
+	      failure_reason = "would create an invalid subreg";
+	      return false;
+	    }
+	  break;
+	}
+      else
+	recurse_p = true;
+      break;
+
+    case RTX_OBJ:
+      if (code == LO_SUM)
+	{
+	  if (!apply_to_rvalue_1 (&XEXP (x, 0))
+	      || !apply_to_rvalue_1 (&XEXP (x, 1)))
+	    return false;
+	  if (from && old_num_changes == num_validated_changes ())
+	    return true;
+
+	  /* (lo_sum (high x) y) -> y where x and y have the same base.  */
+	  rtx op0 = XEXP (x, 0);
+	  rtx op1 = XEXP (x, 1);
+	  if (GET_CODE (op0) == HIGH)
+	    {
+	      rtx base0, base1, offset0, offset1;
+	      split_const (XEXP (op0, 0), &base0, &offset0);
+	      split_const (op1, &base1, &offset1);
+	      if (rtx_equal_p (base0, base1))
+		newx = op1;
+	    }
+	}
+      else if (code == REG)
+	{
+	  if (from && REG_P (from) && reg_overlap_mentioned_p (x, from))
+	    {
+	      failure_reason = "inexact register overlap";
+	      return false;
+	    }
+	}
+      else if (code == MEM)
+	return apply_to_mem_1 (x);
+      else
+	recurse_p = true;
+      break;
+
+    case RTX_CONST_OBJ:
+      break;
+
+    case RTX_AUTOINC:
+      if (from && reg_overlap_mentioned_p (XEXP (x, 0), from))
+	{
+	  failure_reason = "is subject to autoinc";
+	  return false;
+	}
+      recurse_p = true;
+      break;
+
+    case RTX_MATCH:
+    case RTX_INSN:
+      gcc_unreachable ();
+    }
+
+  if (recurse_p)
+    {
+      const char *fmt = GET_RTX_FORMAT (code);
+      for (int i = 0; fmt[i]; i++)
+	switch (fmt[i])
+	  {
+	  case 'E':
+	    for (int j = 0; j < XVECLEN (x, i); j++)
+	      if (!apply_to_rvalue_1 (&XVECEXP (x, i, j)))
+		return false;
+	    break;
+
+	  case 'e':
+	    if (XEXP (x, i) && !apply_to_rvalue_1 (&XEXP (x, i)))
+	      return false;
+	    break;
+	  }
+    }
+  else if (newx && !rtx_equal_p (x, newx))
+    {
+      /* All substitutions made by OLD_NUM_CHANGES onwards have been
+	 simplified.  */
+      result_flags = ((result_flags & ~UNSIMPLIFIED)
+		      | (old_result_flags & UNSIMPLIFIED));
+
+      if (should_note_simplifications)
+	note_simplification (old_num_changes, old_result_flags, x, newx);
+
+      /* There's no longer any point unsharing the substitutions made
+	 for subexpressions, since we'll just copy this one instead.  */
+      bool unshare = false;
+      for (int i = old_num_changes; i < num_changes; ++i)
+	{
+	  unshare |= changes[i].unshare;
+	  changes[i].unshare = false;
+	}
+      if (unshare)
+	validate_unshare_change (insn, loc, newx, 1);
+      else
+	validate_change (insn, loc, newx, 1);
+    }
+
+  return true;
+}
+
+/* Try to process the lvalue expression at *LOC.  Return true on success;
+   leave the caller to clean up on failure.  */
+
+bool
+insn_propagation::apply_to_lvalue_1 (rtx dest)
+{
+  rtx old_dest = dest;
+  while (GET_CODE (dest) == SUBREG
+	 || GET_CODE (dest) == ZERO_EXTRACT
+	 || GET_CODE (dest) == STRICT_LOW_PART)
+    {
+      if (GET_CODE (dest) == ZERO_EXTRACT
+	  && (!apply_to_rvalue_1 (&XEXP (dest, 1))
+	      || !apply_to_rvalue_1 (&XEXP (dest, 2))))
+	return false;
+      dest = XEXP (dest, 0);
+    }
+
+  if (MEM_P (dest))
+    return apply_to_mem_1 (dest);
+
+  /* Check whether the substitution is safe in the presence of this lvalue.  */
+  if (!from
+      || dest == old_dest
+      || !REG_P (dest)
+      || !reg_overlap_mentioned_p (dest, from))
+    return true;
+
+  if (SUBREG_P (old_dest)
+      && SUBREG_REG (old_dest) == dest
+      && !read_modify_subreg_p (old_dest))
+    return true;
+
+  failure_reason = "is part of a read-write destination";
+  return false;
+}
+
+/* Try to process the instruction pattern at *LOC.  Return true on success;
+   leave the caller to clean up on failure.  */
+
+bool
+insn_propagation::apply_to_pattern_1 (rtx *loc)
+{
+  rtx body = *loc;
+  switch (GET_CODE (body))
+    {
+    case COND_EXEC:
+      return (apply_to_rvalue_1 (&COND_EXEC_TEST (body))
+	      && apply_to_pattern_1 (&COND_EXEC_CODE (body)));
+
+    case PARALLEL:
+      {
+	int last = XVECLEN (body, 0) - 1;
+	for (int i = 0; i < last; ++i)
+	  if (!apply_to_pattern_1 (&XVECEXP (body, 0, i)))
+	    return false;
+	return apply_to_pattern_1 (&XVECEXP (body, 0, last));
+      }
+
+    case ASM_OPERANDS:
+      for (int i = 0, len = ASM_OPERANDS_INPUT_LENGTH (body); i < len; ++i)
+	if (!apply_to_rvalue_1 (&ASM_OPERANDS_INPUT (body, i)))
+	  return false;
+      return true;
+
+    case CLOBBER:
+      return apply_to_lvalue_1 (XEXP (body, 0));
+
+    case SET:
+      return (apply_to_lvalue_1 (SET_DEST (body))
+	      && apply_to_rvalue_1 (&SET_SRC (body)));
+
+    default:
+      /* All the other possibilities never store and can use a normal
+	 rtx walk.  This includes:
+
+	 - USE
+	 - TRAP_IF
+	 - PREFETCH
+	 - UNSPEC
+	 - UNSPEC_VOLATILE.  */
+      return apply_to_rvalue_1 (loc);
+    }
+}
+
+/* Apply this insn_propagation object's simplification or substitution
+   to the instruction pattern at LOC.  */
+
+bool
+insn_propagation::apply_to_pattern (rtx *loc)
+{
+  unsigned int num_changes = num_validated_changes ();
+  bool res = apply_to_pattern_1 (loc);
+  if (!res)
+    cancel_changes (num_changes);
+  return res;
+}
+
+/* Apply this insn_propagation object's simplification or substitution
+   to the rvalue expression at LOC.  */
+
+bool
+insn_propagation::apply_to_rvalue (rtx *loc)
+{
+  unsigned int num_changes = num_validated_changes ();
+  bool res = apply_to_rvalue_1 (loc);
+  if (!res)
+    cancel_changes (num_changes);
+  return res;
+}
+
 /* Check whether INSN matches a specific alternative of an .md pattern.  */
 
 bool
diff --git a/gcc/recog.h b/gcc/recog.h
index facf36e7c08..d6af2aa66d9 100644
--- a/gcc/recog.h
+++ b/gcc/recog.h
@@ -82,6 +82,106 @@ alternative_class (const operand_alternative *alt, int i)
   return alt[i].matches >= 0 ? alt[alt[i].matches].cl : alt[i].cl;
 }
 
+/* A class for substituting one rtx for another within an instruction,
+   or for recursively simplifying the instruction as-is.  Derived classes
+   can record or filter certain decisions.  */
+
+class insn_propagation : public simplify_context
+{
+public:
+  /* Assignments for RESULT_FLAGS.
+
+     UNSIMPLIFIED is true if a substitution has been made inside an rtx
+     X and if neither X nor its parent expressions could be simplified.
+
+     FIRST_SPARE_RESULT is the first flag available for derived classes.  */
+  static const uint16_t UNSIMPLIFIED = 1U << 0;
+  static const uint16_t FIRST_SPARE_RESULT = 1U << 1;
+
+  insn_propagation (rtx_insn *);
+  insn_propagation (rtx_insn *, rtx, rtx, bool = true);
+  bool apply_to_pattern (rtx *);
+  bool apply_to_rvalue (rtx *);
+
+  /* Return true if we should accept a substitution into the address of
+     memory expression MEM.  Undoing changes OLD_NUM_CHANGES and up restores
+     MEM's original address.  */
+  virtual bool check_mem (int /*old_num_changes*/,
+			  rtx /*mem*/) { return true; }
+
+  /* Note that we've simplified OLD_RTX into NEW_RTX.  When substituting,
+     this only happens if a substitution occured within OLD_RTX.
+     Undoing OLD_NUM_CHANGES and up will restore the old form of OLD_RTX.
+     OLD_RESULT_FLAGS is the value that RESULT_FLAGS had before processing
+     OLD_RTX.  */
+  virtual void note_simplification (int /*old_num_changes*/,
+				    uint16_t /*old_result_flags*/,
+				    rtx /*old_rtx*/, rtx /*new_rtx*/) {}
+
+private:
+  bool apply_to_mem_1 (rtx);
+  bool apply_to_lvalue_1 (rtx);
+  bool apply_to_rvalue_1 (rtx *);
+  bool apply_to_pattern_1 (rtx *);
+
+public:
+  /* The instruction that we are simplifying or propagating into.  */
+  rtx_insn *insn;
+
+  /* If FROM is nonnull, we're replacing FROM with TO, otherwise we're
+     just doing a recursive simplification.  */
+  rtx from;
+  rtx to;
+
+  /* The number of times that we have replaced FROM with TO.  */
+  unsigned int num_replacements;
+
+  /* A bitmask of flags that describe the result of the simplificiation;
+     see above for details.  */
+  uint16_t result_flags : 16;
+
+  /* True if we should unshare TO when making the next substitution,
+     false if we can use TO itself.  */
+  uint16_t should_unshare : 1;
+
+  /* True if we should call check_mem after substituting into a memory.  */
+  uint16_t should_check_mems : 1;
+
+  /* True if we should call note_simplification after each simplification.  */
+  uint16_t should_note_simplifications : 1;
+
+  /* For future expansion.  */
+  uint16_t spare : 13;
+
+  /* Gives the reason that a substitution failed, for debug purposes.  */
+  const char *failure_reason;
+};
+
+/* Try to replace FROM with TO in INSN.  SHARED_P is true if TO is shared
+   with other instructions, false if INSN can use TO directly.  */
+
+inline insn_propagation::insn_propagation (rtx_insn *insn, rtx from, rtx to,
+					   bool shared_p)
+  : insn (insn),
+    from (from),
+    to (to),
+    num_replacements (0),
+    result_flags (0),
+    should_unshare (shared_p),
+    should_check_mems (false),
+    should_note_simplifications (false),
+    spare (0),
+    failure_reason (nullptr)
+{
+}
+
+/* Try to simplify INSN without performing a substitution.  */
+
+inline insn_propagation::insn_propagation (rtx_insn *insn)
+  : insn_propagation (insn, NULL_RTX, NULL_RTX)
+{
+}
+
 extern void init_recog (void);
 extern void init_recog_no_volatile (void);
 extern int check_asm_operands (rtx);
-- 
2.17.1