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>
6 This file is part of GCC.
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)
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.
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. */
25 #include "coretypes.h"
29 #include "tree-flow.h"
31 #include "langhooks.h"
32 #include "tree-pass.h"
33 #include "tree-dump.h"
34 #include "diagnostic.h"
36 /* The value table that maps expressions to values. */
37 static htab_t value_table;
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
48 /* Associated expression. */
51 /* Virtual uses in E. */
58 static void set_value_handle (tree e, tree v);
61 /* Create and return a new value handle node of type TYPE. */
64 make_value_handle (tree type)
66 static unsigned int id = 0;
69 vh = build0 (VALUE_HANDLE, type);
70 VALUE_HANDLE_ID (vh) = id++;
75 /* Given an expression EXPR, compute a hash value number using the
76 code of the expression, its real operands and virtual operands (if
79 VAL can be used to iterate by passing previous value numbers (it is
80 used by iterative_hash_expr).
82 VUSES is the set of virtual use operands associated with EXPR. It
83 may be NULL if EXPR has no virtual operands. */
86 vn_compute (tree expr, hashval_t val, vuse_optype vuses)
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. */
95 && expr->common.ann->common.type == STMT_ANN))
99 val = iterative_hash_expr (expr, val);
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);
110 /* Compare two expressions E1 and E2 and return true if they are
114 expressions_equal_p (tree e1, tree e2)
121 te1 = TREE_TYPE (e1);
122 te2 = TREE_TYPE (e2);
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))
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
138 val_expr_pair_hash (const void *p)
140 const val_expr_pair_t ve = (val_expr_pair_t) p;
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. */
150 val_expr_pair_expr_eq (const void *p1, const void *p2)
152 const val_expr_pair_t ve1 = (val_expr_pair_t) p1;
153 const val_expr_pair_t ve2 = (val_expr_pair_t) p2;
155 if (expressions_equal_p (ve1->e, ve2->e))
162 /* Set the value handle for expression E to value V */
165 set_value_handle (tree e, tree v)
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 (TREE_CODE_CLASS (TREE_CODE (e)) == 'c')
172 /* Do nothing. Constants are their own value handles. */
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. */
185 vn_add (tree expr, tree val, vuse_optype vuses)
188 val_expr_pair_t new_pair;
190 new_pair = xmalloc (sizeof (struct val_expr_pair_d));
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,
199 *slot = (void *) new_pair;
201 set_value_handle (expr, val);
202 add_to_value (val, expr);
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. */
212 vn_lookup (tree expr, vuse_optype vuses)
215 struct val_expr_pair_d vep = {NULL, NULL, NULL, 0};
217 if (TREE_CODE_CLASS (TREE_CODE (expr)) == 'c')
221 vep.hashcode = vn_compute (expr, 0, vuses);
222 slot = htab_find_slot_with_hash (value_table, &vep, vep.hashcode, NO_INSERT);
226 return ((val_expr_pair_t) *slot)->v;
230 /* Like vn_lookup, but creates a new value for expression EXPR, if
231 EXPR doesn't already have a value. Return the existing/created
232 value for EXPR. VUSES represent the virtual use operands
233 associated with EXPR (if any). They are used when computing the
234 hash value for EXPR. */
237 vn_lookup_or_add (tree expr, vuse_optype vuses)
239 tree v = vn_lookup (expr, vuses);
242 v = make_value_handle (TREE_TYPE (expr));
244 if (dump_file && (dump_flags & TDF_DETAILS))
246 fprintf (dump_file, "Created value ");
247 print_generic_expr (dump_file, v, dump_flags);
248 fprintf (dump_file, " for ");
249 print_generic_expr (dump_file, expr, dump_flags);
250 fprintf (dump_file, "\n");
253 vn_add (expr, v, vuses);
256 set_value_handle (expr, v);
262 /* Get the value handle of EXPR. This is the only correct way to get
263 the value handle for a "thing". If EXPR does not have a value
264 handle associated, it generates and returns a new one. */
267 get_value_handle (tree expr)
269 if (TREE_CODE (expr) == SSA_NAME)
270 return SSA_NAME_VALUE (expr);
271 else if (TREE_CODE_CLASS (TREE_CODE (expr)) == 'c')
273 else if (EXPR_P (expr) || DECL_P (expr))
275 tree_ann_t ann = tree_ann (expr);
276 return ((ann) ? ann->common.value_handle : NULL_TREE);
283 /* Initialize data structures used in value numbering. */
288 value_table = htab_create (511, val_expr_pair_hash,
289 val_expr_pair_expr_eq, free);
293 /* Delete data used for value numbering. */
298 htab_delete (value_table);