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
 155   if (expressions_equal_p (ve1->e, ve2->e))
 156     return true;
 157
 158   return false;
 159 }
 160
 161
 162 /* Set the value handle for expression E to value V */
 163
 164 static void
 165 set_value_handle (tree e, tree v)
 166 {
 167   if (TREE_CODE (e) == SSA_NAME)
 168     SSA_NAME_VALUE (e) = v;
 169   else if (EXPR_P (e) || DECL_P (e))
 170     get_tree_ann (e)->common.value_handle = v;
 171   else if (is_gimple_min_invariant (e))
 172     /* Do nothing.  Constants are their own value handles.  */
 173     ;
 174   else
 175     abort ();
 176 }
 177
 178
 179 /* Insert EXPR into VALUE_TABLE with value VAL, and add expression
 180    EXPR to the value set for value VAL.  VUSES represent the virtual
 181    use operands associated with EXPR (if any).  They are used when
 182    computing the hash value for EXPR.  */
 183
 184 void
 185 vn_add (tree expr, tree val, vuse_optype vuses)
 186 {
 187   void **slot;
 188   val_expr_pair_t new_pair;
 189
 190   new_pair = xmalloc (sizeof (struct val_expr_pair_d));
 191   new_pair->e = expr;
 192   new_pair->v = val;
 193   new_pair->vuses = vuses;
 194   new_pair->hashcode = vn_compute (expr, 0, vuses);
 195   slot = htab_find_slot_with_hash (value_table, new_pair, new_pair->hashcode,
 196                                    INSERT);
 197   if (*slot)
 198     free (*slot);
 199   *slot = (void *) new_pair;
 200
 201   set_value_handle (expr, val);
 202   add_to_value (val, expr);
 203 }
 204
 205
 206 /* Search in VALUE_TABLE for an existing instance of expression EXPR,
 207    and return its value, or NULL if none has been set.  VUSES
 208    represent the virtual use operands associated with EXPR (if any).
 209    They are used when computing the hash value for EXPR.  */
 210
 211 tree
 212 vn_lookup (tree expr, vuse_optype vuses)
 213 {
 214   void **slot;
 215   struct val_expr_pair_d vep = {NULL, NULL, NULL, 0};
 216
 217   /* Constants are their own value.  */
 218   if (is_gimple_min_invariant (expr))
 219     return expr;
 220
 221   vep.e = expr;
 222   vep.vuses = vuses;
 223   vep.hashcode = vn_compute (expr, 0, vuses);
 224   slot = htab_find_slot_with_hash (value_table, &vep, vep.hashcode, NO_INSERT);
 225   if (!slot)
 226     return NULL_TREE;
 227   else
 228     return ((val_expr_pair_t) *slot)->v;
 229 }
 230
 231
 232 /* Like vn_lookup, but creates a new value for expression EXPR, if
 233    EXPR doesn't already have a value.  Return the existing/created
 234    value for EXPR.  VUSES represent the virtual use operands
 235    associated with EXPR (if any).  They are used when computing the
 236    hash value for EXPR.  */
 237
 238 tree
 239 vn_lookup_or_add (tree expr, vuse_optype vuses)
 240 {
 241   tree v = vn_lookup (expr, vuses);
 242   if (v == NULL_TREE)
 243     {
 244       v = make_value_handle (TREE_TYPE (expr));
 245
 246       if (dump_file && (dump_flags & TDF_DETAILS))
 247         {
 248           fprintf (dump_file, "Created value ");
 249           print_generic_expr (dump_file, v, dump_flags);
 250           fprintf (dump_file, " for ");
 251           print_generic_expr (dump_file, expr, dump_flags);
 252           fprintf (dump_file, "\n");
 253         }
 254
 255       vn_add (expr, v, vuses);
 256     }
 257
 258   set_value_handle (expr, v);
 259
 260   return v;
 261 }
 262
 263
 264 /* Get the value handle of EXPR.  This is the only correct way to get
 265    the value handle for a "thing".  If EXPR does not have a value
 266    handle associated, it returns NULL_TREE.  */
 267
 268 tree
 269 get_value_handle (tree expr)
 270 {
 271   if (TREE_CODE (expr) == SSA_NAME)
 272     return SSA_NAME_VALUE (expr);
 273   else if (EXPR_P (expr) || DECL_P (expr))
 274     {
 275       tree_ann_t ann = tree_ann (expr);
 276       return ((ann) ? ann->common.value_handle : NULL_TREE);
 277     }
 278   else if (is_gimple_min_invariant (expr))
 279     return expr;
 280
 281   abort ();
 282 }
 283
 284
 285 /* Initialize data structures used in value numbering.  */
 286
 287 void
 288 vn_init (void)
 289 {
 290   value_table = htab_create (511, val_expr_pair_hash,
 291                              val_expr_pair_expr_eq, free);
 292 }
 293
 294
 295 /* Delete data used for value numbering.  */
 296
 297 void
 298 vn_delete (void)
 299 {
 300   htab_delete (value_table);
 301   value_table = NULL;
 302 }