This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Rewrite exception region handling in bytecode compiler
- From: Andrew Haley <aph at redhat dot com>
- To: java-patches at gcc dot gnu dot org, gcc-patches at gcc dot gnu dot org
- Date: Mon, 18 Apr 2005 21:15:33 +0100
- Subject: Rewrite exception region handling in bytecode compiler
PR 20768 shows that the gcj bytecode compiler is miscompiling
exeception regions. This only occurs when such regions aren't
properly nested, and Sun's compiler doesn't seem to output such
regions. However, ecj does, and this has been causing many failures
of gcj-compiled packages in Fedora Core.
If we have an exception range like this:
from to target type
2 14 14 Class TestExceptionBug$IndexedStoreException
2 12 29 Throwable /* finally */
we compile it to
try
{
try
{
bytes 2 .. 11;
}
catch (java.lang.Throwable)
{
goto *.LJpc=29;
}
*.LJpc=12:
bytes 12 .. 13;
}
catch (TestExceptionBug$IndexedStoreException)
{
goto *.LJpc=14;
}
*.LJpc=14:
That is, we have moved the Throwable inside the IndexedStoreException.
But this is wrong: the JVM Spec makes it clear that the exception
table is to be searched from top to bottom, and the first matching
exception used.
It is not legitimate to hoist an exception region inside one higher in
the table.
What we really need to do in this case is split the exception table
into properly nested regions, like this:
from to target type
2 12 14 Class TestExceptionBug$IndexedStoreException
2 12 29 Throwable /* finally */
12 14 14 Class TestExceptionBug$IndexedStoreException
Which gives:
try
{
try
{
bytes 2 .. 11;
}
catch (TestExceptionBug$IndexedStoreException)
{
goto *.LJpc=14;
}
}
catch (java.lang.Throwable)
{
goto *.LJpc=29;
}
try
{
*.LJpc=12:
bytes 12 .. 13;
}
catch (TestExceptionBug$IndexedStoreException)
{
goto *.LJpc=14;
}
*.LJpc=14:
This patch is a rewrite of the logic that generates exception
regions. The priority of exceptions in the exception table is
preserved, and no matter how scrambled the exception table, we
generate a logically equivalent tree.
In a few cases this logic generates more exception regions than the
existing code. Some region merging optimizations are possible at a
later date, but it's more important for this to be correct.
Tested with JOnAS and Eclipse.
Andrew.
2005-04-18 Andrew Haley <aph@redhat.com>
* java-except.h (struct eh_range.handler): Remove unused field.
(handle_nested_ranges): Remove function declaration.
(sanity_check_exception_range): Add function declaration.
* verify.c (verify_jvm_instructions): Remove call to
handle_nested_ranges.
* verify-glue.c (verify_jvm_instructions_new): Call
sanity_check_exception_range.
* except.c (link_handler, eh_range_freelist, link_handler,
handle_nested_ranges): Remove.
(add_handler): Rewrite.
(sanity_check_exception_range): New function.
(print_ranges): New function.
Index: except.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/java/except.c,v
retrieving revision 1.47
diff -c -p -r1.47 except.c
*** except.c 3 Dec 2004 18:11:21 -0000 1.47
--- except.c 18 Apr 2005 18:58:45 -0000
***************
*** 1,5 ****
/* Handle exceptions for GNU compiler for the Java(TM) language.
! Copyright (C) 1997, 1998, 1999, 2000, 2002, 2003, 2004
Free Software Foundation, Inc.
This file is part of GCC.
--- 1,5 ----
/* Handle exceptions for GNU compiler for the Java(TM) language.
! Copyright (C) 1997, 1998, 1999, 2000, 2002, 2003, 2004, 2005
Free Software Foundation, Inc.
This file is part of GCC.
*************** The Free Software Foundation is independ
*** 42,48 ****
static void expand_start_java_handler (struct eh_range *);
static struct eh_range *find_handler_in_range (int, struct eh_range *,
struct eh_range *);
- static void link_handler (struct eh_range *, struct eh_range *);
static void check_start_handlers (struct eh_range *, int);
static void free_eh_ranges (struct eh_range *range);
--- 42,47 ----
*************** struct eh_range *current_method_handlers
*** 50,57 ****
struct eh_range *current_try_block = NULL;
- struct eh_range *eh_range_freelist = NULL;
-
/* These variables are used to speed up find_handler. */
static int cache_range_start, cache_range_end;
--- 49,54 ----
*************** static struct eh_range *cache_next_child
*** 62,73 ****
struct eh_range whole_range;
#if defined(DEBUG_JAVA_BINDING_LEVELS)
- extern int binding_depth;
extern int is_class_level;
extern int current_pc;
! extern void indent ();
#endif
/* Search for the most specific eh_range containing PC.
--- 59,118 ----
struct eh_range whole_range;
+ /* Check the invariants of the structure we're using to contain
+ exception regions. Either returns true or fails an assertion
+ check. */
+
+ bool
+ sanity_check_exception_range (struct eh_range *range)
+ {
+ struct eh_range *ptr = range->first_child;
+ for (; ptr; ptr = ptr->next_sibling)
+ {
+ gcc_assert (ptr->outer == range
+ && ptr->end_pc > ptr->start_pc);
+ if (ptr->next_sibling)
+ gcc_assert (ptr->next_sibling->start_pc >= ptr->end_pc);
+ gcc_assert (ptr->start_pc >= ptr->outer->start_pc
+ && ptr->end_pc <= ptr->outer->end_pc);
+ (void) sanity_check_exception_range (ptr);
+ }
+ return true;
+ }
+
#if defined(DEBUG_JAVA_BINDING_LEVELS)
extern int is_class_level;
extern int current_pc;
! extern int binding_depth;
! extern void indent (void);
! static void
! print_ranges (struct eh_range *range)
! {
! if (! range)
! return;
!
! struct eh_range *child = range->first_child;
!
! indent ();
! fprintf (stderr, "handler pc %d --> %d ", range->start_pc, range->end_pc);
!
! tree handler = range->handlers;
! for ( ; handler != NULL_TREE; handler = TREE_CHAIN (handler))
! {
! tree type = TREE_PURPOSE (handler);
! if (type == NULL)
! type = throwable_type_node;
! fprintf (stderr, " type=%s ", IDENTIFIER_POINTER (DECL_NAME (TYPE_NAME (type))));
! }
! fprintf (stderr, "\n");
+ int saved = binding_depth;
+ binding_depth++;
+ print_ranges (child);
+ binding_depth = saved;
+
+ print_ranges (range->next_sibling);
+ }
#endif
/* Search for the most specific eh_range containing PC.
*************** find_handler (int pc)
*** 117,230 ****
return find_handler_in_range (pc, h, cache_next_child);
}
- /* Recursive helper routine for check_nested_ranges. */
-
- static void
- link_handler (struct eh_range *range, struct eh_range *outer)
- {
- struct eh_range **ptr;
-
- if (range->start_pc == outer->start_pc && range->end_pc == outer->end_pc)
- {
- outer->handlers = chainon (outer->handlers, range->handlers);
- return;
- }
-
- /* If the new range completely encloses the `outer' range, then insert it
- between the outer range and its parent. */
- if (range->start_pc <= outer->start_pc && range->end_pc >= outer->end_pc)
- {
- range->outer = outer->outer;
- range->next_sibling = NULL;
- range->first_child = outer;
- {
- struct eh_range *p = outer;
- struct eh_range **pr = &(outer->outer->first_child);
- while (*pr != outer)
- pr = &(*pr)->next_sibling;
- *pr = range;
-
- while (p)
- {
- p->outer = range;
- p = p->next_sibling;
- }
- }
- return;
- }
-
- /* Handle overlapping ranges by splitting the new range. */
- if (range->start_pc < outer->start_pc || range->end_pc > outer->end_pc)
- {
- struct eh_range *h = xmalloc (sizeof (struct eh_range));
- if (range->start_pc < outer->start_pc)
- {
- h->start_pc = range->start_pc;
- h->end_pc = outer->start_pc;
- range->start_pc = outer->start_pc;
- }
- else
- {
- h->start_pc = outer->end_pc;
- h->end_pc = range->end_pc;
- range->end_pc = outer->end_pc;
- }
- h->first_child = NULL;
- h->outer = NULL;
- h->handlers = build_tree_list (TREE_PURPOSE (range->handlers),
- TREE_VALUE (range->handlers));
- h->next_sibling = NULL;
- h->expanded = 0;
- h->stmt = NULL;
- /* Restart both from the top to avoid having to make this
- function smart about reentrancy. */
- link_handler (h, &whole_range);
- link_handler (range, &whole_range);
- return;
- }
-
- ptr = &outer->first_child;
- for (;; ptr = &(*ptr)->next_sibling)
- {
- if (*ptr == NULL || range->end_pc <= (*ptr)->start_pc)
- {
- range->next_sibling = *ptr;
- range->first_child = NULL;
- range->outer = outer;
- *ptr = range;
- return;
- }
- else if (range->start_pc < (*ptr)->end_pc)
- {
- link_handler (range, *ptr);
- return;
- }
- /* end_pc > (*ptr)->start_pc && start_pc >= (*ptr)->end_pc. */
- }
- }
-
- /* The first pass of exception range processing (calling add_handler)
- constructs a linked list of exception ranges. We turn this into
- the data structure expected by the rest of the code, and also
- ensure that exception ranges are properly nested. */
-
- void
- handle_nested_ranges (void)
- {
- struct eh_range *ptr, *next;
-
- ptr = whole_range.first_child;
- whole_range.first_child = NULL;
- for (; ptr; ptr = next)
- {
- next = ptr->next_sibling;
- ptr->next_sibling = NULL;
- link_handler (ptr, &whole_range);
- }
- }
-
- /* Free RANGE as well as its children and siblings. */
-
static void
free_eh_ranges (struct eh_range *range)
{
--- 162,167 ----
*************** method_init_exceptions (void)
*** 252,306 ****
cache_range_start = 0xFFFFFF;
}
! /* Add an exception range. If we already have an exception range
! which has the same handler and label, and the new range overlaps
! that one, then we simply extend the existing range. Some bytecode
! obfuscators generate seemingly nonoverlapping exception ranges
! which, when coalesced, do in fact nest correctly.
!
! This constructs an ordinary linked list which check_nested_ranges()
! later turns into the data structure we actually want.
! We expect the input to come in order of increasing START_PC. This
! function doesn't attempt to detect the case where two previously
! added disjoint ranges could be coalesced by a new range; that is
! what the sorting counteracts. */
! void
add_handler (int start_pc, int end_pc, tree handler, tree type)
{
! struct eh_range *ptr, *prev = NULL, *h;
for (ptr = whole_range.first_child; ptr; ptr = ptr->next_sibling)
{
! if (start_pc >= ptr->start_pc
! && start_pc <= ptr->end_pc
! && TREE_PURPOSE (ptr->handlers) == type
! && TREE_VALUE (ptr->handlers) == handler)
{
! /* Already found an overlapping range, so coalesce. */
! ptr->end_pc = MAX (ptr->end_pc, end_pc);
! return;
}
! prev = ptr;
}
h = xmalloc (sizeof (struct eh_range));
h->start_pc = start_pc;
h->end_pc = end_pc;
h->first_child = NULL;
! h->outer = NULL;
h->handlers = build_tree_list (type, handler);
h->next_sibling = NULL;
h->expanded = 0;
h->stmt = NULL;
! if (prev == NULL)
! whole_range.first_child = h;
! else
! prev->next_sibling = h;
! }
/* if there are any handlers for this range, issue start of region */
static void
expand_start_java_handler (struct eh_range *range)
--- 189,354 ----
cache_range_start = 0xFFFFFF;
}
! /* Split an exception range into two at PC. The sub-ranges that
! belong to the range are split and distributed between the two new
! ranges. */
!
! static void
! split_range (struct eh_range *range, int pc)
! {
! struct eh_range *ptr;
! struct eh_range **first_child, **second_child;
! struct eh_range *h;
!
! /* First, split all the sub-ranges. */
! for (ptr = range->first_child; ptr; ptr = ptr->next_sibling)
! {
! if (pc > ptr->start_pc
! && pc < ptr->end_pc)
! {
! split_range (ptr, pc);
! }
! }
!
! /* Create a new range. */
! h = xmalloc (sizeof (struct eh_range));
!
! h->start_pc = pc;
! h->end_pc = range->end_pc;
! h->next_sibling = range->next_sibling;
! range->next_sibling = h;
! range->end_pc = pc;
! h->handlers = build_tree_list (TREE_PURPOSE (range->handlers),
! TREE_VALUE (range->handlers));
! h->next_sibling = NULL;
! h->expanded = 0;
! h->stmt = NULL;
! h->outer = range->outer;
! h->first_child = NULL;
!
! ptr = range->first_child;
! first_child = &range->first_child;
! second_child = &h->first_child;
!
! /* Distribute the sub-ranges bewteen the two new ranges. */
! for (ptr = range->first_child; ptr; ptr = ptr->next_sibling)
! {
! if (ptr->start_pc < pc)
! {
! *first_child = ptr;
! ptr->outer = range;
! first_child = &ptr->next_sibling;
! }
! else
! {
! *second_child = ptr;
! ptr->outer = h;
! second_child = &ptr->next_sibling;
! }
! }
! *first_child = NULL;
! *second_child = NULL;
! }
!
!
! /* Add an exception range.
!
! There are some missed optimization opportunities here. For
! example, some bytecode obfuscators generate seemingly
! nonoverlapping exception ranges which, when coalesced, do in fact
! nest correctly. We could merge these, but we'd have to fix up all
! the enclosed regions first and perhaps create a new range anyway if
! it overlapped existing ranges.
! Also, we don't attempt to detect the case where two previously
! added disjoint ranges could be coalesced by a new range. */
! void
add_handler (int start_pc, int end_pc, tree handler, tree type)
{
! struct eh_range *ptr, *h;
! struct eh_range **first_child, **prev;
+ /* First, split all the existing ranges that we need to enclose. */
for (ptr = whole_range.first_child; ptr; ptr = ptr->next_sibling)
{
! if (start_pc > ptr->start_pc
! && start_pc < ptr->end_pc)
{
! split_range (ptr, start_pc);
}
!
! if (end_pc > ptr->start_pc
! && end_pc < ptr->end_pc)
! {
! split_range (ptr, end_pc);
! }
!
! if (ptr->start_pc >= end_pc)
! break;
}
+ /* Create the new range. */
h = xmalloc (sizeof (struct eh_range));
+ first_child = &h->first_child;
+
h->start_pc = start_pc;
h->end_pc = end_pc;
h->first_child = NULL;
! h->outer = NULL_EH_RANGE;
h->handlers = build_tree_list (type, handler);
h->next_sibling = NULL;
h->expanded = 0;
h->stmt = NULL;
! /* Find every range at the top level that will be a sub-range of the
! range we're inserting and make it so. */
! {
! struct eh_range **prev = &whole_range.first_child;
! for (ptr = *prev; ptr;)
! {
! struct eh_range *next = ptr->next_sibling;
!
! if (ptr->start_pc >= end_pc)
! break;
+ if (ptr->start_pc < start_pc)
+ {
+ prev = &ptr->next_sibling;
+ }
+ else if (ptr->start_pc >= start_pc
+ && ptr->start_pc < end_pc)
+ {
+ *prev = next;
+ *first_child = ptr;
+ first_child = &ptr->next_sibling;
+ ptr->outer = h;
+ ptr->next_sibling = NULL;
+ }
+
+ ptr = next;
+ }
+ }
+
+ /* Find the right place to insert the new range. */
+ prev = &whole_range.first_child;
+ for (ptr = *prev; ptr; prev = &ptr->next_sibling, ptr = ptr->next_sibling)
+ {
+ gcc_assert (ptr->outer == NULL_EH_RANGE);
+ if (ptr->start_pc >= start_pc)
+ break;
+ }
+
+ /* And insert it there. */
+ *prev = h;
+ if (ptr)
+ {
+ h->next_sibling = ptr;
+ h->outer = ptr->outer;
+ }
+ }
+
+
/* if there are any handlers for this range, issue start of region */
static void
expand_start_java_handler (struct eh_range *range)
Index: java-except.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/java/java-except.h,v
retrieving revision 1.18
diff -c -p -r1.18 java-except.h
*** java-except.h 12 Feb 2005 15:21:14 -0000 1.18
--- java-except.h 18 Apr 2005 18:58:45 -0000
*************** struct eh_range
*** 54,61 ****
/* The TRY_CATCH_EXPR for this EH range. */
tree stmt;
-
- tree handler;
};
/* A dummy range that represents the entire method. */
--- 54,59 ----
*************** extern struct eh_range * find_handler (i
*** 67,71 ****
extern void method_init_exceptions (void);
extern void maybe_start_try (int, int);
extern void add_handler (int, int, tree, tree);
- extern void handle_nested_ranges (void);
extern void expand_end_java_handler (struct eh_range *);
--- 65,69 ----
extern void method_init_exceptions (void);
extern void maybe_start_try (int, int);
extern void add_handler (int, int, tree, tree);
extern void expand_end_java_handler (struct eh_range *);
+ extern bool sanity_check_exception_range (struct eh_range *);
Index: verify-glue.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/java/verify-glue.c,v
retrieving revision 1.5
diff -c -p -r1.5 verify-glue.c
*** verify-glue.c 7 Mar 2005 21:10:49 -0000 1.5
--- verify-glue.c 18 Apr 2005 18:58:45 -0000
*************** verify_jvm_instructions_new (JCF *jcf, c
*** 487,493 ****
instruction_bits[handler_pc] |= BCODE_EXCEPTION_TARGET;
}
! handle_nested_ranges ();
method.method = current_function_decl;
method.signature = build_java_signature (TREE_TYPE (current_function_decl));
--- 487,493 ----
instruction_bits[handler_pc] |= BCODE_EXCEPTION_TARGET;
}
! gcc_assert (sanity_check_exception_range (&whole_range));
method.method = current_function_decl;
method.signature = build_java_signature (TREE_TYPE (current_function_decl));