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] Improve COND_EXPR linearization, statement removal, etc


This patch has 3 small improvements to our tree-ssa optimizers which 
individually and as a group allow us to linearize more COND_EXPRs.

First, we call remove_useless_stmts_and_vars before building the flow
graph and running the optimizers.  This removes a lot of unnecessary
crud that sometimes gets in the way of things like COND_EXPR linearization.

Second, when removing blocks, we remove them in reverse order now.  This
exposes more opportunities for COND_EXPR linearization by making it more
likely the two arms of the COND_EXPR are empty.

Finally, we previously would not linearize a COND_EXPR if the postdominator
of its arms had a PHI node.  This patch allows linearization if the PHI
alternatives resulting from the two arms of the COND_EXPR are equivalent.

Bootstrapped and regression tested (of course).




	* tree-ssa-optimize.c (optimize_function_tree): Call
	remove_useless_stmts_and_vars before building the flow graph.
	* tree-cfg.c (remove_useless_stmts_and_vars): Rename argument from
	first_iteration to remove_unused_vars.

	* tree-cfg.c (remove_unreachable_blocks): Remove blocks in reverse
	order.
	(remove_bb): Remove unwanted call to bsi_next.
	(bsi_remove): Refine code which removes useless COMPOUND_EXPRs to allow
	removal if one of the arms is not associated with a basic block.
	(remove_stmt): Improve check for testing when a basic block head/end
	pointer needs to be updated when removing a COMPOUND_EXPR.

	* tree-cfg.c (phi_alternatives_equal): New function.
	(linearize_cond_expr): Allow linearization if the PHI nodes at the
	target have equivalent arguments for the incoming edges from the THEN		and 
ELSE clauses.


Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-cfg.c,v
retrieving revision 1.1.4.139
diff -c -3 -p -r1.1.4.139 tree-cfg.c
*** tree-cfg.c	4 Aug 2003 18:44:02 -0000	1.1.4.139
--- tree-cfg.c	5 Aug 2003 15:58:24 -0000
*************** cleanup_tree_cfg (void)
*** 1521,1527 ****
     to ensure we eliminate all the useless code.  */
  
  int
! remove_useless_stmts_and_vars (tree *first_p, int first_iteration)
  {
    tree_stmt_iterator i;
    int repeat = 0;
--- 1521,1527 ----
     to ensure we eliminate all the useless code.  */
  
  int
! remove_useless_stmts_and_vars (tree *first_p, int remove_unused_vars)
  {
    tree_stmt_iterator i;
    int repeat = 0;
*************** remove_useless_stmts_and_vars (tree *fir
*** 1549,1562 ****
        code = TREE_CODE (*stmt_p);
        if (code == LOOP_EXPR)
  	repeat |= remove_useless_stmts_and_vars (&LOOP_EXPR_BODY (*stmt_p),
! 						 first_iteration);
        else if (code == COND_EXPR)
  	{
  	  tree then_clause, else_clause, cond;
  	  repeat |= remove_useless_stmts_and_vars (&COND_EXPR_THEN (*stmt_p),
! 						   first_iteration);
  	  repeat |= remove_useless_stmts_and_vars (&COND_EXPR_ELSE (*stmt_p),
! 						   first_iteration);
  
  	  then_clause = COND_EXPR_THEN (*stmt_p);
  	  else_clause = COND_EXPR_ELSE (*stmt_p);
--- 1549,1562 ----
        code = TREE_CODE (*stmt_p);
        if (code == LOOP_EXPR)
  	repeat |= remove_useless_stmts_and_vars (&LOOP_EXPR_BODY (*stmt_p),
! 						 remove_unused_vars);
        else if (code == COND_EXPR)
  	{
  	  tree then_clause, else_clause, cond;
  	  repeat |= remove_useless_stmts_and_vars (&COND_EXPR_THEN (*stmt_p),
! 						   remove_unused_vars);
  	  repeat |= remove_useless_stmts_and_vars (&COND_EXPR_ELSE (*stmt_p),
! 						   remove_unused_vars);
  
  	  then_clause = COND_EXPR_THEN (*stmt_p);
  	  else_clause = COND_EXPR_ELSE (*stmt_p);
*************** remove_useless_stmts_and_vars (tree *fir
*** 1590,1608 ****
  	}
        else if (code == SWITCH_EXPR)
  	repeat |= remove_useless_stmts_and_vars (&SWITCH_BODY (*stmt_p),
! 						 first_iteration);
        else if (code == CATCH_EXPR)
  	repeat |= remove_useless_stmts_and_vars (&CATCH_BODY (*stmt_p),
! 						 first_iteration);
        else if (code == EH_FILTER_EXPR)
  	repeat |= remove_useless_stmts_and_vars (&EH_FILTER_FAILURE (*stmt_p),
! 						 first_iteration);
        else if (code == TRY_CATCH_EXPR || code == TRY_FINALLY_EXPR)
  	{
  	  repeat |= remove_useless_stmts_and_vars (&TREE_OPERAND (*stmt_p, 0),
! 						   first_iteration);
  	  repeat |= remove_useless_stmts_and_vars (&TREE_OPERAND (*stmt_p, 1),
! 						   first_iteration);
  
  	  /* If the handler of a TRY_CATCH or TRY_FINALLY is empty, then
  	     we can emit the TRY block without the enclosing TRY_CATCH_EXPR
--- 1590,1608 ----
  	}
        else if (code == SWITCH_EXPR)
  	repeat |= remove_useless_stmts_and_vars (&SWITCH_BODY (*stmt_p),
! 						 remove_unused_vars);
        else if (code == CATCH_EXPR)
  	repeat |= remove_useless_stmts_and_vars (&CATCH_BODY (*stmt_p),
! 						 remove_unused_vars);
        else if (code == EH_FILTER_EXPR)
  	repeat |= remove_useless_stmts_and_vars (&EH_FILTER_FAILURE (*stmt_p),
! 						 remove_unused_vars);
        else if (code == TRY_CATCH_EXPR || code == TRY_FINALLY_EXPR)
  	{
  	  repeat |= remove_useless_stmts_and_vars (&TREE_OPERAND (*stmt_p, 0),
! 						   remove_unused_vars);
  	  repeat |= remove_useless_stmts_and_vars (&TREE_OPERAND (*stmt_p, 1),
! 						   remove_unused_vars);
  
  	  /* If the handler of a TRY_CATCH or TRY_FINALLY is empty, then
  	     we can emit the TRY block without the enclosing TRY_CATCH_EXPR
*************** remove_useless_stmts_and_vars (tree *fir
*** 1637,1643 ****
  	  tree block;
  	  /* First remove anything underneath the BIND_EXPR.  */
  	  repeat |= remove_useless_stmts_and_vars (&BIND_EXPR_BODY (*stmt_p),
! 						   first_iteration);
  
  	  /* If the BIND_EXPR has no variables, then we can pull everything
  	     up one level and remove the BIND_EXPR, unless this is the
--- 1637,1643 ----
  	  tree block;
  	  /* First remove anything underneath the BIND_EXPR.  */
  	  repeat |= remove_useless_stmts_and_vars (&BIND_EXPR_BODY (*stmt_p),
! 						   remove_unused_vars);
  
  	  /* If the BIND_EXPR has no variables, then we can pull everything
  	     up one level and remove the BIND_EXPR, unless this is the
*************** remove_useless_stmts_and_vars (tree *fir
*** 1657,1663 ****
  	      *stmt_p = BIND_EXPR_BODY (*stmt_p);
  	      repeat = 1;
  	    }
! 	  else if (first_iteration)
  	    {
  	      /* If we were unable to completely eliminate the BIND_EXPR,
  		 go ahead and prune out any unused variables.  We do not
--- 1657,1663 ----
  	      *stmt_p = BIND_EXPR_BODY (*stmt_p);
  	      repeat = 1;
  	    }
! 	  else if (remove_unused_vars)
  	    {
  	      /* If we were unable to completely eliminate the BIND_EXPR,
  		 go ahead and prune out any unused variables.  We do not
*************** remove_useless_stmts_and_vars (tree *fir
*** 1785,1798 ****
  static void
  remove_unreachable_blocks (void)
  {
!   int i, n;
  
    find_unreachable_blocks ();
  
!   /* n_basic_blocks will change constantly as we delete blocks, so get a
!      copy first.  */
!   n = n_basic_blocks;
!   for (i = 0; i < n; i++)
      {
        basic_block bb = BASIC_BLOCK (i);
  
--- 1785,1797 ----
  static void
  remove_unreachable_blocks (void)
  {
!   int i;
  
    find_unreachable_blocks ();
  
!   /* Remove unreachable blocks in reverse.  That will expose more unnecessary
!      COMPOUND_EXPRs that we can remove.  */
!   for (i = n_basic_blocks - 1; i >= 0; i--)
      {
        basic_block bb = BASIC_BLOCK (i);
  
*************** remove_bb (basic_block bb, int remove_st
*** 1915,1922 ****
  	  loc.line = get_lineno (stmt);
  	  bsi_remove (&i);
          }
-       else
- 	bsi_next (&i);
      }
  
    /* If requested, give a warning that the first statement in the
--- 1914,1919 ----
*************** bsi_remove (block_stmt_iterator *i)
*** 2055,2068 ****
      {
        if (TREE_CODE (t) == COMPOUND_EXPR)
  	{
! 	  basic_block bb = bb_for_stmt (TREE_OPERAND (t, 0));
  
  	  remove_stmt (&TREE_OPERAND (t, 0));
  
! 	  /* If both operands are empty and they belong to the same basic
! 	     block, then delete the whole COMPOUND_EXPR.  */
  	  if (IS_EMPTY_STMT (TREE_OPERAND (t, 1))
! 	      && bb == bb_for_stmt (TREE_OPERAND (t, 1)))
  	    remove_stmt (i->tp);
  	}
        else
--- 2052,2069 ----
      {
        if (TREE_CODE (t) == COMPOUND_EXPR)
  	{
! 	  basic_block op0_bb = bb_for_stmt (TREE_OPERAND (t, 0));
! 	  basic_block op1_bb = bb_for_stmt (TREE_OPERAND (t, 1));
  
  	  remove_stmt (&TREE_OPERAND (t, 0));
  
! 	  /* If both operands are empty and they are not associated
! 	     with different basic blocks, then delete the whole
! 	     COMPOUND_EXPR.  */
  	  if (IS_EMPTY_STMT (TREE_OPERAND (t, 1))
! 	      && (op0_bb == NULL
! 		  || op1_bb == NULL
! 		  || op0_bb == op1_bb))
  	    remove_stmt (i->tp);
  	}
        else
*************** remove_stmt (tree *stmt_p)
*** 2163,2174 ****
       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;
      }
  
--- 2164,2190 ----
       head/tail pointers which point into operands of the COMPOUND_EXPR.  */
    if (TREE_CODE (stmt) == COMPOUND_EXPR)
      {
!       basic_block op0_bb = bb_for_stmt (TREE_OPERAND (stmt, 0));
!       basic_block op1_bb = bb_for_stmt (TREE_OPERAND (stmt, 1));
! 
! #ifdef ENABLE_CHECKING
!       if (op0_bb && op1_bb && op0_bb != op1_bb)
! 	abort ();
! #endif
! 
!       if (op0_bb)
! 	bb = op0_bb;
!       else
! 	bb = op1_bb;
! 
!       if (bb
! 	  && (&TREE_OPERAND (stmt, 0) == bb->head_tree_p
! 	      || &TREE_OPERAND (stmt, 1) == bb->head_tree_p))
  	update_head = 1;
  
!       if (bb
! 	  && (&TREE_OPERAND (stmt, 0) == bb->end_tree_p
! 	      || &TREE_OPERAND (stmt, 1) == bb->end_tree_p))
  	update_end = 1;
      }
  
*************** linearize_control_structures (void)
*** 2485,2490 ****
--- 2501,2542 ----
      }
  }
  
+ /* If all the phi nodes in PHI have alternatives for BB1 and BB2 and
+    those alterantives are equal in each of the PHI nodes, then return
+    nonzero, else return zero.  */
+ 
+ static int
+ phi_alternatives_equal (tree phi, basic_block bb1, basic_block bb2)
+ {
+   /* Walk through each PHI nodes on the chain.  */
+   for ( ; phi ; phi = TREE_CHAIN (phi))
+     {
+       int i;
+       tree val1 = NULL;
+       tree val2 = NULL;
+ 
+       /* Find the alterantive associated with BB1 and BB2.  Quit when we
+ 	 have found both or we exhaust the alternatives.  */
+       for (i = 0; i < PHI_NUM_ARGS (phi); i++)
+ 	{
+ 	  if (PHI_ARG_EDGE (phi, i)->src == bb1)
+ 	    val1 = PHI_ARG_DEF (phi, i);
+ 	  if (PHI_ARG_EDGE (phi, i)->src == bb2)
+ 	    val2 = PHI_ARG_DEF (phi, i);
+ 
+ 	  if (val1 && val2)
+ 	    break;
+ 	}
+ 
+       /* If we exhaused the alternatives or the alternatives found are
+ 	 not equal, then return false.  */
+       if (i == PHI_NUM_ARGS (phi)
+ 	  || ! operand_equal_p (val1, val2, 0))
+ 	return false;
+     }
+ 
+   return true;
+ }
  
  /* Convert conditional expressions of the form 'if (1)' and 'if (0)' into
     straight line code.  ENTRY_P is a pointer to the COND_EXPR statement to
*************** linearize_cond_expr (tree *entry_p, basi
*** 2510,2516 ****
        if (pdom_info == NULL)
  	pdom_info = calculate_dominance_info (CDI_POST_DOMINATORS);
        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
--- 2562,2575 ----
        if (pdom_info == NULL)
  	pdom_info = calculate_dominance_info (CDI_POST_DOMINATORS);
        pdom_bb = get_immediate_dominator (pdom_info, bb);
! 
!       /* If there is no post dominator, or the post dominator has no
! 	 PHI nodes, or the PHI node alternatives are equal, then we
! 	 can eliminate this conditional.  */
!       if (!pdom_bb
! 	  || !phi_nodes (pdom_bb)
! 	  || phi_alternatives_equal (phi_nodes (pdom_bb),
! 				     then_block, else_block))
          {
  	  /* While neither arm of the conditional has any code, there
  	     may still be important edges attached to those arms such
Index: tree-optimize.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-optimize.c,v
retrieving revision 1.1.4.41
diff -c -3 -p -r1.1.4.41 tree-optimize.c
*** tree-optimize.c	15 Jul 2003 05:53:16 -0000	1.1.4.41
--- tree-optimize.c	5 Aug 2003 15:58:24 -0000
*************** optimize_function_tree (tree fndecl)
*** 56,61 ****
--- 56,66 ----
  
    /* Build the flowgraph.  */
    init_flow ();
+ 
+   /* Run a pass over the statements deleting any obviously useless
+      statements before we build the CFG.  */
+   remove_useless_stmts_and_vars (&DECL_SAVED_TREE (fndecl), 0);
+ 
    build_tree_cfg (fnbody);
  
    /* Begin analysis and optimization passes.  */




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