[tree-ssa] More CCP improvements

[Andrew MacLeod <amacleod at redhat dot com>]

We're sometimes a little too hash-table happy. I've replace the use of a
hash table in for tracking variable values in CCP with a vector of
values.  Yeah, not all SSA_NAME versions are used, so there is a bit of
empty space in the vector, but it prevents a whole whack of calls to the
hash_table lookup (which was consuming about 40% of CCP's time), and
reduces libjava/interpret.cc compile time  from 10.2 secconds to 6.7
seconds. Cummultative bootstrap compile time went from 3.9 seconds in
CCP to 2.8 seconds.

Its also easier on the garbage collector, and in the end, I dont think
it really uses much more memory... We now have one vector allocation of
a 2 word structure. Before, we'd allocate a 3 word structure for each
referenced variable, plus any overhead required for each allocation. 

We were also adding stmts to the worklist when they were already marked
as DONT_SIMULATE_AGAIN. This resulted in an all around waste of time :-)

Furthermore, I've added a shortcircuit in the visit_phi_node routine
which looks at the current value of the PHI node, and doesn't bother
looking at the arguments if its already VARYING. This happens when the
default value of the PHI result is set to VARYING. We were ignoring this
before and eventually re-calculating the value based on the arguments. 

The end result is that compile time for CCP on interpret.cc has dropped
from 10.2 seconds to 5.8 or so.

Bootstrapped on x86, no new regressions, and no lost CCP opportunities
during a bootstrap.  

Andrew


	* tree-ssa-ccp.c (enum latticevalue): Add UNINITIALIZED.
	(const_values, struct value_map_d): Remove hash table structures.
	(value_vector): New array of values.
	(get_value): Use value_vector instead of hash table. Mark inline.
	(visit_phi_node): Ignore arguments if the PHI result is already VARYING.
	(initialize): Initialize value vector instead of hash table.
	(finalize): Free value vector instead of hash table.
	(add_var_to_ssa_edges_worklist): Don't add to worklist if 
	DONT_SIMULATE_AGAIN flag is set.
	(value_map_hash, value_map_eq): Delete.


Index: tree-ssa-ccp.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-ccp.c,v
retrieving revision 1.1.2.94
diff -c -p -r1.1.2.94 tree-ssa-ccp.c
*** tree-ssa-ccp.c	21 Sep 2003 22:14:27 -0000	1.1.2.94
--- tree-ssa-ccp.c	23 Sep 2003 14:13:17 -0000
*************** Software Foundation, 59 Temple Place - S
*** 57,62 ****
--- 57,63 ----
  /* Possible lattice values.  */
  typedef enum
  {
+   UNINITIALIZED = 0,
    UNDEFINED,
    CONSTANT,
    VARYING
*************** typedef struct
*** 74,93 ****
    tree const_val;
  } value;
  
- /* Hash table of constant values indexed by SSA name.   Each variable will
-    be assigned a value out of the constant lattice: UNDEFINED (top),
-    meaning that the variable has a constant of unknown value, CONSTANT,
-    meaning that the variable has a known constant value and VARYING
-    (bottom), meaning that the variable has a non-constant value.  */
- static htab_t const_values;
- 
- /* Structure to map a variable to its constant value.  */
- struct value_map_d
- {
-   tree var;
-   value val;
- };
- 
  /* A bitmap to keep track of executable blocks in the CFG.  */
  static sbitmap executable_blocks;
  
--- 75,80 ----
*************** static int cfg_blocks_head;
*** 100,105 ****
--- 87,97 ----
  
  static sbitmap bb_in_list;
  
+ /* This is used to track the current value of each variable.  */
+ static value *value_vector;
+ 
+ extern unsigned long next_ssa_version;
+ 
  /* Worklist of SSA edges which will need reexamination as their definition
     has changed.  SSA edges are def-use edges in the SSA web.  For each
     edge, we store the definition statement or PHI node D.  The destination
*************** static bool replace_uses_in (tree);
*** 129,138 ****
  static latticevalue likely_value (tree);
  static tree get_rhs (tree);
  static void set_rhs (tree *, tree);
! static value *get_value (tree);
  static value get_default_value (tree);
- static hashval_t value_map_hash (const void *);
- static int value_map_eq (const void *, const void *);
  static tree ccp_fold_builtin (tree, tree);
  static tree get_strlen (tree);
  static inline bool cfg_blocks_empty_p (void);
--- 121,128 ----
  static latticevalue likely_value (tree);
  static tree get_rhs (tree);
  static void set_rhs (tree *, tree);
! static inline value *get_value (tree);
  static value get_default_value (tree);
  static tree ccp_fold_builtin (tree, tree);
  static tree get_strlen (tree);
  static inline bool cfg_blocks_empty_p (void);
*************** tree_ssa_ccp (tree fndecl, sbitmap vars_
*** 219,224 ****
--- 209,233 ----
  }
  
  
+ /* Get the constant value associated with variable VAR.  */
+ 
+ static inline value *
+ get_value (tree var)
+ {
+   value *val;
+ #if defined ENABLE_CHECKING
+   if (TREE_CODE (var) != SSA_NAME)
+     abort ();
+ #endif
+ 
+   val = &(value_vector[SSA_NAME_VERSION (var)]);
+   if (val->lattice_val == UNINITIALIZED)
+     *val = get_default_value (var);
+     
+   return val;
+ }
+ 
+ 
  /* Simulate the execution of BLOCK.  Evaluate the statement associated
     with each variable reference inside the block.  */
  
*************** substitute_and_fold (sbitmap vars_to_ren
*** 395,401 ****
  static void
  visit_phi_node (tree phi)
  {
!   int i;
    value phi_val, *curr_val;
  
    /* If the PHI node has already been deemed to be VARYING, don't simulate
--- 404,410 ----
  static void
  visit_phi_node (tree phi)
  {
!   int i, short_circuit = 0;
    value phi_val, *curr_val;
  
    /* If the PHI node has already been deemed to be VARYING, don't simulate
*************** visit_phi_node (tree phi)
*** 410,429 ****
      }
  
    curr_val = get_value (PHI_RESULT (phi));
!   if (curr_val->lattice_val != CONSTANT)
      {
!       phi_val.lattice_val = UNDEFINED;
!       phi_val.const_val = NULL_TREE;
      }
    else
!     {
!       phi_val.lattice_val = curr_val->lattice_val;
!       phi_val.const_val = curr_val->const_val;
!     }
  
    /* If the variable is volatile or the variable is never referenced in a
       real operand, then consider the PHI node VARYING.  */
!   if (TREE_THIS_VOLATILE (SSA_NAME_VAR (PHI_RESULT (phi))))
      phi_val.lattice_val = VARYING;
    else
      for (i = 0; i < PHI_NUM_ARGS (phi); i++)
--- 419,445 ----
      }
  
    curr_val = get_value (PHI_RESULT (phi));
!   if (curr_val->lattice_val == VARYING)
      {
!       if (dump_file && (dump_flags & TDF_DETAILS))
! 	fprintf (dump_file, "\n   Shortcircuit. Default of VARYING.");
!       short_circuit = 1;
      }
    else
!     if (curr_val->lattice_val != CONSTANT)
!       {
! 	phi_val.lattice_val = UNDEFINED;
! 	phi_val.const_val = NULL_TREE;
!       }
!     else
!       {
! 	phi_val.lattice_val = curr_val->lattice_val;
! 	phi_val.const_val = curr_val->const_val;
!       }
  
    /* If the variable is volatile or the variable is never referenced in a
       real operand, then consider the PHI node VARYING.  */
!   if (short_circuit || TREE_THIS_VOLATILE (SSA_NAME_VAR (PHI_RESULT (phi))))
      phi_val.lattice_val = VARYING;
    else
      for (i = 0; i < PHI_NUM_ARGS (phi); i++)
*************** initialize (void)
*** 1029,1037 ****
    edge e;
    basic_block bb;
  
-   /* Initialize the values array with everything as undefined.  */
-   const_values = htab_create (50, value_map_hash, value_map_eq, NULL);
- 
    /* Compute immediate uses.  */
    compute_immediate_uses (TDFA_USE_OPS);
  
--- 1045,1050 ----
*************** initialize (void)
*** 1047,1052 ****
--- 1060,1068 ----
    bb_in_list = sbitmap_alloc (last_basic_block);
    sbitmap_zero (bb_in_list);
  
+   value_vector = (value *) xmalloc (next_ssa_version * sizeof (value));
+   memset (value_vector, 0, next_ssa_version * sizeof (value));
+ 
    /* Initialize simulation flags for PHI nodes, statements and edges.  */
    FOR_EACH_BB (bb)
      {
*************** initialize (void)
*** 1084,1092 ****
  static void
  finalize (void)
  {
    sbitmap_free (bb_in_list);
    sbitmap_free (executable_blocks);
-   htab_delete (const_values);
  }
  
  /* Is the block worklist empty.  */
--- 1100,1108 ----
  static void
  finalize (void)
  {
+   free (value_vector);
    sbitmap_free (bb_in_list);
    sbitmap_free (executable_blocks);
  }
  
  /* Is the block worklist empty.  */
*************** add_var_to_ssa_edges_worklist (tree var)
*** 1166,1172 ****
      {
        tree use = immediate_use (df, i);
  
!       if (stmt_ann (use)->in_ccp_worklist == 0)
  	{
  	  stmt_ann (use)->in_ccp_worklist = 1;
  	  VARRAY_PUSH_TREE (ssa_edges, use);
--- 1182,1188 ----
      {
        tree use = immediate_use (df, i);
  
!       if (!DONT_SIMULATE_AGAIN (use) && stmt_ann (use)->in_ccp_worklist == 0)
  	{
  	  stmt_ann (use)->in_ccp_worklist = 1;
  	  VARRAY_PUSH_TREE (ssa_edges, use);
*************** set_rhs (tree *stmt_p, tree expr)
*** 1514,1551 ****
  }
  
  
- /* Get the constant value associated with variable VAR.  */
- 
- static value *
- get_value (tree var)
- {
-   void **slot;
-   struct value_map_d *vm_p, vm;
- 
- #if defined ENABLE_CHECKING
-   if (TREE_CODE (var) != SSA_NAME)
-     abort ();
- #endif
- 
-   vm.var = var;
-   slot = htab_find_slot (const_values, (void *) &vm, INSERT);
-   if (*slot == NULL)
-     {
-       /* If this is the first time that we need the value for VAR and we
- 	 still have not seen a definition for it, assume a default value
- 	 accordingly (see get_default_value).  */
-       vm_p = xmalloc (sizeof (*vm_p));
-       vm_p->var = var;
-       vm_p->val = get_default_value (var);
-       *slot = (void *) vm_p;
-     }
-   else
-     vm_p = (struct value_map_d *) *slot;
- 
-   return &(vm_p->val);
- }
- 
- 
  /* Return a default value for variable VAR using the following rules:
  
     1- Global and static variables are considered VARYING, unless they are
--- 1530,1535 ----
*************** get_default_value (tree var)
*** 1590,1611 ****
      }
  
    return val;
- }
- 
- 
- /* Hash and compare functions for CONST_VALUES.  */
- 
- static hashval_t
- value_map_hash (const void *p)
- {
-   return htab_hash_pointer ((const void *)((const struct value_map_d *)p)->var);
- }
- 
- static int
- value_map_eq (const void *p1, const void *p2)
- {
-   return ((const struct value_map_d *)p1)->var
- 	 == ((const struct value_map_d *)p2)->var;
  }
  
  
--- 1574,1579 ----