PR 33870

[pf3gnuchains/gcc-fork.git] / gcc / tree-vn.c

diff --git a/gcc/tree-vn.c b/gcc/tree-vn.c
index 4863cb7..a23d7be 100644 (file)
--- a/gcc/tree-vn.c
+++ b/gcc/tree-vn.c
@@ -1,5 +1,5 @@
 /* Value Numbering routines for tree expressions.
 /* Value Numbering routines for tree expressions.

-   Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
+   Copyright (C) 2001, 2002, 2003, 2004, 2005, 2007 Free Software Foundation, Inc.

    Contributed by Daniel Berlin <dan@dberlin.org>, Steven Bosscher
    <stevenb@suse.de> and Diego Novillo <dnovillo@redhat.com>
 
    Contributed by Daniel Berlin <dan@dberlin.org>, Steven Bosscher
    <stevenb@suse.de> and Diego Novillo <dnovillo@redhat.com>
 


@@ -7,7 +7,7 @@ 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
 
 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)
+the Free Software Foundation; either version 3, or (at your option)

 any later version.
 
 GCC is distributed in the hope that it will be useful,
 any later version.
 
 GCC is distributed in the hope that it will be useful,


@@ -16,9 +16,8 @@ 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
 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, 51 Franklin Street, Fifth Floor,
-Boston, MA 02110-1301, USA.  */
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */

 
 #include "config.h"
 #include "system.h"
 
 #include "config.h"
 #include "system.h"


@@ -32,35 +31,15 @@ Boston, MA 02110-1301, USA.  */
 #include "tree-pass.h"
 #include "tree-dump.h"
 #include "diagnostic.h"
 #include "tree-pass.h"
 #include "tree-dump.h"
 #include "diagnostic.h"

+#include "tree-ssa-sccvn.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
-{
-  /* Value handle.  */
-  tree v;
-
-  /* Associated expression.  */
-  tree e;
-
-  /* for comparing Virtual uses in E.  */
-  tree stmt;
-
-  /* E's hash value.  */
-  hashval_t hashcode;
-} *val_expr_pair_t;
-
-static void set_value_handle (tree e, tree v);
-
+/* Most of this is PRE specific.  The real grunt work is done in
+   tree-ssa-sccvn.c.  This is where the lookup and insertion
+   functions, etc, can be found */

 
 /* Create and return a new value handle node of type TYPE.  */
 
 
 /* Create and return a new value handle node of type TYPE.  */
 

-static tree
+tree

 make_value_handle (tree type)
 {
   static unsigned int id = 0;
 make_value_handle (tree type)
 {
   static unsigned int id = 0;


@@ -72,38 +51,6 @@ make_value_handle (tree type)
 }
 
 
 }
 
 

-/* Given an expression EXPR, compute a hash value number using the
-   code of the expression, its real operands and virtual operands (if
-   any).
-   
-   VAL can be used to iterate by passing previous value numbers (it is
-   used by iterative_hash_expr).
-
-   STMT is the stmt associated with EXPR for comparing virtual operands.  */
-
-hashval_t
-vn_compute (tree expr, hashval_t val, tree stmt)
-{
-  ssa_op_iter iter;
-  tree vuse;
-
-  /* EXPR must not be a statement.  We are only interested in value
-     numbering expressions on the RHS of assignments.  */
-  gcc_assert (expr);
-  gcc_assert (!expr->common.ann
-             || expr->common.ann->common.type != STMT_ANN);
-
-  val = iterative_hash_expr (expr, val);
-
-  /* If the expression has virtual uses, incorporate them into the
-     hash value computed for EXPR.  */
-  if (stmt)
-    FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, iter, SSA_OP_VUSE)
-      val = iterative_hash_expr (vuse,  val);
-
-  return val;
-}
-

 
 /* Compare two expressions E1 and E2 and return true if they are
    equal.  */
 
 /* Compare two expressions E1 and E2 and return true if they are
    equal.  */


@@ -112,7 +59,7 @@ bool
 expressions_equal_p (tree e1, tree e2)
 {
   tree te1, te2;
 expressions_equal_p (tree e1, tree e2)
 {
   tree te1, te2;

-  
+

   if (e1 == e2)
     return true;
 
   if (e1 == e2)
     return true;
 


@@ -135,185 +82,324 @@ expressions_equal_p (tree e1, tree e2)
       return true;
 
     }
       return true;
 
     }

-  else if (TREE_CODE (e1) == TREE_CODE (e2) 
-          && (te1 == te2 || lang_hooks.types_compatible_p (te1, te2))
+  else if (TREE_CODE (e1) == TREE_CODE (e2)
+          && (te1 == te2
+              || types_compatible_p (te1, te2))

           && operand_equal_p (e1, e2, OEP_PURE_SAME))
     return true;
 
   return false;
 }
 
           && operand_equal_p (e1, e2, OEP_PURE_SAME))
     return true;
 
   return false;
 }
 

+/* Set the value handle for expression E to value V.  */

 
 

-/* 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)
+void
+set_value_handle (tree e, tree v)

 {
 {

-  const val_expr_pair_t ve = (val_expr_pair_t) p;
-  return ve->hashcode;
+  if (TREE_CODE (e) == SSA_NAME)
+    SSA_NAME_VALUE (e) = v;
+  else if (EXPR_P (e) || DECL_P (e) || TREE_CODE (e) == TREE_LIST
+          || GIMPLE_STMT_P (e)
+          || TREE_CODE (e) == CONSTRUCTOR)
+    get_tree_common_ann (e)->value_handle = v;
+  else
+    /* Do nothing.  Constants are their own value handles.  */
+    gcc_assert (is_gimple_min_invariant (e));

 }
 
 }
 

-
-/* 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.  */
+/* A comparison function for use in qsort to compare vuses.  Simply
+   subtracts version numbers.  */

 
 static int
 
 static int

-val_expr_pair_expr_eq (const void *p1, const void *p2)
+vuses_compare (const void *pa, const void *pb)

 {
 {

-  bool ret;
-  const val_expr_pair_t ve1 = (val_expr_pair_t) p1;
-  const val_expr_pair_t ve2 = (val_expr_pair_t) p2;
+  const tree vusea = *((const tree *)pa);
+  const tree vuseb = *((const tree *)pb);
+  int sn = SSA_NAME_VERSION (vusea) - SSA_NAME_VERSION (vuseb);

 
 

-  if (! expressions_equal_p (ve1->e, ve2->e))
-    return false;
-
-  ret = compare_ssa_operands_equal (ve1->stmt, ve2->stmt, SSA_OP_VUSE);
-  return ret;
+  return sn;

 }
 
 }
 

+/* Print out the "Created value <x> for <Y>" statement to the
+   dump_file.
+   This is factored because both versions of lookup use it, and it
+   obscures the real work going on in those functions.  */

 
 

-/* Set the value handle for expression E to value V.  */
-   

 static void
 static void

-set_value_handle (tree e, tree v)
+print_creation_to_file (tree v, tree expr, VEC (tree, gc) *vuses)

 {
 {

-  if (TREE_CODE (e) == SSA_NAME)
-    SSA_NAME_VALUE (e) = v;
-  else if (EXPR_P (e) || DECL_P (e) || TREE_CODE (e) == TREE_LIST
-          || TREE_CODE (e) == CONSTRUCTOR)
-    get_tree_ann (e)->common.value_handle = v;
-  else
-    /* Do nothing.  Constants are their own value handles.  */
-    gcc_assert (is_gimple_min_invariant (e));
+  fprintf (dump_file, "Created value ");
+  print_generic_expr (dump_file, v, dump_flags);
+  fprintf (dump_file, " for ");
+  print_generic_expr (dump_file, expr, dump_flags);
+
+  if (vuses && VEC_length (tree, vuses) != 0)
+    {
+      size_t i;
+      tree vuse;
+
+      fprintf (dump_file, " vuses: (");
+      for (i = 0; VEC_iterate (tree, vuses, i, vuse); i++)
+       {
+         print_generic_expr (dump_file, vuse, dump_flags);
+         if (VEC_length (tree, vuses) - 1 != i)
+           fprintf (dump_file, ",");
+       }
+      fprintf (dump_file, ")");
+    }
+  fprintf (dump_file, "\n");

 }
 
 
 }
 
 

+/* Sort the VUSE array so that we can do equality comparisons
+   quicker on two vuse vecs.  */
+
+void
+sort_vuses (VEC (tree,gc) *vuses)
+{
+  if (VEC_length (tree, vuses) > 1)
+    qsort (VEC_address (tree, vuses),
+          VEC_length (tree, vuses),
+          sizeof (tree),
+          vuses_compare);
+}
+
+/* Sort the VUSE array so that we can do equality comparisons
+   quicker on two vuse vecs.  */
+
+void
+sort_vuses_heap (VEC (tree,heap) *vuses)
+{
+  if (VEC_length (tree, vuses) > 1)
+    qsort (VEC_address (tree, vuses),
+          VEC_length (tree, vuses),
+          sizeof (tree),
+          vuses_compare);
+}

 /* Insert EXPR into VALUE_TABLE with value VAL, and add expression
 /* Insert EXPR into VALUE_TABLE with value VAL, and add expression

-   EXPR to the value set for value VAL.  STMT represents the stmt
-   associated with EXPR.  It is used when computing a hash value for EXPR.  */
+   EXPR to the value set for value VAL.  */
+
+void
+vn_add (tree expr, tree val)
+{
+  switch (TREE_CODE_CLASS (TREE_CODE (expr)))
+    {
+    case tcc_comparison:
+    case tcc_binary:
+      vn_binary_op_insert (expr, val);
+      break;
+    case tcc_unary:
+      vn_unary_op_insert (expr, val);
+      break;
+      /* In the case of array-refs of constants, for example, we can
+        end up with no vuses.  */
+    case tcc_reference:
+      vn_reference_insert (expr, val, NULL);
+      break;
+      /* The *only* time CALL_EXPR should appear here is
+        when it has no vuses.  */
+    case tcc_vl_exp:
+    case tcc_exceptional:
+    case tcc_expression:
+    case tcc_declaration:
+      if (TREE_CODE (expr) == CALL_EXPR || DECL_P (expr))
+       {
+         vn_reference_insert (expr, val, NULL);
+         break;
+       }
+      else if (TREE_CODE (expr) == SSA_NAME)
+       {
+         SSA_NAME_VALUE (expr) = val;
+         break;
+       }
+      else if (TREE_CODE (expr) == ADDR_EXPR)
+       {
+         vn_unary_op_insert (expr, val);
+         break;
+       }
+      /* FALLTHROUGH */
+    default:
+      gcc_unreachable ();
+    }
+  set_value_handle (expr, val);
+  if (TREE_CODE (val) == VALUE_HANDLE)
+    add_to_value (val, expr);
+}
+
+/* Insert EXPR into the value numbering tables.  with value VAL, and
+   add expression EXPR to the value set for value VAL.  VUSES
+   represents the virtual use operands associated with EXPR.  It is
+   used when computing a hash value for EXPR.  */

 
 void
 
 void

-vn_add (tree expr, tree val, tree stmt)
+vn_add_with_vuses (tree expr, tree val, VEC (tree, gc) *vuses)

 {
 {

-  void **slot;
-  val_expr_pair_t new_pair;
-  
-  new_pair = xmalloc (sizeof (struct val_expr_pair_d));
-  new_pair->e = expr;
-  new_pair->v = val;
-  new_pair->stmt = stmt;
-  new_pair->hashcode = vn_compute (expr, 0, stmt);
-  slot = htab_find_slot_with_hash (value_table, new_pair, new_pair->hashcode,
-                                  INSERT);
-  if (*slot)
-    free (*slot);
-  *slot = (void *) new_pair;
+  if (!vuses)
+    {
+      vn_add (expr, val);
+      return;
+    }
+  vn_reference_insert (expr, val, vuses);

 
   set_value_handle (expr, val);
 
   set_value_handle (expr, val);

-  add_to_value (val, expr);
+  if (TREE_CODE (val) == VALUE_HANDLE)
+    add_to_value (val, expr);

 }
 
 
 }
 
 

-/* Search in VALUE_TABLE for an existing instance of expression EXPR,
-   and return its value, or NULL if none has been set.  STMT
-   represents the stmt associated with EXPR.  It is used when computing the 
-   hash value for EXPR.  */
+/* Lookup EXPR in the value numbering tables and return the result, if
+   we have one.  */
+
+tree
+vn_lookup (tree expr)
+{
+  /* Constants are their own value.  */
+  if (is_gimple_min_invariant (expr) || TREE_CODE (expr) == FIELD_DECL)
+    return expr;
+
+  switch (TREE_CODE_CLASS (TREE_CODE (expr)))
+    {
+    case tcc_comparison:
+    case tcc_binary:
+      return vn_binary_op_lookup (expr);
+    case tcc_unary:
+      return vn_unary_op_lookup (expr);
+      break;
+      /* In the case of array-refs of constants, for example, we can
+        end up with no vuses.  */
+    case tcc_reference:
+      return vn_reference_lookup (expr, NULL);
+      break;
+      /* It is possible to have CALL_EXPR with no vuses for things
+        like "cos", and these will fall into vn_lookup.   */
+    case tcc_vl_exp:
+    case tcc_exceptional:
+    case tcc_expression:
+    case tcc_declaration:
+      if (TREE_CODE (expr) == CALL_EXPR || DECL_P (expr))
+       return vn_reference_lookup (expr, NULL);
+      else if (TREE_CODE (expr) == SSA_NAME)
+       return SSA_NAME_VALUE (expr);
+      else if (TREE_CODE (expr) == ADDR_EXPR)
+       return vn_unary_op_lookup (expr);
+      /* FALLTHROUGH */
+    default:
+      gcc_unreachable ();
+    }
+  return NULL;
+}
+
+/* Search in the value numbering tables for an existing instance of
+   expression EXPR,  and return its value, or NULL if none has been set.  STMT
+   represents the stmt associated with EXPR.  It is used when computing the
+   hash value for EXPR for reference operations.  */

 
 tree
 
 tree

-vn_lookup (tree expr, tree stmt)
+vn_lookup_with_stmt (tree expr, tree stmt)

 {
 {

-  void **slot;
-  struct val_expr_pair_d vep = {NULL, NULL, NULL, 0};
+  if (stmt == NULL)
+    return vn_lookup (expr);

 
   /* Constants are their own value.  */
 
   /* Constants are their own value.  */

-  if (is_gimple_min_invariant (expr))
+  if (is_gimple_min_invariant (expr) || TREE_CODE (expr) == FIELD_DECL)

     return expr;
 
     return expr;
 

-  vep.e = expr;
-  vep.stmt = stmt;
-  vep.hashcode = vn_compute (expr, 0, stmt); 
-  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;
+  return vn_lookup_with_vuses (expr, shared_vuses_from_stmt (stmt));

 }
 
 }
 

+/* Search in VALUE_TABLE for an existing instance of expression EXPR,
+   and return its value, or NULL if none has been set.  VUSES is the
+   list of virtual use operands associated with EXPR.  It is used when
+   computing the hash value for EXPR.  */

 
 

-/* Like vn_lookup, but creates a new value for expression EXPR, if
-   EXPR doesn't already have a value.  Return the existing/created
-   value for EXPR.  STMT represents the stmt associated with EXPR.  It is used
-   when computing the hash value for EXPR.  */
+tree
+vn_lookup_with_vuses (tree expr, VEC (tree, gc) *vuses)
+{
+  if (!vuses || !VEC_length (tree, vuses))
+    return vn_lookup (expr);
+
+  if (is_gimple_min_invariant (expr) || TREE_CODE (expr) == FIELD_DECL)
+    return expr;
+
+  return vn_reference_lookup (expr, vuses);
+}
+
+static tree
+create_value_handle_for_expr (tree expr, VEC(tree, gc) *vuses)
+{
+  tree v;
+
+  v = make_value_handle (TREE_TYPE (expr));
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    print_creation_to_file (v, expr, vuses);
+  return v;
+}
+
+/* Like vn_lookup, but creates a new value for the operation if one
+   does not exist.  */

 
 tree
 
 tree

-vn_lookup_or_add (tree expr, tree stmt)
+vn_lookup_or_add (tree expr)

 {
 {

-  tree v = vn_lookup (expr, stmt);
+  tree v = vn_lookup (expr);
+

   if (v == NULL_TREE)
     {
   if (v == NULL_TREE)
     {

-      v = make_value_handle (TREE_TYPE (expr));
-
-      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, expr, dump_flags);
-         fprintf (dump_file, "\n");
-       }
-
-      vn_add (expr, v, stmt);
+      v = create_value_handle_for_expr (expr, NULL);
+      vn_add (expr, v);

     }
     }

-
-  set_value_handle (expr, v);
+  else
+    set_value_handle (expr, v);

 
   return v;
 }
 
 
   return v;
 }
 

-
-/* 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 returns NULL_TREE.  
-   NB: If EXPR is min_invariant, this function is *required* to return EXPR.  */
+/* Like vn_lookup, but handles reference operations as well by using
+   STMT to get the set of vuses.  */

 
 tree
 
 tree

-get_value_handle (tree expr)
+vn_lookup_or_add_with_stmt (tree expr, tree stmt)

 {
 {

+  tree v;
+  if (!stmt)
+    return vn_lookup_or_add (expr);

 
 

-  if (is_gimple_min_invariant (expr))
-    return expr;
-
-  if (TREE_CODE (expr) == SSA_NAME)
-    return SSA_NAME_VALUE (expr);
-  else if (EXPR_P (expr) || DECL_P (expr) || TREE_CODE (expr) == TREE_LIST
-          || TREE_CODE (expr) == CONSTRUCTOR)
+  v = vn_lookup_with_stmt (expr, stmt);
+  if (v == NULL_TREE)

     {
     {

-      tree_ann_t ann = tree_ann (expr);
-      return ((ann) ? ann->common.value_handle : NULL_TREE);
+      VEC (tree, gc) *vuses = copy_vuses_from_stmt (stmt);
+      v = create_value_handle_for_expr (expr, vuses);
+      vn_add_with_vuses (expr, v, vuses);

     }
   else
     }
   else

-    gcc_unreachable ();
-}
+    set_value_handle (expr, v);

 
 

+  return v;
+}

 
 

-/* Initialize data structures used in value numbering.  */
+/* Like vn_lookup, but creates a new value for expression EXPR, if
+   EXPR doesn't already have a value.  Return the existing/created
+   value for EXPR.  STMT represents the stmt associated with EXPR.  It is used
+   when computing the hash value for EXPR.  */

 
 

-void
-vn_init (void)
+tree
+vn_lookup_or_add_with_vuses (tree expr, VEC (tree, gc) *vuses)

 {
 {

-  value_table = htab_create (511, val_expr_pair_hash,
-                            val_expr_pair_expr_eq, free);
-}
+  tree v;

 
 

+  if (!vuses || VEC_length (tree, vuses) == 0)
+    return vn_lookup_or_add (expr);

 
 

-/* Delete data used for value numbering.  */
+  v = vn_lookup_with_vuses (expr, vuses);
+  if (v == NULL_TREE)
+    {
+      v = create_value_handle_for_expr (expr, vuses);
+      vn_add_with_vuses (expr, v, vuses);
+    }
+  else
+    set_value_handle (expr, v);

 
 

-void
-vn_delete (void)
-{
-  htab_delete (value_table);
-  value_table = NULL;
+  return v;

 }
 }

+