This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[tree-ssa] Misc fixes


This patch addresses three latent bugs that have been exposed by some
work Jason and I have been doing.

First, computed gotos need to create abnormal edges as they are bloody
difficult to split.  I'm not sure what drugs I was on when I wrote the code
which created those as normal edges.

remove_stmt can leave a dangling pointer in bb->{head,end}_tree_p when
called to eliminate a COMPOUND_EXPR where both operands are empty trees
and one of those empty trees was the start/end of a basic block.

Finally, when we linearize a COND_EXPR, we need to make sure that 
we don't lose any important edges.  Consider:

     while (1)
       {
	 important code;
	 if (whatever)
  	   (void)0
         else
           (void)0
       }

If we flatten the COND_EXPR, we need to make sure that the backedge to the
top of the loop that is associated with the ELSE clause gets moved.

Bootstrapped, regression tested i686-pc-linux-gnu.


	* tree-cfg.c (move_outgoing_edges): New function.
	(merge_tree_blocks): Use it.
	(remove_bb): Remove the block from the pdom_info structures
	as well if they exist.
	(linearize_cond_expr): Move important edges from the then and
	else arms to BB as appropriately

	* tree-cfg.c (remove_stmt): When removing a COMPOUND_EXPR, make
	sure that any basic block pointers to the arms of the COMPOUND_EXPR
	are updated.

	* tree-cfg.c (make_goto_expr_edges): Computed gotos create
	abnormal edges.

Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-cfg.c,v
retrieving revision 1.1.4.124
diff -c -3 -p -r1.1.4.124 tree-cfg.c
*** tree-cfg.c	1 Jul 2003 21:15:35 -0000	1.1.4.124
--- tree-cfg.c	8 Jul 2003 01:17:50 -0000
*************** static bool value_matches_some_label (ed
*** 127,132 ****
--- 127,133 ----
  static void linearize_control_structures (void);
  static bool linearize_cond_expr (tree *, basic_block);
  static void replace_stmt (tree *, tree *);
+ static void move_outgoing_edges (basic_block, basic_block);
  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);
*************** make_goto_expr_edges (basic_block bb)
*** 1331,1349 ****
      {
        dest = GOTO_DESTINATION (goto_t);
        for_call = 0;
-       /* The RTL CFG code got this wrong.  A computed goto creates
- 	 normal edges, except for one case.  Namely a computed goto
- 	 in a nested function has an abnormal edge to the exit block
- 	 (which is handled elsewhere).  */
-       edge_flags = 0;
  
        if (TREE_CODE (dest) == LABEL_DECL && ! NONLOCAL_LABEL (dest))
  	{
  	  make_edge (bb,
  		     VARRAY_BB (label_to_block_map, LABEL_DECL_INDEX (dest)),
! 		     edge_flags);
  	  return;
  	}
      }
  
    /* Look for the block starting with the destination label.  In the
--- 1332,1351 ----
      {
        dest = GOTO_DESTINATION (goto_t);
        for_call = 0;
  
+       /* A GOTO to a local label creates normal edges.  */
        if (TREE_CODE (dest) == LABEL_DECL && ! NONLOCAL_LABEL (dest))
  	{
  	  make_edge (bb,
  		     VARRAY_BB (label_to_block_map, LABEL_DECL_INDEX (dest)),
! 		     0);
  	  return;
  	}
+ 
+       /* If we reach here, then we either have a computed goto or
+ 	 a nonlocal goto.  */
+       edge_flags = EDGE_ABNORMAL;
+ 
      }
  
    /* Look for the block starting with the destination label.  In the
*************** remove_bb (basic_block bb, int remove_st
*** 1840,1845 ****
--- 1842,1852 ----
    bb->pred = NULL;
    bb->succ = NULL;
  
+   /* If we have pdom information, then we must also make sure to
+      clean up the dominance information.  */
+   if (pdom_info)
+     delete_from_dominance_info (pdom_info, bb);
+ 
    /* Remove the basic block from the array.  */
    expunge_block (bb);
  }
*************** remove_stmt (tree *stmt_p)
*** 2001,2006 ****
--- 2008,2015 ----
    tree stmt = *stmt_p;
    basic_block bb = bb_for_stmt (stmt);
    tree parent = parent_stmt (stmt);
+   int update_head = 0;
+   int update_end = 0;
  
    /* If the statement is a control structure, clear the appropriate BB_*
       flags from the basic block.  */
*************** remove_stmt (tree *stmt_p)
*** 2050,2059 ****
--- 2059,2087 ----
        && TREE_OPERAND (stmt, 1)->common.ann->common.type == TREE_ANN_COMMON)
      TREE_OPERAND (stmt, 1)->common.ann = NULL;
  
+   /* If we are removing a COMPOUND_EXPR, we may need to update block
+      head/tail pointers which point into operands of the COMPOUND_EXPR.  */
+   if (TREE_CODE (stmt) == COMPOUND_EXPR)
+     {
+       if (&TREE_OPERAND (stmt, 0) == bb->head_tree_p
+ 	  || &TREE_OPERAND (stmt, 1) == bb->head_tree_p)
+ 	update_head = 1;
+       
+       if (&TREE_OPERAND (stmt, 0) == bb->end_tree_p
+ 	  || &TREE_OPERAND (stmt, 1) == bb->end_tree_p)
+ 	update_end = 1;
+     }
+ 
    /* Replace STMT with an empty statement.  */
    *stmt_p = build_empty_stmt ();
    if (bb)
      add_stmt_to_bb (stmt_p, bb, parent);
+ 
+   if (update_head)
+     bb->head_tree_p = stmt_p;
+ 
+   if (update_end)
+     bb->end_tree_p = stmt_p;
  }
  
  
*************** linearize_cond_expr (tree *entry_p, basi
*** 2370,2375 ****
--- 2398,2407 ----
    tree pred = COND_EXPR_COND (entry);
    tree then_clause = COND_EXPR_THEN (entry);
    tree else_clause = COND_EXPR_ELSE (entry);
+   basic_block then_block = bb_for_stmt (then_clause);
+   basic_block else_block = bb_for_stmt (else_clause);
+   int always_true = (simple_cst_equal (pred, integer_one_node) == 1);
+   int always_false = (simple_cst_equal (pred, integer_zero_node) == 1);
  
    /* Remove the conditional if both branches have been removed.  */
    if (body_is_empty (then_clause) && body_is_empty (else_clause))
*************** linearize_cond_expr (tree *entry_p, basi
*** 2380,2397 ****
        pdom_bb = get_immediate_dominator (pdom_info, bb);
        if (!pdom_bb || !phi_nodes (pdom_bb))
          {
  	  remove_stmt (entry_p);
  	  return true;
  	}
      }
  
    /* Linearize 'if (1)'.  */
!   if (simple_cst_equal (pred, integer_one_node) == 1
!       && body_is_empty (else_clause))
      {
        /* If there is no THEN_CLAUSE, remove the conditional.  */
        if (body_is_empty (then_clause))
! 	remove_stmt (entry_p);
        else
  	merge_tree_blocks (bb, bb_for_stmt (then_clause));
  
--- 2412,2456 ----
        pdom_bb = get_immediate_dominator (pdom_info, bb);
        if (!pdom_bb || !phi_nodes (pdom_bb))
          {
+ 	  /* While neither arm of the conditional has any code, there
+ 	     may still be important edges attached to those arms such
+ 	     as the backedge in a loop, or exception handling related
+ 	     edges (the common characteristic is they are edges implied
+ 	     by control structures which are not explicitly represented
+ 	     in the IL).  */
+ 	  if ((always_true || ! always_false) && then_block)
+ 	    move_outgoing_edges (bb, then_block); 
+ 
+ 	  if ((always_false || ! always_true) && else_block)
+ 	    move_outgoing_edges (bb, else_block); 
+ 	
+ 	  /* Now that we've moved all the edges, go ahead and remove
+ 	     the disconnected blocks.  Note this will remove any edges
+ 	     from BB to the disconnected blocks.  */
+ 	  if (then_block)
+ 	    remove_bb (then_block, 0);
+ 	  if (else_block)
+ 	    remove_bb (else_block, 0);
+ 
+ 	  /* And finally remove the useless statement.  */
  	  remove_stmt (entry_p);
  	  return true;
  	}
      }
  
    /* Linearize 'if (1)'.  */
!   if (always_true && body_is_empty (else_clause))
      {
        /* If there is no THEN_CLAUSE, remove the conditional.  */
        if (body_is_empty (then_clause))
! 	{
! 	  if (then_block)
! 	    {
! 	      move_outgoing_edges (bb, then_block);
! 	      remove_bb (then_block, 0);
! 	    }
! 	  remove_stmt (entry_p);
! 	}
        else
  	merge_tree_blocks (bb, bb_for_stmt (then_clause));
  
*************** linearize_cond_expr (tree *entry_p, basi
*** 2399,2410 ****
      }
  
    /* Linearize 'if (0)'.  */
!   if (simple_cst_equal (pred, integer_zero_node) == 1
!       && body_is_empty (then_clause))
      {
        /* If there is no ELSE_CLAUSE, remove the conditional.  */
        if (body_is_empty (else_clause))
! 	remove_stmt (entry_p);
        else
  	merge_tree_blocks (bb, bb_for_stmt (else_clause));
  
--- 2458,2475 ----
      }
  
    /* Linearize 'if (0)'.  */
!   if (always_false && body_is_empty (then_clause))
      {
        /* If there is no ELSE_CLAUSE, remove the conditional.  */
        if (body_is_empty (else_clause))
! 	{
! 	  if (else_block)
! 	    {
! 	      move_outgoing_edges (bb, else_block);
! 	      remove_bb (else_block, 0);
! 	    }
! 	  remove_stmt (entry_p);
! 	}
        else
  	merge_tree_blocks (bb, bb_for_stmt (else_clause));
  
*************** replace_stmt (tree *tp1, tree *tp2)
*** 4352,4357 ****
--- 4417,4465 ----
      *tp1 = t;
  }
  
+ /* Move all outgoing edges from BB2 to BB1 and keep PHI nodes and
+    dominator information up to date.  */
+ 
+ static void
+ move_outgoing_edges (basic_block bb1, basic_block bb2)
+ {
+   bb_ann_t ann1, ann2;
+ 
+   while (bb2->succ)
+     {
+       tree phi;
+       edge new_edge, old_edge;
+ 	
+       old_edge = bb2->succ;
+       new_edge = make_edge (bb1, old_edge->dest, old_edge->flags);
+ 
+       /* Update PHI nodes at BB2's successor.  The arguments that used to
+ 	 come from BB2 now come from BB1.  */
+       for (phi = phi_nodes (old_edge->dest); phi; phi = TREE_CHAIN (phi))
+ 	{
+ 	  int i;
+ 	  for (i = 0; i < PHI_NUM_ARGS (phi); i++)
+ 	    if (PHI_ARG_EDGE (phi, i) == old_edge)
+ 	      PHI_ARG_EDGE (phi, i) = new_edge;
+ 	}
+ 
+       /* Note that we shouldn't call ssa_remove_edge here because we've
+ 	 already dealt with PHI nodes.  */
+       remove_edge (old_edge);
+     }
+ 
+   /* BB2's dominator children are now BB1's.  Also, remove BB2 as a
+      dominator child of BB1.  */
+   ann1 = bb_ann (bb1);
+   ann2 = bb_ann (bb2);
+   if (ann1->dom_children)
+     {
+       bitmap_clear_bit (ann1->dom_children, bb2->index);
+       if (ann2->dom_children)
+ 	bitmap_a_or_b (ann1->dom_children, ann1->dom_children,
+ 		       ann2->dom_children);
+     }
+ }
  
  /* Given two blocks BB1 and BB2, merge the two blocks by moving all the
     statements in BB2 after the last statement of BB1.
*************** merge_tree_blocks (basic_block bb1, basi
*** 4401,4464 ****
    remap_stmts (bb1, bb2, bb1->end_tree_p);
  
    /* Step 3.  Update edges and dominator children for BB1, and remove BB2.  
*/
-   {
-     bb_ann_t ann1, ann2;
- 
-     /* BB2's successors are now BB1's.  */
-     while (bb1->succ)
-       ssa_remove_edge (bb1->succ);
  
!     while (bb2->succ)
!       {
! 	tree phi;
! 	edge new_edge, old_edge;
! 	
! 	old_edge = bb2->succ;
! 	new_edge = make_edge (bb1, old_edge->dest, old_edge->flags);
! 
! 	/* Update PHI nodes at BB2's successor.  The arguments that used to
! 	   come from BB2 now come from BB1.  */
! 	for (phi = phi_nodes (old_edge->dest); phi; phi = TREE_CHAIN (phi))
! 	  {
! 	    int i;
! 	    for (i = 0; i < PHI_NUM_ARGS (phi); i++)
! 	      if (PHI_ARG_EDGE (phi, i) == old_edge)
! 		PHI_ARG_EDGE (phi, i) = new_edge;
! 	  }
! 
! 	/* Note that we shouldn't call ssa_remove_edge here because we've
! 	   already dealt with PHI nodes.  */
! 	remove_edge (old_edge);
!       }
! 
!     /* BB2's dominator children are now BB1's.  Also, remove BB2 as a
!        dominator child of BB1.  */
!     ann1 = bb_ann (bb1);
!     ann2 = bb_ann (bb2);
!     if (ann1->dom_children)
!       {
! 	bitmap_clear_bit (ann1->dom_children, bb2->index);
! 	if (ann2->dom_children)
! 	  bitmap_a_or_b (ann1->dom_children, ann1->dom_children,
! 			ann2->dom_children);
!       }
! 
!     /* BB1 may no longer be a control expression after merging with BB2.
!        Copy BB2's flags into BB1.  */
!     bb1->flags &= ~BB_CONTROL_EXPR;
!     bb1->flags |= bb2->flags;
! 
!     /* Before removing BB2, clear out its predecessors, successors and
!        head/tail statements, otherwise remove_bb will try to remove
!        statements and edges that now belong to BB1.  */
!     bb2->head_tree_p = NULL;
!     bb2->end_tree_p = NULL;
!     bb2->pred = NULL;
!     bb2->succ = NULL;
!     if (pdom_info != NULL)
!       delete_from_dominance_info (pdom_info, bb2);
!     remove_bb (bb2, 0);
!   }
  }
  
  
--- 4509,4535 ----
    remap_stmts (bb1, bb2, bb1->end_tree_p);
  
    /* Step 3.  Update edges and dominator children for BB1, and remove BB2.  
*/
  
!   /* BB2's successors are now BB1's.  */
!   while (bb1->succ)
!     ssa_remove_edge (bb1->succ);
! 
!   /* Now relocate all the outgoing edges from BB2 to BB1.  */
!   move_outgoing_edges (bb1, bb2);
! 
!   /* BB1 may no longer be a control expression after merging with BB2.
!      Copy BB2's flags into BB1.  */
!   bb1->flags &= ~BB_CONTROL_EXPR;
!   bb1->flags |= bb2->flags;
! 
!   /* Before removing BB2, clear out its predecessors, successors and
!      head/tail statements, otherwise remove_bb will try to remove
!      statements and edges that now belong to BB1.  */
!   bb2->head_tree_p = NULL;
!   bb2->end_tree_p = NULL;
!   bb2->pred = NULL;
!   bb2->succ = NULL;
!   remove_bb (bb2, 0);
  }
  
  







Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]