]>
gcc.gnu.org Git - gcc.git/blob - gcc/tree-vn.c
1 /* Value Numbering routines for tree expressions.
2 Copyright (C) 2001, 2002, 2003, 2004, 2005, 2007, 2008 Free Software
4 Contributed by Daniel Berlin <dan@dberlin.org>, Steven Bosscher
5 <stevenb@suse.de> and Diego Novillo <dnovillo@redhat.com>
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify
10 it under the terms of the GNU General Public License as published by
11 the Free Software Foundation; either version 3, or (at your option)
14 GCC is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING3. If not see
21 <http://www.gnu.org/licenses/>. */
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
++;
54 /* Compare two expressions E1 and E2 and return true if they are
58 expressions_equal_p (tree e1
, tree e2
)
68 if (TREE_CODE (e1
) == TREE_LIST
&& TREE_CODE (e2
) == TREE_LIST
)
72 for (lop1
= e1
, lop2
= e2
;
74 lop1
= TREE_CHAIN (lop1
), lop2
= TREE_CHAIN (lop2
))
78 if (!expressions_equal_p (TREE_VALUE (lop1
), TREE_VALUE (lop2
)))
84 else if (TREE_CODE (e1
) == TREE_CODE (e2
)
85 && operand_equal_p (e1
, e2
, OEP_PURE_SAME
))
91 /* Set the value handle for expression E to value V. */
94 set_value_handle (tree e
, tree v
)
96 if (TREE_CODE (e
) == SSA_NAME
)
97 SSA_NAME_VALUE (e
) = v
;
98 else if (EXPR_P (e
) || DECL_P (e
) || TREE_CODE (e
) == TREE_LIST
100 || TREE_CODE (e
) == CONSTRUCTOR
)
101 get_tree_common_ann (e
)->value_handle
= v
;
103 /* Do nothing. Constants are their own value handles. */
104 gcc_assert (is_gimple_min_invariant (e
));
107 /* Print out the "Created value <x> for <Y>" statement to the
109 This is factored because both versions of lookup use it, and it
110 obscures the real work going on in those functions. */
113 print_creation_to_file (tree v
, tree expr
, VEC (tree
, gc
) *vuses
)
115 fprintf (dump_file
, "Created value ");
116 print_generic_expr (dump_file
, v
, dump_flags
);
117 fprintf (dump_file
, " for ");
118 print_generic_expr (dump_file
, expr
, dump_flags
);
120 if (vuses
&& VEC_length (tree
, vuses
) != 0)
125 fprintf (dump_file
, " vuses: (");
126 for (i
= 0; VEC_iterate (tree
, vuses
, i
, vuse
); i
++)
128 print_generic_expr (dump_file
, vuse
, dump_flags
);
129 if (VEC_length (tree
, vuses
) - 1 != i
)
130 fprintf (dump_file
, ",");
132 fprintf (dump_file
, ")");
134 fprintf (dump_file
, "\n");
137 /* Sort the VUSE array so that we can do equality comparisons
138 quicker on two vuse vecs. */
141 sort_vuses (VEC (tree
,gc
) *vuses
)
143 if (VEC_length (tree
, vuses
) > 1)
144 qsort (VEC_address (tree
, vuses
),
145 VEC_length (tree
, vuses
),
150 /* Sort the VUSE array so that we can do equality comparisons
151 quicker on two vuse vecs. */
154 sort_vuses_heap (VEC (tree
,heap
) *vuses
)
156 if (VEC_length (tree
, vuses
) > 1)
157 qsort (VEC_address (tree
, vuses
),
158 VEC_length (tree
, vuses
),
163 /* Insert EXPR into VALUE_TABLE with value VAL, and add expression
164 EXPR to the value set for value VAL. */
167 vn_add (tree expr
, tree val
)
169 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
173 vn_nary_op_insert (expr
, val
);
176 vn_nary_op_insert (expr
, val
);
178 /* In the case of array-refs of constants, for example, we can
179 end up with no vuses. */
181 vn_reference_insert (expr
, val
, NULL
);
183 /* The *only* time CALL_EXPR should appear here is
184 when it has no vuses. */
186 case tcc_exceptional
:
188 case tcc_declaration
:
189 if (TREE_CODE (expr
) == CALL_EXPR
|| DECL_P (expr
))
191 vn_reference_insert (expr
, val
, NULL
);
194 else if (TREE_CODE (expr
) == SSA_NAME
)
196 SSA_NAME_VALUE (expr
) = val
;
199 switch (TREE_CODE (expr
))
206 vn_nary_op_insert (expr
, val
);
215 set_value_handle (expr
, val
);
216 if (TREE_CODE (val
) == VALUE_HANDLE
)
217 add_to_value (val
, expr
);
220 /* Insert EXPR into the value numbering tables with value VAL, and
221 add expression EXPR to the value set for value VAL. VUSES
222 represents the virtual use operands associated with EXPR. It is
223 used when computing a hash value for EXPR. */
226 vn_add_with_vuses (tree expr
, tree val
, VEC (tree
, gc
) *vuses
)
233 vn_reference_insert (expr
, val
, vuses
);
235 set_value_handle (expr
, val
);
236 if (TREE_CODE (val
) == VALUE_HANDLE
)
237 add_to_value (val
, expr
);
240 /* Lookup EXPR in the value numbering tables and return the result, if
244 vn_lookup (tree expr
)
246 /* Constants are their own value. */
247 if (is_gimple_min_invariant (expr
) || TREE_CODE (expr
) == FIELD_DECL
)
250 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
254 return vn_nary_op_lookup (expr
);
256 return vn_nary_op_lookup (expr
);
258 /* In the case of array-refs of constants, for example, we can
259 end up with no vuses. */
261 return vn_reference_lookup (expr
, NULL
, false);
263 /* It is possible to have CALL_EXPR with no vuses for things
264 like "cos", and these will fall into vn_lookup. */
266 case tcc_exceptional
:
268 case tcc_declaration
:
269 if (TREE_CODE (expr
) == CALL_EXPR
|| DECL_P (expr
))
270 return vn_reference_lookup (expr
, NULL
, false);
271 else if (TREE_CODE (expr
) == SSA_NAME
)
272 return SSA_NAME_VALUE (expr
);
273 switch (TREE_CODE (expr
))
280 return vn_nary_op_lookup (expr
);
291 /* Search in the value numbering tables for an existing instance of
292 expression EXPR, and return its value, or NULL if none has been set. STMT
293 represents the stmt associated with EXPR. It is used when computing the
294 hash value for EXPR for reference operations. */
297 vn_lookup_with_stmt (tree expr
, tree stmt
)
300 return vn_lookup (expr
);
302 /* Constants are their own value. */
303 if (is_gimple_min_invariant (expr
) || TREE_CODE (expr
) == FIELD_DECL
)
306 return vn_lookup_with_vuses (expr
, shared_vuses_from_stmt (stmt
));
309 /* Search in VALUE_TABLE for an existing instance of expression EXPR,
310 and return its value, or NULL if none has been set. VUSES is the
311 list of virtual use operands associated with EXPR. It is used when
312 computing the hash value for EXPR. */
315 vn_lookup_with_vuses (tree expr
, VEC (tree
, gc
) *vuses
)
317 if (!vuses
|| !VEC_length (tree
, vuses
))
318 return vn_lookup (expr
);
320 if (is_gimple_min_invariant (expr
) || TREE_CODE (expr
) == FIELD_DECL
)
323 /* We may not walk the use-def chains here as the alias oracle cannot
324 properly deal with VALUE_HANDLE tree nodes we feed it here. */
325 return vn_reference_lookup (expr
, vuses
, false);
329 create_value_handle_for_expr (tree expr
, VEC(tree
, gc
) *vuses
)
333 v
= make_value_handle (TREE_TYPE (expr
));
335 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
336 print_creation_to_file (v
, expr
, vuses
);
340 /* Like vn_lookup, but creates a new value for the operation if one
344 vn_lookup_or_add (tree expr
)
346 tree v
= vn_lookup (expr
);
350 v
= create_value_handle_for_expr (expr
, NULL
);
354 set_value_handle (expr
, v
);
359 /* Like vn_lookup, but handles reference operations as well by using
360 STMT to get the set of vuses. */
363 vn_lookup_or_add_with_stmt (tree expr
, tree stmt
)
367 return vn_lookup_or_add (expr
);
369 v
= vn_lookup_with_stmt (expr
, stmt
);
372 VEC (tree
, gc
) *vuses
= copy_vuses_from_stmt (stmt
);
373 v
= create_value_handle_for_expr (expr
, vuses
);
374 vn_add_with_vuses (expr
, v
, vuses
);
377 set_value_handle (expr
, v
);
382 /* Like vn_lookup, but creates a new value for expression EXPR, if
383 EXPR doesn't already have a value. Return the existing/created
384 value for EXPR. STMT represents the stmt associated with EXPR. It is used
385 when computing the hash value for EXPR. */
388 vn_lookup_or_add_with_vuses (tree expr
, VEC (tree
, gc
) *vuses
)
392 if (!vuses
|| VEC_length (tree
, vuses
) == 0)
393 return vn_lookup_or_add (expr
);
395 v
= vn_lookup_with_vuses (expr
, vuses
);
398 v
= create_value_handle_for_expr (expr
, vuses
);
399 vn_add_with_vuses (expr
, v
, vuses
);
402 set_value_handle (expr
, v
);
This page took 0.056196 seconds and 5 git commands to generate.