* Makefile.in (tree-vn.o): New.

	(tree-ssa-pre.o): Don't depend on RTL_H.
	* tree-dfa.c (find_referenced_vars): Don't call init_tree_ssa.
	* tree-flow.h (struct var_ann_d): Remove field expr_set.
	(add_to_value, expressions_equal_p, get_value_handle, vn_compute,
	vn_lookup_or_add, vn_add, vn_lookup, vn_init, vn_delete): Declare.
	* tree-optimize.c (execute_init_datastructures): New local function.
	(pass_init_datastructures): New local variable.
	(init_tree_optimization_passes): Sequence pass_init_datastructures.
	* tree-pretty-print.c (MASK_POINTER): Remove.
	(dump_generic_node): Handle VALUE_HANDLE.
	* tree-ssa-pre.c: Move all value numbering routines to tree-vn.c.
	Update callers to use new function names.
	Use VALUE_HANDLE_ID and VALUE_HANDLE_EXPR_SET instead of
	variable annotations.
	* tree-ssa.c (init_tree_ssa): Call vn_init.
	(delete_tree_ssa): Call vn_delete.
	* tree-vn.c: New file.
	* tree.c (tree_size): Handle VALUE_HANDLE.
	(tree_node_structure): Likewise.
	(iterative_hash_expr): Likewise.
	* tree.def (VALUE_HANDLE): New code.
	* tree.h (struct tree_value_handle): New.
	(VALUE_HANDLE_ID): Define.
	(VALUE_HANDLE_EXPR_SET): Define.
	(enum tree_node_structure_enum): Add TS_VALUE_HANDLE.
	(union tree_node): Add struct tree_value_handle.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@83564 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 257 insertions, 0 deletions

diff --git a/gcc/tree-vn.c b/gcc/tree-vn.c
new file mode 100644
index 00000000000..de4c361feb8
--- /dev/null
+++ b/gcc/tree-vn.c
@@ -0,0 +1,257 @@
+/* Value Numbering routines for tree expressions.
+   Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
+   Contributed by Daniel Berlin <dan@dberlin.org>, Steven Bosscher
+   <stevenb@suse.de> and Diego Novillo <dnovillo@redhat.com>
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 2, or (at your option)
+any later version.
+
+GCC is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING.  If not, write to
+the Free Software Foundation, 59 Temple Place - Suite 330,
+Boston, MA 02111-1307, USA.  */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "ggc.h"
+#include "tree.h"
+#include "tree-flow.h"
+#include "hashtab.h"
+#include "langhooks.h"
+#include "tree-pass.h"
+#include "tree-dump.h"
+#include "diagnostic.h"
+
+/* The value table that maps expressions to values.  */
+static htab_t value_table;
+
+/* Map expressions to values.  These are simple pairs of expressions
+   and the values they represent.  To find the value represented by
+   an expression, we use a hash table where the elements are {e,v}
+   pairs, and the expression is the key.  */
+typedef struct val_expr_pair_d
+{
+  tree v, e;
+  hashval_t hashcode;
+} *val_expr_pair_t;
+
+static void set_value_handle (tree e, tree v);
+
+
+/* Create and return a new value handle node of type TYPE.  */
+
+static tree
+make_value_handle (tree type)
+{
+  static unsigned int id = 0;
+  tree vh;
+
+  vh = build0 (VALUE_HANDLE, type);
+  VALUE_HANDLE_ID (vh) = id++;
+  return vh;
+}
+
+
+/* Given an expression or statement P, compute a hash value number using the
+   code of the expression and its real operands.  */
+
+hashval_t
+vn_compute (tree expr, hashval_t val)
+{
+  val = iterative_hash_expr (expr, val);
+  return val;
+}
+
+
+/* Compare two expressions E1 and E2 and return true if they are
+   equal.  */
+
+bool
+expressions_equal_p (tree e1, tree e2)
+{
+  tree te1, te2;
+  
+  if (e1 == e2)
+    return true;
+
+  te1 = TREE_TYPE (e1);
+  te2 = TREE_TYPE (e2);
+
+  if (TREE_CODE (e1) == TREE_CODE (e2) 
+      && (te1 == te2 || lang_hooks.types_compatible_p (te1, te2))
+      && operand_equal_p (e1, e2, 0))
+    return true;
+
+  return false;
+}
+
+
+/* Hash a {v,e} pair that is pointed to by P.
+   The hashcode is cached in the val_expr_pair, so we just return
+   that.  */
+
+static hashval_t
+val_expr_pair_hash (const void *p)
+{
+  const val_expr_pair_t ve = (val_expr_pair_t) p;
+  return ve->hashcode;
+}
+
+
+/* Given two val_expr_pair_t's, return true if they represent the same
+   expression, false otherwise.
+   P1 and P2 should point to the val_expr_pair_t's to be compared.  */
+
+static int
+val_expr_pair_expr_eq (const void *p1, const void *p2)
+{
+  const val_expr_pair_t ve1 = (val_expr_pair_t) p1;
+  const val_expr_pair_t ve2 = (val_expr_pair_t) p2;
+
+  if (expressions_equal_p (ve1->e, ve2->e))
+    return true;
+  
+  return false;
+}
+
+
+/* Set the value handle for expression E to value V */
+   
+static void
+set_value_handle (tree e, tree v)
+{
+  if (TREE_CODE (e) == SSA_NAME)
+    SSA_NAME_VALUE (e) = v;
+  else if (EXPR_P (e) || DECL_P (e))
+    get_tree_ann (e)->common.value_handle = v;
+  else if (TREE_CODE_CLASS (TREE_CODE (e)) == 'c')
+    /* Do nothing.  Constants are their own value handles.  */
+    ;
+  else
+    abort ();
+}
+
+
+/* Insert E into VALUE_TABLE with value V, and add expression E to the
+   value set for value V.  */
+
+void
+vn_add (tree e, tree v)
+{
+  void **slot;
+  val_expr_pair_t new_pair = xmalloc (sizeof (struct val_expr_pair_d));
+  new_pair->e = e;
+  new_pair->v = v;
+  new_pair->hashcode = vn_compute (e, 0);
+  slot = htab_find_slot_with_hash (value_table, new_pair, new_pair->hashcode,
+				   INSERT);
+  if (*slot)
+    free (*slot);
+  *slot = (void *) new_pair;
+  set_value_handle (e, v);
+
+  add_to_value (v, e);
+}
+
+
+/* Search in VALUE_TABLE for an existing instance of expression E, and
+   return its value, or NULL if none has been set.  */
+
+tree
+vn_lookup (tree e)
+{
+  void **slot;
+  struct val_expr_pair_d vep = {NULL, NULL, 0};
+
+  if (TREE_CODE_CLASS (TREE_CODE (e)) == 'c')
+    return e;
+  vep.e = e;
+  vep.hashcode = vn_compute (e, 0); 
+  slot = htab_find_slot_with_hash (value_table, &vep, vep.hashcode, NO_INSERT);
+  if (!slot)
+    return NULL_TREE;
+  else
+    return ((val_expr_pair_t) *slot)->v;
+}
+
+
+/* Like vn_lookup, but creates a new value for expression E if E doesn't
+   already have a value.  Return the existing/created value for E.  */
+
+tree
+vn_lookup_or_add (tree e)
+{
+  tree x = vn_lookup (e);
+  if (x == NULL_TREE)
+    {
+      tree v = make_value_handle (TREE_TYPE (e));
+
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	{     
+	  fprintf (dump_file, "Created value ");
+	  print_generic_expr (dump_file, v, dump_flags);
+	  fprintf (dump_file, " for ");
+	  print_generic_expr (dump_file, e, dump_flags);
+	  fprintf (dump_file, "\n");
+	}
+
+      vn_add (e, v);
+      x = v;
+    }
+
+  set_value_handle (e, x);
+
+  return x;
+}
+
+
+/* Get the value handle of EXPR.  This is the only correct way to get
+   the value handle for a "thing".  If EXPR does not have a value
+   handle associated, it generates and returns a new one.  */
+
+tree
+get_value_handle (tree expr)
+{
+  if (TREE_CODE (expr) == SSA_NAME)
+    return SSA_NAME_VALUE (expr);
+  else if (TREE_CODE_CLASS (TREE_CODE (expr)) == 'c')
+    return expr;
+  else if (EXPR_P (expr) || DECL_P (expr))
+    {
+      tree_ann_t ann = tree_ann (expr);
+      return ((ann) ? ann->common.value_handle : NULL_TREE);
+    }
+
+  abort ();
+}
+
+
+/* Initialize data structures used in value numbering.  */
+
+void
+vn_init (void)
+{
+  value_table = htab_create (511, val_expr_pair_hash,
+			     val_expr_pair_expr_eq, free);
+}
+
+
+/* Delete data used for value numbering.  */
+
+void
+vn_delete (void)
+{
+  htab_delete (value_table);
+  value_table = NULL;
+}