Re: [tree-ssa] EH cleanup patch

[Andrew MacLeod <amacleod at redhat dot com>]

On Mon, 2003-06-16 at 22:14, law@redhat.com wrote:
> 
> This patch improves our handling of EH cleanups.  It can significantly
> reduce the number of edges in the CFG in the presence of cleanups and
> as a result can significantly speed up the tree-ssa optimizers.
> 
> Bootstrapped, regression tested i686-pc-linux-gnu.
> 
> [ Note there is a follow-up patch which removes a few more edges, but
>   that is blocked behind an insert_insn_on_edge bug. ]
> 

OK, give this a try. I tried a few combinations, and I think I got them
all. We'll see :-)  Hopefullt it does what it is suppose to do.

Along the way, I fixed a bug in the CFG builder.. It wasn't removing the
edge from the SWITCH_EXPR to the fallthrough block unless the default
case label was the first case in a list.. ie

  case 42:
  default:
    ....

wasn't being found, so it wasn't removing the fallthrough edge.

Someone ought to remove the case 42: at some point too I suppose.


Anyway, give this a try. I handled 3 or 4 different situations in it. Im
currently running regressions, I fugured you'd want it ASAP :-)

Andrew


	* tree-cfg.c (handle_switch_fallthru): New. Handle fallthru from switch.
	(bsi_committing_edge_insertions): New. Ststic indicating whether edge
	insertion is happening on demand or by queued edge lists.
	(cleanup_switch_expr_graph): Remove fallthru edge if default label
	is anywhere in the case label list.
	(find_insert_location): Call handle_switch_fallthru when appropriate.
	(bsi_commit_edge_inserts): Set bsi_committing_edge_insertion flag.
	* tree-iterator.h (tsi_last): New. Set TSI to last stmt in a chain.


Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-cfg.c,v
retrieving revision 1.1.4.110
diff -c -p -r1.1.4.110 tree-cfg.c
*** tree-cfg.c	17 Jun 2003 02:18:06 -0000	1.1.4.110
--- tree-cfg.c	17 Jun 2003 14:07:28 -0000
*************** static void replace_stmt (tree *, tree *
*** 131,136 ****
--- 131,137 ----
  static void merge_tree_blocks (basic_block, basic_block);
  static bool remap_stmts (basic_block, basic_block, tree *);
  static tree *handle_switch_split (basic_block, basic_block);
+ static tree *handle_switch_fallthru (tree, basic_block, basic_block);
  static enum eh_region_type get_eh_region_type (tree);
  
  /* Block iterator helpers.  */
*************** static tree_stmt_iterator find_insert_lo
*** 156,161 ****
--- 157,165 ----
  /* Location to track pending stmt for edge insertion.  */
  #define PENDING_STMT(e)	((tree)(e->insns))
  
+ /* True when in the process of calling bsi_commit_edge_insertions.  */
+ static int bsi_committing_edge_insertions = 0;
+ 
  /* Set the pending stmt field.  */
  #define SET_PENDING_STMT(e, t)	((e->insns) = (rtx)t)
  
*************** cleanup_cond_expr_graph (basic_block bb)
*** 2059,2064 ****
--- 2063,2069 ----
  static void
  cleanup_switch_expr_graph (basic_block switch_bb)
  {
+   int found = 0;
  #if defined ENABLE_CHECKING
    tree switch_expr = last_stmt (switch_bb);
  #endif
*************** cleanup_switch_expr_graph (basic_block s
*** 2073,2088 ****
  
    /* If the switch() has a default label, remove the fallthru edge that was
       created when we processed the entry block for the switch() statement.  */
!   for (e = switch_bb->succ; e; e = e->succ_next)
      {
!       tree t = first_stmt (e->dest);
!       if (t && TREE_CODE (t) == CASE_LABEL_EXPR && CASE_LOW (t) == NULL_TREE)
! 	{
! 	  basic_block chain_bb = successor_block (switch_bb);
! 	  edge e = find_edge (switch_bb, chain_bb);
! 	  if (e)
! 	    ssa_remove_edge (e);
! 	  break;
  	}
      }
  }
--- 2078,2100 ----
  
    /* If the switch() has a default label, remove the fallthru edge that was
       created when we processed the entry block for the switch() statement.  */
!   for (e = switch_bb->succ; e && !found; e = e->succ_next)
      {
!       block_stmt_iterator bsi;
!       for (bsi = bsi_start (e->dest); !bsi_end_p (bsi); bsi_next (&bsi))
!         {
! 	  tree t = bsi_stmt (bsi);
!           if (TREE_CODE (t) != CASE_LABEL_EXPR)
! 	    break;
! 	  if (CASE_LOW (t) == NULL_TREE)
! 	    {
! 	      basic_block chain_bb = successor_block (switch_bb);
! 	      edge e = find_edge (switch_bb, chain_bb);
! 	      if (e)
! 		ssa_remove_edge (e);
! 	      found = 1;
! 	      break;
! 	    }
  	}
      }
  }
*************** bsi_prev (block_stmt_iterator *i)
*** 3242,3248 ****
  
  /* Note this routine is a bit ugly. Since BIND_EXPRs dont cause new block, 
     the block iterator keeps a stack of BIND_EXPRs which have been decended
!    into. In order to create this stack properly, this routine traverses 
     through the block until it finds the specified tsi stmt.  */
  
  block_stmt_iterator
--- 3254,3260 ----
  
  /* Note this routine is a bit ugly. Since BIND_EXPRs dont cause new block, 
     the block iterator keeps a stack of BIND_EXPRs which have been decended
!    into.  In order to create this stack properly, this routine traverses 
     through the block until it finds the specified tsi stmt.  */
  
  block_stmt_iterator
*************** bsi_insert_before (block_stmt_iterator *
*** 3586,3594 ****
    return;
  }
  
  
  /* Arrange for a place to insert a stmt when we are splitting a block which is
!    targetting by a switch stmt.  Return the container which is used to build
     a TSI where the edge stmt should be inserted after. 
  
     Fallthrough code must be directed around the target label, and a target 
--- 3598,3680 ----
    return;
  }
  
+ /* When inserting on a FALLTHRU edge from a switch, create a new default case 
+    for the code. If there is a fallthru edge, there should be no default case.
+    Inputs are the SWITCH source block, the original DEST block, and the new
+    block which will contain the new default case.  The edge from src->dest
+    has already been split at this point.  */
+ 
+ static tree *
+ handle_switch_fallthru (tree sw_stmt, basic_block dest, basic_block new_bb)
+ {
+   tree_stmt_iterator tsi;
+   block_stmt_iterator bsi;
+   tree goto_stmt, stmt, label;
+   basic_block src;
+   edge e;
+ 
+ 
+   /* First, make all predecessors which don't explicitly goto the DEST block
+      do so, except for SRC->DEST.  */
+ 
+   bsi = bsi_start (dest);
+   stmt = bsi_stmt (bsi);
+   if (TREE_CODE (stmt) != LABEL_EXPR)
+     {
+       /* DEST does not start with a label, add one.  */
+       label = build_decl (LABEL_DECL, NULL_TREE, NULL_TREE);
+       stmt = build1 (LABEL_EXPR, void_type_node, label);
+       bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
+     }
+   else
+     label = LABEL_EXPR_LABEL (stmt);
+ 
+   src = bb_for_stmt (sw_stmt);
+   for (e = dest->pred; e; e = e->pred_next)
+     if (e->src != new_bb)
+       {
+         stmt = last_stmt (e->src);
+ 	if (TREE_CODE (stmt) != GOTO_EXPR)
+ 	  {
+ 	    goto_stmt = build1 (GOTO_EXPR, void_type_node, label);
+ 	    /* Check if already inserts queued up on this edge.  */
+ 	    if (PENDING_STMT (e) && bsi_committing_edge_insertions)
+ 	      bsi_insert_on_edge (e, goto_stmt);
+ 	    else
+ 	      bsi_insert_on_edge_immediate (e, goto_stmt, NULL, NULL);
+ 	  }
+       }
+     else
+       /* This will no longer be a fallthru edge.  */
+       e->flags = e->flags & ~EDGE_FALLTHRU;
+ 
+   /* Now there are no fall throughs to the DEST block, so simple create
+      the default case, and insert there.  */
+ 
+   stmt = SWITCH_BODY (sw_stmt);
+   /* If the switch isn't inside a BIND_EXPR, make one.  */
+   if (TREE_CODE (stmt) != BIND_EXPR)
+     {
+       tree bind = build (BIND_EXPR, void_type_node, NULL_TREE, stmt, NULL_TREE);
+       set_bb_for_stmt (bind, bb_for_stmt (stmt));
+       SWITCH_BODY (sw_stmt) = bind;
+     }
+ 
+   tsi = tsi_last (&BIND_EXPR_BODY(SWITCH_BODY (sw_stmt))); 
+   label = build_decl (LABEL_DECL, NULL_TREE, NULL_TREE);
+   DECL_CONTEXT (label) = current_function_decl;
+   stmt = build (CASE_LABEL_EXPR, void_type_node, NULL_TREE, NULL_TREE, label);
+   tsi_link_after (&tsi, stmt, TSI_NEW_STMT);
+ 
+   append_stmt_to_bb (tsi_container (tsi), new_bb, sw_stmt);
+ 
+   new_bb->succ->flags = new_bb->succ->flags | EDGE_FALLTHRU;
+ 
+   return tsi_container (tsi);
+ }
  
  /* Arrange for a place to insert a stmt when we are splitting a block which is
!    targeted by a switch stmt.  Return the container which is used to build
     a TSI where the edge stmt should be inserted after. 
  
     Fallthrough code must be directed around the target label, and a target 
*************** find_insert_location (basic_block src, b
*** 3840,3846 ****
  	    break;
  
  	  case SWITCH_EXPR:
! 	    ret = handle_switch_split (new_block, dest);
  	    *location = EDGE_INSERT_LOCATION_AFTER;
  	    break;
  
--- 3926,3936 ----
  	    break;
  
  	  case SWITCH_EXPR:
! 	    bsi = bsi_start (dest);
! 	    if (TREE_CODE (bsi_stmt (bsi)) != CASE_LABEL_EXPR)
! 	      ret = handle_switch_fallthru (stmt, dest, new_block);
! 	    else
! 	      ret = handle_switch_split (new_block, dest);
  	    *location = EDGE_INSERT_LOCATION_AFTER;
  	    break;
  
*************** bsi_commit_edge_inserts (int update_anno
*** 4099,4104 ****
--- 4189,4195 ----
    tree stmt, next_stmt;
    int blocks, count = 0;
  
+   bsi_committing_edge_insertions = 1;
    blocks = n_basic_blocks;
    
    FOR_EACH_BB (bb)
*************** bsi_commit_edge_inserts (int update_anno
*** 4133,4138 ****
--- 4224,4230 ----
        /* TODO. Unimplemented at the moment.  */
      }
  
+   bsi_committing_edge_insertions = 0;
    return count;
  }
  
Index: tree-iterator.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-iterator.h,v
retrieving revision 1.1.2.4
diff -c -p -r1.1.2.4 tree-iterator.h
*** tree-iterator.h	2 May 2003 13:52:38 -0000	1.1.2.4
--- tree-iterator.h	17 Jun 2003 14:07:28 -0000
*************** typedef struct {
*** 45,50 ****
--- 45,51 ----
  } tree_stmt_iterator;
  
  static inline tree_stmt_iterator tsi_start 	PARAMS ((tree *));
+ static inline tree_stmt_iterator tsi_last 	PARAMS ((tree *));
  static inline bool tsi_end_p			PARAMS ((tree_stmt_iterator));
  static inline void tsi_next			PARAMS ((tree_stmt_iterator *));
  static inline void tsi_prev			PARAMS ((tree_stmt_iterator *));
*************** tsi_start (tp)
*** 58,63 ****
--- 59,78 ----
       tree *tp;
  {
    tree_stmt_iterator i;
+   i.tp = tp;
+   return i;
+ }
+ 
+ /* Return an iterator pointing to the last stmt in a chain.  */
+ static inline tree_stmt_iterator
+ tsi_last (tp)
+      tree *tp;
+ {
+   tree_stmt_iterator i;
+ 
+   while (TREE_CODE (*tp) == COMPOUND_EXPR)
+     tp = &TREE_OPERAND (*tp, 1);
+ 
    i.tp = tp;
    return i;
  }