[RFC][4.4] PR rtl-optimization/3507 appalling optimization with sub/cmp

[Rask Ingemann Lambertsen <rask at sygehus dot dk>]

   Hi,

   I'll be submitting approximately the patch below when trunk reopens for
stage1. At the moment I'm looking for comments. For example, I'm expecting
someone to say a few words about floating point issues, but feel free to
mention anything that should be changed before the patch can be approved.
I'm aware that comparisons against constants won't be optimized yet.

2007-11-28  Rask Ingemann Lambertsen  <rask@sygehus.dk>

	PR rtl-optimization/3507
	* cse.c (cse_find_comparison_use_1): New.
	(cse_find_comparison_use): New.
	(cse_insn): Try to reuse (a - b) for a comparison (a op b).
	(cse_main): Ask DF for def-use chains.

Index: gcc/cse.c
===================================================================
--- gcc/cse.c	(revision 130131)
+++ gcc/cse.c	(working copy)
@@ -3909,6 +3909,52 @@ record_jump_cond (enum rtx_code code, en
 
   merge_equiv_classes (op0_elt, op1_elt);
 }
+
+struct cse_comparison_use
+{
+  rtx cc_reg;
+  rtx comparison_operator;
+};
+
+/* Callback function for use by cse_find_comparison_use().  */
+static int
+cse_find_comparison_use_1 (rtx *x, void *data)
+{
+  struct cse_comparison_use *use = data;
+  if (GET_RTX_CLASS (GET_CODE (*x)) == RTX_COMM_COMPARE
+      || GET_RTX_CLASS (GET_CODE (*x)) == RTX_COMPARE)
+    if (rtx_equal_p (XEXP (*x, 0), use->cc_reg))
+      {
+	use->comparison_operator = *x;
+	return 1;
+      }
+  return 0;
+}
+
+/* For a register X holding a comparison result set in INSN, return the
+   comparison operator which is the user of X.  Return NULL_RTX if no user
+   is found or if there are more than one user.  */
+static rtx
+cse_find_comparison_use (rtx x, rtx insn)
+{
+  struct cse_comparison_use cmp_use;
+  struct df_ref **defs, *use;
+  struct df_link *def_use;
+  for (defs = DF_INSN_DEFS (insn);
+       *defs && DF_REF_REGNO (*defs) != REGNO (x);
+       defs++)
+    ;
+  def_use = *defs ? DF_REF_CHAIN (*defs) : NULL;
+
+  /* Bail out if there are no uses or multiple uses.  */
+  if (!def_use || def_use->next)
+    return NULL_RTX;
+  use = def_use->ref;
+  cmp_use.cc_reg = x;
+  if (for_each_rtx (&DF_REF_INSN (use), cse_find_comparison_use_1, &cmp_use))
+    return cmp_use.comparison_operator;
+  return NULL_RTX;
+}
 
 /* CSE processing for one instruction.
    First simplify sources and addresses of all assignments
@@ -4256,6 +4302,64 @@ cse_insn (rtx insn, rtx libcall_insn)
 	 simplified result, which may not necessarily be valid.  */
       src_folded = fold_rtx (src, insn);
 
+      /* If src is a comparison a op b, see if c = a - b was already computed.
+	 We'll try to replace a op b with a op c for unsigned comparisons.
+	 We'll try to replace a op b with c op 0 for signed comparisons and
+	 equality comparisons.  */
+      if (src_folded == src
+	  && REG_P (dest)
+	  && GET_CODE (src) == COMPARE)
+	{
+	  enum machine_mode op_mode = GET_MODE (XEXP (src, 0));
+	  rtx minus = gen_rtx_MINUS (op_mode, XEXP (src, 0), XEXP (src, 1));
+	  unsigned minus_hash = HASH (minus, op_mode);
+	  struct table_elt *minus_elt = lookup (minus, minus_hash, op_mode);
+	  rtx cmp = NULL_RTX, res = NULL_RTX, op0 = NULL_RTX, op1 = NULL_RTX;
+
+	  /* We found it.  Now we need to find out if the comparison is
+	     signed or unsigned.  To do so, find the use of dest.  */
+	  if (minus_elt)
+	      cmp = cse_find_comparison_use (dest, insn);
+	  if (cmp)
+	    {
+	      for (minus_elt = minus_elt->first_same_value;
+		   minus_elt; minus_elt = minus_elt->next_same_value)
+		if (REG_P (minus_elt->exp))
+		  {
+		    res = minus_elt->exp;
+		    break;
+		  }
+	    }
+	  if (res)
+	    {
+	      switch (GET_CODE (cmp))
+		{
+		/* Because we found a - b already computed, we can assume it
+		   won't overflow, but only if signed overflow is undefined.  */
+		case LT: case GE: case LE: case GT:
+		  if (flag_trapv || flag_wrapv || !flag_strict_overflow)
+		    break;
+		  /* Fall through.  */
+
+		/* The remaining cases have no problems with overflow.  */
+		case EQ: case NE:
+		  op0 = res;
+		  op1 = CONST0_RTX (op_mode);
+		  break;
+
+		case LTU: case GEU: case LEU: case GTU:
+		  op0 = XEXP (src, 0);
+		  op1 = res;
+		  break;
+
+		default:
+		  break;
+		}
+	    }
+	  if (op0 && op1)
+	    src_folded = gen_rtx_COMPARE (mode, op0, op1);
+	}
+
 #if 0
       /* ??? This caused bad code to be generated for the m68k port with -O2.
 	 Suppose src is (CONST_INT -1), and that after truncation src_folded
@@ -6145,6 +6249,7 @@ cse_main (rtx f ATTRIBUTE_UNUSED, int nr
   int *rc_order = XNEWVEC (int, last_basic_block);
   int i, n_blocks;
 
+  df_chain_add_problem (DF_DU_CHAIN);
   df_set_flags (DF_LR_RUN_DCE);
   df_analyze ();
   df_set_flags (DF_DEFER_INSN_RESCAN);


-- 
Rask Ingemann Lambertsen
Danish law requires addresses in e-mail to be logged and stored for a year