gcc/tree-vn.c

   1 /* Value Numbering routines for tree expressions.
   2    Copyright (C) 2001, 2002, 2003, 2004, 2005 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   /* Value handle.  */
  46   tree v;
  47
  48   /* Associated expression.  */
  49   tree e;
  50
  51   /* Virtual uses in E.  */
  52   vuse_optype vuses;
  53
  54   /* E's hash value.  */
  55   hashval_t hashcode;
  56 } *val_expr_pair_t;
  57
  58 static void set_value_handle (tree e, tree v);
  59
  60
  61 /* Create and return a new value handle node of type TYPE.  */
  62
  63 static tree
  64 make_value_handle (tree type)
  65 {
  66   static unsigned int id = 0;
  67   tree vh;
  68
  69   vh = build0 (VALUE_HANDLE, type);
  70   VALUE_HANDLE_ID (vh) = id++;
  71   return vh;
  72 }
  73
  74
  75 /* Given an expression EXPR, compute a hash value number using the
  76    code of the expression, its real operands and virtual operands (if
  77    any).
  78
  79    VAL can be used to iterate by passing previous value numbers (it is
  80    used by iterative_hash_expr).
  81
  82    VUSES is the set of virtual use operands associated with EXPR.  It
  83    may be NULL if EXPR has no virtual operands.  */
  84
  85 hashval_t
  86 vn_compute (tree expr, hashval_t val, vuse_optype vuses)
  87 {
  88   size_t i;
  89
  90   /* EXPR must not be a statement.  We are only interested in value
  91      numbering expressions on the RHS of assignments.  */
  92   gcc_assert (expr);
  93   gcc_assert (!expr->common.ann
  94               || expr->common.ann->common.type != STMT_ANN);
  95
  96   val = iterative_hash_expr (expr, val);
  97
  98   /* If the expression has virtual uses, incorporate them into the
  99      hash value computed for EXPR.  */
 100   for (i = 0; i < NUM_VUSES (vuses); i++)
 101     val = iterative_hash_expr (VUSE_OP (vuses, i), val);
 102
 103   return val;
 104 }
 105
 106
 107 /* Compare two expressions E1 and E2 and return true if they are
 108    equal.  */
 109
 110 bool
 111 expressions_equal_p (tree e1, tree e2)
 112 {
 113   tree te1, te2;
 114
 115   if (e1 == e2)
 116     return true;
 117
 118   te1 = TREE_TYPE (e1);
 119   te2 = TREE_TYPE (e2);
 120
 121   if (TREE_CODE (e1) == TREE_CODE (e2)
 122       && (te1 == te2 || lang_hooks.types_compatible_p (te1, te2))
 123       && operand_equal_p (e1, e2, OEP_PURE_SAME))
 124     return true;
 125
 126   return false;
 127 }
 128
 129
 130 /* Hash a {v,e} pair that is pointed to by P.
 131    The hashcode is cached in the val_expr_pair, so we just return
 132    that.  */
 133
 134 static hashval_t
 135 val_expr_pair_hash (const void *p)
 136 {
 137   const val_expr_pair_t ve = (val_expr_pair_t) p;
 138   return ve->hashcode;
 139 }
 140
 141
 142 /* Given two val_expr_pair_t's, return true if they represent the same
 143    expression, false otherwise.
 144    P1 and P2 should point to the val_expr_pair_t's to be compared.  */
 145
 146 static int
 147 val_expr_pair_expr_eq (const void *p1, const void *p2)
 148 {
 149   const val_expr_pair_t ve1 = (val_expr_pair_t) p1;
 150   const val_expr_pair_t ve2 = (val_expr_pair_t) p2;
 151   size_t i;
 152
 153   if (! expressions_equal_p (ve1->e, ve2->e))
 154     return false;
 155
 156   if (NUM_VUSES (ve1->vuses) != NUM_VUSES (ve2->vuses))
 157     return false;
 158
 159   for (i = 0; i < NUM_VUSES (ve1->vuses); i++)
 160     if (! expressions_equal_p (VUSE_OP (ve1->vuses, i),
 161                                VUSE_OP (ve2->vuses, i)))
 162       return false;
 163
 164   return true;
 165 }
 166
 167
 168 /* Set the value handle for expression E to value V.  */
 169
 170 static void
 171 set_value_handle (tree e, tree v)
 172 {
 173   if (TREE_CODE (e) == SSA_NAME)
 174     SSA_NAME_VALUE (e) = v;
 175   else if (EXPR_P (e) || DECL_P (e))
 176     get_tree_ann (e)->common.value_handle = v;
 177   else
 178     /* Do nothing.  Constants are their own value handles.  */
 179     gcc_assert (is_gimple_min_invariant (e));
 180 }
 181
 182
 183 /* Insert EXPR into VALUE_TABLE with value VAL, and add expression
 184    EXPR to the value set for value VAL.  VUSES represent the virtual
 185    use operands associated with EXPR (if any).  They are used when
 186    computing the hash value for EXPR.  */
 187
 188 void
 189 vn_add (tree expr, tree val, vuse_optype vuses)
 190 {
 191   void **slot;
 192   val_expr_pair_t new_pair;
 193
 194   new_pair = xmalloc (sizeof (struct val_expr_pair_d));
 195   new_pair->e = expr;
 196   new_pair->v = val;
 197   new_pair->vuses = vuses;
 198   new_pair->hashcode = vn_compute (expr, 0, vuses);
 199   slot = htab_find_slot_with_hash (value_table, new_pair, new_pair->hashcode,
 200                                    INSERT);
 201   if (*slot)
 202     free (*slot);
 203   *slot = (void *) new_pair;
 204
 205   set_value_handle (expr, val);
 206   add_to_value (val, expr);
 207 }
 208
 209
 210 /* Search in VALUE_TABLE for an existing instance of expression EXPR,
 211    and return its value, or NULL if none has been set.  VUSES
 212    represent the virtual use operands associated with EXPR (if any).
 213    They are used when computing the hash value for EXPR.  */
 214
 215 tree
 216 vn_lookup (tree expr, vuse_optype vuses)
 217 {
 218   void **slot;
 219   struct val_expr_pair_d vep = {NULL, NULL, NULL, 0};
 220
 221   /* Constants are their own value.  */
 222   if (is_gimple_min_invariant (expr))
 223     return expr;
 224
 225   vep.e = expr;
 226   vep.vuses = vuses;
 227   vep.hashcode = vn_compute (expr, 0, vuses);
 228   slot = htab_find_slot_with_hash (value_table, &vep, vep.hashcode, NO_INSERT);
 229   if (!slot)
 230     return NULL_TREE;
 231   else
 232     return ((val_expr_pair_t) *slot)->v;
 233 }
 234
 235
 236 /* Like vn_lookup, but creates a new value for expression EXPR, if
 237    EXPR doesn't already have a value.  Return the existing/created
 238    value for EXPR.  VUSES represent the virtual use operands
 239    associated with EXPR (if any).  They are used when computing the
 240    hash value for EXPR.  */
 241
 242 tree
 243 vn_lookup_or_add (tree expr, vuse_optype vuses)
 244 {
 245   tree v = vn_lookup (expr, vuses);
 246   if (v == NULL_TREE)
 247     {
 248       v = make_value_handle (TREE_TYPE (expr));
 249
 250       if (dump_file && (dump_flags & TDF_DETAILS))
 251         {
 252           fprintf (dump_file, "Created value ");
 253           print_generic_expr (dump_file, v, dump_flags);
 254           fprintf (dump_file, " for ");
 255           print_generic_expr (dump_file, expr, dump_flags);
 256           fprintf (dump_file, "\n");
 257         }
 258
 259       vn_add (expr, v, vuses);
 260     }
 261
 262   set_value_handle (expr, v);
 263
 264   return v;
 265 }
 266
 267
 268 /* Get the value handle of EXPR.  This is the only correct way to get
 269    the value handle for a "thing".  If EXPR does not have a value
 270    handle associated, it returns NULL_TREE.
 271    NB: If EXPR is min_invariant, this function is *required* to return EXPR.  */
 272
 273 tree
 274 get_value_handle (tree expr)
 275 {
 276
 277   if (is_gimple_min_invariant (expr))
 278     return expr;
 279
 280   if (TREE_CODE (expr) == SSA_NAME)
 281     return SSA_NAME_VALUE (expr);
 282   else if (EXPR_P (expr) || DECL_P (expr))
 283     {
 284       tree_ann_t ann = tree_ann (expr);
 285       return ((ann) ? ann->common.value_handle : NULL_TREE);
 286     }
 287   else
 288     gcc_unreachable ();
 289 }
 290
 291
 292 /* Initialize data structures used in value numbering.  */
 293
 294 void
 295 vn_init (void)
 296 {
 297   value_table = htab_create (511, val_expr_pair_hash,
 298                              val_expr_pair_expr_eq, free);
 299 }
 300
 301
 302 /* Delete data used for value numbering.  */
 303
 304 void
 305 vn_delete (void)
 306 {
 307   htab_delete (value_table);
 308   value_table = NULL;
 309 }