]>
Commit | Line | Data |
---|---|---|
6de9cd9a | 1 | /* Data flow functions for trees. |
65401a0b JJ |
2 | Copyright (C) 2001, 2002, 2003, 2004, 2005, 2007, 2008, 2009 |
3 | Free Software Foundation, Inc. | |
6de9cd9a DN |
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 | |
9dcd6f09 | 10 | the Free Software Foundation; either version 3, or (at your option) |
6de9cd9a DN |
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 | |
9dcd6f09 NC |
19 | along with GCC; see the file COPYING3. If not see |
20 | <http://www.gnu.org/licenses/>. */ | |
6de9cd9a DN |
21 | |
22 | #include "config.h" | |
23 | #include "system.h" | |
24 | #include "coretypes.h" | |
25 | #include "tm.h" | |
26 | #include "hashtab.h" | |
0c58f841 | 27 | #include "pointer-set.h" |
6de9cd9a DN |
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" | |
6de9cd9a DN |
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" | |
726a989a | 42 | #include "gimple.h" |
6de9cd9a DN |
43 | #include "tree-flow.h" |
44 | #include "tree-inline.h" | |
6de9cd9a DN |
45 | #include "tree-pass.h" |
46 | #include "convert.h" | |
47 | #include "params.h" | |
6674a6ce | 48 | #include "cgraph.h" |
6de9cd9a DN |
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 | { | |
6de9cd9a DN |
55 | long num_var_anns; |
56 | long num_defs; | |
57 | long num_uses; | |
58 | long num_phis; | |
59 | long num_phi_args; | |
726a989a | 60 | size_t max_num_phi_args; |
38635499 | 61 | long num_vdefs; |
6de9cd9a DN |
62 | long num_vuses; |
63 | }; | |
64 | ||
65 | ||
6de9cd9a DN |
66 | /* Local functions. */ |
67 | static void collect_dfa_stats (struct dfa_stats_d *); | |
6de9cd9a | 68 | static tree find_vars_r (tree *, int *, void *); |
6de9cd9a DN |
69 | |
70 | ||
6de9cd9a DN |
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 | ||
c2924966 | 82 | static unsigned int |
6de9cd9a DN |
83 | find_referenced_vars (void) |
84 | { | |
6de9cd9a | 85 | basic_block bb; |
726a989a | 86 | gimple_stmt_iterator si; |
6de9cd9a DN |
87 | |
88 | FOR_EACH_BB (bb) | |
908ff6a3 | 89 | { |
726a989a | 90 | for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si)) |
b5b8b0ac AO |
91 | { |
92 | gimple stmt = gsi_stmt (si); | |
93 | if (is_gimple_debug (stmt)) | |
94 | continue; | |
95 | find_referenced_vars_in (gsi_stmt (si)); | |
96 | } | |
908ff6a3 | 97 | |
726a989a | 98 | for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si)) |
07485407 | 99 | find_referenced_vars_in (gsi_stmt (si)); |
908ff6a3 | 100 | } |
6de9cd9a | 101 | |
c2924966 | 102 | return 0; |
6de9cd9a DN |
103 | } |
104 | ||
8ddbbcae | 105 | struct gimple_opt_pass pass_referenced_vars = |
6de9cd9a | 106 | { |
8ddbbcae JH |
107 | { |
108 | GIMPLE_PASS, | |
6de9cd9a DN |
109 | NULL, /* name */ |
110 | NULL, /* gate */ | |
111 | find_referenced_vars, /* execute */ | |
112 | NULL, /* sub */ | |
113 | NULL, /* next */ | |
114 | 0, /* static_pass_number */ | |
30a80709 | 115 | TV_FIND_REFERENCED_VARS, /* tv_id */ |
6de9cd9a DN |
116 | PROP_gimple_leh | PROP_cfg, /* properties_required */ |
117 | PROP_referenced_vars, /* properties_provided */ | |
118 | 0, /* properties_destroyed */ | |
908ff6a3 KZ |
119 | TODO_dump_func, /* todo_flags_start */ |
120 | TODO_dump_func /* todo_flags_finish */ | |
8ddbbcae | 121 | } |
6de9cd9a DN |
122 | }; |
123 | ||
124 | ||
6de9cd9a DN |
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 | ||
1e128c5f GB |
135 | gcc_assert (t); |
136 | gcc_assert (DECL_P (t)); | |
07beea0d | 137 | gcc_assert (!t->base.ann || t->base.ann->common.type == VAR_ANN); |
6de9cd9a | 138 | |
540f6bda | 139 | ann = GGC_CNEW (struct var_ann_d); |
6de9cd9a | 140 | ann->common.type = VAR_ANN; |
540f6bda | 141 | t->base.ann = (tree_ann_t) ann; |
6de9cd9a DN |
142 | |
143 | return ann; | |
144 | } | |
145 | ||
908ff6a3 KZ |
146 | /* Renumber all of the gimple stmt uids. */ |
147 | ||
148 | void | |
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 | { | |
726a989a RB |
156 | gimple_stmt_iterator bsi; |
157 | for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi)) | |
908ff6a3 | 158 | { |
726a989a RB |
159 | gimple stmt = gsi_stmt (bsi); |
160 | gimple_set_uid (stmt, inc_gimple_stmt_max_uid (cfun)); | |
908ff6a3 KZ |
161 | } |
162 | } | |
163 | } | |
164 | ||
2c08497a BS |
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 | ||
168 | void | |
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 | ||
06d72ee6 | 191 | /* Create a new annotation for a tree T. */ |
7e6eb623 | 192 | |
93c094b5 JH |
193 | tree_ann_common_t |
194 | create_tree_common_ann (tree t) | |
7e6eb623 | 195 | { |
93c094b5 | 196 | tree_ann_common_t ann; |
7e6eb623 | 197 | |
1e128c5f | 198 | gcc_assert (t); |
07beea0d | 199 | gcc_assert (!t->base.ann || t->base.ann->common.type == TREE_ANN_COMMON); |
7e6eb623 | 200 | |
93c094b5 | 201 | ann = GGC_CNEW (struct tree_ann_common_d); |
7e6eb623 | 202 | |
93c094b5 | 203 | ann->type = TREE_ANN_COMMON; |
726a989a | 204 | ann->rn = -1; |
07beea0d | 205 | t->base.ann = (tree_ann_t) ann; |
7e6eb623 DB |
206 | |
207 | return ann; | |
208 | } | |
209 | ||
571325db AP |
210 | /* Build a temporary. Make sure and register it to be renamed. */ |
211 | ||
212 | tree | |
213 | make_rename_temp (tree type, const char *prefix) | |
214 | { | |
215 | tree t = create_tmp_var (type, prefix); | |
e814a0d1 | 216 | |
0890b981 AP |
217 | if (TREE_CODE (TREE_TYPE (t)) == COMPLEX_TYPE |
218 | || TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE) | |
219 | DECL_GIMPLE_REG_P (t) = 1; | |
e814a0d1 | 220 | |
5cd4ec7f | 221 | if (gimple_referenced_vars (cfun)) |
eda9caf6 | 222 | { |
f004ab02 | 223 | add_referenced_var (t); |
0bca51f0 | 224 | mark_sym_for_renaming (t); |
eda9caf6 | 225 | } |
0bca51f0 | 226 | |
571325db AP |
227 | return t; |
228 | } | |
229 | ||
230 | ||
6de9cd9a DN |
231 | |
232 | /*--------------------------------------------------------------------------- | |
233 | Debugging functions | |
234 | ---------------------------------------------------------------------------*/ | |
235 | /* Dump the list of all the referenced variables in the current function to | |
236 | FILE. */ | |
237 | ||
238 | void | |
239 | dump_referenced_vars (FILE *file) | |
240 | { | |
a3648cfc DB |
241 | tree var; |
242 | referenced_var_iterator rvi; | |
243 | ||
ff6a3206 | 244 | fprintf (file, "\nReferenced variables in %s: %u\n\n", |
6de9cd9a | 245 | get_name (current_function_decl), (unsigned) num_referenced_vars); |
a3648cfc DB |
246 | |
247 | FOR_EACH_REFERENCED_VAR (var, rvi) | |
6de9cd9a | 248 | { |
6de9cd9a DN |
249 | fprintf (file, "Variable: "); |
250 | dump_variable (file, var); | |
6de9cd9a | 251 | } |
5006671f RG |
252 | |
253 | fprintf (file, "\n"); | |
6de9cd9a DN |
254 | } |
255 | ||
256 | ||
257 | /* Dump the list of all the referenced variables to stderr. */ | |
258 | ||
259 | void | |
260 | debug_referenced_vars (void) | |
261 | { | |
262 | dump_referenced_vars (stderr); | |
263 | } | |
264 | ||
265 | ||
266 | /* Dump variable VAR and its may-aliases to FILE. */ | |
267 | ||
268 | void | |
269 | dump_variable (FILE *file, tree var) | |
270 | { | |
271 | var_ann_t ann; | |
ff6a3206 | 272 | |
d8903b30 DN |
273 | if (TREE_CODE (var) == SSA_NAME) |
274 | { | |
275 | if (POINTER_TYPE_P (TREE_TYPE (var))) | |
276 | dump_points_to_info_for (file, var); | |
277 | var = SSA_NAME_VAR (var); | |
278 | } | |
6de9cd9a DN |
279 | |
280 | if (var == NULL_TREE) | |
281 | { | |
282 | fprintf (file, "<nil>"); | |
283 | return; | |
284 | } | |
285 | ||
286 | print_generic_expr (file, var, dump_flags); | |
6de9cd9a DN |
287 | |
288 | ann = var_ann (var); | |
289 | ||
ea53115f | 290 | fprintf (file, ", UID D.%u", (unsigned) DECL_UID (var)); |
6de9cd9a | 291 | |
1810f6ed DN |
292 | fprintf (file, ", "); |
293 | print_generic_expr (file, TREE_TYPE (var), dump_flags); | |
294 | ||
c597ef4e DN |
295 | if (TREE_ADDRESSABLE (var)) |
296 | fprintf (file, ", is addressable"); | |
297 | ||
298 | if (is_global_var (var)) | |
299 | fprintf (file, ", is global"); | |
6de9cd9a | 300 | |
c04f07f4 DN |
301 | if (TREE_THIS_VOLATILE (var)) |
302 | fprintf (file, ", is volatile"); | |
303 | ||
6de9cd9a | 304 | if (is_call_clobbered (var)) |
5006671f RG |
305 | fprintf (file, ", call clobbered"); |
306 | else if (is_call_used (var)) | |
307 | fprintf (file, ", call used"); | |
6de9cd9a | 308 | |
66350781 | 309 | if (ann && ann->noalias_state == NO_ALIAS) |
e9e0aa2c | 310 | fprintf (file, ", NO_ALIAS (does not alias other NO_ALIAS symbols)"); |
66350781 | 311 | else if (ann && ann->noalias_state == NO_ALIAS_GLOBAL) |
e9e0aa2c DN |
312 | fprintf (file, ", NO_ALIAS_GLOBAL (does not alias other NO_ALIAS symbols" |
313 | " and global vars)"); | |
66350781 | 314 | else if (ann && ann->noalias_state == NO_ALIAS_ANYTHING) |
e9e0aa2c DN |
315 | fprintf (file, ", NO_ALIAS_ANYTHING (does not alias any other symbols)"); |
316 | ||
66350781 | 317 | if (cfun && gimple_default_def (cfun, var)) |
6de9cd9a DN |
318 | { |
319 | fprintf (file, ", default def: "); | |
5cd4ec7f | 320 | print_generic_expr (file, gimple_default_def (cfun, var), dump_flags); |
6de9cd9a DN |
321 | } |
322 | ||
66350781 DN |
323 | if (DECL_INITIAL (var)) |
324 | { | |
325 | fprintf (file, ", initial: "); | |
326 | print_generic_expr (file, DECL_INITIAL (var), dump_flags); | |
327 | } | |
328 | ||
6de9cd9a DN |
329 | fprintf (file, "\n"); |
330 | } | |
331 | ||
332 | ||
333 | /* Dump variable VAR and its may-aliases to stderr. */ | |
334 | ||
335 | void | |
336 | debug_variable (tree var) | |
337 | { | |
338 | dump_variable (stderr, var); | |
339 | } | |
340 | ||
341 | ||
6de9cd9a DN |
342 | /* Dump various DFA statistics to FILE. */ |
343 | ||
344 | void | |
345 | dump_dfa_stats (FILE *file) | |
346 | { | |
347 | struct dfa_stats_d dfa_stats; | |
348 | ||
349 | unsigned long size, total = 0; | |
350 | const char * const fmt_str = "%-30s%-13s%12s\n"; | |
351 | const char * const fmt_str_1 = "%-30s%13lu%11lu%c\n"; | |
352 | const char * const fmt_str_3 = "%-43s%11lu%c\n"; | |
353 | const char *funcname | |
673fda6b | 354 | = lang_hooks.decl_printable_name (current_function_decl, 2); |
6de9cd9a DN |
355 | |
356 | collect_dfa_stats (&dfa_stats); | |
357 | ||
358 | fprintf (file, "\nDFA Statistics for %s\n\n", funcname); | |
359 | ||
360 | fprintf (file, "---------------------------------------------------------\n"); | |
361 | fprintf (file, fmt_str, "", " Number of ", "Memory"); | |
362 | fprintf (file, fmt_str, "", " instances ", "used "); | |
363 | fprintf (file, "---------------------------------------------------------\n"); | |
364 | ||
365 | size = num_referenced_vars * sizeof (tree); | |
366 | total += size; | |
3cd8c58a | 367 | fprintf (file, fmt_str_1, "Referenced variables", (unsigned long)num_referenced_vars, |
6de9cd9a DN |
368 | SCALE (size), LABEL (size)); |
369 | ||
6de9cd9a DN |
370 | size = dfa_stats.num_var_anns * sizeof (struct var_ann_d); |
371 | total += size; | |
372 | fprintf (file, fmt_str_1, "Variables annotated", dfa_stats.num_var_anns, | |
373 | SCALE (size), LABEL (size)); | |
374 | ||
375 | size = dfa_stats.num_uses * sizeof (tree *); | |
376 | total += size; | |
377 | fprintf (file, fmt_str_1, "USE operands", dfa_stats.num_uses, | |
378 | SCALE (size), LABEL (size)); | |
379 | ||
380 | size = dfa_stats.num_defs * sizeof (tree *); | |
381 | total += size; | |
382 | fprintf (file, fmt_str_1, "DEF operands", dfa_stats.num_defs, | |
383 | SCALE (size), LABEL (size)); | |
384 | ||
385 | size = dfa_stats.num_vuses * sizeof (tree *); | |
386 | total += size; | |
387 | fprintf (file, fmt_str_1, "VUSE operands", dfa_stats.num_vuses, | |
388 | SCALE (size), LABEL (size)); | |
389 | ||
38635499 | 390 | size = dfa_stats.num_vdefs * sizeof (tree *); |
a32b97a2 | 391 | total += size; |
38635499 | 392 | fprintf (file, fmt_str_1, "VDEF operands", dfa_stats.num_vdefs, |
6de9cd9a DN |
393 | SCALE (size), LABEL (size)); |
394 | ||
726a989a | 395 | size = dfa_stats.num_phis * sizeof (struct gimple_statement_phi); |
6de9cd9a DN |
396 | total += size; |
397 | fprintf (file, fmt_str_1, "PHI nodes", dfa_stats.num_phis, | |
398 | SCALE (size), LABEL (size)); | |
399 | ||
400 | size = dfa_stats.num_phi_args * sizeof (struct phi_arg_d); | |
401 | total += size; | |
402 | fprintf (file, fmt_str_1, "PHI arguments", dfa_stats.num_phi_args, | |
403 | SCALE (size), LABEL (size)); | |
404 | ||
405 | fprintf (file, "---------------------------------------------------------\n"); | |
406 | fprintf (file, fmt_str_3, "Total memory used by DFA/SSA data", SCALE (total), | |
407 | LABEL (total)); | |
408 | fprintf (file, "---------------------------------------------------------\n"); | |
409 | fprintf (file, "\n"); | |
410 | ||
411 | if (dfa_stats.num_phis) | |
726a989a | 412 | fprintf (file, "Average number of arguments per PHI node: %.1f (max: %ld)\n", |
6de9cd9a | 413 | (float) dfa_stats.num_phi_args / (float) dfa_stats.num_phis, |
726a989a | 414 | (long) dfa_stats.max_num_phi_args); |
6de9cd9a DN |
415 | |
416 | fprintf (file, "\n"); | |
417 | } | |
418 | ||
419 | ||
420 | /* Dump DFA statistics on stderr. */ | |
421 | ||
422 | void | |
423 | debug_dfa_stats (void) | |
424 | { | |
425 | dump_dfa_stats (stderr); | |
426 | } | |
427 | ||
428 | ||
206048bd | 429 | /* Collect DFA statistics and store them in the structure pointed to by |
6de9cd9a DN |
430 | DFA_STATS_P. */ |
431 | ||
432 | static void | |
726a989a | 433 | collect_dfa_stats (struct dfa_stats_d *dfa_stats_p ATTRIBUTE_UNUSED) |
6de9cd9a | 434 | { |
6de9cd9a | 435 | basic_block bb; |
726a989a RB |
436 | referenced_var_iterator vi; |
437 | tree var; | |
6de9cd9a | 438 | |
1e128c5f | 439 | gcc_assert (dfa_stats_p); |
6de9cd9a DN |
440 | |
441 | memset ((void *)dfa_stats_p, 0, sizeof (struct dfa_stats_d)); | |
442 | ||
726a989a RB |
443 | /* Count all the variable annotations. */ |
444 | FOR_EACH_REFERENCED_VAR (var, vi) | |
445 | if (var_ann (var)) | |
446 | dfa_stats_p->num_var_anns++; | |
6de9cd9a | 447 | |
726a989a | 448 | /* Walk all the statements in the function counting references. */ |
6de9cd9a DN |
449 | FOR_EACH_BB (bb) |
450 | { | |
726a989a RB |
451 | gimple_stmt_iterator si; |
452 | ||
453 | for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si)) | |
6de9cd9a | 454 | { |
726a989a | 455 | gimple phi = gsi_stmt (si); |
6de9cd9a | 456 | dfa_stats_p->num_phis++; |
726a989a RB |
457 | dfa_stats_p->num_phi_args += gimple_phi_num_args (phi); |
458 | if (gimple_phi_num_args (phi) > dfa_stats_p->max_num_phi_args) | |
459 | dfa_stats_p->max_num_phi_args = gimple_phi_num_args (phi); | |
6de9cd9a | 460 | } |
6de9cd9a | 461 | |
726a989a | 462 | for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si)) |
6de9cd9a | 463 | { |
726a989a RB |
464 | gimple stmt = gsi_stmt (si); |
465 | dfa_stats_p->num_defs += NUM_SSA_OPERANDS (stmt, SSA_OP_DEF); | |
466 | dfa_stats_p->num_uses += NUM_SSA_OPERANDS (stmt, SSA_OP_USE); | |
5006671f RG |
467 | dfa_stats_p->num_vdefs += gimple_vdef (stmt) ? 1 : 0; |
468 | dfa_stats_p->num_vuses += gimple_vuse (stmt) ? 1 : 0; | |
6de9cd9a DN |
469 | } |
470 | } | |
6de9cd9a DN |
471 | } |
472 | ||
473 | ||
474 | /*--------------------------------------------------------------------------- | |
475 | Miscellaneous helpers | |
476 | ---------------------------------------------------------------------------*/ | |
477 | /* Callback for walk_tree. Used to collect variables referenced in | |
478 | the function. */ | |
479 | ||
480 | static tree | |
f004ab02 | 481 | find_vars_r (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED) |
6de9cd9a | 482 | { |
908ff6a3 KZ |
483 | /* If we are reading the lto info back in, we need to rescan the |
484 | referenced vars. */ | |
485 | if (TREE_CODE (*tp) == SSA_NAME) | |
486 | add_referenced_var (SSA_NAME_VAR (*tp)); | |
487 | ||
aa4a53af RK |
488 | /* If T is a regular variable that the optimizers are interested |
489 | in, add it to the list of variables. */ | |
908ff6a3 | 490 | else if (SSA_VAR_P (*tp)) |
f004ab02 | 491 | add_referenced_var (*tp); |
aa4a53af RK |
492 | |
493 | /* Type, _DECL and constant nodes have no interesting children. | |
494 | Ignore them. */ | |
6615c446 | 495 | else if (IS_TYPE_OR_DECL_P (*tp) || CONSTANT_CLASS_P (*tp)) |
aa4a53af | 496 | *walk_subtrees = 0; |
6de9cd9a DN |
497 | |
498 | return NULL_TREE; | |
499 | } | |
500 | ||
07485407 DN |
501 | /* Find referenced variables in STMT. In contrast with |
502 | find_new_referenced_vars, this function will not mark newly found | |
503 | variables for renaming. */ | |
504 | ||
505 | void | |
506 | find_referenced_vars_in (gimple stmt) | |
507 | { | |
508 | size_t i; | |
509 | ||
510 | if (gimple_code (stmt) != GIMPLE_PHI) | |
511 | { | |
512 | for (i = 0; i < gimple_num_ops (stmt); i++) | |
513 | walk_tree (gimple_op_ptr (stmt, i), find_vars_r, NULL, NULL); | |
514 | } | |
515 | else | |
516 | { | |
517 | walk_tree (gimple_phi_result_ptr (stmt), find_vars_r, NULL, NULL); | |
518 | ||
519 | for (i = 0; i < gimple_phi_num_args (stmt); i++) | |
520 | { | |
521 | tree arg = gimple_phi_arg_def (stmt, i); | |
522 | walk_tree (&arg, find_vars_r, NULL, NULL); | |
523 | } | |
524 | } | |
525 | } | |
526 | ||
527 | ||
a3648cfc DB |
528 | /* Lookup UID in the referenced_vars hashtable and return the associated |
529 | variable. */ | |
530 | ||
531 | tree | |
532 | referenced_var_lookup (unsigned int uid) | |
533 | { | |
3b302421 RG |
534 | tree h; |
535 | struct tree_decl_minimal in; | |
536 | in.uid = uid; | |
537 | h = (tree) htab_find_with_hash (gimple_referenced_vars (cfun), &in, uid); | |
538 | gcc_assert (h || uid == 0); | |
539 | return h; | |
a3648cfc DB |
540 | } |
541 | ||
4b5e2dbc AM |
542 | /* Check if TO is in the referenced_vars hash table and insert it if not. |
543 | Return true if it required insertion. */ | |
a3648cfc | 544 | |
b23987ec | 545 | bool |
4b5e2dbc | 546 | referenced_var_check_and_insert (tree to) |
a3648cfc | 547 | { |
3b302421 RG |
548 | tree h, *loc; |
549 | struct tree_decl_minimal in; | |
4b5e2dbc AM |
550 | unsigned int uid = DECL_UID (to); |
551 | ||
3b302421 RG |
552 | in.uid = uid; |
553 | h = (tree) htab_find_with_hash (gimple_referenced_vars (cfun), &in, uid); | |
554 | if (h) | |
555 | { | |
556 | /* DECL_UID has already been entered in the table. Verify that it is | |
557 | the same entry as TO. See PR 27793. */ | |
558 | gcc_assert (h == to); | |
559 | return false; | |
560 | } | |
a3648cfc | 561 | |
3b302421 RG |
562 | loc = (tree *) htab_find_slot_with_hash (gimple_referenced_vars (cfun), |
563 | &in, uid, INSERT); | |
564 | *loc = to; | |
4b5e2dbc | 565 | return true; |
a3648cfc DB |
566 | } |
567 | ||
86051306 JH |
568 | /* Lookup VAR UID in the default_defs hashtable and return the associated |
569 | variable. */ | |
570 | ||
571 | tree | |
5cd4ec7f | 572 | gimple_default_def (struct function *fn, tree var) |
86051306 | 573 | { |
e445a2ff RG |
574 | struct tree_decl_minimal ind; |
575 | struct tree_ssa_name in; | |
86051306 | 576 | gcc_assert (SSA_VAR_P (var)); |
e445a2ff RG |
577 | in.var = (tree)&ind; |
578 | ind.uid = DECL_UID (var); | |
579 | return (tree) htab_find_with_hash (DEFAULT_DEFS (fn), &in, DECL_UID (var)); | |
86051306 JH |
580 | } |
581 | ||
582 | /* Insert the pair VAR's UID, DEF into the default_defs hashtable. */ | |
583 | ||
584 | void | |
585 | set_default_def (tree var, tree def) | |
586 | { | |
e445a2ff RG |
587 | struct tree_decl_minimal ind; |
588 | struct tree_ssa_name in; | |
86051306 JH |
589 | void **loc; |
590 | ||
591 | gcc_assert (SSA_VAR_P (var)); | |
e445a2ff RG |
592 | in.var = (tree)&ind; |
593 | ind.uid = DECL_UID (var); | |
594 | if (!def) | |
86051306 | 595 | { |
5cd4ec7f JH |
596 | loc = htab_find_slot_with_hash (DEFAULT_DEFS (cfun), &in, |
597 | DECL_UID (var), INSERT); | |
e445a2ff | 598 | gcc_assert (*loc); |
5cd4ec7f | 599 | htab_remove_elt (DEFAULT_DEFS (cfun), *loc); |
86051306 JH |
600 | return; |
601 | } | |
e445a2ff | 602 | gcc_assert (TREE_CODE (def) == SSA_NAME && SSA_NAME_VAR (def) == var); |
5cd4ec7f JH |
603 | loc = htab_find_slot_with_hash (DEFAULT_DEFS (cfun), &in, |
604 | DECL_UID (var), INSERT); | |
38635499 | 605 | |
86051306 | 606 | /* Default definition might be changed by tail call optimization. */ |
e445a2ff RG |
607 | if (*loc) |
608 | SSA_NAME_IS_DEFAULT_DEF (*(tree *) loc) = false; | |
609 | *(tree *) loc = def; | |
cfaab3a9 DN |
610 | |
611 | /* Mark DEF as the default definition for VAR. */ | |
612 | SSA_NAME_IS_DEFAULT_DEF (def) = true; | |
86051306 JH |
613 | } |
614 | ||
f004ab02 | 615 | /* Add VAR to the list of referenced variables if it isn't already there. */ |
6de9cd9a | 616 | |
65401a0b | 617 | bool |
f004ab02 | 618 | add_referenced_var (tree var) |
6de9cd9a | 619 | { |
6de9cd9a DN |
620 | var_ann_t v_ann; |
621 | ||
622 | v_ann = get_var_ann (var); | |
f004ab02 AM |
623 | gcc_assert (DECL_P (var)); |
624 | ||
4b5e2dbc AM |
625 | /* Insert VAR into the referenced_vars has table if it isn't present. */ |
626 | if (referenced_var_check_and_insert (var)) | |
6de9cd9a | 627 | { |
20c16b36 DN |
628 | /* Scan DECL_INITIAL for pointer variables as they may contain |
629 | address arithmetic referencing the address of other | |
75ccc1e7 RG |
630 | variables. As we are only interested in directly referenced |
631 | globals or referenced locals restrict this to initializers | |
632 | than can refer to local variables. */ | |
59c982fe | 633 | if (DECL_INITIAL (var) |
75ccc1e7 | 634 | && DECL_CONTEXT (var) == current_function_decl) |
f004ab02 | 635 | walk_tree (&DECL_INITIAL (var), find_vars_r, NULL, 0); |
65401a0b JJ |
636 | |
637 | return true; | |
6de9cd9a | 638 | } |
65401a0b JJ |
639 | |
640 | return false; | |
6de9cd9a DN |
641 | } |
642 | ||
326648f1 JH |
643 | /* Remove VAR from the list. */ |
644 | ||
645 | void | |
646 | remove_referenced_var (tree var) | |
647 | { | |
648 | var_ann_t v_ann; | |
3b302421 RG |
649 | struct tree_decl_minimal in; |
650 | void **loc; | |
326648f1 JH |
651 | unsigned int uid = DECL_UID (var); |
652 | ||
5006671f RG |
653 | /* Preserve var_anns of globals. */ |
654 | if (!is_global_var (var) | |
655 | && (v_ann = var_ann (var))) | |
540f6bda | 656 | { |
5006671f RG |
657 | ggc_free (v_ann); |
658 | var->base.ann = NULL; | |
540f6bda | 659 | } |
326648f1 | 660 | gcc_assert (DECL_P (var)); |
3b302421 RG |
661 | in.uid = uid; |
662 | loc = htab_find_slot_with_hash (gimple_referenced_vars (cfun), &in, uid, | |
663 | NO_INSERT); | |
664 | htab_clear_slot (gimple_referenced_vars (cfun), loc); | |
326648f1 JH |
665 | } |
666 | ||
6de9cd9a DN |
667 | |
668 | /* Return the virtual variable associated to the non-scalar variable VAR. */ | |
669 | ||
670 | tree | |
671 | get_virtual_var (tree var) | |
672 | { | |
6de9cd9a DN |
673 | STRIP_NOPS (var); |
674 | ||
675 | if (TREE_CODE (var) == SSA_NAME) | |
676 | var = SSA_NAME_VAR (var); | |
677 | ||
75822272 RK |
678 | while (TREE_CODE (var) == REALPART_EXPR || TREE_CODE (var) == IMAGPART_EXPR |
679 | || handled_component_p (var)) | |
44de5aeb | 680 | var = TREE_OPERAND (var, 0); |
ff6a3206 | 681 | |
6de9cd9a DN |
682 | /* Treating GIMPLE registers as virtual variables makes no sense. |
683 | Also complain if we couldn't extract a _DECL out of the original | |
684 | expression. */ | |
1e128c5f GB |
685 | gcc_assert (SSA_VAR_P (var)); |
686 | gcc_assert (!is_gimple_reg (var)); | |
6de9cd9a DN |
687 | |
688 | return var; | |
689 | } | |
690 | ||
cff4e50d | 691 | /* Mark all the naked symbols in STMT for SSA renaming. */ |
6de9cd9a DN |
692 | |
693 | void | |
726a989a | 694 | mark_symbols_for_renaming (gimple stmt) |
6de9cd9a | 695 | { |
cfaab3a9 | 696 | tree op; |
4c124b4c | 697 | ssa_op_iter iter; |
6de9cd9a | 698 | |
f430bae8 | 699 | update_stmt (stmt); |
6de9cd9a | 700 | |
cfaab3a9 DN |
701 | /* Mark all the operands for renaming. */ |
702 | FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_OPERANDS) | |
703 | if (DECL_P (op)) | |
704 | mark_sym_for_renaming (op); | |
6de9cd9a | 705 | } |
b28b1600 | 706 | |
cfaab3a9 | 707 | |
726a989a RB |
708 | /* Find all variables within the gimplified statement that were not |
709 | previously visible to the function and add them to the referenced | |
710 | variables list. */ | |
b28b1600 JJ |
711 | |
712 | static tree | |
713 | find_new_referenced_vars_1 (tree *tp, int *walk_subtrees, | |
714 | void *data ATTRIBUTE_UNUSED) | |
715 | { | |
716 | tree t = *tp; | |
717 | ||
718 | if (TREE_CODE (t) == VAR_DECL && !var_ann (t)) | |
0bca51f0 | 719 | { |
f004ab02 | 720 | add_referenced_var (t); |
0bca51f0 DN |
721 | mark_sym_for_renaming (t); |
722 | } | |
b28b1600 JJ |
723 | |
724 | if (IS_TYPE_OR_DECL_P (t)) | |
725 | *walk_subtrees = 0; | |
726 | ||
727 | return NULL; | |
728 | } | |
729 | ||
726a989a RB |
730 | |
731 | /* Find any new referenced variables in STMT. */ | |
732 | ||
b28b1600 | 733 | void |
726a989a | 734 | find_new_referenced_vars (gimple stmt) |
b28b1600 | 735 | { |
726a989a | 736 | walk_gimple_op (stmt, find_new_referenced_vars_1, NULL); |
b28b1600 | 737 | } |
7d5f9cc6 DN |
738 | |
739 | ||
cfaab3a9 | 740 | /* If EXP is a handled component reference for a structure, return the |
6bec9271 RG |
741 | base variable. The access range is delimited by bit positions *POFFSET and |
742 | *POFFSET + *PMAX_SIZE. The access size is *PSIZE bits. If either | |
743 | *PSIZE or *PMAX_SIZE is -1, they could not be determined. If *PSIZE | |
744 | and *PMAX_SIZE are equal, the access is non-variable. */ | |
c75ab022 DB |
745 | |
746 | tree | |
6bec9271 RG |
747 | get_ref_base_and_extent (tree exp, HOST_WIDE_INT *poffset, |
748 | HOST_WIDE_INT *psize, | |
749 | HOST_WIDE_INT *pmax_size) | |
c75ab022 | 750 | { |
6bec9271 RG |
751 | HOST_WIDE_INT bitsize = -1; |
752 | HOST_WIDE_INT maxsize = -1; | |
753 | tree size_tree = NULL_TREE; | |
c21c775a | 754 | HOST_WIDE_INT bit_offset = 0; |
00e85045 | 755 | bool seen_variable_array_ref = false; |
133f9369 | 756 | bool seen_union = false; |
6bec9271 | 757 | |
6bec9271 RG |
758 | /* First get the final access size from just the outermost expression. */ |
759 | if (TREE_CODE (exp) == COMPONENT_REF) | |
760 | size_tree = DECL_SIZE (TREE_OPERAND (exp, 1)); | |
761 | else if (TREE_CODE (exp) == BIT_FIELD_REF) | |
762 | size_tree = TREE_OPERAND (exp, 1); | |
55b34b5f | 763 | else if (!VOID_TYPE_P (TREE_TYPE (exp))) |
c75ab022 | 764 | { |
6bec9271 RG |
765 | enum machine_mode mode = TYPE_MODE (TREE_TYPE (exp)); |
766 | if (mode == BLKmode) | |
767 | size_tree = TYPE_SIZE (TREE_TYPE (exp)); | |
768 | else | |
769 | bitsize = GET_MODE_BITSIZE (mode); | |
c75ab022 | 770 | } |
6bec9271 | 771 | if (size_tree != NULL_TREE) |
c75ab022 | 772 | { |
6bec9271 RG |
773 | if (! host_integerp (size_tree, 1)) |
774 | bitsize = -1; | |
775 | else | |
776 | bitsize = TREE_INT_CST_LOW (size_tree); | |
c75ab022 | 777 | } |
6bec9271 RG |
778 | |
779 | /* Initially, maxsize is the same as the accessed element size. | |
780 | In the following it will only grow (or become -1). */ | |
781 | maxsize = bitsize; | |
782 | ||
783 | /* Compute cumulative bit-offset for nested component-refs and array-refs, | |
784 | and find the ultimate containing object. */ | |
785 | while (1) | |
786 | { | |
787 | switch (TREE_CODE (exp)) | |
788 | { | |
789 | case BIT_FIELD_REF: | |
821bb7f8 | 790 | bit_offset += TREE_INT_CST_LOW (TREE_OPERAND (exp, 2)); |
6bec9271 RG |
791 | break; |
792 | ||
793 | case COMPONENT_REF: | |
794 | { | |
795 | tree field = TREE_OPERAND (exp, 1); | |
796 | tree this_offset = component_ref_field_offset (exp); | |
797 | ||
133f9369 MJ |
798 | if (TREE_CODE (TREE_TYPE (TREE_OPERAND (exp, 0))) == UNION_TYPE) |
799 | seen_union = true; | |
800 | ||
821bb7f8 RG |
801 | if (this_offset |
802 | && TREE_CODE (this_offset) == INTEGER_CST | |
803 | && host_integerp (this_offset, 0)) | |
6bec9271 | 804 | { |
821bb7f8 | 805 | HOST_WIDE_INT hthis_offset = TREE_INT_CST_LOW (this_offset); |
c21c775a RG |
806 | hthis_offset *= BITS_PER_UNIT; |
807 | bit_offset += hthis_offset; | |
821bb7f8 | 808 | bit_offset += TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (field)); |
6bec9271 RG |
809 | } |
810 | else | |
811 | { | |
812 | tree csize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0))); | |
813 | /* We need to adjust maxsize to the whole structure bitsize. | |
fa10beec | 814 | But we can subtract any constant offset seen so far, |
6bec9271 | 815 | because that would get us out of the structure otherwise. */ |
8975ae22 EB |
816 | if (maxsize != -1 && csize && host_integerp (csize, 1)) |
817 | maxsize = TREE_INT_CST_LOW (csize) - bit_offset; | |
6bec9271 RG |
818 | else |
819 | maxsize = -1; | |
820 | } | |
821 | } | |
822 | break; | |
823 | ||
824 | case ARRAY_REF: | |
825 | case ARRAY_RANGE_REF: | |
826 | { | |
827 | tree index = TREE_OPERAND (exp, 1); | |
821bb7f8 | 828 | tree low_bound, unit_size; |
6bec9271 | 829 | |
c21c775a | 830 | /* If the resulting bit-offset is constant, track it. */ |
821bb7f8 RG |
831 | if (TREE_CODE (index) == INTEGER_CST |
832 | && host_integerp (index, 0) | |
833 | && (low_bound = array_ref_low_bound (exp), | |
834 | host_integerp (low_bound, 0)) | |
835 | && (unit_size = array_ref_element_size (exp), | |
836 | host_integerp (unit_size, 1))) | |
6bec9271 | 837 | { |
821bb7f8 | 838 | HOST_WIDE_INT hindex = TREE_INT_CST_LOW (index); |
c21c775a | 839 | |
821bb7f8 RG |
840 | hindex -= TREE_INT_CST_LOW (low_bound); |
841 | hindex *= TREE_INT_CST_LOW (unit_size); | |
c21c775a RG |
842 | hindex *= BITS_PER_UNIT; |
843 | bit_offset += hindex; | |
00e85045 RG |
844 | |
845 | /* An array ref with a constant index up in the structure | |
846 | hierarchy will constrain the size of any variable array ref | |
847 | lower in the access hierarchy. */ | |
848 | seen_variable_array_ref = false; | |
6bec9271 RG |
849 | } |
850 | else | |
851 | { | |
852 | tree asize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0))); | |
853 | /* We need to adjust maxsize to the whole array bitsize. | |
fa10beec | 854 | But we can subtract any constant offset seen so far, |
6bec9271 | 855 | because that would get us outside of the array otherwise. */ |
8975ae22 EB |
856 | if (maxsize != -1 && asize && host_integerp (asize, 1)) |
857 | maxsize = TREE_INT_CST_LOW (asize) - bit_offset; | |
6bec9271 RG |
858 | else |
859 | maxsize = -1; | |
00e85045 RG |
860 | |
861 | /* Remember that we have seen an array ref with a variable | |
862 | index. */ | |
863 | seen_variable_array_ref = true; | |
6bec9271 RG |
864 | } |
865 | } | |
866 | break; | |
867 | ||
868 | case REALPART_EXPR: | |
869 | break; | |
870 | ||
871 | case IMAGPART_EXPR: | |
c21c775a | 872 | bit_offset += bitsize; |
6bec9271 RG |
873 | break; |
874 | ||
875 | case VIEW_CONVERT_EXPR: | |
876 | /* ??? We probably should give up here and bail out. */ | |
877 | break; | |
878 | ||
879 | default: | |
880 | goto done; | |
881 | } | |
882 | ||
883 | exp = TREE_OPERAND (exp, 0); | |
884 | } | |
885 | done: | |
886 | ||
00e85045 RG |
887 | /* We need to deal with variable arrays ending structures such as |
888 | struct { int length; int a[1]; } x; x.a[d] | |
889 | struct { struct { int a; int b; } a[1]; } x; x.a[d].a | |
890 | struct { struct { int a[1]; } a[1]; } x; x.a[0][d], x.a[d][0] | |
891 | where we do not know maxsize for variable index accesses to | |
892 | the array. The simplest way to conservatively deal with this | |
893 | is to punt in the case that offset + maxsize reaches the | |
133f9369 MJ |
894 | base type boundary. |
895 | ||
896 | Unfortunately this is difficult to determine reliably when unions are | |
897 | involved and so we are conservative in such cases. | |
898 | ||
899 | FIXME: This approach may be too conservative, we probably want to at least | |
900 | check that the union is the last field/element at its level or even | |
901 | propagate the calculated offsets back up the access chain and check | |
902 | there. */ | |
903 | ||
00e85045 | 904 | if (seen_variable_array_ref |
133f9369 MJ |
905 | && (seen_union |
906 | || (maxsize != -1 | |
907 | && host_integerp (TYPE_SIZE (TREE_TYPE (exp)), 1) | |
908 | && bit_offset + maxsize | |
909 | == (signed) TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (exp)))))) | |
00e85045 RG |
910 | maxsize = -1; |
911 | ||
6bec9271 RG |
912 | /* ??? Due to negative offsets in ARRAY_REF we can end up with |
913 | negative bit_offset here. We might want to store a zero offset | |
914 | in this case. */ | |
c21c775a | 915 | *poffset = bit_offset; |
6bec9271 RG |
916 | *psize = bitsize; |
917 | *pmax_size = maxsize; | |
918 | ||
919 | return exp; | |
c75ab022 | 920 | } |
e9e0aa2c | 921 | |
2e58df6e RG |
922 | /* Returns true if STMT references an SSA_NAME that has |
923 | SSA_NAME_OCCURS_IN_ABNORMAL_PHI set, otherwise false. */ | |
924 | ||
925 | bool | |
726a989a | 926 | stmt_references_abnormal_ssa_name (gimple stmt) |
2e58df6e RG |
927 | { |
928 | ssa_op_iter oi; | |
929 | use_operand_p use_p; | |
930 | ||
931 | FOR_EACH_SSA_USE_OPERAND (use_p, stmt, oi, SSA_OP_USE) | |
932 | { | |
933 | if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (use_p))) | |
934 | return true; | |
935 | } | |
936 | ||
937 | return false; | |
938 | } | |
939 |