]>
Commit | Line | Data |
---|---|---|
6de9cd9a | 1 | /* Alias analysis for trees. |
7f9e6d2a | 2 | Copyright (C) 2004, 2005 Free Software Foundation, Inc. |
6de9cd9a DN |
3 | Contributed by Diego Novillo <dnovillo@redhat.com> |
4 | ||
5 | This file is part of GCC. | |
6 | ||
7 | GCC is free software; you can redistribute it and/or modify | |
8 | it under the terms of the GNU General Public License as published by | |
9 | the Free Software Foundation; either version 2, or (at your option) | |
10 | any later version. | |
11 | ||
12 | GCC is distributed in the hope that it will be useful, | |
13 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
14 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
15 | GNU General Public License for more details. | |
16 | ||
17 | You should have received a copy of the GNU General Public License | |
18 | along with GCC; see the file COPYING. If not, write to | |
366ccddb KC |
19 | the Free Software Foundation, 51 Franklin Street, Fifth Floor, |
20 | Boston, MA 02110-1301, USA. */ | |
6de9cd9a DN |
21 | |
22 | #include "config.h" | |
23 | #include "system.h" | |
24 | #include "coretypes.h" | |
25 | #include "tm.h" | |
26 | #include "tree.h" | |
27 | #include "rtl.h" | |
28 | #include "tm_p.h" | |
29 | #include "hard-reg-set.h" | |
30 | #include "basic-block.h" | |
31 | #include "timevar.h" | |
32 | #include "expr.h" | |
33 | #include "ggc.h" | |
34 | #include "langhooks.h" | |
35 | #include "flags.h" | |
36 | #include "function.h" | |
37 | #include "diagnostic.h" | |
38 | #include "tree-dump.h" | |
eadf906f | 39 | #include "tree-gimple.h" |
6de9cd9a DN |
40 | #include "tree-flow.h" |
41 | #include "tree-inline.h" | |
6de9cd9a | 42 | #include "tree-pass.h" |
e8ca4159 | 43 | #include "tree-ssa-structalias.h" |
6de9cd9a DN |
44 | #include "convert.h" |
45 | #include "params.h" | |
ea900239 | 46 | #include "ipa-type-escape.h" |
c75ab022 | 47 | #include "vec.h" |
a3648cfc DB |
48 | #include "bitmap.h" |
49 | ||
a3648cfc DB |
50 | /* Obstack used to hold grouping bitmaps and other temporary bitmaps used by |
51 | aliasing */ | |
52 | static bitmap_obstack alias_obstack; | |
6de9cd9a | 53 | |
90c1d75a DN |
54 | /* 'true' after aliases have been computed (see compute_may_aliases). */ |
55 | bool aliases_computed_p; | |
6de9cd9a DN |
56 | |
57 | /* Structure to map a variable to its alias set and keep track of the | |
58 | virtual operands that will be needed to represent it. */ | |
59 | struct alias_map_d | |
60 | { | |
61 | /* Variable and its alias set. */ | |
62 | tree var; | |
63 | HOST_WIDE_INT set; | |
64 | ||
65 | /* Total number of virtual operands that will be needed to represent | |
66 | all the aliases of VAR. */ | |
67 | long total_alias_vops; | |
68 | ||
69 | /* Nonzero if the aliases for this memory tag have been grouped | |
70 | already. Used in group_aliases. */ | |
71 | unsigned int grouped_p : 1; | |
72 | ||
73 | /* Set of variables aliased with VAR. This is the exact same | |
74 | information contained in VAR_ANN (VAR)->MAY_ALIASES, but in | |
75 | bitmap form to speed up alias grouping. */ | |
a3648cfc | 76 | bitmap may_aliases; |
6de9cd9a DN |
77 | }; |
78 | ||
79 | ||
6de9cd9a DN |
80 | /* Counters used to display statistics on alias analysis. */ |
81 | struct alias_stats_d | |
82 | { | |
83 | unsigned int alias_queries; | |
84 | unsigned int alias_mayalias; | |
85 | unsigned int alias_noalias; | |
86 | unsigned int simple_queries; | |
87 | unsigned int simple_resolved; | |
88 | unsigned int tbaa_queries; | |
89 | unsigned int tbaa_resolved; | |
ea900239 DB |
90 | unsigned int structnoaddress_queries; |
91 | unsigned int structnoaddress_resolved; | |
6de9cd9a DN |
92 | }; |
93 | ||
94 | ||
95 | /* Local variables. */ | |
96 | static struct alias_stats_d alias_stats; | |
97 | ||
98 | /* Local functions. */ | |
99 | static void compute_flow_insensitive_aliasing (struct alias_info *); | |
100 | static void dump_alias_stats (FILE *); | |
ea900239 | 101 | static bool may_alias_p (tree, HOST_WIDE_INT, tree, HOST_WIDE_INT, bool); |
6de9cd9a DN |
102 | static tree create_memory_tag (tree type, bool is_type_tag); |
103 | static tree get_tmt_for (tree, struct alias_info *); | |
104 | static tree get_nmt_for (tree); | |
105 | static void add_may_alias (tree, tree); | |
53b4bf74 | 106 | static void replace_may_alias (tree, size_t, tree); |
6de9cd9a DN |
107 | static struct alias_info *init_alias_info (void); |
108 | static void delete_alias_info (struct alias_info *); | |
6de9cd9a DN |
109 | static void compute_flow_sensitive_aliasing (struct alias_info *); |
110 | static void setup_pointers_and_addressables (struct alias_info *); | |
6de9cd9a | 111 | static void create_global_var (void); |
6de9cd9a DN |
112 | static void maybe_create_global_var (struct alias_info *ai); |
113 | static void group_aliases (struct alias_info *); | |
9ae2a5d1 | 114 | static void set_pt_anything (tree ptr); |
6de9cd9a DN |
115 | |
116 | /* Global declarations. */ | |
117 | ||
118 | /* Call clobbered variables in the function. If bit I is set, then | |
119 | REFERENCED_VARS (I) is call-clobbered. */ | |
120 | bitmap call_clobbered_vars; | |
121 | ||
a6d02559 | 122 | /* Addressable variables in the function. If bit I is set, then |
ee536902 DN |
123 | REFERENCED_VARS (I) has had its address taken. Note that |
124 | CALL_CLOBBERED_VARS and ADDRESSABLE_VARS are not related. An | |
125 | addressable variable is not necessarily call-clobbered (e.g., a | |
126 | local addressable whose address does not escape) and not all | |
127 | call-clobbered variables are addressable (e.g., a local static | |
128 | variable). */ | |
a6d02559 DN |
129 | bitmap addressable_vars; |
130 | ||
6de9cd9a DN |
131 | /* When the program has too many call-clobbered variables and call-sites, |
132 | this variable is used to represent the clobbering effects of function | |
133 | calls. In these cases, all the call clobbered variables in the program | |
134 | are forced to alias this variable. This reduces compile times by not | |
a32b97a2 | 135 | having to keep track of too many V_MAY_DEF expressions at call sites. */ |
6de9cd9a DN |
136 | tree global_var; |
137 | ||
138 | ||
139 | /* Compute may-alias information for every variable referenced in function | |
140 | FNDECL. | |
141 | ||
142 | Alias analysis proceeds in 3 main phases: | |
143 | ||
144 | 1- Points-to and escape analysis. | |
145 | ||
146 | This phase walks the use-def chains in the SSA web looking for three | |
147 | things: | |
148 | ||
149 | * Assignments of the form P_i = &VAR | |
150 | * Assignments of the form P_i = malloc() | |
151 | * Pointers and ADDR_EXPR that escape the current function. | |
152 | ||
153 | The concept of 'escaping' is the same one used in the Java world. When | |
154 | a pointer or an ADDR_EXPR escapes, it means that it has been exposed | |
155 | outside of the current function. So, assignment to global variables, | |
406eab99 RK |
156 | function arguments and returning a pointer are all escape sites, as are |
157 | conversions between pointers and integers. | |
6de9cd9a DN |
158 | |
159 | This is where we are currently limited. Since not everything is renamed | |
160 | into SSA, we lose track of escape properties when a pointer is stashed | |
161 | inside a field in a structure, for instance. In those cases, we are | |
162 | assuming that the pointer does escape. | |
163 | ||
164 | We use escape analysis to determine whether a variable is | |
165 | call-clobbered. Simply put, if an ADDR_EXPR escapes, then the variable | |
166 | is call-clobbered. If a pointer P_i escapes, then all the variables | |
167 | pointed-to by P_i (and its memory tag) also escape. | |
168 | ||
169 | 2- Compute flow-sensitive aliases | |
170 | ||
171 | We have two classes of memory tags. Memory tags associated with the | |
172 | pointed-to data type of the pointers in the program. These tags are | |
173 | called "type memory tag" (TMT). The other class are those associated | |
174 | with SSA_NAMEs, called "name memory tag" (NMT). The basic idea is that | |
175 | when adding operands for an INDIRECT_REF *P_i, we will first check | |
176 | whether P_i has a name tag, if it does we use it, because that will have | |
177 | more precise aliasing information. Otherwise, we use the standard type | |
178 | tag. | |
179 | ||
180 | In this phase, we go through all the pointers we found in points-to | |
181 | analysis and create alias sets for the name memory tags associated with | |
182 | each pointer P_i. If P_i escapes, we mark call-clobbered the variables | |
183 | it points to and its tag. | |
184 | ||
185 | ||
186 | 3- Compute flow-insensitive aliases | |
187 | ||
188 | This pass will compare the alias set of every type memory tag and every | |
189 | addressable variable found in the program. Given a type memory tag TMT | |
190 | and an addressable variable V. If the alias sets of TMT and V conflict | |
191 | (as computed by may_alias_p), then V is marked as an alias tag and added | |
192 | to the alias set of TMT. | |
193 | ||
194 | For instance, consider the following function: | |
195 | ||
196 | foo (int i) | |
197 | { | |
4244df06 | 198 | int *p, a, b; |
6de9cd9a DN |
199 | |
200 | if (i > 10) | |
201 | p = &a; | |
202 | else | |
4244df06 | 203 | p = &b; |
6de9cd9a DN |
204 | |
205 | *p = 3; | |
6de9cd9a DN |
206 | a = b + 2; |
207 | return *p; | |
208 | } | |
209 | ||
210 | After aliasing analysis has finished, the type memory tag for pointer | |
211 | 'p' will have two aliases, namely variables 'a' and 'b'. Every time | |
212 | pointer 'p' is dereferenced, we want to mark the operation as a | |
213 | potential reference to 'a' and 'b'. | |
214 | ||
215 | foo (int i) | |
216 | { | |
217 | int *p, a, b; | |
218 | ||
219 | if (i_2 > 10) | |
220 | p_4 = &a; | |
221 | else | |
222 | p_6 = &b; | |
223 | # p_1 = PHI <p_4(1), p_6(2)>; | |
224 | ||
a32b97a2 BB |
225 | # a_7 = V_MAY_DEF <a_3>; |
226 | # b_8 = V_MAY_DEF <b_5>; | |
6de9cd9a DN |
227 | *p_1 = 3; |
228 | ||
a32b97a2 | 229 | # a_9 = V_MAY_DEF <a_7> |
6de9cd9a DN |
230 | # VUSE <b_8> |
231 | a_9 = b_8 + 2; | |
232 | ||
233 | # VUSE <a_9>; | |
234 | # VUSE <b_8>; | |
235 | return *p_1; | |
236 | } | |
237 | ||
238 | In certain cases, the list of may aliases for a pointer may grow too | |
239 | large. This may cause an explosion in the number of virtual operands | |
240 | inserted in the code. Resulting in increased memory consumption and | |
241 | compilation time. | |
242 | ||
243 | When the number of virtual operands needed to represent aliased | |
244 | loads and stores grows too large (configurable with @option{--param | |
245 | max-aliased-vops}), alias sets are grouped to avoid severe | |
246 | compile-time slow downs and memory consumption. See group_aliases. */ | |
247 | ||
248 | static void | |
249 | compute_may_aliases (void) | |
250 | { | |
251 | struct alias_info *ai; | |
252 | ||
253 | memset (&alias_stats, 0, sizeof (alias_stats)); | |
254 | ||
255 | /* Initialize aliasing information. */ | |
256 | ai = init_alias_info (); | |
257 | ||
258 | /* For each pointer P_i, determine the sets of variables that P_i may | |
259 | point-to. For every addressable variable V, determine whether the | |
260 | address of V escapes the current function, making V call-clobbered | |
261 | (i.e., whether &V is stored in a global variable or if its passed as a | |
262 | function call argument). */ | |
e8ca4159 | 263 | compute_points_to_sets (ai); |
6de9cd9a DN |
264 | |
265 | /* Collect all pointers and addressable variables, compute alias sets, | |
266 | create memory tags for pointers and promote variables whose address is | |
267 | not needed anymore. */ | |
268 | setup_pointers_and_addressables (ai); | |
269 | ||
270 | /* Compute flow-sensitive, points-to based aliasing for all the name | |
271 | memory tags. Note that this pass needs to be done before flow | |
272 | insensitive analysis because it uses the points-to information | |
273 | gathered before to mark call-clobbered type tags. */ | |
274 | compute_flow_sensitive_aliasing (ai); | |
275 | ||
276 | /* Compute type-based flow-insensitive aliasing for all the type | |
277 | memory tags. */ | |
278 | compute_flow_insensitive_aliasing (ai); | |
279 | ||
280 | /* If the program has too many call-clobbered variables and/or function | |
281 | calls, create .GLOBAL_VAR and use it to model call-clobbering | |
282 | semantics at call sites. This reduces the number of virtual operands | |
283 | considerably, improving compile times at the expense of lost | |
284 | aliasing precision. */ | |
285 | maybe_create_global_var (ai); | |
286 | ||
287 | /* Debugging dumps. */ | |
288 | if (dump_file) | |
289 | { | |
290 | dump_referenced_vars (dump_file); | |
291 | if (dump_flags & TDF_STATS) | |
292 | dump_alias_stats (dump_file); | |
293 | dump_points_to_info (dump_file); | |
294 | dump_alias_info (dump_file); | |
295 | } | |
296 | ||
297 | /* Deallocate memory used by aliasing data structures. */ | |
298 | delete_alias_info (ai); | |
f430bae8 AM |
299 | |
300 | { | |
301 | block_stmt_iterator bsi; | |
302 | basic_block bb; | |
303 | FOR_EACH_BB (bb) | |
304 | { | |
305 | for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) | |
306 | { | |
307 | update_stmt_if_modified (bsi_stmt (bsi)); | |
308 | } | |
309 | } | |
310 | } | |
311 | ||
6de9cd9a DN |
312 | } |
313 | ||
314 | struct tree_opt_pass pass_may_alias = | |
315 | { | |
316 | "alias", /* name */ | |
317 | NULL, /* gate */ | |
318 | compute_may_aliases, /* execute */ | |
319 | NULL, /* sub */ | |
320 | NULL, /* next */ | |
321 | 0, /* static_pass_number */ | |
322 | TV_TREE_MAY_ALIAS, /* tv_id */ | |
0a050485 | 323 | PROP_cfg | PROP_ssa, /* properties_required */ |
c1b763fa | 324 | PROP_alias, /* properties_provided */ |
6de9cd9a DN |
325 | 0, /* properties_destroyed */ |
326 | 0, /* todo_flags_start */ | |
0bca51f0 | 327 | TODO_dump_func | TODO_update_ssa |
7f9e6d2a AP |
328 | | TODO_ggc_collect | TODO_verify_ssa |
329 | | TODO_verify_stmts, /* todo_flags_finish */ | |
9f8628ba | 330 | 0 /* letter */ |
6de9cd9a DN |
331 | }; |
332 | ||
a1d13fa1 DN |
333 | |
334 | /* Data structure used to count the number of dereferences to PTR | |
335 | inside an expression. */ | |
336 | struct count_ptr_d | |
337 | { | |
338 | tree ptr; | |
339 | unsigned count; | |
340 | }; | |
341 | ||
342 | ||
343 | /* Helper for count_uses_and_derefs. Called by walk_tree to look for | |
344 | (ALIGN/MISALIGNED_)INDIRECT_REF nodes for the pointer passed in DATA. */ | |
345 | ||
346 | static tree | |
17c7e33e | 347 | count_ptr_derefs (tree *tp, int *walk_subtrees, void *data) |
a1d13fa1 DN |
348 | { |
349 | struct count_ptr_d *count_p = (struct count_ptr_d *) data; | |
350 | ||
17c7e33e DN |
351 | /* Do not walk inside ADDR_EXPR nodes. In the expression &ptr->fld, |
352 | pointer 'ptr' is *not* dereferenced, it is simply used to compute | |
353 | the address of 'fld' as 'ptr + offsetof(fld)'. */ | |
354 | if (TREE_CODE (*tp) == ADDR_EXPR) | |
355 | { | |
356 | *walk_subtrees = 0; | |
357 | return NULL_TREE; | |
358 | } | |
359 | ||
a1d13fa1 DN |
360 | if (INDIRECT_REF_P (*tp) && TREE_OPERAND (*tp, 0) == count_p->ptr) |
361 | count_p->count++; | |
362 | ||
363 | return NULL_TREE; | |
364 | } | |
365 | ||
366 | ||
367 | /* Count the number of direct and indirect uses for pointer PTR in | |
368 | statement STMT. The two counts are stored in *NUM_USES_P and | |
369 | *NUM_DEREFS_P respectively. *IS_STORE_P is set to 'true' if at | |
370 | least one of those dereferences is a store operation. */ | |
371 | ||
0bca51f0 | 372 | void |
a1d13fa1 DN |
373 | count_uses_and_derefs (tree ptr, tree stmt, unsigned *num_uses_p, |
374 | unsigned *num_derefs_p, bool *is_store) | |
375 | { | |
376 | ssa_op_iter i; | |
377 | tree use; | |
378 | ||
379 | *num_uses_p = 0; | |
380 | *num_derefs_p = 0; | |
381 | *is_store = false; | |
382 | ||
383 | /* Find out the total number of uses of PTR in STMT. */ | |
384 | FOR_EACH_SSA_TREE_OPERAND (use, stmt, i, SSA_OP_USE) | |
385 | if (use == ptr) | |
386 | (*num_uses_p)++; | |
387 | ||
388 | /* Now count the number of indirect references to PTR. This is | |
389 | truly awful, but we don't have much choice. There are no parent | |
390 | pointers inside INDIRECT_REFs, so an expression like | |
391 | '*x_1 = foo (x_1, *x_1)' needs to be traversed piece by piece to | |
392 | find all the indirect and direct uses of x_1 inside. The only | |
393 | shortcut we can take is the fact that GIMPLE only allows | |
394 | INDIRECT_REFs inside the expressions below. */ | |
395 | if (TREE_CODE (stmt) == MODIFY_EXPR | |
396 | || (TREE_CODE (stmt) == RETURN_EXPR | |
397 | && TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR) | |
398 | || TREE_CODE (stmt) == ASM_EXPR | |
399 | || TREE_CODE (stmt) == CALL_EXPR) | |
400 | { | |
401 | tree lhs, rhs; | |
402 | ||
403 | if (TREE_CODE (stmt) == MODIFY_EXPR) | |
404 | { | |
405 | lhs = TREE_OPERAND (stmt, 0); | |
406 | rhs = TREE_OPERAND (stmt, 1); | |
407 | } | |
408 | else if (TREE_CODE (stmt) == RETURN_EXPR) | |
409 | { | |
410 | tree e = TREE_OPERAND (stmt, 0); | |
411 | lhs = TREE_OPERAND (e, 0); | |
412 | rhs = TREE_OPERAND (e, 1); | |
413 | } | |
414 | else if (TREE_CODE (stmt) == ASM_EXPR) | |
415 | { | |
416 | lhs = ASM_OUTPUTS (stmt); | |
417 | rhs = ASM_INPUTS (stmt); | |
418 | } | |
419 | else | |
420 | { | |
421 | lhs = NULL_TREE; | |
422 | rhs = stmt; | |
423 | } | |
424 | ||
c529e0fe | 425 | if (lhs && (TREE_CODE (lhs) == TREE_LIST || EXPR_P (lhs))) |
a1d13fa1 DN |
426 | { |
427 | struct count_ptr_d count; | |
428 | count.ptr = ptr; | |
429 | count.count = 0; | |
430 | walk_tree (&lhs, count_ptr_derefs, &count, NULL); | |
431 | *is_store = true; | |
432 | *num_derefs_p = count.count; | |
433 | } | |
434 | ||
c529e0fe | 435 | if (rhs && (TREE_CODE (rhs) == TREE_LIST || EXPR_P (rhs))) |
a1d13fa1 DN |
436 | { |
437 | struct count_ptr_d count; | |
438 | count.ptr = ptr; | |
439 | count.count = 0; | |
440 | walk_tree (&rhs, count_ptr_derefs, &count, NULL); | |
441 | *num_derefs_p += count.count; | |
442 | } | |
443 | } | |
444 | ||
445 | gcc_assert (*num_uses_p >= *num_derefs_p); | |
446 | } | |
447 | ||
6de9cd9a DN |
448 | /* Initialize the data structures used for alias analysis. */ |
449 | ||
450 | static struct alias_info * | |
451 | init_alias_info (void) | |
452 | { | |
453 | struct alias_info *ai; | |
a3648cfc DB |
454 | referenced_var_iterator rvi; |
455 | tree var; | |
6de9cd9a | 456 | |
a3648cfc | 457 | bitmap_obstack_initialize (&alias_obstack); |
6de9cd9a | 458 | ai = xcalloc (1, sizeof (struct alias_info)); |
d0ce8e4c SB |
459 | ai->ssa_names_visited = sbitmap_alloc (num_ssa_names); |
460 | sbitmap_zero (ai->ssa_names_visited); | |
6de9cd9a | 461 | VARRAY_TREE_INIT (ai->processed_ptrs, 50, "processed_ptrs"); |
a3648cfc DB |
462 | ai->written_vars = BITMAP_ALLOC (&alias_obstack); |
463 | ai->dereferenced_ptrs_store = BITMAP_ALLOC (&alias_obstack); | |
464 | ai->dereferenced_ptrs_load = BITMAP_ALLOC (&alias_obstack); | |
6de9cd9a | 465 | |
53b4bf74 DN |
466 | /* If aliases have been computed before, clear existing information. */ |
467 | if (aliases_computed_p) | |
468 | { | |
3cd8c58a | 469 | unsigned i; |
a912a223 | 470 | |
53b4bf74 DN |
471 | /* Similarly, clear the set of addressable variables. In this |
472 | case, we can just clear the set because addressability is | |
473 | only computed here. */ | |
474 | bitmap_clear (addressable_vars); | |
475 | ||
476 | /* Clear flow-insensitive alias information from each symbol. */ | |
a3648cfc | 477 | FOR_EACH_REFERENCED_VAR (var, rvi) |
53b4bf74 | 478 | { |
90e34bd6 | 479 | var_ann_t ann = var_ann (var); |
a3648cfc | 480 | |
53b4bf74 | 481 | ann->is_alias_tag = 0; |
c1b763fa | 482 | ann->may_aliases = NULL; |
a3648cfc | 483 | NUM_REFERENCES_CLEAR (ann); |
90e34bd6 DN |
484 | |
485 | /* Since we are about to re-discover call-clobbered | |
486 | variables, clear the call-clobbered flag. Variables that | |
487 | are intrinsically call-clobbered (globals, local statics, | |
488 | etc) will not be marked by the aliasing code, so we can't | |
c75ab022 DB |
489 | remove them from CALL_CLOBBERED_VARS. |
490 | ||
491 | NB: STRUCT_FIELDS are still call clobbered if they are for | |
492 | a global variable, so we *don't* clear their call clobberedness | |
493 | just because they are tags, though we will clear it if they | |
494 | aren't for global variables. */ | |
495 | if (ann->mem_tag_kind == NAME_TAG | |
496 | || ann->mem_tag_kind == TYPE_TAG | |
497 | || !is_global_var (var)) | |
90e34bd6 | 498 | clear_call_clobbered (var); |
53b4bf74 DN |
499 | } |
500 | ||
501 | /* Clear flow-sensitive points-to information from each SSA name. */ | |
502 | for (i = 1; i < num_ssa_names; i++) | |
503 | { | |
504 | tree name = ssa_name (i); | |
505 | ||
8b547e44 | 506 | if (!name || !POINTER_TYPE_P (TREE_TYPE (name))) |
53b4bf74 DN |
507 | continue; |
508 | ||
509 | if (SSA_NAME_PTR_INFO (name)) | |
510 | { | |
511 | struct ptr_info_def *pi = SSA_NAME_PTR_INFO (name); | |
512 | ||
513 | /* Clear all the flags but keep the name tag to | |
514 | avoid creating new temporaries unnecessarily. If | |
515 | this pointer is found to point to a subset or | |
516 | superset of its former points-to set, then a new | |
517 | tag will need to be created in create_name_tags. */ | |
518 | pi->pt_anything = 0; | |
a1d13fa1 | 519 | pi->pt_null = 0; |
53b4bf74 DN |
520 | pi->value_escapes_p = 0; |
521 | pi->is_dereferenced = 0; | |
522 | if (pi->pt_vars) | |
523 | bitmap_clear (pi->pt_vars); | |
53b4bf74 DN |
524 | } |
525 | } | |
526 | } | |
527 | ||
c1b763fa DN |
528 | /* Next time, we will need to reset alias information. */ |
529 | aliases_computed_p = true; | |
530 | ||
6de9cd9a DN |
531 | return ai; |
532 | } | |
533 | ||
534 | ||
535 | /* Deallocate memory used by alias analysis. */ | |
536 | ||
537 | static void | |
538 | delete_alias_info (struct alias_info *ai) | |
539 | { | |
540 | size_t i; | |
a3648cfc DB |
541 | referenced_var_iterator rvi; |
542 | tree var; | |
6de9cd9a | 543 | |
d0ce8e4c | 544 | sbitmap_free (ai->ssa_names_visited); |
6de9cd9a | 545 | ai->processed_ptrs = NULL; |
6de9cd9a DN |
546 | |
547 | for (i = 0; i < ai->num_addressable_vars; i++) | |
a3648cfc DB |
548 | free (ai->addressable_vars[i]); |
549 | ||
550 | FOR_EACH_REFERENCED_VAR(var, rvi) | |
6de9cd9a | 551 | { |
a3648cfc DB |
552 | var_ann_t ann = var_ann (var); |
553 | NUM_REFERENCES_CLEAR (ann); | |
6de9cd9a | 554 | } |
a3648cfc | 555 | |
6de9cd9a DN |
556 | free (ai->addressable_vars); |
557 | ||
558 | for (i = 0; i < ai->num_pointers; i++) | |
a3648cfc | 559 | free (ai->pointers[i]); |
6de9cd9a DN |
560 | free (ai->pointers); |
561 | ||
8bdbfff5 NS |
562 | BITMAP_FREE (ai->written_vars); |
563 | BITMAP_FREE (ai->dereferenced_ptrs_store); | |
564 | BITMAP_FREE (ai->dereferenced_ptrs_load); | |
a3648cfc | 565 | bitmap_obstack_release (&alias_obstack); |
6de9cd9a | 566 | free (ai); |
6de9cd9a | 567 | |
e8ca4159 | 568 | delete_points_to_sets (); |
6de9cd9a DN |
569 | } |
570 | ||
d8903b30 DN |
571 | /* Create name tags for all the pointers that have been dereferenced. |
572 | We only create a name tag for a pointer P if P is found to point to | |
573 | a set of variables (so that we can alias them to *P) or if it is | |
574 | the result of a call to malloc (which means that P cannot point to | |
575 | anything else nor alias any other variable). | |
576 | ||
577 | If two pointers P and Q point to the same set of variables, they | |
578 | are assigned the same name tag. */ | |
579 | ||
580 | static void | |
a4f91294 | 581 | create_name_tags (void) |
d8903b30 DN |
582 | { |
583 | size_t i; | |
fd312e90 DB |
584 | VEC (tree, heap) *with_ptvars = NULL; |
585 | tree ptr; | |
d8903b30 | 586 | |
fd312e90 | 587 | /* Collect the list of pointers with a non-empty points to set. */ |
a4f91294 | 588 | for (i = 1; i < num_ssa_names; i++) |
d8903b30 | 589 | { |
a4f91294 DN |
590 | tree ptr = ssa_name (i); |
591 | struct ptr_info_def *pi; | |
592 | ||
593 | if (!ptr | |
594 | || !POINTER_TYPE_P (TREE_TYPE (ptr)) | |
595 | || !SSA_NAME_PTR_INFO (ptr)) | |
596 | continue; | |
597 | ||
598 | pi = SSA_NAME_PTR_INFO (ptr); | |
d8903b30 | 599 | |
50dc9a88 | 600 | if (pi->pt_anything || !pi->is_dereferenced) |
9ae2a5d1 DN |
601 | { |
602 | /* No name tags for pointers that have not been | |
50dc9a88 | 603 | dereferenced or point to an arbitrary location. */ |
9ae2a5d1 DN |
604 | pi->name_mem_tag = NULL_TREE; |
605 | continue; | |
606 | } | |
d8903b30 | 607 | |
fd312e90 DB |
608 | /* Set pt_anything on the pointers without pt_vars filled in so |
609 | that they are assigned a type tag. */ | |
610 | ||
611 | if (pi->pt_vars && !bitmap_empty_p (pi->pt_vars)) | |
612 | VEC_safe_push (tree, heap, with_ptvars, ptr); | |
613 | else | |
614 | set_pt_anything (ptr); | |
615 | } | |
616 | ||
617 | /* If we didn't find any pointers with pt_vars set, we're done. */ | |
618 | if (!with_ptvars) | |
619 | return; | |
620 | ||
621 | /* Now go through the pointers with pt_vars, and find a name tag | |
622 | with the same pt_vars as this pointer, or create one if one | |
623 | doesn't exist. */ | |
624 | for (i = 0; VEC_iterate (tree, with_ptvars, i, ptr); i++) | |
625 | { | |
626 | struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr); | |
627 | size_t j; | |
628 | tree ptr2; | |
629 | tree old_name_tag = pi->name_mem_tag; | |
630 | ||
631 | /* If PTR points to a set of variables, check if we don't | |
632 | have another pointer Q with the same points-to set before | |
633 | creating a tag. If so, use Q's tag instead of creating a | |
634 | new one. | |
635 | ||
636 | This is important for not creating unnecessary symbols | |
637 | and also for copy propagation. If we ever need to | |
638 | propagate PTR into Q or vice-versa, we would run into | |
639 | problems if they both had different name tags because | |
640 | they would have different SSA version numbers (which | |
641 | would force us to take the name tags in and out of SSA). */ | |
642 | for (j = 0; j < i && VEC_iterate (tree, with_ptvars, j, ptr2); j++) | |
d8903b30 | 643 | { |
fd312e90 DB |
644 | struct ptr_info_def *qi = SSA_NAME_PTR_INFO (ptr2); |
645 | ||
646 | if (bitmap_equal_p (pi->pt_vars, qi->pt_vars)) | |
d8903b30 | 647 | { |
fd312e90 DB |
648 | pi->name_mem_tag = qi->name_mem_tag; |
649 | break; | |
d8903b30 | 650 | } |
d8903b30 | 651 | } |
fd312e90 DB |
652 | |
653 | /* If we didn't find a pointer with the same points-to set | |
654 | as PTR, create a new name tag if needed. */ | |
655 | if (pi->name_mem_tag == NULL_TREE) | |
656 | pi->name_mem_tag = get_nmt_for (ptr); | |
657 | ||
658 | /* If the new name tag computed for PTR is different than | |
659 | the old name tag that it used to have, then the old tag | |
660 | needs to be removed from the IL, so we mark it for | |
661 | renaming. */ | |
662 | if (old_name_tag && old_name_tag != pi->name_mem_tag) | |
663 | mark_sym_for_renaming (old_name_tag); | |
664 | ||
38e05395 | 665 | TREE_THIS_VOLATILE (pi->name_mem_tag) |
fd312e90 DB |
666 | |= TREE_THIS_VOLATILE (TREE_TYPE (TREE_TYPE (ptr))); |
667 | ||
d8903b30 | 668 | /* Mark the new name tag for renaming. */ |
0bca51f0 | 669 | mark_sym_for_renaming (pi->name_mem_tag); |
d8903b30 | 670 | } |
fd312e90 DB |
671 | |
672 | VEC_free (tree, heap, with_ptvars); | |
d8903b30 DN |
673 | } |
674 | ||
675 | ||
6de9cd9a DN |
676 | /* For every pointer P_i in AI->PROCESSED_PTRS, create may-alias sets for |
677 | the name memory tag (NMT) associated with P_i. If P_i escapes, then its | |
678 | name tag and the variables it points-to are call-clobbered. Finally, if | |
679 | P_i escapes and we could not determine where it points to, then all the | |
680 | variables in the same alias set as *P_i are marked call-clobbered. This | |
681 | is necessary because we must assume that P_i may take the address of any | |
682 | variable in the same alias set. */ | |
683 | ||
684 | static void | |
685 | compute_flow_sensitive_aliasing (struct alias_info *ai) | |
686 | { | |
687 | size_t i; | |
910fdc79 DB |
688 | |
689 | for (i = 0; i < VARRAY_ACTIVE_SIZE (ai->processed_ptrs); i++) | |
690 | { | |
691 | tree ptr = VARRAY_TREE (ai->processed_ptrs, i); | |
e8ca4159 DN |
692 | if (!find_what_p_points_to (ptr)) |
693 | set_pt_anything (ptr); | |
910fdc79 | 694 | } |
a4f91294 DN |
695 | |
696 | create_name_tags (); | |
d8903b30 | 697 | |
6de9cd9a DN |
698 | for (i = 0; i < VARRAY_ACTIVE_SIZE (ai->processed_ptrs); i++) |
699 | { | |
3cd8c58a | 700 | unsigned j; |
6de9cd9a | 701 | tree ptr = VARRAY_TREE (ai->processed_ptrs, i); |
313679b0 | 702 | struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr); |
6de9cd9a | 703 | var_ann_t v_ann = var_ann (SSA_NAME_VAR (ptr)); |
87c476a2 | 704 | bitmap_iterator bi; |
6de9cd9a | 705 | |
313679b0 | 706 | if (pi->value_escapes_p || pi->pt_anything) |
6de9cd9a DN |
707 | { |
708 | /* If PTR escapes or may point to anything, then its associated | |
50dc9a88 | 709 | memory tags and pointed-to variables are call-clobbered. */ |
313679b0 DN |
710 | if (pi->name_mem_tag) |
711 | mark_call_clobbered (pi->name_mem_tag); | |
6de9cd9a DN |
712 | |
713 | if (v_ann->type_mem_tag) | |
714 | mark_call_clobbered (v_ann->type_mem_tag); | |
715 | ||
50dc9a88 | 716 | if (pi->pt_vars) |
87c476a2 | 717 | EXECUTE_IF_SET_IN_BITMAP (pi->pt_vars, 0, j, bi) |
e8ca4159 | 718 | mark_call_clobbered (referenced_var (j)); |
6de9cd9a DN |
719 | } |
720 | ||
721 | /* Set up aliasing information for PTR's name memory tag (if it has | |
722 | one). Note that only pointers that have been dereferenced will | |
723 | have a name memory tag. */ | |
313679b0 | 724 | if (pi->name_mem_tag && pi->pt_vars) |
87c476a2 ZD |
725 | EXECUTE_IF_SET_IN_BITMAP (pi->pt_vars, 0, j, bi) |
726 | { | |
727 | add_may_alias (pi->name_mem_tag, referenced_var (j)); | |
e03a46f5 | 728 | add_may_alias (v_ann->type_mem_tag, referenced_var (j)); |
87c476a2 | 729 | } |
6de9cd9a DN |
730 | |
731 | /* If the name tag is call clobbered, so is the type tag | |
732 | associated with the base VAR_DECL. */ | |
313679b0 | 733 | if (pi->name_mem_tag |
6de9cd9a | 734 | && v_ann->type_mem_tag |
313679b0 | 735 | && is_call_clobbered (pi->name_mem_tag)) |
6de9cd9a DN |
736 | mark_call_clobbered (v_ann->type_mem_tag); |
737 | } | |
738 | } | |
739 | ||
740 | ||
741 | /* Compute type-based alias sets. Traverse all the pointers and | |
742 | addressable variables found in setup_pointers_and_addressables. | |
743 | ||
744 | For every pointer P in AI->POINTERS and addressable variable V in | |
745 | AI->ADDRESSABLE_VARS, add V to the may-alias sets of P's type | |
746 | memory tag (TMT) if their alias sets conflict. V is then marked as | |
747 | an alias tag so that the operand scanner knows that statements | |
748 | containing V have aliased operands. */ | |
749 | ||
750 | static void | |
751 | compute_flow_insensitive_aliasing (struct alias_info *ai) | |
752 | { | |
753 | size_t i; | |
754 | ||
755 | /* Initialize counter for the total number of virtual operands that | |
756 | aliasing will introduce. When AI->TOTAL_ALIAS_VOPS goes beyond the | |
757 | threshold set by --params max-alias-vops, we enable alias | |
758 | grouping. */ | |
759 | ai->total_alias_vops = 0; | |
760 | ||
761 | /* For every pointer P, determine which addressable variables may alias | |
762 | with P's type memory tag. */ | |
763 | for (i = 0; i < ai->num_pointers; i++) | |
764 | { | |
765 | size_t j; | |
766 | struct alias_map_d *p_map = ai->pointers[i]; | |
767 | tree tag = var_ann (p_map->var)->type_mem_tag; | |
768 | var_ann_t tag_ann = var_ann (tag); | |
769 | ||
770 | p_map->total_alias_vops = 0; | |
a3648cfc | 771 | p_map->may_aliases = BITMAP_ALLOC (&alias_obstack); |
6de9cd9a DN |
772 | |
773 | for (j = 0; j < ai->num_addressable_vars; j++) | |
774 | { | |
775 | struct alias_map_d *v_map; | |
776 | var_ann_t v_ann; | |
777 | tree var; | |
778 | bool tag_stored_p, var_stored_p; | |
779 | ||
780 | v_map = ai->addressable_vars[j]; | |
781 | var = v_map->var; | |
782 | v_ann = var_ann (var); | |
783 | ||
784 | /* Skip memory tags and variables that have never been | |
785 | written to. We also need to check if the variables are | |
786 | call-clobbered because they may be overwritten by | |
0bab1c88 JL |
787 | function calls. |
788 | ||
789 | Note this is effectively random accessing elements in | |
790 | the sparse bitset, which can be highly inefficient. | |
791 | So we first check the call_clobbered status of the | |
792 | tag and variable before querying the bitmap. */ | |
793 | tag_stored_p = is_call_clobbered (tag) | |
e8ca4159 | 794 | || bitmap_bit_p (ai->written_vars, DECL_UID (tag)); |
0bab1c88 | 795 | var_stored_p = is_call_clobbered (var) |
e8ca4159 | 796 | || bitmap_bit_p (ai->written_vars, DECL_UID (var)); |
6de9cd9a DN |
797 | if (!tag_stored_p && !var_stored_p) |
798 | continue; | |
ea900239 DB |
799 | |
800 | if (may_alias_p (p_map->var, p_map->set, var, v_map->set, false)) | |
6de9cd9a DN |
801 | { |
802 | size_t num_tag_refs, num_var_refs; | |
803 | ||
a3648cfc DB |
804 | num_tag_refs = NUM_REFERENCES (tag_ann); |
805 | num_var_refs = NUM_REFERENCES (v_ann); | |
6de9cd9a DN |
806 | |
807 | /* Add VAR to TAG's may-aliases set. */ | |
c75ab022 | 808 | |
d938e461 DB |
809 | /* We should never have a var with subvars here, because |
810 | they shouldn't get into the set of addressable vars */ | |
811 | gcc_assert (!var_can_have_subvars (var) | |
812 | || get_subvars_for_var (var) == NULL); | |
c75ab022 | 813 | |
d938e461 DB |
814 | add_may_alias (tag, var); |
815 | /* Update the bitmap used to represent TAG's alias set | |
816 | in case we need to group aliases. */ | |
817 | bitmap_set_bit (p_map->may_aliases, DECL_UID (var)); | |
6de9cd9a DN |
818 | |
819 | /* Update the total number of virtual operands due to | |
820 | aliasing. Since we are adding one more alias to TAG's | |
821 | may-aliases set, the total number of virtual operands due | |
822 | to aliasing will be increased by the number of references | |
823 | made to VAR and TAG (every reference to TAG will also | |
824 | count as a reference to VAR). */ | |
825 | ai->total_alias_vops += (num_var_refs + num_tag_refs); | |
826 | p_map->total_alias_vops += (num_var_refs + num_tag_refs); | |
827 | ||
d19e9499 | 828 | |
6de9cd9a DN |
829 | } |
830 | } | |
831 | } | |
832 | ||
1810f6ed DN |
833 | /* Since this analysis is based exclusively on symbols, it fails to |
834 | handle cases where two pointers P and Q have different memory | |
835 | tags with conflicting alias set numbers but no aliased symbols in | |
836 | common. | |
837 | ||
838 | For example, suppose that we have two memory tags TMT.1 and TMT.2 | |
839 | such that | |
840 | ||
841 | may-aliases (TMT.1) = { a } | |
842 | may-aliases (TMT.2) = { b } | |
843 | ||
844 | and the alias set number of TMT.1 conflicts with that of TMT.2. | |
845 | Since they don't have symbols in common, loads and stores from | |
846 | TMT.1 and TMT.2 will seem independent of each other, which will | |
847 | lead to the optimizers making invalid transformations (see | |
848 | testsuite/gcc.c-torture/execute/pr15262-[12].c). | |
849 | ||
850 | To avoid this problem, we do a final traversal of AI->POINTERS | |
851 | looking for pairs of pointers that have no aliased symbols in | |
852 | common and yet have conflicting alias set numbers. */ | |
1810f6ed DN |
853 | for (i = 0; i < ai->num_pointers; i++) |
854 | { | |
855 | size_t j; | |
856 | struct alias_map_d *p_map1 = ai->pointers[i]; | |
857 | tree tag1 = var_ann (p_map1->var)->type_mem_tag; | |
a3648cfc | 858 | bitmap may_aliases1 = p_map1->may_aliases; |
1810f6ed DN |
859 | |
860 | for (j = i + 1; j < ai->num_pointers; j++) | |
861 | { | |
862 | struct alias_map_d *p_map2 = ai->pointers[j]; | |
863 | tree tag2 = var_ann (p_map2->var)->type_mem_tag; | |
a3648cfc | 864 | bitmap may_aliases2 = p_map2->may_aliases; |
1810f6ed DN |
865 | |
866 | /* If the pointers may not point to each other, do nothing. */ | |
ea900239 | 867 | if (!may_alias_p (p_map1->var, p_map1->set, tag2, p_map2->set, true)) |
1810f6ed DN |
868 | continue; |
869 | ||
870 | /* The two pointers may alias each other. If they already have | |
871 | symbols in common, do nothing. */ | |
a3648cfc | 872 | if (bitmap_intersect_p (may_aliases1, may_aliases2)) |
1810f6ed DN |
873 | continue; |
874 | ||
a3648cfc | 875 | if (!bitmap_empty_p (may_aliases2)) |
1810f6ed | 876 | { |
b6e7e9af | 877 | unsigned int k; |
a3648cfc | 878 | bitmap_iterator bi; |
1810f6ed DN |
879 | |
880 | /* Add all the aliases for TAG2 into TAG1's alias set. | |
881 | FIXME, update grouping heuristic counters. */ | |
a3648cfc | 882 | EXECUTE_IF_SET_IN_BITMAP (may_aliases2, 0, k, bi) |
b6e7e9af | 883 | add_may_alias (tag1, referenced_var (k)); |
a3648cfc | 884 | bitmap_ior_into (may_aliases1, may_aliases2); |
1810f6ed DN |
885 | } |
886 | else | |
887 | { | |
888 | /* Since TAG2 does not have any aliases of its own, add | |
889 | TAG2 itself to the alias set of TAG1. */ | |
890 | add_may_alias (tag1, tag2); | |
a3648cfc | 891 | bitmap_set_bit (may_aliases1, DECL_UID (tag2)); |
1810f6ed DN |
892 | } |
893 | } | |
894 | } | |
a3648cfc | 895 | |
6de9cd9a | 896 | if (dump_file) |
e8ca4159 | 897 | fprintf (dump_file, "\n%s: Total number of aliased vops: %ld\n", |
6de9cd9a DN |
898 | get_name (current_function_decl), |
899 | ai->total_alias_vops); | |
900 | ||
901 | /* Determine if we need to enable alias grouping. */ | |
902 | if (ai->total_alias_vops >= MAX_ALIASED_VOPS) | |
903 | group_aliases (ai); | |
904 | } | |
905 | ||
906 | ||
907 | /* Comparison function for qsort used in group_aliases. */ | |
908 | ||
909 | static int | |
910 | total_alias_vops_cmp (const void *p, const void *q) | |
911 | { | |
912 | const struct alias_map_d **p1 = (const struct alias_map_d **)p; | |
913 | const struct alias_map_d **p2 = (const struct alias_map_d **)q; | |
914 | long n1 = (*p1)->total_alias_vops; | |
915 | long n2 = (*p2)->total_alias_vops; | |
916 | ||
917 | /* We want to sort in descending order. */ | |
918 | return (n1 > n2 ? -1 : (n1 == n2) ? 0 : 1); | |
919 | } | |
920 | ||
921 | /* Group all the aliases for TAG to make TAG represent all the | |
922 | variables in its alias set. Update the total number | |
923 | of virtual operands due to aliasing (AI->TOTAL_ALIAS_VOPS). This | |
924 | function will make TAG be the unique alias tag for all the | |
925 | variables in its may-aliases. So, given: | |
926 | ||
927 | may-aliases(TAG) = { V1, V2, V3 } | |
928 | ||
929 | This function will group the variables into: | |
930 | ||
931 | may-aliases(V1) = { TAG } | |
932 | may-aliases(V2) = { TAG } | |
933 | may-aliases(V2) = { TAG } */ | |
934 | ||
935 | static void | |
a3648cfc | 936 | group_aliases_into (tree tag, bitmap tag_aliases, struct alias_info *ai) |
6de9cd9a | 937 | { |
b6e7e9af | 938 | unsigned int i; |
6de9cd9a | 939 | var_ann_t tag_ann = var_ann (tag); |
a3648cfc DB |
940 | size_t num_tag_refs = NUM_REFERENCES (tag_ann); |
941 | bitmap_iterator bi; | |
6de9cd9a | 942 | |
a3648cfc | 943 | EXECUTE_IF_SET_IN_BITMAP (tag_aliases, 0, i, bi) |
6de9cd9a DN |
944 | { |
945 | tree var = referenced_var (i); | |
946 | var_ann_t ann = var_ann (var); | |
947 | ||
948 | /* Make TAG the unique alias of VAR. */ | |
949 | ann->is_alias_tag = 0; | |
950 | ann->may_aliases = NULL; | |
951 | ||
952 | /* Note that VAR and TAG may be the same if the function has no | |
953 | addressable variables (see the discussion at the end of | |
9cf737f8 | 954 | setup_pointers_and_addressables). */ |
6de9cd9a DN |
955 | if (var != tag) |
956 | add_may_alias (var, tag); | |
957 | ||
958 | /* Reduce total number of virtual operands contributed | |
959 | by TAG on behalf of VAR. Notice that the references to VAR | |
960 | itself won't be removed. We will merely replace them with | |
961 | references to TAG. */ | |
962 | ai->total_alias_vops -= num_tag_refs; | |
b6e7e9af | 963 | } |
6de9cd9a DN |
964 | |
965 | /* We have reduced the number of virtual operands that TAG makes on | |
966 | behalf of all the variables formerly aliased with it. However, | |
967 | we have also "removed" all the virtual operands for TAG itself, | |
968 | so we add them back. */ | |
969 | ai->total_alias_vops += num_tag_refs; | |
970 | ||
971 | /* TAG no longer has any aliases. */ | |
972 | tag_ann->may_aliases = NULL; | |
973 | } | |
974 | ||
975 | ||
976 | /* Group may-aliases sets to reduce the number of virtual operands due | |
977 | to aliasing. | |
978 | ||
979 | 1- Sort the list of pointers in decreasing number of contributed | |
980 | virtual operands. | |
981 | ||
982 | 2- Take the first entry in AI->POINTERS and revert the role of | |
983 | the memory tag and its aliases. Usually, whenever an aliased | |
984 | variable Vi is found to alias with a memory tag T, we add Vi | |
985 | to the may-aliases set for T. Meaning that after alias | |
986 | analysis, we will have: | |
987 | ||
988 | may-aliases(T) = { V1, V2, V3, ..., Vn } | |
989 | ||
990 | This means that every statement that references T, will get 'n' | |
991 | virtual operands for each of the Vi tags. But, when alias | |
992 | grouping is enabled, we make T an alias tag and add it to the | |
993 | alias set of all the Vi variables: | |
994 | ||
995 | may-aliases(V1) = { T } | |
996 | may-aliases(V2) = { T } | |
997 | ... | |
998 | may-aliases(Vn) = { T } | |
999 | ||
1000 | This has two effects: (a) statements referencing T will only get | |
1001 | a single virtual operand, and, (b) all the variables Vi will now | |
1002 | appear to alias each other. So, we lose alias precision to | |
1003 | improve compile time. But, in theory, a program with such a high | |
1004 | level of aliasing should not be very optimizable in the first | |
1005 | place. | |
1006 | ||
1007 | 3- Since variables may be in the alias set of more than one | |
1008 | memory tag, the grouping done in step (2) needs to be extended | |
1009 | to all the memory tags that have a non-empty intersection with | |
1010 | the may-aliases set of tag T. For instance, if we originally | |
1011 | had these may-aliases sets: | |
1012 | ||
1013 | may-aliases(T) = { V1, V2, V3 } | |
1014 | may-aliases(R) = { V2, V4 } | |
1015 | ||
1016 | In step (2) we would have reverted the aliases for T as: | |
1017 | ||
1018 | may-aliases(V1) = { T } | |
1019 | may-aliases(V2) = { T } | |
1020 | may-aliases(V3) = { T } | |
1021 | ||
1022 | But note that now V2 is no longer aliased with R. We could | |
1023 | add R to may-aliases(V2), but we are in the process of | |
1024 | grouping aliases to reduce virtual operands so what we do is | |
1025 | add V4 to the grouping to obtain: | |
1026 | ||
1027 | may-aliases(V1) = { T } | |
1028 | may-aliases(V2) = { T } | |
1029 | may-aliases(V3) = { T } | |
1030 | may-aliases(V4) = { T } | |
1031 | ||
1032 | 4- If the total number of virtual operands due to aliasing is | |
1033 | still above the threshold set by max-alias-vops, go back to (2). */ | |
1034 | ||
1035 | static void | |
1036 | group_aliases (struct alias_info *ai) | |
1037 | { | |
1038 | size_t i; | |
6de9cd9a DN |
1039 | |
1040 | /* Sort the POINTERS array in descending order of contributed | |
1041 | virtual operands. */ | |
1042 | qsort (ai->pointers, ai->num_pointers, sizeof (struct alias_map_d *), | |
1043 | total_alias_vops_cmp); | |
1044 | ||
6de9cd9a DN |
1045 | /* For every pointer in AI->POINTERS, reverse the roles of its tag |
1046 | and the tag's may-aliases set. */ | |
1047 | for (i = 0; i < ai->num_pointers; i++) | |
1048 | { | |
1049 | size_t j; | |
1050 | tree tag1 = var_ann (ai->pointers[i]->var)->type_mem_tag; | |
a3648cfc | 1051 | bitmap tag1_aliases = ai->pointers[i]->may_aliases; |
6de9cd9a DN |
1052 | |
1053 | /* Skip tags that have been grouped already. */ | |
1054 | if (ai->pointers[i]->grouped_p) | |
1055 | continue; | |
1056 | ||
1057 | /* See if TAG1 had any aliases in common with other type tags. | |
1058 | If we find a TAG2 with common aliases with TAG1, add TAG2's | |
1059 | aliases into TAG1. */ | |
1060 | for (j = i + 1; j < ai->num_pointers; j++) | |
1061 | { | |
a3648cfc | 1062 | bitmap tag2_aliases = ai->pointers[j]->may_aliases; |
6de9cd9a | 1063 | |
a3648cfc | 1064 | if (bitmap_intersect_p (tag1_aliases, tag2_aliases)) |
6de9cd9a DN |
1065 | { |
1066 | tree tag2 = var_ann (ai->pointers[j]->var)->type_mem_tag; | |
1067 | ||
a3648cfc | 1068 | bitmap_ior_into (tag1_aliases, tag2_aliases); |
6de9cd9a DN |
1069 | |
1070 | /* TAG2 does not need its aliases anymore. */ | |
a3648cfc | 1071 | bitmap_clear (tag2_aliases); |
6de9cd9a DN |
1072 | var_ann (tag2)->may_aliases = NULL; |
1073 | ||
1074 | /* TAG1 is the unique alias of TAG2. */ | |
1075 | add_may_alias (tag2, tag1); | |
1076 | ||
1077 | ai->pointers[j]->grouped_p = true; | |
1078 | } | |
1079 | } | |
1080 | ||
1081 | /* Now group all the aliases we collected into TAG1. */ | |
1082 | group_aliases_into (tag1, tag1_aliases, ai); | |
1083 | ||
1084 | /* If we've reduced total number of virtual operands below the | |
1085 | threshold, stop. */ | |
1086 | if (ai->total_alias_vops < MAX_ALIASED_VOPS) | |
1087 | break; | |
1088 | } | |
1089 | ||
1090 | /* Finally, all the variables that have been grouped cannot be in | |
1091 | the may-alias set of name memory tags. Suppose that we have | |
1092 | grouped the aliases in this code so that may-aliases(a) = TMT.20 | |
1093 | ||
1094 | p_5 = &a; | |
1095 | ... | |
a32b97a2 | 1096 | # a_9 = V_MAY_DEF <a_8> |
6de9cd9a DN |
1097 | p_5->field = 0 |
1098 | ... Several modifications to TMT.20 ... | |
1099 | # VUSE <a_9> | |
1100 | x_30 = p_5->field | |
1101 | ||
1102 | Since p_5 points to 'a', the optimizers will try to propagate 0 | |
1103 | into p_5->field, but that is wrong because there have been | |
1104 | modifications to 'TMT.20' in between. To prevent this we have to | |
1105 | replace 'a' with 'TMT.20' in the name tag of p_5. */ | |
1106 | for (i = 0; i < VARRAY_ACTIVE_SIZE (ai->processed_ptrs); i++) | |
1107 | { | |
1108 | size_t j; | |
1109 | tree ptr = VARRAY_TREE (ai->processed_ptrs, i); | |
313679b0 | 1110 | tree name_tag = SSA_NAME_PTR_INFO (ptr)->name_mem_tag; |
6de9cd9a DN |
1111 | varray_type aliases; |
1112 | ||
1113 | if (name_tag == NULL_TREE) | |
1114 | continue; | |
1115 | ||
1116 | aliases = var_ann (name_tag)->may_aliases; | |
1117 | for (j = 0; aliases && j < VARRAY_ACTIVE_SIZE (aliases); j++) | |
1118 | { | |
1119 | tree alias = VARRAY_TREE (aliases, j); | |
1120 | var_ann_t ann = var_ann (alias); | |
bbc630f5 | 1121 | |
c75ab022 DB |
1122 | if ((ann->mem_tag_kind == NOT_A_TAG |
1123 | || ann->mem_tag_kind == STRUCT_FIELD) | |
1124 | && ann->may_aliases) | |
6de9cd9a | 1125 | { |
53b4bf74 DN |
1126 | tree new_alias; |
1127 | ||
1e128c5f GB |
1128 | gcc_assert (VARRAY_ACTIVE_SIZE (ann->may_aliases) == 1); |
1129 | ||
53b4bf74 DN |
1130 | new_alias = VARRAY_TREE (ann->may_aliases, 0); |
1131 | replace_may_alias (name_tag, j, new_alias); | |
6de9cd9a DN |
1132 | } |
1133 | } | |
1134 | } | |
1135 | ||
6de9cd9a DN |
1136 | if (dump_file) |
1137 | fprintf (dump_file, | |
1138 | "%s: Total number of aliased vops after grouping: %ld%s\n", | |
1139 | get_name (current_function_decl), | |
1140 | ai->total_alias_vops, | |
1141 | (ai->total_alias_vops < 0) ? " (negative values are OK)" : ""); | |
1142 | } | |
1143 | ||
1144 | ||
1145 | /* Create a new alias set entry for VAR in AI->ADDRESSABLE_VARS. */ | |
1146 | ||
1147 | static void | |
1148 | create_alias_map_for (tree var, struct alias_info *ai) | |
1149 | { | |
1150 | struct alias_map_d *alias_map; | |
1151 | alias_map = xcalloc (1, sizeof (*alias_map)); | |
1152 | alias_map->var = var; | |
fbc87627 | 1153 | alias_map->set = get_alias_set (var); |
6de9cd9a DN |
1154 | ai->addressable_vars[ai->num_addressable_vars++] = alias_map; |
1155 | } | |
1156 | ||
1157 | ||
1158 | /* Create memory tags for all the dereferenced pointers and build the | |
1159 | ADDRESSABLE_VARS and POINTERS arrays used for building the may-alias | |
1160 | sets. Based on the address escape and points-to information collected | |
1161 | earlier, this pass will also clear the TREE_ADDRESSABLE flag from those | |
1162 | variables whose address is not needed anymore. */ | |
1163 | ||
1164 | static void | |
1165 | setup_pointers_and_addressables (struct alias_info *ai) | |
1166 | { | |
a3648cfc DB |
1167 | size_t n_vars, num_addressable_vars, num_pointers; |
1168 | referenced_var_iterator rvi; | |
1169 | tree var; | |
b9d33488 DB |
1170 | VEC (tree, heap) *varvec = NULL; |
1171 | safe_referenced_var_iterator srvi; | |
6de9cd9a DN |
1172 | |
1173 | /* Size up the arrays ADDRESSABLE_VARS and POINTERS. */ | |
1174 | num_addressable_vars = num_pointers = 0; | |
a3648cfc DB |
1175 | |
1176 | FOR_EACH_REFERENCED_VAR (var, rvi) | |
6de9cd9a | 1177 | { |
6de9cd9a DN |
1178 | if (may_be_aliased (var)) |
1179 | num_addressable_vars++; | |
1180 | ||
1181 | if (POINTER_TYPE_P (TREE_TYPE (var))) | |
1182 | { | |
26e79d10 RH |
1183 | /* Since we don't keep track of volatile variables, assume that |
1184 | these pointers are used in indirect store operations. */ | |
1185 | if (TREE_THIS_VOLATILE (var)) | |
a3648cfc | 1186 | bitmap_set_bit (ai->dereferenced_ptrs_store, DECL_UID (var)); |
6de9cd9a DN |
1187 | |
1188 | num_pointers++; | |
1189 | } | |
1190 | } | |
1191 | ||
1192 | /* Create ADDRESSABLE_VARS and POINTERS. Note that these arrays are | |
1193 | always going to be slightly bigger than we actually need them | |
1194 | because some TREE_ADDRESSABLE variables will be marked | |
1195 | non-addressable below and only pointers with unique type tags are | |
1196 | going to be added to POINTERS. */ | |
1197 | ai->addressable_vars = xcalloc (num_addressable_vars, | |
1198 | sizeof (struct alias_map_d *)); | |
1199 | ai->pointers = xcalloc (num_pointers, sizeof (struct alias_map_d *)); | |
1200 | ai->num_addressable_vars = 0; | |
1201 | ai->num_pointers = 0; | |
1202 | ||
1203 | /* Since we will be creating type memory tags within this loop, cache the | |
1204 | value of NUM_REFERENCED_VARS to avoid processing the additional tags | |
1205 | unnecessarily. */ | |
1206 | n_vars = num_referenced_vars; | |
1207 | ||
b9d33488 | 1208 | FOR_EACH_REFERENCED_VAR_SAFE (var, varvec, srvi) |
6de9cd9a | 1209 | { |
6de9cd9a | 1210 | var_ann_t v_ann = var_ann (var); |
c75ab022 | 1211 | subvar_t svars; |
6de9cd9a | 1212 | |
d8903b30 DN |
1213 | /* Name memory tags already have flow-sensitive aliasing |
1214 | information, so they need not be processed by | |
1810f6ed DN |
1215 | compute_flow_insensitive_aliasing. Similarly, type memory |
1216 | tags are already accounted for when we process their | |
c75ab022 DB |
1217 | associated pointer. |
1218 | ||
1219 | Structure fields, on the other hand, have to have some of this | |
1220 | information processed for them, but it's pointless to mark them | |
1221 | non-addressable (since they are fake variables anyway). */ | |
1222 | if (v_ann->mem_tag_kind != NOT_A_TAG | |
1223 | && v_ann->mem_tag_kind != STRUCT_FIELD) | |
6de9cd9a DN |
1224 | continue; |
1225 | ||
1226 | /* Remove the ADDRESSABLE flag from every addressable variable whose | |
1227 | address is not needed anymore. This is caused by the propagation | |
1228 | of ADDR_EXPR constants into INDIRECT_REF expressions and the | |
1229 | removal of dead pointer assignments done by the early scalar | |
1230 | cleanup passes. */ | |
e8ca4159 | 1231 | if (TREE_ADDRESSABLE (var)) |
6de9cd9a | 1232 | { |
e8ca4159 | 1233 | if (!bitmap_bit_p (addressable_vars, DECL_UID (var)) |
57e28d7d | 1234 | && TREE_CODE (var) != RESULT_DECL |
c597ef4e | 1235 | && !is_global_var (var)) |
6de9cd9a | 1236 | { |
c75ab022 | 1237 | bool okay_to_mark = true; |
0bca51f0 | 1238 | |
c75ab022 DB |
1239 | /* Since VAR is now a regular GIMPLE register, we will need |
1240 | to rename VAR into SSA afterwards. */ | |
0bca51f0 | 1241 | mark_sym_for_renaming (var); |
c75ab022 | 1242 | |
e8ca4159 DN |
1243 | /* If VAR can have sub-variables, and any of its |
1244 | sub-variables has its address taken, then we cannot | |
1245 | remove the addressable flag from VAR. */ | |
c75ab022 DB |
1246 | if (var_can_have_subvars (var) |
1247 | && (svars = get_subvars_for_var (var))) | |
1248 | { | |
1249 | subvar_t sv; | |
1250 | ||
1251 | for (sv = svars; sv; sv = sv->next) | |
1252 | { | |
e8ca4159 | 1253 | if (bitmap_bit_p (addressable_vars, DECL_UID (sv->var))) |
c75ab022 | 1254 | okay_to_mark = false; |
0bca51f0 | 1255 | mark_sym_for_renaming (sv->var); |
c75ab022 DB |
1256 | } |
1257 | } | |
0bca51f0 | 1258 | |
d8903b30 DN |
1259 | /* The address of VAR is not needed, remove the |
1260 | addressable bit, so that it can be optimized as a | |
1261 | regular variable. */ | |
c75ab022 DB |
1262 | if (okay_to_mark) |
1263 | mark_non_addressable (var); | |
6de9cd9a DN |
1264 | } |
1265 | } | |
1266 | ||
1267 | /* Global variables and addressable locals may be aliased. Create an | |
1268 | entry in ADDRESSABLE_VARS for VAR. */ | |
d938e461 DB |
1269 | if (may_be_aliased (var) |
1270 | && (!var_can_have_subvars (var) | |
1271 | || get_subvars_for_var (var) == NULL)) | |
6de9cd9a DN |
1272 | { |
1273 | create_alias_map_for (var, ai); | |
0bca51f0 | 1274 | mark_sym_for_renaming (var); |
6de9cd9a DN |
1275 | } |
1276 | ||
1277 | /* Add pointer variables that have been dereferenced to the POINTERS | |
1278 | array and create a type memory tag for them. */ | |
c1b763fa | 1279 | if (POINTER_TYPE_P (TREE_TYPE (var))) |
6de9cd9a | 1280 | { |
a3648cfc DB |
1281 | if ((bitmap_bit_p (ai->dereferenced_ptrs_store, DECL_UID (var)) |
1282 | || bitmap_bit_p (ai->dereferenced_ptrs_load, DECL_UID (var)))) | |
c1b763fa DN |
1283 | { |
1284 | tree tag; | |
1285 | var_ann_t t_ann; | |
1286 | ||
1287 | /* If pointer VAR still doesn't have a memory tag | |
1288 | associated with it, create it now or re-use an | |
1289 | existing one. */ | |
1290 | tag = get_tmt_for (var, ai); | |
1291 | t_ann = var_ann (tag); | |
1292 | ||
1293 | /* The type tag will need to be renamed into SSA | |
1294 | afterwards. Note that we cannot do this inside | |
1295 | get_tmt_for because aliasing may run multiple times | |
1296 | and we only create type tags the first time. */ | |
0bca51f0 DN |
1297 | mark_sym_for_renaming (tag); |
1298 | ||
1299 | /* Similarly, if pointer VAR used to have another type | |
1300 | tag, we will need to process it in the renamer to | |
1301 | remove the stale virtual operands. */ | |
1302 | if (v_ann->type_mem_tag) | |
1303 | mark_sym_for_renaming (v_ann->type_mem_tag); | |
c1b763fa DN |
1304 | |
1305 | /* Associate the tag with pointer VAR. */ | |
1306 | v_ann->type_mem_tag = tag; | |
1307 | ||
1308 | /* If pointer VAR has been used in a store operation, | |
1309 | then its memory tag must be marked as written-to. */ | |
a3648cfc DB |
1310 | if (bitmap_bit_p (ai->dereferenced_ptrs_store, DECL_UID (var))) |
1311 | bitmap_set_bit (ai->written_vars, DECL_UID (tag)); | |
c1b763fa DN |
1312 | |
1313 | /* If pointer VAR is a global variable or a PARM_DECL, | |
1314 | then its memory tag should be considered a global | |
1315 | variable. */ | |
c597ef4e | 1316 | if (TREE_CODE (var) == PARM_DECL || is_global_var (var)) |
c1b763fa DN |
1317 | mark_call_clobbered (tag); |
1318 | ||
1319 | /* All the dereferences of pointer VAR count as | |
1320 | references of TAG. Since TAG can be associated with | |
1321 | several pointers, add the dereferences of VAR to the | |
a3648cfc | 1322 | TAG. */ |
a3648cfc | 1323 | NUM_REFERENCES_SET (t_ann, |
e8ca4159 DN |
1324 | NUM_REFERENCES (t_ann) |
1325 | + NUM_REFERENCES (v_ann)); | |
c1b763fa DN |
1326 | } |
1327 | else | |
1328 | { | |
1329 | /* The pointer has not been dereferenced. If it had a | |
1330 | type memory tag, remove it and mark the old tag for | |
1331 | renaming to remove it out of the IL. */ | |
1332 | var_ann_t ann = var_ann (var); | |
1333 | tree tag = ann->type_mem_tag; | |
1334 | if (tag) | |
1335 | { | |
0bca51f0 | 1336 | mark_sym_for_renaming (tag); |
c1b763fa DN |
1337 | ann->type_mem_tag = NULL_TREE; |
1338 | } | |
1339 | } | |
6de9cd9a DN |
1340 | } |
1341 | } | |
b9d33488 | 1342 | VEC_free (tree, heap, varvec); |
6de9cd9a DN |
1343 | } |
1344 | ||
1345 | ||
a32b97a2 BB |
1346 | /* Determine whether to use .GLOBAL_VAR to model call clobbering semantics. At |
1347 | every call site, we need to emit V_MAY_DEF expressions to represent the | |
6de9cd9a DN |
1348 | clobbering effects of the call for variables whose address escapes the |
1349 | current function. | |
1350 | ||
1351 | One approach is to group all call-clobbered variables into a single | |
1352 | representative that is used as an alias of every call-clobbered variable | |
1353 | (.GLOBAL_VAR). This works well, but it ties the optimizer hands because | |
1354 | references to any call clobbered variable is a reference to .GLOBAL_VAR. | |
1355 | ||
a32b97a2 BB |
1356 | The second approach is to emit a clobbering V_MAY_DEF for every |
1357 | call-clobbered variable at call sites. This is the preferred way in terms | |
1358 | of optimization opportunities but it may create too many V_MAY_DEF operands | |
1359 | if there are many call clobbered variables and function calls in the | |
1360 | function. | |
6de9cd9a DN |
1361 | |
1362 | To decide whether or not to use .GLOBAL_VAR we multiply the number of | |
1363 | function calls found by the number of call-clobbered variables. If that | |
1364 | product is beyond a certain threshold, as determined by the parameterized | |
1365 | values shown below, we use .GLOBAL_VAR. | |
1366 | ||
1367 | FIXME. This heuristic should be improved. One idea is to use several | |
1368 | .GLOBAL_VARs of different types instead of a single one. The thresholds | |
1369 | have been derived from a typical bootstrap cycle, including all target | |
1370 | libraries. Compile times were found increase by ~1% compared to using | |
1371 | .GLOBAL_VAR. */ | |
1372 | ||
1373 | static void | |
1374 | maybe_create_global_var (struct alias_info *ai) | |
1375 | { | |
3cd8c58a | 1376 | unsigned i, n_clobbered; |
87c476a2 | 1377 | bitmap_iterator bi; |
6de9cd9a | 1378 | |
53b4bf74 | 1379 | /* No need to create it, if we have one already. */ |
e0d3bb46 DN |
1380 | if (global_var == NULL_TREE) |
1381 | { | |
1382 | /* Count all the call-clobbered variables. */ | |
1383 | n_clobbered = 0; | |
87c476a2 ZD |
1384 | EXECUTE_IF_SET_IN_BITMAP (call_clobbered_vars, 0, i, bi) |
1385 | { | |
1386 | n_clobbered++; | |
1387 | } | |
6de9cd9a | 1388 | |
90c1d75a DN |
1389 | /* If the number of virtual operands that would be needed to |
1390 | model all the call-clobbered variables is larger than | |
1391 | GLOBAL_VAR_THRESHOLD, create .GLOBAL_VAR. | |
1392 | ||
1393 | Also create .GLOBAL_VAR if there are no call-clobbered | |
1394 | variables and the program contains a mixture of pure/const | |
1395 | and regular function calls. This is to avoid the problem | |
1396 | described in PR 20115: | |
1397 | ||
1398 | int X; | |
1399 | int func_pure (void) { return X; } | |
1400 | int func_non_pure (int a) { X += a; } | |
1401 | int foo () | |
1402 | { | |
1403 | int a = func_pure (); | |
1404 | func_non_pure (a); | |
1405 | a = func_pure (); | |
1406 | return a; | |
1407 | } | |
1408 | ||
1409 | Since foo() has no call-clobbered variables, there is | |
1410 | no relationship between the calls to func_pure and | |
1411 | func_non_pure. Since func_pure has no side-effects, value | |
1412 | numbering optimizations elide the second call to func_pure. | |
1413 | So, if we have some pure/const and some regular calls in the | |
1414 | program we create .GLOBAL_VAR to avoid missing these | |
1415 | relations. */ | |
1416 | if (ai->num_calls_found * n_clobbered >= (size_t) GLOBAL_VAR_THRESHOLD | |
1417 | || (n_clobbered == 0 | |
1418 | && ai->num_calls_found > 0 | |
1419 | && ai->num_pure_const_calls_found > 0 | |
1420 | && ai->num_calls_found > ai->num_pure_const_calls_found)) | |
e0d3bb46 DN |
1421 | create_global_var (); |
1422 | } | |
6de9cd9a | 1423 | |
90c1d75a DN |
1424 | /* Mark all call-clobbered symbols for renaming. Since the initial |
1425 | rewrite into SSA ignored all call sites, we may need to rename | |
a3648cfc | 1426 | .GLOBAL_VAR and the call-clobbered variables. */ |
90c1d75a DN |
1427 | EXECUTE_IF_SET_IN_BITMAP (call_clobbered_vars, 0, i, bi) |
1428 | { | |
1429 | tree var = referenced_var (i); | |
1430 | ||
1431 | /* If the function has calls to clobbering functions and | |
1432 | .GLOBAL_VAR has been created, make it an alias for all | |
1433 | call-clobbered variables. */ | |
1434 | if (global_var && var != global_var) | |
c75ab022 DB |
1435 | { |
1436 | subvar_t svars; | |
1437 | add_may_alias (var, global_var); | |
1438 | if (var_can_have_subvars (var) | |
1439 | && (svars = get_subvars_for_var (var))) | |
1440 | { | |
1441 | subvar_t sv; | |
1442 | for (sv = svars; sv; sv = sv->next) | |
0bca51f0 | 1443 | mark_sym_for_renaming (sv->var); |
c75ab022 DB |
1444 | } |
1445 | } | |
90c1d75a | 1446 | |
0bca51f0 | 1447 | mark_sym_for_renaming (var); |
90c1d75a | 1448 | } |
6de9cd9a DN |
1449 | } |
1450 | ||
1451 | ||
1452 | /* Return TRUE if pointer PTR may point to variable VAR. | |
1453 | ||
1454 | MEM_ALIAS_SET is the alias set for the memory location pointed-to by PTR | |
1455 | This is needed because when checking for type conflicts we are | |
1456 | interested in the alias set of the memory location pointed-to by | |
1457 | PTR. The alias set of PTR itself is irrelevant. | |
1458 | ||
1459 | VAR_ALIAS_SET is the alias set for VAR. */ | |
1460 | ||
1461 | static bool | |
1462 | may_alias_p (tree ptr, HOST_WIDE_INT mem_alias_set, | |
ea900239 DB |
1463 | tree var, HOST_WIDE_INT var_alias_set, |
1464 | bool alias_set_only) | |
6de9cd9a DN |
1465 | { |
1466 | tree mem; | |
a92b9bdf | 1467 | var_ann_t m_ann; |
6de9cd9a DN |
1468 | |
1469 | alias_stats.alias_queries++; | |
1470 | alias_stats.simple_queries++; | |
1471 | ||
1472 | /* By convention, a variable cannot alias itself. */ | |
1473 | mem = var_ann (ptr)->type_mem_tag; | |
1474 | if (mem == var) | |
1475 | { | |
1476 | alias_stats.alias_noalias++; | |
1477 | alias_stats.simple_resolved++; | |
1478 | return false; | |
1479 | } | |
d3010d72 AP |
1480 | |
1481 | /* If -fargument-noalias-global is >1, pointer arguments may | |
1482 | not point to global variables. */ | |
1483 | if (flag_argument_noalias > 1 && is_global_var (var) | |
1484 | && TREE_CODE (ptr) == PARM_DECL) | |
1485 | { | |
1486 | alias_stats.alias_noalias++; | |
1487 | alias_stats.simple_resolved++; | |
1488 | return false; | |
1489 | } | |
6de9cd9a | 1490 | |
f8d66d34 DN |
1491 | /* If either MEM or VAR is a read-only global and the other one |
1492 | isn't, then PTR cannot point to VAR. */ | |
1493 | if ((unmodifiable_var_p (mem) && !unmodifiable_var_p (var)) | |
1494 | || (unmodifiable_var_p (var) && !unmodifiable_var_p (mem))) | |
1495 | { | |
1496 | alias_stats.alias_noalias++; | |
1497 | alias_stats.simple_resolved++; | |
1498 | return false; | |
1499 | } | |
1500 | ||
6de9cd9a DN |
1501 | m_ann = var_ann (mem); |
1502 | ||
1e128c5f | 1503 | gcc_assert (m_ann->mem_tag_kind == TYPE_TAG); |
6de9cd9a DN |
1504 | |
1505 | alias_stats.tbaa_queries++; | |
1506 | ||
6de9cd9a DN |
1507 | /* If the alias sets don't conflict then MEM cannot alias VAR. */ |
1508 | if (!alias_sets_conflict_p (mem_alias_set, var_alias_set)) | |
1509 | { | |
1810f6ed DN |
1510 | alias_stats.alias_noalias++; |
1511 | alias_stats.tbaa_resolved++; | |
1512 | return false; | |
6de9cd9a | 1513 | } |
ea900239 DB |
1514 | |
1515 | /* If var is a record or union type, ptr cannot point into var | |
1516 | unless there is some operation explicit address operation in the | |
1517 | program that can reference a field of the ptr's dereferenced | |
1518 | type. This also assumes that the types of both var and ptr are | |
1519 | contained within the compilation unit, and that there is no fancy | |
1520 | addressing arithmetic associated with any of the types | |
1521 | involved. */ | |
1522 | ||
1523 | if ((mem_alias_set != 0) && (var_alias_set != 0)) | |
1524 | { | |
1525 | tree ptr_type = TREE_TYPE (ptr); | |
1526 | tree var_type = TREE_TYPE (var); | |
1527 | ||
1528 | /* The star count is -1 if the type at the end of the pointer_to | |
1529 | chain is not a record or union type. */ | |
1530 | if ((!alias_set_only) && | |
1531 | ipa_type_escape_star_count_of_interesting_type (var_type) >= 0) | |
1532 | { | |
1533 | int ptr_star_count = 0; | |
1534 | ||
1535 | /* Ipa_type_escape_star_count_of_interesting_type is a little to | |
1536 | restrictive for the pointer type, need to allow pointers to | |
1537 | primitive types as long as those types cannot be pointers | |
1538 | to everything. */ | |
1539 | while (POINTER_TYPE_P (ptr_type)) | |
1540 | /* Strip the *'s off. */ | |
1541 | { | |
1542 | ptr_type = TREE_TYPE (ptr_type); | |
1543 | ptr_star_count++; | |
1544 | } | |
1545 | ||
1546 | /* There does not appear to be a better test to see if the | |
1547 | pointer type was one of the pointer to everything | |
1548 | types. */ | |
1549 | ||
1550 | if (ptr_star_count > 0) | |
1551 | { | |
1552 | alias_stats.structnoaddress_queries++; | |
1553 | if (ipa_type_escape_field_does_not_clobber_p (var_type, | |
1554 | TREE_TYPE (ptr))) | |
1555 | { | |
1556 | alias_stats.structnoaddress_resolved++; | |
1557 | alias_stats.alias_noalias++; | |
1558 | return false; | |
1559 | } | |
1560 | } | |
1561 | else if (ptr_star_count == 0) | |
1562 | { | |
1563 | /* If ptr_type was not really a pointer to type, it cannot | |
1564 | alias. */ | |
1565 | alias_stats.structnoaddress_queries++; | |
1566 | alias_stats.structnoaddress_resolved++; | |
1567 | alias_stats.alias_noalias++; | |
1568 | return false; | |
1569 | } | |
1570 | } | |
1571 | } | |
1572 | ||
6de9cd9a DN |
1573 | alias_stats.alias_mayalias++; |
1574 | return true; | |
1575 | } | |
1576 | ||
1577 | ||
1578 | /* Add ALIAS to the set of variables that may alias VAR. */ | |
1579 | ||
1580 | static void | |
1581 | add_may_alias (tree var, tree alias) | |
1582 | { | |
1583 | size_t i; | |
1584 | var_ann_t v_ann = get_var_ann (var); | |
1585 | var_ann_t a_ann = get_var_ann (alias); | |
1586 | ||
e8ca4159 | 1587 | /* Don't allow self-referential aliases. */ |
1e128c5f | 1588 | gcc_assert (var != alias); |
6de9cd9a | 1589 | |
e8ca4159 DN |
1590 | /* ALIAS must be addressable if it's being added to an alias set. */ |
1591 | #if 1 | |
1592 | TREE_ADDRESSABLE (alias) = 1; | |
1593 | #else | |
1594 | gcc_assert (may_be_aliased (alias)); | |
1595 | #endif | |
1596 | ||
6de9cd9a DN |
1597 | if (v_ann->may_aliases == NULL) |
1598 | VARRAY_TREE_INIT (v_ann->may_aliases, 2, "aliases"); | |
1599 | ||
1600 | /* Avoid adding duplicates. */ | |
1601 | for (i = 0; i < VARRAY_ACTIVE_SIZE (v_ann->may_aliases); i++) | |
1602 | if (alias == VARRAY_TREE (v_ann->may_aliases, i)) | |
1603 | return; | |
1604 | ||
e30b0ae2 DN |
1605 | /* If VAR is a call-clobbered variable, so is its new ALIAS. |
1606 | FIXME, call-clobbering should only depend on whether an address | |
1607 | escapes. It should be independent of aliasing. */ | |
1608 | if (is_call_clobbered (var)) | |
1609 | mark_call_clobbered (alias); | |
1610 | ||
1611 | /* Likewise. If ALIAS is call-clobbered, so is VAR. */ | |
1612 | else if (is_call_clobbered (alias)) | |
1613 | mark_call_clobbered (var); | |
1614 | ||
6de9cd9a DN |
1615 | VARRAY_PUSH_TREE (v_ann->may_aliases, alias); |
1616 | a_ann->is_alias_tag = 1; | |
1617 | } | |
1618 | ||
1619 | ||
53b4bf74 DN |
1620 | /* Replace alias I in the alias sets of VAR with NEW_ALIAS. */ |
1621 | ||
1622 | static void | |
1623 | replace_may_alias (tree var, size_t i, tree new_alias) | |
1624 | { | |
1625 | var_ann_t v_ann = var_ann (var); | |
1626 | VARRAY_TREE (v_ann->may_aliases, i) = new_alias; | |
e30b0ae2 DN |
1627 | |
1628 | /* If VAR is a call-clobbered variable, so is NEW_ALIAS. | |
1629 | FIXME, call-clobbering should only depend on whether an address | |
1630 | escapes. It should be independent of aliasing. */ | |
1631 | if (is_call_clobbered (var)) | |
1632 | mark_call_clobbered (new_alias); | |
1633 | ||
1634 | /* Likewise. If NEW_ALIAS is call-clobbered, so is VAR. */ | |
1635 | else if (is_call_clobbered (new_alias)) | |
1636 | mark_call_clobbered (var); | |
53b4bf74 DN |
1637 | } |
1638 | ||
1639 | ||
1640 | /* Mark pointer PTR as pointing to an arbitrary memory location. */ | |
1641 | ||
1642 | static void | |
1643 | set_pt_anything (tree ptr) | |
1644 | { | |
1645 | struct ptr_info_def *pi = get_ptr_info (ptr); | |
1646 | ||
1647 | pi->pt_anything = 1; | |
e8ca4159 | 1648 | pi->pt_vars = NULL; |
53b4bf74 DN |
1649 | |
1650 | /* The pointer used to have a name tag, but we now found it pointing | |
1651 | to an arbitrary location. The name tag needs to be renamed and | |
1652 | disassociated from PTR. */ | |
1653 | if (pi->name_mem_tag) | |
1654 | { | |
0bca51f0 | 1655 | mark_sym_for_renaming (pi->name_mem_tag); |
53b4bf74 DN |
1656 | pi->name_mem_tag = NULL_TREE; |
1657 | } | |
1658 | } | |
1659 | ||
1660 | ||
6de9cd9a DN |
1661 | /* Return true if STMT is an "escape" site from the current function. Escape |
1662 | sites those statements which might expose the address of a variable | |
1663 | outside the current function. STMT is an escape site iff: | |
1664 | ||
1665 | 1- STMT is a function call, or | |
1666 | 2- STMT is an __asm__ expression, or | |
1667 | 3- STMT is an assignment to a non-local variable, or | |
1668 | 4- STMT is a return statement. | |
1669 | ||
90c1d75a | 1670 | AI points to the alias information collected so far. */ |
6de9cd9a | 1671 | |
e8ca4159 | 1672 | bool |
90c1d75a | 1673 | is_escape_site (tree stmt, struct alias_info *ai) |
6de9cd9a | 1674 | { |
90c1d75a DN |
1675 | tree call = get_call_expr_in (stmt); |
1676 | if (call != NULL_TREE) | |
6de9cd9a | 1677 | { |
90c1d75a DN |
1678 | ai->num_calls_found++; |
1679 | ||
1680 | if (!TREE_SIDE_EFFECTS (call)) | |
1681 | ai->num_pure_const_calls_found++; | |
6de9cd9a DN |
1682 | |
1683 | return true; | |
1684 | } | |
1685 | else if (TREE_CODE (stmt) == ASM_EXPR) | |
1686 | return true; | |
1687 | else if (TREE_CODE (stmt) == MODIFY_EXPR) | |
1688 | { | |
1689 | tree lhs = TREE_OPERAND (stmt, 0); | |
1690 | ||
1691 | /* Get to the base of _REF nodes. */ | |
1692 | if (TREE_CODE (lhs) != SSA_NAME) | |
1693 | lhs = get_base_address (lhs); | |
1694 | ||
1695 | /* If we couldn't recognize the LHS of the assignment, assume that it | |
1696 | is a non-local store. */ | |
1697 | if (lhs == NULL_TREE) | |
1698 | return true; | |
1699 | ||
406eab99 RK |
1700 | /* If the RHS is a conversion between a pointer and an integer, the |
1701 | pointer escapes since we can't track the integer. */ | |
1702 | if ((TREE_CODE (TREE_OPERAND (stmt, 1)) == NOP_EXPR | |
1703 | || TREE_CODE (TREE_OPERAND (stmt, 1)) == CONVERT_EXPR | |
1704 | || TREE_CODE (TREE_OPERAND (stmt, 1)) == VIEW_CONVERT_EXPR) | |
1705 | && POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND | |
1706 | (TREE_OPERAND (stmt, 1), 0))) | |
1707 | && !POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (stmt, 1)))) | |
1708 | return true; | |
1709 | ||
6de9cd9a DN |
1710 | /* If the LHS is an SSA name, it can't possibly represent a non-local |
1711 | memory store. */ | |
1712 | if (TREE_CODE (lhs) == SSA_NAME) | |
1713 | return false; | |
1714 | ||
1715 | /* FIXME: LHS is not an SSA_NAME. Even if it's an assignment to a | |
1716 | local variables we cannot be sure if it will escape, because we | |
1717 | don't have information about objects not in SSA form. Need to | |
1718 | implement something along the lines of | |
1719 | ||
1720 | J.-D. Choi, M. Gupta, M. J. Serrano, V. C. Sreedhar, and S. P. | |
1721 | Midkiff, ``Escape analysis for java,'' in Proceedings of the | |
1722 | Conference on Object-Oriented Programming Systems, Languages, and | |
1723 | Applications (OOPSLA), pp. 1-19, 1999. */ | |
1724 | return true; | |
1725 | } | |
1726 | else if (TREE_CODE (stmt) == RETURN_EXPR) | |
1727 | return true; | |
1728 | ||
1729 | return false; | |
1730 | } | |
1731 | ||
1732 | ||
1733 | /* Create a new memory tag of type TYPE. If IS_TYPE_TAG is true, the tag | |
1734 | is considered to represent all the pointers whose pointed-to types are | |
1735 | in the same alias set class. Otherwise, the tag represents a single | |
1736 | SSA_NAME pointer variable. */ | |
1737 | ||
1738 | static tree | |
1739 | create_memory_tag (tree type, bool is_type_tag) | |
1740 | { | |
1741 | var_ann_t ann; | |
1742 | tree tag = create_tmp_var_raw (type, (is_type_tag) ? "TMT" : "NMT"); | |
1743 | ||
1744 | /* By default, memory tags are local variables. Alias analysis will | |
1745 | determine whether they should be considered globals. */ | |
1746 | DECL_CONTEXT (tag) = current_function_decl; | |
1747 | ||
e8ca4159 | 1748 | /* Memory tags are by definition addressable. */ |
6de9cd9a DN |
1749 | TREE_ADDRESSABLE (tag) = 1; |
1750 | ||
1751 | ann = get_var_ann (tag); | |
1752 | ann->mem_tag_kind = (is_type_tag) ? TYPE_TAG : NAME_TAG; | |
1753 | ann->type_mem_tag = NULL_TREE; | |
1754 | ||
d8903b30 | 1755 | /* Add the tag to the symbol table. */ |
6de9cd9a | 1756 | add_referenced_tmp_var (tag); |
6de9cd9a DN |
1757 | |
1758 | return tag; | |
1759 | } | |
1760 | ||
1761 | ||
1762 | /* Create a name memory tag to represent a specific SSA_NAME pointer P_i. | |
1763 | This is used if P_i has been found to point to a specific set of | |
1764 | variables or to a non-aliased memory location like the address returned | |
1765 | by malloc functions. */ | |
1766 | ||
1767 | static tree | |
1768 | get_nmt_for (tree ptr) | |
1769 | { | |
313679b0 DN |
1770 | struct ptr_info_def *pi = get_ptr_info (ptr); |
1771 | tree tag = pi->name_mem_tag; | |
6de9cd9a DN |
1772 | |
1773 | if (tag == NULL_TREE) | |
c597ef4e | 1774 | tag = create_memory_tag (TREE_TYPE (TREE_TYPE (ptr)), false); |
6de9cd9a | 1775 | |
50dc9a88 DN |
1776 | /* If PTR is a PARM_DECL, it points to a global variable or malloc, |
1777 | then its name tag should be considered a global variable. */ | |
1778 | if (TREE_CODE (SSA_NAME_VAR (ptr)) == PARM_DECL | |
50dc9a88 | 1779 | || pi->pt_global_mem) |
c597ef4e | 1780 | mark_call_clobbered (tag); |
6de9cd9a DN |
1781 | |
1782 | return tag; | |
1783 | } | |
1784 | ||
1785 | ||
1786 | /* Return the type memory tag associated to pointer PTR. A memory tag is an | |
1787 | artificial variable that represents the memory location pointed-to by | |
1788 | PTR. It is used to model the effects of pointer de-references on | |
1789 | addressable variables. | |
1790 | ||
1791 | AI points to the data gathered during alias analysis. This function | |
1792 | populates the array AI->POINTERS. */ | |
1793 | ||
1794 | static tree | |
1795 | get_tmt_for (tree ptr, struct alias_info *ai) | |
1796 | { | |
1797 | size_t i; | |
1798 | tree tag; | |
1799 | tree tag_type = TREE_TYPE (TREE_TYPE (ptr)); | |
1800 | HOST_WIDE_INT tag_set = get_alias_set (tag_type); | |
1801 | ||
1802 | /* To avoid creating unnecessary memory tags, only create one memory tag | |
1803 | per alias set class. Note that it may be tempting to group | |
1804 | memory tags based on conflicting alias sets instead of | |
1805 | equivalence. That would be wrong because alias sets are not | |
1806 | necessarily transitive (as demonstrated by the libstdc++ test | |
1807 | 23_containers/vector/cons/4.cc). Given three alias sets A, B, C | |
1808 | such that conflicts (A, B) == true and conflicts (A, C) == true, | |
1809 | it does not necessarily follow that conflicts (B, C) == true. */ | |
1810 | for (i = 0, tag = NULL_TREE; i < ai->num_pointers; i++) | |
1811 | { | |
1812 | struct alias_map_d *curr = ai->pointers[i]; | |
f8d66d34 DN |
1813 | tree curr_tag = var_ann (curr->var)->type_mem_tag; |
1814 | if (tag_set == curr->set | |
1815 | && TYPE_READONLY (tag_type) == TYPE_READONLY (TREE_TYPE (curr_tag))) | |
6de9cd9a | 1816 | { |
f8d66d34 | 1817 | tag = curr_tag; |
6de9cd9a DN |
1818 | break; |
1819 | } | |
1820 | } | |
1821 | ||
1822 | /* If VAR cannot alias with any of the existing memory tags, create a new | |
1823 | tag for PTR and add it to the POINTERS array. */ | |
1824 | if (tag == NULL_TREE) | |
1825 | { | |
1826 | struct alias_map_d *alias_map; | |
1827 | ||
53b4bf74 DN |
1828 | /* If PTR did not have a type tag already, create a new TMT.* |
1829 | artificial variable representing the memory location | |
1830 | pointed-to by PTR. */ | |
1831 | if (var_ann (ptr)->type_mem_tag == NULL_TREE) | |
1832 | tag = create_memory_tag (tag_type, true); | |
1833 | else | |
1834 | tag = var_ann (ptr)->type_mem_tag; | |
6de9cd9a DN |
1835 | |
1836 | /* Add PTR to the POINTERS array. Note that we are not interested in | |
1837 | PTR's alias set. Instead, we cache the alias set for the memory that | |
1838 | PTR points to. */ | |
1839 | alias_map = xcalloc (1, sizeof (*alias_map)); | |
1840 | alias_map->var = ptr; | |
1841 | alias_map->set = tag_set; | |
1842 | ai->pointers[ai->num_pointers++] = alias_map; | |
1843 | } | |
1844 | ||
c04f07f4 | 1845 | /* If the pointed-to type is volatile, so is the tag. */ |
38e05395 | 1846 | TREE_THIS_VOLATILE (tag) |= TREE_THIS_VOLATILE (tag_type); |
c04f07f4 | 1847 | |
bbc630f5 DN |
1848 | /* Make sure that the type tag has the same alias set as the |
1849 | pointed-to type. */ | |
1e128c5f | 1850 | gcc_assert (tag_set == get_alias_set (tag)); |
bbc630f5 | 1851 | |
f8d66d34 DN |
1852 | /* If PTR's pointed-to type is read-only, then TAG's type must also |
1853 | be read-only. */ | |
1854 | gcc_assert (TYPE_READONLY (tag_type) == TYPE_READONLY (TREE_TYPE (tag))); | |
1855 | ||
6de9cd9a DN |
1856 | return tag; |
1857 | } | |
1858 | ||
1859 | ||
1860 | /* Create GLOBAL_VAR, an artificial global variable to act as a | |
1861 | representative of all the variables that may be clobbered by function | |
1862 | calls. */ | |
1863 | ||
1864 | static void | |
1865 | create_global_var (void) | |
1866 | { | |
1867 | global_var = build_decl (VAR_DECL, get_identifier (".GLOBAL_VAR"), | |
b07f8ee2 | 1868 | void_type_node); |
6de9cd9a DN |
1869 | DECL_ARTIFICIAL (global_var) = 1; |
1870 | TREE_READONLY (global_var) = 0; | |
58907cda | 1871 | DECL_EXTERNAL (global_var) = 1; |
6de9cd9a DN |
1872 | TREE_STATIC (global_var) = 1; |
1873 | TREE_USED (global_var) = 1; | |
1874 | DECL_CONTEXT (global_var) = NULL_TREE; | |
1875 | TREE_THIS_VOLATILE (global_var) = 0; | |
1876 | TREE_ADDRESSABLE (global_var) = 0; | |
1877 | ||
1878 | add_referenced_tmp_var (global_var); | |
0bca51f0 | 1879 | mark_sym_for_renaming (global_var); |
6de9cd9a DN |
1880 | } |
1881 | ||
1882 | ||
1883 | /* Dump alias statistics on FILE. */ | |
1884 | ||
1885 | static void | |
1886 | dump_alias_stats (FILE *file) | |
1887 | { | |
1888 | const char *funcname | |
673fda6b | 1889 | = lang_hooks.decl_printable_name (current_function_decl, 2); |
6de9cd9a DN |
1890 | fprintf (file, "\nAlias statistics for %s\n\n", funcname); |
1891 | fprintf (file, "Total alias queries:\t%u\n", alias_stats.alias_queries); | |
1892 | fprintf (file, "Total alias mayalias results:\t%u\n", | |
1893 | alias_stats.alias_mayalias); | |
1894 | fprintf (file, "Total alias noalias results:\t%u\n", | |
1895 | alias_stats.alias_noalias); | |
1896 | fprintf (file, "Total simple queries:\t%u\n", | |
1897 | alias_stats.simple_queries); | |
1898 | fprintf (file, "Total simple resolved:\t%u\n", | |
1899 | alias_stats.simple_resolved); | |
1900 | fprintf (file, "Total TBAA queries:\t%u\n", | |
1901 | alias_stats.tbaa_queries); | |
1902 | fprintf (file, "Total TBAA resolved:\t%u\n", | |
1903 | alias_stats.tbaa_resolved); | |
ea900239 DB |
1904 | fprintf (file, "Total non-addressable structure type queries:\t%u\n", |
1905 | alias_stats.structnoaddress_queries); | |
1906 | fprintf (file, "Total non-addressable structure type resolved:\t%u\n", | |
1907 | alias_stats.structnoaddress_resolved); | |
6de9cd9a DN |
1908 | } |
1909 | ||
1910 | ||
1911 | /* Dump alias information on FILE. */ | |
1912 | ||
1913 | void | |
1914 | dump_alias_info (FILE *file) | |
1915 | { | |
1916 | size_t i; | |
1917 | const char *funcname | |
673fda6b | 1918 | = lang_hooks.decl_printable_name (current_function_decl, 2); |
a3648cfc DB |
1919 | referenced_var_iterator rvi; |
1920 | tree var; | |
6de9cd9a | 1921 | |
53b4bf74 DN |
1922 | fprintf (file, "\nFlow-insensitive alias information for %s\n\n", funcname); |
1923 | ||
1924 | fprintf (file, "Aliased symbols\n\n"); | |
a3648cfc DB |
1925 | |
1926 | FOR_EACH_REFERENCED_VAR (var, rvi) | |
53b4bf74 | 1927 | { |
53b4bf74 DN |
1928 | if (may_be_aliased (var)) |
1929 | dump_variable (file, var); | |
1930 | } | |
1931 | ||
1932 | fprintf (file, "\nDereferenced pointers\n\n"); | |
a3648cfc DB |
1933 | |
1934 | FOR_EACH_REFERENCED_VAR (var, rvi) | |
53b4bf74 | 1935 | { |
53b4bf74 DN |
1936 | var_ann_t ann = var_ann (var); |
1937 | if (ann->type_mem_tag) | |
1938 | dump_variable (file, var); | |
1939 | } | |
1940 | ||
1941 | fprintf (file, "\nType memory tags\n\n"); | |
a3648cfc DB |
1942 | |
1943 | FOR_EACH_REFERENCED_VAR (var, rvi) | |
53b4bf74 | 1944 | { |
53b4bf74 DN |
1945 | var_ann_t ann = var_ann (var); |
1946 | if (ann->mem_tag_kind == TYPE_TAG) | |
1947 | dump_variable (file, var); | |
1948 | } | |
1949 | ||
1950 | fprintf (file, "\n\nFlow-sensitive alias information for %s\n\n", funcname); | |
1951 | ||
1952 | fprintf (file, "SSA_NAME pointers\n\n"); | |
1953 | for (i = 1; i < num_ssa_names; i++) | |
1954 | { | |
1955 | tree ptr = ssa_name (i); | |
d804d490 DN |
1956 | struct ptr_info_def *pi; |
1957 | ||
1958 | if (ptr == NULL_TREE) | |
1959 | continue; | |
1960 | ||
1961 | pi = SSA_NAME_PTR_INFO (ptr); | |
53b4bf74 DN |
1962 | if (!SSA_NAME_IN_FREE_LIST (ptr) |
1963 | && pi | |
1964 | && pi->name_mem_tag) | |
1965 | dump_points_to_info_for (file, ptr); | |
1966 | } | |
6de9cd9a | 1967 | |
53b4bf74 | 1968 | fprintf (file, "\nName memory tags\n\n"); |
a3648cfc DB |
1969 | |
1970 | FOR_EACH_REFERENCED_VAR (var, rvi) | |
6de9cd9a | 1971 | { |
6de9cd9a | 1972 | var_ann_t ann = var_ann (var); |
53b4bf74 | 1973 | if (ann->mem_tag_kind == NAME_TAG) |
6de9cd9a DN |
1974 | dump_variable (file, var); |
1975 | } | |
1976 | ||
1977 | fprintf (file, "\n"); | |
1978 | } | |
1979 | ||
1980 | ||
1981 | /* Dump alias information on stderr. */ | |
1982 | ||
1983 | void | |
1984 | debug_alias_info (void) | |
1985 | { | |
1986 | dump_alias_info (stderr); | |
1987 | } | |
1988 | ||
1989 | ||
313679b0 DN |
1990 | /* Return the alias information associated with pointer T. It creates a |
1991 | new instance if none existed. */ | |
1992 | ||
de66168d | 1993 | struct ptr_info_def * |
313679b0 DN |
1994 | get_ptr_info (tree t) |
1995 | { | |
1996 | struct ptr_info_def *pi; | |
1997 | ||
1e128c5f | 1998 | gcc_assert (POINTER_TYPE_P (TREE_TYPE (t))); |
313679b0 DN |
1999 | |
2000 | pi = SSA_NAME_PTR_INFO (t); | |
2001 | if (pi == NULL) | |
2002 | { | |
2003 | pi = ggc_alloc (sizeof (*pi)); | |
2004 | memset ((void *)pi, 0, sizeof (*pi)); | |
2005 | SSA_NAME_PTR_INFO (t) = pi; | |
2006 | } | |
2007 | ||
2008 | return pi; | |
2009 | } | |
2010 | ||
2011 | ||
6de9cd9a DN |
2012 | /* Dump points-to information for SSA_NAME PTR into FILE. */ |
2013 | ||
d8903b30 | 2014 | void |
6de9cd9a DN |
2015 | dump_points_to_info_for (FILE *file, tree ptr) |
2016 | { | |
313679b0 | 2017 | struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr); |
6de9cd9a | 2018 | |
6de9cd9a DN |
2019 | print_generic_expr (file, ptr, dump_flags); |
2020 | ||
d8903b30 | 2021 | if (pi) |
6de9cd9a | 2022 | { |
d8903b30 DN |
2023 | if (pi->name_mem_tag) |
2024 | { | |
2025 | fprintf (file, ", name memory tag: "); | |
2026 | print_generic_expr (file, pi->name_mem_tag, dump_flags); | |
2027 | } | |
6de9cd9a | 2028 | |
d8903b30 DN |
2029 | if (pi->is_dereferenced) |
2030 | fprintf (file, ", is dereferenced"); | |
6de9cd9a | 2031 | |
d8903b30 DN |
2032 | if (pi->value_escapes_p) |
2033 | fprintf (file, ", its value escapes"); | |
6de9cd9a | 2034 | |
d8903b30 DN |
2035 | if (pi->pt_anything) |
2036 | fprintf (file, ", points-to anything"); | |
6de9cd9a | 2037 | |
a1d13fa1 DN |
2038 | if (pi->pt_null) |
2039 | fprintf (file, ", points-to NULL"); | |
2040 | ||
d8903b30 DN |
2041 | if (pi->pt_vars) |
2042 | { | |
2043 | unsigned ix; | |
87c476a2 | 2044 | bitmap_iterator bi; |
d8903b30 DN |
2045 | |
2046 | fprintf (file, ", points-to vars: { "); | |
87c476a2 ZD |
2047 | EXECUTE_IF_SET_IN_BITMAP (pi->pt_vars, 0, ix, bi) |
2048 | { | |
2049 | print_generic_expr (file, referenced_var (ix), dump_flags); | |
2050 | fprintf (file, " "); | |
2051 | } | |
d8903b30 DN |
2052 | fprintf (file, "}"); |
2053 | } | |
6de9cd9a DN |
2054 | } |
2055 | ||
2056 | fprintf (file, "\n"); | |
2057 | } | |
2058 | ||
2059 | ||
d8903b30 DN |
2060 | /* Dump points-to information for VAR into stderr. */ |
2061 | ||
2062 | void | |
2063 | debug_points_to_info_for (tree var) | |
2064 | { | |
2065 | dump_points_to_info_for (stderr, var); | |
2066 | } | |
2067 | ||
2068 | ||
6de9cd9a DN |
2069 | /* Dump points-to information into FILE. NOTE: This function is slow, as |
2070 | it needs to traverse the whole CFG looking for pointer SSA_NAMEs. */ | |
2071 | ||
2072 | void | |
2073 | dump_points_to_info (FILE *file) | |
2074 | { | |
2075 | basic_block bb; | |
2076 | block_stmt_iterator si; | |
4c124b4c | 2077 | ssa_op_iter iter; |
6de9cd9a | 2078 | const char *fname = |
673fda6b | 2079 | lang_hooks.decl_printable_name (current_function_decl, 2); |
a3648cfc DB |
2080 | referenced_var_iterator rvi; |
2081 | tree var; | |
6de9cd9a DN |
2082 | |
2083 | fprintf (file, "\n\nPointed-to sets for pointers in %s\n\n", fname); | |
2084 | ||
2085 | /* First dump points-to information for the default definitions of | |
2086 | pointer variables. This is necessary because default definitions are | |
2087 | not part of the code. */ | |
a3648cfc | 2088 | FOR_EACH_REFERENCED_VAR (var, rvi) |
6de9cd9a | 2089 | { |
6de9cd9a DN |
2090 | if (POINTER_TYPE_P (TREE_TYPE (var))) |
2091 | { | |
df1f6f31 JH |
2092 | tree def = default_def (var); |
2093 | if (def) | |
2094 | dump_points_to_info_for (file, def); | |
6de9cd9a DN |
2095 | } |
2096 | } | |
2097 | ||
2098 | /* Dump points-to information for every pointer defined in the program. */ | |
2099 | FOR_EACH_BB (bb) | |
2100 | { | |
2101 | tree phi; | |
2102 | ||
17192884 | 2103 | for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) |
6de9cd9a DN |
2104 | { |
2105 | tree ptr = PHI_RESULT (phi); | |
2106 | if (POINTER_TYPE_P (TREE_TYPE (ptr))) | |
2107 | dump_points_to_info_for (file, ptr); | |
2108 | } | |
2109 | ||
2110 | for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si)) | |
2111 | { | |
4c124b4c AM |
2112 | tree stmt = bsi_stmt (si); |
2113 | tree def; | |
2114 | FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF) | |
2115 | if (POINTER_TYPE_P (TREE_TYPE (def))) | |
2116 | dump_points_to_info_for (file, def); | |
6de9cd9a DN |
2117 | } |
2118 | } | |
2119 | ||
2120 | fprintf (file, "\n"); | |
2121 | } | |
2122 | ||
2123 | ||
206048bd | 2124 | /* Dump points-to info pointed to by PTO into STDERR. */ |
6de9cd9a DN |
2125 | |
2126 | void | |
2127 | debug_points_to_info (void) | |
2128 | { | |
2129 | dump_points_to_info (stderr); | |
2130 | } | |
2131 | ||
2132 | /* Dump to FILE the list of variables that may be aliasing VAR. */ | |
2133 | ||
2134 | void | |
2135 | dump_may_aliases_for (FILE *file, tree var) | |
2136 | { | |
2137 | varray_type aliases; | |
2138 | ||
2139 | if (TREE_CODE (var) == SSA_NAME) | |
2140 | var = SSA_NAME_VAR (var); | |
2141 | ||
2142 | aliases = var_ann (var)->may_aliases; | |
2143 | if (aliases) | |
2144 | { | |
2145 | size_t i; | |
2146 | fprintf (file, "{ "); | |
2147 | for (i = 0; i < VARRAY_ACTIVE_SIZE (aliases); i++) | |
2148 | { | |
2149 | print_generic_expr (file, VARRAY_TREE (aliases, i), dump_flags); | |
2150 | fprintf (file, " "); | |
2151 | } | |
2152 | fprintf (file, "}"); | |
2153 | } | |
2154 | } | |
2155 | ||
2156 | ||
2157 | /* Dump to stderr the list of variables that may be aliasing VAR. */ | |
2158 | ||
2159 | void | |
2160 | debug_may_aliases_for (tree var) | |
2161 | { | |
2162 | dump_may_aliases_for (stderr, var); | |
2163 | } | |
ab8907ef RH |
2164 | |
2165 | /* Return true if VAR may be aliased. */ | |
2166 | ||
2167 | bool | |
2168 | may_be_aliased (tree var) | |
2169 | { | |
2170 | /* Obviously. */ | |
2171 | if (TREE_ADDRESSABLE (var)) | |
2172 | return true; | |
2173 | ||
ab8907ef RH |
2174 | /* Globally visible variables can have their addresses taken by other |
2175 | translation units. */ | |
2176 | if (DECL_EXTERNAL (var) || TREE_PUBLIC (var)) | |
2177 | return true; | |
2178 | ||
bb1058e4 JW |
2179 | /* Automatic variables can't have their addresses escape any other way. |
2180 | This must be after the check for global variables, as extern declarations | |
2181 | do not have TREE_STATIC set. */ | |
2182 | if (!TREE_STATIC (var)) | |
2183 | return false; | |
2184 | ||
ab8907ef RH |
2185 | /* If we're in unit-at-a-time mode, then we must have seen all occurrences |
2186 | of address-of operators, and so we can trust TREE_ADDRESSABLE. Otherwise | |
2187 | we can only be sure the variable isn't addressable if it's local to the | |
2188 | current function. */ | |
2189 | if (flag_unit_at_a_time) | |
2190 | return false; | |
2191 | if (decl_function_context (var) == current_function_decl) | |
2192 | return false; | |
2193 | ||
2194 | return true; | |
2195 | } | |
c75ab022 | 2196 | |
0bca51f0 | 2197 | |
86a07404 IR |
2198 | /* Given two symbols return TRUE if one is in the alias set of the other. */ |
2199 | bool | |
2200 | is_aliased_with (tree tag, tree sym) | |
2201 | { | |
2202 | size_t i; | |
2203 | varray_type aliases; | |
2204 | ||
2205 | if (var_ann (sym)->is_alias_tag) | |
2206 | { | |
2207 | aliases = var_ann (tag)->may_aliases; | |
2208 | ||
2209 | if (aliases == NULL) | |
2210 | return false; | |
2211 | ||
2212 | for (i = 0; i < VARRAY_ACTIVE_SIZE (aliases); i++) | |
2213 | if (VARRAY_TREE (aliases, i) == sym) | |
2214 | return true; | |
2215 | } | |
2216 | else | |
2217 | { | |
2218 | aliases = var_ann (sym)->may_aliases; | |
2219 | ||
2220 | if (aliases == NULL) | |
2221 | return false; | |
2222 | ||
2223 | for (i = 0; i < VARRAY_ACTIVE_SIZE (aliases); i++) | |
2224 | if (VARRAY_TREE (aliases, i) == tag) | |
2225 | return true; | |
2226 | } | |
2227 | ||
2228 | return false; | |
2229 | } | |
2230 | ||
2231 | ||
0bca51f0 DN |
2232 | /* Add VAR to the list of may-aliases of PTR's type tag. If PTR |
2233 | doesn't already have a type tag, create one. */ | |
2234 | ||
2235 | void | |
2236 | add_type_alias (tree ptr, tree var) | |
2237 | { | |
2238 | varray_type aliases; | |
2239 | tree tag; | |
2240 | var_ann_t ann = var_ann (ptr); | |
94589120 | 2241 | subvar_t svars; |
b9d33488 | 2242 | VEC (tree, heap) *varvec = NULL; |
0bca51f0 DN |
2243 | |
2244 | if (ann->type_mem_tag == NULL_TREE) | |
2245 | { | |
0bca51f0 DN |
2246 | tree q = NULL_TREE; |
2247 | tree tag_type = TREE_TYPE (TREE_TYPE (ptr)); | |
2248 | HOST_WIDE_INT tag_set = get_alias_set (tag_type); | |
b9d33488 | 2249 | safe_referenced_var_iterator rvi; |
0bca51f0 DN |
2250 | |
2251 | /* PTR doesn't have a type tag, create a new one and add VAR to | |
2252 | the new tag's alias set. | |
2253 | ||
2254 | FIXME, This is slower than necessary. We need to determine | |
2255 | whether there is another pointer Q with the same alias set as | |
2256 | PTR. This could be sped up by having type tags associated | |
2257 | with types. */ | |
b9d33488 | 2258 | FOR_EACH_REFERENCED_VAR_SAFE (q, varvec, rvi) |
0bca51f0 | 2259 | { |
0bca51f0 DN |
2260 | if (POINTER_TYPE_P (TREE_TYPE (q)) |
2261 | && tag_set == get_alias_set (TREE_TYPE (TREE_TYPE (q)))) | |
2262 | { | |
2263 | /* Found another pointer Q with the same alias set as | |
2264 | the PTR's pointed-to type. If Q has a type tag, use | |
2265 | it. Otherwise, create a new memory tag for PTR. */ | |
2266 | var_ann_t ann1 = var_ann (q); | |
2267 | if (ann1->type_mem_tag) | |
2268 | ann->type_mem_tag = ann1->type_mem_tag; | |
2269 | else | |
2270 | ann->type_mem_tag = create_memory_tag (tag_type, true); | |
2271 | goto found_tag; | |
2272 | } | |
2273 | } | |
2274 | ||
2275 | /* Couldn't find any other pointer with a type tag we could use. | |
2276 | Create a new memory tag for PTR. */ | |
2277 | ann->type_mem_tag = create_memory_tag (tag_type, true); | |
2278 | } | |
2279 | ||
2280 | found_tag: | |
2281 | /* If VAR is not already PTR's type tag, add it to the may-alias set | |
2282 | for PTR's type tag. */ | |
2283 | gcc_assert (var_ann (var)->type_mem_tag == NOT_A_TAG); | |
2284 | tag = ann->type_mem_tag; | |
94589120 DB |
2285 | |
2286 | /* If VAR has subvars, add the subvars to the tag instead of the | |
2287 | actual var. */ | |
2288 | if (var_can_have_subvars (var) | |
2289 | && (svars = get_subvars_for_var (var))) | |
2290 | { | |
2291 | subvar_t sv; | |
2292 | for (sv = svars; sv; sv = sv->next) | |
2293 | add_may_alias (tag, sv->var); | |
2294 | } | |
2295 | else | |
2296 | add_may_alias (tag, var); | |
0bca51f0 DN |
2297 | |
2298 | /* TAG and its set of aliases need to be marked for renaming. */ | |
2299 | mark_sym_for_renaming (tag); | |
2300 | if ((aliases = var_ann (tag)->may_aliases) != NULL) | |
2301 | { | |
2302 | size_t i; | |
2303 | for (i = 0; i < VARRAY_ACTIVE_SIZE (aliases); i++) | |
2304 | mark_sym_for_renaming (VARRAY_TREE (aliases, i)); | |
2305 | } | |
2306 | ||
2307 | /* If we had grouped aliases, VAR may have aliases of its own. Mark | |
2308 | them for renaming as well. Other statements referencing the | |
2309 | aliases of VAR will need to be updated. */ | |
2310 | if ((aliases = var_ann (var)->may_aliases) != NULL) | |
2311 | { | |
2312 | size_t i; | |
2313 | for (i = 0; i < VARRAY_ACTIVE_SIZE (aliases); i++) | |
2314 | mark_sym_for_renaming (VARRAY_TREE (aliases, i)); | |
2315 | } | |
b9d33488 | 2316 | VEC_free (tree, heap, varvec); |
0bca51f0 DN |
2317 | } |
2318 | ||
2319 | ||
51540eba KB |
2320 | /* Create a new type tag for PTR. Construct the may-alias list of this type |
2321 | tag so that it has the aliasing of VAR. | |
2322 | ||
2323 | Note, the set of aliases represented by the new type tag are not marked | |
2324 | for renaming. */ | |
9cf5a7e3 KB |
2325 | |
2326 | void | |
2327 | new_type_alias (tree ptr, tree var) | |
2328 | { | |
2329 | var_ann_t p_ann = var_ann (ptr); | |
2330 | tree tag_type = TREE_TYPE (TREE_TYPE (ptr)); | |
2331 | var_ann_t v_ann = var_ann (var); | |
2332 | tree tag; | |
2333 | subvar_t svars; | |
2334 | ||
2335 | gcc_assert (p_ann->type_mem_tag == NULL_TREE); | |
2336 | gcc_assert (v_ann->mem_tag_kind == NOT_A_TAG); | |
9cf5a7e3 KB |
2337 | |
2338 | /* Add VAR to the may-alias set of PTR's new type tag. If VAR has | |
2339 | subvars, add the subvars to the tag instead of the actual var. */ | |
2340 | if (var_can_have_subvars (var) | |
2341 | && (svars = get_subvars_for_var (var))) | |
2342 | { | |
51540eba KB |
2343 | subvar_t sv; |
2344 | ||
2345 | tag = create_memory_tag (tag_type, true); | |
2346 | p_ann->type_mem_tag = tag; | |
2347 | ||
9cf5a7e3 KB |
2348 | for (sv = svars; sv; sv = sv->next) |
2349 | add_may_alias (tag, sv->var); | |
2350 | } | |
2351 | else | |
51540eba KB |
2352 | { |
2353 | /* The following is based on code in add_stmt_operand to ensure that the | |
2354 | same defs/uses/vdefs/vuses will be found after replacing a reference | |
2355 | to var (or ARRAY_REF to var) with an INDIRECT_REF to ptr whose value | |
2356 | is the address of var. */ | |
2357 | varray_type aliases = v_ann->may_aliases; | |
2358 | ||
2359 | if ((aliases != NULL) | |
2360 | && (VARRAY_ACTIVE_SIZE (aliases) == 1)) | |
2361 | { | |
2362 | tree ali = VARRAY_TREE (aliases, 0); | |
9cf5a7e3 | 2363 | |
51540eba KB |
2364 | if (get_var_ann (ali)->mem_tag_kind == TYPE_TAG) |
2365 | { | |
2366 | p_ann->type_mem_tag = ali; | |
2367 | return; | |
2368 | } | |
2369 | } | |
2370 | ||
2371 | tag = create_memory_tag (tag_type, true); | |
2372 | p_ann->type_mem_tag = tag; | |
2373 | ||
2374 | if (aliases == NULL) | |
2375 | add_may_alias (tag, var); | |
2376 | else | |
2377 | { | |
2378 | size_t i; | |
2379 | ||
2380 | for (i = 0; i < VARRAY_ACTIVE_SIZE (aliases); i++) | |
2381 | add_may_alias (tag, VARRAY_TREE (aliases, i)); | |
2382 | } | |
2383 | } | |
9cf5a7e3 KB |
2384 | } |
2385 | ||
a3648cfc DB |
2386 | |
2387 | ||
c75ab022 DB |
2388 | /* This represents the used range of a variable. */ |
2389 | ||
2390 | typedef struct used_part | |
2391 | { | |
2392 | HOST_WIDE_INT minused; | |
2393 | HOST_WIDE_INT maxused; | |
31617ef1 DB |
2394 | /* True if we have an explicit use/def of some portion of this variable, |
2395 | even if it is all of it. i.e. a.b = 5 or temp = a.b. */ | |
2396 | bool explicit_uses; | |
2397 | /* True if we have an implicit use/def of some portion of this | |
2398 | variable. Implicit uses occur when we can't tell what part we | |
2399 | are referencing, and have to make conservative assumptions. */ | |
2400 | bool implicit_uses; | |
c75ab022 DB |
2401 | } *used_part_t; |
2402 | ||
2403 | /* An array of used_part structures, indexed by variable uid. */ | |
2404 | ||
a3648cfc DB |
2405 | static htab_t used_portions; |
2406 | ||
2407 | struct used_part_map | |
2408 | { | |
2409 | unsigned int uid; | |
2410 | used_part_t to; | |
2411 | }; | |
2412 | ||
2413 | /* Return true if the uid in the two used part maps are equal. */ | |
2414 | ||
2415 | static int | |
2416 | used_part_map_eq (const void *va, const void *vb) | |
2417 | { | |
2418 | const struct used_part_map *a = va, *b = vb; | |
2419 | return (a->uid == b->uid); | |
2420 | } | |
2421 | ||
2422 | /* Hash a from uid in a used_part_map. */ | |
2423 | ||
2424 | static unsigned int | |
2425 | used_part_map_hash (const void *item) | |
2426 | { | |
2427 | return ((const struct used_part_map *)item)->uid; | |
2428 | } | |
2429 | ||
2430 | /* Free a used part map element. */ | |
2431 | ||
2432 | static void | |
2433 | free_used_part_map (void *item) | |
2434 | { | |
2435 | free (((struct used_part_map *)item)->to); | |
46c73d9a | 2436 | free (item); |
a3648cfc DB |
2437 | } |
2438 | ||
2439 | /* Lookup a used_part structure for a UID. */ | |
2440 | ||
2441 | static used_part_t | |
2442 | up_lookup (unsigned int uid) | |
2443 | { | |
2444 | struct used_part_map *h, in; | |
2445 | in.uid = uid; | |
2446 | h = htab_find_with_hash (used_portions, &in, uid); | |
2447 | if (!h) | |
2448 | return NULL; | |
2449 | return h->to; | |
2450 | } | |
2451 | ||
2452 | /* Insert the pair UID, TO into the used part hashtable. */ | |
2453 | ||
2454 | static void | |
2455 | up_insert (unsigned int uid, used_part_t to) | |
2456 | { | |
2457 | struct used_part_map *h; | |
2458 | void **loc; | |
2459 | ||
2460 | h = xmalloc (sizeof (struct used_part_map)); | |
2461 | h->uid = uid; | |
2462 | h->to = to; | |
2463 | loc = htab_find_slot_with_hash (used_portions, h, | |
2464 | uid, INSERT); | |
46c73d9a DB |
2465 | if (*loc != NULL) |
2466 | free (*loc); | |
a3648cfc DB |
2467 | *(struct used_part_map **) loc = h; |
2468 | } | |
2469 | ||
c75ab022 DB |
2470 | |
2471 | /* Given a variable uid, UID, get or create the entry in the used portions | |
2472 | table for the variable. */ | |
2473 | ||
2474 | static used_part_t | |
2475 | get_or_create_used_part_for (size_t uid) | |
2476 | { | |
2477 | used_part_t up; | |
a3648cfc | 2478 | if ((up = up_lookup (uid)) == NULL) |
c75ab022 DB |
2479 | { |
2480 | up = xcalloc (1, sizeof (struct used_part)); | |
2481 | up->minused = INT_MAX; | |
2482 | up->maxused = 0; | |
31617ef1 DB |
2483 | up->explicit_uses = false; |
2484 | up->implicit_uses = false; | |
c75ab022 | 2485 | } |
a3648cfc | 2486 | |
c75ab022 DB |
2487 | return up; |
2488 | } | |
2489 | ||
31617ef1 | 2490 | |
e8ca4159 DN |
2491 | /* Create and return a structure sub-variable for field FIELD of |
2492 | variable VAR. */ | |
2493 | ||
2494 | static tree | |
2495 | create_sft (tree var, tree field) | |
2496 | { | |
2497 | var_ann_t ann; | |
2498 | tree subvar = create_tmp_var_raw (TREE_TYPE (field), "SFT"); | |
2499 | ||
2500 | /* We need to copy the various flags from VAR to SUBVAR, so that | |
2501 | they are is_global_var iff the original variable was. */ | |
2502 | DECL_CONTEXT (subvar) = DECL_CONTEXT (var); | |
2503 | DECL_EXTERNAL (subvar) = DECL_EXTERNAL (var); | |
2504 | TREE_PUBLIC (subvar) = TREE_PUBLIC (var); | |
2505 | TREE_STATIC (subvar) = TREE_STATIC (var); | |
2506 | TREE_READONLY (subvar) = TREE_READONLY (var); | |
2507 | ||
2508 | /* Add the new variable to REFERENCED_VARS. */ | |
2509 | ann = get_var_ann (subvar); | |
2510 | ann->mem_tag_kind = STRUCT_FIELD; | |
2511 | ann->type_mem_tag = NULL; | |
2512 | add_referenced_tmp_var (subvar); | |
2513 | ||
2514 | return subvar; | |
2515 | } | |
2516 | ||
2517 | ||
c75ab022 DB |
2518 | /* Given an aggregate VAR, create the subvariables that represent its |
2519 | fields. */ | |
2520 | ||
2521 | static void | |
2522 | create_overlap_variables_for (tree var) | |
2523 | { | |
2845f02a | 2524 | VEC(fieldoff_s,heap) *fieldstack = NULL; |
c75ab022 | 2525 | used_part_t up; |
a3648cfc | 2526 | size_t uid = DECL_UID (var); |
c75ab022 | 2527 | |
a3648cfc | 2528 | if (!up_lookup (uid)) |
c75ab022 DB |
2529 | return; |
2530 | ||
a3648cfc | 2531 | up = up_lookup (uid); |
910fdc79 | 2532 | push_fields_onto_fieldstack (TREE_TYPE (var), &fieldstack, 0, NULL); |
2845f02a | 2533 | if (VEC_length (fieldoff_s, fieldstack) != 0) |
c75ab022 DB |
2534 | { |
2535 | subvar_t *subvars; | |
2845f02a | 2536 | fieldoff_s *fo; |
c75ab022 | 2537 | bool notokay = false; |
31617ef1 | 2538 | int fieldcount = 0; |
c75ab022 | 2539 | int i; |
31617ef1 DB |
2540 | HOST_WIDE_INT lastfooffset = -1; |
2541 | HOST_WIDE_INT lastfosize = -1; | |
2542 | tree lastfotype = NULL_TREE; | |
c75ab022 DB |
2543 | |
2544 | /* Not all fields have DECL_SIZE set, and those that don't, we don't | |
2545 | know their size, and thus, can't handle. | |
2546 | The same is true of fields with DECL_SIZE that is not an integer | |
2547 | constant (such as variable sized fields). | |
2548 | Fields with offsets which are not constant will have an offset < 0 | |
2549 | We *could* handle fields that are constant sized arrays, but | |
2550 | currently don't. Doing so would require some extra changes to | |
2551 | tree-ssa-operands.c. */ | |
2552 | ||
2845f02a | 2553 | for (i = 0; VEC_iterate (fieldoff_s, fieldstack, i, fo); i++) |
c75ab022 DB |
2554 | { |
2555 | if (!DECL_SIZE (fo->field) | |
2556 | || TREE_CODE (DECL_SIZE (fo->field)) != INTEGER_CST | |
2557 | || TREE_CODE (TREE_TYPE (fo->field)) == ARRAY_TYPE | |
2558 | || fo->offset < 0) | |
2559 | { | |
2560 | notokay = true; | |
2561 | break; | |
2562 | } | |
31617ef1 | 2563 | fieldcount++; |
c75ab022 | 2564 | } |
31617ef1 DB |
2565 | |
2566 | /* The current heuristic we use is as follows: | |
2567 | If the variable has no used portions in this function, no | |
2568 | structure vars are created for it. | |
2569 | Otherwise, | |
2570 | If the variable has less than SALIAS_MAX_IMPLICIT_FIELDS, | |
2571 | we always create structure vars for them. | |
2572 | If the variable has more than SALIAS_MAX_IMPLICIT_FIELDS, and | |
2573 | some explicit uses, we create structure vars for them. | |
2574 | If the variable has more than SALIAS_MAX_IMPLICIT_FIELDS, and | |
2575 | no explicit uses, we do not create structure vars for them. | |
2576 | */ | |
2577 | ||
2578 | if (fieldcount >= SALIAS_MAX_IMPLICIT_FIELDS | |
2579 | && !up->explicit_uses) | |
2580 | { | |
2581 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
2582 | { | |
2583 | fprintf (dump_file, "Variable "); | |
2584 | print_generic_expr (dump_file, var, 0); | |
2585 | fprintf (dump_file, " has no explicit uses in this function, and is > SALIAS_MAX_IMPLICIT_FIELDS, so skipping\n"); | |
2586 | } | |
2587 | notokay = true; | |
2588 | } | |
2589 | ||
2845f02a | 2590 | /* Bail out, if we can't create overlap variables. */ |
c75ab022 DB |
2591 | if (notokay) |
2592 | { | |
2845f02a | 2593 | VEC_free (fieldoff_s, heap, fieldstack); |
c75ab022 DB |
2594 | return; |
2595 | } | |
2845f02a | 2596 | |
c75ab022 DB |
2597 | /* Otherwise, create the variables. */ |
2598 | subvars = lookup_subvars_for_var (var); | |
c75ab022 | 2599 | |
910fdc79 | 2600 | sort_fieldstack (fieldstack); |
31617ef1 | 2601 | |
2845f02a NS |
2602 | for (i = VEC_length (fieldoff_s, fieldstack); |
2603 | VEC_iterate (fieldoff_s, fieldstack, --i, fo);) | |
c75ab022 | 2604 | { |
31617ef1 | 2605 | subvar_t sv; |
c75ab022 | 2606 | HOST_WIDE_INT fosize; |
31617ef1 | 2607 | tree currfotype; |
c75ab022 | 2608 | |
c75ab022 | 2609 | fosize = TREE_INT_CST_LOW (DECL_SIZE (fo->field)); |
31617ef1 DB |
2610 | currfotype = TREE_TYPE (fo->field); |
2611 | ||
2612 | /* If this field isn't in the used portion, | |
2613 | or it has the exact same offset and size as the last | |
2614 | field, skip it. */ | |
2615 | ||
2616 | if (((fo->offset <= up->minused | |
2617 | && fo->offset + fosize <= up->minused) | |
2618 | || fo->offset >= up->maxused) | |
2619 | || (fo->offset == lastfooffset | |
2620 | && fosize == lastfosize | |
2621 | && currfotype == lastfotype)) | |
2845f02a | 2622 | continue; |
31617ef1 | 2623 | sv = ggc_alloc (sizeof (struct subvar)); |
c75ab022 DB |
2624 | sv->offset = fo->offset; |
2625 | sv->size = fosize; | |
2626 | sv->next = *subvars; | |
e8ca4159 DN |
2627 | sv->var = create_sft (var, fo->field); |
2628 | ||
c75ab022 DB |
2629 | if (dump_file) |
2630 | { | |
2631 | fprintf (dump_file, "structure field tag %s created for var %s", | |
2632 | get_name (sv->var), get_name (var)); | |
2633 | fprintf (dump_file, " offset " HOST_WIDE_INT_PRINT_DEC, | |
2634 | sv->offset); | |
2635 | fprintf (dump_file, " size " HOST_WIDE_INT_PRINT_DEC, | |
2636 | sv->size); | |
2637 | fprintf (dump_file, "\n"); | |
c75ab022 DB |
2638 | } |
2639 | ||
31617ef1 DB |
2640 | lastfotype = currfotype; |
2641 | lastfooffset = fo->offset; | |
2642 | lastfosize = fosize; | |
c75ab022 | 2643 | *subvars = sv; |
c75ab022 | 2644 | } |
d19e9499 DB |
2645 | |
2646 | /* Once we have created subvars, the original is no longer call | |
2647 | clobbered on its own. Its call clobbered status depends | |
2648 | completely on the call clobbered status of the subvars. | |
2649 | ||
2650 | add_referenced_var in the above loop will take care of | |
2651 | marking subvars of global variables as call clobbered for us | |
2652 | to start, since they are global as well. */ | |
2653 | clear_call_clobbered (var); | |
c75ab022 | 2654 | } |
d19e9499 | 2655 | |
2845f02a | 2656 | VEC_free (fieldoff_s, heap, fieldstack); |
c75ab022 DB |
2657 | } |
2658 | ||
2659 | ||
2660 | /* Find the conservative answer to the question of what portions of what | |
2661 | structures are used by this statement. We assume that if we have a | |
2662 | component ref with a known size + offset, that we only need that part | |
2663 | of the structure. For unknown cases, or cases where we do something | |
2664 | to the whole structure, we assume we need to create fields for the | |
2665 | entire structure. */ | |
2666 | ||
2667 | static tree | |
2668 | find_used_portions (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED) | |
2669 | { | |
2670 | switch (TREE_CODE (*tp)) | |
2671 | { | |
2672 | case COMPONENT_REF: | |
2673 | { | |
2674 | HOST_WIDE_INT bitsize; | |
2675 | HOST_WIDE_INT bitpos; | |
2676 | tree offset; | |
2677 | enum machine_mode mode; | |
2678 | int unsignedp; | |
2679 | int volatilep; | |
2680 | tree ref; | |
2681 | ref = get_inner_reference (*tp, &bitsize, &bitpos, &offset, &mode, | |
2682 | &unsignedp, &volatilep, false); | |
2683 | if (DECL_P (ref) && offset == NULL && bitsize != -1) | |
2684 | { | |
a3648cfc | 2685 | size_t uid = DECL_UID (ref); |
c75ab022 DB |
2686 | used_part_t up; |
2687 | ||
2688 | up = get_or_create_used_part_for (uid); | |
2689 | ||
2690 | if (bitpos <= up->minused) | |
2691 | up->minused = bitpos; | |
2692 | if ((bitpos + bitsize >= up->maxused)) | |
2693 | up->maxused = bitpos + bitsize; | |
2694 | ||
31617ef1 | 2695 | up->explicit_uses = true; |
a3648cfc | 2696 | up_insert (uid, up); |
c75ab022 DB |
2697 | |
2698 | *walk_subtrees = 0; | |
2699 | return NULL_TREE; | |
2700 | } | |
2701 | else if (DECL_P (ref)) | |
2702 | { | |
2703 | if (DECL_SIZE (ref) | |
2704 | && var_can_have_subvars (ref) | |
2705 | && TREE_CODE (DECL_SIZE (ref)) == INTEGER_CST) | |
2706 | { | |
2707 | used_part_t up; | |
a3648cfc | 2708 | size_t uid = DECL_UID (ref); |
c75ab022 DB |
2709 | |
2710 | up = get_or_create_used_part_for (uid); | |
2711 | ||
2712 | up->minused = 0; | |
2713 | up->maxused = TREE_INT_CST_LOW (DECL_SIZE (ref)); | |
2714 | ||
31617ef1 DB |
2715 | up->implicit_uses = true; |
2716 | ||
a3648cfc | 2717 | up_insert (uid, up); |
c75ab022 DB |
2718 | |
2719 | *walk_subtrees = 0; | |
2720 | return NULL_TREE; | |
2721 | } | |
2722 | } | |
2723 | } | |
2724 | break; | |
a5eadacc DB |
2725 | /* This is here to make sure we mark the entire base variable as used |
2726 | when you take its address. Because our used portion analysis is | |
2727 | simple, we aren't looking at casts or pointer arithmetic to see what | |
2728 | happens when you take the address. */ | |
2729 | case ADDR_EXPR: | |
2730 | { | |
2731 | tree var = get_base_address (TREE_OPERAND (*tp, 0)); | |
2732 | ||
2733 | if (var | |
2734 | && DECL_P (var) | |
2735 | && DECL_SIZE (var) | |
2736 | && var_can_have_subvars (var) | |
2737 | && TREE_CODE (DECL_SIZE (var)) == INTEGER_CST) | |
2738 | { | |
2739 | used_part_t up; | |
a3648cfc | 2740 | size_t uid = DECL_UID (var); |
a5eadacc DB |
2741 | |
2742 | up = get_or_create_used_part_for (uid); | |
2743 | ||
2744 | up->minused = 0; | |
2745 | up->maxused = TREE_INT_CST_LOW (DECL_SIZE (var)); | |
2746 | up->implicit_uses = true; | |
2747 | ||
a3648cfc | 2748 | up_insert (uid, up); |
a5eadacc DB |
2749 | *walk_subtrees = 0; |
2750 | return NULL_TREE; | |
2751 | } | |
2752 | } | |
2753 | break; | |
c75ab022 DB |
2754 | case VAR_DECL: |
2755 | case PARM_DECL: | |
098209a9 | 2756 | case RESULT_DECL: |
c75ab022 DB |
2757 | { |
2758 | tree var = *tp; | |
2759 | if (DECL_SIZE (var) | |
2760 | && var_can_have_subvars (var) | |
2761 | && TREE_CODE (DECL_SIZE (var)) == INTEGER_CST) | |
2762 | { | |
2763 | used_part_t up; | |
a3648cfc | 2764 | size_t uid = DECL_UID (var); |
c75ab022 DB |
2765 | |
2766 | up = get_or_create_used_part_for (uid); | |
2767 | ||
2768 | up->minused = 0; | |
2769 | up->maxused = TREE_INT_CST_LOW (DECL_SIZE (var)); | |
31617ef1 | 2770 | up->implicit_uses = true; |
c75ab022 | 2771 | |
a3648cfc | 2772 | up_insert (uid, up); |
c75ab022 DB |
2773 | *walk_subtrees = 0; |
2774 | return NULL_TREE; | |
2775 | } | |
2776 | } | |
2777 | break; | |
2778 | ||
2779 | default: | |
2780 | break; | |
2781 | ||
2782 | } | |
2783 | return NULL_TREE; | |
2784 | } | |
2785 | ||
c75ab022 DB |
2786 | /* Create structure field variables for structures used in this function. */ |
2787 | ||
2788 | static void | |
2789 | create_structure_vars (void) | |
2790 | { | |
2791 | basic_block bb; | |
b9d33488 DB |
2792 | safe_referenced_var_iterator rvi; |
2793 | VEC (tree, heap) *varvec = NULL; | |
a3648cfc | 2794 | tree var; |
c75ab022 | 2795 | |
a3648cfc DB |
2796 | used_portions = htab_create (10, used_part_map_hash, used_part_map_eq, |
2797 | free_used_part_map); | |
c75ab022 DB |
2798 | |
2799 | FOR_EACH_BB (bb) | |
2800 | { | |
2801 | block_stmt_iterator bsi; | |
2802 | for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) | |
2803 | { | |
2804 | walk_tree_without_duplicates (bsi_stmt_ptr (bsi), | |
2805 | find_used_portions, | |
2806 | NULL); | |
2807 | } | |
2808 | } | |
b9d33488 | 2809 | FOR_EACH_REFERENCED_VAR_SAFE (var, varvec, rvi) |
c75ab022 | 2810 | { |
c75ab022 DB |
2811 | /* The C++ FE creates vars without DECL_SIZE set, for some reason. */ |
2812 | if (var | |
2813 | && DECL_SIZE (var) | |
2814 | && var_can_have_subvars (var) | |
2815 | && var_ann (var)->mem_tag_kind == NOT_A_TAG | |
2816 | && TREE_CODE (DECL_SIZE (var)) == INTEGER_CST) | |
2817 | create_overlap_variables_for (var); | |
2818 | } | |
a3648cfc | 2819 | htab_delete (used_portions); |
b9d33488 | 2820 | VEC_free (tree, heap, varvec); |
c75ab022 | 2821 | |
c75ab022 DB |
2822 | } |
2823 | ||
2824 | static bool | |
2825 | gate_structure_vars (void) | |
2826 | { | |
2827 | return flag_tree_salias != 0; | |
2828 | } | |
2829 | ||
2830 | struct tree_opt_pass pass_create_structure_vars = | |
2831 | { | |
2832 | "salias", /* name */ | |
2833 | gate_structure_vars, /* gate */ | |
2834 | create_structure_vars, /* execute */ | |
2835 | NULL, /* sub */ | |
2836 | NULL, /* next */ | |
2837 | 0, /* static_pass_number */ | |
2838 | 0, /* tv_id */ | |
2839 | PROP_cfg, /* properties_required */ | |
2840 | 0, /* properties_provided */ | |
2841 | 0, /* properties_destroyed */ | |
2842 | 0, /* todo_flags_start */ | |
2843 | TODO_dump_func, /* todo_flags_finish */ | |
2844 | 0 /* letter */ | |
2845 | }; |