[tree-ssa] Remove redundant labels

[Steven Bosscher <steven at gcc dot gnu dot org>]

Hi,

With this patch we manage to purge 73915 labels in Diego's cc1-i
files.  Seems like a good cleanup before we start using block stmt
iterators.  Bootstrapped and tested on i686-pc-linux-gnu.  OK?

Gr.
Steven

	* tree-cfg.c (replace_label_in_goto, cleanup_dead_labels): New
	functions to cleanup redundant labels at the head of basic blocks.
	(make_edges): Cleanup labels before cleaning up the CFG.

Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-cfg.c,v
retrieving revision 1.1.4.248
diff -c -3 -p -r1.1.4.248 tree-cfg.c
*** tree-cfg.c	9 Jan 2004 22:55:44 -0000	1.1.4.248
--- tree-cfg.c	10 Jan 2004 19:34:04 -0000
*************** static void bsi_commit_edge_inserts_1 (e
*** 113,118 ****
--- 113,119 ----
  
  static void remove_bb (basic_block);
  static bool cleanup_control_flow (void);
+ static void cleanup_dead_labels (void);
  static edge find_taken_edge_cond_expr (basic_block, tree);
  static edge find_taken_edge_switch_expr (basic_block, tree);
  static tree find_case_label_for_value (tree, tree);
*************** make_edges (void)
*** 458,463 ****
--- 459,467 ----
       builder inserted for completeness.  */
    remove_fake_edges ();
  
+   /* To speed up statement iterator walks, we first purge dead labels.  */
+   cleanup_dead_labels ();
+ 
    /* Clean up the graph and warn for unreachable code.  */
    cleanup_tree_cfg ();
  }
*************** cleanup_tree_cfg (void)
*** 712,719 ****
  
    timevar_push (TV_TREE_CLEANUP_CFG);
  
!   /* These three transformations can cascade, so we iterate on them until 
nothing
!      changes.  */
    while (something_changed)
      {
        something_changed = cleanup_control_flow ();
--- 716,723 ----
  
    timevar_push (TV_TREE_CLEANUP_CFG);
  
!   /* These three transformations can cascade, so we iterate on them until
!      nothing changes.  */
    while (something_changed)
      {
        something_changed = cleanup_control_flow ();
*************** cleanup_tree_cfg (void)
*** 727,732 ****
--- 731,850 ----
    verify_flow_info ();
  #endif
    timevar_pop (TV_TREE_CLEANUP_CFG);
+ }
+ 
+ /* Helper for cleanup_dead_labels.  Returns true if the label in
+    the goto statement STMT was replaced, false otherwise.  */
+ static inline bool
+ replace_label_in_goto (tree stmt, tree *label_for_bb)
+ {
+   tree label = GOTO_DESTINATION (stmt);
+   basic_block target_bb = label_to_block (label);
+   if (NONLOCAL_LABEL (label_for_bb[target_bb->index])
+       || !DECL_ARTIFICIAL (label))
+     {
+       label_for_bb[target_bb->index] = label;
+       return false;
+     }
+   else
+     {
+       GOTO_DESTINATION (stmt) = label_for_bb[target_bb->index];
+       return true;
+     }
+ }
+ 
+ /* Cleanup useless labels from the flow graph.  */
+ static void
+ cleanup_dead_labels (void)
+ {
+   bool changed = false;
+   basic_block bb;
+   tree *label_for_bb = xcalloc (last_basic_block, sizeof (tree));
+ 
+   /* First queue labels.  */
+   FOR_EACH_BB (bb)
+     {
+       tree first = first_stmt (bb);
+       if (first && TREE_CODE (first) == LABEL_EXPR)
+ 	label_for_bb[bb->index] = LABEL_EXPR_LABEL (first);
+     }
+ 
+   /* Now redirect all jumps/branches to the first label in a block.  */
+   FOR_EACH_BB (bb)
+     {
+       tree stmt = last_stmt (bb);
+       if (!stmt)
+ 	continue;
+ 
+       switch (TREE_CODE (stmt))
+ 	{
+ 	case GOTO_EXPR:
+ 	  if (simple_goto_p (stmt))
+ 	    changed |= replace_label_in_goto (stmt, label_for_bb);
+ 	  break;
+ 
+ 	case COND_EXPR:
+ 	  changed |= replace_label_in_goto (COND_EXPR_THEN (stmt), label_for_bb);
+ 	  changed |= replace_label_in_goto (COND_EXPR_ELSE (stmt), label_for_bb);
+ 	  break;
+ 
+ 	case SWITCH_EXPR:
+ 	  {
+ 	    size_t i;
+ 	    tree vec = SWITCH_LABELS (stmt);
+ 	    size_t n = TREE_VEC_LENGTH (vec);
+ 
+ 	    /* Replace all destination labels.  */
+ 	    for (i = 0; i < n; ++i)
+ 	      {
+ 		tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
+ 		basic_block bb = label_to_block (lab);
+ 		if (!NONLOCAL_LABEL (label_for_bb[bb->index]))
+ 		  {
+ 		    CASE_LABEL (TREE_VEC_ELT (vec, i)) = label_for_bb[bb->index];
+ 		    changed = true;
+ 		  }
+ 		else
+ 		  label_for_bb[bb->index] = lab;
+ 	      }
+ 
+ 	    break;
+ 	  }
+ 
+ 	default:
+ 	  break;
+ 	}
+     }
+ 
+   if (!changed)
+     return;
+ 
+   /* Finally, purge dead labels.  */
+   FOR_EACH_BB (bb)
+     {
+       block_stmt_iterator i;
+       tree label_for_this_bb = label_for_bb[bb->index];
+ 
+       if (!label_for_this_bb)
+ 	continue;
+ 
+       for (i = bsi_start (bb); !bsi_end_p (i); )
+ 	{
+ 	  tree label, stmt = bsi_stmt (i);
+ 	  if (TREE_CODE (stmt) != LABEL_EXPR)
+ 	    break;
+ 
+ 	  label = LABEL_EXPR_LABEL (stmt);
+ 	  if (label == label_for_this_bb
+ 	      || !DECL_ARTIFICIAL (label)
+ 	      || NONLOCAL_LABEL (label))
+ 	    bsi_next (&i);
+ 	  else
+ 	    bsi_remove (&i);
+ 	}
+     }
+ 
+   free (label_for_bb);
  }
  
  /* Walk the function tree removing unnecessary statements.