Rewrite exception region handling in bytecode compiler

[Andrew Haley]

Jakub, we need this in the Fedora compiler.  It's too late for 4.0.

Andrew.

[Gary Benson]

Jakub, can you let me know when this is available in beehive please?

Thanks,
Gary

Andrew Haley wrote:
>  Jakub, we need this in the Fedora compiler.  It's too late for
> 4.0.
>  
>  Andrew.
>  
>   
Content-Description: forwarded message
>  Date: Mon, 18 Apr 2005 21:15:33 +0100
>  From: Andrew Haley <aph(a)redhat.com&gt;
>  To: java-patches(a)gcc.gnu.org, gcc-patches(a)gcc.gnu.org
>  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(a)redhat.com&gt;
>  
>  	* 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)); 
>  --
>  fedora-devel-java-list mailing list
>  fedora-devel-java-list(a)redhat.com
>  https://www.redhat.com/mailman/listinfo/fedora-devel-java-list

[Gary Benson]

Jakub, does the FC4 compiler have Andrew's new exception code now?

Cheers,
Gary

Andrew Haley wrote:
>  Jakub, we need this in the Fedora compiler.  It's too late for
> 4.0.
>  
>  Andrew.
>  
>  
>  Date: Mon, 18 Apr 2005 21:15:33 +0100
>  From: Andrew Haley <aph(a)redhat.com&gt;
>  To: java-patches(a)gcc.gnu.org, gcc-patches(a)gcc.gnu.org
>  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(a)redhat.com&gt;
>  
>  	* 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));

[Jakub Jelinek]

On Thu, Apr 28, 2005 at 02:15:05PM +0100, Gary Benson wrote:
>  Jakub, does the FC4 compiler have Andrew's new exception code
> now? 
Yes, 4.0.0-0.43 and above, currently rawhide has 4.0.0-1 and I'm working
ATM on 4.0.0-2 rpms.

	Jakub

[Andrew Haley]

Jakub Jelinek writes:
>  On Thu, Apr 28, 2005 at 02:15:05PM +0100, Gary Benson wrote:
>  > Jakub, does the FC4 compiler have Andrew's new exception code now?
>  
>  Yes, 4.0.0-0.43 and above, currently rawhide has 4.0.0-1 and I'm working
>  ATM on 4.0.0-2 rpms. 
I didn't get a chance to look at the PPC issues, sorry.  Let me know
if I can still be of assistance.

Andrew.

[Gary Benson]

Jakub Jelinek wrote:
>  On Thu, Apr 28, 2005 at 02:15:05PM +0100, Gary Benson wrote:
>  > Jakub, does the FC4 compiler have Andrew's new exception code now?
>  
>  Yes, 4.0.0-0.43 and above, currently rawhide has 4.0.0-1 and I'm
>  working ATM on 4.0.0-2 rpms. 
Thank you.

Gary