|
0
|
1 /* Data flow functions for trees.
|
|
|
2 Copyright (C) 2001, 2002, 2003, 2004, 2005, 2007, 2008, 2009
|
|
|
3 Free Software Foundation, Inc.
|
|
|
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
|
|
|
10 the Free Software Foundation; either version 3, or (at your option)
|
|
|
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
|
|
|
19 along with GCC; see the file COPYING3. If not see
|
|
|
20 <http://www.gnu.org/licenses/>. */
|
|
|
21
|
|
|
22 #include "config.h"
|
|
|
23 #include "system.h"
|
|
|
24 #include "coretypes.h"
|
|
|
25 #include "tm.h"
|
|
|
26 #include "hashtab.h"
|
|
|
27 #include "pointer-set.h"
|
|
|
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"
|
|
|
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"
|
|
|
42 #include "gimple.h"
|
|
|
43 #include "tree-flow.h"
|
|
|
44 #include "tree-inline.h"
|
|
|
45 #include "tree-pass.h"
|
|
|
46 #include "convert.h"
|
|
|
47 #include "params.h"
|
|
|
48 #include "cgraph.h"
|
|
|
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 {
|
|
|
55 long num_var_anns;
|
|
|
56 long num_defs;
|
|
|
57 long num_uses;
|
|
|
58 long num_phis;
|
|
|
59 long num_phi_args;
|
|
|
60 size_t max_num_phi_args;
|
|
|
61 long num_vdefs;
|
|
|
62 long num_vuses;
|
|
|
63 };
|
|
|
64
|
|
|
65
|
|
|
66 /* Local functions. */
|
|
|
67 static void collect_dfa_stats (struct dfa_stats_d *);
|
|
|
68 static tree find_vars_r (tree *, int *, void *);
|
|
|
69
|
|
|
70
|
|
|
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
|
|
|
82 static unsigned int
|
|
|
83 find_referenced_vars (void)
|
|
|
84 {
|
|
|
85 basic_block bb;
|
|
|
86 gimple_stmt_iterator si;
|
|
|
87
|
|
|
88 FOR_EACH_BB (bb)
|
|
|
89 {
|
|
|
90 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
|
|
|
91 {
|
|
|
92 size_t i;
|
|
|
93 gimple stmt = gsi_stmt (si);
|
|
|
94 for (i = 0; i < gimple_num_ops (stmt); i++)
|
|
|
95 walk_tree (gimple_op_ptr (stmt, i), find_vars_r, NULL, NULL);
|
|
|
96 }
|
|
|
97
|
|
|
98 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
|
|
|
99 {
|
|
|
100 gimple phi = gsi_stmt (si);
|
|
|
101 size_t i, len = gimple_phi_num_args (phi);
|
|
|
102
|
|
|
103 walk_tree (gimple_phi_result_ptr (phi), find_vars_r, NULL, NULL);
|
|
|
104
|
|
|
105 for (i = 0; i < len; i++)
|
|
|
106 {
|
|
|
107 tree arg = gimple_phi_arg_def (phi, i);
|
|
|
108 walk_tree (&arg, find_vars_r, NULL, NULL);
|
|
|
109 }
|
|
|
110 }
|
|
|
111 }
|
|
|
112
|
|
|
113 return 0;
|
|
|
114 }
|
|
|
115
|
|
|
116 struct gimple_opt_pass pass_referenced_vars =
|
|
|
117 {
|
|
|
118 {
|
|
|
119 GIMPLE_PASS,
|
|
|
120 NULL, /* name */
|
|
|
121 NULL, /* gate */
|
|
|
122 find_referenced_vars, /* execute */
|
|
|
123 NULL, /* sub */
|
|
|
124 NULL, /* next */
|
|
|
125 0, /* static_pass_number */
|
|
|
126 TV_FIND_REFERENCED_VARS, /* tv_id */
|
|
|
127 PROP_gimple_leh | PROP_cfg, /* properties_required */
|
|
|
128 PROP_referenced_vars, /* properties_provided */
|
|
|
129 0, /* properties_destroyed */
|
|
|
130 TODO_dump_func, /* todo_flags_start */
|
|
|
131 TODO_dump_func /* todo_flags_finish */
|
|
|
132 }
|
|
|
133 };
|
|
|
134
|
|
|
135
|
|
|
136 /*---------------------------------------------------------------------------
|
|
|
137 Manage annotations
|
|
|
138 ---------------------------------------------------------------------------*/
|
|
|
139 /* Create a new annotation for a _DECL node T. */
|
|
|
140
|
|
|
141 var_ann_t
|
|
|
142 create_var_ann (tree t)
|
|
|
143 {
|
|
|
144 var_ann_t ann;
|
|
|
145
|
|
|
146 gcc_assert (t);
|
|
|
147 gcc_assert (DECL_P (t));
|
|
|
148 gcc_assert (!t->base.ann || t->base.ann->common.type == VAR_ANN);
|
|
|
149
|
|
|
150 ann = GGC_CNEW (struct var_ann_d);
|
|
|
151 ann->common.type = VAR_ANN;
|
|
|
152 t->base.ann = (tree_ann_t) ann;
|
|
|
153
|
|
|
154 return ann;
|
|
|
155 }
|
|
|
156
|
|
|
157 /* Create a new annotation for a FUNCTION_DECL node T. */
|
|
|
158
|
|
|
159 function_ann_t
|
|
|
160 create_function_ann (tree t)
|
|
|
161 {
|
|
|
162 function_ann_t ann;
|
|
|
163
|
|
|
164 gcc_assert (t);
|
|
|
165 gcc_assert (TREE_CODE (t) == FUNCTION_DECL);
|
|
|
166 gcc_assert (!t->base.ann || t->base.ann->common.type == FUNCTION_ANN);
|
|
|
167
|
|
|
168 ann = (function_ann_t) ggc_alloc (sizeof (*ann));
|
|
|
169 memset ((void *) ann, 0, sizeof (*ann));
|
|
|
170
|
|
|
171 ann->common.type = FUNCTION_ANN;
|
|
|
172
|
|
|
173 t->base.ann = (tree_ann_t) ann;
|
|
|
174
|
|
|
175 return ann;
|
|
|
176 }
|
|
|
177
|
|
|
178 /* Renumber all of the gimple stmt uids. */
|
|
|
179
|
|
|
180 void
|
|
|
181 renumber_gimple_stmt_uids (void)
|
|
|
182 {
|
|
|
183 basic_block bb;
|
|
|
184
|
|
|
185 set_gimple_stmt_max_uid (cfun, 0);
|
|
|
186 FOR_ALL_BB (bb)
|
|
|
187 {
|
|
|
188 gimple_stmt_iterator bsi;
|
|
|
189 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
|
|
|
190 {
|
|
|
191 gimple stmt = gsi_stmt (bsi);
|
|
|
192 gimple_set_uid (stmt, inc_gimple_stmt_max_uid (cfun));
|
|
|
193 }
|
|
|
194 }
|
|
|
195 }
|
|
|
196
|
|
|
197 /* Create a new annotation for a tree T. */
|
|
|
198
|
|
|
199 tree_ann_common_t
|
|
|
200 create_tree_common_ann (tree t)
|
|
|
201 {
|
|
|
202 tree_ann_common_t ann;
|
|
|
203
|
|
|
204 gcc_assert (t);
|
|
|
205 gcc_assert (!t->base.ann || t->base.ann->common.type == TREE_ANN_COMMON);
|
|
|
206
|
|
|
207 ann = GGC_CNEW (struct tree_ann_common_d);
|
|
|
208
|
|
|
209 ann->type = TREE_ANN_COMMON;
|
|
|
210 ann->rn = -1;
|
|
|
211 t->base.ann = (tree_ann_t) ann;
|
|
|
212
|
|
|
213 return ann;
|
|
|
214 }
|
|
|
215
|
|
|
216 /* Build a temporary. Make sure and register it to be renamed. */
|
|
|
217
|
|
|
218 tree
|
|
|
219 make_rename_temp (tree type, const char *prefix)
|
|
|
220 {
|
|
|
221 tree t = create_tmp_var (type, prefix);
|
|
|
222
|
|
|
223 if (TREE_CODE (TREE_TYPE (t)) == COMPLEX_TYPE
|
|
|
224 || TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE)
|
|
|
225 DECL_GIMPLE_REG_P (t) = 1;
|
|
|
226
|
|
|
227 if (gimple_referenced_vars (cfun))
|
|
|
228 {
|
|
|
229 add_referenced_var (t);
|
|
|
230 mark_sym_for_renaming (t);
|
|
|
231 }
|
|
|
232
|
|
|
233 return t;
|
|
|
234 }
|
|
|
235
|
|
|
236
|
|
|
237
|
|
|
238 /*---------------------------------------------------------------------------
|
|
|
239 Debugging functions
|
|
|
240 ---------------------------------------------------------------------------*/
|
|
|
241 /* Dump the list of all the referenced variables in the current function to
|
|
|
242 FILE. */
|
|
|
243
|
|
|
244 void
|
|
|
245 dump_referenced_vars (FILE *file)
|
|
|
246 {
|
|
|
247 tree var;
|
|
|
248 referenced_var_iterator rvi;
|
|
|
249
|
|
|
250 fprintf (file, "\nReferenced variables in %s: %u\n\n",
|
|
|
251 get_name (current_function_decl), (unsigned) num_referenced_vars);
|
|
|
252
|
|
|
253 FOR_EACH_REFERENCED_VAR (var, rvi)
|
|
|
254 {
|
|
|
255 fprintf (file, "Variable: ");
|
|
|
256 dump_variable (file, var);
|
|
|
257 fprintf (file, "\n");
|
|
|
258 }
|
|
|
259 }
|
|
|
260
|
|
|
261
|
|
|
262 /* Dump the list of all the referenced variables to stderr. */
|
|
|
263
|
|
|
264 void
|
|
|
265 debug_referenced_vars (void)
|
|
|
266 {
|
|
|
267 dump_referenced_vars (stderr);
|
|
|
268 }
|
|
|
269
|
|
|
270
|
|
|
271 /* Dump variable VAR and its may-aliases to FILE. */
|
|
|
272
|
|
|
273 void
|
|
|
274 dump_variable (FILE *file, tree var)
|
|
|
275 {
|
|
|
276 var_ann_t ann;
|
|
|
277
|
|
|
278 if (TREE_CODE (var) == SSA_NAME)
|
|
|
279 {
|
|
|
280 if (POINTER_TYPE_P (TREE_TYPE (var)))
|
|
|
281 dump_points_to_info_for (file, var);
|
|
|
282 var = SSA_NAME_VAR (var);
|
|
|
283 }
|
|
|
284
|
|
|
285 if (var == NULL_TREE)
|
|
|
286 {
|
|
|
287 fprintf (file, "<nil>");
|
|
|
288 return;
|
|
|
289 }
|
|
|
290
|
|
|
291 print_generic_expr (file, var, dump_flags);
|
|
|
292
|
|
|
293 ann = var_ann (var);
|
|
|
294
|
|
|
295 fprintf (file, ", UID D.%u", (unsigned) DECL_UID (var));
|
|
|
296
|
|
|
297 fprintf (file, ", ");
|
|
|
298 print_generic_expr (file, TREE_TYPE (var), dump_flags);
|
|
|
299
|
|
|
300 if (ann && ann->symbol_mem_tag)
|
|
|
301 {
|
|
|
302 fprintf (file, ", symbol memory tag: ");
|
|
|
303 print_generic_expr (file, ann->symbol_mem_tag, dump_flags);
|
|
|
304 }
|
|
|
305
|
|
|
306 if (TREE_ADDRESSABLE (var))
|
|
|
307 fprintf (file, ", is addressable");
|
|
|
308
|
|
|
309 if (is_global_var (var))
|
|
|
310 fprintf (file, ", is global");
|
|
|
311
|
|
|
312 if (TREE_THIS_VOLATILE (var))
|
|
|
313 fprintf (file, ", is volatile");
|
|
|
314
|
|
|
315 dump_mem_sym_stats_for_var (file, var);
|
|
|
316
|
|
|
317 if (is_call_clobbered (var))
|
|
|
318 {
|
|
|
319 const char *s = "";
|
|
|
320 var_ann_t va = var_ann (var);
|
|
|
321 unsigned int escape_mask = va->escape_mask;
|
|
|
322
|
|
|
323 fprintf (file, ", call clobbered");
|
|
|
324 fprintf (file, " (");
|
|
|
325 if (escape_mask & ESCAPE_STORED_IN_GLOBAL)
|
|
|
326 { fprintf (file, "%sstored in global", s); s = ", "; }
|
|
|
327 if (escape_mask & ESCAPE_TO_ASM)
|
|
|
328 { fprintf (file, "%sgoes through ASM", s); s = ", "; }
|
|
|
329 if (escape_mask & ESCAPE_TO_CALL)
|
|
|
330 { fprintf (file, "%spassed to call", s); s = ", "; }
|
|
|
331 if (escape_mask & ESCAPE_BAD_CAST)
|
|
|
332 { fprintf (file, "%sbad cast", s); s = ", "; }
|
|
|
333 if (escape_mask & ESCAPE_TO_RETURN)
|
|
|
334 { fprintf (file, "%sreturned from func", s); s = ", "; }
|
|
|
335 if (escape_mask & ESCAPE_TO_PURE_CONST)
|
|
|
336 { fprintf (file, "%spassed to pure/const", s); s = ", "; }
|
|
|
337 if (escape_mask & ESCAPE_IS_GLOBAL)
|
|
|
338 { fprintf (file, "%sis global var", s); s = ", "; }
|
|
|
339 if (escape_mask & ESCAPE_IS_PARM)
|
|
|
340 { fprintf (file, "%sis incoming pointer", s); s = ", "; }
|
|
|
341 if (escape_mask & ESCAPE_UNKNOWN)
|
|
|
342 { fprintf (file, "%sunknown escape", s); s = ", "; }
|
|
|
343 fprintf (file, ")");
|
|
|
344 }
|
|
|
345
|
|
|
346 if (ann->noalias_state == NO_ALIAS)
|
|
|
347 fprintf (file, ", NO_ALIAS (does not alias other NO_ALIAS symbols)");
|
|
|
348 else if (ann->noalias_state == NO_ALIAS_GLOBAL)
|
|
|
349 fprintf (file, ", NO_ALIAS_GLOBAL (does not alias other NO_ALIAS symbols"
|
|
|
350 " and global vars)");
|
|
|
351 else if (ann->noalias_state == NO_ALIAS_ANYTHING)
|
|
|
352 fprintf (file, ", NO_ALIAS_ANYTHING (does not alias any other symbols)");
|
|
|
353
|
|
|
354 if (gimple_default_def (cfun, var))
|
|
|
355 {
|
|
|
356 fprintf (file, ", default def: ");
|
|
|
357 print_generic_expr (file, gimple_default_def (cfun, var), dump_flags);
|
|
|
358 }
|
|
|
359
|
|
|
360 if (MTAG_P (var) && may_aliases (var))
|
|
|
361 {
|
|
|
362 fprintf (file, ", may aliases: ");
|
|
|
363 dump_may_aliases_for (file, var);
|
|
|
364 }
|
|
|
365
|
|
|
366 if (!is_gimple_reg (var))
|
|
|
367 {
|
|
|
368 if (memory_partition (var))
|
|
|
369 {
|
|
|
370 fprintf (file, ", belongs to partition: ");
|
|
|
371 print_generic_expr (file, memory_partition (var), dump_flags);
|
|
|
372 }
|
|
|
373
|
|
|
374 if (TREE_CODE (var) == MEMORY_PARTITION_TAG)
|
|
|
375 {
|
|
|
376 fprintf (file, ", partition symbols: ");
|
|
|
377 dump_decl_set (file, MPT_SYMBOLS (var));
|
|
|
378 }
|
|
|
379 }
|
|
|
380
|
|
|
381 fprintf (file, "\n");
|
|
|
382 }
|
|
|
383
|
|
|
384
|
|
|
385 /* Dump variable VAR and its may-aliases to stderr. */
|
|
|
386
|
|
|
387 void
|
|
|
388 debug_variable (tree var)
|
|
|
389 {
|
|
|
390 dump_variable (stderr, var);
|
|
|
391 }
|
|
|
392
|
|
|
393
|
|
|
394 /* Dump various DFA statistics to FILE. */
|
|
|
395
|
|
|
396 void
|
|
|
397 dump_dfa_stats (FILE *file)
|
|
|
398 {
|
|
|
399 struct dfa_stats_d dfa_stats;
|
|
|
400
|
|
|
401 unsigned long size, total = 0;
|
|
|
402 const char * const fmt_str = "%-30s%-13s%12s\n";
|
|
|
403 const char * const fmt_str_1 = "%-30s%13lu%11lu%c\n";
|
|
|
404 const char * const fmt_str_3 = "%-43s%11lu%c\n";
|
|
|
405 const char *funcname
|
|
|
406 = lang_hooks.decl_printable_name (current_function_decl, 2);
|
|
|
407
|
|
|
408 collect_dfa_stats (&dfa_stats);
|
|
|
409
|
|
|
410 fprintf (file, "\nDFA Statistics for %s\n\n", funcname);
|
|
|
411
|
|
|
412 fprintf (file, "---------------------------------------------------------\n");
|
|
|
413 fprintf (file, fmt_str, "", " Number of ", "Memory");
|
|
|
414 fprintf (file, fmt_str, "", " instances ", "used ");
|
|
|
415 fprintf (file, "---------------------------------------------------------\n");
|
|
|
416
|
|
|
417 size = num_referenced_vars * sizeof (tree);
|
|
|
418 total += size;
|
|
|
419 fprintf (file, fmt_str_1, "Referenced variables", (unsigned long)num_referenced_vars,
|
|
|
420 SCALE (size), LABEL (size));
|
|
|
421
|
|
|
422 size = dfa_stats.num_var_anns * sizeof (struct var_ann_d);
|
|
|
423 total += size;
|
|
|
424 fprintf (file, fmt_str_1, "Variables annotated", dfa_stats.num_var_anns,
|
|
|
425 SCALE (size), LABEL (size));
|
|
|
426
|
|
|
427 size = dfa_stats.num_uses * sizeof (tree *);
|
|
|
428 total += size;
|
|
|
429 fprintf (file, fmt_str_1, "USE operands", dfa_stats.num_uses,
|
|
|
430 SCALE (size), LABEL (size));
|
|
|
431
|
|
|
432 size = dfa_stats.num_defs * sizeof (tree *);
|
|
|
433 total += size;
|
|
|
434 fprintf (file, fmt_str_1, "DEF operands", dfa_stats.num_defs,
|
|
|
435 SCALE (size), LABEL (size));
|
|
|
436
|
|
|
437 size = dfa_stats.num_vuses * sizeof (tree *);
|
|
|
438 total += size;
|
|
|
439 fprintf (file, fmt_str_1, "VUSE operands", dfa_stats.num_vuses,
|
|
|
440 SCALE (size), LABEL (size));
|
|
|
441
|
|
|
442 size = dfa_stats.num_vdefs * sizeof (tree *);
|
|
|
443 total += size;
|
|
|
444 fprintf (file, fmt_str_1, "VDEF operands", dfa_stats.num_vdefs,
|
|
|
445 SCALE (size), LABEL (size));
|
|
|
446
|
|
|
447 size = dfa_stats.num_phis * sizeof (struct gimple_statement_phi);
|
|
|
448 total += size;
|
|
|
449 fprintf (file, fmt_str_1, "PHI nodes", dfa_stats.num_phis,
|
|
|
450 SCALE (size), LABEL (size));
|
|
|
451
|
|
|
452 size = dfa_stats.num_phi_args * sizeof (struct phi_arg_d);
|
|
|
453 total += size;
|
|
|
454 fprintf (file, fmt_str_1, "PHI arguments", dfa_stats.num_phi_args,
|
|
|
455 SCALE (size), LABEL (size));
|
|
|
456
|
|
|
457 fprintf (file, "---------------------------------------------------------\n");
|
|
|
458 fprintf (file, fmt_str_3, "Total memory used by DFA/SSA data", SCALE (total),
|
|
|
459 LABEL (total));
|
|
|
460 fprintf (file, "---------------------------------------------------------\n");
|
|
|
461 fprintf (file, "\n");
|
|
|
462
|
|
|
463 if (dfa_stats.num_phis)
|
|
|
464 fprintf (file, "Average number of arguments per PHI node: %.1f (max: %ld)\n",
|
|
|
465 (float) dfa_stats.num_phi_args / (float) dfa_stats.num_phis,
|
|
|
466 (long) dfa_stats.max_num_phi_args);
|
|
|
467
|
|
|
468 fprintf (file, "\n");
|
|
|
469 }
|
|
|
470
|
|
|
471
|
|
|
472 /* Dump DFA statistics on stderr. */
|
|
|
473
|
|
|
474 void
|
|
|
475 debug_dfa_stats (void)
|
|
|
476 {
|
|
|
477 dump_dfa_stats (stderr);
|
|
|
478 }
|
|
|
479
|
|
|
480
|
|
|
481 /* Collect DFA statistics and store them in the structure pointed to by
|
|
|
482 DFA_STATS_P. */
|
|
|
483
|
|
|
484 static void
|
|
|
485 collect_dfa_stats (struct dfa_stats_d *dfa_stats_p ATTRIBUTE_UNUSED)
|
|
|
486 {
|
|
|
487 basic_block bb;
|
|
|
488 referenced_var_iterator vi;
|
|
|
489 tree var;
|
|
|
490
|
|
|
491 gcc_assert (dfa_stats_p);
|
|
|
492
|
|
|
493 memset ((void *)dfa_stats_p, 0, sizeof (struct dfa_stats_d));
|
|
|
494
|
|
|
495 /* Count all the variable annotations. */
|
|
|
496 FOR_EACH_REFERENCED_VAR (var, vi)
|
|
|
497 if (var_ann (var))
|
|
|
498 dfa_stats_p->num_var_anns++;
|
|
|
499
|
|
|
500 /* Walk all the statements in the function counting references. */
|
|
|
501 FOR_EACH_BB (bb)
|
|
|
502 {
|
|
|
503 gimple_stmt_iterator si;
|
|
|
504
|
|
|
505 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
|
|
|
506 {
|
|
|
507 gimple phi = gsi_stmt (si);
|
|
|
508 dfa_stats_p->num_phis++;
|
|
|
509 dfa_stats_p->num_phi_args += gimple_phi_num_args (phi);
|
|
|
510 if (gimple_phi_num_args (phi) > dfa_stats_p->max_num_phi_args)
|
|
|
511 dfa_stats_p->max_num_phi_args = gimple_phi_num_args (phi);
|
|
|
512 }
|
|
|
513
|
|
|
514 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
|
|
|
515 {
|
|
|
516 gimple stmt = gsi_stmt (si);
|
|
|
517 dfa_stats_p->num_defs += NUM_SSA_OPERANDS (stmt, SSA_OP_DEF);
|
|
|
518 dfa_stats_p->num_uses += NUM_SSA_OPERANDS (stmt, SSA_OP_USE);
|
|
|
519 dfa_stats_p->num_vdefs += NUM_SSA_OPERANDS (stmt, SSA_OP_VDEF);
|
|
|
520 dfa_stats_p->num_vuses += NUM_SSA_OPERANDS (stmt, SSA_OP_VUSE);
|
|
|
521 }
|
|
|
522 }
|
|
|
523 }
|
|
|
524
|
|
|
525
|
|
|
526 /*---------------------------------------------------------------------------
|
|
|
527 Miscellaneous helpers
|
|
|
528 ---------------------------------------------------------------------------*/
|
|
|
529 /* Callback for walk_tree. Used to collect variables referenced in
|
|
|
530 the function. */
|
|
|
531
|
|
|
532 static tree
|
|
|
533 find_vars_r (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
|
|
|
534 {
|
|
|
535 /* If we are reading the lto info back in, we need to rescan the
|
|
|
536 referenced vars. */
|
|
|
537 if (TREE_CODE (*tp) == SSA_NAME)
|
|
|
538 add_referenced_var (SSA_NAME_VAR (*tp));
|
|
|
539
|
|
|
540 /* If T is a regular variable that the optimizers are interested
|
|
|
541 in, add it to the list of variables. */
|
|
|
542 else if (SSA_VAR_P (*tp))
|
|
|
543 add_referenced_var (*tp);
|
|
|
544
|
|
|
545 /* Type, _DECL and constant nodes have no interesting children.
|
|
|
546 Ignore them. */
|
|
|
547 else if (IS_TYPE_OR_DECL_P (*tp) || CONSTANT_CLASS_P (*tp))
|
|
|
548 *walk_subtrees = 0;
|
|
|
549
|
|
|
550 return NULL_TREE;
|
|
|
551 }
|
|
|
552
|
|
|
553 /* Lookup UID in the referenced_vars hashtable and return the associated
|
|
|
554 variable. */
|
|
|
555
|
|
|
556 tree
|
|
|
557 referenced_var_lookup (unsigned int uid)
|
|
|
558 {
|
|
|
559 tree h;
|
|
|
560 struct tree_decl_minimal in;
|
|
|
561 in.uid = uid;
|
|
|
562 h = (tree) htab_find_with_hash (gimple_referenced_vars (cfun), &in, uid);
|
|
|
563 gcc_assert (h || uid == 0);
|
|
|
564 return h;
|
|
|
565 }
|
|
|
566
|
|
|
567 /* Check if TO is in the referenced_vars hash table and insert it if not.
|
|
|
568 Return true if it required insertion. */
|
|
|
569
|
|
|
570 bool
|
|
|
571 referenced_var_check_and_insert (tree to)
|
|
|
572 {
|
|
|
573 tree h, *loc;
|
|
|
574 struct tree_decl_minimal in;
|
|
|
575 unsigned int uid = DECL_UID (to);
|
|
|
576
|
|
|
577 in.uid = uid;
|
|
|
578 h = (tree) htab_find_with_hash (gimple_referenced_vars (cfun), &in, uid);
|
|
|
579 if (h)
|
|
|
580 {
|
|
|
581 /* DECL_UID has already been entered in the table. Verify that it is
|
|
|
582 the same entry as TO. See PR 27793. */
|
|
|
583 gcc_assert (h == to);
|
|
|
584 return false;
|
|
|
585 }
|
|
|
586
|
|
|
587 loc = (tree *) htab_find_slot_with_hash (gimple_referenced_vars (cfun),
|
|
|
588 &in, uid, INSERT);
|
|
|
589 *loc = to;
|
|
|
590 return true;
|
|
|
591 }
|
|
|
592
|
|
|
593 /* Lookup VAR UID in the default_defs hashtable and return the associated
|
|
|
594 variable. */
|
|
|
595
|
|
|
596 tree
|
|
|
597 gimple_default_def (struct function *fn, tree var)
|
|
|
598 {
|
|
|
599 struct tree_decl_minimal ind;
|
|
|
600 struct tree_ssa_name in;
|
|
|
601 gcc_assert (SSA_VAR_P (var));
|
|
|
602 in.var = (tree)&ind;
|
|
|
603 ind.uid = DECL_UID (var);
|
|
|
604 return (tree) htab_find_with_hash (DEFAULT_DEFS (fn), &in, DECL_UID (var));
|
|
|
605 }
|
|
|
606
|
|
|
607 /* Insert the pair VAR's UID, DEF into the default_defs hashtable. */
|
|
|
608
|
|
|
609 void
|
|
|
610 set_default_def (tree var, tree def)
|
|
|
611 {
|
|
|
612 struct tree_decl_minimal ind;
|
|
|
613 struct tree_ssa_name in;
|
|
|
614 void **loc;
|
|
|
615
|
|
|
616 gcc_assert (SSA_VAR_P (var));
|
|
|
617 in.var = (tree)&ind;
|
|
|
618 ind.uid = DECL_UID (var);
|
|
|
619 if (!def)
|
|
|
620 {
|
|
|
621 loc = htab_find_slot_with_hash (DEFAULT_DEFS (cfun), &in,
|
|
|
622 DECL_UID (var), INSERT);
|
|
|
623 gcc_assert (*loc);
|
|
|
624 htab_remove_elt (DEFAULT_DEFS (cfun), *loc);
|
|
|
625 return;
|
|
|
626 }
|
|
|
627 gcc_assert (TREE_CODE (def) == SSA_NAME && SSA_NAME_VAR (def) == var);
|
|
|
628 loc = htab_find_slot_with_hash (DEFAULT_DEFS (cfun), &in,
|
|
|
629 DECL_UID (var), INSERT);
|
|
|
630
|
|
|
631 /* Default definition might be changed by tail call optimization. */
|
|
|
632 if (*loc)
|
|
|
633 SSA_NAME_IS_DEFAULT_DEF (*(tree *) loc) = false;
|
|
|
634 *(tree *) loc = def;
|
|
|
635
|
|
|
636 /* Mark DEF as the default definition for VAR. */
|
|
|
637 SSA_NAME_IS_DEFAULT_DEF (def) = true;
|
|
|
638 }
|
|
|
639
|
|
|
640 /* Add VAR to the list of referenced variables if it isn't already there. */
|
|
|
641
|
|
|
642 bool
|
|
|
643 add_referenced_var (tree var)
|
|
|
644 {
|
|
|
645 var_ann_t v_ann;
|
|
|
646
|
|
|
647 v_ann = get_var_ann (var);
|
|
|
648 gcc_assert (DECL_P (var));
|
|
|
649
|
|
|
650 /* Insert VAR into the referenced_vars has table if it isn't present. */
|
|
|
651 if (referenced_var_check_and_insert (var))
|
|
|
652 {
|
|
|
653 /* This is the first time we found this variable, annotate it with
|
|
|
654 attributes that are intrinsic to the variable. */
|
|
|
655
|
|
|
656 /* Tag's don't have DECL_INITIAL. */
|
|
|
657 if (MTAG_P (var))
|
|
|
658 return true;
|
|
|
659
|
|
|
660 /* Scan DECL_INITIAL for pointer variables as they may contain
|
|
|
661 address arithmetic referencing the address of other
|
|
|
662 variables.
|
|
|
663 Even non-constant initializers need to be walked, because
|
|
|
664 IPA passes might prove that their are invariant later on. */
|
|
|
665 if (DECL_INITIAL (var)
|
|
|
666 /* Initializers of external variables are not useful to the
|
|
|
667 optimizers. */
|
|
|
668 && !DECL_EXTERNAL (var))
|
|
|
669 walk_tree (&DECL_INITIAL (var), find_vars_r, NULL, 0);
|
|
|
670
|
|
|
671 return true;
|
|
|
672 }
|
|
|
673
|
|
|
674 return false;
|
|
|
675 }
|
|
|
676
|
|
|
677 /* Remove VAR from the list. */
|
|
|
678
|
|
|
679 void
|
|
|
680 remove_referenced_var (tree var)
|
|
|
681 {
|
|
|
682 var_ann_t v_ann;
|
|
|
683 struct tree_decl_minimal in;
|
|
|
684 void **loc;
|
|
|
685 unsigned int uid = DECL_UID (var);
|
|
|
686
|
|
|
687 clear_call_clobbered (var);
|
|
|
688 bitmap_clear_bit (gimple_call_used_vars (cfun), uid);
|
|
|
689 if ((v_ann = var_ann (var)))
|
|
|
690 {
|
|
|
691 /* Preserve var_anns of globals, but clear their alias info. */
|
|
|
692 if (MTAG_P (var)
|
|
|
693 || (!TREE_STATIC (var) && !DECL_EXTERNAL (var)))
|
|
|
694 {
|
|
|
695 ggc_free (v_ann);
|
|
|
696 var->base.ann = NULL;
|
|
|
697 }
|
|
|
698 else
|
|
|
699 {
|
|
|
700 v_ann->mpt = NULL_TREE;
|
|
|
701 v_ann->symbol_mem_tag = NULL_TREE;
|
|
|
702 }
|
|
|
703 }
|
|
|
704 gcc_assert (DECL_P (var));
|
|
|
705 in.uid = uid;
|
|
|
706 loc = htab_find_slot_with_hash (gimple_referenced_vars (cfun), &in, uid,
|
|
|
707 NO_INSERT);
|
|
|
708 htab_clear_slot (gimple_referenced_vars (cfun), loc);
|
|
|
709 }
|
|
|
710
|
|
|
711
|
|
|
712 /* Return the virtual variable associated to the non-scalar variable VAR. */
|
|
|
713
|
|
|
714 tree
|
|
|
715 get_virtual_var (tree var)
|
|
|
716 {
|
|
|
717 STRIP_NOPS (var);
|
|
|
718
|
|
|
719 if (TREE_CODE (var) == SSA_NAME)
|
|
|
720 var = SSA_NAME_VAR (var);
|
|
|
721
|
|
|
722 while (TREE_CODE (var) == REALPART_EXPR || TREE_CODE (var) == IMAGPART_EXPR
|
|
|
723 || handled_component_p (var))
|
|
|
724 var = TREE_OPERAND (var, 0);
|
|
|
725
|
|
|
726 /* Treating GIMPLE registers as virtual variables makes no sense.
|
|
|
727 Also complain if we couldn't extract a _DECL out of the original
|
|
|
728 expression. */
|
|
|
729 gcc_assert (SSA_VAR_P (var));
|
|
|
730 gcc_assert (!is_gimple_reg (var));
|
|
|
731
|
|
|
732 return var;
|
|
|
733 }
|
|
|
734
|
|
|
735 /* Mark all the naked symbols in STMT for SSA renaming.
|
|
|
736
|
|
|
737 NOTE: This function should only be used for brand new statements.
|
|
|
738 If the caller is modifying an existing statement, it should use the
|
|
|
739 combination push_stmt_changes/pop_stmt_changes. */
|
|
|
740
|
|
|
741 void
|
|
|
742 mark_symbols_for_renaming (gimple stmt)
|
|
|
743 {
|
|
|
744 tree op;
|
|
|
745 ssa_op_iter iter;
|
|
|
746
|
|
|
747 update_stmt (stmt);
|
|
|
748
|
|
|
749 /* Mark all the operands for renaming. */
|
|
|
750 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_OPERANDS)
|
|
|
751 if (DECL_P (op))
|
|
|
752 mark_sym_for_renaming (op);
|
|
|
753 }
|
|
|
754
|
|
|
755
|
|
|
756 /* Find all variables within the gimplified statement that were not
|
|
|
757 previously visible to the function and add them to the referenced
|
|
|
758 variables list. */
|
|
|
759
|
|
|
760 static tree
|
|
|
761 find_new_referenced_vars_1 (tree *tp, int *walk_subtrees,
|
|
|
762 void *data ATTRIBUTE_UNUSED)
|
|
|
763 {
|
|
|
764 tree t = *tp;
|
|
|
765
|
|
|
766 if (TREE_CODE (t) == VAR_DECL && !var_ann (t))
|
|
|
767 {
|
|
|
768 add_referenced_var (t);
|
|
|
769 mark_sym_for_renaming (t);
|
|
|
770 }
|
|
|
771
|
|
|
772 if (IS_TYPE_OR_DECL_P (t))
|
|
|
773 *walk_subtrees = 0;
|
|
|
774
|
|
|
775 return NULL;
|
|
|
776 }
|
|
|
777
|
|
|
778
|
|
|
779 /* Find any new referenced variables in STMT. */
|
|
|
780
|
|
|
781 void
|
|
|
782 find_new_referenced_vars (gimple stmt)
|
|
|
783 {
|
|
|
784 walk_gimple_op (stmt, find_new_referenced_vars_1, NULL);
|
|
|
785 }
|
|
|
786
|
|
|
787
|
|
|
788 /* If EXP is a handled component reference for a structure, return the
|
|
|
789 base variable. The access range is delimited by bit positions *POFFSET and
|
|
|
790 *POFFSET + *PMAX_SIZE. The access size is *PSIZE bits. If either
|
|
|
791 *PSIZE or *PMAX_SIZE is -1, they could not be determined. If *PSIZE
|
|
|
792 and *PMAX_SIZE are equal, the access is non-variable. */
|
|
|
793
|
|
|
794 tree
|
|
|
795 get_ref_base_and_extent (tree exp, HOST_WIDE_INT *poffset,
|
|
|
796 HOST_WIDE_INT *psize,
|
|
|
797 HOST_WIDE_INT *pmax_size)
|
|
|
798 {
|
|
|
799 HOST_WIDE_INT bitsize = -1;
|
|
|
800 HOST_WIDE_INT maxsize = -1;
|
|
|
801 tree size_tree = NULL_TREE;
|
|
|
802 HOST_WIDE_INT bit_offset = 0;
|
|
|
803 bool seen_variable_array_ref = false;
|
|
|
804
|
|
|
805 gcc_assert (!SSA_VAR_P (exp));
|
|
|
806
|
|
|
807 /* First get the final access size from just the outermost expression. */
|
|
|
808 if (TREE_CODE (exp) == COMPONENT_REF)
|
|
|
809 size_tree = DECL_SIZE (TREE_OPERAND (exp, 1));
|
|
|
810 else if (TREE_CODE (exp) == BIT_FIELD_REF)
|
|
|
811 size_tree = TREE_OPERAND (exp, 1);
|
|
|
812 else
|
|
|
813 {
|
|
|
814 enum machine_mode mode = TYPE_MODE (TREE_TYPE (exp));
|
|
|
815 if (mode == BLKmode)
|
|
|
816 size_tree = TYPE_SIZE (TREE_TYPE (exp));
|
|
|
817 else
|
|
|
818 bitsize = GET_MODE_BITSIZE (mode);
|
|
|
819 }
|
|
|
820 if (size_tree != NULL_TREE)
|
|
|
821 {
|
|
|
822 if (! host_integerp (size_tree, 1))
|
|
|
823 bitsize = -1;
|
|
|
824 else
|
|
|
825 bitsize = TREE_INT_CST_LOW (size_tree);
|
|
|
826 }
|
|
|
827
|
|
|
828 /* Initially, maxsize is the same as the accessed element size.
|
|
|
829 In the following it will only grow (or become -1). */
|
|
|
830 maxsize = bitsize;
|
|
|
831
|
|
|
832 /* Compute cumulative bit-offset for nested component-refs and array-refs,
|
|
|
833 and find the ultimate containing object. */
|
|
|
834 while (1)
|
|
|
835 {
|
|
|
836 switch (TREE_CODE (exp))
|
|
|
837 {
|
|
|
838 case BIT_FIELD_REF:
|
|
|
839 bit_offset += tree_low_cst (TREE_OPERAND (exp, 2), 0);
|
|
|
840 break;
|
|
|
841
|
|
|
842 case COMPONENT_REF:
|
|
|
843 {
|
|
|
844 tree field = TREE_OPERAND (exp, 1);
|
|
|
845 tree this_offset = component_ref_field_offset (exp);
|
|
|
846
|
|
|
847 if (this_offset && TREE_CODE (this_offset) == INTEGER_CST)
|
|
|
848 {
|
|
|
849 HOST_WIDE_INT hthis_offset = tree_low_cst (this_offset, 0);
|
|
|
850
|
|
|
851 hthis_offset *= BITS_PER_UNIT;
|
|
|
852 bit_offset += hthis_offset;
|
|
|
853 bit_offset += tree_low_cst (DECL_FIELD_BIT_OFFSET (field), 0);
|
|
|
854 }
|
|
|
855 else
|
|
|
856 {
|
|
|
857 tree csize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
|
|
|
858 /* We need to adjust maxsize to the whole structure bitsize.
|
|
|
859 But we can subtract any constant offset seen so far,
|
|
|
860 because that would get us out of the structure otherwise. */
|
|
|
861 if (maxsize != -1 && csize && host_integerp (csize, 1))
|
|
|
862 maxsize = TREE_INT_CST_LOW (csize) - bit_offset;
|
|
|
863 else
|
|
|
864 maxsize = -1;
|
|
|
865 }
|
|
|
866 }
|
|
|
867 break;
|
|
|
868
|
|
|
869 case ARRAY_REF:
|
|
|
870 case ARRAY_RANGE_REF:
|
|
|
871 {
|
|
|
872 tree index = TREE_OPERAND (exp, 1);
|
|
|
873 tree low_bound = array_ref_low_bound (exp);
|
|
|
874 tree unit_size = array_ref_element_size (exp);
|
|
|
875
|
|
|
876 /* If the resulting bit-offset is constant, track it. */
|
|
|
877 if (host_integerp (index, 0)
|
|
|
878 && host_integerp (low_bound, 0)
|
|
|
879 && host_integerp (unit_size, 1))
|
|
|
880 {
|
|
|
881 HOST_WIDE_INT hindex = tree_low_cst (index, 0);
|
|
|
882
|
|
|
883 hindex -= tree_low_cst (low_bound, 0);
|
|
|
884 hindex *= tree_low_cst (unit_size, 1);
|
|
|
885 hindex *= BITS_PER_UNIT;
|
|
|
886 bit_offset += hindex;
|
|
|
887
|
|
|
888 /* An array ref with a constant index up in the structure
|
|
|
889 hierarchy will constrain the size of any variable array ref
|
|
|
890 lower in the access hierarchy. */
|
|
|
891 seen_variable_array_ref = false;
|
|
|
892 }
|
|
|
893 else
|
|
|
894 {
|
|
|
895 tree asize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
|
|
|
896 /* We need to adjust maxsize to the whole array bitsize.
|
|
|
897 But we can subtract any constant offset seen so far,
|
|
|
898 because that would get us outside of the array otherwise. */
|
|
|
899 if (maxsize != -1 && asize && host_integerp (asize, 1))
|
|
|
900 maxsize = TREE_INT_CST_LOW (asize) - bit_offset;
|
|
|
901 else
|
|
|
902 maxsize = -1;
|
|
|
903
|
|
|
904 /* Remember that we have seen an array ref with a variable
|
|
|
905 index. */
|
|
|
906 seen_variable_array_ref = true;
|
|
|
907 }
|
|
|
908 }
|
|
|
909 break;
|
|
|
910
|
|
|
911 case REALPART_EXPR:
|
|
|
912 break;
|
|
|
913
|
|
|
914 case IMAGPART_EXPR:
|
|
|
915 bit_offset += bitsize;
|
|
|
916 break;
|
|
|
917
|
|
|
918 case VIEW_CONVERT_EXPR:
|
|
|
919 /* ??? We probably should give up here and bail out. */
|
|
|
920 break;
|
|
|
921
|
|
|
922 default:
|
|
|
923 goto done;
|
|
|
924 }
|
|
|
925
|
|
|
926 exp = TREE_OPERAND (exp, 0);
|
|
|
927 }
|
|
|
928 done:
|
|
|
929
|
|
|
930 /* We need to deal with variable arrays ending structures such as
|
|
|
931 struct { int length; int a[1]; } x; x.a[d]
|
|
|
932 struct { struct { int a; int b; } a[1]; } x; x.a[d].a
|
|
|
933 struct { struct { int a[1]; } a[1]; } x; x.a[0][d], x.a[d][0]
|
|
|
934 where we do not know maxsize for variable index accesses to
|
|
|
935 the array. The simplest way to conservatively deal with this
|
|
|
936 is to punt in the case that offset + maxsize reaches the
|
|
|
937 base type boundary. */
|
|
|
938 if (seen_variable_array_ref
|
|
|
939 && maxsize != -1
|
|
|
940 && host_integerp (TYPE_SIZE (TREE_TYPE (exp)), 1)
|
|
|
941 && bit_offset + maxsize
|
|
|
942 == (signed)TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (exp))))
|
|
|
943 maxsize = -1;
|
|
|
944
|
|
|
945 /* ??? Due to negative offsets in ARRAY_REF we can end up with
|
|
|
946 negative bit_offset here. We might want to store a zero offset
|
|
|
947 in this case. */
|
|
|
948 *poffset = bit_offset;
|
|
|
949 *psize = bitsize;
|
|
|
950 *pmax_size = maxsize;
|
|
|
951
|
|
|
952 return exp;
|
|
|
953 }
|
|
|
954
|
|
|
955 /* Returns true if STMT references an SSA_NAME that has
|
|
|
956 SSA_NAME_OCCURS_IN_ABNORMAL_PHI set, otherwise false. */
|
|
|
957
|
|
|
958 bool
|
|
|
959 stmt_references_abnormal_ssa_name (gimple stmt)
|
|
|
960 {
|
|
|
961 ssa_op_iter oi;
|
|
|
962 use_operand_p use_p;
|
|
|
963
|
|
|
964 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, oi, SSA_OP_USE)
|
|
|
965 {
|
|
|
966 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (use_p)))
|
|
|
967 return true;
|
|
|
968 }
|
|
|
969
|
|
|
970 return false;
|
|
|
971 }
|
|
|
972
|
|
|
973 /* Return true, if the two memory references REF1 and REF2 may alias. */
|
|
|
974
|
|
|
975 bool
|
|
|
976 refs_may_alias_p (tree ref1, tree ref2)
|
|
|
977 {
|
|
|
978 tree base1, base2;
|
|
|
979 HOST_WIDE_INT offset1 = 0, offset2 = 0;
|
|
|
980 HOST_WIDE_INT size1 = -1, size2 = -1;
|
|
|
981 HOST_WIDE_INT max_size1 = -1, max_size2 = -1;
|
|
|
982 bool strict_aliasing_applies;
|
|
|
983
|
|
|
984 gcc_assert ((SSA_VAR_P (ref1)
|
|
|
985 || handled_component_p (ref1)
|
|
|
986 || INDIRECT_REF_P (ref1)
|
|
|
987 || TREE_CODE (ref1) == TARGET_MEM_REF)
|
|
|
988 && (SSA_VAR_P (ref2)
|
|
|
989 || handled_component_p (ref2)
|
|
|
990 || INDIRECT_REF_P (ref2)
|
|
|
991 || TREE_CODE (ref2) == TARGET_MEM_REF));
|
|
|
992
|
|
|
993 /* Defer to TBAA if possible. */
|
|
|
994 if (flag_strict_aliasing
|
|
|
995 && !alias_sets_conflict_p (get_alias_set (ref1), get_alias_set (ref2)))
|
|
|
996 return false;
|
|
|
997
|
|
|
998 /* Decompose the references into their base objects and the access. */
|
|
|
999 base1 = ref1;
|
|
|
1000 if (handled_component_p (ref1))
|
|
|
1001 base1 = get_ref_base_and_extent (ref1, &offset1, &size1, &max_size1);
|
|
|
1002 base2 = ref2;
|
|
|
1003 if (handled_component_p (ref2))
|
|
|
1004 base2 = get_ref_base_and_extent (ref2, &offset2, &size2, &max_size2);
|
|
|
1005
|
|
|
1006 /* If both references are based on different variables, they cannot alias.
|
|
|
1007 If both references are based on the same variable, they cannot alias if
|
|
|
1008 the accesses do not overlap. */
|
|
|
1009 if (SSA_VAR_P (base1)
|
|
|
1010 && SSA_VAR_P (base2))
|
|
|
1011 {
|
|
|
1012 if (!operand_equal_p (base1, base2, 0))
|
|
|
1013 return false;
|
|
|
1014 return ranges_overlap_p (offset1, max_size1, offset2, max_size2);
|
|
|
1015 }
|
|
|
1016
|
|
|
1017 /* If one base is a ref-all pointer weird things are allowed. */
|
|
|
1018 strict_aliasing_applies = (flag_strict_aliasing
|
|
|
1019 && (!INDIRECT_REF_P (base1)
|
|
|
1020 || get_alias_set (base1) != 0)
|
|
|
1021 && (!INDIRECT_REF_P (base2)
|
|
|
1022 || get_alias_set (base2) != 0));
|
|
|
1023
|
|
|
1024 /* If strict aliasing applies the only way to access a scalar variable
|
|
|
1025 is through a pointer dereference or through a union (gcc extension). */
|
|
|
1026 if (strict_aliasing_applies
|
|
|
1027 && ((SSA_VAR_P (ref2)
|
|
|
1028 && !AGGREGATE_TYPE_P (TREE_TYPE (ref2))
|
|
|
1029 && !INDIRECT_REF_P (ref1)
|
|
|
1030 && TREE_CODE (TREE_TYPE (base1)) != UNION_TYPE)
|
|
|
1031 || (SSA_VAR_P (ref1)
|
|
|
1032 && !AGGREGATE_TYPE_P (TREE_TYPE (ref1))
|
|
|
1033 && !INDIRECT_REF_P (ref2)
|
|
|
1034 && TREE_CODE (TREE_TYPE (base2)) != UNION_TYPE)))
|
|
|
1035 return false;
|
|
|
1036
|
|
|
1037 /* If both references are through the same type, or if strict aliasing
|
|
|
1038 doesn't apply they are through two same pointers, they do not alias
|
|
|
1039 if the accesses do not overlap. */
|
|
|
1040 if ((strict_aliasing_applies
|
|
|
1041 && (TYPE_MAIN_VARIANT (TREE_TYPE (base1))
|
|
|
1042 == TYPE_MAIN_VARIANT (TREE_TYPE (base2))))
|
|
|
1043 || (TREE_CODE (base1) == INDIRECT_REF
|
|
|
1044 && TREE_CODE (base2) == INDIRECT_REF
|
|
|
1045 && operand_equal_p (TREE_OPERAND (base1, 0),
|
|
|
1046 TREE_OPERAND (base2, 0), 0)))
|
|
|
1047 return ranges_overlap_p (offset1, max_size1, offset2, max_size2);
|
|
|
1048
|
|
|
1049 /* If both are component references through pointers try to find a
|
|
|
1050 common base and apply offset based disambiguation. This handles
|
|
|
1051 for example
|
|
|
1052 struct A { int i; int j; } *q;
|
|
|
1053 struct B { struct A a; int k; } *p;
|
|
|
1054 disambiguating q->i and p->a.j. */
|
|
|
1055 if (strict_aliasing_applies
|
|
|
1056 && (TREE_CODE (base1) == INDIRECT_REF
|
|
|
1057 || TREE_CODE (base2) == INDIRECT_REF)
|
|
|
1058 && handled_component_p (ref1)
|
|
|
1059 && handled_component_p (ref2))
|
|
|
1060 {
|
|
|
1061 tree *refp;
|
|
|
1062 /* Now search for the type of base1 in the access path of ref2. This
|
|
|
1063 would be a common base for doing offset based disambiguation on. */
|
|
|
1064 refp = &ref2;
|
|
|
1065 while (handled_component_p (*refp)
|
|
|
1066 /* Note that the following is only conservative if there are
|
|
|
1067 never copies of types appearing as sub-structures. */
|
|
|
1068 && (TYPE_MAIN_VARIANT (TREE_TYPE (*refp))
|
|
|
1069 != TYPE_MAIN_VARIANT (TREE_TYPE (base1))))
|
|
|
1070 refp = &TREE_OPERAND (*refp, 0);
|
|
|
1071 if (TYPE_MAIN_VARIANT (TREE_TYPE (*refp))
|
|
|
1072 == TYPE_MAIN_VARIANT (TREE_TYPE (base1)))
|
|
|
1073 {
|
|
|
1074 HOST_WIDE_INT offadj, sztmp, msztmp;
|
|
|
1075 get_ref_base_and_extent (*refp, &offadj, &sztmp, &msztmp);
|
|
|
1076 offset2 -= offadj;
|
|
|
1077 return ranges_overlap_p (offset1, max_size1, offset2, max_size2);
|
|
|
1078 }
|
|
|
1079 /* The other way around. */
|
|
|
1080 refp = &ref1;
|
|
|
1081 while (handled_component_p (*refp)
|
|
|
1082 && (TYPE_MAIN_VARIANT (TREE_TYPE (*refp))
|
|
|
1083 != TYPE_MAIN_VARIANT (TREE_TYPE (base2))))
|
|
|
1084 refp = &TREE_OPERAND (*refp, 0);
|
|
|
1085 if (TYPE_MAIN_VARIANT (TREE_TYPE (*refp))
|
|
|
1086 == TYPE_MAIN_VARIANT (TREE_TYPE (base2)))
|
|
|
1087 {
|
|
|
1088 HOST_WIDE_INT offadj, sztmp, msztmp;
|
|
|
1089 get_ref_base_and_extent (*refp, &offadj, &sztmp, &msztmp);
|
|
|
1090 offset1 -= offadj;
|
|
|
1091 return ranges_overlap_p (offset1, max_size1, offset2, max_size2);
|
|
|
1092 }
|
|
|
1093 /* If we can be sure to catch all equivalent types in the search
|
|
|
1094 for the common base then we could return false here. In that
|
|
|
1095 case we would be able to disambiguate q->i and p->k. */
|
|
|
1096 }
|
|
|
1097
|
|
|
1098 return true;
|
|
|
1099 }
|
|
|
1100
|
|
|
1101 /* Given a stmt STMT that references memory, return the single stmt
|
|
|
1102 that is reached by following the VUSE -> VDEF link. Returns
|
|
|
1103 NULL_TREE, if there is no single stmt that defines all VUSEs of
|
|
|
1104 STMT.
|
|
|
1105 Note that for a stmt with a single virtual operand this may return
|
|
|
1106 a PHI node as well. Note that if all VUSEs are default definitions
|
|
|
1107 this function will return an empty statement. */
|
|
|
1108
|
|
|
1109 gimple
|
|
|
1110 get_single_def_stmt (gimple stmt)
|
|
|
1111 {
|
|
|
1112 gimple def_stmt = NULL;
|
|
|
1113 tree use;
|
|
|
1114 ssa_op_iter iter;
|
|
|
1115
|
|
|
1116 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_VIRTUAL_USES)
|
|
|
1117 {
|
|
|
1118 gimple tmp = SSA_NAME_DEF_STMT (use);
|
|
|
1119
|
|
|
1120 /* ??? This is too simplistic for multiple virtual operands
|
|
|
1121 reaching different PHI nodes of the same basic blocks or for
|
|
|
1122 reaching all default definitions. */
|
|
|
1123 if (def_stmt
|
|
|
1124 && def_stmt != tmp
|
|
|
1125 && !(gimple_nop_p (def_stmt)
|
|
|
1126 && gimple_nop_p (tmp)))
|
|
|
1127 return NULL;
|
|
|
1128
|
|
|
1129 def_stmt = tmp;
|
|
|
1130 }
|
|
|
1131
|
|
|
1132 return def_stmt;
|
|
|
1133 }
|
|
|
1134
|
|
|
1135 /* Given a PHI node of virtual operands, tries to eliminate cyclic
|
|
|
1136 reached definitions if they do not alias REF and returns the
|
|
|
1137 defining statement of the single virtual operand that flows in
|
|
|
1138 from a non-backedge. Returns NULL_TREE if such statement within
|
|
|
1139 the above conditions cannot be found. */
|
|
|
1140
|
|
|
1141 gimple
|
|
|
1142 get_single_def_stmt_from_phi (tree ref, gimple phi)
|
|
|
1143 {
|
|
|
1144 tree def_arg = NULL_TREE;
|
|
|
1145 unsigned i;
|
|
|
1146
|
|
|
1147 /* Find the single PHI argument that is not flowing in from a
|
|
|
1148 back edge and verify that the loop-carried definitions do
|
|
|
1149 not alias the reference we look for. */
|
|
|
1150 for (i = 0; i < gimple_phi_num_args (phi); ++i)
|
|
|
1151 {
|
|
|
1152 tree arg = PHI_ARG_DEF (phi, i);
|
|
|
1153 gimple def_stmt;
|
|
|
1154
|
|
|
1155 if (!(gimple_phi_arg_edge (phi, i)->flags & EDGE_DFS_BACK))
|
|
|
1156 {
|
|
|
1157 /* Multiple non-back edges? Do not try to handle this. */
|
|
|
1158 if (def_arg)
|
|
|
1159 return NULL;
|
|
|
1160 def_arg = arg;
|
|
|
1161 continue;
|
|
|
1162 }
|
|
|
1163
|
|
|
1164 /* Follow the definitions back to the original PHI node. Bail
|
|
|
1165 out once a definition is found that may alias REF. */
|
|
|
1166 def_stmt = SSA_NAME_DEF_STMT (arg);
|
|
|
1167 do
|
|
|
1168 {
|
|
|
1169 if (!is_gimple_assign (def_stmt)
|
|
|
1170 || refs_may_alias_p (ref, gimple_assign_lhs (def_stmt)))
|
|
|
1171 return NULL;
|
|
|
1172 /* ??? This will only work, reaching the PHI node again if
|
|
|
1173 there is a single virtual operand on def_stmt. */
|
|
|
1174 def_stmt = get_single_def_stmt (def_stmt);
|
|
|
1175 if (!def_stmt)
|
|
|
1176 return NULL;
|
|
|
1177 }
|
|
|
1178 while (def_stmt != phi);
|
|
|
1179 }
|
|
|
1180
|
|
|
1181 return SSA_NAME_DEF_STMT (def_arg);
|
|
|
1182 }
|
|
|
1183
|
|
|
1184 /* Return the single reference statement defining all virtual uses
|
|
|
1185 on STMT or NULL_TREE, if there are multiple defining statements.
|
|
|
1186 Take into account only definitions that alias REF if following
|
|
|
1187 back-edges when looking through a loop PHI node. */
|
|
|
1188
|
|
|
1189 gimple
|
|
|
1190 get_single_def_stmt_with_phi (tree ref, gimple stmt)
|
|
|
1191 {
|
|
|
1192 switch (NUM_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_USES))
|
|
|
1193 {
|
|
|
1194 case 0:
|
|
|
1195 gcc_unreachable ();
|
|
|
1196
|
|
|
1197 case 1:
|
|
|
1198 {
|
|
|
1199 gimple def_stmt = SSA_NAME_DEF_STMT (SINGLE_SSA_TREE_OPERAND
|
|
|
1200 (stmt, SSA_OP_VIRTUAL_USES));
|
|
|
1201 /* We can handle lookups over PHI nodes only for a single
|
|
|
1202 virtual operand. */
|
|
|
1203 if (gimple_code (def_stmt) == GIMPLE_PHI)
|
|
|
1204 return get_single_def_stmt_from_phi (ref, def_stmt);
|
|
|
1205 return def_stmt;
|
|
|
1206 }
|
|
|
1207
|
|
|
1208 default:
|
|
|
1209 return get_single_def_stmt (stmt);
|
|
|
1210 }
|
|
|
1211 }
|
