]>
Commit | Line | Data |
---|---|---|
4ee9c684 | 1 | /* Data flow functions for trees. |
82eb5a11 | 2 | Copyright (C) 2001, 2002, 2003, 2004, 2005, 2007, 2008, 2009 |
3 | Free Software Foundation, Inc. | |
4ee9c684 | 4 | Contributed by Diego Novillo <dnovillo@redhat.com> |
5 | ||
6 | This file is part of GCC. | |
7 | ||
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 | |
8c4c00c1 | 10 | the Free Software Foundation; either version 3, or (at your option) |
4ee9c684 | 11 | any later version. |
12 | ||
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. | |
17 | ||
18 | You should have received a copy of the GNU General Public License | |
8c4c00c1 | 19 | along with GCC; see the file COPYING3. If not see |
20 | <http://www.gnu.org/licenses/>. */ | |
4ee9c684 | 21 | |
22 | #include "config.h" | |
23 | #include "system.h" | |
24 | #include "coretypes.h" | |
25 | #include "tm.h" | |
26 | #include "hashtab.h" | |
c6224531 | 27 | #include "pointer-set.h" |
4ee9c684 | 28 | #include "tree.h" |
29 | #include "rtl.h" | |
30 | #include "tm_p.h" | |
31 | #include "hard-reg-set.h" | |
32 | #include "basic-block.h" | |
33 | #include "output.h" | |
4ee9c684 | 34 | #include "timevar.h" |
35 | #include "expr.h" | |
36 | #include "ggc.h" | |
37 | #include "langhooks.h" | |
38 | #include "flags.h" | |
39 | #include "function.h" | |
40 | #include "diagnostic.h" | |
41 | #include "tree-dump.h" | |
75a70cf9 | 42 | #include "gimple.h" |
4ee9c684 | 43 | #include "tree-flow.h" |
44 | #include "tree-inline.h" | |
4ee9c684 | 45 | #include "tree-pass.h" |
46 | #include "convert.h" | |
47 | #include "params.h" | |
acc70efa | 48 | #include "cgraph.h" |
4ee9c684 | 49 | |
50 | /* Build and maintain data flow information for trees. */ | |
51 | ||
52 | /* Counters used to display DFA and SSA statistics. */ | |
53 | struct dfa_stats_d | |
54 | { | |
4ee9c684 | 55 | long num_var_anns; |
56 | long num_defs; | |
57 | long num_uses; | |
58 | long num_phis; | |
59 | long num_phi_args; | |
75a70cf9 | 60 | size_t max_num_phi_args; |
4fb5e5ca | 61 | long num_vdefs; |
4ee9c684 | 62 | long num_vuses; |
63 | }; | |
64 | ||
65 | ||
4ee9c684 | 66 | /* Local functions. */ |
67 | static void collect_dfa_stats (struct dfa_stats_d *); | |
4ee9c684 | 68 | static tree find_vars_r (tree *, int *, void *); |
4ee9c684 | 69 | |
70 | ||
4ee9c684 | 71 | /*--------------------------------------------------------------------------- |
72 | Dataflow analysis (DFA) routines | |
73 | ---------------------------------------------------------------------------*/ | |
74 | /* Find all the variables referenced in the function. This function | |
75 | builds the global arrays REFERENCED_VARS and CALL_CLOBBERED_VARS. | |
76 | ||
77 | Note that this function does not look for statement operands, it simply | |
78 | determines what variables are referenced in the program and detects | |
79 | various attributes for each variable used by alias analysis and the | |
80 | optimizer. */ | |
81 | ||
2a1990e9 | 82 | static unsigned int |
4ee9c684 | 83 | find_referenced_vars (void) |
84 | { | |
4ee9c684 | 85 | basic_block bb; |
75a70cf9 | 86 | gimple_stmt_iterator si; |
4ee9c684 | 87 | |
88 | FOR_EACH_BB (bb) | |
ec415c45 | 89 | { |
75a70cf9 | 90 | for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si)) |
9845d120 | 91 | { |
92 | gimple stmt = gsi_stmt (si); | |
93 | if (is_gimple_debug (stmt)) | |
94 | continue; | |
95 | find_referenced_vars_in (gsi_stmt (si)); | |
96 | } | |
ec415c45 | 97 | |
75a70cf9 | 98 | for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si)) |
8e5b4ed6 | 99 | find_referenced_vars_in (gsi_stmt (si)); |
ec415c45 | 100 | } |
4ee9c684 | 101 | |
2a1990e9 | 102 | return 0; |
4ee9c684 | 103 | } |
104 | ||
20099e35 | 105 | struct gimple_opt_pass pass_referenced_vars = |
4ee9c684 | 106 | { |
20099e35 | 107 | { |
108 | GIMPLE_PASS, | |
0c297edc | 109 | "*referenced_vars", /* name */ |
4ee9c684 | 110 | NULL, /* gate */ |
111 | find_referenced_vars, /* execute */ | |
112 | NULL, /* sub */ | |
113 | NULL, /* next */ | |
114 | 0, /* static_pass_number */ | |
8793e598 | 115 | TV_FIND_REFERENCED_VARS, /* tv_id */ |
4ee9c684 | 116 | PROP_gimple_leh | PROP_cfg, /* properties_required */ |
117 | PROP_referenced_vars, /* properties_provided */ | |
118 | 0, /* properties_destroyed */ | |
ec415c45 | 119 | TODO_dump_func, /* todo_flags_start */ |
120 | TODO_dump_func /* todo_flags_finish */ | |
20099e35 | 121 | } |
4ee9c684 | 122 | }; |
123 | ||
124 | ||
4ee9c684 | 125 | /*--------------------------------------------------------------------------- |
126 | Manage annotations | |
127 | ---------------------------------------------------------------------------*/ | |
128 | /* Create a new annotation for a _DECL node T. */ | |
129 | ||
130 | var_ann_t | |
131 | create_var_ann (tree t) | |
132 | { | |
133 | var_ann_t ann; | |
134 | ||
8c0963c4 | 135 | gcc_assert (t); |
8cee8dc0 | 136 | gcc_assert (TREE_CODE (t) == VAR_DECL |
137 | || TREE_CODE (t) == PARM_DECL | |
138 | || TREE_CODE (t) == RESULT_DECL); | |
4ee9c684 | 139 | |
dd7b9387 | 140 | ann = GGC_CNEW (struct var_ann_d); |
8cee8dc0 | 141 | *DECL_VAR_ANN_PTR (t) = ann; |
4ee9c684 | 142 | |
143 | return ann; | |
144 | } | |
145 | ||
ec415c45 | 146 | /* Renumber all of the gimple stmt uids. */ |
147 | ||
48e1416a | 148 | void |
ec415c45 | 149 | renumber_gimple_stmt_uids (void) |
150 | { | |
151 | basic_block bb; | |
152 | ||
153 | set_gimple_stmt_max_uid (cfun, 0); | |
154 | FOR_ALL_BB (bb) | |
155 | { | |
75a70cf9 | 156 | gimple_stmt_iterator bsi; |
157 | for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi)) | |
ec415c45 | 158 | { |
75a70cf9 | 159 | gimple stmt = gsi_stmt (bsi); |
160 | gimple_set_uid (stmt, inc_gimple_stmt_max_uid (cfun)); | |
ec415c45 | 161 | } |
162 | } | |
163 | } | |
164 | ||
3ee48c5c | 165 | /* Like renumber_gimple_stmt_uids, but only do work on the basic blocks |
166 | in BLOCKS, of which there are N_BLOCKS. Also renumbers PHIs. */ | |
167 | ||
48e1416a | 168 | void |
3ee48c5c | 169 | renumber_gimple_stmt_uids_in_blocks (basic_block *blocks, int n_blocks) |
170 | { | |
171 | int i; | |
172 | ||
173 | set_gimple_stmt_max_uid (cfun, 0); | |
174 | for (i = 0; i < n_blocks; i++) | |
175 | { | |
176 | basic_block bb = blocks[i]; | |
177 | gimple_stmt_iterator bsi; | |
178 | for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi)) | |
179 | { | |
180 | gimple stmt = gsi_stmt (bsi); | |
181 | gimple_set_uid (stmt, inc_gimple_stmt_max_uid (cfun)); | |
182 | } | |
183 | for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi)) | |
184 | { | |
185 | gimple stmt = gsi_stmt (bsi); | |
186 | gimple_set_uid (stmt, inc_gimple_stmt_max_uid (cfun)); | |
187 | } | |
188 | } | |
189 | } | |
190 | ||
ae5a4794 | 191 | /* Build a temporary. Make sure and register it to be renamed. */ |
192 | ||
193 | tree | |
194 | make_rename_temp (tree type, const char *prefix) | |
195 | { | |
196 | tree t = create_tmp_var (type, prefix); | |
6086e5db | 197 | |
8ea8de24 | 198 | if (TREE_CODE (TREE_TYPE (t)) == COMPLEX_TYPE |
199 | || TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE) | |
200 | DECL_GIMPLE_REG_P (t) = 1; | |
6086e5db | 201 | |
2d04fd8d | 202 | if (gimple_referenced_vars (cfun)) |
00f8cbcd | 203 | { |
987392e5 | 204 | add_referenced_var (t); |
88dbf20f | 205 | mark_sym_for_renaming (t); |
00f8cbcd | 206 | } |
88dbf20f | 207 | |
ae5a4794 | 208 | return t; |
209 | } | |
210 | ||
211 | ||
4ee9c684 | 212 | |
213 | /*--------------------------------------------------------------------------- | |
214 | Debugging functions | |
215 | ---------------------------------------------------------------------------*/ | |
216 | /* Dump the list of all the referenced variables in the current function to | |
217 | FILE. */ | |
218 | ||
219 | void | |
220 | dump_referenced_vars (FILE *file) | |
221 | { | |
a55dc2cd | 222 | tree var; |
223 | referenced_var_iterator rvi; | |
48e1416a | 224 | |
c1d73e21 | 225 | fprintf (file, "\nReferenced variables in %s: %u\n\n", |
4ee9c684 | 226 | get_name (current_function_decl), (unsigned) num_referenced_vars); |
48e1416a | 227 | |
a55dc2cd | 228 | FOR_EACH_REFERENCED_VAR (var, rvi) |
4ee9c684 | 229 | { |
4ee9c684 | 230 | fprintf (file, "Variable: "); |
231 | dump_variable (file, var); | |
4ee9c684 | 232 | } |
dd277d48 | 233 | |
234 | fprintf (file, "\n"); | |
4ee9c684 | 235 | } |
236 | ||
237 | ||
238 | /* Dump the list of all the referenced variables to stderr. */ | |
239 | ||
240 | void | |
241 | debug_referenced_vars (void) | |
242 | { | |
243 | dump_referenced_vars (stderr); | |
244 | } | |
245 | ||
246 | ||
247 | /* Dump variable VAR and its may-aliases to FILE. */ | |
248 | ||
249 | void | |
250 | dump_variable (FILE *file, tree var) | |
251 | { | |
252 | var_ann_t ann; | |
c1d73e21 | 253 | |
d793732c | 254 | if (TREE_CODE (var) == SSA_NAME) |
255 | { | |
256 | if (POINTER_TYPE_P (TREE_TYPE (var))) | |
257 | dump_points_to_info_for (file, var); | |
258 | var = SSA_NAME_VAR (var); | |
259 | } | |
4ee9c684 | 260 | |
261 | if (var == NULL_TREE) | |
262 | { | |
263 | fprintf (file, "<nil>"); | |
264 | return; | |
265 | } | |
266 | ||
267 | print_generic_expr (file, var, dump_flags); | |
4ee9c684 | 268 | |
269 | ann = var_ann (var); | |
270 | ||
90db18cd | 271 | fprintf (file, ", UID D.%u", (unsigned) DECL_UID (var)); |
4ee9c684 | 272 | |
c46ca7e9 | 273 | fprintf (file, ", "); |
274 | print_generic_expr (file, TREE_TYPE (var), dump_flags); | |
275 | ||
2ce91ad7 | 276 | if (TREE_ADDRESSABLE (var)) |
277 | fprintf (file, ", is addressable"); | |
48e1416a | 278 | |
2ce91ad7 | 279 | if (is_global_var (var)) |
280 | fprintf (file, ", is global"); | |
4ee9c684 | 281 | |
5a49b0e1 | 282 | if (TREE_THIS_VOLATILE (var)) |
283 | fprintf (file, ", is volatile"); | |
284 | ||
4ee9c684 | 285 | if (is_call_clobbered (var)) |
dd277d48 | 286 | fprintf (file, ", call clobbered"); |
287 | else if (is_call_used (var)) | |
288 | fprintf (file, ", call used"); | |
4ee9c684 | 289 | |
241b2d37 | 290 | if (ann && ann->noalias_state == NO_ALIAS) |
c227f8de | 291 | fprintf (file, ", NO_ALIAS (does not alias other NO_ALIAS symbols)"); |
241b2d37 | 292 | else if (ann && ann->noalias_state == NO_ALIAS_GLOBAL) |
c227f8de | 293 | fprintf (file, ", NO_ALIAS_GLOBAL (does not alias other NO_ALIAS symbols" |
294 | " and global vars)"); | |
241b2d37 | 295 | else if (ann && ann->noalias_state == NO_ALIAS_ANYTHING) |
c227f8de | 296 | fprintf (file, ", NO_ALIAS_ANYTHING (does not alias any other symbols)"); |
297 | ||
241b2d37 | 298 | if (cfun && gimple_default_def (cfun, var)) |
4ee9c684 | 299 | { |
300 | fprintf (file, ", default def: "); | |
2d04fd8d | 301 | print_generic_expr (file, gimple_default_def (cfun, var), dump_flags); |
4ee9c684 | 302 | } |
303 | ||
241b2d37 | 304 | if (DECL_INITIAL (var)) |
305 | { | |
306 | fprintf (file, ", initial: "); | |
307 | print_generic_expr (file, DECL_INITIAL (var), dump_flags); | |
308 | } | |
309 | ||
4ee9c684 | 310 | fprintf (file, "\n"); |
311 | } | |
312 | ||
313 | ||
314 | /* Dump variable VAR and its may-aliases to stderr. */ | |
315 | ||
316 | void | |
317 | debug_variable (tree var) | |
318 | { | |
319 | dump_variable (stderr, var); | |
320 | } | |
321 | ||
322 | ||
4ee9c684 | 323 | /* Dump various DFA statistics to FILE. */ |
324 | ||
325 | void | |
326 | dump_dfa_stats (FILE *file) | |
327 | { | |
328 | struct dfa_stats_d dfa_stats; | |
329 | ||
330 | unsigned long size, total = 0; | |
331 | const char * const fmt_str = "%-30s%-13s%12s\n"; | |
332 | const char * const fmt_str_1 = "%-30s%13lu%11lu%c\n"; | |
333 | const char * const fmt_str_3 = "%-43s%11lu%c\n"; | |
334 | const char *funcname | |
5135beeb | 335 | = lang_hooks.decl_printable_name (current_function_decl, 2); |
4ee9c684 | 336 | |
337 | collect_dfa_stats (&dfa_stats); | |
338 | ||
339 | fprintf (file, "\nDFA Statistics for %s\n\n", funcname); | |
340 | ||
341 | fprintf (file, "---------------------------------------------------------\n"); | |
342 | fprintf (file, fmt_str, "", " Number of ", "Memory"); | |
343 | fprintf (file, fmt_str, "", " instances ", "used "); | |
344 | fprintf (file, "---------------------------------------------------------\n"); | |
345 | ||
346 | size = num_referenced_vars * sizeof (tree); | |
347 | total += size; | |
4f917ffe | 348 | fprintf (file, fmt_str_1, "Referenced variables", (unsigned long)num_referenced_vars, |
4ee9c684 | 349 | SCALE (size), LABEL (size)); |
350 | ||
4ee9c684 | 351 | size = dfa_stats.num_var_anns * sizeof (struct var_ann_d); |
352 | total += size; | |
353 | fprintf (file, fmt_str_1, "Variables annotated", dfa_stats.num_var_anns, | |
354 | SCALE (size), LABEL (size)); | |
355 | ||
356 | size = dfa_stats.num_uses * sizeof (tree *); | |
357 | total += size; | |
358 | fprintf (file, fmt_str_1, "USE operands", dfa_stats.num_uses, | |
359 | SCALE (size), LABEL (size)); | |
360 | ||
361 | size = dfa_stats.num_defs * sizeof (tree *); | |
362 | total += size; | |
363 | fprintf (file, fmt_str_1, "DEF operands", dfa_stats.num_defs, | |
364 | SCALE (size), LABEL (size)); | |
365 | ||
366 | size = dfa_stats.num_vuses * sizeof (tree *); | |
367 | total += size; | |
368 | fprintf (file, fmt_str_1, "VUSE operands", dfa_stats.num_vuses, | |
369 | SCALE (size), LABEL (size)); | |
370 | ||
4fb5e5ca | 371 | size = dfa_stats.num_vdefs * sizeof (tree *); |
2cf24776 | 372 | total += size; |
4fb5e5ca | 373 | fprintf (file, fmt_str_1, "VDEF operands", dfa_stats.num_vdefs, |
4ee9c684 | 374 | SCALE (size), LABEL (size)); |
375 | ||
75a70cf9 | 376 | size = dfa_stats.num_phis * sizeof (struct gimple_statement_phi); |
4ee9c684 | 377 | total += size; |
378 | fprintf (file, fmt_str_1, "PHI nodes", dfa_stats.num_phis, | |
379 | SCALE (size), LABEL (size)); | |
380 | ||
381 | size = dfa_stats.num_phi_args * sizeof (struct phi_arg_d); | |
382 | total += size; | |
383 | fprintf (file, fmt_str_1, "PHI arguments", dfa_stats.num_phi_args, | |
384 | SCALE (size), LABEL (size)); | |
385 | ||
386 | fprintf (file, "---------------------------------------------------------\n"); | |
387 | fprintf (file, fmt_str_3, "Total memory used by DFA/SSA data", SCALE (total), | |
388 | LABEL (total)); | |
389 | fprintf (file, "---------------------------------------------------------\n"); | |
390 | fprintf (file, "\n"); | |
391 | ||
392 | if (dfa_stats.num_phis) | |
75a70cf9 | 393 | fprintf (file, "Average number of arguments per PHI node: %.1f (max: %ld)\n", |
4ee9c684 | 394 | (float) dfa_stats.num_phi_args / (float) dfa_stats.num_phis, |
75a70cf9 | 395 | (long) dfa_stats.max_num_phi_args); |
4ee9c684 | 396 | |
397 | fprintf (file, "\n"); | |
398 | } | |
399 | ||
400 | ||
401 | /* Dump DFA statistics on stderr. */ | |
402 | ||
403 | void | |
404 | debug_dfa_stats (void) | |
405 | { | |
406 | dump_dfa_stats (stderr); | |
407 | } | |
408 | ||
409 | ||
5206b159 | 410 | /* Collect DFA statistics and store them in the structure pointed to by |
4ee9c684 | 411 | DFA_STATS_P. */ |
412 | ||
413 | static void | |
75a70cf9 | 414 | collect_dfa_stats (struct dfa_stats_d *dfa_stats_p ATTRIBUTE_UNUSED) |
4ee9c684 | 415 | { |
4ee9c684 | 416 | basic_block bb; |
75a70cf9 | 417 | referenced_var_iterator vi; |
418 | tree var; | |
4ee9c684 | 419 | |
8c0963c4 | 420 | gcc_assert (dfa_stats_p); |
4ee9c684 | 421 | |
422 | memset ((void *)dfa_stats_p, 0, sizeof (struct dfa_stats_d)); | |
423 | ||
75a70cf9 | 424 | /* Count all the variable annotations. */ |
425 | FOR_EACH_REFERENCED_VAR (var, vi) | |
426 | if (var_ann (var)) | |
427 | dfa_stats_p->num_var_anns++; | |
4ee9c684 | 428 | |
75a70cf9 | 429 | /* Walk all the statements in the function counting references. */ |
4ee9c684 | 430 | FOR_EACH_BB (bb) |
431 | { | |
75a70cf9 | 432 | gimple_stmt_iterator si; |
433 | ||
434 | for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si)) | |
4ee9c684 | 435 | { |
75a70cf9 | 436 | gimple phi = gsi_stmt (si); |
4ee9c684 | 437 | dfa_stats_p->num_phis++; |
75a70cf9 | 438 | dfa_stats_p->num_phi_args += gimple_phi_num_args (phi); |
439 | if (gimple_phi_num_args (phi) > dfa_stats_p->max_num_phi_args) | |
440 | dfa_stats_p->max_num_phi_args = gimple_phi_num_args (phi); | |
4ee9c684 | 441 | } |
4ee9c684 | 442 | |
75a70cf9 | 443 | for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si)) |
4ee9c684 | 444 | { |
75a70cf9 | 445 | gimple stmt = gsi_stmt (si); |
446 | dfa_stats_p->num_defs += NUM_SSA_OPERANDS (stmt, SSA_OP_DEF); | |
447 | dfa_stats_p->num_uses += NUM_SSA_OPERANDS (stmt, SSA_OP_USE); | |
dd277d48 | 448 | dfa_stats_p->num_vdefs += gimple_vdef (stmt) ? 1 : 0; |
449 | dfa_stats_p->num_vuses += gimple_vuse (stmt) ? 1 : 0; | |
4ee9c684 | 450 | } |
451 | } | |
4ee9c684 | 452 | } |
453 | ||
454 | ||
455 | /*--------------------------------------------------------------------------- | |
456 | Miscellaneous helpers | |
457 | ---------------------------------------------------------------------------*/ | |
458 | /* Callback for walk_tree. Used to collect variables referenced in | |
459 | the function. */ | |
460 | ||
461 | static tree | |
987392e5 | 462 | find_vars_r (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED) |
4ee9c684 | 463 | { |
ec415c45 | 464 | /* If we are reading the lto info back in, we need to rescan the |
465 | referenced vars. */ | |
466 | if (TREE_CODE (*tp) == SSA_NAME) | |
467 | add_referenced_var (SSA_NAME_VAR (*tp)); | |
468 | ||
5ff0afa2 | 469 | /* If T is a regular variable that the optimizers are interested |
470 | in, add it to the list of variables. */ | |
ec415c45 | 471 | else if (SSA_VAR_P (*tp)) |
987392e5 | 472 | add_referenced_var (*tp); |
5ff0afa2 | 473 | |
474 | /* Type, _DECL and constant nodes have no interesting children. | |
475 | Ignore them. */ | |
ce45a448 | 476 | else if (IS_TYPE_OR_DECL_P (*tp) || CONSTANT_CLASS_P (*tp)) |
5ff0afa2 | 477 | *walk_subtrees = 0; |
4ee9c684 | 478 | |
479 | return NULL_TREE; | |
480 | } | |
481 | ||
8e5b4ed6 | 482 | /* Find referenced variables in STMT. In contrast with |
483 | find_new_referenced_vars, this function will not mark newly found | |
484 | variables for renaming. */ | |
485 | ||
486 | void | |
487 | find_referenced_vars_in (gimple stmt) | |
488 | { | |
489 | size_t i; | |
490 | ||
491 | if (gimple_code (stmt) != GIMPLE_PHI) | |
492 | { | |
493 | for (i = 0; i < gimple_num_ops (stmt); i++) | |
494 | walk_tree (gimple_op_ptr (stmt, i), find_vars_r, NULL, NULL); | |
495 | } | |
496 | else | |
497 | { | |
498 | walk_tree (gimple_phi_result_ptr (stmt), find_vars_r, NULL, NULL); | |
499 | ||
500 | for (i = 0; i < gimple_phi_num_args (stmt); i++) | |
501 | { | |
502 | tree arg = gimple_phi_arg_def (stmt, i); | |
503 | walk_tree (&arg, find_vars_r, NULL, NULL); | |
504 | } | |
505 | } | |
506 | } | |
507 | ||
508 | ||
a55dc2cd | 509 | /* Lookup UID in the referenced_vars hashtable and return the associated |
510 | variable. */ | |
511 | ||
48e1416a | 512 | tree |
a55dc2cd | 513 | referenced_var_lookup (unsigned int uid) |
514 | { | |
c0ff55b3 | 515 | tree h; |
516 | struct tree_decl_minimal in; | |
517 | in.uid = uid; | |
518 | h = (tree) htab_find_with_hash (gimple_referenced_vars (cfun), &in, uid); | |
519 | gcc_assert (h || uid == 0); | |
520 | return h; | |
a55dc2cd | 521 | } |
522 | ||
48e1416a | 523 | /* Check if TO is in the referenced_vars hash table and insert it if not. |
d328c4ab | 524 | Return true if it required insertion. */ |
a55dc2cd | 525 | |
91fbe448 | 526 | bool |
d328c4ab | 527 | referenced_var_check_and_insert (tree to) |
48e1416a | 528 | { |
c0ff55b3 | 529 | tree h, *loc; |
530 | struct tree_decl_minimal in; | |
d328c4ab | 531 | unsigned int uid = DECL_UID (to); |
532 | ||
c0ff55b3 | 533 | in.uid = uid; |
534 | h = (tree) htab_find_with_hash (gimple_referenced_vars (cfun), &in, uid); | |
535 | if (h) | |
536 | { | |
537 | /* DECL_UID has already been entered in the table. Verify that it is | |
538 | the same entry as TO. See PR 27793. */ | |
539 | gcc_assert (h == to); | |
540 | return false; | |
541 | } | |
a55dc2cd | 542 | |
c0ff55b3 | 543 | loc = (tree *) htab_find_slot_with_hash (gimple_referenced_vars (cfun), |
544 | &in, uid, INSERT); | |
545 | *loc = to; | |
d328c4ab | 546 | return true; |
a55dc2cd | 547 | } |
548 | ||
f7553d0a | 549 | /* Lookup VAR UID in the default_defs hashtable and return the associated |
550 | variable. */ | |
551 | ||
48e1416a | 552 | tree |
2d04fd8d | 553 | gimple_default_def (struct function *fn, tree var) |
f7553d0a | 554 | { |
24239da3 | 555 | struct tree_decl_minimal ind; |
556 | struct tree_ssa_name in; | |
f7553d0a | 557 | gcc_assert (SSA_VAR_P (var)); |
24239da3 | 558 | in.var = (tree)&ind; |
559 | ind.uid = DECL_UID (var); | |
560 | return (tree) htab_find_with_hash (DEFAULT_DEFS (fn), &in, DECL_UID (var)); | |
f7553d0a | 561 | } |
562 | ||
563 | /* Insert the pair VAR's UID, DEF into the default_defs hashtable. */ | |
564 | ||
565 | void | |
566 | set_default_def (tree var, tree def) | |
48e1416a | 567 | { |
24239da3 | 568 | struct tree_decl_minimal ind; |
569 | struct tree_ssa_name in; | |
f7553d0a | 570 | void **loc; |
571 | ||
572 | gcc_assert (SSA_VAR_P (var)); | |
24239da3 | 573 | in.var = (tree)&ind; |
574 | ind.uid = DECL_UID (var); | |
575 | if (!def) | |
f7553d0a | 576 | { |
2d04fd8d | 577 | loc = htab_find_slot_with_hash (DEFAULT_DEFS (cfun), &in, |
578 | DECL_UID (var), INSERT); | |
24239da3 | 579 | gcc_assert (*loc); |
2d04fd8d | 580 | htab_remove_elt (DEFAULT_DEFS (cfun), *loc); |
f7553d0a | 581 | return; |
582 | } | |
24239da3 | 583 | gcc_assert (TREE_CODE (def) == SSA_NAME && SSA_NAME_VAR (def) == var); |
2d04fd8d | 584 | loc = htab_find_slot_with_hash (DEFAULT_DEFS (cfun), &in, |
585 | DECL_UID (var), INSERT); | |
4fb5e5ca | 586 | |
f7553d0a | 587 | /* Default definition might be changed by tail call optimization. */ |
24239da3 | 588 | if (*loc) |
589 | SSA_NAME_IS_DEFAULT_DEF (*(tree *) loc) = false; | |
590 | *(tree *) loc = def; | |
de6ed584 | 591 | |
592 | /* Mark DEF as the default definition for VAR. */ | |
593 | SSA_NAME_IS_DEFAULT_DEF (def) = true; | |
f7553d0a | 594 | } |
595 | ||
987392e5 | 596 | /* Add VAR to the list of referenced variables if it isn't already there. */ |
4ee9c684 | 597 | |
82eb5a11 | 598 | bool |
987392e5 | 599 | add_referenced_var (tree var) |
4ee9c684 | 600 | { |
4ee9c684 | 601 | var_ann_t v_ann; |
602 | ||
603 | v_ann = get_var_ann (var); | |
987392e5 | 604 | gcc_assert (DECL_P (var)); |
48e1416a | 605 | |
d328c4ab | 606 | /* Insert VAR into the referenced_vars has table if it isn't present. */ |
607 | if (referenced_var_check_and_insert (var)) | |
4ee9c684 | 608 | { |
0e3632e5 | 609 | /* Scan DECL_INITIAL for pointer variables as they may contain |
610 | address arithmetic referencing the address of other | |
3a44a278 | 611 | variables. As we are only interested in directly referenced |
612 | globals or referenced locals restrict this to initializers | |
613 | than can refer to local variables. */ | |
b93ca75c | 614 | if (DECL_INITIAL (var) |
3a44a278 | 615 | && DECL_CONTEXT (var) == current_function_decl) |
987392e5 | 616 | walk_tree (&DECL_INITIAL (var), find_vars_r, NULL, 0); |
82eb5a11 | 617 | |
618 | return true; | |
4ee9c684 | 619 | } |
82eb5a11 | 620 | |
621 | return false; | |
4ee9c684 | 622 | } |
623 | ||
fe15b701 | 624 | /* Remove VAR from the list. */ |
625 | ||
626 | void | |
627 | remove_referenced_var (tree var) | |
628 | { | |
629 | var_ann_t v_ann; | |
c0ff55b3 | 630 | struct tree_decl_minimal in; |
631 | void **loc; | |
fe15b701 | 632 | unsigned int uid = DECL_UID (var); |
633 | ||
dd277d48 | 634 | /* Preserve var_anns of globals. */ |
635 | if (!is_global_var (var) | |
636 | && (v_ann = var_ann (var))) | |
dd7b9387 | 637 | { |
dd277d48 | 638 | ggc_free (v_ann); |
8cee8dc0 | 639 | *DECL_VAR_ANN_PTR (var) = NULL; |
dd7b9387 | 640 | } |
fe15b701 | 641 | gcc_assert (DECL_P (var)); |
c0ff55b3 | 642 | in.uid = uid; |
643 | loc = htab_find_slot_with_hash (gimple_referenced_vars (cfun), &in, uid, | |
644 | NO_INSERT); | |
645 | htab_clear_slot (gimple_referenced_vars (cfun), loc); | |
fe15b701 | 646 | } |
647 | ||
4ee9c684 | 648 | |
649 | /* Return the virtual variable associated to the non-scalar variable VAR. */ | |
650 | ||
651 | tree | |
652 | get_virtual_var (tree var) | |
653 | { | |
4ee9c684 | 654 | STRIP_NOPS (var); |
655 | ||
656 | if (TREE_CODE (var) == SSA_NAME) | |
657 | var = SSA_NAME_VAR (var); | |
658 | ||
5f4cbfb8 | 659 | while (TREE_CODE (var) == REALPART_EXPR || TREE_CODE (var) == IMAGPART_EXPR |
660 | || handled_component_p (var)) | |
6374121b | 661 | var = TREE_OPERAND (var, 0); |
c1d73e21 | 662 | |
4ee9c684 | 663 | /* Treating GIMPLE registers as virtual variables makes no sense. |
664 | Also complain if we couldn't extract a _DECL out of the original | |
665 | expression. */ | |
8c0963c4 | 666 | gcc_assert (SSA_VAR_P (var)); |
667 | gcc_assert (!is_gimple_reg (var)); | |
4ee9c684 | 668 | |
669 | return var; | |
670 | } | |
671 | ||
4c5fd53c | 672 | /* Mark all the naked symbols in STMT for SSA renaming. */ |
4ee9c684 | 673 | |
674 | void | |
75a70cf9 | 675 | mark_symbols_for_renaming (gimple stmt) |
4ee9c684 | 676 | { |
de6ed584 | 677 | tree op; |
43daa21e | 678 | ssa_op_iter iter; |
4ee9c684 | 679 | |
22aa74c4 | 680 | update_stmt (stmt); |
4ee9c684 | 681 | |
de6ed584 | 682 | /* Mark all the operands for renaming. */ |
683 | FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_OPERANDS) | |
684 | if (DECL_P (op)) | |
685 | mark_sym_for_renaming (op); | |
4ee9c684 | 686 | } |
909e5ecb | 687 | |
de6ed584 | 688 | |
75a70cf9 | 689 | /* Find all variables within the gimplified statement that were not |
690 | previously visible to the function and add them to the referenced | |
691 | variables list. */ | |
909e5ecb | 692 | |
693 | static tree | |
694 | find_new_referenced_vars_1 (tree *tp, int *walk_subtrees, | |
695 | void *data ATTRIBUTE_UNUSED) | |
696 | { | |
697 | tree t = *tp; | |
698 | ||
699 | if (TREE_CODE (t) == VAR_DECL && !var_ann (t)) | |
88dbf20f | 700 | { |
987392e5 | 701 | add_referenced_var (t); |
88dbf20f | 702 | mark_sym_for_renaming (t); |
703 | } | |
909e5ecb | 704 | |
705 | if (IS_TYPE_OR_DECL_P (t)) | |
706 | *walk_subtrees = 0; | |
707 | ||
708 | return NULL; | |
709 | } | |
710 | ||
75a70cf9 | 711 | |
712 | /* Find any new referenced variables in STMT. */ | |
713 | ||
909e5ecb | 714 | void |
75a70cf9 | 715 | find_new_referenced_vars (gimple stmt) |
909e5ecb | 716 | { |
75a70cf9 | 717 | walk_gimple_op (stmt, find_new_referenced_vars_1, NULL); |
909e5ecb | 718 | } |
6cf80e5b | 719 | |
720 | ||
de6ed584 | 721 | /* If EXP is a handled component reference for a structure, return the |
3fefae7a | 722 | base variable. The access range is delimited by bit positions *POFFSET and |
723 | *POFFSET + *PMAX_SIZE. The access size is *PSIZE bits. If either | |
724 | *PSIZE or *PMAX_SIZE is -1, they could not be determined. If *PSIZE | |
725 | and *PMAX_SIZE are equal, the access is non-variable. */ | |
2be14d8b | 726 | |
727 | tree | |
3fefae7a | 728 | get_ref_base_and_extent (tree exp, HOST_WIDE_INT *poffset, |
729 | HOST_WIDE_INT *psize, | |
730 | HOST_WIDE_INT *pmax_size) | |
2be14d8b | 731 | { |
3fefae7a | 732 | HOST_WIDE_INT bitsize = -1; |
733 | HOST_WIDE_INT maxsize = -1; | |
734 | tree size_tree = NULL_TREE; | |
209f25b9 | 735 | HOST_WIDE_INT bit_offset = 0; |
c7f5d117 | 736 | bool seen_variable_array_ref = false; |
3fefae7a | 737 | |
3fefae7a | 738 | /* First get the final access size from just the outermost expression. */ |
739 | if (TREE_CODE (exp) == COMPONENT_REF) | |
740 | size_tree = DECL_SIZE (TREE_OPERAND (exp, 1)); | |
741 | else if (TREE_CODE (exp) == BIT_FIELD_REF) | |
742 | size_tree = TREE_OPERAND (exp, 1); | |
3a443843 | 743 | else if (!VOID_TYPE_P (TREE_TYPE (exp))) |
2be14d8b | 744 | { |
3fefae7a | 745 | enum machine_mode mode = TYPE_MODE (TREE_TYPE (exp)); |
746 | if (mode == BLKmode) | |
747 | size_tree = TYPE_SIZE (TREE_TYPE (exp)); | |
748 | else | |
749 | bitsize = GET_MODE_BITSIZE (mode); | |
2be14d8b | 750 | } |
3fefae7a | 751 | if (size_tree != NULL_TREE) |
2be14d8b | 752 | { |
3fefae7a | 753 | if (! host_integerp (size_tree, 1)) |
754 | bitsize = -1; | |
755 | else | |
756 | bitsize = TREE_INT_CST_LOW (size_tree); | |
2be14d8b | 757 | } |
3fefae7a | 758 | |
759 | /* Initially, maxsize is the same as the accessed element size. | |
760 | In the following it will only grow (or become -1). */ | |
761 | maxsize = bitsize; | |
762 | ||
763 | /* Compute cumulative bit-offset for nested component-refs and array-refs, | |
764 | and find the ultimate containing object. */ | |
765 | while (1) | |
766 | { | |
767 | switch (TREE_CODE (exp)) | |
768 | { | |
769 | case BIT_FIELD_REF: | |
2adb8813 | 770 | bit_offset += TREE_INT_CST_LOW (TREE_OPERAND (exp, 2)); |
3fefae7a | 771 | break; |
772 | ||
773 | case COMPONENT_REF: | |
774 | { | |
775 | tree field = TREE_OPERAND (exp, 1); | |
776 | tree this_offset = component_ref_field_offset (exp); | |
777 | ||
2adb8813 | 778 | if (this_offset |
779 | && TREE_CODE (this_offset) == INTEGER_CST | |
780 | && host_integerp (this_offset, 0)) | |
3fefae7a | 781 | { |
2adb8813 | 782 | HOST_WIDE_INT hthis_offset = TREE_INT_CST_LOW (this_offset); |
209f25b9 | 783 | hthis_offset *= BITS_PER_UNIT; |
65366b4f | 784 | hthis_offset |
785 | += TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (field)); | |
209f25b9 | 786 | bit_offset += hthis_offset; |
65366b4f | 787 | |
788 | /* If we had seen a variable array ref already and we just | |
789 | referenced the last field of a struct or a union member | |
790 | then we have to adjust maxsize by the padding at the end | |
791 | of our field. */ | |
792 | if (seen_variable_array_ref | |
793 | && maxsize != -1) | |
794 | { | |
795 | tree stype = TREE_TYPE (TREE_OPERAND (exp, 0)); | |
796 | tree next = TREE_CHAIN (field); | |
797 | while (next && TREE_CODE (next) != FIELD_DECL) | |
798 | next = TREE_CHAIN (next); | |
799 | if (!next | |
800 | || TREE_CODE (stype) != RECORD_TYPE) | |
801 | { | |
802 | tree fsize = DECL_SIZE_UNIT (field); | |
803 | tree ssize = TYPE_SIZE_UNIT (stype); | |
804 | if (host_integerp (fsize, 0) | |
805 | && host_integerp (ssize, 0)) | |
806 | maxsize += ((TREE_INT_CST_LOW (ssize) | |
807 | - TREE_INT_CST_LOW (fsize)) | |
808 | * BITS_PER_UNIT - hthis_offset); | |
809 | else | |
810 | maxsize = -1; | |
811 | } | |
812 | } | |
3fefae7a | 813 | } |
814 | else | |
815 | { | |
816 | tree csize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0))); | |
817 | /* We need to adjust maxsize to the whole structure bitsize. | |
f0b5f617 | 818 | But we can subtract any constant offset seen so far, |
3fefae7a | 819 | because that would get us out of the structure otherwise. */ |
74aab153 | 820 | if (maxsize != -1 && csize && host_integerp (csize, 1)) |
821 | maxsize = TREE_INT_CST_LOW (csize) - bit_offset; | |
3fefae7a | 822 | else |
823 | maxsize = -1; | |
824 | } | |
825 | } | |
826 | break; | |
827 | ||
828 | case ARRAY_REF: | |
829 | case ARRAY_RANGE_REF: | |
830 | { | |
831 | tree index = TREE_OPERAND (exp, 1); | |
2adb8813 | 832 | tree low_bound, unit_size; |
3fefae7a | 833 | |
209f25b9 | 834 | /* If the resulting bit-offset is constant, track it. */ |
2adb8813 | 835 | if (TREE_CODE (index) == INTEGER_CST |
836 | && host_integerp (index, 0) | |
837 | && (low_bound = array_ref_low_bound (exp), | |
838 | host_integerp (low_bound, 0)) | |
839 | && (unit_size = array_ref_element_size (exp), | |
840 | host_integerp (unit_size, 1))) | |
3fefae7a | 841 | { |
2adb8813 | 842 | HOST_WIDE_INT hindex = TREE_INT_CST_LOW (index); |
209f25b9 | 843 | |
2adb8813 | 844 | hindex -= TREE_INT_CST_LOW (low_bound); |
845 | hindex *= TREE_INT_CST_LOW (unit_size); | |
209f25b9 | 846 | hindex *= BITS_PER_UNIT; |
847 | bit_offset += hindex; | |
c7f5d117 | 848 | |
849 | /* An array ref with a constant index up in the structure | |
850 | hierarchy will constrain the size of any variable array ref | |
851 | lower in the access hierarchy. */ | |
852 | seen_variable_array_ref = false; | |
3fefae7a | 853 | } |
854 | else | |
855 | { | |
856 | tree asize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0))); | |
857 | /* We need to adjust maxsize to the whole array bitsize. | |
f0b5f617 | 858 | But we can subtract any constant offset seen so far, |
3fefae7a | 859 | because that would get us outside of the array otherwise. */ |
74aab153 | 860 | if (maxsize != -1 && asize && host_integerp (asize, 1)) |
861 | maxsize = TREE_INT_CST_LOW (asize) - bit_offset; | |
3fefae7a | 862 | else |
863 | maxsize = -1; | |
c7f5d117 | 864 | |
865 | /* Remember that we have seen an array ref with a variable | |
866 | index. */ | |
867 | seen_variable_array_ref = true; | |
3fefae7a | 868 | } |
869 | } | |
870 | break; | |
871 | ||
872 | case REALPART_EXPR: | |
873 | break; | |
874 | ||
875 | case IMAGPART_EXPR: | |
209f25b9 | 876 | bit_offset += bitsize; |
3fefae7a | 877 | break; |
878 | ||
879 | case VIEW_CONVERT_EXPR: | |
3fefae7a | 880 | break; |
881 | ||
882 | default: | |
883 | goto done; | |
884 | } | |
885 | ||
886 | exp = TREE_OPERAND (exp, 0); | |
887 | } | |
888 | done: | |
889 | ||
c7f5d117 | 890 | /* We need to deal with variable arrays ending structures such as |
891 | struct { int length; int a[1]; } x; x.a[d] | |
892 | struct { struct { int a; int b; } a[1]; } x; x.a[d].a | |
893 | struct { struct { int a[1]; } a[1]; } x; x.a[0][d], x.a[d][0] | |
afff7257 | 894 | struct { int len; union { int a[1]; struct X x; } u; } x; x.u.a[d] |
c7f5d117 | 895 | where we do not know maxsize for variable index accesses to |
896 | the array. The simplest way to conservatively deal with this | |
897 | is to punt in the case that offset + maxsize reaches the | |
afff7257 | 898 | base type boundary. This needs to include possible trailing padding |
664e30ce | 899 | that is there for alignment purposes. |
ba3a7ba0 | 900 | |
664e30ce | 901 | That is of course only true if the base object is not a decl. */ |
902 | ||
903 | if (DECL_P (exp)) | |
904 | { | |
905 | /* If maxsize is unknown adjust it according to the size of the | |
906 | base decl. */ | |
907 | if (maxsize == -1 | |
908 | && host_integerp (DECL_SIZE (exp), 1)) | |
909 | maxsize = TREE_INT_CST_LOW (DECL_SIZE (exp)) - bit_offset; | |
910 | } | |
911 | else if (seen_variable_array_ref | |
912 | && maxsize != -1 | |
913 | && (!host_integerp (TYPE_SIZE (TREE_TYPE (exp)), 1) | |
914 | || (bit_offset + maxsize | |
915 | == (signed) TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (exp)))))) | |
c7f5d117 | 916 | maxsize = -1; |
917 | ||
3fefae7a | 918 | /* ??? Due to negative offsets in ARRAY_REF we can end up with |
919 | negative bit_offset here. We might want to store a zero offset | |
920 | in this case. */ | |
209f25b9 | 921 | *poffset = bit_offset; |
3fefae7a | 922 | *psize = bitsize; |
923 | *pmax_size = maxsize; | |
924 | ||
925 | return exp; | |
2be14d8b | 926 | } |
c227f8de | 927 | |
b75537fb | 928 | /* Returns true if STMT references an SSA_NAME that has |
929 | SSA_NAME_OCCURS_IN_ABNORMAL_PHI set, otherwise false. */ | |
930 | ||
931 | bool | |
75a70cf9 | 932 | stmt_references_abnormal_ssa_name (gimple stmt) |
b75537fb | 933 | { |
934 | ssa_op_iter oi; | |
935 | use_operand_p use_p; | |
936 | ||
937 | FOR_EACH_SSA_USE_OPERAND (use_p, stmt, oi, SSA_OP_USE) | |
938 | { | |
939 | if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (use_p))) | |
940 | return true; | |
941 | } | |
942 | ||
943 | return false; | |
944 | } | |
945 |