Patch: don't generate dead bytecode

Patch: don't generate dead bytecode

[Tom Tromey]

Today I ran `make class-check' on libgcj.  One of the problems is a
bug in the front end (previously reported).  All the other problems
turned out to be dead byte code which was generated.  It turns out we
generate code for a statement like this:

    if (false) { do something }

This patch removes all that dead bytecode.  It does so by simply not
generating code along a dead branch.

This rebuilds libgcj and passes the test suite (including class-check)
fine.

Ok?

Tom

Index: ChangeLog
from  Tom Tromey  <tromey@redhat.com>
	* jcf-write.c (generate_bytecode_conditional): Return result
	reflects whether condition was generated.
	(generate_bytecode_return): Use return result.
	(generate_bytecode_insns): Likewise.

Index: jcf-write.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/java/jcf-write.c,v
retrieving revision 1.90
diff -u -r1.90 jcf-write.c
--- jcf-write.c 2001/10/08 20:35:03 1.90
+++ jcf-write.c 2001/10/09 03:59:15
@@ -297,7 +297,7 @@
 static int get_access_flags PARAMS ((tree));
 static void write_chunks PARAMS ((FILE *, struct chunk *));
 static int adjust_typed_op PARAMS ((tree, int));
-static void generate_bytecode_conditional PARAMS ((tree, struct jcf_block *,
+static int generate_bytecode_conditional PARAMS ((tree, struct jcf_block *,
 						  struct jcf_block *, int,
 						  struct jcf_partial *));
 static void generate_bytecode_return PARAMS ((tree, struct jcf_partial *));
@@ -1141,9 +1141,11 @@
    branch to TRUE_LABEL; otherwise, branch to FALSE_LABEL.
    TRUE_BRANCH_FIRST is a code geneation hint that the
    TRUE_LABEL may follow right after this. (The idea is that we
-   may be able to optimize away GOTO TRUE_LABEL; TRUE_LABEL:) */
+   may be able to optimize away GOTO TRUE_LABEL; TRUE_LABEL:)
+   Return 0 if we generated a conditional, -1 if the test is always
+   false, and 1 if the test is always true.  */
 
-static void
+static int
 generate_bytecode_conditional (exp, true_label, false_label,
 			       true_branch_first, state)
      tree exp;
@@ -1155,54 +1157,86 @@
   tree exp0, exp1, type;
   int save_SP = state->code_SP;
   enum java_opcode op, negop;
+  int result = 0;
+
   switch (TREE_CODE (exp))
     {
     case INTEGER_CST:
       emit_goto (integer_zerop (exp) ? false_label : true_label, state);
+      result = integer_zerop (exp) ? -1 : 1;
       break;
     case COND_EXPR:
       {
 	struct jcf_block *then_label = gen_jcf_label (state);
 	struct jcf_block *else_label = gen_jcf_label (state);
-	int save_SP_before, save_SP_after;
-	generate_bytecode_conditional (TREE_OPERAND (exp, 0),
-				       then_label, else_label, 1, state);
-	define_jcf_label (then_label, state);
+	int save_SP_before, save_SP_after, r2;
+	int r = generate_bytecode_conditional (TREE_OPERAND (exp, 0),
+					       then_label, else_label,
+					       1, state);
 	save_SP_before = state->code_SP;
-	generate_bytecode_conditional (TREE_OPERAND (exp, 1),
-				       true_label, false_label, 1, state);
+	if (r >= 0)
+	  {
+	    define_jcf_label (then_label, state);
+	    r2 = generate_bytecode_conditional (TREE_OPERAND (exp, 1),
+						true_label, false_label,
+						1, state);
+	    if (r > 0)
+	      result = r2;
+	  }
 	save_SP_after = state->code_SP;
 	state->code_SP = save_SP_before;
-	define_jcf_label (else_label, state);
-	generate_bytecode_conditional (TREE_OPERAND (exp, 2),
-				       true_label, false_label,
-				       true_branch_first, state);
+	if (r <= 0)
+	  {
+	    define_jcf_label (else_label, state);
+	    r2 = generate_bytecode_conditional (TREE_OPERAND (exp, 2),
+						true_label, false_label,
+						true_branch_first, state);
+	    if (r < 0)
+	      result = r2;
+	  }
 	if (state->code_SP != save_SP_after)
 	  abort ();
       }
       break;
     case TRUTH_NOT_EXPR:
-      generate_bytecode_conditional (TREE_OPERAND (exp, 0), false_label,
-				     true_label, ! true_branch_first, state);
+      result = generate_bytecode_conditional (TREE_OPERAND (exp, 0),
+					      false_label, true_label,
+					      ! true_branch_first, state);
       break;
     case TRUTH_ANDIF_EXPR:
       {
 	struct jcf_block *next_label = gen_jcf_label (state);
-	generate_bytecode_conditional (TREE_OPERAND (exp, 0),
-				       next_label, false_label, 1, state);
-	define_jcf_label (next_label, state);
-	generate_bytecode_conditional (TREE_OPERAND (exp, 1),
-				       true_label, false_label, 1, state);
+	int r, r2;
+	r = generate_bytecode_conditional (TREE_OPERAND (exp, 0),
+					   next_label, false_label, 1, state);
+	if (r >= 0)
+	  {
+	    define_jcf_label (next_label, state);
+	    r2 = generate_bytecode_conditional (TREE_OPERAND (exp, 1),
+						true_label, false_label,
+						1, state);
+	    if (r > 0)
+	      r = r2;
+	  }
+	result = r;
       }
       break;
     case TRUTH_ORIF_EXPR:
       {
+	int r, r2;
 	struct jcf_block *next_label = gen_jcf_label (state);
-	generate_bytecode_conditional (TREE_OPERAND (exp, 0),
-				       true_label, next_label, 1, state);
-	define_jcf_label (next_label, state);
-	generate_bytecode_conditional (TREE_OPERAND (exp, 1),
-				       true_label, false_label, 1, state);
+	r = generate_bytecode_conditional (TREE_OPERAND (exp, 0),
+					   true_label, next_label, 1, state);
+	if (r <= 0)
+	  {
+	    define_jcf_label (next_label, state);
+	    r2 = generate_bytecode_conditional (TREE_OPERAND (exp, 1),
+						true_label, false_label,
+						1, state);
+	    if (r < 0)
+	      r = r2;
+	  }
+	result = r;
       }
       break;
     compare_1:
@@ -1348,6 +1382,8 @@
     }
   if (save_SP != state->code_SP)
     abort ();
+
+  return result;
 }
 
 /* Call pending cleanups i.e. those for surrounding CLEANUP_POINT_EXPRs
@@ -1389,12 +1425,19 @@
 	  {
 	    struct jcf_block *then_label = gen_jcf_label (state);
 	    struct jcf_block *else_label = gen_jcf_label (state);
-	    generate_bytecode_conditional (TREE_OPERAND (exp, 0),
-					   then_label, else_label, 1, state);
-	    define_jcf_label (then_label, state);
-	    generate_bytecode_return (TREE_OPERAND (exp, 1), state);
-	    define_jcf_label (else_label, state);
-	    generate_bytecode_return (TREE_OPERAND (exp, 2), state);
+	    int r = generate_bytecode_conditional (TREE_OPERAND (exp, 0),
+						   then_label, else_label,
+						   1, state);
+	    if (r >= 0)
+	      {
+		define_jcf_label (then_label, state);
+		generate_bytecode_return (TREE_OPERAND (exp, 1), state);
+	      }
+	    if (r <= 0)
+	      {
+		define_jcf_label (else_label, state);
+		generate_bytecode_return (TREE_OPERAND (exp, 2), state);
+	      }
 	  }
 	  return;
 	default:
@@ -1617,13 +1660,19 @@
 	struct jcf_block *then_label = gen_jcf_label (state);
 	struct jcf_block *else_label = gen_jcf_label (state);
 	struct jcf_block *end_label = gen_jcf_label (state);
-	generate_bytecode_conditional (exp,
-				       then_label, else_label, 1, state);
-	define_jcf_label (then_label, state);
-	push_int_const (1, state);
-	emit_goto (end_label, state);
-	define_jcf_label (else_label, state);
-	push_int_const (0, state);
+	int r = generate_bytecode_conditional (exp, then_label, else_label,
+					       1, state);
+	if (r >= 0)
+	  {
+	    define_jcf_label (then_label, state);
+	    push_int_const (1, state);
+	    emit_goto (end_label, state);
+	  }
+	if (r <= 0)
+	  {
+	    define_jcf_label (else_label, state);
+	    push_int_const (0, state);
+	  }
 	define_jcf_label (end_label, state);
 	NOTE_PUSH (1);
       }
@@ -1633,16 +1682,24 @@
 	struct jcf_block *then_label = gen_jcf_label (state);
 	struct jcf_block *else_label = gen_jcf_label (state);
 	struct jcf_block *end_label = gen_jcf_label (state);
-	generate_bytecode_conditional (TREE_OPERAND (exp, 0),
-				       then_label, else_label, 1, state);
-	define_jcf_label (then_label, state);
-	generate_bytecode_insns (TREE_OPERAND (exp, 1), target, state);
-	if (CAN_COMPLETE_NORMALLY (TREE_OPERAND (exp, 1))
-	    /* Not all expressions have CAN_COMPLETE_NORMALLY set properly. */
-	    || TREE_CODE (TREE_TYPE (exp)) != VOID_TYPE)
-	  emit_goto (end_label, state);
-	define_jcf_label (else_label, state);
-	generate_bytecode_insns (TREE_OPERAND (exp, 2), target, state);
+	int r = generate_bytecode_conditional (TREE_OPERAND (exp, 0),
+					       then_label, else_label,
+					       1, state);
+	if (r >= 0)
+	  {
+	    define_jcf_label (then_label, state);
+	    generate_bytecode_insns (TREE_OPERAND (exp, 1), target, state);
+	    if (CAN_COMPLETE_NORMALLY (TREE_OPERAND (exp, 1))
+		/* Not all expressions have CAN_COMPLETE_NORMALLY set
+                   properly. */
+		|| TREE_CODE (TREE_TYPE (exp)) != VOID_TYPE)
+	      emit_goto (end_label, state);
+	  }
+	if (r <= 0)
+	  {
+	    define_jcf_label (else_label, state);
+	    generate_bytecode_insns (TREE_OPERAND (exp, 2), target, state);
+	  }
 	define_jcf_label (end_label, state);
 	/* COND_EXPR can be used in a binop. The stack must be adjusted. */
 	if (TREE_TYPE (exp) != void_type_node)

Re: Patch: don't generate dead bytecode

[Per Bothner]

Tom Tromey wrote:

>Today I ran `make class-check' on libgcj.  One of the problems is a
>bug in the front end (previously reported).  All the other problems
>turned out to be dead byte code which was generated.  It turns out we
>generate code for a statement like this:
>
>    if (false) { do something }
>
>This patch removes all that dead bytecode.  It does so by simply not
>generating code along a dead branch.
>
Wouldn't it be a lot simpler and cleaner to optimize this at the tree level,
sort of like constant folding?  For example in patch_if_else_statement.

One possible complication is that CAN_COMPLETE_NORMALLY
needs to be set on the resulting node even if only the optimized-away
branch can complete normally.  I'll try a patch that does this.

Re: Patch: don't generate dead bytecode

[Per Bothner]

Tom Tromey wrote:

>Today I ran `make class-check' on libgcj.  One of the problems is a
>bug in the front end (previously reported).  All the other problems
>turned out to be dead byte code which was generated.  It turns out we
>generate code for a statement like this:
>
>    if (false) { do something }
>
>This patch removes all that dead bytecode.  It does so by simply not
>generating code along a dead branch.
>
The attached patch seems to work.  Could you see if it works as well as
your patch?

Re: Patch: don't generate dead bytecode

[Per Bothner]

Oops.  I left out one "think" from the patch.  (I've got two patches
going at once.)  Try again ...

Re: Patch: don't generate dead bytecode

[Per Bothner]

Per Bothner wrote:

I checked in this patch:

2001-10-11  Per Bothner  <per@bothner.com>

    * parse.y (patch_if_else_statement):  If the condition is constant,
    optimize away the test.


>------------------------------------------------------------------------
>
>Index: parse.y
>===================================================================
>RCS file: /cvs/gcc/gcc/gcc/java/parse.y,v
>retrieving revision 1.318
>diff -u -p -r1.318 parse.y
>--- parse.y	2001/10/09 05:40:35	1.318
>+++ parse.y	2001/10/10 00:02:47
>@@ -15008,6 +14993,9 @@ patch_if_else_statement (node)
>      tree node;
> {
>   tree expression = TREE_OPERAND (node, 0);
>+  int can_complete_normally
>+    = (CAN_COMPLETE_NORMALLY (TREE_OPERAND (node, 1))
>+       | CAN_COMPLETE_NORMALLY (TREE_OPERAND (node, 2)));
> 
>   TREE_TYPE (node) = error_mark_node;
>   EXPR_WFL_LINECOL (wfl_operator) = EXPR_WFL_LINECOL (node);
>@@ -15023,11 +15011,22 @@ patch_if_else_statement (node)
>       return error_mark_node;
>     }
>   
>+  if (TREE_CODE (expression) == INTEGER_CST)
>+    {
>+      if (integer_zerop (expression))
>+	node = TREE_OPERAND (node, 2);
>+      else
>+	node = TREE_OPERAND (node, 1);
>+      if (CAN_COMPLETE_NORMALLY (node) != can_complete_normally)
>+	{
>+	  node = build (COMPOUND_EXPR, void_type_node, node, empty_stmt_node);
>+	  CAN_COMPLETE_NORMALLY (node) = can_complete_normally;
>+	}
>+      return node;
>+    }
>   TREE_TYPE (node) = void_type_node;
>   TREE_SIDE_EFFECTS (node) = 1;
>-  CAN_COMPLETE_NORMALLY (node)
>-    = CAN_COMPLETE_NORMALLY (TREE_OPERAND (node, 1))
>-    | CAN_COMPLETE_NORMALLY (TREE_OPERAND (node, 2));
>+  CAN_COMPLETE_NORMALLY (node) = can_complete_normally;
>   return node;
> }
> 
>

Re: Patch: don't generate dead bytecode

[Tom Tromey]

>>>>> "Per" == Per Bothner <per@bothner.com> writes:

Per> 2001-10-11  Per Bothner  <per@bothner.com>
Per>     * parse.y (patch_if_else_statement):  If the condition is constant,
Per>     optimize away the test.

This patch almost fixes all the problems.  One remains:

/x1/egcs/build/gcc/gcj -B/x1/egcs/build/i686-pc-linux-gnu/libjava/ -B/x1/egcs/build/gcc/ --encoding=UTF-8 --syntax-only ./java/io/ObjectInputStream.class
java/io/ObjectInputStream.java: In class `java.io.ObjectInputStream':
java/io/ObjectInputStream.java: In method `java.io.ObjectInputStream.dumpElement(java.lang.String)':
java/io/ObjectInputStream.java:1538: warning: Unreachable bytecode from 3 to before 16.
java/io/ObjectInputStream.java: In method `java.io.ObjectInputStream.dumpElementln(java.lang.String)':
java/io/ObjectInputStream.java:1544: warning: Unreachable bytecode from 3 to before 16.


Some of the code in question looks like this:

  private void dumpElement (String msg)
  {
    if (Configuration.DEBUG && dump)  
      System.out.print(msg);
  }

Here's the corresponding bytecode:

  0: goto 16
  3: getstatic #922=<Field java.io.ObjectInputStream.dump boolean>
  6: ifeq 16
  9: getstatic #926=<Field java.lang.System.out java.io.PrintStream>
 12: aload_1
 13: invokevirtual #931=<Method java.io.PrintStream.print (java.lang.String)void>
 16: return


It looks like `&&' isn't being short-circuited properly.

Tom

Re: Patch: don't generate dead bytecode

[Per Bothner]

Tom Tromey wrote:

>This patch almost fixes all the problems.  One remains:
>
>/x1/egcs/build/gcc/gcj -B/x1/egcs/build/i686-pc-linux-gnu/libjava/ -B/x1/egcs/build/gcc/ --encoding=UTF-8 --syntax-only ./java/io/ObjectInputStream.class
>java/io/ObjectInputStream.java: In class `java.io.ObjectInputStream':
>java/io/ObjectInputStream.java: In method `java.io.ObjectInputStream.dumpElement(java.lang.String)':
>java/io/ObjectInputStream.java:1538: warning: Unreachable bytecode from 3 to before 16.
>java/io/ObjectInputStream.java: In method `java.io.ObjectInputStream.dumpElementln(java.lang.String)':
>java/io/ObjectInputStream.java:1544: warning: Unreachable bytecode from 3 to before 16.
>
The problem is fundamentally that fold may create a SAVE_EXPR, which we 
can't use when
generating bytecode, because it would be too expensive to allocate a 
register for
a temp when we don't know when we can re-use it.  (It has been argued 
that SAVE_EXPR
is Bad Thing more generally, but I don't know of any plans to remove it.)

So patch_binop when generating bytecodes, to be safe, only calls fold 
when both operands
are constant. One fix to to do our own folding for '||' and '&&'.  I'll 
look into that.

Re: Patch: don't generate dead bytecode

[Tom Tromey]

>>>>> "Per" == Per Bothner <per@bothner.com> writes:

Per> Perhaps rather than writing our own fold it would be better to
Per> add some flag to force fold to respect evaluation order and
Per> otherwise not do anything that might break Java semantics.

The other problem we face is that a Java fold() must handle string
operations as well.  Whether we should write our own or modify the
existing one, I don't know.  fold() certainly seems complicated, so
rewriting it might be a mistake.  Anyway, last time I looked this area
was one of our leading causes of failure for Jacks tests, so on a
correctness metric it is a big win to fix.

Tom

Re: Patch: don't generate dead bytecode

[Per Bothner]

Tom Tromey wrote:

>The other problem we face is that a Java fold() must handle string
>operations as well.
>
fold only does "shallow" folding - i.e. it assumes that you call
it at each step when you create tree-node for an operator, so that
any operands to a binary operator have already been folded.
fold does not recursively traverse its input.  Thus I don't think
strings are a problem - basically we just need to handle string
concatenation separately before we call fold - like we do now.

    --Per

Re: Patch: don't generate dead bytecode

[Tom Tromey]

>>>>> "Per" == Per Bothner <per@bothner.com> writes:

[ revisiting old email ]

Per> So patch_binop when generating bytecodes, to be safe, only calls
Per> fold when both operands are constant. One fix to to do our own
Per> folding for '||' and '&&'.  I'll look into that.

I think we need our own fold() anyway.  The fold in gcc doesn't
implement Java semantics precisely.  As I recall there are lots of
Jacks test failures resulting from our deviations here.

Tom

Re: Patch: don't generate dead bytecode

[Per Bothner]

[-- Attachment #1: Type: text/plain, Size: 1518 bytes --]

Tom Tromey wrote:

>>>>>>"Per" == Per Bothner <per@bothner.com> writes:
>>>>>>
>[ revisiting old email ]
>
>Per> So patch_binop when generating bytecodes, to be safe, only calls
>Per> fold when both operands are constant. One fix to to do our own
>Per> folding for '||' and '&&'.  I'll look into that.
>
>I think we need our own fold() anyway.  The fold in gcc doesn't
>implement Java semantics precisely.  As I recall there are lots of
>Jacks test failures resulting from our deviations here.
>
Folding a binary operator when both operand are constants is presumably
safe - or are the some traps I'm not aware of?

The hard part is all the logic in fold that re-arranges the computation
when the operands are not both constants.  That is where you can get
the non-obvous optimizations - but it is also the case where the
difference between Java and C/C++ semantics can cause mistakes.
Perhaps rather than writing our own fold it would be better to add
some flag to force fold to respect evaluation order and otherwise
not do anything that might break Java semantics.  I suspect we can
get such a change into the existing fold - but it requires someone
understanding the issues better than I do to propose a clean solution.

I did implement a patch as I suggested, but I haven't gotten around
to checking it in.  This is partly because it only handles the case where
first operand is constant.  The case when the second operand is constant
is a little trickier.   But I can certainly check in what I have.

    --Per


[-- Attachment #2: patch --]
[-- Type: text/plain, Size: 647 bytes --]

Index: parse.y
===================================================================
RCS file: /cvs/gcc/gcc/gcc/java/parse.y,v
retrieving revision 1.321
diff -u -p -r1.321 parse.y
--- parse.y	2001/10/11 23:50:48	1.321
+++ parse.y	2001/11/19 07:06:26
@@ -13756,6 +13756,14 @@ patch_binop (node, wfl_op1, wfl_op2)
 	  error_found = 1;
 	  break;
 	}
+      else if (integer_zerop (op1))
+	{
+	  return code == TRUTH_ANDIF_EXPR ? op1 : op2;
+	}
+      else if (integer_onep (op1))
+	{
+	  return code == TRUTH_ANDIF_EXPR ? op2 : op1;
+	}
       /* The type of the conditional operators is BOOLEAN */
       prom_type = boolean_type_node;
       break;

Re: Patch: don't generate dead bytecode

[Bryce McKinlay]

Per Bothner wrote:

> Folding a binary operator when both operand are constants is presumably
> safe - or are the some traps I'm not aware of? 


Here's a case which we get wrong with -O. Note that if x and y are not 
constant, it works correctly.

public class PR4822
{
  public static void main(String[] args)
  {
    int x = 99;
    int y = 0;

    if ((x = y) == (99 - (y = 99)))
      System.out.println ("OK");
    else
      System.out.println ("FAIL");
  }
}


regards

Bryce.