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 (is_gimple_min_invariant (e
))
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 /* Constants are their own value. */
218 if (is_gimple_min_invariant (expr
))
223 vep
.hashcode
= vn_compute (expr
, 0, vuses
);
224 slot
= htab_find_slot_with_hash (value_table
, &vep
, vep
.hashcode
, NO_INSERT
);
228 return ((val_expr_pair_t
) *slot
)->v
;
232 /* Like vn_lookup, but creates a new value for expression EXPR, if
233 EXPR doesn't already have a value. Return the existing/created
234 value for EXPR. VUSES represent the virtual use operands
235 associated with EXPR (if any). They are used when computing the
236 hash value for EXPR. */
239 vn_lookup_or_add (tree expr
, vuse_optype vuses
)
241 tree v
= vn_lookup (expr
, vuses
);
244 v
= make_value_handle (TREE_TYPE (expr
));
246 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
248 fprintf (dump_file
, "Created value ");
249 print_generic_expr (dump_file
, v
, dump_flags
);
250 fprintf (dump_file
, " for ");
251 print_generic_expr (dump_file
, expr
, dump_flags
);
252 fprintf (dump_file
, "\n");
255 vn_add (expr
, v
, vuses
);
258 set_value_handle (expr
, v
);
264 /* Get the value handle of EXPR. This is the only correct way to get
265 the value handle for a "thing". If EXPR does not have a value
266 handle associated, it returns NULL_TREE. */
269 get_value_handle (tree expr
)
271 if (TREE_CODE (expr
) == SSA_NAME
)
272 return SSA_NAME_VALUE (expr
);
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
);
278 else if (is_gimple_min_invariant (expr
))
285 /* Initialize data structures used in value numbering. */
290 value_table
= htab_create (511, val_expr_pair_hash
,
291 val_expr_pair_expr_eq
, free
);
295 /* Delete data used for value numbering. */
300 htab_delete (value_table
);