[PATCH] New flag_evaluation_order to preserve evaluation order.

[Roger Sayle <roger at eyesopen dot com>]

The following patch introduces a new global variable to gcc to allow
front-ends to communicate with the middle-end (fold-const.c and expr.c)
that they require left-to-right evaluation order.  This is true for
Java but not for the C-family languages.

The patch then tweaks expand_operands, so that we protect the first
operand from being clobbered by the second.  This is important for
expressions such as "x = y * (y = 3)".  If the first operand of the
multiplication returns "(reg/v: SI 59 [y])", it can still be clobbered
by expanding/evaluating the second operand.  At first I considered
using force_reg, but as above if the value is already in a reg then
we don't actually make a copy.  Then I considered using copy_to_reg,
but if we have a CONST_INT that function doesn't know the correct
mode for the temporary register.  Finally, I realized that some types
of operands can't be held in registers at all, so in the end I ended
up using the save_expr mechanism that has all the necessary logic.
This even optimizes away unnecessary copies for constant operands.


With this infrastructure in place, we can then avoid using save_expr in
the java front-end to attempt to control evaluation order.  The problem
is that save_expr alone isn't sufficient to force the middle-end to
maintain evaluation order, it simply disables numerous constant folding
optimizations and can lead to worse code generation, whilst not actually
guaranteeing the correct evaluation order.  I have a follow-up patch
to honor SAVE_EXPR in Java's bytecode generation, by creating a stack
temporary for each SAVE_EXPR node.  Obviously, the fewer SAVE_EXPRs there
are in the tree representation, the better quality JVM bytecode we'll
generate.  Finally, once gcj's force_evaluation_order becomes a no-op
for binary operations, there's no need to call it from the parser when
constructing binary operators.


Historically, prior to my introduction of expand_operands it would have
been ugly to attempt to implement this in expr.c, which is probably
why the java front-end did things the way it did.  Now that this code
has been cleaned up/factored into a single function, its much easier
for the middle-end to support evaluation order constaints properly.

There may still be (almost certainly) constant folding tree
transformations that affect evaluation order.  I intend to address
some of these in follow up patches.  However, with this patch, we
now have a mechanism to selectively disable them as they are found.
This flag can/will also be used to disable my planned Sethi-Ullman
evaluation order optimizations, when it isn't appropriate for the
current front-end.


The following patch has been tested on i686-pc-linux-gnu with a complete
"make bootstrap", all languages except treelang, and regression tested
with a top-level "make -k check" with no new failures (especially in the
libjava testsuite).  If needed the patch could be committed in two stages,
first the middle-end changes and then the java changes.  However, the
former are completely pointless without the latter.

Ok for mainline?


2003-09-26  Roger Sayle  <roger@eyesopen.com>

	* toplev.c (flag_evaluation_order): New global variable.
	* flags.h (flag_evaluation_order): Prototype here.
	* expr.c (expand_operands): If we need to preserve observable
	evaluation order, protect exp1 from clobbering exp0's result.

	* java/lang.c (java_init_options): Set flag_evaluation_order.
	* java/expr.c (force_evaluation_order): Don't attempt to force
	evaluation order of binary operations using save_expr.
	* java/parse.y (java_complete_lhs): No longer need to call
	force_evaluation_order when constructing binary operators.


Index: toplev.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/toplev.c,v
retrieving revision 1.829
diff -c -3 -p -r1.829 toplev.c
*** toplev.c	22 Sep 2003 05:09:12 -0000	1.829
--- toplev.c	26 Sep 2003 03:52:19 -0000
*************** int flag_trapv = 0;
*** 988,993 ****
--- 988,996 ----
  /* Nonzero if signed arithmetic overflow should wrap around.  */
  int flag_wrapv = 0;

+ /* Nonzero if subexpressions must be evaluated from left-to-right.  */
+ int flag_evaluation_order = 0;
+
  /* Add or remove a leading underscore from user symbols.  */
  int flag_leading_underscore = -1;

Index: flags.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/flags.h,v
retrieving revision 1.120
diff -c -3 -p -r1.120 flags.h
*** flags.h	3 Sep 2003 20:57:31 -0000	1.120
--- flags.h	26 Sep 2003 03:52:19 -0000
*************** extern int flag_trapv;
*** 604,609 ****
--- 604,612 ----
  /* Nonzero if the signed arithmetic overflow should wrap around.  */
  extern int flag_wrapv;

+ /* Nonzero if subexpressions must be evaluated from left-to-right.  */
+ extern int flag_evaluation_order;
+
  /* Value of the -G xx switch, and whether it was passed or not.  */
  extern unsigned HOST_WIDE_INT g_switch_value;
  extern bool g_switch_set;
Index: expr.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/expr.c,v
retrieving revision 1.587
diff -c -3 -p -r1.587 expr.c
*** expr.c	21 Sep 2003 05:07:10 -0000	1.587
--- expr.c	26 Sep 2003 03:52:21 -0000
*************** expand_operands (tree exp0, tree exp1, r
*** 6542,6547 ****
--- 6542,6551 ----
      }
    else
      {
+       /* If we need to preserve evaluation order, copy exp0 into its own
+ 	 temporary variable so that it can't be clobbered by exp1.  */
+       if (flag_evaluation_order && TREE_SIDE_EFFECTS (exp1))
+ 	exp0 = save_expr (exp0);
        *op0 = expand_expr (exp0, target, VOIDmode, modifier);
        *op1 = expand_expr (exp1, NULL_RTX, VOIDmode, modifier);
      }
Index: java/lang.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/java/lang.c,v
retrieving revision 1.142
diff -c -3 -p -r1.142 lang.c
*** java/lang.c	3 Sep 2003 13:44:43 -0000	1.142
--- java/lang.c	26 Sep 2003 03:52:21 -0000
*************** java_init_options (unsigned int argc ATT
*** 685,690 ****
--- 685,693 ----
    /* In Java arithmetic overflow always wraps around.  */
    flag_wrapv = 1;

+   /* Java requires left-to-right evaluation of subexpressions.  */
+   flag_evaluation_order = 1;
+
    jcf_path_init ();

    return CL_Java;
Index: java/expr.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/java/expr.c,v
retrieving revision 1.172
diff -c -3 -p -r1.172 expr.c
*** java/expr.c	21 Sep 2003 05:07:19 -0000	1.172
--- java/expr.c	26 Sep 2003 03:52:22 -0000
*************** force_evaluation_order (tree node)
*** 3324,3339 ****
  {
    if (flag_syntax_only)
      return node;
!   if (TREE_CODE_CLASS (TREE_CODE (node)) == '2')
!     {
!       if (TREE_SIDE_EFFECTS (TREE_OPERAND (node, 1)))
! 	TREE_OPERAND (node, 0) = save_expr (TREE_OPERAND (node, 0));
!     }
!   else if (TREE_CODE (node) == CALL_EXPR
!            || TREE_CODE (node) == NEW_CLASS_EXPR
!            || (TREE_CODE (node) == COMPOUND_EXPR
!                && TREE_CODE (TREE_OPERAND (node, 0)) == CALL_EXPR
!                && TREE_CODE (TREE_OPERAND (node, 1)) == SAVE_EXPR))
      {
        tree arg, cmp;

--- 3324,3334 ----
  {
    if (flag_syntax_only)
      return node;
!   if (TREE_CODE (node) == CALL_EXPR
!       || TREE_CODE (node) == NEW_CLASS_EXPR
!       || (TREE_CODE (node) == COMPOUND_EXPR
! 	  && TREE_CODE (TREE_OPERAND (node, 0)) == CALL_EXPR
! 	  && TREE_CODE (TREE_OPERAND (node, 1)) == SAVE_EXPR))
      {
        tree arg, cmp;

Index: java/parse.y
===================================================================
RCS file: /cvs/gcc/gcc/gcc/java/parse.y,v
retrieving revision 1.444
diff -c -3 -p -r1.444 parse.y
*** java/parse.y	22 Sep 2003 05:09:31 -0000	1.444
--- java/parse.y	26 Sep 2003 03:52:26 -0000
*************** java_complete_lhs (tree node)
*** 12265,12271 ****

            TREE_OPERAND (node, 1) = nn;
          }
!       return force_evaluation_order (patch_binop (node, wfl_op1, wfl_op2));

      case INSTANCEOF_EXPR:
        wfl_op1 = TREE_OPERAND (node, 0);
--- 12265,12271 ----

            TREE_OPERAND (node, 1) = nn;
          }
!       return patch_binop (node, wfl_op1, wfl_op2);

      case INSTANCEOF_EXPR:
        wfl_op1 = TREE_OPERAND (node, 0);


Roger
--
Roger Sayle,                         E-mail: roger@eyesopen.com
OpenEye Scientific Software,         WWW: http://www.eyesopen.com/
Suite 1107, 3600 Cerrillos Road,     Tel: (+1) 505-473-7385
Santa Fe, New Mexico, 87507.         Fax: (+1) 505-473-0833