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, 51 Franklin Street, Fifth Floor,
  21 Boston, MA 02110-1301, 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            || TREE_CODE (e) == CONSTRUCTOR)
 187     get_tree_ann (e)->common.value_handle = v;
 188   else
 189     /* Do nothing.  Constants are their own value handles.  */
 190     gcc_assert (is_gimple_min_invariant (e));
 191 }
 192
 193
 194 /* Insert EXPR into VALUE_TABLE with value VAL, and add expression
 195    EXPR to the value set for value VAL.  STMT represents the stmt
 196    associated with EXPR.  It is used when computing a hash value for EXPR.  */
 197
 198 void
 199 vn_add (tree expr, tree val, tree stmt)
 200 {
 201   void **slot;
 202   val_expr_pair_t new_pair;
 203
 204   new_pair = XNEW (struct val_expr_pair_d);
 205   new_pair->e = expr;
 206   new_pair->v = val;
 207   new_pair->stmt = stmt;
 208   new_pair->hashcode = vn_compute (expr, 0, stmt);
 209   slot = htab_find_slot_with_hash (value_table, new_pair, new_pair->hashcode,
 210                                    INSERT);
 211   if (*slot)
 212     free (*slot);
 213   *slot = (void *) new_pair;
 214
 215   set_value_handle (expr, val);
 216   add_to_value (val, expr);
 217 }
 218
 219
 220 /* Search in VALUE_TABLE for an existing instance of expression EXPR,
 221    and return its value, or NULL if none has been set.  STMT
 222    represents the stmt associated with EXPR.  It is used when computing the
 223    hash value for EXPR.  */
 224
 225 tree
 226 vn_lookup (tree expr, tree stmt)
 227 {
 228   void **slot;
 229   struct val_expr_pair_d vep = {NULL, NULL, NULL, 0};
 230
 231   /* Constants are their own value.  */
 232   if (is_gimple_min_invariant (expr))
 233     return expr;
 234
 235   vep.e = expr;
 236   vep.stmt = stmt;
 237   vep.hashcode = vn_compute (expr, 0, stmt);
 238   slot = htab_find_slot_with_hash (value_table, &vep, vep.hashcode, NO_INSERT);
 239   if (!slot)
 240     return NULL_TREE;
 241   else
 242     return ((val_expr_pair_t) *slot)->v;
 243 }
 244
 245
 246 /* Like vn_lookup, but creates a new value for expression EXPR, if
 247    EXPR doesn't already have a value.  Return the existing/created
 248    value for EXPR.  STMT represents the stmt associated with EXPR.  It is used
 249    when computing the hash value for EXPR.  */
 250
 251 tree
 252 vn_lookup_or_add (tree expr, tree stmt)
 253 {
 254   tree v = vn_lookup (expr, stmt);
 255   if (v == NULL_TREE)
 256     {
 257       v = make_value_handle (TREE_TYPE (expr));
 258
 259       if (dump_file && (dump_flags & TDF_DETAILS))
 260         {
 261           fprintf (dump_file, "Created value ");
 262           print_generic_expr (dump_file, v, dump_flags);
 263           fprintf (dump_file, " for ");
 264           print_generic_expr (dump_file, expr, dump_flags);
 265           fprintf (dump_file, "\n");
 266         }
 267
 268       vn_add (expr, v, stmt);
 269     }
 270
 271   set_value_handle (expr, v);
 272
 273   return v;
 274 }
 275
 276
 277 /* Get the value handle of EXPR.  This is the only correct way to get
 278    the value handle for a "thing".  If EXPR does not have a value
 279    handle associated, it returns NULL_TREE.
 280    NB: If EXPR is min_invariant, this function is *required* to return EXPR.  */
 281
 282 tree
 283 get_value_handle (tree expr)
 284 {
 285
 286   if (is_gimple_min_invariant (expr))
 287     return expr;
 288
 289   if (TREE_CODE (expr) == SSA_NAME)
 290     return SSA_NAME_VALUE (expr);
 291   else if (EXPR_P (expr) || DECL_P (expr) || TREE_CODE (expr) == TREE_LIST
 292            || TREE_CODE (expr) == CONSTRUCTOR)
 293     {
 294       tree_ann_t ann = tree_ann (expr);
 295       return ((ann) ? ann->common.value_handle : NULL_TREE);
 296     }
 297   else
 298     gcc_unreachable ();
 299 }
 300
 301
 302 /* Initialize data structures used in value numbering.  */
 303
 304 void
 305 vn_init (void)
 306 {
 307   value_table = htab_create (511, val_expr_pair_hash,
 308                              val_expr_pair_expr_eq, free);
 309 }
 310
 311
 312 /* Delete data used for value numbering.  */
 313
 314 void
 315 vn_delete (void)
 316 {
 317   htab_delete (value_table);
 318   value_table = NULL;
 319 }