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]

[tree-ssa] Share some INDIRECT_REF nodes [patch]


The dataflow routines treat INDIRECT_REF nodes of the form
INDIRECT_REF <VAR_DECL> as regular variables.  This causes some
grief when we want to add annotation to these variables, because
INDIRECT_REF nodes are not shared.

At first we had changed var_ann() for an INDIRECT_REF node to
access the annotation object for its base pointer.  This is a bit
slow because of the additional indirection that it needs to do.

Besides the extra indirection in var_ann(), the fact that
INDIRECT_REF nodes aren't shared also meant that optimizers can't
rely on pointer equality to test if two variables are the same.
More overhead.

The patch also changes get_base_symbol from a recursive into an
iterative function.

Bootstrapped and tested on x86.


Diego.

	* tree-dfa.c (find_vars_r): Share INDIRECT_REF nodes whose operand
	is a VAR_DECL.  
	(add_referenced_var): Add additional argument 'sym'.  Update all users.
	Don't call get_base_symbol.
	(add_indirect_ref_var): Rename argument 'var' to 'ptr'.
	(htab_hash_var): Remove.  Update all users to use htab_hash_pointer.
	(htab_var_eq): Remove.  Update all users to use htab_eq_pointer.

	* tree-flow-inline.h (var_ann): Don't retrieve the annotation of
	the base pointer for INDIRECT_REF variables.
	(is_aliased): Remove.  Update all users.
	(is_dereferenced): Remove.  Update all users.
	(same_var_p): Remove.  Update all users to use pointer equality.

	* tree-simple.c (get_base_symbol): Convert tail recursion into
	iteration.

	* tree-ssa.c (rewrite_out_of_ssa): Add FIXME note about overlapping
	live ranges for different versions of the same variable.

Index: tree-dfa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-dfa.c,v
retrieving revision 1.1.4.70
diff -d -u -p -r1.1.4.70 tree-dfa.c
--- tree-dfa.c	3 Feb 2003 23:56:24 -0000	1.1.4.70
+++ tree-dfa.c	4 Feb 2003 00:22:38 -0000
@@ -104,7 +104,7 @@ static void add_stmt_operand		PARAMS ((t
       						 voperands_t));
 static void add_immediate_use		PARAMS ((tree, tree));
 static tree find_vars_r			PARAMS ((tree *, int *, void *));
-static void add_referenced_var		PARAMS ((tree, void *));
+static void add_referenced_var		PARAMS ((tree, tree, void *));
 static void add_indirect_ref_var	PARAMS ((tree, void *));
 static void compute_immediate_uses_for	PARAMS ((tree, int));
 static void add_may_alias		PARAMS ((tree, tree));
@@ -514,7 +514,8 @@ add_stmt_operand (var_p, stmt, is_def, f
      voperands_t prev_vops;
 {
   bool is_scalar;
-  tree var;
+  tree var, deref;
+  varray_type aliases;
 
   var = *var_p;
   STRIP_NOPS (var);
@@ -530,7 +531,8 @@ add_stmt_operand (var_p, stmt, is_def, f
   if (var == NULL_TREE || !SSA_VAR_P (var))
     return;
 
-  if (!is_aliased (var))
+  aliases = may_aliases (var);
+  if (aliases == NULL)
     {
       /* The variable is not aliased.  If it's a scalar, process it as a
 	 real operand.  Otherwise, add it to the virtual operands.  Note
@@ -562,7 +564,6 @@ add_stmt_operand (var_p, stmt, is_def, f
     {
       /* The variable is aliased.  Add its aliases to the virtual operands.  */
       size_t i;
-      varray_type aliases = may_aliases (var);
 
       if (is_def)
 	{
@@ -579,12 +580,12 @@ add_stmt_operand (var_p, stmt, is_def, f
   /* A definition of a pointer variable 'p' clobbers its associated
      indirect variable '*p', because now 'p' is pointing to a different
      memory location.  */
+  deref = indirect_ref (var);
   if (is_def
       && SSA_DECL_P (var)
       && POINTER_TYPE_P (TREE_TYPE (var))
-      && is_dereferenced (var))
+      && deref != NULL_TREE)
     {
-      tree deref = indirect_ref (var);
       add_stmt_operand (&deref, stmt, true, true, prev_vops);
 
       /* If the relocation of 'p' is due to an expression that may
@@ -687,7 +688,7 @@ add_vdef (var, stmt, prev_vops)
       for (i = 0; i < VARRAY_ACTIVE_SIZE (prev_vops->vdef_ops); i++)
 	{
 	  tree d = VARRAY_TREE (prev_vops->vdef_ops, i);
-	  if (same_var_p (var, SSA_NAME_VAR (VDEF_RESULT (d))))
+	  if (var == SSA_NAME_VAR (VDEF_RESULT (d)))
 	    {
 	      vdef = d;
 	      break;
@@ -716,7 +717,7 @@ add_vdef (var, stmt, prev_vops)
 
   /* Don't allow duplicate entries.  */
   for (i = 0; i < VARRAY_ACTIVE_SIZE (ann->vops->vdef_ops); i++)
-    if (same_var_p (var, VDEF_RESULT (VARRAY_TREE (ann->vops->vdef_ops, i))))
+    if (var == VDEF_RESULT (VARRAY_TREE (ann->vops->vdef_ops, i)))
       return;
 
   VARRAY_PUSH_TREE (ann->vops->vdef_ops, vdef);
@@ -743,7 +744,7 @@ add_vuse (var, stmt, prev_vops)
       for (i = 0; i < VARRAY_ACTIVE_SIZE (prev_vops->vuse_ops); i++)
 	{
 	  tree u = VARRAY_TREE (prev_vops->vuse_ops, i);
-	  if (same_var_p (var, SSA_NAME_VAR (u)))
+	  if (var == SSA_NAME_VAR (u))
 	    {
 	      vuse = u;
 	      break;
@@ -774,7 +775,7 @@ add_vuse (var, stmt, prev_vops)
 
   /* Don't allow duplicate entries.  */
   for (i = 0; i < VARRAY_ACTIVE_SIZE (ann->vops->vuse_ops); i++)
-    if (same_var_p (var, VARRAY_TREE (ann->vops->vuse_ops, i)))
+    if (var == VARRAY_TREE (ann->vops->vuse_ops, i))
       return;
 
   VARRAY_PUSH_TREE (ann->vops->vuse_ops, var);
@@ -1079,6 +1080,8 @@ dump_variable (file, var)
      FILE *file;
      tree var;
 {
+  varray_type aliases;
+
   if (var == NULL_TREE)
     {
       fprintf (file, "<nil>");
@@ -1087,9 +1090,9 @@ dump_variable (file, var)
 
   print_generic_expr (file, var, 0);
   
-  if (is_aliased (var))
+  aliases = may_aliases (var);
+  if (aliases)
     {
-      varray_type aliases = may_aliases (var);
       size_t i, num_aliases = VARRAY_ACTIVE_SIZE (aliases);
       fprintf (file, ", may aliases: ");
       for (i = 0; i < num_aliases; i++)
@@ -1435,13 +1438,15 @@ compute_may_aliases ()
   VARRAY_WIDE_INT_INIT (addressable_vars_alias_set, 20, "addressable_vars_alias_set");
 
   /* Hash table of all the objects the SSA builder needs to be aware of.  */
-  vars_found = htab_create (50, htab_hash_var, htab_var_eq, NULL);
+  vars_found = htab_create (50, htab_hash_pointer, htab_eq_pointer, NULL);
 
   /* Hash table of all the unique INDIRECT_REFs found.  */
-  indirect_refs_found = htab_create (50, htab_hash_var, htab_var_eq, NULL);
+  indirect_refs_found = htab_create (50, htab_hash_pointer, htab_eq_pointer,
+				     NULL);
 
   /* Hash table of all the unique addressable variables found.  */
-  addressable_vars_found = htab_create (50, htab_hash_var, htab_var_eq, NULL);
+  addressable_vars_found = htab_create (50, htab_hash_pointer, htab_eq_pointer,
+					NULL);
 
   walk_state[0] = vars_found;
   walk_state[1] = indirect_refs_found;
@@ -1786,7 +1791,7 @@ add_may_alias (var, alias)
 
   /* Avoid adding duplicates.  */
   for (i = 0; i < VARRAY_ACTIVE_SIZE (ann->may_aliases); i++)
-    if (same_var_p (alias, VARRAY_TREE (ann->may_aliases, i)))
+    if (alias == VARRAY_TREE (ann->may_aliases, i))
       return;
 
   VARRAY_PUSH_TREE (ann->may_aliases, alias);
@@ -1987,10 +1992,31 @@ find_vars_r (tp, walk_subtrees, data)
 {
   if (SSA_VAR_P (*tp))
     {
-      add_referenced_var (*tp, data);
+      tree sym, var, deref;
+
+      var = *tp;
+      sym = get_base_symbol (var);
+
+      /* If VAR is an INDIRECT_REF node for a VAR_DECL pointer, rewrite *TP
+	 with the first INDIRECT_REF we found (if any).  We need to share
+	 INDIRECT_REF nodes because we treat them as regular variables and
+	 several passes rely on pointer equality for testing if two variables
+	 are the same.  */
+      if (TREE_CODE (var) == INDIRECT_REF && DECL_P (TREE_OPERAND (var, 0)))
+	{
+	  deref = indirect_ref (sym);
+	  if (deref)
+	    *tp = deref;
+	  else
+	    set_indirect_ref (sym, var);
+	}
+
+      add_referenced_var (var, sym, data);
+
       return NULL_TREE;
     }
 
+
   /* Function calls.  Consider them a reference for an artificial variable
      called GLOBAL_VAR.  This variable is a pointer that will alias every
      global variable and locals that have had their address taken.  The
@@ -2028,46 +2054,28 @@ find_vars_r (tp, walk_subtrees, data)
 }
 
 
-/* Add VAR to the list of dereferenced variables.  Also add it to the sets
-   ADDRESSABLE_VARS or INDIRECT_REFS needed for alias analysis.  DATA is an
-   array with three hash tables used to avoid adding the same variable more
-   than once to its corresponding set.  Note that this function assumes
-   that VAR is a valid SSA variable.  */
+/* Add VAR to the list of dereferenced variables.  SYM is the base symbol
+   when VAR is anything but a _DECL node.  Otherwise, SYM and VAR are the
+   same tree.
+   
+   Also add VAR to the sets ADDRESSABLE_VARS or INDIRECT_REFS needed for
+   alias analysis.  DATA is an array with three hash tables used to avoid
+   adding the same variable more than once to its corresponding set.  Note
+   that this function assumes that VAR is a valid SSA variable.  */
 
 static void
-add_referenced_var (var, data)
+add_referenced_var (var, sym, data)
      tree var;
+     tree sym;
      void *data;
 {
   void **slot;
-  tree sym;
-  tree ind;
   htab_t vars_found = ((htab_t *) data)[0];
   htab_t indirect_refs_found = ((htab_t *) data)[1];
   htab_t addressable_vars_found = ((htab_t *) data)[2];
 
-  /* Get the underlying symbol.  We will need it shortly.  */
-  if (TREE_CODE (var) == INDIRECT_REF)
-    {
-      sym = get_base_symbol (TREE_OPERAND (var, 0));
-      ind = var;
-
-      if (!is_dereferenced (sym))
-	set_indirect_ref (sym, ind);
-      else
-	ind = indirect_ref (sym);
-    }
-  else
-    {
-      sym = get_base_symbol (var);
-      ind = NULL_TREE;
-    }
-
-  /* Make VAR either the canonical INDIRECT_REF or the real symbol.  */
-  var = (ind ? ind : var);
-
   /* First handle an INDIRECT_REF.  */
-  if (ind)
+  if (TREE_CODE (var) == INDIRECT_REF)
     {
       slot = htab_find_slot (indirect_refs_found, (void *) var, INSERT);
       if (*slot == NULL)
@@ -2115,49 +2123,18 @@ add_referenced_var (var, data)
    pointer decl.  */
 
 static void
-add_indirect_ref_var (var, data)
-     tree var;
+add_indirect_ref_var (ptr, data)
+     tree ptr;
      void *data;
 {
-  tree deref = indirect_ref (var);
-
+  tree deref = indirect_ref (ptr);
   if (deref == NULL_TREE)
     {
-      deref = build1 (INDIRECT_REF, TREE_TYPE (TREE_TYPE (var)), var);
-      set_indirect_ref (var, deref);
+      deref = build1 (INDIRECT_REF, TREE_TYPE (TREE_TYPE (ptr)), ptr);
+      set_indirect_ref (ptr, deref);
     }
 
-  add_referenced_var (deref, data);
-}
-
-
-/* Return a hash value for a variable.  If the variable is an INDIRECT_REF
-   node, return the hash value for its pointer.  */
-
-hashval_t
-htab_hash_var (p)
-     const void *p;
-{
-  tree v = (tree) p;
-  if (TREE_CODE (v) == INDIRECT_REF)
-    v = TREE_OPERAND (v, 0);
-  return htab_hash_pointer (v);
-}
-
-
-/* Check if variables V1 and V2 are the same.
-   Two variables are the same if both V1 and V2 are pointers to the same
-   variable, or if they are both indirect refs to the same variable.  */
-
-int
-htab_var_eq (v1, v2)
-     const void *v1;
-     const void *v2;
-{
-  return (v1 == v2
-	  || (TREE_CODE ((tree) v1) == INDIRECT_REF
-	      && TREE_CODE ((tree) v2) == INDIRECT_REF
-	      && TREE_OPERAND ((tree) v1, 0) == TREE_OPERAND ((tree) v2, 0)));
+  add_referenced_var (deref, ptr, data);
 }
 
 
Index: tree-flow-inline.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow-inline.h,v
retrieving revision 1.1.2.22
diff -d -u -p -r1.1.2.22 tree-flow-inline.h
--- tree-flow-inline.h	3 Feb 2003 01:26:53 -0000	1.1.2.22
+++ tree-flow-inline.h	4 Feb 2003 00:22:38 -0000
@@ -33,19 +33,11 @@ var_ann (t)
   if (!SSA_VAR_P (t))
     abort ();
 #endif
-  /* SSA_NAME nodes share the same annotations as the VAR_DECL node that
-     they wrap.  */
+  /* SSA_NAME nodes share the same annotations as the VAR_DECL/INDIRECT_REF
+     node that they wrap.  */
   if (TREE_CODE (t) == SSA_NAME)
     t = SSA_NAME_VAR (t);
 
-  /* INDIRECT_REF nodes share the annotation from the canonical
-     dereference for their base pointer (see find_vars_r).  */
-  if (TREE_CODE (t) == INDIRECT_REF)
-    {
-      t = get_base_symbol (t);
-      t = ((var_ann_t) t->common.ann)->indirect_ref;
-    }
-
   return (t->common.ann && t->common.ann->common.type == VAR_ANN)
 	 ? (var_ann_t) t->common.ann
 	 : NULL;
@@ -84,13 +76,6 @@ may_aliases (var)
 }
 
 static inline bool
-is_aliased (var)
-     tree var;
-{
-  return may_aliases (var) != NULL;
-}
-
-static inline bool
 may_alias_global_mem_p (var)
      tree var;
 {
@@ -117,13 +102,6 @@ indirect_ref (var)
   return ann ? ann->indirect_ref : NULL_TREE;
 }
 
-static inline bool
-is_dereferenced (var)
-     tree var;
-{
-  return indirect_ref (var) != NULL_TREE;
-}
-
 static inline int
 get_lineno (expr)
      tree expr;
@@ -333,14 +311,6 @@ is_exec_stmt (t)
      tree t;
 {
   return (t && t != empty_stmt_node && t != error_mark_node);
-}
-
-static inline bool
-same_var_p (v1, v2)
-     tree v1;
-     tree v2;
-{
-  return htab_var_eq ((const void *)v1, (const void *)v2);
 }
 
 #endif /* _TREE_FLOW_INLINE_H  */
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow.h,v
retrieving revision 1.1.4.49
diff -d -u -p -r1.1.4.49 tree-flow.h
--- tree-flow.h	3 Feb 2003 23:56:25 -0000	1.1.4.49
+++ tree-flow.h	4 Feb 2003 00:22:38 -0000
@@ -172,9 +172,7 @@ static inline void unmodify_stmt		PARAMS
 static inline bool stmt_modified_p		PARAMS ((tree));
 static inline tree create_indirect_ref		PARAMS ((tree));
 static inline varray_type may_aliases		PARAMS ((tree));
-static inline bool is_aliased			PARAMS ((tree));
 static inline bool may_alias_global_mem_p 	PARAMS ((tree));
-static inline bool is_dereferenced	 	PARAMS ((tree));
 static inline void set_indirect_ref		PARAMS ((tree, tree));
 static inline tree indirect_ref			PARAMS ((tree));
 static inline int get_lineno			PARAMS ((tree));
@@ -339,9 +337,6 @@ extern void compute_reached_uses	PARAMS 
 extern void compute_immediate_uses	PARAMS ((int));
 extern void compute_reaching_defs	PARAMS ((int));
 extern tree copy_stmt			PARAMS ((tree));
-extern hashval_t htab_hash_var		PARAMS ((const void *));
-extern int htab_var_eq			PARAMS ((const void *, const void *));
-static inline bool same_var_p		PARAMS ((tree, tree));
 extern void dump_alias_info		PARAMS ((FILE *));
 extern void debug_alias_info		PARAMS ((void));
 extern tree get_virtual_var		PARAMS ((tree));
Index: tree-simple.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-simple.c,v
retrieving revision 1.1.4.27
diff -d -u -p -r1.1.4.27 tree-simple.c
--- tree-simple.c	3 Feb 2003 01:26:53 -0000	1.1.4.27
+++ tree-simple.c	4 Feb 2003 00:22:38 -0000
@@ -937,30 +937,34 @@ tree
 get_base_symbol (t)
      tree t;
 {
-  STRIP_NOPS (t);
-
-  switch (TREE_CODE (t))
+  do
     {
-    case VAR_DECL:
-    case FUNCTION_DECL:
-    case PARM_DECL:
-    case FIELD_DECL:
-    case LABEL_DECL:
-      return t;
+      STRIP_NOPS (t);
 
-    case SSA_NAME:
-      return get_base_symbol (SSA_NAME_VAR (t));
+      if (DECL_P (t))
+	return t;
 
-    case ARRAY_REF:
-    case COMPONENT_REF:
-    case INDIRECT_REF:
-    case REALPART_EXPR:
-    case IMAGPART_EXPR:
-      return get_base_symbol (TREE_OPERAND (t, 0));
+      switch (TREE_CODE (t))
+	{
+	case SSA_NAME:
+	  t = SSA_NAME_VAR (t);
+	  break;
 
-    default:
-      return NULL_TREE;
+	case ARRAY_REF:
+	case COMPONENT_REF:
+	case INDIRECT_REF:
+	case REALPART_EXPR:
+	case IMAGPART_EXPR:
+	  t = TREE_OPERAND (t, 0);
+	  break;
+
+	default:
+	  return NULL_TREE;
+	}
     }
+  while (t);
+
+  return t;
 }
 
 void
Index: tree-ssa-ccp.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-ccp.c,v
retrieving revision 1.1.2.43
diff -d -u -p -r1.1.2.43 tree-ssa-ccp.c
--- tree-ssa-ccp.c	3 Feb 2003 01:26:53 -0000	1.1.2.43
+++ tree-ssa-ccp.c	4 Feb 2003 00:22:38 -0000
@@ -1074,7 +1074,7 @@ static hashval_t
 value_map_hash (p)
      const void *p;
 {
-  return htab_hash_var ((const void *)((const struct value_map_d *)p)->var);
+  return htab_hash_pointer ((const void *)((const struct value_map_d *)p)->var);
 }
 
 static int
@@ -1082,6 +1082,6 @@ value_map_eq (p1, p2)
      const void *p1;
      const void *p2;
 {
-  return same_var_p (((const struct value_map_d *)p1)->var,
-		     ((const struct value_map_d *)p2)->var);
+  return ((const struct value_map_d *)p1)->var
+	 == ((const struct value_map_d *)p2)->var;
 }
Index: tree-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa.c,v
retrieving revision 1.1.4.46
diff -d -u -p -r1.1.4.46 tree-ssa.c
--- tree-ssa.c	3 Feb 2003 23:56:25 -0000	1.1.4.46
+++ tree-ssa.c	4 Feb 2003 00:22:38 -0000
@@ -495,7 +495,12 @@ rewrite_block (bb)
 }
 
 
-/* Take function FNDECL out of SSA form.  */
+/* Take function FNDECL out of SSA form.
+
+   FIXME: Need to support overlapping live ranges for different versions of
+	  the same variable.  At the moment, we will silently generate
+	  wrong code if an optimizer pass moves code so that two versions
+	  of the same variable have overlapping live ranges.  */
 
 void
 rewrite_out_of_ssa (fndecl)
@@ -993,7 +998,7 @@ static hashval_t
 def_blocks_hash (p)
      const void *p;
 {
-  return htab_hash_var ((const void *)((const struct def_blocks_d *)p)->var);
+  return htab_hash_pointer ((const void *)((const struct def_blocks_d *)p)->var);
 }
 
 static int
@@ -1001,8 +1006,8 @@ def_blocks_eq (p1, p2)
      const void *p1;
      const void *p2;
 {
-  return same_var_p (((const struct def_blocks_d *)p1)->var,
-                     ((const struct def_blocks_d *)p2)->var);
+  return ((const struct def_blocks_d *)p1)->var
+	 == ((const struct def_blocks_d *)p2)->var;
 }
 
 
@@ -1012,7 +1017,7 @@ static hashval_t
 currdef_hash (p)
      const void *p;
 {
-  return htab_hash_var ((const void *)((const struct currdef_d *)p)->var);
+  return htab_hash_pointer ((const void *)((const struct currdef_d *)p)->var);
 }
 
 static int
@@ -1020,8 +1025,8 @@ currdef_eq (p1, p2)
      const void *p1;
      const void *p2;
 {
-  return same_var_p (((const struct currdef_d *)p1)->var,
-                     ((const struct currdef_d *)p2)->var);
+  return ((const struct currdef_d *)p1)->var
+	 == ((const struct currdef_d *)p2)->var;
 }
 
 


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