IPA merge 6: variable annotations

[Jan Hubicka <jh at suse dot cz>]

Hi,
the variable annotations cause problems on IPA branch since they are shared
for static variables across all functions, while the infromation stored in them
is local for each pass.

This patch solves this by putting variable annotations into per function
hashtables, for performance reasons this is done for static variables
only, local variables still use direct pointers.  This is mostly outcome
of dicussion with Rth on the summit.  I didn't measured any off noise
slowdowns caused by this on my common testcases (static varibales are
not too common compared to temporaries and the extra conditional inline
don't seem to kill us) but I am not 100% satisfied by the solution.

The infromation used to store in variable annotations is from major part
not only local to function, but also don't need to have very long
lifespan.  (majority is used within single pass only, very little needs
to survive across the IPA passes)

On the IPA branch I instead use simple hack in delete_tree_ssa that reset
annotations on static variables after each compilation.  This sort of
works, just breaks aliasing.

I believe we should discuss some longer term plan how to move all this
data from the annotations to structures allocated locally when needed.
We can use an hashtables, but this might prove to be slow and bit
impractical.

How would sound putting dense UIDs to each referenced var into the
annotations implemented by direct pointers/hashtable as I am doing now
and using on-side arrays/bitmaps in the passes? (pretty much as we do
for REGNOs on RTL land).

I remember disucssing the variable UIDs with Kenny and others on GCC
summit and we was considering some strategies for static numbering (ie
giving global UIDs in a way so each function has just limited range),
but I think we found out this is not going to work in all cases when we
want to invent new local and global variables on the go.  So it seem to
me the hashtable assinging static's the local UIDs is probably best
solution here for local passes, we still can use DECL_UID for purposes
of IPA datastructures.

I would be happy to voluntee to start on such or similar conversion
incrementally if we can decide the overall plan...

Bootstrapped/regtested i686-linux, OK?
Honza

	* tree-flow-inline.h (gimple_var_anns): New function.
	(var_ann): Use hashtable for static functions.
	* tree-dfa.c (create_var_ann): Likewise.
	* tree-ssa.c (var_ann_eq, var_ann_hash): New functions.
	(init_tree_ssa): Initialize var anns.
	(delete_tree_ssa): Delete var anns; also clear out gimple_df.
	* tree-flow.h (struct static_var_ann_d): New structure.
	(gimple_df): Add var_anns.
Index: tree-flow-inline.h
===================================================================
*** tree-flow-inline.h	(revision 119454)
--- tree-flow-inline.h	(working copy)
*************** gimple_nonlocal_all (struct function *fu
*** 91,96 ****
--- 91,105 ----
    gcc_assert (fun && fun->gimple_df);
    return fun->gimple_df->nonlocal_all;
  }
+ 
+ /* Hashtable of variables annotations.  Used for static variables only;
+    local variables have direct pointer in the tree node.  */
+ static inline htab_t
+ gimple_var_anns (struct function *fun)
+ {
+   return fun->gimple_df->var_anns;
+ }
+ 
  /* Initialize the hashtable iterator HTI to point to hashtable TABLE */
  
  static inline void *
*************** var_ann (tree t)
*** 194,201 ****
    gcc_assert (t);
    gcc_assert (DECL_P (t));
    gcc_assert (TREE_CODE (t) != FUNCTION_DECL);
-   gcc_assert (!t->common.ann || t->common.ann->common.type == VAR_ANN);
  
    return (var_ann_t) t->common.ann;
  }
  
--- 203,221 ----
    gcc_assert (t);
    gcc_assert (DECL_P (t));
    gcc_assert (TREE_CODE (t) != FUNCTION_DECL);
  
+   if (TREE_STATIC (t))
+     {
+       struct static_var_ann_d *sann
+         = ((struct static_var_ann_d *)
+ 	   htab_find_with_hash (gimple_var_anns (cfun), t, DECL_UID (t)));
+       if (!sann)
+ 	return NULL;
+       gcc_assert (sann->ann.common.type = VAR_ANN);
+       return &sann->ann;
+     }
+ 
+   gcc_assert (!t->common.ann || t->common.ann->common.type == VAR_ANN);
    return (var_ann_t) t->common.ann;
  }
  
Index: tree-dfa.c
===================================================================
*** tree-dfa.c	(revision 119454)
--- tree-dfa.c	(working copy)
*************** var_ann_t
*** 125,141 ****
  create_var_ann (tree t)
  {
    var_ann_t ann;
  
    gcc_assert (t);
    gcc_assert (DECL_P (t));
    gcc_assert (!t->common.ann || t->common.ann->common.type == VAR_ANN);
  
!   ann = GGC_CNEW (struct var_ann_d);
  
    ann->common.type = VAR_ANN;
  
!   t->common.ann = (tree_ann_t) ann;
! 
    return ann;
  }
  
--- 125,157 ----
  create_var_ann (tree t)
  {
    var_ann_t ann;
+   struct static_var_ann_d *sann = NULL;
  
    gcc_assert (t);
    gcc_assert (DECL_P (t));
    gcc_assert (!t->common.ann || t->common.ann->common.type == VAR_ANN);
  
!   if (TREE_STATIC (t))
!     {
!       sann = GGC_CNEW (struct static_var_ann_d);
!       ann = &sann->ann;
!     }
!   else
!     ann = GGC_CNEW (struct var_ann_d);
  
    ann->common.type = VAR_ANN;
  
!   if (TREE_STATIC (t))
!     {
!        void **slot;
!        sann->uid = DECL_UID (t);
!        slot = htab_find_slot_with_hash (gimple_var_anns (cfun),
! 				        t, DECL_UID (t), INSERT);
!        gcc_assert (!*slot);
!        *slot = sann;
!     }
!   else
!     t->common.ann = (tree_ann_t) ann; 
    return ann;
  }
  
Index: tree-ssa.c
===================================================================
*** tree-ssa.c	(revision 119454)
--- tree-ssa.c	(working copy)
*************** int_tree_map_hash (const void *item)
*** 824,829 ****
--- 824,847 ----
    return ((const struct int_tree_map *)item)->uid;
  }
  
+ /* Return true if the uid in both int tree maps are equal.  */
+ 
+ static int
+ var_ann_eq (const void *va, const void *vb)
+ {
+   const struct static_var_ann_d *a = (const struct static_var_ann_d *) va;
+   tree b = (tree) vb;
+   return (a->uid == DECL_UID (b));
+ }
+ 
+ /* Hash a UID in a int_tree_map.  */
+ 
+ static unsigned int
+ var_ann_hash (const void *item)
+ {
+   return ((const struct static_var_ann_d *)item)->uid;
+ }
+ 
  
  /* Initialize global DFA and SSA structures.  */
  
*************** init_tree_ssa (void)
*** 835,840 ****
--- 853,860 ----
  				     		      int_tree_map_eq, NULL);
    cfun->gimple_df->default_defs = htab_create_ggc (20, int_tree_map_hash, 
  				                   int_tree_map_eq, NULL);
+   cfun->gimple_df->var_anns = htab_create_ggc (20, var_ann_hash, 
+ 					       var_ann_eq, NULL);
    cfun->gimple_df->call_clobbered_vars = BITMAP_GGC_ALLOC ();
    cfun->gimple_df->addressable_vars = BITMAP_GGC_ALLOC ();
    init_alias_heapvars ();
*************** delete_tree_ssa (void)
*** 884,890 ****
    /* Remove annotations from every referenced variable.  */
    FOR_EACH_REFERENCED_VAR (var, rvi)
      {
!       ggc_free (var->common.ann);
        var->common.ann = NULL;
      }
    htab_delete (gimple_referenced_vars (cfun));
--- 904,911 ----
    /* Remove annotations from every referenced variable.  */
    FOR_EACH_REFERENCED_VAR (var, rvi)
      {
!       if (var->common.ann)
!         ggc_free (var->common.ann);
        var->common.ann = NULL;
      }
    htab_delete (gimple_referenced_vars (cfun));
*************** delete_tree_ssa (void)
*** 896,907 ****
--- 917,932 ----
    cfun->gimple_df->global_var = NULL_TREE;
    
    htab_delete (cfun->gimple_df->default_defs);
+   cfun->gimple_df->default_defs = NULL;
+   htab_delete (cfun->gimple_df->var_anns);
+   cfun->gimple_df->var_anns = NULL;
    cfun->gimple_df->call_clobbered_vars = NULL;
    cfun->gimple_df->addressable_vars = NULL;
    cfun->gimple_df->modified_noreturn_calls = NULL;
    cfun->gimple_df->aliases_computed_p = false;
    delete_alias_heapvars ();
    gcc_assert (!need_ssa_update_p ());
+   cfun->gimple_df = NULL;
  }
  
  
Index: tree-flow.h
===================================================================
*** tree-flow.h	(revision 119454)
--- tree-flow.h	(working copy)
*************** typedef struct edge_def *edge;
*** 38,43 ****
--- 38,44 ----
  struct basic_block_def;
  typedef struct basic_block_def *basic_block;
  #endif
+ struct static_var_ann_d;
  
  /* Gimple dataflow datastructure. All publicly available fields shall have
     gimple_ accessor defined in tree-flow-inline.h, all publicly modifiable
*************** struct gimple_df GTY(()) {
*** 90,95 ****
--- 91,100 ----
    unsigned int in_ssa_p : 1;
  
    struct ssa_operands ssa_operands;
+ 
+   /* Hashtable of variables annotations.  Used for static variables only;
+      local variables have direct pointer in the tree node.  */
+   htab_t GTY((param_is (struct static_var_ann_d))) var_anns;
  };
  
  /* Accessors for internal use only.  Generic code should use abstraction
*************** struct var_ann_d GTY(())
*** 273,278 ****
--- 278,291 ----
    unsigned int escape_mask;
  };
  
+ /* Contianer for variable annotation used by hashtable for annotations for
+    static variables.  */
+ struct static_var_ann_d GTY(())
+ {
+   struct var_ann_d ann;
+   unsigned int uid;
+ };
+ 
  struct function_ann_d GTY(())
  {
    struct tree_ann_common_d common;