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