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, 51 Franklin Street, Fifth Floor,
21 Boston, MA 02110-1301, 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"
35 #include "tree-ssa-sccvn.h"
37 /* Most of this is PRE specific. The real grunt work is done in
38 tree-ssa-sccvn.c. This is where the lookup and insertion
39 functions, etc, can be found */
41 /* Create and return a new value handle node of type TYPE. */
44 make_value_handle (tree type)
46 static unsigned int id = 0;
49 vh = build0 (VALUE_HANDLE, type);
50 VALUE_HANDLE_ID (vh) = id++;
56 /* Compare two expressions E1 and E2 and return true if they are
60 expressions_equal_p (tree e1, tree e2)
70 if (TREE_CODE (e1) == TREE_LIST && TREE_CODE (e2) == TREE_LIST)
74 for (lop1 = e1, lop2 = e2;
76 lop1 = TREE_CHAIN (lop1), lop2 = TREE_CHAIN (lop2))
80 if (!expressions_equal_p (TREE_VALUE (lop1), TREE_VALUE (lop2)))
86 else if (TREE_CODE (e1) == TREE_CODE (e2)
88 || types_compatible_p (te1, te2))
89 && operand_equal_p (e1, e2, OEP_PURE_SAME))
95 /* Set the value handle for expression E to value V. */
98 set_value_handle (tree e, tree v)
100 if (TREE_CODE (e) == SSA_NAME)
101 SSA_NAME_VALUE (e) = v;
102 else if (EXPR_P (e) || DECL_P (e) || TREE_CODE (e) == TREE_LIST
104 || TREE_CODE (e) == CONSTRUCTOR)
105 get_tree_common_ann (e)->value_handle = v;
107 /* Do nothing. Constants are their own value handles. */
108 gcc_assert (is_gimple_min_invariant (e));
114 /* A comparison function for use in qsort to compare vuses. Simply
115 subtracts version numbers. */
118 vuses_compare (const void *pa, const void *pb)
120 const tree vusea = *((const tree *)pa);
121 const tree vuseb = *((const tree *)pb);
122 int sn = SSA_NAME_VERSION (vusea) - SSA_NAME_VERSION (vuseb);
127 /* Print out the "Created value <x> for <Y>" statement to the
129 This is factored because both versions of lookup use it, and it
130 obscures the real work going on in those functions. */
133 print_creation_to_file (tree v, tree expr, VEC (tree, gc) *vuses)
135 fprintf (dump_file, "Created value ");
136 print_generic_expr (dump_file, v, dump_flags);
137 fprintf (dump_file, " for ");
138 print_generic_expr (dump_file, expr, dump_flags);
140 if (vuses && VEC_length (tree, vuses) != 0)
145 fprintf (dump_file, " vuses: (");
146 for (i = 0; VEC_iterate (tree, vuses, i, vuse); i++)
148 print_generic_expr (dump_file, vuse, dump_flags);
149 if (VEC_length (tree, vuses) - 1 != i)
150 fprintf (dump_file, ",");
152 fprintf (dump_file, ")");
154 fprintf (dump_file, "\n");
158 /* Sort the VUSE array so that we can do equality comparisons
159 quicker on two vuse vecs. */
162 sort_vuses (VEC (tree,gc) *vuses)
164 if (VEC_length (tree, vuses) > 1)
165 qsort (VEC_address (tree, vuses),
166 VEC_length (tree, vuses),
171 /* Sort the VUSE array so that we can do equality comparisons
172 quicker on two vuse vecs. */
175 sort_vuses_heap (VEC (tree,heap) *vuses)
177 if (VEC_length (tree, vuses) > 1)
178 qsort (VEC_address (tree, vuses),
179 VEC_length (tree, vuses),
183 /* Insert EXPR into VALUE_TABLE with value VAL, and add expression
184 EXPR to the value set for value VAL. */
187 vn_add (tree expr, tree val)
189 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
193 vn_binary_op_insert (expr, val);
196 vn_unary_op_insert (expr, val);
198 /* In the case of array-refs of constants, for example, we can
199 end up with no vuses. */
201 vn_reference_insert (expr, val, NULL);
203 /* The *only* time CALL_EXPR should appear here is
204 when it has no vuses. */
206 case tcc_exceptional:
208 case tcc_declaration:
209 if (TREE_CODE (expr) == CALL_EXPR || DECL_P (expr))
211 vn_reference_insert (expr, val, NULL);
214 else if (TREE_CODE (expr) == SSA_NAME)
216 SSA_NAME_VALUE (expr) = val;
219 else if (TREE_CODE (expr) == ADDR_EXPR)
221 vn_unary_op_insert (expr, val);
228 set_value_handle (expr, val);
229 if (TREE_CODE (val) == VALUE_HANDLE)
230 add_to_value (val, expr);
233 /* Insert EXPR into the value numbering tables. with value VAL, and
234 add expression EXPR to the value set for value VAL. VUSES
235 represents the virtual use operands associated with EXPR. It is
236 used when computing a hash value for EXPR. */
239 vn_add_with_vuses (tree expr, tree val, VEC (tree, gc) *vuses)
246 vn_reference_insert (expr, val, vuses);
248 set_value_handle (expr, val);
249 if (TREE_CODE (val) == VALUE_HANDLE)
250 add_to_value (val, expr);
254 /* Lookup EXPR in the value numbering tables and return the result, if
258 vn_lookup (tree expr)
260 /* Constants are their own value. */
261 if (is_gimple_min_invariant (expr) || TREE_CODE (expr) == FIELD_DECL)
264 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
268 return vn_binary_op_lookup (expr);
270 return vn_unary_op_lookup (expr);
272 /* In the case of array-refs of constants, for example, we can
273 end up with no vuses. */
275 return vn_reference_lookup (expr, NULL);
277 /* It is possible to have CALL_EXPR with no vuses for things
278 like "cos", and these will fall into vn_lookup. */
280 case tcc_exceptional:
282 case tcc_declaration:
283 if (TREE_CODE (expr) == CALL_EXPR || DECL_P (expr))
284 return vn_reference_lookup (expr, NULL);
285 else if (TREE_CODE (expr) == SSA_NAME)
286 return SSA_NAME_VALUE (expr);
287 else if (TREE_CODE (expr) == ADDR_EXPR)
288 return vn_unary_op_lookup (expr);
296 /* Search in the value numbering tables for an existing instance of
297 expression EXPR, and return its value, or NULL if none has been set. STMT
298 represents the stmt associated with EXPR. It is used when computing the
299 hash value for EXPR for reference operations. */
302 vn_lookup_with_stmt (tree expr, tree stmt)
305 return vn_lookup (expr);
307 /* Constants are their own value. */
308 if (is_gimple_min_invariant (expr) || TREE_CODE (expr) == FIELD_DECL)
311 return vn_lookup_with_vuses (expr, shared_vuses_from_stmt (stmt));
314 /* Search in VALUE_TABLE for an existing instance of expression EXPR,
315 and return its value, or NULL if none has been set. VUSES is the
316 list of virtual use operands associated with EXPR. It is used when
317 computing the hash value for EXPR. */
320 vn_lookup_with_vuses (tree expr, VEC (tree, gc) *vuses)
322 if (!vuses || !VEC_length (tree, vuses))
323 return vn_lookup (expr);
325 if (is_gimple_min_invariant (expr) || TREE_CODE (expr) == FIELD_DECL)
328 return vn_reference_lookup (expr, vuses);
332 create_value_handle_for_expr (tree expr, VEC (tree, gc) *vuses)
336 v = make_value_handle (TREE_TYPE (expr));
338 if (dump_file && (dump_flags & TDF_DETAILS))
339 print_creation_to_file (v, expr, vuses);
341 VALUE_HANDLE_VUSES (v) = vuses;
345 /* Like vn_lookup, but creates a new value for the operation if one
349 vn_lookup_or_add (tree expr)
351 tree v = vn_lookup (expr);
355 v = create_value_handle_for_expr (expr, NULL);
359 set_value_handle (expr, v);
364 /* Like vn_lookup, but handles reference operations as well by using
365 STMT to get the set of vuses. */
368 vn_lookup_or_add_with_stmt (tree expr, tree stmt)
372 return vn_lookup_or_add (expr);
374 v = vn_lookup_with_stmt (expr, stmt);
377 VEC (tree, gc) *vuses = copy_vuses_from_stmt (stmt);
378 v = create_value_handle_for_expr (expr, vuses);
379 vn_add_with_vuses (expr, v, vuses);
382 set_value_handle (expr, v);
387 /* Like vn_lookup, but creates a new value for expression EXPR, if
388 EXPR doesn't already have a value. Return the existing/created
389 value for EXPR. STMT represents the stmt associated with EXPR. It is used
390 when computing the hash value for EXPR. */
393 vn_lookup_or_add_with_vuses (tree expr, VEC (tree, gc) *vuses)
397 if (!vuses || VEC_length (tree, vuses) == 0)
398 return vn_lookup_or_add (expr);
400 v = vn_lookup_with_vuses (expr, vuses);
403 v = create_value_handle_for_expr (expr, vuses);
404 vn_add_with_vuses (expr, v, vuses);
407 set_value_handle (expr, v);