gcc/tree-vn.c

   1 /* Value Numbering routines for tree expressions.
   2    Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
   3    Contributed by Daniel Berlin <dan@dberlin.org>, Steven Bosscher
   4    <stevenb@suse.de> and Diego Novillo <dnovillo@redhat.com>
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify
   9 it under the terms of the GNU General Public License as published by
  10 the Free Software Foundation; either version 2, or (at your option)
  11 any later version.
  12
  13 GCC is distributed in the hope that it will be useful,
  14 but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 GNU General Public License for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING.  If not, write to
  20 the Free Software Foundation, 59 Temple Place - Suite 330,
  21 Boston, MA 02111-1307, USA.  */
  22
  23 #include "config.h"
  24 #include "system.h"
  25 #include "coretypes.h"
  26 #include "tm.h"
  27 #include "ggc.h"
  28 #include "tree.h"
  29 #include "tree-flow.h"
  30 #include "hashtab.h"
  31 #include "langhooks.h"
  32 #include "tree-pass.h"
  33 #include "tree-dump.h"
  34 #include "diagnostic.h"
  35
  36 /* The value table that maps expressions to values.  */
  37 static htab_t value_table;
  38
  39 /* Map expressions to values.  These are simple pairs of expressions
  40    and the values they represent.  To find the value represented by
  41    an expression, we use a hash table where the elements are {e,v}
  42    pairs, and the expression is the key.  */
  43 typedef struct val_expr_pair_d
  44 {
  45   tree v, e;
  46   hashval_t hashcode;
  47 } *val_expr_pair_t;
  48
  49 static void set_value_handle (tree e, tree v);
  50
  51
  52 /* Create and return a new value handle node of type TYPE.  */
  53
  54 static tree
  55 make_value_handle (tree type)
  56 {
  57   static unsigned int id = 0;
  58   tree vh;
  59
  60   vh = build0 (VALUE_HANDLE, type);
  61   VALUE_HANDLE_ID (vh) = id++;
  62   return vh;
  63 }
  64
  65
  66 /* Given an expression or statement P, compute a hash value number using the
  67    code of the expression and its real operands.  */
  68
  69 hashval_t
  70 vn_compute (tree expr, hashval_t val)
  71 {
  72   val = iterative_hash_expr (expr, val);
  73   return val;
  74 }
  75
  76
  77 /* Compare two expressions E1 and E2 and return true if they are
  78    equal.  */
  79
  80 bool
  81 expressions_equal_p (tree e1, tree e2)
  82 {
  83   tree te1, te2;
  84
  85   if (e1 == e2)
  86     return true;
  87
  88   te1 = TREE_TYPE (e1);
  89   te2 = TREE_TYPE (e2);
  90
  91   if (TREE_CODE (e1) == TREE_CODE (e2)
  92       && (te1 == te2 || lang_hooks.types_compatible_p (te1, te2))
  93       && operand_equal_p (e1, e2, 0))
  94     return true;
  95
  96   return false;
  97 }
  98
  99
 100 /* Hash a {v,e} pair that is pointed to by P.
 101    The hashcode is cached in the val_expr_pair, so we just return
 102    that.  */
 103
 104 static hashval_t
 105 val_expr_pair_hash (const void *p)
 106 {
 107   const val_expr_pair_t ve = (val_expr_pair_t) p;
 108   return ve->hashcode;
 109 }
 110
 111
 112 /* Given two val_expr_pair_t's, return true if they represent the same
 113    expression, false otherwise.
 114    P1 and P2 should point to the val_expr_pair_t's to be compared.  */
 115
 116 static int
 117 val_expr_pair_expr_eq (const void *p1, const void *p2)
 118 {
 119   const val_expr_pair_t ve1 = (val_expr_pair_t) p1;
 120   const val_expr_pair_t ve2 = (val_expr_pair_t) p2;
 121
 122   if (expressions_equal_p (ve1->e, ve2->e))
 123     return true;
 124
 125   return false;
 126 }
 127
 128
 129 /* Set the value handle for expression E to value V */
 130
 131 static void
 132 set_value_handle (tree e, tree v)
 133 {
 134   if (TREE_CODE (e) == SSA_NAME)
 135     SSA_NAME_VALUE (e) = v;
 136   else if (EXPR_P (e) || DECL_P (e))
 137     get_tree_ann (e)->common.value_handle = v;
 138   else if (TREE_CODE_CLASS (TREE_CODE (e)) == 'c')
 139     /* Do nothing.  Constants are their own value handles.  */
 140     ;
 141   else
 142     abort ();
 143 }
 144
 145
 146 /* Insert E into VALUE_TABLE with value V, and add expression E to the
 147    value set for value V.  */
 148
 149 void
 150 vn_add (tree e, tree v)
 151 {
 152   void **slot;
 153   val_expr_pair_t new_pair = xmalloc (sizeof (struct val_expr_pair_d));
 154   new_pair->e = e;
 155   new_pair->v = v;
 156   new_pair->hashcode = vn_compute (e, 0);
 157   slot = htab_find_slot_with_hash (value_table, new_pair, new_pair->hashcode,
 158                                    INSERT);
 159   if (*slot)
 160     free (*slot);
 161   *slot = (void *) new_pair;
 162   set_value_handle (e, v);
 163
 164   add_to_value (v, e);
 165 }
 166
 167
 168 /* Search in VALUE_TABLE for an existing instance of expression E, and
 169    return its value, or NULL if none has been set.  */
 170
 171 tree
 172 vn_lookup (tree e)
 173 {
 174   void **slot;
 175   struct val_expr_pair_d vep = {NULL, NULL, 0};
 176
 177   if (TREE_CODE_CLASS (TREE_CODE (e)) == 'c')
 178     return e;
 179   vep.e = e;
 180   vep.hashcode = vn_compute (e, 0);
 181   slot = htab_find_slot_with_hash (value_table, &vep, vep.hashcode, NO_INSERT);
 182   if (!slot)
 183     return NULL_TREE;
 184   else
 185     return ((val_expr_pair_t) *slot)->v;
 186 }
 187
 188
 189 /* Like vn_lookup, but creates a new value for expression E if E doesn't
 190    already have a value.  Return the existing/created value for E.  */
 191
 192 tree
 193 vn_lookup_or_add (tree e)
 194 {
 195   tree x = vn_lookup (e);
 196   if (x == NULL_TREE)
 197     {
 198       tree v = make_value_handle (TREE_TYPE (e));
 199
 200       if (dump_file && (dump_flags & TDF_DETAILS))
 201         {
 202           fprintf (dump_file, "Created value ");
 203           print_generic_expr (dump_file, v, dump_flags);
 204           fprintf (dump_file, " for ");
 205           print_generic_expr (dump_file, e, dump_flags);
 206           fprintf (dump_file, "\n");
 207         }
 208
 209       vn_add (e, v);
 210       x = v;
 211     }
 212
 213   set_value_handle (e, x);
 214
 215   return x;
 216 }
 217
 218
 219 /* Get the value handle of EXPR.  This is the only correct way to get
 220    the value handle for a "thing".  If EXPR does not have a value
 221    handle associated, it generates and returns a new one.  */
 222
 223 tree
 224 get_value_handle (tree expr)
 225 {
 226   if (TREE_CODE (expr) == SSA_NAME)
 227     return SSA_NAME_VALUE (expr);
 228   else if (TREE_CODE_CLASS (TREE_CODE (expr)) == 'c')
 229     return expr;
 230   else if (EXPR_P (expr) || DECL_P (expr))
 231     {
 232       tree_ann_t ann = tree_ann (expr);
 233       return ((ann) ? ann->common.value_handle : NULL_TREE);
 234     }
 235
 236   abort ();
 237 }
 238
 239
 240 /* Initialize data structures used in value numbering.  */
 241
 242 void
 243 vn_init (void)
 244 {
 245   value_table = htab_create (511, val_expr_pair_hash,
 246                              val_expr_pair_expr_eq, free);
 247 }
 248
 249
 250 /* Delete data used for value numbering.  */
 251
 252 void
 253 vn_delete (void)
 254 {
 255   htab_delete (value_table);
 256   value_table = NULL;
 257 }