Improve null pointer check elimination

[law at redhat dot com]

This patch improves our null pointer check elimination optimization in two
ways.

First, when all arguments to a PHI have the nonzero property, then the 
result of the PHI has the nonzero property.  This allows us to eliminate
a few more useless null pointer checks in GCC itself.

Second, if we have a dereference of a pointer (P2) which is set from the
cast of another pointer (P1), then we know that both P1 and P2 have nonzero
values.  This allows us to eliminate a fair number of null pointer checks
in libjava.

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

	* toplev.h (flag_delete_null_pointer_checks): Move from here to...
	* flags.h (flag_delete_null_pointer_checks): Here.
	* tree-flow.h (cprop_into_successor_phis): Add argument to prototype.
	* tree-phinodes.c (resize_phi_node): Initialize PHI_ARG_NONZERO.
	(add_phi_arg, remove_phi_arg_num): Similarly.
	* tree-ssa-copy.c (cprop_into_successor_phis): Propagate nonzero 
	property into PHI nodes.
	* tree-ssa-dom.c: Remove redundant inclusion of flags.h.
	(record_equivalences_from_phis): If all PHI arguments are known to be
	nonzero, then the result must be nonzero as well.
	(cprop_into_phis): Pass nonzero_vars bitmap to cprop_into_successor_phis
	(record_equivalences_from_stmt): Check flag_delete_null_pointer_checks
	appropriately.  Walk the USE-DEF chains and propagate nonzero property
	as appropriate.
	* tree.h (PHI_ARG_NONZERO): Define.
	(phi_arg_d): Add nonzero flag.

Index: flags.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/flags.h,v
retrieving revision 1.138
diff -c -p -r1.138 flags.h
*** flags.h	13 May 2004 06:39:39 -0000	1.138
--- flags.h	17 May 2004 18:28:42 -0000
*************** extern int flag_cse_skip_blocks;
*** 323,328 ****
--- 323,332 ----
     perform miscellaneous relatively-expensive optimizations.  */
  extern int flag_expensive_optimizations;
  
+ /* Nonzero means to use global dataflow analysis to eliminate
+    useless null pointer tests.  */
+ extern int flag_delete_null_pointer_checks;
+ 
  /* Nonzero means don't put addresses of constant functions in registers.
     Used for compiling the Unix kernel, where strange substitutions are
     done on the assembly output.  */
Index: toplev.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/toplev.h,v
retrieving revision 1.120
diff -c -p -r1.120 toplev.h
*** toplev.h	13 May 2004 06:39:45 -0000	1.120
--- toplev.h	17 May 2004 18:28:42 -0000
*************** extern int flag_loop_optimize;
*** 113,119 ****
  extern int flag_crossjumping;
  extern int flag_if_conversion;
  extern int flag_if_conversion2;
- extern int flag_delete_null_pointer_checks;
  extern int flag_keep_static_consts;
  extern int flag_peel_loops;
  extern int flag_rerun_cse_after_loop;
--- 113,118 ----
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow.h,v
retrieving revision 2.3
diff -c -p -r2.3 tree-flow.h
*** tree-flow.h	14 May 2004 15:27:36 -0000	2.3
--- tree-flow.h	17 May 2004 18:28:44 -0000
*************** extern void debug_dominator_optimization
*** 575,581 ****
  extern void propagate_value (tree *, tree);
  extern void replace_exp (tree *, tree);
  extern bool cprop_into_stmt (tree, varray_type);
! extern void cprop_into_successor_phis (basic_block, varray_type);
  
  /* In tree-flow-inline.h  */
  static inline int phi_arg_from_edge (tree, edge);
--- 575,581 ----
  extern void propagate_value (tree *, tree);
  extern void replace_exp (tree *, tree);
  extern bool cprop_into_stmt (tree, varray_type);
! extern void cprop_into_successor_phis (basic_block, varray_type, bitmap);
  
  /* In tree-flow-inline.h  */
  static inline int phi_arg_from_edge (tree, edge);
Index: tree-phinodes.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-phinodes.c,v
retrieving revision 2.1
diff -c -p -r2.1 tree-phinodes.c
*** tree-phinodes.c	13 May 2004 06:39:48 -0000	2.1
--- tree-phinodes.c	17 May 2004 18:28:46 -0000
*************** resize_phi_node (tree *phi, int len)
*** 280,285 ****
--- 280,286 ----
      {
        PHI_ARG_DEF (new_phi, i) = NULL_TREE;
        PHI_ARG_EDGE (new_phi, i) = NULL;
+       PHI_ARG_NONZERO (new_phi, i) = false;
      }
  
    *phi = new_phi;
*************** add_phi_arg (tree *phi, tree def, edge e
*** 366,371 ****
--- 367,373 ----
  
    PHI_ARG_DEF (*phi, i) = def;
    PHI_ARG_EDGE (*phi, i) = e;
+   PHI_ARG_NONZERO (*phi, i) = false;
    PHI_NUM_ARGS (*phi)++;
  }
  
*************** remove_phi_arg_num (tree phi, int i)
*** 408,418 ****
--- 410,422 ----
      {
        PHI_ARG_DEF (phi, i) = PHI_ARG_DEF (phi, num_elem - 1);
        PHI_ARG_EDGE (phi, i) = PHI_ARG_EDGE (phi, num_elem - 1);
+       PHI_ARG_NONZERO (phi, i) = PHI_ARG_NONZERO (phi, num_elem - 1);
      }
  
    /* Shrink the vector and return.  */
    PHI_ARG_DEF (phi, num_elem - 1) = NULL_TREE;
    PHI_ARG_EDGE (phi, num_elem - 1) = NULL;
+   PHI_ARG_NONZERO (phi, num_elem - 1) = false;
    PHI_NUM_ARGS (phi)--;
  
    /* If we removed the last PHI argument, then go ahead and
Index: tree-ssa-copy.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-copy.c,v
retrieving revision 2.1
diff -c -p -r2.1 tree-ssa-copy.c
*** tree-ssa-copy.c	13 May 2004 06:39:49 -0000	2.1
--- tree-ssa-copy.c	17 May 2004 18:28:46 -0000
*************** cprop_into_stmt (tree stmt, varray_type 
*** 272,282 ****
  /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
     known value for that SSA_NAME (or NULL if no value is known).  
  
!    Propagate values from CONST_AND_COPIES into the PHI nodes of the
!    successors of BB.  */
  
  void
! cprop_into_successor_phis (basic_block bb, varray_type const_and_copies)
  {
    edge e;
  
--- 272,287 ----
  /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
     known value for that SSA_NAME (or NULL if no value is known).  
  
!    NONZERO_VARS is the set SSA_NAMES known to have a nonzero value,
!    even if we don't know their precise value.
! 
!    Propagate values from CONST_AND_COPIES and NONZERO_VARS into the PHI
!    nodes of the successors of BB.  */
  
  void
! cprop_into_successor_phis (basic_block bb,
! 			   varray_type const_and_copies,
! 			   bitmap nonzero_vars)
  {
    edge e;
  
*************** cprop_into_successor_phis (basic_block b
*** 341,346 ****
--- 346,356 ----
  	  orig_p = &PHI_ARG_DEF (phi, hint);
  	  if (TREE_CODE (*orig_p) != SSA_NAME)
  	    continue;
+ 
+ 	  /* If the alternative is known to have a nonzero value, record
+ 	     that fact in the PHI node itself for future use.  */
+ 	  if (bitmap_bit_p (nonzero_vars, SSA_NAME_VERSION (*orig_p)))
+ 	    PHI_ARG_NONZERO (phi, i) = true;
  
  	  /* If we have *ORIG_P in our constant/copy table, then replace
  	     ORIG_P with its value in our constant/copy table.  */
Index: tree-ssa-dom.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-dom.c,v
retrieving revision 2.4
diff -c -p -r2.4 tree-ssa-dom.c
*** tree-ssa-dom.c	15 May 2004 06:21:34 -0000	2.4
--- tree-ssa-dom.c	17 May 2004 18:28:50 -0000
*************** Boston, MA 02111-1307, USA.  */
*** 40,46 ****
  #include "domwalk.h"
  #include "real.h"
  #include "tree-pass.h"
- #include "flags.h"
  #include "langhooks.h"
  
  /* This file implements optimizations on the dominator tree.  */
--- 40,45 ----
*************** dom_opt_finalize_block (struct dom_walk_
*** 1314,1320 ****
  
     Ignoring any alternatives which are the same as the result, if
     all the alternatives are equal, then the PHI node creates an
!    equivalence.  */
  static void
  record_equivalences_from_phis (struct dom_walk_data *walk_data, basic_block 
bb)
  {
--- 1313,1324 ----
  
     Ignoring any alternatives which are the same as the result, if
     all the alternatives are equal, then the PHI node creates an
!    equivalence.
! 
!    Additionally, if all the PHI alternatives are known to have a nonzero
!    value, then the result of this PHI is known to have a nonzero value,
!    even if we do not know its exact value.  */
! 
  static void
  record_equivalences_from_phis (struct dom_walk_data *walk_data, basic_block 
bb)
  {
*************** record_equivalences_from_phis (struct do
*** 1367,1372 ****
--- 1371,1387 ----
  	  && may_propagate_copy (lhs, rhs))
  	set_value_for (lhs, rhs, const_and_copies);
  
+       /* Now see if we know anything about the nonzero property for the
+ 	 result of this PHI.  */
+       for (i = 0; i < PHI_NUM_ARGS (phi); i++)
+ 	{
+ 	  if (!PHI_ARG_NONZERO (phi, i))
+ 	    break;
+ 	}
+ 
+       if (i == PHI_NUM_ARGS (phi))
+ 	bitmap_set_bit (nonzero_vars, SSA_NAME_VERSION (PHI_RESULT (phi)));
+ 
        register_new_def (lhs, &bd->block_defs);
      }
  }
*************** static void
*** 2257,2263 ****
  cprop_into_phis (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
  		 basic_block bb)
  {
!   cprop_into_successor_phis (bb, const_and_copies);
  }
  
  /* Search for redundant computations in STMT.  If any are found, then
--- 2272,2278 ----
  cprop_into_phis (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
  		 basic_block bb)
  {
!   cprop_into_successor_phis (bb, const_and_copies, nonzero_vars);
  }
  
  /* Search for redundant computations in STMT.  If any are found, then
*************** record_equivalences_from_stmt (tree stmt
*** 2422,2446 ****
    /* Look at both sides for pointer dereferences.  If we find one, then
       the pointer must be nonnull and we can enter that equivalence into
       the hash tables.  */
!   for (i = 0; i < 2; i++)
!     {
!       tree t = TREE_OPERAND (stmt, i);
! 
!       /* Strip away any COMPONENT_REFs.  */
!       while (TREE_CODE (t) == COMPONENT_REF)
!         t = TREE_OPERAND (t, 0);
! 
!       /* Now see if this is a pointer dereference.  */
!       if (TREE_CODE (t) == INDIRECT_REF)
!         {
! 	  tree op = TREE_OPERAND (t, 0);
! 
! 	  /* If the pointer is a SSA variable, then enter new
! 	     equivalences into the hash table.  */
! 	  if (TREE_CODE (op) == SSA_NAME)
! 	    record_var_is_nonzero (op, block_nonzero_vars_p);
! 	}
!     }
  
    /* A memory store, even an aliased store, creates a useful
       equivalence.  By exchanging the LHS and RHS, creating suitable
--- 2437,2475 ----
    /* Look at both sides for pointer dereferences.  If we find one, then
       the pointer must be nonnull and we can enter that equivalence into
       the hash tables.  */
!   if (flag_delete_null_pointer_checks)
!     for (i = 0; i < 2; i++)
!       {
! 	tree t = TREE_OPERAND (stmt, i);
! 
! 	/* Strip away any COMPONENT_REFs.  */
! 	while (TREE_CODE (t) == COMPONENT_REF)
! 	  t = TREE_OPERAND (t, 0);
! 
! 	/* Now see if this is a pointer dereference.  */
! 	if (TREE_CODE (t) == INDIRECT_REF)
!           {
! 	    tree op = TREE_OPERAND (t, 0);
! 
! 	    /* If the pointer is a SSA variable, then enter new
! 	       equivalences into the hash table.  */
! 	    while (TREE_CODE (op) == SSA_NAME)
! 	      {
! 		tree def = SSA_NAME_DEF_STMT (op);
! 
! 		record_var_is_nonzero (op, block_nonzero_vars_p);
! 
! 		/* And walk up the USE-DEF chains noting other SSA_NAMEs
! 		   which are known to have a nonzero value.  */
! 		if (def
! 		    && TREE_CODE (def) == MODIFY_EXPR
! 		    && TREE_CODE (TREE_OPERAND (def, 1)) == NOP_EXPR)
! 		  op = TREE_OPERAND (TREE_OPERAND (def, 1), 0);
! 		else
! 		  break;
! 	      }
! 	  }
!       }
  
    /* A memory store, even an aliased store, creates a useful
       equivalence.  By exchanging the LHS and RHS, creating suitable
Index: tree.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree.h,v
retrieving revision 1.492
diff -c -p -r1.492 tree.h
*** tree.h	13 May 2004 06:39:50 -0000	1.492
--- tree.h	17 May 2004 18:28:58 -0000
*************** struct tree_ssa_name GTY(())
*** 1203,1208 ****
--- 1203,1209 ----
  #define PHI_ARG_ELT(NODE, I)	PHI_NODE_ELT_CHECK (NODE, I)
  #define PHI_ARG_EDGE(NODE, I)	PHI_NODE_ELT_CHECK (NODE, I).e
  #define PHI_ARG_DEF(NODE, I)	PHI_NODE_ELT_CHECK (NODE, I).def
+ #define PHI_ARG_NONZERO(NODE, I) PHI_NODE_ELT_CHECK (NODE, I).nonzero
  
  struct edge_def;
  
*************** struct phi_arg_d GTY(())
*** 1210,1215 ****
--- 1211,1217 ----
  {
    tree def;
    struct edge_def * GTY((skip (""))) e;
+   bool nonzero;
  };
  
  struct tree_phi_node GTY(())