Left-chaining canonical forms fix

[gkeating at apple dot com (Geoffrey Keating)]

simplify-rtx.c wants to:

      /* "(a op b) op (c op d)" becomes "((a op b) op c) op d)".  */

but on powerpc, (and (not (reg)) (not (reg))) is an insn, and if you
put some of them together, they get canonicalised as

(and (and (not (reg)) (not (reg))) (not (reg)))

or so.  Unfortunately, commutative_operand_precedence in rtlanal.c
says:

  /* If only one operand is a `neg', `not',
    `mult', `plus', or `minus' expression, it will be the first
    operand.  */

which you'll note does not include AND, and the resulting infinite
recursion eventually causes GCC to run out of stack space.

I think it makes sense to left-chain, so let's do that.

Bootstrapped, tested, 'make info' on powerpc-darwin.

-- 
- Geoffrey Keating <geoffk@apple.com>

===File ~/patches/gcc-canonassoc.patch======================
Index: ChangeLog
2004-02-16  Geoffrey Keating  <geoffk@apple.com>

	* doc/md.texi (Insn Canonicalizations): Document left-chaining
	in associative operators.
	* rtlanal.c (commutative_operand_precedence): Create some new
	variables.  Prefer a commutative operand on the left, then
	binary expressions, then NEG and NOT.

Index: testsuite/ChangeLog
2004-02-16  Geoffrey Keating  <geoffk@apple.com>

	* gcc.c-torture/compile/20040216-1.c: New.

Index: rtlanal.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/rtlanal.c,v
retrieving revision 1.177
diff -u -p -u -p -r1.177 rtlanal.c
--- rtlanal.c	6 Feb 2004 04:28:46 -0000	1.177
+++ rtlanal.c	17 Feb 2004 04:58:56 -0000
@@ -3029,35 +3029,48 @@ regno_use_in (unsigned int regno, rtx x)
 int
 commutative_operand_precedence (rtx op)
 {
+  enum rtx_code code = GET_CODE (op);
+  char class;
+  
   /* Constants always come the second operand.  Prefer "nice" constants.  */
-  if (GET_CODE (op) == CONST_INT)
+  if (code == CONST_INT)
     return -7;
-  if (GET_CODE (op) == CONST_DOUBLE)
+  if (code == CONST_DOUBLE)
     return -6;
   op = avoid_constant_pool_reference (op);
-  if (GET_CODE (op) == CONST_INT)
+  if (code == CONST_INT)
     return -5;
-  if (GET_CODE (op) == CONST_DOUBLE)
+  if (code == CONST_DOUBLE)
     return -4;
   if (CONSTANT_P (op))
     return -3;
 
   /* SUBREGs of objects should come second.  */
-  if (GET_CODE (op) == SUBREG
+  if (code == SUBREG
       && GET_RTX_CLASS (GET_CODE (SUBREG_REG (op))) == 'o')
     return -2;
 
-  /* If only one operand is a `neg', `not',
-    `mult', `plus', or `minus' expression, it will be the first
-    operand.  */
-  if (GET_CODE (op) == NEG || GET_CODE (op) == NOT
-      || GET_CODE (op) == MULT || GET_CODE (op) == PLUS
-      || GET_CODE (op) == MINUS)
+  class = GET_RTX_CLASS (code);
+
+  /* Prefer operands that are themselves commutative to be first.
+     This helps to make things linear.  In particular,
+     (and (and (reg) (reg)) (not (reg))) is canonical.  */
+  if (class == 'c')
+    return 4;
+
+  /* If only one operand is a binary expression, it will be the first
+     operand.  In particular,  (plus (minus (reg) (reg)) (neg (reg)))
+     is canonical, although it will usually be further simplified.  */
+  if (class == '2')
     return 2;
+  
+  /* Then prefer NEG and NOT.  */
+  if (code == NEG || code == NOT)
+    return 1;
 
   /* Complex expressions should be the first, so decrease priority
      of objects.  */
-  if (GET_RTX_CLASS (GET_CODE (op)) == 'o')
+  if (GET_RTX_CLASS (code) == 'o')
     return -1;
   return 0;
 }
Index: doc/md.texi
===================================================================
RCS file: /cvs/gcc/gcc/gcc/doc/md.texi,v
retrieving revision 1.89
diff -u -p -u -p -r1.89 md.texi
--- doc/md.texi	4 Feb 2004 06:12:54 -0000	1.89
+++ doc/md.texi	17 Feb 2004 04:58:56 -0000
@@ -3835,6 +3835,15 @@ second operand.  If a machine only suppo
 operand, only patterns that match a constant in the second operand need
 be supplied.
 
+@item
+For associative operators, a sequence of operators will always chain
+to the left; for instance, only the left operand of an integer @code{plus}
+can itself be a @code{plus}.  @code{and}, @code{ior}, @code{xor},
+@code{plus}, @code{mult}, @code{smin}, @code{smax}, @code{umin}, and
+@code{umax} are associative when applied to integers, and sometimes to
+floating-point.
+
+@item
 @cindex @code{neg}, canonicalization of
 @cindex @code{not}, canonicalization of
 @cindex @code{mult}, canonicalization of
Index: testsuite/gcc.c-torture/compile/20040216-1.c
===================================================================
RCS file: testsuite/gcc.c-torture/compile/20040216-1.c
diff -N testsuite/gcc.c-torture/compile/20040216-1.c
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ testsuite/gcc.c-torture/compile/20040216-1.c	17 Feb 2004 04:59:02 -0000
@@ -0,0 +1,4 @@
+int foo (int a, int b, int c, int d)
+{
+  return ~a & ~b & ~c & ~d;
+}
============================================================