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