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