Improve VRP, partial fix pr26344

Jeffrey A Law law@redhat.com
Wed Mar 8 22:10:00 GMT 2006


I initially thought that the best solution for these problems
was going to be to move the forwprop pass.  While that approach
looked appealing (and still has some overall appeal), it's
no longer my preferred approach.  Basically it's unclear at this
time if it's really going to be better or if it's just going to
trade one set of missed micro optimizations for another set of
missed micro optimizations.

So I went back and revisited VRP in the hope of finding a way
to safely and efficiently implement the backwards propagation of
non-null ranges through pointer typecasts.

For those not familiar with VRP and the propagation engine it
uses, it is *critical* that we not go backwards through the 
lattice.  ie, once something is VR_VARYING, it does not go
back to VR_RANGE or VR_ANTI_RANGE.

It is also important to not generate lots of useless ASSERT_EXPRs
from a compile-time performance standpoint.  For example, if
a pointer is used once and only once in a dereference, we do not
want to generate an ASSERT_EXPR for it claiming it has a non-null
range.  Note this need makes it virtually impossible to perform
the backwards propagation after the propagation engine has run
(we won't have ASSERT_EXPRs for the key pointers and thus no ranges
for them).

The good news is initial discovery of non-null pointers occurs
before the VRP propagation engine runs.  If we could do the
backwards propagation during that initial non-null discovery,
then we would have a fighting chance.  And that's exactly what
this patch does.

With this patch we always attempt to infer a value range, even
for single use operands -- note carefully that we still suppress
creating ASSERT_EXPRs for such operands to avoid compile time
regressions.  When we discover a non-null pointer, we then walk
up its use-def chain to see if the pointer was set via a NOP_EXPR
type conversion from another pointer type.  If we find such a
type conversion and the source pointer for that type conversion is
used more than once, then we register an ASSERT_EXPR for the
source pointer in the NOP_EXPR.

This fixes two of the three gcc.dg/tree-ssa missed optimization
regressions as well as the one reported for C++.

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


-------------- next part --------------
	* tree-vrp.c (infer_value_range): Only count pointer uses
	and dereferences if -fdelete-null-pointer-checks is enabled.

	* tree-vrp.c (find_assert_locations): Infer value ranges for
	single use pointers, but do not create ASSERT_EXPRs for them.
	When a non-null range is inferred for a pointer, backwards
	propagate that range to other equivalent pointers through the
	use-def chain.

	* gcc.dg/tree-ssa/20030730-1.c: No longer expected to fail.
	* gcc.dg/tree-ssa/20030730-2.c: No longer expected to fail.
	* g++.dg/tree-ssa/pr26406.C: New test.

Index: gcc/tree-vrp.c
===================================================================
*** gcc/tree-vrp.c	(revision 111822)
--- gcc/tree-vrp.c	(working copy)
*************** infer_value_range (tree stmt, tree op, e
*** 2440,2455 ****
    if (stmt_ends_bb_p (stmt) && EDGE_COUNT (bb_for_stmt (stmt)->succs) == 0)
      return false;
  
!   if (POINTER_TYPE_P (TREE_TYPE (op)))
      {
        bool is_store;
        unsigned num_uses, num_derefs;
  
        count_uses_and_derefs (op, stmt, &num_uses, &num_derefs, &is_store);
!       if (num_derefs > 0 && flag_delete_null_pointer_checks)
  	{
- 	  /* We can only assume that a pointer dereference will yield
- 	     non-NULL if -fdelete-null-pointer-checks is enabled.  */
  	  *val_p = build_int_cst (TREE_TYPE (op), 0);
  	  *comp_code_p = NE_EXPR;
  	  return true;
--- 2440,2455 ----
    if (stmt_ends_bb_p (stmt) && EDGE_COUNT (bb_for_stmt (stmt)->succs) == 0)
      return false;
  
!   /* We can only assume that a pointer dereference will yield
!      non-NULL if -fdelete-null-pointer-checks is enabled.  */
!   if (flag_delete_null_pointer_checks && POINTER_TYPE_P (TREE_TYPE (op)))
      {
        bool is_store;
        unsigned num_uses, num_derefs;
  
        count_uses_and_derefs (op, stmt, &num_uses, &num_derefs, &is_store);
!       if (num_derefs > 0)
  	{
  	  *val_p = build_int_cst (TREE_TYPE (op), 0);
  	  *comp_code_p = NE_EXPR;
  	  return true;
*************** find_assert_locations (basic_block bb)
*** 2952,2972 ****
  	     operands it was looking for was present in the sub-graph.  */
  	  SET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
  
- 	  /* If OP is used only once, namely in this STMT, don't
- 	     bother creating an ASSERT_EXPR for it.  Such an
- 	     ASSERT_EXPR would do nothing but increase compile time.
- 	     Experiments show that with this simple check, we can save
- 	     more than 20% of ASSERT_EXPRs.  */
- 	  if (has_single_use (op))
- 	    continue;
- 
  	  /* If OP is used in such a way that we can infer a value
  	     range for it, and we don't find a previous assertion for
  	     it, create a new assertion location node for OP.  */
  	  if (infer_value_range (stmt, op, &comp_code, &value))
  	    {
! 	      register_new_assert_for (op, comp_code, value, bb, NULL, si);
! 	      need_assert = true;
  	    }
  	}
  
--- 2952,3001 ----
  	     operands it was looking for was present in the sub-graph.  */
  	  SET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
  
  	  /* If OP is used in such a way that we can infer a value
  	     range for it, and we don't find a previous assertion for
  	     it, create a new assertion location node for OP.  */
  	  if (infer_value_range (stmt, op, &comp_code, &value))
  	    {
! 	      /* If we are able to infer a non-zero value range for OP,
! 		 then walk backwards through the use-def chain to see if OP
! 		 was set via a typecast.
! 
! 		 If so, then we can also infer a nonzero value range
! 		 for the operand of the NOP_EXPR.  */
! 	      if (comp_code == NE_EXPR && integer_zerop (value))
! 		{
! 		  tree t = op;
! 		  tree def_stmt = SSA_NAME_DEF_STMT (t);
! 	
! 		  while (TREE_CODE (def_stmt) == MODIFY_EXPR
! 			 && TREE_CODE (TREE_OPERAND (def_stmt, 1)) == NOP_EXPR
! 			 && TREE_CODE (TREE_OPERAND (TREE_OPERAND (def_stmt, 1), 0)) == SSA_NAME
! 			 && POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (TREE_OPERAND (def_stmt, 1), 0))))
! 		    {
! 		      t = TREE_OPERAND (TREE_OPERAND (def_stmt, 1), 0);
! 		      def_stmt = SSA_NAME_DEF_STMT (t);
! 
! 		      /* Note we want to register the assert for the
! 			 operand of the NOP_EXPR after SI, not after the
! 			 conversion.  */
! 		      if (! has_single_use (t))
! 			{
! 			  register_new_assert_for (t, comp_code, value,
! 						   bb, NULL, si);
! 			  need_assert = true;
! 			}
! 		    }
! 		}
! 
! 	      /* If OP is used only once, namely in this STMT, don't
! 		 bother creating an ASSERT_EXPR for it.  Such an
! 		 ASSERT_EXPR would do nothing but increase compile time.  */
! 	      if (!has_single_use (op))
! 		{
! 		  register_new_assert_for (op, comp_code, value, bb, NULL, si);
! 		  need_assert = true;
! 		}
  	    }
  	}
  
Index: gcc/testsuite/gcc.dg/tree-ssa/20030730-1.c
===================================================================
*** gcc/testsuite/gcc.dg/tree-ssa/20030730-1.c	(revision 111822)
--- gcc/testsuite/gcc.dg/tree-ssa/20030730-1.c	(working copy)
*************** foo (int attr_kind, unsigned long offset
*** 19,24 ****
  }
  
  /* There should be no IF conditionals.  */
! /* { dg-final { scan-tree-dump-times "if " 0 "dom3" { xfail *-*-* } } } */
                                                                                  
  /* { dg-final { cleanup-tree-dump "dom3" } } */
--- 19,24 ----
  }
  
  /* There should be no IF conditionals.  */
! /* { dg-final { scan-tree-dump-times "if " 0 "dom3" } } */
                                                                                  
  /* { dg-final { cleanup-tree-dump "dom3" } } */
Index: gcc/testsuite/gcc.dg/tree-ssa/20030730-2.c
===================================================================
*** gcc/testsuite/gcc.dg/tree-ssa/20030730-2.c	(revision 111822)
--- gcc/testsuite/gcc.dg/tree-ssa/20030730-2.c	(working copy)
*************** foo (int attr_kind, unsigned long offset
*** 19,24 ****
  }
  
  /* There should be no IF conditionals.  */
! /* { dg-final { scan-tree-dump-times "if " 0 "dom3" { xfail *-*-* } } } */
  
  /* { dg-final { cleanup-tree-dump "dom3" } } */
--- 19,24 ----
  }
  
  /* There should be no IF conditionals.  */
! /* { dg-final { scan-tree-dump-times "if " 0 "dom3" } } */
  
  /* { dg-final { cleanup-tree-dump "dom3" } } */
Index: gcc/testsuite/g++.dg/tree-ssa/pr26406.C
===================================================================
*** gcc/testsuite/g++.dg/tree-ssa/pr26406.C	(revision 0)
--- gcc/testsuite/g++.dg/tree-ssa/pr26406.C	(revision 0)
***************
*** 0 ****
--- 1,14 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O2 -fdump-tree-optimized" } */
+ 
+ int *f(int *b)
+ {
+   int * a = new int[104];
+   *a = 1;
+   if (a == 0)
+     return b;
+   return a;
+ }
+ 
+ /* { dg-final { scan-tree-dump-not "if" "optimized" } } */
+ /* { dg-final { cleanup-tree-dump "optimized" } } */


More information about the Gcc-patches mailing list