This is the mail archive of the
java-patches@gcc.gnu.org
mailing list for the Java project.
Java: array clean up and store check optimization
- From: Bryce McKinlay <bryce at waitaki dot otago dot ac dot nz>
- To: gcc-patches at gcc dot gnu dot org, java-patches at gcc dot gnu dot org
- Date: Wed, 20 Feb 2002 17:33:17 +1300
- Subject: Java: array clean up and store check optimization
Hi
This patch cleans up the code for generating array accesses in GCJ, and
adds a new performance flag -fno-store-check.
Previously, references to a Java array's "length" and "data" fields were
generated using an INDIRECT_REF and some pointer arithmetic. GCJ tends
to generate poor code for bounds checks, so I tried changing these to
use COMPONENT_REFs instead in the hope that having a proper decl in the
tree would help it out. An array ref is now represented by an ARRAY_REF
instead of an INDIRECT_REF. Unfortunatly this doesn't seem to have
improved the bounds check situation at all (exactly the same code gets
generated for my test case), however it does shorten/simplify the code
and make -fverbose-asm's output more verbose, and makes proper type
information available to the back-end which could theoretically help the
optimizer. Which is nice.
These changes made it easier to add a new option, -fno-store-check,
which disables assignability checks for stores into object arrays,
similar to how -fno-bounds-check disables bounds checking. I also added
some logic to recognise the really obvious cases where the store check
can always be eliminated at compile time - specifically when we have a
"final" array component type, or when we have "o[x] = o[y]". There are
plenty more cases where the check could quite obviously be eliminated
(eg "Object a = o[x]; o[y] = a" or "Object[] o = new Object[1]; o[0] =
new X()") - hopefully one day we'll have a nice tree optimization
framework which will make this sort of thing easier to implement.
Despite its naivety, this optimization is enough to double GCJ's
performance on the infamous ShellSort.java, making it about 20% faster
than Linux JDK 1.4 even without using --no-store-check or
--no-bounds-check. With both these options enabled, GCJ is more than
twice as fast again. This suggests that a lot could be gained by making
our type checking faster in general, something I've been thinking about
doing.
bootstrapped and regtested on i686 and PowerPC Linux. OK to commit?
regards
Bryce.
2002-02-20 Bryce McKinlay <bryce@waitaki.otago.ac.nz>
* expr.c (java_array_data_offset): Removed function.
(JAVA_ARRAY_LENGTH_OFFSET): Removed macro.
(build_java_array_length_access): Obtain "length" value using a
COMPONENT_REF, instead of INDIRECT_REF and arithmetic.
(build_java_arrayaccess): Correct comment. Access "data" using a
COMPONENT_REF, and return an ARRAY_REF instead of an INDIRECT_REF.
(build_java_arraystore_check): New function.
(expand_java_arraystore): Use build_java_arraystore_check.
* parse.y (patch_assignment): Simplify code to insert a store check
when lvalue is an ARRAY_REF. Use build_java_arraystore_check.
* check-init.c (check_init): Update to reflect that an array length
access is now a COMPONENT_REF.
* gcj.texi (Code Generation): Improve documentation of
-fno-bounds-check. Add documentation for -fno-store-check.
* java-tree.h (flag_store_check): Declare.
(build_java_arraystore_check): Declare.
* lang.c (flag_store_check): Initialize to 1.
(lang_f_options): Add store-check option.
* jvspec.c: Don't pass store-check option to jvgenmain.
* lang-options.h: Add help string for -fno-store-check.
Index: check-init.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/java/check-init.c,v
retrieving revision 1.40
diff -c -r1.40 check-init.c
*** check-init.c 2001/12/11 03:29:12 1.40
--- check-init.c 2002/02/20 00:28:20
***************
*** 558,564 ****
final_assign_error (DECL_NAME (decl));
break;
}
! else if (TREE_CODE (tmp) == INDIRECT_REF && IS_ARRAY_LENGTH_ACCESS (tmp))
{
/* We can't emit a more specific message here, because when
compiling to bytecodes we don't get here. */
--- 558,564 ----
final_assign_error (DECL_NAME (decl));
break;
}
! else if (TREE_CODE (tmp) == COMPONENT_REF && IS_ARRAY_LENGTH_ACCESS (tmp))
{
/* We can't emit a more specific message here, because when
compiling to bytecodes we don't get here. */
Index: gcj.texi
===================================================================
RCS file: /cvs/gcc/gcc/gcc/java/gcj.texi,v
retrieving revision 1.21
diff -c -r1.21 gcj.texi
*** gcj.texi 2002/02/07 19:39:27 1.21
--- gcj.texi 2002/02/20 00:28:24
***************
*** 390,398 ****
@item -fno-bounds-check
By default, @code{gcj} generates code which checks the bounds of all
! array indexing operations. With this option, these checks are omitted.
! Note that this can result in unpredictable behavior if the code in
! question actually does violate array bounds constraints.
@item -fjni
With @code{gcj} there are two options for writing native methods: CNI
--- 390,409 ----
@item -fno-bounds-check
By default, @code{gcj} generates code which checks the bounds of all
! array indexing operations. With this option, these checks are omitted, which
! can improve performance for code that uses arrays extensively. Note that this
! can result in unpredictable behavior if the code in question actually does
! violate array bounds constraints. It is safe to use this option if you are
! sure that your code will never throw an @code{ArrayIndexOutOfBoundsException}.
!
! @item -fno-store-check
! Don't generate array store checks. When storing objects into arrays, a runtime
! check is normally generated in order to ensure that the object is assignment
! compatible with the component type of the array (which may not be known
! at compile-time). With this option, these checks are omitted. This can
! improve performance for code which stores objects into arrays frequently.
! It is safe to use this option if you are sure your code will never throw an
! @code{ArrayStoreException}.
@item -fjni
With @code{gcj} there are two options for writing native methods: CNI
Index: java-tree.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/java/java-tree.h,v
retrieving revision 1.135
diff -c -r1.135 java-tree.h
*** java-tree.h 2002/02/18 04:55:06 1.135
--- java-tree.h 2002/02/20 00:28:25
***************
*** 213,218 ****
--- 213,221 ----
in order to improve binary compatibility. */
extern int flag_indirect_dispatch;
+ /* When zero, don't generate runtime array store checks. */
+ extern int flag_store_check;
+
/* Encoding used for source files. */
extern const char *current_encoding;
***************
*** 1106,1111 ****
--- 1109,1115 ----
extern tree build_java_soft_divmod PARAMS ((enum tree_code, tree, tree, tree));
extern tree binary_numeric_promotion PARAMS ((tree, tree, tree *, tree *));
extern tree build_java_arrayaccess PARAMS ((tree, tree, tree));
+ extern tree build_java_arraystore_check PARAMS ((tree, tree));
extern tree build_newarray PARAMS ((int, tree));
extern tree build_anewarray PARAMS ((tree, tree));
extern tree build_new_array PARAMS ((tree, tree));
Index: jvspec.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/java/jvspec.c,v
retrieving revision 1.51
diff -c -r1.51 jvspec.c
*** jvspec.c 2001/12/23 16:07:13 1.51
--- jvspec.c 2002/02/20 00:28:25
***************
*** 65,70 ****
--- 65,72 ----
%{<femit-class-file} %{<femit-class-files} %{<fencoding*}\
%{<fuse-boehm-gc} %{<fhash-synchronization} %{<fjni}\
%{<findirect-dispatch} \
+ %{<fno-store-check}\
%{<fclasspath*} %{<fCLASSPATH*} %{<foutput-class-dir}\
%{<fuse-divide-subroutine} %{<fno-use-divide-subroutine}\
%{<fcheck-references} %{<fno-check-references}\
Index: lang.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/java/lang.c,v
retrieving revision 1.84
diff -c -r1.84 lang.c
*** lang.c 2002/01/01 01:42:15 1.84
--- lang.c 2002/02/20 00:28:26
***************
*** 157,162 ****
--- 158,169 ----
in order to improve binary compatibility. */
int flag_indirect_dispatch = 0;
+ /* When zero, don't generate runtime array store checks. */
+ int flag_store_check = 1;
+
/* When non zero, print extra version information. */
static int version_flag = 0;
***************
*** 179,185 ****
{"check-references", &flag_check_references, 1},
{"force-classes-archive-check", &flag_force_classes_archive_check, 1},
{"optimize-static-class-initialization", &flag_optimize_sci, 1 },
! {"indirect-dispatch", &flag_indirect_dispatch, 1}
};
static const struct string_option
--- 186,194 ----
{"check-references", &flag_check_references, 1},
{"force-classes-archive-check", &flag_force_classes_archive_check, 1},
{"optimize-static-class-initialization", &flag_optimize_sci, 1 },
! {"indirect-dispatch", &flag_indirect_dispatch, 1},
! {"store-check", &flag_store_check, 1}
};
static const struct string_option
Index: lang-options.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/java/lang-options.h,v
retrieving revision 1.28
diff -c -r1.28 lang-options.h
*** lang-options.h 2001/08/09 04:19:12 1.28
--- lang-options.h 2002/02/20 00:58:06
***************
*** 30,35 ****
--- 30,37 ----
{ "-fbounds-check", "" },
{ "-fno-bounds-check",
N_("Disable automatic array bounds checking") },
+ { "-fno-store-check",
+ N_("Disable assignability checks for stores into object arrays") },
{ "-fjni",
N_("Assume native functions are implemented using JNI") },
{ "--classpath",
***************
*** 54,56 ****
--- 56,60 ----
N_("Always check for non gcj generated classes archives") },
{ "-fno-optimize-static-class-initialization",
N_("Never optimize static class initialization code") },
+ { "-findirect-dispatch",
+ N_("Use offset tables for virtual method calls") },
Index: parse.y
===================================================================
RCS file: /cvs/gcc/gcc/gcc/java/parse.y,v
retrieving revision 1.351
diff -c -r1.351 parse.y
*** parse.y 2002/02/18 04:55:07 1.351
--- parse.y 2002/02/20 00:58:08
***************
*** 12589,12597 ****
{
lhs_type = TREE_TYPE (lvalue);
}
! /* Or Lhs can be a array access. Should that be lvalue ? FIXME +
! comment on reason why */
! else if (TREE_CODE (wfl_op1) == ARRAY_REF)
{
lhs_type = TREE_TYPE (lvalue);
lvalue_from_array = 1;
--- 12589,12596 ----
{
lhs_type = TREE_TYPE (lvalue);
}
! /* Or Lhs can be an array access. */
! else if (TREE_CODE (lvalue) == ARRAY_REF)
{
lhs_type = TREE_TYPE (lvalue);
lvalue_from_array = 1;
***************
*** 12693,12772 ****
&& lvalue_from_array
&& JREFERENCE_TYPE_P (TYPE_ARRAY_ELEMENT (lhs_type)))
{
! tree check;
! tree base = lvalue;
! /* We need to retrieve the right argument for
! _Jv_CheckArrayStore. This is somewhat complicated by bounds
! and null pointer checks, both of which wrap the operand in
! one layer of COMPOUND_EXPR. */
! if (TREE_CODE (lvalue) == COMPOUND_EXPR)
! base = TREE_OPERAND (lvalue, 0);
! else
{
! tree op = TREE_OPERAND (base, 0);
!
! /* We can have a SAVE_EXPR here when doing String +=. */
! if (TREE_CODE (op) == SAVE_EXPR)
! op = TREE_OPERAND (op, 0);
! /* We can have a COMPOUND_EXPR here when doing bounds check. */
! if (TREE_CODE (op) == COMPOUND_EXPR)
! op = TREE_OPERAND (op, 1);
! base = TREE_OPERAND (op, 0);
! /* Strip the last PLUS_EXPR to obtain the base. */
! if (TREE_CODE (base) == PLUS_EXPR)
! base = TREE_OPERAND (base, 0);
}
-
- /* Build the invocation of _Jv_CheckArrayStore */
- new_rhs = save_expr (new_rhs);
- check = build (CALL_EXPR, void_type_node,
- build_address_of (soft_checkarraystore_node),
- tree_cons (NULL_TREE, base,
- build_tree_list (NULL_TREE, new_rhs)),
- NULL_TREE);
- TREE_SIDE_EFFECTS (check) = 1;
-
- /* We have to decide on an insertion point */
- if (TREE_CODE (lvalue) == COMPOUND_EXPR)
- {
- tree t;
- if (flag_bounds_check)
- {
- t = TREE_OPERAND (TREE_OPERAND (TREE_OPERAND (lvalue, 1), 0), 0);
- TREE_OPERAND (TREE_OPERAND (TREE_OPERAND (lvalue, 1), 0), 0) =
- build (COMPOUND_EXPR, void_type_node, t, check);
- }
- else
- TREE_OPERAND (lvalue, 1) = build (COMPOUND_EXPR, lhs_type,
- check, TREE_OPERAND (lvalue, 1));
- }
- else if (flag_bounds_check)
- {
- tree hook = lvalue;
- tree compound = TREE_OPERAND (lvalue, 0);
- tree bound_check, new_compound;
-
- if (TREE_CODE (compound) == SAVE_EXPR)
- {
- compound = TREE_OPERAND (compound, 0);
- hook = TREE_OPERAND (hook, 0);
- }
-
- /* Find the array bound check, hook the original array access. */
- bound_check = TREE_OPERAND (compound, 0);
- TREE_OPERAND (hook, 0) = TREE_OPERAND (compound, 1);
-
- /* Make sure the bound check will happen before the store check */
- new_compound =
- build (COMPOUND_EXPR, void_type_node, bound_check, check);
-
- /* Re-assemble the augmented array access. */
- lvalue = build (COMPOUND_EXPR, TREE_TYPE (lvalue),
- new_compound, lvalue);
- }
else
! lvalue = build (COMPOUND_EXPR, TREE_TYPE (lvalue), check, lvalue);
}
/* Final locals can be used as case values in switch
--- 12692,12720 ----
&& lvalue_from_array
&& JREFERENCE_TYPE_P (TYPE_ARRAY_ELEMENT (lhs_type)))
{
! tree array, store_check, base, index_expr;
! /* Get the INDIRECT_REF. */
! array = TREE_OPERAND (TREE_OPERAND (lvalue, 0), 0);
! /* Get the array pointer expr. */
! array = TREE_OPERAND (array, 0);
! store_check = build_java_arraystore_check (array, new_rhs);
!
! index_expr = TREE_OPERAND (lvalue, 1);
!
! if (TREE_CODE (index_expr) == COMPOUND_EXPR)
{
! /* A COMPOUND_EXPR here is a bounds check. The bounds check must
! happen before the store check, so prepare to insert the store
! check within the second operand of the existing COMPOUND_EXPR. */
! base = index_expr;
}
else
! base = lvalue;
!
! index_expr = TREE_OPERAND (base, 1);
! TREE_OPERAND (base, 1) = build (COMPOUND_EXPR, TREE_TYPE (index_expr),
! store_check, index_expr);
}
/* Final locals can be used as case values in switch
Index: expr.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/java/expr.c,v
retrieving revision 1.131
diff -c -r1.131 expr.c
*** expr.c 2002/01/28 16:52:27 1.131
--- expr.c 2002/02/20 01:52:57
***************
*** 79,85 ****
static void java_stack_pop PARAMS ((int));
static tree build_java_throw_out_of_bounds_exception PARAMS ((tree));
static tree build_java_check_indexed_type PARAMS ((tree, tree));
- static tree java_array_data_offset PARAMS ((tree));
static tree case_identity PARAMS ((tree, tree));
static unsigned char peek_opcode_at_pc PARAMS ((struct JCF *, int, int));
static bool emit_init_test_initialization PARAMS ((struct hash_entry *,
--- 79,84 ----
***************
*** 628,638 ****
/* Implementation of operations on array: new, load, store, length */
- /* Array core info access macros */
-
- #define JAVA_ARRAY_LENGTH_OFFSET(A) \
- byte_position (TREE_CHAIN (TYPE_FIELDS (TREE_TYPE (TREE_TYPE (A)))))
-
tree
decode_newarray_type (atype)
int atype;
--- 627,632 ----
***************
*** 699,704 ****
--- 693,699 ----
tree node;
{
tree type = TREE_TYPE (node);
+ tree array_type = TREE_TYPE (type);
HOST_WIDE_INT length;
if (!is_array_type_p (type))
***************
*** 707,719 ****
length = java_array_type_length (type);
if (length >= 0)
return build_int_2 (length, 0);
! node = build1 (INDIRECT_REF, int_type_node,
! fold (build (PLUS_EXPR, ptr_type_node,
! java_check_reference (node,
! flag_check_references),
! JAVA_ARRAY_LENGTH_OFFSET(node))));
IS_ARRAY_LENGTH_ACCESS (node) = 1;
! return fold (node);
}
/* Optionally checks a reference against the NULL pointer. ARG1: the
--- 702,715 ----
length = java_array_type_length (type);
if (length >= 0)
return build_int_2 (length, 0);
!
! node = build (COMPONENT_REF, int_type_node,
! build_java_indirect_ref (array_type, node,
! flag_check_references),
! lookup_field (&array_type, get_identifier ("length")));
!
IS_ARRAY_LENGTH_ACCESS (node) = 1;
! return node;
}
/* Optionally checks a reference against the NULL pointer. ARG1: the
***************
*** 752,770 ****
return build1 (INDIRECT_REF, type, java_check_reference (expr, check));
}
- static tree
- java_array_data_offset (array)
- tree array;
- {
- tree array_type = TREE_TYPE (TREE_TYPE (array));
- tree data_fld = TREE_CHAIN (TREE_CHAIN (TYPE_FIELDS (array_type)));
-
- if (data_fld == NULL_TREE)
- return size_in_bytes (array_type);
- else
- return byte_position (data_fld);
- }
-
/* Implement array indexing (either as l-value or r-value).
Returns a tree for ARRAY[INDEX], assume TYPE is the element type.
Optionally performs bounds checking and/or test to NULL.
--- 748,753 ----
***************
*** 774,785 ****
build_java_arrayaccess (array, type, index)
tree array, type, index;
{
! tree arith, node, throw = NULL_TREE;
!
! arith = fold (build (PLUS_EXPR, int_type_node,
! java_array_data_offset (array),
! fold (build (MULT_EXPR, int_type_node,
! index, size_in_bytes(type)))));
if (flag_bounds_check)
{
--- 757,766 ----
build_java_arrayaccess (array, type, index)
tree array, type, index;
{
! tree node, throw = NULL_TREE;
! tree data_field;
! tree ref;
! tree array_type = TREE_TYPE (TREE_TYPE (array));
if (flag_bounds_check)
{
***************
*** 802,825 ****
TREE_SIDE_EFFECTS( throw ) = 1;
}
}
! /* The SAVE_EXPR is for correct evaluation order. It would be
! cleaner to use force_evaluation_order (see comment there), but
! that is difficult when we also have to deal with bounds
! checking. The SAVE_EXPR is not necessary to do that when we're
! not checking for array bounds. */
! if (TREE_SIDE_EFFECTS (index) && throw)
! throw = build (COMPOUND_EXPR, int_type_node, save_expr (array), throw);
!
! node = build1 (INDIRECT_REF, type,
! fold (build (PLUS_EXPR, ptr_type_node,
! java_check_reference (array,
! flag_check_references),
! (throw ? build (COMPOUND_EXPR, int_type_node,
! throw, arith ) : arith))));
return node;
}
/* Makes sure that INDEXED_TYPE is appropriate. If not, make it from
ARRAY_NODE. This function is used to retrieve something less vague than
a pointer type when indexing the first dimension of something like [[<t>.
--- 783,873 ----
TREE_SIDE_EFFECTS( throw ) = 1;
}
}
+
+ /* If checking bounds, wrap the index expr with a COMPOUND_EXPR in order
+ to have the bounds check evaluated first. */
+ if (throw != NULL_TREE)
+ index = build (COMPOUND_EXPR, int_type_node, throw, index);
+
+ data_field = lookup_field (&array_type, get_identifier ("data"));
+
+ ref = build (COMPONENT_REF, TREE_TYPE (data_field),
+ build_java_indirect_ref (array_type, array,
+ flag_check_references),
+ data_field);
! node = build (ARRAY_REF, type, ref, index);
!
return node;
}
+ /* Generate code to throw an ArrayStoreException if OBJECT is not assignable
+ (at runtime) to an element of ARRAY. A NOP_EXPR is returned if it can
+ determine that no check is required. */
+
+ tree
+ build_java_arraystore_check (array, object)
+ tree array;
+ tree object;
+ {
+ tree check, element_type;
+ tree array_type_p = TREE_TYPE (array);
+ tree object_type = TYPE_NAME (TREE_TYPE (TREE_TYPE (object)));
+
+ if (! is_array_type_p (array_type_p))
+ abort ();
+
+ /* Get the TYPE_DECL for ARRAY's element type. */
+ element_type = TYPE_NAME (TREE_TYPE (TREE_TYPE (TREE_TYPE (array_type_p))));
+
+ if (TREE_CODE (element_type) != TYPE_DECL
+ || TREE_CODE (object_type) != TYPE_DECL)
+ abort ();
+
+ if (!flag_store_check)
+ return build1 (NOP_EXPR, array_type_p, array);
+
+ /* No check is needed if the element type is final or is itself an array.
+ Also check that element_type matches object_type, since in the bytecode
+ compilation case element_type may be the actual element type of the array
+ rather than its declared type. */
+ if (element_type == object_type
+ && (TYPE_ARRAY_P (TREE_TYPE (element_type))
+ || CLASS_FINAL (element_type)))
+ return build1 (NOP_EXPR, array_type_p, array);
+
+ /* Avoid the check if OBJECT was just loaded from the same array. */
+ if (TREE_CODE (object) == ARRAY_REF)
+ {
+ tree target;
+ tree source = TREE_OPERAND (object, 0); /* COMPONENT_REF. */
+ source = TREE_OPERAND (source, 0); /* INDIRECT_REF. */
+ source = TREE_OPERAND (source, 0); /* Source array's DECL or SAVE_EXPR. */
+ if (TREE_CODE (source) == SAVE_EXPR)
+ source = TREE_OPERAND (source, 0);
+
+ target = array;
+ if (TREE_CODE (target) == SAVE_EXPR)
+ target = TREE_OPERAND (target, 0);
+
+ if (source == target)
+ return build1 (NOP_EXPR, array_type_p, array);
+ }
+
+ /* Build an invocation of _Jv_CheckArrayStore */
+ check = build (CALL_EXPR, void_type_node,
+ build_address_of (soft_checkarraystore_node),
+ tree_cons (NULL_TREE, array,
+ build_tree_list (NULL_TREE, object)),
+ NULL_TREE);
+ TREE_SIDE_EFFECTS (check) = 1;
+
+ return check;
+ }
+
/* Makes sure that INDEXED_TYPE is appropriate. If not, make it from
ARRAY_NODE. This function is used to retrieve something less vague than
a pointer type when indexing the first dimension of something like [[<t>.
***************
*** 973,984 ****
if (TREE_CODE (rhs_type_node) == POINTER_TYPE)
{
! tree check = build (CALL_EXPR, void_type_node,
! build_address_of (soft_checkarraystore_node),
! tree_cons (NULL_TREE, array,
! build_tree_list (NULL_TREE, rhs_node)),
! NULL_TREE);
! TREE_SIDE_EFFECTS (check) = 1;
expand_expr_stmt (check);
}
--- 1021,1027 ----
if (TREE_CODE (rhs_type_node) == POINTER_TYPE)
{
! tree check = build_java_arraystore_check (array, rhs_node);
expand_expr_stmt (check);
}