1 /* Value Numbering routines for tree expressions.
2 Copyright (C) 2001, 2002, 2003, 2004, 2005, 2007 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 3, 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 COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
28 #include "tree-flow.h"
30 #include "langhooks.h"
31 #include "tree-pass.h"
32 #include "tree-dump.h"
33 #include "diagnostic.h"
34 #include "tree-ssa-sccvn.h"
36 /* Most of this is PRE specific. The real grunt work is done in
37 tree-ssa-sccvn.c. This is where the lookup and insertion
38 functions, etc, can be found */
40 /* Create and return a new value handle node of type TYPE. */
43 make_value_handle (tree type
)
45 static unsigned int id
= 0;
48 vh
= build0 (VALUE_HANDLE
, type
);
49 VALUE_HANDLE_ID (vh
) = id
++;
55 /* Compare two expressions E1 and E2 and return true if they are
59 expressions_equal_p (tree e1
, tree e2
)
69 if (TREE_CODE (e1
) == TREE_LIST
&& TREE_CODE (e2
) == TREE_LIST
)
73 for (lop1
= e1
, lop2
= e2
;
75 lop1
= TREE_CHAIN (lop1
), lop2
= TREE_CHAIN (lop2
))
79 if (!expressions_equal_p (TREE_VALUE (lop1
), TREE_VALUE (lop2
)))
85 else if (TREE_CODE (e1
) == TREE_CODE (e2
)
87 || types_compatible_p (te1
, te2
))
88 && operand_equal_p (e1
, e2
, OEP_PURE_SAME
))
94 /* Set the value handle for expression E to value V. */
97 set_value_handle (tree e
, tree v
)
99 if (TREE_CODE (e
) == SSA_NAME
)
100 SSA_NAME_VALUE (e
) = v
;
101 else if (EXPR_P (e
) || DECL_P (e
) || TREE_CODE (e
) == TREE_LIST
103 || TREE_CODE (e
) == CONSTRUCTOR
)
104 get_tree_common_ann (e
)->value_handle
= v
;
106 /* Do nothing. Constants are their own value handles. */
107 gcc_assert (is_gimple_min_invariant (e
));
110 /* Print out the "Created value <x> for <Y>" statement to the
112 This is factored because both versions of lookup use it, and it
113 obscures the real work going on in those functions. */
116 print_creation_to_file (tree v
, tree expr
, VEC (tree
, gc
) *vuses
)
118 fprintf (dump_file
, "Created value ");
119 print_generic_expr (dump_file
, v
, dump_flags
);
120 fprintf (dump_file
, " for ");
121 print_generic_expr (dump_file
, expr
, dump_flags
);
123 if (vuses
&& VEC_length (tree
, vuses
) != 0)
128 fprintf (dump_file
, " vuses: (");
129 for (i
= 0; VEC_iterate (tree
, vuses
, i
, vuse
); i
++)
131 print_generic_expr (dump_file
, vuse
, dump_flags
);
132 if (VEC_length (tree
, vuses
) - 1 != i
)
133 fprintf (dump_file
, ",");
135 fprintf (dump_file
, ")");
137 fprintf (dump_file
, "\n");
141 /* Sort the VUSE array so that we can do equality comparisons
142 quicker on two vuse vecs. */
145 sort_vuses (VEC (tree
,gc
) *vuses
)
147 if (VEC_length (tree
, vuses
) > 1)
148 qsort (VEC_address (tree
, vuses
),
149 VEC_length (tree
, vuses
),
154 /* Sort the VUSE array so that we can do equality comparisons
155 quicker on two vuse vecs. */
158 sort_vuses_heap (VEC (tree
,heap
) *vuses
)
160 if (VEC_length (tree
, vuses
) > 1)
161 qsort (VEC_address (tree
, vuses
),
162 VEC_length (tree
, vuses
),
166 /* Insert EXPR into VALUE_TABLE with value VAL, and add expression
167 EXPR to the value set for value VAL. */
170 vn_add (tree expr
, tree val
)
172 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
176 vn_nary_op_insert (expr
, val
);
179 vn_nary_op_insert (expr
, val
);
181 /* In the case of array-refs of constants, for example, we can
182 end up with no vuses. */
184 vn_reference_insert (expr
, val
, NULL
);
186 /* The *only* time CALL_EXPR should appear here is
187 when it has no vuses. */
189 case tcc_exceptional
:
191 case tcc_declaration
:
192 if (TREE_CODE (expr
) == CALL_EXPR
|| DECL_P (expr
))
194 vn_reference_insert (expr
, val
, NULL
);
197 else if (TREE_CODE (expr
) == SSA_NAME
)
199 SSA_NAME_VALUE (expr
) = val
;
202 else if (TREE_CODE (expr
) == ADDR_EXPR
)
204 vn_nary_op_insert (expr
, val
);
211 set_value_handle (expr
, val
);
212 if (TREE_CODE (val
) == VALUE_HANDLE
)
213 add_to_value (val
, expr
);
216 /* Insert EXPR into the value numbering tables. with value VAL, and
217 add expression EXPR to the value set for value VAL. VUSES
218 represents the virtual use operands associated with EXPR. It is
219 used when computing a hash value for EXPR. */
222 vn_add_with_vuses (tree expr
, tree val
, VEC (tree
, gc
) *vuses
)
229 vn_reference_insert (expr
, val
, vuses
);
231 set_value_handle (expr
, val
);
232 if (TREE_CODE (val
) == VALUE_HANDLE
)
233 add_to_value (val
, expr
);
237 /* Lookup EXPR in the value numbering tables and return the result, if
241 vn_lookup (tree expr
)
243 /* Constants are their own value. */
244 if (is_gimple_min_invariant (expr
) || TREE_CODE (expr
) == FIELD_DECL
)
247 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
251 return vn_nary_op_lookup (expr
);
253 return vn_nary_op_lookup (expr
);
255 /* In the case of array-refs of constants, for example, we can
256 end up with no vuses. */
258 return vn_reference_lookup (expr
, NULL
);
260 /* It is possible to have CALL_EXPR with no vuses for things
261 like "cos", and these will fall into vn_lookup. */
263 case tcc_exceptional
:
265 case tcc_declaration
:
266 if (TREE_CODE (expr
) == CALL_EXPR
|| DECL_P (expr
))
267 return vn_reference_lookup (expr
, NULL
);
268 else if (TREE_CODE (expr
) == SSA_NAME
)
269 return SSA_NAME_VALUE (expr
);
270 else if (TREE_CODE (expr
) == ADDR_EXPR
)
271 return vn_nary_op_lookup (expr
);
279 /* Search in the value numbering tables for an existing instance of
280 expression EXPR, and return its value, or NULL if none has been set. STMT
281 represents the stmt associated with EXPR. It is used when computing the
282 hash value for EXPR for reference operations. */
285 vn_lookup_with_stmt (tree expr
, tree stmt
)
288 return vn_lookup (expr
);
290 /* Constants are their own value. */
291 if (is_gimple_min_invariant (expr
) || TREE_CODE (expr
) == FIELD_DECL
)
294 return vn_lookup_with_vuses (expr
, shared_vuses_from_stmt (stmt
));
297 /* Search in VALUE_TABLE for an existing instance of expression EXPR,
298 and return its value, or NULL if none has been set. VUSES is the
299 list of virtual use operands associated with EXPR. It is used when
300 computing the hash value for EXPR. */
303 vn_lookup_with_vuses (tree expr
, VEC (tree
, gc
) *vuses
)
305 if (!vuses
|| !VEC_length (tree
, vuses
))
306 return vn_lookup (expr
);
308 if (is_gimple_min_invariant (expr
) || TREE_CODE (expr
) == FIELD_DECL
)
311 return vn_reference_lookup (expr
, vuses
);
315 create_value_handle_for_expr (tree expr
, VEC(tree
, gc
) *vuses
)
319 v
= make_value_handle (TREE_TYPE (expr
));
321 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
322 print_creation_to_file (v
, expr
, vuses
);
326 /* Like vn_lookup, but creates a new value for the operation if one
330 vn_lookup_or_add (tree expr
)
332 tree v
= vn_lookup (expr
);
336 v
= create_value_handle_for_expr (expr
, NULL
);
340 set_value_handle (expr
, v
);
345 /* Like vn_lookup, but handles reference operations as well by using
346 STMT to get the set of vuses. */
349 vn_lookup_or_add_with_stmt (tree expr
, tree stmt
)
353 return vn_lookup_or_add (expr
);
355 v
= vn_lookup_with_stmt (expr
, stmt
);
358 VEC (tree
, gc
) *vuses
= copy_vuses_from_stmt (stmt
);
359 v
= create_value_handle_for_expr (expr
, vuses
);
360 vn_add_with_vuses (expr
, v
, vuses
);
363 set_value_handle (expr
, v
);
368 /* Like vn_lookup, but creates a new value for expression EXPR, if
369 EXPR doesn't already have a value. Return the existing/created
370 value for EXPR. STMT represents the stmt associated with EXPR. It is used
371 when computing the hash value for EXPR. */
374 vn_lookup_or_add_with_vuses (tree expr
, VEC (tree
, gc
) *vuses
)
378 if (!vuses
|| VEC_length (tree
, vuses
) == 0)
379 return vn_lookup_or_add (expr
);
381 v
= vn_lookup_with_vuses (expr
, vuses
);
384 v
= create_value_handle_for_expr (expr
, vuses
);
385 vn_add_with_vuses (expr
, v
, vuses
);
388 set_value_handle (expr
, v
);