[RFA:] cse.c (fold_rtx): Find cheaper comparison equivalent (was: Patches ping...)

[Hans-Peter Nilsson <hans-peter dot nilsson at axis dot com>]

> Date: Fri, 13 Jan 2006 07:14:11 -0700 (MST)
> From: Roger Sayle <roger@eyesopen.com>

> On Mon, 9 Jan 2006, Hans-Peter Nilsson wrote:
> > 2. "[RFA:] Find more equivalents in cse.c:find_comparison_args"

[denied, instead suggesting:]

> The theory would go something like this.  If the second operand
> is a constant value, look through each of the equivalent
> expressions of the first operand, and call
> simplify_const_relational_operation on each one/pair.  If the
> result is non-NULL, you've folded the rtx.  Not only would
> this catch "abs(x) >= 0", but also "(x & 7) < 10", where we'd
> not normally prefer a AND in find_comparison_args.
> 
> Depending on how well this goes, you could even try using
> simplify_relational_operation, and then select the result
> with the lowest COST

I've implemented the latter suggestion; it almost didn't hurt at all.
All goodness; not only does it handle the case at hand (reduced):

static int b (int y, int x) { return x < 0 ? x : y; }
int a (int y, int x)
{
  return b (y, __builtin_abs (x));
}

it also causes removal of many other redundant if:s compared to
the earlier version.  It didn't seem to affect the old cc0 CSiBE
results though, so I'm not sure it'll cause visible improvements
on other (non-cbranch-split-after-reload) platforms.

> allowing "abs(x) == 0" -> "x == 0".

That's not implemented in simplify_relational_operation AFAICT
(and empirically, the abs instruction is still there, replacing
"<" with "==" in the code above).  It also doesn't seem to fold
the "(x & 7) < 10" case you mention; ("s/__builtin_abs (x)/x &
7/" and "s/x < 0/x < 10/" above) for similar reasons, it seems.
Perhaps you meant those as plausible future improvements to
simplify_relational_operation of which this patch would
automatically take advantage.  Fair enough.

Bootstrapped and checked on i686-pc-linux-gnu (FC2), cross to
mmix-knuth-mmixware cris-axis-elf, cris-axis-linux-gnu (cc0 and
non-cc0 implementation), sh64-elf, sh-elf, mips-elf.

Ok to commit?

:ADDPATCH middle-end:

gcc:
	* cse.c (fold_rtx) <case RTX_COMM_COMPARE, RTX_COMPARE>: When arg1
	has a constant equivalent, iterate over equivalents for arg0,
	calling simplify_relational_operation and if there's a result
	cheaper than X, apply fold_rtx and return the result.

Index: cse.c
===================================================================
--- cse.c	(revision 110246)
+++ cse.c	(working copy)
@@ -3982,6 +3983,57 @@ fold_rtx (rtx x, rtx insn)
 	     comparison.  */
 	  if (const_arg0 == 0 || const_arg1 == 0)
 	    {
+	      if (const_arg1 != NULL)
+		{
+		  rtx cheapest_simplification;
+		  int cheapest_cost;
+		  rtx simp_result;
+		  struct table_elt *p;
+
+		  /* See if we can find an equivalent of folded_arg0
+		     that gets us a cheaper expression, possibly a
+		     constant through simplifications.  */
+		  p = lookup (folded_arg0, SAFE_HASH (folded_arg0, mode_arg0),
+			      mode_arg0);
+		  
+		  if (p != NULL)
+		    {
+		      cheapest_simplification = x;
+		      cheapest_cost = COST (x);
+
+		      for (p = p->first_same_value; p != NULL; p = p->next_same_value)
+			{
+			  int cost;
+
+			  /* If the entry isn't valid, skip it.  */
+			  if (! exp_equiv_p (p->exp, p->exp, 1, false))
+			    continue;
+
+			  /* Try to simplify using this equivalence.  */
+			  simp_result
+			    = simplify_relational_operation (code, mode,
+							     mode_arg0,
+							     p->exp,
+							     const_arg1);
+
+			  if (simp_result == NULL)
+			    continue;
+
+			  cost = COST (simp_result);
+			  if (cost < cheapest_cost)
+			    {
+			      cheapest_cost = COST (simp_result);
+			      cheapest_simplification = simp_result;
+			    }
+			}
+
+		      /* If we have a cheaper expression now, use that
+			 and try folding it further, from the top.  */
+		      if (cheapest_simplification != x)
+			return fold_rtx (cheapest_simplification, insn);
+		    }
+		}
+
 	      /* Some addresses are known to be nonzero.  We don't know
 		 their sign, but equality comparisons are known.  */
 	      if (const_arg1 == const0_rtx

brgds, H-P