Patch: `instanceof' optimization

[Tom Tromey <tromey at cygnus dot com>]

This patch adds some optimizations for the Java `instanceof'
operator.  In particular, for `VAL instanceof TYPE':

* If TYPE is Object or we know that the class of VAL is derived from
  TYPE, then we only need to check VAL against `null'.
* If TYPE is final, then we only need to check if VAL is null or if
  VAL's class == TYPE.

It's doubtful that this optimization will help greatly in real code.
However, I think it doesn't make the compiler uglier, and it
definitely can't hurt.  I added a regression test to libgcj to make
sure this doesn't break anything, and I also rebuilt libgcj using this
patch without problems.

Ok to commit?

2000-05-16  Tom Tromey  <tromey@cygnus.com>

	* java-tree.h (build_instanceof): Declare.
	* parse.y (patch_binop): Use build_instanceof.
	* expr.c (build_instanceof): New function.  If class is final,
	don't make a function call.
	(expand_java_INSTANCEOF): Use it.
	(build_get_class): New function.

Tom

Index: expr.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/java/expr.c,v
retrieving revision 1.74
diff -u -r1.74 expr.c
--- expr.c	2000/05/09 01:51:59	1.74
+++ expr.c	2000/05/16 21:35:49
@@ -1036,17 +1036,86 @@
 		     NULL_TREE));
 }
 
+/* This returns an expression which will extract the class of an
+   object.  */
+
+tree
+build_get_class (value)
+     tree value;
+{
+  tree class_field = lookup_field (&dtable_type, get_identifier ("class"));
+  tree vtable_field = lookup_field (&object_type_node,
+				    get_identifier ("vtable"));
+  return build (COMPONENT_REF, class_ptr_type,
+		build1 (INDIRECT_REF, dtable_type,
+			build (COMPONENT_REF, dtable_ptr_type,
+			       build1 (INDIRECT_REF, object_type_node, value),
+			       vtable_field)),
+		class_field);
+}
+
+/* This builds the tree representation of the `instanceof' operator.
+   It tries various tricks to optimize this in cases where types are
+   known.  */
+
+tree
+build_instanceof (value, type)
+     tree value, type;
+{
+  tree expr;
+  tree itype = TREE_TYPE (TREE_TYPE (soft_instanceof_node));
+  tree valtype = TREE_TYPE (TREE_TYPE (value));
+  tree valclass = TYPE_NAME (valtype);
+  tree klass = TYPE_NAME (type);
+
+  if (type == object_type_node || inherits_from_p (valtype, type))
+    {
+      /* Anything except `null' is an instance of Object.  Likewise,
+	 if the object is known to be an instance of the class, then
+	 we only need to check for `null'.  */
+      expr = build (COND_EXPR, itype,
+		    value,
+		    boolean_true_node, boolean_false_node);
+    }
+  else if (! CLASS_INTERFACE (valclass)
+	   && ! CLASS_INTERFACE (klass)
+	   && ! inherits_from_p (type, valtype)
+	   && (CLASS_FINAL (klass)
+	       || ! inherits_from_p (valtype, type)))
+    {
+      /* The classes are from different branches of the derivation
+	 tree, so we immediately know the answer.  */
+      expr = boolean_false_node;
+    }
+  else if (CLASS_FINAL (klass))
+    {
+      tree save = save_expr (value);
+      expr = build (COND_EXPR, itype,
+		    save,
+		    build (EQ_EXPR, itype,
+			   build_get_class (save),
+			   build_class_ref (type)),
+		    boolean_false_node);
+    }
+  else
+    {
+      expr = build (CALL_EXPR, itype,
+		    build_address_of (soft_instanceof_node),
+		    tree_cons (NULL_TREE, value,
+			       build_tree_list (NULL_TREE,
+						build_class_ref (type))),
+		    NULL_TREE);
+    }
+  TREE_SIDE_EFFECTS (expr) = TREE_SIDE_EFFECTS (value);
+  return expr;
+}
+
 static void
 expand_java_INSTANCEOF (type)
      tree type;
 {
   tree value = pop_value (object_ptr_type_node);
-  value = build (CALL_EXPR, TREE_TYPE (TREE_TYPE (soft_instanceof_node)),
-		 build_address_of (soft_instanceof_node),
-		 tree_cons (NULL_TREE, value,
-			    build_tree_list (NULL_TREE,
-					     build_class_ref (type))),
-		 NULL_TREE);
+  value = build_instanceof (value, type);
   push_value (value);
 }
 
Index: java-tree.h
===================================================================
RCS file: /cvs/gcc/egcs/gcc/java/java-tree.h,v
retrieving revision 1.67
diff -u -r1.67 java-tree.h
--- java-tree.h	2000/05/05 04:23:23	1.67
+++ java-tree.h	2000/05/16 21:35:54
@@ -674,6 +674,8 @@
 extern tree build_new_array PARAMS ((tree, tree));
 extern tree build_java_array_length_access PARAMS ((tree));
 extern tree build_java_arraynull_check PARAMS ((tree, tree, tree));
+extern tree build_get_class PARAMS ((tree));
+extern tree build_instanceof PARAMS ((tree, tree));
 extern tree create_label_decl PARAMS ((tree));
 extern void push_labeled_block PARAMS ((tree));
 extern tree prepare_eh_table_type PARAMS ((tree));
Index: parse.y
===================================================================
RCS file: /cvs/gcc/egcs/gcc/java/parse.y,v
retrieving revision 1.162
diff -u -r1.162 parse.y
--- parse.y	2000/05/02 20:32:31	1.162
+++ parse.y	2000/05/16 21:37:11
@@ -12346,18 +12346,7 @@
 	    }
 	  /* Otherwise we have to invoke instance of to figure it out */
 	  else
-	    {
-	      tree call =
-		build (CALL_EXPR, boolean_type_node,
-		       build_address_of (soft_instanceof_node),
-		       tree_cons 
-		       (NULL_TREE, op1,
-			build_tree_list (NULL_TREE,
-					 build_class_ref (op2_type))),
-		       NULL_TREE);
-	      TREE_SIDE_EFFECTS (call) = TREE_SIDE_EFFECTS (op1);
-	      return call;
-	    }
+	    return build_instanceof (op1, op2_type);
 	}
       /* There is no way the expression operand can be an instance of
 	 the type operand. This is a compile time error. */