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]

Re: [Bug optimization/13875] [tree-ssa] missed jump thread optimization on the tree-level


In message <20040303181405.32100.qmail@sources.redhat.com>, "dann at godzilla d
ot ics dot uci dot edu" writes:
 >
 >------- Additional Comments From dann at godzilla dot ics dot uci dot edu  20
 >04-03-03 18:14 -------
 >As per Jeff's request, a brief look at generate-3.4.ii.t54.vars function:
 >
 >void MODEL_GENERATOR::assumePTLiteral(bool&, bool, const GLITERAL&, GINTERPRE
 >T&)
 >[snip]
 >
 >  T.8294 = (bool)(int)ptl->neg;
 >  if (T.8294 == 0) goto <L18>; else goto <L17>;
 >
 ><L17>:;
 >  if (reallyPT) goto <L21>; else goto <L18>;
 >
 ><L18>:;
 >  T.8297 = !T.8294;
 >  if (T.8297 == 0) goto <L33>; else goto <L20>;
 >
 ><L20>:;
 >  if (reallyPT == 0) goto <L21>; else goto <L33>;
 >
 ><L21>:;
 >  if (TraceLevel > 1) goto <L22>; else goto <L31>;
 >
 >see some jump threading opportunities missed, the  T.8297 variable
 >could be eliminated.
 >
 >Other observations: 
 > --   casts like "if ((bool)(int)(bool) ....)"
 > --  lots of code will be eliminated after PR13954 and PR13761 are fixed
OK.  It turned out to be easier to go ahead and propagate booleans
more aggressively.   Given:

     x = !y;

     if (x == 0)

     ...

     if (x != 0)

     ...

     if (x == 0)


Even though x is used more than, it is advantageous to go ahead and forward
propagate Y into the conditionals since we won't introduce any new expression
evaluations.  ie  the above turns into


      if (y != 0)

      ...

      if (y == 0)

      ...

      if (y != 0)





Additionally code which was supposed to record an SSA_NAME = <const>
equivalence due to following a COND_EXPR was instead recording a less
precise equivalence for the expression in the COND_EXPR due to a minor
buglet.

This is preventing some constant propagations from occurring which are
critical to fully optimizing the code in question.

The tree-ssa-forwprop.c looks larger than it really is...  There's some
reformatting going on as a hunk of code was moved outside a loop.

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

	* tree-ssa-dom.c: (get_eq_expr_value): Fix typo when comparing a
	boolean against a constant.
	* tree-ssa-forwprop.c (record_single_argument_cond_exprs): Do not
	record the same SSA_NAME more than once.  Only record the SSA_NAME
	tested, not the COND_EXPR.
	(substitute_single_use_vars): Substitute booleans which are
	set from a TRUTH_NOT_EXPR even if they have more than one use site.

Index: tree-ssa-dom.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-dom.c,v
retrieving revision 1.1.2.145
diff -c -p -r1.1.2.145 tree-ssa-dom.c
*** tree-ssa-dom.c	2 Mar 2004 18:41:49 -0000	1.1.2.145
--- tree-ssa-dom.c	8 Mar 2004 01:55:40 -0000
*************** get_eq_expr_value (tree if_stmt,
*** 2889,2895 ****
        tree op1 = TREE_OPERAND (cond, 1);
  
        /* Special case comparing booleans against a constant as we know
! 	 the value of op0 on both arms of the branch.  */
        if ((TREE_CODE (cond) == EQ_EXPR || TREE_CODE (cond) == NE_EXPR)
  	  && TREE_CODE (op0) == SSA_NAME
  	  && TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE
--- 2889,2896 ----
        tree op1 = TREE_OPERAND (cond, 1);
  
        /* Special case comparing booleans against a constant as we know
! 	 the value of OP0 on both arms of the branch.  ie, we can record
! 	 an equivalence for OP0 rather than COND.  */
        if ((TREE_CODE (cond) == EQ_EXPR || TREE_CODE (cond) == NE_EXPR)
  	  && TREE_CODE (op0) == SSA_NAME
  	  && TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE
*************** get_eq_expr_value (tree if_stmt,
*** 2907,2913 ****
  	      else
  		retval.src = boolean_false_node;
  	    }
! 	  retval.dst = cond;
  	  return retval;
  	}
  
--- 2908,2914 ----
  	      else
  		retval.src = boolean_false_node;
  	    }
! 	  retval.dst = op0;
  	  return retval;
  	}
  
Index: tree-ssa-forwprop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-forwprop.c,v
retrieving revision 1.1.2.4
diff -c -p -r1.1.2.4 tree-ssa-forwprop.c
*** tree-ssa-forwprop.c	5 Mar 2004 20:54:47 -0000	1.1.2.4
--- tree-ssa-forwprop.c	8 Mar 2004 02:05:38 -0000
*************** record_single_argument_cond_exprs (void)
*** 108,114 ****
  
    vars = BITMAP_XMALLOC ();
  
!   VARRAY_TREE_INIT (retval, 10, "forward propagation objects");
  
    /* The first pass over the blocks gathers the set of variables we need
       immediate uses for as well as the set of interesting COND_EXPRs.
--- 108,114 ----
  
    vars = BITMAP_XMALLOC ();
  
!   VARRAY_TREE_INIT (retval, 10, "forward propagation vars");
  
    /* The first pass over the blocks gathers the set of variables we need
       immediate uses for as well as the set of interesting COND_EXPRs.
*************** record_single_argument_cond_exprs (void)
*** 146,151 ****
--- 146,156 ----
  	      else
  		test_var = TREE_OPERAND (cond, 0);
  
+ 	      /* If we have already recorded this SSA_NAME as interesting,
+ 		 do not do so again.  */
+ 	      if (bitmap_bit_p (vars, SSA_NAME_VERSION (test_var)))
+ 		continue;
+ 
  	      /* Now get the defining statement for TEST_VAR and see if it
  		 something we are interested in.  */
  	      def = SSA_NAME_DEF_STMT (test_var);
*************** record_single_argument_cond_exprs (void)
*** 211,219 ****
  		  else
  		    continue;
  
! 		  /* All the tests passed, record COND_EXPR and TEST_VAR
! 		     as interesting.  */
! 		  VARRAY_PUSH_TREE (retval, last);
  		  VARRAY_PUSH_TREE (retval, test_var);
  		  bitmap_set_bit (vars, SSA_NAME_VERSION (test_var));
  		}
--- 216,222 ----
  		  else
  		    continue;
  
! 		  /* All the tests passed, record TEST_VAR as interesting.  */
  		  VARRAY_PUSH_TREE (retval, test_var);
  		  bitmap_set_bit (vars, SSA_NAME_VERSION (test_var));
  		}
*************** record_single_argument_cond_exprs (void)
*** 223,230 ****
    return retval;
  }
  
! /* Given FORWPROP_DATA containing pairs of potentially optimizable COND_EXPRs
!    and the SSA_NAME used in the COND_EXPR, attempt to rewrite the condition
     in each COND_EXPR to use the RHS of the statement which defines the
     SSA_NAME used in the COND_EXPR.  */
    
--- 226,233 ----
    return retval;
  }
  
! /* Given FORWPROP_DATA containing SSA_NAMEs which are used in COND_EXPRs
!    that we may be able to optimize, attempt to rewrite the condition
     in each COND_EXPR to use the RHS of the statement which defines the
     SSA_NAME used in the COND_EXPR.  */
    
*************** substitute_single_use_vars (varray_type 
*** 233,261 ****
  {
    unsigned int i;
  
!   for (i = 0; i < VARRAY_ACTIVE_SIZE (forwprop_data); i += 2)
      {
!       tree test_var = VARRAY_TREE (forwprop_data, i + 1);
        tree def = SSA_NAME_DEF_STMT (test_var);
        dataflow_t df;
!       int num_uses;
  
        /* Now compute the immediate uses of TEST_VAR.  */
        df = get_immediate_uses (def);
        num_uses = num_immediate_uses (df);
  
!       /* If TEST_VAR is used precisely one time, then we may have
!          an optimizable case.  */
!       if (num_uses == 1)
  	{
! 	  tree cond_stmt = VARRAY_TREE (forwprop_data, i);
! 	  tree cond = COND_EXPR_COND (cond_stmt);
! 	  enum tree_code cond_code = TREE_CODE (cond);
! 	  tree def_rhs = TREE_OPERAND (def, 1);
! 	  enum tree_code def_rhs_code = TREE_CODE (def_rhs);
! 	  block_stmt_iterator bsi;
  	  tree new_cond;
  
  	  /* If the definition of the single use variable was from an
  	     arithmetic operation, then we just need to adjust the
  	     constant in the COND_EXPR_COND and update the variable tested.  */
--- 236,288 ----
  {
    unsigned int i;
  
!   for (i = 0; i < VARRAY_ACTIVE_SIZE (forwprop_data); i++)
      {
!       tree test_var = VARRAY_TREE (forwprop_data, i);
        tree def = SSA_NAME_DEF_STMT (test_var);
        dataflow_t df;
!       int j, num_uses, propagated_uses;
!       block_stmt_iterator bsi;
  
        /* Now compute the immediate uses of TEST_VAR.  */
        df = get_immediate_uses (def);
        num_uses = num_immediate_uses (df);
+       propagated_uses = 0;
  
!       /* If TEST_VAR is used more than once and is not a boolean set
! 	 via TRUTH_NOT_EXPR with another SSA_NAME as its argument, then
! 	 we can not optimize.  */
!       if (num_uses == 1
! 	  || (TREE_CODE (TREE_TYPE (test_var)) == BOOLEAN_TYPE
! 	      && TREE_CODE (TREE_OPERAND (def, 1)) == TRUTH_NOT_EXPR
! 	      && (TREE_CODE (TREE_OPERAND (TREE_OPERAND (def, 1), 0))
! 		  == SSA_NAME)))
! 	;
!       else
! 	continue;
! 
!       /* Walk over each use and try to forward propagate the RHS of
! 	 DEF into the use.  */
!       for (j = 0; j < num_uses; j++)
  	{
! 	  tree cond_stmt;
! 	  tree cond;
! 	  enum tree_code cond_code;
! 	  tree def_rhs;
! 	  enum tree_code def_rhs_code;
  	  tree new_cond;
  
+ 	  cond_stmt = immediate_use (df, j);
+ 
+ 	  /* For now we can only propagate into COND_EXPRs.  */
+ 	  if (TREE_CODE (cond_stmt) != COND_EXPR) 
+ 	    continue;
+ 
+ 	  cond = COND_EXPR_COND (cond_stmt);
+ 	  cond_code = TREE_CODE (cond);
+ 	  def_rhs = TREE_OPERAND (def, 1);
+ 	  def_rhs_code = TREE_CODE (def_rhs);
+ 
  	  /* If the definition of the single use variable was from an
  	     arithmetic operation, then we just need to adjust the
  	     constant in the COND_EXPR_COND and update the variable tested.  */
*************** substitute_single_use_vars (varray_type 
*** 333,353 ****
  	  /* Replace the condition.  */
  	  COND_EXPR_COND (cond_stmt) = new_cond;
  	  modify_stmt (cond_stmt);
! 
! 	  /* Now delete the defining statement, unfortunately
! 	     we have to find the defining statement in whatever
! 	     block it might be in.  */
! 	  for (bsi = bsi_start (bb_for_stmt (def));
! 	       !bsi_end_p (bsi);
! 	       bsi_next (&bsi))
! 	    {
! 	      if (def == bsi_stmt (bsi))
! 		{
! 		  bsi_remove (&bsi);
! 		  break;
! 		}
! 	    }
  	}
      }
  }
  
--- 360,382 ----
  	  /* Replace the condition.  */
  	  COND_EXPR_COND (cond_stmt) = new_cond;
  	  modify_stmt (cond_stmt);
! 	  propagated_uses++;
  	}
+ 
+       /* If we propagated into all the uses, then we can delete DEF.
+ 	 Unfortunately, we have to find the defining statement in
+ 	 whatever block it might be in.  */
+       if (num_uses && num_uses == propagated_uses)
+ 	for (bsi = bsi_start (bb_for_stmt (def));
+ 	     !bsi_end_p (bsi);
+ 	     bsi_next (&bsi))
+ 	  {
+ 	    if (def == bsi_stmt (bsi))
+ 	      {
+ 		bsi_remove (&bsi);
+ 		break;
+ 	      }
+ 	  }
      }
  }
  





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