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>
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 /* for comparing 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 STMT is the stmt associated with EXPR for comparing virtual operands. */
85 vn_compute (tree expr
, hashval_t val
, tree stmt
)
90 /* EXPR must not be a statement. We are only interested in value
91 numbering expressions on the RHS of assignments. */
93 gcc_assert (!expr
->common
.ann
94 || expr
->common
.ann
->common
.type
!= STMT_ANN
);
96 val
= iterative_hash_expr (expr
, val
);
98 /* If the expression has virtual uses, incorporate them into the
99 hash value computed for EXPR. */
101 FOR_EACH_SSA_TREE_OPERAND (vuse
, stmt
, iter
, SSA_OP_VUSE
)
102 val
= iterative_hash_expr (vuse
, val
);
108 /* Compare two expressions E1 and E2 and return true if they are
112 expressions_equal_p (tree e1
, tree e2
)
119 te1
= TREE_TYPE (e1
);
120 te2
= TREE_TYPE (e2
);
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
))
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
136 val_expr_pair_hash (const void *p
)
138 const val_expr_pair_t ve
= (val_expr_pair_t
) p
;
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. */
148 val_expr_pair_expr_eq (const void *p1
, const void *p2
)
151 const val_expr_pair_t ve1
= (val_expr_pair_t
) p1
;
152 const val_expr_pair_t ve2
= (val_expr_pair_t
) p2
;
154 if (! expressions_equal_p (ve1
->e
, ve2
->e
))
157 ret
= compare_ssa_operands_equal (ve1
->stmt
, ve2
->stmt
, SSA_OP_VUSE
);
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
;
172 /* Do nothing. Constants are their own value handles. */
173 gcc_assert (is_gimple_min_invariant (e
));
177 /* Insert EXPR into VALUE_TABLE with value VAL, and add expression
178 EXPR to the value set for value VAL. STMT represents the stmt
179 associated with EXPR. It is used when computing a hash value for EXPR. */
182 vn_add (tree expr
, tree val
, tree stmt
)
185 val_expr_pair_t new_pair
;
187 new_pair
= xmalloc (sizeof (struct val_expr_pair_d
));
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
,
196 *slot
= (void *) new_pair
;
198 set_value_handle (expr
, val
);
199 add_to_value (val
, expr
);
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 represents the stmt associated with EXPR. It is used when computing the
206 hash value for EXPR. */
209 vn_lookup (tree expr
, tree stmt
)
212 struct val_expr_pair_d vep
= {NULL
, NULL
, NULL
, 0};
214 /* Constants are their own value. */
215 if (is_gimple_min_invariant (expr
))
220 vep
.hashcode
= vn_compute (expr
, 0, stmt
);
221 slot
= htab_find_slot_with_hash (value_table
, &vep
, vep
.hashcode
, NO_INSERT
);
225 return ((val_expr_pair_t
) *slot
)->v
;
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 represents the stmt associated with EXPR. It is used
232 when computing the hash value for EXPR. */
235 vn_lookup_or_add (tree expr
, tree stmt
)
237 tree v
= vn_lookup (expr
, stmt
);
240 v
= make_value_handle (TREE_TYPE (expr
));
242 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
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");
251 vn_add (expr
, v
, stmt
);
254 set_value_handle (expr
, v
);
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. */
266 get_value_handle (tree expr
)
269 if (is_gimple_min_invariant (expr
))
272 if (TREE_CODE (expr
) == SSA_NAME
)
273 return SSA_NAME_VALUE (expr
);
274 else if (EXPR_P (expr
) || DECL_P (expr
))
276 tree_ann_t ann
= tree_ann (expr
);
277 return ((ann
) ? ann
->common
.value_handle
: NULL_TREE
);
284 /* Initialize data structures used in value numbering. */
289 value_table
= htab_create (511, val_expr_pair_hash
,
290 val_expr_pair_expr_eq
, free
);
294 /* Delete data used for value numbering. */
299 htab_delete (value_table
);